funzione di lunghezza in "The Seasoned Schemer"

Question

Ho letto Il Seasoned Schemer e mi sono imbattuto in questa definizione della lunghezza funzione

(define length 
    (let ((h (lambda (l) 0))) 
    (set! h (L (lambda (arg) (h arg)))) 
    h)) 

tardi dicono:

Qual è il valore di (L (lambda (arg) (h arg)))? E 'la funzione

(lambda (l) 
    (cond ((null? l) 0) 
    (else (add1 ((lambda (arg) (h arg)) (cdr l)))))) 

non credo Capisco questo completamente. Suppongo che dovremmo definire L come esercizio. Ho scritto una definizione di L nella definizione di lunghezza utilizzando letrec. Ecco quello che ho scritto:

(define length 
    (let ((h (lambda (l) 0))) 
    (letrec ((L 
       (lambda (f) 
       (letrec ((LR 
          (lambda (l) 
          (cond ((null? l) 0) 
            (else 
            (+ 1 (LR (cdr l)))))))) 
        LR))))     
    (set! h (L (lambda (arg) (h arg)))) 
    h))) 

Quindi, L prende una funzione come argomento e restituisce come valore di un'altra funzione che prende una lista come argomento ed esegue una ricorsione in un elenco. Sono corretto o irrimediabilmente sbagliato nella mia interpretazione? In ogni caso la definizione funziona

(length (list 1 2 3 4)) => 4 

Answer 1

In "The Seasoned Schemer" length viene inizialmente definita in questo modo:

(define length 
    (let ((h (lambda (l) 0))) 
    (set! h (lambda (l) 
       (if (null? l) 
        0 
        (add1 (h (cdr l)))))) 
    h)) 

Più tardi nel libro, il risultato precedente è generalizzata e length viene ridefinito in termini di Y! (l'ordine applicativo, combinatore Y imperativo) in questo modo:

(define Y! 
    (lambda (L) 
    (let ((h (lambda (l) 0))) 
     (set! h (L (lambda (arg) (h arg)))) 
     h))) 

(define L 
    (lambda (length) 
    (lambda (l) 
     (if (null? l) 
      0 
      (add1 (length (cdr l))))))) 

(define length (Y! L)) 

La prima definizione di length mostrato nella domanda è solo un passaggio intermedio: con la procedura L esattamente come sopra definito, non è necessario ridefinirlo. Lo scopo di questa parte del capitolo è di raggiungere la seconda definizione mostrata nella mia risposta.