哪些编程语言支持以自身为参数的功能？

Question

我正在做一项学术练习（为了个人成长）。我想找到一种编程语言，使您可以定义能够接受自身（即，指向自身的指针）作为参数的函数。

例如，在JavaScript中：

function foo(x, y) {
    if (y === 0) return;
    x(x, y - 1);
}
foo(foo, 10);

上面的代码将在y达到零之前恰好执行11次foo（），从而导致递归终止。

我尝试在OCaml中定义类似的功能，如下所示：

let rec foo x y = if y < 1 then "hi" else x x (y - 1);;

但是它失败并出现类型错误：

Error: This expression has type 'a -> 'b -> 'c
   but an expression was expected of type 'a
   The type variable 'a occurs inside 'a -> 'b -> 'c

我想知道，是否可以在OCaml中定义这样的功能？我对OCaml特别感兴趣，因为我知道它具有全局类型推断系统。我想知道这样的功能是否与全局类型推断兼容。因此，我正在寻找任何具有全局类型推断功能的语言的示例。

Answer 1

可以使用任何具有可变性或递归性或两者兼有的语言来调用带有自身指针的函数。基本上，所有传统的图灵完整语言都具有这些功能，因此有很多答案。

真正的问题是如何键入此类函数。非强类型语言（例如C / C ++）或动态（或逐渐）类型的语言没有意义，因为它们支持某种形式的类型强制，这基本上使这项任务变得微不足道。他们依靠程序员提供类型并将其视为理所当然。因此，我们应该对使用静态类型系统的严格类型语言感兴趣。

如果我们将重点放在OCaml上，那么如果您通过该-rectypes选项，编译器将接受您的定义，该选项将禁用发生检查，不允许使用递归类型。实际上，您的函数类型为('a -> int -> string as 'a) -> int -> string，

 # let foo x y = if y < 1 then "hi" else x x (y - 1);;
 val foo : ('a -> int -> string as 'a) -> int -> string = <fun>

请注意，您不需要rec这里，因为您的函数并不是真正的递归。递归是类型，('a -> int -> string as 'a)在这里as向左扩展到括号​​，即'a = 'a -> int -> string。这是重复出现的，默认情况下，许多编译器不允许使用这样的方程式（即，在方程式的两边出现相同类型变量的方程式，因此进行名称出现检查）。如果禁用此检查，则编译器将允许使用此定义。但是，据观察，发生检查所捕获的错误多于不允许格式正确的程序。换句话说，当触发事件检查时，它更有可能是错误，而不是故意编写类型良好的函数的尝试。

因此，在现实生活中，程序员不愿意将此选项引入其构建系统。好消息是，如果我们稍微修改一下原始定义，则实际上并不需要递归类型。例如，我们可以将定义更改为以下内容，

 let foo x y = if y < 1 then "hi" else x (y - 1)

现在有类型

 val foo : (int -> string) -> int -> string = <fun>

即，它是一个函数，它接受type的另一个函数(int -> string)并返回type 的函数(int -> string)。因此，要运行，foo我们需要给它传递一个递归调用的函数foo，例如

 let rec run y = foo run y

这是递归起作用的地方。是的，我们没有直接将函数传递给自身。取而代之的是，我们为它传递了一个函数，该函数引用foo并在foo调用此函数时实际上通过额外的引用来调用自身。我们可能还会注意到，将函数包装为其他类型的值^1）（使用，记录，变体或对象）也将允许您进行定义。我们甚至可以将那些额外的帮助程序类型指定为[@@unboxed]这样编译器就不会在包装器周围引入多余的装箱。但这是一种作弊。我们仍然不会将函数传递给它自己，而是一个包含该函数的对象（即使编译器优化会从类型系统的角度删除这些额外的间接访问，这些对象仍然是不同的对象，因此发生检查是未触发）。因此，如果我们不想启用递归类型，我们仍然需要一些间接性。让我们坚持最简单的间接形式，即run函数，并尝试推广这种方法。

实际上，我们的run功能是更通用的定点组合器的特定情况。我们可以run使用任何类型的函数进行参数化('a -> 'b) -> ('a -> 'b)，以便它不仅适用于foo：

 let rec run foo y = foo (run foo) y

实际上，让我们为其命名fix，

 let rec fix f n = f (fix f) n

有类型

 val fix : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>

而且，我们仍然可以将其应用于 foo

 # fix foo 10

该奥列格Kiselyov网站是一个很好的资源，可显示定义OCaml中，方案和Haskell的不动点组合子的许多方面。

^1）这基本上与委托方法相同，在其他答案中也显示了这两种方法（两者都包括类型推断的语言，例如Haskell和OCaml，以及没有类型推断的语言，例如C ++和C＃）。