ocaml - 哪些编程语言支持将自身作为参数的函数？

Question

我正在做一个学术练习(为了个人成长)。我想找到允许您定义能够接受自身(即指向自身的指针)作为参数的函数的编程语言。

例如，在 JavaScript 中:

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

上面的代码将在 y 达到零之前执行 foo() 11 次，导致递归终止。

我尝试在 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

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

真正的问题是如何键入这样的函数。 Non strongly typed语言(如 C/C++)或 dynamically (或 gradually )类型没有意义，因为它们启用某种形式的类型强制，这基本上使任务变得微不足道。他们依赖程序员提供一种类型并将其视为理所当然。因此，我们应该对具有静态类型系统的严格类型语言感兴趣。

如果我们将重点放在 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>

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

 let rec run y = foo run y

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

事实上，我们的 run函数是更一般的 fixed-point combinator 的特例.我们可以参数化 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

Oleg Kiselyov web site是一个很好的资源，展示了在 OCaml、Scheme 和 Haskell 中定义定点组合器的多种方法。

1)这与其他答案中显示的委托(delegate)方法基本相同(包括具有类型推断的语言，如 Haskell 和 OCaml，以及不具有类型推断的语言，如 C++ 和 C#)。