-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathgen.html
188 lines (176 loc) · 10.5 KB
/
gen.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
Assignment and generalized variables are one of the most interesting parts of the Arc language. While assignment with <code>=</code> 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 <a href="assignment.html">Arc: Assignment</a>.
<p>
Assignment works with variables, tables, and strings:
<pre class="repl">
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"
</pre>
Assignment also works with complex list operations:
<pre class="repl">
arc> (= l '(a (b c) d))
arc> (= (car (cadr l)) 'z)
arc> l
(a (z c) d)
</pre>
In general, the destination of the assignment is called a "place" or a "generalized variable". The <code>=</code> macro assigns one or more values to one or more places.
<p>
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 <code>(= (z 1) #\p)</code> modifies a character inside <code>z</code>, instead of modifying the character returned by <code>(z 1)</code> Perhaps something like a C++ pointer or reference is being used?
<p>
The actual implementation is rather surprising. Assignment uses the <code>setform</code> 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:
<pre class="repl">
arc> (macex '(= (car (cadr l)) 'z))
((fn () (atwith (gs67 (cadr l) gs68 (quote z)) ((fn (val) (scar gs67 val)) gs68))))
</pre>
When untangled, the above code is approximately doing <code>(scar (cadr l) val)</code>, which will set the desired place to <code>val</code>.
<pre class="repl">
arc> (macex '(= (z 1) #\b))
((fn () (atwith (gs69 z gs71 1 gs72 #\b) ((fn (gs70) (sref gs69 gs70 gs71)) gs72))))
</pre>
Or approximately <code>(sref z #\b 1)</code>.
<p>
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.
<h2>The details</h2>
Assignment has few layers of wrappers. The macro <code>=</code> simply calls <code>expand=list</code>, which pairs up the arguments and calls <code>expand=</code>. For a simple symbol assignment, <code>expand=</code> simply uses <code>set</code>. Otherwise, <code>expand=</code> uses <code>setforms</code> to determine the setter function, and then uses that function.
<p>
The core of assignment is <code>setforms</code>, which performs the analysis on a place. It returns a list of length three: <code>(binds val setter)</code>, where <code>val</code> is a "getter" to return the current value at the place, <code>setter</code> is a function that takes the new value and assigns the new value to the place, and <code>binds</code> are variable bindings used by <code>val</code> and <code>setter</code>.
<p>
For example:
<pre class="repl">
arc> (setforms 'x)
((gs75 x)
gs75
(fn (gs76) (set x gs76)))
</pre>
The first item binds the variable <code>x</code> to a temporary. The getter simply returns the temporary. The setter is a function that will set <code>x</code> to the desired value.
<p>
A more complex example also illustrates the variable bindings, the getter form, and the setter function:
<pre class="repl">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)))
</pre>
<h2>The table of setters</h2>
To determine how to handle a particular function, <code>setforms</code> uses
the global table <code>setter</code>. This table contains information on how to handle each function that can be used as a place.
<pre class="repl">
arc> setter
#hash((cddr . #<procedure>) (caar . #<procedure>) (cdr . #<procedure>) (cadr . #<procedure>) (car . #<procedure>))
</pre>
The <code>arc.arc</code> 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:
<pre class="repl">
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: #<procedure: nthcdr> (d . nil) 1 (a b c . nil)"
</pre>
As will be shown below, the <code>setters</code> table can be extended to support more functions as places.
<p>
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 <code>setforms</code> result for that expression. For example, to set the place <code>(cdr (car x))</code>:
<pre class="repl">
arc> ((setter 'cdr) '(cdr (car x)))
((gs2593 (car x)) (cdr gs2593) (fn (val) (scdr gs2593 val)))
</pre>
The <code>setter</code> table is initialized and updated via the <code>defset</code> macro. For instance, the <code>arc.arc</code> for using <code>car</code> as a place is:
<pre class="code">
(defset car (x)
(w/uniq g
(list (list g x)
`(car ,g)
`(fn (val) (scar ,g val)))))
</pre>
The <code>defset</code> code can be compared with the the setcar output and the assignment macro expansion. The list returned by <code>setforms</code> directly matches the code above. The assignment expansion contains at its core the "setter" returned by <code>setforms</code>, wrapped in an <code>atwith</code> with the "binds" and the assignment value, all wrapped in a <code>fn</code> that is evaluated.
<pre class="repl">
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))))
</pre>
<p>
Confusingly, the <code>arc.arc</code> code uses "setter" both as the name of the global table, and as the name of the setter function returned by <code>setforms</code>.
<h2>The implementation of <code>setforms</code></h2>
The <code>setforms</code> function is somewhat more complex than just a lookup in the <code>setter</code> table. It consists of three main paths.
<p>
Handling an expression that is a symbol is relatively straightforward. For a symbol with "special syntax", <code>ssexpand</code> is called to expand the special syntax, and <code>setforms</code> is tried again. For a regular symbol, <code>setforms</code> returns a straightforward <code>set</code> expression.
<p>
For a "metafn" expression (<code>compose</code> or <code>complement</code>), <code>expand-metafn-call</code> and <code>ssexpand</code> are applied and <code>setforms</code> is called again.
<p>
The third path is where <code>setforms</code> does its work. If the <code>setter</code> table has an entry for the outermost form, then <code>setforms</code> is done. Otherwise, <code>setforms</code> treats the expression as a data structure being indexed. (For example, <code>(tbl 'key)</code> 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 <code>sref</code>. (Strangely, <code>setforms</code> supports multiple arguments to the data structure, even though <code>sref</code> does not. <code>setforms</code> also prints a warning if the expression is a function call.
<h2>Adding a new place type</h2>
Arc can be extended to handle new types of places. The <code>defset</code> macro is given code to generate the <code>setforms</code> list for the new place.
<p>
For example, suppose it is desired to make the last element of a list, <code>(last g)</code>, a place that Arc can handle. The getter form is straightforward, and the last element could be set with <code>(sref g val (- (len g) 1))</code>. This is expressed to <code>defset</code> as:
<pre class="repl">
(defset last (x)
(w/uniq (g)
(list (list g x)
`(last ,g)
`(fn (val) (sref ,g val (- (len ,g) 1))))))
</pre>
The new place can be used in simple or combined cases:
<pre class="repl">
arc> (= x '(a b c d e))
arc> (= (last x) 'z)
arc> x
(a b c d z)
</pre>
<pre class="repl">
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))
</pre>
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.
<p>
Another example shows how files can be made into places. The following code implements support for files as places; the expression <code>(file "foo")</code> will let the file "foo" be used as a place.
<pre class="code">
(def file (x) (readfile1 x))
(defset file (x)
(w/uniq (g)
(list (list g x)
`(readfile1 ,g)
`(fn (val) (writefile1 val ,g)))))
</pre>
This allows files to be accessed directly with <code>=</code> and other operations that act on places:
<pre class="repl">
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
</pre>
At the end of this, the file "foo" contains 100, and "bar" contains 43, as expected.
<h2>Generalized variables in Lisp</h2>
Generalized variables have an extensive implementation in Common Lisp, which presumably provided the motivation for their Arc implementation.
See
chapter 12 of <a href="http://www.paulgraham.com/onlisp.html">On Lisp</a> for
a long discussion of generalized variables.
<p>
Many of the operations in Arc have analogous operations in Common Lisp.
Arc uses <code>=</code> to set a place to a value, while Common Lisp uses
<a href="http://www.lispworks.com/documentation/HyperSpec/Body/m_setf_.htm">setf</a>.
Arc's <code>setforms</code> is similar to Common Lisp's <a href="http://www.lispworks.com/documentation/HyperSpec/Body/f_get_se.htm">get-setf-expansion</a>.
The list of binds, val, and setter returned by <code>setforms</code> 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 <code>defset</code> is similar to Common Lisp's <a href="http://www.lispworks.com/documentation/HyperSpec/Body/m_defi_3.htm">define-setf-expander</a>.