Internals of places and setforms
Assignment and generalized variables are one of the most interesting parts of the Arc language. While assignment with = seems straightforward, it is actually remarkably complex and flexible. This page describes the details and internals of generalized variables, places, and setforms. For a more introductory guide, see Arc: Assignment.
Assignment works with variables, tables, and strings:
arc> (= x 1 y (table) z "string")
arc> (= (y "key") "value")
"value"
arc> (= (z 1) #\p)
arc> x
1
arc> y
#hash(("key" . "value"))
arc> z
"spring"
Assignment also works with complex list operations:
arc> (= l '(a (b c) d))
arc> (= (car (cadr l)) 'z)
arc> l
(a (z c) d)
In general, the destination of the assignment is called a "place" or a "generalized variable". The = macro assigns one or more values to one or more places.
At this point, you may be wondering how assignment actually works. It looks like it's looking up the value in the table, string, or list, and then changing that value. You might wonder why (= (z 1) #\p) modifies a character inside z, instead of modifying the character returned by (z 1) Perhaps something like a C++ pointer or reference is being used?
The actual implementation is rather surprising. Assignment uses the setform macro, which takes apart the target expression, "reverse engineers" how to set a value at that place, and then builds code to perform the desired set operation.
Macro expansion illustrates what is actually happening:
arc> (macex '(= (car (cadr l)) 'z))
((fn () (atwith (gs67 (cadr l) gs68 (quote z)) ((fn (val) (scar gs67 val)) gs68))))
When untangled, the above code is approximately doing (scar (cadr l) val), which will set the desired place to val.
arc> (macex '(= (z 1) #\b))
((fn () (atwith (gs69 z gs71 1 gs72 #\b) ((fn (gs70) (sref gs69 gs70 gs71)) gs72))))
Or approximately (sref z #\b 1).
Note that the generated code has little resemblance to the original assignment, and the code for a list assignment is very different from the code for a string assignment.
The details
Assignment has few layers of wrappers. The macro = simply calls expand=list, which pairs up the arguments and calls expand=. For a simple symbol assignment, expand= simply uses set. Otherwise, expand= uses setforms to determine the setter function, and then uses that function.
The core of assignment is setforms, which performs the analysis on a place. It returns a list of length three: (binds val setter), where val is a "getter" to return the current value at the place, setter is a function that takes the new value and assigns the new value to the place, and binds are variable bindings used by val and setter.
For example:
arc> (setforms 'x)
((gs75 x)
gs75
(fn (gs76) (set x gs76)))
The first item binds the variable x to a temporary. The getter simply returns the temporary. The setter is a function that will set x to the desired value.
A more complex example also illustrates the variable bindings, the getter form, and the setter function:
arc> (setforms '((car (x 3)) 2))
((gs2484 (car (x 3)) gs2486 2) (gs2484 gs2486) (fn (gs2485) (sref gs2484 gs2485 gs2486)))
arc> (setforms '((car (x 3)) 2))
((gs84 (car (x 3)) gs86 2)
(gs84 gs86)
(fn (gs85) (sref gs84 gs85 gs86)))
The table of setters
To determine how to handle a particular function, setforms uses
the global table setter. This table contains information on how to handle each function that can be used as a place.
arc> setter
#hash((cddr . #) (caar . #) (cdr . #) (cadr . #) (car . #))
The arc.arc file initializes the table. By default, only the limited set of functions above can be used as the outermost form in a place. Other functions that might be expected to work as places will fail:
arc> (= x '(a b c))
(a b c)
arc> (= (nthcdr 1 x) '(d))
Error: "procedure /c/mzscheme/ac.scm:1062:12: expects 3 arguments, given 4: # (d . nil) 1 (a b c . nil)"
As will be shown below, the setters table can be extended to support more functions as places.
The contents of the table are somewhat complex.
This table uses the outermost form of the place as key, and returns a procedure that, given an expression, will generate the setforms result for that expression. For example, to set the place (cdr (car x)):
arc> ((setter 'cdr) '(cdr (car x)))
((gs2593 (car x)) (cdr gs2593) (fn (val) (scdr gs2593 val)))
The setter table is initialized and updated via the defset macro. For instance, the arc.arc for using car as a place is:
(defset car (x)
(w/uniq g
(list (list g x)
`(car ,g)
`(fn (val) (scar ,g val)))))
The defset code can be compared with the the setcar output and the assignment macro expansion. The list returned by setforms directly matches the code above. The assignment expansion contains at its core the "setter" returned by setforms, wrapped in an atwith with the "binds" and the assignment value, all wrapped in a fn that is evaluated.
arc> (setforms '(car y))
((gs2413 y) (car gs2413) (fn (val) (scar gs2413 val)))
arc> (macex '(= (car y) 42))
((fn () (atwith (gs2416 y gs2417 42) ((fn (val) (scar gs2416 val)) gs2417))))
Confusingly, the arc.arc code uses "setter" both as the name of the global table, and as the name of the setter function returned by setforms.
The implementation of setforms
The setforms function is somewhat more complex than just a lookup in the setter table. It consists of three main paths.
Handling an expression that is a symbol is relatively straightforward. For a symbol with "special syntax", ssexpand is called to expand the special syntax, and setforms is tried again. For a regular symbol, setforms returns a straightforward set expression.
For a "metafn" expression (compose or complement), expand-metafn-call and ssexpand are applied and setforms is called again.
The third path is where setforms does its work. If the setter table has an entry for the outermost form, then setforms is done. Otherwise, setforms treats the expression as a data structure being indexed. (For example, (tbl 'key) to index into a table.) It generates the list of "binds", "getter", and "setter", where the getter is a simple invocation of the data structure and the setter uses sref. (Strangely, setforms supports multiple arguments to the data structure, even though sref does not. setforms also prints a warning if the expression is a function call.
Adding a new place type
Arc can be extended to handle new types of places. The defset macro is given code to generate the setforms list for the new place.
For example, suppose it is desired to make the last element of a list, (last g), a place that Arc can handle. The getter form is straightforward, and the last element could be set with (sref g val (- (len g) 1)). This is expressed to defset as:
(defset last (x)
(w/uniq (g)
(list (list g x)
`(last ,g)
`(fn (val) (sref ,g val (- (len ,g) 1))))))
The new place can be used in simple or combined cases:
arc> (= x '(a b c d e))
arc> (= (last x) 'z)
arc> x
(a b c d z)
arc> (= y '((a b c) d e (f g h)))
((a b c) d e (f g h))
arc> (= (last (car y)) 'lastcar)
arc> (= (car (last y)) 'carlast)
arc> y
((a b lastcar) d e (carlast g h))
The new place can also be used with zap, etc.
This implementation isn't particularly efficient, as the list is traversed twice, but it illustrates how generalized variables and places can be extended in Arc.
Another example shows how files can be made into places. The following code implements support for files as places; the expression (file "foo") will let the file "foo" be used as a place.
(def file (x) (readfile1 x))
(defset file (x)
(w/uniq (g)
(list (list g x)
`(readfile1 ,g)
`(fn (val) (writefile1 val ,g)))))
This allows files to be accessed directly with = and other operations that act on places:
arc> (= (file "foo") 42)
42
arc> (++ (file "foo"))
43
arc> (= (file "bar") 100)
100
arc> (swap (file "foo") (file "bar"))
43
arc> (file "foo")
100
arc> (file "bar")
43
At the end of this, the file "foo" contains 100, and "bar" contains 43, as expected.
Generalized variables in Lisp
Generalized variables have an extensive implementation in Common Lisp, which presumably provided the motivation for their Arc implementation.
See
chapter 12 of On Lisp for
a long discussion of generalized variables.
Many of the operations in Arc have analogous operations in Common Lisp.
Arc uses = to set a place to a value, while Common Lisp uses
setf.
Arc's setforms is similar to Common Lisp's get-setf-expansion.
The list of binds, val, and setter returned by setforms is similar to the
5 values making up a "setf expansion" in Common Lisp, where binds combines the list of temporary variables and the list of value forms, val is the accessing form, and setter takes the role of the storing form and list of store variables.
Arc's defset is similar to Common Lisp's define-setf-expander.
Operations to support places
setforms place
Generates the getter and setter code to access a place.
|
>(setforms '(car x))
((gs2459 x) (car gs2459) (fn (val) (scar gs2459 val)))
|
setter
(tests)
|
|
defset name parms [body ...]
Defines a new type of place. Creates a new setforms handler for the function of the specified name.
|
>(defset foo (x) nil)
#<procedure:...t/private/kw.rkt:592:14>
|
metafn x
Helper predicate for setforms. Tests if x is a meta function: that is, it has special syntax, or uses compose or complement.
|
>'(metafn '(a:b))
(metafn (quote (a:b)))
|
|
expand-metafn-call f args
Helper for setforms. Take a function of the form (compose ...) and expands it into the approprate composed function calls..
|
>(expand-metafn-call '(compose g h) '(a b))
(g (h a b))
|
|
expand= place val
Helper for =. Generates code to assign val to place.
|
>(expand= 'a 42)
(assign a 42)
|
|
expand=list terms
Helper for =. Pairs up the arguments to =, and calls expand= on each pair.
|
>(expand=list '(a 42 b 43))
(do (assign a 42) (assign b 43))
|
|
or= place val
Similar to the or macro, except assigns val to place if place is nil. New in arc3.
|
>(let x nil (or= x 4) (or= x 5) x)
4
|
Legend
: Foundation operation.
: Macro.
: Procedure.
: Variable.
: Destructive; arguments may be modified.
: Predicate.
: View code.
Copyright 2008 Ken Shirriff.