function - 遅延評価なしの単純な純粋な関数型言語でのfoldの実装

Question

自動プログラム合成のための単純な関数型言語を実装しようとしています。データ構造は関数と値のグラフであり、javascriptにコンパイルされます。次のグラフはフォールド関数である必要があります。 funcAppノードは関数ノードといくつかの値ノードに接続されており、関数を値に適用します。 arg0はリスト、arg1は初期値（z）arg2は適用される関数です。

これは、folloiwngスキームの定義と同等です（私の「言語」はSchemeではありませんが、グラフです）

(define (foldr f z xs)
   (if (null? xs)
       z
       (f (car xs) (foldr f z (cdr xs)))))

問題は、特別な演算子がないため、特にすべてがif正常な関数であるということです。この形式では、else句が常に計算されるため、プログラムは終了せず、代わりに最大スタック深度に達します。

この問題は、遅延評価によって一部の言語で解決さ​​れると思います。したがって、私の質問は次のとおりです。この無限再帰を持たない機能バージョンのfoldはありますか2）必要に応じて、このような単純な言語に遅延評価を適用することを検討し始めます。

Answer 1

バインダーの下で評価すること (特に、ラムダの本体を評価すること) はかなり珍しいと思うので、厳密な言語を遅延化するための標準的な解決策はラムダを導入することだと思います。スキームの構文はわかりませんが、Haskell の構文ではx、厳密な関数の遅延パラメーターになりたい場合は、次のfように記述できますf (\() -> x)(そして、そのようなラムダを期待するように適切に変更し、f必要なときにそれらを呼び出します)。それらを怠惰にしないでください）。

Answer 2

if 式の両方の分岐をサンクにコンパイルし、条件に基づいて適切なサンクを呼び出すことができます。スキームの正式な定義がそのように書かれていても驚かないでしょう。