¿Cuántas primitivas se necesitan para construir una máquina LISP? ¿Diez, siete o cinco?

En este sitio dicen que hay 10 primitivas LISP. Las primitivas son: atom, quote, eq, car, cdr, cons, cond, lambda, label, apply.

http://hyperpolyglot.wikidot.com/lisp#ten-primitives

Stevey reconoce que hay siete (o cinco):

Es parte de la pureza de la idea de LISP: solo necesitas las siete (¿o son cinco?) Primitivas para construir la máquina completa. http://steve-yegge.blogspot.com/2006/04/lisp-is-not-acceptable-lisp.html

¿Cuál es el número mínimo de primitivas para construir una máquina LISP (es decir, algo que pueda ejecutar una función eval / value en código LISP)? (¿Y cuáles son?)

(Puedo entender que podrías vivir sin atom, label and apply)

Predicados básicos / funciones F

McCarthy 's elementales S-funciones y predicados fueron:

1. atom

   Lo cual era necesario porque car y cdr se definen solo para listas, lo que significa que no puede contar con ningún tipo de respuesta para indicar lo que estaba sucediendo si le dio carun átomo.

2. eq

   Para probar la igualdad entre átomos.

3. car

   Para devolver la primera mitad (dirección) de la celda de contras. (Contenido del registro de direcciones).

4. cdr

   Para devolver la segunda mitad (decremento) de la celda de contras. (Contenido del registro de decrementos).

5. cons

   Para crear una nueva celda de contras, con la mitad de la dirección que contiene el primer argumento de contras y la mitad de decremento que contiene el segundo argumento.

Uniéndolo: funciones S

Luego continuó agregando a su notación básica, para permitir escribir lo que él llamó funciones S:

1. quote

   Representar una expresión sin evaluarla.

2. cond

   El condicional básico que se utilizará con los predicados descritos anteriormente.

3. lambda

   Para denotar una función.

4. label

   Aunque no necesitaba esto para la recursividad, es posible que no supiera sobre el Y-Combinator ( según Paul Graham ), lo agregó por conveniencia y para permitir una recursión fácil.

Entonces puede ver que en realidad definió 9 "operadores" básicos para su máquina Lisp. En una respuesta anterior a otra de tus preguntas, te expliqué cómo podrías representar y operar números con este sistema.

Pero la respuesta a esta pregunta realmente depende de lo que desee de su máquina Lisp. Podría implementar uno sin la labelfunción, ya que simplemente podría componer todo funcionalmente y obtener la recursividad mediante la aplicación del Y-Combinator.

atompodría descartarse si definió la caroperación en los átomos para devolverNIL .

Básicamente, podría tener la máquina LISP de McCarthy con 7 de estas 9 primitivas definidas, pero aparentemente podría definir una versión más concisa dependiendo de la cantidad de inconvenientes que desee infligirse. Me gusta bastante su máquina, o las muchas primitivas en los lenguajes más nuevos como Clojure.

La mejor manera de saberlo con certeza es implementarlo. Usé 3 veranos para crear Zozotez, que es un LISP al estilo McCarty que se ejecuta en Brainfuck .

Traté de averiguar lo que necesitaba y en un foro encontrarás un hilo que dice que solo necesitas lambda.Por lo tanto, puede hacer un LISP completo en el cálculo lambda que desee. Lo encontré interesante, pero difícilmente es el camino a seguir si quieres algo que eventualmente tenga efectos secundarios y funcione en el mundo real.

Para un LISP completo de Turing utilicé la explicación de Paul Grahams del artículo de McCarthy y todo lo que realmente necesitas es:

• evaluación de símbolo
• cotización de formulario especial
• forma especial si (o cond)
• forma especial lambda (similar a la cita)
• función eq
• función átomo
• función contras
• coche funcional
• función cdr
• función-despacho (lista-lambda)

Eso es 10. Además de esto, para tener una implementación que pueda probar y no solo en un tablero de dibujo:

• función leer
• función escribir

Eso es 12. En mi Zozotez set y flambda (macroes anónimos, como lambda) también. Podría alimentarlo con una biblioteca que implemente cualquier lisp enlazado dinámico (Elisp, picoLisp) con la excepción de la 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 LISP (no en 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 un analizador. Actualmente estoy trabajando en un compilador de esquemas escrito en esquema con diferentes objetivos (como Stalin es para el objetivo C), con suerte BF como uno de ellos.

McCarthy utilizó siete operadores para definir el Lisp originales: quote, atom, eq, car, cdr, consy cond. Este artículo vuelve sobre sus pasos.

Esta faq dice:

No existe un único conjunto mínimo "mejor" de primitivas; todo depende de la implementación. Por ejemplo, incluso algo tan básico como los números no necesita ser primitivo y puede representarse como listas. Un posible conjunto de primitivas podría incluir CAR, CDR y CONS para la manipulación de expresiones S, READ e PRINT para la entrada / salida de expresiones S y APPLY y EVAL para las entrañas de un intérprete. Pero luego es posible que desee agregar LAMBDA para funciones, EQ para igualdad, COND para condicionales, SET para asignación y DEFUN para definiciones. QUOTE también puede ser útil.

Eso proviene del sitio web de la Escuela de Ciencias de la Computación, Carnegie Melon.

Paul Graham implementa eval usando siete .

En el Micro Manual de McCarthy para LISP, implementa eval usando diez .

Usted sólo necesita un sistema x86 MOVde instrucciones .

"El M / o / Vfuscator (abreviatura de 'o', suena como" mobfuscator ") compila programas en instrucciones" mov "y solo instrucciones" mov ". Aritmética, comparaciones, saltos, llamadas a funciones y todo lo demás que necesita un programa todo realizado a través de operaciones mov; no hay código de modificación automática, ningún cálculo activado por transporte y ninguna otra forma de trampa sin movimiento ".

Sin embargo, en serio, estas primitivas no implementarán una máquina Lisp. Una máquina necesita instalaciones como E / S y recolección de basura. ¡Sin mencionar un mecanismo de llamada a función! Bien, tienes siete primitivas que son funciones. ¿Cómo llama la máquina a una función?

La comprensión adecuada de lo que hacen posible estas primitivas es que exponen el conjunto de instrucciones de una máquina universal de Turing . Debido a que esas instrucciones son "Lispy", por un desliz de la lengua (hablando con un Lisp) furtivamente llamamos a esto una "Máquina Lisp". "Universal" significa que la máquina es programable: con algunas instrucciones de combinación aplicadas a la Universal Turing Machine, podemos crear una instancia de cualquier Turing Machine. Pero hasta ahora, todo eso es puramente una construcción matemática.

Para simular realmente este UTM, realizarlo físicamente para poder explorarlo en una computadora, necesitamos una máquina que nos proporcione una forma de ingresar esos formularios que crean máquinas de Turing a partir de combinaciones de esas siete instrucciones Lisp. Y también necesitamos alguna forma de salida; la máquina para al menos poder decirnos "sí", "no" o "Espera, todavía estoy funcionando".

En otras palabras, la única forma en que esas siete instrucciones pueden funcionar en la práctica es si están alojadas en una máquina más grande que proporciona el entorno.

También tenga en cuenta que los siete primitivos de Graham no tienen soporte explícito para números, por lo que tendría que construirlos a partir de funciones (técnica de "numerales de la Iglesia"). Ninguna implementación Lisp de producción hace una locura.