Каков тип этой самоприменимой факториальной функции?

Question

Я написал анонимную факториальную функцию в C++ и скомпилировал свой код с помощью g++4.9.2. Это работает хорошо. Тем не менее, я не знаю тип моей функции.

#include<iostream>
#include<functional>
using std::function;
int main()
{
    //tested at g++ 4.9.2
    //g++ -std=c++1y -o anony anony.cpp
    auto fac = [](auto self,auto n)->auto{
        if(n < 1)
            return 1;
        else 
            return n * self(self,n-1);
    };
    std::cout<<fac(fac,3)<<std::endl;//6
    return 0;
}

Итак, мне интересно: какие бывают fac а также self? Если я просто переведу код C++ на Haskell, он не будет компилироваться, поскольку включает в себя бесконечные типы:

fac2 self 0 = 1
fac2 self n = n * (self self $ n-1)

и я должен определить некоторую рекурсивную работу типа вокруг этого:

data Y a = Y ((Y a)->a->a)
fac2 self 0 = 1
fac2 self n = n * ((applY self self) (n-1))
    where applY (Y f1) f2 = f1 f2
fact2 = fac2 $ Y fac2

Итак, почему g ++ может получить точно правильный тип fac функция, и какой тип G ++ считает fac функция есть?

Answer 1

Выражение следующее auto fac = является лямбда-выражением, и компилятор автоматически сгенерирует из него объект замыкания. Тип этого объекта уникален и известен только компилятору.

От N4296, §5.1.2 / 3 [expr.prim.lambda]

Тип лямбда-выражения (который также является типом объекта замыкания) является уникальным, неименованным типом класса без объединения, называемым типом замыкания, свойства которого описаны ниже. Этот тип класса не является ни агрегатным (8.5.1), ни литеральным типом (3.9). Тип замыкания объявляется в наименьшей области блока, области класса или области пространства имен, которая содержит соответствующее лямбда-выражение.

Обратите внимание, что из-за этого даже два идентичных лямбда-выражения будут иметь разные типы. Например,

auto l1 = []{};
auto l2 = []{}; // l1 and l2 are of different types

---

Ваше лямбда-выражение является обобщенной лямбда-выражением C++14 и будет переведено компилятором в класс, похожий на следующий:

struct __unique_name
{
    template<typename Arg1, typename Arg2>
    auto operator()(Arg1 self, Arg2 n) const
    { 
        // body of your lambda
    }
};

Я не могу комментировать часть Haskell, но причина, по которой рекурсивное выражение работает в C++, заключается в том, что вы просто передаете копию экземпляра объекта замыкания (fac) в каждом звонке. operator() будучи шаблоном, можно определить тип лямбды, хотя это не тот тип, который вы можете назвать иначе.

Answer 2

C++ fac на самом деле это не функция, а структура, которая имеет функцию-член.

struct aaaa // Not its real name.
{
    template<typename a, typename b>
    auto operator()(a self, b n) const
    { 
    }
};

Перегруженный оператор вызова скрывает некоторые хитрости, которые выполняет C++ для реализации "лямбда-функций"

Когда вы "звоните" fac что происходит

fac.operator() (fac, 3);

поэтому аргумент функции - не сама функция, а объект, который имеет ее в качестве члена.
Одним из последствий этого является то, что тип функции (то есть тип operator()) не встречается в типе operator() функционировать сам.
(Тип self это структура, которая определяет функцию.)

Часть шаблона не обязательна для этой работы; это неуниверсальная версия fac "Функция":

struct F
{
    int operator()(const F& self, int n) const
    { 
        // ...
    }
};

F fac;
fac(fac, 3);

Если мы сохраним шаблон и переименуем operator() в applY:

// The Y type
template<typename a>
struct Y
{
    // The wrapped function has type (Y<a>, a) -> a
    a applY(const Y<a>& self, a n) const
    { 
        if(n < 1)
            return 1;
        else 
            return n * self.applY(self, n-1);
    }
};

template<typename a>
a fac(a n)
{
    Y<a> y;
    return y.applY(y, n);
}

мы видим, что ваша рабочая программа на Haskell и ваша программа на C++ очень похожи - различия в основном в пунктуации.

Напротив, в Хаскеле

fac2 self 0 = 1
fac2 self n = n * (self self $ n-1)

self это функция, и fac2 тип должен был бы быть

X -> Int -> Int

для некоторых X,
поскольку self это функция, и self self $ n-1 является Int, self тип также X -> Int -> Int,

Но что могло X быть?
Должен совпадать с типом self сам, т.е. X -> Int -> Int,
Но это означает, что тип self есть (заменяет X):

(X -> Int -> Int) -> Int -> Int  

так типа X также должен быть

(X -> Int -> Int) -> Int -> Int  

так self тип должен быть

((X -> Int -> Int) -> Int -> Int) -> Int -> Int

и так до бесконечности.
То есть в Хаскеле тип был бы бесконечным.

Ваше решение для Haskell по существу явно вводит необходимую косвенность, которую C++ генерирует через свою структуру с помощью функции-члена.

Answer 3

Как указывали другие, лямбда действует как структура, включающая шаблон. Тогда возникает вопрос: почему Haskell не может набирать само-приложение, а C++?

Ответ заключается в разнице между шаблонами C++ и полиморфными функциями Haskell. Сравните это:

-- valid Haskell
foo :: forall a b. a -> b -> a
foo x y = x

// valid C++
template <typename a, typename b>
a foo(a x, b y) { return x; }

Хотя они могут выглядеть почти эквивалентно, на самом деле они не такие.

Когда тип Haskell проверяет вышеупомянутое объявление, он проверяет, является ли определение безопасным для любых типов. a,b, То есть, если мы подставим a,b с любыми двумя типами, функция должна быть четко определена.

С ++ следует другому подходу. При определении шаблона не проверяется, что любая замена a,b будет правильно. Эта проверка откладывается до момента использования шаблона, т.е. во время создания экземпляра. Чтобы подчеркнуть точку зрения, давайте добавим +1 в нашем коде:

-- INVALID Haskell
foo :: forall a b. a -> b -> a
foo x y = x+1

// valid C++
template <typename a, typename b>
a foo(a x, b y) { return x+1; }

Определение Haskell не будет проверять тип: нет гарантии, что вы можете выполнить x+1 когда x имеет произвольный тип. Код C++ в порядке, вместо этого. Тот факт, что некоторые замены a привести к неправильному коду сейчас неактуально.

Откладывание этой проверки приводит к тому, что некоторые "бесконечно типизированные значения" допускаются примерно. Динамические языки, такие как Python или Scheme, дополнительно откладывают эти ошибки типов до времени выполнения и, конечно, прекрасно справятся с самостоятельным применением.