Napisz tłumacza zmianowego

10

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ę fi wartość xze stosu i stosuje się fdo x. Jeśli fma arity 1, lista f(x)jest dodawana na początku stosu. Jeśli ma arity n > 1, nowa (n-1)funkcja gjest wypychana na stos. Wymaga danych wejściowych i zwrotów .x1,x2,...,xn-1f(x,x1,x2,...,xn-1)
  • ?( puste ) popycha puste do stosu.
  • +( klon ) wypycha na stos jednoargumentową funkcję, która powiela dane wejściowe: dowolna wartość xjest odwzorowywana [x,x].
  • >( shift ) wypycha na stos jednoargumentową funkcję, która przyjmuje funkcję n-ary f, i zwraca funkcję (n+1)-ary, gktóra ignoruje swój pierwszy argument x, wywołuje fpozostałe i haczy xprzed wynikiem. Na przykład shift(clone)jest funkcją binarną, która pobiera dane wejściowe a,bi zwraca [a,b,b].
  • /( fork ) wypycha na stos funkcję potrójną, która pobiera trzy dane wejściowe a,b,ci zwraca, [b]jeśli ajest pusta, i w [c]przeciwnym razie.
  • $( wywołanie ) wypycha na stos funkcję binarną, która wyskakuje z funkcji fi wartości x, i stosuje fsię xdokładnie tak, jak to !robi.
  • .( łańcuch ) wypycha na stos funkcję binarną, która wyskakuje z dwóch funkcji fi gzwraca ich skład: funkcja, hktóra ma tę samą aranżację fi która przyjmuje swoje dane wejściowe normalnie, stosuje się fdo nich, a następnie w pełni stosuje gsię do wyniku (wywołania tyle razy, ile dyktuje to jego arsenał), przy czym niewykorzystane przedmioty z produkcji fpozostają w wyniku h. Załóżmy na przykład, że fjest to funkcja binarna, która klonuje swój drugi argument i gjest 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, fto najpierw zastosujemy do a,bprodukcji[a,b,b], następnie gjest 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, 0czy była pusta, a 1jeś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 0s lub 1s 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 0s i 1s. 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ę ni zwrócić przynajmniej nznaki 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 ai 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,xdane 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 1s zawsze wzrasta o jeden:

@?/!@>!??/!!>!+.!!.!!.!!.+>!.!!$$$$+$>!>!$>!>!+>!$>!>!>!+>!>!///!!>!>!>!.!!.!!.!!.!!.!!.!!.!!.!!.!!.!!+!!!!!

Repozytorium zawiera wersję z adnotacjami.

Zgarb
źródło
Jestem trochę zdezorientowany. Kiedy piszesz „przyjmuje”, tak jak w poleceniu shift, masz na myśli trzaski, czy masz na myśli zastosowanie polecenia zastosuj?
tecywiz121
1
Poza tym nie jestem pewien z twojej specyfikacji, jak powinien działać łańcuch. Czy możesz wyjaśnić to na przykładzie?
tecywiz121
@ tecywiz121 Tak to rozumiem: powiedz, że masz dwie funkcje na górze stosu f(x1, x2, ..., xn)i g(y1, y2, ..., ym). Wywołanie .wyskakuje z nich obu i powoduje uruchomienie funkcji h(z1, z2, ..., zn). Teraz możesz pochłonąć wszystkie te argumenty, stopniowo je curry !. Po ntakich aplikacjach pozostała funkcja miała tylko jeden argument i w tym momencie oblicza f(z1, z2, ..., zn)(tj. fStosuje się do wszystkich argumentów, w których się przeglądasz), co wypycha niektóre nowe wartości, a następnie natychmiast zużywa mwartości ze stosu i wywołuje gje.
Martin Ender
@ MartinBüttner Jeśli Zgarb uważa, że ​​jest to zgodne z regułami, możesz użyć drugiego parametru wejściowego określającego maksymalny rozmiar wyniku. Byłoby to również rozwiązanie dla leniwej kwestii oceny.
randomra 18.04.15
@ tecywiz121 .działa dokładnie tak, jak opisał Martin, z tym wyjątkiem, że jeśli fzwraca listę mniejszą niż mwartości, wynik jest niezdefiniowany (skład ma arity n, więc nie może jeść więcej argumentów ze stosu). Zasadniczo dane wyjściowe fsą używane jako tymczasowy stos, na który gjest wypychany i nakładany mza pomocą !, a wynik jest dodawany do głównego stosu.
Zgarb

Odpowiedzi:

12

Python 2, 752 667 534 506 445 436 427 404 398 393 bajtów

To 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.

k,d=[],[]
u=k.append
def z(f,a=1):f.a=a;return f
exec "i=!x:x(*map(k.pop,[-1]*x.a)));e=dict(zip('?+>/$.@',[0,!x:u(x)<u(x)),!x:u(!a,*_:x(*_)<u(a),x.a+1))),!x,y,z:u((z,y)[x<1]),3),!x,y:u(!*_:x(y,*_),x.a-1))if x.a>1 else x(y),2),!x,y:u(!*_:x(*_)<i(y),x.a)),2),!x:d.append(`+(x>0)`)<u(x))]))".replace('!',"z(lambda ")
for _ in raw_input():
 try:[i,u][_ in e](e.get(_,e['$']))
 except:break
print d

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:

stack = []
push = stack.append

def arity(func,a=1): #give each of our functions an arity
    func.arity = a
    return func

def do(func): ##pop the args off the stack, then call the function
    args = map(stack.pop,[-1]*func.arity)
    func(*args)

def call(func,arg): #apply is just do(call)
    if func.arity == 1:
        func(arg)
    else:
        def curried(*a): #a quick little currier
            func(arg, *a)
        curried = arity(curried, func.arity - 1)
        push(curried)

def clone(arg):
    push(arg)
    push(arg)

def shift(func):
    def shifted(a, *arg):
        func(*arg)
        push(a)
    shifted = arity(shifted, func.arity + 1)
    push(shifted)

def fork(a, b, c):
    if a == 0:
        push(b)
    else:
        push(c)

def chain(func, gunc):
    def composition(*args):
        func(*args)
        do(gunc)
    composition = arity(composition, func.arity)
    push(composition)

def say(arg):
    print '10'[arg == 0],
    push(arg)

commands = {'?': 0,
            '+': arity(clone),
            '>': arity(shift),
            '/': arity(fork, 3),
            '$': arity(call, 2),
            '.': arity(chain, 2),
            '@': arity(say)}

def interpret(input_string):
    for command in input_string:
        try:
            if command == '!':
                do(call)
            else:
                push(commands[command])
        except RuntimeError: #this handles max recursion depth errors
            break            # for infinite programs
    print

if __name__ == "__main__":
    interpret(raw_input())

Podstawową ideą jest to, że lista Pythona działa bardzo ładnie jako stos, a przechowywanie u=k.appendnie tylko zapisuję postacie, ale mogę także użyć @ujako dekoratora do wypychania funkcji (już nie!).

Ponieważ 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 atrybut dekoratora .

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:

>>> tests
['?@!@@!', '$+.!!+!!', '?@$..!!+.!!+>!.!!!!+?/!!!@!@>!!!', '?@+$>!>!.!!+>!.!!///!!>!>!.!!+!!!!', '?@+$>!>!.!!+>!.!!///!!>!>!.!!+!!!!!!!', '?@+$>!>!.!!+>!.!!///!!>!>!.!!+!!!!!!!!!!', '?@+$>!>!.!!+>!.!!///!!>!>!.!!+!!!!!!!!!!!!!', '@?/!@>!.!!??/!!>!.!!+.!!.+>!.!!$$.!!$.!!$.!!+.!!$>!>!.!!$>!>!.!!+>!.!!$>!>!>!.!!+>!>!.!!///!!>!>!>!.!!+!!!!!']
>>> for t in tests: m(t)
0 1

0 0 1 0
0
0 0
0 0 0
0 0 0 0
0 0 1 0 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
sirpercival
źródło
1
Moja pierwsza reakcja: @ _ @ Poważnie, dobra robota - umieszczenie rzeczywistych funkcji na stosie jest naprawdę fajnym rozwiązaniem. Kilka wskazówek: 1) Operatory trójskładnikowe można zwykle skracać w taki czy inny sposób . 2) Możesz wymienić na ['1','0'][...]just '10'[...]. 3) Dlaczego x is 0i nie x==0(lub x<1)? 4) Nie zawracaj sobie głowy określaniem RuntimeError, wystarczy except. 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.
DLosc
1
Powinieneś być w stanie to przyciąć 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życiu x.a-1jako warunek (0 / false jeśli xma 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 mnie
minąłeś
1
Po napotkaniu podobnego problemu z moim rozumiem, co teraz się nie udaje - jeśli x.a==1to prawda, ale x(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.
DLosc
1
Tylko jeden spór: w określonym formacie wyjściowym nie ma spacji - możesz rozwiązać różne strategie , nie wiedząc, który z nich jest najkrótszy. Oczywiście, twój program obsługuje, RuntimeErrorpodczas gdy mój po prostu prosi użytkownika o przekierowanie stderr ... więc prawdopodobnie mamy nawet spory. ; ^)
DLosc
1
Do czego służy *_lambdas?
mbomb007
4

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 !.

/switch {
    /y exch def
    /x exch def
    {x} {y} ifelse
} bind def

/unwrap {
    dup type (arraytype) eq {aload pop} if
} bind def

/! { % IN: <x> <f> OUT: <g>|<f(x)>
    [ 3 1 roll unwrap] cvx %prefix argument into function
    dup /fun exch def %bind

    [ count 1 roll ] { %run the function sandboxed so it can't take any additional args
        2 dict begin
        /=only {} def % suppress output
            {
                fun
            } stopped /err exch def clear err
        end
    } .runandhide


    exch {
        $error /errorname get
        (stackunderflow) ne {
            handleerror
        } if

        $error /newerror false put

        unwrap
    } {
        unwrap exec
    } ifelse
} def

/? 0 def
/+ {{dup}} def
/_ {{/f exch def pop f}} def % using _ instead of >
/: {{? ne 3 1 roll switch}} def % using : instead of /
/$ {{!}} def
/. {{/g exch def exec g}} def 
/@ {{dup ? eq {0}{1} ifelse =only}} def

Sposób, w jaki !działa jest prosta: Po pierwsze, to dodaje argumentu xdo fpoprzedzając xdo treści f, spychając go na stosie, a nazywanie kopię wyniku fun.

Następnie zawija cały stos jako tablicę. .runandhideto rozszerzenie Ghostscript do uruchamiania kodu w trybie piaskownicy, ukrywające zawartość poprzedniej tablicy przed procedurą, na której jest wywoływana. dictKomenda popycha nowy słownik na stosie dict, zawężając zakres nazw zdefiniowanych w ciągu aż endwyskakuje 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. stoppedjest odpowiednikiem tryinstrukcji 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 funprogram przywraca oryginalny stos z ukrytej tablicy, a jeśli funzakończy się bez błędu, uruchomi go naprawdę, zachowując dane wyjściowe.

AJMansfield
źródło
2

Python3, 685 670 634 633 bajtów

Jestem 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 wadę!

from re import*
E,*k="E"
P="e(k.pop(),k.pop())"
def H(a,b):global k;k+=list(a)+[N(b)];exec("k+=%s;"%P*Z(N(b)));return[]
def e(a,b):a=sub("(?<!\d)0",repr(N(b,1)).replace("\\",r"\\"),a,1);return Z(a)and[a]or list(eval(a))
D=list(zip("ilhydsSNZ",[3,2,2]+[1]*6,sub("A","N(a)",',b,c:[N([b,c][a>E])]|,b:e(A,N(b))|,b:["H(%s,%s)"%(A,repr(b))]|:print(0+(a>E),end="")or[A]|:[A]*2|:["S(0,%s)"%A]|,b:b+[A]|,b=-1:sub("\d+",lambda m:str(int(m.group())+b),a)|:len(split("\D0",a))-1').split("|")))
for n,r,f in D:exec(n+"=lambda a"+f)
F=dict(zip("/$.@+>?!",D))
for z in input():n,r,f=F[z];k+=z!="!"and[[n+"(%s)"%",".join("0"*r),E][z=="?"]]or eval(P)

kjest 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, robi repr„d i wszystkie numery zwiększany: "h('h(1,1)',0)". Gdy wszystkie 0s są zamienione w funkcji, całość jest przekazywana eval, 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 przez execlinię 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:

from re import *
E="E"
stack=[]

clone=lambda a:[unnest(a)]*2
shift=lambda a:["shifted(0,%s)"%unnest(a)]
fork=lambda a,b,c:[unnest(c if a!=E else b)]
call=lambda a,b:apply(unnest(a),unnest(b))
chain=lambda a,b:["chained(%s,%s)"%(unnest(a),repr(b))]
def say(a):
 print(1 if a!=E else 0,end="")
 return [unnest(a)]

shifted=lambda a,b:b+[unnest(a)]
def chained(a,b):
 global stack
 stack+=list(a)+[unnest(b)]
 exec("stack+=apply(stack.pop(),stack.pop());"*zeros(unnest(b)))
 return []

nest=lambda a,direction:sub("\d+",lambda m:str(int(m.group())+direction),a)
unnest=lambda a:nest(a,-1)
zeros=lambda a:len(split("\D0",a))-1
def apply(a,b):
 a=sub("(?<!\d)0",repr(nest(b,1)).replace("\\",r"\\"),a,1)
 return [a] if zeros(a) else list(eval(a))

functions=dict(zip("+>/$.@",zip(["clone","shift","fork","call","chain","say"],[1,1,3,2,2,1])))

for cmd in input():
 if"!"==cmd:
  stack+=apply(stack.pop(),stack.pop())
 elif"?"==cmd:
  stack+=[E]
 else:
  name,arity=functions[cmd]
  stack+=[name+"(%s)"%",".join("0"*arity)]

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ć.

DLosc
źródło
Czy możesz napisać program, który generuje powyższy program, a następnie go wykonuje? Masz wiele powtarzających się kodów, które powinny być kompresowalne jak lambda ai k.pop().
mbomb007
@ mbomb007 ... Myślę, że mój mózg eksplodowałby. (Ale zobacz ostatnią edycję - i k.pop()tak
sprawiłem,
czy potrafisz wykonać trik exec / translate dla wszystkich tych lambdów? skleić je wszystkie w jednym sznurku?
sirpercival
jeszcze jeden komentarz: Wątpię, czy można polegać na zagnieżdżaniu funkcji <= 9 w tym języku
sirpercival
@sirpercival Tak, myślałem o tym. I nie, chyba nie. : ^ P
DLosc
1

Cejlon, 1167 1057 1031

Nie 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):

import ceylon.language.meta.model {
    N=Function
}
import ceylon.collection {
    H=HashMap
}
//↑ Import of stuff we need – with a shorter alias.
// (The comment is down here due to a bug in my comment and space
//  remover – it doesn't remove a comment if it is the first token
//  at all.)

// Our data items are either functions or blanks.
interface D of F | b {}

// There is no point in having many blanks – so here a singleton.
object b satisfies D {}

// The function class. Our functions take a number of data items,
// and return a number of data items.
// We know the arity a, and have also an actual function f, and a number
// or already collected arguments.
class F(shared Integer a, [D+](D+) f, [D*] c = [])
        satisfies D {
    // apply once (= collect one parameter). Returns either the result,
    // or a function with arity one less.
    shared [D+] o(D i) {
        [D+] s = [i].prepend(c);
        return a == 1 then f(*s) else [F(a - 1, f, s)];
    }
    // apply fully (= with all needed parameters).
    // The input size should equal the arity.
    shared [D+] y([D+] i) {
        // merge collected and input arguments.
        return f(*i.prepend(c));
    }
}
// creates a shift function from a ceylon function,
// deriving the arity using reflection.
F m<A>(N<[D+],A> f)
        given A satisfies [D+]
        => F(f.parameterTypes.size, (D+ i) => f.apply(*i));

//
// clone: a unary function that duplicates its input: any value x is mapped to [x,x].
//
[D, D] e(D x) => [x, x];

//
// shift: a unary function that takes in an n-ary function f, and returns an
// (n+1)-ary function g that ignores its first argument x, calls f on the
// remaining ones, and tacks x in front of the result. For example,
// shift(clone) is a binary function that takes inputs a,b and returns [a,b,b].
//
[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)];
}

//
// fork: a ternary function that takes three inputs a,d,c, and returns [d] if a is a blank,
// and [c] otherwise.
//
[D] k(D a, D d, D c) => a == b then [d] else [c];

//
// call: a binary function that pops a function f and a value x,
//        and applies f to x exactly as ! does.
//
[D+] l(F a, D x) => a.o(x);

//
// chain:  a binary function that pops two functions f and g, and returns their composition:
//         a function h that has the same arity as f, and which takes its inputs normally, applies
//         f to them, and then fully applies g to the result (calls it as many times as its arity
//         dictates), with unused items from the output of f remaining in the result of h. For
//         example, suppose that f is a binary function that clones its second argument, and
//         g is call. If the stack contains [f,g,a,b,c] and we do .!!, then it contains
//         [chain(f,g),a,b,c]; if we do !! next, then f is first applied to a,b, producing
//         [a,b,b], then g is applied to the first two elements of that since its arity is 2,
//         producing [a(b),b], and the stack will finally be [a(b),b,c].
//
[F] n(F f, F g) {
    [D+] h(D+ i) {
        // call f, remember the results.
        [D+] r = f.y(i);
        // first some results from f are the arguments to g:
        assert (is [D+] d = r[0:g.a]);
        // remaining results from f are passed back directly, with the results from g.
        return g.y(d).append(r[g.a...]);
    }
    return [F(f.a, h)];
}

//
// say: a unary function that simply returns its input, and prints 0 if it was a blank,
//      and 1 if it was a function.
// 
[D] y(D x) {
    process.write(x == b then "0" else "1");
    return [x];
}

//
// Interpreter class, which manages the stack and interprets the commands.
// Just call the r method with the individual command characters.
//
class I() {
    // The stack. The only variable in the whole program.
    variable D[] s = [];

    // a hash map of items to be pushed by commands, most build using the m function.
    // The apply command is not here, this is handled separately by the interpreter. 
    value c = H {
        '?'->b,
        '+'->m(`e`),
        '>'->m(`t`),
        '/'->m(`k`),
        '$'->m(`l`),
        '.'->m(`n`),
        '@'->m(`y`)
    };

    // Interprets one command, indicated by a character.
    // Will throw an AssertionError for unknown commands.
    shared void r(Character i) {
        if (i == '!') {
            assert (
                is F f = s[0],
                is D x = s[1]);
            // apply f on x, push the result onto a shortened version of the stack.
            s = f.o(x).append(s[2...]);
        } else {
            assert (is D d = c[i]);
            // push d on top of the stack.
            s = [d].append(s);
        }
    }
}

shared void z() {
    process.readLine()?.collect(I().r);
}

Funkcje klonowania e, shift t, fork k, call l, say yi chain nuż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ę blankna b, to się zepsuło, ponieważ teraz porównało parametry, aa bzamiast tego az pustym. Zajęło mi trochę czasu na debugowanie).

zFunkcja jest wspólna, bo moja IDE uruchamia te funkcje - narzędzie wiersza polecenia można również uruchomić te niewspólną.

Paŭlo Ebermann
źródło
Wersje zapętlone w pewnym momencie generują błąd StackOverflowError, a następnie kończą. JVM nie ma optymalizacji stosu rekurencyjnego (lub przynajmniej żadnej, która działałaby dla mojego programu).
Paŭlo Ebermann