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

greg@utcsri.UUCP (Gregory Smith) (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.

Some DEC pdp-11 FORTRAN compilers do this too, usually as an option.
For those interested, I will try to show the mechanics of this:

Suppose the program is

	I=1
	K=350
	J=J+1
	A=B
	CALL FOO

The compiled output would be:
	.WORD	MOI$1M,I	; move-int-1-to-mem
	.WORD	MOI$IM,350,K	; move-int-immediate-to-mem
	.WORD	ADI$1M,J	; add-int-1 to mem
	.WORD	MOF$MM,A,B	; move-float-mem-to-mem
	.WORD	CAL$,FOO	; call foo.

There were a *lot* of operations defined, as you can imagine.
This is executed with R4 pointing to the above list of words. The
routines used are as follows ( more or less)
MOI$1M:	MOV	#1,@(R4)+
	JMP	@(R4)+
MOI$IM:	MOV	(R4)+,@(R4)+
	JMP	@(R4)+
ADI$1M:	INC	@(R4)+
	JMP	@(R4)+
MOF$MM:	MOV	(R4)+,R0	; get source
	MOV	(R4)+,R1	; dest
	MOV	(R0)+,(R1)+	; move one word
	MOV	(R0),(R1)	; move the other
	JMP	@(R4)+
CAL$:	MOV	(R4)+,R0	; get subr. address
	MOV	R4,-(SP)	; save threaded PC
	JSR	PC,(R0)		; call it
	MOV	(SP)+,R4	; get R4 back
	JMP	@(R4)+

Thanks to JMP @(R4)+ the threading overhead is minimal. However, for
integer operations, this overhead is almost half of the instructions
executed.  The win comes with floating point stuff, especially double
prec. and complex. The complex multiply A=B*C  can be done by

	.WORD	MOC$MS,B	; mov-cplx mem to stack
	.WORD	MUC$MS,C	; mul-cplx mem to stack
	.WORD	MOC$SM,A	; mov-cplx stack to mem.

Of course, the advantage is only in code size. ( the definitions of
MOC$MS, MUC$MS and MOC$SM are left as an exercise for the reader :-) )
Another interesting point is that JMP @(R4)+ does not modify condition
codes, so comparison routines like CMI$MI ( CMP @(R4)+,(R4)+/ JMP @(R4)+)
can set condition codes, to be used by a conditional threaded branch
( which does either MOV (R4),R4 if the branch is taken or TST (R4)+ if not).
This would not be possible on, say, an 8080, where the code to go to
the next handler would be fairly long and would trash the c. codes.

Sorry for those of you who don't read PDP-11. A 68K can't do anything
like JMP @(R4)+. It would have to do something like this at the end of
each handler:
	MOVA.L	(A6)+,A0	; get next in A0
	JMP	(A0)		; go do it.
Condition codes are still unaffected, but the threading overhead is
now that much bigger.
All of this is from memory, so I may have spelled a few of the threaded
names wrong.
This method can obviously be used by any language, and is especially
attractive on horrible CPUs like the 6502 where in-line code is
impractical (no 16-bit regs, except PC :-( )

-- 
"Shades of scorpions! Daedalus has vanished ..... Great Zeus, my ring!"
----------------------------------------------------------------------
Greg Smith     University of Toronto      UUCP: ..utzoo!utcsri!greg

elg@usl.UUCP (Eric Lee Green) (06/18/86)

In article <634@ucbcad.BERKELEY.EDU> keppel@pavepaws.UUCP (David Keppel) 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

I'm not really a FORTH expert, just a sometime user who's written a
couple of little things in FORTH, but:

Subroutines are composed of a list of subroutine addresses... each
subroutine address corresponds to one FORTH word. Or, a subroutine is
composed of ML. To execute a subroutine, there's two choices:

If it's an assembly language (ML) subroutine, directly execute it.
Only a few routines at the very bottom of the pile are written in ML,
mostly things like "+", "-", etc.

If it's a list of subroutine addresses, execute the individual
subroutines in that list, in the same way as above (i.e., recurse).

Needless to say, there's several ways to thread subroutines. A really
fast implementation is to just make the list of subroutine addresses a
ML list of subroutine calls. However, on a small computer like a 6502,
that takes 3/2 more space of just storing the addresses. On a VAX I
wouldn't care, on a C-64, well... The method commonly used is to have
an inner interpreter which fetches an address from the list of
addresses, looks at the header at that address to detirmine if it's an
ML or address list, and if it's a ML routine do a jsr to it, else
stack the pseudo-interpreter's current "program counter" and jump back
to the beginning of the list.

For things like branches and loops, what the called code does is alter
the return address on the interpreter address stack, or just pop the
address stack to the interpreter address counter (= a "return" in
threaded code).

And that's how that's done. It's probably about 30% slower than
writing it in assembly language, because of all the overhead. On the
other hand, it's extremely compact code, and fits the FORTH language very
well.

Why doesn't any other language use it? Traditionally, FORTH has been
run on machines with extremely small main memory stores, where the
memory savings was more than worth the overhead of going to a threaded
interpreter. Compilers for large machines haven't had to worry about
such things, plus the large machine's architecture is more fitted to
compact compiler output. It's interesting to note that almost every
compiler I've seen for 6502 machines produces a P-Code-like code,
which is executed in a similiar fashion (the P-Code interpreter
interprets the P-Code as an index into a list of addresses to which it
then does a jmp).
-- 
Computing from the Bayous,
       Eric Green {akgua,ut-sally}!usl!elg
            (Snail Mail P.O. Box 92191, Lafayette, LA 70509)

rb@ccird1.UUCP (Rex Ballard) (06/20/86)

In article <2199@peora.UUCP> jer@peora.UUCP (J. Eric Roskos) writes:
>> When coding in Forth, you do all the coding in the high level language
>> (and can interactively test the code).
>
>I'm not entirely sure what this has to do with net.arch, but aside from
>that, this raises an issue that's been puzzling me for several years.
>In fact, I've even written a couple of postings in the past on it, then
>usually cancelled them because the question was so ambiguous.
>
>The question is, *why* is Forth described in such glowing terms, when the
>attributes that are listed as the reason for such a description are not
>particularly unusual?
>
>Thus my question... what is the real *advantage* of FORTH?

Good parts of forth:
Interactive - imagine, you don't have to go through a make/compile/assemble 
	    phase to test your code.  In fact you can experiment with a
	    few variations to find the best answers.  It completely eliminates
	    the need to "patch" in machine code.
Small -	    On a machine such as the 8085 or the 6502, a fully servicable
	    Kernal can fit in as little as 2K, including multi-tasking.
	    On a machine with a more powerful instruction set, as little
	    as 1K can be used.  For controllers and special purpose boxes,
	    or in a situation where a large kernal is not desired, this
	    is another win for forth.

Fast -	    Compared to hand-written assembler, FORTH is slow, as much as
	    4 to 10 times slower.  However compared to interpreters, and
	    compilers that lack good optimization, it is very fast, often
	    100 times faster than BASIC.  Forth is also quite easy to
	    benchmark, since you are basicly timing about 26 primitives
	    and an "inner interpreter".

Maintenence - Most forth applications are subject to frequent change without
	    notice.  Not so much bug fixes as things like "yesterday I tracked
	    one star, now I want a different one".  Robotics, Laser fusion
	    labs, and a variety of other situations can't wait three weeks
	    between runs while the enhancements are re-checked.

Modular -   Because the programmer is responsible for the parameter stack
	    large functions are seldom used.  The result is that routines
	    are build on other routines, much the way a VLSI circuit can
	    be built up from simpler circuits.  You can make a DQ flipflop
	    with just a few gates, use the macro 8 times to make a register,
	    use the register macro a few times to make bus controllers, add
	    a little "glue", and have a CPU on one chip.  Forth tends to
	    do the same thing in software.  Another advantage is that if
	    you wish to change a time-out value to tune the system, you
	    can change or expand the original definition and the "callers"
	    won't need to be "re-linked".  Obviously, an archetecture
	    with fast "calls" can easily capture the same market.

Builds/Does -This is the one novices scratch their heads over for days.
	    It is also a very powerful concept.  If I want to add subroutine
	    and call it using a macro, I could write the subroutine, then
	    write the macro.  Effectively, I would be enhancing the language.
	    Forth has a mechanism to do this for you.  This allows you to
	    build operators that define their own storage, and even perform
	    their own operations, just by referencing them.

Design Discipline/Creativity - Because forward referencing is very difficult,
	there are two basic ways to aproach a project in forth.  On is to
	have a truly complete design, in which common modules have already
	been identified, or you can "create" your way up to an incomplete
	design.  Things like "transform structure A to structure B" have
	to be done field by field, which often means that similar fields
	can use the same routines.  If the structure is complex enough,
	it may even be broken down into smaller substructures.  As a result,
	a complex record can be transformed in as little as 100 lines of
	code, where normally a 2000 line 'C' program might have been tried.
	This bottom up approach often leads to very tight "macro-level"
	designs.  If the programmer wishes, he can design his way up,
	identifying common types of data and common operations that
	could be performed on it.  This ultimately leads to an Object
	Oriented Design, almost by accident.  Forth is not an object
	oriented language, but Object Oriented Design is definitely
	a valuable skill.

Hardware functions can be done in software -  Demand paged memory, various
	   types of caching, management of various tasks, and peripheral
	   control can be efficiently done in software.  Even tricks like
	   multi-computing (each with their own ram and storage, working
	   on different parts of the problem at the same time), can be
	   almost trivial in forth.  This is often done in Robotics where
	   "fingers" and the "arm" are controlled by different processors
	   under the direction of a master processor.

Extensibility - Not only can the language be extended, but the Forth
	"operating system" can be extended as well.



Of course other languages, such as Lisp, Smalltalk, and Prolog have many
of these features (smalltalk classes are very similar to forth builds/does
clauses).  They also require powerful machines to run them effectively.
The main advantage of forth is it's "elegent simplicity".  Many of these
other languages almost look like decendants of forth.

Forth has disadvantages too:

No OBJECT modules - There is no such thing as an object code library.
	 Everything depends on the user's access to the source. Without
	 it, there is little one can do to change the system.  It is
	 possible to "decompile" the object, but the source must be
	 reloaded.  Object can be saved as a whole unit, but not in
	 loadable pieces.  Some Forths are able to do this, but
	 the tradeoffs are efficiency and memory size.

No OBJECT level portability - Although the source code to a forth
	 application can be made to run on practically any machine,
	 everything, including the kernal must also be loaded.  Any
	 Operating System vectors are unique to the system.

Organization - There is almost no organization and little documentation
	 to a standard forth Kernal.  You can do a "vlist" and every
	 word it knows about spews out, in the order of definition.
	 Source is organized in terms of "screens", which makes things
	 easy to read, but requires a good associative memory on the
	 part of the programmer.  Here Smalltalk or NEON are ultimately
	 better.

Information - Since there are no libraries in forth, and most people
	have little desire to give away source to their favorite
	utilities, the wheel is often re-invented, or at least
	hand entered.  You can get some utilities via compuserve
	and various bulletin boards, but the good stuff, like
	animation graphics are well protected from telephones.
	Rumor has it that Atari and Activision have some of the
	best forth libraries.

Religion - Forth programmers defend their language like fundamentalist
	preachers defend the "7 day creation".  Infix notation, parameter
	management, class definitions, object oriented design, hierarchal
	"definition directories", and "standard entry points" have all
	been proposed, and rejected.  It took 4 years for the '83 standard
	to accept the existance of DTL's and STL's, which run 8 to 50 times
	faster than the '79 standard on some machines (not all, but some).
	Many valuable contributions to general languages are made by people
	who get "fed up" with the forth camp and create their own languages.
	NEON is a good example.

Archetecture - Any machine which can support the incredible depth of calls
	generated by forth, could also run other languages almost as quickly.
	Forth is usually used to hide the archetectural deficencies of the
	host chip, this is what makes it so popular on 8080's and 6502's,
	but a "toy language" on 8086's and 68K's.

Advantages are better elsewhere -  You can get all the advantages of a
	Forth language in assembler.  Just write the primitives as calls.
	You can even eliminate the "load register" instructions.  You
	sacrifice the interactive nature, but a good symbolic debugger
	will give you that.


Summary:
	Anyone who is designing system level archetectures, operating systems,
	or languages, and has not looked at forth, should spend about as long
	with that "system" as they spent in the learning stages of C and Unix,
	say a month or two, working in forth on an "El Cheapo" computer like
	an Atari or a C-64, preferably doing something like "McPaint in Forth"
	or some similarly trivial task involving graphics.  You can almost
	write your own forth in about three months (part time) just by reading
	Brodie.

	FORTH isn't a panacea, it's more of a Pandora's Box, but there are
	some good principles, concepts, and disciplines that can greatly
	increase your effectiveness as a software (or hardware) engineer.
	It is also a veritable Gold Mine of ideas, but to get to the gold,
	you've gotta move some dirt.