Reduktionsregel für IF?

7

Ich arbeite an Simon Peyton Jones '"Die Implementierung funktionaler Programmiersprachen" und auf Seite 20 sehe ich:

WENN WAHR ((λp.p) 3) ↔ WENN WAHR 3 (pro β-Rot) (1)
                   ↔ (λx.IF TRUE 3 x) (pro η rot) (2)
                   ↔ (λx.3) (3)

Die Schritte 1 bis 2 werden als η-Umwandlung erklärt. Aber von 2 bis 3 heißt es: "Der letzte Schritt ist die Reduktionsregel für IF." Ich bin mir nicht sicher, was diese Reduktionsregel ist.

Galaxienwesen
quelle

Antworten:

10

Die von Ihnen angeforderte Reduktionsregel ist die übliche für IF-Anweisungen. Es besteht aus zwei Berechnungsregeln und einer Kontextregel:

  • IF TRUE a b a

  • IF FALSE a b b

  • aaIF a b cIF a b c

Sowohl in den Einstellungen Call-by-Value (streng) als auch Call-by-Need (faul) können sowohl als auch beliebige Ausdrücke sein. Sie müssen keine Werte sein.ab

Regeln dieser Art, die bestimmte Funktionen (hier IF) reduzieren , werden oft als Delta-Regeln bezeichnet.

Der obige Grundschritt (2) ist nun notwendig, damit die Reduktionsregeln für angewendet werden können. erfordert 3 Argumente, hat aber im ursprünglichen Begriff nur zwei, kann also nicht reduziert werden. ( wird wie jede Funktion in Haskell teilweise angewendet. Dies bedeutet, dass nur ein Teil der Argumente angegeben werden muss.) Die Verwendung von -expansion liefert das zusätzliche Argument, ohne die Semantik zu ändern.IFIFIFη

Dave Clarke
quelle
1
Ich würde hinzufügen IF a b c -> IF a' b c with a-> a'
Fabio F.
Ja, aber sollte die η-Umwandlung keine Bedingungen hinzufügen? Es scheint nicht ganz ehrlich zu sein, von IF TRUE 3 zu λx.IF TRUE 3 x zu wechseln (entschuldigen Sie mein Auslassen von x im ursprünglichen Beitrag) - wenn es dann im nächsten Schritt als konform zur IF-Reduktion verwendet wird -, weil wir hinzugefügt haben das x nur um die quasi ELSE Hälfte zu sein. Was ist zum Beispiel, wenn das Problem WENN FALSCH 3 war ? Könnten wir es in λx.IF FALSE 3 x umwandeln ? Dann wäre Schritt 3 λx.x gewesen , was nicht richtig erscheint ... Seltsam , das hier. Es ging darum zu beweisen, dass WAHR ((λp.p) 3) äquivalent zu (λx.3) ist. Dies hat mich verwirrt.
Galaxienwesen
@galaxybeing: Ich habe einen Kommentar hinzugefügt, warum Sie -expansion verwenden. Letztendlich ist es so, dass IF zwei Argumente hat und daher seine Reduktionsregeln angewendet werden können. η
Dave Clarke
@galaxybeing IF FALSE 3 ist äquivalent zu \x -> IF FALSE 3 x(vorausgesetzt, eine teilweise Anwendung von IFist zulässig). IF FALSE 3braucht ein weiteres Argument, um auf einen Wert reduziert zu werden; Anwendung auf xErträge IF FALSE 3 x, die sich auf einfach reduziert x. Dies IF FALSE 3ist in der Tat gleichbedeutend mit \x -> x, solange wir den untypisierten Lambda-Kalkül verwenden. Wenn Sie dies in Haskell ausprobieren (indem Sie eine Funktion definieren, if' :: Bool -> a -> adamit Sie sie teilweise anwenden können), erhalten Sie die idFunktion, die auf den Typ spezialisiert ist, den Haskell für die 3.
Ben