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.