将命令转换为功能代码

Question

我需要编写一个程序,将命令式代码转换为纯函数式.我并不担心I/O--我有一些解决方案 - 但我确实需要处理堆对象和局部变量.

我想这可以通过传递一个TheWorld带有每个函数调用的对象并返回,然后从那里进行优化,尝试从不使用它的函数中删除该参数等来完成.但是有没有一种已知的更好的方法呢？

Answer 1

正如SK-logic指出的那样,您可以用SSA形式代表您的命令式程序.

然而,基于Zadarnowski等人发布的算法,您可以直接将命令式SSA表示转换为"管理规范形式"(一种受限制的功能语言)中的等效纯函数程序.

这两种语言由下式给出:

请参阅:" SSA优化算法的功能视角 ",它提供了将SSA形式的程序自动转换为ANF的算法.

Answer 2

有许多方法可以有效地进行这种翻译.首先,值得用随后的CPS变换进行SSA变换:这样你就可以从带有变量和分支的命令式代码中获得一堆简单的相互递归函数.函数调用(甚至虚拟调用)也可以通过传递continuation参数而不是依赖于隐式堆栈语义来轻松地进行CPS编辑.

在SSA转换之前,数组的处理方式与变量相同,所有数组访问都应该用get和update函数调用替换,而函数调用应该具有隐式复制语义(但在这种情况下要注意别名).结构相同.

并且只有在无法维护复制语义的情况下,您才需要拥有此TheWorld对象,该对象应保留所有已分配的对象,并且每次修改其中一个对象时都应该进行复制.