[gforth] / gforth / Attic / gforth.ds

gforth: gforth/Attic/gforth.ds

1 :	anton	1.1	\input texinfo @c --texinfo--
2 :			@comment The source is gforth.ds, from which gforth.texi is generated
3 :			@comment %**start of header (This is for running Texinfo on a region.)
4 :	anton	1.4	@setfilename gforth.info
5 :	anton	1.1	@settitle GNU Forth Manual
6 :	anton	1.4	@comment @setchapternewpage odd
7 :	anton	1.1	@comment %**end of header (This is for running Texinfo on a region.)
8 :
9 :			@ifinfo
10 :			This file documents GNU Forth 0.0
11 :
12 :			Copyright @copyright{} 1994 GNU Forth Development Group
13 :
14 :			Permission is granted to make and distribute verbatim copies of
15 :			this manual provided the copyright notice and this permission notice
16 :			are preserved on all copies.
17 :
18 :	anton	1.4	@ignore
19 :	anton	1.1	Permission is granted to process this file through TeX and print the
20 :			results, provided the printed document carries a copying permission
21 :			notice identical to this one except for the removal of this paragraph
22 :			(this paragraph not being relevant to the printed manual).
23 :
24 :	anton	1.4	@end ignore
25 :	anton	1.1	Permission is granted to copy and distribute modified versions of this
26 :			manual under the conditions for verbatim copying, provided also that the
27 :			sections entitled "Distribution" and "General Public License" are
28 :			included exactly as in the original, and provided that the entire
29 :			resulting derived work is distributed under the terms of a permission
30 :			notice identical to this one.
31 :
32 :			Permission is granted to copy and distribute translations of this manual
33 :			into another language, under the above conditions for modified versions,
34 :			except that the sections entitled "Distribution" and "General Public
35 :			License" may be included in a translation approved by the author instead
36 :			of in the original English.
37 :			@end ifinfo
38 :
39 :			@titlepage
40 :			@sp 10
41 :			@center @titlefont{GNU Forth Manual}
42 :			@sp 2
43 :			@center for version 0.0
44 :			@sp 2
45 :			@center Anton Ertl
46 :
47 :			@comment The following two commands start the copyright page.
48 :			@page
49 :			@vskip 0pt plus 1filll
50 :			Copyright @copyright{} 1994 GNU Forth Development Group
51 :
52 :			@comment !! Published by ... or You can get a copy of this manual ...
53 :
54 :			Permission is granted to make and distribute verbatim copies of
55 :			this manual provided the copyright notice and this permission notice
56 :			are preserved on all copies.
57 :
58 :			Permission is granted to copy and distribute modified versions of this
59 :			manual under the conditions for verbatim copying, provided also that the
60 :			sections entitled "Distribution" and "General Public License" are
61 :			included exactly as in the original, and provided that the entire
62 :			resulting derived work is distributed under the terms of a permission
63 :			notice identical to this one.
64 :
65 :			Permission is granted to copy and distribute translations of this manual
66 :			into another language, under the above conditions for modified versions,
67 :			except that the sections entitled "Distribution" and "General Public
68 :			License" may be included in a translation approved by the author instead
69 :			of in the original English.
70 :			@end titlepage
71 :
72 :
73 :			@node Top, License, (dir), (dir)
74 :			@ifinfo
75 :			GNU Forth is a free implementation of ANS Forth available on many
76 :			personal machines. This manual corresponds to version 0.0.
77 :			@end ifinfo
78 :
79 :			@menu
80 :	anton	1.4	* License::
81 :			* Goals:: About the GNU Forth Project
82 :			* Other Books:: Things you might want to read
83 :			* Invocation:: Starting GNU Forth
84 :			* Words:: Forth words available in GNU Forth
85 :			* ANS conformance:: Implementation-defined options etc.
86 :			* Model:: The abstract machine of GNU Forth
87 :			* Emacs and GForth:: The GForth Mode
88 :			* Internals:: Implementation details
89 :			* Bugs:: How to report them
90 :			* Pedigree:: Ancestors of GNU Forth
91 :			* Word Index:: An item for each Forth word
92 :			* Node Index:: An item for each node
93 :	anton	1.1	@end menu
94 :
95 :			@node License, Goals, Top, Top
96 :			@unnumbered License
97 :			!! Insert GPL here
98 :
99 :			@iftex
100 :			@unnumbered Preface
101 :			This manual documents GNU Forth. The reader is expected to know
102 :			Forth. This manual is primarily a reference manual. @xref{Other Books}
103 :			for introductory material.
104 :			@end iftex
105 :
106 :			@node Goals, Other Books, License, Top
107 :			@comment node-name, next, previous, up
108 :			@chapter Goals of GNU Forth
109 :			@cindex Goals
110 :			The goal of the GNU Forth Project is to develop a standard model for
111 :			ANSI Forth. This can be split into several subgoals:
112 :
113 :			@itemize @bullet
114 :			@item
115 :			GNU Forth should conform to the ANSI Forth standard.
116 :			@item
117 :			It should be a model, i.e. it should define all the
118 :			implementation-dependent things.
119 :			@item
120 :			It should become standard, i.e. widely accepted and used. This goal
121 :			is the most difficult one.
122 :			@end itemize
123 :
124 :			To achieve these goals GNU Forth should be
125 :			@itemize @bullet
126 :			@item
127 :			Similar to previous models (fig-Forth, F83)
128 :			@item
129 :			Powerful. It should provide for all the things that are considered
130 :			necessary today and even some that are not yet considered necessary.
131 :			@item
132 :			Efficient. It should not get the reputation of being exceptionally
133 :			slow.
134 :			@item
135 :			Free.
136 :			@item
137 :			Available on many machines/easy to port.
138 :			@end itemize
139 :
140 :			Have we achieved these goals? GNU Forth conforms to the ANS Forth
141 :			standard; it may be considered a model, but we have not yet documented
142 :			which parts of the model are stable and which parts we are likely to
143 :			change; it certainly has not yet become a de facto standard. It has some
144 :			similarities and some differences to previous models; It has some
145 :			powerful features, but not yet everything that we envisioned; on RISCs
146 :			it is as fast as interpreters programmed in assembly, on
147 :			register-starved machines it is not so fast, but still faster than any
148 :			other C-based interpretive implementation; it is free and available on
149 :			many machines.
150 :
151 :			@node Other Books, Invocation, Goals, Top
152 :			@chapter Other books on ANS Forth
153 :
154 :			As the standard is relatively new, there are not many books out yet. It
155 :			is not recommended to learn Forth by using GNU Forth and a book that is
156 :			not written for ANS Forth, as you will not know your mistakes from the
157 :			deviations of the book.
158 :
159 :			There is, of course, the standard, the definite reference if you want to
160 :			write ANS Forth programs. It will be available in printed form from
161 :			Global Engineering Documents !! somtime in spring or summer 1994. If you
162 :			are lucky, you can still get dpANS6 (the draft that was approved as
163 :			standard) by aftp from ftp.uu.net:/vendor/minerva/x3j14.
164 :
165 :			@cite{Forth: The new model} by Jack Woehr (!! Publisher) is an
166 :			introductory book based on a draft version of the standard. It does not
167 :			cover the whole standard. It also contains interesting background
168 :			information (Jack Woehr was in the ANS Forth Technical Committe). It is
169 :			not appropriate for complete newbies, but programmers experienced in
170 :			other languages should find it ok.
171 :
172 :			@node Invocation, Words, Other Books, Top
173 :			@chapter Invocation
174 :
175 :			You will usually just say @code{gforth}. In many other cases the default
176 :			GNU Forth image will be invoked like this:
177 :
178 :			@example
179 :			gforth [files] [-e forth-code]
180 :			@end example
181 :
182 :			executing the contents of the files and the Forth code in the order they
183 :			are given.
184 :
185 :			In general, the command line looks like this:
186 :
187 :			@example
188 :			gforth [initialization options] [image-specific options]
189 :			@end example
190 :
191 :			The initialization options must come before the rest of the command
192 :			line. They are:
193 :
194 :			@table @code
195 :			@item --image-file @var{file}
196 :			Loads the Forth image @var{file} instead of the default
197 :			@file{gforth.fi}.
198 :
199 :			@item --path @var{path}
200 :			Uses @var{path} for searching the image file and Forth source code
201 :			files instead of the default in the environment variable
202 :			@code{GFORTHPATH} or the path specified at installation time (typically
203 :			@file{/usr/local/lib/gforth:.}). A path is given as a @code{:}-separated
204 :			list.
205 :
206 :			@item --dictionary-size @var{size}
207 :			@item -m @var{size}
208 :			Allocate @var{size} space for the Forth dictionary space instead of
209 :			using the default specified in the image (typically 256K). The
210 :			@var{size} specification consists of an integer and a unit (e.g.,
211 :			@code{4M}). The unit can be one of @code{b} (bytes), @code{e} (element
212 :			size, in this case Cells), @code{k} (kilobytes), and @code{M}
213 :			(Megabytes). If no unit is specified, @code{e} is used.
214 :
215 :			@item --data-stack-size @var{size}
216 :			@item -d @var{size}
217 :			Allocate @var{size} space for the data stack instead of using the
218 :			default specified in the image (typically 16K).
219 :
220 :			@item --return-stack-size @var{size}
221 :			@item -r @var{size}
222 :			Allocate @var{size} space for the return stack instead of using the
223 :			default specified in the image (typically 16K).
224 :
225 :			@item --fp-stack-size @var{size}
226 :			@item -f @var{size}
227 :			Allocate @var{size} space for the floating point stack instead of
228 :			using the default specified in the image (typically 16K). In this case
229 :			the unit specifier @code{e} refers to floating point numbers.
230 :
231 :			@item --locals-stack-size @var{size}
232 :			@item -l @var{size}
233 :			Allocate @var{size} space for the locals stack instead of using the
234 :			default specified in the image (typically 16K).
235 :
236 :			@end table
237 :
238 :			As explained above, the image-specific command-line arguments for the
239 :			default image @file{gforth.fi} consist of a sequence of filenames and
240 :			@code{-e @var{forth-code}} options that are interpreted in the seqence
241 :			in which they are given. The @code{-e @var{forth-code}} or
242 :			@code{--evaluate @var{forth-code}} option evaluates the forth
243 :			code. This option takes only one argument; if you want to evaluate more
244 :			Forth words, you have to quote them or use several @code{-e}s. To exit
245 :			after processing the command line (instead of entering interactive mode)
246 :			append @code{-e bye} to the command line.
247 :
248 :			Not yet implemented:
249 :			On startup the system first executes the system initialization file
250 :			(unless the option @code{--no-init-file} is given; note that the system
251 :			resulting from using this option may not be ANS Forth conformant). Then
252 :			the user initialization file @file{.gforth.fs} is executed, unless the
253 :			option @code{--no-rc} is given; this file is first searched in @file{.},
254 :			then in @file{~}, then in the normal path (see above).
255 :
256 :	anton	1.4	@node Words, ANS conformance, Invocation, Top
257 :	anton	1.1	@chapter Forth Words
258 :
259 :			@menu
260 :	anton	1.4	* Notation::
261 :			* Arithmetic::
262 :			* Stack Manipulation::
263 :			* Memory access::
264 :			* Control Structures::
265 :			* Locals::
266 :			* Defining Words::
267 :			* Wordlists::
268 :			* Files::
269 :			* Blocks::
270 :			* Other I/O::
271 :			* Programming Tools::
272 :			* Threading Words::
273 :	anton	1.1	@end menu
274 :
275 :			@node Notation, Arithmetic, Words, Words
276 :			@section Notation
277 :
278 :			The Forth words are described in this section in the glossary notation
279 :			that has become a de-facto standard for Forth texts, i.e.
280 :
281 :	anton	1.4	@format
282 :	anton	1.1	@var{word} @var{Stack effect} @var{wordset} @var{pronunciation}
283 :	anton	1.4	@end format
284 :	anton	1.1	@var{Description}
285 :
286 :			@table @var
287 :			@item word
288 :			The name of the word. BTW, GNU Forth is case insensitive, so you can
289 :			type the words in in lower case.
290 :
291 :			@item Stack effect
292 :			The stack effect is written in the notation @code{@var{before} --
293 :			@var{after}}, where @var{before} and @var{after} describe the top of
294 :			stack entries before and after the execution of the word. The rest of
295 :			the stack is not touched by the word. The top of stack is rightmost,
296 :			i.e., a stack sequence is written as it is typed in. Note that GNU Forth
297 :			uses a separate floating point stack, but a unified stack
298 :			notation. Also, return stack effects are not shown in @var{stack
299 :			effect}, but in @var{Description}. The name of a stack item describes
300 :			the type and/or the function of the item. See below for a discussion of
301 :			the types.
302 :
303 :			@item pronunciation
304 :			How the word is pronounced
305 :
306 :			@item wordset
307 :			The ANS Forth standard is divided into several wordsets. A standard
308 :			system need not support all of them. So, the fewer wordsets your program
309 :			uses the more portable it will be in theory. However, we suspect that
310 :			most ANS Forth systems on personal machines will feature all
311 :			wordsets. Words that are not defined in the ANS standard have
312 :			@code{gforth} as wordset.
313 :
314 :			@item Description
315 :			A description of the behaviour of the word.
316 :			@end table
317 :
318 :	anton	1.4	The type of a stack item is specified by the character(s) the name
319 :			starts with:
320 :	anton	1.1
321 :			@table @code
322 :			@item f
323 :			Bool, i.e. @code{false} or @code{true}.
324 :			@item c
325 :			Char
326 :			@item w
327 :			Cell, can contain an integer or an address
328 :			@item n
329 :			signed integer
330 :			@item u
331 :			unsigned integer
332 :			@item d
333 :			double sized signed integer
334 :			@item ud
335 :			double sized unsigned integer
336 :			@item r
337 :			Float
338 :			@item a_
339 :			Cell-aligned address
340 :			@item c_
341 :			Char-aligned address (note that a Char is two bytes in Windows NT)
342 :			@item f_
343 :			Float-aligned address
344 :			@item df_
345 :			Address aligned for IEEE double precision float
346 :			@item sf_
347 :			Address aligned for IEEE single precision float
348 :			@item xt
349 :			Execution token, same size as Cell
350 :			@item wid
351 :			Wordlist ID, same size as Cell
352 :			@item f83name
353 :			Pointer to a name structure
354 :			@end table
355 :
356 :	anton	1.4	@node Arithmetic, Stack Manipulation, Notation, Words
357 :	anton	1.1	@section Arithmetic
358 :			Forth arithmetic is not checked, i.e., you will not hear about integer
359 :			overflow on addition or multiplication, you may hear about division by
360 :			zero if you are lucky. The operator is written after the operands, but
361 :			the operands are still in the original order. I.e., the infix @code{2-1}
362 :			corresponds to @code{2 1 -}. Forth offers a variety of division
363 :			operators. If you perform division with potentially negative operands,
364 :			you do not want to use @code{/} or @code{/mod} with its undefined
365 :			behaviour, but rather @code{fm/mod} or @code{sm/mod} (probably the
366 :	anton	1.4	former, @pxref{Mixed precision}).
367 :
368 :			@menu
369 :			* Single precision::
370 :			* Bitwise operations::
371 :			* Mixed precision:: operations with single and double-cell integers
372 :			* Double precision:: Double-cell integer arithmetic
373 :			* Floating Point::
374 :			@end menu
375 :	anton	1.1
376 :	anton	1.4	@node Single precision, Bitwise operations, Arithmetic, Arithmetic
377 :	anton	1.1	@subsection Single precision
378 :			doc-+
379 :			doc--
380 :			doc-*
381 :			doc-/
382 :			doc-mod
383 :			doc-/mod
384 :			doc-negate
385 :			doc-abs
386 :			doc-min
387 :			doc-max
388 :
389 :	anton	1.4	@node Bitwise operations, Mixed precision, Single precision, Arithmetic
390 :	anton	1.1	@subsection Bitwise operations
391 :			doc-and
392 :			doc-or
393 :			doc-xor
394 :			doc-invert
395 :			doc-2*
396 :			doc-2/
397 :
398 :	anton	1.4	@node Mixed precision, Double precision, Bitwise operations, Arithmetic
399 :	anton	1.1	@subsection Mixed precision
400 :			doc-m+
401 :			doc-*/
402 :			doc-*/mod
403 :			doc-m*
404 :			doc-um*
405 :			doc-m*/
406 :			doc-um/mod
407 :			doc-fm/mod
408 :			doc-sm/rem
409 :
410 :	anton	1.4	@node Double precision, Floating Point, Mixed precision, Arithmetic
411 :	anton	1.1	@subsection Double precision
412 :			doc-d+
413 :			doc-d-
414 :			doc-dnegate
415 :			doc-dabs
416 :			doc-dmin
417 :			doc-dmax
418 :
419 :	anton	1.4	@node Floating Point, , Double precision, Arithmetic
420 :			@subsection Floating Point
421 :
422 :			Angles in floating point operations are given in radians (a full circle
423 :			has 2 pi radians). Note, that gforth has a separate floating point
424 :			stack, but we use the unified notation.
425 :
426 :			Floating point numbers have a number of unpleasant surprises for the
427 :			unwary (e.g., floating point addition is not associative) and even a few
428 :			for the wary. You should not use them unless you know what you are doing
429 :			or you don't care that the results you get are totally bogus. If you
430 :			want to learn about the problems of floating point numbers (and how to
431 :			avoid them), you might start with @cite{Goldberg, What every computer
432 :			scientist should know about floating-point numbers, Computing Surveys
433 :			?}.
434 :
435 :			doc-f+
436 :			doc-f-
437 :			doc-f*
438 :			doc-f/
439 :			doc-fnegate
440 :			doc-fabs
441 :			doc-fmax
442 :			doc-fmin
443 :			doc-floor
444 :			doc-fround
445 :			doc-f**
446 :			doc-fsqrt
447 :			doc-fexp
448 :			doc-fexpm1
449 :			doc-fln
450 :			doc-flnp1
451 :			doc-flog
452 :			doc-fsin
453 :			doc-fcos
454 :			doc-fsincos
455 :			doc-ftan
456 :			doc-fasin
457 :			doc-facos
458 :			doc-fatan
459 :			doc-fatan2
460 :			doc-fsinh
461 :			doc-fcosh
462 :			doc-ftanh
463 :			doc-fasinh
464 :			doc-facosh
465 :			doc-fatanh
466 :
467 :			@node Stack Manipulation, Memory access, Arithmetic, Words
468 :	anton	1.1	@section Stack Manipulation
469 :
470 :			gforth has a data stack (aka parameter stack) for characters, cells,
471 :			addresses, and double cells, a floating point stack for floating point
472 :			numbers, a return stack for storing the return addresses of colon
473 :			definitions and other data, and a locals stack for storing local
474 :			variables. Note that while every sane Forth has a separate floating
475 :			point stack, this is not strictly required; an ANS Forth system could
476 :			theoretically keep floating point numbers on the data stack. As an
477 :			additional difficulty, you don't know how many cells a floating point
478 :			number takes. It is reportedly possible to write words in a way that
479 :			they work also for a unified stack model, but we do not recommend trying
480 :	anton	1.4	it. Instead, just say that your program has an environmental dependency
481 :			on a separate FP stack.
482 :
483 :			Also, a Forth system is allowed to keep the local variables on the
484 :	anton	1.1	return stack. This is reasonable, as local variables usually eliminate
485 :			the need to use the return stack explicitly. So, if you want to produce
486 :			a standard complying program and if you are using local variables in a
487 :			word, forget about return stack manipulations in that word (see the
488 :			standard document for the exact rules).
489 :
490 :	anton	1.4	@menu
491 :			* Data stack::
492 :			* Floating point stack::
493 :			* Return stack::
494 :			* Locals stack::
495 :			* Stack pointer manipulation::
496 :			@end menu
497 :
498 :			@node Data stack, Floating point stack, Stack Manipulation, Stack Manipulation
499 :	anton	1.1	@subsection Data stack
500 :			doc-drop
501 :			doc-nip
502 :			doc-dup
503 :			doc-over
504 :			doc-tuck
505 :			doc-swap
506 :			doc-rot
507 :			doc--rot
508 :			doc-?dup
509 :			doc-pick
510 :			doc-roll
511 :			doc-2drop
512 :			doc-2nip
513 :			doc-2dup
514 :			doc-2over
515 :			doc-2tuck
516 :			doc-2swap
517 :			doc-2rot
518 :
519 :	anton	1.4	@node Floating point stack, Return stack, Data stack, Stack Manipulation
520 :	anton	1.1	@subsection Floating point stack
521 :			doc-fdrop
522 :			doc-fnip
523 :			doc-fdup
524 :			doc-fover
525 :			doc-ftuck
526 :			doc-fswap
527 :			doc-frot
528 :
529 :	anton	1.4	@node Return stack, Locals stack, Floating point stack, Stack Manipulation
530 :	anton	1.1	@subsection Return stack
531 :			doc->r
532 :			doc-r>
533 :			doc-r@
534 :			doc-rdrop
535 :			doc-2>r
536 :			doc-2r>
537 :			doc-2r@
538 :			doc-2rdrop
539 :
540 :	anton	1.4	@node Locals stack, Stack pointer manipulation, Return stack, Stack Manipulation
541 :	anton	1.1	@subsection Locals stack
542 :
543 :	anton	1.4	@node Stack pointer manipulation, , Locals stack, Stack Manipulation
544 :	anton	1.1	@subsection Stack pointer manipulation
545 :			doc-sp@
546 :			doc-sp!
547 :			doc-fp@
548 :			doc-fp!
549 :			doc-rp@
550 :			doc-rp!
551 :			doc-lp@
552 :			doc-lp!
553 :
554 :	anton	1.4	@node Memory access, Control Structures, Stack Manipulation, Words
555 :	anton	1.1	@section Memory access
556 :
557 :	anton	1.4	@menu
558 :			* Stack-Memory transfers::
559 :			* Address arithmetic::
560 :			* Memory block access::
561 :			@end menu
562 :
563 :			@node Stack-Memory transfers, Address arithmetic, Memory access, Memory access
564 :	anton	1.1	@subsection Stack-Memory transfers
565 :
566 :			doc-@
567 :			doc-!
568 :			doc-+!
569 :			doc-c@
570 :			doc-c!
571 :			doc-2@
572 :			doc-2!
573 :			doc-f@
574 :			doc-f!
575 :			doc-sf@
576 :			doc-sf!
577 :			doc-df@
578 :			doc-df!
579 :
580 :	anton	1.4	@node Address arithmetic, Memory block access, Stack-Memory transfers, Memory access
581 :	anton	1.1	@subsection Address arithmetic
582 :
583 :			ANS Forth does not specify the sizes of the data types. Instead, it
584 :			offers a number of words for computing sizes and doing address
585 :			arithmetic. Basically, address arithmetic is performed in terms of
586 :			address units (aus); on most systems the address unit is one byte. Note
587 :			that a character may have more than one au, so @code{chars} is no noop
588 :			(on systems where it is a noop, it compiles to nothing).
589 :
590 :			ANS Forth also defines words for aligning addresses for specific
591 :			addresses. Many computers require that accesses to specific data types
592 :			must only occur at specific addresses; e.g., that cells may only be
593 :			accessed at addresses divisible by 4. Even if a machine allows unaligned
594 :			accesses, it can usually perform aligned accesses faster.
595 :
596 :			For the performance-concious: alignment operations are usually only
597 :			necessary during the definition of a data structure, not during the
598 :			(more frequent) accesses to it.
599 :
600 :			ANS Forth defines no words for character-aligning addresses. This is not
601 :			an oversight, but reflects the fact that addresses that are not
602 :			char-aligned have no use in the standard and therefore will not be
603 :			created.
604 :
605 :			The standard guarantees that addresses returned by @code{CREATE}d words
606 :			are cell-aligned; in addition, gforth guarantees that these addresses
607 :			are aligned for all purposes.
608 :
609 :			doc-chars
610 :			doc-char+
611 :			doc-cells
612 :			doc-cell+
613 :			doc-align
614 :			doc-aligned
615 :			doc-floats
616 :			doc-float+
617 :			doc-falign
618 :			doc-faligned
619 :			doc-sfloats
620 :			doc-sfloat+
621 :			doc-sfalign
622 :			doc-sfaligned
623 :			doc-dfloats
624 :			doc-dfloat+
625 :			doc-dfalign
626 :			doc-dfaligned
627 :			doc-address-unit-bits
628 :
629 :	anton	1.4	@node Memory block access, , Address arithmetic, Memory access
630 :	anton	1.1	@subsection Memory block access
631 :
632 :			doc-move
633 :			doc-erase
634 :
635 :			While the previous words work on address units, the rest works on
636 :			characters.
637 :
638 :			doc-cmove
639 :			doc-cmove>
640 :			doc-fill
641 :			doc-blank
642 :
643 :	anton	1.4	@node Control Structures, Locals, Memory access, Words
644 :	anton	1.1	@section Control Structures
645 :
646 :			Control structures in Forth cannot be used in interpret state, only in
647 :			compile state, i.e., in a colon definition. We do not like this
648 :			limitation, but have not seen a satisfying way around it yet, although
649 :			many schemes have been proposed.
650 :
651 :	anton	1.4	@menu
652 :			* Selection::
653 :			* Simple Loops::
654 :			* Counted Loops::
655 :			* Arbitrary control structures::
656 :			* Calls and returns::
657 :			* Exception Handling::
658 :			@end menu
659 :
660 :			@node Selection, Simple Loops, Control Structures, Control Structures
661 :	anton	1.1	@subsection Selection
662 :
663 :			@example
664 :			@var{flag}
665 :			IF
666 :			@var{code}
667 :			ENDIF
668 :			@end example
669 :			or
670 :			@example
671 :			@var{flag}
672 :			IF
673 :			@var{code1}
674 :			ELSE
675 :			@var{code2}
676 :			ENDIF
677 :			@end example
678 :
679 :	anton	1.4	You can use @code{THEN} instead of @code{ENDIF}. Indeed, @code{THEN} is
680 :	anton	1.1	standard, and @code{ENDIF} is not, although it is quite popular. We
681 :			recommend using @code{ENDIF}, because it is less confusing for people
682 :			who also know other languages (and is not prone to reinforcing negative
683 :			prejudices against Forth in these people). Adding @code{ENDIF} to a
684 :			system that only supplies @code{THEN} is simple:
685 :			@example
686 :			: endif POSTPONE then ; immediate
687 :			@end example
688 :
689 :			[According to @cite{Webster's New Encyclopedic Dictionary}, @dfn{then
690 :			(adv.)} has the following meanings:
691 :			@quotation
692 :			... 2b: following next after in order ... 3d: as a necessary consequence
693 :			(if you were there, then you saw them).
694 :			@end quotation
695 :			Forth's @code{THEN} has the meaning 2b, whereas @code{THEN} in Pascal
696 :			and many other programming languages has the meaning 3d.]
697 :
698 :			We also provide the words @code{?dup-if} and @code{?dup-0=-if}, so you
699 :			can avoid using @code{?dup}.
700 :
701 :			@example
702 :			@var{n}
703 :			CASE
704 :			@var{n1} OF @var{code1} ENDOF
705 :			@var{n2} OF @var{code2} ENDOF
706 :	anton	1.4	@dots{}
707 :	anton	1.1	ENDCASE
708 :			@end example
709 :
710 :			Executes the first @var{codei}, where the @var{ni} is equal to
711 :			@var{n}. A default case can be added by simply writing the code after
712 :			the last @code{ENDOF}. It may use @var{n}, which is on top of the stack,
713 :			but must not consume it.
714 :
715 :	anton	1.4	@node Simple Loops, Counted Loops, Selection, Control Structures
716 :	anton	1.1	@subsection Simple Loops
717 :
718 :			@example
719 :			BEGIN
720 :			@var{code1}
721 :			@var{flag}
722 :			WHILE
723 :			@var{code2}
724 :			REPEAT
725 :			@end example
726 :
727 :			@var{code1} is executed and @var{flag} is computed. If it is true,
728 :			@var{code2} is executed and the loop is restarted; If @var{flag} is false, execution continues after the @code{REPEAT}.
729 :
730 :			@example
731 :			BEGIN
732 :			@var{code}
733 :			@var{flag}
734 :			UNTIL
735 :			@end example
736 :
737 :			@var{code} is executed. The loop is restarted if @code{flag} is false.
738 :
739 :			@example
740 :			BEGIN
741 :			@var{code}
742 :			AGAIN
743 :			@end example
744 :
745 :			This is an endless loop.
746 :
747 :	anton	1.4	@node Counted Loops, Arbitrary control structures, Simple Loops, Control Structures
748 :	anton	1.1	@subsection Counted Loops
749 :
750 :			The basic counted loop is:
751 :			@example
752 :			@var{limit} @var{start}
753 :			?DO
754 :			@var{body}
755 :			LOOP
756 :			@end example
757 :
758 :			This performs one iteration for every integer, starting from @var{start}
759 :			and up to, but excluding @var{limit}. The counter, aka index, can be
760 :			accessed with @code{i}. E.g., the loop
761 :			@example
762 :			10 0 ?DO
763 :			i .
764 :			LOOP
765 :			@end example
766 :			prints
767 :			@example
768 :			0 1 2 3 4 5 6 7 8 9
769 :			@end example
770 :			The index of the innermost loop can be accessed with @code{i}, the index
771 :			of the next loop with @code{j}, and the index of the third loop with
772 :			@code{k}.
773 :
774 :			The loop control data are kept on the return stack, so there are some
775 :			restrictions on mixing return stack accesses and counted loop
776 :			words. E.g., if you put values on the return stack outside the loop, you
777 :			cannot read them inside the loop. If you put values on the return stack
778 :			within a loop, you have to remove them before the end of the loop and
779 :			before accessing the index of the loop.
780 :
781 :			There are several variations on the counted loop:
782 :
783 :			@code{LEAVE} leaves the innermost counted loop immediately.
784 :
785 :			@code{LOOP} can be replaced with @code{@var{n} +LOOP}; this updates the
786 :			index by @var{n} instead of by 1. The loop is terminated when the border
787 :			between @var{limit-1} and @var{limit} is crossed. E.g.:
788 :
789 :	anton	1.2	@code{4 0 ?DO i . 2 +LOOP} prints @code{0 2}
790 :	anton	1.1
791 :	anton	1.2	@code{4 1 ?DO i . 2 +LOOP} prints @code{1 3}
792 :	anton	1.1
793 :			The behaviour of @code{@var{n} +LOOP} is peculiar when @var{n} is negative:
794 :
795 :	anton	1.2	@code{-1 0 ?DO i . -1 +LOOP} prints @code{0 -1}
796 :	anton	1.1
797 :	anton	1.2	@code{ 0 0 ?DO i . -1 +LOOP} prints nothing
798 :	anton	1.1
799 :			Therefore we recommend avoiding using @code{@var{n} +LOOP} with negative
800 :			@var{n}. One alternative is @code{@var{n} S+LOOP}, where the negative
801 :			case behaves symmetrical to the positive case:
802 :
803 :	anton	1.2	@code{-2 0 ?DO i . -1 +LOOP} prints @code{0 -1}
804 :	anton	1.1
805 :	anton	1.2	@code{-1 0 ?DO i . -1 +LOOP} prints @code{0}
806 :	anton	1.1
807 :	anton	1.2	@code{ 0 0 ?DO i . -1 +LOOP} prints nothing
808 :	anton	1.1
809 :	anton	1.2	The loop is terminated when the border between @var{limit@minus{}sgn(n)} and
810 :	anton	1.1	@var{limit} is crossed. However, @code{S+LOOP} is not part of the ANS
811 :			Forth standard.
812 :
813 :			@code{?DO} can be replaced by @code{DO}. @code{DO} enters the loop even
814 :			when the start and the limit value are equal. We do not recommend using
815 :			@code{DO}. It will just give you maintenance troubles.
816 :
817 :			@code{UNLOOP} is used to prepare for an abnormal loop exit, e.g., via
818 :			@code{EXIT}. @code{UNLOOP} removes the loop control parameters from the
819 :			return stack so @code{EXIT} can get to its return address.
820 :
821 :			Another counted loop is
822 :			@example
823 :			@var{n}
824 :			FOR
825 :			@var{body}
826 :			NEXT
827 :			@end example
828 :			This is the preferred loop of native code compiler writers who are too
829 :			lazy to optimize @code{?DO} loops properly. In GNU Forth, this loop
830 :			iterates @var{n+1} times; @code{i} produces values starting with @var{n}
831 :			and ending with 0. Other Forth systems may behave differently, even if
832 :			they support @code{FOR} loops.
833 :
834 :	anton	1.4	@node Arbitrary control structures, Calls and returns, Counted Loops, Control Structures
835 :	anton	1.2	@subsection Arbitrary control structures
836 :
837 :			ANS Forth permits and supports using control structures in a non-nested
838 :			way. Information about incomplete control structures is stored on the
839 :			control-flow stack. This stack may be implemented on the Forth data
840 :			stack, and this is what we have done in gforth.
841 :
842 :			An @i{orig} entry represents an unresolved forward branch, a @i{dest}
843 :			entry represents a backward branch target. A few words are the basis for
844 :			building any control structure possible (except control structures that
845 :			need storage, like calls, coroutines, and backtracking).
846 :
847 :	anton	1.3	doc-if
848 :			doc-ahead
849 :			doc-then
850 :			doc-begin
851 :			doc-until
852 :			doc-again
853 :			doc-cs-pick
854 :			doc-cs-roll
855 :	anton	1.2
856 :			On many systems control-flow stack items take one word, in gforth they
857 :			currently take three (this may change in the future). Therefore it is a
858 :			really good idea to manipulate the control flow stack with
859 :			@code{cs-pick} and @code{cs-roll}, not with data stack manipulation
860 :			words.
861 :
862 :			Some standard control structure words are built from these words:
863 :
864 :	anton	1.3	doc-else
865 :			doc-while
866 :			doc-repeat
867 :	anton	1.2
868 :			Counted loop words constitute a separate group of words:
869 :
870 :	anton	1.3	doc-?do
871 :			doc-do
872 :			doc-for
873 :			doc-loop
874 :			doc-s+loop
875 :			doc-+loop
876 :			doc-next
877 :			doc-leave
878 :			doc-?leave
879 :			doc-unloop
880 :			doc-undo
881 :	anton	1.2
882 :			The standard does not allow using @code{cs-pick} and @code{cs-roll} on
883 :			@i{do-sys}. Our system allows it, but it's your job to ensure that for
884 :			every @code{?DO} etc. there is exactly one @code{UNLOOP} on any path
885 :	anton	1.3	through the definition (@code{LOOP} etc. compile an @code{UNLOOP} on the
886 :			fall-through path). Also, you have to ensure that all @code{LEAVE}s are
887 :			resolved (by using one of the loop-ending words or @code{UNDO}).
888 :	anton	1.2
889 :			Another group of control structure words are
890 :
891 :	anton	1.3	doc-case
892 :			doc-endcase
893 :			doc-of
894 :			doc-endof
895 :	anton	1.2
896 :			@i{case-sys} and @i{of-sys} cannot be processed using @code{cs-pick} and
897 :			@code{cs-roll}.
898 :
899 :	anton	1.3	@subsubsection Programming Style
900 :
901 :			In order to ensure readability we recommend that you do not create
902 :			arbitrary control structures directly, but define new control structure
903 :			words for the control structure you want and use these words in your
904 :			program.
905 :
906 :			E.g., instead of writing
907 :
908 :			@example
909 :			begin
910 :			...
911 :			if [ 1 cs-roll ]
912 :			...
913 :			again then
914 :			@end example
915 :
916 :			we recommend defining control structure words, e.g.,
917 :
918 :			@example
919 :			: while ( dest -- orig dest )
920 :			POSTPONE if
921 :			1 cs-roll ; immediate
922 :
923 :			: repeat ( orig dest -- )
924 :			POSTPONE again
925 :			POSTPONE then ; immediate
926 :			@end example
927 :
928 :			and then using these to create the control structure:
929 :
930 :			@example
931 :			begin
932 :			...
933 :			while
934 :			...
935 :			repeat
936 :			@end example
937 :
938 :			That's much easier to read, isn't it? Of course, @code{BEGIN} and
939 :			@code{WHILE} are predefined, so in this example it would not be
940 :			necessary to define them.
941 :
942 :	anton	1.4	@node Calls and returns, Exception Handling, Arbitrary control structures, Control Structures
943 :	anton	1.3	@subsection Calls and returns
944 :
945 :			A definition can be called simply be writing the name of the
946 :			definition. When the end of the definition is reached, it returns. An earlier return can be forced using
947 :
948 :			doc-exit
949 :
950 :			Don't forget to clean up the return stack and @code{UNLOOP} any
951 :			outstanding @code{?DO}...@code{LOOP}s before @code{EXIT}ing. The
952 :			primitive compiled by @code{EXIT} is
953 :
954 :			doc-;s
955 :
956 :	anton	1.4	@node Exception Handling, , Calls and returns, Control Structures
957 :	anton	1.3	@subsection Exception Handling
958 :
959 :			doc-catch
960 :			doc-throw
961 :
962 :	anton	1.4	@node Locals, Defining Words, Control Structures, Words
963 :	anton	1.1	@section Locals
964 :
965 :	anton	1.2	Local variables can make Forth programming more enjoyable and Forth
966 :			programs easier to read. Unfortunately, the locals of ANS Forth are
967 :			laden with restrictions. Therefore, we provide not only the ANS Forth
968 :			locals wordset, but also our own, more powerful locals wordset (we
969 :			implemented the ANS Forth locals wordset through our locals wordset).
970 :
971 :			@menu
972 :	anton	1.4	* gforth locals::
973 :			* ANS Forth locals::
974 :	anton	1.2	@end menu
975 :
976 :	anton	1.4	@node gforth locals, ANS Forth locals, Locals, Locals
977 :	anton	1.2	@subsection gforth locals
978 :
979 :			Locals can be defined with
980 :
981 :			@example
982 :			@{ local1 local2 ... -- comment @}
983 :			@end example
984 :			or
985 :			@example
986 :			@{ local1 local2 ... @}
987 :			@end example
988 :
989 :			E.g.,
990 :			@example
991 :			: max @{ n1 n2 -- n3 @}
992 :			n1 n2 > if
993 :			n1
994 :			else
995 :			n2
996 :			endif ;
997 :			@end example
998 :
999 :			The similarity of locals definitions with stack comments is intended. A
1000 :			locals definition often replaces the stack comment of a word. The order
1001 :			of the locals corresponds to the order in a stack comment and everything
1002 :			after the @code{--} is really a comment.
1003 :
1004 :			This similarity has one disadvantage: It is too easy to confuse locals
1005 :			declarations with stack comments, causing bugs and making them hard to
1006 :			find. However, this problem can be avoided by appropriate coding
1007 :			conventions: Do not use both notations in the same program. If you do,
1008 :			they should be distinguished using additional means, e.g. by position.
1009 :
1010 :			The name of the local may be preceded by a type specifier, e.g.,
1011 :			@code{F:} for a floating point value:
1012 :
1013 :			@example
1014 :			: CX* @{ F: Ar F: Ai F: Br F: Bi -- Cr Ci @}
1015 :			\ complex multiplication
1016 :			Ar Br f* Ai Bi f* f-
1017 :			Ar Bi f* Ai Br f* f+ ;
1018 :			@end example
1019 :
1020 :			GNU Forth currently supports cells (@code{W:}, @code{W^}), doubles
1021 :			(@code{D:}, @code{D^}), floats (@code{F:}, @code{F^}) and characters
1022 :			(@code{C:}, @code{C^}) in two flavours: a value-flavoured local (defined
1023 :			with @code{W:}, @code{D:} etc.) produces its value and can be changed
1024 :			with @code{TO}. A variable-flavoured local (defined with @code{W^} etc.)
1025 :			produces its address (which becomes invalid when the variable's scope is
1026 :			left). E.g., the standard word @code{emit} can be defined in therms of
1027 :			@code{type} like this:
1028 :
1029 :			@example
1030 :			: emit @{ C^ char* -- @}
1031 :			char* 1 type ;
1032 :			@end example
1033 :
1034 :			A local without type specifier is a @code{W:} local. Both flavours of
1035 :			locals are initialized with values from the data or FP stack.
1036 :
1037 :			Currently there is no way to define locals with user-defined data
1038 :			structures, but we are working on it.
1039 :
1040 :			GNU Forth allows defining locals everywhere in a colon definition. This poses the following questions:
1041 :
1042 :	anton	1.4	@menu
1043 :			* Where are locals visible by name?::
1044 :			* How long do locals live? ::
1045 :			* Programming Style::
1046 :			* Implementation::
1047 :			@end menu
1048 :
1049 :			@node Where are locals visible by name?, How long do locals live?, gforth locals, gforth locals
1050 :	anton	1.2	@subsubsection Where are locals visible by name?
1051 :
1052 :			Basically, the answer is that locals are visible where you would expect
1053 :			it in block-structured languages, and sometimes a little longer. If you
1054 :			want to restrict the scope of a local, enclose its definition in
1055 :			@code{SCOPE}...@code{ENDSCOPE}.
1056 :
1057 :			doc-scope
1058 :			doc-endscope
1059 :
1060 :			These words behave like control structure words, so you can use them
1061 :			with @code{CS-PICK} and @code{CS-ROLL} to restrict the scope in
1062 :			arbitrary ways.
1063 :
1064 :			If you want a more exact answer to the visibility question, here's the
1065 :			basic principle: A local is visible in all places that can only be
1066 :			reached through the definition of the local@footnote{In compiler
1067 :			construction terminology, all places dominated by the definition of the
1068 :			local.}. In other words, it is not visible in places that can be reached
1069 :			without going through the definition of the local. E.g., locals defined
1070 :			in @code{IF}...@code{ENDIF} are visible until the @code{ENDIF}, locals
1071 :			defined in @code{BEGIN}...@code{UNTIL} are visible after the
1072 :			@code{UNTIL} (until, e.g., a subsequent @code{ENDSCOPE}).
1073 :
1074 :			The reasoning behind this solution is: We want to have the locals
1075 :			visible as long as it is meaningful. The user can always make the
1076 :			visibility shorter by using explicit scoping. In a place that can
1077 :			only be reached through the definition of a local, the meaning of a
1078 :			local name is clear. In other places it is not: How is the local
1079 :			initialized at the control flow path that does not contain the
1080 :			definition? Which local is meant, if the same name is defined twice in
1081 :			two independent control flow paths?
1082 :
1083 :			This should be enough detail for nearly all users, so you can skip the
1084 :			rest of this section. If you relly must know all the gory details and
1085 :			options, read on.
1086 :
1087 :			In order to implement this rule, the compiler has to know which places
1088 :			are unreachable. It knows this automatically after @code{AHEAD},
1089 :			@code{AGAIN}, @code{EXIT} and @code{LEAVE}; in other cases (e.g., after
1090 :			most @code{THROW}s), you can use the word @code{UNREACHABLE} to tell the
1091 :			compiler that the control flow never reaches that place. If
1092 :			@code{UNREACHABLE} is not used where it could, the only consequence is
1093 :			that the visibility of some locals is more limited than the rule above
1094 :			says. If @code{UNREACHABLE} is used where it should not (i.e., if you
1095 :			lie to the compiler), buggy code will be produced.
1096 :
1097 :			Another problem with this rule is that at @code{BEGIN}, the compiler
1098 :	anton	1.3	does not know which locals will be visible on the incoming
1099 :			back-edge. All problems discussed in the following are due to this
1100 :			ignorance of the compiler (we discuss the problems using @code{BEGIN}
1101 :			loops as examples; the discussion also applies to @code{?DO} and other
1102 :	anton	1.2	loops). Perhaps the most insidious example is:
1103 :			@example
1104 :			AHEAD
1105 :			BEGIN
1106 :			x
1107 :			[ 1 CS-ROLL ] THEN
1108 :	anton	1.4	@{ x @}
1109 :	anton	1.2	...
1110 :			UNTIL
1111 :			@end example
1112 :
1113 :			This should be legal according to the visibility rule. The use of
1114 :			@code{x} can only be reached through the definition; but that appears
1115 :			textually below the use.
1116 :
1117 :			From this example it is clear that the visibility rules cannot be fully
1118 :			implemented without major headaches. Our implementation treats common
1119 :			cases as advertised and the exceptions are treated in a safe way: The
1120 :			compiler makes a reasonable guess about the locals visible after a
1121 :			@code{BEGIN}; if it is too pessimistic, the
1122 :			user will get a spurious error about the local not being defined; if the
1123 :			compiler is too optimistic, it will notice this later and issue a
1124 :			warning. In the case above the compiler would complain about @code{x}
1125 :			being undefined at its use. You can see from the obscure examples in
1126 :			this section that it takes quite unusual control structures to get the
1127 :			compiler into trouble, and even then it will often do fine.
1128 :
1129 :			If the @code{BEGIN} is reachable from above, the most optimistic guess
1130 :			is that all locals visible before the @code{BEGIN} will also be
1131 :			visible after the @code{BEGIN}. This guess is valid for all loops that
1132 :			are entered only through the @code{BEGIN}, in particular, for normal
1133 :			@code{BEGIN}...@code{WHILE}...@code{REPEAT} and
1134 :			@code{BEGIN}...@code{UNTIL} loops and it is implemented in our
1135 :			compiler. When the branch to the @code{BEGIN} is finally generated by
1136 :			@code{AGAIN} or @code{UNTIL}, the compiler checks the guess and
1137 :			warns the user if it was too optimisitic:
1138 :			@example
1139 :			IF
1140 :	anton	1.4	@{ x @}
1141 :	anton	1.2	BEGIN
1142 :			\ x ?
1143 :			[ 1 cs-roll ] THEN
1144 :			...
1145 :			UNTIL
1146 :			@end example
1147 :
1148 :			Here, @code{x} lives only until the @code{BEGIN}, but the compiler
1149 :			optimistically assumes that it lives until the @code{THEN}. It notices
1150 :			this difference when it compiles the @code{UNTIL} and issues a
1151 :			warning. The user can avoid the warning, and make sure that @code{x}
1152 :			is not used in the wrong area by using explicit scoping:
1153 :			@example
1154 :			IF
1155 :			SCOPE
1156 :	anton	1.4	@{ x @}
1157 :	anton	1.2	ENDSCOPE
1158 :			BEGIN
1159 :			[ 1 cs-roll ] THEN
1160 :			...
1161 :			UNTIL
1162 :			@end example
1163 :
1164 :			Since the guess is optimistic, there will be no spurious error messages
1165 :			about undefined locals.
1166 :
1167 :			If the @code{BEGIN} is not reachable from above (e.g., after
1168 :			@code{AHEAD} or @code{EXIT}), the compiler cannot even make an
1169 :			optimistic guess, as the locals visible after the @code{BEGIN} may be
1170 :			defined later. Therefore, the compiler assumes that no locals are
1171 :			visible after the @code{BEGIN}. However, the useer can use
1172 :			@code{ASSUME-LIVE} to make the compiler assume that the same locals are
1173 :			visible at the BEGIN as at the point where the item was created.
1174 :
1175 :			doc-assume-live
1176 :
1177 :			E.g.,
1178 :			@example
1179 :	anton	1.4	@{ x @}
1180 :	anton	1.2	AHEAD
1181 :			ASSUME-LIVE
1182 :			BEGIN
1183 :			x
1184 :			[ 1 CS-ROLL ] THEN
1185 :			...
1186 :			UNTIL
1187 :			@end example
1188 :
1189 :			Other cases where the locals are defined before the @code{BEGIN} can be
1190 :			handled by inserting an appropriate @code{CS-ROLL} before the
1191 :			@code{ASSUME-LIVE} (and changing the control-flow stack manipulation
1192 :			behind the @code{ASSUME-LIVE}).
1193 :
1194 :			Cases where locals are defined after the @code{BEGIN} (but should be
1195 :			visible immediately after the @code{BEGIN}) can only be handled by
1196 :			rearranging the loop. E.g., the ``most insidious'' example above can be
1197 :			arranged into:
1198 :			@example
1199 :			BEGIN
1200 :	anton	1.4	@{ x @}
1201 :	anton	1.2	... 0=
1202 :			WHILE
1203 :			x
1204 :			REPEAT
1205 :			@end example
1206 :
1207 :	anton	1.4	@node How long do locals live?, Programming Style, Where are locals visible by name?, gforth locals
1208 :	anton	1.2	@subsubsection How long do locals live?
1209 :
1210 :			The right answer for the lifetime question would be: A local lives at
1211 :			least as long as it can be accessed. For a value-flavoured local this
1212 :			means: until the end of its visibility. However, a variable-flavoured
1213 :			local could be accessed through its address far beyond its visibility
1214 :			scope. Ultimately, this would mean that such locals would have to be
1215 :			garbage collected. Since this entails un-Forth-like implementation
1216 :			complexities, I adopted the same cowardly solution as some other
1217 :			languages (e.g., C): The local lives only as long as it is visible;
1218 :			afterwards its address is invalid (and programs that access it
1219 :			afterwards are erroneous).
1220 :
1221 :	anton	1.4	@node Programming Style, Implementation, How long do locals live?, gforth locals
1222 :	anton	1.2	@subsubsection Programming Style
1223 :
1224 :			The freedom to define locals anywhere has the potential to change
1225 :			programming styles dramatically. In particular, the need to use the
1226 :			return stack for intermediate storage vanishes. Moreover, all stack
1227 :			manipulations (except @code{PICK}s and @code{ROLL}s with run-time
1228 :			determined arguments) can be eliminated: If the stack items are in the
1229 :			wrong order, just write a locals definition for all of them; then
1230 :			write the items in the order you want.
1231 :
1232 :			This seems a little far-fetched and eliminating stack manipulations is
1233 :	anton	1.4	unlikely to become a conscious programming objective. Still, the number
1234 :			of stack manipulations will be reduced dramatically if local variables
1235 :			are used liberally (e.g., compare @code{max} in @ref{gforth locals} with
1236 :			a traditional implementation of @code{max}).
1237 :	anton	1.2
1238 :			This shows one potential benefit of locals: making Forth programs more
1239 :			readable. Of course, this benefit will only be realized if the
1240 :			programmers continue to honour the principle of factoring instead of
1241 :			using the added latitude to make the words longer.
1242 :
1243 :			Using @code{TO} can and should be avoided. Without @code{TO},
1244 :			every value-flavoured local has only a single assignment and many
1245 :			advantages of functional languages apply to Forth. I.e., programs are
1246 :			easier to analyse, to optimize and to read: It is clear from the
1247 :			definition what the local stands for, it does not turn into something
1248 :			different later.
1249 :
1250 :			E.g., a definition using @code{TO} might look like this:
1251 :			@example
1252 :			: strcmp @{ addr1 u1 addr2 u2 -- n @}
1253 :			u1 u2 min 0
1254 :			?do
1255 :			addr1 c@ addr2 c@ - ?dup
1256 :			if
1257 :			unloop exit
1258 :			then
1259 :			addr1 char+ TO addr1
1260 :			addr2 char+ TO addr2
1261 :			loop
1262 :			u1 u2 - ;
1263 :			@end example
1264 :			Here, @code{TO} is used to update @code{addr1} and @code{addr2} at
1265 :			every loop iteration. @code{strcmp} is a typical example of the
1266 :			readability problems of using @code{TO}. When you start reading
1267 :			@code{strcmp}, you think that @code{addr1} refers to the start of the
1268 :			string. Only near the end of the loop you realize that it is something
1269 :			else.
1270 :
1271 :			This can be avoided by defining two locals at the start of the loop that
1272 :			are initialized with the right value for the current iteration.
1273 :			@example
1274 :			: strcmp @{ addr1 u1 addr2 u2 -- n @}
1275 :			addr1 addr2
1276 :			u1 u2 min 0
1277 :			?do @{ s1 s2 @}
1278 :			s1 c@ s2 c@ - ?dup
1279 :			if
1280 :			unloop exit
1281 :			then
1282 :			s1 char+ s2 char+
1283 :			loop
1284 :			2drop
1285 :			u1 u2 - ;
1286 :			@end example
1287 :			Here it is clear from the start that @code{s1} has a different value
1288 :			in every loop iteration.
1289 :
1290 :	anton	1.4	@node Implementation, , Programming Style, gforth locals
1291 :	anton	1.2	@subsubsection Implementation
1292 :
1293 :			GNU Forth uses an extra locals stack. The most compelling reason for
1294 :			this is that the return stack is not float-aligned; using an extra stack
1295 :			also eliminates the problems and restrictions of using the return stack
1296 :			as locals stack. Like the other stacks, the locals stack grows toward
1297 :			lower addresses. A few primitives allow an efficient implementation:
1298 :
1299 :			doc-@local#
1300 :			doc-f@local#
1301 :			doc-laddr#
1302 :			doc-lp+!#
1303 :			doc-lp!
1304 :			doc->l
1305 :			doc-f>l
1306 :
1307 :			In addition to these primitives, some specializations of these
1308 :			primitives for commonly occurring inline arguments are provided for
1309 :			efficiency reasons, e.g., @code{@@local0} as specialization of
1310 :			@code{@@local#} for the inline argument 0. The following compiling words
1311 :			compile the right specialized version, or the general version, as
1312 :			appropriate:
1313 :
1314 :			doc-compile-@@local
1315 :			doc-compile-f@@local
1316 :			doc-compile-lp+!
1317 :
1318 :			Combinations of conditional branches and @code{lp+!#} like
1319 :			@code{?branch-lp+!#} (the locals pointer is only changed if the branch
1320 :			is taken) are provided for efficiency and correctness in loops.
1321 :
1322 :			A special area in the dictionary space is reserved for keeping the
1323 :			local variable names. @code{@{} switches the dictionary pointer to this
1324 :			area and @code{@}} switches it back and generates the locals
1325 :			initializing code. @code{W:} etc.@ are normal defining words. This
1326 :			special area is cleared at the start of every colon definition.
1327 :
1328 :			A special feature of GNU Forths dictionary is used to implement the
1329 :			definition of locals without type specifiers: every wordlist (aka
1330 :			vocabulary) has its own methods for searching
1331 :	anton	1.4	etc. (@pxref{Wordlists}). For the present purpose we defined a wordlist
1332 :	anton	1.2	with a special search method: When it is searched for a word, it
1333 :			actually creates that word using @code{W:}. @code{@{} changes the search
1334 :			order to first search the wordlist containing @code{@}}, @code{W:} etc.,
1335 :			and then the wordlist for defining locals without type specifiers.
1336 :
1337 :			The lifetime rules support a stack discipline within a colon
1338 :			definition: The lifetime of a local is either nested with other locals
1339 :			lifetimes or it does not overlap them.
1340 :
1341 :			At @code{BEGIN}, @code{IF}, and @code{AHEAD} no code for locals stack
1342 :			pointer manipulation is generated. Between control structure words
1343 :			locals definitions can push locals onto the locals stack. @code{AGAIN}
1344 :			is the simplest of the other three control flow words. It has to
1345 :			restore the locals stack depth of the corresponding @code{BEGIN}
1346 :			before branching. The code looks like this:
1347 :			@format
1348 :			@code{lp+!#} current-locals-size @minus{} dest-locals-size
1349 :			@code{branch} <begin>
1350 :			@end format
1351 :
1352 :			@code{UNTIL} is a little more complicated: If it branches back, it
1353 :			must adjust the stack just like @code{AGAIN}. But if it falls through,
1354 :			the locals stack must not be changed. The compiler generates the
1355 :			following code:
1356 :			@format
1357 :			@code{?branch-lp+!#} <begin> current-locals-size @minus{} dest-locals-size
1358 :			@end format
1359 :			The locals stack pointer is only adjusted if the branch is taken.
1360 :
1361 :			@code{THEN} can produce somewhat inefficient code:
1362 :			@format
1363 :			@code{lp+!#} current-locals-size @minus{} orig-locals-size
1364 :			<orig target>:
1365 :			@code{lp+!#} orig-locals-size @minus{} new-locals-size
1366 :			@end format
1367 :			The second @code{lp+!#} adjusts the locals stack pointer from the
1368 :	anton	1.4	level at the @var{orig} point to the level after the @code{THEN}. The
1369 :	anton	1.2	first @code{lp+!#} adjusts the locals stack pointer from the current
1370 :			level to the level at the orig point, so the complete effect is an
1371 :			adjustment from the current level to the right level after the
1372 :			@code{THEN}.
1373 :
1374 :			In a conventional Forth implementation a dest control-flow stack entry
1375 :			is just the target address and an orig entry is just the address to be
1376 :			patched. Our locals implementation adds a wordlist to every orig or dest
1377 :			item. It is the list of locals visible (or assumed visible) at the point
1378 :			described by the entry. Our implementation also adds a tag to identify
1379 :			the kind of entry, in particular to differentiate between live and dead
1380 :			(reachable and unreachable) orig entries.
1381 :
1382 :			A few unusual operations have to be performed on locals wordlists:
1383 :
1384 :			doc-common-list
1385 :			doc-sub-list?
1386 :			doc-list-size
1387 :
1388 :			Several features of our locals wordlist implementation make these
1389 :			operations easy to implement: The locals wordlists are organised as
1390 :			linked lists; the tails of these lists are shared, if the lists
1391 :			contain some of the same locals; and the address of a name is greater
1392 :			than the address of the names behind it in the list.
1393 :
1394 :			Another important implementation detail is the variable
1395 :			@code{dead-code}. It is used by @code{BEGIN} and @code{THEN} to
1396 :			determine if they can be reached directly or only through the branch
1397 :			that they resolve. @code{dead-code} is set by @code{UNREACHABLE},
1398 :			@code{AHEAD}, @code{EXIT} etc., and cleared at the start of a colon
1399 :			definition, by @code{BEGIN} and usually by @code{THEN}.
1400 :
1401 :			Counted loops are similar to other loops in most respects, but
1402 :			@code{LEAVE} requires special attention: It performs basically the same
1403 :			service as @code{AHEAD}, but it does not create a control-flow stack
1404 :			entry. Therefore the information has to be stored elsewhere;
1405 :			traditionally, the information was stored in the target fields of the
1406 :			branches created by the @code{LEAVE}s, by organizing these fields into a
1407 :			linked list. Unfortunately, this clever trick does not provide enough
1408 :			space for storing our extended control flow information. Therefore, we
1409 :			introduce another stack, the leave stack. It contains the control-flow
1410 :			stack entries for all unresolved @code{LEAVE}s.
1411 :
1412 :			Local names are kept until the end of the colon definition, even if
1413 :			they are no longer visible in any control-flow path. In a few cases
1414 :			this may lead to increased space needs for the locals name area, but
1415 :			usually less than reclaiming this space would cost in code size.
1416 :
1417 :
1418 :	anton	1.4	@node ANS Forth locals, , gforth locals, Locals
1419 :	anton	1.2	@subsection ANS Forth locals
1420 :
1421 :			The ANS Forth locals wordset does not define a syntax for locals, but
1422 :			words that make it possible to define various syntaxes. One of the
1423 :			possible syntaxes is a subset of the syntax we used in the gforth locals
1424 :			wordset, i.e.:
1425 :
1426 :			@example
1427 :			@{ local1 local2 ... -- comment @}
1428 :			@end example
1429 :			or
1430 :			@example
1431 :			@{ local1 local2 ... @}
1432 :			@end example
1433 :
1434 :			The order of the locals corresponds to the order in a stack comment. The
1435 :			restrictions are:
1436 :	anton	1.1
1437 :	anton	1.2	@itemize @bullet
1438 :			@item
1439 :			Locals can only be cell-sized values (no type specifers are allowed).
1440 :			@item
1441 :			Locals can be defined only outside control structures.
1442 :			@item
1443 :			Locals can interfere with explicit usage of the return stack. For the
1444 :			exact (and long) rules, see the standard. If you don't use return stack
1445 :			accessing words in a definition using locals, you will we all right. The
1446 :			purpose of this rule is to make locals implementation on the return
1447 :			stack easier.
1448 :			@item
1449 :			The whole definition must be in one line.
1450 :			@end itemize
1451 :
1452 :			Locals defined in this way behave like @code{VALUE}s
1453 :	anton	1.4	(@xref{Values}). I.e., they are initialized from the stack. Using their
1454 :	anton	1.2	name produces their value. Their value can be changed using @code{TO}.
1455 :
1456 :			Since this syntax is supported by gforth directly, you need not do
1457 :			anything to use it. If you want to port a program using this syntax to
1458 :			another ANS Forth system, use @file{anslocal.fs} to implement the syntax
1459 :			on the other system.
1460 :
1461 :			Note that a syntax shown in the standard, section A.13 looks
1462 :			similar, but is quite different in having the order of locals
1463 :			reversed. Beware!
1464 :
1465 :			The ANS Forth locals wordset itself consists of the following word
1466 :
1467 :			doc-(local)
1468 :
1469 :			The ANS Forth locals extension wordset defines a syntax, but it is so
1470 :			awful that we strongly recommend not to use it. We have implemented this
1471 :			syntax to make porting to gforth easy, but do not document it here. The
1472 :			problem with this syntax is that the locals are defined in an order
1473 :			reversed with respect to the standard stack comment notation, making
1474 :			programs harder to read, and easier to misread and miswrite. The only
1475 :			merit of this syntax is that it is easy to implement using the ANS Forth
1476 :			locals wordset.
1477 :	anton	1.3
1478 :	anton	1.4	@node Defining Words, Wordlists, Locals, Words
1479 :			@section Defining Words
1480 :
1481 :			@node Values, , Defining Words, Defining Words
1482 :			@subsection Values
1483 :
1484 :			@node Wordlists, Files, Defining Words, Words
1485 :			@section Wordlists
1486 :
1487 :			@node Files, Blocks, Wordlists, Words
1488 :			@section Files
1489 :
1490 :			@node Blocks, Other I/O, Files, Words
1491 :			@section Blocks
1492 :
1493 :			@node Other I/O, Programming Tools, Blocks, Words
1494 :			@section Other I/O
1495 :
1496 :			@node Programming Tools, Threading Words, Other I/O, Words
1497 :			@section Programming Tools
1498 :
1499 :			@node
1500 :			@subsection Debugging
1501 :
1502 :			The simple debugging aids provided in @file{debugging.fs}
1503 :			are meant to support a different style of debugging than the
1504 :			tracing/stepping debuggers used in languages with long turn-around
1505 :			times.
1506 :
1507 :			A much better (faster) way in fast-compilig languages is to add
1508 :			printing code at well-selected places, let the program run, look at
1509 :			the output, see where things went wrong, add more printing code, etc.,
1510 :			until the bug is found.
1511 :
1512 :			The word @code{~~} is easy to insert. It just prints debugging
1513 :			information (by default the source location and the stack contents). It
1514 :			is also easy to remove (@kbd{C-x ~} in the Emacs Forth mode to
1515 :			query-replace them with nothing). The deferred words
1516 :			@code{printdebugdata} and @code{printdebugline} control the output of
1517 :			@code{~~}. The default source location output format works well with
1518 :			Emacs' compilation mode, so you can step through the program at the
1519 :			source level using @kbd{C-x `}.
1520 :
1521 :			Note that the default actions clobber the contents of the pictured
1522 :			numeric output string, so you should not use @code{~~}, e.g., between
1523 :			@code{<#} and @code{#>}.
1524 :
1525 :			doc-~~
1526 :			doc-printdebugdata
1527 :			doc-printdebugline
1528 :
1529 :			@node
1530 :			@subsection Assertions
1531 :
1532 :			@node Threading Words, , Programming Tools, Words
1533 :			@section Threading Words
1534 :
1535 :			These words provide access to code addresses and other threading stuff
1536 :			in gforth (and, possibly, other interpretive Forths). It more or less
1537 :			abstracts away the differences between direct and indirect threading
1538 :			(and, for direct threading, the machine dependences). However, at
1539 :			present this wordset is still inclomplete. It is also pretty low-level;
1540 :			some day it will hopefully be made unnecessary by an internals words set
1541 :			that abstracts implementation details away completely.
1542 :
1543 :			doc->code-address
1544 :			doc->does-code
1545 :			doc-code-address!
1546 :			doc-does-code!
1547 :			doc-does-handler!
1548 :			doc-/does-handler
1549 :
1550 :			@node ANS conformance, Model, Words, Top
1551 :			@chapter ANS conformance
1552 :
1553 :			@node Model, Emacs and GForth, ANS conformance, Top
1554 :			@chapter Model
1555 :
1556 :			@node Emacs and GForth, Internals, Model, Top
1557 :			@chapter Emacs and GForth
1558 :
1559 :			GForth comes with @file{gforth.el}, an improved version of
1560 :			@file{forth.el} by Goran Rydqvist (icluded in the TILE package). The
1561 :			improvements are a better (but still not perfect) handling of
1562 :			indentation. I have also added comment paragraph filling (@kbd{M-q}),
1563 :			commenting (@kbd{C-x \}) and uncommenting (@kbd{C-x \|}) regions and
1564 :			removing debugging tracers (@kbd{C-x ~}). I left the stuff I do not use
1565 :			alone, even though some of it only makes sense for TILE. To get a
1566 :			description of these features, enter Forth mode and type @kbd{C-h m}.
1567 :
1568 :			In addition, GForth supports Emacs quite well: The source code locations
1569 :			given in error messages, debugging output (from @code{~~}) and failed
1570 :			assertion messages are in the right format for Emacs' compilation mode
1571 :			(@pxref{Compilation, , Running Compilations under Emacs, emacs, Emacs
1572 :			Manual}) so the source location corresponding to an error or other
1573 :			message is only a few keystrokes away (@kbd{C-x `} for the next error,
1574 :			@kbd{C-c C-c} for the error under the cursor).
1575 :
1576 :			Also, if you @code{include} @file{etags.fs}, a new @file{TAGS} file
1577 :			(@pxref{Tags, , Tags Tables, emacs, Emacs Manual}) will be produced that
1578 :			contains the definitions of all words defined afterwards. You can then
1579 :			find the source for a word using @kbd{M-.}. Note that emacs can use
1580 :			several tags files at the same time (e.g., one for the gforth sources
1581 :			and one for your program).
1582 :
1583 :			To get all these benefits, add the following lines to your @file{.emacs}
1584 :			file:
1585 :
1586 :			@example
1587 :			(autoload 'forth-mode "gforth.el")
1588 :			(setq auto-mode-alist (cons '("\\.fs\\'" . forth-mode) auto-mode-alist))
1589 :			@end example
1590 :
1591 :			@node Internals, Bugs, Emacs and GForth, Top
1592 :	anton	1.3	@chapter Internals
1593 :
1594 :			Reading this section is not necessary for programming with gforth. It
1595 :			should be helpful for finding your way in the gforth sources.
1596 :
1597 :	anton	1.4	@menu
1598 :			* Portability::
1599 :			* Threading::
1600 :			* Primitives::
1601 :			* System Architecture::
1602 :			@end menu
1603 :
1604 :			@node Portability, Threading, Internals, Internals
1605 :	anton	1.3	@section Portability
1606 :
1607 :			One of the main goals of the effort is availability across a wide range
1608 :			of personal machines. fig-Forth, and, to a lesser extent, F83, achieved
1609 :			this goal by manually coding the engine in assembly language for several
1610 :			then-popular processors. This approach is very labor-intensive and the
1611 :			results are short-lived due to progress in computer architecture.
1612 :
1613 :			Others have avoided this problem by coding in C, e.g., Mitch Bradley
1614 :			(cforth), Mikael Patel (TILE) and Dirk Zoller (pfe). This approach is
1615 :			particularly popular for UNIX-based Forths due to the large variety of
1616 :			architectures of UNIX machines. Unfortunately an implementation in C
1617 :			does not mix well with the goals of efficiency and with using
1618 :			traditional techniques: Indirect or direct threading cannot be expressed
1619 :			in C, and switch threading, the fastest technique available in C, is
1620 :			significantly slower. Another problem with C is that it's very
1621 :			cumbersome to express double integer arithmetic.
1622 :
1623 :			Fortunately, there is a portable language that does not have these
1624 :			limitations: GNU C, the version of C processed by the GNU C compiler
1625 :			(@pxref{C Extensions, , Extensions to the C Language Family, gcc.info,
1626 :			GNU C Manual}). Its labels as values feature (@pxref{Labels as Values, ,
1627 :			Labels as Values, gcc.info, GNU C Manual}) makes direct and indirect
1628 :			threading possible, its @code{long long} type (@pxref{Long Long, ,
1629 :			Double-Word Integers, gcc.info, GNU C Manual}) corresponds to Forths
1630 :			double numbers. GNU C is available for free on all important (and many
1631 :			unimportant) UNIX machines, VMS, 80386s running MS-DOS, the Amiga, and
1632 :			the Atari ST, so a Forth written in GNU C can run on all these
1633 :			machines@footnote{Due to Apple's look-and-feel lawsuit it is not
1634 :			available on the Mac (@pxref{Boycott, , Protect Your Freedom--Fight
1635 :			``Look And Feel'', gcc.info, GNU C Manual}).}.
1636 :
1637 :			Writing in a portable language has the reputation of producing code that
1638 :			is slower than assembly. For our Forth engine we repeatedly looked at
1639 :			the code produced by the compiler and eliminated most compiler-induced
1640 :			inefficiencies by appropriate changes in the source-code.
1641 :
1642 :			However, register allocation cannot be portably influenced by the
1643 :			programmer, leading to some inefficiencies on register-starved
1644 :			machines. We use explicit register declarations (@pxref{Explicit Reg
1645 :			Vars, , Variables in Specified Registers, gcc.info, GNU C Manual}) to
1646 :			improve the speed on some machines. They are turned on by using the
1647 :			@code{gcc} switch @code{-DFORCE_REG}. Unfortunately, this feature not
1648 :			only depends on the machine, but also on the compiler version: On some
1649 :			machines some compiler versions produce incorrect code when certain
1650 :			explicit register declarations are used. So by default
1651 :			@code{-DFORCE_REG} is not used.
1652 :
1653 :	anton	1.4	@node Threading, Primitives, Portability, Internals
1654 :	anton	1.3	@section Threading
1655 :
1656 :			GNU C's labels as values extension (available since @code{gcc-2.0},
1657 :			@pxref{Labels as Values, , Labels as Values, gcc.info, GNU C Manual})
1658 :			makes it possible to take the address of @var{label} by writing
1659 :			@code{&&@var{label}}. This address can then be used in a statement like
1660 :			@code{goto @var{address}}. I.e., @code{goto &&x} is the same as
1661 :			@code{goto x}.
1662 :
1663 :			With this feature an indirect threaded NEXT looks like:
1664 :			@example
1665 :			cfa = *ip++;
1666 :			ca = *cfa;
1667 :			goto *ca;
1668 :			@end example
1669 :			For those unfamiliar with the names: @code{ip} is the Forth instruction
1670 :			pointer; the @code{cfa} (code-field address) corresponds to ANS Forths
1671 :			execution token and points to the code field of the next word to be
1672 :			executed; The @code{ca} (code address) fetched from there points to some
1673 :			executable code, e.g., a primitive or the colon definition handler
1674 :			@code{docol}.
1675 :
1676 :			Direct threading is even simpler:
1677 :			@example
1678 :			ca = *ip++;
1679 :			goto *ca;
1680 :			@end example
1681 :
1682 :			Of course we have packaged the whole thing neatly in macros called
1683 :			@code{NEXT} and @code{NEXT1} (the part of NEXT after fetching the cfa).
1684 :
1685 :	anton	1.4	@menu
1686 :			* Scheduling::
1687 :			* Direct or Indirect Threaded?::
1688 :			* DOES>::
1689 :			@end menu
1690 :
1691 :			@node Scheduling, Direct or Indirect Threaded?, Threading, Threading
1692 :	anton	1.3	@subsection Scheduling
1693 :
1694 :			There is a little complication: Pipelined and superscalar processors,
1695 :			i.e., RISC and some modern CISC machines can process independent
1696 :			instructions while waiting for the results of an instruction. The
1697 :			compiler usually reorders (schedules) the instructions in a way that
1698 :			achieves good usage of these delay slots. However, on our first tries
1699 :			the compiler did not do well on scheduling primitives. E.g., for
1700 :			@code{+} implemented as
1701 :			@example
1702 :			n=sp[0]+sp[1];
1703 :			sp++;
1704 :			sp[0]=n;
1705 :			NEXT;
1706 :			@end example
1707 :			the NEXT comes strictly after the other code, i.e., there is nearly no
1708 :			scheduling. After a little thought the problem becomes clear: The
1709 :			compiler cannot know that sp and ip point to different addresses (and
1710 :	anton	1.4	the version of @code{gcc} we used would not know it even if it was
1711 :			possible), so it could not move the load of the cfa above the store to
1712 :			the TOS. Indeed the pointers could be the same, if code on or very near
1713 :			the top of stack were executed. In the interest of speed we chose to
1714 :			forbid this probably unused ``feature'' and helped the compiler in
1715 :			scheduling: NEXT is divided into the loading part (@code{NEXT_P1}) and
1716 :			the goto part (@code{NEXT_P2}). @code{+} now looks like:
1717 :	anton	1.3	@example
1718 :			n=sp[0]+sp[1];
1719 :			sp++;
1720 :			NEXT_P1;
1721 :			sp[0]=n;
1722 :			NEXT_P2;
1723 :			@end example
1724 :	anton	1.4	This can be scheduled optimally by the compiler.
1725 :	anton	1.3
1726 :			This division can be turned off with the switch @code{-DCISC_NEXT}. This
1727 :			switch is on by default on machines that do not profit from scheduling
1728 :			(e.g., the 80386), in order to preserve registers.
1729 :
1730 :	anton	1.4	@node Direct or Indirect Threaded?, DOES>, Scheduling, Threading
1731 :	anton	1.3	@subsection Direct or Indirect Threaded?
1732 :
1733 :			Both! After packaging the nasty details in macro definitions we
1734 :			realized that we could switch between direct and indirect threading by
1735 :			simply setting a compilation flag (@code{-DDIRECT_THREADED}) and
1736 :			defining a few machine-specific macros for the direct-threading case.
1737 :			On the Forth level we also offer access words that hide the
1738 :			differences between the threading methods (@pxref{Threading Words}).
1739 :
1740 :			Indirect threading is implemented completely
1741 :			machine-independently. Direct threading needs routines for creating
1742 :			jumps to the executable code (e.g. to docol or dodoes). These routines
1743 :			are inherently machine-dependent, but they do not amount to many source
1744 :			lines. I.e., even porting direct threading to a new machine is a small
1745 :			effort.
1746 :
1747 :	anton	1.4	@node DOES>, , Direct or Indirect Threaded?, Threading
1748 :	anton	1.3	@subsection DOES>
1749 :			One of the most complex parts of a Forth engine is @code{dodoes}, i.e.,
1750 :			the chunk of code executed by every word defined by a
1751 :			@code{CREATE}...@code{DOES>} pair. The main problem here is: How to find
1752 :			the Forth code to be executed, i.e. the code after the @code{DOES>} (the
1753 :			DOES-code)? There are two solutions:
1754 :
1755 :			In fig-Forth the code field points directly to the dodoes and the
1756 :			DOES-code address is stored in the cell after the code address
1757 :			(i.e. at cfa cell+). It may seem that this solution is illegal in the
1758 :			Forth-79 and all later standards, because in fig-Forth this address
1759 :			lies in the body (which is illegal in these standards). However, by
1760 :			making the code field larger for all words this solution becomes legal
1761 :			again. We use this approach for the indirect threaded version. Leaving
1762 :			a cell unused in most words is a bit wasteful, but on the machines we
1763 :			are targetting this is hardly a problem. The other reason for having a
1764 :			code field size of two cells is to avoid having different image files
1765 :	anton	1.4	for direct and indirect threaded systems (@pxref{System Architecture}).
1766 :	anton	1.3
1767 :			The other approach is that the code field points or jumps to the cell
1768 :			after @code{DOES}. In this variant there is a jump to @code{dodoes} at
1769 :			this address. @code{dodoes} can then get the DOES-code address by
1770 :			computing the code address, i.e., the address of the jump to dodoes,
1771 :			and add the length of that jump field. A variant of this is to have a
1772 :			call to @code{dodoes} after the @code{DOES>}; then the return address
1773 :			(which can be found in the return register on RISCs) is the DOES-code
1774 :			address. Since the two cells available in the code field are usually
1775 :			used up by the jump to the code address in direct threading, we use
1776 :			this approach for direct threading. We did not want to add another
1777 :			cell to the code field.
1778 :
1779 :	anton	1.4	@node Primitives, System Architecture, Threading, Internals
1780 :	anton	1.3	@section Primitives
1781 :
1782 :	anton	1.4	@menu
1783 :			* Automatic Generation::
1784 :			* TOS Optimization::
1785 :			* Produced code::
1786 :			@end menu
1787 :
1788 :			@node Automatic Generation, TOS Optimization, Primitives, Primitives
1789 :	anton	1.3	@subsection Automatic Generation
1790 :
1791 :			Since the primitives are implemented in a portable language, there is no
1792 :			longer any need to minimize the number of primitives. On the contrary,
1793 :			having many primitives is an advantage: speed. In order to reduce the
1794 :			number of errors in primitives and to make programming them easier, we
1795 :			provide a tool, the primitive generator (@file{prims2x.fs}), that
1796 :			automatically generates most (and sometimes all) of the C code for a
1797 :			primitive from the stack effect notation. The source for a primitive
1798 :			has the following form:
1799 :
1800 :			@format
1801 :			@var{Forth-name} @var{stack-effect} @var{category} [@var{pronounc.}]
1802 :			[@code{""}@var{glossary entry}@code{""}]
1803 :			@var{C code}
1804 :			[@code{:}
1805 :			@var{Forth code}]
1806 :			@end format
1807 :
1808 :			The items in brackets are optional. The category and glossary fields
1809 :			are there for generating the documentation, the Forth code is there
1810 :			for manual implementations on machines without GNU C. E.g., the source
1811 :			for the primitive @code{+} is:
1812 :			@example
1813 :			+ n1 n2 -- n core plus
1814 :			n = n1+n2;
1815 :			@end example
1816 :
1817 :			This looks like a specification, but in fact @code{n = n1+n2} is C
1818 :			code. Our primitive generation tool extracts a lot of information from
1819 :			the stack effect notations@footnote{We use a one-stack notation, even
1820 :			though we have separate data and floating-point stacks; The separate
1821 :			notation can be generated easily from the unified notation.}: The number
1822 :			of items popped from and pushed on the stack, their type, and by what
1823 :			name they are referred to in the C code. It then generates a C code
1824 :			prelude and postlude for each primitive. The final C code for @code{+}
1825 :			looks like this:
1826 :
1827 :			@example
1828 :			I_plus: /* + ( n1 n2 -- n ) / / label, stack effect */
1829 :			/* / / documentation */
1830 :	anton	1.4	@{
1831 :	anton	1.3	DEF_CA /* definition of variable ca (indirect threading) */
1832 :			Cell n1; /* definitions of variables */
1833 :			Cell n2;
1834 :			Cell n;
1835 :			n1 = (Cell) sp[1]; /* input */
1836 :			n2 = (Cell) TOS;
1837 :			sp += 1; /* stack adjustment */
1838 :			NAME("+") /* debugging output (with -DDEBUG) */
1839 :	anton	1.4	@{
1840 :	anton	1.3	n = n1+n2; /* C code taken from the source */
1841 :	anton	1.4	@}
1842 :	anton	1.3	NEXT_P1; /* NEXT part 1 */
1843 :			TOS = (Cell)n; /* output */
1844 :			NEXT_P2; /* NEXT part 2 */
1845 :	anton	1.4	@}
1846 :	anton	1.3	@end example
1847 :
1848 :			This looks long and inefficient, but the GNU C compiler optimizes quite
1849 :			well and produces optimal code for @code{+} on, e.g., the R3000 and the
1850 :			HP RISC machines: Defining the @code{n}s does not produce any code, and
1851 :			using them as intermediate storage also adds no cost.
1852 :
1853 :			There are also other optimizations, that are not illustrated by this
1854 :			example: Assignments between simple variables are usually for free (copy
1855 :			propagation). If one of the stack items is not used by the primitive
1856 :			(e.g. in @code{drop}), the compiler eliminates the load from the stack
1857 :			(dead code elimination). On the other hand, there are some things that
1858 :			the compiler does not do, therefore they are performed by
1859 :			@file{prims2x.fs}: The compiler does not optimize code away that stores
1860 :			a stack item to the place where it just came from (e.g., @code{over}).
1861 :
1862 :			While programming a primitive is usually easy, there are a few cases
1863 :			where the programmer has to take the actions of the generator into
1864 :			account, most notably @code{?dup}, but also words that do not (always)
1865 :			fall through to NEXT.
1866 :
1867 :	anton	1.4	@node TOS Optimization, Produced code, Automatic Generation, Primitives
1868 :	anton	1.3	@subsection TOS Optimization
1869 :
1870 :			An important optimization for stack machine emulators, e.g., Forth
1871 :			engines, is keeping one or more of the top stack items in
1872 :	anton	1.4	registers. If a word has the stack effect @var{in1}...@var{inx} @code{--}
1873 :			@var{out1}...@var{outy}, keeping the top @var{n} items in registers
1874 :	anton	1.3	@itemize
1875 :			@item
1876 :			is better than keeping @var{n-1} items, if @var{x>=n} and @var{y>=n},
1877 :			due to fewer loads from and stores to the stack.
1878 :			@item is slower than keeping @var{n-1} items, if @var{x<>y} and @var{x<n} and
1879 :			@var{y<n}, due to additional moves between registers.
1880 :			@end itemize
1881 :
1882 :			In particular, keeping one item in a register is never a disadvantage,
1883 :			if there are enough registers. Keeping two items in registers is a
1884 :			disadvantage for frequent words like @code{?branch}, constants,
1885 :			variables, literals and @code{i}. Therefore our generator only produces
1886 :			code that keeps zero or one items in registers. The generated C code
1887 :			covers both cases; the selection between these alternatives is made at
1888 :			C-compile time using the switch @code{-DUSE_TOS}. @code{TOS} in the C
1889 :			code for @code{+} is just a simple variable name in the one-item case,
1890 :			otherwise it is a macro that expands into @code{sp[0]}. Note that the
1891 :			GNU C compiler tries to keep simple variables like @code{TOS} in
1892 :			registers, and it usually succeeds, if there are enough registers.
1893 :
1894 :			The primitive generator performs the TOS optimization for the
1895 :			floating-point stack, too (@code{-DUSE_FTOS}). For floating-point
1896 :			operations the benefit of this optimization is even larger:
1897 :			floating-point operations take quite long on most processors, but can be
1898 :			performed in parallel with other operations as long as their results are
1899 :			not used. If the FP-TOS is kept in a register, this works. If
1900 :			it is kept on the stack, i.e., in memory, the store into memory has to
1901 :			wait for the result of the floating-point operation, lengthening the
1902 :			execution time of the primitive considerably.
1903 :
1904 :			The TOS optimization makes the automatic generation of primitives a
1905 :			bit more complicated. Just replacing all occurrences of @code{sp[0]} by
1906 :			@code{TOS} is not sufficient. There are some special cases to
1907 :			consider:
1908 :			@itemize
1909 :			@item In the case of @code{dup ( w -- w w )} the generator must not
1910 :			eliminate the store to the original location of the item on the stack,
1911 :			if the TOS optimization is turned on.
1912 :	anton	1.4	@item Primitives with stack effects of the form @code{--}
1913 :			@var{out1}...@var{outy} must store the TOS to the stack at the start.
1914 :			Likewise, primitives with the stack effect @var{in1}...@var{inx} @code{--}
1915 :	anton	1.3	must load the TOS from the stack at the end. But for the null stack
1916 :			effect @code{--} no stores or loads should be generated.
1917 :			@end itemize
1918 :
1919 :	anton	1.4	@node Produced code, , TOS Optimization, Primitives
1920 :	anton	1.3	@subsection Produced code
1921 :
1922 :			To see what assembly code is produced for the primitives on your machine
1923 :			with your compiler and your flag settings, type @code{make engine.s} and
1924 :	anton	1.4	look at the resulting file @file{engine.s}.
1925 :	anton	1.3
1926 :	anton	1.4	@node System Architecture, , Primitives, Internals
1927 :	anton	1.3	@section System Architecture
1928 :
1929 :			Our Forth system consists not only of primitives, but also of
1930 :			definitions written in Forth. Since the Forth compiler itself belongs
1931 :			to those definitions, it is not possible to start the system with the
1932 :			primitives and the Forth source alone. Therefore we provide the Forth
1933 :			code as an image file in nearly executable form. At the start of the
1934 :			system a C routine loads the image file into memory, sets up the
1935 :			memory (stacks etc.) according to information in the image file, and
1936 :			starts executing Forth code.
1937 :
1938 :			The image file format is a compromise between the goals of making it
1939 :			easy to generate image files and making them portable. The easiest way
1940 :			to generate an image file is to just generate a memory dump. However,
1941 :			this kind of image file cannot be used on a different machine, or on
1942 :			the next version of the engine on the same machine, it even might not
1943 :			work with the same engine compiled by a different version of the C
1944 :			compiler. We would like to have as few versions of the image file as
1945 :			possible, because we do not want to distribute many versions of the
1946 :			same image file, and to make it easy for the users to use their image
1947 :			files on many machines. We currently need to create a different image
1948 :			file for machines with different cell sizes and different byte order
1949 :			(little- or big-endian)@footnote{We consider adding information to the
1950 :			image file that enables the loader to change the byte order.}.
1951 :
1952 :			Forth code that is going to end up in a portable image file has to
1953 :	anton	1.4	comply to some restrictions: addresses have to be stored in memory with
1954 :			special words (@code{A!}, @code{A,}, etc.) in order to make the code
1955 :			relocatable. Cells, floats, etc., have to be stored at the natural
1956 :			alignment boundaries@footnote{E.g., store floats (8 bytes) at an address
1957 :			dividable by~8. This happens automatically in our system when you use
1958 :			the ANS Forth alignment words.}, in order to avoid alignment faults on
1959 :			machines with stricter alignment. The image file is produced by a
1960 :			metacompiler (@file{cross.fs}).
1961 :	anton	1.3
1962 :			So, unlike the image file of Mitch Bradleys @code{cforth}, our image
1963 :			file is not directly executable, but has to undergo some manipulations
1964 :			during loading. Address relocation is performed at image load-time, not
1965 :			at run-time. The loader also has to replace tokens standing for
1966 :			primitive calls with the appropriate code-field addresses (or code
1967 :			addresses in the case of direct threading).
1968 :	anton	1.4
1969 :			@node Bugs, Pedigree, Internals, Top
1970 :			@chapter Bugs
1971 :
1972 :			@node Pedigree, Word Index, Bugs, Top
1973 :			@chapter Pedigree
1974 :
1975 :			@node Word Index, Node Index, Pedigree, Top
1976 :			@chapter Word Index
1977 :
1978 :			@node Node Index, , Word Index, Top
1979 :			@chapter Node Index
1980 :	anton	1.1
1981 :			@contents
1982 :			@bye
1983 :

CVS Admin

gforth: gforth/Attic/gforth.ds

ViewCVS and CVS Help