【笔记】从零开始手搓编程语言（三）

2025-11-27

字数统计: 4k字 | 阅读时长≈ 15分

来自瑞典Linköping University的Filip Strömbäck老师来我们组访问，进行的一个名为Bootstrapping a Programming Language from Nothing的Seminar。本文的内容为基于此材料的个人理解。

经过前两周的奋战，我们终于摆脱了手写二进制、手动数字节的地狱。使用上次开发的工具我们已经可以像编写汇编代码一样比较舒适地开发了（尽管我们还要操心一下ELF文件头的填写和机器码的翻译，不过和之前相比已经好很多了）。下一步我们可以选择做一个真的汇编器，不过这同样困难且枯燥，而且对我们的开发体验提升不大。我是说，如果我们能现在就实现一个语义更高级的语言，我们为什么还需要汇编呢？不过，这真的能做到吗？

Week 3: Core Forth

能的！不过在此之前我们需要谨慎设计我们要实现的语言，毕竟我们在前两周已经体验过手搓机器码的痛苦了：

它的Core必须足够小，小到至少我们手写机器代码的时候代码复杂规模可以接受、不会太痛苦
它的模型最好和我们使用的x86汇编接近，我们能比较轻松地把里面的概念翻译成在我们现有的线性地址下对应的数据结构和机器码
它最好保留和底下的实现细节（地址空间、代码）等的联系、保留内嵌机器码的能力，这样我们可以利用已经实现的功能去一点点替换，让需要写的机器码越来越少
它的实现最好足够模块化，我们现在的调试手段还很原始，模块化的设计可以尽可能减轻每一次的调试负担
它最好有很强的元编程能力，使得我们可以从一个很小的内核演化出更强的抽象、表达能力
……

存在这样的语言吗？Filip老师告诉我有的，一个叫Forth的语言完美地满足了所有的要求，看来它是我们bootstraping最理想的帮手了。好吧，其实我也没学过这个语言，所以首先要学习一下它是怎么做到满足这么多要求的。

Forth速通

栈

Forth的模型是个很简单的栈机，我们首先有一个32位整数的栈，一开始什么都没有。我们在代码中每写一个整数就能push它进栈，整数之间用空格分开。例如：

1 2 3

执行之后栈的状态是这样的（我们用括号表示栈，栈顶在右侧，括号其实是Forth中的注释）：

( 1 2 3 )

相当于是顺序地执行了push 1; push 2; push 3，这样。

用一些在数字之外的ascii字符串可以表示一些命令，在Forth中称为word。先从最简单的操作栈的word开始。

首先，dup可以复制栈顶一份。例如：

1 2 dup

我们会得到：

( 1 2 2 )

类似的，drop则会移除栈顶：

1 2	1 2 3 drop ( 1 2 )

swap会交换栈顶两个数的顺序：

1 2	1 2 3 swap ( 1 3 2 )

Word

其实，在Forth中我们只有word这一种构造。Forth程序就是用空格分开的数字和word序列，遇到数字就push进栈、一个个依次执行。不过慢慢我们会发现，它真的很强大！

例如算数运算+是一个word，它移除栈顶两个数，push进它们的和（是的你发现了，写法和逆波兰式一模一样呢）：

1 2	1 2 + ( 3 )

如果我们把+看做一个函数的话，栈顶的两个数就是它的参数，而返回值则也是push回栈上。我们可以想函数签名一样，用记录输入和输出栈的方式来描述一个word的行为，例如+的“签名”就是：

1	( a b -- a+b )

--左边是执行前的栈状态，右边则是执行后。当然为了简洁我们只写相关的最顶部的两个数。

当然我们是可以定义一个新word的：

: add-two
  2 +
;
1 add-two
( 3 )

以:开始后面跟的是新定义的word的名字，然后跟着它的实现。我们就实现了一个简单的+2函数。

这不是我们柯里化的梗吗（

我们发现这个add-two的功能和把它替换成它的body的2 +的结果是完全一样的。是的，定义一个word的语义仅仅是把它的定义展开即可，就像宏一样。

这不是我们引用透明的梗吗（

代码即数据

我们设计Forth的解释器是一个个word被输入、处理的，word的所有参数通过栈来传递，这使得编译一段Forth代码变得很简单，例如我们想实现上面add-two代码的编译过程：

数字2：push对应的数字入栈。
+: 查表、call对应的子程序即可

需要注意的是，不论是代码还是数据，都是从同一个输入流中读入的，这意味着代码即是数据。随后我们会发现，这意味着前面执行的word可以以后面的word为数据，从而达到改变后续代码语义的效果！

元编程

注释一般认为是在编程语言语义之外的东西。然而在Forth中，一切皆word，包括注释！我们用括号来表示注释，其实(也是普通的word。那么它们是怎么实现的呢？

1
2
3

: ( 
  read-until-(
;

其中read-until-(是一个一直消耗输入直到遇到)的word。大概思路是(会一直读（消耗）输入直到读到)，这样等它结束时，当中的所有内容都被忽略了。看起来不错。

不过有个小问题，就是在定义word的时候，我们也希望能用注释：

1	: add-two ( a -- a+2 ) 2 + ;

这就有问题了：我们观察这个word的编译过程会发现，在遇到(这个word时，如果我们直接生成它的代码（一句call XXX），然后会继续编译下一个叫a的word……这并不是我们想要的行为。

引起这个问题的原因是，我们其实想(这个word在编译时 运行，而不是直接编译成代码在运行时 运行。为了解决这个问题，Forth提供称为immediate（立即）的机制，我们可以在定义word的时候声明它为立即的，这样的word将在编译时运行：

1
2
3

: ( 
  read-until-(
; immediate

这样，哪怕(出现在定义中（编译代码的地方），它也会被直接执行，而不是生成对应的代码。

我们很快会发现这是个很强的特性：这意味着我们可以在编译时执行任意代码！例如，我们可以实现操作控制流的wordreturn：

1
2
3

: return
  0xC3 emit-byte
;

其中emit-byte是在生成代码的指针处输出一个字节的数据，于是，当编译到这里的时候，return会在编译的机器码处插入一个0xC3，也就是ret指令。虽然有点耍赖，但是这确实可以实现我们的需求。

同样的，还可以实现更复杂但使用的分支结构if、else、fi：if读栈顶的数，不为零则执行后面的word且跳过else到fi，为零则执行else后面的。不过，这些具体的实现会在下一篇再介绍。

最后，定义word的:其实也可以作为一个word来定义，只需要配合;作为一个结束的信号即可。;要在编译时工作，因此是个immediate，这也是为什么要设计一个和开始定义不一样的符号。;做的事情很简单：插入一个ret指令，并告诉:结束编译即可。嗯，好像有点问题，:要怎么知道编译结束的呢？

简单的接口

在第一个(的例子中，它是编译、运行都运行的“两栖”word，而;则不太一样：一方面，;这个word只在编译时工作（用来结束编译），在运行时我们不希望它工作，这意味着;需要知道自己在运行时还是编译时；另一方面，;需要告诉解释器编译已经完成这个消息。

我们似乎需要一个解释器与immediateword之间的接口来完成这个需求。

Value	Input	Output
0	此immediate word处于运行时	正常继续
1	此immediate word处于编译时	正常继续
2	此immediate word处于编译时，最后的指令是call	正常继续，最后的指令是call
3	不会发生	停止编译，保留这个word
4	不会发生	停止编译，不保留这个word

其中，Input是由解释器（运行时）或:（编译时）提供给每个immediate word的来表明身份，而Output是immediate word返回给对应环境的。对于解释器，直接忽略这个输出即可，而:则可以根据这个结果判断是继续编译还是停止。

2这个值代表的比较特殊，它可以帮我们更简单地完成尾递归消除优化。

实现

看起来不错，那该如何实现这样一个语言的解释器呢？

首先，我们需要一个栈
我们应该有一个所有word的表，开始运行的时候内容是所有的built-in的word，因为在代码中也可以定义word，所以这个表应该要可以追加项目
我们要实现这些built-in的word
最后，我们需要一个REPL（read-evaluate-print-loop）循环，它每次读一个字符串，然后执行对应的操作
- 读到数字，就把它push到栈上
- 不是数字的话就是word，查找并执行对应的word
- 如果没找到的话，就输出错误
然后进行下一次循环

差不多了。不过，毕竟我们还是要从机器码写起，现在我们一个个来看这些部分如何实现：

栈

首先，我们要留一个内存空间给栈，例如从0x300000到0x400000，应该够用了。我们把它单独分一个段，这样在栈溢出或者写错地址的时候会直接段错误而不是带着bug跑，这对于debug很有用。我们和x86栈的惯例一样，从高地址到低地址使用。最后，我们还需要留一个寄存器专门做栈顶指针，为了不和x86栈的esp打架，我们用edi。

Word表

我们需要一个数据结构存放所有的word，需要包括的是：

word的名字
word对应的代码
是不是immediate
最后，这是个链表，所以我们还需要一个指向上一个条目的指针

每个word都被编译/实现成一个合法的函数，这样我们之间用call就可以执行对应的word了。我们的内存布局如下：

00         ; 1字节：0-普通word 1-immediate word
"dup"      ; word名，一个以'\0'为结尾的字符串
XXXXXXXX   ; 4字节：指向上一条目 第一条指令处 的指针，第一个word这个地址为0
8B 07 ...  ; 从这里开始是这个word的代码

这个精心设计的布局有很多好处：

首先，我们默认指向每个word条目对应的第一条指令的地址，这样在我们的解释器执行word时，只需要按照链表找到对应的word，call过去就可以了。
word的指针-4就可以拿到上一个word的地址，我们可以这样遍历这个链表。
表示这个word的immediate信息的字节在最前面，是为了做word名字符串另一个方向的终结符（因为0和1都不是合法的字符），word的名字是不定长的，这样我们就可以从后面开始一路找到字符串的开头了。

因为我们要直接call这个数据结构，所以我们需要把这个段设置成可执行的。不过一个更方便的办法是直接把它放在我们的主程序代码段的后面，因为这个表只会往高地址一个方向生长，所以这样就足够了。我们把built-in的word就这样一个个手写进这个链表，而我们的代码段时可读写的，所以运行时定义的word也可以往后接着追加。这样，我们代码段的结构大概长这样：

...
E8 -repl  ;; call repl

;; call exit
C7 C0 00000001  ;; mov eax, 1       ; syscall: exit
C7 C3 00000000  ;; mov ebx, 0       ; status: 0
CD 80           ;; int 0x80         ; make syscall

;; 主程序结束了，下面的空间是word表
;; 这是第一个word
00 "dup" 00
00000000 ;; pointer to previous word
:dup
8B 07           ;; mov eax, [edi]  ; get the top of stack
...

为了追加条目，我们还需要两个全局变量：FREE指向这个表第一个空的（可以写入的）字节，HEAD指向当前最后一个word。

Built-in Word

下一个重要的问题是：我们到底需要提供多少内置的word？你发现了，其实如果我们有一个emit-byte可以在FREE的地方写一个字节然后更新FREE，一个可以更改HEAD的word，我们似乎就已经可以用这个语言手写机器码手动注册这个word表来定义任何的word了。

是的，这个语言的core可以很小很小，然后我们可以用手写这个很小的语言的解释器，然后接下来就用这个语言自己写自己了！唯一的问题是，这样在“这个语言里手写机器码”来完成剩下的启动流程，还不如直接在源码里面写呢……

这个故事告诉我们，或许最小化core未必是个好主意，我们需要做一些权衡：我们要选择一些最重要的word内置在解释器里，它们实现简单，但可以简化我们下一步的启动流程——我们最好按照重要性排序，实现那些最重要的word，把那些没那么重要的放在这个语言里自己进一步实现（作为标准库）。

以下是我在这一阶段实现的word：

Stack Manipulation

dup: ( n -- n n )
drop: ( n -- )
swap: ( n1 n2 -- n2 n1 )

Memory Access

@: ( addr -- value ) read address
!: ( addr value -- ) write address
@b: ( addr -- byte ) read byte
!b: ( addr byte -- ) write byte

Input/Output

get-char: ( -- char ) read a char from input stream
put-char: ( char -- ) write a char to output stream
put-string: ( string -- ) write a string to output stream

String Manipulation

read: ( -- string ) read a line from input stream into the string buffer
string==: ( string1 string2 -- flag ) compare two strings, return 1 if equal, 0 if not equal
parse-number: ( string -- number ok ) parse a number from string, support decimal and hexadecimal (prefix 0x). Return the number and ok=1 if successful, ok=0 if not a number.
parse-digit: ( char -- digit ) parse a digit, return -1 if not a digit
string-copy: ( src dest -- len ) copy a string from src to dest, return its length, null terminator included.

Interpreter Functionality

find-word: ( string -- wordptr immediate ) find a word by its name, return the pointer to the word and immediate flag, if not found, return 0 0.
word-name: ( wordptr -- string ) get the name of a word
execute: ( wordptr -- ) execute a word by its pointer
read-eval-print: ( -- ) the REPL loop, return when EOF

Code Generation

:: ( -- ) start a new word definition
;: ( -- ) end a word definition
immediate: ( -- ) make the current word immediate
emit-byte: ( byte -- ) emit a byte to free text space
emit-word: ( word -- ) emit a 4-byte word to free text space
emit-offset: ( offset -- ) emit a 4-byte offset to free text space
emit-string: ( string -- ) emit a string to free text space

Information

head@: ( -- addr ) get the lastes defined word address
free@: ( -- addr ) get the free text space pointer
old-esp@: ( -- addr ) get the original esp
fd-in@: ( -- fd ) get the input file descriptor
fd-out@: ( -- fd ) get the output file descriptor
stack-min@: ( -- addr ) get the minimum address of the forth stack
stack-size: ( -- size ) get the size of the forth stack
stack-curr@: ( -- addr ) get the current top address of the forth stack

还挺多的。其中repl也被实现成了一个word。

流程

经过前面的努力，我们已经得到了一个比较好用的写机器码的工具，所以没有邪道了。把这些都实现之后，我们就得到了一个可以用的forth解释器。接下来我们就可以用它在forth中完成剩下的部分了。

本文作者： Frankenstein
本文链接： https://salty-frankenstein.github.io/blog/2025/11/27/【笔记】从零开始手搓编程语言（三）/
版权声明： 本博客文章采用 CC BY-SA 4.0 协议进行许可。转载请注明作者与原文链接。