lisp minima Davvero

Question

Qual è l'insieme minimo di primitive richiesto in modo tale che una lingua è Turing completa e una variante lisp?

Sembra come auto, cdr e un po 'di controllo del flusso e qualcosa per REPL è sufficiente. E 'bello se c'è tale lista.

Si supponga ci sono solo 3 tipi di dati, numeri interi, i simboli e le liste. (Come in picolisp)

Answer 1

C'è una buona discussione di questo nel Lisp FAQ . Dipende dalla vostra scelta di primitive. "LISP 1.5 del Programmatore Manuale" originale di McCarthy lo ha fatto con cinque funzioni:. CAR, CDR, CONS, EQ, e ATOM

Answer 2

Il lambda calcolo è Turing completo. Ha una primitiva - lambda. Tradurre che ad una sintassi Lisp è piuttosto banale.

Answer 3

Credo che l'insieme minimo è quello che John McCarthy pubblicato nel documento originale.

The Roots of Lisp .

Il codice .

Answer 4

Il modo migliore per conoscere questa realtà per certo è se si implementa esso. Ho usato 3 estati per creare Zozotez che è un LISP McCarty-ish in esecuzione su Brainfuck .

ho cercato di scoprire che cosa avevo bisogno e su un forum troverete un filo che dice Hai solo bisogno di lambda. Così, si può fare un intero LISP in lambda calcolo, se vuoi. Ho trovato interessante, ma non è certo la strada da percorrere se si vuole qualcosa che alla fine ha effetti collaterali e lavora nel mondo reale.

Per una completa LISP Turing ho usato Paul Graham spiegazione di carta di McCarthy e tutto quello che ha realmente bisogno è:

• simbolo valutazione
• forma speciale citazione
• forma speciale se (o cond)
• forma speciale lambda (simile a citare)
• Funzione eq
• Funzione atomo
• cons funzione
• auto funzione
• Funzione cdr
• Funzione-spedizione (a fondo ma in realtà non esposto al sistema in modo che gestisce una lista in cui primo elemento è una funzione)

Questo è 10. In aggiunta a questo, per avere un'implementazione che è possibile testare e non solo su un tavolo da disegno:

• funzione di lettura
• funzione di scrittura

Questo è 12. A mio Zozotez I implemeted set e flambda (macroes anonimi, come lambda) pure. Potrei dargli da mangiare una libreria che implementa qualsiasi dinamica legata Lisp (Elisp, picoLisp) con l'eccezione di file di I / O (perché il BF sottostante non supporta diverso da stdin / stdout).

Lo consiglio a chiunque di realizzare un LISP1-interprete, sia in LISP e (not LISP), per comprendere appieno come è implementata una lingua. LISP ha una sintassi molto semplice quindi è un buon punto di partenza. Per tutti gli altri linguaggi di programmazione come implementare un interprete è molto simile. Per esempio. nelle SICP le procedure guidate di fare un interprete per un linguaggio logico, ma la struttura e come implementare è molto simile ad un interprete Lisp, anche se questa lingua è completamente diverso da quello Lisp.