Aide à la compréhension des continuations du schéma

Question

J'ai travaillé aux côtés Le petit intrigue Pour apprendre le schéma et utiliser PLT-Scheme pour mon environnement.

Le petit intrigue m'a énormément aidé avec la récursivité (c'est simple pour moi maintenant) mais je suis coincé sur une partie du livre qui présente des "collectionneurs" et appelle la fonction dans son ensemble une continuation.

Voici l'exemple de code qu'ils ont utilisé. Je comprends les éléments récursifs mais je suis coincé, en particulier sur les fonctions lambda - mon esprit ne peut pas suivre le chemin et comment les arguments pour cette fonction lambda sont définis (car leur seul appel est de les appeler à nouveau dans la récursivité, il y a Aucune utilisation du béton dans le corps de la fonction).

Si quelqu'un pouvait me donner plus ou moins me donner une rupture du chemin du calcul par la récursivité de la fonction dans les collectionneurs lambda, cela peut m'aider.

;; Build a nested list of even numbers by removing the odd ones from its
;; argument and simultaneously multiply the even numbers and sum the odd
;; numbers that occur in its argument.
(define (even-only-collector l col)
  (cond
    ((null? l)
      (col (quote ()) 1 0))
    ((atom? (car l))
      (cond
        ((even? (car l))
          (even-only-collector (cdr l)
            (lambda (newl p s)
              (col (cons (car l) newl)
                (* (car l) p) s))))
         (else
           (even-only-collector (cdr l)
             (lambda (newl p s)
               (col newl
                 p (+ (car l) s)))))))
    (else
      (even-only-collector (car l)
        (lambda (al ap as)
          (even-only-collector (cdr l)
            (lambda (dl dp ds)
              (col (cons al dl)
                (* ap dp)
                (+ as ds)))))))))

;; The collector function
(define (collector newl product sum)
  (cons sum
    (cons product newl)))

Merci d'avance!!

Answer 1

Essayez quelque chose de plus simple pour voir comment cela fonctionne. Par exemple, voici une version d'un list-sum fonction qui reçoit un argument de continuation (qui est souvent appelé k):

(define (list-sum l k)
  (if (null? l)
    ???
    (list-sum (cdr l) ???)))

Le modèle de base est là, et les parties manquantes sont là où les choses intéressantes se produisent. L'argument de continuation est une fonction qui prévoit de recevoir le résultat - donc si la liste est nul, il est clair que nous devons l'envoyer 0, puisque c'est la somme:

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) ???)))

Maintenant, lorsque la liste n'est pas nul, nous appelons la fonction récursivement avec la queue de la liste (en d'autres termes, c'est une itération), mais la question est de savoir quelle devrait être la continuation. Ce faisant:

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) k)))

est clairement faux - cela signifie que k recevra finalement la somme de (cdr l) au lieu de tous l. Au lieu de cela, utilisez une nouvelle fonction là-bas, qui résumera le premier élément de l aussi avec la valeur qu'elle reçoit:

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) (lambda (sum) (+ (car l) sum)))))

Cela se rapproche, mais toujours mal. Mais c'est un bon point de réfléchir à la façon dont les choses fonctionnent - nous appelons list-sum avec une continuation qui recevra elle-même la somme globale et ajoutera le premier élément que nous voyons maintenant. La partie manquante est évidente dans le fait que nous ignorons k. Ce dont nous avons besoin, c'est de composer k Avec cette fonction - nous faisons donc la même opération de somme, puis envoyez le résultat à k:

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) (compose k (lambda (s) (+ s (car l)))))))

ce qui fonctionne enfin. (Btw, rappelez-vous que chacun de ces lambda Les fonctions ont sa propre "copie" de l.) Vous pouvez essayer ceci avec:

(list-sum '(1 2 3 4) (lambda (x) x))

Et enfin notez que c'est la même chose que:

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) (lambda (s) (k (+ s (car l)))))))

Si vous rendez la composition explicite.

(Vous pouvez également utiliser ce code dans le langage étudiant intermédiaire + lambda, et cliquer sur le bouton pas à pas pour voir comment se déroule l'évaluation - cela prendra un certain temps, mais vous verrez comment les fonctions de continuation sont imbriquées, chacun avec sa propre vue de la liste.)

Answer 2

Voici une façon de vous aider à "obtenir une idée plus concrète". Imaginez si le collecteur était défini ainsi:

(define (collector l p s)
  (display l)
  (newline)
  (display p)
  (newline)
  (display s)
  (newline))

Vous pouvez voir dans le cas de base, si vous passez dans une liste vide, il appellera votre fonction avec des arguments '(), 1 et 0. Maintenant, travaillez avec une liste d'éléments et voyez avec quoi il appellera votre fonction. Continuez à travailler avec des listes de plus en plus longues, jusqu'à ce que vous découvriez ce qui se passe.

Bonne chance!