Forth 栈式语言

本章导读

Forth 诞生于 1970 年，最初用于天文台望远镜控制。它的核心哲学：一切皆词（word）——数字是词，运算符是词，控制结构是词，用户定义也是词。解释器的工作就是：分词→查字典→执行。没有类型系统，没有语法树，只有栈和字典。

51.1 逆波兰表达式

中缀表达式 (3 + 4) * 2 在 Forth 中写作 3 4 + 2 *：

// 中缀 → RPN 对照
// (3 + 4) * 2  →  3 4 + 2 *
// 10 - 2 * 3   →  10 2 3 * -
// (1 + 2) * (3 + 4)  →  1 2 + 3 4 + *

// RPN 求值过程（3 4 + 2 *）：
// 读入 3 → 栈: [3]
// 读入 4 → 栈: [3, 4]
// 读入 + → 弹出 4 和 3，压入 7 → 栈: [7]
// 读入 2 → 栈: [7, 2]
// 读入 * → 弹出 2 和 7，压入 14 → 栈: [14]
// 结果：14

RPN 的优势：不需要括号、不需要优先级规则、天然适合栈机执行。

51.2 数据栈操作

Forth 的核心是一个整数栈。基本栈操作词：

// 栈操作词
// DUP   : a → a a        （复制栈顶）
// DROP  : a →            （丢弃栈顶）
// SWAP  : a b → b a      （交换栈顶两个）
// OVER  : a b → a b a    （复制次栈顶）
// ROT   : a b c → b c a  （旋转三个）
// .     : a →            （弹出并打印）
// .S    : 栈不变          （打印整个栈，调试用）

// 示例：
// 5 DUP * .  →  输出 25（5 的平方）
// 1 2 3 ROT . . .  →  输出 1 3 2

在 xlang 中用 list 实现栈：

list<int> stack = list<int>()

func push(int val)
    stack.push(val)
end

func pop() as int
    assert stack.len() > 0, "栈下溢"
    return stack.pop()
end

51.3 内置词

内置词分为四类：

// 算术词
// +  : a b → a+b
// -  : a b → a-b
// *  : a b → a*b
// /  : a b → a/b
// MOD: a b → a%b
// NEGATE: a → -a

// 比较词（结果为 -1 真 / 0 假）
// =  : a b → flag
// <  : a b → flag
// >  : a b → flag

// 栈操作词
// DUP DROP SWAP OVER ROT

// I/O 词
// .   : 弹出栈顶并打印
// ."  : 打印后续字符串（到 " 为止）
// CR  : 换行
// EMIT: 弹出 ASCII 码并输出字符

51.4 用户定义词

Forth 最强大的特性——用户可以定义新词：

// 定义格式：: 词名 定义体 ;
// 例：定义平方词
// : SQUARE DUP * ;
// 5 SQUARE .  →  25

// 定义组合词
// : CUBE DUP DUP * * ;
// 3 CUBE .  →  27

// 定义带逻辑的词
// : ABS DUP 0 < IF NEGATE THEN ;
// -5 ABS .  →  5

实现原理：定义时把词体（token 列表）存入字典；执行时逐 token 递归解释。

// 字典：词名 → 词体（token 列表）
dict<string, list<string>> userWords = dict<string, list<string>>()

// 解析定义
func parseDefine(list<string> tokens, int pos) as int
    string name = tokens[pos]
    pos += 1
    list<string> body = list<string>()
    while pos < tokens.len() and tokens[pos] != ";"
        body.push(tokens[pos])
        pos += 1
    end
    userWords[name] = body
    return pos + 1   // 跳过 ";"
end

51.5 条件与循环

Forth 的控制结构也是词：

// 条件：flag IF ... THEN
// 栈顶非 0 则执行 IF 和 THEN 之间的词
// : ABS DUP 0 < IF NEGATE THEN ;

// 带 ELSE：flag IF ... ELSE ... THEN
// : MIN 2DUP < IF DROP ELSE NIP THEN ;

// 循环：limit start DO ... LOOP
// 从 start 到 limit-1 循环，I 获取当前索引
// : COUNTDOWN 0 DO I . LOOP ;
// 5 COUNTDOWN  →  0 1 2 3 4

实现 IF/THEN：找到匹配的 THEN 位置，条件为假则跳过：

func execIf(list<string> tokens, int pos) as int
    int flag = pop()
    // 找到匹配的 THEN（处理嵌套）
    int depth = 1
    int thenPos = pos
    while depth > 0
        if tokens[thenPos] == "IF" then depth += 1 end
        if tokens[thenPos] == "THEN" then depth -= 1 end
        thenPos += 1
    end
    if flag == 0 then
        return thenPos   // 条件假，跳到 THEN 之后
    end
    return pos           // 条件真，继续执行
end

51.6 字典与词查找

解释器的核心是字典查找——每个 token 先查内置词，再查用户词，最后当数字处理：

func execute(string token)
    // 1. 尝试作为数字
    int num = 0
    bool isNum = int.tryParse(token, num)
    if isNum then
        push(num)
        return
    end

    // 2. 查内置词
    if execBuiltin(token) then return end

    // 3. 查用户定义词
    if userWords.has(token) then
        list<string> body = userWords[token]
        int i = 0
        while i < body.len()
            // 递归执行词体（处理控制结构需要返回新位置）
            i = execToken(body, i)
        end
        return
    end

    // 4. 未知词
    println("未知词: " + token)
end

51.7 完整实现

// forth.xl — 迷你 Forth 解释器

list<int> stack = list<int>()
dict<string, list<string>> userWords = dict<string, list<string>>()

func push(int v)
    stack.push(v)
end

func pop() as int
    assert stack.len() > 0, "stack underflow"
    return stack.pop()
end

func execBuiltin(string w) as bool
    if w == "+" then push(pop() + pop()); return true end
    // 注意：Forth 的 - 是 a b → a-b，弹出顺序是 b 先出
    if w == "-" then int b = pop(); push(pop() - b); return true end
    if w == "*" then push(pop() * pop()); return true end
    if w == "/" then int b = pop(); push(pop() / b); return true end
    if w == "MOD" then int b = pop(); push(pop() % b); return true end
    if w == "DUP" then int a = pop(); push(a); push(a); return true end
    if w == "DROP" then pop(); return true end
    if w == "SWAP" then int b = pop(); int a = pop(); push(b); push(a); return true end
    if w == "OVER" then int b = pop(); int a = pop(); push(a); push(b); push(a); return true end
    if w == "." then println(pop().toString()); return true end
    if w == "=" then int b = pop(); int a = pop(); if a == b then push(-1) else push(0) end; return true end
    if w == "<" then int b = pop(); int a = pop(); if a < b then push(-1) else push(0) end; return true end
    if w == ">" then int b = pop(); int a = pop(); if a > b then push(-1) else push(0) end; return true end
    if w == "NEGATE" then push(-pop()); return true end
    if w == "CR" then println(""); return true end
    return false
end

func run(string source)
    list<string> tokens = string.split(source, " ")
    int i = 0
    while i < tokens.len()
        string tok = tokens[i]
        if tok == ":" then
            // 用户定义
            string name = tokens[i + 1]
            list<string> body = list<string>()
            i += 2
            while i < tokens.len() and tokens[i] != ";"
                body.push(tokens[i])
                i += 1
            end
            userWords[name] = body
        elif tok == "" then
            // 跳过空 token
        else
            executeToken(tok)
        end
        i += 1
    end
end

func executeToken(string tok)
    int num = 0
    if int.tryParse(tok, num) then
        push(num)
        return
    end
    if execBuiltin(tok) then return end
    if userWords.has(tok) then
        list<string> body = userWords[tok]
        int j = 0
        while j < body.len()
            executeToken(body[j])
            j += 1
        end
        return
    end
    println("未知词: " + tok)
end

// 测试
run("3 4 + .")              // 7
run(": SQUARE DUP * ;")
run("5 SQUARE .")           // 25
run(": CUBE DUP DUP * * ;")
run("3 CUBE .")             // 27

51.8 REPL 交互

把解释器包装为交互式 REPL：

// REPL 模式
println("Mini Forth REPL（输入 QUIT 退出）")
while true
    print("ok> ")
    string line = io.readLine()
    if line == "QUIT" then break end
    if line == ".S" then
        // 打印栈内容
        print("栈: ")
        int i = 0
        while i < stack.len()
            print(stack[i].toString() + " ")
            i += 1
        end
        println("")
    else
        run(line)
    end
end

51.9 测试用例

// 算术
run("2 3 + .")          // 5
run("10 3 - .")         // 7
run("4 5 * .")          // 20
run("15 4 / .")         // 3
run("17 5 MOD .")       // 2

// 栈操作
run("5 DUP + .")        // 10
run("1 2 SWAP - .")     // 1 (2-1)

// 用户定义
run(": DOUBLE 2 * ;")
run("21 DOUBLE .")      // 42

// 嵌套定义
run(": QUAD DOUBLE DOUBLE ;")
run("3 QUAD .")         // 12

// 比较
run("3 4 < .")          // -1 (真)
run("5 2 > .")          // -1 (真)

51.10 扩展方向

• IF/ELSE/THEN：完整的条件分支
• DO/LOOP：计数循环，I 获取索引
• 变量：VARIABLE 定义，@ 读取，! 写入
• 字符串：." 打印字符串，S" 压入字符串
• 递归：RECURSE 词调用当前正在定义的词
• 编译模式：将词体编译为字节码，用虚拟机执行（性能提升 10x）

深入细节

⚠️ 常见错误

本章小结

复习题

1. 将中缀表达式 (5 + 3) * (7 - 2) 转换为 RPN。
2. Forth 中 10 3 - 的结果是什么？为什么不是 -7？
3. DUP 和 OVER 的栈效果有什么不同？
4. : SQUARE DUP * ; 定义后，5 SQUARE 的执行过程是什么？
5. 用户定义词存储在什么数据结构中？执行时如何查找？
6. 如果重新定义一个已存在的词，之前引用它的词会怎样？
7. Forth 的 IF/THEN 中，"真"和"假"分别用什么值表示？
8. 为什么 Forth 不需要括号和运算符优先级？

编程练习