创建最短的图灵完整解释器

Question

我刚刚尝试创建最小的语言解释器.你想加入并尝试吗？

游戏规则:

• 您应该指定您正在解释的编程语言.如果它是您发明的语言,它应该在评论中附带一个命令列表.
• 您的代码应该从分配给代码和数据变量的示例程序和数据开始.
• 您的代码应以结果的输出结束.每个中间步骤最好有调试语句.
• 您的代码应该像编写的那样运行.
• 您可以假设数据为0和1(int,string或boolean,您的选择)和输出是一位.
• 对于在标准模型上编写的任何算法,例如图灵机,马尔可夫链或您选择的类似算法,语言应该是图灵完备的,如果编写一个程序后,如何编写一个程序是相当明显的(或解释)由您的口译员执行算法.
• 代码的长度定义为删除输入部分,输出部分,调试语句和非必要的空格后代码的长度.请将结果代码及其长度添加到帖子中.
• 您不能使用使编译器为您执行代码的函数,例如eval(),exec()或类似的函数.

这是一个社区维基,这意味着问题和答案都不会从投票中获得声誉点.但无论如何投票!

Answer 1

Python,250个字节.

这个比ilya n.的Python解决方案更长,但语言更容易掌握.这种语言中的每个命令(我称之为Kaputt,德语中的"broken")是一个字节.定义了以下6个命令:

• 0:将零推到堆栈上
• 1:将一个推入堆栈
• I:( if)从堆栈中弹出一个值(必须为零或一个).运行以下代码块(直到" i")如果它是一个; 如果它是零,则跳过该块.
• i:(endif)结束if块并在块未运行时推送一个(因为" I"弹出一个零).请参阅下文,了解后者的解释.
• D:(def)从堆栈中弹出要定义的函数的名称(见下文),并将以下块(直到" d")绑定到该名称.
• d:(enddef)结束函数定义.
• 任何其他字节:检查是否有一个函数(一个字节;但参见下面的编辑)名称.如果是,请运行此功能; 如果没有,将此字节推入堆栈以供立即使用D.

嵌套ifs是合法的; 嵌套函数定义不是.当i(并且仅当相应的if块未运行)时,(endif)推送一个这样的事实允许以下类似于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...]

请注意,实际上不允许使用注释,换行符,空格等.

以下是常见功能的一些示例.这些使用了上述缩写( / ).

<D(/)d

定义了一个函数<(pop),它从堆栈中弹出一个值而不用任何东西.

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

定义&弹出堆栈的两个值的函数(和),如果两个值都是1则推送一个,否则推零.

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

定义~交换堆栈顶部两个值的函数(swap).

RD(R/<)d

定义函数R(remove)以递归方式从堆栈顶部删除所有值,然后删除另外两个值(其中最顶层的值应为零).

以下解释器函数需要程序p,它是一个字符串(或任何其他可迭代的字节),以及输入堆栈S,它是一个(可能是空的)字节列表.解释器运行后,此列表包含输出堆栈.

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)

显然,没有错误检查的余地,因此i()需要合法的Kaputt代码.测试用例:

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"]

快乐的编码:-)

编辑:解释器中没有固有内容强制令牌仅为一个字节.要求这更多是为了与内置命令(一个字节,因为这使得解释器更短)保持一致.如果传递字符串列表而不是字符串,则可以编写更具可读性的Kaputt代码,如下所示:

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

这定义了一个函数inc,它增加堆栈顶部的两位数(顶部的LSB).

测试:

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)]

我们将多字节函数名称称为语言扩展名:-)

Answer 2

解释我刚刚创建的语言的Python程序:

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)

优化版本:

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个字节

更新:我想补充一点,我的程序的重点不是创建任何实用的语言,甚至不是以某种方式拥有"最好的"(=='最短')解释器,而是展示有趣的编程技巧.例如,我依靠直接访问全局变量globals(),所以我从来没有测试过j命令,节省了宝贵的字节:)

Answer 3

#include "/dev/tty"

Answer 4

使用A86组装下面的代码,得到一个150字节的BF解释器!

    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

在命令行上指定文件名,不需要双引号,作为BF源.

Answer 5

不是我的,但看看210 位二进制演算自我解释这里.