在功能解释器中序列化正在运行的程序

2018-06-20 21:54:11

我正在撰写一个使用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:          ...

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

要序列化，我将保存当前标签名称和输入时的状态。反序列化将对输入代码进行预处理以再次构建标签，然后在给定状态下以给定标签恢复。但是现在我必须在实施我的口译员时考虑这些问题。即使使用构图来隐藏这些看起来也很丑陋。

题

有没有解决这个问题的好方法？我在想以完全错误的方式序列化一个程序吗？这对这样的结构甚至可能吗？

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

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

问题

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

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

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

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

主机功能在国家

程序状态不能轻易序列化的原因是它包含用于延续的主机功能。这些延续必须转化为数据结构，这些数据结构可以序列化并独立重构为原始延续代表的行为。去功能化通常用于以一阶语言表达高阶语言，但我相信它也会启用序列化。

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

但是，据我所知，由于绑定语句的原因，禁用功能化不能使用Cont Monad。缺乏良好的抽象使其很难合作。

对解决方案的思考

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

首先，为了最大限度地减少所需的工作量，我会重写语句级解释器，使其更像是一个更易于序列化的状态机。然后，我会去除表达功能。函数调用会将剩余表达式的defunctionlized延续推入状态机的内部堆栈。

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

看看语句是如何工作的，我不相信Cont Monad是将语句链接在一起的最佳方法（但我认为它在表达层和内部操作上运行得非常好）。状态机似乎更自然的方法，这也会更容易序列化。

写在语句之间的机器将被写入。该州的所有其他结构也将被制成可序列化的。内建函数必须使用可序列化的句柄来识别它们，以便没有函数处于该状态。

处理表达式

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

函数返回时，功能化的延续会传递结果。

关注

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

去功能化似乎需要直接处理延续，并会使整个解释器不够灵活。

链接地址: http://www.djcxy.com/p/58763.html

上一篇: Serializing Running Programs in a Functional Interpreter

下一篇: Separating State for a Model and GUI IO ( Wx) : Stack or FRP?