Lambda-Expression-Reduktion.

Question

Ich kann den folgenden Lambda-Expression mit normaler Reihenfolge (Call-by-name) und Anwendungsauftrag (Call-by-value) Reduction) lösen.Ich bekomme immer wieder unterschiedliche Antworten für beide.Dies ist der Lambda-Ausdruck, der mit beiden Techniken reduziert werden muss:

$ (\ lambda f \ x \ ldotp f \ (f \ x)) \ (\ lambda f \ x \ ldotp f \ (f \ x)) \ f \x $

Answer 1

Ich bekomme weiterhin unterschiedliche Antworten für beide.

Sie sollten das gleiche Ergebnis für beide Bestellungen erhalten. Bitte zeigen Sie Ihre Arbeit, damit die Community Ihnen dabei helfen kann, Ihren Fehler zu finden.

Meine Vermutung ist, dass Sie versehentlich ersetzt werden, substituierte $ F $ anstelle von $ x $ gegen Ende, Wenn $ F $ tatsächlich kostenlos ist.

Das korrekte Reduktionsverfahren ist unten gezeigt.

---

$ (\ lambda f \ x \ ldotp f \ (f \ x)) \ (\ lambda f \ x \ ldotp f \ (f \ x)) \ f \ x $

Es gibt keinen Unterschied zwischen normaler Ordnung und anwendender Reihenfolge im ersten Schritt.

$ (\ lambda f \ x \ ldotp f \ (f \ x)) \ ((\ lambda f \ x \ ldotp f \ (f \ x)) \ f ) \ x $

---

In diesem Schritt gibt es einen Unterschied, da der Wert auf, $ (\ lambda f \ x \ ldotp f \ (f \ x)) \ f) $ ist nicht in der Normalform von Beta. Lass es uns ignorieren und zuerst normale Reihenfolge verwenden.

Normale Reihenfolge

$ (\ \ lambda f \ x \ ldotp f \ (f \ x)) \ f) \ (((\ lambda f \ x \ ldotp f \ (f \ x)) \ f) \ x) $

$ (\ lambda x \ ldotp \ f \ (f \ x)) \ (((\ lambda f \ x \ ldotp f \ (f \ x)) \ f ) \ x) $

$ f \ (f \ (((\ lambda f \ x \ ldotp f \ (f \ x)) \ f) \ x)) $ < / p>

$ F \ (f \ (f \ (f \ x))) $

---

Lass uns zum ersten Schritt zurückkehren.

$ (\ lambda f \ x \ ldotp f \ (f \ x)) \ ((\ lambda f \ x \ ldotp f \ (f \ x)) \ f ) \ x $

---

Diese Zeit lasst uns eine anwendbare Reihenfolge verwenden

Anwendungsreihenfolge

$ (\ lambda f \ x \ ldotp f \ (f \ x)) \ (\ lambda x \ ldotp f \ (f \ x)) \ x $

$ (\ lambda x \ ldotp f \ (f \ x)) \ ((\ lambda x \ ldotp f \ (f \ x)) \ x) $

$ (\ lambda x \ ldotp f \ (f \ x)) \ (f \ (f \ x)) $

$ F \ (f \ (f \ (f \ x))) $

---

Mit normaler Reihenfolge haben wir den Ausdruck reduziert:

$ F \ (f \ (f \ (f \ x))) $

Mit einer anwendbaren Reihenfolge haben wir den Ausdruck reduziert zu:

$ F \ (f \ (f \ (f \ x))) $

Die Ergebnisse sind gleich.