创建最短的图灵完全解释器 [英] Creating the shortest Turing-complete interpreter

问题描述

我刚刚尝试创建尽可能小的语言解释器。您想加入并尝试吗？

I've just tried to create the smallest possible language interpreter. Would you like to join and try?

游戏规则：

• 您应指定要解释的编程语言。如果是您发明的语言，则应在注释中附带命令列表。


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


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


• 您的代码应可按编写的方式运行。


• 您可以假定数据为0且1s（int，string或boolean，由您选择），输出为单个位。


• 对于在标准模型上编写的任何算法（例如图灵机，马尔可夫链或您选择的类似算法），该语言应具有图灵完备性。


• 将代码的长度定义为移除输入部分，输出部分后的代码长度。 ，调试语句和不必要的空格。


• 您不能使用使编译器为您执行代码的函数，例如 eval（）， exec（）或类似的语言。

• You should specify a programming language you're interpreting. If it's a language you invented, it should come with a list of commands in the comments.
• Your code should start with example program and data assigned to your code and data variables.
• Your code should end with output of your result. It's preferable that there are debug statements at every intermediate step.
• Your code should be runnable as written.
• You can assume that data are 0 and 1s (int, string or boolean, your choice) and output is a single bit.
• The language should be Turing-complete in the sense that for any algorithm written on a standard model, such as Turing machine, Markov chains, or similar of your choice, it's reasonably obvious (or explained) how to write a program that after being executred by your interpreter performs the algorithm.
• The length of the code is defined as the length of the code after removal of input part, output part, debug statements and non-necessary whitespaces. Please add the resulting code and its length to the post.
• You can't use functions that make compiler execute code for you, such as eval(), exec() or similar.

这是社区Wiki，这意味着问题和答案都不会从投票中获得声誉点。

This is a Community Wiki, meaning neither the question nor answers get the reputation points from votes. But vote anyway!

推荐答案

Python，250字节。

Python, 250 bytes.

这一种语言比ilya n。的Python解决方案要长，但是该语言更易于掌握。该语言的每个命令（我称其为 Kaputt ，德语为破）是一个字节。定义了以下6条命令：

This one is longer than ilya n.'s Python solution, but the language is a little easier to grasp. Each command in this language (I call it Kaputt, the German word for "broken") is one byte. The following 6 commands are defined:

• 0 ：将零压入堆栈


• 1 ：将一个推入堆栈


• I ：（如果）从堆栈中弹出一个值（必须为零或一）。运行以下代码块（直到 i ）；


• i ：（endif）结束if块，如果块 not 运行（因为 I 弹出零）。


• D ：（def）关闭待定义函数的名称。堆栈（请参见下文）并将以下块（直到 d ）绑定到该名称。


• d ：（enddef）结束函数定义。


• 其他字节：检查是否有此函数（一个字节；但是请参见编辑下面）的名称。如果是这样，请运行此功能。如果没有，则将该字节压入堆栈以供 D 立即使用。

• 0: Push a zero onto the stack
• 1: Push a one onto the stack
• I: (if) Pop a value off the stack (which must be zero or one). Run the following block of code (until "i") if it's a one; skip the block if it's a zero.
• i: (endif) Ends the if block and pushes a one if the block was not run (because the "I" popped a zero). See below for an explanation of the latter.
• D: (def) Pops the name of the to-be-defined function off the stack (see below) and binds the following block (until "d") to that name.
• d: (enddef) Ends the function definition.
• Any other byte: Check if there is a function by this (one-byte; but see the edit below) name. If so, run this function; if not, push this byte onto the stack for immediate use by D.

嵌套是否合法；嵌套函数定义不是。 i （endif）推入一个if并且仅当相应的if块未运行时才推入一个事实，这使得下面的惯用法类似于if / else / endif结构：

Nested ifs are legal; nested function definitions are not. The fact that i (endif) pushes a one if and only if the corresponding if block was not run allows for the following idiom resembling an if/else/endif structure:

# [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...]

请注意，注释，换行符，空格等

Note that comments, linebreaks, spaces etc. are not actually allowed.

以下是一些常用功能的示例。这些使用上面提到的缩写（/）。

Here are some examples of common functions. These make use of the abbreviations ( / ) mentioned above.

<D(/)d

定义函数< （pop）将从堆栈中弹出一个值，而不用它做任何事情。

defines the function < (pop) that pops a value off the stack without using it for anything.

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

定义函数& （和）会弹出堆栈的两个值，如果两个值都为1，则按1，否则按0。

defines the function & (and) that pops two values of the stack and pushes a one if both values are ones, pushes a zero otherwise.

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

定义函数〜（交换）可交换堆栈中的前两个值。

defines the function ~ (swap) that swaps the top two values on the stack.

RD(R/<)d

定义函数 R （删除），该操作以递归方式从堆栈顶部删除所有这些值，然后再删除另外两个值（其中一个值应为零）。

defines the function R (remove) that recursively removes all ones from the top of the stack, and then removes two more values (the top one of which should be zero).

以下解释器函数需要程序p，它是一个字符串（或一个y个其他可迭代字节）和输入堆栈S（它是字节列表（可能为空））。解释器运行后，此列表包含输出堆栈。

The following interpreter function expects the program p, which is a string (or any other iterable of bytes), and the input stack S, which is a (possibly empty) list of bytes. After the interpreter has run, this list contains the output stack.

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 代码。测试案例：

Obviously, there was no room for error checking, so i() expects legal Kaputt code. Test cases:

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 代码，如下所示：

There is nothing inherent in the interpreter that forces tokens to be one byte only. Requiring this was more for consistency with the built-in commands (which are one-byte because that makes the interpreter shorter). If you pass a list of strings instead of a string, you can write more readable Kaputt code like this:

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

此函数定义了 inc 会递增堆栈顶部的两位数（LSB位于顶部）。

This defines a function inc that increments the two-bit number on top of the stack (LSB on top).

测试：

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

让我们调用多字节函数命名语言扩展为:-)

Let's call multi-byte function names a language extension :-)

这篇关于创建最短的图灵完全解释器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！