Equivalence of "mutable" closures

and capture-free renaming of free variables in Scheme code

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

        (counter)    ; advance the 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:

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

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
 


Articles' Posting Headers

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


Last updated January 5, 2001

This site's top page is http://okmij.org/ftp/

oleg-at-okmij.org
Your comments, problem reports, questions are very welcome!