[net.lang] RRe: What's so good about FORTH?

philm@astroatc.UUCP (Phil Mason) (06/16/86)

In article <634@ucbcad.BERKELEY.EDU> keppel@pavepaws.UUCP (David Keppel) writes:
>In article <432@astroatc.UUCP> philm@astroatc.UUCP (Phil Mason) writes:
>>* small size : theaded-code is about a small as you can get.
>
>Pardon, but I've never quite understood what threaded-code is.
>Could somebody give me an explanation of
>	o what it is
>	o why it is fast
>	o why other major languages don't use it or don't admit to using it
>

Threaded code is a interesting concept. If you have an algorithm, and express
the algorithm with nothing but subroutine calls, one could say that the code
is threaded. In FORTH, the subroutine calls are implicit. In a high-level
(non-assembly language) routine, a list of the addresses of all of the 
component operations, in the proper order, is sufficient to describe the
operation of the routine.

Threaded code is not by its nature fast. It is amazingly compact, however.
Speed is determined by the qualities of the threaded code interpreter and
the processor on which the interpreter runs. If subroutine calls are very
expensive time-wise on the processor, threaded code will REALLY gum up the
works.

FORTH appears to be the only major language that uses threaded code as the
primary means of expressing algorithms internally. Other languages and
applications do use threaded code but by no means even close to the extent
that FORTH does. Threaded code is used for compactness and simplicity.

- -

-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Kirk  : Bones ?                |  Phil Mason, Astronautics Technical Center
Bones : He's dead Jim.         |  Madison, Wisconsin - "Eat Cheese or Die!"
- - - - - - - - - - - - - - - -|  
...seismo-uwvax-astroatc!philm |  I would really like to believe that my
...ihnp4-nicmad/               |  employer shares all my opinions, but . . . 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

ark@alice.UucP (Andrew Koenig) (06/17/86)

> FORTH appears to be the only major language that uses threaded code as the
> primary means of expressing algorithms internally. Other languages and
> applications do use threaded code but by no means even close to the extent
> that FORTH does. Threaded code is used for compactness and simplicity.

Have a look at the Spitbol compilers sometime.

steve@jplgodo.UUCP (Steve Schlaifer x43171 156/224) (06/17/86)

In article <634@ucbcad.BERKELEY.EDU>, keppel@pavepaws.berkeley.edu (David Keppel) writes:
> [ Summary: What is threaded code? ]

Essentially, threaded code consists of a long series of subroutine calls.
In a threaded code implementation, the implementor writes some primitive words
that actually use the machine instructions to perform the kernal operations
needed.  On top of this layer, the remaining (high level) words required to
complete the language implementation are written as a series of calls to
other words (either high level or primitive).  In either direct or indirect
threading, these calls are represented as just the address of the start of
the code for the word to be executed (primitive word) or code needed to
nest the interpretor down a level (high level word).  A part of the threaded
language system called the inner interpretor picks up each address in turn
and then jumps to the code to be executed.  The last operation performed in
a word is usually a branch back to the inner interpretor.

The compactness of threaded code comes from only needing 2 bytes to cause
any word in the dictionary to be executed no matter how complex the operation
actually is.  Further, if the language is extensible like Forth, then any
application specific sequence of operations that is going to be
used frequently, can be added to the language and thereafter represented
in the dictionary as just a 2 byte code address.

A good book on threaded code is Threaded Interpretive Languages published
by Byte Books.  Also, Leo Brodie's book on Forth (I think it's called 
Starting Forth) has some good discussion of threading.
-- 

...smeagol\			Steve Schlaifer
......wlbr->!jplgodo!steve	Advance Projects Group, Jet Propulsion Labs
....group3/			4800 Oak Grove Drive, M/S 156/204
				Pasadena, California, 91109
					+1 818 354 3171

philm@astroatc.UUCP (Phil Mason) (06/18/86)

In article <5654@alice.uUCp> ark@alice.UucP (Andrew Koenig) writes:
>> FORTH appears to be the only major language that uses threaded code as the
>> primary means of expressing algorithms internally. Other languages and
>> applications do use threaded code but by no means even close to the extent
>> that FORTH does. Threaded code is used for compactness and simplicity.
>
>Have a look at the Spitbol compilers sometime.

Are these compilers real or just facetiously named? If they are real,
what's the story on them. It's news to me.



-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Kirk  : Bones ?                |  Phil Mason, Astronautics Technical Center
Bones : He's dead Jim.         |  Madison, Wisconsin - "Eat Cheese or Die!"
- - - - - - - - - - - - - - - -|  
...seismo-uwvax-astroatc!philm |  I would really like to believe that my
...ihnp4-nicmad/               |  employer shares all my opinions, but . . . 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

faustus@ucbcad.BERKELEY.EDU (Wayne A. Christopher) (06/20/86)

Maybe I'm not seeing the point about "threaded" languages -- you don't see
C programmers claiming that the major advantage of C is that you can use
function calls to build up higher-level routines out of lower ones...  Or is
it just that since forth is the first language many micro users use after
basic and asm, functions (or "words") seem like a really big thing...

	Wayne

mwm@eris.berkeley.edu (Mike (I'll be mellow when I'm dead) Meyer) (06/21/86)

In article <679@ucbcad.BERKELEY.EDU> faustus@ucbcad.BERKELEY.EDU (Wayne A. Christopher) writes:
>Maybe I'm not seeing the point about "threaded" languages -- you don't see
>C programmers claiming that the major advantage of C is that you can use
>function calls to build up higher-level routines out of lower ones...  Or is
>it just that since forth is the first language many micro users use after
>basic and asm, functions (or "words") seem like a really big thing...
>
>	Wayne

The advantage that Forth offers over C is that the programmer-defined
words look like the built-in words, and can replace them.

LISP offers the same advantage, and is more readable, to boot.

	<mike

mj@myrias.UUCP (Michal Jaegermann) (06/25/86)

>Maybe I'm not seeing the point about "threaded" languages -- you don't see
>C programmers claiming that the major advantage of C is that you can use

A fact that Forth is "threaded" is not a part of a language definition
but side-effect of the most popular implementation method.  It gives
very compact and flexible code with an ease of extensions.  The method
is far from beeing unique to Forth and there are some Forth
implementations which are not exatly "threaded".  At least not in the
sense described earlier in some response.  An extreme case is to have
the whole Forth as a huge 'case' statement in C.  (Yes, I have seen
something like that :-) ).

Michal Jaegermann
Myrias Research Corporation
Edmonton, Alberta, CANADA

philm@astroatc.UUCP (Phil Mason) (06/26/86)

In article <255@myrias.UUCP> mj@myrias.UUCP (Michal Jaegermann) writes:
>>Maybe I'm not seeing the point about "threaded" languages -- you don't see
>>C programmers claiming that the major advantage of C is that you can use
>
>A fact that Forth is "threaded" is not a part of a language definition
>but side-effect of the most popular implementation method.  It gives
>very compact and flexible code with an ease of extensions.  The method
>is far from beeing unique to Forth and there are some Forth
>implementations which are not exatly "threaded".  At least not in the
>sense described earlier in some response.  An extreme case is to have
>the whole Forth as a huge 'case' statement in C.  (Yes, I have seen
>something like that :-) ).
>

A neat concept is that Forth is a psuedo-code based system. The
inner interpreter of Forth actually handles the threaded object code. 
The raw code that makes up the outer Forth interpreter is just an application 
run on the Forth pseudo-machine (the inner interpreter). You can really
think of the innermost guts of Forth as kind of a machine language for the
portable threaded code stack machine and not be incorrect. That's one reason
why the inner interpreter can be written in any language as long as it can 
interpret the threaded code with which the outer interpreter is written.



-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Kirk  : Bones ?                |  Phil Mason, Astronautics Technical Center
Bones : He's dead Jim.         |  Madison, Wisconsin - "Eat Cheese or Die!"
- - - - - - - - - - - - - - - -|  
...seismo-uwvax-astroatc!philm |  I would really like to believe that my
...ihnp4-nicmad/               |  employer shares all my opinions, but . . . 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

lambert@mcvax.uucp (Lambert Meertens) (06/29/86)

In article <255@myrias.UUCP> mj@myrias.UUCP (Michal Jaegermann) writes:

> The fact that Forth is "threaded" is not a part of a language definition but
> side-effect of the most popular implementation method.  [...]  The method
> is far from beeing unique to Forth and there are some Forth implementations
> which are not exactly "threaded".  [...]  An extreme case is to have the
> whole Forth as a huge 'case' statement in C.  (Yes, I have seen something
> like that :-) ).

How else can you implement threading if C is used as the implementation
language?  (Or is that what the smiley is for?)  In other languages the
obvious implementation would be to have each code fragment (for interpreting
a "word") switch to the interpretation of the next word by having it end on

    goto *(IC++)

(or goto *(++IC), depending on your and your machine's taste).  But labels
are not a C type: you can only goto a constant label, not to a label
expression.  So the closest you can get--as far as I can see--is to have
this huge switch

    while (1) switch (*(IC++)) {
    case word1: ...; break;
    case word2: ...; break;
    ...;
    }

This is almost as efficient, but not quite: you loose a few cycles in the
jump taken at each break.  Also, you had better make sure that the words
are contiguous numbers so that good code is produced for the switch.
(Instead of break you can use continue.  In the assembler output of cc this
is one jump less, but compiled with -O, at least on our cc, the extra jump
is optimized away anyway and the resultant object files are identical.)

Are there other ideas on implementing threading in C?

-- 

     Lambert Meertens
     ...!{seismo,okstate,garfield,decvax,philabs}!lambert@mcvax.UUCP
     CWI (Centre for Mathematics and Computer Science), Amsterdam