Tłumacz ustny

25

Na podstawie komentarza George'a Edisona do tego pytania napisz najmniejszego tłumacza.

  • Możesz użyć wybranego przez siebie języka.
  • Puste języki się nie liczą. Twój program musi mieć co najmniej dwa znaki.
  • Program nie musi interpretować całego języka, a jedynie kompletny zestaw funkcji językowych Turinga (zawierający tłumacza).
  • Quines się nie liczy.
  • Nie używaj wbudowanej evalfunkcji języka lub jej odpowiednika. To samo dotyczy applyitp.
Hoa Long Tam
źródło
1
(Hmm .. powinienem coś zrobić /usr/bin/cat) co z kompletnością Turinga?
Ming-Tang,
@ SHiNKiROU: Dzięki, nie uważałem tego za test. Zaktualizowano
Hoa Long Tam
Powiązane: Język w / najmniejszy interpreter napisany sam w sobie na przepełnieniu stosu, choć jest niewiele (tylko jedna?) Odpowiedzi, które są zgodne z podanymi tu regułami.
dmckee,
1
Czy musimy przepisać ten parser Scheme sexp, czy możemy uznać, że język hosta jest w porządku?
JB
@JB: Narzędzia przetwarzania łańcucha języka są w porządku, w tym sexpanalizator składni.
Hoa Long Tam

Odpowiedzi:

19

CI - 260

,(1p0(2d())(41(2d())('#((1p0()(10()(1d,1p$)=)<)$2d,1p$)(40(1d,1c$^)(''(1d,^)('0
'9('0-(,'0'9('0-2p10*+1p$)(!1d)~)$^)(0($)'$(^)'^(&)'&(c)'c(p)'p(d)'d(=)'=(<)'<(
>)'>(~)'~(.)'.(,)',(!)'!(+)'+(-)'-(*)'*(/)'/(%)'%()38p(1p3p0(3d)((2)(3)=p1d1p$)
=)$)~)=)=,2p$&)=)=)<)$$

320 → 260: Wciśnij proste odwzorowania znaków na instrukcje, a następnie złóż je. Zmniejsza to o połowę rozmiar kodu na skrzynkę (jest 18 skrzynek), ale składanie kosztuje 30 znaków.

To kolejny z moich skonstruowanych języków (bazowy tłumacz hostowany na Gist ). Jest wyjątkowy, ponieważ język realizuje fragmenty kodu. Oznacza to, że ciągi instrukcji w tym języku opartym na stosie są używane z takim samym skutkiem, jak struktury danych lub zamknięcia w innych językach:

1^      # Push a 1, and "lift" it to be a code literal.
(5 +)   # Define a code literal.
&       # Join the two code literals, forming (1 5 +)
$       # Execute the code literal.

Interpreter buduje fragment kodu całego programu przed jego uruchomieniem, więc można go również uznać za kompilator. Z tego powodu układanie interpretera w stos nie powoduje wykładniczego obciążenia w czasie wykonywania.

Tłumacz tłumaczy wszystkich swoich operatorów bezpośrednio od tłumacza hosta. Jednak sam analizuje, więc większość kodu to tylko sekwencje, które tłumaczą znaki na odpowiadające im literały kodu. Nie jest to to samo, co używanie eval, ale pokazuje, jak zależna jest implementacja dowolnego języka programowania od semantyki języka / architektury hosta.


Odniesienie językowe:

Uzyskaj tłumacza tutaj

Bloki

  • ( ... )

    Utwórz „blok”, który jest faktycznie listą instrukcji bez kontekstu. Wewnętrznie może to być nawet kod maszynowy.

  • blok $

    Zadzwoń na blok. Odbiorca otrzymuje globalny stos, który zawiera wywoływany blok.

  • wartość ^

    Podnieś wartość. Mianowicie, zamień go w blok, który wypycha tę wartość.

    Przykład :

       1 ^
    == (1)
    
  • blok1 blok2 &

    Połącz dwa bloki, tworząc jeden, który będzie działał oba kolejno.

    Przykład :

       (1) (2) &
    == (1 2)
    

Manipulacja stosami

  • n c

    Skopiuj n-tą wartość stosu.

    Przykład :

       5 4 3 2 1 0 3c
    == 5 4 3 2 1 0 3
    
  • n p

    Podnieś n-tą wartość stosu (usuń ją i przenieś na przód).

    Przykład :

       5 4 3 2 1 0 3p
    == 5 4 2 1 0 3
    
  • n d

    Upuść n wartości ze stosu. 0djest zakazem.

    Przykład :

       5 4 3 2 1 0 3d
    == 5 4 3
    

Operatorzy relacyjni

  • ab (on_true) (on_false) =

    Sprawdź, czy a jest równe b. Zużyj wszystkie argumenty oprócz pierwszego i wywołaj komendę on_true lub on_false. Jeśli jeden argument jest równy zero, a drugi jest innego typu, wynik będzie fałszywy. W przeciwnym razie aib muszą być liczbami całkowitymi.

    Przykład :

       3 3 ('0+ .) (1d) =
    == 3 '0+ .
    
  • ab (on_true) (on_false) <

    Sprawdź, czy a jest mniejsze niż b. aib muszą być liczbami całkowitymi.

    Przykład :

       3 5 (1d 5) () <
    == 3 1d 5
    == 5
    
  • ab (on_true) (on_false) >

    Sprawdź, czy a jest większe niż b. aib muszą być liczbami całkowitymi.

    Przykład :

       3 5 (1d 5) () >
    == 3
    
  • a lo hi (on_true) (on_false) ~

    Sprawdź, czy lo <= a <= hi. a, lo i hi muszą być liczbami całkowitymi.

    Przykład :

       3 0 10 ('0+ .) (1d) ~
    == 3 '0+ .
    

I / O

  • do .

    Umieść postać c (zużywając ją ze stosu).

  • ,

    Zdobądź postać i wepchnij ją na stos. Po osiągnięciu końca pliku wypychane jest -1.

  • do !

    Unget postaci. Podobnie jak ungetc w C, dozwolona jest tylko jedna odpowiedź zwrotna.

Literały całkowite

  • 'c

    Naciśnij znak c.

  • [0–9] +

    Naciśnij liczbę całkowitą dziesiętną.

Arytmetyka

  • ab +
  • ab -
  • ab *

    Dodaj / odejmij / pomnóż dwie liczby.

    Przykład :

       3 5 + 7 3 + *
    == 80
    
  • ab /

  • ab %

    Podział i moduł. W przeciwieństwie do C, zaokrąglają się w kierunku ujemnej nieskończoności.

Różne

  • #komentarz do kodu

    #Charakter komentuje się wszystko do końca linii.

  • )

    Służy do zakończenia bloków. Można go również użyć do zakończenia całego programu.

  • Wszystkie pozostałe znaki są ignorowane.

Joey Adams
źródło
24

Binary Lambda Calculus, 232 bity (29 bajtów)

0101000110100000000101011000000000011110000101111110011110000101110011110000001111000010110110111001111100001111100001011110100111010010110011100001101100001011111000011111000011100110111101111100111101110110000110010001101000011010

Szczegółowe informacje można znaleźć na stronie http://en.wikipedia.org/wiki/Binary_lambda_calculus#Lambda_encoding

John Tromp
źródło
2
Dlaczego nie jest to zaakceptowana odpowiedź D: BLC jest niesamowita!
kot
Czy potrafisz to w ogóle wyjaśnić?
PyRulez
1
Niestety Wikipedia usunęła stronę Binary Lambda Calculus. Moja strona tromp.github.io/cl/cl.html prowadzi do zachowanej kopii i do artykułu, który napisałem, wyjaśniając działanie tłumacza.
John Tromp,
13

Nie mogę przypisać sobie tego , ale pomyślałem, że podzielę się tym niesamowitym:

Brainf *** (423)

>>>+[[-]>>[-]++>+>+++++++[<++++>>++<-]++>>+>+>+++++[>++>++++++<<-]+>>>,<++[[>[
->>]<[>>]<<-]<[<]<+>>[>]>[<+>-[[<+>-]>]<[[[-]<]++<-[<+++++++++>[<->-]>>]>>]]<<
]<]<[[<]>[[>]>>[>>]+[<<]<[<]<+>>-]>[>]+[->>]<<<<[[<<]<[<]+<<[+>+<<-[>-->+<<-[>
+<[>>+<<-]]]>[<+>-]<]++>>-->[>]>>[>>]]<<[>>+<[[<]<]>[[<<]<[<]+[-<+>>-[<<+>++>-
[<->[<<+>>-]]]<[>+<-]>]>[>]>]>[>>]>>]<<[>>+>>+>>]<<[->>>>>>>>]<<[>.>>>>>>>]<<[
>->>>>>]<<[>,>>>]<<[>+>]<<[+<<]<]
Peter Olson
źródło
10

BlockScript - 535

{[B':=?0:B';=?0:B'}=?0:B'{=?,A!,A!d1c&:B'?=?,A!,A!2e&:B''=?,,A!d3c&:B{[B'0<?0:B
'9>?0:1}!?B'0-{[,g!?c'0-B10*d+A!:Bd]A!d3c&}!:B'#=?{[,10=?,]A!:A!}!:,A!Bb&}{[AC[
B]DB?[AB{[Bh&hbhn!}{[B[AB]C?1-eA!:b}&[C1=?E[C]FHc&B!:C2=?{G?D:E[C}!FHcI!:C3=?E[
C]B!:C'!=?G[ABC]Hc&dbh&D?b@I!B!:b@I!:C'&=?HB!:C'@=?FGDI!:C'[=?GF&HDI!:C']=?F[A]
HDI!:C',=?,B!:C'.=?G.FHDI!:C'a'z{[DC<?0:DB>?0:1}!?Ce-HA!B!:C'A'Ze!?F[B]Cg-dA!B!
:{C'+=?{[CB+}:C'-=?{[CB-}:C'*=?{[CB*}:C'/=?{[CB/}:C'%=?{[CB%}:C'<=?{[CB<}:C'>=?
{[CB>}:C'==?{[CB=}:0}!?H[A][B]Ge!B!:FHDI!:c},c!0ac&0&0&0bho!;

BlockScript to trywialny język oparty na stosach spaghetti , który stworzyłem specjalnie na to wyzwanie. Podstawowym tłumaczem jest blockcript.c .

Przykładowy program (drukuje pierwsze 15 liczb Fibonacciego):

{[B?B10/A!B10%d&:0}
{[B0<?'-.0B-A!:{B?Bh!{[B?B[A]A!B[B]'0+.:}!:'0.}!10.}
{[B?Dd!DC+B1-CecA!:}
0 1 15d!
;

Interpreter odczytuje zarówno kod źródłowy, jak i program z standardowego wejścia, w tej kolejności. Oznacza to, że aby uruchomić tłumacza w tłumaczu, po prostu skopiuj i wklej:

# Level 1
{[B':=?0:B';=?0:B'}=?0:B'{=?,A!,A!d1c&:B'?=?,A!,A!2e&:B''=?,,A!d3c&:B{[B'0<?0:B
'9>?0:1}!?B'0-{[,g!?c'0-B10*d+A!:Bd]A!d3c&}!:B'#=?{[,10=?,]A!:A!}!:,A!Bb&}{[AC[
B]DB?[AB{[Bh&hbhn!}{[B[AB]C?1-eA!:b}&[C1=?E[C]FHc&B!:C2=?{G?D:E[C}!FHcI!:C3=?E[
C]B!:C'!=?G[ABC]Hc&dbh&D?b@I!B!:b@I!:C'&=?HB!:C'@=?FGDI!:C'[=?GF&HDI!:C']=?F[A]
HDI!:C',=?,B!:C'.=?G.FHDI!:C'a'z{[DC<?0:DB>?0:1}!?Ce-HA!B!:C'A'Ze!?F[B]Cg-dA!B!
:{C'+=?{[CB+}:C'-=?{[CB-}:C'*=?{[CB*}:C'/=?{[CB/}:C'%=?{[CB%}:C'<=?{[CB<}:C'>=?
{[CB>}:C'==?{[CB=}:0}!?H[A][B]Ge!B!:FHDI!:c},c!0ac&0&0&0bho!;

# Level 2
{[B':=?0:B';=?0:B'}=?0:B'{=?,A!,A!d1c&:B'?=?,A!,A!2e&:B''=?,,A!d3c&:B{[B'0<?0:B
'9>?0:1}!?B'0-{[,g!?c'0-B10*d+A!:Bd]A!d3c&}!:B'#=?{[,10=?,]A!:A!}!:,A!Bb&}{[AC[
B]DB?[AB{[Bh&hbhn!}{[B[AB]C?1-eA!:b}&[C1=?E[C]FHc&B!:C2=?{G?D:E[C}!FHcI!:C3=?E[
C]B!:C'!=?G[ABC]Hc&dbh&D?b@I!B!:b@I!:C'&=?HB!:C'@=?FGDI!:C'[=?GF&HDI!:C']=?F[A]
HDI!:C',=?,B!:C'.=?G.FHDI!:C'a'z{[DC<?0:DB>?0:1}!?Ce-HA!B!:C'A'Ze!?F[B]Cg-dA!B!
:{C'+=?{[CB+}:C'-=?{[CB-}:C'*=?{[CB*}:C'/=?{[CB/}:C'%=?{[CB%}:C'<=?{[CB<}:C'>=?
{[CB>}:C'==?{[CB=}:0}!?H[A][B]Ge!B!:FHDI!:c},c!0ac&0&0&0bho!;

# Level 3
{[B?B10/A!B10%d&:0}
{[B0<?'-.0B-A!:{B?Bh!{[B?B[A]A!B[B]'0+.:}!:'0.}!10.}
{[B?Dd!DC+B1-CecA!:}
0 1 15d!
;

Podobnie jak w filmie Incepcja , nie można zejść głębiej niż trzy poziomy. To nie jest kwestia czasu, ale przestrzeni. BlockScript obficie wycieka pamięć, a to ma związek ze sposobem zaprojektowania samego języka.


Odniesienie językowe:

Uzyskaj tłumacza tutaj

W BlockScript „stos” nie jest tablicą, która jest zastępowana kolejnymi operacjami, do których możesz być przyzwyczajony. W rzeczywistości jest on implementowany jako niezmienna lista połączona, a stos utrzymuje się przez cały czas trwania programu. Ponadto żaden operator (oprócz @) nie usuwa wartości ze stosu. Jednak modyfikacje stosu wpływają tylko na blok, w którym występują.

Wybór wartości

  • a przez z

    Weź 0-25 przedmiot ze stosu i pchnij go na stos. aodnosi się do głowy lub ostatnio pchanego przedmiotu stosu.

  • A przez Z

    Pobierz 0-25 pozycję bieżącej klatki i pchnij ją na stos.

  • [

    Otwórz „ramkę”, aby wybrać elementy z odnośnika stosu (patrz poniżej) na szczycie stosu. [nie wymaga dopasowania ], ale ramki mają zasięg leksykalny. W BlockScript „zakres” jest określany przez nawiasy klamrowe ( {... }), które tworzą bloki. Zatem otwarcie ramki wewnątrz bloku nie będzie miało wpływu na kod poza blokiem.

  • ]

    Zamknij bieżącą ramkę, wracając do poprzedniej ramki (jeśli istnieje).

Bloki

  • { ... }

    Utwórz „blok” i wepchnij go na stos. Wewnątrz bloku stos zacznie się od tego, co było przed blokiem, z wyjątkiem tego, że stos wywołującego zostanie przesunięty na wierzch. Stosy są trwałe i niezmienne w BlockScript, więc bloki są zamknięciami. Ten idiom {[oznacza otwórz blok, a następnie otwórz ramkę, aby rozpocząć wybieranie argumentów (za Apomocą Z). Zwracana wartość bloku jest szczytem stosu, gdy }zostanie osiągnięta.

    Przykład:

    '3 '2 '1 {[ b. d. f. B. C. D. A! } 'D 'C 'B d!;
    

    To drukuje 123BCD123DCB123BCD123DCB…. Małe litery odnoszą się do wartości stosu, podczas gdy duże litery odnoszą się do argumentów (ponieważ ramka jest ustawiona na stos wywołującego). A!przejmuje głowę dzwoniącego (co z pewnością jest wywoływanym blokiem) i dzwoni do niego. Jeśli zastanawiasz się, dlaczego odwraca się za BCDkażdym razem, to dlatego, że B. C. D.wypycha te argumenty w odwrotnej kolejności tuż przed wywołaniem samego bloku.

  • !

    Zadzwoń na blok. Wciśnij wartość zwracaną na stos.

Referencje stosu

  • &

    Utwórz odniesienie do stosu i popchnij je do stosu. Potraktuj to jako „super-przeciw”, ponieważ skutecznie bierze każdy przedmiot ze stosu i tworzy z niego „krotkę”. Idiomu &[środki, niezależnie a, b, cokreślone wcześniej mogą być dostępne z A, B, C(w dalszej części bloku, aż ]spotyka).

    Po części dlatego, że &przechwytuje więcej wartości, niż zwykle potrzebuje, BlockScript przecieka pamięć z założenia.

  • @

    Przełącz się na stos wskazywany przez odniesienie do stosu a. Ten operator jest dość dziwny, ale interpreter BlockScript korzysta z niego kilka razy, aby uniknąć konieczności dwukrotnego przekazywania tych samych argumentów. Efekty @(lub dowolnej operacji stosu, jeśli o to chodzi) są ograniczone do bloku, w którym są wywoływane. Ramka pozostaje nienaruszona @, więc można jej użyć do przechwytywania potrzebnych wartości po zmianie stosów.

Wyrażenie warunkowe

  • ? <on true> : <on false>

    Wyrażenie warunkowe, podobnie jak operator trójskładnikowy w C. To znaczy, jeśli ajest „prawda” (to znaczy, że nie jest równe zeru całkowitemu), to wykonaj <na true> , w przeciwnym razie <na false> .

I / O

Uwaga: Wprowadzanie i wysyłanie odbywa się w UTF-8. „Znak” to liczba całkowita odpowiadająca indeksowi Unicode.

  • ,

    Zdobądź następny znak wejścia i pchnij go na stos. Po osiągnięciu końca wprowadzania naciśnij zamiast tego -1.

  • .

    Wyprowadź postać na wierzch stosu.

Liczby całkowite / literowe

Uwaga: Liczby całkowite i znaki są takie same w BlockScript.

  • 'c

    Naciśnij znak c.

  • [0–9] +

    Naciśnij liczbę całkowitą dziesiętną.

Arytmetyka

Te operatory działają tylko na wartościach całkowitych.

  • +Oblicz b+ a(wypychając wynik, ale nie odrzucając żadnej wartości).
  • -Oblicz b- a.
  • *Oblicz b* a.
  • /Oblicz b/ a(dzielenie liczb całkowitych; zaokrągla w kierunku ujemnej nieskończoności).
  • %Oblicz b% a(moduł całkowity; zaokrągla w kierunku ujemnej nieskończoności).

Operatorzy relacyjni

Te operatory działają tylko na wartościach całkowitych.

  • <Jeśli bjest mniejsze niż a, naciśnij 1, w przeciwnym razie naciśnij 0.
  • >
  • =

Różne

  • # Komentarz do końca linii
  • Program musi kończyć się na ;
  • Wszystkie pozostałe znaki są ignorowane.
Joey Adams
źródło
2
Chrystus. Chcesz udostępnić specyfikację, tak jak w przypadku CI?
Casey
@Casey: Dodano odniesienie.
Joey Adams
1
Czy chciałbyś wiedzieć, że śnisz? ... Na poziomie 4.
Mateen Ulhaq,
3

Zozotez LISP : 414

dodawanie linii w celu uzyskania ładnego bloku nie jest potrzebne i nie jest liczone.

((\(E V A L)(E(r)'(())))(\(x e)(?(s x)(V x e)((\(b j)(?(= b ")(a j)(?(= b \)x
(?(= b ?)(?(E(a j)e)(E(a(d j))e)(E(a(d(d j)))e))(?(s b)(A b(E(a j)e)(E(a(d j)
)e))(E(a(d(d b)))(L(a(d b))j e)))))))(E(a x)e)(d x))))(\(x g)(? g(?(= x(a(a
g)))(d(a g))(V x(d g)))x))(\(f h v)(?(= f r)(r)(?(= f p)(p h)(?(= f s)(s h)(?
(= f a)(a h)(?(= f d)(d h)(?(= f =)(= h v)(c h v))))))))(\(k v i)(? k(L(d k)(
d v)(c(c(a k)(E(a v)i))i))i)))

Teoretycznie powinien być w stanie uruchomić się sam, ale ponieważ oryginalny interpreter jest plikiem binarnym BrainFuck, a sam interpreter, mogłem przetestować tylko każdą część. Po otrzymaniu samego i prostego wyrażenia (p p)myślę, że potrzebuje więcej czasu niż 40 minut, na które czekałem do tej pory i używam mojego szybkiego, jitbfaby go uruchomić, który (źle) używa Perla Inline-C do uruchomienia kodu C w locie.

Niemożliwe jest zaimplementowanie całego Zozoteza w Zozotezie, ponieważ nie ma on możliwości mutowania wad i :(setq / defin) potrzebuje tego do aktualizacji powiązań. Nie wdrożyłem również wyraźnego argumentu start / progn lub & rest, makr i specjalnych argumentów drukowania, ponieważ nie użyłem go w tłumaczu. Uwzględniłem p(drukuję), mimo że go nie używam, więc programy muszą jawnie wydrukować swoje obliczenia, tak jak oryginalny tłumacz.

To samo bez golfa:

;; A stand alone Zozotez script need to be
;; contained in one expression, here with
;; all functions provided as arguments to
;; get them bound in the dynamic environment
((\ (E V A L)
  (E(r)'(())))
 ;; E (EVAL)
 (\ (x e)
   (? (s x)
      (V x e)
      ((\ (b j)
         (? (= b ") (a j)
         (? (= b \) x
         (? (= b ?) (? (E(a j)e) (E(a(d j))e) (E(a(d(d j)))e))
         (? (s b)
            (A b (E(a j)e) (E (a(d j))e))
            (E (a(d(d b))) (L(a(d b))j e)))))))
       (E (a x) e)(d x))))
 ;; V (VALUE / symbol->value)
 (\ (x g)
   (? g
      (? (= x (a (a g)))
         (d (a g))
         (V x (d g)))
      x))
 ;; A (APPLY) but just for primitives
 (\ (f h v)
   (? (= f r) (r)
   (? (= f p) (p h)
   (? (= f s) (s h)
   (? (= f a) (a h)
   (? (= f d) (d h)
   (? (= f =)
      (= h v)
      (c h v))))))))
 ;; L ( joint evLis / extend-env)
 (\ (k v i)
   (? k
      (L (d k) 
         (d v)
     (c (c (a k) 
           (E (a v) i)) 
        i))
      i)))
Sylwester
źródło
0

CHIQRSX9 + (prawdopodobnie niekonkurencyjny), 2 bajty

+I

Nie ma sposobu, aby napisać interpretera samo-tłumaczącego w tym języku opartym na HQ9 + bez użycia I, który uruchamia wbudowany interpreter przetwarzający STDIN.

użytkownik8397947
źródło
1
Nigdzie w przepisach nie jest mowa o tym, że wbudowane auto-tłumacze są niedozwolone. Mówi o eval, co dotyczy wyrażeń, a nie programów.
Erik the Outgolfer
Jak obliczyć liczby pierwsze w tym języku?
pppery
@ppperry Xma sprawić, że język Turinga będzie kompletny (a tym samym będzie w stanie obliczyć liczby pierwsze) w sposób zależny od implementacji.
user8397947,
Zgodnie ze stroną Esolang Xpolecenie interpretera Perla losowo zaburza program i wykonuje go, co oznacza, że ​​nie można używać poleceń do deterministycznego obliczania liczb pierwszych. Czy możesz podać przykład tłumacza, który pozwala korzystać z niego Xw sposób określony przez Ciebie?
pppery
@ppperry Najwyraźniej tłumacz napisany w Perlu jest jedynym tłumaczem, więc nie. A co, jeśli istnieje program, który oblicza liczby pierwsze, gdy są „losowe” z określoną wartością?
user8397947,
0

Współbieżny system plików Befunge 98 - 53 \ 18 bajtów (prawie na pewno oszukiwanie)

Pełny 53 bajtowy interpreter bez ograniczeń (chociaż nie testowałem skomplikowanych interakcji czasowych obejmujących dzielenie i zawijanie adresów IP):

v ;;;;;;;;
>]390'ai@
 t;;;;;;;;
;>zzzzz#;

Odczytuje dane wejściowe z pliku o nazwie ai wykonuje go. Nie jest to określone w regułach, że nie możemy używać kodu modyfikującego.

18-bajtowy interpreter, który nie pozwala na owijanie (przesunięcie IP jednej krawędzi kodu i rozpoczęcie od drugiej krawędzi):

]210'ai@
t
><
pppery
źródło