Lisp realmente mínimo

Question

¿Cuál es el mínimo conjunto de primitivas requeridas tales que una lengua es Turing completo y una variante de Lisp?

Parece coche, CDR y algunos de control de flujo y algo para REPL es suficiente. Sería agradable si existe tal lista.

Suponga que sólo hay 3 tipos de datos, números enteros, los símbolos y las listas. (Como en picolisp)

Answer 1

Hay una buena discusión sobre esto en el Lisp FAQ . Depende de su elección de primitivas. originales "LISP 1.5 del Manual del Programador" de McCarthy hizo con cinco funciones:. CAR, CDR, CONS, EQ y ATOM

Answer 2

El cálculo lambda es Turing completo. Tiene una primitiva - la lambda. Traducirlo a una sintaxis Lisp es bastante trivial.

Answer 3

Creo que el conjunto mínimo es lo que John McCarthy publicó en el documento original.

Las raíces de Lisp .

El código .

Answer 4

La mejor manera de saber realmente a ciencia cierta es si la aplicación de la misma. Solía ??3 veranos para crear Zozotez que es un LISP McCarty-ish ejecutando en Brainfuck .

Me trató de averiguar lo que necesitaba y en un foro se puede encontrar un hilo que dice Sólo necesita lambda. por lo tanto, puede hacer toda una LISP en el cálculo lambda si lo desea. Me pareció interesante, pero es apenas el camino a seguir si quieres algo que a la larga tiene efectos secundarios y funciona en el mundo real.

Para una LISP Turing completo que utiliza Paul Graham explicación del papel de McCarthy y todo lo que realmente necesita es:

• símbolo de la evaluación
• forma especial cita
• forma especial si (o cond)
• lambda forma especial (similar a citar)
• función eq
• átomo de función
• contras de función
• coche de función
• función CDR
• función de despacho (básicamente aplicar, pero en realidad no se expone al sistema por lo que maneja una lista donde primer elemento es una función)

Eso es 10. Además de esto, para tener una aplicación que se puede probar y no sólo en un tablero de dibujo:

• función de lectura
• función de escritura

Eso es 12. En mi Zozotez I implementado algunas set y flambda (macroes anónimos, como lambda) también. Podría darle de comer una biblioteca de implementar cualquier Lisp con destino dinámico (Elisp, picoLisp) con la excepción del archivo de E / S (debido a que el BF subyacente no lo soporta aparte de la entrada estándar / salida estándar).

Lo recomendaría a cualquiera implementar un LISP1-intérprete, tanto en LISP y (not LISP), para entender completamente cómo se implementa un idioma. LISP tiene una sintaxis muy simple, así que es un buen punto de partida. Para todos los demás lenguajes de programación modo en que implementa un intérprete es muy similar. P.ej. en los videos SICP los asistentes realizar un intérprete para un lenguaje lógico, pero la estructura y la forma de ponerla en práctica es muy similar a un intérprete de Lisp a pesar de que este lenguaje es completamente diferente a Lisp.