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 KN |
12 | |
13 | @ifinfo | |
14 | @dircategory Scheme Programming | |
15 | @direntry | |
16 | * Guile VM: (guile-vm). Guile Virtual Machine. | |
17 | @end direntry | |
18 | ||
19 | This file documents Guile VM. | |
20 | ||
21 | Copyright @copyright{} 2000 Keisuke Nishida | |
22 | ||
23 | Permission is granted to make and distribute verbatim copies of this | |
24 | manual provided the copyright notice and this permission notice are | |
25 | preserved on all copies. | |
26 | ||
27 | @ignore | |
28 | Permission is granted to process this file through TeX and print the | |
29 | results, provided the printed document carries a copying permission | |
30 | notice identical to this one except for the removal of this paragraph | |
31 | (this paragraph not being relevant to the printed manual). | |
32 | ||
33 | @end ignore | |
34 | Permission is granted to copy and distribute modified versions of this | |
35 | manual under the conditions for verbatim copying, provided that the | |
36 | entire resulting derived work is distributed under the terms of a | |
37 | permission notice identical to this one. | |
38 | ||
39 | Permission is granted to copy and distribute translations of this manual | |
40 | into another language, under the above conditions for modified versions, | |
41 | except that this permission notice may be stated in a translation | |
42 | approved by the Free Software Foundation. | |
43 | @end ifinfo | |
44 | ||
45 | @titlepage | |
46 | @title Guile VM Specification | |
47 | @subtitle for Guile VM @value{VERSION} | |
48 | @author Keisuke Nishida | |
49 | ||
50 | @page | |
51 | @vskip 0pt plus 1filll | |
52 | Edition @value{EDITION} @* | |
53 | Updated for Guile VM @value{VERSION} @* | |
54 | @value{UPDATED} @* | |
55 | ||
56 | Copyright @copyright{} 2000 Keisuke Nishida | |
57 | ||
58 | Permission is granted to make and distribute verbatim copies of this | |
59 | manual provided the copyright notice and this permission notice are | |
60 | preserved on all copies. | |
61 | ||
62 | Permission is granted to copy and distribute modified versions of this | |
63 | manual under the conditions for verbatim copying, provided that the | |
64 | entire resulting derived work is distributed under the terms of a | |
65 | permission notice identical to this one. | |
66 | ||
67 | Permission is granted to copy and distribute translations of this manual | |
68 | into another language, under the above conditions for modified versions, | |
69 | except that this permission notice may be stated in a translation | |
70 | approved by the Free Software Foundation. | |
71 | @end titlepage | |
72 | ||
73 | @contents | |
74 | ||
75 | @c ********************************************************************* | |
76 | @node Top, Introduction, (dir), (dir) | |
77 | @top Guile VM Specification | |
78 | ||
79 | This document corresponds to Guile VM @value{VERSION}. | |
80 | ||
81 | @menu | |
fa19602c LC |
82 | * Introduction:: |
83 | * Variable Management:: | |
84 | * Program Execution:: | |
85 | * Instruction Set:: | |
015959cb KN |
86 | @end menu |
87 | ||
88 | @c ********************************************************************* | |
fa19602c | 89 | @node Introduction, Variable Management, Top, Top |
015959cb | 90 | @chapter What is Guile VM? |
a98cef7e KN |
91 | |
92 | A Guile VM has a set of registers and its own stack memory. Guile may | |
93 | have more than one VM's. Each VM may execute at most one program at a | |
94 | time. Guile VM is a CISC system so designed as to execute Scheme and | |
95 | other languages efficiently. | |
96 | ||
fa19602c | 97 | @unnumberedsubsec Registers |
a98cef7e | 98 | |
fa19602c LC |
99 | @itemize |
100 | @item pc - Program counter ;; ip (instruction poiner) is better? | |
101 | @item sp - Stack pointer | |
102 | @item bp - Base pointer | |
103 | @item ac - Accumulator | |
104 | @end itemize | |
a98cef7e | 105 | |
fa19602c | 106 | @unnumberedsubsec Engine |
a98cef7e KN |
107 | |
108 | A VM may have one of three engines: reckless, regular, or debugging. | |
109 | Reckless engine is fastest but dangerous. Regular engine is normally | |
110 | fail-safe and reasonably fast. Debugging engine is safest and | |
111 | functional but very slow. | |
112 | ||
fa19602c | 113 | @unnumberedsubsec Memory |
a98cef7e KN |
114 | |
115 | Stack is the only memory that each VM owns. The other memory is shared | |
116 | memory that is shared among every VM and other part of Guile. | |
117 | ||
fa19602c | 118 | @unnumberedsubsec Program |
a98cef7e KN |
119 | |
120 | A VM program consists of a bytecode that is executed and an environment | |
121 | in which execution is done. Each program is allocated in the shared | |
122 | memory and may be executed by any VM. A program may call other programs | |
123 | within a VM. | |
124 | ||
fa19602c | 125 | @unnumberedsubsec Instruction |
a98cef7e KN |
126 | |
127 | Guile VM has dozens of system instructions and (possibly) hundreds of | |
128 | functional instructions. Some Scheme procedures such as cons and car | |
129 | are implemented as VM's builtin functions, which are very efficient. | |
130 | Other procedures defined outside of the VM are also considered as VM's | |
131 | functional features, since they do not change the state of VM. | |
132 | Procedures defined within the VM are called subprograms. | |
133 | ||
134 | Most instructions deal with the accumulator (ac). The VM stores all | |
135 | results from functions in ac, instead of pushing them into the stack. | |
136 | I'm not sure whether this is a good thing or not. | |
137 | ||
fa19602c | 138 | @node Variable Management, Program Execution, Introduction, Top |
015959cb | 139 | @chapter Variable Management |
a98cef7e KN |
140 | |
141 | A program may have access to local variables, external variables, and | |
142 | top-level variables. | |
143 | ||
fa19602c | 144 | @section Local/external variables |
a98cef7e KN |
145 | |
146 | A stack is logically divided into several blocks during execution. A | |
147 | "block" is such a unit that maintains local variables and dynamic chain. | |
148 | A "frame" is an upper level unit that maintains subprogram calls. | |
149 | ||
fa19602c | 150 | @example |
a98cef7e KN |
151 | Stack |
152 | dynamic | | | | | |
153 | chain +==========+ - = | |
154 | | |local vars| | | | |
155 | `-|block data| | block | | |
156 | /|frame data| | | | |
157 | | +----------+ - | | |
158 | | |local vars| | | frame | |
159 | `-|block data| | | | |
160 | /+----------+ - | | |
161 | | |local vars| | | | |
162 | `-|block data| | | | |
163 | /+==========+ - = | |
164 | | |local vars| | | | |
165 | `-|block data| | | | |
166 | /|frame data| | | | |
167 | | +----------+ - | | |
168 | | | | | | | |
fa19602c | 169 | @end example |
a98cef7e KN |
170 | |
171 | The first block of each frame may look like this: | |
172 | ||
fa19602c | 173 | @example |
a98cef7e KN |
174 | Address Data |
175 | ------- ---- | |
176 | xxx0028 Local variable 2 | |
177 | xxx0024 Local variable 1 | |
178 | bp ->xxx0020 Local variable 0 | |
179 | xxx001c Local link (block data) | |
180 | xxx0018 External link (block data) | |
181 | xxx0014 Stack pointer (block data) | |
182 | xxx0010 Return address (frame data) | |
183 | xxx000c Parent program (frame data) | |
fa19602c | 184 | @end example |
a98cef7e KN |
185 | |
186 | The base pointer (bp) always points to the lowest address of local | |
187 | variables of the recent block. Local variables are referred as "bp[n]". | |
188 | The local link field has a pointer to the dynamic parent of the block. | |
189 | The parent's variables are referred as "bp[-1][n]", and grandparent's | |
190 | are "bp[-1][-1][n]". Thus, any local variable is represented by its | |
191 | depth and offset from the current bp. | |
192 | ||
193 | A variable may be "external", which is allocated in the shared memory. | |
194 | The external link field of a block has a pointer to such a variable set, | |
195 | which I call "fragment" (what should I call?). A fragment has a set of | |
196 | variables and its own chain. | |
197 | ||
fa19602c | 198 | @example |
a98cef7e KN |
199 | local external |
200 | chain| | chain | |
201 | | +-----+ .--------, | | |
015959cb | 202 | `-|block|--+->|external|-' |
a98cef7e KN |
203 | /+-----+ | `--------'\, |
204 | `-|block|--' | | |
205 | /+-----+ .--------, | | |
015959cb | 206 | `-|block|---->|external|-' |
a98cef7e KN |
207 | +-----+ `--------' |
208 | | | | |
fa19602c | 209 | @end example |
a98cef7e KN |
210 | |
211 | An external variable is referred as "bp[-2]->variables[n]" or | |
212 | "bp[-2]->link->...->variables[n]". This is also represented by a pair | |
213 | of depth and offset. At any point of execution, the value of bp | |
214 | determines the current local link and external link, and thus the | |
215 | current environment of a program. | |
216 | ||
217 | Other data fields are described later. | |
218 | ||
fa19602c | 219 | @section Top-level variables |
a98cef7e KN |
220 | |
221 | Guile VM uses the same top-level variables as the regular Guile. A | |
222 | program may have direct access to vcells. Currently this is done by | |
223 | calling scm_intern0, but a program is possible to have any top-level | |
224 | environment defined by the current module. | |
225 | ||
fa19602c | 226 | @section Scheme and VM variable |
a98cef7e KN |
227 | |
228 | Let's think about the following Scheme code as an example: | |
229 | ||
fa19602c | 230 | @example |
a98cef7e KN |
231 | (define (foo a) |
232 | (lambda (b) (list foo a b))) | |
fa19602c | 233 | @end example |
a98cef7e KN |
234 | |
235 | In the lambda expression, "foo" is a top-level variable, "a" is an | |
236 | external variable, and "b" is a local variable. | |
237 | ||
238 | When a VM executes foo, it allocates a block for "a". Since "a" may be | |
239 | externally referred from the closure, the VM creates a fragment with a | |
240 | copy of "a" in it. When the VM evaluates the lambda expression, it | |
241 | creates a subprogram (closure), associating the fragment with the | |
242 | subprogram as its external environment. When the closure is executed, | |
243 | its environment will look like this: | |
244 | ||
fa19602c | 245 | @example |
a98cef7e KN |
246 | block Top-level: foo |
247 | +-------------+ | |
248 | |local var: b | fragment | |
249 | +-------------+ .-----------, | |
250 | |external link|---->|variable: a| | |
251 | +-------------+ `-----------' | |
fa19602c | 252 | @end example |
a98cef7e KN |
253 | |
254 | The fragment remains as long as the closure exists. | |
255 | ||
fa19602c | 256 | @section Addressing mode |
a98cef7e KN |
257 | |
258 | Guile VM has five addressing modes: | |
259 | ||
fa19602c LC |
260 | @itemize |
261 | @item Real address | |
262 | @item Local position | |
263 | @item External position | |
264 | @item Top-level location | |
265 | @item Constant object | |
266 | @end itemize | |
a98cef7e KN |
267 | |
268 | Real address points to the address in the real program and is only used | |
269 | with the program counter (pc). | |
270 | ||
271 | Local position and external position are represented as a pair of depth | |
272 | and offset from bp, as described above. These are base relative | |
273 | addresses, and the real address may vary during execution. | |
274 | ||
275 | Top-level location is represented as a Guile's vcell. This location is | |
276 | determined at loading time, so the use of this address is efficient. | |
277 | ||
015959cb | 278 | Constant object is not an address but gives an instruction an Scheme |
a98cef7e KN |
279 | object directly. |
280 | ||
281 | [ We'll also need dynamic scope addressing to support Emacs Lisp? ] | |
282 | ||
fa19602c | 283 | @unnumberedsubsec At a Glance |
a98cef7e KN |
284 | |
285 | Guile VM has a set of instructions for each instruction family. `%load' | |
286 | is, for example, a family to load an object from memory and set the | |
287 | accumulator (ac). There are four basic `%load' instructions: | |
288 | ||
fa19602c | 289 | @example |
a98cef7e KN |
290 | %loadl - Local addressing |
291 | %loade - External addressing | |
292 | %loadt - Top-level addressing | |
293 | %loadi - Immediate addressing | |
fa19602c | 294 | @end example |
a98cef7e KN |
295 | |
296 | A possible program code may look like this: | |
297 | ||
fa19602c | 298 | @example |
a98cef7e KN |
299 | %loadl (0 . 1) ; ac = local[0][1] |
300 | %loade (2 . 3) ; ac = external[2][3] | |
301 | %loadt (foo . #<undefined>) ; ac = #<undefined> | |
302 | %loadi "hello" ; ac = "hello" | |
fa19602c | 303 | @end example |
a98cef7e KN |
304 | |
305 | One instruction that uses real addressing is `%jump', which changes the | |
306 | value of the program counter: | |
307 | ||
fa19602c | 308 | @example |
a98cef7e | 309 | %jump 0x80234ab8 ; pc = 0x80234ab8 |
fa19602c | 310 | @end example |
a98cef7e | 311 | |
a98cef7e | 312 | |
fa19602c LC |
313 | @node Program Execution, Instruction Set, Variable Management, Top |
314 | @chapter Program Execution | |
a98cef7e | 315 | |
fa19602c | 316 | Overall procedure: |
a98cef7e | 317 | |
fa19602c LC |
318 | @enumerate |
319 | @item A source program is compiled into a bytecode. | |
320 | @item A bytecode is given an environment and becomes a program. | |
321 | @item A VM starts execution, creating a frame for it. | |
322 | @item Whenever a program calls a subprogram, a new frame is created for it. | |
323 | @item When a program finishes execution, it returns a value, and the VM | |
324 | continues execution of the parent program. | |
325 | @item When all programs terminated, the VM returns the final value and stops. | |
326 | @end enumerate | |
a98cef7e | 327 | |
fa19602c | 328 | @section Environment |
a98cef7e KN |
329 | |
330 | Local variable: | |
331 | ||
fa19602c | 332 | @example |
a98cef7e KN |
333 | (let ((a 1) (b 2) (c 3)) (+ a b c)) -> |
334 | ||
335 | %pushi 1 ; a | |
336 | %pushi 2 ; b | |
337 | %pushi 3 ; c | |
338 | %bind 3 ; create local bindings | |
339 | %pushl (0 . 0) ; local variable a | |
340 | %pushl (0 . 1) ; local variable b | |
341 | %pushl (0 . 2) ; local variable c | |
342 | add 3 ; ac = a + b + c | |
343 | %unbind ; remove local bindings | |
fa19602c | 344 | @end example |
a98cef7e KN |
345 | |
346 | External variable: | |
347 | ||
fa19602c | 348 | @example |
a98cef7e KN |
349 | (define foo (let ((n 0)) (lambda () n))) |
350 | ||
351 | %pushi 0 ; n | |
352 | %bind 1 ; create local bindings | |
353 | %export [0] ; make it an external variable | |
354 | %make-program #<bytecode xxx> ; create a program in this environment | |
355 | %unbind ; remove local bindings | |
356 | %savet (foo . #<undefined>) ; save the program in foo | |
357 | ||
358 | (foo) -> | |
359 | ||
360 | %loadt (foo . #<program xxx>) ; program has an external link | |
361 | %call 0 ; change the current external link | |
362 | %loade (0 . 0) ; external variable n | |
363 | %return ; recover the external link | |
fa19602c | 364 | @end example |
a98cef7e KN |
365 | |
366 | Top-level variable: | |
367 | ||
fa19602c | 368 | @example |
a98cef7e KN |
369 | foo -> |
370 | ||
371 | %loadt (foo . #<program xxx>) ; top-level variable foo | |
fa19602c | 372 | @end example |
a98cef7e | 373 | |
fa19602c | 374 | @section Flow control |
a98cef7e | 375 | |
fa19602c | 376 | @example |
a98cef7e KN |
377 | (if #t 1 0) -> |
378 | ||
379 | %loadi #t | |
380 | %br-if-not L1 | |
381 | %loadi 1 | |
382 | %jump L2 | |
383 | L1: %loadi 0 | |
384 | L2: | |
fa19602c | 385 | @end example |
a98cef7e | 386 | |
fa19602c | 387 | @section Function call |
a98cef7e KN |
388 | |
389 | Builtin function: | |
390 | ||
fa19602c | 391 | @example |
a98cef7e KN |
392 | (1+ 2) -> |
393 | ||
394 | %loadi 2 ; ac = 2 | |
395 | 1+ ; one argument | |
396 | ||
397 | (+ 1 2) -> | |
398 | ||
399 | %pushi 1 ; 1 -> stack | |
400 | %loadi 2 ; ac = 2 | |
401 | add2 ; two argument | |
402 | ||
403 | (+ 1 2 3) -> | |
404 | ||
405 | %pushi 1 ; 1 -> stack | |
406 | %pushi 2 ; 2 -> stack | |
407 | %pushi 3 ; 3 -> stack | |
408 | add 3 ; many argument | |
fa19602c | 409 | @end example |
a98cef7e KN |
410 | |
411 | External function: | |
412 | ||
fa19602c | 413 | @example |
a98cef7e KN |
414 | (version) -> |
415 | ||
416 | %func0 (version . #<primitive-procedure version>) ; no argument | |
417 | ||
418 | (display "hello") -> | |
419 | ||
420 | %loadi "hello" | |
421 | %func1 (display . #<primitive-procedure display>) ; one argument | |
422 | ||
423 | (open-file "file" "w") -> | |
424 | ||
425 | %pushi "file" | |
426 | %loadi "w" | |
427 | %func2 (open-file . #<primitive-procedure open-file>) ; two arguments | |
428 | ||
429 | (equal 1 2 3) | |
430 | ||
431 | %pushi 1 | |
432 | %pushi 2 | |
433 | %pushi 3 | |
434 | %loadi 3 ; the number of arguments | |
435 | %func (equal . #<primitive-procedure equal>) ; many arguments | |
fa19602c | 436 | @end example |
a98cef7e | 437 | |
fa19602c | 438 | @section Subprogram call |
a98cef7e | 439 | |
fa19602c | 440 | @example |
a98cef7e KN |
441 | (define (plus a b) (+ a b)) |
442 | (plus 1 2) -> | |
443 | ||
444 | %pushi 1 ; argument 1 | |
445 | %pushi 2 ; argument 2 | |
446 | %loadt (plus . #<program xxx>) ; load the program | |
447 | %call 2 ; call it with two arguments | |
448 | %pushl (0 . 0) ; argument 1 | |
449 | %loadl (0 . 1) ; argument 2 | |
450 | add2 ; ac = 1 + 2 | |
451 | %return ; result is 3 | |
fa19602c | 452 | @end example |
a98cef7e | 453 | |
fa19602c LC |
454 | @node Instruction Set, , Program Execution, Top |
455 | @chapter Instruction Set | |
a98cef7e KN |
456 | |
457 | The Guile VM instruction set is roughly divided two groups: system | |
458 | instructions and functional instructions. System instructions control | |
459 | the execution of programs, while functional instructions provide many | |
460 | useful calculations. By convention, system instructions begin with a | |
461 | letter `%'. | |
462 | ||
fa19602c LC |
463 | @section Environment control instructions |
464 | ||
465 | @itemize | |
466 | @item %alloc | |
467 | @item %bind | |
468 | @item %export | |
469 | @item %unbind | |
470 | @end itemize | |
471 | ||
472 | @section Subprogram control instructions | |
473 | ||
474 | @itemize | |
475 | @item %make-program | |
476 | @item %call | |
477 | @item %return | |
478 | @end itemize | |
479 | ||
480 | @section Data control instructinos | |
481 | ||
482 | @itemize | |
483 | @item %push | |
484 | @item %pushi | |
485 | @item %pushl, %pushl:0:0, %pushl:0:1, %pushl:0:2, %pushl:0:3 | |
486 | @item %pushe, %pushe:0:0, %pushe:0:1, %pushe:0:2, %pushe:0:3 | |
487 | @item %pusht | |
488 | @end itemize | |
489 | ||
490 | @itemize | |
491 | @item %loadi | |
492 | @item %loadl, %loadl:0:0, %loadl:0:1, %loadl:0:2, %loadl:0:3 | |
493 | @item %loade, %loade:0:0, %loade:0:1, %loade:0:2, %loade:0:3 | |
494 | @item %loadt | |
495 | @end itemize | |
496 | ||
497 | @itemize | |
498 | @item %savei | |
499 | @item %savel, %savel:0:0, %savel:0:1, %savel:0:2, %savel:0:3 | |
500 | @item %savee, %savee:0:0, %savee:0:1, %savee:0:2, %savee:0:3 | |
501 | @item %savet | |
502 | @end itemize | |
503 | ||
504 | @section Flow control instructions | |
505 | ||
506 | @itemize | |
507 | @item %br-if | |
508 | @item %br-if-not | |
509 | @item %jump | |
510 | @end itemize | |
511 | ||
512 | @section Function call instructions | |
513 | ||
514 | @itemize | |
515 | @item %func, %func0, %func1, %func2 | |
516 | @end itemize | |
517 | ||
518 | @section Scheme built-in functions | |
519 | ||
520 | @itemize | |
521 | @item cons | |
522 | @item car | |
523 | @item cdr | |
524 | @end itemize | |
525 | ||
526 | @section Mathematical buitin functions | |
527 | ||
528 | @itemize | |
529 | @item 1+ | |
530 | @item 1- | |
531 | @item add, add2 | |
532 | @item sub, sub2, minus | |
533 | @item mul2 | |
534 | @item div2 | |
535 | @item lt2 | |
536 | @item gt2 | |
537 | @item le2 | |
538 | @item ge2 | |
539 | @item num-eq2 | |
540 | @end itemize | |
015959cb KN |
541 | |
542 | @c ********************************************************************* | |
fa19602c LC |
543 | @c @node Concept Index, Command Index, Related Information, Top |
544 | @c @unnumbered Concept Index | |
545 | @c @printindex cp | |
015959cb | 546 | |
fa19602c LC |
547 | @c @node Command Index, Variable Index, Concept Index, Top |
548 | @c @unnumbered Command Index | |
549 | @c @printindex fn | |
015959cb | 550 | |
fa19602c LC |
551 | @c @node Variable Index, , Command Index, Top |
552 | @c @unnumbered Variable Index | |
553 | @c @printindex vr | |
015959cb KN |
554 | |
555 | @bye | |
556 | \f | |
557 | @c Local Variables: | |
558 | @c mode:outline-minor | |
559 | @c outline-regexp:"@\\(ch\\|sec\\|subs\\)" | |
560 | @c End: |