File:  [gforth] / gforth / Attic / gforth.ds
Revision 1.3: download - view: text, annotated - select for diffs
Wed Nov 23 16:54:39 1994 UTC (29 years, 4 months ago) by anton
Branches: MAIN
CVS tags: HEAD
added package target to Makefile.in
some documentation changes

\input texinfo   @c -*-texinfo-*-
@comment The source is gforth.ds, from which gforth.texi is generated
@comment %**start of header (This is for running Texinfo on a region.)
@setfilename gforth-info
@settitle GNU Forth Manual
@setchapternewpage odd
@comment %**end of header (This is for running Texinfo on a region.)

@ifinfo
This file documents GNU Forth 0.0

Copyright @copyright{} 1994 GNU Forth Development Group

     Permission is granted to make and distribute verbatim copies of
     this manual provided the copyright notice and this permission notice
     are preserved on all copies.
     
     @ignore
     Permission is granted to process this file through TeX and print the
     results, provided the printed document carries a copying permission
     notice identical to this one except for the removal of this paragraph
     (this paragraph not being relevant to the printed manual).
     
     @end ignore
     Permission is granted to copy and distribute modified versions of this
     manual under the conditions for verbatim copying, provided also that the
     sections entitled "Distribution" and "General Public License" are
     included exactly as in the original, and provided that the entire
     resulting derived work is distributed under the terms of a permission
     notice identical to this one.
     
     Permission is granted to copy and distribute translations of this manual
     into another language, under the above conditions for modified versions,
     except that the sections entitled "Distribution" and "General Public
     License" may be included in a translation approved by the author instead
     of in the original English.
@end ifinfo

@titlepage
@sp 10
@center @titlefont{GNU Forth Manual}
@sp 2
@center for version 0.0
@sp 2
@center Anton Ertl

@comment  The following two commands start the copyright page.
@page
@vskip 0pt plus 1filll
Copyright @copyright{} 1994 GNU Forth Development Group

@comment !! Published by ... or You can get a copy of this manual ...

     Permission is granted to make and distribute verbatim copies of
     this manual provided the copyright notice and this permission notice
     are preserved on all copies.
     
     Permission is granted to copy and distribute modified versions of this
     manual under the conditions for verbatim copying, provided also that the
     sections entitled "Distribution" and "General Public License" are
     included exactly as in the original, and provided that the entire
     resulting derived work is distributed under the terms of a permission
     notice identical to this one.
     
     Permission is granted to copy and distribute translations of this manual
     into another language, under the above conditions for modified versions,
     except that the sections entitled "Distribution" and "General Public
     License" may be included in a translation approved by the author instead
     of in the original English.
@end titlepage


@node Top, License, (dir), (dir)
@ifinfo
GNU Forth is a free implementation of ANS Forth available on many
personal machines. This manual corresponds to version 0.0.
@end ifinfo

@menu
* License::             
* Goals::               About the GNU Forth Project
* Other Books::         Things you might want to read
* Invocation::          Starting GNU Forth
* Words::               Forth words available in GNU Forth
* ANS conformance::     Implementation-defined options etc.
* Model::               The abstract machine of GNU Forth
* Emacs and GForth::    The GForth Mode
* Internals::           Implementation details
* Bugs::                How to report them
* Pedigree::            Ancestors of GNU Forth
* Word Index::          An item for each Forth word
* Node Index::          An item for each node
@end menu

@node License, Goals, Top, Top
@unnumbered License
!! Insert GPL here

@iftex
@unnumbered Preface
This manual documents GNU Forth. The reader is expected to know
Forth. This manual is primarily a reference manual. @xref{Other Books}
for introductory material.
@end iftex

@node    Goals, Other Books, License, Top
@comment node-name,     next,           previous, up
@chapter Goals of GNU Forth
@cindex Goals
The goal of the GNU Forth Project is to develop a standard model for
ANSI Forth. This can be split into several subgoals:

@itemize @bullet
@item
GNU Forth should conform to the ANSI Forth standard.
@item
It should be a model, i.e. it should define all the
implementation-dependent things.
@item
It should become standard, i.e. widely accepted and used. This goal
is the most difficult one.
@end itemize

To achieve these goals GNU Forth should be
@itemize @bullet
@item
Similar to previous models (fig-Forth, F83)
@item
Powerful. It should provide for all the things that are considered
necessary today and even some that are not yet considered necessary.
@item
Efficient. It should not get the reputation of being exceptionally
slow.
@item
Free.
@item
Available on many machines/easy to port.
@end itemize

Have we achieved these goals? GNU Forth conforms to the ANS Forth
standard; it may be considered a model, but we have not yet documented
which parts of the model are stable and which parts we are likely to
change; it certainly has not yet become a de facto standard. It has some
similarities and some differences to previous models; It has some
powerful features, but not yet everything that we envisioned; on RISCs
it is as fast as interpreters programmed in assembly, on
register-starved machines it is not so fast, but still faster than any
other C-based interpretive implementation; it is free and available on
many machines.

@node Other Books, Invocation, Goals, Top
@chapter Other books on ANS Forth

As the standard is relatively new, there are not many books out yet. It
is not recommended to learn Forth by using GNU Forth and a book that is
not written for ANS Forth, as you will not know your mistakes from the
deviations of the book.

There is, of course, the standard, the definite reference if you want to
write ANS Forth programs. It will be available in printed form from
Global Engineering Documents !! somtime in spring or summer 1994. If you
are lucky, you can still get dpANS6 (the draft that was approved as
standard) by aftp from ftp.uu.net:/vendor/minerva/x3j14.

@cite{Forth: The new model} by Jack Woehr (!! Publisher) is an
introductory book based on a draft version of the standard. It does not
cover the whole standard. It also contains interesting background
information (Jack Woehr was in the ANS Forth Technical Committe). It is
not appropriate for complete newbies, but programmers experienced in
other languages should find it ok.

@node Invocation, Words, Other Books, Top
@chapter Invocation

You will usually just say @code{gforth}. In many other cases the default
GNU Forth image will be invoked like this:

@example
gforth [files] [-e forth-code]
@end example

executing the contents of the files and the Forth code in the order they
are given.

In general, the command line looks like this:

@example
gforth [initialization options] [image-specific options]
@end example

The initialization options must come before the rest of the command
line. They are:

@table @code
@item --image-file @var{file}
Loads the Forth image @var{file} instead of the default
@file{gforth.fi}.

@item --path @var{path}
Uses @var{path} for searching the image file and Forth source code
files instead of the default in the environment variable
@code{GFORTHPATH} or the path specified at installation time (typically
@file{/usr/local/lib/gforth:.}). A path is given as a @code{:}-separated
list.

@item --dictionary-size @var{size}
@item -m @var{size}
Allocate @var{size} space for the Forth dictionary space instead of
using the default specified in the image (typically 256K). The
@var{size} specification consists of an integer and a unit (e.g.,
@code{4M}). The unit can be one of @code{b} (bytes), @code{e} (element
size, in this case Cells), @code{k} (kilobytes), and @code{M}
(Megabytes). If no unit is specified, @code{e} is used.

@item --data-stack-size @var{size}
@item -d @var{size}
Allocate @var{size} space for the data stack instead of using the
default specified in the image (typically 16K).

@item --return-stack-size @var{size}
@item -r @var{size}
Allocate @var{size} space for the return stack instead of using the
default specified in the image (typically 16K).

@item --fp-stack-size @var{size}
@item -f @var{size}
Allocate @var{size} space for the floating point stack instead of
using the default specified in the image (typically 16K). In this case
the unit specifier @code{e} refers to floating point numbers.

@item --locals-stack-size @var{size}
@item -l @var{size}
Allocate @var{size} space for the locals stack instead of using the
default specified in the image (typically 16K).

@end table

As explained above, the image-specific command-line arguments for the
default image @file{gforth.fi} consist of a sequence of filenames and
@code{-e @var{forth-code}} options that are interpreted in the seqence
in which they are given. The @code{-e @var{forth-code}} or
@code{--evaluate @var{forth-code}} option evaluates the forth
code. This option takes only one argument; if you want to evaluate more
Forth words, you have to quote them or use several @code{-e}s. To exit
after processing the command line (instead of entering interactive mode)
append @code{-e bye} to the command line.

Not yet implemented:
On startup the system first executes the system initialization file
(unless the option @code{--no-init-file} is given; note that the system
resulting from using this option may not be ANS Forth conformant). Then
the user initialization file @file{.gforth.fs} is executed, unless the
option @code{--no-rc} is given; this file is first searched in @file{.},
then in @file{~}, then in the normal path (see above).

@node Words,  , Invocation, Top
@chapter Forth Words

@menu
* Notation::
* Arithmetic::
* Stack Manipulation::
* Memory access::
* Control Structures::
* Local Variables::
* Defining Words::
* Vocabularies::
* Files::
* Blocks::
* Other I/O::
* Programming Tools::
@end menu

@node Notation, Arithmetic, Words, Words
@section Notation

The Forth words are described in this section in the glossary notation
that has become a de-facto standard for Forth texts, i.e.

@quotation
@var{word}     @var{Stack effect}   @var{wordset}   @var{pronunciation}
@var{Description}
@end quotation

@table @var
@item word
The name of the word. BTW, GNU Forth is case insensitive, so you can
type the words in in lower case.

@item Stack effect
The stack effect is written in the notation @code{@var{before} --
@var{after}}, where @var{before} and @var{after} describe the top of
stack entries before and after the execution of the word. The rest of
the stack is not touched by the word. The top of stack is rightmost,
i.e., a stack sequence is written as it is typed in. Note that GNU Forth
uses a separate floating point stack, but a unified stack
notation. Also, return stack effects are not shown in @var{stack
effect}, but in @var{Description}. The name of a stack item describes
the type and/or the function of the item. See below for a discussion of
the types.

@item pronunciation
How the word is pronounced

@item wordset
The ANS Forth standard is divided into several wordsets. A standard
system need not support all of them. So, the fewer wordsets your program
uses the more portable it will be in theory. However, we suspect that
most ANS Forth systems on personal machines will feature all
wordsets. Words that are not defined in the ANS standard have
@code{gforth} as wordset.

@item Description
A description of the behaviour of the word.
@end table

The name of a stack item corresponds in the following way with its type:

@table @code
@item name starts with
Type
@item f
Bool, i.e. @code{false} or @code{true}.
@item c
Char
@item w
Cell, can contain an integer or an address
@item n
signed integer
@item u
unsigned integer
@item d
double sized signed integer
@item ud
double sized unsigned integer
@item r
Float
@item a_
Cell-aligned address
@item c_
Char-aligned address (note that a Char is two bytes in Windows NT)
@item f_
Float-aligned address
@item df_
Address aligned for IEEE double precision float
@item sf_
Address aligned for IEEE single precision float
@item xt
Execution token, same size as Cell
@item wid
Wordlist ID, same size as Cell
@item f83name
Pointer to a name structure
@end table

@node Arithmetic,  , Notation, Words
@section Arithmetic
Forth arithmetic is not checked, i.e., you will not hear about integer
overflow on addition or multiplication, you may hear about division by
zero if you are lucky. The operator is written after the operands, but
the operands are still in the original order. I.e., the infix @code{2-1}
corresponds to @code{2 1 -}. Forth offers a variety of division
operators. If you perform division with potentially negative operands,
you do not want to use @code{/} or @code{/mod} with its undefined
behaviour, but rather @code{fm/mod} or @code{sm/mod} (probably the
former).

@subsection Single precision
doc-+
doc--
doc-*
doc-/
doc-mod
doc-/mod
doc-negate
doc-abs
doc-min
doc-max

@subsection Bitwise operations
doc-and
doc-or
doc-xor
doc-invert
doc-2*
doc-2/

@subsection Mixed precision
doc-m+
doc-*/
doc-*/mod
doc-m*
doc-um*
doc-m*/
doc-um/mod
doc-fm/mod
doc-sm/rem

@subsection Double precision
doc-d+
doc-d-
doc-dnegate
doc-dabs
doc-dmin
doc-dmax

@node Stack Manipulation,,,
@section Stack Manipulation

gforth has a data stack (aka parameter stack) for characters, cells,
addresses, and double cells, a floating point stack for floating point
numbers, a return stack for storing the return addresses of colon
definitions and other data, and a locals stack for storing local
variables. Note that while every sane Forth has a separate floating
point stack, this is not strictly required; an ANS Forth system could
theoretically keep floating point numbers on the data stack. As an
additional difficulty, you don't know how many cells a floating point
number takes. It is reportedly possible to write words in a way that
they work also for a unified stack model, but we do not recommend trying
it. Also, a Forth system is allowed to keep the local variables on the
return stack. This is reasonable, as local variables usually eliminate
the need to use the return stack explicitly. So, if you want to produce
a standard complying program and if you are using local variables in a
word, forget about return stack manipulations in that word (see the
standard document for the exact rules).

@subsection Data stack
doc-drop
doc-nip
doc-dup
doc-over
doc-tuck
doc-swap
doc-rot
doc--rot
doc-?dup
doc-pick
doc-roll
doc-2drop
doc-2nip
doc-2dup
doc-2over
doc-2tuck
doc-2swap
doc-2rot

@subsection Floating point stack
doc-fdrop
doc-fnip
doc-fdup
doc-fover
doc-ftuck
doc-fswap
doc-frot

@subsection Return stack
doc->r
doc-r>
doc-r@
doc-rdrop
doc-2>r
doc-2r>
doc-2r@
doc-2rdrop

@subsection Locals stack

@subsection Stack pointer manipulation
doc-sp@
doc-sp!
doc-fp@
doc-fp!
doc-rp@
doc-rp!
doc-lp@
doc-lp!

@node Memory access
@section Memory access

@subsection Stack-Memory transfers

doc-@
doc-!
doc-+!
doc-c@
doc-c!
doc-2@
doc-2!
doc-f@
doc-f!
doc-sf@
doc-sf!
doc-df@
doc-df!

@subsection Address arithmetic

ANS Forth does not specify the sizes of the data types. Instead, it
offers a number of words for computing sizes and doing address
arithmetic. Basically, address arithmetic is performed in terms of
address units (aus); on most systems the address unit is one byte. Note
that a character may have more than one au, so @code{chars} is no noop
(on systems where it is a noop, it compiles to nothing).

ANS Forth also defines words for aligning addresses for specific
addresses. Many computers require that accesses to specific data types
must only occur at specific addresses; e.g., that cells may only be
accessed at addresses divisible by 4. Even if a machine allows unaligned
accesses, it can usually perform aligned accesses faster. 

For the performance-concious: alignment operations are usually only
necessary during the definition of a data structure, not during the
(more frequent) accesses to it.

ANS Forth defines no words for character-aligning addresses. This is not
an oversight, but reflects the fact that addresses that are not
char-aligned have no use in the standard and therefore will not be
created.

The standard guarantees that addresses returned by @code{CREATE}d words
are cell-aligned; in addition, gforth guarantees that these addresses
are aligned for all purposes.

doc-chars
doc-char+
doc-cells
doc-cell+
doc-align
doc-aligned
doc-floats
doc-float+
doc-falign
doc-faligned
doc-sfloats
doc-sfloat+
doc-sfalign
doc-sfaligned
doc-dfloats
doc-dfloat+
doc-dfalign
doc-dfaligned
doc-address-unit-bits

@subsection Memory block access

doc-move
doc-erase

While the previous words work on address units, the rest works on
characters.

doc-cmove
doc-cmove>
doc-fill
doc-blank

@node Control Structures
@section Control Structures

Control structures in Forth cannot be used in interpret state, only in
compile state, i.e., in a colon definition. We do not like this
limitation, but have not seen a satisfying way around it yet, although
many schemes have been proposed.

@subsection Selection

@example
@var{flag}
IF
  @var{code}
ENDIF
@end example
or
@example
@var{flag}
IF
  @var{code1}
ELSE
  @var{code2}
ENDIF
@end example

You can use @code{THEN} instead of {ENDIF}. Indeed, @code{THEN} is
standard, and @code{ENDIF} is not, although it is quite popular. We
recommend using @code{ENDIF}, because it is less confusing for people
who also know other languages (and is not prone to reinforcing negative
prejudices against Forth in these people). Adding @code{ENDIF} to a
system that only supplies @code{THEN} is simple:
@example
: endif   POSTPONE then ; immediate
@end example

[According to @cite{Webster's New Encyclopedic Dictionary}, @dfn{then
(adv.)}  has the following meanings:
@quotation
... 2b: following next after in order ... 3d: as a necessary consequence
(if you were there, then you saw them).
@end quotation
Forth's @code{THEN} has the meaning 2b, whereas @code{THEN} in Pascal
and many other programming languages has the meaning 3d.]

We also provide the words @code{?dup-if} and @code{?dup-0=-if}, so you
can avoid using @code{?dup}.

@example
@var{n}
CASE
  @var{n1} OF @var{code1} ENDOF
  @var{n2} OF @var{code2} ENDOF
  @dots
ENDCASE
@end example

Executes the first @var{codei}, where the @var{ni} is equal to
@var{n}. A default case can be added by simply writing the code after
the last @code{ENDOF}. It may use @var{n}, which is on top of the stack,
but must not consume it.

@subsection Simple Loops

@example
BEGIN
  @var{code1}
  @var{flag}
WHILE
  @var{code2}
REPEAT
@end example

@var{code1} is executed and @var{flag} is computed. If it is true,
@var{code2} is executed and the loop is restarted; If @var{flag} is false, execution continues after the @code{REPEAT}.

@example
BEGIN
  @var{code}
  @var{flag}
UNTIL
@end example

@var{code} is executed. The loop is restarted if @code{flag} is false.

@example
BEGIN
  @var{code}
AGAIN
@end example

This is an endless loop.

@subsection Counted Loops

The basic counted loop is:
@example
@var{limit} @var{start}
?DO
  @var{body}
LOOP
@end example

This performs one iteration for every integer, starting from @var{start}
and up to, but excluding @var{limit}. The counter, aka index, can be
accessed with @code{i}. E.g., the loop
@example
10 0 ?DO
  i .
LOOP
@end example
prints
@example
0 1 2 3 4 5 6 7 8 9
@end example
The index of the innermost loop can be accessed with @code{i}, the index
of the next loop with @code{j}, and the index of the third loop with
@code{k}.

The loop control data are kept on the return stack, so there are some
restrictions on mixing return stack accesses and counted loop
words. E.g., if you put values on the return stack outside the loop, you
cannot read them inside the loop. If you put values on the return stack
within a loop, you have to remove them before the end of the loop and
before accessing the index of the loop.

There are several variations on the counted loop:

@code{LEAVE} leaves the innermost counted loop immediately.

@code{LOOP} can be replaced with @code{@var{n} +LOOP}; this updates the
index by @var{n} instead of by 1. The loop is terminated when the border
between @var{limit-1} and @var{limit} is crossed. E.g.:

@code{4 0 ?DO  i .  2 +LOOP}   prints @code{0 2}

@code{4 1 ?DO  i .  2 +LOOP}   prints @code{1 3}

The behaviour of @code{@var{n} +LOOP} is peculiar when @var{n} is negative:

@code{-1 0 ?DO  i .  -1 +LOOP}  prints @code{0 -1}

@code{ 0 0 ?DO  i .  -1 +LOOP}  prints nothing

Therefore we recommend avoiding using @code{@var{n} +LOOP} with negative
@var{n}. One alternative is @code{@var{n} S+LOOP}, where the negative
case behaves symmetrical to the positive case:

@code{-2 0 ?DO  i .  -1 +LOOP}  prints @code{0 -1}

@code{-1 0 ?DO  i .  -1 +LOOP}  prints @code{0}

@code{ 0 0 ?DO  i .  -1 +LOOP}  prints nothing

The loop is terminated when the border between @var{limit@minus{}sgn(n)} and
@var{limit} is crossed. However, @code{S+LOOP} is not part of the ANS
Forth standard.

@code{?DO} can be replaced by @code{DO}. @code{DO} enters the loop even
when the start and the limit value are equal. We do not recommend using
@code{DO}. It will just give you maintenance troubles.

@code{UNLOOP} is used to prepare for an abnormal loop exit, e.g., via
@code{EXIT}. @code{UNLOOP} removes the loop control parameters from the
return stack so @code{EXIT} can get to its return address.

Another counted loop is
@example
@var{n}
FOR
  @var{body}
NEXT
@end example
This is the preferred loop of native code compiler writers who are too
lazy to optimize @code{?DO} loops properly. In GNU Forth, this loop
iterates @var{n+1} times; @code{i} produces values starting with @var{n}
and ending with 0. Other Forth systems may behave differently, even if
they support @code{FOR} loops.

@subsection Arbitrary control structures

ANS Forth permits and supports using control structures in a non-nested
way. Information about incomplete control structures is stored on the
control-flow stack. This stack may be implemented on the Forth data
stack, and this is what we have done in gforth.

An @i{orig} entry represents an unresolved forward branch, a @i{dest}
entry represents a backward branch target. A few words are the basis for
building any control structure possible (except control structures that
need storage, like calls, coroutines, and backtracking).

doc-if
doc-ahead
doc-then
doc-begin
doc-until
doc-again
doc-cs-pick
doc-cs-roll

On many systems control-flow stack items take one word, in gforth they
currently take three (this may change in the future). Therefore it is a
really good idea to manipulate the control flow stack with
@code{cs-pick} and @code{cs-roll}, not with data stack manipulation
words.

Some standard control structure words are built from these words:

doc-else
doc-while
doc-repeat

Counted loop words constitute a separate group of words:

doc-?do
doc-do
doc-for
doc-loop
doc-s+loop
doc-+loop
doc-next
doc-leave
doc-?leave
doc-unloop
doc-undo

The standard does not allow using @code{cs-pick} and @code{cs-roll} on
@i{do-sys}. Our system allows it, but it's your job to ensure that for
every @code{?DO} etc. there is exactly one @code{UNLOOP} on any path
through the definition (@code{LOOP} etc. compile an @code{UNLOOP} on the
fall-through path). Also, you have to ensure that all @code{LEAVE}s are
resolved (by using one of the loop-ending words or @code{UNDO}).

Another group of control structure words are

doc-case
doc-endcase
doc-of
doc-endof

@i{case-sys} and @i{of-sys} cannot be processed using @code{cs-pick} and
@code{cs-roll}.

@subsubsection Programming Style

In order to ensure readability we recommend that you do not create
arbitrary control structures directly, but define new control structure
words for the control structure you want and use these words in your
program.

E.g., instead of writing

@example
begin
  ...
if [ 1 cs-roll ]
  ...
again then
@end example

we recommend defining control structure words, e.g.,

@example
: while ( dest -- orig dest )
 POSTPONE if
 1 cs-roll ; immediate

: repeat ( orig dest -- )
 POSTPONE again
 POSTPONE then ; immediate
@end example

and then using these to create the control structure:

@example
begin
  ...
while
  ...
repeat
@end example

That's much easier to read, isn't it? Of course, @code{BEGIN} and
@code{WHILE} are predefined, so in this example it would not be
necessary to define them.

@subsection Calls and returns

A definition can be called simply be writing the name of the
definition. When the end of the definition is reached, it returns. An earlier return can be forced using

doc-exit

Don't forget to clean up the return stack and @code{UNLOOP} any
outstanding @code{?DO}...@code{LOOP}s before @code{EXIT}ing. The
primitive compiled by @code{EXIT} is

doc-;s

@subsection Exception Handling

doc-catch
doc-throw

@node Locals
@section Locals

Local variables can make Forth programming more enjoyable and Forth
programs easier to read. Unfortunately, the locals of ANS Forth are
laden with restrictions. Therefore, we provide not only the ANS Forth
locals wordset, but also our own, more powerful locals wordset (we
implemented the ANS Forth locals wordset through our locals wordset).

@menu
@end menu

@subsection gforth locals

Locals can be defined with

@example
@{ local1 local2 ... -- comment @}
@end example
or
@example
@{ local1 local2 ... @}
@end example

E.g.,
@example
: max @{ n1 n2 -- n3 @}
 n1 n2 > if
   n1
 else
   n2
 endif ;
@end example

The similarity of locals definitions with stack comments is intended. A
locals definition often replaces the stack comment of a word. The order
of the locals corresponds to the order in a stack comment and everything
after the @code{--} is really a comment.

This similarity has one disadvantage: It is too easy to confuse locals
declarations with stack comments, causing bugs and making them hard to
find. However, this problem can be avoided by appropriate coding
conventions: Do not use both notations in the same program. If you do,
they should be distinguished using additional means, e.g. by position.

The name of the local may be preceded by a type specifier, e.g.,
@code{F:} for a floating point value:

@example
: CX* @{ F: Ar F: Ai F: Br F: Bi -- Cr Ci @}
\ complex multiplication
 Ar Br f* Ai Bi f* f-
 Ar Bi f* Ai Br f* f+ ;
@end example

GNU Forth currently supports cells (@code{W:}, @code{W^}), doubles
(@code{D:}, @code{D^}), floats (@code{F:}, @code{F^}) and characters
(@code{C:}, @code{C^}) in two flavours: a value-flavoured local (defined
with @code{W:}, @code{D:} etc.) produces its value and can be changed
with @code{TO}. A variable-flavoured local (defined with @code{W^} etc.)
produces its address (which becomes invalid when the variable's scope is
left). E.g., the standard word @code{emit} can be defined in therms of
@code{type} like this:

@example
: emit @{ C^ char* -- @}
    char* 1 type ;
@end example

A local without type specifier is a @code{W:} local. Both flavours of
locals are initialized with values from the data or FP stack.

Currently there is no way to define locals with user-defined data
structures, but we are working on it.

GNU Forth allows defining locals everywhere in a colon definition. This poses the following questions:

@subsubsection Where are locals visible by name?

Basically, the answer is that locals are visible where you would expect
it in block-structured languages, and sometimes a little longer. If you
want to restrict the scope of a local, enclose its definition in
@code{SCOPE}...@code{ENDSCOPE}.

doc-scope
doc-endscope

These words behave like control structure words, so you can use them
with @code{CS-PICK} and @code{CS-ROLL} to restrict the scope in
arbitrary ways.

If you want a more exact answer to the visibility question, here's the
basic principle: A local is visible in all places that can only be
reached through the definition of the local@footnote{In compiler
construction terminology, all places dominated by the definition of the
local.}. In other words, it is not visible in places that can be reached
without going through the definition of the local. E.g., locals defined
in @code{IF}...@code{ENDIF} are visible until the @code{ENDIF}, locals
defined in @code{BEGIN}...@code{UNTIL} are visible after the
@code{UNTIL} (until, e.g., a subsequent @code{ENDSCOPE}).

The reasoning behind this solution is: We want to have the locals
visible as long as it is meaningful. The user can always make the
visibility shorter by using explicit scoping. In a place that can
only be reached through the definition of a local, the meaning of a
local name is clear. In other places it is not: How is the local
initialized at the control flow path that does not contain the
definition? Which local is meant, if the same name is defined twice in
two independent control flow paths?

This should be enough detail for nearly all users, so you can skip the
rest of this section. If you relly must know all the gory details and
options, read on.

In order to implement this rule, the compiler has to know which places
are unreachable. It knows this automatically after @code{AHEAD},
@code{AGAIN}, @code{EXIT} and @code{LEAVE}; in other cases (e.g., after
most @code{THROW}s), you can use the word @code{UNREACHABLE} to tell the
compiler that the control flow never reaches that place. If
@code{UNREACHABLE} is not used where it could, the only consequence is
that the visibility of some locals is more limited than the rule above
says. If @code{UNREACHABLE} is used where it should not (i.e., if you
lie to the compiler), buggy code will be produced.

Another problem with this rule is that at @code{BEGIN}, the compiler
does not know which locals will be visible on the incoming
back-edge. All problems discussed in the following are due to this
ignorance of the compiler (we discuss the problems using @code{BEGIN}
loops as examples; the discussion also applies to @code{?DO} and other
loops). Perhaps the most insidious example is:
@example
AHEAD
BEGIN
  x
[ 1 CS-ROLL ] THEN
  { x }
  ...
UNTIL
@end example

This should be legal according to the visibility rule. The use of
@code{x} can only be reached through the definition; but that appears
textually below the use.

From this example it is clear that the visibility rules cannot be fully
implemented without major headaches. Our implementation treats common
cases as advertised and the exceptions are treated in a safe way: The
compiler makes a reasonable guess about the locals visible after a
@code{BEGIN}; if it is too pessimistic, the
user will get a spurious error about the local not being defined; if the
compiler is too optimistic, it will notice this later and issue a
warning. In the case above the compiler would complain about @code{x}
being undefined at its use. You can see from the obscure examples in
this section that it takes quite unusual control structures to get the
compiler into trouble, and even then it will often do fine.

If the @code{BEGIN} is reachable from above, the most optimistic guess
is that all locals visible before the @code{BEGIN} will also be
visible after the @code{BEGIN}. This guess is valid for all loops that
are entered only through the @code{BEGIN}, in particular, for normal
@code{BEGIN}...@code{WHILE}...@code{REPEAT} and
@code{BEGIN}...@code{UNTIL} loops and it is implemented in our
compiler. When the branch to the @code{BEGIN} is finally generated by
@code{AGAIN} or @code{UNTIL}, the compiler checks the guess and
warns the user if it was too optimisitic:
@example
IF
  { x }
BEGIN
  \ x ? 
[ 1 cs-roll ] THEN
  ...
UNTIL
@end example

Here, @code{x} lives only until the @code{BEGIN}, but the compiler
optimistically assumes that it lives until the @code{THEN}. It notices
this difference when it compiles the @code{UNTIL} and issues a
warning. The user can avoid the warning, and make sure that @code{x}
is not used in the wrong area by using explicit scoping:
@example
IF
  SCOPE
  { x }
  ENDSCOPE
BEGIN
[ 1 cs-roll ] THEN
  ...
UNTIL
@end example

Since the guess is optimistic, there will be no spurious error messages
about undefined locals.

If the @code{BEGIN} is not reachable from above (e.g., after
@code{AHEAD} or @code{EXIT}), the compiler cannot even make an
optimistic guess, as the locals visible after the @code{BEGIN} may be
defined later. Therefore, the compiler assumes that no locals are
visible after the @code{BEGIN}. However, the useer can use
@code{ASSUME-LIVE} to make the compiler assume that the same locals are
visible at the BEGIN as at the point where the item was created.

doc-assume-live

E.g.,
@example
{ x }
AHEAD
ASSUME-LIVE
BEGIN
  x
[ 1 CS-ROLL ] THEN
  ...
UNTIL
@end example

Other cases where the locals are defined before the @code{BEGIN} can be
handled by inserting an appropriate @code{CS-ROLL} before the
@code{ASSUME-LIVE} (and changing the control-flow stack manipulation
behind the @code{ASSUME-LIVE}).

Cases where locals are defined after the @code{BEGIN} (but should be
visible immediately after the @code{BEGIN}) can only be handled by
rearranging the loop. E.g., the ``most insidious'' example above can be
arranged into:
@example
BEGIN
  { x }
  ... 0=
WHILE
  x
REPEAT
@end example

@subsubsection How long do locals live?

The right answer for the lifetime question would be: A local lives at
least as long as it can be accessed. For a value-flavoured local this
means: until the end of its visibility. However, a variable-flavoured
local could be accessed through its address far beyond its visibility
scope. Ultimately, this would mean that such locals would have to be
garbage collected. Since this entails un-Forth-like implementation
complexities, I adopted the same cowardly solution as some other
languages (e.g., C): The local lives only as long as it is visible;
afterwards its address is invalid (and programs that access it
afterwards are erroneous).

@subsubsection Programming Style

The freedom to define locals anywhere has the potential to change
programming styles dramatically. In particular, the need to use the
return stack for intermediate storage vanishes. Moreover, all stack
manipulations (except @code{PICK}s and @code{ROLL}s with run-time
determined arguments) can be eliminated: If the stack items are in the
wrong order, just write a locals definition for all of them; then
write the items in the order you want.

This seems a little far-fetched and eliminating stack manipulations is
unlikely to become a conscious programming objective. Still, the
number of stack manipulations will be reduced dramatically if local
variables are used liberally (e.g., compare @code{max} in \sect{misc}
with a traditional implementation of @code{max}).

This shows one potential benefit of locals: making Forth programs more
readable. Of course, this benefit will only be realized if the
programmers continue to honour the principle of factoring instead of
using the added latitude to make the words longer.

Using @code{TO} can and should be avoided.  Without @code{TO},
every value-flavoured local has only a single assignment and many
advantages of functional languages apply to Forth. I.e., programs are
easier to analyse, to optimize and to read: It is clear from the
definition what the local stands for, it does not turn into something
different later.

E.g., a definition using @code{TO} might look like this:
@example
: strcmp @{ addr1 u1 addr2 u2 -- n @}
 u1 u2 min 0
 ?do
   addr1 c@ addr2 c@ - ?dup
   if
     unloop exit
   then
   addr1 char+ TO addr1
   addr2 char+ TO addr2
 loop
 u1 u2 - ;
@end example
Here, @code{TO} is used to update @code{addr1} and @code{addr2} at
every loop iteration. @code{strcmp} is a typical example of the
readability problems of using @code{TO}. When you start reading
@code{strcmp}, you think that @code{addr1} refers to the start of the
string. Only near the end of the loop you realize that it is something
else.

This can be avoided by defining two locals at the start of the loop that
are initialized with the right value for the current iteration.
@example
: strcmp @{ addr1 u1 addr2 u2 -- n @}
 addr1 addr2
 u1 u2 min 0 
 ?do @{ s1 s2 @}
   s1 c@ s2 c@ - ?dup 
   if
     unloop exit
   then
   s1 char+ s2 char+
 loop
 2drop
 u1 u2 - ;
@end example
Here it is clear from the start that @code{s1} has a different value
in every loop iteration.

@subsubsection Implementation

GNU Forth uses an extra locals stack. The most compelling reason for
this is that the return stack is not float-aligned; using an extra stack
also eliminates the problems and restrictions of using the return stack
as locals stack. Like the other stacks, the locals stack grows toward
lower addresses. A few primitives allow an efficient implementation:

doc-@local#
doc-f@local#
doc-laddr#
doc-lp+!#
doc-lp!
doc->l
doc-f>l

In addition to these primitives, some specializations of these
primitives for commonly occurring inline arguments are provided for
efficiency reasons, e.g., @code{@@local0} as specialization of
@code{@@local#} for the inline argument 0. The following compiling words
compile the right specialized version, or the general version, as
appropriate:

doc-compile-@@local
doc-compile-f@@local
doc-compile-lp+!

Combinations of conditional branches and @code{lp+!#} like
@code{?branch-lp+!#} (the locals pointer is only changed if the branch
is taken) are provided for efficiency and correctness in loops.

A special area in the dictionary space is reserved for keeping the
local variable names. @code{@{} switches the dictionary pointer to this
area and @code{@}} switches it back and generates the locals
initializing code. @code{W:} etc.@ are normal defining words. This
special area is cleared at the start of every colon definition.

A special feature of GNU Forths dictionary is used to implement the
definition of locals without type specifiers: every wordlist (aka
vocabulary) has its own methods for searching
etc. (@xref{dictionary}). For the present purpose we defined a wordlist
with a special search method: When it is searched for a word, it
actually creates that word using @code{W:}. @code{@{} changes the search
order to first search the wordlist containing @code{@}}, @code{W:} etc.,
and then the wordlist for defining locals without type specifiers.

The lifetime rules support a stack discipline within a colon
definition: The lifetime of a local is either nested with other locals
lifetimes or it does not overlap them.

At @code{BEGIN}, @code{IF}, and @code{AHEAD} no code for locals stack
pointer manipulation is generated. Between control structure words
locals definitions can push locals onto the locals stack. @code{AGAIN}
is the simplest of the other three control flow words. It has to
restore the locals stack depth of the corresponding @code{BEGIN}
before branching. The code looks like this:
@format
@code{lp+!#} current-locals-size @minus{} dest-locals-size
@code{branch} <begin>
@end format

@code{UNTIL} is a little more complicated: If it branches back, it
must adjust the stack just like @code{AGAIN}. But if it falls through,
the locals stack must not be changed. The compiler generates the
following code:
@format
@code{?branch-lp+!#} <begin> current-locals-size @minus{} dest-locals-size
@end format
The locals stack pointer is only adjusted if the branch is taken.

@code{THEN} can produce somewhat inefficient code:
@format
@code{lp+!#} current-locals-size @minus{} orig-locals-size
<orig target>:
@code{lp+!#} orig-locals-size @minus{} new-locals-size
@end format
The second @code{lp+!#} adjusts the locals stack pointer from the
level at the {\em orig} point to the level after the @code{THEN}. The
first @code{lp+!#} adjusts the locals stack pointer from the current
level to the level at the orig point, so the complete effect is an
adjustment from the current level to the right level after the
@code{THEN}.

In a conventional Forth implementation a dest control-flow stack entry
is just the target address and an orig entry is just the address to be
patched. Our locals implementation adds a wordlist to every orig or dest
item. It is the list of locals visible (or assumed visible) at the point
described by the entry. Our implementation also adds a tag to identify
the kind of entry, in particular to differentiate between live and dead
(reachable and unreachable) orig entries.

A few unusual operations have to be performed on locals wordlists:

doc-common-list
doc-sub-list?
doc-list-size

Several features of our locals wordlist implementation make these
operations easy to implement: The locals wordlists are organised as
linked lists; the tails of these lists are shared, if the lists
contain some of the same locals; and the address of a name is greater
than the address of the names behind it in the list.

Another important implementation detail is the variable
@code{dead-code}. It is used by @code{BEGIN} and @code{THEN} to
determine if they can be reached directly or only through the branch
that they resolve. @code{dead-code} is set by @code{UNREACHABLE},
@code{AHEAD}, @code{EXIT} etc., and cleared at the start of a colon
definition, by @code{BEGIN} and usually by @code{THEN}.

Counted loops are similar to other loops in most respects, but
@code{LEAVE} requires special attention: It performs basically the same
service as @code{AHEAD}, but it does not create a control-flow stack
entry. Therefore the information has to be stored elsewhere;
traditionally, the information was stored in the target fields of the
branches created by the @code{LEAVE}s, by organizing these fields into a
linked list. Unfortunately, this clever trick does not provide enough
space for storing our extended control flow information. Therefore, we
introduce another stack, the leave stack. It contains the control-flow
stack entries for all unresolved @code{LEAVE}s.

Local names are kept until the end of the colon definition, even if
they are no longer visible in any control-flow path. In a few cases
this may lead to increased space needs for the locals name area, but
usually less than reclaiming this space would cost in code size.


@subsection ANS Forth locals

The ANS Forth locals wordset does not define a syntax for locals, but
words that make it possible to define various syntaxes. One of the
possible syntaxes is a subset of the syntax we used in the gforth locals
wordset, i.e.:

@example
@{ local1 local2 ... -- comment @}
@end example
or
@example
@{ local1 local2 ... @}
@end example

The order of the locals corresponds to the order in a stack comment. The
restrictions are:

@itemize @bullet
@item
Locals can only be cell-sized values (no type specifers are allowed).
@item
Locals can be defined only outside control structures.
@item
Locals can interfere with explicit usage of the return stack. For the
exact (and long) rules, see the standard. If you don't use return stack
accessing words in a definition using locals, you will we all right. The
purpose of this rule is to make locals implementation on the return
stack easier.
@item
The whole definition must be in one line.
@end itemize

Locals defined in this way behave like @code{VALUE}s
(@xref{values}). I.e., they are initialized from the stack. Using their
name produces their value. Their value can be changed using @code{TO}.

Since this syntax is supported by gforth directly, you need not do
anything to use it. If you want to port a program using this syntax to
another ANS Forth system, use @file{anslocal.fs} to implement the syntax
on the other system.

Note that a syntax shown in the standard, section A.13 looks
similar, but is quite different in having the order of locals
reversed. Beware!

The ANS Forth locals wordset itself consists of the following word

doc-(local)

The ANS Forth locals extension wordset defines a syntax, but it is so
awful that we strongly recommend not to use it. We have implemented this
syntax to make porting to gforth easy, but do not document it here. The
problem with this syntax is that the locals are defined in an order
reversed with respect to the standard stack comment notation, making
programs harder to read, and easier to misread and miswrite. The only
merit of this syntax is that it is easy to implement using the ANS Forth
locals wordset.

@node Internals
@chapter Internals

Reading this section is not necessary for programming with gforth. It
should be helpful for finding your way in the gforth sources.

@section Portability

One of the main goals of the effort is availability across a wide range
of personal machines. fig-Forth, and, to a lesser extent, F83, achieved
this goal by manually coding the engine in assembly language for several
then-popular processors. This approach is very labor-intensive and the
results are short-lived due to progress in computer architecture.

Others have avoided this problem by coding in C, e.g., Mitch Bradley
(cforth), Mikael Patel (TILE) and Dirk Zoller (pfe). This approach is
particularly popular for UNIX-based Forths due to the large variety of
architectures of UNIX machines. Unfortunately an implementation in C
does not mix well with the goals of efficiency and with using
traditional techniques: Indirect or direct threading cannot be expressed
in C, and switch threading, the fastest technique available in C, is
significantly slower. Another problem with C is that it's very
cumbersome to express double integer arithmetic.

Fortunately, there is a portable language that does not have these
limitations: GNU C, the version of C processed by the GNU C compiler
(@pxref{C Extensions, , Extensions to the C Language Family, gcc.info,
GNU C Manual}). Its labels as values feature (@pxref{Labels as Values, ,
Labels as Values, gcc.info, GNU C Manual}) makes direct and indirect
threading possible, its @code{long long} type (@pxref{Long Long, ,
Double-Word Integers, gcc.info, GNU C Manual}) corresponds to Forths
double numbers. GNU C is available for free on all important (and many
unimportant) UNIX machines, VMS, 80386s running MS-DOS, the Amiga, and
the Atari ST, so a Forth written in GNU C can run on all these
machines@footnote{Due to Apple's look-and-feel lawsuit it is not
available on the Mac (@pxref{Boycott, , Protect Your Freedom--Fight
``Look And Feel'', gcc.info, GNU C Manual}).}.

Writing in a portable language has the reputation of producing code that
is slower than assembly. For our Forth engine we repeatedly looked at
the code produced by the compiler and eliminated most compiler-induced
inefficiencies by appropriate changes in the source-code.

However, register allocation cannot be portably influenced by the
programmer, leading to some inefficiencies on register-starved
machines. We use explicit register declarations (@pxref{Explicit Reg
Vars, , Variables in Specified Registers, gcc.info, GNU C Manual}) to
improve the speed on some machines. They are turned on by using the
@code{gcc} switch @code{-DFORCE_REG}. Unfortunately, this feature not
only depends on the machine, but also on the compiler version: On some
machines some compiler versions produce incorrect code when certain
explicit register declarations are used. So by default
@code{-DFORCE_REG} is not used.

@section Threading

GNU C's labels as values extension (available since @code{gcc-2.0},
@pxref{Labels as Values, , Labels as Values, gcc.info, GNU C Manual})
makes it possible to take the address of @var{label} by writing
@code{&&@var{label}}.  This address can then be used in a statement like
@code{goto *@var{address}}. I.e., @code{goto *&&x} is the same as
@code{goto x}.

With this feature an indirect threaded NEXT looks like:
@example
cfa = *ip++;
ca = *cfa;
goto *ca;
@end example
For those unfamiliar with the names: @code{ip} is the Forth instruction
pointer; the @code{cfa} (code-field address) corresponds to ANS Forths
execution token and points to the code field of the next word to be
executed; The @code{ca} (code address) fetched from there points to some
executable code, e.g., a primitive or the colon definition handler
@code{docol}.

Direct threading is even simpler:
@example
ca = *ip++;
goto *ca;
@end example

Of course we have packaged the whole thing neatly in macros called
@code{NEXT} and @code{NEXT1} (the part of NEXT after fetching the cfa).

@subsection Scheduling

There is a little complication: Pipelined and superscalar processors,
i.e., RISC and some modern CISC machines can process independent
instructions while waiting for the results of an instruction. The
compiler usually reorders (schedules) the instructions in a way that
achieves good usage of these delay slots. However, on our first tries
the compiler did not do well on scheduling primitives. E.g., for
@code{+} implemented as
@example
n=sp[0]+sp[1];
sp++;
sp[0]=n;
NEXT;
@end example
the NEXT comes strictly after the other code, i.e., there is nearly no
scheduling. After a little thought the problem becomes clear: The
compiler cannot know that sp and ip point to different addresses (and
the version of @code{gcc} we used would not know it even if it could),
so it could not move the load of the cfa above the store to the
TOS. Indeed the pointers could be the same, if code on or very near the
top of stack were executed. In the interest of speed we chose to forbid
this probably unused ``feature'' and helped the compiler in scheduling:
NEXT is divided into the loading part (@code{NEXT_P1}) and the goto part
(@code{NEXT_P2}). @code{+} now looks like:
@example
n=sp[0]+sp[1];
sp++;
NEXT_P1;
sp[0]=n;
NEXT_P2;
@end example
This can be scheduled optimally by the compiler (see \sect{TOS}).

This division can be turned off with the switch @code{-DCISC_NEXT}. This
switch is on by default on machines that do not profit from scheduling
(e.g., the 80386), in order to preserve registers.

@subsection Direct or Indirect Threaded?

Both! After packaging the nasty details in macro definitions we
realized that we could switch between direct and indirect threading by
simply setting a compilation flag (@code{-DDIRECT_THREADED}) and
defining a few machine-specific macros for the direct-threading case.
On the Forth level we also offer access words that hide the
differences between the threading methods (@pxref{Threading Words}).

Indirect threading is implemented completely
machine-independently. Direct threading needs routines for creating
jumps to the executable code (e.g. to docol or dodoes). These routines
are inherently machine-dependent, but they do not amount to many source
lines. I.e., even porting direct threading to a new machine is a small
effort.

@subsection DOES>
One of the most complex parts of a Forth engine is @code{dodoes}, i.e.,
the chunk of code executed by every word defined by a
@code{CREATE}...@code{DOES>} pair. The main problem here is: How to find
the Forth code to be executed, i.e. the code after the @code{DOES>} (the
DOES-code)? There are two solutions:

In fig-Forth the code field points directly to the dodoes and the
DOES-code address is stored in the cell after the code address
(i.e. at cfa cell+). It may seem that this solution is illegal in the
Forth-79 and all later standards, because in fig-Forth this address
lies in the body (which is illegal in these standards). However, by
making the code field larger for all words this solution becomes legal
again. We use this approach for the indirect threaded version. Leaving
a cell unused in most words is a bit wasteful, but on the machines we
are targetting this is hardly a problem. The other reason for having a
code field size of two cells is to avoid having different image files
for direct and indirect threaded systems (@pxref{image-format}).

The other approach is that the code field points or jumps to the cell
after @code{DOES}. In this variant there is a jump to @code{dodoes} at
this address. @code{dodoes} can then get the DOES-code address by
computing the code address, i.e., the address of the jump to dodoes,
and add the length of that jump field. A variant of this is to have a
call to @code{dodoes} after the @code{DOES>}; then the return address
(which can be found in the return register on RISCs) is the DOES-code
address. Since the two cells available in the code field are usually
used up by the jump to the code address in direct threading, we use
this approach for direct threading. We did not want to add another
cell to the code field.

@section Primitives

@subsection Automatic Generation

Since the primitives are implemented in a portable language, there is no
longer any need to minimize the number of primitives. On the contrary,
having many primitives is an advantage: speed. In order to reduce the
number of errors in primitives and to make programming them easier, we
provide a tool, the primitive generator (@file{prims2x.fs}), that
automatically generates most (and sometimes all) of the C code for a
primitive from the stack effect notation.  The source for a primitive
has the following form:

@format
@var{Forth-name}	@var{stack-effect}	@var{category}	[@var{pronounc.}]
[@code{""}@var{glossary entry}@code{""}]
@var{C code}
[@code{:}
@var{Forth code}]
@end format

The items in brackets are optional. The category and glossary fields
are there for generating the documentation, the Forth code is there
for manual implementations on machines without GNU C. E.g., the source
for the primitive @code{+} is:
@example
+    n1 n2 -- n    core    plus
n = n1+n2;
@end example

This looks like a specification, but in fact @code{n = n1+n2} is C
code. Our primitive generation tool extracts a lot of information from
the stack effect notations@footnote{We use a one-stack notation, even
though we have separate data and floating-point stacks; The separate
notation can be generated easily from the unified notation.}: The number
of items popped from and pushed on the stack, their type, and by what
name they are referred to in the C code. It then generates a C code
prelude and postlude for each primitive. The final C code for @code{+}
looks like this:

@example
I_plus:	/* + ( n1 n2 -- n ) */  /* label, stack effect */
/*  */                          /* documentation */
{
DEF_CA                          /* definition of variable ca (indirect threading) */
Cell n1;                        /* definitions of variables */
Cell n2;
Cell n;
n1 = (Cell) sp[1];              /* input */
n2 = (Cell) TOS;
sp += 1;                        /* stack adjustment */
NAME("+")                       /* debugging output (with -DDEBUG) */
{
n = n1+n2;                      /* C code taken from the source */
}
NEXT_P1;                        /* NEXT part 1 */
TOS = (Cell)n;                  /* output */
NEXT_P2;                        /* NEXT part 2 */
}
@end example

This looks long and inefficient, but the GNU C compiler optimizes quite
well and produces optimal code for @code{+} on, e.g., the R3000 and the
HP RISC machines: Defining the @code{n}s does not produce any code, and
using them as intermediate storage also adds no cost.

There are also other optimizations, that are not illustrated by this
example: Assignments between simple variables are usually for free (copy
propagation). If one of the stack items is not used by the primitive
(e.g.  in @code{drop}), the compiler eliminates the load from the stack
(dead code elimination). On the other hand, there are some things that
the compiler does not do, therefore they are performed by
@file{prims2x.fs}: The compiler does not optimize code away that stores
a stack item to the place where it just came from (e.g., @code{over}).

While programming a primitive is usually easy, there are a few cases
where the programmer has to take the actions of the generator into
account, most notably @code{?dup}, but also words that do not (always)
fall through to NEXT.

@subsection TOS Optimization

An important optimization for stack machine emulators, e.g., Forth
engines, is keeping  one or more of the top stack items in
registers.  If a word has the stack effect {@var{in1}...@var{inx} @code{--}
@var{out1}...@var{outy}}, keeping the top @var{n} items in registers
@itemize
@item
is better than keeping @var{n-1} items, if @var{x>=n} and @var{y>=n},
due to fewer loads from and stores to the stack.
@item is slower than keeping @var{n-1} items, if @var{x<>y} and @var{x<n} and
@var{y<n}, due to additional moves between registers.
@end itemize

In particular, keeping one item in a register is never a disadvantage,
if there are enough registers. Keeping two items in registers is a
disadvantage for frequent words like @code{?branch}, constants,
variables, literals and @code{i}. Therefore our generator only produces
code that keeps zero or one items in registers. The generated C code
covers both cases; the selection between these alternatives is made at
C-compile time using the switch @code{-DUSE_TOS}. @code{TOS} in the C
code for @code{+} is just a simple variable name in the one-item case,
otherwise it is a macro that expands into @code{sp[0]}. Note that the
GNU C compiler tries to keep simple variables like @code{TOS} in
registers, and it usually succeeds, if there are enough registers.

The primitive generator performs the TOS optimization for the
floating-point stack, too (@code{-DUSE_FTOS}). For floating-point
operations the benefit of this optimization is even larger:
floating-point operations take quite long on most processors, but can be
performed in parallel with other operations as long as their results are
not used. If the FP-TOS is kept in a register, this works. If
it is kept on the stack, i.e., in memory, the store into memory has to
wait for the result of the floating-point operation, lengthening the
execution time of the primitive considerably.

The TOS optimization makes the automatic generation of primitives a
bit more complicated. Just replacing all occurrences of @code{sp[0]} by
@code{TOS} is not sufficient. There are some special cases to
consider:
@itemize
@item In the case of @code{dup ( w -- w w )} the generator must not
eliminate the store to the original location of the item on the stack,
if the TOS optimization is turned on.
@item Primitives with stack effects of the form {@code{--}
@var{out1}...@var{outy}} must store the TOS to the stack at the start.
Likewise, primitives with the stack effect {@var{in1}...@var{inx} @code{--}}
must load the TOS from the stack at the end. But for the null stack
effect @code{--} no stores or loads should be generated.
@end itemize

@subsection Produced code

To see what assembly code is produced for the primitives on your machine
with your compiler and your flag settings, type @code{make engine.s} and
look at the resulting file @file{engine.c}.

@section System Architecture

Our Forth system consists not only of primitives, but also of
definitions written in Forth. Since the Forth compiler itself belongs
to those definitions, it is not possible to start the system with the
primitives and the Forth source alone. Therefore we provide the Forth
code as an image file in nearly executable form. At the start of the
system a C routine loads the image file into memory, sets up the
memory (stacks etc.) according to information in the image file, and
starts executing Forth code.

The image file format is a compromise between the goals of making it
easy to generate image files and making them portable. The easiest way
to generate an image file is to just generate a memory dump. However,
this kind of image file cannot be used on a different machine, or on
the next version of the engine on the same machine, it even might not
work with the same engine compiled by a different version of the C
compiler. We would like to have as few versions of the image file as
possible, because we do not want to distribute many versions of the
same image file, and to make it easy for the users to use their image
files on many machines. We currently need to create a different image
file for machines with different cell sizes and different byte order
(little- or big-endian)@footnote{We consider adding information to the
image file that enables the loader to change the byte order.}.

Forth code that is going to end up in a portable image file has to
comply to some restrictions: addresses have to be stored in memory
with special words (@code{A!}, @code{A,}, etc.) in order to make the
code relocatable. Cells, floats, etc., have to be stored at the
natural alignment boundaries@footnote{E.g., store floats (8 bytes) at
an address dividable by~8. This happens automatically in our system
when you use the ANSI alignment words.}, in order to avoid alignment
faults on machines with stricter alignment. The image file is produced
by a metacompiler (@file{cross.fs}).

So, unlike the image file of Mitch Bradleys @code{cforth}, our image
file is not directly executable, but has to undergo some manipulations
during loading. Address relocation is performed at image load-time, not
at run-time. The loader also has to replace tokens standing for
primitive calls with the appropriate code-field addresses (or code
addresses in the case of direct threading).

@contents
@bye


FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>