"Anwendbare Ordnung" und "Normale Ordnung" in der Lambda-Rechnung

14

Anwendbare Reihenfolge: Bewerten Sie die Argumente einer Funktion immer vollständig, bevor Sie die Funktion selbst bewerten, wie z.

(λx.x2(λx.(x+1)  2)))(λx.x2(2+1)) (λx.x2(3)) 32  9

Normale Reihenfolge: Der Ausdruck würde von außen nach innen reduziert, wie -

(λx.x2(λx.(x+1) 2)) (λx.(x+1)   2)2 (2+1)2 32  9

Let M=(λx.y (λx.(x  x) λx.(x  x)))

Warum ist es so, dass in der anwendbaren Reihenfolge Endlosschleife, aber in der normalen Reihenfolge M y ?M
My

URL87
quelle
1
Haben Sie versucht, sie überhaupt zu bewerten? Ist der erste oder der zweite Fall unklar?
Karolis Juodelė
@ KarolisJuodelė: 1st
URL87
1
Sollten nicht die Lambda - Ausdrücke mit Klammern geschrieben werden , um das Ende des ersten Lambda - Ausdrucks und den Anfang des Arguments zu markieren, zum Beispiel:Let M = (λx.y) ((λx.(x x)) λx.(x x))
mattgately

Antworten:

7

(λx.y (λx.(x  x) λx.(x  x)))

λx.(x  x) λx.(x  x)λx.(x  x) λx.(x  x)
λx.(x  x)
Karolis Juodelė
quelle
15

The term you are reducing is (KyΩ) where Ky is the constant function λx.y (it always returns y, ignoring its argument) and Ω=(λx.(xx)λx.(xx)) is a non-terminating term. In some sense Ω is the ultimate non-terminating term: it beta-reduces to itself, i.e. ΩΩ. (Make sure to work it out on paper at least once in your life.)

Applicative order reduction must reduce the argument of the function to a normal form, before it can evaluate the top-level redex. Since the argument Ω has no normal form, applicative order reduction loops infinitely. More generally, for any term M, MΩMΩ, and this is the reduction chosen by the applicative order strategy.

Normal order reduction starts by reducing the top-level redex (because the function Ky is already in normal form). Since Ky ignores its argument, (KyΩ)y in one step. More generally, KyNy for any term N, and this is the reduction chosen by the normal order strategy.

Dieser Fall zeigt ein allgemeineres Phänomen: Die anwendbare Ordnungsreduktion findet immer nur dann eine Normalform, wenn der Term stark normalisiert, wohingegen die normale Ordnungsreduktion immer die Normalform findet, wenn es eine gibt. Dies liegt daran, dass die anwendbare Reihenfolge immer zuerst die vollständigen Argumente bewertet und somit die Gelegenheit verpasst, dass sich herausstellt, dass ein Argument nicht verwendet wird. Die normale Reihenfolge wertet Argumente so spät wie möglich aus und gewinnt immer, wenn sich herausstellt, dass das Argument nicht verwendet wird.

(Die Kehrseite ist, dass die anwendbare Reihenfolge in der Praxis in der Regel schneller ist, da ein Argument relativ selten nicht verwendet wird; wohingegen ein Argument häufig mehrfach verwendet wird und bei anwendbarer Reihenfolge das Argument nur einmal ausgewertet wird. Normal order wertet das Argument so oft aus, wie es verwendet wird, sei es 0, 1 oder mehrmals.)

Gilles 'SO - hör auf böse zu sein'
quelle
Ich nehme an, Sie haben in Absatz 3 einen Tippfehler gemacht. KyNN sollte sein y, richtig? Unabhängig davon +1.
Karolis Juodelė