LETREC + CALL/CC = SET! even in a limited setting

57 views
Skip to first unread message

Alan Bawden

unread,
Mar 2, 1989, 11:27:00 AM3/2/89
to
The following function, which I mailed out to this last last February, was
intended to demonstrate how CALL-WITH-CURRENT-CONTINUATION could be used to
expose the SET! hidden in the definition of LETREC:

(define (make-cell)
(call-with-current-continuation
(lambda (return-from-make-cell)
(letrec ((state
(call-with-current-continuation
(lambda (return-new-state)
(return-from-make-cell
(lambda (op)
(case op
((set)
(lambda (value)
(call-with-current-continuation
(lambda (return-from-access)
(return-new-state
(list value return-from-access))))))
((get) (car state)))))))))
((cadr state) 'done)))))

Here is another way to do it that has an additional interesting property:

(define (make-cell initial-value)
(letrec ((state (call-with-current-continuation
(lambda (return-new-state)
(list initial-value return-new-state #F)))))
(if (caddr state)
((caddr state) 'done)
(lambda (op)
(case op
((get) (car state))
((set)
(lambda (new-value)
(call-with-current-continuation
(lambda (return-from-set)
((cadr state)
(list new-value (cadr state) return-from-set)))))))))))

Notice that the variable STATE does not occur anywhere in the right hand
side of its own definition in the LETREC. Thus you might think that you
could optimize this into an instance of LET. But that optimization would
be incorrect (assuming that the expansion of LETREC given in R^3RS really
-is- its definition), because then this code will stop producing
side-effectable cells.

A simpler case of this peculiarity of LETREC:

(define (test)
(letrec ((x (call-with-current-continuation
(lambda (c)
(list #T c)))))
(if (car x)
((cadr x) (list #F (lambda () x)))
(eq? x ((cadr x))))))

(TEST) should return #T. If you replace the LETREC with LET (you might be
tempted because X does not appear anywhere in the right hand side of the
definition!), then (TEST) will return #F.

I wonder if any real compilers make this mistaken optimization?

Reply all
Reply to author
Forward
0 new messages