哪些编程语言支持将自身作为参数的函数？
Which programming languages support functions that take themselves as arguments?
我正在做学术练习（为了个人成长）。我想找到允许您定义能够接受自身（即指向自身的指针）作为参数的函数的编程语言。
例如，在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 特别感兴趣，因为我知道它有一个全局类型推断系统。我想知道这些函数是否与全局类型推断兼容。因此，我正在寻找具有全局类型推断的 any 语言中这些类型函数的示例。
recursion/iteration（您所要求的名称）令人难以置信的一种语言是 Lisp 的一种方言，称为 Scheme。查看一本名为 SICP 的书，了解该语言。调用自身是一种实现匿名递归.
的技巧
以下是您的过程在 Scheme 中的样子：
(define (foo x y)
(if (= y 0) null (x x (- y 1))))
(foo foo 10)
我可以写一些例子：
- C++
- C
- C#
- Python
- 方案
C++
好的，这不是您想到的第一种语言，而且绝对不是一种轻松的方式，但很有可能。它是 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
您也可以在 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);
}
C#
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);
}
}
Python
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)
您可以在支持函数指针的 C、支持 delegates 的 C# 和 Java 中完成，您可能需要在其中声明自己的 @FunctionalInterface 方法比赛。
您的 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 的算法之间的唯一区别是后者省略了 occurs-统一期间检查。也就是说，在某种意义上，使用 -rectypes 推理算法实际上变成了 "simpler"。当然，这假设类型的适当表示为允许循环的图（有理树）。
为了完整性，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 创建了短暂的 "records"，所以它确实是函数本身，在 运行 时间。
动态类型语言只是将 self 传递给 self 并完成它。
在任何具有可变性或递归性或两者兼有的语言中，都可以使用指向自身的指针来调用函数。基本上，所有传统的图灵完备语言都具有这些特征，因此有很多答案。
真正的问题是如何键入这样的函数。 Non strongly typed languages (like C/C++) or dynamically (or gradually) typed 没有意义，因为它们启用某种形式的类型强制，这基本上使任务变得微不足道。他们依赖于程序员提供类型并将其视为理所当然。因此，我们应该对具有静态类型系统的严格类型语言感兴趣。
如果我们将重点放在 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。这是一个循环，默认情况下，许多编译器不允许这样的等式（即，等式两边出现相同类型变量的等式，因此得名 occurrence check）。如果这个检查被禁用，编译器将允许这个和类似的定义。但是，据观察，出现检查捕获的错误多于不允许格式良好的程序。换句话说，当发生检查被触发时，它更可能是一个错误，而不是故意尝试编写一个类型良好的函数。
因此，在现实生活中，程序员不愿意将此选项引入他们的构建系统。好消息是，如果我们稍微修改一下原始定义，我们真的不需要递归类型。比如我们可以把定义改成下面这样，
let foo x y = if y < 1 then "hi" else x (y - 1)
现在有类型
val foo : (int -> string) -> int -> string = <fun>
即，它是一个接受另一个 (int -> string) 类型函数和 returns 一个 (int -> string) 类型函数的函数。因此，对于 运行 foo 我们需要传递给它一个递归调用 foo 的函数，例如
let rec run y = foo run y
这就是递归发挥作用的地方。是的，我们没有直接将函数传递给它自己。相反，我们向它传递了一个引用 foo 的函数，当 foo 调用此函数时，它实际上通过额外的引用调用了自身。我们可能还会注意到，将我们的函数包装在其他类型的值中1)（使用、记录或变体或对象）也将允许您的定义。我们甚至可以将这些额外的帮助程序类型指定为 [@@unboxed]，这样编译器就不会在包装器周围引入额外的装箱。但这是一种欺骗。我们仍然不会将函数传递给它自己，而是传递一个包含这个函数的对象（即使编译器优化会删除这个额外的间接寻址，从类型系统的角度来看，它们仍然是不同的对象，因此发生检查是未触发）。所以，如果我们不想启用递归类型，我们仍然需要一些间接的方法。让我们坚持使用最简单的间接形式，即 run 函数，并尝试推广这种方法。
其实我们的run函数是一个更一般的fixed-point combinator的特例。我们可以用 ('a -> 'b) -> ('a -> 'b) 类型的任何函数参数化 run，这样它不仅适用于 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#）。
我正在做学术练习（为了个人成长）。我想找到允许您定义能够接受自身（即指向自身的指针）作为参数的函数的编程语言。
例如，在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 特别感兴趣，因为我知道它有一个全局类型推断系统。我想知道这些函数是否与全局类型推断兼容。因此，我正在寻找具有全局类型推断的 any 语言中这些类型函数的示例。
recursion/iteration（您所要求的名称）令人难以置信的一种语言是 Lisp 的一种方言，称为 Scheme。查看一本名为 SICP 的书，了解该语言。调用自身是一种实现匿名递归.
的技巧以下是您的过程在 Scheme 中的样子：
(define (foo x y)
(if (= y 0) null (x x (- y 1))))
(foo foo 10)
我可以写一些例子：
- C++
- C
- C#
- Python
- 方案
C++
好的，这不是您想到的第一种语言，而且绝对不是一种轻松的方式，但很有可能。它是 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
您也可以在 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);
}
C#
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);
}
}
Python
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)
您可以在支持函数指针的 C、支持 delegates 的 C# 和 Java 中完成，您可能需要在其中声明自己的 @FunctionalInterface 方法比赛。
您的 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 的算法之间的唯一区别是后者省略了 occurs-统一期间检查。也就是说，在某种意义上，使用 -rectypes 推理算法实际上变成了 "simpler"。当然，这假设类型的适当表示为允许循环的图（有理树）。
为了完整性，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 创建了短暂的 "records"，所以它确实是函数本身，在 运行 时间。
动态类型语言只是将 self 传递给 self 并完成它。
在任何具有可变性或递归性或两者兼有的语言中，都可以使用指向自身的指针来调用函数。基本上，所有传统的图灵完备语言都具有这些特征，因此有很多答案。
真正的问题是如何键入这样的函数。 Non strongly typed languages (like C/C++) or dynamically (or gradually) typed 没有意义，因为它们启用某种形式的类型强制，这基本上使任务变得微不足道。他们依赖于程序员提供类型并将其视为理所当然。因此，我们应该对具有静态类型系统的严格类型语言感兴趣。
如果我们将重点放在 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。这是一个循环，默认情况下，许多编译器不允许这样的等式（即，等式两边出现相同类型变量的等式，因此得名 occurrence check）。如果这个检查被禁用，编译器将允许这个和类似的定义。但是，据观察，出现检查捕获的错误多于不允许格式良好的程序。换句话说，当发生检查被触发时，它更可能是一个错误，而不是故意尝试编写一个类型良好的函数。
因此，在现实生活中，程序员不愿意将此选项引入他们的构建系统。好消息是，如果我们稍微修改一下原始定义，我们真的不需要递归类型。比如我们可以把定义改成下面这样，
let foo x y = if y < 1 then "hi" else x (y - 1)
现在有类型
val foo : (int -> string) -> int -> string = <fun>
即，它是一个接受另一个 (int -> string) 类型函数和 returns 一个 (int -> string) 类型函数的函数。因此，对于 运行 foo 我们需要传递给它一个递归调用 foo 的函数，例如
let rec run y = foo run y
这就是递归发挥作用的地方。是的，我们没有直接将函数传递给它自己。相反，我们向它传递了一个引用 foo 的函数，当 foo 调用此函数时，它实际上通过额外的引用调用了自身。我们可能还会注意到，将我们的函数包装在其他类型的值中1)（使用、记录或变体或对象）也将允许您的定义。我们甚至可以将这些额外的帮助程序类型指定为 [@@unboxed]，这样编译器就不会在包装器周围引入额外的装箱。但这是一种欺骗。我们仍然不会将函数传递给它自己，而是传递一个包含这个函数的对象（即使编译器优化会删除这个额外的间接寻址，从类型系统的角度来看，它们仍然是不同的对象，因此发生检查是未触发）。所以，如果我们不想启用递归类型，我们仍然需要一些间接的方法。让我们坚持使用最简单的间接形式，即 run 函数，并尝试推广这种方法。
其实我们的run函数是一个更一般的fixed-point combinator的特例。我们可以用 ('a -> 'b) -> ('a -> 'b) 类型的任何函数参数化 run，这样它不仅适用于 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#）。