我正在做一个学术练习（个人成长）。我想找到一些编程语言，它们允许你定义能够接受自己的函数（即指向自己的指针）作为参数。
例如，在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特别感兴趣，因为我知道它有一个全局类型推理系统。我想知道这些函数是否与全局类型推断兼容。因此，我正在寻找具有全局类型推断的任何语言中的这些类型的函数的示例。
在任何语言中，可以使用可变性或递归或两者来调用具有指向自身的指针的函数。基本上，所有传统的图灵完整语言都具有这些功能，因此有很多答案。
真正的问题是如何输入这样的功能。 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调用这个函数时，它实际上通过一个额外的引用来调用它自己。我们可能还会注意到，将我们的函数包装在某种其他类型的值中1）（使用，记录，变体或对象）也将允许您的定义。我们甚至可以将这些额外的辅助类型指定为[@@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）这与委托方法基本相同，在其他答案中显示（包括具有类型推断的语言，如Haskell和OCaml，以及不包含C ++和C＃的语言）。
您的OCaml函数需要递归类型，即包含对其自身的直接引用的类型。如果在运行OCaml时指定-rectypes，则可以定义此类型（并具有此类型的值）。
这是与您的功能的会话：
$ rlwrap ocaml -rectypes
OCaml version 4.06.1
# let rec foo x y = if y < 1 then "hi" else x x (y - 1);;
val foo : ('a -> int -> string as 'a) -> int -> string = <fun>
# foo foo 10;;
- : string = "hi"
#
默认情况下不支持递归类型，因为它们几乎总是编程错误的结果。
正如Jeffrey指出的那样，如果激活-rectypes，OCaml可以处理这个问题。并且默认情况下它没有打开的原因并不是ML样式类型推断的问题，而是它通常对程序员没有帮助（掩盖编程错误）。
即使没有-rectypes模式，您也可以通过辅助类型定义轻松构造等效函数。例如：
type 'a rf = {f : 'a rf -> 'a}
let rec foo x y = if y < 1 then "hi" else x.f x (y - 1)
请注意，这仍然会推断其他所有内容，例如其他函数参数。样品用途：
foo {f = foo} 11
编辑：就ML类型推断而言，具有和不具有-rectypes的算法之间的唯一区别是后者在统一期间省略了发生检查。也就是说，使用-rectypes，推理算法实际上在某种意义上变得“更简单”。当然，这假设合适的类型表示为允许循环的图形（有理树）。
我可以写一些例子：
好的，所以不是你想到的第一种语言，绝对不是一种无痛的方式，但它很有可能。这是C ++而且它就在这里，因为他们说写了你所知道的东西:)哦，我不建议在学术兴趣之外做这件事。
#include <any>
#include <iostream>
void foo(std::any x, int y)
{
std::cout << y << std::endl;
if (y == 0)
return;
// one line, like in your example
//std::any_cast<void (*) (std::any, int)>(x)(x, y - 1);
// or, more readable:
auto f = std::any_cast<void (*) (std::any, int)>(x);
f(x, y - 1);
}
int main()
{
foo(foo, 10);
}
如果演员表太多（而且太丑陋），你可以写一个像波纹管一样的小包装。但最大的优势是性能：你完全绕过std::any重型。
#include <iostream>
class Self_proxy
{
using Foo_t = void(Self_proxy, int);
Foo_t* foo;
public:
constexpr Self_proxy(Foo_t* f) : foo{f} {}
constexpr auto operator()(Self_proxy x, int y) const
{
return foo(x, y);
}
};
void foo(Self_proxy x, int y)
{
std::cout << y << std::endl;
if (y == 0)
return;
x(x, y - 1);
}
int main()
{
foo(foo, 10);
}
和包装器的通用版本（为简洁省略转发）：
#include <iostream>
template <class R, class... Args>
class Self_proxy
{
using Foo_t = R(Self_proxy<R, Args...>, Args...);
Foo_t* foo;
public:
constexpr Self_proxy(Foo_t* f) : foo{f} {}
constexpr auto operator()(Self_proxy x, Args... args) const
{
return foo(x, args...);
}
};
void foo(Self_proxy<void, int> x, int y)
{
std::cout << y << std::endl;
if (y == 0)
return;
x(x, y - 1);
}
int main()
{
foo(foo, 10);
}
您也可以在C中执行此操作：
#include <stdio.h>
typedef void(* dummy_f_type)(void);
void foo(dummy_f_type x, int y)
{
printf("%d\n", y);
if (y == 0)
return;
void (* f) (dummy_f_type, int) = (void (*) (dummy_f_type, int)) x;
f(x, y - 1);
}
int main()
{
foo((dummy_f_type)foo, 10);
}
要避免的陷阱是你不能使用void*作为x的类型，因为将指针类型强制转换为数据指针类型是无效的。
或者，如评论中的leushenko所示，您可以使用与包装器相同的模式：
#include <stdio.h>
struct RF {
void (* f) (struct RF, int);
};
void foo(struct RF x, int y)
{
printf("%d\n", y);
if (y == 0)
return;
x.f(x, y - 1);
}
int main()
{
foo((struct RF) { foo }, 10);
}
https://dotnetfiddle.net/XyDagc
using System;
public class Program
{
public delegate void MyDelegate (MyDelegate x, int y);
public static void Foo(MyDelegate x, int y)
{
Console.WriteLine(y);
if (y == 0)
return;
x(x, y - 1);
}
public static void Main()
{
Foo(Foo, 10);
}
}
https://repl.it/repls/DearGoldenPresses
def f(x, y):
print(y)
if y == 0:
return
x(x, y - 1)
f(f, 10)
最后这是一种功能语言
https://repl.it/repls/PunyProbableKernelmode
(define (f x y)
(print y)
(if (not (= y 0)) (x x (- y 1)))
)
(f f 10)
一种令人难以置信的递归/迭代语言（你所要求的名称）是一种名为Scheme的Lisp方言。查看一本名为SICP的书籍。调用self是一种实现匿名递归的技术。
以下是您的程序在Scheme中的样子：
(define (foo x y)
(if (= y 0) null (x x (- y 1))))
(foo foo 10)
为了完整，Haskell。
newtype U a = U { app :: U a -> a }
foo :: Int -> ()
foo y = f (U f) y
where
f x y | y <= 0 = ()
| otherwise = app x x (y-1)
试：
> foo 10
()
静态类型语言似乎或多或少地做了同样的事情：将函数放入记录中并将其作为参数传递给自身。 Haskell的newtype创建了短暂的“记录”，所以它在运行时确实是函数本身。
动态类型语言只是将self传递给self并完成它。
您可以在支持函数指针的C，支持delegates的C＃和Java中使用Java来实现，您可能需要为要匹配的方法声明自己的@FunctionalInterface。