Aritmetica con Chiesa numeri

Question

sto lavorando attraverso SICP, ed il problema 2,6 mi ha messo in una sorta di dilemma. Nel trattare con numeri Church, il concetto di codifica zero e 1 per essere funzioni arbitrarie che soddisfano certi assiomi sembra avere senso. Inoltre, derivando la formulazione diretta dei numeri individuali utilizzando la definizione dello zero, e una funzione aggiuntiva 1 senso. Non capisco come un operatore più può essere formato.

Finora ho questo.

(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)))))

Guardando attraverso la voce di Wikipedia per lambda calcolo , ho scoperto che la definizione di vantaggio era PLUS: = ?mnfx.mf (nfx). Usando questa definizione sono stato in grado di formulare la seguente procedura.

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

Quello che non capisco, è come tale procedura può essere derivata direttamente utilizzando solo le informazioni fornite dalle procedure in precedenza derivati. Qualcuno può rispondere a questo in una sorta di rigorosa prova di come la forma? Intuitivamente, credo di aver capito cosa sta succedendo, ma, come ha detto una volta Richard Feynman, "Se non riesco a costruirlo, non riesco a capirlo ..."

Answer 1

In realtà è piuttosto semplice. Questo sarà probabilmente essere visto come flamebait, ma le parentesi rendere più difficile per vedere - un modo migliore per vedere ciò che accade è uno immagina che sei in una lingua curry, o semplicemente utilizzare il fatto che Scheme dispone di funzioni multi-argomento e abbraccio che ... Ecco una spiegazione che utilizza lambda e argomento più conveniente dove:

• Ogni numero N è codificato come

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

• Questo significa che la codifica di N è effettivamente

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

  dove f^N è elevamento a potenza funzionale.

• Un modo semplice per dire questo (supponendo currying): il numero N è codificato come

  (lambda (f) f^N)
  

  quindi N è in realtà un "raise alla potenza di N" Funzione

• Ora prendete la vostra espressione (guardando dentro le lambdas qui):

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

  poiché n è è una codifica di una serie, è che l'elevamento a potenza, quindi questo è in realtà:

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

  e lo stesso per m:

  (f^m (f^n x))
  

  e il resto dovrebbe essere ovvio ... Hai applicazioni m di f applicati sulle applicazioni n di f applicato su x.

• Infine, per lasciare alcuni divertirsi - Ecco un altro modo per definire plus:

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

  (Beh, non troppo divertente, dal momento che questo è probabilmente più evidente.)

Answer 2

^{(assicurarsi di aver compreso funzioni di ordine superiore ) .} In Alonzo Church 's tipizzato lambda calcolo una funzione è il tipo di dati unica primitiva. Non ci sono numeri, booleani, elenchi o qualsiasi altra cosa, solo funzioni. Le funzioni possono avere solo 1 argomento, ma le funzioni possono accettare e / o valori di ritorno delle funzioni-non di queste funzioni, ma le funzioni di se stessi. Pertanto per rappresentare i numeri, booleani, liste e altri tipi di dati, è necessario trovare un modo intelligente per funzioni anonime a stare per loro. numeri Chiesa è il modo per rappresentare numeri naturali . Tre la maggior parte dei costrutti primitivi in ??lambda calcolo non tipizzate sono:

1. λx.x, una identità funzione , accetta qualche funzione e subito lo restituisce.
2. λx.x x, auto-applicazione.
3. λf.λx.f x, applicazione di funzione, prende una funzione e un argomento, e applica una funzione di un argomento.

Come si codifica 0, 1, 2 come nient'altro che funzioni? Abbiamo in qualche modo bisogno di costruire la nozione di quantità nel sistema. Abbiamo solo funzioni, ogni funzione può essere utilizzata solo per 1 argomento. Dove possiamo vedere qualcosa di simile quantità? Ehi, siamo in grado di applicare una funzione a un parametro più volte! C'è ovviamente un senso di quantità in 3 invocazioni ripetute di una funzione: f (f (f x)). Quindi cerchiamo di codificare in lambda calcolo:

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

E così via. Ma come si fa a passare da 0 a 1, o 1-2? Come si scrive una funzione che, dato un numero, sarebbe restituire un numero incrementato di 1? Vediamo il modello in cifre della Chiesa che il termine inizia sempre con λf.λx. e dopo si dispone di una limitata applicazione ripetuta di f , quindi abbiamo bisogno di ottenere in qualche modo nel corpo di λf.λx. e avvolgerlo in un altro f. Come si fa a cambiare un corpo di un'astrazione senza riduzione? Beh, è ??possibile applicare una funzione, avvolgere il corpo in una funzione, quindi avvolgere il nuovo corpo nel vecchio lambda astrazione. Ma non si vuole argomenti al cambiamento, quindi, di applicare le astrazioni ai valori con lo stesso nome:. ((λf.λx.f x) f) x → f x, ma ((λf.λx.f x) a) b) → a b, che non è quello che ci serve

Ecco perché add1 è λn.λf.λx.f ((n f) x): si applica a n f e poi x per ridurre l'espressione al corpo, quindi applicare f a quel corpo, allora astratto di nuovo con λf.λx.. Esercizio: anche vedere che è vero, imparare in fretta ß-riduzione e ridurre (λn.λf.λx.f ((n f) x)) (λf.λx.f (f x)) di incremento 2 da 1.

Ora comprendere l'intuizione dietro avvolgendo il corpo in un'altra funzione invocazione, come possiamo implementare aggiunta di 2 numeri? Abbiamo bisogno di una funzione che, dato λf.λx.f (f x) (2) e λf.λx.f (f (f x)) (3), restituirà λf.λx.f (f (f (f (f x)))) (5). Guardate 2. E se fosse possibile sostituisci la sua x con il corpo di 3, che è f (f (f x))? Per ottenere il corpo di 3, è ovvio, basta applicarlo al f e poi x. Ora applicare 2 a f, ma poi applicarlo al corpo di 3, di non x. poi wrap in λf.λx. di nuovo:. λa.λb.λf.λx.a f (b f x)

Conclusione: Per aggiungere 2 numeri a e b insieme, entrambi i quali sono rappresentati come numeri della Chiesa, si vuole sostituisci x in a con il corpo di b, in modo che f (f x) + f (f (f x)) = f (f (f (f (f x)))). Per rendere questo accada, si applicano a a f, poi a b f x.

Answer 3

La risposta di Eli è tecnicamente corretta, ma in quanto al punto che la questione viene posta la procedura di #apply non è stato introdotto, non credo che gli autori destinati allo studente di avere una conoscenza di quella o di concetti come currying di essere in grado di rispondere a questa domanda.

Ci hanno praticamente guida uno alla risposta suggerendo che un applicano il metodo di sostituzione, e poi da lì si dovrebbe notare che l'effetto dell'aggiunta è una composizione di un numero sull'altro. La composizione è un concetto è stato introdotto in esercizio 1.42; e questo è tutto ciò che è necessario per capire come una procedura di additivo può lavorare in questo sistema.

; 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))))