Commit | Line | Data |
---|---|---|
015959cb KN |
1 | \input texinfo @c -*-texinfo-*- |
2 | @c %**start of header | |
3 | @setfilename guile-vm.info | |
4 | @settitle Guile VM Specification | |
5 | @footnotestyle end | |
6 | @setchapternewpage odd | |
7 | @c %**end of header | |
8 | ||
fa19602c LC |
9 | @set EDITION 0.6 |
10 | @set VERSION 0.6 | |
11 | @set UPDATED 2005-04-26 | |
015959cb | 12 | |
238e7a11 LC |
13 | @c Macro for instruction definitions. |
14 | @macro insn{} | |
15 | Instruction | |
16 | @end macro | |
17 | ||
015959cb KN |
18 | @ifinfo |
19 | @dircategory Scheme Programming | |
20 | @direntry | |
238e7a11 | 21 | * Guile VM: (guile-vm). Guile's Virtual Machine. |
015959cb KN |
22 | @end direntry |
23 | ||
24 | This file documents Guile VM. | |
25 | ||
26 | Copyright @copyright{} 2000 Keisuke Nishida | |
238e7a11 | 27 | Copyright @copyright{} 2005 Ludovic Court`es |
015959cb KN |
28 | |
29 | Permission is granted to make and distribute verbatim copies of this | |
30 | manual provided the copyright notice and this permission notice are | |
31 | preserved on all copies. | |
32 | ||
33 | @ignore | |
34 | Permission is granted to process this file through TeX and print the | |
35 | results, provided the printed document carries a copying permission | |
36 | notice identical to this one except for the removal of this paragraph | |
37 | (this paragraph not being relevant to the printed manual). | |
38 | ||
39 | @end ignore | |
40 | Permission is granted to copy and distribute modified versions of this | |
41 | manual under the conditions for verbatim copying, provided that the | |
42 | entire resulting derived work is distributed under the terms of a | |
43 | permission notice identical to this one. | |
44 | ||
45 | Permission is granted to copy and distribute translations of this manual | |
46 | into another language, under the above conditions for modified versions, | |
47 | except that this permission notice may be stated in a translation | |
48 | approved by the Free Software Foundation. | |
49 | @end ifinfo | |
50 | ||
51 | @titlepage | |
52 | @title Guile VM Specification | |
53 | @subtitle for Guile VM @value{VERSION} | |
54 | @author Keisuke Nishida | |
55 | ||
56 | @page | |
57 | @vskip 0pt plus 1filll | |
58 | Edition @value{EDITION} @* | |
59 | Updated for Guile VM @value{VERSION} @* | |
60 | @value{UPDATED} @* | |
61 | ||
62 | Copyright @copyright{} 2000 Keisuke Nishida | |
238e7a11 | 63 | Copyright @copyright{} 2005 Ludovic Court`es |
015959cb KN |
64 | |
65 | Permission is granted to make and distribute verbatim copies of this | |
66 | manual provided the copyright notice and this permission notice are | |
67 | preserved on all copies. | |
68 | ||
69 | Permission is granted to copy and distribute modified versions of this | |
70 | manual under the conditions for verbatim copying, provided that the | |
71 | entire resulting derived work is distributed under the terms of a | |
72 | permission notice identical to this one. | |
73 | ||
74 | Permission is granted to copy and distribute translations of this manual | |
75 | into another language, under the above conditions for modified versions, | |
76 | except that this permission notice may be stated in a translation | |
77 | approved by the Free Software Foundation. | |
78 | @end titlepage | |
79 | ||
80 | @contents | |
81 | ||
82 | @c ********************************************************************* | |
83 | @node Top, Introduction, (dir), (dir) | |
84 | @top Guile VM Specification | |
85 | ||
238e7a11 LC |
86 | This document would like to correspond to Guile VM @value{VERSION}. |
87 | However, be warned that important parts still correspond to version | |
88 | 0.0 and are not valid anymore. | |
015959cb KN |
89 | |
90 | @menu | |
fa19602c LC |
91 | * Introduction:: |
92 | * Variable Management:: | |
93 | * Program Execution:: | |
94 | * Instruction Set:: | |
f41cb00c LC |
95 | |
96 | @detailmenu | |
97 | --- The Detailed Node Listing --- | |
98 | ||
99 | Instruction Set | |
100 | ||
101 | * Environment Control Instructions:: | |
102 | * Branch Instructions:: | |
103 | * Subprogram Control Instructions:: | |
104 | * Data Control Instructions:: | |
105 | ||
106 | @end detailmenu | |
015959cb KN |
107 | @end menu |
108 | ||
109 | @c ********************************************************************* | |
fa19602c | 110 | @node Introduction, Variable Management, Top, Top |
015959cb | 111 | @chapter What is Guile VM? |
a98cef7e KN |
112 | |
113 | A Guile VM has a set of registers and its own stack memory. Guile may | |
114 | have more than one VM's. Each VM may execute at most one program at a | |
115 | time. Guile VM is a CISC system so designed as to execute Scheme and | |
116 | other languages efficiently. | |
117 | ||
fa19602c | 118 | @unnumberedsubsec Registers |
a98cef7e | 119 | |
fa19602c LC |
120 | @itemize |
121 | @item pc - Program counter ;; ip (instruction poiner) is better? | |
122 | @item sp - Stack pointer | |
123 | @item bp - Base pointer | |
124 | @item ac - Accumulator | |
125 | @end itemize | |
a98cef7e | 126 | |
fa19602c | 127 | @unnumberedsubsec Engine |
a98cef7e KN |
128 | |
129 | A VM may have one of three engines: reckless, regular, or debugging. | |
130 | Reckless engine is fastest but dangerous. Regular engine is normally | |
131 | fail-safe and reasonably fast. Debugging engine is safest and | |
132 | functional but very slow. | |
133 | ||
fa19602c | 134 | @unnumberedsubsec Memory |
a98cef7e KN |
135 | |
136 | Stack is the only memory that each VM owns. The other memory is shared | |
137 | memory that is shared among every VM and other part of Guile. | |
138 | ||
fa19602c | 139 | @unnumberedsubsec Program |
a98cef7e KN |
140 | |
141 | A VM program consists of a bytecode that is executed and an environment | |
142 | in which execution is done. Each program is allocated in the shared | |
143 | memory and may be executed by any VM. A program may call other programs | |
144 | within a VM. | |
145 | ||
fa19602c | 146 | @unnumberedsubsec Instruction |
a98cef7e KN |
147 | |
148 | Guile VM has dozens of system instructions and (possibly) hundreds of | |
149 | functional instructions. Some Scheme procedures such as cons and car | |
150 | are implemented as VM's builtin functions, which are very efficient. | |
151 | Other procedures defined outside of the VM are also considered as VM's | |
152 | functional features, since they do not change the state of VM. | |
153 | Procedures defined within the VM are called subprograms. | |
154 | ||
155 | Most instructions deal with the accumulator (ac). The VM stores all | |
156 | results from functions in ac, instead of pushing them into the stack. | |
157 | I'm not sure whether this is a good thing or not. | |
158 | ||
fa19602c | 159 | @node Variable Management, Program Execution, Introduction, Top |
015959cb | 160 | @chapter Variable Management |
a98cef7e KN |
161 | |
162 | A program may have access to local variables, external variables, and | |
163 | top-level variables. | |
164 | ||
fa19602c | 165 | @section Local/external variables |
a98cef7e KN |
166 | |
167 | A stack is logically divided into several blocks during execution. A | |
168 | "block" is such a unit that maintains local variables and dynamic chain. | |
169 | A "frame" is an upper level unit that maintains subprogram calls. | |
170 | ||
fa19602c | 171 | @example |
a98cef7e KN |
172 | Stack |
173 | dynamic | | | | | |
174 | chain +==========+ - = | |
175 | | |local vars| | | | |
176 | `-|block data| | block | | |
177 | /|frame data| | | | |
178 | | +----------+ - | | |
179 | | |local vars| | | frame | |
180 | `-|block data| | | | |
181 | /+----------+ - | | |
182 | | |local vars| | | | |
183 | `-|block data| | | | |
184 | /+==========+ - = | |
185 | | |local vars| | | | |
186 | `-|block data| | | | |
187 | /|frame data| | | | |
188 | | +----------+ - | | |
189 | | | | | | | |
fa19602c | 190 | @end example |
a98cef7e KN |
191 | |
192 | The first block of each frame may look like this: | |
193 | ||
fa19602c | 194 | @example |
a98cef7e KN |
195 | Address Data |
196 | ------- ---- | |
197 | xxx0028 Local variable 2 | |
198 | xxx0024 Local variable 1 | |
199 | bp ->xxx0020 Local variable 0 | |
200 | xxx001c Local link (block data) | |
201 | xxx0018 External link (block data) | |
202 | xxx0014 Stack pointer (block data) | |
203 | xxx0010 Return address (frame data) | |
204 | xxx000c Parent program (frame data) | |
fa19602c | 205 | @end example |
a98cef7e KN |
206 | |
207 | The base pointer (bp) always points to the lowest address of local | |
208 | variables of the recent block. Local variables are referred as "bp[n]". | |
209 | The local link field has a pointer to the dynamic parent of the block. | |
210 | The parent's variables are referred as "bp[-1][n]", and grandparent's | |
211 | are "bp[-1][-1][n]". Thus, any local variable is represented by its | |
212 | depth and offset from the current bp. | |
213 | ||
214 | A variable may be "external", which is allocated in the shared memory. | |
215 | The external link field of a block has a pointer to such a variable set, | |
216 | which I call "fragment" (what should I call?). A fragment has a set of | |
217 | variables and its own chain. | |
218 | ||
fa19602c | 219 | @example |
a98cef7e KN |
220 | local external |
221 | chain| | chain | |
222 | | +-----+ .--------, | | |
015959cb | 223 | `-|block|--+->|external|-' |
a98cef7e KN |
224 | /+-----+ | `--------'\, |
225 | `-|block|--' | | |
226 | /+-----+ .--------, | | |
015959cb | 227 | `-|block|---->|external|-' |
a98cef7e KN |
228 | +-----+ `--------' |
229 | | | | |
fa19602c | 230 | @end example |
a98cef7e KN |
231 | |
232 | An external variable is referred as "bp[-2]->variables[n]" or | |
233 | "bp[-2]->link->...->variables[n]". This is also represented by a pair | |
234 | of depth and offset. At any point of execution, the value of bp | |
235 | determines the current local link and external link, and thus the | |
236 | current environment of a program. | |
237 | ||
238 | Other data fields are described later. | |
239 | ||
fa19602c | 240 | @section Top-level variables |
a98cef7e KN |
241 | |
242 | Guile VM uses the same top-level variables as the regular Guile. A | |
243 | program may have direct access to vcells. Currently this is done by | |
244 | calling scm_intern0, but a program is possible to have any top-level | |
245 | environment defined by the current module. | |
246 | ||
fa19602c | 247 | @section Scheme and VM variable |
a98cef7e KN |
248 | |
249 | Let's think about the following Scheme code as an example: | |
250 | ||
fa19602c | 251 | @example |
a98cef7e KN |
252 | (define (foo a) |
253 | (lambda (b) (list foo a b))) | |
fa19602c | 254 | @end example |
a98cef7e KN |
255 | |
256 | In the lambda expression, "foo" is a top-level variable, "a" is an | |
257 | external variable, and "b" is a local variable. | |
258 | ||
259 | When a VM executes foo, it allocates a block for "a". Since "a" may be | |
260 | externally referred from the closure, the VM creates a fragment with a | |
261 | copy of "a" in it. When the VM evaluates the lambda expression, it | |
262 | creates a subprogram (closure), associating the fragment with the | |
263 | subprogram as its external environment. When the closure is executed, | |
264 | its environment will look like this: | |
265 | ||
fa19602c | 266 | @example |
a98cef7e KN |
267 | block Top-level: foo |
268 | +-------------+ | |
269 | |local var: b | fragment | |
270 | +-------------+ .-----------, | |
271 | |external link|---->|variable: a| | |
272 | +-------------+ `-----------' | |
fa19602c | 273 | @end example |
a98cef7e KN |
274 | |
275 | The fragment remains as long as the closure exists. | |
276 | ||
fa19602c | 277 | @section Addressing mode |
a98cef7e KN |
278 | |
279 | Guile VM has five addressing modes: | |
280 | ||
fa19602c LC |
281 | @itemize |
282 | @item Real address | |
283 | @item Local position | |
284 | @item External position | |
285 | @item Top-level location | |
286 | @item Constant object | |
287 | @end itemize | |
a98cef7e KN |
288 | |
289 | Real address points to the address in the real program and is only used | |
290 | with the program counter (pc). | |
291 | ||
292 | Local position and external position are represented as a pair of depth | |
293 | and offset from bp, as described above. These are base relative | |
294 | addresses, and the real address may vary during execution. | |
295 | ||
296 | Top-level location is represented as a Guile's vcell. This location is | |
297 | determined at loading time, so the use of this address is efficient. | |
298 | ||
015959cb | 299 | Constant object is not an address but gives an instruction an Scheme |
a98cef7e KN |
300 | object directly. |
301 | ||
302 | [ We'll also need dynamic scope addressing to support Emacs Lisp? ] | |
303 | ||
fa19602c | 304 | @unnumberedsubsec At a Glance |
a98cef7e KN |
305 | |
306 | Guile VM has a set of instructions for each instruction family. `%load' | |
307 | is, for example, a family to load an object from memory and set the | |
308 | accumulator (ac). There are four basic `%load' instructions: | |
309 | ||
fa19602c | 310 | @example |
a98cef7e KN |
311 | %loadl - Local addressing |
312 | %loade - External addressing | |
313 | %loadt - Top-level addressing | |
314 | %loadi - Immediate addressing | |
fa19602c | 315 | @end example |
a98cef7e KN |
316 | |
317 | A possible program code may look like this: | |
318 | ||
fa19602c | 319 | @example |
a98cef7e KN |
320 | %loadl (0 . 1) ; ac = local[0][1] |
321 | %loade (2 . 3) ; ac = external[2][3] | |
322 | %loadt (foo . #<undefined>) ; ac = #<undefined> | |
323 | %loadi "hello" ; ac = "hello" | |
fa19602c | 324 | @end example |
a98cef7e KN |
325 | |
326 | One instruction that uses real addressing is `%jump', which changes the | |
327 | value of the program counter: | |
328 | ||
fa19602c | 329 | @example |
a98cef7e | 330 | %jump 0x80234ab8 ; pc = 0x80234ab8 |
fa19602c | 331 | @end example |
a98cef7e | 332 | |
a98cef7e | 333 | |
fa19602c LC |
334 | @node Program Execution, Instruction Set, Variable Management, Top |
335 | @chapter Program Execution | |
a98cef7e | 336 | |
fa19602c | 337 | Overall procedure: |
a98cef7e | 338 | |
fa19602c LC |
339 | @enumerate |
340 | @item A source program is compiled into a bytecode. | |
341 | @item A bytecode is given an environment and becomes a program. | |
342 | @item A VM starts execution, creating a frame for it. | |
343 | @item Whenever a program calls a subprogram, a new frame is created for it. | |
344 | @item When a program finishes execution, it returns a value, and the VM | |
345 | continues execution of the parent program. | |
346 | @item When all programs terminated, the VM returns the final value and stops. | |
347 | @end enumerate | |
a98cef7e | 348 | |
fa19602c | 349 | @section Environment |
a98cef7e KN |
350 | |
351 | Local variable: | |
352 | ||
fa19602c | 353 | @example |
a98cef7e KN |
354 | (let ((a 1) (b 2) (c 3)) (+ a b c)) -> |
355 | ||
356 | %pushi 1 ; a | |
357 | %pushi 2 ; b | |
358 | %pushi 3 ; c | |
359 | %bind 3 ; create local bindings | |
360 | %pushl (0 . 0) ; local variable a | |
361 | %pushl (0 . 1) ; local variable b | |
362 | %pushl (0 . 2) ; local variable c | |
363 | add 3 ; ac = a + b + c | |
364 | %unbind ; remove local bindings | |
fa19602c | 365 | @end example |
a98cef7e KN |
366 | |
367 | External variable: | |
368 | ||
fa19602c | 369 | @example |
a98cef7e KN |
370 | (define foo (let ((n 0)) (lambda () n))) |
371 | ||
372 | %pushi 0 ; n | |
373 | %bind 1 ; create local bindings | |
374 | %export [0] ; make it an external variable | |
375 | %make-program #<bytecode xxx> ; create a program in this environment | |
376 | %unbind ; remove local bindings | |
377 | %savet (foo . #<undefined>) ; save the program in foo | |
378 | ||
379 | (foo) -> | |
380 | ||
381 | %loadt (foo . #<program xxx>) ; program has an external link | |
382 | %call 0 ; change the current external link | |
383 | %loade (0 . 0) ; external variable n | |
384 | %return ; recover the external link | |
fa19602c | 385 | @end example |
a98cef7e KN |
386 | |
387 | Top-level variable: | |
388 | ||
fa19602c | 389 | @example |
a98cef7e KN |
390 | foo -> |
391 | ||
392 | %loadt (foo . #<program xxx>) ; top-level variable foo | |
fa19602c | 393 | @end example |
a98cef7e | 394 | |
fa19602c | 395 | @section Flow control |
a98cef7e | 396 | |
fa19602c | 397 | @example |
a98cef7e KN |
398 | (if #t 1 0) -> |
399 | ||
400 | %loadi #t | |
401 | %br-if-not L1 | |
402 | %loadi 1 | |
403 | %jump L2 | |
404 | L1: %loadi 0 | |
405 | L2: | |
fa19602c | 406 | @end example |
a98cef7e | 407 | |
fa19602c | 408 | @section Function call |
a98cef7e KN |
409 | |
410 | Builtin function: | |
411 | ||
fa19602c | 412 | @example |
a98cef7e KN |
413 | (1+ 2) -> |
414 | ||
415 | %loadi 2 ; ac = 2 | |
416 | 1+ ; one argument | |
417 | ||
418 | (+ 1 2) -> | |
419 | ||
420 | %pushi 1 ; 1 -> stack | |
421 | %loadi 2 ; ac = 2 | |
422 | add2 ; two argument | |
423 | ||
424 | (+ 1 2 3) -> | |
425 | ||
426 | %pushi 1 ; 1 -> stack | |
427 | %pushi 2 ; 2 -> stack | |
428 | %pushi 3 ; 3 -> stack | |
429 | add 3 ; many argument | |
fa19602c | 430 | @end example |
a98cef7e KN |
431 | |
432 | External function: | |
433 | ||
fa19602c | 434 | @example |
a98cef7e KN |
435 | (version) -> |
436 | ||
437 | %func0 (version . #<primitive-procedure version>) ; no argument | |
438 | ||
439 | (display "hello") -> | |
440 | ||
441 | %loadi "hello" | |
442 | %func1 (display . #<primitive-procedure display>) ; one argument | |
443 | ||
444 | (open-file "file" "w") -> | |
445 | ||
446 | %pushi "file" | |
447 | %loadi "w" | |
448 | %func2 (open-file . #<primitive-procedure open-file>) ; two arguments | |
449 | ||
450 | (equal 1 2 3) | |
451 | ||
452 | %pushi 1 | |
453 | %pushi 2 | |
454 | %pushi 3 | |
455 | %loadi 3 ; the number of arguments | |
456 | %func (equal . #<primitive-procedure equal>) ; many arguments | |
fa19602c | 457 | @end example |
a98cef7e | 458 | |
fa19602c | 459 | @section Subprogram call |
a98cef7e | 460 | |
a98cef7e | 461 | |
fa19602c LC |
462 | @node Instruction Set, , Program Execution, Top |
463 | @chapter Instruction Set | |
a98cef7e KN |
464 | |
465 | The Guile VM instruction set is roughly divided two groups: system | |
466 | instructions and functional instructions. System instructions control | |
467 | the execution of programs, while functional instructions provide many | |
238e7a11 LC |
468 | useful calculations. |
469 | ||
470 | @menu | |
471 | * Environment Control Instructions:: | |
f41cb00c | 472 | * Branch Instructions:: |
238e7a11 LC |
473 | * Subprogram Control Instructions:: |
474 | * Data Control Instructions:: | |
475 | @end menu | |
476 | ||
f41cb00c | 477 | @node Environment Control Instructions, Branch Instructions, Instruction Set, Instruction Set |
238e7a11 LC |
478 | @section Environment Control Instructions |
479 | ||
480 | @deffn @insn{} link binding-name | |
481 | Look up @var{binding-name} (a string) in the current environment and | |
482 | push the corresponding variable object onto the stack. If | |
483 | @var{binding-name} is not bound yet, then create a new binding and | |
484 | push its variable object. | |
485 | @end deffn | |
486 | ||
487 | @deffn @insn{} variable-ref | |
488 | Dereference the variable object which is on top of the stack and | |
489 | replace it by the value of the variable it represents. | |
490 | @end deffn | |
491 | ||
492 | @deffn @insn{} variable-set | |
493 | Set the value of the variable on top of the stack (at @code{sp[0]}) to | |
494 | the object located immediately before (at @code{sp[-1]}). | |
495 | @end deffn | |
496 | ||
497 | As an example, let us look at what a simple function call looks like: | |
498 | ||
499 | @example | |
500 | (+ 2 3) | |
501 | @end example | |
502 | ||
503 | This call yields the following sequence of instructions: | |
a98cef7e | 504 | |
238e7a11 | 505 | @example |
62082959 | 506 | (link "+") ;; lookup binding "+" |
238e7a11 LC |
507 | (variable-ref) ;; dereference it |
508 | (make-int8 2) ;; push immediate value `2' | |
509 | (make-int8 3) ;; push immediate value `3' | |
510 | (tail-call 2) ;; call the proc at sp[-3] with two args | |
511 | @end example | |
fa19602c | 512 | |
62082959 LC |
513 | @deffn @insn{} local-ref offset |
514 | Push onto the stack the value of the local variable located at | |
515 | @var{offset} within the current stack frame. | |
516 | @end deffn | |
517 | ||
518 | @deffn @insn{} local-set offset | |
519 | Pop the Scheme object located on top of the stack and make it the new | |
520 | value of the local variable located at @var{offset} within the current | |
521 | stack frame. | |
522 | @end deffn | |
523 | ||
524 | @deffn @insn{} external-ref offset | |
525 | Push the value of the closure variable located at position | |
526 | @var{offset} within the program's list of external variables. | |
527 | @end deffn | |
528 | ||
529 | @deffn @insn{} external-set offset | |
530 | Pop the Scheme object located on top of the stack and make it the new | |
531 | value of the closure variable located at @var{offset} within the | |
532 | program's list of external variables. | |
533 | @end deffn | |
534 | ||
0b5f0e49 LC |
535 | @deffn @insn{} make-closure |
536 | Pop the program object from the stack and assign it the current | |
537 | closure variable list as its closure. Push the result program | |
538 | object. | |
539 | @end deffn | |
540 | ||
541 | Let's illustrate this: | |
62082959 LC |
542 | |
543 | @example | |
544 | (let ((x 2)) | |
545 | (lambda () | |
546 | (let ((x++ (+ 1 x))) | |
547 | (set! x x++) | |
548 | x++))) | |
549 | @end example | |
550 | ||
551 | The resulting program has one external (closure) variable, i.e. its | |
552 | @var{nexts} is set to 1 (@pxref{Subprogram Control Instructions}). | |
553 | This yields the following code: | |
554 | ||
555 | @example | |
0b5f0e49 LC |
556 | ;; the traditional program prologue with NLOCS = 0 and NEXTS = 1 |
557 | ||
62082959 LC |
558 | 0 (make-int8 2) |
559 | 2 (external-set 0) | |
560 | 4 (make-int8 4) | |
0b5f0e49 LC |
561 | 6 (link "+") ;; lookup `+' |
562 | 9 (vector 1) ;; create the external variable vector for | |
563 | ;; later use by `object-ref' and `object-set' | |
62082959 LC |
564 | ... |
565 | 40 (load-program ##34#) | |
0b5f0e49 LC |
566 | 59 (make-closure) ;; assign the current closure to the program |
567 | ;; just pushed by `load-program' | |
568 | 60 (return) | |
62082959 LC |
569 | @end example |
570 | ||
571 | The program loaded here by @var{load-program} contains the following | |
572 | sequence of instructions: | |
573 | ||
574 | @example | |
575 | 0 (object-ref 0) ;; push the variable for `+' | |
576 | 2 (variable-ref) ;; dereference `+' | |
577 | 3 (make-int8:1) ;; push 1 | |
578 | 4 (external-ref 0) ;; push the value of `x' | |
579 | 6 (call 2) ;; call `+' and push the result | |
580 | 8 (local-set 0) ;; make it the new value of `x++' | |
581 | 10 (local-ref 0) ;; push the value of `x++' | |
582 | 12 (external-set 0) ;; make it the new value of `x' | |
583 | 14 (local-ref 0) ;; push the value of `x++' | |
584 | 16 (return) ;; return it | |
585 | @end example | |
586 | ||
0b5f0e49 LC |
587 | At this point, you should know pretty much everything about the three |
588 | types of variables a program may need to access. | |
fa19602c | 589 | |
f41cb00c LC |
590 | |
591 | @node Branch Instructions, Subprogram Control Instructions, Environment Control Instructions, Instruction Set | |
592 | @section Branch Instructions | |
593 | ||
594 | All the conditional branch instructions described below work in the | |
595 | same way: | |
596 | ||
597 | @itemize | |
598 | @item They take the Scheme object located on the stack and use it as | |
599 | the branch condition; | |
600 | @item If the condition if false, then program execution continues with | |
601 | the next instruction; | |
602 | @item If the condition is true, then the instruction pointer is | |
603 | increased by the offset passed as an argument to the branch | |
604 | instruction; | |
605 | @item Finally, when the instruction finished, the condition object is | |
606 | removed from the stack. | |
607 | @end itemize | |
608 | ||
609 | Note that the offset passed to the instruction is encoded on two 8-bit | |
610 | integers which are then combined by the VM as one 16-bit integer. | |
611 | ||
612 | @deffn @insn{} br offset | |
613 | Jump to @var{offset}. | |
614 | @end deffn | |
615 | ||
616 | @deffn @insn{} br-if offset | |
617 | Jump to @var{offset} if the condition on the stack is not false. | |
618 | @end deffn | |
619 | ||
620 | @deffn @insn{} br-if-not offset | |
621 | Jump to @var{offset} if the condition on the stack is false. | |
622 | @end deffn | |
623 | ||
624 | @deffn @insn{} br-if-eq offset | |
625 | Jump to @var{offset} if the two objects located on the stack are | |
626 | equal in the sense of @var{eq?}. Note that, for this instruction, the | |
627 | stack pointer is decremented by two Scheme objects instead of only | |
628 | one. | |
629 | @end deffn | |
630 | ||
631 | @deffn @insn{} br-if-not-eq offset | |
632 | Same as @var{br-if-eq} for non-equal objects. | |
633 | @end deffn | |
634 | ||
635 | @deffn @insn{} br-if-null offset | |
636 | Jump to @var{offset} if the object on the stack is @code{'()}. | |
637 | @end deffn | |
638 | ||
639 | @deffn @insn{} br-if-not-null offset | |
640 | Jump to @var{offset} if the object on the stack is not @code{'()}. | |
641 | @end deffn | |
642 | ||
643 | ||
644 | @node Subprogram Control Instructions, Data Control Instructions, Branch Instructions, Instruction Set | |
238e7a11 LC |
645 | @section Subprogram Control Instructions |
646 | ||
647 | Programs (read: ``compiled procedure'') may refer to external | |
648 | bindings, like variables or functions defined outside the program | |
649 | itself, in the environment in which it will evaluate at run-time. In | |
650 | a sense, a program's environment and its bindings are an implicit | |
651 | parameter of every program. | |
652 | ||
653 | @cindex Object table | |
654 | In order to handle such bindings, each program has an @dfn{object | |
0b5f0e49 LC |
655 | table} associated to it. This table (actually a Scheme vector) |
656 | contains all constant objects referenced by the program. The object | |
657 | table of a program is initialized right before a program is loaded | |
658 | with @var{load-program}. | |
659 | ||
660 | Variable objects are one such type of constant object: when a global | |
661 | binding is defined, a variable object is associated to it and that | |
662 | object will remain constant over time, even if the value bound to it | |
663 | changes. Therefore, external bindings only need to be looked up once | |
664 | when the program is loaded. References to the corresponding external | |
665 | variables from within the program are then performed via the | |
666 | @var{object-ref} instruction and are almost as fast as local variable | |
667 | references. | |
238e7a11 LC |
668 | |
669 | Let us consider the following program (procedure) which references | |
670 | external bindings @code{frob} and @var{%magic}: | |
671 | ||
672 | @example | |
673 | (lambda (x) | |
674 | (frob x %magic)) | |
675 | @end example | |
676 | ||
677 | This yields the following assembly code: | |
678 | ||
679 | @example | |
680 | (make-int8 64) ;; number of args, vars, etc. (see below) | |
681 | (link "frob") | |
682 | (link "%magic") | |
62082959 | 683 | (vector 2) ;; object table (external bindings) |
238e7a11 LC |
684 | ... |
685 | (load-program #u8(20 0 23 21 0 20 1 23 36 2)) | |
686 | (return) | |
687 | @end example | |
688 | ||
689 | All the instructions occurring before @var{load-program} (some were | |
690 | omitted for simplicity) form a @dfn{prologue} which, among other | |
691 | things, pushed an object table (a vector) that contains the variable | |
692 | objects for the variables bound to @var{frob} and @var{%magic}. This | |
693 | vector and other data pushed onto the stack are then popped by the | |
694 | @var{load-program} instruction. | |
695 | ||
696 | Besides, the @var{load-program} instruction takes one explicit | |
697 | argument which is the bytecode of the program itself. Disassembled, | |
698 | this bytecode looks like: | |
699 | ||
700 | @example | |
0b5f0e49 | 701 | (object-ref 0) ;; push the variable object of `frob' |
238e7a11 LC |
702 | (variable-ref) ;; dereference it |
703 | (local-ref 0) ;; push the value of `x' | |
704 | (object-ref 1) ;; push the variable object of `%magic' | |
705 | (variable-ref) ;; dereference it | |
706 | (tail-call 2) ;; call `frob' with two parameters | |
707 | @end example | |
708 | ||
709 | This clearly shows that there is little difference between references | |
62082959 LC |
710 | to local variables and references to externally bound variables since |
711 | lookup of externally bound variables if performed only once before the | |
712 | program is run. | |
238e7a11 LC |
713 | |
714 | @deffn @insn{} load-program bytecode | |
f41cb00c LC |
715 | Load the program whose bytecode is @var{bytecode} (a u8vector), pop |
716 | its meta-information from the stack, and push a corresponding program | |
717 | object onto the stack. The program's meta-information may consist of | |
718 | (in the order in which it should be pushed onto the stack): | |
fa19602c LC |
719 | |
720 | @itemize | |
238e7a11 LC |
721 | @item optionally, a pair representing meta-data (see the |
722 | @var{program-meta} procedure); [FIXME: explain their meaning] | |
723 | @item optionally, a vector which is the program's object table (a | |
724 | program that does not reference external bindings does not need an | |
725 | object table); | |
2d80426a LC |
726 | @item either one immediate integer or four immediate integers |
727 | representing respectively the number of arguments taken by the | |
728 | function (@var{nargs}), the number of @dfn{rest arguments} | |
729 | (@var{nrest}, 0 or 1), the number of local variables (@var{nlocs}) and | |
62082959 LC |
730 | the number of external variables (@var{nexts}) (@pxref{Environment |
731 | Control Instructions}). | |
fa19602c LC |
732 | @end itemize |
733 | ||
238e7a11 LC |
734 | @end deffn |
735 | ||
736 | @deffn @insn{} object-ref offset | |
737 | Push the variable object for the external variable located at | |
738 | @var{offset} within the program's object table. | |
739 | @end deffn | |
740 | ||
741 | @deffn @insn{} return | |
742 | Free the program's frame. | |
743 | @end deffn | |
744 | ||
f41cb00c LC |
745 | @deffn @insn{} call nargs |
746 | Call the procedure, continuation or program located at | |
747 | @code{sp[-nargs]} with the @var{nargs} arguments located from | |
748 | @code{sp[0]} to @code{sp[-nargs + 1]}. The | |
749 | procedure/continuation/program and its arguments are dropped from the | |
62082959 LC |
750 | stack and the result is pushed. When calling a program, the |
751 | @code{call} instruction reserves room for its local variables on the | |
752 | stack, and initializes its list of closure variables and its vector of | |
753 | externally bound variables. | |
f41cb00c LC |
754 | @end deffn |
755 | ||
756 | @deffn @insn{} tail-call nargs | |
757 | Same as @code{call} except that, for tail-recursive calls to a | |
758 | program, the current stack frame is re-used, as required by RnRS. | |
62082959 | 759 | This instruction is otherwise similar to @code{call}. |
f41cb00c LC |
760 | @end deffn |
761 | ||
238e7a11 LC |
762 | |
763 | @node Data Control Instructions, , Subprogram Control Instructions, Instruction Set | |
764 | @section Data Control Instructions | |
765 | ||
766 | @deffn @insn{} make-int8 value | |
767 | Push @var{value}, an 8-bit integer, onto the stack. | |
768 | @end deffn | |
769 | ||
770 | @deffn @insn{} make-int8:0 | |
771 | Push the immediate value @code{0} onto the stack. | |
772 | @end deffn | |
773 | ||
774 | @deffn @insn{} make-int8:1 | |
775 | Push the immediate value @code{1} onto the stack. | |
776 | @end deffn | |
777 | ||
778 | @deffn @insn{} make-false | |
779 | Push @code{#f} onto the stack. | |
780 | @end deffn | |
781 | ||
782 | @deffn @insn{} make-true | |
783 | Push @code{#t} onto the stack. | |
784 | @end deffn | |
fa19602c LC |
785 | |
786 | @itemize | |
787 | @item %push | |
788 | @item %pushi | |
789 | @item %pushl, %pushl:0:0, %pushl:0:1, %pushl:0:2, %pushl:0:3 | |
790 | @item %pushe, %pushe:0:0, %pushe:0:1, %pushe:0:2, %pushe:0:3 | |
791 | @item %pusht | |
792 | @end itemize | |
793 | ||
794 | @itemize | |
795 | @item %loadi | |
796 | @item %loadl, %loadl:0:0, %loadl:0:1, %loadl:0:2, %loadl:0:3 | |
797 | @item %loade, %loade:0:0, %loade:0:1, %loade:0:2, %loade:0:3 | |
798 | @item %loadt | |
799 | @end itemize | |
800 | ||
801 | @itemize | |
802 | @item %savei | |
803 | @item %savel, %savel:0:0, %savel:0:1, %savel:0:2, %savel:0:3 | |
804 | @item %savee, %savee:0:0, %savee:0:1, %savee:0:2, %savee:0:3 | |
805 | @item %savet | |
806 | @end itemize | |
807 | ||
808 | @section Flow control instructions | |
809 | ||
810 | @itemize | |
811 | @item %br-if | |
812 | @item %br-if-not | |
813 | @item %jump | |
814 | @end itemize | |
815 | ||
816 | @section Function call instructions | |
817 | ||
818 | @itemize | |
819 | @item %func, %func0, %func1, %func2 | |
820 | @end itemize | |
821 | ||
822 | @section Scheme built-in functions | |
823 | ||
824 | @itemize | |
825 | @item cons | |
826 | @item car | |
827 | @item cdr | |
828 | @end itemize | |
829 | ||
830 | @section Mathematical buitin functions | |
831 | ||
832 | @itemize | |
833 | @item 1+ | |
834 | @item 1- | |
835 | @item add, add2 | |
836 | @item sub, sub2, minus | |
837 | @item mul2 | |
838 | @item div2 | |
839 | @item lt2 | |
840 | @item gt2 | |
841 | @item le2 | |
842 | @item ge2 | |
843 | @item num-eq2 | |
844 | @end itemize | |
015959cb KN |
845 | |
846 | @c ********************************************************************* | |
fa19602c LC |
847 | @c @node Concept Index, Command Index, Related Information, Top |
848 | @c @unnumbered Concept Index | |
849 | @c @printindex cp | |
015959cb | 850 | |
fa19602c LC |
851 | @c @node Command Index, Variable Index, Concept Index, Top |
852 | @c @unnumbered Command Index | |
853 | @c @printindex fn | |
015959cb | 854 | |
fa19602c LC |
855 | @c @node Variable Index, , Command Index, Top |
856 | @c @unnumbered Variable Index | |
857 | @c @printindex vr | |
015959cb KN |
858 | |
859 | @bye | |
860 | \f | |
861 | @c Local Variables: | |
862 | @c mode:outline-minor | |
863 | @c outline-regexp:"@\\(ch\\|sec\\|subs\\)" | |
864 | @c End: | |
238e7a11 LC |
865 | |
866 | @c LocalWords: bytecode |