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

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

6 голосов
/ 22 апреля 2019

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

Например, в 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 ]

6 голосов
/ 22 апреля 2019

На любом языке, который имеет изменчивость, рекурсию или и то и другое, можно вызвать функцию с указателем на себя.По сути, все обычные полные языки Тьюринга обладают такими возможностями, поэтому ответов так много.

Реальный вопрос в том, как печатать такие функции. Не строго типизированные языки (такие как 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 # ).

4 голосов
/ 22 апреля 2019

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

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

3 голосов
/ 22 апреля 2019

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

3 голосов
/ 22 апреля 2019

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

  • 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 heavy. 

#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)
2 голосов
/ 22 апреля 2019

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

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 на Haskell создает эфемерные "записи", так что это действительно сама функция во время выполнения.

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

2 голосов
/ 22 апреля 2019

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

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

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

(foo foo 10)
0 голосов
/ 22 апреля 2019

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

...