Clem to minimalny język programowania oparty na stosach, oferujący funkcje najwyższej klasy. Twoim celem jest napisanie tłumacza języka Clem. Powinien poprawnie wykonać wszystkie przykłady zawarte w implementacji referencyjnej, która jest dostępna tutaj .

• Jak zwykle obowiązują standardowe luki .
• Najmniejszy wpis według liczby bajtów wygrywa.

Język Clem

Clem to język programowania oparty na stosie z pierwszorzędnymi funkcjami. Najlepszym sposobem na naukę Clem jest uruchomienie cleminterpretera bez argumentów. Rozpocznie się w trybie interaktywnym, umożliwiając grę z dostępnymi poleceniami. Aby uruchomić przykładowe programy, wpisz clem example.clmgdzie example to nazwa programu. Ten krótki samouczek powinien wystarczyć, aby zacząć.

Istnieją dwie główne klasy funkcji. Funkcje atomowe i funkcje złożone. Funkcje złożone to listy złożone z innych funkcji złożonych i funkcji atomowych. Zauważ, że funkcja złożona nie może się zawierać.

Funkcje atomowe

Pierwszym typem funkcji atomowej jest stała . Stała jest po prostu liczbą całkowitą. Na przykład -10. Gdy interpreter napotyka stałą , wypycha ją na stos. Uruchom clemteraz. Wpisz -10polecenie. Powinieneś zobaczyć

> -10
001: (-10)
>

Wartość 001opisuje pozycję funkcji na stosie i (-10) jest stałą, którą właśnie wprowadziłeś. Teraz wpisz +11po znaku zachęty. Powinieneś zobaczyć

> +11
002: (-10)
001: (11)
>

Zauważ, że (-10)przesunął się na drugą pozycję na stosie i (11)teraz zajmuje pierwszą. Taka jest natura stosu! Zauważysz, że -jest to również polecenie zmniejszenia. Za każdym razem -lub +poprzedzając liczbę, oznaczają one znak tej liczby, a nie odpowiadające jej polecenie. Wszystkie pozostałe funkcje atomowe są komendami . Łącznie jest ich 14:

@  Rotate the top three functions on the stack
#  Pop the function on top of the stack and push it twice
$  Swap the top two functions on top of the stack
%  Pop the function on top of the stack and throw it away
/  Pop a compound function. Split off the first function, push what's left, 
   then push the first function.
.  Pop two functions, concatenate them and push the result
+  Pop a function. If its a constant then increment it. Push it
-  Pop a function. If its a constant then decrement it. Push it
<  Get a character from STDIN and push it to the stack. Pushes -1 on EOF.
>  Pop a function and print its ASCII character if its a constant
c  Pop a function and print its value if its a constant
w  Pop a function from the stack. Peek at the top of the stack. While it is
   a non-zero constant, execute the function.

Wpisanie polecenia w wierszu spowoduje wykonanie polecenia. Wpisz #znak zachęty (polecenie duplikatu). Powinieneś zobaczyć

> #
003: (-10)
002: (11)
001: (11)
> 

Zauważ, że (11) zostało zduplikowane. Teraz wpisz %w wierszu polecenia (polecenie upuszczenia). Powinieneś zobaczyć

> %
002: (-10)
001: (11)
> 

Aby wypchnąć polecenie na stos, po prostu umieść je w nawiasie. Wpisz (-)polecenie. Spowoduje to przesunięcie operatora zmniejszania na stos. Powinieneś zobaczyć

> (-)
003: (-10)
002: (11)
001: (-)
> 

Funkcje złożone

Możesz również zawrzeć wiele funkcji atomowych w nawiasach, aby utworzyć funkcję złożoną. Po wprowadzeniu funkcji złożonej w wierszu polecenia jest ona wypychana na stos. Wpisz ($+$)polecenie. Powinieneś zobaczyć

> ($+$)
004: (-10)
003: (11)
002: (-)
001: ($ + $)
>

Technicznie wszystko na stosie jest funkcją złożoną. Jednak niektóre funkcje złożone na stosie składają się z jednej funkcji atomowej (w takim przypadku uznamy je za funkcje atomowe ze względu na wygodę). Podczas manipulowania funkcjami złożonymi na stosie .często przydatne jest polecenie (konkatenacja). Wpisz .teraz. Powinieneś zobaczyć

> . 
003: (-10)
002: (11)
001: (- $ + $)
> 

Zauważ, że pierwsza i druga funkcja na stosie zostały połączone, a druga funkcja na stosie jest pierwsza na liście wynikowej. Aby wykonać funkcję znajdującą się na stosie (atomową lub złożoną), musimy wydać wpolecenie (while). wKomenda pokaże pierwszą funkcję na stosie i wykonać go wielokrotnie tak długo, jak druga funkcja na stosie jest niezerowa stała. Spróbuj przewidzieć, co się stanie, jeśli piszemy w. Teraz wpisz w. Powinieneś zobaczyć

> w
002: (1)
001: (0)
> 

Czy tego się spodziewałeś? Dwie liczby znajdujące się na szczycie stosu zostały dodane i ich suma pozostaje. Spróbujmy jeszcze raz. Najpierw upuszczamy zero i wciskamy 10, wpisując %10. Powinieneś zobaczyć

> %10
002: (1)
001: (10)
> 

Teraz napiszemy całą funkcję w jednym ujęciu, ale dodamy dodatkową %na końcu, aby pozbyć się zera. Wpisz (-$+$)w%polecenie. Powinieneś zobaczyć

> (-$+$)w%
001: (11)
> 

(Uwaga: ten algorytm działa tylko wtedy, gdy pierwsza stała na stosie jest dodatnia).

Smyczki

Ciągi są również obecne. Są to głównie cukier składniowy, ale mogą być bardzo przydatne. Gdy interpreter napotka ciąg, wypycha każdy znak od ostatniego do pierwszego na stos. Wpisz, %aby usunąć 11 z poprzedniego przykładu. Teraz wpisz 0 10 "Hi!"polecenie. 0Wstawi terminator NULL i 10będzie wstawić znak nowej linii. Powinieneś zobaczyć

> 0 10 "Hi!"
005: (0)
004: (10)
003: (33)
002: (105)
001: (72)
> 

Wpisz, (>)waby wydrukować znaki ze stosu, aż napotkamy terminator NULL. Powinieneś zobaczyć

> (>)w
Hi!
001: (0)
> 

Wnioski

Mam nadzieję, że powinno to wystarczyć do rozpoczęcia pracy z tłumaczem. Projekt języka powinien być stosunkowo prosty. Daj mi znać, jeśli coś jest strasznie niejasne :) Kilka rzeczy pozostało celowo niejasnych: wartości muszą być podpisane i co najmniej 16 bitów, stos musi być wystarczająco duży, aby uruchomić wszystkie programy referencyjne itp. Wiele szczegółów nie zostało wyrzeźbionych tutaj, ponieważ pełna specyfikacja języka byłaby zbyt duża do opublikowania (a jeszcze jej nie napisałem: P). W razie wątpliwości naśladuj implementację referencyjną.

Strona esolangs.org dla Clem

Referencyjna implementacja w C

Haskell, 931 921 875

nie jest jeszcze w pełni golfa, ale prawdopodobnie nigdy nie będzie. Mimo to jest już krótszy niż wszystkie inne rozwiązania. Niedługo będę grać w golfa. Nie mam już ochoty grać w golfa.

prawdopodobnie ma kilka subtelnych błędów, ponieważ nie grałem z referencyjną implementacją C.

to rozwiązanie używa tego typu StateT [String] IO ()do przechowywania „uruchomialnego” programu clem. większość programu jest parserem, który analizuje „program uruchamialny”.

w celu uruchomienia tego użycia r "<insert clem program here>".

import Text.Parsec
import Control.Monad.State
import Control.Monad.Trans.Class
import Data.Char
'#'%(x:y)=x:x:y
'%'%(x:y)=y
'@'%(x:y:z:w)=y:z:x:w
'$'%(x:y:z)=y:x:z
'/'%((a:b):s)=[a]:b:s
'+'%(a:b)=i a(show.succ)a:b
'.'%(a:b:c)=(a++b):c
_%x=x
b=concat&between(s"(")(s")")(many$many1(noneOf"()")<|>('(':)&((++")")&b))
e=choice[s"w">>c(do p<-t;let d=h>>= \x->if x=="0"then a else u p>>d in d),m&k,s"-">>(m&(' ':)&k<|>c(o(\(a:b)->i a(show.pred)a:b))),s"c">>c(do
 d<-t
 i d(j.putStr.show)a),o&(++)&map(show.ord)&between(s"\"")(s"\"")(many$noneOf"\""),(do
 s"<"
 c$j getChar>>=m.show.ord),(do
 s">"
 c$do
 g<-t
 i g(j.putChar.chr)a),m&b,o&(%)&anyChar]
k=many1 digit
i s f g|(reads s::[(Int,String)])>[]=f$(read s::Int)|0<1=g
t=h>>=(o tail>>).c
c n=return n
a=c()
h=head&get
(&)f=fmap f
m=o.(:)
o=modify
u=(\(Right r)->r).parse(sequence_&many e)""
r=(`runStateT`[]).u
s=string
j=lift

Python, 1684 1281 znaków

Wykonałem wszystkie podstawowe rzeczy związane z golfem. Uruchamia wszystkie przykładowe programy i dopasowuje wyjściowy znak po znaku.

import sys,os,copy as C
L=len
S=[]
n=[S]
Q=lambda:S and S.pop()or 0
def P(o):
 if o:n[0].append(o)
def X():x=Q();P(x);P(C.deepcopy(x))
def W():S[-2::]=S[-1:-3:-1]
def R():a,b,c=Q(),Q(),Q();P(a);P(c);P(b)
def A(d):
 a=Q()
 if a and a[0]:a=[1,a[1]+d,lambda:P(a)]
 P(a)
def V():
 a=Q();P(a)
 if a and a[0]-1and L(a[2])>1:r=a[2].pop(0);P(r)
def T():
 b,a=Q(),Q()
 if a!=b:P([0,0,(a[2],[a])[a[0]]+(b[2],[b])[b[0]]])
 else:P(a);P(b)
def r():a=os.read(0,1);F(ord(a)if a else-1)
def q(f):
 a=Q()
 if a and a[0]:os.write(1,(chr(a[1]%256),str(a[1]))[f])
def e(f,x=0):f[2]()if f[0]+f[1]else([e(z)for z in f[2]]if x else P(f))
def w():
 a=Q()
 while a and S and S[-1][0]and S[-1][1]:e(a,1)
def Y():n[:0]=[[]]
def Z():
 x=n.pop(0)
 if x:n[0]+=([[0,0,x]],x)[L(x)+L(n)==2]
D={'%':Q,'#':X,'$':W,'@':R,'+':lambda:A(1),'-':lambda:A(-1),'/':V,'.':T,'<':r,'>':lambda:q(0),'c':lambda:q(1),'w':w,'(':Y,')':Z}
def g(c):D[c]()if L(n)<2or c in'()'else P([0,1,D[c]])
N=['']
def F(x):a=[1,x,lambda:P(a)];a[2]()
def E():
 if'-'==N[0]:g('-')
 elif N[0]:F(int(N[0]))
 N[0]=''
s=j=""
for c in open(sys.argv[1]).read()+' ':
 if j:j=c!="\n"
 elif'"'==c:E();s and map(F,map(ord,s[:0:-1]));s=(c,'')[L(s)>0]
 elif s:s+=c
 elif';'==c:E();j=1
 else:
    if'-'==c:E()
    if c in'-0123456789':N[0]+=c
    else:E();c in D and g(c)

Testowanie :

Zbierz clemint.py , clemtest_data.py , clemtest.py i skompilowany clemplik binarny do katalogu i uruchom clemtest.py.

Wyjaśnienie :

Najbardziej niestosowana wersja to ta . Śledź wraz z tym.

Sto główny stos. Każda pozycja na stosie ma 3 listy, jedną z:

Constant: [1, value, f]
Atomic: [0, 1, f]
Compound: [0, 0, fs]

Dla stałych fjest funkcją, która wypycha stałą na stos. Dla atmoics, fto funkcja wykonuje jedną z operacji (na przykład -, +). Dla związków fsjest lista pozycji.

xecwykonuje element. Jeśli jest stała lub atomowa, po prostu wykonuje funkcję. Jeśli jest złożony, jeśli nie było jeszcze rekurencji, wykonuje każdą funkcję. Więc wykonanie (10 20 - 30)będzie wykonanie każdej z funkcji 10, 20, -, i 30, pozostawiając 10 19 30na stosie. Jeśli nastąpiła rekurencja, to po prostu wypycha funkcję złożoną na stos. Na przykład podczas wykonywania (10 20 (3 4) 30)wynik powinien być następujący 10 20 (3 4) 30: nie 10 20 3 4 30.

Zagnieżdżanie było trochę trudne. Co robisz czytając (1 (2 (3 4)))? Rozwiązaniem jest mieć stosy. Na każdym poziomie zagnieżdżania na stosie umieszczany jest nowy stos, a wszystkie operacje wypychania trafiają na ten stos. Ponadto, jeśli zostało zagnieżdżone, funkcje atomowe są wypychane zamiast wykonywane. Więc jeśli widzisz 10 20 (- 30) 40, 10jest wciśnięty, a następnie 20, po czym nowy stos jest tworzony, -a 30są wypychane na nowy stos i )Zdejmuje nowego komina, zamienia ją w danej pozycji i odkłada ją na stosie o jeden poziom niżej. endnest()uchwyty ). To było trochę trudne, ponieważ istnieje szczególny przypadek, w którym tylko jeden przedmiot został popchnięty, a my wracamy na główny stos. Oznacza to, że (10)powinien popchnąć stałą10, a nie kompozyt z jedną stałą, ponieważ wtedy -i +nie działają. Nie jestem pewien, czy jest to zgodne z zasadami, ale tak to działa ...

Mój interpreter jest procesorem znak po znaku - nie tworzy tokenów - więc liczby, łańcuchy i komentarze były nieco denerwujące. Istnieje osobny stos, Ndla aktualnie przetwarzanego numeru i za każdym razem, gdy przetwarzana jest postać, która nie jest liczbą, muszę zadzwonić, endnum()aby sprawdzić, czy najpierw powinienem uzupełnić ten numer i umieścić go na stosie. To, czy jesteśmy w ciągu, czy w komentarzu, jest śledzone przez zmienne boolowskie; gdy sznurek jest zamknięty, popycha wszystkie wewnętrzne części stosu. Liczby ujemne również wymagały specjalnego traktowania.

To tyle na temat przeglądu. Resztę realizacji wszystkich Zabudowy i upewniając się zrobić głębokie kopie +, -i #.

C 837

Dzięki @ceilingcat za znalezienie znacznie lepszej (i krótszej) wersji

Traktuje to wszystko jako proste ciągi - wszystkie elementy stosu są ciągami, nawet stałe są ciągami.

#define Q strcpy
#define F(x)bcopy(b,f,p-b);f[p-b-x]=!Q(r,p);
#define C(x,y)Q(S[s-x],S[s-y]);
#define N[9999]
#define A Q(S[s++]
#define D sprintf(S[s++],"%d"
#define G(x)}if(*f==x){
#define H(x)G(x)s--;
#define R return
#define Z(x)T(t,u,v)-1||putchar(x);H(
char S N N;s;c;T(b,f,r)char*b,*f,*r;{char*p;strtol(b+=strspn(b," "),&p,0);if(p>b){F(0)R 1;}if(c=*b==40){for(p=++b;c;)c+=(*p==40)-(*p++==41);F(1)R-1;}p++;F(0)*r*=!!*b;R 0;}*P(char*p){if(*p==34)R++p;char*r=P(p+1);D,*p);R r;}E(char*x){char*p,c N,f N,r N,t N,u N,v N;for(Q(c,x);*c;Q(c,p)){Q(t,S[s-1]);if(T(c,f,p=r))A,f);else{{G(64)C(0,1)C(1,2)C(2,3)C(3,0)G(35)A,t);G(36)C(0,2)C(2,1)C(1,0)H(37)H(47)T(t,u,v);*v&&A,v);A,u);H(46)strcat(strcat(S[s-1]," "),t);H(43)D,atoi(t)+1);H(45)D,atoi(t)-1);G(60)D,getchar());H(62)Z(atoi(u))99)Z(*u)119)for(Q(u,t);atoi(S[s-1]);)E(u);G(34)p=P(p);}}}}

Wypróbuj online!

Mniej oryginalna wersja mojego oryginału (w przeciwieństwie do wersji golfowej, ta drukuje stos, gdy kończy się, jeśli nie jest pusty, i przyjmuje parametr -e, abyś mógł podać skrypt w wierszu poleceń zamiast odczytywać z pliku):

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define FIRST_REST(x) memcpy(first, b, p - b); first[p - b - x] = '\0'; strcpy(rest, p);
#define COPY(dest,src) strcpy(stack[size + dest], stack[size + src]);
char stack[9999][9999]; int size = 0;
int token(char *b, char *first, char *rest)
{
    while (*b == 32) b++;
    char *p; int x = strtol(b, &p, 0);
    if (p > b) { FIRST_REST(0) return 1; }
    if (*b == '(') { int c = 1; for (p = ++b; c; ++p) c += (*p == '(') - (*p == ')'); FIRST_REST(1) return -1; }
    p++; FIRST_REST(0) if (!*b) *rest = '\0'; return 0;
}
char *push(char *pointer)
{
    if (*pointer == '\"') return pointer+1;
    char *result = push(pointer+1);
    sprintf(stack[size++], "%d", *pointer);
    return result;
}
void eval(char *x)
{
    char program[9999], first[9999], rest[9999], tos[9999], tmp1[9999], tmp2[9999];
    char *pointer;
    for (strcpy(program, x); *program; strcpy(program, pointer))
    {
        *stack[size] = '\0';
        strcpy(tos, stack[size-1]);
        if (token(program, first, rest))
        {
            pointer = rest;
            strcpy(stack[size++], first);
        }
        else
        {
            pointer = rest;
            if (*first == '@'){
                COPY(0, -1) COPY(-1, -2) COPY(-2, -3) COPY(-3, 0) }
            if (*first == '#')
                strcpy(stack[size++], tos);
            if (*first == '$'){
                COPY(0, -2) COPY(-2, -1) COPY(-1, 0) }
            if (*first == '%')
                size--;
            if (*first == '/'){
                size--; token(tos, tmp1, tmp2); if (*tmp2) strcpy(stack[size++], tmp2); strcpy(stack[size++], tmp1); }
            if (*first == '.'){
                size--; strcat(stack[size - 1], " "); strcat(stack[size - 1], tos); }
            if (*first == '+'){
                size--; sprintf(stack[size++], "%d", atoi(tos) + 1); }
            if (*first == '-'){
                size--; sprintf(stack[size++], "%d", atoi(tos) - 1); }
            if (*first == '<')
                sprintf(stack[size++], "%d", getchar());
            if (*first == '>'){
                size--; if (token(tos, tmp1, tmp2) == 1) putchar(atoi(tmp1)); }
            if (*first == 'c'){
                size--; if (token(tos, tmp1, tmp2) == 1) printf("%s", tmp1); }
            if (*first == 'w'){
                size--; strcpy(tmp1, tos); while (atoi(stack[size - 1])) eval(tmp1); }
            if (*first == '\"')
                pointer=push(pointer);
        }
    }
}
int main(int argc, char **argv)
{
    char program[9999] = "";
    int i = 0, comment = 0, quote = 0, space = 0;
    if (!strcmp(argv[1], "-e"))
        strcpy(program, argv[2]);
    else
    {
        FILE* f = fopen(argv[1], "r");
        for (;;) {
            char ch = fgetc(f);
            if (ch < 0) break;
            if (!quote) {
                if (ch == '\n') comment = 0;
                if (ch == ';') comment = 1;
                if (comment) continue;
                if (ch <= ' ') { ch = ' '; if (space++) continue; }
                else space = 0;
            }
            if (ch == '\"') quote = 1 - quote;
            program[i++] = ch;
        }
        fclose(f);
    }
    eval(program);
    for (int i = 0; i < size; i++) printf("%03d: (%s)\r\n",size-i,stack[i]);
    return 0;
}