On Tuesday, December 30, 2003 12:39 PM, Ben Rudiak-Gould [SMTP:benrg@dark.darkweb.com] wrote:
With letrec and unrestricted call/cc you can implement ML-style refs:
With an *implementation of letrec that uses mutation* and unrestricted call/cc, you can implement ML-style ref cells: Petite Chez Scheme Version 6.0a Copyright (c) 1998 Cadence Research Systems
(define-syntax letrec^ (syntax-rules () ((_ ((Var Exp)) Body Bodies ...) (let ((Y (lambda (f) ((lambda (g) (f (g g))) (lambda (g) (f (lambda (x) ((g g) x)))))))) (let ((Var (Y (lambda (Var) Exp)))) Body Bodies ...)))))
(letrec^ ((fact (lambda (n) (if (zero? n) 1 (* n (fact (- n 1))))))) (fact 5)) 120
(define (make-cell) (call/cc (lambda (return-from-make-cell) (letrec^ ((state (call/cc (lambda (return-new-state) (return-from-make-cell (lambda (op) (case op ((set) (lambda (value) (call/cc (lambda (return-from-access) (return-new-state (list value return-from-access)))))) ((get) (car state))))))))) ((cadr state) 'done)))))
(define c (make-cell))
((c 'set) 3)
(c 'get) 3
((c 'set) 7) done
(c 'get) 3
On Tue, 30 Dec 2003, Kevin S. Millikin wrote:
On Tuesday, December 30, 2003 12:39 PM, Ben Rudiak-Gould wrote:
With letrec and unrestricted call/cc you can implement ML-style refs:
With an *implementation of letrec that uses mutation* and unrestricted call/cc, you can implement ML-style ref cells:
[...]
(define c (make-cell)) ((c 'set) 3) (c 'get) 3 ((c 'set) 7) done (c 'get) 3
Interesting. This still violates referential transparency, though. (c 'get) returns a value or errors out depending on whether (c 'set) has been called yet. Here's a more obvious violation:
(let* ((c (make-cell)) (d (make-cell))) ((c 'set) 1) ((d 'set) 2) (d 'get)) 2 (let* ((c (make-cell)) (d c)) ((c 'set) 1) ((d 'set) 2) (d 'get)) 1
And take a look at this!
(define c (make-cell)) (define d c) ((d 'set) 9) (d 'get)
Error in car: #<procedure> is not a pair. Type (debug) to enter the debugger. Something very nasty is going on here. I'm not sure exactly what it is, but I think at least one of the define statements is getting executed at least twice. I still think there's a deep antagonism between unrestricted call/cc and referential transparency, and changing letrec's semantics can't fix it. -- Ben
participants (2)
-
Ben Rudiak-Gould -
Kevin S. Millikin