get-first - the-seasoned-schemer

Question

Please take a look at two-in-a-row*? function in chapter 19.

My question is about the (leave '()) in the get-first helper function. Note that (waddle l) will either return '() or an atom, which indicates the list has exhausted or an atom from the list is retrieved.

Without (leave '()) it will still return those two kinds of values, just not use the continuation leave. But the book says without (leave '()) is bad, I just can not see why.

(define two-in-a-row*
  (letrec ([leave id] ; the identity function 
           [fill id]
           [waddle (lambda (l)
                     (cond [(null? l) '()]
                           [(atom? (car l))
                            (begin 
                              (letcc rest
                                     (set! fill rest)
                                     (leave (car l)))
                              (waddle (cdr l)))]
                           [else
                            (begin
                              (waddle (car l))
                              (waddle (cdr l)))]))]
           [get-first (lambda (l)
                        (letcc here
                               (set! leave here)
                               (waddle l)
                               (leave '()) ; why is this part needed???
                               ))]
           [get-next (lambda (l)
                       (letcc here
                              (set! leave here)
                              (fill 'go)))]
           [T? (lambda (a)
                 (let ([n (get-next 'dummy)])
                   (if (atom? n)
                       (or (eq? a n)
                           (T? n))
                       #f)))])
    (lambda (l)
      (let ([fst (get-first l)])
        (if (atom? fst)
            (T? fst)
            #f)))))

Thanks very much.

Another interesting tread about this problem.

Answer 1

So thanks for Will Ness's examples. I went over some even simpler ones. So "what is it so bad about that?" -- without (leave '()) in get-first.

Short Answer:
Note that from my code
i) leave will always be recreated each time when we call get-first or get-next. It will return to either get-first or get-next.
ii) fill will result to be a chain depending on previous fill, and it will always return to get-first.

Example
Input: '(1)

So we start by evaluating get-first on '(1).
i) set leave
ii) start (waddle '(1)
iii) since 1 is an atom, so set fill to be current continuation. Note if we use fill, then it will go to do (waddle (cdr l)), then it will return to get-first. iv) return to get-first by using leave with return value 1.

Then we go to eval (T? 1), which will in turn go to run get-next.
i) set leave
ii) run fill
iii) start (waddle '())
iv) return () from waddle, then return to get-first.

Note
1) If we don't have (leave '(), then get-first will return '(), then the two-in-a-row* return #f. So we can get the same answer, but the behavior is not what we want.
2) If we have it, then note that leave is now the leave created by get-next, thus it is going to transfer '() to get-next.
3) With more than 1 input in the list when we create fill it will be created based on previous fill, thus result to be a chain depending previous fill.

Answer 2

The naming looks off. I used "yield" for "leave", and "next" for "fill". I also had to define atom? and re-write letcc as call/cc, to make it work in Racket. Here's the full code:

(define two-in-a-row*
  (letrec ([yield '()] 
           [next '()]
           [atom? (lambda (x) (and (not (null? x))
                                   (not (pair? x))))]
           [waddle (lambda (l)
                     (cond [(null? l) '()]
                           [(atom? (car l))
                            (begin 
                              (call/cc (lambda ( here2 )
                                          (set! next here2)
                                          (yield (car l))))
                              (waddle (cdr l)))]
                           [else
                            (begin (waddle (car l))
                                   (waddle (cdr l)))]))]
           [get-first (lambda (l)
                        (call/cc (lambda ( here1 )
                                    (set! yield here1)
                                    (waddle l)
                                    (yield '()) ; why is this part needed???
                                    )))]
           [get-next (lambda ()
                       (call/cc (lambda ( here3 )
                                   (set! yield here3)
                                   (next 'dummy))))]
           [T? (lambda (a)
                 (let ([n (get-next)])  (display (list "next:" n))
                   (and (atom? n)
                        (or (eq? a n)
                            (T? n)))))])
    (lambda (l)
      (let ([a (get-first l)])
        (and (begin                     (display (list "first:" a))
                    (atom? a))
             (T? a))))))

We can see the difference here:

(two-in-a-row* '(((7) (b)) c (d)))
  ; w/out yield () : (first: 7)(next: b)(next: c)(next: d)(first: ())#f
  ; w/    yield () : (first: 7)(next: b)(next: c)(next: d)(next: ())#f
  ; w/    yield #f : (first: 7)(next: b)(next: c)(next: d)(next: #f)(next: #f)#t

(two-in-a-row* '(((7) (b)) c ()))
  ; w/out yield () : (first: 7)(next: b)(next: c)(first: ())#f
  ; w/    yield () : (first: 7)(next: b)(next: c)(next: ())#f
  ; w/    yield #f : (first: 7)(next: b)(next: c)(next: #f)(next: #f)#t

(two-in-a-row* '(((7) (b)) b ()))
  ; w/out yield () : (first: 7)(next: b)(next: b)#t
  ; w/    yield () : (first: 7)(next: b)(next: b)#t
  ; w/    yield #f : (first: 7)(next: b)(next: b)#t

Answer 3

This is tricky. The clue in the book is the wow! reply. The student is saying wow! because they've realised () is returned from a different function.

This isn't clear, neither in the book or by using drracket, and it took me a while to understand but the key to understanding this is:

1. get-first called waddle to make the fill continuation.
2. waddle (when not using continuations) returns to get-first.

But

1. get-next calls fill.
2. fill continues in waddle
3. waddle uses leave to return to get-next rather than get-first.

But in the case of (waddle '()), waddle does not use leave to return to get-next. It returns normally. And that means it returns to get-first.

This means that get-next won't actually get the () return value. It won't get this value because waddle is returning to get-first instead.

Now comes to interesting part.

1. We know that, for the value (), waddle returns to get-first when we want it to return to get-next.
2. We know that get-next sets leave to return to get-next.
3. Therefore, get-first can use leave to return to get-next.

The real reason this is tricky is because look at the scenario when you don't use (leave '()) in get-first.

1. fill calls waddle with ().
2. waddle returns to get-first.
3. get-first then returns ().

And this is equivalent to:

  (let ([fst '()])     ;; was (let ([fst (get-first l)])
    (if (atom? fst)
        (T? fst)
        #f)))))

Which returns the same value as the version that returns into get-next:

       [T? (lambda (a)
             (let ([n '()])      ;; was (let ([n (get-next 'dummy)])
               (if (atom? n)
                   (or (eq? a n)
                       (T? n))
                   #f)))])

Both are #f, but only accidentally! No one said the book wouldn't make you think ;)