computer science - Creando el intérprete más corto de Turing-complete

computer-science code-golf

Question

Acabo de intentar crear el intérprete de idiomas más pequeño posible. ¿Te gustaría unirte e intentarlo?

Reglas del juego:

• Debe especificar un lenguaje de programación que esté interpretando. Si es un lenguaje que inventaste, debería venir con una lista de comandos en los comentarios.
• Su código debería comenzar con el programa de ejemplo y los datos asignados a su código y variables de datos.
• Tu código debe terminar con la salida de tu resultado. Es preferible que haya instrucciones de depuración en cada paso intermedio.
• Su código debe ser ejecutable como está escrito.
• Puede suponer que los datos son 0 y 1 (int, string o booleano, su elección) y la salida es un bit único.
• El lenguaje debe ser Turing-completo en el sentido de que para cualquier algoritmo escrito en un modelo estándar, como la máquina de Turing, cadenas de Markov, o similar de su elección, es razonablemente obvio (o explicado) cómo escribir un programa que después de ejecutarse por su intérprete realiza el algoritmo.
• La longitud del código se define como la longitud del código después de la eliminación de la parte de entrada, la parte de salida, las declaraciones de depuración y los espacios en blanco no necesarios. Agregue el código resultante y su longitud a la publicación.
• No puede usar funciones que hagan que el compilador ejecute código para usted, como eval() , exec() o similar.

Esta es una Wiki de la comunidad, lo que significa que ni la pregunta ni las respuestas obtienen los puntos de reputación de los votos. ¡Pero vota de todos modos!

Answer 1

¡Reúna el siguiente código usando A86 para obtener un intérprete BF de 150 bytes!

 add dh,10h
push dx
add dh,10h
push dx
mov bl,80h
lea dx,[bx+2]
add bl,byte ptr [bx]
mov byte ptr [bx+1],al
mov ah,3dh
int 21h
pop ds,es
jc l14
mov bx,ax
mov ah,3fh
mov cx,di
xor dx,dx
int 21h
jc l14
mov bx,ax
xor ax,ax
rep stosw
xor di,di
xor si,si
inc ch
l1:
cmp si,bx
jae l14
lodsb
mov bp,8
push l1
l2:
dec bp
js ret
cmp al,[bp+l15]
jne l2
l3:
mov cl,[bp+8+l15]
jmp cx
l4:
inc di
ret
l5:
dec di
ret
l6:
es inc byte ptr [di]
ret
l7:
es dec byte ptr [di]
ret
l8:
mov ah,2
es mov dl,[di]
int 21h
ret
l9:
mov ah,8
int 21h
es mov [di],al
ret
l10:
es cmp byte ptr [di],dh
jne ret
l11:
cmp si,bx
jae l14
lodsb
cmp al,'']''
jne l11
ret
l12:
es cmp byte ptr [di],dh
je ret
l13:
dec si
jz l14
cmp byte ptr [si-1],''[''
jne l13
l14:
ret
l15:
db ''>''
db ''<''
db ''+''
db ''-''
db ''.''
db '',''
db ''[''
db '']''
db offset l4-100h
db offset l5-100h
db offset l6-100h
db offset l7-100h
db offset l8-100h
db offset l9-100h
db offset l10-100h
db offset l12-100h

Especifique un nombre de archivo en la línea de comando, sin necesidad de comillas dobles, como fuente BF.

Answer 2

Escrito en Perl , 140 caracteres de longitud, incluida la invocación de shell y las banderas:

perl -ne''push@a,split;if(eof){$i=0;while($i>=0){($a,$b,$c)=@a[$i..$i+2];$b>-1?$a[$b]-=$a[$a]:print chr$a[$a];$i=$b>-1&&$a[$b]<=0?$c:$i+3;}}''

Versión legible:

#!/usr/bin/perl -n
push @prog, split //s+/, $_;
if(eof) {
$i = 0;
while($i >= 0) {
($a, $b, $c) = @prog[$i .. $i + 2];
if($b > -1) {
$prog[$b] -= $prog[$a];
} else {
print chr $prog[$a];
}
if($b > -1 and $prog[$b] <= 0) {
$i = $c;
} else {
$i + 3;
}
}
}

Lo anterior es un intérprete para el código pseudo-máquina para una computadora con un subleq instrucciones utilizando la instrucción subleq . Básicamente, el código fuente debería ser solo un grupo de números separados por espacios en blanco. Un programa de prueba simple para verificar mis resultados (debe imprimir "Hola" y una nueva línea de Unix):

0 0 6 72 105 10 3 -1 9 4 -1 12 5 -1 15 0 0 -1

Versión legible de la entrada de prueba (funciona igual de bien):

0 0 6
72 105 10
3 -1 9
4 -1 12
5 -1 15
0 0 -1

Answer 3

Intérprete URM en CoffeeScript , 143 bytes (167 con nuevas líneas).

Esta versión de URM consta de una cantidad ilimitada de registros, con cero, sucesores y operadores de salto. Es bien sabido que esto es turing-completo.

El programa URM está escrito en la matriz c (comandos), y las entradas están en la matriz r (registros). Después del cálculo, la salida está en r[0] y se muestra este valor.

El intérprete, con programa de ejemplo y entrada que calcula 32 + 13 (y de hecho produce 45):

# Addition program, similar to http://planetmath.org/examplesofunlimitedregistermachines
c = [[''j'', 1, 2, 4], [''s'', 0], [''s'', 2], [''j'', 1, 1, 0]]
# Input: 32, 13, thus the desired output is: 45
r = [32, 13]
k = 0
while k < c.length
t = c[k]
k += 1
if t[0] == ''z''
r[t[1]] = 0
if t[0] == ''s''
if !r[t[1]]?
r[t[1]] = 0
r[t[1]] += 1
if t[0] == ''j'' && r[t[1]] == r[t[2]]
k = t[3]
alert r[0]

Versión reducida:

k=0
while k<c.length
t=c[k]
k+=1
if t[0]==''z''
r[t[1]]=0
if t[0]==''s''
if !r[t[1]]?
r[t[1]]=0
r[t[1]]+=1
if t[0]==''j''&&r[t[1]]==r[t[2]]
k=t[3]
alert r[0]

Lo que realmente me gusta de este código es que es realmente sencillo y fácil de entender.

Answer 4

Lenguaje personalizado: SLA
Palabras clave:
i - Interpretar SLB q - Salir

Lenguaje personalizado: SLB
Palabras clave:
cp ("texto") - Interpretar texto como programa C

Ejemplo:
cp ("# include / nint main () {puts (/" Hi! / n / "); return 0}")

Intérprete (Escrito en SLA): iq

3 personajes!

Answer 5

Mi propia entrada, implementación de OISC en Ruby . Tiene 85 bytes de largo, y estoy seguro de que uno podría exprimir algunos más con algunos trucos ingeniosos. Los programas deben contener datos en código (línea de números separados por espacios). Por el momento no puedo proporcionar un programa de trabajo escrito en OISC, pero lo haré más tarde.

p,m=0,gets.chomp.split.map(:to_i)
while p>0
p=(m[m[b]]-=m[m[a]])>0?p+3:c
end
$><<m[0]

El código es bastante directo. m es una "memoria" que contiene programas y datos. La primera línea inicializa m con el código proporcionado y p - puntero de memoria. El bucle principal es subleq operación subleq , escrito con un operador ternario. La última línea es una forma inteligente de generar el número contenido en la memoria.

Answer 6

No es mío, pero eche un vistazo al auto-intérprete de cálculo lambda binario de 210 bits here .

Answer 7

Programa de Python que interpreta un lenguaje que acabo de crear:

from random import randint
z = [randint(0,1), None] # example: input data is 0 or 1
x = ''_b_ed_a_i____d_ai'' # this program will set p = data[1] = not data[0]
# input x[i], data z[k]
# jumper j
# p is +1 or -1 each step
# commands:
# a set data = 0 or 1
# b j += 0 or +-9 depending on data
# d move data left or right
# e perform jump left or right
# j set jumper to 0
# i end program
# output: p or some data[x], both possible
g = globals()
p = i = 1
a = b = d = j = e = k = 0
while i:
h = x[i]
g[h] = p = -p
i += 1 + j*e
if a: z[k] = i % 2
if z[k]: j += 9*b
k += d
g[h] = 0
# print(a, b, d, e, i, j, k, h, z)
print(''Input:'', z, ''Output:'', p > 0)

Versión optimizada:

g=globals()
p=i=1
a=b=d=j=e=k=0
while i:
h=x[i]
g[h]=p=-p
i+=1+j*e
if a:z[k]=i%2
if z[k]:j+=9*b
k+=d
g[h]=0

114 bytes

Actualización: Quiero agregar que el objetivo de mi programa no es crear ningún lenguaje práctico, ni siquiera tener de alguna manera el mejor intérprete (= "el más corto"), sino demostrar trucos de programación interesantes. Por ejemplo, estoy confiando en el acceso directo a variables globals() través de globals() , por lo que nunca compruebo el comando j , ahorrando preciosos bytes :)

Answer 8

Python, 250 bytes.

Esta es más larga que la solución Python de ilya n., pero el lenguaje es un poco más fácil de entender. Cada comando en este idioma (lo llamo Kaputt , la palabra alemana para "roto") es un byte. Los siguientes 6 comandos están definidos:

• 0 : Empuja un cero en la pila
• 1 : Empuja uno en la pila
• I : (if) Pop un valor fuera de la pila (que debe ser cero o uno). Ejecute el siguiente bloque de código (hasta " i ") si es uno; salta el bloque si es un cero.
• i : (endif) Finaliza el bloque if y empuja uno si el bloque no se ejecutó (porque la " I " hizo saltar un cero). Vea abajo para una explicación de este último.
• D : (def) Coloca el nombre de la función que se va a definir fuera de la pila (ver a continuación) y vincula el siguiente bloque (hasta " d ") a ese nombre.
• d : (enddef) Finaliza la definición de la función.
• Cualquier otro byte: compruebe si hay una función en este nombre (un byte, pero vea la edición a continuación). Si es así, ejecuta esta función; si no, inserte este byte en la pila para uso inmediato por D

Los ifs anidados son legales; Las definiciones de funciones anidadas no lo son. El hecho de que i (endif) presione one si y solo si el bloque if correspondiente no se ejecutó permite la siguiente expresión que se asemeja a una estructura if / else / endif:

# [code that left a one or zero on the stack]
I # abbreviated "(" below
# [code to be run if it was a one]
0iI # abbreviated "/" below
# [code to be run if it was a zero]
1iIi # abbreviated ")" below
# [continuing...]

Tenga en cuenta que los comentarios, los saltos de línea, los espacios, etc., en realidad no están permitidos.

Aquí hay algunos ejemplos de funciones comunes. Estos hacen uso de las abreviaturas ( / ) mencionadas anteriormente.

<D(/)d

define la función < (pop) que saca un valor de la pila sin usarlo para nada.

&D((1/0)/<0)d

define la función & (y) que muestra dos valores de la pila y empuja a uno si ambos valores son unos, de lo contrario empuja a cero.

~D((11/10)/(01/00))d

define la función ~ (intercambio) que intercambia los dos valores superiores en la pila.

RD(R/<)d

define la función R (eliminar) que recursivamente elimina todos los de la pila y luego elimina dos valores más (el superior debe ser cero).

La siguiente función de intérprete espera que el programa p, que es una cadena (o cualquier otro iterable de bytes), y la pila de entrada S, que es una lista de bytes (posiblemente vacía). Una vez que el intérprete se ha ejecutado, esta lista contiene la pila de salida.

def i(p,S,F=0):
A=S.append
F=F or{}
C=0
k=[]
for c in p:
h=0in k
if c=="d":C=0
elif C!=0:C+=[c]
elif c=="I":k+=[int(h or S.pop())]
elif c=="i":k.pop()or A("1")
elif 1-h:
if c=="D":C=F[S.pop()]=[]
else:i(F.get(c)or A(c)or"",S,F)

Obviamente, no había espacio para la comprobación de errores, por lo que i() espera el código Kaputt legal. Casos de prueba:

script = "<D(/)d" # < = pop
script += "&D((1/0)/<0)d" # & = and
script += "~D((11/10)/(01/00))d" # ~ = swap
script += "RD(R/<)d" # R = remove
script += "|D(<1/(1/0))d" # | = or
script=script.replace("(","I")
script=script.replace("/","0iI")
script=script.replace(")","1iIi") # ( and / and ) are no real commands of the language.
S=[]
i(script+"1111010111111111R",S)
assert S == ["1","1","1","1","0"]
S=[]
i(script+"00&",S)
assert S == ["0"]
S=[]
i(script+"01~",S)
assert S == ["1","0"]
S=[]
i(script+"00|",S)
assert S == ["0"]
S=[]
i(script+"01|",S)
assert S == ["1"]

Feliz codificación :-)

Edición: No hay nada inherente en el intérprete que obligue a los tokens a ser de un solo byte. Exigir esto era más por coherencia con los comandos incorporados (que son de un byte porque eso hace que el intérprete sea más corto). Si pasa una lista de cadenas en lugar de una cadena, puede escribir un código Kaputt más legible como este:

script = """
inc D
(
(
0 0
/
1 0
)
/
1
)
d
""".replace("(","I").replace("/","0 i I").replace(")","1 i I i").split()

Esto define una función inc que incrementa el número de dos bits en la parte superior de la pila (LSB en la parte superior).

Prueba:

for n in xrange(4):
S=[]
i(script + [str((n & 2)/2), str(n & 1), "inc"], S)
assert S == [str(((n+1) & 2)/2), str((n+1) & 1)]

Llamemos a los nombres de funciones de múltiples bytes una extensión de idioma :-)

Answer 9

Sobre la base de mi entrada de código de golf anterior , aquí hay un emulador de OISC (ligeramente generalizado para IO) en

Fortran77

Obsfucado y sin el andamio de carga ( 655 caracteres ):

 subroutine o(n,m)
integer m(n)
l=1;
do while (l.ne.0)
i=m(l)
j=m(l+1)
k=m(l+2)
mi=mg(n,m,i)
mj=mg(n,m,j)
if(j.eq.(n+2)) then
write(6,*)mj-mi
else
m(l+1)=mj-mi
endif
if (m(l+1).lt.0) then
l=mg(n,m,k)
else
l=l+3
endif
end do
return
end
function mg(n,m,i)
integer m(n)
if (i.eq.n+2) then
read(5,*)mg
elseif (i.eq.n+1) then
mg=0
else
mg=m(i)
endif
return
end

con comentarios, cargando andamios, etc. (2435 caracteres):

 program c
parameter (n=1024) ! The size to use for memeory
integer m(n) ! represent the memory
c Load a program into memory
i=1
1 read(5,*,end=2)l
c write (6,*) "Load ",l," into location ",i
m(i)=l
i=i+1
goto 1
c Run the computer
2 call o(n,m)
stop
end
subroutine o(n,m)
c Simulate a simple computer that supports only a single
c instruction. Memory is a fixed size array of integers.
c
c The supported instruction is subtract-branch-negative which we
c give the assembly syntax
c
c sbn i j k
c
c and acts by subtracting the value in memeory location i from that
c in location j and storing the result in j. If the result is
c negative, the PC is set to k. Because there is only one opcode, it
c is not represented, so a program consists simply of a series of
c triplet (i,j,k), and the PC is generally incremented by 3. The
c program counter starts at 1
c
c Povisions for IO and halting are by way of special memory
c location:
c
c * PC=0 means halt
c * writes (opcode argument j) to memory location n+1 send
c output, reads from n+1 evaluate as 0
c * reads (opcode argument i, j, k) from memory location n+2 fetch
c input, writes to n+2 are forbidden
c * All others reads and writes outside of memeory are forbidden
c n ! the size of the computers memory
integer m(n) ! an array representing the computers memory
l=1; ! program counter
do while (l.ne.0)
i=m(l)
j=m(l+1)
k=m(l+2)
c write (6,*) "Executing from PC=",l,": (",i,", ",j,", ", k,")"
c handle the write special case for output
mi=mg(n,m,i)
mj=mg(n,m,j)
if(j.eq.(n+1)) then
write(6,*)mj-mi
else
c write (6,*) "Setting location ",j," to ",mj-mi
m(l+1)=mj-mi
endif
if (m(l+1).lt.0) then
l=mg(n,m,k)
else
l=l+3
endif
end do
return
end
c Handle the various read special cases
function mg(n,m,i)
integer m(n)
if (i.eq.n+2) then
read(5,*)mg
elseif (i.eq.n+1) then
mg=0
else
mg=m(i)
endif
c write (6,*) "Read ",mg," from location ",i
return
end

Programa de ejemplo:

13
1025
0
14
1025
0
14
15
0
0
0
0
-1
1
0

dando como resultado la salida:

$ cat trivial.oisc | ./a.out
1
-1

que es como se esperaba.

Realmente es un código extremadamente sencillo. El punto aquí no es realmente cuán estricto puedo codificarlo, sino cuán sencillo es el idioma que necesita para la integridad de Turing.

Answer 10

La solución de 106 bytes fue publicada en el concurso codegolf.com . Está escrito en perl e interpreta Brainfuck . No hay manera de revisarlo en este punto, afaik.

No es mi solución, pero creo que es más corta que las entradas actuales. La solución posible debería ser más corta, ya que no hay necesidad de utilizar Brainfuck como lenguaje completo de Turing.

Answer 11

#include "/dev/tty"