Consider(define counter (let ((n 0)) (lambda () (begin (set! n (+ 1 n)) n))))Doesset!modify the closure, or more precisely, does it change the value of a symbolcounter? 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)the-same?
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 the-same? actually is.
To generalize our re-writing of the closure, let us introduce a special
form define-closure:
(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,
such that
(define-closure counter ((n
0)) (lambda () (set! n (+ 1 n)) n))
expands to
(define hidden-var-name 0)
(define counter
(lambda () (set! hidden-var-name (+ 1 hidden-var-name)
hidden-var-name)))
Where hidden-var-name is a name that only the body of the
counter knows about.
One can claim that both implementations of define-closure are
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
the internal 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
following factors:
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.eqv?procedure returns#fif: ...obj1andobj2are procedures that would behave differently (return different value(s) or have different side effects) for some arguments....
Eq?andeqv?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) xor
(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 counter with those of
counter-ref but still obtain the same final
sequence. Thus we can replace any occurrence of counter
with counter-ref in 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
./file1
The next invocation of ./file1 will print a different
result, while the names file1 and file2 will
still be associated with the same i-node. That is, names
file1 and file2 can be used
interchangeably.define-closure had 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
old-var with new-var in the
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 n within 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.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-var even if it is
quoted. This feature seems undesirable. Thus we have to bite the
bullet and do our own substitution. The resulting rename procedure
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 v1 and v2 are indeed replaced
with 'hidden names' except where explicitly or implicitly quoted. We
also see that the Gambit pre-compiler turned internal
defines into letrec and let*
into repeated 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 Subject: Re: binding concepts Date: 17 Aug 2000 00:00:00 GMT Message-ID: <8nfl5g$gdk$1@nnrp1.deja.com> References: <8ncemh$9sv$1@nereid.worldonline.nl> <8nfbjh$1qv$1@nereid.worldonline.nl> X-Article-Creation-Date: Thu Aug 17 03:11:56 2000 GMT Newsgroups: comp.lang.scheme From: oleg Subject: Re: bindings, still confused Date: 24 Aug 2000 00:00:00 GMT Message-ID: <8o1pm5$t7t$1@nnrp1.deja.com> References: <8nq2qf$7e$1@nereid.worldonline.nl> X-Article-Creation-Date: Thu Aug 24 00:19:33 2000 GMT Newsgroups: comp.lang.scheme From: oleg Subject: Re: bindings, still confused Date: 24 Aug 2000 00:00:00 GMT Message-ID: <8o4737$mgl$1@nnrp1.deja.com> References: <8nq2qf$7e$1@nereid.worldonline.nl> <8o1pm5$t7t$1@nnrp1.deja.com> X-Article-Creation-Date: Thu Aug 24 22:20:36 2000 GMT Newsgroups: comp.lang.scheme
oleg-at-okmij.org