¿Algún lenguaje de programación utiliza funciones recursivas generales como base?

23

Esta es una pregunta ingenua y, por lo tanto, posiblemente malformada, ¡disculpas de antemano!

Mi opinión es que una máquina de Turing puede verse como la base computacional para los lenguajes de programación de procedimientos / imperativos. Del mismo modo, el cálculo lambda es la base de los lenguajes de programación funcionales.

Recientemente he aprendido que la Tesis de Church-Turing también muestra equivalencia mutua con un tercer modelo de computación: las funciones recursivas generales . ¿Hay algún lenguaje de programación que use esto como su modelo de computación? Si no, ¿hay alguna razón técnica por la cual; es decir, además de "Nadie lo ha intentado todavía"?

Xophmeister
fuente
1
Diría que las máquinas de Turing o las máquinas de registro universal son una base de los PL de procesador (PL de ensamblaje). No tienen funciones. Las funciones recursivas son una base de los PL imperativos. No tienen funciones de orden superior. μ
Beroal
1
También recomendaría buscar en la lógica de primer orden y Prolog.
Beroal
1
Antes de C ++ 11, constexprpodía (/ tenía que) usar 'plantillas' para que el compilador realizara los cálculos en tiempo de compilación. Las restricciones en las plantillas no permiten bucles, pero puede usar la recursividad para emular cualquier bucle, de modo que termine con una instalación Turing-complete (metaprogramación) como parte del estándar del lenguaje C ++, consulte, por ejemplo, stackoverflow.com/questions / 189172 / c-templates-turing-complete
JimmyB

Respuestas:

45

Respuesta directa a la pregunta: sí, existen PL esotéricos y poco prácticos basados ​​en funciones recursivas (piense en espacios en blanco), pero ningún lenguaje de programación práctico se basa en funciones recursivas debido a razones válidas.μμμ

Las funciones recursivas generales (es decir, -recursivas) son significativamente menos expresivas que los cálculos lambda. Por lo tanto, hacen una base pobre para los lenguajes de programación. Tampoco tiene razón en que la TM es la base de los PL imperativos: en realidad, los buenos lenguajes de programación imperativos están mucho más cerca de -calculus que de las máquinas de Turing.λμλ

En términos de computabilidad, las funciones recursivas , la máquina de Turing y el cálculo tipo son equivalentes. Sin embargo, el LC sin tipo tiene buenas propiedades que ninguno de los otros dos tiene. Es muy simple (solo 3 formas sintácticas y 2 reglas computacionales), es altamente composicional y puede expresar construcciones de programación con relativa facilidad. Además, equipado con un sistema de tipo simple (p. Ej., Sistema extendido con ), el cálculo puede ser extremadamente expresivo ya que puede expresar muchas construcciones de programación complejas de manera fácil, correcta y compositiva. También puede extender elλ F ω f i x λ λμλFωfixλλ-cálculo para incluir fácilmente construcciones que no son lambdas. Ninguno de los otros modelos computacionales mencionados anteriormente le dan esas buenas propiedades.

La máquina de Turing no es compositiva ni universal (necesita tener una TM para cada problema). No hay conceptos de "funciones", "variables" o "composición". Tampoco es exactamente cierto que los TM sean la base de los PL imperativos: FWIW, los PL imperativos están mucho, mucho más cerca de los cálculos lambda con operadores de control que de las máquinas Turing. Consulte "Una correspondencia entre ALGOL 60 y la notación lambda de la Iglesia" de Peter J. Landin para obtener una explicación detallada. Si ha programado en Brainf ** k (que en realidad implementa una máquina de Turing bastante simple), sabrá que las máquinas de Turing no son una buena idea para la programación.

μ μ NμLas funciones recursivas son similares a las TM a este respecto. Son composicionales, pero no tan composicionales como el LC. Tampoco puede codificar construcciones de programación útiles en funciones recursivas . Además, las funciones recursivas solo computan sobre , y para computar sobre cualquier otra cosa necesitaría codificar sus datos en números naturales usando algún tipo de numeración de Gödel, lo cual es doloroso.μμN

Por lo tanto, ¡no es una coincidencia que la mayoría de los lenguajes de programación se basen de alguna manera en el cálculo ! El cálculo tiene buenas propiedades: expresividad, composicionalidad y extensibilidad, que otros sistemas carecen. Sin embargo, las máquinas de Turing son buenas para estudiar la complejidad computacional, y las funciones recursivas son buenas para estudiar la noción lógica de computabilidad. Ambos tienen propiedades sobresalientes de las que carece -calculus, pero en el campo de la programación -calculus claramente gana.λ μ λ λλλμλλ

De hecho, hay muchos, muchos más sistemas completos de Turing, pero carecen de propiedades sobresalientes. El juego de la vida de Conway, las macros de LaTeX e incluso el ADN (algunos afirman) están completos en Turing, pero nadie programa (es decir, hace una programación seria) con Conway ni estudia la complejidad computacional usando macros de LaTeX. Simplemente carecen de buenas propiedades. Turing completo per se es casi sin sentido cuando se trata de programación.

Además, muchos sistemas computacionales completos que no son de Turing son muy útiles cuando se trata de programación. Las expresiones regulares y yacc no están completas en Turing, pero son extremadamente poderosas para resolver una cierta clase de problemas. Coq tampoco es completo para Turing, pero es increíblemente poderoso (en realidad se considera mucho más expresivo que su primo completo de Turing, OCaml). Cuando se trata de programación, la integridad de Turing no es la clave, ya que muchos (casi) sistemas inútiles son de Turing sin interés. No vas a decir que Brainf ** k o Whitespace son lenguajes de programación más potentes que Coq, ¿verdad? Una base expresiva es la clave para poderosos lenguajes de programación, y es por eso que los lenguajes de programación modernos casi siempre se basan en elλ-cálculo.

xuq01
fuente
77
"nadie programa con Conway" ... algunos construyen un juego de Tetris en el Juego de la vida de Conway ... también es tan práctico como el espacio en blanco :)
Alexei Levenkov
Una forma de ver esto es que una función -calculus que simula máquinas de Turing probablemente sería mucho más corta que una máquina de Turing que simula el -calculus (que tampoco he visto). λλλ
Ortografía no contextual
@AlexeiLevenkov Eso es completamente falso. El espacio en blanco es esencialmente un lenguaje imperativo (simple), aunque con una sintaxis extraña. Cuenta con instalaciones para la aritmética, el flujo de control básico, pila y la manipulación del montón, y I / O . El proyecto QFT, por otro lado, requería diseñar un compilador desde un lenguaje muy simple hasta un ensamblaje RISC creado para una CPU construida dentro de un autómata celular similar a Wireworld emulado usando OTCA Metapixels .
Ortografía no contextual
@AlexeiLevenkov El último compilador Cogol → CGoL requirió el trabajo de muchas personas durante cuatro años, mientras que existe un proyecto llamado HaPyLi , que compila un lenguaje mucho más complejo para Whitespace, que fue escrito por una persona en su tiempo libre.
Ortografía no contextual
4

Escribir µ-recursive function programming languageen Google me llevó a este repositorio de GitHub , por lo que la respuesta a su pregunta es:

Sí, y se llama miopía.

Está escrito en Haskell, por cierto.

Kapol
fuente
Añadiría: pero ningún lenguaje de programación práctico se basa en funciones recursivas . Parece que la miopía es un primo lejano de Brainf ** k y está muy lejos de la programación práctica. μ
xuq01
2
Por supuesto. Supuse que OP quiere encontrar un lenguaje para estudiar la teoría o algo así, no conquistar el mundo con ella ;-)
Kapol