La firma tipo di un combinatore non corrisponde alla firma di tipo della sua funzione lambda equivalente

Question

considerare questo combinatore:

S (S K) 

applicarlo agli argomenti XY:

S (S K) X Y 

Esso si contrae a:

X Y 

Ho convertito S (SK) nei termini Lambda corrispondenti e ottenuto questo risultato:

(\x y -> x y) 

ho usato lo strumento Haskell WinGHCi per ottenere la firma di tipo (\ x y -> x y) ed è restituito:

(t1 -> t) -> t1 -> t 

che ha senso per me.

Successivamente, ho usato WinGHCi per ottenere la firma di tipo s (s k) ed è tornato:

((t -> t1) -> t) -> (t -> t1) -> t 

che non ha senso per me. Perché le firme del tipo sono diverse?

Nota: ho definito s, k, e io come:

s = (\f g x -> f x (g x)) 
k = (\a x -> a) 
i = (\f -> f) 

Answer 1

Grazie a tutti coloro che hanno risposto alla mia domanda. Ho studiato le tue risposte. Per essere sicuro di aver capito cosa ho imparato, ho scritto la mia risposta alla mia domanda. Se la mia risposta non è corretta, per favore fatemelo sapere.

Iniziamo con i tipi di k e s: prima opera

k :: t1 -> t2 -> t1 
    k = (\a x -> a) 

    s :: (t3 -> t4 -> t5) -> (t3 -> t4) -> t3 -> t5 
    s = (\f g x -> f x (g x)) 

Let sulla determing la firma tipo di (s k).

Recall s 's definizione:

s = (\f g x -> f x (g x)) 

Sostituendo k per f risultati in (\f g x -> f x (g x)) amministrazione a:

(\g x -> k x (g x)) 

Importante Il tipo di ge x deve essere coerente con k' s digitare la firma.

Ricordiamo che k ha questo tipo di firma:

k :: t1 -> t2 -> t1 

Quindi, per questa definizione di funzione k x (g x) possiamo dedurre:

• Il tipo di x è il tipo di primo argomento k s' , che è il tipo t1.

• Il tipo di s' k secondo argomento è t2, quindi il risultato di (g x) deve essere t2.

• g ha x come argomento che abbiamo già determinato ha tipo t1. Quindi la firma del tipo di (g x) è (t1 -> t2).

• Il tipo di risultato k s' è t1, quindi il risultato di (s k) è t1.

Così, la firma tipo di (\g x -> k x (g x)) è questo:

(t1 -> t2) -> t1 -> t1 

successivo, k è definito per restituire sempre il suo primo argomento.Quindi questo:

k x (g x) 

contratti a questo:

x 

E questo:

(\g x -> k x (g x)) 

contratti a questo:

(\g x -> x) 

Ok, ora abbiamo capito (s k) :

s k :: (t1 -> t2) -> t1 -> t1 
    s k = (\g x -> x) 

Ora cerchiamo di determinare il tipo di firma s (s k).

Procediamo nello stesso modo.

Recall s 's definizione:

s = (\f g x -> f x (g x)) 

Sostituendo (s k) per f risultati in (\f g x -> f x (g x)) amministrazione a:

(\g x -> (s k) x (g x)) 

Importante Il tipo di g e x devono essere coerenti con (s k)' s digitare la firma.

Ricordiamo che (s k) ha questo tipo di firma:

s k :: (t1 -> t2) -> t1 -> t1 

Quindi, per questa definizione di funzione (s k) x (g x) possiamo dedurre:

• Il tipo di x è il tipo di primo argomento (s k) s' , che è il tipo (t1 -> t2).

• Il tipo di s' (s k) secondo argomento è t1, quindi il risultato di (g x) deve essere t1.

• g ha x come argomento, che abbiamo già determinato ha tipo (t1 -> t2). Quindi la firma del tipo di (g x) è ((t1 -> t2) -> t1).

• Il tipo di risultato (s k) s' è t1, quindi il risultato di s (s k) è t1.

Così, la firma tipo di (\g x -> (s k) x (g x)) è questo:

((t1 -> t2) -> t1) -> (t1 -> t2) -> t1 

In precedenza abbiamo determinato che s k ha questa definizione:

(\g x -> x) 

Cioè, si tratta di una funzione che prende due argomenti e restituisce il secondo.

Pertanto, questo:

(s k) x (g x) 

Contratti a questo:

(g x) 

E questo:

(\g x -> (s k) x (g x)) 

contratti a questo:

(\g x -> g x) 

Ok, ora abbiamo capito s (s k).

s (s k) :: ((t1 -> t2) -> t1) -> (t1 -> t2) -> t1 
    s (s k) = (\g x -> g x) 

Infine, confrontare la firma tipo di s (s k) con la firma tipo di questa funzione:

p = (\g x -> g x) 

Il tipo di p è:

p :: (t1 -> t) -> t1 -> t 

p e s (s k) hanno la stessa definizione (\g x -> g x) quindi perché hanno diversi tipi di firme?

La ragione per cui s (s k) ha una firma di tipo diverso da p è che non ci sono vincoli su p. Abbiamo visto che s in (s k) è vincolato per essere coerente con la firma del tipo di k e che il primo s in s (s k) è vincolato per essere coerente con la firma del tipo di (s k). Quindi, la firma del tipo di s (s k) è vincolata a causa del suo argomento. Anche se p e s (s k) hanno la stessa definizione, i vincoli su g e x differiscono.

Answer 2

Si comincia con i tipi di k e s

k :: t1 -> t2 -> t1 
k = (\a x -> a) 

s :: (t3 -> t4 -> t5) -> (t3 -> t4) -> t3 -> t5 
s = (\f g x -> f x (g x)) 

Quindi passando k come primo argomento di s, abbiamo unificare il tipo con il tipo del primo argomento s e utilizzare s al tipo

s :: (t1 -> t2 -> t1) -> (t1 -> t2) -> t1 -> t1 

quindi otteniamo

s k :: (t1 -> t2) -> t1 -> t1 
s k = (\g x -> k x (g x)) = (\g x -> x) 

Poi nel s (s k), l'esterno s viene utilizzata al tipo (t3 = t1 -> t2, t4 = t5 = t1)

s :: ((t1 -> t2) -> t1 -> t1) -> ((t1 -> t2) -> t1) -> (t1 -> t2) -> t1 

applicazione che per s k gocce il tipo del primo argomento e ci lascia con

s (s k) :: ((t1 -> t2) -> t1) -> (t1 -> t2) -> t1 

Come riassunto: In Haskell, il tipo di s (s k) deriva dai tipi delle sue sottoespressioni costitutive, non dal suo effetto sui suoi argomenti. Pertanto ha un tipo meno generale rispetto all'espressione lambda che denota l'effetto di s (s k).

Answer 3

Il sistema di tipi che si utilizza è fondamentalmente uguale al lambda calcolo semplice (non si utilizzano funzioni ricorsive o tipi ricorsivi). Il lambda calcolo semplicemente tipizzato non è del tutto generale; non è completo di Turing e non può essere usato per scrivere ricorsioni generali.Il calcolo del combinatore SKI è completo di Turing e può essere utilizzato per scrivere combinatori a virgola fissa e ricorsione generale; pertanto, la piena potenza del calcolo del combinatore SKI non può essere espressa nel calcolo lambda semplicemente tipizzato (sebbene possa essere nel calcolo lambda non tipizzato).