From posting-system@google.com Sun Jun 23 19:03:25 2002
Date: Sun, 23 Jun 2002 16:03:23 -0700
From: oleg-at-pobox.com
Newsgroups: comp.lang.scheme
Subject: How to map a set! [Was: How to play with the first arg of set! ?]
References: <3d131e2d$0$597$626a54ce@news.free.fr>
Message-ID: <7eb8ac3e.0206231503.5a725685@posting.google.com>
Status: OR

The topic of this article is making sure that
     (for-each (lambda (v val) (set! v val)) (list x y z) (list 1 2 3))
upon completion, changes the values of the previously bound variables x,
y, and z to respectively 1, 2, and 3.

This article was prompted by Thomas Baruchel's dream:

> dreaming of something like:
> (set! (if #t x y) 3.14)

Fulfilling this dream seems difficult, until, as the first step, we
make a small change: (set-car! (if #t x y) 3.14)
The solution immediately presents itself:

(let ((x (list 1)) (y (list 2)))
  (for-each display
    (list "Before: " "x= " (car x) " and y= " (car y) #\newline))
  (set-car! (if #t x y) 3.1415)
  (for-each display
    (list "After: " "x= " (car x) " and y= " (car y) #\newline))
)

It runs and gives the expected result. This solution follows the
general principle that there is no decidable computer science problem
that can't be solved by an extra indirection. 

Thomas Baruchel wanted to use set! rather than set-car!. We shall show
how we can do that.

In the example above, the extra level of indirection was accomplished
by wrapping a value into a list. A cleaner approach is to use a
dedicated record type (see SRFI-9)

(define-record-type refcell
  (ref val)   ; constructor
  ref?        ; predicate
  (val ref-ref ref-set!)) ; one field and its accessors

The record declaration creates a (quasi-) unique type. To access the
value wrapped in a refcell x, we generally have to write (ref-ref
x). This is inconvenient. Therefore, we will overload +, -, and other
strict operations to dereference the cells tacitly:

(define (! val) (if (ref? val) (ref-ref val) val))

To avoid writing (set! op (let ((op op)) (lambda args (apply op (map !
args))))) for each operation op manually, we enlist the help of a
macro:

(define-syntax !ize
  (syntax-rules ()
    ((_ op) (set! op    ; In Scheme 48, replace this set! with define
	       (let ((op op))
		 (lambda args (apply op (map ! args))))))))

(!ize +) (!ize -) (!ize *) (!ize /) (!ize <) (!ize <=) (!ize >=) (!ize >)
(!ize display)

To assign a new value to a ref cell x, we normally have to write
(ref-set! x new-val). Again, this is inconvenient. We would like to
use the familiar set! for that purpose. We still want to use set! to
mutate non-ref-cell bindings. The following pinch of black magic makes
it possible to overload set!

; Petrofsky extraction. Search groups.google.com for "dirty macro"
(define-syntax extract
  (syntax-rules ()
    ((_ symb body _cont)
      (letrec-syntax
	((tr
           (syntax-rules (symb)
	      ((_ x symb tail (cont-head symb-l . cont-args))
	       (cont-head (x . symb-l) . cont-args)) ; symb has occurred
	      ((_ d (x . y) tail cont)   ; if body is a composite form,
	       (tr x x (y . tail) cont)) ; look inside
	      ((_ d1 d2 () (cont-head  symb-l . cont-args))
	       (cont-head (symb . symb-l) . cont-args)) ; symb does not occur
	      ((_ d1 d2 (x . y) cont)
	       (tr x x y cont)))))
	(tr body body () _cont)))))

(define-syntax with-ext-set!
  (syntax-rules ()
    ((_ . _body)
     (let-syntax
       ((bind-set	; continuation from extract
	 (syntax-rules ()
	    ((_ (set-symb) body)
	     (let-syntax
		 ((set-symb
		   (syntax-rules ()
		     ((_ (?exp . ?args) ?val)
		      (ref-set! (?exp . ?args) (! ?val)))
		     ((_ ?var ?val)
		      (let ((val (! ?val)))
			(if (ref? ?var) (ref-set! ?var val) 
			    (set! ?var val))))
		     )))
	       . body)))))
     (extract set! _body (bind-set () _body))))))

And now, the final example:

(with-ext-set!
 (let ((x (ref 11)) (y (ref 12)) (z (ref 13)) (u 14))
  (for-each display
     (list "Before: " "x= " x ", y= " y ", z= " z ", u= " u
	   #\newline))
  (map (lambda (var val) (set! var val))
       (list x y z) (list 1 2 3))
  (set! u (+ x y))
  (for-each display
     (list "After: " "x= " x ", y= " y ", z= " z ", u= " u
	   #\newline))
  (set! (if (< x y) x y) 3.1415)
  (for-each display
     (list "Finally: " "x= " x ", y= " y ", z= " z ", u= " u
	   #\newline))

))

The printed result:

Before: x= 11, y= 12, z= 13, u= 14
After: x= 1, y= 2, z= 3, u= 3
Finally: x= 3.1415, y= 2, z= 3, u= 3 

All the examples were tested with Bigloo 2.4b and Scheme48.

As we see, we never have to dereference cells explicitly. Variable x
behaves as if it were bound to a value, as the regular variable 'u' is.

Please note the statement:
       (map (lambda (var val) (set! var val))
         (list x y z) (list 1 2 3))

As the printout shows, the statement indeed works as we wanted it
to. Please also note that set! is overloaded rather than merely
replaced: we can still use set! to mutate ordinary bindings, as in
(set! u (+ x y)). A statement (set! (if (< x y) x y) 3.1415)
demonstrates that the extended set! is indeed expressive.

Related work: it is easy to see that our refcells behave like
references in C++. You cannot mutate a reference or read the
reference itself: you can only mutate or read the referred
value. OCaml implements reference cells precisely as mutable records
of one element. A transformation from (let ((x val)) ...) to (let ((x
(ref val))) ...) is a a very common step of compiling Scheme
programs. This transformation makes bindings and their collections
(environments) immutable, which enables sharing.