Arithmetik mit Kirche Ziffern

StackOverflow https://stackoverflow.com/questions/3912341

Frage

Ich arbeite durch SICP und die Problem 2.6 mich in so etwas wie ein Dilemma gestellt hat. mit Kirche Ziffern im Umgang mit dem Konzept der Codierung Null und 1 beliebige Funktionen zu sein, die bestimmte Axiome erfüllen Sinn zu machen scheint. Zusätzlich Ableiten die direkte Formulierung von Einzelnummern der Definition von Null verwendet wird, und eine Add-1-Funktion ist sinnvoll. Ich verstehe nicht, wie ein Plus-Operator gebildet werden kann.

So weit ich das habe. 

(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))

Beim Blick durch den Wikipedia-Eintrag für Lambda-Kalkül , fand ich, dass die Definition von Plus war PLUS: = ?mnfx.mf (NFX). Mit dieser Definition konnte ich das folgende Verfahren formulieren. 

(define (plus n m)
  (lambda (f) (lambda (x) ((m f) ((n f) x)))))

Was ich nicht verstehe, ist, wie das Verfahren direkt nur die von den zuvor abgeleiteten Verfahren gemachten Angaben unter Verwendung abgeleitet werden kann. Kann jemand in irgendeiner Art von strengem Beweis artiger Form beantwortet das? Intuitiv, ich glaube, ich verstehe, was los ist, aber wie Richard Feynman einmal gesagt: „Wenn ich es nicht bauen kann, kann ich nicht verstehen ...“

War es hilfreich?

Lösung

Es ist eigentlich ziemlich einfach. Dies wird wahrscheinlich als flamebait angesehen werden, aber die Pars machen es schwieriger zu sehen - einen besseren Weg, um zu sehen, was passiert, entweder vorstellen, dass Sie in einer Curry-Sprache sind, oder verwenden Sie einfach die Tatsache, dass Scheme Mehr Argument Funktionen und dass umarmt ... Hier ist eine Erklärung, dass Verwendungen lambda und mehr Argumente wo praktisch:

  • Jede Zahl N ist codiert als 

    (lambda (f x) ...apply (f (f (f ... (f x)))) N times...)

  • Das bedeutet, dass die Codierung von N ist eigentlich 

    (lambda (f x) (f^N x))

    wo f^N ist funktional Potenzierung.

  • Ein einfacher Weg, um diese (unter der Annahme currying) zu sagen: Die Zahl N ist codiert als 

    (lambda (f) f^N)

    so N eigentlich ein ist "potenzieren N" Funktion

  • Ihr Ausdruck nehmen (mit Blick in den lambdas hier): 

    ((m f) ((n f) x))

    da n ist eine Codierung einer Zahl ist, dann ist es, dass Potenzierung, so dass dies eigentlich ist: 

    ((m f) (f^n x))

    und das gleiche gilt für m: 

    (f^m (f^n x))

    und der Rest sollte klar sein ... Sie haben m Anwendungen von f auf n Anwendungen von f angewandt auf x angewendet wird.

  • Schließlich verlassen einige Spaß - hier ist eine andere Art und Weise plus zu definieren: 

    (define plus (lambda (m) (lambda (n) ((m add1) n))))

    (Na ja, nicht zu viel Spaß, da dies eine wahrscheinlich mehr offensichtlich.)

Andere Tipps

(Stellen Sie sicher verstehen Funktionen höherer Ordnung ) . In Alonzo Church 's nicht typisierten Lambda-Kalkül eine Funktion der einzigen primitive Datentyp ist. Es gibt keine Zahlen, Boolesche Werte, Listen oder irgendetwas anderes, nur Funktionen. Funktionen können nur 1 Argument, aber Funktionen übernehmen und / oder Rück Funktionen Nicht Werte dieser Funktionen, sondern Funktionen selbst. Daher zu repräsentieren Zahlen, Boolesche Werte, Listen und andere Arten von Daten, müssen Sie mit einem cleveren Weg für anonyme Funktionen für sie zu stehen kommen. Kirche Ziffern die Art und Weise natürliche Zahlen . Drei primitivsten Konstrukte in nicht typisierten Lambda-Kalkül sind:

  1. λx.x, eine Identitätsfunktion , nimmt eine gewisse Funktion und sofort gibt es zurück.
  2. λx.x x, Selbstanwendung.
  3. λf.λx.f x, Funktionsanwendung, nimmt eine Funktion und ein Argument, und wendet eine Funktion auf ein Argument.

Wie codieren Sie 0, 1, 2, wie nichts anderes, als Funktionen? Wir müssen irgendwie die Vorstellung von Menge in das System zu bauen. Wir haben nur Funktionen, kann jede Funktion nur 1 Argument angewendet werden. Wo können wir etwas wie Menge sehen? Hey, können wir eine Funktion auf einen Parameter mehrfach bewerben! Es ist offensichtlich ein Gefühl der Menge in 3 wiederholten Anrufungen einer Funktion: f (f (f x)). Lassen Sie uns also kodieren sie in Lambda-Kalkül:

  • 0 = λf.λx.x
  • 1 = λf.λx.f x
  • 2 = λf.λx.f (f x)
  • 3 = λf.λx.f (f (f x))

Und so weiter. Aber wie gehen Sie von 0 auf 1 oder von 1 bis 2? Wie würden Sie eine Funktion, dass bei einer Zahl schreiben, würde um 1 erhöht eine Zahl zurückgeben? Wir sehen die Muster in der Kirche Zahlen, dass der Begriff beginnt immer mit λf.λx. und nachdem Sie haben eine begrenzte wiederholte Anwendung von f , so dass wir irgendwie in den Körper λf.λx. erhalten müssen und wickeln Sie es in eine anderen f. Wie Sie ohne Reduktion einen Körper einer Abstraktion ändern? Nun, können Sie eine Funktion anwenden, wickeln den Körper in einer Funktion, dann wickelt die neuen Körper in die alte Lambda-Abstraktion. Aber Sie wollen nicht, Argumente zu ändern, damit Sie Abstraktionen auf die Werte des gleichen Namens gelten. ((λf.λx.f x) f) x → f x, aber ((λf.λx.f x) a) b) → a b, das ist nicht das, was wir brauchen,

Deshalb add1 ist λn.λf.λx.f ((n f) x): Sie n zu f anwenden und dann x den Ausdruck auf den Körper zu reduzieren, dann gelten f zu diesem Körper, dann abstrakt es wieder mit λf.λx.. Übung: zu sehen, dass es wahr ist, schnell lernen ß-Reduktion und reduziert (λn.λf.λx.f ((n f) x)) (λf.λx.f (f x)) zu Schritt 2 von 1.

Sie nun die Intuition das Verständnis des Körpers in einen anderen Funktionsaufruf hinter Einwickeln, wie implementieren wir die Zugabe von 2 Zahlen? Wir brauchen eine Funktion, dass angesichts λf.λx.f (f x) (2) und λf.λx.f (f (f x)) (3) zurückkehren würde λf.λx.f (f (f (f (f x)))) (5). Blick auf 2. Was wäre, wenn Sie ersetzen seine x mit dem Körper 3, das ist f (f (f x))? Um Körper von 3, ist es offensichtlich, gilt es nur f und dann x. Jetzt gelten 2 bis f, aber dann es auf Körper von 3, nicht zu x. dann wrap es in λf.λx. wieder. λa.λb.λf.λx.a f (b f x)

Fazit: So fügen Sie 2 Zahlen a und b zusammen, die beide als Kirche Zeichen dargestellt sind, möchten Sie ersetzen x in a mit dem Körper b, so dass f (f x) + f (f (f x)) = f (f (f (f (f x)))). Um dies zu ermöglichen, gilt a zu f, dann b f x.

Eli Antwort ist technisch korrekt, aber an dem Punkt, da, dass diese Frage der #apply Verfahren gefragt wird eingeführt nicht, ich glaube nicht, dass die Autoren die Schüler das die Kenntnis davon zu haben oder von Begriffen wie currying zu sein der Lage, diese Frage zu beantworten.

Sie ziemlich Führung einer auf die Antwort darauf hindeutet, dass man die Substitutionsmethode anwenden, und dann von dort aus soll man feststellen, dass die Wirkung der Zugabe ist eine Zusammensetzung aus einer Zahl auf die anderen. Zusammensetzung wird ein Konzept wurde in Übung 1.42 eingeführt; und das ist alles, was erforderlich ist, um zu verstehen, wie ein additives Verfahren kann in diesem System arbeiten. 

; The effect of procedure #add-1 on `one`, and `two` was the composition of `f` 
; onto `one` and `f` onto `two`.
;
; one   : (λ (f) (λ (x) (f x)))
; two   : (λ (f) (λ (x) (f (f x))))
; three : (λ (f) (λ (x) (f (f (f x)))))
;
; Thus one may surmise from this that an additive procedure in this system would
; work by composing one number onto the other.
;
; From exercise 1.42 you should already have a procedure called #compose.
;
; With a little trial and error (or just plain be able to see it) you get the
; following solution.

(define (adder n m)
  (λ (f)
    (let ((nf (n f))
          (mf (m f)))
      (compose nf mf))))
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top