哪些编程语言支持以函数自身作为参数的函数?

6

我正在进行一项学术练习(为了个人成长)。我想要寻找可以定义函数并接受自身作为参数的编程语言(即,指向自身的指针)。

例如,在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,因为我知道它有全局类型推断系统。我想知道这样的函数是否兼容全局类型推断。因此,我正在寻找具有全局类型推断的任何语言中这些类型的函数示例。


允许您定义能够接受自身(即指向自身的指针)作为参数的函数的语言:Machine。Mel的故事 - Mars
7个回答

7
在任何具有可变性或递归性或两者都具备的语言中,都可以使用指向自身的指针调用函数。基本上,所有传统的图灵完备语言都具备这些特征,因此有很多答案。
真正的问题是如何为这样的函数定义类型。非强类型语言(如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>

即,它是一个接受另一个类型为(int -> string)的函数并返回类型为(int -> string)的函数。因此,要运行foo,我们需要传递一个递归调用foo的函数,例如:
 let rec run y = foo run y

这就是递归发挥作用的地方。是的,我们没有直接将函数传递给自身。相反,我们传递了一个引用foo的函数,当foo调用此函数时,它实际上通过额外的引用调用了自身。我们还可以注意到,将我们的函数包装在某种其他类型的值中1)(使用记录、变体或对象)也将允许您的定义。我们甚至可以指定那些额外的辅助类型为[@@unboxed],以便编译器不会在包装器周围引入额外的装箱。但这是一种欺骗。我们仍然不会将函数传递给自己,而是传递一个包含此函数的对象(即使编译器优化将从类型系统的角度删除此额外的间接引用,这些仍然是不同的对象,因此不会触发出现检查)。因此,如果我们不想启用递归类型,我们仍然需要一些间接引用。让我们坚持最简单的间接引用形式,即run函数,并尝试推广这种方法。
实际上,我们的run函数是更一般的不动点组合子的一个特殊情况。我们可以使用任何类型为('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网站是一个非常好的资源,展示了在OCaml、Scheme和Haskell中定义不动点组合子的许多方法。


1)这本质上与委托方法相同,其他回答中已经展示了这种方法(包括具有类型推断功能的语言,如Haskell和OCaml,以及不具有该功能的语言,如C++和C#)。


当然,在没有递归 let 的语言中定义固定点组合器仍然需要自我应用,这将使您回到原点。另一件事是,间接步骤仍然是一个间接步骤,无论是使用类似于“运行”的递归定义,还是使用记录或递归类型 - 无论是命名的,如Haskell(U a〜U a-> a),还是未命名的,OCaml风格(t〜t-> a)。你知道那句话,“没有什么是不能用一步间接解决的!”(我的措辞):)从足够远的距离看,它们之间没有太大的区别。 - Will Ness
OCaml...如果您传递-rectypes选项,将禁用出现检查。谢谢。我一直想知道为什么需要“rec”,但从未知道原因。现在它有了意义,每次我键入“rec”时,我都会永远想起这个答案。您已经通过该语句将自己变成了虚拟雕像。 - Guy Coder

4
您的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"
#

默认情况下不支持递归类型,因为它们几乎总是由编程错误引起的。


那么有了那个标志,OCaml会自动推断递归类型吗? - Will Ness
@WillNess,是的。 - Andreas Rossberg
@AndreasRossberg,太酷了!谢谢。在Haskell中,我们必须手动完成所有标记/取消标记,使用特殊目的的递归类型。你正在使用的{f = foo}语法是什么?你的rf类型是记录类型吗?x.f访问它的f字段吗?(我猜对了吗?) :) - Will Ness
1
@WillNess,你猜对了。在Ocaml中,这种松散的出现检查甚至曾经是默认行为,直到1997年的1.05版本才被更改,但由于用户抱怨而进行了更改。 - Andreas Rossberg

3

正如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

编辑: 就机器学习类型推断而言,使用-rectypes算法与不使用的唯一区别在于后者在统一过程中省略了出现检查。也就是说,在使用-rectypes情况下,推断算法实际上变得更“简单”了。当然,这要求类型的适当表示为允许循环的图形式(有理树)。


3

我可以写一些示例:

  • C++
  • C
  • C#
  • Python
  • Scheme

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

或者,正如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)

Scheme

这是一门函数式编程语言。

https://repl.it/repls/PunyProbableKernelmode

(define (f x y)
  (print y)
  (if (not (= y 0)) (x x (- y 1)))
)

(f f 10)

@WillNess 是的,谢谢 :). 我想你可以编写一个小包装器来隐藏其实现中的转换。但是你不能使用 std::function,因为你会陷入递归类型声明的问题,除非你像 C 版本那样做一些事情,例如 std::function<void(void)>,在这种情况下,你又回到了转换。 - bolov
@WillNess 如果一个类是指针或引用类型,那么它可以包含一个自身类型的成员。例如,class X 可以包含一个成员 X&X*,但不能是 X(因为需要无限的空间来存储它)。你可以参考 CRTP。但它并不适用于我们的情况。[cont] - bolov
我的意思是:在 C++ 中,函数有一个类型,其中包含它的参数类型。因此,您不能拥有一个接受其本身类型的函数,因为您无法声明这样的函数:您将进入无限声明,例如:f 是一个函数,它接受一个类型为函数的参数,该函数接受一个类型为函数的参数,该函数接受一个类型为函数的参数...。模板无法解决此问题。这就是为什么我们需要一些与 f 的类型声明无关的其他类型,但可以转换为 f 的原因。 - bolov
在 C 中也不需要使用类型转换,您可以使用与上面的 ML 示例相同的辅助类型模式。(类型转换并不是如何在保持静态类型的情况下完成此操作的示例)。 - Alex Celeste
1
为什么在C语言中,void (*)()表示函数调用的迂回方式?void (*)()是一个指向可以接受任意数量的参数的函数的指针。在线尝试! - user3003999
显示剩余8条评论

2
一个非常适用于递归/迭代(你所询问的内容)的语言是Lisp的方言之一——Scheme。如果想要学习,可以看看《计算机程序的构造和解释》(SICP)这本书。在Scheme中,调用自己即为实现匿名递归的技巧。
下面是在Scheme中实现该过程的代码:
(define (foo x y)
    (if (= y 0) null (x x (- y 1))))

(foo foo 10)

1
Scheme有点作弊,因为它既没有静态类型,也没有全局类型推断。我相信,问题实际上并不是关于是否可能将函数传递给自身(这很简单),而是(推断)此类函数的类型。这并不容易。 - ivg

2

为了完整起见,提供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传递给自己即可完成。

Original Answer翻译成"最初的回答"


0

你可以使用支持函数指针的 C 语言,支持委托的 C# 语言,或者在 Java 中声明自己的 @FunctionalInterface 来匹配方法。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接