| 1 |
<html><head><title>XLISP Internals</title> |
| 2 |
|
| 3 |
<style type="text/css"> |
| 4 |
pre.example { |
| 5 |
color: #000000; |
| 6 |
background-color: #F5F5F5; |
| 7 |
padding-top: 8px; |
| 8 |
padding-right: 8px; |
| 9 |
padding-bottom: 8px; |
| 10 |
padding-left: 8px; |
| 11 |
border: #808080; |
| 12 |
border-style: solid; |
| 13 |
border-top-width: 1px; |
| 14 |
border-right-width: 1px; |
| 15 |
border-bottom-width: 1px; |
| 16 |
border-left-width: 1px; |
| 17 |
width:auto; |
| 18 |
} |
| 19 |
</style> |
| 20 |
|
| 21 |
</head> |
| 22 |
|
| 23 |
<body> |
| 24 |
|
| 25 |
<a href="../start.htm">Nyquist / XLISP 2.0</a> - |
| 26 |
<a href="../manual/contents.htm">Contents</a> | |
| 27 |
<a href="../tutorials/tutorials.htm">Tutorials</a> | |
| 28 |
<a href="../examples/examples.htm">Examples</a> | |
| 29 |
<a href="../reference/reference-index.htm">Reference</a> |
| 30 |
|
| 31 |
<hr> |
| 32 |
|
| 33 |
<h1>XLISP Internals</h1> |
| 34 |
|
| 35 |
<hr> |
| 36 |
|
| 37 |
<p>92Jan14 [email protected] [Jeff Prothero]. Public Domain.</p> |
| 38 |
|
| 39 |
<pre> |
| 40 |
+---------------------+ |
| 41 |
| xlisp 2.1 internals | |
| 42 |
+---------------------+ |
| 43 |
|
| 44 |
"Trust the Source, Luke, trust the Source!" |
| 45 |
</pre> |
| 46 |
|
| 47 |
<hr> |
| 48 |
|
| 49 |
<h2> Contents</h2> |
| 50 |
|
| 51 |
<hr> |
| 52 |
|
| 53 |
<ol> |
| 54 |
<li><nobr><a href="xlisp-internals.html#SEC01">Who should read this?</a></nobr></li> |
| 55 |
<li><nobr><a href="xlisp-internals.html#SEC02">What is an LVAL?</a></nobr></li> |
| 56 |
<li><nobr><a href="xlisp-internals.html#SEC03">What is the obarray?</a></nobr></li> |
| 57 |
<li><nobr><a href="xlisp-internals.html#SEC04">The Interpreter Stacks</a></nobr></li> |
| 58 |
<li><nobr><a href="xlisp-internals.html#SEC05">What is a context?</a></nobr></li> |
| 59 |
<li><nobr><a href="xlisp-internals.html#SEC06">What is an environment?</a></nobr></li> |
| 60 |
<li><nobr><a href="xlisp-internals.html#SEC07">How are XLISP entities stored and identified?</a></nobr></li> |
| 61 |
<li><nobr><a href="xlisp-internals.html#SEC08">How are vectors implemented?</a></nobr></li> |
| 62 |
<li><nobr><a href="xlisp-internals.html#SEC09">How are strings implemented?</a></nobr></li> |
| 63 |
<li><nobr><a href="xlisp-internals.html#SEC10">How are symbols implemented?</a></nobr></li> |
| 64 |
<li><nobr><a href="xlisp-internals.html#SEC11">How are closures implemented?</a></nobr></li> |
| 65 |
<li><nobr><a href="xlisp-internals.html#SEC12">How are objects implemented?</a></nobr></li> |
| 66 |
<li><nobr><a href="xlisp-internals.html#SEC13">How are classes implemented?</a></nobr></li> |
| 67 |
<li><nobr><a href="xlisp-internals.html#SEC14">How is the class hierarchy laid out?</a></nobr></li> |
| 68 |
<li><nobr><a href="xlisp-internals.html#SEC15">How do we look up the value of a variable?</a></nobr></li> |
| 69 |
<li><nobr><a href="xlisp-internals.html#SEC16">How are function calls implemented?</a></nobr></li> |
| 70 |
<li><nobr><a href="xlisp-internals.html#SEC17">How are message-sends implemented?</a></nobr></li> |
| 71 |
<li><nobr><a href="xlisp-internals.html#SEC18">How is garbage collection implemented?</a></nobr></li> |
| 72 |
<li><nobr><a href="xlisp-internals.html#SEC19">How are the source files laid out?</a></nobr></li> |
| 73 |
<li><nobr><a href="xlisp-internals.html#SEC20">How do I add a new primitive fn to xlisp?</a></nobr></li> |
| 74 |
<li><nobr><a href="xlisp-internals.html#SEC21">Minor Observations.</a></nobr></li> |
| 75 |
<li><nobr><a href="xlisp-internals.html#SEC22">Acknowledgements. </a></nobr></li> |
| 76 |
</ol> |
| 77 |
|
| 78 |
<a name="SEC01"></a> |
| 79 |
|
| 80 |
<hr> |
| 81 |
|
| 82 |
<h2>Who should read this ?</h2> |
| 83 |
|
| 84 |
<hr> |
| 85 |
|
| 86 |
<p>Anyone poking through the C implementation of XLISP for the first time. |
| 87 |
This is intended to provide a rough roadmap of the global XLISP structures |
| 88 |
and algorithms. If you just want to write lisp code in XLISP, you don't need |
| 89 |
to read this file. Go read the |
| 90 |
<nobr><a href="../manual/xlisp-man-index.htm">XLISP 2.0 Manual</a>,</nobr> |
| 91 |
the <nobr><a href="../tutorials/xlisp-objects.htm">XLisp Objects Primer</a>,</nobr> |
| 92 |
and the <nobr><a href="../reference/reference-index.htm">XLisp Language Reference</a>,</nobr> |
| 93 |
in about that order. If you want to tinker with the XLISP implementation |
| 94 |
code, you should *still* read those three before reading this. The following |
| 95 |
isn't intended to be exhaustively precise, that's what the source code is |
| 96 |
for. It is intended only to allow you a fighting change of understanding the |
| 97 |
code the first time through [instead of the third time].</p> |
| 98 |
|
| 99 |
<p>At the bottom of the file you'll find an example of how to add new |
| 100 |
primitive functions to XLISP.</p> |
| 101 |
|
| 102 |
<p><nobr> <a href="#top">Back to top</a></nobr></p> |
| 103 |
|
| 104 |
<a name="SEC02"></a> |
| 105 |
|
| 106 |
<hr> |
| 107 |
|
| 108 |
<h2>What is an LVAL ?</h2> |
| 109 |
|
| 110 |
<hr> |
| 111 |
|
| 112 |
<p>An LVAL is the C type for a generic pointer to an XLISP |
| 113 |
garbage-collectable something. [Cons cell, object, string, closure, symbol, |
| 114 |
vector, whatever.] Virtually every variable in the interpreter is an LVAL. |
| 115 |
Cons cells contain two LVAL slots, symbols contains four LVAL slots, |
| 116 |
etc.</p> |
| 117 |
|
| 118 |
<p><nobr> <a href="#top">Back to top</a></nobr></p> |
| 119 |
|
| 120 |
<a name="SEC03"></a> |
| 121 |
|
| 122 |
<hr> |
| 123 |
|
| 124 |
<h2>What is the obarray ?</h2> |
| 125 |
|
| 126 |
<hr> |
| 127 |
|
| 128 |
<p>The obarray is the XLISP symbol table. More precisely, it is a hashtable |
| 129 |
mapping ASCII strings [symbol names] to symbols. [The name 'obarray' is |
| 130 |
traditional but a bit of a misnomer, since it contains only XLISP symbols, |
| 131 |
and in particular contains no XLISP objects.] It is used when converting |
| 132 |
Lisp expressions from text to internal form. Since it is a root for the |
| 133 |
garbage collector, it also serves to distinguish permanent global-variable |
| 134 |
symbols from other symbols. You can permanently protect a symbol from the |
| 135 |
garbage collector by entering it into the obarray. This is called |
| 136 |
'interning' the symbol. The obarray is called 'obarray' in C and |
| 137 |
<a href="../reference/global-obarray.htm">*obarray*</a> |
| 138 |
in XLISP. It is physically implemented as a vector-valued symbol.</p> |
| 139 |
|
| 140 |
<p><nobr> <a href="#top">Back to top</a></nobr></p> |
| 141 |
|
| 142 |
<a name="SEC04"></a> |
| 143 |
|
| 144 |
<hr> |
| 145 |
|
| 146 |
<h2>The Interpreter Stacks</h2> |
| 147 |
|
| 148 |
<hr> |
| 149 |
|
| 150 |
<p>XLISP uses two stacks, an 'evaluation stack' and an 'argument stack'. |
| 151 |
Both are roots for the garbage collector. The evaluation stack is largely |
| 152 |
private to the interpreter and protects internal values from garbage |
| 153 |
collection, while the argument stack holds the conventional user-visible |
| 154 |
stackframes.</p> |
| 155 |
|
| 156 |
<p>The evaluation stack is an 'edepth'-long array of LVAL allocated by |
| 157 |
'xldmem.c:xlminit()'. It grows zeroward.</p> |
| 158 |
|
| 159 |
<p>'xlstkbase' points to the zero-near end of the evaluation stack.</p> |
| 160 |
|
| 161 |
<p>'xlstktop' points to the zero-far end of the evaluation stack, the |
| 162 |
occupied part of the stack lies between 'xlstack' and 'xlstktop'. Note that |
| 163 |
'xlstktop' is *NOT* the top of the stack in the conventional sense of |
| 164 |
indicating the most recent entry on the stack. 'xlstktop' is a static bounds |
| 165 |
pointer which never changes once the stack is allocated.</p> |
| 166 |
|
| 167 |
<p>'xlstack' starts at the zero-far end of the evaluation stack. '*xlstack' |
| 168 |
is the most recent LVAL on the stack. The garbage collector marks everything |
| 169 |
reachable from the evaluation stack [among other things], so we frequently |
| 170 |
push things on this stack while C code is manipulating them. [Via |
| 171 |
'xlsave()', 'xlprotect()', 'xlsave1()', 'xlprot1()'.]</p> |
| 172 |
|
| 173 |
<p>The argument stack is an 'adepth'-long array of LVAL. It also grows |
| 174 |
zeroward. The evaluator pushes arguments on the argument stack at the start |
| 175 |
of a function call [form evaluation]. Built-in functions usually eat them |
| 176 |
directly off the stack. For user-lisp functions 'xleval.c:evfun()' pops them |
| 177 |
off the stack and binds them to the appropriate symbols before beginning |
| 178 |
execution of the function body proper.</p> |
| 179 |
|
| 180 |
<p><table cellpadding="0" cellspacing="0" style="margin-left:10px"><tbody> |
| 181 |
<tr valign="top"> |
| 182 |
<td colspan="3"><nobr><b>xlargstkbase</b></nobr></td> |
| 183 |
<td><nobr> - </nobr></td> |
| 184 |
<td width="100%">is the zero-near end of argument stack.</td> |
| 185 |
</tr> |
| 186 |
<tr> |
| 187 |
<td><nobr><font size="-2"> </font></nobr></td> |
| 188 |
</tr> |
| 189 |
<tr valign="top"> |
| 190 |
<td colspan="3"><nobr><b>xlargstktop</b></nobr></td> |
| 191 |
<td><nobr> - </nobr></td> |
| 192 |
<td width="100%">is the zero-far end of argument stack. Like 'xlstktop', |
| 193 |
'xlargstktop' is a static bounds pointer which never changes after the |
| 194 |
stack is allocated.</td> |
| 195 |
</tr> |
| 196 |
<tr> |
| 197 |
<td><nobr><font size="-2"> </font></nobr></td> |
| 198 |
</tr> |
| 199 |
<tr valign="top"> |
| 200 |
<td><nobr><b>*xlsp</b></nobr></td> |
| 201 |
<td><nobr><code> </code></nobr></td> |
| 202 |
<td><nobr>[stack pointer]</nobr></td> |
| 203 |
<td><nobr> - </nobr></td> |
| 204 |
<td width="100%">is the most recent item on the argument stack.</td> |
| 205 |
</tr> |
| 206 |
<tr> |
| 207 |
<td><nobr><font size="-2"> </font></nobr></td> |
| 208 |
</tr> |
| 209 |
<tr valign="top"> |
| 210 |
<td><nobr><b>*xlfp</b></nobr></td> |
| 211 |
<td><nobr><code> </code></nobr></td> |
| 212 |
<td><nobr>[frame pointer]</nobr></td> |
| 213 |
<td><nobr> - </nobr></td> |
| 214 |
<td width="100%">is the base of the current stackframe.</td> |
| 215 |
</tr> |
| 216 |
</tbody></table></p> |
| 217 |
|
| 218 |
<p><nobr> <a href="#top">Back to top</a></nobr></p> |
| 219 |
|
| 220 |
<a name="SEC05"></a> |
| 221 |
|
| 222 |
<hr> |
| 223 |
|
| 224 |
<h2>What is a context ?</h2> |
| 225 |
|
| 226 |
<hr> |
| 227 |
|
| 228 |
<p>A XLISP context is something like a checkpoint, recording a particular |
| 229 |
point buried in the execution history so that we can abort or return back to |
| 230 |
it. Contexts are used to implement call and return, catch and throw, |
| 231 |
signals, gotos, and breaks. 'xlcontext' points to the chain of active |
| 232 |
contexts, the top one being the second-newest active context. [The newest, |
| 233 |
that is, the current, active context is implemented by the variables |
| 234 |
'xlstack', 'xlenv', 'xlfenv', 'xldenv', 'xlcontext', 'xlargv', 'xlargc', |
| 235 |
'xlfp', and 'xlsp'.] Context records are written by 'xljump.c:xlbegin()' and |
| 236 |
read by 'xljump.c:xljump()'. Context records are C structures on the C |
| 237 |
program stack. They are not in the dynamic memory pool or on the Lisp |
| 238 |
execution or argument stacks.</p> |
| 239 |
|
| 240 |
<p><nobr> <a href="#top">Back to top</a></nobr></p> |
| 241 |
|
| 242 |
<a name="SEC06"></a> |
| 243 |
|
| 244 |
<hr> |
| 245 |
|
| 246 |
<h2>What is an environment ?</h2> |
| 247 |
|
| 248 |
<hr> |
| 249 |
|
| 250 |
<p>An environment is basically a store of symbol-value pairs, used to |
| 251 |
resolve variable references by the Lisp program. XLISP maintains three |
| 252 |
environments, in the global variables 'xlenv', 'xlfenv' and 'xldenv'.</p> |
| 253 |
|
| 254 |
<p>Lisp supports two sorts of binding, 'lexical binding' and 'dynamic |
| 255 |
binding'. Lexically bound variables are visible only in code textually |
| 256 |
within their binding form. Dynamically bound variables are visible in any |
| 257 |
code *called* from the binding form. [Either kind of binding may be shadowed |
| 258 |
by other declarations, of course.] Historically, Lisp has been moving from |
| 259 |
dynamic binding [which is easy for interpreters to handle], to lexical |
| 260 |
binding [which is easy for humans and compilers to handle]. Almost all XLISP |
| 261 |
binding forms are lexically scoped. The most important exception is |
| 262 |
<a href="../reference/progv.htm">progv</a>.</p> |
| 263 |
|
| 264 |
<p>'xlenv' and 'xlfenv' track lexical bindings. 'xlenv' and 'xlfenf' are |
| 265 |
conceptually a single environment, although they are implemented separately. |
| 266 |
They are linked-list stacks which are pushed when we enter a function and |
| 267 |
popped when we exit it. We also switch 'xlenv+xlfenf' environments entirely |
| 268 |
when we begin executing a new closure [user-function written in Lisp].</p> |
| 269 |
|
| 270 |
<p>The 'xlenv' environment is the most heavily used environment. It is used |
| 271 |
to resolve everyday data references to local variables. It consists of a |
| 272 |
list of frames [and objects]. Each frame is a list of symbol-value pairs. In |
| 273 |
the case of an object, we check all the instance and class variables of the |
| 274 |
object, then do the same for its superclass, until we run out of |
| 275 |
superclasses.</p> |
| 276 |
|
| 277 |
<p>The 'xlfenv' environment is maintained strictly parallel to 'xlenv', but |
| 278 |
is used to find function values instead of variable values. The separation |
| 279 |
may be partly for lookup speed and partly for historical reasons. Merging |
| 280 |
these two lists into a single list [while distinguishing function bindings |
| 281 |
from variable bindings, of course] would slightly decrease fn enter/exit |
| 282 |
overhead while increasing the overhead of looking up each variable or |
| 283 |
function binding.</p> |
| 284 |
|
| 285 |
<p>When we send a message, we set 'xlenv' to the value it had when the |
| 286 |
message closure was built, then push on (obj msg-class), where 'msg-class' |
| 287 |
is the [super]class defining the method. [We also set 'xlfenv' to the value |
| 288 |
'xlfenv' had when the method was built.] This makes the object instance |
| 289 |
variables part of the environment, and saves the information needed to |
| 290 |
correctly resolve references to class variables, and to implement |
| 291 |
<a href="../reference/send-super.htm">send-super</a>.</p> |
| 292 |
|
| 293 |
<p>The 'xldenv' environment tracks dynamic bindings. It is a simple list of |
| 294 |
symbol-value pairs, treated as a stack. |
| 295 |
<a href="../reference/progv.htm">progv</a> uses it to save the old |
| 296 |
values of symbols it binds, and it is also used to save old values of |
| 297 |
's_evalhook' and 's_applyhook' |
| 298 |
[<a href="../reference/global-evalhook.htm">*evalhook*</a> and |
| 299 |
<a href="../reference/global-applyhook.htm">*applyhook*</a>]. These latter |
| 300 |
mostly support the debug facilities.</p> |
| 301 |
|
| 302 |
<p>These environments are manipulated in C via the 'xlisp.h' macros |
| 303 |
'xlframe(e)', 'xlbind(s,v)', 'xlfbind(s,v)', 'xlpbind(s,v,e)', |
| 304 |
'xldbind(s,v)', 'xlunbind(e)'.</p> |
| 305 |
|
| 306 |
<p><nobr> <a href="#top">Back to top</a></nobr></p> |
| 307 |
|
| 308 |
<a name="SEC07"></a> |
| 309 |
|
| 310 |
<hr> |
| 311 |
|
| 312 |
<h2>How are XLISP entities stored and identified ?</h2> |
| 313 |
|
| 314 |
<hr> |
| 315 |
|
| 316 |
<p>Conceptually, XLISP manages memory as a single array of fixed-size |
| 317 |
objects. Keeping all objects the same size simplifies memory management |
| 318 |
enormously, since any object can be allocated anywhere, and complex |
| 319 |
compacting schemes aren't needed. Every LVAL pointer points somewhere in |
| 320 |
this array. Every XLISP object has the basic format <nobr>'xldmem.h:typdef |
| 321 |
struct node':</nobr></p> |
| 322 |
|
| 323 |
<pre class="example"> |
| 324 |
struct node { |
| 325 |
char n_type; |
| 326 |
char n_flags; |
| 327 |
LVAL car; |
| 328 |
LVAL cdr; |
| 329 |
} |
| 330 |
</pre> |
| 331 |
|
| 332 |
<p>where 'n_type' is one of:</p> |
| 333 |
|
| 334 |
<p><table cellpadding="0" cellspacing="0" style="margin-left:10px"><tbody> |
| 335 |
<tr valign="top"> |
| 336 |
<td><nobr><b>FREE</b></nobr></td> |
| 337 |
<td><nobr> - </nobr></td> |
| 338 |
<td width="100%">a node on the freelist.</td> |
| 339 |
</tr> |
| 340 |
<tr valign="top"> |
| 341 |
<td><nobr><b>SUBR</b></nobr></td> |
| 342 |
<td><nobr> - </nobr></td> |
| 343 |
<td width="100%">a function implemented in C. [Needs evaluated arguments.]</td> |
| 344 |
</tr> |
| 345 |
<tr valign="top"> |
| 346 |
<td><nobr><b>FSUBR</b></nobr></td> |
| 347 |
<td><nobr> - </nobr></td> |
| 348 |
<td width="100%">a 'special form' implemented in C. [Needs unevaluated arguments.]</td> |
| 349 |
</tr> |
| 350 |
<tr valign="top"> |
| 351 |
<td><nobr><b>CONS</b></nobr></td> |
| 352 |
<td><nobr> - </nobr></td> |
| 353 |
<td width="100%">a regular lisp cons cell.</td> |
| 354 |
</tr> |
| 355 |
<tr valign="top"> |
| 356 |
<td><nobr><b>SYMBOL</b></nobr></td> |
| 357 |
<td><nobr> - </nobr></td> |
| 358 |
<td width="100%">a symbol.</td> |
| 359 |
</tr> |
| 360 |
<tr valign="top"> |
| 361 |
<td><nobr><b>FIXNUM</b></nobr></td> |
| 362 |
<td><nobr> - </nobr></td> |
| 363 |
<td width="100%">an integer.</td> |
| 364 |
</tr> |
| 365 |
<tr valign="top"> |
| 366 |
<td><nobr><b>FLONUM</b></nobr></td> |
| 367 |
<td><nobr> - </nobr></td> |
| 368 |
<td width="100%">a floating-point number.</td> |
| 369 |
</tr> |
| 370 |
<tr valign="top"> |
| 371 |
<td><nobr><b>STRING</b></nobr></td> |
| 372 |
<td><nobr> - </nobr></td> |
| 373 |
<td width="100%">a string.</td> |
| 374 |
</tr> |
| 375 |
<tr valign="top"> |
| 376 |
<td><nobr><b>OBJECT</b></nobr></td> |
| 377 |
<td><nobr> - </nobr></td> |
| 378 |
<td width="100%">any object, including |
| 379 |
<a href="../reference/class.htm">class</a> objects.</td> |
| 380 |
</tr> |
| 381 |
<tr valign="top"> |
| 382 |
<td><nobr><b>STREAM</b></nobr></td> |
| 383 |
<td><nobr> - </nobr></td> |
| 384 |
<td width="100%">an input or output file.</td> |
| 385 |
</tr> |
| 386 |
<tr valign="top"> |
| 387 |
<td><nobr><b>VECTOR</b></nobr></td> |
| 388 |
<td><nobr> - </nobr></td> |
| 389 |
<td width="100%">a variable-size array of LVALs.</td> |
| 390 |
</tr> |
| 391 |
<tr valign="top"> |
| 392 |
<td><nobr><b>CLOSURE</b></nobr></td> |
| 393 |
<td><nobr> - </nobr></td> |
| 394 |
<td width="100%">result of <a href="../reference/defun.htm">defun</a> |
| 395 |
or <a href="../reference/lambda.htm">lambda</a>, a function |
| 396 |
written in Lisp.</td> |
| 397 |
</tr> |
| 398 |
<tr valign="top"> |
| 399 |
<td><nobr><b>CHAR</b></nobr></td> |
| 400 |
<td><nobr> - </nobr></td> |
| 401 |
<td width="100%">an ASCII character.</td> |
| 402 |
</tr> |
| 403 |
<tr valign="top"> |
| 404 |
<td><nobr><b>USTREAM</b></nobr></td> |
| 405 |
<td><nobr> - </nobr></td> |
| 406 |
<td width="100%">an internal stream.</td> |
| 407 |
</tr> |
| 408 |
<tr valign="top"> |
| 409 |
<td><nobr><b>STRUCT</b></nobr></td> |
| 410 |
<td><nobr> - </nobr></td> |
| 411 |
<td width="100%">a structure.</td> |
| 412 |
</tr> |
| 413 |
</tbody></table></p> |
| 414 |
|
| 415 |
<p>Messages may be sent only to nodes with a 'n_type' of OBJECT.</p> |
| 416 |
|
| 417 |
<p>Obviously, several of the above types won't fit in a fixed-size two-slot |
| 418 |
node. The escape is to have them 'malloc()' some memory and have one of the |
| 419 |
slots point to it. VECTOR is the archetype. For example, see |
| 420 |
'xldmem.c:newvector()'. To some extent, this 'malloc()' hack simply exports |
| 421 |
the memory fragmentation problem to the C 'malloc()/free()' routines. |
| 422 |
However, it helps keep XLISP simple, and it has the happy side-effect of |
| 423 |
unpinning the body of the vector, so that vectors can easily be expanded and |
| 424 |
contracted.</p> |
| 425 |
|
| 426 |
<p>The garbage collector has special-case code for each of the above node |
| 427 |
types, so it can find all LVAL slots and recycle any 'malloc()'-ed ram when |
| 428 |
a node is garbage-collected.</p> |
| 429 |
|
| 430 |
<p>XLISP pre-allocates nodes for all ASCII characters, and for small |
| 431 |
integers. These nodes are never garbage-collected.</p> |
| 432 |
|
| 433 |
<p>As a practical matter, allocating all nodes in a single array is not very |
| 434 |
sensible. Instead, nodes are allocated as needed, in segments of one or two |
| 435 |
thousand nodes, and the segments linked by a pointer chain rooted at |
| 436 |
'xldmem.c:segs'.</p> |
| 437 |
|
| 438 |
<p><nobr> <a href="#top">Back to top</a></nobr></p> |
| 439 |
|
| 440 |
<a name="SEC08"></a> |
| 441 |
|
| 442 |
<hr> |
| 443 |
|
| 444 |
<h2>How are vectors implemented ?</h2> |
| 445 |
|
| 446 |
<hr> |
| 447 |
|
| 448 |
<p>An XLISP vector is a generic array of LVAL slots. Vectors are also the |
| 449 |
canonical illustration of XLISP's escape mechanism for node types which need |
| 450 |
more than two LVAL slots [the maximum possible in the fixed-size nodes in |
| 451 |
the dynamic memory pool]. The node CAR/CDR slots for a vector hold a size |
| 452 |
field plus a pointer to a 'malloc()'-ed ram chunk, which is automatically |
| 453 |
'free()'-ed when the vector is garbage-collected.</p> |
| 454 |
|
| 455 |
<p>'xldmem.h' defines macros for reading and writing vector fields and |
| 456 |
slots, 'getsize()', 'getelement()' and 'setelement()'. It also defines |
| 457 |
macros for accessing each of the other types of XLISP nodes.</p> |
| 458 |
|
| 459 |
<p><nobr> <a href="#top">Back to top</a></nobr></p> |
| 460 |
|
| 461 |
<a name="SEC09"></a> |
| 462 |
|
| 463 |
<hr> |
| 464 |
|
| 465 |
<h2>How are strings implemented ?</h2> |
| 466 |
|
| 467 |
<hr> |
| 468 |
|
| 469 |
<p>Strings work much like vectors. The node has a pointer to a 'malloc()'-ed |
| 470 |
ram chunk which is automatically 'free()'-ed when the string gets |
| 471 |
garbage-collected.</p> |
| 472 |
|
| 473 |
<p><nobr> <a href="#top">Back to top</a></nobr></p> |
| 474 |
|
| 475 |
<a name="SEC10"></a> |
| 476 |
|
| 477 |
<hr> |
| 478 |
|
| 479 |
<h2>How are symbols implemented ?</h2> |
| 480 |
|
| 481 |
<hr> |
| 482 |
|
| 483 |
<p>A symbol is a generic user-visible Lisp variable, with separate slots for |
| 484 |
print name, value, function, and property list. Any or all of these slots |
| 485 |
[including name] may be NIL.</p> |
| 486 |
|
| 487 |
<p>You create an XLISP symbol from C by calling 'xlmakesym(name)' or |
| 488 |
'xlenter(name)' [to make a symbol and enter it in the obarray].</p> |
| 489 |
|
| 490 |
<p>You may create symbols from XLISP by explicitly calling |
| 491 |
<a href="../reference/gensym.htm">gensym</a>, |
| 492 |
<a href="reference/make-symbol.htm">make-symbol</a> [uninterned symbols], |
| 493 |
or <a href="../reference/intern.htm">intern</a> [interned symbol]. |
| 494 |
However, the Lisp reader will create symbols on sight, so most Lisp symbols |
| 495 |
are created as side-effects of expressions like:</p> |
| 496 |
|
| 497 |
<pre class="example"> |
| 498 |
'name |
| 499 |
</pre> |
| 500 |
|
| 501 |
<p>A symbol is <a href="../reference/intern.htm">intern</a>ed if it |
| 502 |
is listed in the <a href="../reference/global-obarray.htm">*obarray*</a>. |
| 503 |
Various parts of the system, like the Lisp reader, treat the |
| 504 |
<a href="../reference/global-obarray.htm">*obarray*</a> |
| 505 |
essentially as the list of all known symbols. It is unusual but occasionally |
| 506 |
useful to create uninterned symbols. You can make |
| 507 |
<a href="../reference/read.htm">read</a> create an uninterned |
| 508 |
symbol by preceding it with '#:'. In XLISP, a newly created symbol has no |
| 509 |
value unless its name begins with a ':', in which case it has itself for its |
| 510 |
value. Handy for keywords and message selectors.]</p> |
| 511 |
|
| 512 |
<p>Most of the symbol-specific code in the interpreter is in 'xlsym.c'.</p> |
| 513 |
|
| 514 |
<p>Physically, a symbol is implemented like a four-slot vector [print name, |
| 515 |
value, function, and property list].</p> |
| 516 |
|
| 517 |
<p>Random musing: Abstractly, the Lisp symbols plus cons cells [etc.] |
| 518 |
constitute a single directed graph, and the symbols mark spots where normal |
| 519 |
recursive evaluation should stop. Normal Lisp programming practice is to |
| 520 |
have a symbol in every cycle in the graph, so that recursive traversal can |
| 521 |
be done without mark bits.</p> |
| 522 |
|
| 523 |
<p><nobr> <a href="#top">Back to top</a></nobr></p> |
| 524 |
|
| 525 |
<a name="SEC11"></a> |
| 526 |
|
| 527 |
<hr> |
| 528 |
|
| 529 |
<h2>How are closures implemented ?</h2> |
| 530 |
|
| 531 |
<hr> |
| 532 |
|
| 533 |
<p>A closure, the return value from a |
| 534 |
<a href="../reference/lambda.htm">lambda</a>, is a regular |
| 535 |
coded-in-lisp function. Physically, it is implemented like an eleven-slot |
| 536 |
vector, with the node 'n_type' field hacked to contain CLOSURE instead of |
| 537 |
VECTOR. The vector slots contain:</p> |
| 538 |
|
| 539 |
<p><table cellpadding="0" cellspacing="0" style="margin-left:10px"><tbody> |
| 540 |
<tr valign="top"> |
| 541 |
<td><nobr><b>name</b></nobr></td> |
| 542 |
<td><nobr> - </nobr></td> |
| 543 |
<td width="100%">a symbol, the first argument of |
| 544 |
<a href="../reference/defun.htm">defun</a>. |
| 545 |
<a href="../reference/nil.htm">nil</a> for |
| 546 |
<a href="../reference/lambda.htm">lambda</a> closures.</td> |
| 547 |
</tr> |
| 548 |
<tr valign="top"> |
| 549 |
<td><nobr><b>type</b></nobr></td> |
| 550 |
<td><nobr> - </nobr></td> |
| 551 |
<td width="100%">'s_lambda' or 's_macro'. Must be 's_lambda' to be |
| 552 |
executable.</td> |
| 553 |
</tr> |
| 554 |
<tr valign="top"> |
| 555 |
<td><nobr><b>args</b></nobr></td> |
| 556 |
<td><nobr> - </nobr></td> |
| 557 |
<td width="100%">list of required formal arguments [as symbols].</td> |
| 558 |
</tr> |
| 559 |
<tr valign="top"> |
| 560 |
<td><nobr><b>oargs</b></nobr></td> |
| 561 |
<td><nobr> - </nobr></td> |
| 562 |
<td width="100%">list of |
| 563 |
<a href="../reference/lambda-keyword-optional.htm">&optional</a> arguments, |
| 564 |
each like <nobr>(name (default specified-p)).</nobr></td> |
| 565 |
</tr> |
| 566 |
<tr valign="top"> |
| 567 |
<td><nobr><b>rest</b></nobr></td> |
| 568 |
<td><nobr> - </nobr></td> |
| 569 |
<td width="100%">name of '&rest' formal arguments, else |
| 570 |
<a href="../reference/nil.htm">nil</a>.</td> |
| 571 |
</tr> |
| 572 |
<tr valign="top"> |
| 573 |
<td><nobr><b>kargs</b></nobr></td> |
| 574 |
<td><nobr> - </nobr></td> |
| 575 |
<td width="100%"><a href="../reference/lambda-keyword-key.htm">&key</a>-word |
| 576 |
arguments, each like <nobr>((':foo 'bar default specified-p))</nobr></td> |
| 577 |
</tr> |
| 578 |
<tr valign="top"> |
| 579 |
<td><nobr><b>aargs</b></nobr></td> |
| 580 |
<td><nobr> - </nobr></td> |
| 581 |
<td width="100%"><a href="../reference/lambda-keyword-aux.htm">&aux</a> |
| 582 |
variables, each like <nobr>(('arg default)).</nobr></td> |
| 583 |
</tr> |
| 584 |
<tr valign="top"> |
| 585 |
<td><nobr><b>body</b></nobr></td> |
| 586 |
<td><nobr> - </nobr></td> |
| 587 |
<td width="100%">actual code [as a Lisp list] for the function.</td> |
| 588 |
</tr> |
| 589 |
<tr valign="top"> |
| 590 |
<td><nobr><b>env</b></nobr></td> |
| 591 |
<td><nobr> - </nobr></td> |
| 592 |
<td width="100%">value of 'xlenv' when the closure was built.</td> |
| 593 |
</tr> |
| 594 |
<tr valign="top"> |
| 595 |
<td><nobr><b>fenv</b></nobr></td> |
| 596 |
<td><nobr> - </nobr></td> |
| 597 |
<td width="100%">value of 'xlfend' when the closure was built.</td> |
| 598 |
</tr> |
| 599 |
<tr valign="top"> |
| 600 |
<td><nobr><b>lambda</b></nobr></td> |
| 601 |
<td><nobr> - </nobr></td> |
| 602 |
<td width="100%">the original formal args list in the |
| 603 |
<a href="../reference/defun.htm">defun</a> or |
| 604 |
<a href="../reference/lambda.htm">lambda</a>.</td> |
| 605 |
</tr> |
| 606 |
</tbody></table></p> |
| 607 |
|
| 608 |
<p>The lambda field is for printout purposes. The remaining fields store a |
| 609 |
predigested version of the formal arguments list. This is a limited form of |
| 610 |
compilation. By processing the arguments list at closure-creation time, we |
| 611 |
reduce the work needed during calls to the closure.</p> |
| 612 |
|
| 613 |
<p><nobr> <a href="#top">Back to top</a></nobr></p> |
| 614 |
|
| 615 |
<a name="SEC12"></a> |
| 616 |
|
| 617 |
<hr> |
| 618 |
|
| 619 |
<h2>How are objects implemented ?</h2> |
| 620 |
|
| 621 |
<hr> |
| 622 |
|
| 623 |
<p>An object is implemented like a vector, with the size determined by the |
| 624 |
number of instance variables. The first slot in the vector points to the |
| 625 |
class of the object, the remaining slots hold the instance variables for the |
| 626 |
object. An object needs enough slots to hold all the instance variables |
| 627 |
defined by its class, *plus* all the instance variables defined by all of |
| 628 |
its superclasses.</p> |
| 629 |
|
| 630 |
<p><nobr> <a href="#top">Back to top</a></nobr></p> |
| 631 |
|
| 632 |
<a name="SEC13"></a> |
| 633 |
|
| 634 |
<hr> |
| 635 |
|
| 636 |
<h2>How are classes implemented ?</h2> |
| 637 |
|
| 638 |
<hr> |
| 639 |
|
| 640 |
<p>A class is a specific kind of object, hence has a class pointer plus |
| 641 |
instance variables. All classes have the following instance variables:</p> |
| 642 |
|
| 643 |
<pre> |
| 644 |
MESSAGES a list of <nobr>(interned-symbol method-closure)</nobr> pairs. |
| 645 |
IVARS instance variable names, a list of interned symbols. |
| 646 |
CVARS class variable names, a list of interned symbols. |
| 647 |
CVALS class variable values, a vector of values. |
| 648 |
SUPERCLASS a pointer to the superclass. |
| 649 |
IVARCNT the number of class instance variables, a fixnum. |
| 650 |
IVARTOTAL the total number of instance variables, a fixnum. |
| 651 |
</pre> |
| 652 |
|
| 653 |
<p>IVARCNT is the count of the number of instance variables defined by our |
| 654 |
class. IVARTOTAL is the total number of instance variables in an object of this |
| 655 |
class -- IVARCNT for this class plus the IVARCNTs from all of our |
| 656 |
superclasses.</p> |
| 657 |
|
| 658 |
<table cellpadding="0"><tbody><tr><td> </td><td bgcolor="eeeeee"> |
| 659 |
<a href="xlisp-internals.html#SEC00">Back to Top</a></nobr></li> |
| 660 |
</tr></tbody></table> |
| 661 |
|
| 662 |
<h3><a name="SEC14">How is the class hierarchy laid out ?</a></h3> |
| 663 |
|
| 664 |
<p>The fundamental objects are the OBJECT and CLASS class objects. (Both are |
| 665 |
instances of class CLASS, and since CLASSes are a particular kind of OBJECT, |
| 666 |
both are also objects, with n_type==OBJECT. Bear with me!)</p> |
| 667 |
|
| 668 |
<p>OBJECT is the root of the class hierarchy: everything you can send a message |
| 669 |
to has OBJECT as its class or super*class. (Vectors, chars, integers and so |
| 670 |
forth stand outside the object hierarchy -- you can't send messages to them. I'm |
| 671 |
not sure why Dave did it this way.) OBJECT defines the messages:</p> |
| 672 |
|
| 673 |
<pre> |
| 674 |
:isnew -- Does nothing but return the object. |
| 675 |
:class -- Returns contents of class-pointer slot. |
| 676 |
:show -- Prints names of obj, obj->class and instance vars. |
| 677 |
</pre> |
| 678 |
|
| 679 |
<p>Since a CLASS is a specialized type of OBJECT (with instance variables like |
| 680 |
MESSAGES which generic OBJECTs lack), class CLASS has class OBJECT as its |
| 681 |
superclass. The CLASS object defines the messages:</p> |
| 682 |
|
| 683 |
<pre> |
| 684 |
:new -- Create new object with self.IVARTOTAL LVAR slots, plus |
| 685 |
one for the class pointer. Point class slot to self. |
| 686 |
Set new.n_type char to OBJECT. |
| 687 |
:isnew -- Fill in IVARS, CVARS, CVALS, SUPERCLASS, IVARCNT and |
| 688 |
IVARTOTAL, using parameters from :new call. (The |
| 689 |
:isnew msg inherits the :new msg parameters because |
| 690 |
the :isnew msg is generated automatically after |
| 691 |
each :new msg, courtesy of a special hack in |
| 692 |
xlobj.c:sendmsg().) |
| 693 |
:answer -- Add a (msg closure) pair to self.MESSAGES. |
| 694 |
</pre> |
| 695 |
|
| 696 |
<p>Here's a figure to summarize the above, with a generic object thrown in for |
| 697 |
good measure. Note that all instances of CLASS will have a SUPERCLASS pointer, |
| 698 |
but no normal object will. Note also that the messages known to an object are |
| 699 |
those which can be reached by following exactly one Class Ptr and then zero or |
| 700 |
more Superclass Ptrs. For example, the generic object can respond to :ISNEW, |
| 701 |
:CLASS and :SHOW, but not to :NEW or :ANSWER. (The functions implementing the |
| 702 |
given messages are shown in parentheses.)</p> |
| 703 |
|
| 704 |
<pre> |
| 705 |
NIL |
| 706 |
^ |
| 707 |
| |
| 708 |
|Superclass Ptr |
| 709 |
| |
| 710 |
Msg+--------+ |
| 711 |
:isnew (xlobj.c:obisnew) <----| class |Class Ptr |
| 712 |
:class (xlobj.c:obclass) <----| OBJECT |------------------------------>+ |
| 713 |
:show (xlobj.c:objshow) <----| | | |
| 714 |
+--------+ | |
| 715 |
^ ^ ^ | |
| 716 |
+---------+ | | | | |
| 717 |
| generic |Class Ptr | | +<---------------+ | |
| 718 |
| object |-------------->+ |Superclass Ptr ^Superclass Ptr | |
| 719 |
+---------+ | | | |
| 720 |
Msg+--------+ +---------+ | |
| 721 |
:isnew (xlobj.c:clnew) <----| class |Class Ptr | generic |Class Ptr | |
| 722 |
:new (xlobj.c:clisnew) <----| CLASS |------->+ | CLASS |------->+ | |
| 723 |
:answer(xlobj.c:clanswer)<----| | | | | | | |
| 724 |
+--------+ | +---------+ | | |
| 725 |
^ ^ | | | |
| 726 |
| | v v | |
| 727 |
| +-----------+ <------------------+ v |
| 728 |
+<------------------------------------+ |
| 729 |
</pre> |
| 730 |
|
| 731 |
<p>Thus, class CLASS inherits the :CLASS and :SHOW messages from class OBJECT, |
| 732 |
overrides the default :ISNEW message, and provides new messages :NEW and |
| 733 |
:ANSWER.</p> |
| 734 |
|
| 735 |
<p>New classes are created by (send CLASS :NEW ...) messages. Their Class Ptr |
| 736 |
will point to CLASS. By default, they will have OBJECT as their superclass, but |
| 737 |
this can be overridden by the second optional argument to :NEW.</p> |
| 738 |
|
| 739 |
<p>The above basic structure is set up by xlobj.c:xloinit().</p> |
| 740 |
|
| 741 |
<table cellpadding="0"><tbody><tr><td> </td><td bgcolor="eeeeee"> |
| 742 |
<a href="xlisp-internals.html#SEC00">Back to Top</a></nobr></li> |
| 743 |
</tr></tbody></table> |
| 744 |
|
| 745 |
<h3><a name="SEC15">How do we look up the value of a variable ?</a></h3> |
| 746 |
|
| 747 |
<p>When we're cruising along evaluating an expression and encounter a symbol, |
| 748 |
the symbol might refer to a global variable, an instance variable, or a class |
| 749 |
variable in any of our superclasses. Figuring out which means digging through |
| 750 |
the environment. The canonical place this happens is in xleval.c:xleval(), which |
| 751 |
simply passes the buck to xlsym.c:xlgetvalue(), which in turn passes the buck to |
| 752 |
xlxsym.c:xlxgetvalue(), where the fun of scanning down xlenv begins. The xlenv |
| 753 |
environment looks something like</p> |
| 754 |
|
| 755 |
<pre> |
| 756 |
Backbone Environment frame contents |
| 757 |
-------- -------------------------- |
| 758 |
xlenv --> frame ((sym val) (sym val) (sym val) ... ) |
| 759 |
frame ... |
| 760 |
object (obj msg-class) |
| 761 |
frame ... |
| 762 |
object ... |
| 763 |
frame ... |
| 764 |
... |
| 765 |
</pre> |
| 766 |
|
| 767 |
<p>The "frame" lines are due to everyday nested constructs like LET expressions, |
| 768 |
while the "object" lines represent an object environment entered via a message |
| 769 |
send. xlxgetvalue scans the enviroment left to right, and then top to bottom. It |
| 770 |
scans down the regular environment frames itself, and calls |
| 771 |
xlobj.c:xlobjgetvalue() to search the object environment frames.</p> |
| 772 |
|
| 773 |
<p>xlobjgetvalue() first searches for the symbol in the msg-class, then in all |
| 774 |
the successive superclasses of msg-class. In each class, it first checks the |
| 775 |
list of instance-variable names in the IVARS slot, then the list of |
| 776 |
class-variables name in the CVARS slot.</p> |
| 777 |
|
| 778 |
<table cellpadding="0"><tbody><tr><td> </td><td bgcolor="eeeeee"> |
| 779 |
<a href="xlisp-internals.html#SEC00">Back to Top</a></nobr></li> |
| 780 |
</tr></tbody></table> |
| 781 |
|
| 782 |
<h3><a name="SEC16">How are function calls implemented ?</a></h3> |
| 783 |
|
| 784 |
<p>xleval.c contains the central expression-evaluation code. xleval.c:xleval() |
| 785 |
is the standard top-level entrypoint. The two central functions are |
| 786 |
xleval.c:xlevform() and xleval.c:evfun(). xlevform() can evaluate four kinds of |
| 787 |
expression nodes:</p> |
| 788 |
|
| 789 |
<p><b>SUBR:</b> A normal primitive fn coded in C. We call evpushargs() to |
| 790 |
evaluate and push the arguments, then call the primitive.</p> |
| 791 |
|
| 792 |
<p><b>FSUBR:</b> A special primitive fn coded in C, which (like IF) wants its |
| 793 |
arguments unevaluated. We call pushargs() (instead of evpushargs()) and then the |
| 794 |
C fn.</p> |
| 795 |
|
| 796 |
<p><b>CLOSURE:</b> A preprocessed written-in-lisp fn from a DEFUN or LAMBDA. We |
| 797 |
call evpushargs() and then evfun().</p> |
| 798 |
|
| 799 |
<p><b>CONS:</b> We issue an error if CONS.car isn't a LAMBDA, otherwise we call |
| 800 |
xleval.c:xlclose() to build a CLOSURE from the LAMBDA, and fall into the CLOSURE |
| 801 |
code.</p> |
| 802 |
|
| 803 |
<p>The common thread in all the above cases is that we call evpushargs() or |
| 804 |
pushargs() to push all the arguments on the evaluation stack, leaving the number |
| 805 |
and location of the arguments in the global variables xlargc and xlargv. The |
| 806 |
primitive C functions consume their arguments directly from the argument |
| 807 |
stack.</p> |
| 808 |
|
| 809 |
<p>xleval.c:evfun() evaluates a CLOSURE by:</p> |
| 810 |
|
| 811 |
<p>(1) Switching xlenv and xlfenv to the values they had when the CLOSURE was |
| 812 |
built. (These values are recorded in the CLOSURE.)</p> |
| 813 |
|
| 814 |
<p>(2) Binding the arguments to the environment. This involves scanning through |
| 815 |
the section of the argument stack indicated by xlargc/xlargv, using information |
| 816 |
from the CLOSURE to resolve keyword arguments correctly and assign appropriate |
| 817 |
default values to optional arguments, among other things.</p> |
| 818 |
|
| 819 |
<p>(3) Evaluating the body of the function via xleval.c:xleval().</p> |
| 820 |
|
| 821 |
<p>(4) Cleaning up and restoring the original environment.</p> |
| 822 |
|
| 823 |
<table cellpadding="0"><tbody><tr><td> </td><td bgcolor="eeeeee"> |
| 824 |
<a href="xlisp-internals.html#SEC00">Back to Top</a></nobr></li> |
| 825 |
</tr></tbody></table> |
| 826 |
|
| 827 |
<h3><a name="SEC17">How are message-sends implemented ?</a></h3> |
| 828 |
|
| 829 |
<p>We scan the MESSAGES list in the CLASS object of the recipient, looking for a |
| 830 |
(message-symbol method) pair that matches our message symbol. If necessary, we |
| 831 |
scan the MESSAGES lists of the recipient's superclasses too. |
| 832 |
(xlobj.c:sendmsg().) Once we find it, we basically do a normal function |
| 833 |
evaluation. (xlobjl.c:evmethod().)</p> |
| 834 |
|
| 835 |
<p>Two differences between message-send and normal function invocation:</p> |
| 836 |
|
| 837 |
<p>1) We need to replace the message-symbol by the recipient on the argument |
| 838 |
stack to make "self" available in the method closure.</p> |
| 839 |
|
| 840 |
<p>2) We need to push an 'object' stack entry on the xlenv environment to record |
| 841 |
which class is handling the message (so that, for example, SEND-SUPER can find |
| 842 |
our superclass).</p> |
| 843 |
|
| 844 |
<table cellpadding="0"><tbody><tr><td> </td><td bgcolor="eeeeee"> |
| 845 |
<a href="xlisp-internals.html#SEC00">Back to Top</a></nobr></li> |
| 846 |
</tr></tbody></table> |
| 847 |
|
| 848 |
<h3><a name="SEC18">How is garbage collection implemented ?</a></h3> |
| 849 |
|
| 850 |
<p>The dynamic memory pool managed by xlisp consists of a chain of memory |
| 851 |
segments (xldmem.h:struct segment) rooted at global C variable "segs". Each |
| 852 |
segment contains an array of "struct node"s plus a pointer to the next segment. |
| 853 |
Each node contains a n_type field and a MARK bit, which is zero except during |
| 854 |
garbage collection.</p> |
| 855 |
|
| 856 |
<p>Xlisp uses a simple, classical mark-and-sweep garbage collector. When it runs |
| 857 |
out of memory (fnodes==NIL), it does a recursive traversal setting the MARK flag |
| 858 |
on all nodes reachable from the obarray, the three environments |
| 859 |
xlenv/xlfenv/xldenv, and the evaluation and argument stacks. (A "switch" on the |
| 860 |
n_type field tells us how to find all the LVAL slots in the node (plus |
| 861 |
associated storage), and a pointer-reversal trick lets us avoid using too much |
| 862 |
stack space during the traversal.) sweep() then adds all un-MARKed LVALs to |
| 863 |
fnodes, and clears the MARK bit on the remaining nodes. If this fails to produce |
| 864 |
enough free nodes, a new segment is malloc()ed.</p> |
| 865 |
|
| 866 |
<p>The code to do this stuff is mostly in xldmem.c.</p> |
| 867 |
|
| 868 |
<table cellpadding="0"><tbody><tr><td> </td><td bgcolor="eeeeee"> |
| 869 |
<a href="xlisp-internals.html#SEC00">Back to Top</a></nobr></li> |
| 870 |
</tr></tbody></table> |
| 871 |
|
| 872 |
<h3><a name="SEC19">How are the source files laid out ?</a></h3> |
| 873 |
|
| 874 |
<p>To really understand the source, of course, you simply have to sit down and |
| 875 |
read it. There's no royal road to hacking! So this is a map of the source, not a |
| 876 |
picture of it.</p> |
| 877 |
|
| 878 |
<p>The core portable xlisp files have the prefix 'xl' (for 'xlisp').</p> |
| 879 |
|
| 880 |
<p>The best place to start reading the code is in the two main header files, |
| 881 |
xlisp.h and xldmem.h.</p> |
| 882 |
|
| 883 |
<p>The xldmem.h file ('dmem' for 'dynamic memory') defines the actual structure |
| 884 |
in memory of all the primitive xlisp data types. This is the file you will most |
| 885 |
likely refer to most often.</p> |
| 886 |
|
| 887 |
<p>The xlisp.h file defines essentially all global constants and macros which |
| 888 |
don't need to know about the structures in xldmem.h, mainly manifest constants |
| 889 |
sizing various arrays for different machines, and macros to test for the type of |
| 890 |
a list object and to help parse xlisp argument lists.</p> |
| 891 |
|
| 892 |
<p>The central code files to understand are xlmain.c, xleval.c, xlbfun.c, and |
| 893 |
xlsym.c.</p> |
| 894 |
|
| 895 |
<p><b>xlmain.c</b> contains both main() and the central read-eval-print loop, so |
| 896 |
it is the place from which to begin tracing flow of control.</p> |
| 897 |
|
| 898 |
<p><b>xleval.c</b> (with some support from xlbfun.) contains the heart of xlisp, |
| 899 |
the code to evaluate functions and macros.</p> |
| 900 |
|
| 901 |
<p><b>xlsym.c</b> contains the code to find the value of a symbol.</p> |
| 902 |
|
| 903 |
<p>Once you understand the above three, you know where xlisp decides to evaluate |
| 904 |
an s-expression, how it evaluates it, and how it finds the values needed by the |
| 905 |
expression.</p> |
| 906 |
|
| 907 |
<p>A good file to tackle next is xlobj.c, which handles much of the |
| 908 |
object-oriented support, and has much of the flavor of xleval.c.</p> |
| 909 |
|
| 910 |
<p>Most of the other files are just libraries of functions to handle particular |
| 911 |
types of processing, and are easily understood once the central code is |
| 912 |
grokked.</p> |
| 913 |
|
| 914 |
<p>One of the charms of xlisp *is* that it is small enough to easily read and |
| 915 |
comprehend. I hope it stays that way!</p> |
| 916 |
|
| 917 |
<p>Here's a very brief file-by-file overview of the source. Your files will |
| 918 |
probably be laid out just a little differently. In particular, if you're not |
| 919 |
running on unix, instead of 'unixstuff.c' you'll have something like |
| 920 |
'dosstuff.c'.</p> |
| 921 |
|
| 922 |
<pre> |
| 923 |
Size Name Contains |
| 924 |
----- -------- -------- |
| 925 |
2054 osdefs.h System specific declarations. Empty file in my case. |
| 926 |
2050 osptrs.h System specific pointers. Empty file in my case. |
| 927 |
14172 unixstuff.c Isolates I/O fns, which tend to be OS-specific. Unix version. |
| 928 |
19049 xlbfun.c 'Basic FUNctions': highlevel eval stuff + random support. |
| 929 |
30229 xlcont.c 'CONTrol': case, do, while, dotimes, other special forms. |
| 930 |
6380 xldbug.c 'DeBUG': break, abort, error, baktrace... |
| 931 |
18006 xldmem.c 'Dynamic MEMory': ram allocation, garbage collector. |
| 932 |
9431 xldmem.h Declaration of LVAL, scads of useful macros. |
| 933 |
21220 xleval.c 'EVALuation': eval, apply, macroexpand and support for them. |
| 934 |
11935 xlfio.c 'File I/O': OPEN, READ-CHAR, WRITE-CHAR ... |
| 935 |
18481 xlftab.c 'Function TABle': Array of all xlisp primitives. |
| 936 |
4866 xlglob.c 'GLOBal variables': Boring list of declarations. |
| 937 |
11048 xlimage.c 'memory IMAGE': Code to save/restore contents of xlisp. |
| 938 |
10579 xlinit.c 'INITialization': Start-of-the-world setup code. |
| 939 |
6016 xlio.c 'Input/Output': misc I/O stuff, some called by xlfio.c. |
| 940 |
12664 xlisp.h consp() ..., xlgetarg() ..., misc types. |
| 941 |
5853 xljump.c catch, throw, return ... |
| 942 |
20723 xllist.c car, cdr, append, map ... basic list manipulation. |
| 943 |
11975 xlmath.c Arithmetic functions -- addition, multiplication ... |
| 944 |
16425 xlobj.c Object support -- create objects & classes, send msgs... |
| 945 |
4134 xlpp.c A little prettyprinter. |
| 946 |
9487 xlprin.c Print an arbitrary lisp value in ascii. |
| 947 |
19535 xlread.c Read in an arbitrary ascii lisp expression. |
| 948 |
15062 xlstr.c Manipulation of characters and strings. |
| 949 |
12889 xlstruct.c Lisp structures -- defstruct and kin. |
| 950 |
5957 xlsubr.c eq, equal, some internal utility fns. |
| 951 |
7019 xlsym.c Symbols and obarrays ... maksym, getvalue, getprop... |
| 952 |
5566 xlsys.c Misc stuff -- read file, print backtrace, peek/poke... |
| 953 |
3926 xmain.c main(), with top read-eval-print loop. |
| 954 |
</pre> |
| 955 |
|
| 956 |
<table cellpadding="0"><tbody><tr><td> </td><td bgcolor="eeeeee"> |
| 957 |
<a href="xlisp-internals.html#SEC00">Back to Top</a></nobr></li> |
| 958 |
</tr></tbody></table> |
| 959 |
|
| 960 |
<h3><a name="SEC20">How do I add a new primitive fn to xlisp ?</a></h3> |
| 961 |
|
| 962 |
<p>A preliminary comment: You should have a copy of Guy L Steele's "Common Lisp: |
| 963 |
The Language" (2nd Edition), and make your new primitives compatible with the |
| 964 |
standard whenever practical.</p> |
| 965 |
|
| 966 |
<p>Add a line to the end of xlftab.c:funtab[]. This table contains a list of |
| 967 |
triples:</p> |
| 968 |
|
| 969 |
<p>The first element of each triple is the function name as it will appear to |
| 970 |
the programmer. Make it all upper case.</p> |
| 971 |
|
| 972 |
<p>The second element is S (for SUBR) if (like most fns) your function wants its |
| 973 |
arguments pre-evaluated, else F (for FSUBR).</p> |
| 974 |
|
| 975 |
<p>The third element is the name of the C function to call.</p> |
| 976 |
|
| 977 |
<p>Remember that your arguments arrive on the xlisp argument stack rather than |
| 978 |
via the usual C parameter mechanism.</p> |
| 979 |
|
| 980 |
<p>CAUTION: Try to keep your files separate from generic xlisp files, and to |
| 981 |
minimize the number of changes you make in the generic xlisp files. This way, |
| 982 |
you'll have an easier time re-installing your changes when new versions of xlisp |
| 983 |
come out. For example, if you are going to add many primitive functions to your |
| 984 |
xlisp, use an #include file rather than putting them all in xlftab.c. It's a |
| 985 |
good idea to put a marker (like a comment with your initials) on each line you |
| 986 |
change or insert in the generic xlisp fileset.</p> |
| 987 |
|
| 988 |
<p>CAUTION: Remember that you usually need to protect the LVAL variables in your |
| 989 |
function from the garbage-collector. It never hurts to do this, and often |
| 990 |
produces obscure bugs if you do not. You protect uninitialized local variables |
| 991 |
with xlsave1() and initialized local variables with xlprot1().</p> |
| 992 |
|
| 993 |
<p>BE CAREFUL NOT TO PROTECT UNINITIALIZED LOCAL VARIABLES WITH XLPROT1() OR |
| 994 |
XLPROTECT()! This will appear to work fine until garbage collection happens at |
| 995 |
an inconvenient moment, at which point the garbage collector will wind up |
| 996 |
following your uninitialized pointer off to never-never land.</p> |
| 997 |
|
| 998 |
<p>Note: If you have several pointers to protect, you can save a little runtime |
| 999 |
and codespace by using xlstkcheck(number-of-variables-to-protect) followed by |
| 1000 |
xlsave()s and xlprotect()s instead of the more expensive xlsave1()s and |
| 1001 |
xlprot1()s.</p> |
| 1002 |
|
| 1003 |
<p>Generic code for a new primitive fn:</p> |
| 1004 |
|
| 1005 |
<pre> |
| 1006 |
/* xlsamplefun - do useless stuff. */ |
| 1007 |
/* Called like (samplefun '(a c b) 1 2.0) */ |
| 1008 |
LVAL xlsamplefun() |
| 1009 |
{ |
| 1010 |
/* Variables to hold the arguments: */ |
| 1011 |
LVAL list_arg, integer_arg, float_arg; |
| 1012 |
|
| 1013 |
/* Get the arguments, with appropriate errors */ |
| 1014 |
/* if any are of the wrong type. Look in */ |
| 1015 |
/* xlisp.h for macros to read other types of */ |
| 1016 |
/* arguments. Look in xlmath.c for examples */ |
| 1017 |
/* of functions which can handle an argument */ |
| 1018 |
/* which may be either int or float: */ |
| 1019 |
list_arg = xlgalist() ; /* "XLisp Get A LIST" */ |
| 1020 |
integer_arg = xlgafixnum(); /* "XLisp Get A FIXNUM" */ |
| 1021 |
float_arg = xlgaflonum(); /* "XLisp Get A FLONUM" */ |
| 1022 |
|
| 1023 |
/* Issue an error message if there are any extra arguments: */ |
| 1024 |
xllastarg(); |
| 1025 |
|
| 1026 |
/* Call a separate C function to do the actual */ |
| 1027 |
/* work. This way, the main function can */ |
| 1028 |
/* be called from both xlisp code and C code. */ |
| 1029 |
/* By convention, the name of the xlisp wrapper */ |
| 1030 |
/* starts with "xl", and the native C function */ |
| 1031 |
/* has the same name minus the "xl" prefix: */ |
| 1032 |
return samplefun( list_arg, integer_arg, float_arg ); |
| 1033 |
} |
| 1034 |
LVAL samplefun( list_arg, integer_arg, float_arg ) |
| 1035 |
LVAL list_arg, integer_arg, float_arg; |
| 1036 |
{ |
| 1037 |
FIXTYPE val_of_integer_arg; |
| 1038 |
FLOTYPE val_of_float_arg; |
| 1039 |
|
| 1040 |
/* Variables which will point to LISP objects: */ |
| 1041 |
LVAL result; |
| 1042 |
LVAL list_ptr; |
| 1043 |
LVAL float_ptr; |
| 1044 |
LVAL int_ptr; |
| 1045 |
|
| 1046 |
/* Protect our internal pointers by */ |
| 1047 |
/* pushing them on the evaluation */ |
| 1048 |
/* stack so the garbage collector */ |
| 1049 |
/* can't recycle them in the middle */ |
| 1050 |
/* of the routine: */ |
| 1051 |
xlstkcheck(4); /* Make sure following xlsave */ |
| 1052 |
/* calls won't overrun stack. */ |
| 1053 |
xlsave(list_ptr); /* Use xlsave1() if you don't */ |
| 1054 |
xlsave(float_ptr);/* do an xlstkcheck(). */ |
| 1055 |
xlsave(int_ptr); |
| 1056 |
xlsave(result); |
| 1057 |
|
| 1058 |
/* Semantic check, illustrating use of xlfail(): */ |
| 1059 |
if (list_ptr == NIL) { |
| 1060 |
xlfail("null list"); |
| 1061 |
/* Won't return. */ |
| 1062 |
} |
| 1063 |
|
| 1064 |
/* Create an internal list structure, protected */ |
| 1065 |
/* against garbage collection until we exit fn: */ |
| 1066 |
list_ptr = cons(list_arg,list_arg); |
| 1067 |
|
| 1068 |
/* Get the actual values of our fixnum and flonum: */ |
| 1069 |
val_of_integer_arg = getfixnum( integer_arg ); |
| 1070 |
val_of_float_arg = getflonum( float_arg ); |
| 1071 |
|
| 1072 |
/* Semantic check, illustrating use of xlerror(): */ |
| 1073 |
if (val_of_integer_arg < -2) { |
| 1074 |
xlerror("bad integer",cvfixnum(val_of_integer_arg)); |
| 1075 |
/* Won't return. */ |
| 1076 |
} |
| 1077 |
|
| 1078 |
/*******************************************/ |
| 1079 |
/* You can have any amount of intermediate */ |
| 1080 |
/* computations at this point in the fn... */ |
| 1081 |
/*******************************************/ |
| 1082 |
|
| 1083 |
/* Make new numeric values to return: */ |
| 1084 |
integer_ptr = cvfixnum( val_of_integer_arg * 3 ); |
| 1085 |
float_ptr = cvflonum( val_of_float_arg * 3.0 ); |
| 1086 |
|
| 1087 |
/* Cons it all together to produce a return value: */ |
| 1088 |
result = cons( float_ptr, NIL ); |
| 1089 |
result = cons( integer_ptr, result ); |
| 1090 |
result = cons( list_ptr, result ); |
| 1091 |
|
| 1092 |
/* Restore the stack, canceling the xlsave()s: */ |
| 1093 |
xlpopn(4); /* Use xlpop() for a single argument.*/ |
| 1094 |
|
| 1095 |
return result; |
| 1096 |
} |
| 1097 |
</pre> |
| 1098 |
|
| 1099 |
<p><b>Example of what NOT to do:</b></p> |
| 1100 |
|
| 1101 |
<p>Here's a function I wrote which does *NOT* correctly prevent the garbage |
| 1102 |
collector from stealing its dynamically allocated cells:</p> |
| 1103 |
|
| 1104 |
<pre> |
| 1105 |
LVAL incorrect_Point_To_List( p )/*DON'T USE THIS CODE! */ |
| 1106 |
geo_point* p; |
| 1107 |
/*- |
| 1108 |
Convert point to (x y z) list. |
| 1109 |
-*/ |
| 1110 |
{ |
| 1111 |
LVAL result; |
| 1112 |
xlsave1(result); |
| 1113 |
result = cons( /* THIS CODE IS BROKEN! */ |
| 1114 |
cvflonum( p->x), /* THIS CODE IS BROKEN! */ |
| 1115 |
cons( /* THIS CODE IS BROKEN! */ |
| 1116 |
cvflonum( p->y), /* THIS CODE IS BROKEN! */ |
| 1117 |
cons( /* THIS CODE IS BROKEN! */ |
| 1118 |
cvflonum(p->z), /* THIS CODE IS BROKEN! */ |
| 1119 |
NIL /* THIS CODE IS BROKEN! */ |
| 1120 |
) /* THIS CODE IS BROKEN! */ |
| 1121 |
) /* THIS CODE IS BROKEN! */ |
| 1122 |
); /* THIS CODE IS BROKEN! */ |
| 1123 |
xlpop(); |
| 1124 |
return result; |
| 1125 |
} |
| 1126 |
</pre> |
| 1127 |
|
| 1128 |
<p>The problem with the above function is that the "z" cell will be allocated |
| 1129 |
first, and is not protected during the allocation of the "y" flonum (or vice |
| 1130 |
versa, depending on the order the compiler chooses to evaluate these arguments). |
| 1131 |
Similarly, the "y" cell is not protected during allocation of the "x" flonum. |
| 1132 |
Here is a correct version, in which "result" always protects the |
| 1133 |
list-to-date:</p> |
| 1134 |
|
| 1135 |
<pre> |
| 1136 |
LVAL correct_Point_To_List( p ) |
| 1137 |
geo_point* p; |
| 1138 |
/*- |
| 1139 |
Convert point to (x y z) list. |
| 1140 |
-*/ |
| 1141 |
{ |
| 1142 |
LVAL result; |
| 1143 |
xlsave1(result); |
| 1144 |
result = cons( cvflonum(p->z), NIL ); |
| 1145 |
result = cons( cvflonum(p->y), result ); |
| 1146 |
result = cons( cvflonum(p->x), result ); |
| 1147 |
xlpop(); |
| 1148 |
return result; |
| 1149 |
} |
| 1150 |
</pre> |
| 1151 |
|
| 1152 |
<table cellpadding="0"><tbody><tr><td> </td><td bgcolor="eeeeee"> |
| 1153 |
<a href="xlisp-internals.html#SEC00">Back to Top</a></nobr></li> |
| 1154 |
</tr></tbody></table> |
| 1155 |
|
| 1156 |
<h3><a name="SEC21">Minor Observations:</a></h3> |
| 1157 |
|
| 1158 |
<p>xlapply, xlevform and sendmsg will issue an error if they encounter a s_macro |
| 1159 |
CLOSURE. You are not allowed to use APPLY or FUNCALL with macros in Common Lisp. |
| 1160 |
There is no way provided to declare macro methods, nor do they make much |
| 1161 |
sense...</p> |
| 1162 |
|
| 1163 |
<p>Neither xlapply nor sendmsg will handle FSUBRs. Common Lisp does not allow |
| 1164 |
APPLYing a special form (FSUBR), and since SEND is a SUBR, all of its arguments |
| 1165 |
are already evaluated, so it is not possible to have FSUBR methods.</p> |
| 1166 |
|
| 1167 |
<p>Since xlisp tracks the three most recent input expressions (in variables +, |
| 1168 |
++ and +++) and three most recent results (in variables *, ** and ***), things |
| 1169 |
may occasionally not get garbage-collected as soon as you expect!</p> |
| 1170 |
|
| 1171 |
<p>Both xlobj.c:xloinit() and xlobj.c:obsymvols() initialize the "object" and |
| 1172 |
"class" variables. This is neither redundant nor a bug:</p> |
| 1173 |
|
| 1174 |
<p>xloinit creates the classes class and object, as well as the symbols, but |
| 1175 |
sets the C variables class and object to point to the class and object.</p> |
| 1176 |
|
| 1177 |
<p>obsymbols just sets the C variables by looking up the symbols. It is needed |
| 1178 |
because when you restore a workspace you don't create new objects but still need |
| 1179 |
to know where the existing objects are (they might be in a different location in |
| 1180 |
the saved workspace). Notice that obsymbols is called by xlsymbols which is |
| 1181 |
called both when initializing a new workspace and when restoring an old |
| 1182 |
workspace.</p> |
| 1183 |
|
| 1184 |
<table cellpadding="0"><tbody><tr><td> </td><td bgcolor="eeeeee"> |
| 1185 |
<a href="xlisp-internals.html#SEC00">Back to Top</a></nobr></li> |
| 1186 |
</tr></tbody></table> |
| 1187 |
|
| 1188 |
<h3><a name="SEC22">Acknowledgements</a></h3> |
| 1189 |
|
| 1190 |
<p>This document is considerably improved thanks to careful reading and |
| 1191 |
thoughtful suggestions from Ken Whedbee ([email protected]) and (especially) |
| 1192 |
Tom Almy ([email protected]).</p> </pre> |
| 1193 |
|
| 1194 |
<table cellpadding="0"><tbody><tr><td> </td><td bgcolor="eeeeee"> |
| 1195 |
<a href="xlisp-internals.html#SEC00">Back to Top</a></nobr></li> |
| 1196 |
</tr></tbody></table> |
| 1197 |
|
| 1198 |
<br><hr> |
| 1199 |
|
| 1200 |
<a href="../start.htm">Nyquist / XLISP 2.0</a> - |
| 1201 |
<a href="../manual/contents.htm">Contents</a> | |
| 1202 |
<a href="../tutorials/tutorials.htm">Tutorials</a> | |
| 1203 |
<a href="../examples/examples.htm">Examples</a> | |
| 1204 |
<a href="../reference/reference-index.htm">Reference</a> |
| 1205 |
|
| 1206 |
</body></html> |