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.14
i -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 0
są 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)
daje1
.
„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ć1
jako funkcję lub makro, ale(q (1 2 3))
zwraca listę(1 2 3)
. Ocenaa
daje 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 (0
lub 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 przekazaniemd
, 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, d
jest 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ą d
i 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 a
wywołuje funkcję, b
któ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ż x
na 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.
źródło
-1
, nadal mogę wygenerować wartość -1, wykonując(s 0 1)
.F
nie są dostępne w funkcji,G
jeśliF
wywołaniaG
(jak w przypadku dynamicznego zakresu), ale nie są również dostępne w funkcji,H
jeśliH
jest zagnieżdżona funkcja zdefiniowana w środkuF
(jak w przypadku zakresu leksykalnego) - patrz przypadek testowy 5. Więc nazywając to „leksykalnym „może wprowadzać w błąd.Odpowiedzi:
Python 2,
685675660657646642640 bajtówOdczytuje 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:(
, pchamy pustą listę na górze stosu wyrażeń;)
, wstawiamy wartość na górze stosu wyrażeń i dołączamy ją do listy, która była wcześniej pod nią na stosie;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ącV()
i wydrukuj wynik, odpowiednio sformatowany przy użyciuF()
.Ocena
Utrzymujemy zakres globalny
G
, jako listę par klucz / wartość. Początkowo zawiera tylko wbudowane funkcje (ale nie makra i niev
, 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ściV()
żywo w nieskończonej pętli, czyli w jaki sposób przeprowadzamy optymalizację wywołania ogona (TCO), jak wyjaśniono później.Przetwarzamy
e
zgodnie 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,
e
musi być nazwą makra wbudowanego (tjq
,i
,d
lubv
), i zwrócić go bez zmian. W przeciwnym razie, jeślie
nie jest łańcuchem,e
jest listą (niepustą), tj. wywołaniem funkcji. Oceniamy pierwszy element listy, tj. Wyrażenie funkcji, wywołującV()
rekurencyjnie (przy użyciu bieżącego zasięgu lokalnego); nazywamy wynikf
. Reszta listyA
to lista argumentów.f
moż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
f
jest to ciąg znaków, tj. Wbudowane makro, obsługujemy go w miejscu. Jeśli jest to makroi
lubv
, oceniamy jego pierwszy operand i albo odpowiednio wybieramy drugi lub trzeci operand, w przypadkui
, albo wykorzystujemy wynik pierwszego operandu, w przypadkuv
; zamiast rekurencyjnej oceny wybranego wyrażenia, które pokonałoby TCO, po prostu zamieniamye
to wyrażenie i przeskakujemy na początek pętli. Jeślif
jest to makrod
, dodajemy parę, której pierwszym elementem jest pierwszy operand, a którego drugim elementem jest wynik oceny drugiego operandu, do zasięgu globalnegoG
, i zwracamy pierwszy operand. W przeciwnym razief
jest to makroq
, w którym to przypadku po prostu zwracamy jego operand bezpośrednio.Z drugiej strony, jeśli
f
jest 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. ElementyA
i zamieniamyA
na wynik.Jeśli
f
jest lambda, nazywamy ją, przekazując rozpakowane argumentyA
i zwracamy wynik.W przeciwnym razie
f
jest 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 makri
iv
aby wykonać TCO, nie oceniamy treści rekurencyjnie, lecz zastępujemye
je treścią i przechodzimy do następnej iteracji. W przeciwieństwiei
av
jednak możemy również zastąpić zakresu lokalnego,L
z nowej lokalnej zakresu funkcji. Jeśli lista parametrówP
, w rzeczywistości jest listą, nowy zasięg lokalny jest tworzony przez skompresowanie listy parametrówP
za pomocą listy argumentówA
; 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).Pokaż fragment kodu
A oto przykładowa sesja z implementacją sortowania korespondencji seryjnej:
Pokaż fragment kodu
źródło
import zlib;exec(zlib.decompress(your_code_compressed_in_bytes))
A[0]
do jakiejś zmiennej jeden char tuż po wyjątkiem blokuA
w tym przypadku jest puste) i nie chcę „regresować”.C (GNU), 1095 bajtów
Duża część akcji rozgrywa się w gigantycznej
v
funkcji. Zamiast jawnego wdrażania rekurencji ogona,v
jest on tak skonstruowany, że wiele wywołań odv
dov
bę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órychscanf
rozszerzeń, które nie były dostępne w systemie Windows, których zwykle używam. Perspektywa napisania parsera ze standardemscanf
była tak okropna, że zamiast tego użyłem maszyny wirtualnej z systemem Linux do przetestowania programu. Analiza bezscanf
klas znaków prawdopodobnie spowodowałaby dodanie ponad 100 bajtów.Częściowo nie golfista
źródło
Ceylon, 2422 bajty
(Myślę, że to mój najdłuższy jak dotąd program w golfa.)
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
V
z implementacją klasL
(lista - tylko opakowanie wokół sekwencji CejlonuV
),S
(symbol - opakowanie wokół łańcucha),I
(liczba całkowita - opakowanie wokół liczby całkowitej Cejlonu) orazB
(funkcja wbudowana lub makro, opakowanie wokół Funkcja Ceylon).Używam standardowej notacji równości Cejlonu, wdrażając
equals
metodę (a takżehash
atrybut, który tak naprawdę jest potrzebny tylko dla symboli), a także standardowystring
atrybut wyjścia.Mamy atrybut boolowski
b
(który domyślnie jest prawdziwy, przesłonięty wI
iL
zwracać fałsz dla pustych list) oraz dwie metodyl
(wywołanie, tj. Użycie tego obiektu jako funkcji) ivO
(ocena jednego kroku). Obie zwracają wartość lub obiekt kontynuacji, który pozwala następnie na ocenę dla jeszcze jednego kroku, ivF
(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ąd
wbudowanego) orazLC
dla 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ć
Function
obiekty 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
run
metodzie, 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ę ).
źródło