Droste's Lair是一个在两周内快速开发完成的非同寻常的编程环境，用于构建和计算数学结构。在Droste's Lair中，用户可以通过直接交互来操作数学结构，例如在棋盘上放置多米诺骨牌和在列表之间拖动项目。该系统的强大功能源于构建在此基础之上的两种抽象形式：一种允许执行线程彼此分支的“amb”机制和一种支持递归的过程调用机制。

此外，Droste's Lair还是一款剑与魔法风格的点击式冒险游戏。（有点像。）

**游戏指南**

为了让您快速了解Droste's Lair的游戏玩法，我们将带您进行三次快速游览地牢。我们邀请您加入我们的游戏指南——每个旅程的顶部和底部都有游戏链接，您可以从一开始就玩，也可以跳到结局。

地牢仍在开发中。如果某些内容让您感到困惑，那不是您的问题，而是我们的问题。

可以通过滚动、拖动背景或按住Shift键移动光标来平移。可以使用Ctrl-Z进行撤销。超越这些的功能将在适当的时候引入，或者将被深深地保密。

**命运的逆转**

加入游戏开始

在地牢的墙壁上，一块羊皮纸昏暗地映照着闪烁的烛光。上面有一个列表：[a, b, c, d]。

您的老师（他也是一位很酷的巫师）的任务是反转此列表的元素。您首先尝试逐个移动元素。点击一个元素……

……拾取它，并显示它可以放置的位置。您将其添加到第二个当前为空的列表的开头。

您的操作神奇地在墙上创建了第二个羊皮纸方块，显示了其效果。您几乎可以将其视为“漫画书”，尽管潮湿的空气和远处铁链的叮当声使情况变得一点也不滑稽。

您可以继续逐个移动项目，对于这么短的列表来说，这不会花费很长时间。但您知道，比您想象的要快，您将面对更大的敌人。手动移动项目，您最多只能处理几个项目，然后就会被某种兽人的棍棒击倒。您需要一种自动化这些动作的方法，一种类似于巫师学徒的方法。

要施放的法术一直都在您身边，在左上角：♌︎。这个符号标志着您正在编写的脚本。借助它，您可以获取您到目前为止所做的操作，并将其再次作为自己的法术施放。

带着一些不安（毕竟您正在使用递归！），您抓住符号并将其施放到最新的面板上……

您的不安是有道理的。您法术的效果简直令人惊叹。

通往墙壁的传送门打开了，深邃的洞穴，以及更深邃的洞穴。在每个洞穴内部，符号♌︎都在发挥作用。因此，每个洞穴都以“开始”羊皮纸开始，然后有一个“移动项目1”羊皮纸，就像洞穴外部的脚本一样。但是每个洞穴都以先前洞穴的结果开始。因此，虽然顶层移动“a”，下一层移动“b”，依此类推。

这种疯狂会在哪里结束？在底部，在一个与您符号咒语的邪恶后果的命运攸关的遭遇中：基本情况。您从未远离它。稍微平移一下，您就可以到达最深的洞穴，位于地表以下四层。

在这一最深层，第一个列表已耗尽。所有项目都已反序移动到第二个列表中。这是一个巨大的进步，但我们还没有完成。尽管我们的答案潜藏在递归洞穴的深处，但没有任何东西会浮出水面。还没有。

问题在于我们的羊皮纸被卡住了。羊皮纸的灵魂呼唤着我们：“列表为空！”。我们知道，实际上，第一个列表为空根本不是问题——这仅仅意味着我们已经准备好从灵魂世界中召回我们的答案。因此，我们通过为它提供一条逃生路线来引导羊皮纸。点击双匕首标记（‡）即可创建一个。

逃生路线引导羊皮纸从最深层逃脱，在那里它遇到了空列表的障碍。在每一较高层，逃生路线都是可用的，但羊皮纸并没有使用它，因为它可以愉快地继续执行项目移动和递归调用。最后，我们在最右边得到了最终答案。我们奇怪的配方完成了。我们已准备好面对更大的列表，以及可能怀着恶意意图将它们带给我们的可怕生物。

见证结局

**永无止境的**

加入游戏开始

您在第一次测试中表现出色，但您的老师提醒您，您仍然是一个新手。毕竟，您的第一个法术只追踪了一条时间线。在每个点上，它都做了一件事，做了一个决定，定义了一条可能性线索。最强大的法术消除了决定的界限。当面对“是或否？”的问题时，这些法术会回答“是和否”，成为一棵树的分支树枝，永远伸向无垠的天空。

为了学习这项艺术，您承担了一项简单的任务：生成一副牌中的所有花牌。您从原始材料开始：一张牌面列表和一张花色列表。

花牌是通过将牌面与花色组合而成的。因此，首先，您选择一个牌面。

您就像反转列表时一样：从牌面列表中取出一项并将其添加到新列表中。因此，您选择了一个特定的牌面。但这并不是您真正想要的。您真正想要的是，您知道，消除决定的界限，并选择所有可能的牌面。

为此，您点击“移动项目1”标题。它循环遍历几个不同的标题（“移动第一个项目”、“移动最后一个项目”），然后停在“移动任何项目”上。就是这样！

现在有三个羊皮纸堆叠在一起，三个平行的行动宇宙。它们展开是因为您悬停在它们上面，但稍稍移开片刻就会将它们缩小成一个紧凑的堆栈。

完成工作意味着对花色做同样的事情，在分支上创建分支。您从右侧的一个面板上选择一个花色，并将其放在所选牌面的旁边。

然后您将此步骤从“移动项目2”更改为“移动任何项目”。

您的12张花牌都在这里。在烛光下展开，它们很美丽。

见证结局

**枚举**

加入游戏开始

您已经学习了施放递归法术和将世界分解成无数可能性的基础知识。现在是时候将这些神秘的艺术应用到真正的挑战中了。

一个邪恶的巫师正在用一个阴险的谜题折磨附近的村庄：他问道，一个2xN的棋盘可以用多少种方法完全覆盖多米诺骨牌？

什么！？N不是一个数字！那是字母！您现在还无法应对这个巫师的“假装字母是数字”的障眼法。但是您可以通过将N替换为数字来开始了解。假设是4。

您准备了一个2x4的棋盘。

如何填充它？好吧，您可以尝试放下一个多米诺骨牌。

啊，现在也许我们可以用这样的垂直多米诺骨牌填充棋盘的其余部分。您意识到您想一遍又一遍地重复一个步骤，有点像您接受过训练的反转练习……但这有点不同。之前，您将递归法术施放到整个羊皮纸面板上。在这里，这将导致下一个多米诺骨牌反复堆叠在同一方块中的第一个多米诺骨牌之上。我们需要施放法术，使其作用于棋盘的其余部分，而忽略第一个多米诺骨牌。

也许您可以……稍微挥动一下魔杖？

您将法术施放到子网格上，并松了一口气。它似乎起作用了！

在递归的深处，您的“放置多米诺骨牌”操作失败了，因为它超出了棋盘范围。但这没关系；这仅仅意味着棋盘已被填满。因此，您激活了逃生路线。

您已成功找到了一种只使用垂直多米诺骨牌填充棋盘的方法。现在您应该尝试使用水平多米诺骨牌。从最左边的空白棋盘重新开始，您创建了一个第二个分支来放置两个水平多米诺骨牌。

再次，在您放置前两个多米诺骨牌后，您需要填充棋盘。您决定再次施放一个递归法术，询问顶级过程在填充棋盘的其余部分时可能会做出怎样的选择。

您期望得到另一个简单的循环，显示如何添加两个水平多米诺骨牌以填充棋盘。但发生了一些不同寻常的事情。

您在顶层定义的两路分支已复制到递归法术的每一层！不再有简单的单向循环了——相反，随着每个更深的洞穴，都会出现新的分支可能性。

您检查最终输出。仔细考虑一下，这五种覆盖似乎是唯一可能的。您是否偶然发现了一个完全通用的程序？

一次理解所有这些内容是困难的。幸运的是，您的老师教过您一个“折叠深度超过1的调用法术”（按键盘上的“2”），因此您现在就使用它。您面前的许多洞穴都缩小了，只留下了最高层结构可见。

啊，当然。在添加一个垂直多米诺骨牌后，您可以添加第二个垂直多米诺骨牌或两个水平多米诺骨牌。类似地，在添加水平多米诺骨牌后，您可以添加一个垂直多米诺骨牌或两个水平多米诺骨牌。看起来，遵循这种分支模式，始终添加一个垂直或两个水平多米诺骨牌，可以得到所有可能的覆盖。

您已经征服了2x4棋盘的问题！但一些谜团仍然存在……那个邪恶的巫师到底是什么意思“N”？找出答案将是另一天的旅程。

见证结局

**解释**

（又名讨论和未来工作）

现在您已经从地牢的磨难中返回，我们想告诉您一些关于Droste's Lair的由来。拿起一杯加香的蜂蜜酒，坐下来。

您好！我们是Elliot和Josh。我们在今年早些时候通过Ink & Switch等互联网圈子认识。我们发现我们有很多共同的兴趣，尤其是在数学可视化方面。因此，我们决定一起开始一个小型项目，最终花费了大约两周的时间。

我们将项目的严格时间限制作为放纵和遵循我们心血来潮的借口。Droste's Lair绝对是一项艺术探索。它也可能是一个研究项目。我们对最终结果感到非常满意。这是一个真正奇怪的小作品，它将我们的一些长期原则与一些冒险的实验结合在一起。制作它真的很有趣，玩起来也可能很有趣。我们不确定它到底有什么用，但这没关系。

在接下来的“解释”中，我们将讨论构成Droste's Lair的各种想法，我们思考过的一些紧张关系，以及一些悬而未决的开放性问题。

**编程模型及其起源**

这个项目属于一系列项目的传承，这些项目共同设计了一个底层编程模型，以及一个用于查看和交互该模型的可视化界面。当然，我们会借鉴传统编程语言中的想法，但始终会问“它是什么样子的？”和“编辑它是什么感觉？”。

我们受到该领域的一些先前项目的启发。Josh有兴趣重新审视一个旧的想法：一个用于构建树以解决组合计数问题的实时编程界面。他最初的原型，名为“构建并计数”，采用了函数式编程结构，其中分支树的每一层都充当“映射”操作，定义一个可以在树中更深处引用的新变量。

Marcel Goethals最近的Subsequently原型为这种函数式嵌套作用域氛围提供了一个令人兴奋的替代方案。在Subsequently中，每个漫画面板都包含某个时间点世界状态的完整状态。您直接对面板的内容进行操作。没有变量埋藏在某个其他面板中；您需要的一切都在您所处的位置。Subsequently还证明，某些过程（例如从数组中选取元素）作为改变世界状态的命令式过程感觉更自然，而不是作为函数式过程。

Subsequently缺乏“远距离的幽灵般行为”及其命令式模型对我们来说很有吸引力。它们加起来产生了适合实时、交互式、可视化编程系统的物理感觉。此外，它们与传统的计算机科学标准相比很奇怪，这始终是一个好兆头。

为了扩展Subseqently模型以用于“构建并计数”风格的计数问题，我们必须添加分支。当然，Subsequently具有条件分支，如上图所示，但我们需要无条件分支——所有分支都同时被采用，“消除了决定的界限”。这听起来很花哨，但构建起来很简单。它在计算机科学领域也是老生常谈，也被称为“amb”或“列表单子”或“不确定性”。诚然，在像Droste's Lair这样的命令式环境中看到这种东西并不常见，这令人兴奋。

我们调制的Subsequently加分支药水足以解决一些简单的计数问题，例如我们在“永无止境”游览中制作的卡片。但我们仍然无法掌握一些最有趣的计数问题。这些问题涉及递归：其中计算更大结构的可能性涉及将其分解成多个部分，计算每个部分的可能性，然后将这些部分的可能性重新组合成整个结构的可能性。在游览中，我们展示了如何使用递归来计算用多米诺骨牌覆盖棋盘的方法。实际上，我们最初的动机是一个更复杂的问题：计算分形谢尔宾斯基图（也称为河内图，因为它描绘了河内塔难题中的状态）上的路径。在我们的短跑中，我们无法解决这个问题，但多米诺骨牌是一个不错的替代方案。

除了递归在计数问题中的适用性之外，我们也仅仅是对如何在可视化编程界面中使递归结构易于理解感到好奇。（尤其是Elliot一直在研究这一方面一段时间。）

有了这些，我们就有了Droste's Lair中编程模型的基本公式：

Subsequently风格的命令式流程图

……加上分支路径

……加上递归。

基本上就是这样，只要您忽略（就像我们现在一样）Droste's Lair也是一款点击式冒险游戏。

**分支**

Droste's Lair提供了两种产生分支计算的方法：

在单个面板上调用多个操作或过程，或

调用具有多个输出的操作或过程。

当在面板上调用多个不同的操作时，它们会从该面板分支出来（1）。但是，当单个操作或过程具有多个输出时，我们会将其输出分组到界面中的面板堆栈中（2）。或者也可以不分组这些输出，而是将它们显示为分支路径。

将多个输出放入堆栈中涉及权衡。我们选择的堆栈可视化使界面更接近底层流程图的结构：用户添加的每个操作都显示在一个地方。如果“移动任何项目”之类的操作在界面中产生分支，则这些操作将被多次描绘，使界面与底层程序的匹配度降低。但在某些方面，程序的运行时行为会更加清晰。

在构建实时编程系统时，这种在突出显示静态和动态结构之间的张力很常见。程序的动态执行是程序静态规范的“展开”（通过循环/调用）和“切片”（通过条件）。同时显示静态和动态层具有挑战性。

但是，有一些技术可以提供帮助。周到的视觉设计可以走很远。而且，对我们来说幸运的是，计算机是交互式的，因此我们也可以使用交互式技术。Droste's Lair未来的工作可以让用户根据需要在堆叠视图和分支视图之间切换。或者，也许悬停面板可以通过突出显示来显示屏幕上与其不太明显相关的其他元素。

**递归**

与Droste's Lair不同，Subsequently没有递归。要在Subsequently中循环，您需要从一个步骤到上一步创建一个箭头，本质上是一个“goto”。尽管goto如今已过时，但对于特定的情况范围来说，它确实是一种非常棒的循环方式。

我们希望我们的系统处理的一些问题似乎超出了这一范围，例如前面提到的谢尔宾斯基问题。我们知道有充分的理由抵制全面递归，递归学习和使用起来非常困难，尤其是在那些不是专业程序员的人看来。因此，我们花了一些时间进行草图绘制，看看我们是否可以找到递归的替代方案，以便在适合Subsequently模型的同时，让我们获得所需的表达能力。

最终，我们无法让任何东西工作，而且我们选择了相当传统的递归。我们仍然觉得这条道路上可能有一些有趣的东西。例如，我们花了一些时间思考流程图箭头从流程图的整个面板流出而不是从面板的一部分流出的含义。在我们看来，这可以让流程图表达递归的“分而治之”结构。（一种看待这一点的方法是：流程图箭头大致对应于尾递归调用。我们在这里所做的事情表明，可以适度放松此约束，以便进行多个同时的尾递归调用，这些调用彼此可以交换，因为它们对结构的不同部分进行操作。）

将疯狂的替代方案放在一边，现在我们的工作是将递归调用（通常是过程调用）引入Subsequently模型。在Subsequently中，操作表示为一个漫画面板，该面板显示操作后的世界图片，并带有说明操作本身的图形以及面板上方的描述性文本。

我们将此设计扩展到我们对过程调用的描述中。我们系统中的调用表示为一个包含被调用过程的正文的洞，后跟一个“'过程调用'操作后”的面板。

视觉上将调用表示为编辑器铺砌地板上的物理洞穴的灵感来自递归中“深度”的隐喻，以及爬进越来越深的洞穴和/或递归函数时产生的令人毛骨悚然、令人迷失方向的感觉。

在Droste's Lair中，您可以对整个面板或您选择的面板内容的一部分调用过程。

关于我们在洞中如何可视化面板内容的一点说明：最直接的做法是仅显示被调用过程对其所接收的部分进行操作，而羊皮纸上没有任何关于它们来自的较大整体的参考。但我们认为这样做会放弃我们在设计中努力追求的大量物理“对象永久性”感。进入和退出过程调用需要重新定位。为了保持我们想要的基础感，我们选择始终显示部分的整体上下文。我们使用颜色编码的轮廓来显示过程调用正在积极关注的部分，并淡出其余部分。

（我们在Droste's Lair的整个界面中都保持一个概念性的配色方案：黄色表示操作，紫色表示过程和调用，红色表示问题。）

尽管我们在本项目中尝试尽可能具体和易于理解地可视化递归，但构建递归过程仍然是一项极其“程序员思维”的活动。即使有了我们的可视化效果，大多数人也不会觉得很自然。但我们还没有准备好放弃递归！我们可以做些什么来减少构建系统中递归所需的“程序员思维”？也许用户可以首先手动构建具体的树，然后我们的系统可以帮助他们构建与之匹配的递归函数？

**条件**

在涉及流程控制时，我们的设计自然偏离了Subsequently的设计。我们一直在寻找方法来减少递归的“程序员思维”；我们倾向于让用户随心所欲地做事，然后让他们作为对情况的事后反应来处理随之而来的错误。

放弃传统的if-then风格条件语句开启了巨大的设计空间。在初始设计过程和早期实现过程中，我们经历了多次错误处理迭代。第一个适用于我们所有示例的设计是允许用户将错误处理程序面板附加到任何其他面板作为该面板操作的“捕获”。最终，我们选择了一种在我们的示例中感觉更自然一点的机制：在面板的所有可能操作都导致错误时，附加一个“转义”面板。

我们不确定这是否是处理此类系统中的错误或其他条件的“正确”方法。需要进行更多探索！

**活力与美学**

到目前为止，在本解释中，我们还没有承认房间里的龙：Droste's Lair不仅仅是一个可视化编程系统。它也是一款剑与魔法风格的点击式冒险游戏。有点像……也许不是真的，但它肯定受到了这些游戏的审美和设计的启发。

这个奇怪的决定源于我们渴望涉足“活力”（游戏开发中的一个术语）。Droste's Lair可能不是您遇到过的最充满活力的东西。但我们习惯于制作0%活力的编程系统，因此这对我们来说是进入活力领域的一大步。

活力很酷

看看nool

Elliot通过游戏开发开始学习代码

重新点燃

精心制作的物品

充满艺术性和思考的作品

一起创作的乐趣

希望也能使用

我们为什么要创造事物？

它们对谁有吸引力？

我们为什么要制作看起来像Microsoft Office的东西？

活力能帮助粉红色的头脑

克服试图

思考平凡事物带来的痛苦吗？

使事物不那么抽象

添加逼真的纹理和物体

帮助一些人理解递归

鼓励类似游戏的思考

和玩耍模式

**更多未来方向**

我们在上面的讨论中已经强调了一些局限性和悬而未决的问题。但这里还有更多！

更多微观世界：游览中的演示使用了两个简单的“微观世界”——列表和多米诺骨牌平铺。我们已经能够从这些微观世界中获得一些乐趣，但我们想知道其他哪些简单状态和动作领域能够更具生成性。

混合微观世界：为什么我不能将花色拖到多米诺骨牌网格中？为什么我不能在列表中放置多米诺骨牌？将世界混合在一起可以成倍增加可能性，但目前尚不清楚哪些底层模型可以使之成为现实。

扩展：对于此原型，我们坚持使用小型玩具示例——数据和流程图都不会变得很大。当它们变得很大时，我们可视化事物的方式就会开始失效。这与对可视化编程的常见批评相吻合——无法扩展到更大规模的情况。但我们还不怎么担心。当需要扩展规模时，我们将有如此多的技术可以借鉴！扩展和折叠、小地图、轮廓视图、更紧凑的图形设计等等。我们已经在“枚举”游览中展示的递归深度过滤器中涉足了这一领域。

可学习性：如果您已经冒险进入Droste's Lair并实际花了一些时间，我们为您的勇气鼓掌。您可能已经注意到——在许多方面，它都很难使用。我们可以做些什么来指导人们进行探索？我们可以借鉴游戏的叙事技巧吗？我们的编程模型中的新机制能否让人们从具体的动作平稳过渡到抽象的概念，例如递归？

动作的表示：遵循Subsequently的示例，我们在Droste's Lair中添加了操作本身的可视化表示。与其仅仅看到操作前后的世界状态，不如在状态中添加注释以显示发生了什么。至少有四种与操作相关的假设视图：一个“之前”视图、一个“之后”视图、一个显示即将发生的事情的“之前”注释视图，以及一个显示刚刚发生的事情的“之后”注释视图。在我们当前的系统中，我们关注“之后”的注释视图。这是最佳关注点吗？有没有办法包含更多视图，或者允许在视图之间移动？

我们用它做什么：我们构建Droste's Lair作为一项短期实验。老实说，我们对此非常满意。但有些人可能会想知道：这东西有什么用？我们也想知道，尽管我们会用更不具对抗性的方式来表达它。这个项目能否发展成为一种教育工具？一个数学实验室？一个货真价实的博弈？一个用于数据集成工作流的编程环境？嗯……

感谢……

Marcel Goethels，感谢Subsequently的精彩灵感。

Ink & Switch和Pacific Programming Interfaces Confab，感谢你们为分享提供场所。

Ivan Reese，感谢您的游戏测试和富有洞察力的反馈。

Andrew Blinn，感谢您的游戏测试、富有洞察力的反馈以及他对活力的支持。

Rocky430，感谢您与Elliot就Frutiger Aero和PSX等美学进行了启发性的对话。

Nick Joliat，感谢您的分形灵感。

Todd Matthews，感谢您想出这个绝妙的名字。

请与我们联系！[email protected]

[email protected]

MMXXIV