Digitando il combinatore Y

Question

http: //muaddibspace.blogspot. com / 2008/01 / tipo di inferenza-per-semplicemente-digitato-lambda.html è una definizione sintetica di lambda calcolo semplicemente digitato in Prolog.

Sembra a posto, ma poi si pretende di assegnare un tipo alla Combinator Y ... mentre in un senso molto reale l'intero scopo di aggiungere tipi di lambda calcolo è quello di rifiutare di assegnare un tipo di cose come il combinatore Y .

Qualcuno può vedere esattamente dove il suo errore o - più probabilmente - la mia incomprensione è

Answer 1

Il combinatore Y, nella sua forma di base

Y f = (\x -> f (x x)) (\x -> f (x x))

solo non può essere digitato con il semplice sistema di tipo proposto in questo articolo.

Ci sono altri, molto più facile ma gli esempi significativi che non possono essere digitati a quel livello:

Prendete per esempio.

test f = (f 1, f "Hello")

Questo funziona ovviamente per test (\x -> x) ma non possiamo dare il tipo più alto in classifica che è stato richiesto qui, vale a dire

test :: (∀a . a -> a) -> (Int, String)  

Ma anche in sistemi di tipo più avanzate come le estensioni GHCI di Haskell che consentono quanto sopra, Y è ancora difficile da digitare.

Quindi, data la possibilità di ricorsione, possiamo solo definire e il lavoro utilizzando il fix combinatore

fix f = f (fix f) 

con fix :: (a -> a) -> a

Answer 2

Typing dovrebbe non consentire l'applicazione di sé, non dovrebbe essere possibile trovare un tipo per (t t). Se ove possibile t allora avrebbe un tipo A -> B, e avremmo A = A -> B. Dato che l'applicazione sé è parte di Y combinatore, è anche possibile non invia un tipo ad esso.

Purtroppo molti sistemi Prolog consentono una soluzione per A = A -> B. Questo accade per molti motivi, sia il sistema Prolog consente termini circolari, quindi l'unificazione riusciranno e le associazioni risultanti possono ulteriormente essere elaborato. O il sistema Prolog non consente termini circolari, poi dipende se implementa un controllo verifica. Se la verifica di controllo è attivata, allora l'unificazione non avrà successo. Se la verifica di controllo è disattivata, quindi l'unificazione potrebbe avere successo, ma le associazioni risultanti non può essere ulteriormente elaborati, molto probabilmente portando a impilare troppo pieno nella stampa o ulteriori accorpamenti.

Quindi credo che un'unificazione circolare di questo tipo avviene in codice dato dal sistema Prolog utilizzato e diventa inosservato.

Un modo per risolvere il problema sarebbe quello di uno interruttore sulla verifica di controllo o per sostituire una delle unificazioni verificatisi nel codice una chiamata esplicita a unify_with_occurs_check / 2.

Con i migliori saluti

P.S .: Il seguente codice di prologo funziona meglio:

/**
 * Simple type inference for lambda expression.
 *
 * Lambda expressions have the following syntax:
 *    apply(A,B): The application.
 *    [X]>>A: The abstraction.
 *    X: A variable.
 *
 * Type expressions have the following syntax:
 *    A>B: Function domain
 *
 * To be on the save side, we use some unify_with_occurs_check/2.
 */

find(X,[Y-S|_],S) :- X==Y, !.
find(X,[_|C],S) :- find(X,C,S).

typed(C,X,T) :- var(X), !, find(X,C,S), 
                unify_with_occurs_check(S,T).
typed(C,[X]>>A,S>T) :- typed([X-S|C],A,T).
typed(C,apply(A,B),R) :- typed(C,A,S>R), typed(C,B,T), 
                unify_with_occurs_check(S,T).

Ecco alcune piste di esempio:

Jekejeke Prolog, Development Environment 0.8.7
(c) 1985-2011, XLOG Technologies GmbH, Switzerland
?- typed([F-A,G-B],apply(F,G),C).
A = B > C
?- typed([F-A],apply(F,F),B).
No
?- typed([],[X]>>([Y]>>apply(Y,X)),T).
T = _T > ((_T > _Q) > _Q)