用代码驱动仓库起重机,在紧到非用递归不可的指令上限下,重新堆放彩色板条箱。
用起重机指令(左右移动、抓取、放下以及颜色条件)编写程序,把各箱位中的板条箱重新排列成目标堆叠。指令上限故意定得很紧,所以你要依靠 Call 命令,它会从头重新运行整个程序;失败的条件就成为停止递归的基本情况。共有十个手工设计的关卡,从一个红色板条箱到六个箱子的高塔,其中八个不用 Call 就无法解开。
Tower of Three(三箱塔):箱位 1 里有三个红色板条箱,必须全部移到箱位 2,而你只能用六条指令。逐条写出来,每个箱子需要 Grab、Right、Drop 和 Left,即使去掉最后一个 Left,三个箱子也要十一条指令。六条不够。
所以只写一趟,让它重复:Grab、If-held 红色、Right、Drop、Left、Call。正好六条指令。起重机抓起一个箱子,检查手里是不是红色,把它运过去放下,返回,再调用整个程序。第四次调用时箱位 1 已经空了,Grab 什么也没抓到,If-held 红色检查失败,程序停止。这个失败的检查就是基本情况。
把 If-held 红色改成 If-held 蓝色,同样的六条指令也能通过四箱关卡和六箱高塔,因为这个例程从不数箱子,而是一直进行到一个不剩为止。这正是递归的要义:程序只描述一个步骤和一条停止规则,运行多少次由输入决定。
Claw Compiler 通过板条箱堆垛起重机和严格的移动预算来教授递归,使困难的想法具体化。
吊车指令——左右移动、抓取、放下,以及基于颜色的条件判断——是一种附带了实体躯体的极简汇编语言。
通过小世界中的小机器人来教编程,可以追溯到卡雷尔机器人(Karel the Robot),这是理查德·帕蒂斯在 1981 年的一本书中推出、并在斯坦福大学的课程中使用的入门语言。游戏也采用了这一思路:Lightbot 让玩家编程引导机器人穿过迷宫,以此教授循环和过程;而 Claw Compiler 最接近的前身是 Cargo-Bot,这是一款 2012 年的 iPad 谜题游戏,玩家要教机器人搬运箱子。Two Lives Left 与 Rui Viana 一起,以他在该公司的 iPad 编程应用 Codea 中制作的原型为基础开发了它,并宣传其为第一款完全在 iPad 上编程的游戏。
任务是把一堆堆板条箱重新排列成目标堆叠,这是由一台每次只能拿着一样东西的机器来完成的排序。单个抓手的限制本身就是一课。这与寄存器所施加的约束相同,也是为什么真正的排序需要一个放东西的地方——发现自己需要一个空箱位,就是发现了临时存储的概念。
由于 Call 总是最后一条指令,这里的每个程序都是尾递归的:自我调用是它做的最后一件事。许多语言实现会把尾调用变成一次简单的跳回开头,所以同一个程序既可以看作递归,也可以看作循环。认识到两者是同一个概念,是理解递归的一大部分。
Claw Compiler 是为 PlayPendium 制作的原创免费浏览器游戏:一种七条指令的起重机语言,十个因指令上限而必须使用递归(而非可有可无)的关卡,一个所有玩家共享的每日关卡,以及一个随机发放其他关卡的练习模式。