我想在Elm中实现自引用/指针。
我受mal的启发在Elm中编写玩具LISP解释器。
[我正在尝试实现类似letrec的东西,以支持递归和相互递归绑定(我在上面提到的“自引用”和“指针”)。
这里是一些示例代码:
(letrec
([count (lambda (items)
(if (empty? items)
0
(+ 1 (count (cdr items)))
)
)
])
(count (quote 1 2 3))
)
;=>3
请注意,lambda的主体如何引用绑定count
。换句话说,该功能需要引用其自身。
定义lambda时,我们需要创建一个由三个组成部分组成的function closure:
摘自维基百科文章:
通常在创建闭包时使用函数的词汇环境(即,可用变量集)的表示形式来实现闭包。引用环境在创建闭包时将非本地名称绑定到词法环境中的相应变量,此外,它们的生存期至少延长到闭包本身的生存期。当稍后在可能具有不同词法环境的情况下输入闭包时,将使用其非局部变量执行该函数,该非局部变量引用闭包捕获的变量,而不是当前环境。
基于上面的lisp代码,在创建lambda时,我们创建了一个闭包,该闭包的count
变量必须绑定到lambda,从而创建一个无限/循环/自引用。相互递归的定义使这个问题变得更加复杂,letrec也必须支持这种定义。
Elm,是一种纯函数式语言,不支持强制性的状态修改。因此,我相信不可能在Elm中表示自参考值。您可以提供有关在Elm中实施letrec的替代方法的一些指导吗?
Jos von Bakel已在榆树实施mal。请参阅他的笔记here和环境实现here。他竭尽全力以自己的内部GC机制手动构建一个指针系统。尽管此方法有效,但似乎需要进行大量的努力。我渴望一个纯粹的功能实现。
Haskell中的恶意实现(请参见代码here)使用Data.IORef
模拟指针。对我来说,这似乎也很hack。
似乎可以使用Y-Combinator来实现这些自引用。似乎还有一个Data.IORef
也可用于相互递归函数。在我看来,还必须存在一个Z *组合器(等效于Y *但支持Y* Combinator),这在逻辑上是合理的。我是否应该转换所有的eager evaluation model of Elm实例,以便将每个绑定都包裹在Z *周围?]
Y-Combinator对我来说是新手,我的直觉根本不理解它,所以我不确定上述解决方案是否会起作用。
非常感谢您阅读!我为解决这个问题而苦苦挣扎了好几天了。
谢谢!
-Advait
表达式可以在其中看到绑定的绑定构造不需要任何外来的自引用机制。
其工作原理是为变量创建一个环境,然后将值分配给它们。在那些变量已经可见的环境中评估初始化表达式。因此,如果这些表达式碰巧是letrec
表达式,那么它们将捕获该环境,这就是函数之间可以相互引用的方式。
[请注意,如果分配是按从左到右的顺序执行的,并且其中一个lambda恰好在初始化期间被调度,然后碰巧通过一个尚未分配的变量向前调用了一个lambda,这将有问题例如
lambda
[请注意,在R7RS计划报告中,(letrec
([alpha (lambda () (omega)]
[beta (alpha)] ;; problem: alpha calls omega, not yet stored in variable.
[omega (lambda ())])
...)
实际上被记录为是这样工作的。绑定所有变量,然后为其分配值。该文档还规定了有关使用初始化表达式中捕获的延续的限制。