McCarthy's LISP 1959

Na początku 1959 r. John McCarthy napisał przełomowy artykuł, w którym zdefiniował tylko dziewięć prymitywnych funkcji, które razem wzięte stanowią podstawę wszystkich dzisiejszych języków podobnych do LISP. Papier jest dostępny w formie cyfrowej tutaj:

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

Twoim zadaniem jest, aby w pełni wdrożyć parser i tłumacza LISP McCarthy'ego dokładnie jak opisano w dokumencie 1960: Oznacza to, że funkcje QUOTE, ATOM, EQ, CAR, CDR, CONS, COND, LAMBDA, i LABELpowinny być funkcjonalne. Artykuł będzie miał pierwszeństwo przed tym tekstem wyzwania przy rozważaniu poprawności odpowiedzi, ale próbowałem podsumować dziewięć funkcji poniżej. Należy pamiętać, że język będzie w WSZYSTKICH CZAPACH i nie jest konieczne sprawdzanie błędów, wszystkie dane wejściowe należy uznać za prawidłowe.

Rodzaje

• Istnieją tylko dwa typy w LISP McCarthy'ego: atom i lista połączona, która jest rekurencyjnie zdefiniowana jako głowa, która może być listą lub atomem, oraz lista, do której głowa jest dołączona (ogon). NILma tę szczególną właściwość, że jest zarówno atomem, jak i listą.
• Zgodnie z artykułem, nazwy atomów będą składać się wyłącznie z wielkich liter, cyfr i spacji, chociaż ciągi kolejnych spacji powinny być traktowane jako jedna spacja, a wszystkie wiodące i końcowe spacje powinny zostać usunięte. Przykład nazwy równoważnik atomu (wymienić podkreślenia ze znaku spacji) ___ATOM__1__ = ATOM_1. Przykład nie równoważnych nazw atomów:A_TOM_1 != ATOM_1
• Listy są oznaczone w nawiasach, a domniemana NILznajduje się na końcu każdej listy. Elementy na liście są oddzielone przecinkami, a nie białymi znakami, jak w większości współczesnych Lisps. Tak więc lista (ATOM 1, (ATOM 2))byłaby {[ATOM 1] -> {[ATOM 2] -> NIL} -> NIL}.

QUOTE:

• Bierze jeden argument, którym może być atom (pojedynczy element) lub lista połączona. Zwraca dokładnie argument.
• Przypadki testowe:
• (QUOTE, ATOM 1) -> ATOM 1
• (QUOTE, (ATOM 1, ATOM 2)) -> (ATOM 1, ATOM 2)

ATOM:

• Bierze jeden argument, którym może być atom (pojedynczy element) lub lista połączona. Zwraca T(prawda), jeśli argument jest atomem, lub NIL(fałsz), jeśli argument nie jest atomem.
• Przypadki testowe:
• (ATOM, (QUOTE, ATOM 1)) -> T
• (ATOM, (QUOTE, (ATOM 1, ATOM 2))) -> NIL

EQ:

• Bierze dwa argumenty, które muszą być atomami (zachowanie jest niezdefiniowane, jeśli jeden z argumentów nie jest atomem). Zwraca T(prawda), jeśli dwa atomy są równoważne, lub NIL(fałsz), jeśli nie są.
• Przypadki testowe:
• (EQ, (QUOTE, ATOM 1), (QUOTE, ATOM 1)) -> T
• (EQ, (QUOTE, ATOM 1), (QUOTE, ATOM 2)) -> NIL

CAR:

• Bierze jeden argument, który musi być listą (zachowanie nie jest zdefiniowane, jeśli nie jest listą). Zwraca pierwszy atom (głowa) z tej listy.
• Przypadki testowe:
• (CAR, (QUOTE, (ATOM 1, ATOM 2))) -> ATOM 1

CDR:

• Bierze jeden argument, który musi być listą (zachowanie nie jest zdefiniowane, jeśli nie jest listą). Zwraca każdy atom oprócz pierwszego atomu z listy, tj. Ogon. Zauważ, że każda lista kończy się na domniemanym NIL, więc uruchomienie CDRlisty, która wydaje się mieć tylko jeden element, powróci NIL.
• Przypadki testowe:
• (CDR, (QUOTE, (ATOM 1, ATOM 2))) -> (ATOM 2)
• (CDR, (QUOTE, (ATOM 1))) -> NIL

CONS:

• Przyjmuje dwa argumenty. Pierwszy może być atomem lub listą, ale drugi musi być listą lub NIL. Przygotowuje pierwszy argument do drugiego argumentu i zwraca nowo utworzoną listę.
• Przypadki testowe:
• (CONS, (QUOTE, ATOM 1), (QUOTE, NIL)) -> (ATOM 1)
• (CONS, (QUOTE, ATOM 1), (CONS, (QUOTE, ATOM 2), (QUOTE, NIL))) -> (ATOM 1, ATOM 2)

COND:

• To jest swego rodzaju oświadczenie LISP „jeśli-inaczej”. Pobiera argumenty o zmiennej długości, z których każdy musi być listą długości dokładnie 2. Dla każdej listy argumentów w kolejności oceń pierwszy termin, a jeśli to prawda (T), zwróć powiązany drugi termin i wyjdź z funkcji . Jeśli pierwszy warunek nie jest prawdziwy, przejdź do następnego argumentu i przetestuj jego stan i tak dalej, aż do osiągnięcia pierwszego prawdziwego warunku. Można założyć, że co najmniej jeden z warunków argumentu jest prawdziwy - jeśli wszystkie są fałszywe, jest to zachowanie nieokreślone. Dobry przykład zachowania tej funkcji znajduje się na stronie 4.
• Przypadki testowe:
• (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:

• Definiuje anonimową funkcję. Przyjmuje dwa argumenty, pierwszy to lista atomów reprezentujących argumenty funkcji, a drugi to dowolne wyrażenie S (ciało funkcji), które zwykle używa argumentów.
• Przypadki testowe:
• Definiowanie i używanie anonimowej funkcji „isNull”:
• ((LAMBDA, (ATOM 1), (EQ, ATOM 1, (QUOTE, NIL))), (QUOTE, NIL)) -> T
• ((LAMBDA, (ATOM 1), (EQ, ATOM 1, (QUOTE, NIL))), (QUOTE, ATOM 1)) -> NIL

LABEL:

• Nadaje nazwę anonimowej LAMBDAfunkcji, która umożliwia również wywoływanie tej funkcji rekurencyjnie w treści LAMBDA. Bierze dwa argumenty, pierwszy to etykieta, a drugi to LAMBDAfunkcja, z którą etykieta powinna być powiązana. Zwraca podaną nazwę. Wszystkie LABELnazwy mają zasięg globalny, a przedefiniowanie LABELzachowania jest niezdefiniowane.
• Zabawne LABELjest to, że tak naprawdę nie jest konieczne tworzenie funkcji rekurencyjnych, ponieważ obecnie wiemy, że LAMBDAmożna go użyć z „Y-Combinatorem” do wykonania tego zadania, ale McCarthy nie był świadomy tej metody, pisząc oryginalny artykuł. W każdym razie znacznie ułatwia pisanie programów.
• Przypadki testowe:
• (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
• (po uruchomieniu powyższego) (SUBST, (QUOTE, A), (QUOTE, B), (QUOTE, (A, B, C))) -> (A, A, C)

Aby pomóc w wizualizacji SUBSTpowyższej funkcji, może być reprezentowana jako ten pseudokod podobny do Pythona:

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:])

KOŃCOWA SPRAWA TESTOWA:

Jeśli poprawnie transkrybowałem, Twój tłumacz powinien być w stanie interpretować za EVALpomocą tego kodu:

(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))))))

Po uruchomieniu tego behemota ta linia powinna zwrócić (A, B, C):

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

Jednak, aby zacytować samego Johna McCarthy'ego na stronie 16, wygląda na to, że zabrakło mu znaków na swoim komputerze:

Gdyby na komputerze dostępnych było więcej znaków, można by to znacznie poprawić ...

Dlatego to wyzwanie jest oznaczone kodem golfowym i zwycięzcą zostanie najkrótsza odpowiedź w postaci. Obowiązują standardowe luki. Powodzenia!

Uwaga na temat ciągów znaków : Rozumiem, że niektórzy sądzą, że można wygrać to wyzwanie, używając Lisp i modyfikując składnię, aby pasowała do języka hosta, a następnie używając łańcucha (eval). Nie jestem szczególnie przekonany, że to podejście niekoniecznie zwycięży, szczególnie dzięki regułom nazewnictwa identyfikatorów, a nawet jeśli tak, to sądzę, że zakazanie ciągów znaków evalwe wszystkich językach byłoby subiektywnym i śliskim nachyleniem. Ale nie chcę karać ludzi za podejmowanie tego wyzwania we właściwy sposób, więc mogę pozwolić dwóm zwycięzcom na to wyzwanie, jednym w języku podobnym do Lisp i drugim w języku innym niż Lispy, jeśli stanie się to problemem .

Python 3, 770 bajtów

To jest REPL na stdin / stdout. Oczekuje, że każda linia będzie pełną instrukcją lub pustą. evalsłuży do skrócenia implementacji, ale poza tym nie jest konieczny dla logiki.

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)))