Qual è il tipo di questa funzione fattoriale auto-applicante?

Question

Ho scritto una funzione fattoriale anonima in C++ e ho compilato il mio codice con g ++ 4.9.2. Funziona bene. Tuttavia, non conosco il tipo della mia funzione.

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

Quindi, mi chiedo: quali sono i tipi di fac e self? Se ho appena tradurre il codice C++ in Haskell, non si compila perché si tratta di infiniti tipi:

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

e devo definire un certo tipo di lavoro ricorsivo intorno ad esso:

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 

Così , perché g ++ può ottenere esattamente il tipo giusto della funzione fac e che tipo pensa g ++ la funzione fac?

Answer 1

L'espressione successiva a auto fac = è un'espressione lambda e il compilatore genererà automaticamente un oggetto di chiusura. Il tipo di quell'oggetto è unico e conosciuto solo dal compilatore.

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

Il tipo di lambda-espressione (che è anche il tipo dell'oggetto chiusura) è un tipo di classe non unione univoco, senza nome, denominato tipo di chiusura, le cui proprietà sono descritte di seguito. Questo tipo di classe non è né un aggregato (8.5.1) né un tipo letterale (3.9). Il tipo di chiusura è dichiarato nel più piccolo scope, scope della classe o scope del namespace che contiene la corrispondente espressione lambda.

Si noti che a causa di questo, anche due espressioni lambda identiche avranno tipi distinti. Ad esempio,

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

---

tua espressione lambda è un C++ 14 lambda generica, e sarà tradotto dal compilatore a una classe simile al seguente:

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

non posso commentare nella parte Haskell, ma la ragione per cui l'espressione ricorsiva funziona in C++ è perché stai semplicemente passando una copia dell'istanza dell'oggetto di chiusura (fac) in ogni chiamata. Il operator() essendo un modello è in grado di dedurre il tipo di lambda anche se non è uno che si può nominare diversamente.

Answer 2

Il C++ fac non è realmente una funzione, ma una struttura che ha una funzione membro.

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

L'operatore di chiamata overload nasconde alcuni dei trucchi che C++ esegue per realizzare "funzioni lambda"

Quando si "chiama" fac, ciò che accade è

fac.operator() (fac, 3); 

così la l'argomento della funzione non è la funzione stessa, ma un oggetto che lo ha come membro.
Un effetto di ciò è che il tipo di funzione (ovvero il tipo di operator()) non si verifica nel tipo della funzione operator() stessa.
(Il tipo di self è la struttura che definisce la funzione.)

La parte modello non è necessaria per il funzionamento; questa è una versione non generica della "funzione" fac:

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

F fac; 
fac(fac, 3); 

Se manteniamo il modello e rinominiamo 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); 
} 

vediamo che il vostro lavoro programma di Haskell e il vostro programma C++ sono molto simili - le differenze sono principalmente punteggiatura.

Al contrario, in Haskell

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

selfè una funzione ed il tipo fac2 s' dovrebbe essere

X -> Int -> Int 

per qualche X.
Poiché è una funzione e self self $ n-1 è un tipo di Int, self è anche X -> Int -> Int.

Ma cosa potrebbe essere X?
Deve essere uguale al tipo di self stesso, ad esempio X -> Int -> Int.
Ma ciò significa che il tipo di self è (sostituiva X):

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

così il tipo X deve anche essere

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

così self s' tipo deve essere

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

e così via, all'infinito.
Ovvero, in Haskell il tipo sarebbe infinito.

La soluzione per Haskell essenzialmente introduce esplicitamente l'indiretta necessaria che C++ genera attraverso la sua struttura con una funzione membro.

Answer 3

Come altri hanno sottolineato, il lambda agisce come una struttura che coinvolge un modello.La domanda diventa quindi: perché Haskell non può digitare l'auto-applicazione, mentre C++ può?

La risposta si trova sulla differenza tra i modelli C++ e le funzioni polimorfiche di Haskell. Confronta questi:

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

Mentre potrebbero sembrare quasi equivalenti, non sono proprio tali.

Quando il tipo Haskell verifica la dichiarazione precedente, controlla che la definizione sia di tipo sicuro per qualsiasi tipo a,b. Cioè, se sostituiamo a,b con due tipi qualsiasi, la funzione deve essere ben definita.

C++ segue un altro approccio. Alla definizione del modello, non viene verificato che qualsiasi sostituzione per a,b sarà corretta. Questo controllo è differito al punto di utilizzo del modello, cioè al momento dell'istanziazione. Per sottolineare il punto, aggiungiamo un +1 nel nostro codice:

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

La definizione Haskell non digitare controllo: non c'è nessuna garanzia è possibile eseguire x+1 quando x è di un tipo arbitrario. Il codice C++ va bene, invece. Il fatto che alcune sostituzioni di a portano a codice errato è irrilevante al momento.

Il rinvio di questo controllo fa sì che alcuni "valori tipizzati all'infinito" siano consentiti, approssimativamente. I linguaggi dinamici come Python o Scheme rimandano ulteriormente questi errori di tipo fino al momento dell'esecuzione e, naturalmente, gestiranno correttamente l'auto-applicazione.