1

我正在编写一个使用 Cont Monad 的变体在功能上实现的解释器。受 Smalltalk 使用图像捕获正在运行的程序的启发，我正在研究如何序列化正在执行的托管程序，并且需要帮助确定如何在高级别上完成此任务。

问题陈述

使用 Cont monad，我可以在解释器中捕获正在运行的程序的当前延续。存储当前延续允许通过调用延续来恢复解释器的执行。我想序列化这个延续，以便可以将正在运行的程序的状态保存到磁盘或由另一个解释器实例加载。但是，我的语言（我的目标和工作都在 Javascript 中）不支持以这种方式序列化函数。

我会对一种方法感兴趣，该方法可用于在给定的执行点建立延续给定的一些元数据，而无需再次运行整个程序，直到它到达该点。优选地，将对解释器本身的实现做出最小的改变。

考虑的方法

一种可行的方法是将所有控制流逻辑推入程序状态。例如，我目前使用宿主语言对循环行为的递归来表达 C 风格的循环：

var forLoop = function(init, test, update, body) {
    var iter = function() {
        // When test is true, evaluate the loop body and start iter again
        // otherwise, evaluate an empty statement and finish
        return branch(test,    
            next(             
                next(body, update),
                iter()),
             empty);
    };

    return next(
        init,
        iter());
};

这是一个很好的解决方案，但是如果我通过 for 循环中途暂停程序，我不知道如何序列化已建立的延续。

我知道我可以使用跳转序列化转换后的程序，并且可以从跳转操作构造 for 循环。我的解释器的第一遍将生成代码块并将它们保存在程序状态中。这些块将捕获托管语言中的一些操作，并可能执行其他块。预处理程序看起来像这样：

Label         Actions (Block of code, there is no sequencing)
-----------------------------------
start:        init, GOTO loop

loop:         IF test GOTO loop_body ELSE GOTO end

loop_body:    body, GOTO update

update:       update, GOTO loop

end:          ...

这使得每个代码块都是独立的，只依赖于存储在程序状态中的值。

要序列化，我会保存当前标签名称和输入时的状态。反序列化将预处理输入代码以再次构建标签，然后以给定状态在给定标签处恢复。但是现在我在实现我的解释器时必须考虑这些块。即使使用合成来隐藏其中的一些似乎有点难看。

问题

有没有什么好的现有方法来解决这个问题？我是否正在考虑以完全错误的方式序列化程序？对于这样的结构，这甚至可能吗？

4

1 回答 1

0

经过更多的研究，我对如何做到这一点有了一些想法。但是，我不确定添加序列化是我现在想要做的事情，因为它会对实现的其余部分产生很大影响。

我对这种方法不满意，非常希望听到任何替代方案。

问题

正如我所指出的，将程序转换为语句列表使序列化更容易。整个程序可以转换成汇编语言之类的东西，但我想避免这种情况。

保持表达式的概念，我最初没有考虑的是函数调用可以发生在深度嵌套的表达式内部。以这个程序为例：

function id(x) { return x; }
10 + id(id(5)) * id(3);

序列化程序应该能够在任何语句处序列化程序，但该语句可能会在表达式内部进行评估。

该州的主机功能

程序状态不能轻易序列化的原因是它包含用于延续的宿主函数。这些延续必须转换成可以序列化并独立重构为原始延续所表示的动作的数据结构。去功能化最常用于以一阶语言表达高阶语言，但我相信它也可以实现序列化。

并非所有延续都可以在不彻底重写解释器的情况下轻松取消功能。由于我们只对特定点的序列化感兴趣，因此这些点的序列化需要对整个延续堆栈进行去功能化。所以所有的语句和表达式都必须去功能化，但是内部逻辑在大多数情况下可以保持不变，因为我们不希望在内部操作中允许序列化。

但是，据我所知，由于绑定语句，去功能化对 Cont Monad 不起作用。缺乏良好的抽象使其难以使用。

对解决方案的思考

目标是创建一个仅由可用于重建整个程序状态的简单数据结构组成的对象。

首先，为了尽量减少所需的工作量，我会重写语句级解释器，以使用更像状态机的东西，可以更容易地序列化。然后，我会去功能化表达式。函数调用会将剩余表达式的去功能延续推入状态机的内部堆栈。

使程序状态成为可序列化的对象

看看语句是如何工作的，我不相信 Cont Monad 是将语句链接在一起的最佳方法（我确实认为它在表达式级别和内部操作中工作得很好）。状态机似乎更自然的方法，这也更容易序列化。

将编写一台在语句之间步进的机器。该状态中的所有其他结构也将可序列化。内置函数必须使用可序列化句柄来识别它们，以便没有函数处于该状态。

处理表达式

表达式将被重写以传递去功能化的延续而不是宿主函数延续。当在表达式中遇到函数调用时，它会捕获去功能化的当前延续并将其推送到语句机器的内部堆栈（这只会发生在托管函数中，而不是内置函数），从而创建一个可以恢复计算的还原点。

当函数返回时，将结果传递给去功能化的延续。

关注点

Javascript 还允许在几乎任何表达式（getter、setter、类型转换、高阶内置函数）中评估托管函数，如果我们允许在这些函数内部进行序列化，这可能会使事情复杂化。

去功能化似乎需要直接使用延续，并且会使整个解释器不那么灵活。

于 2013-10-10T19:25:54.047 回答