Programiści Lisp mogą pochwalić się tym, że Lisp jest potężnym językiem, który można zbudować z bardzo małego zestawu prymitywnych operacji . Zastosujmy ten pomysł w praktyce, grając w golfa dla tłumacza dialektu o nazwie tinylisp.

Specyfikacja języka

W tej specyfikacji każdy warunek, którego wynik jest opisany jako „niezdefiniowany”, może zrobić wszystko w twoim tłumaczu: zawiesić się, zawieść po cichu, wygenerować losowy gobbldegook lub działać zgodnie z oczekiwaniami. Referencyjna implementacja w Pythonie 3 jest dostępna tutaj .

Składnia

Tokeny w tinylisp są (, )lub dowolnym ciągiem jednego lub więcej drukowalnych znaków ASCII, z wyjątkiem nawiasów lub spacji. (Tj. Wyrażenie regularne:. [()]|[^() ]+) Każdy token składający się wyłącznie z cyfr jest literałem całkowitym. (Zera są w porządku). Każdy żeton, który zawiera nie-cyfr jest symbolem, nawet liczbowe wyglądające przykłady podoba 123abc, 3.14i -10. Wszystkie białe znaki (w tym co najmniej 32 i 10 znaków ASCII) są ignorowane, z wyjątkiem przypadków, gdy oddziela tokeny.

Program Tinylisp składa się z szeregu wyrażeń. Każde wyrażenie jest albo liczbą całkowitą, symbolem, albo wyrażeniem s (lista). Listy zawierają zero lub więcej wyrażeń owiniętych w nawiasy. Nie stosuje się separatora między elementami. Oto przykłady wyrażeń:

4
tinylisp!!
()
(c b a)
(q ((1 2)(3 4)))

Wyrażenia, które nie są dobrze sformułowane (w szczególności mają niedopasowane nawiasy), dają niezdefiniowane zachowanie. (Implementacja referencyjna automatycznie zamyka otwarte pareny i przestaje parsować w niedopasowanych parens zamykających.)

Typy danych

Typami danych Tinylisp są liczby całkowite, symbole i listy. Wbudowane funkcje i makra można również uznać za typ, chociaż ich format wyjściowy jest niezdefiniowany. Lista może zawierać dowolną liczbę wartości dowolnego typu i może być dowolnie głęboko zagnieżdżona. Liczby całkowite muszą być obsługiwane co najmniej od -2 ^ 31 do 2 ^ 31-1.

Pusta lista - ()określana również jako zero - i liczba całkowita 0są jedynymi wartościami uznanymi za logicznie fałszywe; wszystkie inne liczby całkowite, niepuste listy, wbudowane i wszystkie symbole są logicznie prawdziwe.

Ocena

Wyrażenia w programie są oceniane w kolejności, a wyniki każdego z nich wysyłane do standardowego wyjścia (więcej o formatowaniu wyjściowym później).

• Literał całkowity ocenia się sam.
• Pusta lista ()ocenia się sama.
• Lista jednego lub więcej elementów ocenia pierwszy element i traktuje go jako funkcję lub makro, wywołując go z pozostałymi elementami jako argumentami. Jeśli element nie jest funkcją / makro, zachowanie jest niezdefiniowane.
• Symbol jest obliczany jako nazwa, podając wartość powiązaną z tą nazwą w bieżącej funkcji. Jeśli nazwa nie jest zdefiniowana w bieżącej funkcji, ocenia się na związaną z nią wartość w zakresie globalnym. Jeśli nazwa nie jest zdefiniowana w bieżącym lub globalnym zasięgu, wynik jest niezdefiniowany (implementacja odniesienia wyświetla komunikat o błędzie i zwraca zero).

Wbudowane funkcje i makra

Tinylisp ma siedem wbudowanych funkcji. Funkcja ocenia każdy z argumentów przed zastosowaniem do nich jakiejś operacji i zwrócenia wyniku.

• c- minus [lista truct]. Pobiera dwa argumenty, wartość i listę, i zwraca nową listę uzyskaną przez dodanie wartości na początku listy.
• h- głowa ( samochód , w terminologii Lisp). Pobiera listę i zwraca pierwszy element lub zero, jeśli podano zero.
• t- ogon ( cdr , w terminologii Lisp). Pobiera listę i zwraca nową listę zawierającą wszystkie oprócz pierwszego elementu lub zero, jeśli podano zero.
• s- odejmować. Pobiera dwie liczby całkowite i zwraca pierwszy minus drugi.
• l- mniej niż. Przyjmuje dwie liczby całkowite; zwraca 1, jeśli pierwszy jest mniejszy niż drugi, w przeciwnym razie 0.
• e- równy. Pobiera dwie wartości tego samego typu (obie liczby całkowite, obie listy lub oba symbole); zwraca 1, jeśli dwa są równe (lub identyczne w każdym elemencie), 0 w przeciwnym razie. Testowanie wbudowanych pod kątem równości jest niezdefiniowane (implementacja referencyjna działa zgodnie z oczekiwaniami).
• v- eval. Pobiera jedną listę, liczbę całkowitą lub symbol reprezentujący wyrażenie i ocenia je. Na przykład robienie (v (q (c a b)))jest tym samym, co robienie (c a b); (v 1)daje 1.

„Wartość” obejmuje tutaj dowolną listę, liczbę całkowitą, symbol lub wbudowane, o ile nie określono inaczej. Jeśli funkcja jest wymieniona jako przyjmująca określone typy, przekazywanie jej różnych typów jest zachowaniem niezdefiniowanym, podobnie jak przekazywanie niewłaściwej liczby argumentów (implementacja referencji na ogół ulega awarii).

Istnieją trzy wbudowane makra w Tinylisp. Makro, w przeciwieństwie do funkcji, nie ocenia swoich argumentów przed zastosowaniem do nich operacji.

• q- cytat. Przyjmuje jedno wyrażenie i zwraca je bez oceny. Np. Ocena (1 2 3)daje błąd, ponieważ próbuje wywołać 1jako funkcję lub makro, ale (q (1 2 3))zwraca listę (1 2 3). Ocena adaje wartość powiązaną z nazwą a, ale (q a)sama nazwa.
• i- Jeśli. Przyjmuje trzy wyrażenia: warunek, wyrażenie iftrue i wyrażenie iffalse. Najpierw ocenia stan. Jeśli wynikiem jest fałsz ( 0lub zero), ocenia i zwraca wyrażenie iffalse. W przeciwnym razie ocenia i zwraca wyrażenie iftrue. Zauważ, że wyrażenie, które nie jest zwracane, nigdy nie jest oceniane.
• d- def. Przyjmuje symbol i wyrażenie. Ocenia wyrażenie i wiąże je z danym symbolem traktowanym jako nazwa o zasięgu globalnym , a następnie zwraca symbol. Próba ponownego zdefiniowania nazwy powinna zakończyć się niepowodzeniem (po cichu, z komunikatem lub przez awarię; implementacja referencyjna wyświetla komunikat o błędzie). Uwaga: nie jest konieczne cytowanie nazwy przed jej przekazaniem d, choć konieczne jest zacytowanie wyrażenia, jeśli jest to lista lub symbol, którego nie chcesz oceniać: np (d x (q (1 2 3))).

Przekazywanie nieprawidłowej liczby argumentów do makra jest niezdefiniowanym zachowaniem (awaria implementacji odniesienia). Przekazywanie czegoś, co nie jest symbolem jako pierwszego argumentu, djest niezdefiniowanym zachowaniem (implementacja odwołania nie powoduje błędu, ale wartości nie można później odwoływać się).

Funkcje i makra zdefiniowane przez użytkownika

Począwszy od tych dziesięciu wbudowanych wersji, język można rozszerzyć, konstruując nowe funkcje i makra. Nie mają one dedykowanego typu danych; są to po prostu listy o określonej strukturze:

• Funkcja to lista dwóch elementów. Pierwsza to albo lista jednej lub więcej nazw parametrów, albo pojedyncza nazwa, która otrzyma listę dowolnych argumentów przekazanych do funkcji (pozwalając w ten sposób na funkcje zmienności). Drugi to wyrażenie, które jest ciałem funkcji.
• Makro jest takie samo jak funkcja, tyle że zawiera zero przed nazwami parametrów, co czyni go listą składającą się z trzech elementów. (Próba wywołania list składających się z trzech elementów, które nie zaczynają się od zera, jest niezdefiniowanym zachowaniem; implementacja referencyjna ignoruje pierwszy argument i traktuje je również jako makra).

Na przykład następujące wyrażenie jest funkcją, która dodaje dwie liczby całkowite:

(q               List must be quoted to prevent evaluation
 (
  (x y)          Parameter names
  (s x (s 0 y))  Expression (in infix, x - (0 - y))
 )   
)

I makro, które przyjmuje dowolną liczbę argumentów, ocenia i zwraca pierwszy:

(q
 (
  ()
  args
  (v (h args))
 )
)

Funkcje i makra mogą być wywoływane bezpośrednio, powiązane z nazwami za pomocą di przekazywane do innych funkcji lub makr.

Ponieważ ciała funkcji nie są wykonywane w czasie definicji, funkcje rekurencyjne można łatwo zdefiniować:

(d len
 (q (
  (list)
  (i list                      If list is nonempty
   (s 1 (s 0 (len (t list))))  1 - (0 - len(tail(list)))
   0                           else 0
  )
 ))
)

Zauważ jednak, że powyższe nie jest dobrym sposobem na zdefiniowanie funkcji długości, ponieważ nie używa ...

Rekurencja wezwania ogona

Rekurencja przywołania ogona jest ważną koncepcją w Lisp. Implementuje pewne rodzaje rekurencji jako pętle, dzięki czemu stos wywołań jest niewielki. Twój interpreter Tinylisp musi wdrożyć odpowiednią rekurencję wywołania ogona!

• Jeśli wyrażenie zwrotne funkcji lub makra zdefiniowanej przez użytkownika jest wywołaniem innej funkcji lub makra zdefiniowanego przez użytkownika, interpreter nie może używać rekurencji do oceny tego wywołania. Zamiast tego musi zastąpić bieżącą funkcję i argumenty nową funkcją i argumentami oraz zapętlić do momentu rozwiązania łańcucha wywołań.
• Jeśli wyrażenie zwrotne funkcji zdefiniowanej przez użytkownika lub makra jest wywołaniem i, nie należy od razu oceniać wybranej gałęzi. Zamiast tego sprawdź, czy jest to wywołanie innej funkcji zdefiniowanej przez użytkownika lub makra. Jeśli tak, zamień funkcję i argumenty jak wyżej. Dotyczy to dowolnie głęboko zagnieżdżonych wystąpień i.

Rekurencja ogona musi działać zarówno dla rekurencji bezpośredniej (funkcja wywołuje samą funkcję), jak i rekurencji pośredniej (funkcja awywołuje funkcję, bktóra wywołuje [itd.], Która wywołuje funkcję a).

Funkcja rekurencyjnej długości ogona (z funkcją pomocniczą len*):

(d len*
 (q (
  (list accum)
  (i list
   (len*
    (t list)
    (s 1 (s 0 accum))
   )
   accum
  )
 ))
)
(d len
 (q (
  (list)
  (len* list 0)
 ))
)

Ta implementacja działa dla dowolnie dużych list, ograniczonych tylko maksymalnym rozmiarem liczby całkowitej.

Zakres

Parametry funkcji to zmienne lokalne (w rzeczywistości stałe, ponieważ nie można ich modyfikować). Są one w zasięgu podczas wykonywania treści tego wywołania tej funkcji i poza zasięgiem podczas głębszych wywołań i po powrocie funkcji. Mogą „ukrywać” globalnie zdefiniowane nazwy, przez co nazwa globalna jest tymczasowo niedostępna. Na przykład poniższy kod zwraca 5, a nie 41:

(d x 42)
(d f
 (q (
  (x)
  (s x 1)
 ))
)
(f 6)

Jednak poniższy kod zwraca 41, ponieważ xna poziomie połączenia 1 nie jest dostępny z poziomu połączenia 2:

(d x 42)
(d f
 (q (
  (x)
  (g 15)
 ))
)
(d g
 (q (
  (y)
  (s x 1)
 ))
)
(f 6)

Jedynymi nazwami w zakresie w danym momencie są 1) lokalne nazwy aktualnie wykonywanej funkcji, jeśli takie istnieją, oraz 2) nazwy globalne.

Wymagania dotyczące przedłożenia

Wejście i wyjście

Twój interpreter może odczytać program ze standardowego wejścia lub z pliku określonego przez standardowe wejście lub argument wiersza poleceń. Po dokonaniu oceny każdego wyrażenia, powinien on wypisać wynik tego wyrażenia na standardowe wyjście z końcowym znakiem nowej linii.

• Liczby całkowite powinny być wyprowadzane w najbardziej naturalnej reprezentacji języka implementacji. Mogą być wyprowadzane ujemne liczby całkowite z wiodącymi znakami ujemnymi.
• Symbole powinny być wyprowadzane jako ciągi, bez otaczających cudzysłowów lub znaków specjalnych .
• Listy powinny być wyprowadzane ze wszystkimi elementami oddzielonymi spacjami i owinięte w nawiasy. Przestrzeń wewnątrz nawiasów jest opcjonalne: (1 2 3)i ( 1 2 3 )to zarówno dopuszczalne formaty.
• Wyprowadzanie wbudowanych funkcji i makr jest niezdefiniowanym zachowaniem. (Interpretacja referencyjna wyświetla je jako <built-in function>.)

Inny

Interpretator referencyjny obejmuje środowisko REPL i możliwość ładowania modułów Tinylisp z innych plików; są one zapewniane dla wygody i nie są wymagane do tego wyzwania.

Przypadki testowe

Przypadki testowe są podzielone na kilka grup, dzięki czemu można testować prostsze przed przystąpieniem do bardziej złożonych. Jednak będą również działać dobrze, jeśli zrzucisz je wszystkie w jednym pliku razem. Po prostu nie zapomnij usunąć nagłówków i oczekiwanego wyniku przed jego uruchomieniem.

Jeśli poprawnie zaimplementowano rekurencję wywołania ogona, końcowa (wieloczęściowa) skrzynka testowa powróci bez powodowania przepełnienia stosu. Implementacja referencyjna oblicza to na moim laptopie w około sześć sekund.

Python 2, 685 675 660 657 646 642 640 bajtów

import sys,re
E=[]
G=zip("chtsle",[eval("lambda x,y=0:"+f)for f
in"[x]+y (x+[E])[0] x[1:] x-y +(x<y) +(x==y)".split()])
def V(e,L=E):
 while 1:
    try:return e and int("0%s"%e)
    except:A=e[1:]
    if""<e:return dict(G+L).get(e,e)
    f=V(e[0],L)
    if""<f:
     if f in"iv":t=V(A[0],L);e=(e[~bool(t)],t)[f>"u"];continue
     if"e">f:G[:]+=(A[0],V(A[1],L)),
     return A[0]
    if[]>f or f[0]:A=[V(a,L)for a in A]
    if[]>f:return f(*A)
    P,e=f[-2:];L=([(P,A)],zip(P,A))[P<""]
F=lambda x:V<x<""and"(%s)"%" ".join(map(F,x))or"%s"%x
for t in re.sub("([()])"," \\1 ",sys.stdin.read()).split():
 if")"==t:t=E.pop()
 if"("==t:E+=[],
 elif E:E[-1]+=t,
 else:print F(V(t))

Odczytuje dane wejściowe ze STDIN i zapisuje dane wyjściowe do STDOUT.

Chociaż nie jest to bezwzględnie wymagane, interpreter obsługuje funkcje zerowe i makra oraz optymalizuje wywołania tail wykonywane za pośrednictwem v.

Wyjaśnienie

Rozbiór gramatyczny zdania

Analizować dane wejściowe, najpierw otoczyć każdego wystąpienie (i )ze spacjami i podzielić wynikowy ciąg znaków w słowach; daje nam to listę tokenów. Utrzymujemy stos wyrażeń E, który początkowo jest pusty. Skanujemy tokeny w celu:

• jeśli napotkamy a (, pchamy pustą listę na górze stosu wyrażeń;
• jeśli napotkamy a ), wstawiamy wartość na górze stosu wyrażeń i dołączamy ją do listy, która była wcześniej pod nią na stosie;
• w przeciwnym razie dołączamy bieżący token jako ciąg do listy na górze stosu wyrażeń (na tym etapie zachowujemy liczby całkowite jako ciągi i analizujemy je podczas analizy).

Jeśli podczas przetwarzania zwykłego tokena lub po usunięciu wyrażenia ze stosu z tego powodu ), stos wyrażeń jest pusty, znajdujemy się na wyrażeniu najwyższego poziomu i oceniamy wartość, którą w innym przypadku dodalibyśmy, używając V()i wydrukuj wynik, odpowiednio sformatowany przy użyciu F().

Ocena

Utrzymujemy zakres globalny G, jako listę par klucz / wartość. Początkowo zawiera tylko wbudowane funkcje (ale nie makra i nie v, które traktujemy jako makro), które są zaimplementowane jako lambdas.

Ocena dzieje się wewnątrz V(), który odbywa się wyraz oceniać e, a lokalny zakres, L, który jest też listę par klucz / wartość (przy ocenie wyrażenia najwyższego poziomu, zakres lokalny jest pusty). Wnętrzności V()żywo w nieskończonej pętli, czyli w jaki sposób przeprowadzamy optymalizację wywołania ogona (TCO), jak wyjaśniono później.

Przetwarzamy ezgodnie z jego rodzajem:

• jeśli jest to pusta lista lub ciąg znaków zamienny na int, zwracamy go natychmiast (być może po konwersji na int); Inaczej,

• jeśli jest to ciąg znaków, sprawdzamy go w słowniku zbudowanym z połączenia globalnych i lokalnych zasięgów. Jeśli znajdziemy powiązaną wartość, zwrócimy ją; w przeciwnym razie, emusi być nazwą makra wbudowanego (tj q, i, dlub v), i zwrócić go bez zmian. W przeciwnym razie, jeśli enie jest łańcuchem,

• ejest listą (niepustą), tj. wywołaniem funkcji. Oceniamy pierwszy element listy, tj. Wyrażenie funkcji, wywołując V()rekurencyjnie (przy użyciu bieżącego zasięgu lokalnego); nazywamy wynik f. Reszta listy Ato lista argumentów. fmoże być tylko ciągiem, w którym to przypadku jest wbudowanym makrem (lub funkcją v), lambda, w którym to przypadku jest funkcją wbudowaną lub listą, w którym to przypadku jest funkcją lub makro zdefiniowanym przez użytkownika.

  Jeśli fjest to ciąg znaków, tj. Wbudowane makro, obsługujemy go w miejscu. Jeśli jest to makro ilub v, oceniamy jego pierwszy operand i albo odpowiednio wybieramy drugi lub trzeci operand, w przypadku i, albo wykorzystujemy wynik pierwszego operandu, w przypadku v; zamiast rekurencyjnej oceny wybranego wyrażenia, które pokonałoby TCO, po prostu zamieniamy eto wyrażenie i przeskakujemy na początek pętli. Jeśli fjest to makro d, dodajemy parę, której pierwszym elementem jest pierwszy operand, a którego drugim elementem jest wynik oceny drugiego operandu, do zasięgu globalnego G, i zwracamy pierwszy operand. W przeciwnym razie fjest to makro q, w którym to przypadku po prostu zwracamy jego operand bezpośrednio.

  Z drugiej strony, jeśli fjest lambda lub listą, której pierwszym elementem nie jest (), to jest funkcją niepustą, a nie makrem, w którym to przypadku oceniamy jej argumenty, tj. Elementy Ai zamieniamy Ana wynik.

  Jeśli fjest lambda, nazywamy ją, przekazując rozpakowane argumenty Ai zwracamy wynik.

  W przeciwnym razie fjest to lista, tj. Funkcja lub makro zdefiniowane przez użytkownika; jego lista parametrów jest przedostatnim elementem, a jego ciało jest ostatnim elementem. Podobnie jak w przypadku makr ii vaby wykonać TCO, nie oceniamy treści rekurencyjnie, lecz zastępujemy eje treścią i przechodzimy do następnej iteracji. W przeciwieństwie ia vjednak możemy również zastąpić zakresu lokalnego, Lz nowej lokalnej zakresu funkcji. Jeśli lista parametrów P, w rzeczywistości jest listą, nowy zasięg lokalny jest tworzony przez skompresowanie listy parametrów Pza pomocą listy argumentów A; w przeciwnym razie mamy do czynienia z funkcją wariadyczną, w którym to przypadku nowy zasięg lokalny ma tylko jeden element, parę (P, A).

REPL

Jeśli chcesz się nim bawić, oto wersja interpretera REPL. Obsługuje redefiniowanie symboli i importowanie plików za pomocą argumentów wiersza poleceń lub (import <filename>)makra. Aby wyjść z interpretera, zakończ wprowadzanie (zwykle Ctrl + D lub Ctrl + Z).

try:import sys,re,readline
except:0
E=[];G=zip("chtsle",[eval("lambda x,y=0:"+f)for f
in"[x]+y (x+[E])[0] x[1:] x-y +(x<y) +(x==y)".split()])
def V(e,L=E):
 while 1:
    try:return e and int("0%s"%e)
    except:A=e[1:]
    if""<e:return dict(G+L).get(e,e)
    f=V(e[0],L)
    if""<f:
     if f in"iv":t=V(A[0],L);e=(e[~bool(t)],t)[f>"u"];continue
     if"e">f:G[:]+=(A[0],V(A[1],L)),
     elif"j">f:X(open(str(A[0])).read())
     return A[0]
    if[]>f or f[0]:A=[V(a,L)for a in A]
    if[]>f:return f(*A)
    P,e=f[-2:];L=([(P,A)],zip(P,A))[P<""]
F=lambda x:V<x<""and"(%s)"%" ".join(map(F,x))or"%s"%x
def X(s,v=0):
 for t in re.sub("([()])"," \\1 ",s).split():
    if")"==t:t=E.pop()
    if"("==t:E[:]+=[],
    elif E:E[-1]+=t,
    else:
     x=V(t)
     if v:print F(x)
for f in sys.argv[1:]:X("(g %s)"%f)
while 1:
 try:X(raw_input(">."[[]<E]*3+" "),1)
 except EOFError:break
 except KeyboardInterrupt:E=[];print
 except Exception as e:print"Error: "+e.message

A oto przykładowa sesja z implementacją sortowania korespondencji seryjnej:

>>> (d let d) (d if i) (d head h) (d tail t) (d prepend c) (d less l)
let
if
head
tail
prepend
less
>>>
>>> (let list (q (x... x...)))
list
>>> (let lambda (q (() (params body) (list params body))))
lambda
>>> (let def (q (() (name params body) (
...     v (list (q let) name (list (q lambda) params body))
... ))))
def
>>>
>>> (def else(body) body)
else
>>> (def or(x y) ( if x x y ))
or
>>> (def and(x y) ( if x y x ))
and
>>>
>>> (def front-half(L) ( front-half/impl L L ))
front-half
>>> (def front-half/impl(L M) (
...     if M (
...         prepend (head L)
...                 (front-half/impl (tail L) (tail (tail M)))
...     ) (else
...         ()
...     )
... ))
front-half/impl
>>>
>>> (def back-half(L) ( back-half/impl L L ))
back-half
>>> (def back-half/impl(L M) (
...     if M (
...         back-half/impl (tail L) (tail (tail M))
...     ) (else
...         L
...     )
... ))
back-half/impl
>>>
>>> (def merge(L M comp) (
...     if (and L M) (
...         if (comp (head M) (head L)) (
...             prepend (head M) (merge L (tail M) comp)
...         ) (else (
...             prepend (head L) (merge (tail L) M comp)
...         ))
...     ) (else (
...         or L M
...     ))
... ))
merge
>>>
>>> (def sort(L comp) (
...     if (and L (tail L)) (
...         merge (sort (front-half L) comp)
...               (sort (back-half L) comp)
...               comp
...     ) (else
...         L
...     )
... ))
sort
>>>
>>>
>>> (let my-list (list 4 7 2 5 9 1 6 10 8 3))
my-list
>>> my-list
(4 7 2 5 9 1 6 10 8 3)
>>> (sort my-list less)
(1 2 3 4 5 6 7 8 9 10)
>>> (sort my-list (lambda(x y) ( less y x )))
(10 9 8 7 6 5 4 3 2 1)

C (GNU), 1095 bajtów

Duża część akcji rozgrywa się w gigantycznej vfunkcji. Zamiast jawnego wdrażania rekurencji ogona, vjest on tak skonstruowany, że wiele wywołań od vdo vbędzie obsługiwanych przez optymalizację rekurencji ogona gcc. Nie ma śmieci.

Powoduje to częste korzystanie z rozszerzeń GCC, więc można je było skompilować tylko za pomocą gcc (użyj polecenia gcc -w -Os tl.c). Używa również niektórych scanfrozszerzeń, które nie były dostępne w systemie Windows, których zwykle używam. Perspektywa napisania parsera ze standardem scanfbyła tak okropna, że ​​zamiast tego użyłem maszyny wirtualnej z systemem Linux do przetestowania programu. Analiza bez scanfklas znaków prawdopodobnie spowodowałaby dodanie ponad 100 bajtów.

#define O(...)({o*_=malloc(32);*_=(o){__VA_ARGS__};_;})
#define P printf
#define F(I,B)({for(I;x->c;x=x->l)B;})
#define Z return
typedef struct o{struct o*n,*l,*c;int i,t;}o;E(o a,o b){Z
a.n?!strcmp(a.n,b.n):a.c?b.c&&E(*a.c,*b.c)&E(*a.l,*b.l):!b.c&a.i==b.i;}p(o*x){x->t?P("%d ",x->i):x->n?P("%s ",x->n):F(P("("),p(x->c);P(")"));}o*x,G,N;*C(o*h,o*t){Z
O(c:h,l:t);}o*v(o*x,o*e){o*W(o*l,o*e){Z
l->c?C(v(l->c,e),W(l->l,e)):&N;}o*y,*a,*f;int t;Z
x->c?y=v(x->c,e),x=x->l,t=y->i,t?9/t?a=v(x->c,e),t>7?(t>8?a->c:a->l)?:a:t>6?v(a,e):t<6?x=v(x->l->c,e),t>4?C(a,x):O(t:1,i:t>3?E(*a,*x):t>2?a->i<x->i:a->i-x->i):v((a-&N&&!a->t|a->i?x:x->l)->l->c,e):(t&1&&d(x->c->n,v(x->l->c,e)),x->c):(y->l->l->l?y=y->l:(x=W(x,e)),a=y->c,v(y->l->c,a->n?O(n:a->n,c:x,l:&G):F(f=&G,(f=O(n:a->c->n,c:x->c,l:f),a=a->l);f))):x->n?e->n?strcmp(x->n,e->n)?v(x,e->l):e->c:e:x;}d(o*n,o*x){*v(O(n:""),&G)=(o){n:n,c:x,l:O()};}*R(h){char*z,*q;Z
scanf(" %m[^ \n()]",&q)>0?h=strtoul(q,&z,10),C(*z?O(n:q):O(t:1,i:h),R()):~getchar()&1?q=R(),C(q,R()):&N;}main(i){for(;++i<12;)d(strndup("slecivthqd"+i-2,1),O(i:i));F(x=R(),p(v(x->c,&G)));}

Częściowo nie golfista

typedef struct o o;
struct o {
    char* n;
    o* l, //next in this list
     * c; 
    int i,
        t;
} ;



#define O(...)({o*_=malloc(32);*_=(o){__VA_ARGS__};_;})

E(o a, o b) { //tests equality 
    return
        a.n ? !strcmp(a.n,b.n) :
        a.t ? a.i==b.i :
        a.c ? b.c && E(*a.c,*b.c)&E(*a.l,*b.l) :
        !b.c
    ;
}

#define P printf


p(o*x){
    x->t?P("%d ",x->i):x->n?P("%s ",x->n):({for(P("(");x->c;x=x->l)p(x->c);P(")");});
}


o*_,G,N; //N = nil



o*C(o*h,o*t){return O(c:h,l:t);}


/*
        2 3 4 5 6 7 8 9 10 11
        s l e c i v t h d  q
    */


o* v(o* x, o* e) { //takes list, int, or name
    o*W(o* l, o* e) { //eval each item in list
        return l->c ? C(v(l->c ,e), W(l->l, e)) : &N;
    }

    o*y,*a,*f;int t;
    return x->c ? //nonempty list = function/macro call
        y = v(x->c,e), //evals to function/macro
        x = x->l,   //list position of first arg (if it exists)
        (t=y->t)?   //builtin no., if any
             t>9 ?
              t&1 ? x->c // 11 = q
                : //10 = d
                (d(x->c,v(x->l->c,e)),x->c)
           : (a = v(x->c,e), //eval'd first arg
             t)>7 ? // t/h
                (t > 8 ? a->c : a->l) ?: a
           : t>6 ? //v
                v(a,e)
           : (x = x->l, //position of 2nd arg in list
             t)>5 ? //i
                v( (a->n||a->l||a->i|a->t>1 ? x : x->l)->c, e)
           : (x = v(x->c,e), //evaluated 2nd arg
             t)>4 ? // c
                C(a,x)
           : O(t:1,i:
                t>3 ? E(*a,*x) :  //e
                t>2 ? a->i<x->i : //l
                      a->i-x->i   //s
              )
        :
        (
            y->l->l->l ? //whether this is macro
                y = y->l :
                (x = W(x,e)),  //eval args
            a = y->c,  //a = arg list
            //a = a->n ? x=C(x, &N), C(a, &N) : a, //transform variadic style to normal
            v(y->l->c,
               a->n ? //variadic
                O(n:a->n,c:x,l:&G)
              : ({
                   for(f=&G; a->c; a=a->l,x=x->l)
                      f=O(n:a->c->n, c: x->c, l:f);
                   f;
                })
            )
        )
    :
    x->n ? // name
        e->n ?
            strcmp(x->n,e->n) ?
                v(x,e->l)
            : e->c
        : e
     : x; //int or nil
}

d(o*n,o*x){
    * v(O(n:""),&G) =
        (o){n:n->n,c:x,l:O()};
}


;
o*R(){
    char*z,*q;int h;
return scanf(" %m[^ \n()]",&q)>0?
    h=strtoul(q,&z,10),
    C(*z ? O(n:q) : O(t:1,i:h), R())
: getchar()&1?&N:(q=R(),C(q,R()));
}
main(i) {

    for(;++i<12;) d(O(n:strndup("slecivthdq"+i-2,1)),O(t:i));

    o *q;
    for(q=R(); q->c; q=q->l) p(v(q->c,&G));

}

Ceylon, 2422 bajty

(Myślę, że to mój najdłuższy jak dotąd program w golfa.)

import ceylon.language{sh=shared,va=variable,fo=formal,O=Object}import ceylon.language.meta.model{F=Function}interface X{sh fo V v(S t);sh fo G g;}class G(va Map<S,V>m)satisfies X{v(S t)=>m[t]else nV;g=>this;sh S d(S s,V v){assert(!s in m);m=map{s->v,*m};return s;}}V nV=>nothing;class LC(G c,Map<S,V>m)satisfies X{g=>c;v(S t)=>m[t]else g.v(t);}alias C=>V|Co;interface Co{sh fo C st();}interface V{sh fo C l(X c,V[]a);sh default Boolean b=>0<1;sh fo C vO(X c);sh default V vF(X c){va C v=vO(c);while(is Co n=v){v=n.st();}assert(is V r=v);return r;}}class L(sh V*i)satisfies V{vO(X c)=>if(nonempty i)then i[0].vF(c).l(c,i.rest)else this;equals(O o)=>if(is L o)then i==o.i else 1<0;b=>!i.empty;string=>"(``" ".join(i)``)";hash=>i.hash;sh actual C l(X c,V[]p){value[h,ns,x]=i.size<3then[f,i[0],i[1]]else[m,i[1],i[2]];value n=if(is L ns)then[*ns.i.narrow<S>()]else ns;assert(is S|S[]n,is V x);V[]a=h(c,p);LC lC=if(is S n)then LC(c.g,map{n->L(*a)})else LC(c.g,map(zipEntries(n,a)));return object satisfies Co{st()=>x.vO(lC);};}}class S(String n)satisfies V{vO(X c)=>c.v(this);l(X c,V[]a)=>nV;equals(O o)=>if(is S o)then n==o.n else 1<0;hash=>n.hash;string=>n;}class I(sh Integer i)satisfies V{vO(X c)=>this;l(X c,V[]a)=>nV;equals(O o)=>if(is I o)then i==o.i else 1<0;hash=>i;b=>!i.zero;string=>i.string;}V[]f(X c,V[]a)=>[for(v in a)v.vF(c)];V[]m(X c,V[]a)=>a;L c(X c,V h,L t)=>L(h,*t.i);V h(X c,L l)=>l.i[0]else L();V t(X c,L l)=>L(*l.i.rest);I s(X c,I f,I s)=>I(f.i-s.i);I l(X c,I f,I s)=>I(f.i<s.i then 1else 0);I e(X c,V v1,V v2)=>I(v1==v2then 1else 0);C v(X c,V v)=>v.vO(c);V q(X c,V a)=>a;C i(X c,V d,V t,V f)=>d.vF(c).b then t.vO(c)else f.vO(c);S d(X c,S s,V x)=>c.g.d(s,x.vF(c));class B<A>(F<C,A>nat,V[](X,V[])h=f)satisfies V given A satisfies[X,V+]{vO(X c)=>nV;string=>nat.declaration.name;l(X c,V[]a)=>nat.apply(c,*h(c,a));}{<S->V>*}b=>{S("c")->B(`c`),S("h")->B(`h`),S("t")->B(`t`),S("s")->B(`s`),S("l")->B(`l`),S("e")->B(`e`),S("v")->B(`v`),S("q")->B(`q`,m),S("i")->B(`i`,m),S("d")->B(`d`,m)};[V*]p(String inp){value ts=inp.split(" \n()".contains,1<0,1<0);va[[V*]*]s=[];va[V*]l=[];for(t in ts){if(t in" \n"){}else if(t=="("){s=[l,*s];l=[];}else if(t==")"){l=[L(*l.reversed),*(s[0]else[])];s=s.rest;}else if(exists i=parseInteger(t),i>=0){l=[I(i),*l];}else{l=[S(t),*l];}}return l.reversed;}sh void run(){va value u="";while(exists l=process.readLine()){u=u+l+"\n";}V[]e=p(u);X c=G(map(b));for(v in e){print(v.vF(c));}}

Mogłem grać w golfa o kilka bajtów więcej, ponieważ użyłem dwuliterowych identyfikatorów w niektórych miejscach, ale zabrakło mi dość znaczących pojedynczych liter dla nich. Chociaż nawet w ten sposób nie wygląda tak bardzo jak Ceylon ...

Jest to implementacja obiektowa .

Mamy interfejs wartości Vz implementacją klas L(lista - tylko opakowanie wokół sekwencji CejlonuV ), S(symbol - opakowanie wokół łańcucha), I(liczba całkowita - opakowanie wokół liczby całkowitej Cejlonu) oraz B(funkcja wbudowana lub makro, opakowanie wokół Funkcja Ceylon).

Używam standardowej notacji równości Cejlonu, wdrażając equals metodę (a także hashatrybut, który tak naprawdę jest potrzebny tylko dla symboli), a także standardowy stringatrybut wyjścia.

Mamy atrybut boolowski b(który domyślnie jest prawdziwy, przesłonięty w IiL zwracać fałsz dla pustych list) oraz dwie metody l(wywołanie, tj. Użycie tego obiektu jako funkcji) i vO(ocena jednego kroku). Obie zwracają wartość lub obiekt kontynuacji, który pozwala następnie na ocenę dla jeszcze jednego kroku, i vF(w pełni oceniają) pętle, aż wynik nie będzie już kontynuacją.

Interfejs kontekstowy umożliwia dostęp do zmiennych. Istnieją dwie implementacje,G dla kontekstu globalnego (który pozwala dodawać zmienne za pomocą dwbudowanego) oraz LCdla kontekstu lokalnego, który jest aktywny podczas oceny wyrażenia funkcji użytkownika (wraca do kontekstu globalnego).

Ocena symboli uzyskuje dostęp do kontekstu, listy (jeśli nie są puste) oceniają najpierw oceniając ich pierwszy element, a następnie wywołując metodę wywołania. Wywołanie jest implementowane tylko przez listy i wbudowane - najpierw ocenia argument (jeśli funkcja, a nie makro), a następnie robi rzeczywiste interesujące rzeczy - dla wbudowanych tylko to, co jest zakodowane na stałe, dla list tworzy nowy kontekst lokalny i zwraca kontynuacja z tym.

Do wbudowanych użyłem sztuczki podobnej do tej, którą zastosowałem w moim Shift Interpreter , co pozwala mi zdefiniować je za pomocą potrzebnych typów argumentów, ale wywołać je za pomocą sekwencji ogólnej za pomocą odbicia (typy zostaną sprawdzone w czasie połączenia). Pozwala to uniknąć kłopotów związanych z konwersją / asercją typów w funkcjach / makrach, ale wymaga funkcji najwyższego poziomu, aby uzyskać Functionobiekty meta-modelu .

The p (parsowanie) dzieli ciąg znaków na spacje, znaki nowej linii i nawiasy, a następnie zapętla tokeny i tworzy listy przy użyciu stosu i listy bieżącej.

Tłumacz (w runmetodzie, która jest punktem wejścia) następnie pobiera tę listę wyrażeń (które są tylko wartościami), ocenia każde z nich i drukuje wynik.

Poniżej znajduje się wersja z komentarzami i przeglądarka formatująca.

W moim repozytorium Github znaleziono wcześniejszą wersję, zanim zacząłem grać w golfa (i nadal mam trochę nieporozumień na temat oceny listy), wkrótce ją tam zamieszczę (więc jeśli chcesz, zobacz oryginalną wersję ).

//  Tiny Lisp, tiny interpreter
//
// An interpreter for a tiny subset of Lisp, from which most of the
// rest of the language can be bootstrapped.
//
// Question:   https://codegolf.stackexchange.com/q/62886/2338
// My answer:  https://codegolf.stackexchange.com/a/63352/2338
//
import ceylon.language {
    sh=shared,
    va=variable,
    fo=formal,
    O=Object
}
import ceylon.language.meta.model {
    F=Function
}

// context

interface X {
    sh fo V v(S t);
    sh fo G g;
}
// global (mutable) context, with the buildins 
class G(va Map<S,V> m) satisfies X {
    // get entry throws error on undefined variables. 
    v(S t) => m[t] else nV;
    g => this;
    sh S d(S s, V v) {
        // error when already defined
        assert (!s in m);
        // building a new map is cheaper (code-golf wise) than having a mutable one.
        m = map { s->v, *m };
        return s;
    }
}

// This is simply a shorter way of writing "this is not an allowed operation".
// It will throw an exception when trying to access it.
// nV stands for "no value".
V nV => nothing;

// local context
class LC(G c, Map<S,V> m) satisfies X {
    g => c;
    v(S t) => m[t] else g.v(t);
    // sh actual String string => "[local: ``m``, global: ``g``]";
}

// continuation or value
alias C => V|Co;

// continuation
interface Co {
    sh fo C st();
}

// value
interface V {
    // use this as a function and call with arguments.
    // will not work for all types of stuff.
    sh fo C l(X c, V[] a);
    // check the truthiness. Defaults to true, as
    // only lists and integers can be falsy.
    sh default Boolean b => 0 < 1;
    // evaluate once (return either a value or a continuation).
    // will not work for all kinds of expression.
    sh fo C vO(X c);
    /// evaluate fully
    sh default V vF(X c) {
        va C v = vO(c);
        while (is Co n = v) {
            v = n.st();
        }
        assert (is V r = v);
        return r;
    }
}
class L(sh V* i) satisfies V {

    vO(X c) => if (nonempty i) then i[0].vF(c).l(c, i.rest) else this;
    equals(O o) => if (is L o) then i == o.i else 1 < 0;
    b => !i.empty;
    string => "(``" ".join(i)``)";
    hash => i.hash;

    sh actual C l(X c, V[] p) {
        value [h, ns, x] =
                i.size < 3
                then [f, i[0], i[1]]
                else [m, i[1], i[2]];
        // parameter names – either a single symbol, or a list of symbols.
        // If it is a list, we filter it to throw out any non-symbols.
        // Should throw an error if there are any, but this is harder.
        value n = if (is L ns) then [*ns.i.narrow<S>()] else ns;
        assert (is S|S[] n, is V x);
        V[] a = h(c, p);

        // local context
        LC lC = if (is S n) then
            LC(c.g, map { n -> L(*a) })
        else
            LC(c.g, map(zipEntries(n, a)));
        // return a continuation instead of actually
        // calling it here, to allow stack unwinding.
        return object satisfies Co {
            st() => x.vO(lC);
        };
    }
}

// symbol
class S(String n) satisfies V {
    // evaluate: resolve
    vO(X c) => c.v(this);
    // call is not allowed
    l(X c, V[] a) => nV;
    // equal if name is equal
    equals(O o) => if (is S o) then n == o.n else 1 < 0;
    hash => n.hash;
    string => n;
}

// integer
class I(sh Integer i) satisfies V {

    vO(X c) => this;
    l(X c, V[] a) => nV;
    equals(O o) => if (is I o) then i == o.i else 1 < 0;
    hash => i;
    b => !i.zero;
    string => i.string;
}

// argument handlers for functions or macros
V[] f(X c, V[] a) => [for (v in a) v.vF(c)];
V[] m(X c, V[] a) => a;

// build-in functions
// construct
L c(X c, V h, L t) => L(h, *t.i);
// head
V h(X c, L l) => l.i[0] else L();
// tail
V t(X c, L l) => L(*l.i.rest);
// subtract
I s(X c, I f, I s) => I(f.i - s.i);
// lessThan
I l(X c, I f, I s) => I(f.i < s.i then 1 else 0);
// equal
I e(X c, V v1, V v2) => I(v1 == v2 then 1 else 0);
// eval (returns potentially a continuation)
C v(X c, V v) => v.vO(c);

// build-in macros
// quote
V q(X c, V a) => a;
// if (also returns potentially a continuation)
C i(X c, V d, V t, V f) => d.vF(c).b then t.vO(c) else f.vO(c);
// define symbol in global context
S d(X c, S s, V x) => c.g.d(s, x.vF(c));

// buildin function or macro, made from a native function and an argument handler
class B<A>(F<C,A> nat, V[](X, V[]) h = f)
        satisfies V
        given A satisfies [X, V+] {
    vO(X c) => nV;
    string => nat.declaration.name;
    // this "apply" is a hack which breaks type safety ...
    // but it will be checked at runtime.
    l(X c, V[] a) => nat.apply(c, *h(c, a));
}

// define buildins
{<S->V>*} b => {
    S("c") -> B(`c`),
    S("h") -> B(`h`),
    S("t") -> B(`t`),
    S("s") -> B(`s`),
    S("l") -> B(`l`),
    S("e") -> B(`e`),
    S("v") -> B(`v`),
    S("q") -> B(`q`, m),
    S("i") -> B(`i`, m),
    S("d") -> B(`d`, m)
};

// parses a string into a list of expressions.
[V*] p(String inp) {
    // split string into tokens (retain separators, don't group them –
    // whitespace and empty strings will be sorted out later in the loop)
    value ts = inp.split(" \n()".contains, 1 < 0, 1 < 0);
    // stack of not yet finished nested lists, outer most at bottom
    va [[V*]*] s = [];
    // current list, in reverse order (because appending at the start is shorter)
    va [V*] l = [];
    for (t in ts) {
        if (t in " \n") {
            // do nothing for empty tokens
        } else if (t == "(") {
            // push the current list onto the stack, open a new list.
            s = [l, *s];
            l = [];
        } else if (t == ")") {
            // build a lisp list from the current list,
            // pop the latest list from the stack, append the created lisp list. 
            l = [L(*l.reversed), *(s[0] else [])];
            s = s.rest;
        } else if (exists i = parseInteger(t), i >= 0) {
            // append an integer to the current list.
            l = [I(i), *l];
        } else {
            // append a symbol to the current list.
            l = [S(t), *l];
        }
    }
    return l.reversed;
}

// Runs the interpreter.
// This handles input and output, calls the parser and evaluates the expressions.
sh void run() {
    va value u = "";
    while (exists l = process.readLine()) {
        u = u + l + "\n";
    }
    V[] e = p(u);
    // create global context
    X c = G(map(b));
    // iterate over the expressions, ...
    for (v in e) {
        // print("  '``v``' → ...");
        // ... evaluate each (fully) and print the result.
        print(v.vF(c));
    }
}