Wie wende ich die Regeln der Lambda-Berechnung in Racket an - Schläger, Lambda-Kalkül

Ich versuche, einige der Lambda-Berechnungsfunktionen zu testen, die ich mit Racket geschrieben habe, aber mit den Testfällen nicht viel Glück hatte. Zum Beispiel eine Definition gegeben

; successor function
(define my_succ (λ (one)
(λ (two)
(λ (three)
(two ((one two) three))))))

Ich versuche, es auf 1 2 3 anzuwenden, und erwarte, dass der Nachfolger von 2 3 ist

(((my_succ 1) 2) 3)

logisch ist, da my_succ eine Funktion ist, die ein Argument übernimmt und an eine andere Funktion übergibt, die ein Argument übernimmt, das es an die dritte Funktion übergibt, die ein Argument übernimmt. Aber ich verstehe

application: not a procedure;
expected a procedure that can be applied to arguments
given: 1
arguments.:

Ich habe Googling ausprobiert und viel Code für die Regeln gefunden, jedoch keine Beispiele für die Anwendung dieser Regeln. Wie muss ich die obige Nachfolgerfunktion aufrufen, um sie zu testen?

Antworten:

Sie mischen zwei völlig verschiedene Dinge: Lambda-Ausdrücke und Funktionen in Racket.

1. In Racket können Sie anonyme Funktionen haben, die in der λ-Notation geschrieben werden können (wie (λ(x) (+ x 1)) das gibt den Nachfolger einer ganzen Zahl zurück, so dass ((λ(x) (+ x 1)) 1) kehrt zurück 2),
2. im Reiner Lambda-Kalkül Sie haben nur Lambda-Ausdrücke, die in einer ähnlichen Notation geschrieben werden und als Funktionen interpretiert werden können.

In der zweiten Domäne haben Sie keine natürlichen Zahlen wie 0, 1, 2, ..., aber Sie haben nur Lambda-Ausdrücke und Zahlen als solche darstellen. Zum Beispiel, wenn Sie das sogenannte verwenden Ziffern der KircheSie vertreten (technisch ausgedrückt) kodieren) die Nummer 0 mit dem Begriff Lambda λf.λx.x, 1 mit λf.λx.f x, 2 mit λf.λx.f (f x) und so weiter.

Also die Funktion successor (für mit dieser Kodierung dargestellte Zahlen) entsprechen einem Begriff, der in der Racket-Notation die von Ihnen geschriebene Funktion ist, Sie können ihn jedoch nicht auf Zahlen wie z. B. anwenden 0, 1usw., aber nur zu anderen Lambda-Ausdrücken, das heißt, Sie könnten so etwas schreiben

(define zero (λ(f) (λ (x) x)))   ; this correspond to λf.λx.x

(successor zero)

Das Ergebnis in Racket ist ein Verfahren (es wird gedruckt als: #<procedure>), aber wenn Sie versuchen zu prüfen, ob Ihr Ergebnis korrekt ist, vergleichen Sie es mit der funktionalen Codierung von 1, du wirst etwas seltsames finden. Eigentlich:

(equal? (successor zero) (λ(f) (λ(x) (f x))))

produziert #fWenn Sie zwei Verfahren in Racket vergleichen, erhalten Sie immer false (z. B. (equal? (λ(x)x) (λ(x)x)) produziert #f), es sei denn, Sie vergleichen den Wert "identisch" (im Sinne von "gleiche Speicherzelle")(equal? zero zero) gibt #t). Dies ist darauf zurückzuführen, dass zum korrekten Vergleich zweier Funktionen unendliche Paare von Paaren (Eingang, Ausgang) verglichen werden sollten!

Eine andere Möglichkeit wäre, Lambda-Ausdrücke als eine Art Struktur in Racket darzustellen, so dass Sie Kirchenzahlen sowie "normale" Lambda-Ausdrücke darstellen und eine Funktion definieren können apply (oder besser reduce) die Lambda-Reduktion durchführen.