StoneKnifeForth（带有元圆编译器）

这就是StoneKnifeForth，这是一种受Forth启发的非常简单的语言。预计它不会有用；相反，其目的是显示编译器的简单程度。删除注释时，编译器在两页代码下有点不足。

该软件包包括一个用“ StoneKnifeForth”编写的“元圆环编译器”，并将StoneKnifeForth编译为x86 Linux ELFexecutable。

还有一个用Python编写的StoneKnifeForth解释器（已通过Python 2.4测试）。它似乎比编译器发出的代码慢100倍。

使用通过编译器编译的编译器，编译从其中“删除”了注释和多余空格的编译器版本大约需要0.02秒。

因此，这是一种编程语言实现，可以每24fps电影帧从源代码重新编译一次。整个“修剪后的”源代码均为1902字节，不到我所知的最新类似项目otccelf（即4748字节）的一半。

正如用Python编写的解释器所演示的那样，编程语言本身实质上是与机器无关的，很少有x86怪癖：

（如果源语言是x86机器代码，那么做一个小的“编译器”将很容易。）

输出的可执行文件是4063字节，包含大约1400条指令。 valgrind报告说，它需要1,813,395条指令进行编译。 （因此，您会认为它可以在2.6 ms内自行编译。长时间运行是由于一次读取其输入字节的结果。）

艾伦·凯（Alan Kay）在《 Lisp 1.5程序员手册》中经常表达对亚圆Lisp解释器的热情。例如，在http://acmqueue.com/modules.php?name=Content&pa=showpage&pid=273&page=4中，他写道：

是的，那是我读研究生时给我的最大启示-当我最终理解Lisp 1.5手册第13页底部的一半代码是Lisp本身时。这些就是“麦克斯韦的软件方程式！”这是整个编程世界，我可以进行几行切换。我意识到，只要我想知道自己在做什么，就可以将这个东西的内核写下一半，而不会丢失任何东西力量。实际上，它将比大多数系统通过其他方式可能完成的重新进入更加容易，从而获得动力。

但是，如果您试图通过将元循环解释器翻译成低级语言来实现它，那么就会遇到问题。元循环解释器对大量的事情产生了重要的影响，而事实证明，这些事情对实现而言并非无关紧要-实际上，大约一半的代码专用于元循环解释器范围之外的事情。这是Lisp 1.5元圆解释器忽略的一些问题，有些语义上的问题，而仅仅是一些实现方面的问题：

在约翰·雷诺兹（John C. Reynolds）的论文“ Revisited InterpretersRevisited”，高阶和符号计算，第11卷，第355–361页（1998年）中，他说：

在第5节结束之前的第四段和第三段中，我应该强调一个事实，即元圆解释器并不是真正的定义，因为当理解定义语言时，它是微不足道的，否则它是模棱两可的。特别是，口译员I和II对应用程序顺序一无所知，而口译员I和III对高阶功能一无所知。吉姆·莫里斯（Jim Morris）更加坚决地说：

就自身而言，定义要素的活动令人高度怀疑，尤其是当它们与功能对象一样微妙时。我认为，这是一种时尚，应予以揭穿。 [自定义的]解释程序的区域意义。 。 。它显示了一个简单的通用语言查询功能。

另一方面，我清楚地记得约翰·麦卡锡（John McCarthy）对LISP [1DI]的定义，它是一种II风格的定义解释器，当我第一次学习该语言时，它就提供了很大的帮助。但是，这并不是我的理解的唯一支持。

（就其价值而言，自定义解释器不一定是图灵完备的；甚至可以为非图灵完备的语言编写非图灵完备的元圆解释器，例如David Turner的Total FunctionalProgramming系统）

元循环编译器迫使您面对这种额外的复杂性。此外，元循环编译器以一种解释器没有的方式实现自我维持。一旦运行了编译器，就可以随意向其支持的语言中添加功能，然后利用编译器中的这些功能。

因此，这是一个“石刀”编程工具：几乎一无所获。

当我写Ur-Scheme时，我的想法是看我是否可以找出如何逐步开发编译器的方法，首先是在不到一天的时间内构建一个小型的元圆编译器，然后从中添加功能。我几乎失败了；我花了两个半星期的时间才能成功地进行自我编译。

问题的一部分是，R5RS计划的最小子集足以在其中编写编译器，而不会因使用低级语言编写而使编译器更大，而仍然是比较大的语言。 Ur-Scheme并没有太多算术功能，但它确实具有整数，动态类型，闭包，字符，字符串，列表，递归，布尔值，可变参数函数，让我们介绍局部变量，字符和字符串文字，一种粗略的宏系统，五种不同的条件形式（if，cond，case和or），引号，尾调用优化，函数参数计数验证，边界检查，符号，缓冲输入（以使其无需花费几秒钟的时间自行编译）以及用于处理的函数库列表，字符串和字符。并添加了所有这些内容，因为必须使编译器能够自行编译。最终结果是编译器的源代码为90 KB，如果不加注释，则大约为1600行。

现在，也许您一天可以编写1600行工作方案，但是我确信这是不可能的。编译器来看，它仍然不是一个很大的编译器，但是它比otccelf大得多。因此，我假设也许是一种更简单的语言，而不要求与其他任何东西兼容，这将使我能够更轻松地引导编译器。

于是StoneKnifeForth诞生了。它受到了Forth的启发，因此继承了大部分Forth的传统简化形式：

出人意料的是，尽管它确实具有汇编程序的风格，但所产生的语言仍然几乎可以用其编写编译器。

不幸的是，我仍然无法在一天内完成它。从我第一次在笔记本中开始对其进行刻划直到它能够成功编译它已经有15天了，尽管git仅显示出在那六天中发生了积极的发展（包括我朋友亚里斯多德的一些帮助）。这是一种改进，但并不是我想要的那样多的改进。到那时，它只有13k的源代码和114条非注释行，绝对比Ur-Scheme的90k和1600行小很多。 （虽然还有另外181行Python用于引导程序解释器。）

可以想象一天编写和调试114行代码，甚至300行。认为我可以在一天内做到这一点仍然有些乐观，因此也许我需要找到一种进一步增加增量的方法。

我的理论是，一旦有了一个可以运行的编译器，就可以逐步向语言中添加功能并在进行测试时对其进行测试。到目前为止，Ihaven尚未涉及到这一部分。

为了找到最佳的成本/收益比，Wirth使用了一种高度直观的指标，该指标的起源对我来说还是未知的，但这很可能是Wirth自己的发明。他使用编译器的自编译速度来衡量编译器的质量。考虑到Wirth的编译器是用他们所编译的语言编写的，并且编译器本身就是实质性的，非平凡的软件，因此引入了高度实用的基准，直接使编译器的复杂性与性能发生了竞争。在自编译速度基准下，仅允许将这些优化合并到编译器中，以加快编译速度，以至于新代码添加的内在成本得到了充分补偿。

Wisth与Edsger Dijkstra和Chuck Moore一起显然是简化编程的伟大使徒之一。但是我非常怀疑，鉴于Oberon语言的复杂性，Oberon编译器能否以200万条指令进行编译。

R. Kent Dybvig使用了相同的标准。在谈到1985-1987年的Chez计划的发展时，他写道：

在某个时候，我们实际上制定了以下规则来保持编译开销：如果优化不能使编译器自身更快地弥补执行优化的费用，则该优化将被放弃。这排除了我们尝试的几种优化，包括早期尝试使用sourceoptimizer。

它可能有用的一种明显方式是，您可以阅读它并从中学到东西，然后将其用于实际有用的软件中。本节是关于牵强的方法。

如果您想对抗肯·汤普森（Ken Thompson）的“信任信任”（Trusting Trust）攻击，则希望以最小的编译器和最小的芯片开始； StoneKnifeForth可能是一个很好的方法。

有一些直接的更改可以进一步减少可执行文件的大小，但是它们会使编译器更加复杂，而不是更简单。一些引用最多的例程应该是开放代码的，这也应该加快速度，并使它们可用于使用同一编译器编译的其他程序。以下是一段时间前在十多个地方调用的例程：

11 0x169 xchg 13 0xc20亮22 0x190-（现在由+代替，仅在25个地方使用）25 0x15b pop 26 0x1bc = 35 0x13d dup 60 0x286。

其中，xchg，pop，-，=和dup都可以在呼叫站点以零成本或负成本进行开放编码，然后可以删除它们的定义和临时变量。

我尝试了对xchg，pop，dup和+进行开放编码。该可执行文件缩减了346字节（从4223字节减少到3877字节，减少了18％；在自身的“修剪”版本上，它也减少了42％的指令进行编译，从1,492,993减少到870,863），并且源代码几乎保持不变大小完全相同，共有119条非注释行；机器代码定义各占一行。他们看起来像这样：

dup＆＃39d = [pop 80。 ; ]（dup是`push％eax`）dup＆＃39; p = [pop 88。 ; ]（pop是`pop％eax`）dup＆＃39; x = [pop 135。 4。 36。 ; ]（xchg是xchg％eax，（％esp）dup＆＃39; + = [pop 3。4。36。89。;]（`add [％esp]，％eax; pop％ecx`）

但是，我决定不这样做。当前的编译器已经包含58个字节的机器代码，这将再增加9个字节。我认为高级Forth定义（：dup X！;等）更容易理解和验证的正确性。并且它们不依赖于底层细节，例如我们要编译的体系结构或我们如何表示堆栈。此外，它为引导过程增加了另一步。

Forth使用两个堆栈：一个用于过程嵌套（“返回堆栈”），另一个用于参数传递（“数据堆栈”或“操作数堆栈”）。这种安排由其他类似Forth的语言共享，例如PostScript和HP计算器程序。通常，在Forth中，与其他语言不同，用户可以直接访问“返回堆栈”。

现在，StoneKnifeForth主要将这两个堆栈存储在内存中，尽管它会将操作数堆栈的顶部保留在％eax中。寄存器％esp和％ebp指向堆栈内存的位置。当前正在使用的一个在％esp中，另一个在％ebp中。因此，每当在两个堆栈之间切换时，编译器必须发出xchg％esp，％ebp指令。因此，在编译自身时，发出的指令中有30％左右是xchg％esp，％ebp。

我认为，受colorForth的启发，我考虑仅将操作数堆栈指针保留在％edi中并从那里直接使用它，而不是将其交换到％esp中。 x86具有存储指令（GCC称为stosl），它将在％edi中将％eax中的32位值写入内存，并将％edi递增（或递减）4，这对于从％eax推入值（如点亮，为新值腾出空间）。但是，从堆栈中弹出值会变得有些毛茸茸。对应于stosl的lodsd或lodsl指令使用％esi而不是％edi，您必须设置“ DF”（方向标志），使其减量而不是递增，并且像stosl一样，它在更新索引寄存器之前而不是之后访问内存。

因此，尽管我们将消除输出中的大量冗余和丑陋的xchgin指令以及Restack，u，U和％flush函数，但编译器当前发出的一堆相对简单的指令序列将变得更加毛茸茸。变化大致如下：

！当前流行（％eax）；弹出％eax，它是三个字节；这会在输出中出现17次。新代码将是：sub $ 8，％edimov 4（％edi），％ecxmov％ecx，（％eax）mov（％edi），％eax这是十个字节。存储，！的字节版本与此类似。

-当前为％eax（％esp）；弹出％eax，它是四个字节;这在输出中发生23次。新代码将为7个字节：sub $ 4，％edisub％eax，（％edi）mov（％edi），％eax＆lt;＆lt; 39;类似的东西，虽然它只出现3次。

在JZ，jnz和Getchar中，会出现弹出％eax，它是一个字节（88）。新代码将为5个字节：$ 4，subedmov（％edi），％eax JZ在输出中发生38次，jnz发生5次，Getchar发生一次。

当时在输出代码中有193次推送％eax出现，每一次紧随其后的是立即移动到％eax中，这些都将变为stosd，这也是一个字节。

因此，此更改将使编译器源中的机器代码数量增加10-3 + 7-4 + 5-1 + 5-1 + 5-1 = 22字节，这是一个很大的数字，因为现在那里只有58个字节；我认为这会使编译器更难遵循，尽管Restack也不行。它还将使编译器输出的大小增加（10 -3）* 17 +（7-4）* 23 +（5-1）*（38 + 5 +1）= 364字节，尽管这将消除430 xchg％ esp，％ebp指令，每个两个字节，总共2 * 430-364 =少496个字节；结果程序将获得（4-2）* 17 +（3-2）* 23 +（2-1）*（38 + 5 +

我最初的想法是，以推挤为代价，对空间进行优化弹出是很愚蠢的。尽管它们在程序执行期间发生相同的次数，但通常传递给被调用方的数据要多于返回给调用方的数据，因此，推送站点的数量大于弹出站点的数量。 （在该程序中，根据上述数字，它大约是2的倍数。）此外，堆栈值的使用者经常想对堆栈中的前两个值做一些有趣的事情，而不仅仅是丢弃堆栈顶部：-减去＆lt;比较，！并存储发送给内存。只有JZ和jnz（和流行音乐）只想放弃堆栈顶部-但令我惊讶的是，它们占流行音乐的一半。

但是，我没有考虑要在编译器中添加机器代码的位置数量。如果我使用％esi而不是％edi来获取单字节单指令pop（以lodsl的形式）而不是单字节推入怎么办？这会使Lit（增加操作数堆栈深度的唯一操作）变得更丑陋，并且在编译过程中193次调用Lit导致的193％推送％eax出现的每种193次都会变大4个字节（总共增加772个字节），但是减小操作数堆栈深度的七个原语将获得较少的额外复杂性。而且我们仍然会丢失xchg％esp，％ebp废话，包括避免发出它们的代码。

如果将ELF标头和Msyscall和/ buf的创建移至运行时而不是编译时，则可以从编译器和解释器中消除＃和字节编译时指令；输出将更简单； Msyscall和/ bufwouldn不需要两个单独的名称和棘手的代码将它们戳到输出中；棘手的代码不需要用9行注释来解释它；字符“ E”，“ L”和“ F”不需要是幻数。

也许在此基础之上构建一种用于更大，更好的语言的编译器。也许像Lua，Scheme或Smalltalk之类的东西。第一步是使解析更加方便。另一步骤可能是在编译器中建立某种中间表示，或者某种某种模式匹配功能，以使其更容易在中间表示上指定重写（用于优化或代码生成）。

当然，现有的系统编程起来并不方便，代码很难阅读，并且在失败时也很难调试-尤其是在编译器中，它没有发出错误消息的任何方式。垃圾回收，带有边界检查的数组，有限映射（关联数组），强类型（实际上是任何类型），动态派发，可以使您免于不正确的堆栈效应，元编程等的所有这些工作；交互式REPL将是有用的非语言功能。

我（Kragen Javier Sitaker）于2008年撰写了StoneKnifeForth，并立即在阿根廷出版。当时我没有添加明确的版权许可，但现在是一个：

是一种小的命令式编程语言，具有强大的编译能力（编译器自举）。

0.9版于2006年7月15日发布。1000条源代码行包括递归下降语法分析器和手工编码的词法分析器。

//如果ch在s中，则返回1，否则返回0 elsefunc in（ch：char，s：array char）：intvar i：intbegin i = 0而s [i]＃0如果ch = s [i]，则返回1 endif i = i + 1温德返回0end

杰克·克伦肖（Jack Crenshaw）的“让我们构建一个编译器”。 这是一本使用手册，它引导您逐步完成以Pascal编写的约340页文字的玩具语言编译器的编译。 文字确实很容易阅读，但仍然至少需要三到十个小时才能阅读。 它使用递归下降解析，没有中间表示，并且发出68000汇编代码。