Calc 程序简介 nBrainfuck

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

Calc 程序简介 nBrainfuck

TI-Nspire 机上 Brainfuck 解释器！

本文由 MaxAlex 编写，所有文字均为原创。


Brainfuck
图片来自 Codingame

第一章 概述

Brainfuck，是一种由 Urban Müller 在1993年创造的极小化程序语言。该语言只包含八个简单的命令和一个指令指针。

虽然它是图灵完备的，但它的目的并非是为了实际使用，而是为了给程序员们制造挑战与娱乐。只需要把要完成的命令分解成微小的步骤，你就能用这门语言来编写程序。

这种语言基于一个简单的机器模型，除了指令，这个机器还包括：一个以字节为单位、被初始化为零的数组、一个指向该数组的指针（初始时指向数组的第一个字节）、以及用于输入输出的两个字节流。

下面是这八种状态的描述，其中每个状态由一个字符标识：

> 指针加一
< 指针减一
+ 指针指向的字节的值加一
- 指针指向的字节的值减一
. 输出指针指向的单元内容（ASCII码）
, 输入内容到指针指向的单元（ASCII码）
[ 如果指针指向的单元值为零，向后跳转到对应的 ] 指令的次一指令处
] 如果指针指向的单元值不为零，向前跳转到对应的 [ 指令的次一指令处

近日笔者了解到了一些奇奇怪怪的 Esolang，其中的 Brainfuck 语言通过模拟单带图灵机来工作。考虑到这门语言简洁有趣，笔者便产生了将其移植到 TI-Nspire 计算器平台上的想法。

第二章 已有的轮子

说干就干，笔者在 Github 上找到了一个 Brainfuck 的综合仓库，其中包含了一个用 Lua 语言写好的 Brianfuck 解释器。秉着“不重复造轮子”的思想（说到底还是条懒狗），笔者决定在这个现有的解释器的源码上进行修改，使其能够在 TI-Nspire 平台上正常运行。由于德州仪器官方向 TI-Nspire 用户直接提供了 TI-Lua，因此移植起来并不困难。

下面先贴出原版解释器的源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
--  Copyright (c) 2016 Francois Perrad

local f = arg[1] and assert(io.open(arg[1], 'r')) or io.stdin
local src = string.gsub(f:read'*a', '[^><+%-%.,%[%]]', '')
local len = string.len(src)
f:close()
io.stdout:setvbuf'no'

local stack = {}
local jump = {}
local code = {}
for pc = 1, len do
    local opcode = src:sub(pc, pc)
    code[pc] = opcode
    if opcode == '[' then
        stack[#stack+1] = pc
    elseif opcode == ']' then
        local target = stack[#stack]
        stack[#stack] = nil
        jump[target] = pc
        jump[pc] = target
    end
end
src = nil
stack = nil

local buffer = setmetatable({}, {
    __index = function ()
        return 0    -- default value
    end
})

local ptr = 1
local pc = 1
while pc <= len do
    local opcode = code[pc]
    if opcode == '>' then
        ptr = ptr + 1
    elseif opcode == '<' then
        ptr = ptr - 1
    elseif opcode == '+' then
        buffer[ptr] = buffer[ptr] + 1
    elseif opcode == '-' then
        buffer[ptr] = buffer[ptr] - 1
    elseif opcode == '.' then
        io.stdout:write(string.char(buffer[ptr]))
    elseif opcode == ',' then
        buffer[ptr] = string.byte(io.stdin:read(1) or '\0')
    elseif opcode == '[' then
        if buffer[ptr] == 0 then
            pc = jump[pc]
        end
    elseif opcode == ']' then
        if buffer[ptr] ~= 0 then
            pc = jump[pc]
        end
    end
    pc = pc + 1
end

我们不妨先来分析一下这段代码。TI-Lua 中并没有 Lua 的标准输入输出库（io），因此我们不对输入输出的有关行作过多说明。

1
2
3
local f = arg[1] and assert(io.open(arg[1], 'r')) or io.stdin
local src = string.gsub(f:read'*a', '[^><+%-%.,%[%]]', '')
local len = string.len(src)

我们先来看脚本的第一部分，这里一共声明了三个变量：
f 为代表 Brainfuck 源码的字符串；src 则是对 f 去除非 Brainfuck 操作符后的源码；len 代表源码长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
local stack = {}
local jump = {}
local code = {}
for pc = 1, len do
    local opcode = src:sub(pc, pc)
    code[pc] = opcode
    if opcode == '[' then
        stack[#stack+1] = pc
    elseif opcode == ']' then
        local target = stack[#stack]
        stack[#stack] = nil
        jump[target] = pc
        jump[pc] = target
    end
end
src = nil
stack = nil

在这一部分中，解释器将会对处理后的字符串 src 进行处理，分离出单个操作符并存储到 code 数组中。此外，解释器也记录了每个配套的 [ 和 ] 的跳转位置，便于接下来执行时进行跳转。stack 是为了处理嵌套的 [ 和 ] 而设置的变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
local buffer = setmetatable({}, {
    __index = function ()
        return 0    -- default value
    end
})

local ptr = 1
local pc = 1
while pc <= len do
    local opcode = code[pc]
    if opcode == '>' then
        ptr = ptr + 1
    elseif opcode == '<' then
        ptr = ptr - 1
    elseif opcode == '+' then
        buffer[ptr] = buffer[ptr] + 1
    elseif opcode == '-' then
        buffer[ptr] = buffer[ptr] - 1
    elseif opcode == '.' then
        io.stdout:write(string.char(buffer[ptr]))
    elseif opcode == ',' then
        buffer[ptr] = string.byte(io.stdin:read(1) or '\0')
    elseif opcode == '[' then
        if buffer[ptr] == 0 then
            pc = jump[pc]
        end
    elseif opcode == ']' then
        if buffer[ptr] ~= 0 then
            pc = jump[pc]
        end
    end
    pc = pc + 1
end

这一部分是解释器的最后一部分，也是最为核心的一部分。我们首先声明了一个名为 buffer 的表，并通过元表将其初始化为0（可以理解为把表全部填充为0），这便是图灵机中的那条无限长的纸带，而纸带上存储的就是数据；ptr 为纸带的读写头，它存储了当前读写头所处的位置；pc 则是存储 code 数组中当前所执行到的位置，便于在遇到 [ 和 ] 时进行跳转。在 while 循环中，我们逐个读取 code 数组中的各个操作符，并用 if..elseif 结构来处理它们。

第三章 正式实践

上面的这段代码并不能直接复制后在 TI-Nspire 平台运行，因此我们要对其进行一定的修改。为保证最大的兼容性，笔者决定采用 TI-Lua API 1.0 来编写 nBrainfuck。

我们先把原版解释器进行封装，放入 Brainfuck 函数中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
function brainfuck(input)
    local src = string.gsub(input, '[^><+%-%.,%[%]]', '')
    local len = string.len(src)
    
    if len == 0 then return -1 end -- 没有可执行的 Brianfuck 代码

    local stack = {}
    local jump = {}
    local code = {}
    for pc = 1, len do
        local opcode = src:sub(pc, pc)
        code[pc] = opcode
        if opcode == '[' then
            stack[#stack+1] = pc
        elseif opcode == ']' then
            local target = stack[#stack]
            stack[#stack] = nil
            jump[target] = pc
            jump[pc] = target
        end
    end
    src = nil
    stack = nil

    local buffer = setmetatable({}, {
        __index = function ()
            return 0
        end
    })

    local ptr = 1
    local pc = 1
    local bfOutput = ""
    while pc <= len do
        local opcode = code[pc]
        if opcode == '>' then
            ptr = ptr + 1
        elseif opcode == '<' then
            ptr = ptr - 1
        elseif opcode == '+' then
            buffer[ptr] = buffer[ptr] + 1
        elseif opcode == '-' then
            buffer[ptr] = buffer[ptr] - 1
        elseif opcode == '.' then
            local buf = string.char(buffer[ptr])
            bfOutput = bfOutput..buf
        elseif opcode == ',' then
            buffer[ptr] = coroutine.yield(1,bfOutput)
            bfOutput = ""
        elseif opcode == '[' then
            if buffer[ptr] == 0 then
                pc = jump[pc]
            end
        elseif opcode == ']' then
            if buffer[ptr] ~= 0 then
                pc = jump[pc]
            end
        end
        pc = pc + 1
    end
    return 0,bfOutput
end

在这里，我们声明了一个名为 bfOutput 的变量用于存储 Brainfuck 程序的输出（因为 TI-Lua 仅允许在 on.paint(gc) 中进行绘制）。在遇到 . 标识符时将输出的字符连接至 bfOutput，最后在程序结束后将其返回即可。, 标识符（即输入）的处理相对复杂，我们将在下文中谈到。

由于 TI-Lua 是一门事件驱动语言，所以我们还要引入处理事件的函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function on.activate()
    -- 执行剪贴板中的 Brainfuck 代码
    co = coroutine.create(function ()
       return brainfuck(clipboard.getText())
    end)
    status, res, output = coroutine.resume(co)
end

function on.deactivate()
    -- reset output
    status, res, output = nil
end

function on.paint(gc)
   if res == -1 then -- 打印错误信息
       gc:setColorRGB(183,28,28)
       gc:setFont("serif","i","9")
       gc:drawString(gc,"BF Error: This is not a valid Brainfuck program.",10,25)
   elseif (res == 0 or res == 1) and output ~= nil then -- 打印输出
       gc:setColorRGB(0,0,0)
       gc:setFont("sansserif","r","11")
       gc:drawString(output,10,25)
   end
end

function on.charIn(char)
    if coroutine.status(co)=="suspended" then -- 处理输入
        local st, rs, op = coroutine.resume(co,string.byte(char))
        status, res, output = st, rs, output..op
        platform.window:invalidate() --重绘屏幕
    end
end

其中，我们在 on.activate 函数中运行解释器，并将用户剪贴板中的内容传入刚刚封装的 Brainfuck 函数。不过，还是由于 TI-Lua 的事件驱动特性，我们转而使用了 Lua 中的协程来处理用户的输入。协程启动后，如果遇到 , 标识符则会挂起协程并返回已有的输出。接下来等待用户按下按键，调用 on.charIn 函数，并将用户的输入传入，重启协程。

第四章 完成

上面简要写出了笔者构建 nBrainfuck 时的思路，具体的程序可前往这里下载体验。