«previous next»

TABLE OF CONTENTS

Abstract & Authors

1. Chuck Moore's Programming Language

1.2 Philosophy and Goals

2. Development and Dissemination

3. Forth Without Chuck Moore

4. Hardware Implementations of Forth

5. Present and Future Directions

6. A Posteriori Evaluation

References

Addenda

Also in: Croatian (Hrvatski)

2 Development and Dissemination

By the early 1970's, Forth had reached a level of maturity that not only enabled it to be used in significant applications, but that attracted the attention of other programmers and organizations. Responding to their needs, Moore implemented it on more computers and adapted it to handle ever larger classes of applications.

2.1 Forth at NRAO

Moore developed the first complete, stand-alone implementation of Forth in 1971 for the 11-meter radio telescope operated by the National Radio Astronomy Observatory (NRAO) at Kitt Peak, Arizona. This system ran on two early minicomputers (a 16 KB DDP-116 and a 32 KB H316) joined by a serial link. Both a multiprogrammed system and a multiprocessor system (in that both computers shared responsibility for controlling the telescope and its scientific instruments), it was responsible for pointing and tracking the telescope, collecting data and recording it on magnetic tape, and supporting an interactive graphics terminal on which an astronomer could analyze previously recorded data. The multiprogrammed nature of the system allowed all these functions to be performed concurrently, without timing conflicts or other interference.

The system was also unique for that time in that all software development took place on the minis themselves, using magnetic tape for source. Not only did these Forth systems support application development, they even supported themselves. Forth itself was written in Forth, using a "metacompiler" to generate a new system kernel when needed.

To place these software capabilities in context, it's important to realize that manufacturer-supplied system software for these early minicomputers was extremely primitive. The main tools were cross assemblers and FORTRAN cross compilers running on mainframes (although the FORTRAN cross compilers were too inefficient to do anything complex, given the tiny memories on the target machines). On-line programming support was limited to assemblers loaded from paper tape, with source maintained on paper tape. Digital Equipment Corp. had just announced its RT-11 OS for its PDP-11 line, which offered limited foreground-background operation; no form of concurrency was available for the H316 family. Multiuser operation of the sort that enabled NRAO's astronomers to graphically analyze data while an operator controlled the telescope and live data was flowing in, was unheard-of.

Edward K. Conklin, head of the Tucson division of NRAO which operated the 11-meter telescope, found it difficult to maintain the software since Moore was based at NRAO's headquarters in Charlottesville, VA. So in 1971 he brought in Elizabeth Rather, a systems analyst at the University of Arizona, to provide local support on a part time basis. Rather was appalled to find this critical system written in a unique language, undocumented and known to only one human. Her instinctive reaction was to re-write the whole thing in FORTRAN to get it under control. Alas, however, there was neither time nor budget for this, so she set out to learn and document the system as best she could.

After about two months, Rather began to realize that something extraordinary was happening: despite the incredibly primitive nature of the on-line computers, despite the weirdness of the language, despite the lack of any local experts or resources, she could accomplish more in the few hours she spent on the Forth computers once a week than the entire rest of the week when she had virtually unlimited access to several large mainframes.

She wondered why. The obvious answer seemed to lie in the interactive nature of Forth. The programmer's attention is never broken by the procedural overhead of opening and closing files, loading and running compilers, linkers, loaders, debuggers, etc. But there's more to it than that. For example, all the tools used by Forth's OS, compiler, and other internal functions are available to the programmer. And, as Chuck Moore intended, its constraints are minimal and its attitude is permissive. Forth devotees still love to debate the source and magnitude of such productivity increases!

Rather immediately left the University and began working for NRAO jointly with Kitt Peak National Observatory (KPNO), an optical observatory with which NRAO shared facilities, maintaining the Forth system for NRAO and developing one for KPNO (which was later used on KPNO's 156" Mayall telescope and other instruments [Phys. Sci. 1975]). During the next two years she wrote the first Forth manual [Rather, 1972] and gave a number of papers and colloquia within the observatory and related astronomical organizations [Moore, 1974a].

In 1973 Moore and Rather replaced the twin-computer system by a single disk-based PDP-11 computer [Moore, 1974a&b]. This was a multi-user system, supporting four terminals in addition to the tasks controlling the telescope and taking data. It was so successful that the control portions of it were still in use in 1991 (data acquisition and analysis functions are more dependent on experimental equipment and techniques, which have changed radically over the years). The system was so advanced that astronomers from all over the world began asking for copies of the software. Versions were installed at Steward Observatory, MIT, Imperial College (London), the Cerro Tololo (Chile) Inter-American Observatory, and the University of Utrecht (Netherlands). Its use spread rapidly, and in 1976 Forth was adopted as a standard language by the International Astronomical Union.

2.2 Commercial Minicomputer Systems

Following completion of the upgraded system in 1973, Moore and his colleagues Rather and Conklin formed FORTH, Inc. to explore commercial uses of the language. FORTH, Inc. developed multiuser versions of Forth [Rather, 1976a] for most of the minicomputers then in use (see Table 1), selling these as components of custom applications in a widely diverse market, ranging from data base applications to scientific applications such as image processing. The minicomputers and applications of 70's provided the environment in which Forth developed and stabilized, to the extent that all of the innovations contributed by independent implementors in the years that followed represented relatively minor variants on this theme. Because of this, we shall take a close look at the design and structure of these systems.

1970-71

Honeywell H316

NRAO

Data acquisition, on-line analysis w/graphics terminal

1971

Honeywell DDP116

NRAO

Radio telescope control

1971-2

IBM 370/30

NRAO

Data analysis

1972

Varian 620

KPNO

Optical telescope control and instrumentation

1972

HP2100

KPNO

Instrumentation

1972-3

Modcomp

NRAO

Data analysis

1973

PDP-11

NRAO

Radio telescope control, data acquisition, analysis, graphics

1973

DG Nova

Steward Observatory

Data acquisition and analysis

1974

SPC-16

Steward Observatory

Ground control of balloon-borne telescope

1975

SDS920

Aerospace Corp.

Antenna control

1975

Prime

Gen'l Dynamics,
Pomona

Environmental controls

1976

Four-Phase

Source Data
Systems

Data entry and data base management

1977

Interdata Series 32

Alameda Co., CA

Data base management

1977

CA LSI-4

MICOA

Business systems

1978

Honeywell Level 6

Source Data
Systems

Data entry and data base management

1978

Intel 8086

Aydin Controls

Graphics and image Processing

1980

Raytheon PTS-100

American Airlines

Airline display and workstations

Table 1. Computers for which Chuck Moore personally implemented Forth systems. In 1978, his implementations of Forth on the Level 6 and 8086 represented the first resident software on both CPUs, anticipating their manufacturers' systems by many months.

2.2.1 Environmental constraints

Minicomputers of the 1970's were much less powerful than the smallest microcomputers of today. In the first half of the decade not all systems even had disks — 1/2" tape was often the only mass storage available. Memory sizes ranged from 16 to 64 Kbytes, although the latter were considered large. In the early 70's, most programming for minis was done in assembly language. By the middle of the decade compilers for Fortran and BASIC were available, and manufacturer-supplied executives such as DEC's RT-11 supported foreground-background operation. Multiuser systems were also becoming common: a PDP-11 or Nova could be expected to support up to eight users, although the performance in a system with eight active users was poor.

On this hardware, Moore's Forth systems offered an integrated development toolkit including interactive access to an assembler, editor and the high-level Forth language, combined with a multitasking, multiuser operating environment supporting 64 users without visible degradation, all resident without run-time overlays.

Although time-critical portions of the system were written in assembler, as most applications required very high performance, Moore could port an entire Forth development environment to a new computer in about two weeks. He achieved this by writing Forth in Forth — any Forth computer could generate Forth for another, given the target system's assembler and code for about 60 primitives. Since the first step in a port was designing and writing the target assembler, it is possible that Moore has written more assemblers for different processors than anyone else.

Being able to port the system easily to new architectures was important, since the minicomputer market was extremely fragmented. A large number of CPUs was available, and each was supported by a large number of possible disk controller and drive combinations. Today, by contrast, the microcomputer market is dominated by a very short list of processor families, and adherence to de-facto standards such as the PC/AT is the norm.

Installations were done on site, since it was impractical to ship the minicomputers. When LSI-11's first became available, Moore bought one and mounted it in a carry-on suitcase, with a single 8" floppy drive in a second suitcase. This portable personal computer accompanied him everywhere until 1982, acting as a "friendly" host for generating new Forths.

2.2.2 Application requirements

If the principal environmental constraints were memory limitations and a need to serve a broad spectrum of CPU architectures, the application requirements were dominated by a need for performance. Here are some of the principal application areas in which Forth achieved success in this period:

1. Commercial/business data base systems:
First developed for Cybek Corp. under the guidance of Arthur A. Gravina, these systems supported multiple terminals on a Data General Nova, handling high-speed transaction processing. The first was written for Vernon Graphics, Inc., a service bureau to Pacific Telephone, in 1974. It supported 32 terminals processing transactions against a 300 MB data base. In its first week the system handled over 100,000 transactions a day (40,000 was the requirement). The system was subsequently upgraded to support 64 terminals and a 600 MB data base, with no discernable degradation in response times, which remained under one second.
Cybek subsequently marketed this system for business applications in banking and hospital management; its current version is marketed by a division of McDonnell Douglas. A similar effort by Source Data Systems in Iowa produced a multi-terminal data-entry system marketed by NCR Corp. for hospital management and similar applications.
The performance of such a system is overwhelmingly dominated by operating system issues, principally the ability of the native Forth block-based file system to read and write data files very quickly.
2. Image Processing:
FORTH, Inc. developed a series of image processing applications for the Naval Weapons Research Center, NASA's Goddard Space Flight Center, the Royal Greenwich Observatory in England, and others. Central to these was a need for performing standardized operations (e.g., enhancement, windowing, etc.) on images residing on different kinds of hardware. The approach taken included many features now associated with object oriented programming: encapsulation (the basic object was an "image," with characteristic parameters and methods), inheritance (you could add new images that would inherit characteristics of previously defined classes of images) and dynamic binding of manipulation methods. Moore, the principal architect of this approach, was unaware of any academic work in this area. Striving to achieve the same goals as later OOPS writers, he independently derived similar solutions.
Image processing systems are also distinguished by a need to manipulate and move large quantities of data very fast; a 512x512x16 image, for example, occupies 512 KB. In addition to the high-speed disk performance that characterized Forth data base systems, these also required fast processing speed and the ability to handle algorithms such as FFTs. As many minicomputers lacked hardware floating-point arithmetic, Forth included flexible integer and fixed-point fraction operators, as well as specialized array primitives.
3. Instrumentation and control:
Forth was first developed and used for this purpose at NRAO note], and Forth is widely used for instrumentation and controls today. FORTH, Inc. did several more astronomical systems (for the Universities of Wyoming [Gehrz, 1978], Minnesota, Hawaii and Illinois; Cal Tech; plus the Royal Greenwich Observatory and St Andrews University in the UK). In addition, a number of commercial instrument manufacturers such as Princeton Applied Research (now a division of EG&G) and Nicolet Instruments adopted Forth as a language for internal development.
These applications are characterized by high data rates, as much as 20 KHz in some cases, which really strained the CPU speed of the processors available. Fast interrupt response was essential, along with high-speed multitasking to allow data acquisition to proceed concurrently with operator activity and instrument control.

2.2.3 Influences

The evolution of Forth prior to 1978 was completely dominated by Moore himself. As we have seen, Moore was and is a fanatic minimalist, dedicated to the principle of zero-based design in which every feature and every instruction must justify its existence or be ruthlessly scrapped.

Moore originally developed the system for his own use. It surprised him a little to find that Rather and the other early users also liked it and found it enhanced their productivity as much as it did his. But even after the formation of FORTH, Inc. and its open marketing of the system, the selection and design of support tools and the general programming interface was dominated by his personal tastes.

Moore was working primarily as a consultant, supported by others within FORTH, Inc., installing a Forth system on a customer's computer as the first step in developing a custom application. Since the customer was primarily interested in the application, it was imperative that the port be completed quickly and inexpensively. The extreme simplicity of Forth made this possible without compromising the performance of the application.

Each of these projects contributed its own lessons, tools and techniques. Moore carried microfiche listings of all previous projects in his briefcase, and often referred to them to get the code for some unique primitive or driver from the past. Frequently used words might become a standard fixture of the system. Also, improved techniques for solving common problems were integrated into the system.

This pattern of continual evolution created customer support headaches for FORTH, Inc., however, as no two installed systems were the same. In most cases the installation included a five-day Forth programming course taught by Rather, who had to check every evening to make sure that the system still behaved the way it was being taught.

2.3 Early Microprocessor Systems

In 1976, Robert O. Winder, of RCA's Semiconductor Division engaged FORTH, Inc. to implement Forth on its new CDP-1802 8-bit microprocessor [Rather, 1976b], [Electronics,1976]. The new product, called "microFORTH," was subsequently implemented on the Intel 8080, Motorola 6800 and Zilog Z80, and sold by FORTH, Inc. as an off-the-shelf product. microFORTH was successfully used in numerous embedded microprocessor instrumentation and control applications in the United States, Britain and Japan.

2.3.1 Environment and applications

microFORTH was FORTH, Inc.'s first experience with off-the-shelf, mail-order software packages; the minicomputer systems were all installed on-site. The mail-order operation was made possible by the rapid standardization of the industry on 8" "IBM-format" floppy disks, and the relatively small number of development systems for each CPU type.

These microprocessors were all 8-bit devices, typically with 16K bytes of memory in the development system. The target systems were usually custom boards (although Intel's Single Board Computer series quickly became popular) and the software was expected to run from PROM in an embedded environment without disk or (usually) terminal. This was significantly different from the minicomputer environment, where there was always a disk, and a program was expected to run on the same (or identical) computer as the one used for development.

Most microprocessor manufacturers offered development platforms consisting of the same microprocessor as in the target, up to 64K bytes of RAM, a serial line for a terminal, a parallel printer port, and two 8" floppy disk drives. Software support was mainly assembler, although Intel soon introduced PL/M. In-circuit emulators and separate utilities were introduced for debugging.

microFORTH was principally marketed as an interactive alternative to assembler which, unlike PL/M, was available across most microprocessor families and therefore offered a higher degree of transportability.

2.3.2 Language definition

Following some initial experimentation with 8-bit stack width and 128-byte block buffers, it was quickly decided to maintain the same basic internal architecture as on the minicomputer systems. The organization of the program changed significantly, however.

microFORTH came with a target nucleus designed to run from PROM. This nucleus was only 1K in size, containing primitives such as single-precision arithmetic and other very basic functions. The development environment supported writing and testing code interactively, and then compiling a version of that code designed to mate to the run-time nucleus. A version of VARIABLE was provided to support segregated ROM/RAM data space (CONSTANTs were in PROM), and defining words were adapted so that user-defined structures could be made to reside in either. And whereas previously VARIABLEs could be initialized at compile time, that capability was removed, as it's difficult to initialize target RAM when a ROM is being compiled without setting up a "shadow" table; ROM space was considered too precious for that.

The multiprogramming support was initially stripped out, although it later came back using a new, faster task-swapping algorithm, and the data base tools vanished completely.

FORTH, Inc. never released the metacompiler used to generate Forth on new minicomputer CPUs. A variant of this metacompiler became an integral part of microFORTH, however, as it was used to generate the ROMable code for the target application. This was significant, as we shall see in the next section.

2.3.3 Influences

The principal architect of microFORTH was Dean Sanderson. Although Sanderson worked closely with Moore and shared most of his basic philosophies, differences in style and approach were inevitable. But the major new influence came from the broader customer base that resulted from the wider marketing of microFORTH. It was customer pressure that brought back multiprogramming, and this larger customer base also caused standards groups to form.

2.4 Language Definition

The commercial mini and microcomputer implementations produced by FORTH, Inc. in the early- and mid-1970's for the first time encapsulated the principles and elements of Forth as it is used today. For this reason, we shall summarize these briefly.

2.4.1 Design principles

Much as algebra was the "metaphor" for FORTRAN, Forth was conceived on the model of English prose (though some have suggested that its postfix notation tends to resemble verb-at-the-end languages such as German). Its elements ("words") are named data items (roughly equivalent to nouns), named procedures (equivalent to verbs), and defining words (special kinds of verbs capable of creating data items with customized characteristics). Words may be defined in terms of previously defined words or in machine code (using the embedded assembler).

Forth "words" are functionally analogous to subroutines in other languages. They are also equivalent to commands in other languages - Forth blurs the distinction between linguistic elements and functional elements.

Words are referenced (either from the keyboard or in program source) by name. As a result, the term "word" is applied both to program (and linguistic) units and to their text names. In parsing text, Forth considers a word to be any string of characters bounded by spaces (or "white space" characters in some file-based systems). Except for these, there are no special characters that cannot be included in a word or start a word, although many programming teams adopt naming conventions to improve readability. Words encountered in text fall into three categories: defined words (i.e., Forth routines), numbers, and undefined words.

There are no explicit typing mechanisms in Forth, a feature which sometimes surprises newcomers, but is generally admired by experienced Forth programmers.

2.4.2 Structured programming disciplines

Architecturally, Forth words adhere strictly to the principles of "structured programming" as articulated by Dijkstra [e.g., Dijkstra, 1969] and "modular programming" [Parnas, 1971]. These principles may be summarized as follows:

Top-down design and bottom-up coding and testing are strongly encouraged by Forth's structure.

As was the case with Moore's independent development of OOPs-like features in his image processing system, Moore was unfamiliar with the contemporary literature on structured programming. These principles were first called to his attention in 1973 by Rather, who received several comments on the apparent relationship between Forth and structured programming in seminars she was giving on Forth. On reading one of Djikstra's papers, Moore observed, "it just seems like good programming practice to me."

In fact, advanced Forth programmers with knowledge of the underlying implementation know ways of "cheating," but such practices are frowned upon, and definitely not supported or encouraged by the structure of the language.

2.4.3 Elements of Forth

Moore's Forth systems of the early 1970's were built on a nucleus of only 4K bytes. This tiny program included disk (or tape) and terminal drivers and the ability to search and build the dictionary. This nucleus was then used to compile from source the balance of the programming environment, including the assembler, editor, multiuser support and several hundred general commands. Booting the system, including compiling most of it from source into executable form, took only a few seconds.

A metacompiler, also written in Forth, was used to compile the nucleus. The entire source for the system was about 40 pages long.

These systems were "native," that is, running without any host OS or executive. This was a necessity in the early days, as OSs weren't available. Later, it was regarded as a significant advantage, as I/O services in a native Forth environment were much faster than could be supplied by a general purpose OS.

The principal elements of Forth will be discussed briefly in the sections that follow.

2.4.3.1 Dictionary

A Forth program is organized into an extensible dictionary that occupies almost all the memory used by the system. The dictionary is classically implemented as a linked list of variable-length items, each of which defines a word. The content of each definition depends upon the type of word (data item, constant, sequence of operations, etc.). On multi-user Forth systems individual users may have private dictionaries, each of which is connected to a shared, re-entrant system dictionary.

2.4.3.2 Push-down stacks

Forth maintains two push-down stacks, or LIFO lists (on a multiprogrammed version, a pair for each task). These are used to pass data between Forth words and for controlling logical flow. A stack contains one-cell items, where a cell is 16 bits wide on 8-bit and 16-bit computers and 32 bits wide on most implementations for 32-bit processors such as the 680x0 family. Extended-precision numbers occupy two stack positions, with the most significant part on top. Items on either stack may be addresses or data items of various kinds. Stacks are of indefinite size, and usually grow towards low memory.

Forth's explicit use of stacks leads to a "postfix" notation in which operands precede operators. Since results of operations are left on the stack, operations may be strung together effortlessly, and there is little need to define variables to use for temporary storage.

2.4.3.3 Interpreters

Forth is an interpretive system, in that program execution is typically controlled by a small machine-code routine (often only two or three instructions) interpreting lists of pointers or tokens for abstract machine functions. This architecture is much faster than classical interpreters, as used in BASIC and PROLOG for example, enabling it to perform satisfactorily in the real-time applications for which it was designed.

This internal engine is often referred to as the "inner" or "address" interpreter [note], as distinct from Forth's more traditional text interpreter which processes source and user input. The text interpreter extracts strings separated by spaces from the terminal or mass storage, looking each word up in the dictionary. If a word is found it is executed by invoking the address interpreter, which processes a string of addresses compiled in a word definition by executing the definition pointed to by each. The text is not stored in memory, even in condensed form. If a word is not found, the system attempts to convert it as a number and push it onto the stack. If number conversion fails (due to a non-numeric character), the interpreter aborts with an error message.

The address interpreter has two important properties. First, it is fast, often requiring as few as one or two machine instructions per address. Second, it makes Forth definitions extremely compact, as each reference requires only one cell (or computer word; Forth users prefer to avoid the use of "word" as a hardware unit because of its use to denote an element in the language). In contrast, a subroutine call constructed by most compilers requires instructions for handling the calling sequence before and after a CALL or JSR instruction and address, and typically save and restore registers within the subroutine. Forth's stack architecture obviates the need for an explicit calling sequence, and most implementations make global register assignments in which certain system state variables are assigned to dedicated registers, and all other registers are designated scratch registers for use in code words.

2.4.3.4 Assembler

Most Forth systems include a macro assembler for the CPU on which they run. When using CODE the programmer has full control over the CPU, as with any other assembler, and CODE definitions run at full machine speed. The assembler lets the programmer use explicit CPU-dependent code in manageable pieces with machine-independent interfacing conventions. To move an application to a different processor requires re-coding only the CODE words, which will interact with other Forth words in exactly the same manner.

Forth assemblers feature an unusual design, which has two goals:

  1. to improve transportability between processors by standardizing assembler notation as much as possible without impairing the programmer's control of the processor, and
  2. to yield a compact assembler that can be resident at all times to facilitate interactive programming and debugging.

In a classical Forth assembler, the op-code itself is a Forth word which assembles the instruction according to operands passed on the stack giving the addressing information. This leads to a format in which the addressing mode specifiers precede the op-code (consistent with the postfix notation used elsewhere in Forth). Moore also standardized notation for addressing modes, although he usually used the manufacturer's instruction mnemonics. Registers were generally referred to by number, except for registers assigned to key internal system functions. For example, the stack pointer is usually in a register called S. One would address the second item on a two-byte wide stack using the phrase 2 S).

Forth assemblers support structured programming in the same way that high-level Forth does. Arbitrary branching to labelled locations is discouraged; on the other hand, structures such as BEGIN … UNTIL and IF … ELSE … THEN are available in the assembler (implemented as macros that assemble appropriate conditional and unconditional branches). Such structures are easy to implement because the stack is available during assembly to carry addressing information.

Conventional assemblers leave the code in a file, which must be integrated with code in files from high-level language compilers (if any) by a linker before the resultant program can be loaded into memory for testing. The resident Forth assembler assembles the code directly into memory in executable form, thus avoiding the linking step.

The Forth assembler is used to write short, named routines that function just like high-level Forth words: when the name of the routine is invoked, it will be executed. Like other Forth routines, code routines expect their arguments on the stack and leave their results there. Within code a programmer may refer to constants (to get a value), variables (to get an address) or other defined data types. Code routines may be called from high-level definitions just as other Forth words, but do not themselves call high-level or code definitions.

These features enable Forth programmers to write code in short, easily testable modules that are automatically integrated into an application. Programming is fully structured, with consistent rules of usage and user interface for both assembler and high-level programming. Words are tested incrementally, while the desired behavior is fresh in the programmer's mind. Most new words can be tested simply by placing input values on the stack, typing the word to be tested and validating the result left on the stack by displaying it.

The result is complete control of the computer, high performance where needed, and overall shortening of development time due to interactive programming at all levels.

2.4.3.5 Disk support

Classical Forth divides mass storage into "blocks" of 1024 bytes each. The block size was chosen as a convenient standard across disks whose sector sizes vary. At least two block buffers are maintained in memory, and the block management algorithm makes it appear that all blocks are in memory at all times. The command n BLOCK returns the memory address of block n, having read it if necessary. A buffer whose contents is changed is marked so that when it needs to be reused its block is automatically written out. This algorithm provides a convenient form of virtual memory for data and source storage, with a minimum number of physical disk accesses required. FORTH, Inc.'s data base applications build data files out of blocks, with a file defined as spanning a specified range of blocks; data access is through operations performed against named fields within selected files.

In native Forths, the block system is both fast and reliable, as the disk driver computes the physical address of the block from its number - no directory is required. In disk-intensive applications, performance can be enhanced by adding more buffers, so more blocks will be found in memory; the buffers become a disk cache.

In the 1980's, Forth systems became available running under conventional OSs, as we shall see. Many of these support blocks within host OS files, although some have abandoned blocks altogether. As blocks provide a compatible means of accessing mass storage across both native and non-native systems, ANS Forth (Section 5.1) requires that blocks be available if any mass storage support is available.

2.4.3.6 Multiprogramming

The earliest Forth systems supported multiprogramming, in that the computer could execute multiple concurrent program sequences. In 1973, Moore extended this capability to support multiple users, each with a terminal and independent sub-dictionaries and stacks. The entity executing one of these program sequences or supporting a user is referred to as a task. Many of today's Forths support multiprogramming, and most of these use variants of Moore's approach.

This approach allocates CPU time using a cooperative, non-preemptive algorithm: a task relinquishes the CPU while awaiting completion of an I/O operation or upon use of the word PAUSE, which relinquishes the CPU for exactly one lap around the round-robin task queue.

Moore's systems used interrupts for I/O. Interrupts were directly vectored to the response code using an assembler macro, without intervention by the Forth executive. Interrupt code performed only the most time-critical operations (e.g., read a number, increment a counter), then reenabled the task that had been suspended pending the interrupt. The task would actually resume operation the next time it was encountered in the round-robin task loop, at which time it would complete any high-level processing occasioned by the event and continue its work.

In theory this non-preemptive algorithm is vulnerable to a task monopolizing the CPU with logically or computationally intensive activity, but in practice real-time systems are so dominated by I/O that this is rarely a problem. Where CPU-intensive operations do occur, PAUSE is used to "tune" performance.

Event:

VRTX

OS9

PDOS

polyFORTH

Interrupt response

91

43.75

93.4

7.0

Context switch

128

186.25

93.4

36.0

Suspend task

180

316.25

184.7

6.8

Copy memory (80 bytes)

 

212.5

97.0

Table 2. Performance comparisons of several real-time OSs on a M68010 [Cox, 1987]. Times are averages, given in µs. Times were normalized to a 10 MHz 68010. polyFORTH's use of non-preemptive task scheduling accounts for its performance advantage.

Consultant Bill Cox pointed out [Cox, 1987] that a non-preemptive algorithm such as this has several advantages. First, the task scheduler itself is simpler and faster, taking as little as one machine instruction per task. Second, since a task is suspended only at known, well-defined times, it has less "context" to be saved and restored, so the context-switch itself is faster. Third, task code can be written with the knowledge of exactly when the task does or does not control the CPU, and management of shared resources is considerably simplified. Cox compared the performance of several real-time OSs; the results are given in Table 2.

Tasks were constructed when the system was booted, and each was given a fixed memory allocation adequate to the functions it was intended to perform. As re-booting took only a few seconds, it was easy to reconfigure a task.

2.4.3.7 Computation

Until the late 1970's, few minicomputers offered floating point arithmetic — indeed, many lacked hardware multiply and divide. From the beginning, however, Forth was used for computationally intensive work. Controlling the radio telescope, for example, required converting wanted positions from the celestial coordinates in which astronomical objects are located to an azimuth/elevation coordinate system once per second and interpolating intermediate positions five times per second, with data acquisition and operator activity proceeding concurrently.

Moore's approach was to build into Forth the ability to manipulate integers effectively. For example, the command */ multiplies two single-cell integers and divides by a third, with a double-length intermediate product. This reflects the way most multiply and divide machine instructions work, and enables calculations such as:

12345 355 113 */

This phrase multiplies 12345 by the ratio 355/113, which represents PI with an error of 8.5 x 10-8 [Brodie, 1981]. The ability to multiply by a ratio is ideal for calibration and scaling, as well as rational approximations. Similarly, the word /MOD performs a single division, returning both the quotient and remainder. A rich set of single, double and mixed-precision operations such as these make integer arithmetic much more usable than it is in most languages.

Moore expressed angles internally as 14-bit, 15-bit or 30-bit fixed-point binary fractions. He provided a set of primitives to convert to and from angle formats (e.g., dd:mm:ss), and a math library supporting transcendental functions for these formats based largely on algorithms from [Hart 1968]. Operations such as the Fast Fourier Transform were provided in some applications, built on specialized primitives supporting complex numbers as scaled integer pairs.

Today fast floating-point processors are common. Many Forths support floating point, as does ANS Forth. But in many cases, such as embedded systems on simple microcontrollers, Forth's integer arithmetic still provides simpler, faster solutions.

2.4.3.8 Data types

Perhaps nowhere was Moore's personal philosophy more in evidence than in his approach to data typing. Basically, he wanted to assume full responsibility for manipulating data objects in whatever way he wished. If pressed on this point, he would say, "If I want to add 1 to the letter A, it's none of the compiler's business to tell me I can't."

Standard words in Forth support single and double-precision CONSTANTs, which return their values on the stack, and VARIABLEs, which return a pointer. CREATE names the beginning of a data region in which space can be reserved. The pointer returned by a CREATEd entity can be incremented to index into an array. The nature of the values kept in constants and variables was entirely arbitrary; there is normally no explicit type checking. Strings are normally kept in memory with their length in the first byte. The address of this structure, or the address and length of the actual string, can be passed on the stack.

CONSTANT, VARIABLE and CREATE are "defining words," that is, they define new words with characteristic behaviors. Forth also provides tools to enable the programmer to build new defining words, specifying a custom behavior both at compile time (e.g., setting up and initializing a table) and run-time (e.g., accepting an index and automatically applying it to the base address of the structure).

«previous next»