Consider(define counter (let ((n 0)) (lambda () (begin (set! n (+ 1 n)) n))))Does
set!modify the closure, or more precisely, does it change the value of a symbol
counter? It would be nice if we could prove the closure not to change.
In other words,
(let* ((counter (let ((n 0)) (lambda () (set! n (+ 1 n)) n))) (counter1 counter)) (counter) ; advance the counter (the-same? counter counter1)) ==> ?There are two questions in here: the result of an expression
(the-same? counter counter1)
Let's re-write the example in a slightly different way:
(let* ((n 0) (counter (lambda () (set! n (+ 1 n)) n)) (counter1 counter)) (counter) (the-same? counter counter1))It becomes obvious that the expression returns
#t, even if we are not clear what
To generalize our re-writing of the closure, let us introduce a special
(define-macro (define-closure name bindings body) `(define ,name (let ,bindings ,body)))so that
(define-closure counter ((n 0)) (lambda () (set! n (+ 1 n)) n))
Now consider another implementation for
(define-closure counter ((n
0)) (lambda () (set! n (+ 1 n)) n))
(define hidden-var-name 0) (define counter (lambda () (set! hidden-var-name (+ 1 hidden-var-name) hidden-var-name)))Where
hidden-var-nameis a name that only the body of the counter knows about.
One can claim that both implementations of
equivalent: a user should not be able to tell the
difference between the two implementations.
This re-writing of the closure separates closure's environment from
its functional body, and hopefully clarifies the question of whether
set! "modifies" the closure.
We still have not decided what
the-same? actually is.
What are the ways to define
the-same? We may want to consider the
Henry Baker expounded on the issues of identity in great detail in his wonderful (and wonderfully written) paper,
Equal Rights for Functional Objects or, The More Things Change, The More They Are the Same
Henry G. Baker.
ACM OOPS Messenger 4, 4 (Oct 1993), 2-27.
R5RS also has a say on the matter, in Section 6.1, "Equivalence predicates":
TheR5RS gives then several examples of comparing for equivalence procedures with a local state. One of the examples is almost literally our counter.
obj2are procedures that would behave differently (return different value(s) or have different side effects) for some arguments....
eqv?are guaranteed to have the same behavior on ... procedures ...
From yet another point of view, an executable file on Unix, Winxx or
any other OS contains a code segment (with instructions for the CPU)
as well as a data segment, on which the code operates. Likewise, the
closure value associated with
counter has two normally
invisible components: an 'executable' code and a private data part, a
binding of a variable named
n to a value 0.
(define counter-ref counter) ; counter-ref is another binding to the same procedural ; value. In other words, 'counter-ref' may be replaced ; by 'counter' everywhere where it occurs in ; the expressions below. (eqv? counter-ref counter) ; #t (counter) ; the procedural value is invoked. ; the private data part now contains the ; binding of 'n' to a value 1. The previous ; binding is forgotten. (eqv? counter-ref counter) ; #t as counter-ref remains bound ; to the same procedural value, which now has ; the updated binding of 'n' to 1.Note that further evaluation of either
(counter-ref)will return the same result: 2. Furthermore, let us evaluate
(counter)several times in a row and collect the results into a sequence. We could have replaced some of the invocations of
counterwith those of
counter-refbut still obtain the same final sequence. Thus we can replace any occurrence of
counter-refin an arbitrary code, without affecting the program's behavior.
In Unix terms, this example is equivalent to:
echo 'date > /tmp/a; cat /tmp/a' > file1 ln file1 file2 # file1 or file2 are the same file: both names are # bound to the same i-node ./file1The next invocation of
./file1will print a different result, while the names
file2will still be associated with the same i-node. That is, names
file2can be used interchangeably.
define-closurehad to rename all occurrences of a particular free variable in a lambda form.
The first attempt at the solution:
(defmacro define-closure (name bindings body) (let ((vars-in-bindings (map car bindings)) (new-names (map (lambda (x) (gentemp)) bindings)) (renamer (gentemp)) ) `(begin ,@(map (lambda (binding new-var) `(define ,new-var ,@(cdr binding))) bindings new-names) (define-syntax ,renamer (syntax-rules () ((,renamer ,@vars-in-bindings) ,body))) (define ,name (,renamer ,@new-names)))))Yes, this an old-style macro that expands to a new style macro . The sole purpose of the latter is to replace every occurrence of an
body. The name of that renaming macro is itself 'hidden' to avoid any name clashes. It works out great:
scm --version scm 5d2 scm -r5 -r4 ==> ... enter the macro above ... ==>(define-closure counter ((n 0)) (lambda () (set! n (+ 1 n)) n)) counter ==>counter #<CLOSURE #f #@lambda (set! scm:G1 (+ 1 scm:G1)) scm:G1>As we see, all occurrences of
nwithin the body of the closure are replaced with
scm:G1, a 'hidden' identifier.
Alas, the renamer is way too efficient. It indeed replaces
every occurrence of the
old-var with the
new-var is made to be unique, so
it should not clash with any of the existing or future variable
names. Therefore, it is always safe to replace the
old-var with the
new-var even if the
old-var is later bound, e.g.:
(lambda () (set! old-var (+ 1 old-var)) ((lambda (old-var) (+ old-var old-var)) old-var) )However, the renaming macro replaces the
old-vareven if it is quoted. This feature seems undesirable. Thus we have to bite the bullet and do our own substitution. The resulting
renameprocedure turns out surprisingly short:
(define-macro (define-closure name bindings body) ; given the list ((old-var . new-var) ...) and a data ; structure that represents a Scheme expression, replace ; every occurrence of the old-var with the new-var, ; except when the old-var is quoted, or used as a selector ; symbol in a case form. (define (rename alist expr) (cond ((null? expr) expr) ((symbol? expr) (cond ((assq expr alist) => cdr) (else expr))) ((and (pair? expr) (eq? 'quote (car expr))) expr) ((and (pair? expr) (eq? 'case (car expr))) (cons 'case (cons (rename alist (cadr expr)) (map (lambda (one-case) (cons (car one-case) (rename alist (cdr one-case)))) (cddr expr))))) ((pair? expr) (cons (rename alist (car expr)) (rename alist (cdr expr)))) (else expr))) (let ((vars-in-bindings (map car bindings)) (new-names (map (lambda (x) (gensym)) bindings)) ) `(begin ,@(map (lambda (binding new-var) `(define ,new-var ,@(cdr binding))) bindings new-names) (define ,name ,(rename (map cons vars-in-bindings new-names) body))) ))The rename procedure does not handle quasiquote, but this is easy to add.
; Gambit-C 3.0 (pp (lambda () (let ((x 0)) (define-closure fib-counter ((v2 1) (v1 1)) (lambda () (let ((v (+ v2 v1))) (set! v2 v1) (set! v1 v) (case v1 ; this contrived form merely verifies handling of 'case' ((v1) (dummy dummy dummy)) (else (list 'v1 v1 'v2 v2 'v v)))))) (let* ((r1 (fib-counter)) (r2 (fib-counter)) (r3 (fib-counter))) (list r1 r2 r3))))) ==> (lambda () (let ((x 0)) (letrec ((g0 1) (g1 1) (fib-counter (lambda () (let ((v (+ g0 g1))) (set! g0 g1) (set! g1 v) (case g1 ((v1) (dummy dummy dummy)) (else (list 'v1 g1 'v2 g0 'v v))))))) (let ((r1 (fib-counter))) (let ((r2 (fib-counter))) (let ((r3 (fib-counter))) (list r1 r2 r3)))))))We see that
v2are indeed replaced with 'hidden names' except where explicitly or implicitly quoted. We also see that the Gambit pre-compiler turned internal
let. This Fibonacci counter works as expected: when the above thunk is invoked, it yields
((v1 2 v2 1 v 2) (v1 3 v2 2 v 3) (v1 5 v2 3 v 5))
The present page is a compilation of three articles posted on a
comp.lang.scheme newsgroup on Aug 17 and Aug 24, 2000.
The entire thread is available from Deja.com
From: oleg-at-pobox.com Subject: Re: binding concepts Date: 17 Aug 2000 00:00:00 GMT Message-ID: <email@example.com> References: <firstname.lastname@example.org> <email@example.com> X-Article-Creation-Date: Thu Aug 17 03:11:56 2000 GMT Newsgroups: comp.lang.scheme From: oleg-at-pobox.com Subject: Re: bindings, still confused Date: 24 Aug 2000 00:00:00 GMT Message-ID: <firstname.lastname@example.org> References: <email@example.com> X-Article-Creation-Date: Thu Aug 24 00:19:33 2000 GMT Newsgroups: comp.lang.scheme From: oleg-at-pobox.com Subject: Re: bindings, still confused Date: 24 Aug 2000 00:00:00 GMT Message-ID: <firstname.lastname@example.org> References: <email@example.com> <firstname.lastname@example.org> X-Article-Creation-Date: Thu Aug 24 22:20:36 2000 GMT Newsgroups: comp.lang.scheme
oleg-at-pobox.com or oleg-at-okmij.org or oleg-at-computer.org