スキームの継続を理解するのに役立ちます

Question

私は一緒に働いています 小さなスキーマー スキームを学び、私の環境にPLT-Schemeを使用します。

小さなスキーマー 再帰に非常に役立ちました（今では私にとっては簡単です）が、「コレクター」を紹介し、機能全体を継続と呼ぶ本の一部にこだわっています。

これが彼らが使用したコードの例です。私は再帰的な要素を理解していますが、特にラムダ関数にとどまります - 私の心は道をたどることができません、そしてそのラムダ関数の議論がどのように設定されているか（彼らの唯一の呼び出しは再帰で再びそれらを呼び出すことです、関数本文内での具体的な使用はありません）。

誰かが、ラムダコレクターへの関数の再帰を通して計算の経路を多かれ少なかれ私に崩壊させることができれば、それは私を助けるかもしれません。

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

前もって感謝します！！

Answer 1

Try something simpler to see how this works. For example, here's a version of a list-sum function that receives a continuation argument (which is often called k):

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

The basic pattern is there, and the missing parts are where the interesting things happen. The continuation argument is a function that expects to receive the result -- so if the list is null, it's clear that we should send it 0, since that is the sum:

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

Now, when the list is not null, we call the function recursively with the list's tail (in other words, this is an iteration), but the question is what should the continuation be. Doing this:

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

is clearly wrong -- it means that k will eventually receive the the sum of (cdr l) instead of all of l. Instead, use a new function there, which will sum up the first element of l too along with the value that it receives:

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

This is getting closer, but still wrong. But it's a good point to think about how things are working -- we're calling list-sum with a continuation that will itself receive the overall sum, and add the first item we see now to it. The missing part is evident in the fact that we're ignoring k. What we need is to compose k with this function -- so we do the same sum operation, then send the result to k:

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

which is finally working. (BTW, remember that each of these lambda functions has its own "copy" of l.) You can try this with:

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

And finally note that this is the same as:

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

if you make the composition explicit.

(You can also use this code in the intermediate+lambda student language, and click the stepper button to see how the evaluation proceeds -- this will take a while to go over, but you'll see how the continuation functions get nested, each with it's own view of the list.)

Answer 2

Here's one way to help you "get a more concrete idea". Imagine if the collector were defined thus:

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

You can see in the base case, if you pass in an empty list, it will call your function with arguments '(), 1, and 0. Now, work with a one-element list, and see what it'll call your function with. Keep working up with longer and longer lists, until you figure out what's going on.

Good luck!