Какие языки программирования поддерживают функции, которые принимают себя в качестве аргументов?

Я делаю академическое упражнение (для личностного роста). Я хочу найти языки программирования, которые позволяют вам определять функции, которые могут принимать себя (т.е. указатели на себя) в качестве аргументов.

Например, в JavaScript:

function foo(x, y) {
    if (y === 0) return;
    x(x, y - 1);
}
foo(foo, 10);

Приведенный выше код выполнит foo() ровно 11 раз, прежде чем y достигнет нуля, что приведет к прекращению рекурсии.

Я попытался определить похожую функцию в 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, потому что я знаю, что он имеет глобальную систему вывода типов. Я хочу знать, совместимы ли такие функции с глобальным выводом типов. Таким образом, я ищу примеры этих типов функций на любом языке с глобальным выводом типов.

Источник

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

Веб-сайт Олега Киселева - отличный ресурс, показывающий множество способов определения комбинатора с фиксированной точкой в ​​OCaml, Scheme и Haskell.

1) Это по сути то же самое, что и делегированный подход, который был показан в других ответах (включая языки с выводом типа, такие как Haskell и OCaml, и языки, которые не делают, например C++ и C#).

Источник

Ваша функция 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"
#

По умолчанию рекурсивные типы не поддерживаются, поскольку они почти всегда являются результатом ошибок программирования.

Источник

Как указывает Джеффри, 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 алгоритм вывода фактически становится "проще" в некотором смысле. Конечно, это предполагает подходящее представление типов в виде графов (рациональных деревьев), которое допускает циклы.

Источник

Некоторые примеры, которые я могу написать:

  • C++
  • С
  • C#
  • питон
  • Схема

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 также:

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);
    }
}

питон

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)
Источник

Для полноты, Хаскелл.

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

Языки со статической типизацией, кажется, делают более или менее одно и то же для достижения этой цели: помещают функцию в запись и передают ее себе в качестве аргумента. Хаскеля newtype хотя создает эфемерные "записи", так что это действительно сама функция во время выполнения.

Динамически типизированные языки просто передают себя себе и делают с этим.

Источник

Один язык, который невероятен для рекурсии / итерации (название того, что вы просите) - это диалект Lisp, называемый Scheme. Проверьте книгу под названием SICP для этого языка. Вызов себя - это метод реализации анонимной рекурсии.

Вот как ваша процедура будет выглядеть на схеме:

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

(foo foo 10)
Источник

Вы можете сделать это в C, который поддерживает указатели функций, C#, который поддерживает delegates, и Java, в которой вам может потребоваться объявить @FunctionalInterface для метода, чтобы соответствовать.

Источник
Другие вопросы по тегам