Wyzwanie
Wyzwanie polega na zaprojektowaniu interpretera języka przypominającego seplenienie, który odtąd zostanie ukuty: GLisp . Kod programu dla GLisp będzie składał się z dowolnej liczby zagnieżdżonych wyrażeń oznaczonych nawiasami, w następującej formie:
(func arg1 arg2 ...)
Zauważ, że interpreter musi uwzględniać zewnętrzne znaki spacji przed i po nawiasach, funkcjach i argumentach.
Rodzaje
Zaimplementujesz cztery typy: Integer, List, Boolean i Function. Wartości całkowite i logiczne można jawnie wstawiać do kodu źródłowego z ich własną składnią. Twój tłumacz musi założyć, że ciąg znaków numerycznych oznacza liczbę całkowitą (nie musisz implementować składni, aby jawnie wstawić ujemne liczby całkowite). Twój tłumacza musi również założyć, że true
i false
są wyznaczone wartości logiczne. Funkcje nie mogą być wyraźnie zdefiniowane przez użytkownika i zawsze zwracają pojedynczą wartość (Lista o dowolnej długości liczy się jako pojedyncza wartość).
Funkcje
Wymagane są następujące funkcje, które mają format Funkcja , Arity . Jeśli przed Arity n
występuje znak plus, oznacza to n
lub więcej argumentów. Możesz założyć, że wszystkie argumenty podane funkcji są tego samego typu, chyba że podano inaczej. Możesz również założyć, że jeśli nie zostanie określone zachowanie dla typu certyfikatu, możesz założyć, że żaden argument tej funkcji nigdy nie będzie tego typu. Argumenty będą nazywane jak na poniższym diagramie:
(func argument1 argument2 ... argumentn)
+ , 2+
- Jeśli wszystkie argumenty są typu Integer , musisz zwrócić sumę argumentów
- Jeśli wszystkie argumenty są typu List , należy zwrócić konkatenację argumentów w porządku rosnącym (
arg1+arg2+ ...
) - Jeśli wszystkie argumenty są typu Boolean , musisz zwrócić logiczną Wszystkie sekwencje argumentów
(+ 1 2 3 4 5) -> 15
(+ (list 1 2) (list 3 4)) -> (list 1 2 3 4)
(+ true true true) -> true
- , 2+
- Jeśli wszystkie argumenty są typu Integer , musisz zwrócić różnicę argumentów (
arg1-arg2- ...
) - Jeśli wszystkie argumenty są typu Boolean , musisz zwrócić logiczną Dowolną z sekwencji argumentów
(- 8 4 3) -> 1
(- 0 123) -> -123
(- true false false true false) -> true
- Jeśli wszystkie argumenty są typu Integer , musisz zwrócić różnicę argumentów (
* , 2+
- Jeśli wszystkie argumenty są typu Integer , musisz zwrócić iloczyn argumentów
- Jeśli jeden argument jest typu List, a drugi jest liczbą całkowitą (możesz założyć, że będą to jedyne podane argumenty), musisz zwrócić nową Listę z elementami w
arg1
powtarzanycharg2
czasach. (* 1 2 3 4 5) -> 120
(* (list 1 2 3) 2) -> (list 1 2 3 1 2 3)
/ , 2+
- Jeśli wszystkie argumenty są tego samego typu Integer , musisz zwrócić iloraz argumentów (
arg/arg2/ ...
) (możesz założyć, że dzielenie jest wykonywane sekwencyjnie, a część dziesiętna na każdym kroku jest obcinana) - Jeśli jeden argument jest typu List, a drugi jest typu Funkcja , musisz zwrócić wynikową Listę po
arg2
odwzorowaniu na każdą wartość (/ 100 10 3) -> 3
(/ (list 1 2 3) inc) -> (list 2 3 4)
- Jeśli wszystkie argumenty są tego samego typu Integer , musisz zwrócić iloraz argumentów (
% , 2
- Jeśli wszystkie argumenty są typu Integer , musisz zwrócić moduł argumentów
(% 4 2) -> 0
= , 2+
- Jeśli zarówno typ, jak i wartość wszystkich argumentów są takie same, musisz zwrócić wartość true. W przeciwnym razie zwróć false.
(= 0 0 0) -> true
(= 0 false (list)) -> false
lista , 0+
- Musisz zwrócić listę wszystkich argumentów, niezależnie od typu. Jeśli nie podano żadnych argumentów, musisz zwrócić pustą listę
(list 3 4 (list 5)) -> (list 3 4 (list 5))
inc , 1
- Jeśli argument jest typu Integer , musisz zwrócić całkowitą powiększoną o jeden
- Jeśli argument jest typu List , musisz zwrócić listę obróconą zgodnie z ruchem wskazówek zegara o jeden obrót
(inc 1) -> 2
(inc (list 1 2 3)) -> (list 3 1 2)
dec , 1
- Jeśli argument jest typu Integer , musisz zwrócić całkowitą pomniejszoną o jeden
- Jeśli argument jest typu List , musisz zwrócić listę obróconą w lewo o jeden obrót
(dec 1) -> 0
(dec (list 1 2 3)) -> (list 2 3 1)
gdyby 3
- Jeśli podano trzy argumenty dowolnego typu: Jeśli wartość prawdy
arg1
to prawda, zwróćarg2
, w przeciwnym razie zwróćarg3
(if (not (list 1)) 8 false) -> false
- Jeśli podano trzy argumenty dowolnego typu: Jeśli wartość prawdy
nie , 1
- Jeśli podano argument dowolnego typu, jeśli wartość prawdy
arg1
to False, zwróćtrue
, w przeciwnym razie zwróćfalse
. (not (list)) -> true
- Jeśli podano argument dowolnego typu, jeśli wartość prawdy
len , 1
- Jeśli podano argument typu List , zwróć długość
arg1
(len (list 4 2 true (list 3) (list))) -> 5
- Jeśli podano argument typu List , zwróć długość
Tabela prawdy:,
0, (list), false -> false
gdzie (list)
oznacza pustą listę. Wszystko inne jest true
.
Twój interpreter może być pełnym programem, który odczytuje dane źródłowe ze standardowego wejścia lub pliku, lub funkcją, która pobiera źródło jako ciąg znaków i zwraca wartość wyjściową.
Jeśli wybierzesz to pierwsze, wynikiem dla liczb całkowitych są po prostu liczby, dla booleanów jest true
lub false
, a dla list jest oddzielona spacjami sekwencja wartości ujęta w nawiasy (np. (1 2 3 4 (5 6 7))
Oznaczenia (list 1 2 3 4 (list 5 6 7))
).
Jeśli wybierzesz ten drugi, wartość musi zostać zwrócona w odpowiednim typie języka implementacji lub, jeśli nie istnieje podobny typ, typ niestandardowy. Listy mogą być zwracane jako tablice lub wektory, jeśli język nie ma typu listy , booleany powinny być zwracane jako typ boolowski w języku lub typ niestandardowy, jeśli język ich nie obsługuje.
Przypadki testowe
(list 1 2 3 (list 4 5 true)) -> (1 2 3 (4 5 true))
(/ 4000 (+ 1 2 3 4 (* 5 8))) -> 80
(+ (not (- (len (list 5 6 7)) (/ 10 3))) true) -> true
(if ( len (list ) ) 4 (if (+ (= 8 8 8) (not (list 4))) 8 5)) -> 5
Wyjaśnienia
- Twój tłumacz może radzić sobie z nieprawidłowymi danymi wejściowymi w dowolny sposób, ale nie może zgłaszać wyjątku (może jednak wydrukować komunikat o błędzie i wyjść płynnie)
- Funkcje zawsze oceniają argumenty od lewej do prawej
- Nieprawidłowe dane wejściowe to wszelkie dane wejściowe, które są niepoprawne pod względem składniowym. Obejmuje to między innymi niedopasowane nawiasy klamrowe, dzielenie przez zero i funkcje częściowo zastosowane (chyba że skorzystają z premii)
- W przypadku
=
, jeśli wartości są różne i każdy z rodzajów są różne, zwrotfalse
Bonusy
- Ocena * 0,8, jeśli wspierasz częściowo zastosowane funkcje. Na przykład
((+ 2) 3)
byłoby to samo(+ 2 3)
, ale dopuszcza takie rzeczy jak(/ (list 1 2 3) (+ 2))
. Możesz założyć, że funkcja jest częściowo zastosowana, jeśli otrzyma mniej niż minimalną liczbę argumentów - Wynik * 0,85, jeśli nie ocenisz argumentów zastosowanych,
if
chyba że zostaną zwrócone
To jest golf golfowy, więc wygrywa interpreter z najmniejszą liczbą bajtów!
źródło
(if (not (array 1)) 8 false) -> false
?(+ 3 (if false 5))
? Ogólnie rzecz biorąc, czym tak naprawdę jest „nic nie zwracać”? Nie określiłeś żadnego typu jednostki, która ma zostać(+ bool bool...)
logiczne AND i(- bool bool...)
logiczne OR? Standardowa notacja pierścieniowa byłaby używana+
dla OR i*
AND. 2. Czy „nieprawidłowe dane wejściowe” mają obejmować przypadki,(/ 2 0)
które są poprawne pod względem składniowym? 3. Bo=
jeśli wartości nie są takie same, czy powinien zwrócićfalse
? 4. Definicjanot
wydaje się być odwrotna. 5. Jakie są tokeny? Mówisz, że interpreter musi obsługiwać dodatkowe białe znaki, ale nie mówisz o tym, na czym może polegać. W przypadku takich złożonych pytań naprawdę powinieneś użyć piaskownicy, aby można było sprawdzić specyfikację.((+ 2 3) 4)
równa9
lub występuje błąd? W przypadku funkcji var-arg nie jest jasne, kiedy należy uznać aplikację za częściową. Robi się jeszcze bardziej błotnisty dzięki takim rzeczom, jak((if true (+ 2 3) (- 5)) 4)
Odpowiedzi:
Haskell,
1370126311791128116311071084 bajtów * 0,8 * 0,85 = 737,12Pełny program, czytanie
stdin
i pisanie dostdout
.g
jest również wersją funkcji.Implementuje zarówno funkcje częściowe, jak i leniwą ocenę
if
.Przykładowe przebiegi (w wersji funkcji):
Teraz ma wszystkie testy jednostkowe z opisu:
źródło
e[K,L _]
, których możesz użyćdrop 1
jako bezpiecznej wersjitail
i użyćtake
do bezpiecznej wersjihead
połączenia dwóch definicjie[K,L _]
notElem
inna wskazówka: możesz to zrobićs=string
i używać zamiast obustring
ichar
(s"C"
vs.char 'C'
). kolejna wskazówka: użyj osłon zamiastif
sMaybe
wartości według list.Nothing
jest[]
iJust x
jest[x]
. To pozbywa się długich konstruktorów i dodaje jeszcze kilka funkcji:if p then Just x else Nothing
jest[x|p]
,(==Nothing)
jestnull
lista monada staje się tak samo jak może monady, i tak dalej.Python 2, 1417 * 0,8 * 0,85 = 963,56
Całkowity remont. Jeśli chcesz zobaczyć poprzednie wersje, sprawdź historię edycji .
Jest o wiele więcej do gry w golfa. Powoli nad tym pracuję.
Z zlib / base64 otrzymujemy 1093 * 0,8 * 0,85 = 743,24 :
Uwaga: jeśli zauważysz, że mój wynik rośnie, to prawdopodobnie dlatego, że znalazłem kilka błędów
źródło
Common Lisp, 868 bajtów * 0,85 = 737,8
Czy to oszustwo, aby wdrożyć Lisp z Lisp? Nadal wiele do optymalizacji.
Drukuje literę E w przypadku błędu wejścia. Przykładowe przebiegi:
źródło
Haskell, 972
dość hacky rozwiązanie. przechowuje to wszystko jako ciągi znaków w postaci gotowej do wyjścia - ich typy można rozróżnić po pierwszej literze -
0..9
dla liczb,(
dla listt
lubf
dla boolanów i wszystko inne dla funkcji.aby uruchomić użyj
r
funkcji.źródło