Me encontré con un problema extraño al escribir un intérprete que (debería) engancharse a programas / funciones externas: las funciones en 'C' y 'C ++' no pueden conectar funciones variadas , por ejemplo, no puedo hacer una función que llame a 'printf' con exactamente los mismos argumentos que obtuvo, y en su lugar tiene que llamar a una versión alternativa que tome un objeto variadic. Esto es muy problemático ya que quiero poder hacer un objeto que contenga un gancho anónimo.

Entonces, pensé que esto era extraño ya que Forth , JavaScript , y quizás una gran cantidad de otros idiomas pueden hacer esto muy fácilmente sin tener que recurrir al lenguaje ensamblador / código de máquina. Dado que otros lenguajes pueden hacer esto tan fácilmente, ¿eso significa que la clase de problemas que cada lenguaje de programación puede resolver en realidad varía según el idioma, a pesar de que estos lenguajes están completos ?

Turing idiomas completos pueden calcular el mismo conjunto de funciones , que es el conjunto de funciones parciales recursivas generales. Eso es.$\mathbb{N}^k \rightarrow \mathbb{N}$

Esto no dice nada sobre las características del lenguaje. Una máquina de Turing tiene características de composición muy limitadas. El cálculo tipo es mucho más compositivo, pero carece de muchas características que se encuentran comúnmente en los idiomas modernos.$\lambda$

La integridad de Turing no dice nada acerca de tener tipos, matrices integradas / enteros / diccionarios, capacidades de entrada / salida, acceso a la red, subprocesamiento múltiple, asignación dinámica, ...

Solo porque Java no tiene la característica X (por ejemplo, macros, tipos de rango superior o tipos dependientes), no deja de ser Turing completo de repente.

La integridad de Turing y la expresividad del lenguaje son dos nociones diferentes.

La integridad de Turing es un concepto abstracto de computabilidad. Si un idioma es completo de Turing, entonces es capaz de hacer cualquier cálculo que cualquier otro lenguaje completo de Turing puede hacer.

Sin embargo, esto no dice qué tan conveniente es hacerlo. Algunas características que son fáciles en algunos idiomas pueden ser muy difíciles en otros, debido a las opciones de diseño. Turing completo sólo dice que usted puede hacer el cálculo. Como ejemplo extremo, puede ser difícil enganchar funciones varadic en C ++, pero es posible escribir un intérprete de JavaScript en C ++ que pueda enganchar funciones variadas.

El diseño del lenguaje es un arte bastante interesante. Uno de los pasos principales que uno tiene que seguir es identificar qué comportamientos desea formar la columna vertebral de su lenguaje. Estas conductas son cosas que son fáciles de hacer en su idioma porque están integradas en la planta baja. Tomamos decisiones de diseño sobre qué características incluir en cada idioma.

En cuanto a su ejemplo particular, cuando se desarrolló C, fue diseñado para funcionar muy cerca de la forma en que funcionaban los lenguajes ensambladores de la época. Las funciones variadas simplemente empujaron argumentos a la pila, con muy poca seguridad de tipografía. La implementación de estas funciones variadas se dejó al compilador, para garantizar la máxima portabilidad. En consecuencia, se hicieron muy pocas suposiciones sobre las capacidades del hardware. Para cuando llegó JavaScript, la escena había cambiado. Ya opera en una máquina virtual como lenguaje interpretado, por lo que el equilibrio cambia hacia la conveniencia. Permitir el enganche de funciones variadas se vuelve razonable. Incluso en el caso de JavaScript compilado Just In Time, nuestros compiladores están dispuestos a almacenar mucha más información adicional sobre los argumentos que los compiladores C de antaño estaban dispuestos a almacenar.

Piense en los lenguajes de programación como diferentes vehículos terrestres: bicicletas, automóviles, aerodeslizadores, trenes.

Turing Completeness dice que "este vehículo puede ir a cualquier lugar al que pueda ir cualquier otro vehículo". Es decir, puede calcular todas las mismas funciones. Entrada a salida, de principio a fin.

Pero, esa declaración no dice nada acerca de cómo llegar allí. Podría estar en rieles, podría estar en carreteras, podría estar en el aire. Del mismo modo, Turing Completeness no dice nada acerca de cómo se calcula una función. Puede usar recursividad, iteración o algunos autómatas celulares extraños. Puede usar tipos o no, puede usar técnicas dinámicas o estáticas. Pero, si todo lo que considera son funciones (o conjuntos / lenguajes formales) que puede calcular, siempre que Turing Complete, estas características le otorgan el mismo poder.

Lo que esencialmente está preguntando es la diferencia entre el poder computacional y lo que comúnmente se llama poder expresivo (o simplemente expresividad ) de un lenguaje (o sistema de cómputo).

Potencia de cálculo

El poder computacional se refiere a qué tipos de problemas puede calcular el lenguaje. La clase de potencia computacional más conocida es la que es equivalente a una máquina universal de Turing . Hay una gran cantidad de otros sistemas de computación, tales como acceso aleatorio Máquinas , λ-cálculo , SK cálculo combinador , funciones mu-recursivo , WHILEprogramas, y muchos otros. Y resulta que todos estos pueden simularse entre sí, lo que significa que todos tienen el mismo poder computacional.

Esto da lugar a la Tesis de Church-Turing (llamada así por Alonzo Church que creó el cálculo λ y Alan Turing que creó la Máquina Universal de Turing). La tesis de la Iglesia de Turing es una hipótesis sobre la computabilidad con dos aspectos:

1. todos los sistemas de computación capaces de computación general son igualmente poderosos y
2. un ser humano que sigue un algoritmo puede calcular exactamente las funciones que una máquina de Turing (y, por lo tanto, cualquiera de los otros sistemas) puede calcular.

Sin embargo, el segundo es más importante en el campo de la filosofía de la mente que la informática.

Sin embargo, hay dos cosas que la Tesis de Turing de la Iglesia no dice, que son muy relevantes para su pregunta:

1. qué tan eficientes son las diversas simulaciones y
2. cuán conveniente es la codificación de un problema.

Un ejemplo simple para (1): en una máquina de acceso aleatorio, copiar una matriz requiere un tiempo proporcional a la longitud de la matriz. Sin embargo, en una máquina de Turing, lleva un tiempo proporcional al cuadrado de la longitud de la matriz, porque la máquina de Turing no tiene acceso aleatorio a la memoria, solo puede moverse a través de la cinta una celda a la vez. Por lo tanto, necesita moverse a través de los n elementos de la matriz n veces para copiarlos. Por lo tanto, diferentes modelos de cálculo pueden tener diferentes características de rendimiento, incluso en el caso asintótico, donde tratamos de abstraernos de los detalles de implementación.

Abundan los ejemplos para (2): tanto el cálculo λ como Python son completos de Turing. ¿Pero prefieres escribir un programa en Python o en cálculo λ?

También hay una tercera arruga que he eludido hasta ahora: todos esos sistemas originales fueron diseñados por lógicos, filósofos o matemáticos, no por informáticos ... simplemente porque las computadoras y, por lo tanto, la informática no existían. Todo esto se remonta a principios de la década de 1930, incluso antes de los primeros experimentos de Konrad Zuse (que de todos modos no eran programables y / o Turing completos). Solo hablan de "funciones computables en los números naturales".

Ahora, como resultado, hay muchas cosas que puedes expresar como funciones en números naturales; después de todo, nuestras computadoras modernas incluso funcionan con mucho menos que eso (básicamente 3-4 funciones en los números 0 y 1, y eso es todo ), pero, por ejemplo, ¿qué función calcula un sistema operativo?

Esta noción de E / S, efectos secundarios, interactuando con el medio ambiente, no está captada por la idea de "funciones sobre números naturales". Y, sin embargo, es algo importante, ya que, como Simon Peyton Jones dijo una vez: "Todo lo que hace una función pura sin efectos secundarios es calentar tu CPU" , a lo que un miembro de la audiencia respondió "en realidad, eso es un lado -efecto, también! "

Edwin Brady , el diseñador de Idris , (solo la mitad) usa en broma (no sé si lo inventó) el término "Tetris-complete" para expresar esta diferencia entre "puede calcular cualquier función computable en números naturales" y "puede ser usado para escribir programas no triviales que interactúan con el entorno ". Aún más irónicamente, demuestra esto al implementar un clon de Space Invaders en Idris , pero dice que confía en que Tetris se reduce a Space Invaders.

Otra cosa a destacar es que no solo la equivalencia de Turing no es necesariamente suficiente para hablar sobre la escritura de programas "útiles", sino que puede que OTOH ni siquiera sea necesario . Por ejemplo, SQL solo se ha convertido en equivalente de Turing con ANSI SQL: 1999 , pero aún era útil antes de eso. De hecho, algunos podrían argumentar que hacer que sea equivalente a Turing no ha aumentado su utilidad en absoluto. Hay muchos lenguajes específicos de dominio que no son equivalentes a Turing. El lenguaje de descripción de datos generalmente no es (y no debería ser). Total Languages ​​obviamente no puede ser equivalente a Turing, pero aún puede escribir bucles de eventos, servidores web o sistemas operativos en ellos. También hay idiomas que son equivalentes a Turing pero que en realidad se consideran un error.

Entonces, en general, la equivalencia de Turing no es terriblemente interesante, a menos que desee analizar estáticamente los programas.

Expresividad

Suponiendo que nuestro sistema de computación es computacionalmente lo suficientemente poderoso como para resolver nuestro problema, lo que tenemos que hacer a continuación es expresar nuestro algoritmo para resolver ese problema en algún tipo de notación formal para ese sistema. En otras palabras: necesitamos escribir un programa en algún lenguaje de computadora. Ahí es donde entra en juego la noción de expresividad .

Se refiere esencialmente a lo "fácil" o "agradable" que es escribir nuestro programa en nuestro lenguaje de programación particular. Como puede ver, la noción es bastante vaga, subjetiva y más psicológica que técnica.

Sin embargo, hay intentos de definiciones más precisas. El más famoso (y el más riguroso que conozco) es de Matthias Felleisen en su artículo Sobre el poder expresivo de los lenguajes de programación (las dos primeras páginas contienen una introducción suave, el resto del documento es más carnoso).

La intuición principal es la siguiente: cuando se traduce un programa de un idioma a otro idioma, algunos de los cambios que necesita realizar están contenidos localmente (como, por ejemplo, convertir FORbucles en WHILEbucles o bucles en GOTOs condicionales ), y algunos requieren un cambio a lo global estructura del programa.

Cuando puede reemplazar una característica de un idioma con una característica diferente de un idioma diferente por solo transformaciones locales, entonces se dice que estas características no tienen efecto sobre el poder expresivo. Esto se llama azúcar sintáctico .

Por otro lado, si requiere un cambio en la estructura global del programa, se dice que el idioma al que está traduciendo no puede expresar la función. Y se dice que el lenguaje del que está traduciendo es más expresivo (con respecto a esta característica).

Tenga en cuenta que esto proporciona una definición de expresividad objetivamente medible. Tenga en cuenta también que la noción depende del contexto de la característica, y es comparativa. Entonces, si todos los programas en el idioma A se pueden traducir al idioma B con solo cambios locales, y hay al menos un programa en el idioma B que no se puede traducir a A con solo cambios locales, entonces el idioma B es estrictamente más expresivo que el idioma UNA. Sin embargo, el escenario más probable es que muchos programas en ambos idiomas se pueden traducir de un lado a otro, pero hay algunos programas en ambos idiomas que no se pueden traducir al otro. Esto significa que ninguno de los idiomas es estrictamente más expresivo que el otro, solo tienen características diferentes que permiten que diferentes programas se expresen de diferentes maneras.

Esto proporciona una definición formal de lo que significa ser "más expresivo", pero aún no capta las nociones psicológicas detrás del fenómeno. Por ejemplo, el azúcar sintáctico, de acuerdo con este modelo, no aumenta el poder expresivo de un idioma, ya que puede traducirse utilizando solo cambios locales. Sin embargo, sabemos por experiencia que tienen FOR, WHILEy IFdisponible, incluso si son de azúcar sintáctica para simplemente condicionales GOTOmarcas expresar nuestra intención más fácil .

El hecho es que diferentes idiomas tienen características diferentes que hacen que expresar diferentes formas de pensar sobre un problema sea más fácil o más difícil. Y algunas personas pueden encontrar una manera de expresar su intención más fácilmente y otras una manera diferente.

Un ejemplo que encontré en la etiqueta Ruby en StackOverflow: muchos usuarios que siguen la etiqueta Ruby afirman que los bucles son más fáciles de entender que la recursividad y la recursión es solo para programadores funcionales avanzados y los bucles son más intuitivos para los recién llegados, pero he visto múltiples casos de recién llegados que intuitivamente escriben código como este:

def rock_paper_scissors
  get_user_input
  determine_outcome
  print_winner
  rock_paper_scissors # start from the top
end

Lo que generalmente lleva a varias personas a comentar que "esto no funciona" y "lo están haciendo mal" y la "forma correcta" es esta:

def rock_paper_scissors
  loop do
    get_user_input
    determine_outcome
    print_winner
  end
end

Entonces, claramente, hay algunas personas para quienes la recursividad de la cola es una forma más natural de expresar el concepto de "bucle" que las construcciones de bucle.

Resumen

El hecho de que dos idiomas sean equivalentes a Turing dice una y exactamente una cosa: que pueden calcular el mismo conjunto de funciones en números naturales que una máquina de Turing. Eso es.

No dice nada acerca de qué tan rápido calculan esas funciones. No dice nada sobre la facilidad de expresar esas funciones. Y no dice nada acerca de qué más pueden hacer además de calcular funciones en números naturales (por ejemplo, vincular a bibliotecas C, leer la entrada del usuario, escribir la salida en la pantalla).

¿eso significa que la clase de problemas que cada lenguaje de programación puede resolver realmente varía según el idioma, a pesar de que estos lenguajes están completos?

Sí.

1. Hay problemas que no están cubiertos por el término "Turing-complete" (que solo se refiere a las funciones informáticas en números naturales) como la impresión en la pantalla. Se pueden completar dos idiomas en Turing, pero uno puede permitir la impresión en la pantalla y el otro no.
2. Incluso si ambos idiomas pueden resolver los mismos problemas, eso no dice nada sobre cuán compleja es la codificación y lo fácil que es expresar esta codificación. Por ejemplo, C puede resolver todos los problemas que Haskell puede, simplemente escribiendo un intérprete de Haskell en C ... ¡pero primero debe escribir el intérprete de Haskell para resolver un problema de esta manera!

Todos los lenguajes de programación completos de Turing pueden implementar el mismo conjunto de algoritmos. Entonces, si ve que algún algoritmo es muy difícil de implementar en un idioma en particular, no significa que sea imposible.

Recuerde que un lenguaje consiste en sintaxis y semántica. A veces, el conjunto de palabras que pertenecen a algún idioma no es mínimo para ser considerado Turing completo, hay características que facilitan las cosas (es por eso que se llaman características ). Si elimina esas características, el idioma aún está completo.

Algunos de estos pueden ser de interés:

• Compilador de fuente a fuente en Wikipedia

• Sobre la importancia de la integridad de Turing en Lambda the Ultimate

Todos los lenguajes completos de Turing pueden calcular las mismas cosas.

Si intenta implementar un lenguaje moderno, notará que la mayoría de sus características no agregan ninguna capacidad computacional. Muchas de esas características pueden reducirse a otras más simples que ya existen en el mismo idioma.

Aquí hay unos ejemplos:

• Si no tiene enumeraciones, puede usar enteros.
• Si no tiene buffers que conozcan su tamaño, puede crear un tipo que contenga un tamaño y un buffer que no conozca su tamaño.
• Si no tiene una verificación de límites de los búferes, puede verificar el índice cada vez que los use.
• Si no tiene funciones variadas, puede crear una función que tome un búfer que conozca su tamaño y leer de ese búfer la misma información que obtendría de los argumentos formales.
• Si no tiene operadores, puede usar funciones.
• Si no tiene tipos que pueden heredarse entre sí, puede crear tipos que se contengan entre sí y acceder a ellos a través de un nivel adicional de indirección, con el subtipo que es simplemente una transformación del identificador de todo el tipo a un manejar al tipo contenido.
• Si no tiene delegados pero tiene punteros de función, puede crear un tipo que contenga el objeto de referencia y un puntero de función.
• Si no tiene delegados pero tiene interfaces, puede declarar una interfaz que contenga un único método con la firma que desee.
• Si no tiene tipos genéricos, puede usar tipos no genéricos que solo asuman los límites superiores o inferiores que le interesan (y tal vez realice los cambios apropiados en los puntos de uso, para mantener contento al compilador).
• Si no tiene un sistema de tipo lineal / afín, puede evitar usar cualquier variable más de una vez.
• ...y así.

El diseño del lenguaje principal se enfoca en características que hacen que sea más fácil y conveniente para nosotros calcular las cosas más rápido, reconocer nuestros errores antes, programar contra componentes desconocidos, hacer que el paralelismo sea más seguro, etc.

Las cosas puramente computacionales se concretaron hace mucho tiempo.

Las respuestas existentes señalan correctamente que la integridad de Turing no es una buena manera de comparar idiomas. De hecho, casi todos los idiomas están completos en Turing. ("Si todos son especiales, nadie es especial", como solía decir The Incredibles).

Sin embargo, es posible comparar la expresividad de los lenguajes con la precisión matemática. Eche un vistazo a Felleisen sobre el poder expresivo de los lenguajes de programación . Aproximadamente, la idea es hacer la siguiente pregunta: ¿Puedo convertir cualquier programa en el idioma A en un programa en el idioma B haciendo solo cambios locales ? En otras palabras, Felleisen le da una forma matemáticamente precisa a su intuición.

Además de las respuestas de todos los demás, aquí hay otra analogía.

Para lavar la ropa, necesita tres cosas: un depósito que contenga agua, un detergente de algún tipo y un mecanismo de agitación. Esto podría realizarse de muchas maneras. El depósito de agua es cualquier cosa que contenga suficiente agua (por ejemplo, una bañera, un lago, un río). El mecanismo de agitación podría ser un dispositivo mecánico, una tabla de lavar o incluso una roca contra la cual se golpea la ropa. Y los detergentes también vienen en varias formas.

Entonces, ¿cuál es la diferencia entre una lavadora moderna computarizada y una roca al lado de un río?

Se reduce a tres cosas: eficiencia, seguridad y conveniencia. Algunos métodos de lavado usan menos energía, contaminan menos el medio ambiente, usan menos agua, etc. Algunos métodos de lavado requieren actividades manuales menos repetitivas (que resultan en lesiones) o estar afuera en condiciones climáticas adversas. Y algunos métodos de lavado no requieren que un humano cuide el proceso.

Los lenguajes de programación completos de Turing son de uso general, por lo que se asignan a más de una tarea. Sin embargo, para una tarea determinada, algunos lenguajes de programación son más eficientes, más convenientes y más seguros (en el sentido de que menos pueden salir mal cuando el programa se usa realmente) que otros.

Otros han proporcionado muchas buenas respuestas, pero no mencionan explícitamente una advertencia que una vez me confundió mucho: la integridad de Turing no implica que un lenguaje pueda expresar funciones computables arbitrarias de sus entradas a sus salidas. Es más débil: debe haber alguna forma de representar el dominio y el rango del conjunto de funciones computables como entradas y salidas de modo que cada una de estas funciones se asigne a un programa que tome una representación de sus entradas a las salidas correspondientes.

Tomemos, por ejemplo, un lenguaje que expresa máquinas de Turing. Cada programa en el idioma es una máquina de Turing.

Ahora considere el sublenguaje de todas las máquinas de Turing que leen y escriben solo los caracteres a, b y en blanco. Está completa, pero no puede expresar ningún programa que, por ejemplo, produzca c en todas las entradas, porque no puede escribir ningún cs. Solo puede expresar todas las funciones computables en entradas y salidas codificadas como cadenas de as y bs.

Por lo tanto, no es cierto que todos los lenguajes completos de Turing puedan calcular las mismas cosas, ni siquiera cuando limitamos estas cosas para que sean las funciones computables de sus entradas potenciales a sus salidas potenciales. El lenguaje puede requerir que las entradas y salidas se codifiquen de ciertas maneras.