Wyzwanie polega na napisaniu interpretera dla niepisanego rachunku lambda w jak najmniejszej liczbie znaków. Nietypowy rachunek lambda definiujemy w następujący sposób:
Składnia
Istnieją następujące trzy rodzaje wyrażeń:
Wyrażenie lambda ma postać, w
(λ x. e)
którejx
może być dowolną nazwą zmiennej prawnej ie
dowolnym wyrażeniem prawnym. Tutajx
jest nazywany parametrem ie
nazywa ciało funkcji.Dla uproszczenia dodajemy dodatkowe ograniczenie, że nie może istnieć zmienna o takiej samej nazwie jak
x
obecnie w zakresie. A zaczyna być zmienne w zakresie, gdy pojawi się nazwa pomiędzy(λ
a.
i zatrzymuje się w zakresie w odpowiedni)
.- Aplikacja funkcji ma formę,
(f a)
gdzief
ia
są wyrażeniami prawnymi. Tutajf
nazywa się funkcję ia
nazywa się argumentem. - Zmienna ma postać
x
gdziex
jest legalną nazwą zmiennej.
Semantyka
Funkcja jest stosowana przez zastąpienie każdego wystąpienia parametru w treści funkcji argumentem. Bardziej formalnie ekspresja formy ((λ x. e) a)
, w której x
jest nazwą zmienne, e
i a
są wyrażeniami, ocenia się (lub zmniejsza) do ekspresji e'
, gdzie e'
jest wynikiem zastąpienia w każdym wystąpieniu x
w e
z a
.
Forma normalna jest wyrażeniem, którego nie można dalej oceniać.
Wyzwanie
Twoim zadaniem, jeśli zdecydujesz się to zaakceptować, jest napisanie interpretera, który jako dane wejściowe przyjmuje wyrażenie niepisanego rachunku lambda niezawierającego wolnych zmiennych i generuje jako wynik normalną formę wyrażenia (lub wyrażenie alfa zgodne z nim) . Jeśli wyrażenie nie ma normalnej postaci lub nie jest prawidłowym wyrażeniem, zachowanie jest niezdefiniowane.
Rozwiązanie o najmniejszej liczbie znaków wygrywa.
Kilka uwag:
- Dane wejściowe można odczytać ze standardowego wejścia lub z nazwy pliku podanej jako argument wiersza poleceń (wystarczy zaimplementować jedno lub drugie - nie oba). Wyjście przechodzi na standardowe wyjście.
- Alternatywnie możesz zdefiniować funkcję, która pobiera dane wejściowe jako ciąg znaków i zwraca dane wyjściowe jako ciąg znaków.
- Jeśli występują problemy ze znakami spoza ASCII, możesz użyć znaku odwrotnego ukośnika (
\
) zamiast λ. - Liczymy liczbę znaków, a nie bajtów, więc nawet jeśli plik źródłowy jest zakodowany jako Unicode λ, liczy się jako jeden znak.
- Prawne nazwy zmiennych składają się z jednej lub większej liczby małych liter, tj. Znaków od a do z (nie trzeba obsługiwać nazw alfanumerycznych, wielkich liter lub liter spoza alfabetu łacińskiego - chociaż takie postępowanie oczywiście nie unieważnia rozwiązania).
- Jeśli chodzi o to wyzwanie, nawiasy nie są opcjonalne. Każde wyrażenie lambda i każda aplikacja funkcji będzie otoczona dokładnie jedną parą nawiasów. Żadna nazwa zmiennej nie będzie otoczona nawiasami.
- Cukier syntaktyczny, taki jak pisanie
(λ x y. e)
dla(λ x. (λ y. e))
, nie musi być obsługiwany. - Jeśli do oceny funkcji wymagana jest głębokość rekurencji większa niż 100, zachowanie jest niezdefiniowane. To powinno być wystarczająco niskie, aby można je było wdrożyć bez optymalizacji we wszystkich językach, a jednocześnie wystarczająco duże, aby móc wykonywać większość wyrażeń.
- Możesz także założyć, że odstępy będą takie jak w przykładach, tj. Bez spacji na początku i na końcu danych wejściowych lub przed a
λ
lub.
dokładnie jedną spacją po a.
oraz między funkcją i jej argumentem a po aλ
.
Przykładowe wejście i wyjście
Wejście:
((λ x. x) (λ y. (λ z. z)))
Wynik:
(λ y. (λ z. z))
Wejście:
(λ x. ((λ y. y) x))
Wynik:
(λ x. x)
Wejście:
((λ x. (λ y. x)) (λ a. a))
Wynik:
(λ y. (λ a. a))
Wejście:
(((λ x. (λ y. x)) (λ a. a)) (λ b. b))
Wynik:
(λ a. a)
Wejście:
((λ x. (λ y. y)) (λ a. a))
Wynik:
(λ y. y)
Wejście:
(((λ x. (λ y. y)) (λ a. a)) (λ b. b))
Wynik:
(λ b. b)
Wejście:
((λx. (x x)) (λx. (x x)))
Dane wyjściowe: cokolwiek (jest to przykład wyrażenia, które nie ma normalnej postaci)
Wejście:
(((λ x. (λ y. x)) (λ a. a)) ((λx. (x x)) (λx. (x x))))
Dane wyjściowe:
(λ a. a)
(Jest to przykład wyrażenia, które nie normalizuje się, jeśli oceniasz argumenty przed wywołaniem funkcji, i niestety przykład, dla którego moje próbowane rozwiązanie kończy się niepowodzeniem)Wejście:
((λ a. (λ b. (a (a (a b))))) (λ c. (λ d. (c (c d)))))
Dane wyjściowe:
`(λ a. (λ b. (a (a (a (a (a (a (a (a b))))))))))
oblicza 2 ^ 3 w liczbach kościelnych.
(\y. a)
.Odpowiedzi:
Najnowszy:
Zmniejszyłem go do 644 znaków , połączyłem części cEll w cOpy i Par; buforowane wywołania do komórki i cdr do tymczasowych zmiennych lokalnych i przeniesiono te zmienne lokalne do globalnych w funkcjach „terminalnych” (tj. nierekurencyjnych). Ponadto stałe dziesiętne są krótsze niż literały znakowe, a ten paskudny biznes ...
... poprawnie identyfikuje małe litery (zakładając ASCII), ale akceptuje także dowolne z `{|} ~. (Ta sama obserwacja na temat ASCII znajduje się w tym doskonałym wideo o UTF-8 .)
Etola: |
Wcześniej:
Czy mogę dostać kilka głosów za wysiłek? Pracowałem nad tym dniem i nocą przez tydzień. Wykopałem oryginalny artykuł McCarthy'ego i byłem nękany przez błąd w samym dokumencie, dopóki nie przeczytałem dodatku do The Roots of Lisp Paula Grahama . Byłem tak rozproszony, że zamknąłem się z domu, a potem zupełnie zapomniałem, aż wróciłem do domu tej nocy o 12:30 (trochę późno, żeby zadzwonić do kierownika budowy, który mieszka daleko w hrabstwie), i musiałem spędzić noc u babci (rąbałam, aż bateria mojego laptopa wyczerpała się).
A po tym wszystkim nie jest nawet blisko zwycięskiego wejścia!
Nie jestem pewien, jak to skrócić; i użyłem wszystkich brudnych sztuczek, o których mogłem myśleć! Może nie da się tego zrobić w C.
Z pewną hojnością w liczeniu (pierwsza część bierze ciąg i wypisuje wynik), to
778770709694 znaków. Ale żeby był samodzielny, musi mieć tosbrk
wezwanie. Do obsługi bardziej skomplikowanych wyrażeń potrzebny jest takżesignal
moduł obsługi. I oczywiście nie można go przekształcić w moduł z dowolnym kodem, który próbuje użyćmalloc
.Niestety, oto jest:
Oto blok tuż przed ostatecznymi obniżkami. Sztuczki tutaj to kursory liczb całkowitych zamiast wskaźników (wykorzystujące zachowanie „domyślnej int”) oraz użycie „pamięci scratch”:
char*n
jest to wskaźnik „nowy” lub „następny” w wolnej przestrzeni. Ale czasami zapisuję ciąg do pamięci, a następnie wywołuję strlen i inkrementację n; efektywnie wykorzystując pamięć, a następnie przydzielając ją, po łatwiejszym obliczeniu rozmiaru. Widać, że jest to prawie prosto z artykułu McCarthy'ego, z wyjątkiemcell()
interfejsów między funkcjami a ciągiem reprezentacji danych.źródło
sprintf(n,...);n+=strlen(n)+1;
jest lepszy niżn+=sprintf(n,...)+1;
Odwracanie składni tablicyx[m]
zamiastm[x]
zezwalam na zastąpienie wszystkich pośrednich makrami „postfiksowymi”#define M [m]
...x M
co oszczędza 1 znak i daje „wolny” podział linii, ponieważ białe znaki są potrzebne do oddzielenia tokenów.// um ...
przechodzi przez ciąg i zlicza nawiasy, aż znajdzie pasujące ścisłe pareny na prawidłowym poziomie zagnieżdżenia.Binary Lambda Calculus 186
Program pokazany na zrzucie szesnastkowym poniżej
nie akceptuje całkowicie proponowanego formatu. Raczej oczekuje terminu lambda w formacie binarnego rachunku lambda (blc). Jednak pokazuje każdy krok w normalnej redukcji formy, używając minimalnych nawiasów.
Przykład: obliczenie 2 ^ 3 cyframi kościelnymi
Zapisz powyższy zrzut heksowy za pomocą xxd -r> symbolic.Blc
Weź interpretera blc ze strony http://tromp.github.io/cl/uni.c
Ponieważ zrzut heksowy jest raczej nieczytelny, tutaj jest wersja „zdemontowana”
zamiana 00 (lambda) na \ i 01 (aplikacja) na @ Teraz jest prawie tak czytelna, jak pieprzenie mózgu :-)
Zobacz także http://www.ioccc.org/2012/tromp/hint.html
źródło
Haskell,
342323317305 znakówW chwili pisania tego tekstu jest to jedyne rozwiązanie, które ocenia ((λ f. (Λ x. (Fx)))) (λ y. (Λ x. Y))) do prawidłowego wyniku (λ x. (Λ z. x)) zamiast (λ x. (λ x. x)). Prawidłowa implementacja rachunku lambda wymaga podstawienia unikającego przechwytywania , nawet w ramach uproszczenia tego problemu, że żadna zmienna nie cienia innej zmiennej w swoim zakresie. (Mój program działa nawet bez tej gwarancji).
Uwagi:
Wersja bez golfa z dokumentacją.
źródło
Python -
321320Oto moja (naprawiona) próba:
źródło
Ruby 254 znaków
Może być używany jak
Rozwiązanie nie jest jeszcze w pełni zagrane w golfa, ale jest już prawie nieczytelne.
źródło
Edycja: sprawdź moją odpowiedź poniżej pod kątem 250 w czystym JavaScript.
2852243 znaków przy użyciu LiveScript (bez Regex! Nie w pełni golfowy - można poprawić)Test:
Który jest
3^2=9
, jak stwierdzono w OP.Jeśli ktoś jest ciekawy, oto rozszerzona wersja z kilkoma komentarzami:
źródło
Łuk Waterhouse - 140 znaków
źródło
C 1039 bajtów
Zmienne zezwalają jako dane wejściowe przy użyciu małych liter [od a..z] sys może generować zmienne przy użyciu wielkich liter [od A..Z], jeśli jest taka potrzeba na wyjściu ... Załóżmy, że konfiguracja znaków ascii.
źródło
Haskell 456 C.
Może być znacznie krótszy, jeśli w pełni wykorzystana jest leniwa funkcja oceny Haskell. Niestety nie wiem jak to zrobić.
Ponadto wiele znaków jest marnowanych na etapie analizy.
Wersja bez golfa
źródło
Masz 231 z JavaScript / bez Regex
Odbiera tablice 2-elementowe.
1
oznaczaλ
i 2 oznacza zmienną indeksu bruijn.Test:
źródło
Python: 1266 znaków (mierzonych za pomocą wc)
Nie najkrótszy z długiego ujęcia, ale poprawnie obsługuje zmianę nazwy alfa i wszystkie przykłady wymienione w poście PO.
źródło
except NameError
justexcept
? (3) Nazwy funkcji dwuznakowych można zmienić na nazwy jednoznakowe. (4) Istnieje kilka miejsc, w których masz zadania, które mają spacje wokół=
. (5)if t[0]=='c'
można zastąpićif'c'==t[0]
.C ++ (gcc) ,
782766758731 bajtówWypróbuj online!
Podstawową ideą jest to, że kod wykorzystuje wewnętrzną reprezentację opartą na idei indeksów de Bruijna - z tym wyjątkiem, że odwracam wskaźniki, aby wskazać głębokość lambda wiązania danej zmiennej. W kodzie:
E::t
reprezentuje typ węzła - 0 dla zmiennego węzła liścia, 1 dla węzła lambda i 2 dla węzła aplikacji funkcji. (Dobiera się tak, że pokrywa się z Arity węzła, który okazuje się być możliwe.) AE::l
iE::r
są dzieci, zgodnie z (tylkoE::l
dla węzła lambda), iE::i
jest indeksem lambda głębokość zmienną węzła liścia.E::E(E&o,int d,int e)
klonuje podwyrażenie, które początkowo znajdowało się na głębokości lambda, wd
celu wklejenia w nowym miejscu na głębokości lambdad+e
. Obejmuje to zachowanie zmiennych na głębokości lambda mniejszej niżd
podczas zwiększania zmiennych na głębokości lambda przynajmniejd
oe
.E::s
ma podstawienie podwyrażeniev
do różnej liczbyd
w*this
natomiast zmniejszanie liczby zmiennych powyżejd
(oraze
jest wewnętrznym Detal śledzenia przyrost lambda głębokość gdy musi skorzystaćE::c
).E::R
szuka pojedynczej redukcji beta do wykonania, preferując najwyższe lub najbardziej lewe wystąpienia, zgodnie z wyszukiwaniem w przedsprzedaży AST. Zwraca wartość niezerową, jeśli znalazł redukcję do wykonania lub zero, jeśli nie znalazła żadnej.E::u
jestto_string
operacją typu, która odtwarza łańcuch „czytelny dla człowieka” przy użyciu syntetycznych nazw zmiennych. (Pamiętaj, że z powodu niewielkiej gry w golfa wV
funkcji pomocnika będzie generować tylko nazwy zawierającea
przeloti
).E::E(int d, std::map<std::string, int> m, char*&s)
analizuje ciąg wejściowys
do wyrażenia AST w oparciu o odwzorowaniem
aktualnie powiązanych nazw zmiennych na wskaźniki głębokości lambda.f
to główna funkcja odpowiadająca na pytanie.(Jak widać na łączu TIO, kod obsługuje nazwy zmiennych z wieloma znakami, a także otrzymuje poprawną odpowiedź
(\ a. (\ b. a))
na((\ f. (\ x. (f x))) (\ y. (\ x. y)))
. Zdarza się również, że parsowanie kodu może obsługiwać cieniowanie zmiennych bez dodatkowych kosztów.)-16 bajtów częściowo z powodu pomysłu autorstwa ceilingcat (który sam wymyśliłem niezależnie), a częściowo z powodu zmiany
E*a=new E;
na,E&a=*new E;
a następnie zmianya->
naa.
-8 więcej bajtów z powodu innego komentarza użytkownika ceilingcat (pomiń przypisanie z trójki
a.t
)-27 bajtów z konwersji parsera i klonowania do konstruktorów
E
źródło
C 637 bajtów
Ta wersja nie używa zmiennych pomocniczych (więc nie wynika to w 100% z tego, co mówi rachunek lambda ... jak wiele innych tutaj ...). Każda zmienna musi mieć długość 1 znaków (tak jak inne tutaj). Kod testowy:
wyniki:
to jest pół-niemęski:
źródło