LISP 1959 de McCarthy

Au début de 1959, John McCarthy écrivit un document novateur définissant seulement neuf fonctions primitives qui, une fois réunies, constituent toujours la base de toutes les langues de type LISP aujourd'hui. Le document est disponible numérisé ici:

http://www-formal.stanford.edu/jmc/recursive.pdf

Votre travail consiste à mettre pleinement en œuvre un analyseur et interprète pour le LISP de McCarthy exactement comme décrit dans le document 1960: C'est, les fonctions QUOTE, ATOM, EQ, CAR, CDR, CONS, COND, LAMBDAet LABELdoivent tous être fonctionnels. Le document aura la priorité sur ce texte de défi lorsque l’on examinera l’exactitude des réponses, mais j’ai essayé de résumer les neuf fonctions ci-dessous. Notez que la langue sera en majuscule et qu'aucune vérification d'erreur n'est nécessaire, toutes les entrées doivent être présumées être valides.

Les types

• Le LISP de McCarthy ne comprend que deux types: un atome et une liste chaînée, qui est définie de manière récursive comme une tête, qui peut être une liste ou un atome, et une liste à laquelle la tête est attachée (queue). NILa la propriété particulière d'être à la fois un atome et une liste.
• Selon le document, les noms d'atomes ne seront composés que de lettres majuscules, de chiffres et du caractère d'espacement, bien que les chaînes d'espaces consécutifs soient considérées comme un seul espace et que tous les caractères d'espacement en début et en fin soient supprimés. Exemples de noms d'atome équivalent (remplacer underscore avec espace): ___ATOM__1__ = ATOM_1. Exemple de noms d'atomes non équivalents:A_TOM_1 != ATOM_1
• Les listes sont indiquées par des parenthèses, et un implicite NILest à la fin de chaque liste. Les éléments d'une liste sont séparés par des virgules et non par des espaces comme dans la plupart des Lisps modernes. Donc, la liste (ATOM 1, (ATOM 2))serait {[ATOM 1] -> {[ATOM 2] -> NIL} -> NIL}.

QUOTE:

• Prend un argument qui peut être un atome (élément unique) ou une liste chaînée. Retourne l'argument exactement.
• Cas de test:
• (QUOTE, ATOM 1) -> ATOM 1
• (QUOTE, (ATOM 1, ATOM 2)) -> (ATOM 1, ATOM 2)

ATOM:

• Prend un argument qui peut être un atome (élément unique) ou une liste chaînée. Renvoie T(true) si l'argument est un atome ou NIL(false) si l'argument n'est pas un atome.
• Cas de test:
• (ATOM, (QUOTE, ATOM 1)) -> T
• (ATOM, (QUOTE, (ATOM 1, ATOM 2))) -> NIL

EQ:

• Prend deux arguments qui doivent être des atomes (le comportement n'est pas défini si l'un des arguments n'est pas un atome). Renvoie T(true) si les deux atomes sont équivalents ou NIL(false) s'ils ne le sont pas.
• Cas de test:
• (EQ, (QUOTE, ATOM 1), (QUOTE, ATOM 1)) -> T
• (EQ, (QUOTE, ATOM 1), (QUOTE, ATOM 2)) -> NIL

CAR:

• Prend un argument qui doit être une liste (le comportement est indéfini s'il ne s'agit pas d'une liste). Retourne le premier atome (tête) de cette liste.
• Cas de test:
• (CAR, (QUOTE, (ATOM 1, ATOM 2))) -> ATOM 1

CDR:

• Prend un argument qui doit être une liste (le comportement est indéfini s'il ne s'agit pas d'une liste). Renvoie chaque atome sauf le premier atome de la liste, c'est-à-dire la queue. Notez que chaque liste se termine de manière implicite NIL, donc si vous CDRretournez sur une liste qui semble ne contenir qu'un seul élément NIL.
• Cas de test:
• (CDR, (QUOTE, (ATOM 1, ATOM 2))) -> (ATOM 2)
• (CDR, (QUOTE, (ATOM 1))) -> NIL

CONS:

• Prend deux arguments. Le premier peut être un atome ou une liste mais le second doit être une liste ou NIL. Ajoute le premier argument au second argument et renvoie la liste nouvellement créée.
• Cas de test:
• (CONS, (QUOTE, ATOM 1), (QUOTE, NIL)) -> (ATOM 1)
• (CONS, (QUOTE, ATOM 1), (CONS, (QUOTE, ATOM 2), (QUOTE, NIL))) -> (ATOM 1, ATOM 2)

COND:

• C'est la déclaration "if-else" de LISP. Prend une quantité d'arguments de longueur variable, dont chacun doit être une liste de longueur exactement 2. Pour chaque liste d'arguments dans l'ordre, évaluez le premier terme et si c'est vrai (T), retournez le deuxième terme associé et quittez la fonction . Si le premier terme n'est pas vrai, passez au prochain argument et testez sa condition, et ainsi de suite jusqu'à ce que la première condition vraie soit atteinte. Au moins une des conditions d'argument peut être considérée comme vraie - si elles sont toutes fausses, il s'agit d'un comportement non défini. Voir page 4 pour un bon exemple du comportement de cette fonction.
• Cas de test:
• (COND, ((ATOM, (QUOTE, ATOM 1)), (QUOTE, 1)), ((ATOM, (QUOTE, (ATOM 1, ATOM 2))), (QUOTE, 2))) -> 1
• (COND, ((ATOM, (QUOTE, (ATOM 1, ATOM 2))), (QUOTE, 2)), ((ATOM, (QUOTE, ATOM 1)), (QUOTE, 1))) -> 1

LAMBDA:

• Définit une fonction anonyme. Prend deux arguments, le premier étant une liste d'atomes qui représentent les arguments de la fonction et le second étant toute expression S (le corps de la fonction), qui utiliserait typiquement les arguments.
• Cas de test:
• Définir et utiliser une fonction "isNull" anonyme:
• ((LAMBDA, (ATOM 1), (EQ, ATOM 1, (QUOTE, NIL))), (QUOTE, NIL)) -> T
• ((LAMBDA, (ATOM 1), (EQ, ATOM 1, (QUOTE, NIL))), (QUOTE, ATOM 1)) -> NIL

LABEL:

• Donne un nom à une LAMBDAfonction anonyme , ce qui permet également à cette fonction d’être appelée de manière récursive dans le corps du fichier LAMBDA. Prend deux arguments, le premier étant une étiquette et le second étant la LAMBDAfonction à laquelle l'étiquette doit être liée. Renvoie le nom fourni. La portée de tous les LABELnoms est globale et la redéfinition d'un LABELcomportement est indéfinie.
• Fait amusant, il LABELn'est pas réellement nécessaire de créer des fonctions récursives, car nous savons maintenant qu'il LAMBDApeut être utilisé avec un 'Y-Combinator' pour accomplir cette tâche, mais McCarthy n'était pas au courant de cette méthode lors de la rédaction du document original. Cela rend les programmes beaucoup plus faciles à écrire de toute façon.
• Cas de test:
• (LABEL, SUBST, (LAMBDA, (X, Y, Z), (COND, ((ATOM, Z), (COND, ((EQ, Y, Z), X), ((QUOTE, T), Z))), ((QUOTE, T), (CONS, (SUBST, X, Y, (CAR, Z)), (SUBST, X, Y, (CDR, Z))))))) -> SUBST
• (après avoir exécuté ce qui précède) (SUBST, (QUOTE, A), (QUOTE, B), (QUOTE, (A, B, C))) -> (A, A, C)

Pour aider à visualiser la SUBSTfonction ci-dessus, elle pourrait être représentée par ce pseudo-code de type Python:

def substitute(x, y, z): # substitute all instances of y (an atom) with x (any sexp) in z
    if isAtom(z):
        if y == z:
            return x
        elif True: 
            return z
    elif True:
        return substitute(x,y,z[0]) + substitute(x,y,z[1:])

CAS DE TEST FINAL:

Si je l'ai bien transcrit, votre interprète devrait pouvoir interpréter EVALavec ce code:

(LABEL, CAAR, (LAMBDA, (X), (CAR, (CAR, X))))
(LABEL, CDDR, (LAMBDA, (X), (CDR, (CDR, X))))
(LABEL, CADR, (LAMBDA, (X), (CAR, (CDR, X))))
(LABEL, CDAR, (LAMBDA, (X), (CDR, (CAR, X))))
(LABEL, CADAR, (LAMBDA, (X), (CAR, (CDR, (CAR, X)))))
(LABEL, CADDR, (LAMBDA, (X), (CAR, (CDR, (CDR, X)))))
(LABEL, CADDAR, (LAMBDA, (X), (CAR, (CDR, (CDR, (CAR, X))))))

(LABEL, ASSOC, (LAMBDA, (X, Y), (COND, ((EQ, (CAAR, Y), X), (CADAR, Y)), ((QUOTE, T), (ASSOC, X, (CDR, Y))))))

(LABEL, AND, (LAMBDA, (X, Y), (COND, (X, (COND, (Y, (QUOTE, T)), ((QUOTE, T), (QUOTE, NIL)))), ((QUOTE, T), (QUOTE, NIL)))))
(LABEL, NOT, (LAMBDA, (X), (COND, (X, (QUOTE, NIL)), ((QUOTE, T), (QUOTE, T)))))

(LABEL, NULL, (LAMBDA, (X), (AND, (ATOM, X), (EQ, X, (QUOTE, NIL)))))

(LABEL, APPEND, (LAMBDA, (X, Y), (COND, ((NULL, X), Y), ((QUOTE, T), (CONS, (CAR, X), (APPEND, (CDR, X), Y))))))

(LABEL, LIST, (LAMBDA, (X, Y), (CONS, X, (CONS, Y, (QUOTE, NIL))))) 

(LABEL, PAIR, (LAMBDA, (X, Y), (COND, ((AND, (NULL, X), (NULL, Y)), (QUOTE, NIL)), ((AND, (NOT, (ATOM, X)), (NOT, (ATOM, Y))), (CONS, (LIST, (CAR, X), (CAR, Y)), (PAIR, (CDR, X), (CDR, Y)))))))

(LABEL, EVAL, (LAMBDA, (E, A), (COND, ((ATOM, E), (ASSOC, E, A)), ((ATOM, (CAR, E)), (COND, ((EQ, (CAR, E), (QUOTE, QUOTE)), (CADR, E)), ((EQ, (CAR, E), (QUOTE, ATOM)), (ATOM, (EVAL, ((CADR, E), A)))), ((EQ, (CAR, E), (QUOTE, EQ)), (EQ, (EVAL, (CADR, E, A)), (EVAL, (CADDR, E, A)))), ((EQ, (CAR, E), (QUOTE, COND)), (EVCON, (CDR, E), A)), ((EQ, (CAR, E), (QUOTE, CAR)), (CAR, (EVAL, (CADR, E), A))), ((EQ, (CAR, E), (QUOTE, CDR)), (CDR, (EVAL, (CADR, E), A))), ((EQ, (CAR, E), (QUOTE, CONS)), (CONS, (EVAL, (CADR, E), A), (EVAL, (CADDR, E), A))), ((QUOTE, T), (EVAL, (CONS, (ASSOC, (CAR, E), A), (EVLIS, (CDR, E), A)), A)))), ((EQ, (CAAR, E), (QUOTE, LABEL)), (EVAL, (CONS, (CADDAR, E), (CDR, E)), (CONS, (CONS, (CADAR, E), (CONS, (CAR, E), (CONS, A, (QUOTE, NIL))))))), ((EQ, (CAAR, E), (QUOTE, LAMBDA)), (EVAL, (CADDAR, E), (APPEND, (PAIR, (CADAR, E), (EVLIS, (CDR, E), A)), A))))))

(LABEL, EVCON, (LAMBDA, (C, A), (COND, ((EVAL, (CAAR, C), A), (EVAL, (CADAR, C), A)), ((QUOTE, T), (EVCON, (CDR, C), A)))))

(LABEL, EVLIS, (LAMBDA, (M, A), (COND, ((NULL, M), (QUOTE, NIL)), ((QUOTE, T), (CONS, (EVAL, (CAR, M), A), (EVLIS, (CDR, M), A))))))

Après avoir exécuté ce géant, cette ligne devrait retourner (A, B, C):

(EVAL, (QUOTE, (CONS, X, (QUOTE, (B, C)))), (QUOTE, ((X, A), (Y, B))))

Cependant, pour citer John McCarthy lui-même à la page 16, il semble qu'il manque de caractères sur son ordinateur:

Si plus de caractères étaient disponibles sur l'ordinateur, cela pourrait être considérablement amélioré ...

Par conséquent, ce défi est étiqueté code-golf et la réponse la plus courte en caractères sera gagnante. Les failles standard s'appliquent. Bonne chance!

Note sur les évaluations de chaîne : Je comprends que certains pensent qu'il serait possible de remporter ce défi en utilisant un Lisp, en modifiant la syntaxe pour l'adapter au langage hôte, puis en utilisant une chaîne (eval). Je ne suis pas particulièrement convaincu que cette approche l'emporte nécessairement, en particulier avec les règles de nommage des identifiants, et même si c'était le cas, l'interdiction des chaînes de caractères evaldans toutes les langues constituerait une pente subjective et glissante. Mais je ne veux pas punir les gens qui font ce défi de la bonne façon. Je peux donc autoriser deux gagnants pour ce défi, un dans une langue similaire à Lisp et un dans une langue autre que Lispy, si cela pose problème. .

Python 3, 770 octets

Ceci est une REPL sur stdin / stdout. S'attend à ce que chaque ligne soit complète ou vide. evalest utilisé pour raccourcir la mise en œuvre, mais n'est pas non plus nécessaire pour la logique.

import re,sys;S=re.sub
P=lambda l:eval(S("([A-Z0-9][A-Z0-9 ]*)",r"' '.join('\1'.strip().split())",S("NIL","()",S("\)",",)",l))))
d={"QUOTE":'(v,L[1])[1]',"EQ":'[(),"T"][E(L[1],v)==E(L[2],v)]',
"CDR":'E(L[1],v)[1:]',"CONS":'(E(L[1],v),)+E(L[2],v)',"CAR":'E(L[1],v)[0]',
"LAMBDA":'("#",)+L[1:]',"LABEL":'[v.update({L[1]:E(L[2],v)}),L[1]][1]'}
def E(L,v):
 if L*0=="":return v[L]
 elif L[0]in d:return eval(d[L[0]])
 elif L[0]=="COND":return next(E(l[1],v)for l in L[1:]if E(l[0],v)=="T")
 elif L[0]=="ATOM":o=E(L[1],v);return[(),"T"][o*0in["",o]]
 else:l=E(L[0],v);n=v.copy();n.update({a:E(p,v)for a,p in zip(l[1],L[1:])});return E(l[2],n)
R=lambda o:o==()and"NIL"or 0*o==()and"(%s)"%", ".join(R(e)for e in o)or o
g={}
for l in sys.stdin:
 if l.strip():print(R(E(P(l),g)))