LISP de McCarthy

39

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é 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. .

Harry
la source
1
Vous avez un exemple Lambda définissant une fonction "IsNull", mais il ressemble à la valeur Nil return Nil, alors qu'il me semble qu'il devrait renvoyer T?
nmjcman101
1
Vous avez ((LAMBDA, (ATOM 1), (EQ, ATOM 1, (QUOTE, NIL))), (QUOTE, NIL)) -> NIL(QUOTE NIL)à la fin est l'entrée, alors cela devrait revenir T?
nmjcman101
1
Bien, mais vous avez écrit-> NIL
nmjcman101
1
Dans votre description, CONSvous dites "Ajoute le premier argument au deuxième argument et renvoie la liste nouvellement créée", mais les scénarios de test montrent que le deuxième argument est ajouté au premier. Qui est correct?
Jordanie
1
Je base mon implémentation sur le didacticiel lisp de kjetilvalle , et la syntaxe est légèrement différente. Les lettres minuscules sont utilisées et aucune virgule n'est présente. Pourrais-je simplement exécuter une transformation en minuscule et supprimer des virgules de la chaîne d'entrée afin qu'elle soit plus ou moins conforme à la conception de l'interprète ci-dessus? Je suis assez nouveau sur Lisp, mais je voulais explorer ce défi dans ma propre langue. Jusqu'à présent, l'analyseur est implémenté . (Ma langue ressemble à Lisp, mais est implémentée dans Node.js)
Andrakis

Réponses:

17

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)))
orlp
la source
1
@ Harry Les deux premiers cas de test fonctionnent après avoir corrigé un petit bug que j'ai introduit lors des dernières retouches. L'éval fonctionne parfaitement. Mais l' SUBSTexemple est toujours cassé (à ma connaissance) en tant que testcase. Un des CONDs atteint la fin avant de trouver un T.
Orlp
1
Merci d'avoir réglé ça! C'est très impressionnant! Cela fonctionne pour moi sur tous les cas de test maintenant, y compris EVAL(si agréablement surpris que je l'ai eu dès le premier essai!) Je vais vous attribuer la prime et la réponse acceptée maintenant!
Harry
2
Aussi, j'adore la R(E(P(l)configuration ;-)
Harry
2
@ Harry je te gêne pas que c'était un accident! R = repr, E = eval, P = parse, l = line.
Orlp
4
Je voulais juste que vous sachiez, j'ai écrit un article mentionnant votre mise en œuvre ici !
Harry