Escribe un intérprete de Clem

11

Clem es un lenguaje de programación mínimo basado en pila con funciones de primera clase. Su objetivo es escribir un intérprete para el lenguaje Clem. Debe ejecutar correctamente todos los ejemplos incluidos en la implementación de referencia, que está disponible aquí .

  • Como de costumbre, se aplican las lagunas estándar .
  • La entrada más pequeña por conteo de bytes gana.

El lenguaje clem

Clem es un lenguaje de programación basado en pila con funciones de primera clase. La mejor manera de aprender Clem es ejecutar el clemintérprete sin argumentos. Comenzará en modo interactivo, permitiéndole jugar con los comandos disponibles. Para ejecutar los programas de ejemplo, escriba clem example.clmdonde ejemplo es el nombre del programa. Este breve tutorial debería ser suficiente para comenzar.

Hay dos clases principales de funciones. Funciones atómicas y funciones compuestas. Las funciones compuestas son listas compuestas de otras funciones compuestas y funciones atómicas. Tenga en cuenta que una función compuesta no puede contenerse a sí misma.

Funciones atómicas

El primer tipo de función atómica es la constante . Una constante es simplemente un valor entero. Por ejemplo, -10. Cuando el intérprete encuentra una constante , la empuja a la pila. Corre clemahora. Escriba -10en el indicador. Debería ver

> -10
001: (-10)
>

El valor 001describe la posición de la función en la pila y (-10) es la constante que acaba de ingresar. Ahora ingrese +11en el indicador. Debería ver

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

Observe que se (-10)ha movido a la segunda posición en la pila y (11)ahora ocupa la primera. Esta es la naturaleza de una pila! Notarás que -también es el comando de decremento. Cada vez -o +preceder a un número, denotan el signo de ese número y no el comando correspondiente. Todas las demás funciones atómicas son comandos . Hay 14 en total:

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

Al escribir un comando en el indicador, se ejecutará el comando. Escriba #en el indicador (el comando duplicado). Debería ver

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

Observe que el (11) se ha duplicado. Ahora escriba %en el indicador (el comando soltar). Debería ver

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

Para enviar un comando a la pila, simplemente enciérrelo entre paréntesis. Escriba (-)en el indicador. Esto empujará al operador de disminución a la pila. Debería ver

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

Funciones compuestas

También puede encerrar múltiples funciones atómicas entre paréntesis para formar una función compuesta. Cuando ingresa una función compuesta en el indicador, se empuja a la pila. Escriba ($+$)en el indicador. Debería ver

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

Técnicamente, todo en la pila es una función compuesta. Sin embargo, algunas de las funciones compuestas en la pila consisten en una sola función atómica (en cuyo caso, las consideraremos funciones atómicas por conveniencia). Al manipular funciones compuestas en la pila, el .comando (concatenación) suele ser útil. Escribe .ahora. Debería ver

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

Observe que las funciones primera y segunda en la pila se concatenaron, y que la segunda función en la pila viene primero en la lista resultante. Para ejecutar una función que está en la pila (ya sea atómica o compuesta), debemos emitir el wcomando (while). El wcomando mostrará la primera función en la pila y la ejecutará repetidamente siempre que la segunda función en la pila sea una constante distinta de cero. Intenta predecir qué sucederá si escribimos w. Ahora, escribe w. Debería ver

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

¿Es eso lo que esperabas? Se agregaron los dos números que se encuentran en la parte superior de la pila y su suma permanece. Vamos a intentarlo de nuevo. Primero, soltaremos el cero y empujaremos un 10 escribiendo %10. Debería ver

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

Ahora escribiremos toda la función en una sola toma, pero agregaremos un extra %al final para eliminar el cero. Escriba (-$+$)w%en el indicador. Debería ver

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

(Tenga en cuenta que este algoritmo solo funciona si la primera constante en la pila es positiva).

Instrumentos de cuerda

Las cuerdas también están presentes. En su mayoría son azúcares sintácticos, pero pueden ser bastante útiles. Cuando el intérprete encuentra una cadena, empuja a cada personaje del último al primero en la pila. Escriba %para descartar el 11 del ejemplo anterior. Ahora, escriba 0 10 "Hi!"en el indicador. El 0insertará un terminador NULL y la 10insertará un carácter de nueva línea. Debería ver

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

Escriba (>)wpara imprimir caracteres de la pila hasta que encontremos el terminador NULL. Debería ver

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

Conclusiones

Esperemos que esto sea suficiente para comenzar con el intérprete. El diseño del lenguaje debe ser relativamente sencillo. Avíseme si hay algo terriblemente confuso :) Algunas cosas se han dejado intencionalmente vagas: los valores deben estar firmados y al menos 16 bits, la pila debe ser lo suficientemente grande como para ejecutar todos los programas de referencia, etc. Muchos detalles no se han tallado aquí porque una especificación de lenguaje completo sería prohibitivamente grande para publicar (y aún no he escrito uno: P). En caso de duda, imite la implementación de referencia.

La página de esolangs.org para Clem

La implementación de referencia en C

O por
fuente
Dices que aún no has escrito la especificación del idioma. ¿Supongo que eres el creador del idioma?
COTO
@COTO Eso es correcto. Yo creé el lenguaje.
Orby
55
Pregunta muy importante: ¿lo pronuncia "klem" o "see-lem"?
Martin Ender
44
@ MartinBüttner: "klem" :)
Orby
2
Es posible que desee especificar la dirección en la que el comando @ gira las 3 funciones principales. (001 -> 002 -> 003 -> 001, o 003 -> 002 -> 001 -> 003)
kwokkie

Respuestas:

1

Haskell, 931 921 875

esto aún no está totalmente golfizado, pero probablemente nunca lo será. Aún así, ya es más corto que todas las demás soluciones. Voy a jugar al golf más pronto. No tengo ganas de jugar al golf más que esto.

probablemente tiene algunos errores sutiles porque no jugué con la implementación de referencia C.

Esta solución utiliza el tipo StateT [String] IO ()para almacenar un programa clem "ejecutable". la mayoría del programa es un analizador que analiza el "programa ejecutable".

para ejecutar este uso 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
orgulloso Haskeller
fuente
5

Python, 1684 1281 caracteres

Tengo todas las cosas básicas de golf hechas. Ejecuta todos los programas de ejemplo y coincide con la salida carácter por carácter.

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)

Prueba :

Reúna clemint.py , clemtest_data.py , clemtest.py y un clembinario compilado en un directorio y ejecútelo clemtest.py.

Expansión :

La versión más despiadada es esta . Sigue junto con ese.

SEs la pila principal. Cada elemento de la pila es una lista de 3, una de:

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

Para las constantes, fes una función que empuja la constante a la pila. Para atmoics, fes una función que ejecuta una de las operaciones (por ejemplo -, +). Para los compuestos, fses una lista de artículos.

xecejecuta un elemento Si es una constante o una atómica, solo ejecuta la función. Si es un compuesto, si aún no ha habido recursividad, ejecuta cada función. Así ejecución (10 20 - 30)ejecutará cada una de las funciones 10, 20, -y 30, dejando 10 19 30en la pila. Si ha habido recursividad, simplemente empuja la función compuesta a la pila. Por ejemplo, al ejecutar (10 20 (3 4) 30), el resultado debería ser 10 20 (3 4) 30, no 10 20 3 4 30.

Anidar fue un poco complicado. ¿Qué haces mientras lees (1 (2 (3 4)))? La solución es tener una pila de pilas. En cada nivel de anidación, se empuja una nueva pila en la pila de pilas, y todas las operaciones de inserción van a esta pila. Además, si ha habido anidamiento, las funciones atómicas se empujan en lugar de ejecutarse. Entonces, si ve 10 20 (- 30) 40, 10se empuja, entonces 20, se crea una nueva pila, -y 30se empuja a la nueva pila, y se )sale de la nueva pila, la convierte en un elemento y la empuja hacia la pila un nivel hacia abajo. endnest()manijas ). Fue un poco complicado ya que hay un caso especial en el que solo se ha presionado un elemento y estamos volviendo a la pila principal. Es decir, (10)debe empujar la constante10, no es un compuesto con una constante, porque entonces -y +no funciona. No estoy seguro de si esto tiene principios, pero es la forma en que funciona ...

Mi intérprete es un procesador carácter por carácter, no crea tokens, por lo que los números, las cadenas y los comentarios son algo molestos de tratar. Hay una pila separada N, para un número procesado actualmente, y cada vez que se procesa un carácter que no es un número, tengo que llamar endnum()para ver si primero debo completar ese número y ponerlo en la pila. Las variables booleanas realizan un seguimiento de si estamos en una cadena o un comentario; Cuando se cierra una cuerda, empuja todas las entrañas de la pila. Los números negativos también requieren un manejo especial.

Eso es todo para el resumen. El resto estaba poniendo en práctica todos los muebles empotrados, y asegurándose de hacer copias de profundidad en +, -, y #.

Claudiu
fuente
¡Prestigio! ¿Te divertiste? :)
Orby
@Orby: ¡seguro que sí! Es un lenguaje interesante, definitivamente extraño. Espero poder conseguir un intérprete que sea <1k. No estoy seguro de qué esperar de otras presentaciones.
Claudiu
4

C 837

Gracias a @ceilingcat por encontrar una versión mucho mejor (y más corta)

Esto trata todo como cadenas simples: todos los elementos de la pila son cadenas, incluso las constantes son cadenas.

#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);}}}}

Pruébalo en línea!

Una versión menos golfizada de mi original (a diferencia de la versión golfizada, esta imprime la pila cuando termina si no está vacía y toma un parámetro -e para que pueda especificar el script en la línea de comando en lugar de leerlo desde un archivo):

#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;
}
Jerry Jeremiah
fuente
¡Agradable! Impresionante vencer a la solución de Python en C. tengo que subir mi versión más corta, me las arreglé para cortar 60 bytes o menos .. todavía me pregunto si hay un enfoque diferente, que produciría mucho menos de 1000 caracteres
Claudiu
@Claudiu Yo también lo pensé, pero no pude entender cómo.
Jerry Jeremiah