functional-programming - 将命令式转换为函数式代码

Question

我需要编写一个程序，将命令式代码转换为纯函数式风格。我不担心 I/O——我对此有一些解决方案——但我确实需要处理堆对象以及局部变量。

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

Answer 1

有许多方法可以有效地进行这种翻译。首先，值得做一个带有后续CPS转换的 SSA 转换：这样你就可以从带有变量和分支的命令式代码中得到一堆琐碎的相互递归函数。函数调用（甚至虚拟调用）也可以通过传递延续参数而不是依赖于隐式堆栈语义轻松地进行 CPS 编辑。

数组可以像处理变量一样处理，在 SSA 转换之前，所有数组访问都应该替换为函数调用get，update函数调用应该具有隐式复制语义（但在这种情况下要注意别名）。结构也一样。

并且仅在无法维护复制语义的情况下，您需要拥有该TheWorld对象，该对象应保留所有已分配的对象，并且每次修改其中一个时都应完整复制。

Answer 2

正如 SK-logic 指出的那样，您可以以 SSA 形式表示您的命令式程序。

但是，您可以直接将命令式 SSA 表示转换为“管理范式”中的等效纯函数式程序，而不是应用 CPS 转换，这是一种基于 Zadarnowski 等人发布的算法的受限函数式语言。

这两种语言由以下给出：

请参阅：“ A Functional Perspective on SSA Optimization Algorithms ”，它提供了用于将 SSA 形式的程序自动转换为 ANF 的算法。

Answer 3

在许多函数式编程语言中，可以用一系列表达式替换一系列局部变量赋值let。

例如，这个 C 函数可以这样翻译：

int example(int a,int b){
    a += 1;
    b += 2;
    if(a == 1){
        b += 1;
    }
    else if(b == 1){
        a += 1;
    }
    return a + b;
}

Futhark编程语言中的等效函数可以这样编写，使用记录数据结构来存储局部变量：

let example a b =
    let vars = {a,b} in
    let vars = vars with a = vars.a + 1 in
    let vars = vars with b = vars.b + 2 in
    let vars = (if vars.a == 1 then
        let vars = vars with b = vars.b + 1 in
        vars
    else if b == 1 then
        let vars = vars with a = vars.a + 1 in
        vars
    else
        vars)
    in vars.a + vars.b

在某些情况下，还可以将一系列命令式语句转换为单个算术表达式。在 Prolog 中，这可以通过替换 subterms来完成：

:- use_module(prolog_vars_list).
:- set_prolog_flag(double_quotes, chars).
:- initialization(main).

main :- 
    To_solve = (Z=11,
    Z=Z*2,
    A=1+A,
    A=A+2,
    A = Z+1,
    A = A * 2,
    A=A+3+Z+P),

    run_imperative(To_solve,B),
    
    %print the input
    writeln(To_solve),
    
    %now print the output
    writeln(B).

run_imperative(A,B) :- imperative_to_declarative(A,_=B).

imperative_to_declarative((A,B,C),D1) :- 
imperative_to_declarative((B,C),D),imperative_to_declarative((A,D),D1).

imperative_to_declarative((A=A1,B=B1),(_=C)) :-
    replace(A,A1,B1,C).

replace(Subterm0, Subterm, Term0, Term) :-
        (   Term0 == Subterm0 -> Term = Subterm
        ;   var(Term0) -> Term = Term0
        ;   Term0 =.. [F|Args0],
            maplist(replace(Subterm0,Subterm), Args0, Args),
            Term =.. [F|Args]
        ).

还有几种方法可以使用 monad 或递归来实现 while 循环。