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

Я написал анонимную факториальную функцию в С++ и скомпилировал свой код с 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? Если я просто переведю код С++ в 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?

Ответ 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

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

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

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

Ответ 2

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

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

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

Когда вы вызываете 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 и ваша С++-программа очень похожи - различия в основном являются пунктуацией.

Напротив, в Haskell

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

и т.д., ad infinitum.
То есть, в Haskell тип будет бесконечным.

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

Ответ 3

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

Ответ лежит на различии между шаблонами С++ и полиморфными функциями 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. Эта проверка откладывается до точки использования шаблона, то есть во время создания. Чтобы подчеркнуть смысл, добавим в наш код a +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 имеет произвольный тип. Вместо этого код на С++. Тот факт, что некоторые подстановки a приводят к некорректному коду, сейчас не имеет значения.

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