哪种编程语言支持以自身为参数的函数？

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

您的OCaml函数需要递归类型，即包含对自身的直接引用的类型。如果在运行-rectypes时指定OCaml，则可以定义此类类型(并具有此类类型的值)。

这里有一个关于您的功能的会话：

$ 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"
#

默认情况下不支持递归类型，因为它们几乎总是编程错误的结果。

Answer 2

我可以写一些例子：

• 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中这样做：

https://ideone.com/E1LkUW

#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的类型，因为将指针类型转换为数据指针类型是无效的。

或者，如注释中的莱申科所示，您可以在包装器中使用相同的模式：

#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)

Answer 3

正如Jeffrey所指出的，如果您激活OCaml，-rectypes可以处理这个问题。默认情况下没有打开它的原因不是因为它是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，推理算法实际上在某种意义上变得“更简单”。当然，这假设将类型表示为允许循环的图(rational树)。