Wie kann ich definieren, y-combinator, ohne "lass rec"?

Question

In fast allen Beispielen, ein y-combinator in ML-Typ von Sprachen ist wie folgt geschrieben:

let rec y f x = f (y f) x
let factorial = y (fun f -> function 0 -> 1 | n -> n * f(n - 1))

Dies funktioniert wie erwartet, aber es fühlt sich an wie Betrug zum definieren der y-combinator mit let rec ....

Ich möchte definieren, diese combinator ohne die Verwendung von Rekursion, mit der standard-definition:

Y = λf·(λx·f (x x)) (λx·f (x x))

Eine direkte übersetzung ist wie folgt:

let y = fun f -> (fun x -> f (x x)) (fun x -> f (x x));;

Aber F# beschwert, dass Sie es nicht herausfinden können, die Arten:

  let y = fun f -> (fun x -> f (x x)) (fun x -> f (x x));;
  --------------------------------^

C:\Users\Juliet\AppData\Local\Temp\stdin(6,33): error FS0001: Type mismatch. Expecting a
    'a    
but given a
    'a -> 'b    
The resulting type would be infinite when unifying ''a' and ''a -> 'b'

Wie Schreibe ich den y-combinator in F# ohne Verwendung let rec ...?

Answer 1

Als Compiler weist darauf hin, gibt es keine Art, die so x zugeordnet werden kann, dass der Ausdruck (x x) ist gut getippt (dies ist nicht ganz richtig, man kann explizit x als obj->_ geben - meinen letzten Absatz). Sie können dieses Problem umgehen, indem Sie einen rekursiven Typ deklarieren, so dass ein sehr ähnlicher Ausdruck funktioniert:

type 'a Rec = Rec of ('a Rec -> 'a)

Nun kann der Y-Combinator wie folgt geschrieben werden:

let y f =
  let f' (Rec x as rx) = f (x rx)
  f' (Rec f')

Leider werden Sie feststellen, dass dies nicht sehr nützlich, weil F # eine strenge Sprache, so dass jede Funktion, dass Sie versuchen, diesen combinator zu definieren verwendet, wird einen Stapelüberlauf verursachen. Stattdessen müssen Sie die applicative Ordnung Version des Y-Combinator (\f.(\x.f(\y.(x x)y))(\x.f(\y.(x x)y))) verwenden:

let y f =
  let f' (Rec x as rx) = f (fun y -> x rx y)
  f' (Rec f')

Eine andere Möglichkeit wäre explizite Faulheit zu verwenden, um die normale Ordnung Y-Combinator zu definieren:

type 'a Rec = Rec of ('a Rec -> 'a Lazy)
let y f =
  let f' (Rec x as rx) = lazy f (x rx)
  (f' (Rec f')).Value

Dies hat den Nachteil, dass rekursive Funktionsdefinitionen nun eine explizite Kraft des faulen Wertes benötigen (die Value Eigenschaft verwenden):

let factorial = y (fun f -> function | 0 -> 1 | n -> n * (f.Value (n - 1)))

Sie hat jedoch den Vorteil, dass Sie nicht-Funktion rekursive Werte definieren können, wie Sie kann in einer faulen Sprache:

let ones = y (fun ones -> LazyList.consf 1 (fun () -> ones.Value))

Als letzte Alternative können Sie besser versuchen, die nicht typisierten Lambda-Kalkül nähern durch Boxen mit und einziehe. Dies würden Sie (wieder mit der applicative Ordnung Version des Y-Combinator):

let y f =
  let f' (x:obj -> _) = f (fun y -> x x y)
  f' (fun x -> f' (x :?> _))

Dies hat den offensichtlichen Nachteil, dass sie nicht mehr benötigte Boxen verursacht und Unboxing, aber zumindest ist dies ganz im Innern der Umsetzung und wird nie wirklich zum Scheitern zur Laufzeit führen.

Answer 2

Ich würde sagen, es ist unmöglich, und fragte, warum, würde ich handwave und berufen sich auf die Tatsache, dass einfach typisierten Lambda-Kalkül hat die Normalisierung Eigenschaft . Kurz gesagt, alle Bedingungen des einfach typisierten Lambda-Kalkül beenden (folglich kann Y nicht in dem einfach typisierten Lambda-Kalkül definiert werden).

F # 's-Typ-System ist nicht genau die Art von System einfach Lambda-Kalkül getippt, aber es ist nah genug. F # ohne let rec kommt wirklich nah an das einfach Lambda-Kalkül getippt - und zu wiederholen, in dieser Sprache Sie nicht einen Begriff definieren, der nicht enden, und das schließt die Definition zu Y.

Mit anderen Worten, in F #, „lassen Sie rec“ Bedarf eine Sprache primitiv sein, zumindest aber, denn selbst wenn Sie sind in der Lage mich von den anderen Primitiven zu definieren, würden Sie nicht in der Lage sein, diese Definition zu geben. es als eine primitive ermöglicht, unter anderem, einer besonderen Art zu dieser primitiv.

geben

EDIT: KVB zeigt in seiner Antwort, dass Typdefinitionen (eines des Merkmals aus dem einfach eingegeben Lambda-Kalkül fehlen aber in let-rec-less F #) ermöglicht eine Art von Rekursion zu bekommen. Sehr clever.

Answer 3

Fall und lassen Aussagen in ML Derivate sind, was macht es Turing, ich glaube, Sie sind basierend auf die System-F und nicht einfach getippt, aber der Punkt ist derselbe.

System F nicht finden können, eine Art für jeden festen Punkt combinator, wenn es könnte, es war nicht stark normalisierend.

Was stark Normalisierung bedeutet, dass jeder Ausdruck hat genau eine normale form, wo eine normale form ist ein Ausdruck, der nicht mehr weiter reduzieren, dies unterscheidet sich von nicht typisierten, wo jeder Ausdruck hat bei max eine normale form, es können auch keine normale form bei allen.

Wenn typed lambda calculi bauen konnten, einen festen Punkt-operator in was immer, es war durchaus möglich, einen Ausdruck zu haben, die keine normale form.

Ein weiteres berühmtes theorem, das Halteproblem ist, impliziert, dass stark die Normalisierung der Sprachen sind nicht Turing-vollständig, Sie sagt, das ist unmöglich entscheiden (anders als die beweisen) von einer turing-vollständigen Sprache, was Teil seiner Programme wird halt auf das, was input.Wenn Sie eine Sprache ist stark normalisierend, es ist entscheidbar, wenn es angehalten wird, nämlich immer halte.Unser Algorithmus um zu entscheiden, dies ist das Programm: true;.

Um dies zu lösen, ML-Derivate erweitern Sie System-F mit Fall und lassen (rec), um diese zu überwinden.Funktionen können somit beziehen sich in Ihren Definitionen wieder, so dass Sie in der Wirkung kein lambda calculi überhaupt nicht mehr, ist es nicht mehr möglich, die verlassen sich auf anonyme Funktionen allein für alle berechenbaren Funktionen.So können Sie wieder in eine Endlosschleife Gerät und wieder Ihre turing-Vollständigkeit.

Answer 4

Kurze Antwort:. Sie können nicht

Lange Antwort: Das einfach typisierten Lambda-Kalkül ist stark Normalisieren. Dies bedeutet, es ist Turing nicht gleichwertig. Der Grund dafür kocht im Grunde auf die Tatsache, dass ein Y Combinator entweder primitiv oder rekursiv definiert sein muss (wie Sie gefunden haben). Es kann einfach nicht im System F (oder einfacher typisierten Kalküle) ausgedrückt werden. Es gibt keinen Weg, um diesen (es ist nachgewiesen worden, nachdem alle). Die Y-Combinator Sie können implementieren funktioniert genau so, wie Sie wollen, though.

Ich würde vorschlagen, Sie Schema versuchen, wenn Sie einen echten Kirche Stil Y Combinator wollen. Verwenden Sie die applicative Version oben angegebenen, als andere Versionen werden nicht funktionieren, wenn Sie nicht ausdrücklich Faulheit hinzufügen, oder verwenden Sie einen faulen Scheme-Interpreter. (Schema technisch nicht vollständig untypisierten, aber es ist dynamisch typisiert, was dafür gut genug ist.)

Sehen Sie diese für den Nachweis der starken Normalisierung: http://citeseerx.ist.psu.edu/viewdoc/summary ? doi = 10.1.1.127.1794

Nach etwas mehr zu denken, ich ist ziemlich sicher, dass ein primitiven Y Combinator fügt hinzu, dass verhält sich genau so, wie der letrec definierte man tut macht System F Turing abgeschlossen. Alles, was Sie tun müssen, dann eine Turing-Maschine zu simulieren und eine Verschiebung (positionieren Sie den Kopf) das Band als eine ganze Zahl (in binär interpretiert) implementieren.