6

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

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

4

7 回答 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函数是更一般的定点组合器的一个特例。我们可以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 网站是一个很好的资源,它展示了在 OCaml、Scheme 和 Haskell 中定义定点组合器的多种方法。


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

于 2019-04-22T20:23:27.753 回答
4

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

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

于 2019-04-22T06:56:25.600 回答
3

我可以写一些例子:

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

或者,如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)
于 2019-04-22T05:29:18.283 回答
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

编辑:就 ML 类型推断而言,具有和不具有 -rectypes 的算法之间的唯一区别是后者在统一期间省略了发生检查。也就是说,使用 -rectypes 推理算法实际上在某种意义上变得“更简单”了。当然,这假设将类型表示为允许循环的图(有理树)。

于 2019-04-22T09:11:57.777 回答
2

一种对于递归/迭代(您所要求的名称)令人难以置信的语言是一种名为 Scheme 的 Lisp 方言。看看这门语言的 SICP 书。调用 self一种实现匿名递归的技术。

这是您的程序在 Scheme 中的样子:

(define (foo x y)
    (if (= y 0) null (x x (- y 1))))

(foo foo 10)
于 2019-04-22T05:17:27.200 回答
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
()

静态类型语言似乎在做或多或少相同的事情来实现这一点:将函数放入记录中并将其作为参数传递给自身。Haskellnewtype创建了短暂的“记录”,所以它确实是函数本身,在运行时。

动态类型语言只是将 self 传递给 self 并完成它。

于 2019-04-22T11:22:29.353 回答
0

您可以在支持函数指针的 C、支持delegates 的 C# 和 Java 中执行此操作,您可能需要在其中声明自己@FunctionalInterface的方法以匹配方法。

于 2019-04-22T05:40:35.387 回答