EDYCJA: Jak niektórzy z was podejrzewali, w oficjalnym tłumaczu wystąpił błąd: kolejność kompozycji .
została odwrócona. Miałem dwie wersje tłumacza i użyłem tutaj niewłaściwej. Przykłady zostały również napisane dla tej niepoprawnej wersji. Naprawiłem interpreter w repozytorium i poniższe przykłady. Opis >
był również trochę niejednoznaczny, więc to naprawiłem. Przepraszam za to, że trwało to tak długo, że pochłonęły mnie pewne rzeczy z życia.
EDYCJA 2: Mój tłumacz miał błąd w implementacji, .
który został odzwierciedlony w przykładach (polegali na nieokreślonym zachowaniu). Problem został już rozwiązany.
Wprowadzenie
Shift to ezoteryczny funkcjonalny język programowania, który stworzyłem kilka lat temu, ale opublikowałem go dzisiaj. Jest oparty na stosie, ale ma również automatyczne curry, takie jak Haskell.
Specyfikacja
Shift ma dwa typy danych:
- Funkcje, które mają dowolną dodatnią arity (liczba wejść) i które zwróci listę wyjść. Na przykład funkcja, która duplikuje jedyne dane wejściowe, ma arity 1, a funkcja zamiany dwóch danych wejściowych ma arity 2.
- Puste miejsca, które są identyczne i nie mają innego celu niż bycie funkcjami.
Program Shift zawiera zero lub więcej poleceń , z których każde jest pojedynczym znakiem ASCII. Łącznie jest 8 poleceń:
!
( Apply ) wyświetla funkcjęf
i wartośćx
ze stosu i stosuje sięf
dox
. Jeślif
ma arity 1, listaf(x)
jest dodawana na początku stosu. Jeśli ma arityn > 1
, nowa(n-1)
funkcjag
jest wypychana na stos. Wymaga danych wejściowych i zwrotów .x1,x2,...,xn-1
f(x,x1,x2,...,xn-1)
?
( puste ) popycha puste do stosu.+
( klon ) wypycha na stos jednoargumentową funkcję, która powiela dane wejściowe: dowolna wartośćx
jest odwzorowywana[x,x]
.>
( shift ) wypycha na stos jednoargumentową funkcję, która przyjmuje funkcjęn
-aryf
, i zwraca funkcję(n+1)
-ary,g
która ignoruje swój pierwszy argumentx
, wywołujef
pozostałe i haczyx
przed wynikiem. Na przykładshift(clone)
jest funkcją binarną, która pobiera dane wejściowea,b
i zwraca[a,b,b]
./
( fork ) wypycha na stos funkcję potrójną, która pobiera trzy dane wejściowea,b,c
i zwraca,[b]
jeślia
jest pusta, i w[c]
przeciwnym razie.$
( wywołanie ) wypycha na stos funkcję binarną, która wyskakuje z funkcjif
i wartościx
, i stosujef
sięx
dokładnie tak, jak to!
robi..
( łańcuch ) wypycha na stos funkcję binarną, która wyskakuje z dwóch funkcjif
ig
zwraca ich skład: funkcja,h
która ma tę samą aranżacjęf
i która przyjmuje swoje dane wejściowe normalnie, stosuje sięf
do nich, a następnie w pełni stosujeg
się do wyniku (wywołania tyle razy, ile dyktuje to jego arsenał), przy czym niewykorzystane przedmioty z produkcjif
pozostają w wynikuh
. Załóżmy na przykład, żef
jest to funkcja binarna, która klonuje swój drugi argument ig
jest wywołaniem . Jeśli stos zawiera[f,g,a,b,c]
i my to robimy.!!
, to zawiera[chain(f,g),a,b,c]
; jeśli zrobimy to!!
dalej,f
to najpierw zastosujemy doa,b
produkcji[a,b,b]
, następnieg
jest stosowany do pierwszych dwóch elementów tego, ponieważ jego arsenał wynosi 2, co powoduje[a(b),b]
, że stos będzie w końcu[a(b),b,c]
.@
( powiedzmy ) wypycha jednoargumentową funkcję, która po prostu zwraca dane wejściowe i wypisuje,0
czy była pusta, a1
jeśli była funkcją.
Zauważ, że wszystkie polecenia oprócz !
po prostu wypychają wartość na stos, nie ma sposobu na wprowadzenie danych, a jedynym sposobem na wyprowadzenie czegokolwiek jest użycie @
. Program jest interpretowany przez ocenianie poleceń jeden po drugim, wypisywanie 0
s lub 1
s za każdym razem, gdy wywoływane jest „powiedz”, i wychodzenie. Każde zachowanie nieopisane tutaj (zastosowanie pustego miejsca, zastosowanie stosu o długości 0 lub 1, wywołanie „łańcucha” na pustym miejscu itp.) Jest niezdefiniowane: interpreter może ulec awarii, po cichu zawieść, poprosić o dane wejściowe lub cokolwiek innego.
Zadanie
Twoim zadaniem jest napisanie tłumacza dla Shift. Powinien wziąć z argumentu STDIN, wiersza poleceń lub funkcji program Shift do interpretacji i wypisać go do STDOUT lub zwrócić wynikowe (być może nieskończone) wyjście 0
s i 1
s. Jeśli piszesz funkcję, musisz mieć możliwość uzyskania dostępu do danych wyjściowych o nieskończonej długości (generator w Pythonie, lista leniwa w Haskell itp.). Alternatywnie możesz wziąć inne dane wejściowe, liczbę n
i zwrócić przynajmniej n
znaki wyjścia, jeśli jest ono dłuższe niż n
.
Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone.
Przypadki testowe
Ten program Shift drukuje 01
:
?@!@@!
Zaczynając od lewej: wciśnij puste miejsce, wciśnij say , a następnie zastosuj say do pustego miejsca. To wychodzi 0
. Następnie Push powiedzieć dwa razy i zastosować drugi głos do pierwszego. To wychodzi 1
.
Ten program zapętla się na zawsze, nie dając żadnych wyników:
$+.!!+!!
Wciśnij call i klon , a następnie zastosuj do nich łańcuch (potrzebujemy dwóch !
s, ponieważ łańcuch jest funkcją binarną). Teraz stos zawiera funkcję, która pobiera jeden argument, duplikuje go i wywołuje pierwszą kopię na drugiej. Za pomocą +!!
kopiujemy tę funkcję i wywołujemy ją samą.
Ten program drukuje 0010
:
?@$.++>!.!!.!!.!!!!+?/!!!@!@>!!!
Naciśnij puste miejsce i powiedz . Następnie utwórz funkcję binarną, która kopiuje swój drugi argument b
, a następnie kopiuje pierwszy a
i komponuje go ze sobą, a następnie stosuje kompozycję do kopii b
, zwracając [a(a(b)),b]
. Zastosuj to do powiedzenia i puste, a następnie zastosuj powiedz do dwóch elementów pozostałych na stosie.
Ten program drukuje 0
. Dla każdego !!!
dołączonego do niego drukuje dodatkowy 0
.
?@+$>!>!+>!///!!>!>!.!!.!!.!!+!!!!
Naciśnij puste miejsce i powiedz . Następnie utwórz funkcję potrójną, która przyjmuje f,g,x
dane wejściowe i zwraca [f,f,g,g(x)]
. Sklonuj tę funkcję i zastosuj ją do siebie, powiedzmy , i do spacji. Ta aplikacja nie zmienia stosu, więc możemy zastosować tę funkcję ponownie tyle razy, ile chcemy.
Ten program wypisuje nieskończoną sekwencję 001011011101111...
, w której liczba 1
s zawsze wzrasta o jeden:
@?/!@>!??/!!>!+.!!.!!.!!.+>!.!!$$$$+$>!>!$>!>!+>!$>!>!>!+>!>!///!!>!>!>!.!!.!!.!!.!!.!!.!!.!!.!!.!!.!!+!!!!!
Repozytorium zawiera wersję z adnotacjami.
źródło
f(x1, x2, ..., xn)
ig(y1, y2, ..., ym)
. Wywołanie.
wyskakuje z nich obu i powoduje uruchomienie funkcjih(z1, z2, ..., zn)
. Teraz możesz pochłonąć wszystkie te argumenty, stopniowo je curry!
. Pon
takich aplikacjach pozostała funkcja miała tylko jeden argument i w tym momencie obliczaf(z1, z2, ..., zn)
(tj.f
Stosuje się do wszystkich argumentów, w których się przeglądasz), co wypycha niektóre nowe wartości, a następnie natychmiast zużywam
wartości ze stosu i wywołujeg
je..
działa dokładnie tak, jak opisał Martin, z tym wyjątkiem, że jeślif
zwraca listę mniejszą niżm
wartości, wynik jest niezdefiniowany (skład ma arityn
, więc nie może jeść więcej argumentów ze stosu). Zasadniczo dane wyjściowef
są używane jako tymczasowy stos, na któryg
jest wypychany i nakładanym
za pomocą!
, a wynik jest dodawany do głównego stosu.Odpowiedzi:
Python 2,
752667534506445436427404398393 bajtówTo wcale nie jest krótkie ... ale dałem z siebie wszystko. Wszelkie sugestie dotyczące gry w golfa będą bardzo mile widziane ...
EDIT6: To jest teraz skrypt zamiast funkcji. Zapisz go w pliku (shift.py, forex), a następnie uruchom za pomocą
$ python shift.py '<my_input>'
. Pamiętaj, aby wpisać dane wejściowe w pojedynczych cudzysłowach, w przeciwnym razie bash oszaleje na punkcie wejściowych znaków.EDYCJA 7: Aaaaaa i ... to już nie jest czytelne. Ale pozbyłem się 23 bajtów więcej, więc to chyba dobrze? Opublikuję też wersję bez golfa.
EDIT8: Jeszcze jeden golf dzięki @Zgarb.
EDYCJA: dzięki @DLosc za pomoc w grze w golfa! Udało się zmniejszyć go o 85 bajtów.
EDYCJA 2: wytnij tonę niepotrzebnych opakowań i upuściłem ją o kolejne 133 bajty!
EDIT3: ... i 28 innych dzięki @ Sp3000 i @orlp na czacie!
EDIT4: z pomocą @orlp & @ Sp3000 usunął wszystkie dekoratory, a teraz jest o 61 bajtów krótszy.
EDYCJA 5: pomóż mieeeeee, nie mogę przestać grać w golfa .... jeszcze 9 bajtów. Pozbycie się ostatecznej instrukcji print pozwoliłoby zaoszczędzić kolejne 7, ale jeśli uruchomisz m () w pętli, wszystkie dane wyjściowe znajdą się w tym samym wierszu ... czy to w porządku?
Oto wersja bez golfa:
Podstawową ideą jest to, że lista Pythona działa bardzo ładnie jako stos, a przechowywanie
u=k.append
nie tylko zapisuję postacie,ale mogę także użyć(już nie!).@u
jako dekoratora do wypychania funkcjiPonieważ kilka funkcji, które działają na funkcje n-arity, musi być w stanie zaakceptować dowolną liczbę argumentów, musiałem użyć
*args
, co oznaczało, że mój pierwotny plan śledzenia f.func_code.co_argcount musiał zostać zastąpiony arity atrybutdekoratora.Jeśli chodzi o obsługę nieskończonych programów, interpreter działa, dopóki nie osiągnie maksymalnej głębokości rekurencyjnej; moduł obsługi RuntimeError na dole ma cicho wychodzący w tym momencie i wypisuje bieżący ciąg wyjściowy.
Przypadki testowe:
źródło
['1','0'][...]
just'10'[...]
. 3) Dlaczegox is 0
i niex==0
(lubx<1
)? 4) Nie zawracaj sobie głowy określaniemRuntimeError
, wystarczyexcept
. 5) Ponieważ używasz języka Python 2, tabulacje i spacje liczą się jako różne poziomy wcięcia - to dobrze, ale powinno ci zaoszczędzić ~ 25 bajtów.x.a==1and x(y)or u(a(x.a-1)(b.partial(x,y)))
- operatory logiczne nadal mają zwarcie, ale używają mniej znaków niż trójka. Następnie zapisz innego bajtu przy użyciux.a-1
jako warunek (0 / false jeślix
ma wartość 1, niezerowe / true inaczej) i zamiana „wtedy” i „inny” wyrażeń:x.a-1and u(a(x.a-1)(b.partial(x,y)))or x(y)
. (Muszę jeszcze trochę kopać w golfa, kiedy mniex.a==1
to prawda, alex(y)
zwraca coś fałszywego, próbuje również oceniću(...)
. Ale wygląda na to, że nie musisz zapisywać marnych 3 bajtów, które by ci dały! Przyznaję, proszę pana: przekroczyłeś mnie.RuntimeError
podczas gdy mój po prostu prosi użytkownika o przekierowanie stderr ... więc prawdopodobnie mamy nawet spory. ; ^)*_
lambdas?Ghostscript
Jeszcze nie grałem w golfa, ponieważ wciąż muszę wypracować funkcję parsowania.
Ta implementacja używa
_
oraz:
zamiast>
i/
, i wymaga oddzielenia wszystkich znaków programu spacjami. Wynika to z tego, że>
i/
nie są poprawnymi nazwami w Postscript, a operatory nie ograniczają się, ale zostanie to naprawione podczas pisania parsera.Pierwsza część kodu powinna być dość przejrzysta, ponieważ jedynie powtarza definicje funkcji operatora. Magia dzieje się w definicji
!
.Sposób, w jaki
!
działa jest prosta: Po pierwsze, to dodaje argumentux
dof
poprzedzającx
do treścif
, spychając go na stosie, a nazywanie kopię wynikufun
.Następnie zawija cały stos jako tablicę.
.runandhide
to rozszerzenie Ghostscript do uruchamiania kodu w trybie piaskownicy, ukrywające zawartość poprzedniej tablicy przed procedurą, na której jest wywoływana.dict
Komenda popycha nowy słownik na stosie dict, zawężając zakres nazw zdefiniowanych w ciągu ażend
wyskakuje go wycofać. Zastępuje również=only
(operator wyjściowy, w którym używam@
) atrapę, tłumiąc dane wyjściowe podczas uruchamiania próbnego.stopped
jest odpowiednikiemtry
instrukcji PostScript znalezionej w innych językach i zwraca wartość true, jeśli procedura zgłosiła błąd, a false, jeśli zakończyła działanie.Po zakończeniu próbnego uruchomienia
fun
program przywraca oryginalny stos z ukrytej tablicy, a jeślifun
zakończy się bez błędu, uruchomi go naprawdę, zachowując dane wyjściowe.źródło
Python3,
685670634633 bajtówJestem prawie pewien, że to najdłuższa rzecz, jaką kiedykolwiek grałem w golfa. Kiedyś było to trochę czytelne, ale przestrzeganie rad @ sirpercival wyeliminowało tę wadę!
k
jest stosem, który zawiera funkcje przedstawione jako ciągi znaków"h(0,0)"
(które są c h ain ). Gdy funkcja jest przekazywana jako argument do innej funkcji, robirepr
„d i wszystkie numery zwiększany:"h('h(1,1)',0)"
. Gdy wszystkie0
s są zamienione w funkcji, całość jest przekazywanaeval
, wywołując w ten sposób odpowiednią funkcję Pythona - z których większość to funkcje lambda generowane z dużego łańcucha w linii 6 przezexec
linię 7.Największym bólem głowy było uzyskanie wielu poziomów zagnieżdżonych funkcji odpowiednio zwiększonych, cytowanych i uciekających. Mógłbym zaoszczędzić trochę więcej na operacjach wyrażeń regularnych, gdybym mógł założyć, że zagnieżdżanie funkcji nie będzie przebiegać głębiej niż na 9 poziomach, ale jak zaznaczono w komentarzach, prawdopodobnie nie jest to bezpieczne założenie.
Ungolfed wcześniejsza wersja kodu:
Jedyną potencjalną wadą tej implementacji jest to, że wykorzystuje rekurencję, więc programy, które powinny być nieskończone, dość szybko osiągają maksymalną głębokość rekurencji. (Prawdopodobnie chcesz przekierować stderr po uruchomieniu nieskończonego programu - w przeciwnym razie ślad stosu zapełni rzeczywiste dane wyjściowe.) Poza tym wszystko wydaje się działać.
źródło
lambda a
ik.pop()
.k.pop()
takCejlon,
116710571031Nie rozumiem go tak krótko, jak w wersjach monofonicznych typu python ...
import ceylon.language.meta.model{N=Function}import ceylon.collection{H=HashMap}interface D of F|b{}object b satisfies D{}class F(shared Integer a,[D+](D+)f,[D*]c=[])satisfies D{shared[D+]o(D i){[D+]s=[i].prepend(c);return a==1then f(*s)else[F(a-1,f,s)];}shared[D+]y([D+]i){return f(*i.prepend(c));}}F m<A>(N<[D+],A>f)given A satisfies[D+]=>F(f.parameterTypes.size,(D+i)=>f.apply(*i));[D,D]e(D x)=>[x,x];[F]t(F f){[D+]g(D+i){assert(is[D+]r=i.rest);return[i[0],*f.y(r)];}return[F(f.a+1,g)];}[D]k(D a,D d,D c)=>a==b then[d]else[c];[D+]l(F a,D x)=>a.o(x);[F]n(F f,F g){[D+]h(D+i){[D+]r=f.y(i);assert(is[D+]d=r[0:g.a]);return g.y(d).append(r[g.a...]);}return[F(f.a,h)];}[D]y(D x){process.write(x==b then"0"else"1");return[x];}class I(){variable D[]s=[];value c=H{'?'->b,'+'->m(`e`),'>'->m(`t`),'/'->m(`k`),'$'->m(`l`),'.'->m(`n`),'@'->m(`y`)};shared void r(Character i){if(i=='!'){assert(is F f=s[0],is D x=s[1]);s=f.o(x).append(s[2...]);}else{assert(is D d=c[i]);s=[d].append(s);}}}shared void z(){process.readLine()?.collect(I().r);}
Oto sformatowana (i skomentowana) wersja tego samego kodu (ze spacjami / nowymi wierszami / komentarzami staje się 4867 bajtami):
Funkcje klonowania
e
, shiftt
, forkk
, calll
, sayy
i chainn
używają ostatniej litery nazw dla wersji skróconej, ponieważ to dawało mniej kolizji. (Ciekawostki: rozwidlenie pierwotnie zdefiniowano w ten sposób:[Data] fork(Data a, Data b, Data c) => a == blank then [b] else [c];
- kiedy zmieniłem nazwęblank
nab
, to się zepsuło, ponieważ teraz porównało parametry,a
ab
zamiast tegoa
z pustym. Zajęło mi trochę czasu na debugowanie).z
Funkcja jest wspólna, bo moja IDE uruchamia te funkcje - narzędzie wiersza polecenia można również uruchomić te niewspólną.źródło