function - 以简单的纯函数式语言实现折叠，无需延迟评估

Question

我正在尝试为自动程序合成实现一种简单的功能语言。数据结构是函数和值的图，可编译为 javascript。下图应该是一个折叠函数。 funcApp节点连接到一个函数节点和许多值节点，并将函数应用于值。 arg0是列表，arg1是初始值 (z)arg2是要应用的函数。

它相当于以下方案定义（虽然我的“语言”不是方案，但它是图）

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

问题是，由于没有特殊的运算符，所以一切，特别if是只是一个正常的功能。在这种形式下，程序永远不会终止，而是达到最大堆栈深度，因为 else 子句总是被计算。

我认为这个问题在某些语言中是通过惰性求值解决的。所以我的问题是：是否有没有这种无限递归的功能版本的 fold 2）如果有必要，从哪里开始考虑将惰性求值应用于这样的简单语言。

Answer 1

我认为在 binders 下进行评估（尤其是评估 lambdas 的主体）是非常罕见的，所以我认为惰性化严格语言的标准解决方案是引入 lambda。我不知道方案语法，但在 Haskell 语法中，如果你想x成为严格函数的惰性参数f，你可能会写类似f (\() -> x)(并f适当修改以期望这样的 lambda，并在你想要的时候调用它们不要懒惰他们）。

Answer 2

您可以将 if 表达式的两个分支编译为 thunk，并根据条件调用适当的 thunk。如果 scheme 的正式定义是这样写的，我不会感到惊讶。