This is gforth.info, produced by makeinfo version 4.0 from gforth.texi.

INFO-DIR-SECTION GNU programming tools
START-INFO-DIR-ENTRY
* Gforth: (gforth).             A fast interpreter for the Forth language.
END-INFO-DIR-ENTRY

   This file documents Gforth 0.5.0

   Copyright (C) 1995-2000 Free Software Foundation, Inc.

   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.


File: gforth.info,  Node: memory-idef,  Prev: The optional Memory-Allocation word set,  Up: The optional Memory-Allocation word set

Implementation Defined Options
------------------------------

values and meaning of ior:
     The iors returned by the file and memory allocation words are
     intended as throw codes. They typically are in the range
     -512--2047 of OS errors.  The mapping from OS error numbers to
     iors is -512-errno.


File: gforth.info,  Node: The optional Programming-Tools word set,  Next: The optional Search-Order word set,  Prev: The optional Memory-Allocation word set,  Up: ANS conformance

The optional Programming-Tools word set
=======================================

* Menu:

* programming-idef::            Implementation Defined Options
* programming-ambcond::         Ambiguous Conditions


File: gforth.info,  Node: programming-idef,  Next: programming-ambcond,  Prev: The optional Programming-Tools word set,  Up: The optional Programming-Tools word set

Implementation Defined Options
------------------------------

ending sequence for input following `;CODE' and `CODE':
     `END-CODE'

manner of processing input following `;CODE' and `CODE':
     The `ASSEMBLER' vocabulary is pushed on the search order stack, and
     the input is processed by the text interpreter, (starting) in
     interpret state.

search order capability for `EDITOR' and `ASSEMBLER':
     The ANS Forth search order word set.

source and format of display by `SEE':
     The source for `see' is the executable code used by the inner
     interpreter.  The current `see' tries to output Forth source code
     (and on some platforms, assembly code for primitives) as well as
     possible.


File: gforth.info,  Node: programming-ambcond,  Prev: programming-idef,  Up: The optional Programming-Tools word set

Ambiguous conditions
--------------------

deleting the compilation word list (`FORGET'):
     Not implemented (yet).

fewer than u+1 items on the control-flow stack (`CS-PICK', `CS-ROLL'):
     This typically results in an `abort"' with a descriptive error
     message (may change into a `-22 throw' (Control structure mismatch)
     in the future). You may also get a memory access error. If you are
     unlucky, this ambiguous condition is not caught.

name can't be found (`FORGET'):
     Not implemented (yet).

name not defined via `CREATE':
     `;CODE' behaves like `DOES>' in this respect, i.e., it changes the
     execution semantics of the last defined word no matter how it was
     defined.

`POSTPONE' applied to `[IF]':
     After defining `: X POSTPONE [IF] ; IMMEDIATE'. `X' is equivalent
     to `[IF]'.

reaching the end of the input source before matching `[ELSE]' or `[THEN]':
     Continue in the same state of conditional compilation in the next
     outer input source. Currently there is no warning to the user
     about this.

removing a needed definition (`FORGET'):
     Not implemented (yet).


File: gforth.info,  Node: The optional Search-Order word set,  Prev: The optional Programming-Tools word set,  Up: ANS conformance

The optional Search-Order word set
==================================

* Menu:

* search-idef::                 Implementation Defined Options
* search-ambcond::              Ambiguous Conditions


File: gforth.info,  Node: search-idef,  Next: search-ambcond,  Prev: The optional Search-Order word set,  Up: The optional Search-Order word set

Implementation Defined Options
------------------------------

maximum number of word lists in search order:
     `s" wordlists" environment? drop .'. Currently 16.

minimum search order:
     `root root'.


File: gforth.info,  Node: search-ambcond,  Prev: search-idef,  Up: The optional Search-Order word set

Ambiguous conditions
--------------------

changing the compilation word list (during compilation):
     The word is entered into the word list that was the compilation
     word list at the start of the definition. Any changes to the name
     field (e.g., `immediate') or the code field (e.g., when executing
     `DOES>') are applied to the latest defined word (as reported by
     `last' or `lastxt'), if possible, irrespective of the compilation
     word list.

search order empty (`previous'):
     `abort" Vocstack empty"'.

too many word lists in search order (`also'):
     `abort" Vocstack full"'.


File: gforth.info,  Node: Standard vs Extensions,  Next: Model,  Prev: ANS conformance,  Up: Top

Should I use Gforth extensions?
*******************************

   As you read through the rest of this manual, you will see
documentation for Standard words, and documentation for some appealing
Gforth extensions. You might ask yourself the question: "Should I
restrict myself to the standard, or should I use the extensions?"

   The answer depends on the goals you have for the program you are
working on:

   * Is it just for yourself or do you want to share it with others?

   * If you want to share it, do the others all use Gforth?

   * If it is just for yourself, do you want to restrict yourself to
     Gforth?


   If restricting the program to Gforth is ok, then there is no reason
not to use extensions.  It is still a good idea to keep to the standard
where it is easy, in case you want to reuse these parts in another
program that you want to be portable.

   If you want to be able to port the program to other Forth systems,
there are the following points to consider:

   * Most Forth systems that are being maintained support the ANS Forth
     standard.  So if your program complies with the standard, it will
     be portable among many systems.

   * A number of the Gforth extensions can be implemented in ANS Forth
     using public-domain files provided in the `compat/' directory.
     These are mentioned in the text in passing.  There is no reason
     not to use these extensions, your program will still be ANS Forth
     compliant; just include the appropriate compat files with your
     program.

   * The tool `ans-report.fs' (*note ANS Report::) makes it easy to
     analyse your program and determine what non-Standard words it
     relies upon.  However, it does not check whether you use standard
     words in a non-standard way.

   * Some techniques are not standardized by ANS Forth, and are hard or
     impossible to implement in a standard way, but can be implemented
     in most Forth systems easily, and usually in similar ways (e.g.,
     accessing word headers).  Forth has a rich historical precedent
     for programmers taking advantage of implementation-dependent
     features of their tools (for example, relying on a knowledge of
     the dictionary structure). Sometimes these techniques are
     necessary to extract every last bit of performance from the
     hardware, sometimes they are just a programming shorthand.

   * Does using a Gforth extension save more work than the porting this
     part to other Forth systems (if any) will cost?

   * Is the additional functionality worth the reduction in portability
     and the additional porting problems?


   In order to perform these consideratios, you need to know what's
standard and what's not.  This manual generally states if something is
non-standard, but the authoritative source is the standard document
(http://www.taygeta.com/forth/dpans.html).  Appendix A of the Standard
(RATIONALE) provides a valuable insight into the thought processes of
the technical committee.

   Note also that portability between Forth systems is not the only
portability issue; there is also the issue of portability between
different platforms (processor/OS combinations).


File: gforth.info,  Node: Model,  Next: Integrating Gforth,  Prev: Standard vs Extensions,  Up: Top

Model
*****

   This chapter has yet to be written. It will contain information, on
which internal structures you can rely.


File: gforth.info,  Node: Integrating Gforth,  Next: Emacs and Gforth,  Prev: Model,  Up: Top

Integrating Gforth into C programs
**********************************

   This is not yet implemented.

   Several people like to use Forth as scripting language for
applications that are otherwise written in C, C++, or some other
language.

   The Forth system ATLAST provides facilities for embedding it into
applications; unfortunately it has several disadvantages: most
importantly, it is not based on ANS Forth, and it is apparently dead
(i.e., not developed further and not supported). The facilities
provided by Gforth in this area are inspired by ATLAST's facilities, so
making the switch should not be hard.

   We also tried to design the interface such that it can easily be
implemented by other Forth systems, so that we may one day arrive at a
standardized interface. Such a standard interface would allow you to
replace the Forth system without having to rewrite C code.

   You embed the Gforth interpreter by linking with the library
`libgforth.a' (give the compiler the option `-lgforth').  All global
symbols in this library that belong to the interface, have the prefix
`forth_'. (Global symbols that are used internally have the prefix
`gforth_').

   You can include the declarations of Forth types and the functions and
variables of the interface with `#include <forth.h>'.

   Types.

   Variables.

   Data and FP Stack pointer. Area sizes.

   functions.

   forth_init(imagefile) forth_evaluate(string) exceptions?
forth_goto(address) (or forth_execute(xt)?)  forth_continue() (a
corountining mechanism)

   Adding primitives.

   No checking.

   Signals?

   Accessing the Stacks


File: gforth.info,  Node: Emacs and Gforth,  Next: Image Files,  Prev: Integrating Gforth,  Up: Top

Emacs and Gforth
****************

   Gforth comes with `gforth.el', an improved version of `forth.el' by
Goran Rydqvist (included in the TILE package). The improvements are:

   * A better (but still not perfect) handling of indentation.

   * Comment paragraph filling (`M-q')

   * Commenting (`C-x \') and uncommenting (`C-u C-x \') of regions

   * Removal of debugging tracers (`C-x ~', *note Debugging::).

   * Support of the `info-lookup' feature for looking up the
     documentation of a word.

   I left the stuff I do not use alone, even though some of it only
makes sense for TILE. To get a description of these features, enter
Forth mode and type `C-h m'.

   In addition, Gforth supports Emacs quite well: The source code
locations given in error messages, debugging output (from `~~') and
failed assertion messages are in the right format for Emacs'
compilation mode (*note Running Compilations under Emacs:
(emacs)Compilation.) so the source location corresponding to an error
or other message is only a few keystrokes away (`C-x `' for the next
error, `C-c C-c' for the error under the cursor).

   Also, if you `require' `etags.fs', a new `TAGS' file will be
produced (*note Tags Tables: (emacs)Tags.) that contains the
definitions of all words defined afterwards. You can then find the
source for a word using `M-.'. Note that emacs can use several tags
files at the same time (e.g., one for the Gforth sources and one for
your program, *note Selecting a Tags Table: (emacs)Select Tags Table.).
The TAGS file for the preloaded words is
`$(datadir)/gforth/$(VERSION)/TAGS' (e.g.,
`/usr/local/share/gforth/0.2.0/TAGS').  To get the best behaviour with
`etags.fs', you should avoid putting definitions both before and after
`require' etc., otherwise you will see the same file visited several
times by commands like `tags-search'.

   Moreover, for words documented in this manual, you can look up the
glossary entry quickly by using `C-h TAB' (`info-lookup-symbol', *note
Documentation Commands: (emacs)Documentation.).  This feature requires
Emacs 20.3 or later and does not work for words containing `:'.

   To get all these benefits, add the following lines to your `.emacs'
file:

     (autoload 'forth-mode "gforth.el")
     (setq auto-mode-alist (cons '("\\.fs\\'" . forth-mode) auto-mode-alist))


File: gforth.info,  Node: Image Files,  Next: Engine,  Prev: Emacs and Gforth,  Up: Top

Image Files
***********

   An image file is a file containing an image of the Forth dictionary,
i.e., compiled Forth code and data residing in the dictionary.  By
convention, we use the extension `.fi' for image files.

* Menu:

* Image Licensing Issues::      Distribution terms for images.
* Image File Background::       Why have image files?
* Non-Relocatable Image Files::  don't always work.
* Data-Relocatable Image Files::  are better.
* Fully Relocatable Image Files::  better yet.
* Stack and Dictionary Sizes::  Setting the default sizes for an image.
* Running Image Files::         `gforth -i file' or file.
* Modifying the Startup Sequence::  and turnkey applications.


File: gforth.info,  Node: Image Licensing Issues,  Next: Image File Background,  Prev: Image Files,  Up: Image Files

Image Licensing Issues
======================

   An image created with `gforthmi' (*note gforthmi::) or `savesystem'
(*note Non-Relocatable Image Files::) includes the original image;
i.e., according to copyright law it is a derived work of the original
image.

   Since Gforth is distributed under the GNU GPL, the newly created
image falls under the GNU GPL, too. In particular, this means that if
you distribute the image, you have to make all of the sources for the
image available, including those you wrote.  For details see *Note GNU
General Public License (Section 3): License.

   If you create an image with `cross' (*note cross.fs::), the image
contains only code compiled from the sources you gave it; if none of
these sources is under the GPL, the terms discussed above do not apply
to the image. However, if your image needs an engine (a gforth binary)
that is under the GPL, you should make sure that you distribute both in
a way that is at most a _mere aggregation_, if you don't want the terms
of the GPL to apply to the image.


File: gforth.info,  Node: Image File Background,  Next: Non-Relocatable Image Files,  Prev: Image Licensing Issues,  Up: Image Files

Image File Background
=====================

   Gforth consists not only of primitives (in the engine), 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
engine and the Forth source alone. Therefore we provide the Forth code
as an image file in nearly executable form. When Gforth starts up, a C
routine loads the image file into memory, optionally relocates the
addresses, then sets up the memory (stacks etc.) according to
information in the image file, and (finally) starts executing Forth
code.

   The image file variants represent different compromises between the
goals of making it easy to generate image files and making them
portable.

   Win32Forth 3.4 and Mitch Bradley's `cforth' use relocation at
run-time. This avoids many of the complications discussed below (image
files are data relocatable without further ado), but costs performance
(one addition per memory access).

   By contrast, the Gforth loader performs relocation at image load
time. The loader also has to replace tokens that represent primitive
calls with the appropriate code-field addresses (or code addresses in
the case of direct threading).

   There are three kinds of image files, with different degrees of
relocatability: non-relocatable, data-relocatable, and fully relocatable
image files.

   These image file variants have several restrictions in common; they
are caused by the design of the image file loader:

   * There is only one segment; in particular, this means, that an
     image file cannot represent `ALLOCATE'd memory chunks (and
     pointers to them). The contents of the stacks are not represented,
     either.

   * The only kinds of relocation supported are: adding the same offset
     to all cells that represent data addresses; and replacing special
     tokens with code addresses or with pieces of machine code.

     If any complex computations involving addresses are performed, the
     results cannot be represented in the image file. Several
     applications that use such computations come to mind:
        - Hashing addresses (or data structures which contain
          addresses) for table lookup. If you use Gforth's `table's or
          `wordlist's for this purpose, you will have no problem,
          because the hash tables are recomputed automatically when the
          system is started. If you use your own hash tables, you will
          have to do something similar.

        - There's a cute implementation of doubly-linked lists that uses
          `XOR'ed addresses. You could represent such lists as
          singly-linked in the image file, and restore the
          doubly-linked representation on startup.(1)

        - The code addresses of run-time routines like `docol:' cannot
          be represented in the image file (because their tokens would
          be replaced by machine code in direct threaded
          implementations). As a workaround, compute these addresses at
          run-time with `>code-address' from the executions tokens of
          appropriate words (see the definitions of `docol:' and
          friends in `kernel/getdoers.fs').

        - On many architectures addresses are represented in machine
          code in some shifted or mangled form. You cannot put `CODE'
          words that contain absolute addresses in this form in a
          relocatable image file. Workarounds are representing the
          address in some relative form (e.g., relative to the CFA,
          which is present in some register), or loading the address
          from a place where it is stored in a non-mangled form.

   ---------- Footnotes ----------

   (1) In my opinion, though, you should think thrice before using a
doubly-linked list (whatever implementation).


File: gforth.info,  Node: Non-Relocatable Image Files,  Next: Data-Relocatable Image Files,  Prev: Image File Background,  Up: Image Files

Non-Relocatable Image Files
===========================

   These files are simple memory dumps of the dictionary. They are
specific to the executable (i.e., `gforth' file) they were created
with. What's worse, they are specific to the place on which the
dictionary resided when the image was created. Now, there is no
guarantee that the dictionary will reside at the same place the next
time you start Gforth, so there's no guarantee that a non-relocatable
image will work the next time (Gforth will complain instead of crashing,
though).

   You can create a non-relocatable image file with

`savesystem'       "name" -         gforth       ``savesystem''


File: gforth.info,  Node: Data-Relocatable Image Files,  Next: Fully Relocatable Image Files,  Prev: Non-Relocatable Image Files,  Up: Image Files

Data-Relocatable Image Files
============================

   These files contain relocatable data addresses, but fixed code
addresses (instead of tokens). They are specific to the executable
(i.e., `gforth' file) they were created with. For direct threading on
some architectures (e.g., the i386), data-relocatable images do not
work. You get a data-relocatable image, if you use `gforthmi' with a
Gforth binary that is not doubly indirect threaded (*note Fully
Relocatable Image Files::).


File: gforth.info,  Node: Fully Relocatable Image Files,  Next: Stack and Dictionary Sizes,  Prev: Data-Relocatable Image Files,  Up: Image Files

Fully Relocatable Image Files
=============================

   These image files have relocatable data addresses, and tokens for
code addresses. They can be used with different binaries (e.g., with and
without debugging) on the same machine, and even across machines with
the same data formats (byte order, cell size, floating point format).
However, they are usually specific to the version of Gforth they were
created with. The files `gforth.fi' and `kernl*.fi' are fully
relocatable.

   There are two ways to create a fully relocatable image file:

* Menu:

* gforthmi::                    The normal way
* cross.fs::                    The hard way


File: gforth.info,  Node: gforthmi,  Next: cross.fs,  Prev: Fully Relocatable Image Files,  Up: Fully Relocatable Image Files

`gforthmi'
----------

   You will usually use `gforthmi'. If you want to create an image file
that contains everything you would load by invoking Gforth with `gforth
options', you simply say:
     gforthmi file options

   E.g., if you want to create an image `asm.fi' that has the file
`asm.fs' loaded in addition to the usual stuff, you could do it like
this:

     gforthmi asm.fi asm.fs

   `gforthmi' is implemented as a sh script and works like this: It
produces two non-relocatable images for different addresses and then
compares them. Its output reflects this: first you see the output (if
any) of the two Gforth invocations that produce the non-relocatable
image files, then you see the output of the comparing program: It
displays the offset used for data addresses and the offset used for
code addresses; moreover, for each cell that cannot be represented
correctly in the image files, it displays a line like this:

          78DC         BFFFFA50         BFFFFA40

   This means that at offset $78dc from `forthstart', one input image
contains $bffffa50, and the other contains $bffffa40. Since these cells
cannot be represented correctly in the output image, you should examine
these places in the dictionary and verify that these cells are dead
(i.e., not read before they are written).

   If you insert the option `--application' in front of the image file
name, you will get an image that uses the `--appl-image' option instead
of the `--image-file' option (*note Invoking Gforth::). When you
execute such an image on Unix (by typing the image name as command),
the Gforth engine will pass all options to the image instead of trying
to interpret them as engine options.

   If you type `gforthmi' with no arguments, it prints some usage
instructions.

   There are a few wrinkles: After processing the passed options, the
words `savesystem' and `bye' must be visible. A special doubly indirect
threaded version of the `gforth' executable is used for creating the
non-relocatable images; you can pass the exact filename of this
executable through the environment variable `GFORTHD' (default:
`gforth-ditc'); if you pass a version that is not doubly indirect
threaded, you will not get a fully relocatable image, but a
data-relocatable image (because there is no code address offset). The
normal `gforth' executable is used for creating the relocatable image;
you can pass the exact filename of this executable through the
environment variable `GFORTH'.


File: gforth.info,  Node: cross.fs,  Prev: gforthmi,  Up: Fully Relocatable Image Files

`cross.fs'
----------

   You can also use `cross', a batch compiler that accepts a Forth-like
programming language (*note Cross Compiler::).

   `cross' allows you to create image files for machines with different
data sizes and data formats than the one used for generating the image
file. You can also use it to create an application image that does not
contain a Forth compiler. These features are bought with restrictions
and inconveniences in programming. E.g., addresses have to be stored in
memory with special words (`A!', `A,', etc.) in order to make the code
relocatable.


File: gforth.info,  Node: Stack and Dictionary Sizes,  Next: Running Image Files,  Prev: Fully Relocatable Image Files,  Up: Image Files

Stack and Dictionary Sizes
==========================

   If you invoke Gforth with a command line flag for the size (*note
Invoking Gforth::), the size you specify is stored in the dictionary.
If you save the dictionary with `savesystem' or create an image with
`gforthmi', this size will become the default for the resulting image
file. E.g., the following will create a fully relocatable version of
`gforth.fi' with a 1MB dictionary:

     gforthmi gforth.fi -m 1M

   In other words, if you want to set the default size for the
dictionary and the stacks of an image, just invoke `gforthmi' with the
appropriate options when creating the image.

   Note: For cache-friendly behaviour (i.e., good performance), you
should make the sizes of the stacks modulo, say, 2K, somewhat
different. E.g., the default stack sizes are: data: 16k (mod 2k=0); fp:
15.5k (mod 2k=1.5k); return: 15k(mod 2k=1k); locals: 14.5k (mod
2k=0.5k).


File: gforth.info,  Node: Running Image Files,  Next: Modifying the Startup Sequence,  Prev: Stack and Dictionary Sizes,  Up: Image Files

Running Image Files
===================

   You can invoke Gforth with an image file image instead of the
default `gforth.fi' with the `-i' flag (*note Invoking Gforth::):
     gforth -i image

   If your operating system supports starting scripts with a line of the
form `#! ...', you just have to type the image file name to start
Gforth with this image file (note that the file extension `.fi' is just
a convention). I.e., to run Gforth with the image file image, you can
just type image instead of `gforth -i image'.  This works because every
`.fi' file starts with a line of this format:

     #! /usr/local/bin/gforth-0.4.0 -i

   The file and pathname for the Gforth engine specified on this line is
the specific Gforth executable that it was built against; i.e. the value
of the environment variable `GFORTH' at the time that `gforthmi' was
executed.

   You can make use of the same shell capability to make a Forth source
file into an executable. For example, if you place this text in a file:

     #! /usr/local/bin/gforth
     
     ." Hello, world" CR
     bye

and then make the file executable (chmod +x in Unix), you can run it
directly from the command line. The sequence `#!' is used in two ways;
firstly, it is recognised as a "magic sequence" by the operating
system(1) secondly it is treated as a comment character by Gforth.
Because of the second usage, a space is required between `#!' and the
path to the executable (moreover, some Unixes require the sequence `#!
/').

   The disadvantage of this latter technique, compared with using
`gforthmi', is that it is slightly slower; the Forth source code is
compiled on-the-fly, each time the program is invoked.

`#!'       -         gforth       ``hash-bang''
   An alias for `\'

   ---------- Footnotes ----------

   (1) The Unix kernel actually recognises two types of files:
executable files and files of data, where the data is processed by an
interpreter that is specified on the "interpreter line" - the first
line of the file, starting with the sequence #!. There may be a small
limit (e.g., 32) on the number of characters that may be specified on
the interpreter line.


File: gforth.info,  Node: Modifying the Startup Sequence,  Prev: Running Image Files,  Up: Image Files

Modifying the Startup Sequence
==============================

   You can add your own initialization to the startup sequence through
the deferred word `'cold'. `'cold' is invoked just before the
image-specific command line processing (i.e., loading files and
evaluating (`-e') strings) starts.

   A sequence for adding your initialization usually looks like this:

     :noname
         Defers 'cold \ do other initialization stuff (e.g., rehashing wordlists)
         ... \ your stuff
     ; IS 'cold

   You can make a turnkey image by letting `'cold' execute a word (your
turnkey application) that never returns; instead, it exits Gforth via
`bye' or `throw'.

   You can access the (image-specific) command-line arguments through
the variables `argc' and `argv'. `arg' provides convenient access to
`argv'.

   If `'cold' exits normally, Gforth processes the command-line
arguments as files to be loaded and strings to be evaluated.  Therefore,
`'cold' should remove the arguments it has used in this case.

`'cold'       -         gforth       ``tick-cold''

`argc'       - addr         gforth       ``argc''
   `Variable' - the number of command-line arguments (including the
command name).

`argv'       - addr         gforth       ``argv''
   `Variable' - a pointer to a vector of pointers to the command-line
arguments (including the command-name). Each argument is represented as
a C-style string.

`arg'       n - addr count         gforth       ``arg''
   Return the string for the nth command-line argument.


File: gforth.info,  Node: Engine,  Next: Binding to System Library,  Prev: Image Files,  Up: Top

Engine
******

   Reading this chapter is not necessary for programming with Gforth. It
may be helpful for finding your way in the Gforth sources.

   The ideas in this section have also been published in Bernd Paysan,
`ANS fig/GNU/??? Forth' (in German), Forth-Tagung '93 and M. Anton
Ertl, `A Portable Forth Engine
(http://www.complang.tuwien.ac.at/papers/ertl93.ps.Z)', EuroForth '93.

* Menu:

* Portability::
* Threading::
* Primitives::
* Performance::


File: gforth.info,  Node: Portability,  Next: Threading,  Prev: Engine,  Up: Engine

Portability
===========

   An important goal of the Gforth Project 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 is 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
(*note Extensions to the C Language Family: (gcc.info)C Extensions.).
Its labels as values feature (*note Labels as Values: (gcc.info)Labels
as Values.) makes direct and indirect threading possible, its `long
long' type (*note Double-Word Integers: (gcc.info)Long Long.)
corresponds to Forth's double numbers(1). 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.

   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 (*note Variables in
Specified Registers: (gcc.info)Explicit Reg Vars.) to improve the speed
on some machines. They are turned on by using the configuration flag
`--enable-force-reg' (`gcc' switch `-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
`-DFORCE_REG' is not used.

   ---------- Footnotes ----------

   (1) Unfortunately, long longs are not implemented properly on all
machines (e.g., on alpha-osf1, long longs are only 64 bits, the same
size as longs (and pointers), but they should be twice as long
according to *note Double-Word Integers: (gcc.info)Long Long.). So, we
had to implement doubles in C after all. Still, on most machines we can
use long longs and achieve better performance than with the emulation
package.


File: gforth.info,  Node: Threading,  Next: Primitives,  Prev: Portability,  Up: Engine

Threading
=========

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

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

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

   Of course we have packaged the whole thing neatly in macros called
`NEXT' and `NEXT1' (the part of `NEXT' after fetching the cfa).

* Menu:

* Scheduling::
* Direct or Indirect Threaded?::
* DOES>::


File: gforth.info,  Node: Scheduling,  Next: Direct or Indirect Threaded?,  Prev: Threading,  Up: Threading

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 `+'
implemented as
     n=sp[0]+sp[1];
     sp++;
     sp[0]=n;
     NEXT;
   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 `gcc' we used would not know it even if
it was possible), 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 several parts: `NEXT_P0',
`NEXT_P1' and `NEXT_P2'). `+' now looks like:
     NEXT_P0;
     n=sp[0]+sp[1];
     sp++;
     NEXT_P1;
     sp[0]=n;
     NEXT_P2;

   There are various schemes that distribute the different operations of
NEXT between these parts in several ways; in general, different schemes
perform best on different processors.  We use a scheme for most
architectures that performs well for most processors of this
architecture; in the furture we may switch to benchmarking and chosing
the scheme on installation time.


File: gforth.info,  Node: Direct or Indirect Threaded?,  Next: DOES>,  Prev: Scheduling,  Up: Threading

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 (`-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 (*note 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.
Therefore, even porting direct threading to a new machine requires
little effort.

   The default threading method is machine-dependent. You can enforce a
specific threading method when building Gforth with the configuration
flag `--enable-direct-threaded' or `--enable-indirect-threaded'. Note
that direct threading is not supported on all machines.


File: gforth.info,  Node: DOES>,  Prev: Direct or Indirect Threaded?,  Up: Threading

DOES>
-----

   One of the most complex parts of a Forth engine is `dodoes', i.e.,
the chunk of code executed by every word defined by a
`CREATE'...`DOES>' pair. The main problem here is: How to find the
Forth code to be executed, i.e. the code after the `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 and for
direct threading on some machines. Leaving a cell unused in most words
is a bit wasteful, but on the machines we are targeting 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 (direct threaded systems require two-cell code fields on many
machines).

   The other approach is that the code field points or jumps to the cell
after `DOES>'. In this variant there is a jump to `dodoes' at this
address (the `DOES>'-handler). `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 `dodoes' after the `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 used up by the jump to the code address in direct threading on many
architectures, we use this approach for direct threading on these
architectures. We did not want to add another cell to the code field.


File: gforth.info,  Node: Primitives,  Next: Performance,  Prev: Threading,  Up: Engine

Primitives
==========

* Menu:

* Automatic Generation::
* TOS Optimization::
* Produced code::


File: gforth.info,  Node: Automatic Generation,  Next: TOS Optimization,  Prev: Primitives,  Up: Primitives

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 has 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 (`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:

Forth-name  ( stack-effect )        category    [pronounc.]
[`""'glossary entry`""']
C code
[`:'
Forth code]

   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 `+' is:
     +    ( n1 n2 -- n )   core    plus
     n = n1+n2;

   This looks like a specification, but in fact `n = n1+n2' is C code.
Our primitive generation tool extracts a lot of information from the
stack effect notations(1): 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 `+' looks like this:

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

   This looks long and inefficient, but the GNU C compiler optimizes
quite well and produces optimal code for `+' on, e.g., the R3000 and the
HP RISC machines: Defining the `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 `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 `prims2x.fs':
The compiler does not optimize code away that stores a stack item to
the place where it just came from (e.g., `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 `?dup', but also words that do not (always) fall
through to `NEXT'.

   ---------- Footnotes ----------

   (1) 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.


File: gforth.info,  Node: TOS Optimization,  Next: Produced code,  Prev: Automatic Generation,  Up: Primitives

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 in1...inx `--' out1...outy, keeping the
top n items in registers
   * is better than keeping n-1 items, if x>=n and y>=n, due to fewer
     loads from and stores to the stack.

   * is slower than keeping n-1 items, if x<>y and x<n and y<n, due to
     additional moves between registers.

   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 `?branch',
constants, variables, literals and `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 `-DUSE_TOS'. `TOS' in the C
code for `+' is just a simple variable name in the one-item case,
otherwise it is a macro that expands into `sp[0]'. Note that the GNU C
compiler tries to keep simple variables like `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 (`-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 `sp[0]' by
`TOS' is not sufficient. There are some special cases to consider:
   * In the case of `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.

   * Primitives with stack effects of the form `--' out1...outy must
     store the TOS to the stack at the start.  Likewise, primitives
     with the stack effect in1...inx `--' must load the TOS from the
     stack at the end. But for the null stack effect `--' no stores or
     loads should be generated.


File: gforth.info,  Node: Produced code,  Prev: TOS Optimization,  Up: Primitives

Produced code
-------------

   To see what assembly code is produced for the primitives on your
machine with your compiler and your flag settings, type `make engine.s'
and look at the resulting file `engine.s'.  Alternatively, you can also
disassemble the code of primitives with `see' on some architectures.

