¿Cuál es el conjunto mínimo de primitivas requeridas de modo que un idioma es Turing completo y una variante de lisp?Lisp realmente mínimo
Parece que el coche, el cdr y algunos controles de flujo y algo para REPL es suficiente. Sería bueno si hay tal lista.
Suponga que sólo hay 3 tipos de datos, números enteros, los símbolos y las listas. (Como en picolisp)
Hay una buena discusión de esto en el Lisp FAQ. Depende de tu elección de primitivos. El "LISP 1.5 Programmer's Manual" original de McCarthy lo hizo con cinco funciones: CAR, CDR, CONS, EQ y ATOM.
Al leer dichas preguntas frecuentes, parece que utilizó esas cinco funciones junto con los formularios especiales CONS, LAMBDA y QUOTE. – Zak
El lambda calculus es Turing completo. Tiene un primitivo, el lambda. Traducir eso a una sintaxis lisp es bastante trivial.
En realidad tiene * tres * primitivas: expresiones lambda, llamadas a funciones y referencias de variables. –
Creo que el conjunto mínimo es lo que John McCarthy publicó en el documento original.
La mejor manera de saber esto con certeza es si lo implementa. Utilicé 3 veranos para crear Zozotez que es un LISP McCarty-ish ejecutándose en Brainfuck.
Traté de averiguar lo que necesitaba y en un foro encontrarás un hilo que dice You only need lambda. Por lo tanto, puedes hacer un LISP completo en cálculo lambda si lo deseas. Lo encontré interesante, pero difícilmente es el camino a seguir si quieres algo que finalmente tenga efectos secundarios y funcione en el mundo real.
Para una completa LISP Turing Solía Paul Grahams explanation of McCarthy's paper y todo lo que realmente necesita es:
Eso es 10. Además de esto, tener una aplicación que se puede probar y no sólo en un tablero de dibujo:
Eso es 12.En mi Zozotez implementé set y flambda (macro anónimas, como lambda) también. Podría alimentarlo en una biblioteca que implemente cualquier ceceo dinámico enlazado (Elisp, picoLisp) con la excepción de E/S de archivos (porque el BF subyacente no lo admite más que stdin/stdout).
Recomiendo a cualquiera que implemente un intérprete LISP1, tanto en LISP como en (not LISP), para comprender completamente cómo se implementa un lenguaje. LISP tiene una sintaxis muy simple, por lo que es un buen punto de partida. Para todos los demás lenguajes de programación, la forma de implementar un intérprete es muy similar. P.ej. en el SICP videos los asistentes hacen un intérprete para un lenguaje lógico, pero la estructura y la forma de implementarlo es muy similar a un intérprete de lisp aunque este lenguaje es completamente diferente de Lisp.
Tenga en cuenta que los enteros son innecesarios, puede implementarlos a partir de funciones puras. – celtschk