# Equivalence of "mutable" closures

### The question

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))

(the-same? counter counter1)) ==> ?
```
There are two questions in here: the result of an expression
```(the-same? counter counter1)```
and the precise meaning of the predicate `the-same?`

### Discussion

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))```
expands to the example in the question.

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.

### Approaches to deciding equivalence

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:

• identity vs. state.
Given two objects, one may ask if they have the same identity, or if they are in the same state. Two people over the age of 21 are in the same state (adult), but obviously have different identities. On the other hand, a minor legally becomes an adult on his 21st birthday -- that is, changes state -- while retaining his identity.
• two objects have the same identity if they can be substituted for one another without changing the behavior of a program
• two mutable objects are identical if mutating one of them effects the same change in the other. Mutating an object means changing that object's state.

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":

The` eqv?` procedure returns `#f` if: ... `obj1` and `obj2` are procedures that would behave differently (return different value(s) or have different side effects) for some arguments....
`Eq?` and `eqv?` are guaranteed to have the same behavior on ... procedures ...
R5RS gives then several examples of comparing for equivalence procedures with a local state. One of the examples is almost literally our counter.

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.

## Renaming of free variables

The second implementation of `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 `define`s 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))```

### References

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: <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-at-pobox.com
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-at-pobox.com
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
```

### Last updated January 5, 2001

This site's top page is http://pobox.com/~oleg/ftp/

oleg-at-pobox.com or oleg-at-okmij.org or oleg-at-computer.org