Discussione combinatore in "The Little Schemer"

Question

Così, ho passato molto tempo a leggere e rileggere la fine del capitolo 9 in The Little Schemer, dove il combinatore applicativo Y è stato sviluppato per la funzione length . Credo che la mia confusione si riduce ad una singola istruzione che contrasta due versioni di lunghezza (prima che il combinatore è scomposto out):

A: 
    ((lambda (mk-length) 
    (mk-length mk-length)) 
    (lambda (mk-length) 
    (lambda (l) 
     (cond 
     ((null? l) 0) 
     (else (add1 
       ((mk-length mk-length) 
       (cdr l)))))))) 

B: 
((lambda (mk-length) 
     (mk-length mk-length)) 
    (lambda (mk-length) 
     ((lambda (length) 
     (lambda (l) 
      (cond 
      ((null? l) 0) 
      (else (add1 (length (cdr l))))))) 
     (mk-length mk-length)))) 

Page 170 (4th ed.) afferma che un

restituisce una funzione quando abbiamo applicato a un argomento

mentre B

non Ret urna una funzione

producendo così un regresso infinito di auto-applicazioni. Sono sconcertato da questo. Se B è tormentato da questo problema, non vedo come A lo eviti.

Answer 1

Ottima domanda. Per il beneficio di quelli senza un'installazione DrRacket funzionante (me compreso) cercherò di rispondere.

In primo luogo, usiamo nomi sane, facilmente tracciabili da un occhio/mente umana:

((lambda (h)  ; A. 
    (h h))   ; apply h on h 
(lambda (g) 
    (lambda (lst) 
     (if (null? lst) 0 
     (add1 
       ((g g) (cdr lst))))))) 

Il primo termine lambda è ciò che è noto come omega combinator. Se applicato a qualcosa, causa l'autoapplicazione di quel termine. Così il sopra è equivalente a

(let ((h (lambda (g) 
      (lambda (lst) 
      (if (null? lst) 0 
       (add1 ((g g) (cdr lst)))))))) 
    (h h)) 

Quando h viene applicato sulla h, nuova associazione è formato:

(let ((h (lambda (g) 
      (lambda (lst) 
      (if (null? lst) 0 
       (add1 ((g g) (cdr lst)))))))) 
    (let ((g h)) 
    (lambda (lst) 
      (if (null? lst) 0 
       (add1 ((g g) (cdr lst))))))) 

Ora non c'è niente di applicare più, quindi l'interno lambda modulo viene restituito - insieme con il collegamenti nascosti ai frame dell'ambiente (cioè quelli lasciano vincoli) sopra di esso.

Questo abbinamento di un'espressione lambda con il suo ambiente di definizione è noto come closure. Per il mondo esterno è solo un'altra funzione di un parametro, lst. Non ci sono più passaggi di riduzione da eseguire al momento.

Ora, quando verrà chiamata tale chiusura, la nostra funzione list-length, l'esecuzione arriverà al punto di applicazione automatica (g g) e verranno eseguiti nuovamente gli stessi passaggi di riduzione descritti sopra. Ma non prima.

---

Ora, di quel libro gli autori vogliono arrivare al combinatore Y, in modo da applicare alcune trasformazioni di codice sulla prima espressione, di organizzare in qualche modo per che l'auto-applicazione (g g) essere effettuato automaticamente - così possiamo scrivere l'applicazione funzione ricorsiva in modo normale, (f x), invece di dover scrivere come ((g g) x) per tutte le chiamate ricorsive:

((lambda (h)  ; B. 
    (h h))   ; apply h on h 
(lambda (g) 
    ((lambda (f)   ; 'f' to become bound to '(g g)', 
     (lambda (lst) 
     (if (null? lst) 0 
      (add1 (f (cdr lst)))))) ; here: (f x) instead of ((g g) x)! 
    (g g))))      ; (this is not quite right) 

Ora, dopo pochi passi di riduzione arriviamo

(let ((h (lambda (g) 
      ((lambda (f)  
       (lambda (lst) 
       (if (null? lst) 0 
        (add1 (f (cdr lst)))))) 
      (g g))))) 
    (let ((g h)) 
    ((lambda (f) 
     (lambda (lst) 
      (if (null? lst) 0 
       (add1 (f (cdr lst)))))) 
    (g g)))) 

che equivale a

(let ((h (lambda (g) 
      ((lambda (f)  
       (lambda (lst) 
       (if (null? lst) 0 
        (add1 (f (cdr lst)))))) 
      (g g))))) 
    (let ((g h)) 
    (let ((f (g g)))   ; problem! (under applicative-order evaluation) 
     (lambda (lst) 
      (if (null? lst) 0 
       (add1 (f (cdr lst)))))))) 

E qui arriva guai: l'auto-applicazione di (g g) viene eseguita troppo presto, prima che che lambda interno può essere anche restituito, come chiusura, al run- sistema temporale. Vogliamo solo ridurlo quando l'esecuzione è arrivata a quel punto all'interno di l'espressione lambda, dopo che è stata chiamata la chiusura. Ridurlo prima della creazione della chiusura è ridicolo. A errore sottile. :)

Naturalmente, poiché g è tenuto a h, (g g) si riduce a (h h) e siamo di nuovo al punto di partenza, applicando h su h. Looping.

---

Naturalmente gli autori ne sono consapevoli. Vogliono lo us per capirlo.

Così il colpevole è semplice - è applicative order of evaluation: valutare l'argomento prima il legame è formato parametro formale della funzione e il valore del suo argomento.

Questa trasformazione del codice non era del tutto corretta. Avrebbe funzionato con lo normal order dove gli argomenti non sono stati valutati in anticipo.

Questa è risolto abbastanza facilmente "eta-expansion", che ritarda l'applicazione fino al punto di chiamata effettiva: (lambda (x) ((g g) x)) dice in realtà: "volontà chiamata ((g g) x) quando chiamato con un argomento di x".

E questo è in realtà ciò che il codice di trasformazione avrebbe dovuto essere, in primo luogo:

((lambda (h)  ; C. 
    (h h))   ; apply h on h 
(lambda (g) 
    ((lambda (f)   ; 'f' to become bound to '(lambda (x) ((g g) x))', 
     (lambda (lst) 
     (if (null? lst) 0 
      (add1 (f (cdr lst)))))) ; here: (f x) instead of ((g g) x) 
    (lambda (x) ((g g) x))))) 

Ora che passo di riduzione successiva può essere eseguita:

(let ((h (lambda (g) 
      ((lambda (f)  
       (lambda (lst) 
       (if (null? lst) 0 
        (add1 (f (cdr lst)))))) 
      (lambda (x) ((g g) x)))))) 
    (let ((g h)) 
    (let ((f (lambda (x) ((g g) x)))) 
     (lambda (lst) 
      (if (null? lst) 0 
       (add1 (f (cdr lst)))))))) 

e la chiusura (lambda (lst) ...) è formato e restituito senza problemi e quando viene chiamato (f (cdr lst)) (all'interno della chiusura) viene ridotto a ((g g) (cdr lst)) proprio come lo volevamo.

---

Infine, notiamo che (lambda (f) (lambda (lst ...)) espressione in C. non dipende da alcuna delle h e g. Così possiamo tirarla fuori, ne fanno un argomento, ed essere lasciato con ... il combinatore Y:

(((lambda (rec)   ; D. 
     ((lambda (h) (h h)) 
     (lambda (g) 
      (rec (lambda (x) ((g g) x)))))) ; applicative-order Y combinator 
    (lambda (f)  
     (lambda (lst) 
      (if (null? lst) 0 
      (add1 (f (cdr lst))))))) 
    (list 1 2 3))       ; ==> 3 

Così ora, chiamando Y su una funzione equivale a fare una definizione ricorsiva fuori di esso:

(y (lambda (f) (lambda (x) .... (f x) ....))) 
=== define f = (lambda (x) .... (f x) ....) 

... ma utilizzando letrec (o chiamato let) è meglio - più efficiente, defining the closure in self-referential environment frame. Tutta la cosa Y è un esercizio teorico per i sistemi in cui non è possibile — cioè dove non è possibile nome cose, creare associazioni con nomi "che puntano" alle cose, riferendosi alle cose.

Per inciso, la capacità di punto alle cose è ciò che distingue i primati superiori dal resto degli esseri viventi Animal Kingdom ⁄, o almeno così ho sentito dire. :)

Answer 2

Per vedere cosa succede, utilizzare lo stepper in DrRacket. Lo stepper consente di visualizzare tutti i passaggi intermedi (e di andare avanti e indietro).

incollare il seguente in DrRacket:

(((lambda (mk-length) 
    (mk-length mk-length)) 
    (lambda (mk-length) 
    (lambda (l) 
     (cond 
     ((null? l) 0) 
     (else (add1 
       ((mk-length mk-length) 
       (cdr l)))))))) 
'(a b c)) 

quindi scegliere la lingua di insegnamento "Intermediate Student con lambda". Quindi fare clic sul pulsante stepper (il triangolo verde seguito da una barra).

Questo è ciò che il primo passo si presenta come:

poi fare un esempio per la seconda funzione e vediamo cosa va storto.