Jaki jest typ tej samoczynnej funkcji silni?

Question

Napisałem anonimową funkcję czynnikową w C++ i skompilowałem mój kod za pomocą g ++ 4.9.2. To działa dobrze. Jednak nie znam typu mojej funkcji.

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

Tak, zastanawiam się: jakie są rodzaje fac i self? Gdybym tylko przetłumaczyć kod C++ do Haskell, nie będzie skompilować ponieważ wiąże się nieskończone rodzaje:

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

i muszę zdefiniować pewne rekurencyjnej pracy typ wokół niego:

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 

Tak , dlaczego g ++ może uzyskać dokładnie odpowiedni typ funkcji fac, a jaki typ g ++ jest funkcją fac?

Answer 1

Wyrażenie następujące po auto fac = jest wyrażeniem lambda, a kompilator automatycznie wygeneruje z niego obiekt zamknięcia. Typ tego obiektu jest unikalny i znany tylko kompilatorowi.

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

Typem lambda ekspresji (który jest również rodzaj obiektu zamknięcia) jest unikalnym, nienazwanym typem klasy niezłącznym - zwanym typ zamknięcia - którego właściwości opisano poniżej. Ten typ klasy nie jest agregatem (8.5.1) ani literalnym (3.9). Typ zamknięcia jest zadeklarowany w najmniejszym zakresie bloków, zakresie klasy lub zakresie przestrzeni nazw, który zawiera odpowiadające wyrażeniu lambda :.

Zauważ, że z tego powodu nawet dwa identyczne wyrażenia lambda będą miały różne typy. Na przykład,

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

---

wyrażenia lambda jest C++ 14 generic lambda i będzie tłumaczony przez kompilator do klasy przypominającego następujący:

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

nie mogę komentować w części Haskella, ale powód, dla którego wyrażenie rekurencyjne działa w C++, polega na tym, że po prostu przekazujesz kopię instancji obiektu zamknięcia (fac) w każdym wywołaniu. operator() będący szablonem jest w stanie wydedukować typ lambda, mimo że nie jest to nazwa, którą można nazwać inaczej.

Answer 2

Funkcja C++ fac nie jest funkcją, ale strukturą z funkcją składową.

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

przeciążone operator call ukrywa niektóre oszustwa, że ​​C++ wykonuje w celu realizacji "funkcji lambda"

Kiedy "call" fac, co się dzieje, jest

fac.operator() (fac, 3); 

więc Argument funkcji nie jest samą funkcją, ale obiektem, który ma ją jako element.
Jednym z efektów jest to, że typ funkcji (tj. Typ operator()) nie występuje w typie samej funkcji operator().
(Typ self jest strukturą, która definiuje funkcję.)

Część z szablonem nie jest konieczna do tego działania; to jest non-generic wersja "funkcji" fac:

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

F fac; 
fac(fac, 3); 

Jeśli będziemy szablonu i zmienić operator() do 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); 
} 

widzimy, że praca programu Haskell i Twój program w C++ są bardzo podobne - różnice to głównie interpunkcja.

Natomiast w Haskell

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

selfjest funkcja i typ fac2 „s musiałby być

X -> Int -> Int 

jakiegoś X.
Ponieważ self jest funkcją, a self self $ n-1 to typ Int, self to także X -> Int -> Int.

Ale co może być X?
Musi być taki sam, jak sam typ self, tj. X -> Int -> Int.
Ale oznacza to, że typ self oznacza (zastępując X)

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

więc typ X musi być

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

tak self jest typu musi być

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

i tak dalej, ad infinitum.
Oznacza to, że w Haskell typ byłby nieskończony.

Twoje rozwiązanie dla Haskella zasadniczo jawnie wprowadza niezbędny kierunek, który C++ generuje poprzez swoją strukturę z funkcją składową.

Answer 3

Jak inni zwrócili uwagę, lambda działa jako struktura z szablonem.Powstaje zatem pytanie: dlaczego Haskell nie może wpisać własnej aplikacji, podczas gdy C++ może?

Odpowiedź dotyczy różnicy między szablonami C++ i funkcjami polimorficznymi Haskella. Porównaj te:

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

Chociaż mogą wyglądać niemal równorzędnie, tak naprawdę nie są takie.

Gdy typ Haskella sprawdza powyższą deklarację, sprawdza, czy definicja jest bezpieczna dla dowolnego typu a,b. Oznacza to, że jeśli zastąpimy a,b dowolnymi dwoma typami, funkcja musi być dobrze zdefiniowana.

C++ stosuje inne podejście. Przy definicji szablonu nie jest sprawdzane, czy jakiekolwiek zastąpienie dla a,b będzie poprawne. Ta kontrola jest odroczona do punktu użycia szablonu, tj. W czasie tworzenia. Aby podkreślić punkt, dodajmy +1 w naszym kodzie:

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

Definicja Haskell nie będzie typ kontroli: nie ma gwarancji, można wykonać x+1 gdy x jest z dowolnego typu. Zamiast tego kod C++ jest w porządku. Fakt, że niektóre zamienniki a prowadzą do niepoprawnego kodu, jest teraz nieistotny.

Odroczenie tego czeku powoduje, że niektóre "nieskończenie wpisane wartości" są dozwolone w przybliżeniu. Języki dynamiczne, takie jak Python lub Scheme, dalej odkładają te błędy typu do czasu wykonania, i oczywiście będą dobrze radzić sobie z samo-aplikacją.