14

命令型コードを純粋関数型に変換するプログラムを作成する必要があります。I / Oについては心配していません-そのためのいくつかの解決策を考えています-しかし、ローカル変数だけでなくヒープオブジェクトも処理する必要があります。

関数の呼び出しと戻りのたびにオブジェクトを渡し、TheWorldそこから最適化して、使用されていない関数からそのパラメーターを削除しようとすることで、これを実行できると思います。しかし、それを行うためのより良い方法は知られていますか？

4

3 に答える 3

9

このような翻訳を効率的に行うには、いくつかの方法があります。まず、結果としてCPS変換を使用してSSA変換を実行する価値があります。このようにして、変数と分岐を含む命令型コードから、相互に再帰的な些細な関数を取得します。暗黙的なスタックセマンティクスに依存する代わりに継続パラメーターを渡すことにより、関数呼び出し（および仮想呼び出しでさえ）を簡単にCPSすることもできます。

配列は変数と同じ方法で処理できます。SSA変換の前に、すべての配列アクセスをget関数update呼び出しに置き換える必要があります。関数呼び出しには、暗黙のコピーセマンティクスが必要です（ただし、この場合はエイリアシングに注意してください）。構造についても同じです。

また、コピーのセマンティクスを維持できない場合にのみTheWorld、割り当てられたすべてのオブジェクトを保持し、オブジェクトの1つを変更するたびに完全にコピーする必要があるこのオブジェクトが必要です。

于 2011-07-07T10:25:23.097 に答える
9

SK-logicが指摘しているように、SSA形式で命令型プログラムを表すことができます。

ただし、CPS変換を適用するのではなく、命令型SSA表現を、Zadarnowski et alによって公開されたアルゴリズムに基づいて、制限付き関数型言語である「AdministrativeNormalForm」の同等の純粋な関数型プログラムに直接変換できます。

2つの言語は次のように与えられます。

ここに画像の説明を入力してください

SSA形式のプログラムをANFに自動的に変換するためのアルゴリズムを提供する「SSA最適化アルゴリズムの機能的展望」を参照してください。

于 2011-07-07T18:27:49.913 に答える
1

多くの関数型プログラミング言語では、一連のローカル変数の割り当てを一連の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では、これはサブタームを置き換えることによって行うことができます：

:- 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]
        ).

モナドまたは再帰を使用してwhileループを実装する方法もいくつかあります。

于 2019-12-18T23:15:49.090 に答える