7

Ozチュートリアルの関数に関する章では、次のように述べています。

怠惰な関数型言語と同様に、Ozでは、Standard ML、Scheme、並行関数型言語Erlangなど、特定の厳密な関数型言語には見られない特定の形式の末尾再帰の最適化が可能です。ただし、Ozの標準関数定義は怠惰ではありません。

次に、 Ozで末尾再帰である次の関数を示します。

fun {Map Xs F}
   case Xs
   of nil then nil
   [] X|Xr then {F X}|{Map Xr F}
   end 
end

これは、空のリストを空のリストと空でないリストにマップし、関数をそのヘッドに適用した結果にマップし、その後、テールFを呼び出した結果の前に追加します。Map他の言語では、これは末尾再帰ではありません。これは、最後の操作が先頭であり、への再帰呼び出しではないためMapです。

だから私の質問は：「Ozの標準関数定義が怠惰ではない」場合、SchemeやErlangのような言語がこの関数の末尾再帰最適化を実行できない（またはできない）ので、Ozは何をしますか？そして、関数がOzで末尾再帰になるのはいつですか？

4

2 に答える 2

5

これはTail Recursion ModuloConsと呼ばれます。基本的に、再帰呼び出しの直後にリストに追加することは、再帰呼び出しの直前にリストに追加することと同じです(したがって、純粋に機能的な「ループ」の「副作用」としてリストを作成します)。これは末尾再帰の一般化であり、リストだけでなく、定数操作を伴うデータ コンストラクターでも機能します。cons

これは、1974 年に Daniel P. Friedman と David S. Wise によってテクニカル レポート TR19: Unwinding Structured Recursions into IterationsでLISP コンパイル手法として最初に説明されました (名前は付けられていません)。史上初の Prolog コンパイラを作成するコンテキスト。

ただし、Oz の興味深い点は、TRMC が言語機能でも明示的なコンパイラの最適化でもなく、言語の実行セマンティクスの単なる副作用であることです。特に、Oz が宣言型の同時制約言語であるという事実は、すべての変数がデータフロー変数であることを意味します (または、すべての保存場所を含む「すべてが約束です」)。すべてが promise であるため、最初に戻り値を promise として設定し、後でそれを実行するように、関数からの戻りをモデル化できます。

Peter Van Roy と Seif Haridi による本Concepts, Techniques, and Models of Computer Programmingの共著者である Peter van Roy は、Oz の設計者の 1 人であり、その実装者の 1 人でもあり、TRMC がどのように正確に機能するかをコメント スレッドで説明しています。 Lambda the Ultimate:末尾再帰マップと宣言型エージェント:

上記の不適切な Scheme コードの例は、Oz 構文に直接変換すると、適切な末尾再帰 Oz コードに変わります。これは与える：

fun {Map F Xs}
   if Xs==nil then nil
   else {F Xs.1}|{Map F Xs.2} end
end

これは、Oz に単一代入変数があるためです。実行を理解するために、この例を Oz カーネル言語に翻訳します (わかりやすくするために、部分的な翻訳のみを示しています)。

proc {Map F Xs Ys}
   if Xs==nil then Ys=nil
   else local Y Yr in
      Ys=Y|Yr
      {F Xs.1 Y}
      {Map F Xs.2 Yr}
   end end
end

つまり、最初はバインドされていないMapため、末尾再帰です。Yrこれは単なる巧妙なトリックではありません。宣言型の同時実行と宣言型のマルチエージェント システムが可能になるため、非常に重要です。

于 2014-08-05T11:34:53.273 に答える
3

私は怠惰な関数型言語にはあまり詳しくありませんが、質問の関数 Map について考えると、ヒープ内の一時的に不完全な値が許可されている場合 (1 回の呼び出しでより完全な値にミュートされる場合)、末尾再帰の実装に変換するのは簡単です。一度に）。

私は、彼らがオズでのこの変化について話していると仮定しなければなりません. Lispers はこの最適化を手動で行っていました -- すべての値は変更可能で、この場合は呼び出された関数setcdrが使用されます -- しかし、自分が何をしているのかを知る必要がありました。コンピュータには、常にギガバイトのメモリがあるとは限りませんでした。これを手作業で行うことは正当化されていましたが、おそらくもはやそうではありません。

あなたの質問に戻りますが、他の現代の言語はおそらく、構築中に不完全な値を観察することが可能であるため、自動的にそれを行いません。これは、Oz が解決策を見つけたものに違いありません。それを説明する他の言語と比較して、オズには他にどのような違いがありますか?

于 2009-10-03T11:46:41.477 に答える