Lenguaje de programación donde cada expresión tiene sentido

Por recomendación, vuelvo a publicar esto desde Stack Overflow .

Recientemente he estado pensando en el siguiente tema.

Considere el código para un estándar "¡Hola, mundo!" programa:

main()
{
    printf("Hello World");

}

Ahora, casi cualquier cambio en este código lo hará completamente inútil, de hecho, casi todos los cambios evitarán que el código se compile. Por ejemplo:

main(5
{
    printf("Hello World");

}

Ahora a la pregunta real. ¿Existe un lenguaje de programación en el que cada combinación posible de símbolos, es decir, cada expresión, tenga sentido? Intenté pensar en algún tipo de solución y se me ocurrieron dos:

1. Postfix con un número limitado de variables. Esencialmente, todas las variables ya están definidas antes de escribir cualquier código y debe trabajar solo con ellas. Teóricamente, puede realizar un número arbitrario de operaciones formando una cadena de muchos programas simples, cada uno de los cuales proporciona resultados a los demás. El código podría escribirse como una serie de caracteres en notación postfix;

2. "Postfix" con una pila de variables. Las variables se almacenan en una pila; cada operación toma dos variables desde arriba y coloca el resultado en su lugar. El programa finaliza cuando alcanza la última operación o variable.

Personalmente, odio ambos. No solo son limitados, son poco elegantes. Ni siquiera son soluciones reales, más como soluciones alternativas, esencialmente "deslocalizando" parte del trabajo a un proceso externo.

¿Alguien tiene alguna otra idea de cómo resolver este problema?

Redcode, el lenguaje ensamblador detrás de codewars, fue escrito explícitamente para tener muy pocas instrucciones de detención, porque el código a menudo se destroza antes de que finalmente se dé por vencido, y cuantas más oportunidades tenga para detenerse, menos interesante será el juego.

Usted ve muy pocos lenguajes de este tipo en la práctica porque no solo queremos que se ejecute un programa, queremos que se ejecute de la manera que esperamos. Si puede hacer un error tipográfico y cambiar la forma en que se ejecutó el programa, debe ser aceptablemente cercano al comportamiento esperado original, o los programadores con frustración.

Hay cierta precedencia para tales cosas al usar lenguajes naturales en lugar de lenguajes formales, pero no es lo que yo llamaría un campo grande cuando lo comparas con el uso de lenguajes formales. Si está interesado en dichos lenguajes de programación, la comunidad de procesamiento de lenguaje natural es donde buscaría.

Otro campo que podría observar es la genética. Hay notablemente pocas secuencias genéticas que son simplemente inválidas. Muchos de ellos que no son muy efectivos en las reproducciones, pero muy pocos inválidos.

La idea de una máquina universal de Turing utiliza un "lenguaje de programación" tal: una codificación de máquinas de Turing como números naturales, representada, por ejemplo, en binario, de modo que cada número natural denota una máquina de Turing, es decir, un programa. En este lenguaje, cada cadena de ceros y unos es un programa.

Si le preocupa que algunos números puedan codificar programas no válidos, puede desviarse de la siguiente manera. Imagine escribir todas las cadenas en el conjunto de caracteres de su lenguaje de programación (por ejemplo, Java), en orden lexicográfico, comenzando con cadenas de longitud uno, luego dos, luego tres, ... Luego, cree un nuevo lenguaje de programación dejando el número representar el º cadena en la lista que tenga un programa Java válido. En el nuevo lenguaje de programación, los programas son solo números naturales y cada número natural es un programa válido.$n$$n$

Estoy seguro de que también hay lenguajes de programación esotéricos donde cada cadena es un programa; sin embargo, si solo está pidiendo una lista de esos, creo que su pregunta está fuera de tema aquí.

Ampliar un lenguaje de programación para que cada expresión tenga sentido siempre es posible, pero no interesante. Por ejemplo, puede asignar el significado "no hacer nada" a cualquier expresión que el idioma original rechace.

El diseño de un lenguaje de programación en el que cada expresión tenga sentido de una manera "puede ejecutarlo" no es particularmente útil. Un buen lenguaje de programación no es solo uno donde un mono puede escribir en un teclado y escribir un programa válido, sino uno en el que un programador puede escribir fácilmente el programa que pretendía escribir. Escribir programas válidos no es la parte difícil de la programación: la parte difícil es escribir un programa que realice lo que se esperaba de él. Rechazar programas obviamente incorrectos es muy útil a este respecto.

Otra forma de abordar esto es definir completamente la semántica de todas las entradas posibles, incluida la especificación de qué tiempo de compilación, tiempo de carga o error de tiempo de ejecución se debe generar para cada entrada, si corresponde. Es decir, "abortar el programa después de imprimir Syntax error at line 42en la secuencia de error estándar" es parte de la semántica definida del lenguaje. Cada expresión "tiene sentido" en el sentido de que tiene un significado definido. ¿Es ese un significado útil? Tal vez, después de todo, si el programa obviamente está equivocado, rechazarlo es útil.

Echa un vistazo a Jot , un lenguaje completo de Turing basado en la lógica combinatoria, donde cada secuencia de 0s y 1s (incluida una secuencia vacía) es un programa válido.

Un buen ejemplo es el espacio en blanco . En el lenguaje apropiado, cualquier combinación de operadores es válida. Los operadores son espacio, tabulación y nueva línea (específicamente "\ n"). Todos los demás personajes se consideran comentarios .

Esta respuesta, y de hecho su pregunta (así como toda esta página web) son ejemplos de programas válidos de espacios en blanco (aunque pueden no hacer nada particularmente interesante).

Me gustaría abordar la idea que muchos carteles han dado, que tal lenguaje sería "inútil". Quizás sería inútil que los humanos escriban, manualmente, con la intención de resolver alguna tarea en particular. Sin embargo, a pesar de ser un caso de uso mayoritario para lenguajes de programación, ciertamente no es el único caso de uso. Varios casos de uso vienen a la mente donde dicho lenguaje es útil, y podemos buscar en esos campos ejemplos de dichos lenguajes.

En primer lugar, la alusión de Cort Ammon a la genética es acertada: la transformación del programa en la pregunta (en sustitución )de 5) puede verse como una mutación . Este tipo de manipulación es común en el campo de la computación evolutiva ; en particular, los algoritmos genéticos realizan tales transformaciones en cadenas , mientras que la programación genética transforma los programas . En cualquier caso, generalmente queremos asignar significado a cada posibilidad, ya que eso producirá el espacio de búsqueda más compacto.

Los algoritmos genéticos dependen de algún tipo de función de evaluación para cadenas; Si utilizamos un intérprete de lenguaje de programación como nuestra función de evaluación, entonces tenemos un escenario en el que es útil un lenguaje de programación que asigne significado a todas las cadenas posibles. En la programación genética, se supone que nuestra función de evaluación es un intérprete de lenguaje de programación, pero podemos elegir varias representaciones para nuestros programas; por ejemplo, muchos sistemas operan en árboles de sintaxis abstracta. Si elegimos cadenas como nuestra representación, recuperamos el mismo escenario que con los algoritmos genéticos.

Otra situación en la que podemos querer que cada cadena sea un programa válido es cuando enumeramos programas. Esto está relacionado con la biyección mencionada por CodesInChaos, pero podemos preferir operar con cadenas en lugar de números naturales por varias razones:

• Si hay alguna estructura en el lenguaje, por ejemplo. podemos asignar significado a subcadenas, esto puede perderse al traducir a números naturales. En este caso, podemos preferir usar cadenas para razonar y transformar subcadenas localmente, en lugar de representar el programa completo como un número. Esto es análogo a cómo podríamos preferir usar operaciones bit a bit en una expresión int en lugar de expresiones aritméticas, cuando cada bit tiene un significado individual. Esto es básicamente una generalización del escenario evolutivo.
• Es posible que queramos generar los programas a pedido; por ejemplo, podríamos comenzar a ejecutar un programa completamente indeterminado y solo generar (por ejemplo, aleatoriamente) las instrucciones individuales (por ejemplo, caracteres) cuando / si el puntero de instrucción llega a ellas. Esto es común en la teoría de la información algorítmica, donde el programa es una cinta de máquina de Turing, y el objetivo es caracterizar el comportamiento de los programas generados aleatoriamente. Por ejemplo, podemos formular el Solomonoff antes de cadenas arbitrarias como la probabilidad de que una máquina Turing universal con una cinta aleatoria produzca esa cadena.

En términos de lenguajes de ejemplo, muchos sistemas de cálculo evolutivo se basan en lenguajes de pila como la familia Push . Estos tienden a permitir flujos arbitrarios de tokens (que podríamos representar como caracteres individuales). A veces (como en el ejemplo Brainfuck de BrainSlugs83) existen restricciones para equilibrar los paréntesis; sin embargo, podemos relacionar esto con los programas de auto delimitación , ya que una cadena como [no puede ser un programa válido , pero es un prefijo de programa válido . Si imaginamos un compilador / intérprete leyendo el código fuente de stdin, entonces no rechazará una cadena como [, simplemente esperará más entrada antes de continuar.

Lenguajes como Binary Combinatory Logic y Binary Lambda Calculus surgieron directamente del trabajo en la teoría de información algorítmica, por ejemplo. de http://tromp.github.io/cl/cl.html

Este diseño de una computadora universal minimalista fue motivado por mi deseo de llegar a una definición concreta de la complejidad de Kolmogorov, que estudia la aleatoriedad de los objetos individuales.

Los lenguajes de programación reales deben transmitir significado a las personas , no a las computadoras. Como un montón de textos divertidos con letras barajadas casi al azar flotando alrededor del 'ëet show, la gente puede leer galimatías y darle sentido, incluso sin darse cuenta abiertamente de la destrucción. Solo piense en lo difícil que es encontrar errores tipográficos y otros errores similares en los textos.

Un lenguaje de programación como el que pides hará que las personas entiendan lo que quieren leer, no lo que está escrito. La depuración en idiomas donde hay un conjunto limitado de declaraciones legales, donde no hay mucha ambigüedad posible, ya es bastante difícil. Los buenos idiomas reducen las posibles interpretaciones debido, por ejemplo, a símbolos o errores tipográficos transpuestos. Los lenguajes naturales también son conocidos por su redundancia, por el mismo tipo de razón.

En el lenguaje de programación Brainfuck , casi todas las expresiones binarias posibles pueden interpretarse como un programa. - Es decir, podría tomar un programa completamente bueno, escribir un montón de basura en él y, aún así, sería compilable / interpretable sin ningún problema.

( Editar: Resulta que tienes que hacer coincidir los corchetes de apertura y cierre, pero de lo contrario, lo anterior es cierto).

Lo logra a través de estos dos métodos simples:

1. Todos los comandos que entiende son de un solo byte (en BF son todos caracteres ASCII individuales, por ejemplo *).

2. Todos los caracteres que no entiende, se descartan como comentarios.

El lenguaje de programación es Turing completo (es decir, puede hacer cualquier cosa que cualquier otro lenguaje pueda hacer).

*: Resulta que no todos los comandos BF son un solo byte ASCII, es decir, los corchetes DEBEN coincidir, por lo que ese idioma no cumple con el primer criterio allí. - Pero cualquier lenguaje que cumpla con ambos criterios satisfaría lo que pide el OP.