-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathsetforms.html
314 lines (302 loc) · 15.3 KB
/
setforms.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
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
<html dir="ltr">
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type"/>
<title>Arc: Internals of places and setforms</title>
<link rel="shortcut icon" href="/assets/favicon.png">
<link rel="stylesheet" type="text/css" href="code.css">
<link href="/assets/bootstrap.css" rel="stylesheet">
</head>
<body style='margin:12px 50px 0'>
<div class="navbar navbar-inverse">
<div class="navbar-inner">
<ul class="nav navbar-nav">
<li><a href="/ref/">Arc 3.1</a>
<li><a href="http://tryarc.org">Try it</a></li>
<li><a href="http://github.com/arclanguage/anarki">Get it</a></li>
<li><a href="http://ycombinator.com/arc/tut.txt">Tutorial</a></li>
<li><a href="http://arclanguage.org/forum">Forum</a></li>
</ul>
</div>
</div> <!-- end of navbar -->
<div class="links">Previous: <a href="app.html">The Arc application server</a>
Up: <a href="index.html">Contents</a>
Next: <a href="fnindex.html">Index</a>
</div>
<h1 class="links">Internals of places and setforms</h1>
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>.
<h2>Operations to support places</h2>
<p><table class='arc'>
<tr>
<td class='arc'><a name='setforms'></a>
<img src='proc.gif' title='Procedure'/>
<span class='op'>setforms</span> <span class='args'>place</span>
<div class='desc'>Generates the getter and setter code to access a place.</div>
</td>
<td class='arc'><pre>
>(setforms '(car x))
<span class="return">((gs2459 x) (car gs2459) (fn (val) (scar gs2459 val)))
</span></pre>
</td></tr>
<tr>
<td class='arc'><a name='setter'></a>
<img src='var.gif' title='Variable'/>
<span class='op'>setter</span> <span class='args'></span>
<div class='desc'>(tests)</div>
</td>
<td class='arc'> </td></tr>
<tr>
<td class='arc'><a name='defset'></a>
<img src='macro.gif' title='Macro'/>
<img src='destructive.gif' title='Destructive'/>
<span class='op'>defset</span> <span class='args'>name parms [body ...]</span>
<div class='desc'>Defines a new type of place. Creates a new <code>setforms</code> handler for the function of the specified name.</div>
</td>
<td class='arc'><pre>
>(defset foo (x) nil)
<span class="return">#<procedure:...t/private/kw.rkt:592:14>
</span></pre>
</td></tr>
<tr>
<td class='arc'><a name='metafn'></a>
<img src='proc.gif' title='Procedure'/>
<img src='predicate.gif' title='Predicate'/>
<span class='op'>metafn</span> <span class='args'>x</span>
<div class='desc'>Helper predicate for setforms. Tests if x is a meta function: that is, it has special syntax, or uses compose or complement.</div>
</td>
<td class='arc'><pre>
>'(metafn '(a:b))
<span class="return">(metafn (quote (a:b)))
</span></pre>
</td></tr>
<tr>
<td class='arc'><a name='expand-metafn-call'></a>
<img src='proc.gif' title='Procedure'/>
<span class='op'>expand-metafn-call</span> <span class='args'>f args</span>
<div class='desc'>Helper for setforms. Take a function of the form (compose ...) and expands it into the approprate composed function calls..</div>
</td>
<td class='arc'><pre>
>(expand-metafn-call '(compose g h) '(a b))
<span class="return">(g (h a b))
</span></pre>
</td></tr>
<tr>
<td class='arc'><a name='expand%3d'></a>
<img src='proc.gif' title='Procedure'/>
<span class='op'>expand=</span> <span class='args'>place val</span>
<div class='desc'>Helper for =. Generates code to assign val to place.</div>
</td>
<td class='arc'><pre>
>(expand= 'a 42)
<span class="return">(assign a 42)
</span></pre>
</td></tr>
<tr>
<td class='arc'><a name='expand%3dlist'></a>
<img src='proc.gif' title='Procedure'/>
<span class='op'>expand=list</span> <span class='args'>terms</span>
<div class='desc'>Helper for =. Pairs up the arguments to =, and calls expand= on each pair.</div>
</td>
<td class='arc'><pre>
>(expand=list '(a 42 b 43))
<span class="return">(do (assign a 42) (assign b 43))
</span></pre>
</td></tr>
</table>
<tr>
<td class='arc'><a name='or%3d'></a>
<img src='proc.gif' title='Procedure'/>
<span class='op'>or=</span> <span class='args'>place val</span>
<div class='desc'>Similar to the or macro, except assigns val to place if place is nil. New in arc3.</div>
</td>
<td class='arc'><pre>
>(let x nil (or= x 4) (or= x 5) x)
<span class="return">4
</span></pre>
</td></tr>
<h3>Legend</h3>
<img src='/doc/foundation.gif' title='Foundation'/>: Foundation operation.
<br><img src='/doc/macro.gif' title='Macro'/>: Macro.
<br><img src='/doc/proc.gif' title='Procedure'/>: Procedure.
<br><img src='/doc/var.gif' title='Variable'/>: Variable.
<br><img src='/doc/destructive.gif' title='Destructive'/>: Destructive; arguments may be modified.
<br><img src='/doc/predicate.gif' title='Predicate'/>: Predicate.
<br><img src='/doc/code.gif' title='View code'/>: View code.
<p>
Copyright 2008 Ken Shirriff.
</body>
</html>