© Copyright 1989,
Philip Koopman,
All Rights Reserved.
Stack Computers: the new wave
© Copyright 1989,
Philip Koopman,
All Rights Reserved.
Chapter 3. Multiple-stack, 0-operand Machines
Since the majority of modern stack machines have their roots in the Forth programming language, an introduction to the terms of this language is in order.
The Forth programming language was invented by Charles Moore for control of telescopes in observatories using small computers (Moore 1980). Because of its roots, Forth stresses efficiency, compactness, flexible and efficient hardware/software interaction. At the same time, Forth is sufficiently powerful that it can and has been used for a large variety of general purpose programming tasks including: database management, accounting software, word processors, graphics, expert systems, and scientific computations. Appendix B contains a glossary of the primitive operations in the Forth language.
Some of the advantages of programming in the Forth language include ease of program modification and debugging, extreme flexibility, a very quick compile/edit/test cycle, high portability across a wide variety of machines, and compact source and object code (Jonak 1986). Kogge (1982) describes threaded code software environments, with an emphasis on the underlying mechanisms of the Forth language.
In order to solve the original telescope control problem, Forth needed several important qualities. It had to be suitable for real time control, highly interactive for easy use by non-programmers, and had to fit within severe memory space constraints.
From these origins, the language took on two major features: the use of threaded code, and 0-operand stack instructions. In order to conceptualize the operation of the language, the Forth virtual machine is used as a model for computation. The Forth virtual machine has two stacks: a data stack and a return stack. Forth programs are actually an emulation of MS0 machine code running on the host hardware. Forth programs consist of very small subroutines that execute only calls to other subroutines and primitive stack operation instructions. Programs are built in a tree-like fashion, with each subroutine calling upon a small collection of underlying subroutines.
It is easy to see that Forth is a natural machine language for 0-operand stack hardware as exemplified by the Canonical Stack Machine.
It should be noted that even if a processor is designed as a Forth processor, it is still capable of executing any other high level language. This is because the primitives of the Forth language are defined at a very low level, and correspond to the machine code operations that would have to be present in any stack machine. Thus, a machine that is advertised as a "Forth machine" is usually suitable for running other languages as well.
The primitives of the Forth language include all the operations of the Canonical Stack Machine listed in Table 3.1. All the operations names not enclosed by `[...]' correspond exactly to Forth function names.
The bracketed names [IF], [CALL], [EXIT] and [LIT] correspond to internal Forth functions that are automatically compiled to support programs. For example, [IF] would be compiled to perform a conditional branch when the Forth construct IF ... THEN is encountered. [CALL] would be compiled anytime a reference to a Forth word that it not a machine primitive operation is encountered. [EXIT] is compiled by the ; at the end of a Forth definition and by the word EXIT. Finally, [LIT] would be compiled every time a literal value such as 1234 is encountered in a program.
Several Forth constructions such as LOOP, variables, and constants are not directly supported by the Canonical Stack Machine, but can be synthesized from simpler operations. Obviously, an efficient Forth language computer will have direct support for all frequently used Forth structures.
The main characteristic of Forth programs that separates Forth from most other languages is the high frequency of subroutine calls. Good Forth programming style encourages incremental program development and testing with small subroutines. Subroutines often only consist of 5 or 10 instructions. A static frequency of approximately 50% of the instructions being subroutine calls is considered normal.
This kind of software environment allows extraordinarily rapid and accurate program construction, and is especially effective in environments with limited memory capacity. It also encourages the use of machines with fast subroutine calls.
A major advantage of the Forth programming language is that it provides an unprecedented level of interactivity in its development environment. The development tools include an integrated incremental compiler and editor which allow interactive testing and modification of individual procedures. The encouragement for writing small procedures and modular code allows easy and fast testing during development, with a greatly reduced need for fixing words after they are first written. The consensus among Forth programmers is that use of the Forth language reduces development time by a factor of 10 compared to other languages over a wide range of applications.
Forth programs tend to emphasize flexibility for problem solving. Since Forth is an extensible language, new data and control structures may be added to the language to support specific application areas. This flexibility allows one or two programmers to solve a problem that might require a larger team effort in other languages, reducing project management overhead and thus magnifying the productivity increase. Forth has not been used extensively in extremely large programming efforts, so its effectiveness in very large applications is as yet unknown.
Phil Koopman --
koopman@cmu.edu
NEXT SECTION