1998年的公开实验
本·奥尔姆斯特德设计Malbolge时,关心的是一种与常见语言相反的目标:让编写程序本身变得困难。他在规范开头比较了INTERCAL等实验性语言,认为某些语言虽然外观古怪,操作仍过于容易推断,于是把新的障碍落实到运行规则中。
原始网页提供了MS-DOS和Unix下载包,包括解释器源代码及不同处理器用的二进制文件。保存下来的页面在Malbolge下载项上标注1998年4月15日更新;语言、说明及解释器均被作者放入公有领域。规范当时还没有展示可用例程。这项开放实验吸引网络编程爱好者继续寻找可运行的程序与编写方法。
三进制机器与共享内存
Malbolge把执行环境规定为一台小型三进制虚拟机。每个机器字有十个三进制位,可表示0至59048;内存有59049个单元,程序和数据共用这片空间。累加器A、代码指针C和数据指针D开始都为零。
加载时,空白字符被忽略,程序字符依次进入内存,其余空间根据已有内容通过特殊运算生成。C负责指出当前指令,D参与数据操作,二者在通常的执行步骤之后都会递增。因此,程序员既要安排将执行什么,也要同时追踪数据指针下一步会走到哪里。
参考:[2]
字符含义随地址而变
同一个字符放到不同地址,不一定表示同一操作。解释器把字符数值与当前位置结合,经模94运算和查表后才确定指令;执行后又用另一张表改写代码单元。单纯复制一段看似可用的文字,既可能改变指令意义,也可能让它第二次运行时做出不同动作。
数据运算同样刻意避开熟悉的加减和赋值。核心操作包括三进制位的循环右移,以及逐位查表的特殊组合运算。语言没有直接的通用装入、存储指令,要保留原值或反复读取同一数据,往往必须设计一串辅助操作。难度来自这些规则的相互作用,而不只是字符难认。
一个输出程序如何走到首字符
安德鲁·库克后来写出的问候语程序,适合说明这种机制。酒井正彦在2010年的技术报告中逐步展示其开头:第一条有效操作改变D,接下来的两次特殊运算构造A中的值,随后输出指令才把字符送出。此时A的三进制数值为2200,等于十进制72,因而输出ASCII字符H。
这段过程没有直接写出“输出H”的字面命令,而是先让寄存器经过受约束的状态变化。阅读程序时,还必须把纸面字符和解码后的操作区分开;报告为此把同一例子的原始字符序列与操作序列并列展示。这个后来出现的例程展示了原始规范留下的规则如何被组织成实际输出。
参考:[4]
利用改写周期建立循环
卢·谢弗把Malbolge当作一种可分析的变换系统。他发现,代码置换表存在若干短周期,某些指令经过有限次改写可以返回原状。另一方面,跳转先改变C,随后的改写作用于新位置,因此原跳转指令本身可以保留下来。
这为安排可重复执行的结构提供了办法。谢弗在2004年构造了复制输入到输出的程序,但它在输入结束时不能正确停止。到2010年,酒井的报告进一步展示低级和高级汇编层,将受约束的指令组合封装成较易组织的操作,并列出rot13等程序。这些工具降低的是编写负担,并没有把原始语言的复杂规则抹掉。
规范、解释器与能力边界
最初文本和参考实现并不处处一致:规范中的两个输入输出符号,与C语言解释器中对应的读写行为相反。谢弗及后来的技术报告按解释器解释这些行为,所以重建早期程序时,必须说明采用哪一个依据。
奥尔姆斯特德在原规范中猜测语言可能具备图灵完备性。原始机器拥有固定内存;谢弗后来提出Malbolge-T变体,引入可向两侧移动的外部存储带,用来讨论正式的图灵完备性。原始语言的循环和字符转换能力,则在其有限内存范围内得到程序实例的展示。