7

考虑以下 SML 函数：

fn x => x x

这会产生以下错误（新泽西州标准 ML v110.72）：

stdIn:1.9-1.12 Error: operator is not a function [circularity]
  operator: 'Z
  in expression:
    x x

我可以理解为什么这是不允许的——首先，我不确定如何写下它的类型——但这并不是完全荒谬的；例如，我可以将标识函数传递给它并取回它。

这个函数有名字吗？（有没有办法用 SML 来表达？）

4

2 回答 2

7

没有办法用类似 ML 的类型系统的语言来表达这个功能。即使使用 identity 函数，它也不起作用，因为第一个x和第二个 inx x必须是该函数的不同实例，分别是 type(_a -> _a) -> (_a -> _a)和_a -> _a，对于某些 type _a。

事实上，类型系统旨在禁止像

(λx . x x) (λx . x x)

在无类型的 lambda 演算中。在动态类型语言Scheme中，可以编写这个函数：

(define (apply-to-self x) (x x))

并得到预期的结果

> (define (id x) x)
> (eq? (apply-to-self id) id)
#t
于 2012-02-06T15:35:44.220 回答
4

像这样的函数经常在定点组合器中遇到。例如，编写了一种形式的Y 组合λf.(λx.f (x x)) (λx.f (x x))器。定点组合器用于在无类型 lambda 演算中实现一般递归，而无需任何额外的递归构造，这是使无类型 lambda 演算图灵完备的部分原因。

当人们开发简单类型的 lambda 演算，这是一个基于 lambda 演算的简单静态类型系统时，他们发现不再可能编写这样的函数。事实上，在简单类型的 lambda 演算中执行一般递归是不可能的。因此，简单类型的 lambda 演算不再是图灵完备的。（一个有趣的副作用是简单类型的 lambda 演算中的程序总是终止。）

真正的静态类型编程语言（如标准 ML）需要内置递归机制来克服该问题，例如命名递归函数（使用val recor定义fun）和命名递归数据类型。

仍然可以使用递归数据类型来模拟您想要的东西，但它并不那么漂亮。

基本上，你想定义一个像'a foo = 'a foo -> 'a; 但是，这是不允许的。您改为将其包装在数据类型中：datatype 'a foo = Wrap of ('a foo -> 'a);

datatype 'a foo = Wrap of ('a foo -> 'a);
fun unwrap (Wrap x) = x;

基本上Wrap和unwrap用于在 和 之间进行转换'a foo，'a foo -> 'a反之亦然。

每当您需要对其自身调用函数时x x，您必须显式编写(unwrap x) x(or unwrap x x);而不是 即unwrap把它变成一个函数，然后你可以将它应用到原始值。

PS 另一种 ML 语言 OCaml 具有启用递归类型的选项（通常禁用）；如果您使用-rectypes标志运行解释器或编译器，则可以编写类似fun x -> x x. 基本上，在幕后，类型检查器会找出您需要“包装”和“解包”递归类型的位置，然后为您插入它们。我不知道任何具有类似递归类型功能的标准 ML 实现。

于 2012-02-07T05:42:25.890 回答