Eingabe des Y combinator

Question

http: //muaddibspace.blogspot. com / 2008/01 / Typ-Inferenz-for-einfach typisierte-lambda.html eine kurze Definition des einfach typisierten Lambda-Kalkül in Prolog ist.

Es sieht okay, aber dann behauptet er einen Typ der Y-Combinator zuweisen ... während in einem sehr realen Sinn des gesamten Zweck Typen Lambda-Kalkül ist das Hinzufügen zu verweigern, eine Art, die Dinge wie die Y Combinator zuweisen .

Kann mir jemand genau sehen, wo seine Fehler oder - wahrscheinlicher - mein Mißverständnis

Answer 1

Die Y Combinator in seiner Grundform

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

nur kann nicht typisierten unter Verwendung des einfachen Typ System in dem Artikel vorgeschlagen.

Es gibt noch andere, viel einfacher, aber aussagekräftige Beispiele, die nicht auf dieser Ebene eingegeben werden können:

Nehmen Sie z.

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

Das funktioniert natürlich für test (\x -> x) aber wir können nicht der ranghöhere Art geben, die hier erforderlich waren, nämlich

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

Aber auch in fortgeschritteneren Typ Systemen wie die GHCI Erweiterungen von Haskell, die den oben erlauben, Y ist immer noch schwer zu geben.

So, da die Möglichkeit der Rekursion können wir nur definieren und die Arbeit mit dem fix combinator

fix f = f (fix f) 

mit fix :: (a -> a) -> a

Answer 2

Typing sollte Selbst Anwendung nicht zulassen, sollte es nicht möglich sein, eine Art für (t t) zu finden. Wenn es wenn möglich, dann t würde eine Art A -> B haben, und wir würden A = A -> B haben. Teil von Y Combinator, sein auch nicht möglich zu geben, um einen Typ es da Selbst Anwendung.

Leider sind viele Prolog-Systeme erlauben eine Lösung für A = A -> B. Dies geschieht aus vielen Gründen, entweder das Prolog-System ermöglicht Kreis Bedingungen, dann wird die Vereinigung erfolgreich zu sein und die sich daraus ergebenden Bindungen können auch weiterverarbeitet werden. Oder das System Prolog nicht kreisförmig Bedingungen zulässt, dann hängt es davon ab, ob es implementiert eine Überprüfung stattfindet. Wenn die Prüfung erfolgt ist, dann wird Einigung nicht gelingen. Wenn das geschieht Check ausgeschaltet ist, dann könnte die Vereinigung gelingt aber die sich ergebenden Bindungen können nicht weiterverarbeitet werden, höchstwahrscheinlich führenden Überlauf beim Drucken oder weitere Vereinheitlichungen zu stapeln.

Also habe ich eine kreisförmige Vereinigung dieser Art denke, geschieht in dem gegebenen Code durch das verwendete System Prolog und es wird unbemerkt.

Eine Möglichkeit, das Problem zu lösen, würde zu jedem Schalter wird auf der Prüfung erfolgt oder durch einen expliziten Aufruf von unify_with_occurs_check / 2 eine der auftretenden Vereinheitlichungen im Code zu ersetzen.

Mit freundlichen Grüßen

P. S .: Der folgende Prolog-Code funktioniert besser:

/**
 * 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).

Hier sind einige Beispiele läuft:

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)