letrec

Isn't
(letrec ([is-even? (lambda (n)
                    (or (zero? n)
                        (is-odd? (sub1 n))))]
         [is-odd? (lambda (n)
                   (and (not (zero? n))
                        (is-even? (sub1 n))))])
        (is-odd? 11))

equivalent to...

(let
    ([is-even? nil]
     [is-odd? nil])
    (set! is-even? (lambda (n)
                    (or (zero? n)
                        (is-odd? (sub1 n)))))
    (set! is-odd? (lambda (n)
                   (and (not (zero? n))
                        (is-even? (sub1 n)))))
    (is-odd? 11))

>>15
Because shift introduces two new prompts (at call site, and inside the reified continuation), control only one (at call site). prompt and reset are the same thing.

>>26
I knew I forgot something. Well, letrec's evaluation order is unspecified (they are first evaluated, then bound), your code is equivalent to letrec*, whose evaluation order is sequential (and they are bound right after evaluation).call/cc simply can make the sequential evaluation order apparent:


(define-syntax letrec1
  (syntax-rules ()
    ((letrec ((a x) ...) body ...)
     (let ((a #f) ...)
       (set! a x)
       ...
       body ...))))
(define-syntax letrec2
  (syntax-rules ()
    ((letrec ((a t x) ...) body ...) ; the t variables because I'm lazy.
     (let ((a #f) ... (t x) ...)
         (set! a t)
         ...
         body ...))))

(define (g)
  (let ((cont #f))
    (letrec1 ((x (call/cc (lambda (c) (set! cont c) 0)))
              (y (call/cc (lambda (c) (set! cont c) 0))))
      (if cont
          (let ((c cont))
            (set! cont #f)
            (set! x 1)
            (set! y 1)
            (c 0))
          (+ x y)))))

(define (h)
  (let ((cont #f))
    (letrec2 ((x t1 (call/cc (lambda (c) (set! cont c) 0)))
              (y t2 (call/cc (lambda (c) (set! cont c) 0))))
      (if cont
          (let ((c cont))
            (set! cont #f)
            (set! x 1)
            (set! y 1)
            (c 0))
          (+ x y)))))

(display (g))
(display (h))

The call to g will return 1, the call to h will return 0. The trick is in the two (set! x 1) (set! y 1):

(let ((cont #f))
 (let ((x #f) (y #f))
  (set! x (call/cc (lambda (c) (set! cont c) 0))) ; yes, both the calls to call/cc are needed, to prevent you to cheat by evaluating the expressions in reverse order.
  (set! y (call/cc (lambda (c) (set! cont c) 0)))
  (if cont
      (let ((c cont))
        (set! cont #f)
        (set! x 1)
        (set! y 1)
        (c 0))
       (+ x y))))

You start evaluating that code, x and y are bound to 0, and that's ok.
cont is bound to this continuation, though:
(lambda (x)
 (set! y x)
 (if cont blah blah))
In this continuation, x has already been evaluated and bound to 0.
So, when we do:
(set! x 1) (set! y 1) (c 0)
The continuation is called, but x is not re-evaluated and re-bound to 0, it will still be the 1 we set!ed right now.
Thus, with x = 1, y = 0, cont = #f, the whole expression will return (+ x y) => (+ 1 0) => 1.

If the order was unspecified, it would return 0. Understanding why is left as an exercise for the reader.

A R5RS letrec is equivalent to this:

(letrec ((even? (lambda (x) (or (zero? x) (not (odd? (- x 1))))))
         (odd?  (lambda (x) (and (not (zero? x)) (even? (- x 1))))))
  (odd? 11))

;=>

(let ((even? #<unspecified>) (odd? #<unspecified>))
 (let ((tmp1 (lambda (x) (or (zero? x) (not (odd? (- x 1))))))
       (tmp2 (lambda (x) (and (not (zero? x)) (even? (- x 1))))))
  (set! even? tmp1)
  (set! odd?  tmp2)
  (odd? 11)))

The two lets can be merged safely.