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 LABEL
powinny 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).
NIL
ma 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
NIL
znajduje 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, lubNIL
(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, lubNIL
(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 uruchomienieCDR
listy, która wydaje się mieć tylko jeden element, powróciNIL
. - 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
LAMBDA
funkcji, która umożliwia również wywoływanie tej funkcji rekurencyjnie w treściLAMBDA
. Bierze dwa argumenty, pierwszy to etykieta, a drugi toLAMBDA
funkcja, z którą etykieta powinna być powiązana. Zwraca podaną nazwę. WszystkieLABEL
nazwy mają zasięg globalny, a przedefiniowanieLABEL
zachowania jest niezdefiniowane. - Zabawne
LABEL
jest to, że tak naprawdę nie jest konieczne tworzenie funkcji rekurencyjnych, ponieważ obecnie wiemy, żeLAMBDA
moż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 SUBST
powyż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 EVAL
pomocą 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 eval
we 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 .
źródło
((LAMBDA, (ATOM 1), (EQ, ATOM 1, (QUOTE, NIL))), (QUOTE, NIL)) -> NIL
gdzie(QUOTE NIL)
na końcu jest wejście, więc to powinno wrócićT
?-> NIL
CONS
mówisz: „Dołącza pierwszy argument do drugiego argumentu i zwraca nowo utworzoną listę”, ale przypadki testowe pokazują drugi argument dołączany do pierwszego. Który jest poprawny?Odpowiedzi:
Python 3, 770 bajtów
To jest REPL na stdin / stdout. Oczekuje, że każda linia będzie pełną instrukcją lub pustą.
eval
służy do skrócenia implementacji, ale poza tym nie jest konieczny dla logiki.źródło
SUBST
przykład jest wciąż łamany (o ile wiem) jako przypadek testowy. Jeden z nichCOND
osiąga koniec, zanim znajduje aT
.EVAL
(tak miło mnie zaskoczyło, że trafiłem już za pierwszym razem!) Przyznam ci nagrodę i zaakceptowaną odpowiedź już teraz!R(E(P(l)
konfigurację ;-)repr
, E =eval
, P =parse
, l =line
.