| Starting date: Last revision: |
August 18, 2001 February 5, 2005 |
Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.1 or any later version published by the Free Software Foundation, with no Invariant Sections, with no Front-Cover Texts, and with no Back-Cover Texts. A copy of the license may be found at http://www.gnu.org/copyleft/fdl.html.
| 1. | Introduction | ||||||||
| 2. | The translation model | ||||||||
| 3. | ^Forth words | ||||||||
|
|||||||||
|
|||||||||
|
|||||||||
|
|||||||||
|
|||||||||
| 4. | Sample code | ||||||||
|
|||||||||
|
|||||||||
|
^Forth (pronounced "hat Forth", or "to the power Forth") is a dialect of Forth intended for automatic text translation into source for the implementation language of a normal Forth. It grew out of a set of assembly language macros dating back to mid-1991, written for the Ann Arbor macro assembler (AAma by Martinus Veltman) to run on Motorola 680x0 cpu's under a variety of operating systems.
Here is an example from that earlier scheme:
; #S ( ud -- 0 0 ) 6.1.0050
; Convert all digits of an unsigned, 64-bit number ud, adding
; each to the pictured numeric output text, until the remainder
; is zero. A single zero is added to the output string if the
; number was initially zero. Use only between <# and #>.
; "sharp-s", x79
DEF #s,numDigits
BEGIN |numDigit |over |over |or |zeroEqual |UNTIL
ENDEF
This defines numDigits as an assembly language macro that expands to a subroutine call in the target Forth, which is subroutine threaded. The "|" character is used by AAma to separate multiple assembly language statements on the same line.
Words like over are defined as assembly
language macros that expand to inline source:
; OVER ( a b -- a b a ) 6.1.1990
DEFM over,over |.MACRO over
movel 4(ps),-(ps)
.ENDM |ENDEFM over
The AAma macro pairs DEF ENDEF and DEFM ENDEFM take care of inserting the words #s and over into normal Forth word lists for use by the normal Forth interpreter and compiler.
The language thus made up out of assembly language macros was of course not interactive Forth -- it was intended for compilation only (by the assembler), in a sort of source analog to Forth target compilation. Although its syntax was a bit rough, it had some advantages:
It has long been claimed that C fulfills the role that assembly language used to. In particular, gcc, the GNU C compiler, supports many cpu's and UNIX-like systems, with pretty good optimization, and access to assembly language as needed. One could wish for something better than the usual intricate C-header environment, but maybe the problems that addresses are intrinsically complex and unavoidable.
Anyway, that's where we went. The name "^Forth" formerly referred to the system of macros described above together with the ANS Forth they helped to implement (all unpublished). Now it refers to an actual dialect of Forth, which allows mixing of C and Forth source in files interpreted by a normal Forth, with C source as output. Currently the host Forth system is pfe (Portable Forth Environment), and the C ouput links with pfe, either directly or by treating pfe as a dynamic library on systems that permit it, such as Linux and Darwin.
The translation still makes heavy use of macros. But of the natural C/UNIX analogs, it uses cpp macros only a little, and m4 macros not at all. Instead it uses text processing facilities from our Dynamic-Strings word set, ported to pfe. As a result, we are able to make the Forth part of the syntax almost completely Forth-like, with some inevitable differences due to the nature of cross compilation.
Part of the point is to give C optimization a chance to act on Forth code. Anton Ertl and Martin Maierhofer in Translating Forth to Efficient C have analyzed a number of the issues, and actually implemented a proof of concept translator called Forth2C. Some benchmark results, including comparisons to hand-coded C, can be found on Ertl's performance page, which is based on his 1996 Ph.D. dissertation, Implementation of Stack-Based Languages on Register Machines.
Our current translator produces code for a pfe loadable module. The main optimizations are:
We have some ideas for enabling more sophisticated C optimization, but maybe the scheme above, together with whatever results from the judicious inclusion of explicit C code, is good enough.
The only other Forth to C translator we have heard about is part of a quite ambitious, rule-based translator project by Rob Chapman, called Timbre. It predated Ertl and Maierhofer's work and is still actively developed. Our style of intermixing Forth and C is quite a bit like that described in Chapman's C Without C article.
Here we try to distinguish the translation model from its pfe implementation. The language in this document does assume that the output is to be C source. With small changes in wording, it could just as well have been source for some other development language (like assembly language).
The ^Forth translator converts a ^Forth source file to a C source file. The translator is written in the host Forth. In particular it defines all of the ^Forth-specific words described in this document. The translator converts the input file by interpreting it in the usual way.
^Forth, colon-like defining words do not switch to compilation state for the body of a word definition. Instead they act in a special word list context, where previously defined words in the body of the definition emit text rather than compiling code.
This kind of situation is called "scoping" in Elizabeth Rather's proposal for a cross-compiler standard. While there is an overlap between the concepts of Forth to C translation and Forth cross-compilation, it is only partial. We have two, maybe three scopes instead of four. One is analogous to HOST, and one to perhaps some combination of INTERPRETER and COMPILER. The third, consisting of the compiled and linked C code, we take to be analogous to TARGET; but since that is outside the translation process, we don't make it a formal scope. We do use the term "target" to refer to the extended host system, or the application, or even a new Forth system that results from compiling and linking the translation output.
We call the two basic scopes the "host" and "translator" scopes. The translator scope uses a translation word list, which contains redefined or new words that emit source translations, and ^Forth words which are to be invisible in host scope. We make a translation word list part of the model rather than an implementation detail, because we think it adds clarity.
^Forth files are translated mostly in translation scope.
Besides the output file itself, the translator uses two logical text streams to build the output, a definition stream and an index stream.
The definition stream starts over with each ^Forth colon-like definition. It builds the source for the corresponding C function.
The index stream is used to build C source for target dictionary entries.
How the translator combines the definition and index streams into the output file depends on how the target dictionary is implemented. If it keeps word headers and code together, the translator would intermix the index and definition streams in the output. With pfe, headers and code are separated; and the pfe translator appends the index stream onto the end of the output file in one piece.
^Forth words fall into two main categories, ^Forth-special words, and words they define. The ^Forth-special words are specified in this document. Some of them organize the structure of a ^Forth source file, and others are special defining words.
The host and translator scopes are managed by the words host[ and ]host. With the exception of these two, all of the words specified in this document are to be in the translation word list, visible in translator scope and not in host scope. These two words are used to escape to and return from the host scope, for example, to do a setup calculation or to modify the translator.
host[ ( -- )
]host ( -- )
^Forth source files have two basic sections:
A ^Forth source file gets treated in either of two ways, as the main translation file, or as an external resource for the main translation file. ^Forth defining words in the body of the file correspondingly work in one of two modes, nonexternal or external.
The main translation file loads the ^Forth files mentioned with REQUIRES in its preamble as external resources to get calling stubs, inlined source, storage references, C prototypes, etc. These are produced by the action of ^Forth defining words in external mode. External files do not load additional external resources; their preambles are simply ignored. The body of the main file produces source definitions in the normal, nonexternal mode.
This logic is handled by BEGIN-EXTERNAL and END-EXTERNAL.
BEGIN-EXTERNAL ( -- )
If the current file is an external resource for the main translation, it is being loaded in external mode. Its preamble and the immediately following END-EXTERNAL are skipped, and there is no switch to nonexternal mode in the rest of the file.
END-EXTERNAL ( -- )
BEGIN-EXTERNAL and END-EXTERNAL are the only ^Forth words that can switch between nonexternal and external modes. They are to appear exactly once in a ^Forth file.
Note that preambles do not nest, and shouldn't need to.
^Forth word definitions in the main translation file are made available for insertion into the target dictionary by MAKE-INDEX.
MAKE-INDEX ( `<name> "<title>"` -- )
This word followed by the name and quoted title must appear between END-EXTERNAL and the first ^Forth definition that is to appear in the target dictionary. Subsequent ^Forth defining words emit C code to the index stream to make the words searchable in the target dictionary.
If the current file is external, MAKE-INDEX does nothing but skip over <name> and "<title>".
In the pfe implementation, MAKE-INDEX starts a string concatenation stream for the index with a dictionary-code preamble, and sets a flag so that subsequent ^Forth defining words know to concatenate extra dictionary code to the index stream. When it reaches the end of the main translation file, the translator appends the index stream plus a dictionary postamble to the output file.
The following two words transmit literal C text up to a terminating string. The first writes directly to the output file. The second concatenates to the definition stream, which is written to the output file at the end of a definition. There are restrictions on usage.
{" ( `<text>"}` -- )
{" is not to be used inside a ^Forth definition, and is normally used only in the preamble.
c{ ( "<text>}c" -- )
c{ and the terminating }c are to be used only between def: and ;def, in particular not between defm: and ;defm.
The last sectioning word adds C-style comments to ^Forth.
/* ( "<text>*/" -- )
Note that even without this word, C-style comments inside {" "} or c{ }c pairs appear in the output. Outside of such pairs, /* is a normal Forth word that must be followed by whitespace, but */ need not be delimited by whitespace on either side.
^Forth defining words have different names than their ANS Forth counterparts. With the exception of ;def, they all parse not only a name but also a quoted label from the input stream. The label is the Forth pronunciation with underscores instead of hyphens, used to build the identifier for the corresponding C function. The quotes are just a reminder that the label comes from the pronunciation.
All ^Forth defining words except ;def have different actions in nonexternal and external mode.
def: ( `<name> "<label>"` -- )
In external mode, also write the function prototype to the output file; and skip past ;def.
In nonexternal mode, also start or restart the definition stream with the C function header; and concatenate C code to the index stream that inserts a searchable target dictionary entry, if one was started by MAKE-INDEX.
Ordinary numbers are not permitted between def: and ;def. Instead they should be predefined with constant:. "def-colon"
;def ( -- )
The reason for prohibiting ordinary numbers between def: and ;def is that they do not emit source code; they just leave their values on the data stack. It's good programming practise anyway to use named constants instead.
The next word defines words that do C inlining.
defm: ( `<name> "<label>"` -- )
In other words, when executed in translator scope, <name> concatenates the body of the definition to the definition stream. Note that the body must be C code.
In addition when the mode is nonexternal, start or restart the definition stream with the C function header (identifier based on <label>), append the body of the definition, and append the C function trailer. Also, if MAKE-INDEX started an index stream, emit to it C code that inserts a searchable target dictionary entry. Empty the definition stream into the output file, while treating the index stream, if present, as required by the target dictionary. "def-m-colon"
As stated above, any stack comment would have to be on the same line as "<label>". Maybe we should relax the starting line condition for the body of a defm: word by making a stack comment mandatory, so it could serve as a delimiter for the start of the body.
The reason for prohibiting c{ and }c between defm: and ;defm is simply that they are not C code.
The next word enables words already defined in the host system to be used in ^Forth definitions.
ext-def: ( `<name> "<label>"` -- )
Remaining are the ^Forth data-defining words. Here we use "handle the index" as a shorthand for "if MAKE-INDEX started one, emit C code to the index stream that inserts a searchable target dictionary entry, and treat it as required by the target dictionary".
constant: ( `<name> "<label>"` n -- )
In nonexternal mode, also handle the index. "constant-colon"
variable: ( `<name> "<label>"` -- )
In nonexternal mode, also write to the output file a C data declaration with identifier based on <label>; and handle the index.
In external mode, also write to the output file a C extern data declaration with identifier based on <label>. "variable-colon"
2variable: ( `<name> "<label>"` -- )
In nonexternal mode, also write to the output file an appropriate C data declaration with identifier based on <label>; and handle the index.
In external mode, also write to the output file an appropriate C extern data declaration with identifier based on <label>. "two-variable-colon"
ext-variable: ( `<name> "<label>"` -- )
Also write to the output file any C declarations required by the host implementation, with identifier based on <label>. "ext-variable-colon"
Note that any C declarations written by ext-variable: should be the same in external and nonexternal mode, because the variable in question is external to the translation process. In the pfe version, ext-variable: does not emit such declarations, because they are taken care of in a basic include generated by BEGIN-EXTERNAL.
In the pfe case, variables defined by variable: and ext-variable: have an altogether different structure. In pfe, ANS variables like BASE, along with some other variables and data structures, have a special implementation so threads can have their own copies, like user variables.
create-allot: ( `<name> "<label>"` u -- )
In nonexternal mode, also write to the output file a C data declaration with identifier based on <label>; and handle the index.
In external mode, also write to the output file a C extern data declaration with identifier based on <label>. "create-allot-colon"
Besides having two basic scopes, the specification above has introduced external and nonexternal modes. We hope this doesn't lead to the kind of problem associated with traditional state-smart words. The mode is relevant only in translator scope.
The only mode-dumb words among those specified above are the following:
host[ ]host {" c{ /* ;def
Actually ;def is a special case, since it is skipped in one mode but not the other. It is somewhat analogous to words defined by the ^Forth defining words, which get different definitions in the two modes, each one mode-dumb.
In the ANS Forth cross-compiler proposal, it is an ambiguous condition to use immediate in any but the host scope. It is also true in ^Forth that immediacy makes no sense for words in translator scope that may appear between def: and ;def. But that does not mean that immediate should not be defined in translator scope, affecting the source output to make words in the target dictionary immediate.
Here we display and comment on abbreviated extracts from two ^Forth files from our pfe implementation.
The first excerpt is from a file that adopts a number of pfe
primitives, mostly for ^Forth inlining. The pfe version of
BEGIN-EXTERNAL emits source for pfe setup that
includes def-config.h, defines some extra register
variables, and includes pfe-base.h. That defines pfe
types, defines things like SP, and provides prototypes
for pfe subroutines like mmul(). The ^Forth defining
words prepend "p4_" to the labels they parse, to
satisfy pfe.
/* ^Forth: Kernel Words
File: kernel.hf
Author: David.N.Williams@umich.edu
License: LGPL
The parts of this code not derived from PFE are
Copyright (C) 2001 by David N. Williams
*/
BEGIN-EXTERNAL
{"
#include <pfe/double-sub.h>
#include <string.h>
"}
/* No REQUIRES. */
END-EXTERNAL
MAKE-INDEX app "Kernel Word Set"
decimal
\ *** System Variables
\ CORE
ext-variable: >in "TO_IN"
ext-variable: base "BASE"
\ FIG
ext-variable: csp "CSP"
\ *** Constants
\ CORE EXT
-1 constant: true "true"
0 constant: false "false"
\ COMMON
defm: cell "cell" ( -- PFE_SIZEOF_CELL )
*--SP = PFE_SIZEOF_CELL; ;defm
defm: -cell "minus_cell" ( -- -PFE_SIZEOF_CELL )
*--SP = -PFE_SIZEOF_CELL; ;defm
\ *** Glossary
\ Many of these primitives are copied from pfe.
\ FIG
defm: !csp "store_csp" ( -- )
p4_CSP = SP;
;defm
\ CORE
defm: ! "store" ( n addr -- )
*(p4cell *) SP[0] = SP[1]; SP += 2;
;defm
defm: @ "fetch" ( addr -- n )
*SP = *(p4cell *) *SP;
;defm
defm: * "star" ( n1 n2 -- n )
SP[1] = SP[1] * SP[0]; SP += 1;
;defm
defm: */ "star_slash" ( n1 n2 n3 -- n4 )
*(fdiv_t *) &SP[0] =
p4_d_fmdiv (p4_d_mmul (SP[2], SP[1]), SP[0]);
SP[2] = SP[0]; SP += 2;
;defm
If the word */ were to be used in a high-level def: word in another ^Forth file, that file would need an explicit "#include <pfe/double-sub.h>" statement, besides "REQUIRES kernel.hf", in its preamble, to get the pfe prototypes for p4_d_fmdiv() and p4_d_mmul(), since preambles don't nest.
The second excerpt is the prime number benchmark from a
^Forth version of the Gforth collection of four traditional
benchmarks. It illustrates higher level definitions, and a
couple of specialized uses of c{ and
}c to mix C and Forth code in such definitions.
More discussion follows the code.
/* ^Forth: Gforth Benchmarks
File: gfbench.hf
Derived by: david.n.williams@umich.edu
License: Public Domain (We're guessing that includes
the original benchmark codes.)
*/
BEGIN-EXTERNAL
{"
/* No extra include's. */
"}
REQUIRES kernel.hf
END-EXTERNAL
\ debug
\ ext-def: .s "dot_s"
MAKE-INDEX app "Gforth Benchmarks Word Set"
/* *** siev.fs *** */
\ : SECS TIME&DATE SWAP 60 * + SWAP 3600 * + NIP NIP NIP ;
\ CREATE FLAGS 8190 ALLOT
8190 create-allot: flags "flags"
8190 constant: #flags "sharp_flags" \ for primes up to 16,384
\ FLAGS 8190 + CONSTANT EFLAG
variable: eflag "eflag"
def: primes "primes" ( -- #primes )
flags #flags one fill zero three ( #primes odd)
eflag @ flags
DO ( #primes odd) i c@
IF ( prime) dup i + ( hole) dup eflag @ <
IF ( hole) eflag @ swap
DO zero i c! ( prime) dup +LOOP
ELSE ( hole) drop
THEN ( #primes prime) swap 1+ swap
THEN ( odd) two +
LOOP ( odd) drop ( #primes)
;def
/* This is intended to be a fairly direct translation
of PRIMES above.
*/
def: cprimes "c_primes" ( -- #primes )
c{
int primes = 0, odd = 3;
char *p = (char *) &flags, *q = (char *) eflag, *r;
memset (p, 1, sharp_flags);
while (p < q){
if (*p){ /* odd is prime */
/* *--SP = odd; }c . c{ */ /* print primes for debug */
r = p + odd;
if (r < q){
while (r < q){
*r = 0; r += odd;}}
primes += 1;}
odd += 2; p++;}
*--SP = primes;
}c ;def
1000 constant: #iters "sharp_iters"
\ 1 constant: #iters "sharp_iters" \ debug
def: benchmark "benchmark" ( -- )
zero #iters zero DO primes nip LOOP ;def
def: cbenchmark "c_benchmark" ( -- )
zero #iters zero DO cprimes nip LOOP ;def
\ SECS BENCHMARK . SECS SWAP - CR . .( secs)
def: sieve-main "sieve_main" ( -- )
flags #flags + eflag !
benchmark ( . ) drop
;def
def: csieve-main "c_sieve_main" ( -- )
flags #flags + eflag !
cbenchmark ( . ) drop
;def
The examples above of C/Forth mixing within a definition are degenerate cases, where all or nearly all of the code is C. Note the debugging line near the middle of cprimes. When not commented out, it illustrates how to mix C and Forth in the same definition, albeit with only one word of Forth.
The words zero, one, and three in primes are defined with constant: in kernel.hf.
The word cprimes is a pretty direct, hand-coded C translation of primes which should nevertheless optimize pretty well. We've done that for all four traditional benchmarks, so we could compare pfe, Gforth, ^Forth, and pure C execution times. The complete file and results for a Macintosh OS X system are included in our Forth archive.
Ertl and Maierhofer included hand-coded C versions of the Gforth benchmarks in their earlier Forth2C studies.
Finally, here is an excerpt from the bubble sort benchmark
in gfbench.hf to illustrate the use of
host[ and ]host:
\ 6000 constant elements ( -- int)
6000 constant: elements "elements"
\ align create list elements cells allot
host[ 6000 cells ]host create-allot: list "list"
We could not do this in translator scope, because cells is defined in kernel.hf to emit C source.