computer-science - 创建最短的图灵完备解释器

Question

关闭。这个问题需要更多 focused .它目前不接受答案。




7年前关闭。










锁定。这个问题及其答案是locked因为这个问题是题外话，但具有历史意义。它目前不接受新的答案或交互。








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

游戏规则:

您应该指定您正在解释的编程语言。如果它是您发明的一种语言，它应该在评论中附带一个命令列表。

您的代码应该从分配给您的代码和数据变量的示例程序和数据开始。

您的代码应以结果输出结束。最好在每个中间步骤都有调试语句。

您的代码应该可以按照编写的方式运行。

您可以假设数据是 0 和 1(整数、字符串或 bool 值，您可以选择)并且输出是单个位。

该语言应该是图灵完备的，因为对于在标准模型上编写的任何算法，例如图灵机、马尔可夫链或您选择的类似算法，如何编写执行后的程序是相当明显(或解释)的由您的解释器执行算法。

代码长度定义为去掉输入部分、输出部分、调试语句和不必要的空格后的代码长度。请将生成的代码及其长度添加到帖子中。

您不能使用使编译器为您执行代码的函数，例如 eval() , exec()或类似的。

这是一个社区 Wiki，这意味着问题和答案都不会从投票中获得声誉点数。但无论如何都要投票!

Answer 1

Python，250 字节。

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

0 : 将零压入堆栈

1 : 将一个压入堆栈

I :(如果)从堆栈中弹出一个值(必须为零或一)。运行以下代码块(直到“i”)，如果它是一个；如果它是零，则跳过该 block 。

i : (endif) 结束 if block ，如果 block 没有运行，则压入 1(因为“I”弹出一个零)。有关后者的解释，请参见下文。

D : (def) 将要定义的函数的名称从堆栈中弹出(见下文)并将后面的 block (直到“d”)绑定(bind)到该名称。

d : (enddef) 结束函数定义。

任何其他字节:检查此(一个字节；但请参阅下面的编辑)名称是否存在函数。如果是，运行这个函数；如果没有，则将此字节压入堆栈以供D 立即使用。 .

嵌套 if 是合法的；嵌套函数定义不是。 i 的事实(endif) 当且仅当相应的 if block 未运行允许以下类似于 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

定义函数 & (and) 弹出堆栈的两个值，如果两个值都是 1，则压入 1，否则压入 0。

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

快乐编码:-)

编辑:解释器中没有任何东西可以强制 token 仅是一个字节。要求这样做更多是为了与内置命令保持一致(这是一个字节，因为这会使解释器更短)。如果传递字符串列表而不是字符串，则可以编写更具可读性的 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)]

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