The Forth`�ngIng0was a�miScrute UV k)cRocode`(suAcjprg#es�Mr &or! t(e Fnr~( langu`gen I. ad�i�ion to a hardware`stqck"eo2 evaluatmon and!subboutkne pprametev"pasRing aN, �he `ard7ir�0s�ack fo2 b$tuvn` addre3 {tor!gE( vlisM pro�essow$Fe�tu0et�! &0mBhp�wryuerhebc/ntp�l store fnb mi#rocgde? -

FORTRAN MACHINE

Taxonomy category: MS0
Implementation: Conceptual Design
Applications: Direct execution of the FORTRAN language
Who and when: University of Science and Technology of China, PRC, 1980
References: Chen et al. (1980)

This paper presents a conceptual design paper for a direct execution FORTRAN machine. The proposed machine would have several hardware stacks for return address, loop limit and branch address, and expression evaluation storage. While the implementation method was not specified, isolated memory space stacks would certainly be appropriate to reduce memory traffic. As with most other direct execution machines, stacks were mandatory to support program parsing.

FRISC 3

Taxonomy category: ML0
Implementation: 32-Bit 2 micron silicon compiler CMOS microprocessor
Applications: General purpose space-borne computing and control. Optimized for the Forth language
Who and when: Johns Hopkins University, 1986
References: Fraeman et al. (1986), Hayes (1986), Hayes & Lee (1988), Hayes et al. (1987), Williams et al. (1986)

The Johns Hopkins University/APL Forth processing chip is designed for spacecraft processing applications. The chip executes Forth primitives, and allows multiple operations to be compacted into microcode-like fields in the instruction. Although Forth is a 0-operand language, the chip allows selecting any of the top 4 stack elements to be used with the top stack element for an operation, thus making it a "¹/₂" operand machine. The on-chip data and return stacks are rather small: 16 elements each, forced mostly by technology constraints.

G-MACHINE

Taxonomy category: SL0
Implementation: 32-Bit processor simulation
Applications: Graph Reduction
Who and when: Oregon Graduate Center, 1985
References: Kieburtz (1985)

The G-Machine was specially built to perform graph reduction in support of executing functional programming languages. It executed G-code, which was a zero-address machine language designed to manipulate its single stack. Program memory was highly structured to support the requirements of graph reduction. Each memory word included four fields used for reference counting and two 32-bit cells used for graph pointers.

GLOSS

Taxonomy category: SS0
Implementation: Conceptual design
Applications: Multiple communicating processors.
Who and when: University of Washington, 1973
References: Herriot (1973)

The GLOSS conceptual design was an attempt to define a generic high level language machine for a variety of languages, including ALGOL 68, LISP 1.5, and SNOBOL 4. It was based on using a demand driven data-flow system where sub-processes were invoked on multiple parallel processors in a manner similar to procedure calls. Each processor had a set of evaluation stacks resident in memory.

HITAC-10

Taxonomy category: SS0
Implementation: Add-on hardware to a minicomputer
Applications: Experimental minicomputer addition
Who and when: Keio University, Japan, 1974
References: Ohdate et al. (1975)

The stack hardware discussed in this paper was back-fitted onto an existing HITAC-10 minicomputer. In order to simplify the design and construction, the stack hardware was added as an I/O device on the system bus. The stack controller had four top-of-stack registers. All extra elements were stored in an area of memory using DMA. The controller had two stack limit pointers for memory bounds checking. The stack controller was used for subroutine parameter passing; no arithmetic could be performed on stack elements.

HP300 & HP3000

Taxonomy category: SS1
Implementation: 16-Bit Minicomputer family
Applications: General purpose multi-user computer.
Who and when: Hewlett Packard, 1976-1980's
References: Bartlett (1973), Bergh & Mei (1979), Blake (1977)

The HP3000 family is a commercial line of minicomputers based on a 1-operand stack architecture. The origins of the family may be found in the HP300 computer, which could be considered a 3-address machine that had two top-of-stack registers buffering a program memory resident stack. Later, the HP3000 series used a stack/accumulator addressing mode, and included four top-of-stack registers. The stacks were featured in the architectures to ease implementation of reentrancy, recursion, code sharing, program protection, and dynamic storage allocation in a multi-user environment. The stack is used not only for expression evaluation, but also for parameter passing and subroutine return address storage.

HUT

Taxonomy category: MS0
Implementation: 16-Bit AM2903 bit-sliced processor
Applications: Spacecraft experiment control. Optimized for the Forth language
Who and when: Johns Hopkins University, Applied Physics Laboratory 1982
References: Ballard (1984)

The HUT processor was designed to control the Hopkins Ultraviolet Telescope (HUT) Space Shuttle experiment. At the time it was designed, no space-qualified microprocessors were powerful enough for the task, so a bit-sliced processor was custom designed for the job. The designers chose to implement a Forth language processor for simplicity of implementation, extensibility, and flexibility.

ICL2900

Taxonomy category: SS1
Implementation: Family of mini-computers
Applications: General purpose computing.
Who and when: ICL, 1975
References: Keedy (1977)

The designers of the ICL family were concerned with protection and code sharing in a multiprogrammed environment, as well as efficient compilation and execution with compact object code. While often compared with the contemporary Burroughs machines, the ICL machines had several distinct characteristics. One of these was the use of a stack/accumulator 1-operand addressing scheme and several specialized registers. With this capability, a register or memory location could be used with the top stack element for operations.

INTEL 80x86

Taxonomy category: SS2 (when used in stack mode)
Implementation: Family of 16 and 32-bit microprocessors
Applications: General purpose computing
Who and when: Intel Corporation 1980's
References: Intel (1981)

The 80x86 processor family, which includes the 8088, 8086, 80186, 80286, and 80386 is a family of microprocessors with a general purpose register architecture. Simple PUSH and POP instructions are supported to manipulate the stack. Many high level language compilers produce code that uses the BP (base pointer) register as a frame pointer to a combined return address and parameter passing stack. When used in this mode, the 80x86 family can be considered to be doing stack processing. In the context of stack computers, the 80x86 is simply included in this listing as a representative example of a conventional machine that can be used as an SS2 architecture.

INTERNAL MACHINE

Taxonomy category: MS0
Implementation: Conceptual design
Applications: Directly interpretable languages
Who and when: North Electric Co., 1973
References: Welin (1973)

The Internal Machine was a conceptual design for a machine that could efficiently execute directly interpretable languages. A stack instruction model was picked for generality. The design specifies two stacks: one for expression evaluation and parameter passing, and a second stack for subroutine return addresses.

IPL-VI

Taxonomy category: SS1
Implementation: Conceptual design for microcoded interpreter
Applications: General purpose computing
Who and when: Rand Corporation, 1958
References: Shaw et al. (1959)

The Information Processing Languages (IPL's) were a series of conceptual language designs for implementing high level programs. IPL-VI was a language designed meant to be implemented as an interpreted language with microcode support. IPL-VI emphasized advanced (for 1959) computing structures for non-numerical computing, especially list manipulation. A stack was used to pass parameters between subroutines. Since all memory in the IPL-VI design was formatted as list elements, the subroutine parameter LIFO consisted of a list of elements that pointed to the next element further down in the list. IPL-VI instructions used 1-operand addressing.

ITS (Pascal)

Taxonomy category: SS0
Implementation: 16-Bit microprocessor
Applications: Direct execution of Pascal P-code
Who and when: Nippon Electric Co., 1980
References: Tanabe & Yamamoto (1980)

The ITS processor was designed to execute UCSD Pascal P-code. The designers claimed a several-times speedup over fully compiled code on a contemporary microprocessor (presumably an 8086). The ITS had a 256-word stack on-chip, which was apparently only used for expression evaluation. The top two stack elements were kept in registers for speed.

KDF-9

Taxonomy category: ML0
Implementation: 48-Bit mainframe
Applications: General purpose computing using ALGOL
Who and when: English Electric, 1960
References: Allmark & Lucking (1962), Duncan (1977), Haley (1962)

The KDF-9 was perhaps the first true stack computer. It was inspired by the advent of ALGOL-60, and introduced many of the features found on modern stack computers. The KDF-9 had an expression evaluation stack which could be used for parameter passing, as well as a separate return address stack. Unfortunately, these stacks were limited by technology considerations to only 16 elements apiece (constructed from magnetic cores!). A problem with the design was that while 16 elements is quite sufficient for expression evaluation, the ALGOL compiler was constrained by the 16-element stack depth, causing slow compilation.

KOBE UNIVERSITY MACHINE

Taxonomy category: ML0
Implementation: 16-Bit wide AM2903 bit-slice with writable control store.
Applications: Academic Research
Who and when: Kobe University, Kobe Japan, 1983
References: Kaneda et al. (1983), Wada et al. (1982a), Wada et al. (1982b)

This machine was designed to execute both Forth and Pascal efficiently using a stack architecture. Forth was executed by directly implementing Forth primitives in microcode. Pascal was executed by supporting a UCSD P-code emulator. This machine had separate data memory in addition to program memory.

LAX2

Taxonomy category: SS0
Implementation: Microcoded interpreter on Varian V73
Applications: Experimental
Who and when: Group for Datalogical Research & Royal Institute of Technology, Sweden, 1980
References: Bage & Thorelli (1980)

The LAX2 architecture was implemented as a partially microcoded interpreter with the goals of cost effective software production along with good memory and execution time economy for string manipulation and interactive applications. The architecture used tagged data types. Each process in the machine had a private memory area shared between the evaluation stack and a garbage-collected heap for temporary string storage.

LILITH

Taxonomy category: ML1/MS1
Implementation: 16-Bit AM2901 bit-sliced processor
Applications: Direct execution of Modula-2 M-code and interactive user interfaces.
Who and when: ETH (Swiss Federal Institute of Technology), 1979.
References: Ohran (1984), Wirth (1979)

Lilith was a Modula-2 execution machine developed by Niklaus Wirth. The goals of the machine were to provide efficient support for the Modula-2 language as well as an effective user interface. A stack architecture was chosen for compact code. The Lilith had two stacks: a program memory resident stack for parameter passing, and a hardware expression evaluation stack. The instruction set was stack-based, with the ability to read an element from any location in the parameter stack and operate upon it with the top element of the evaluation stack.

LISP MACHINES

Taxonomy category: ML1
Implementation: Various machines. 1982 to present.
Applications: List processing, artificial intelligence research
Who and when: Various companies (such as Symbolics)
References: Lim (1987), Moon (1985), Sansonnet et al. (1982)

LISP machine architecture is a whole topic in its own right; this is simply a summary of some of the common characteristics of LISP-specific processors. LISP machines tend to have multiple stacks and 1-address (relative to top of stack) instruction formats. Some machines have substantial hardware stacks (over 1K word) that can overflow into program memory. Procedure calls tend to be very important, because of the recursion commonly used in traversing lists. These machines typically store data elements in a garbage-collected program/data memory.

MCODE

Taxonomy category: SS1
Implementation: Unspecified
Applications: Execution of Modula-2 M-code (using StarMod language)
Who and when: University of Wisconsin - Madison, 1980
References: Cook, R. & Donde, N. (1982), Cook, R. & Lee, I. (1980)

The MCODE machine was designed to execute Modula-2 M-code, which was compiled from a language called StarMod, a Modula-2 derivative. MCODE was based on Tanenbaum's EM-1 design, but with several improvements to solve problems that arise in real computers. One improvement was the use of a set-mode instruction that changed the interpretation of the data types (integer, floating point, etc.) for all subsequent operations.

MESA

Taxonomy category: SS0
Implementation: Architectural family for workstations
Applications: Graphics-intensive workstations (Alto, Dorado machines)
Who and when: Xerox Office Products Division, 1979
References: Johnsson & Wick (1982), McDaniel (1982), Sweet & Sandman (1982)

Mesa was actually a modular high level language expanded to include an architecture for a family of processors. The goals of the architecture were efficient implementation, compact encoding, and technology independence. In order to accomplish these goals, the Mesa architecture specified a single stack for use in expression evaluation and parameter passing to procedures for the purpose of producing compact 0-operand stack instructions. While the stack implementation was not specified, Mesa follows the general pattern of machines with a small stack buffer and the bulk of the stack in program memory. An interesting instruction was the "recover" operation, which captured a previously popped stack value that had not yet been overwritten by doing a stack push without writing a value.

MF1600

Taxonomy category: ML0
Implementation: TTL discrete components, 16-bit machine
Applications: General purpose processing
Who and when: Xycom & Advance Processor Designs, 1987
References: Burnley & Harkaway, 1987

The Advanced Processor Design MF1600, which is the processor used on the Xycom XVME-616 product, is a high performance Forth machine design that makes use of fast TTL logic devices. It features a 16-bit data path and a microcode memory ROM that can be customized by the manufacturer for specific applications.

MICRO-3L

Taxonomy category: SL1
Implementation: Simulated machine
Applications: Functional Programs
Who and when: University of Utah, 1982
References: Castan & Organick (1982)

The micro-3L processor project used the 3L-model (Lisp Like
Language model) for specifying a processor that is well suited to list processing. The project proposed creating a multiprocessor system to execute functional languages. Each micro-3L processor was to use a 256-element register file. 128 of the registers were intended to be used as a return address stack, with overflow handled by swapping into main memory. Data manipulations were performed using an Accumulator and an operand from the bottom 128 elements of the register file.

MICRODATA 32/S

Taxonomy category: SS0
Implementation: Microcode upgrade to a 16-bit register-oriented minicomputer.
Applications: Running a version of PL/I
Who and when: Microdata Corporation, 1973
References: Burns & Savitt (1973)

The Microdata 32/S was a version of the Microdata 3200 general-purpose minicomputer that had additional microcode to implement stack instructions. The 3200 system was a 16-bit minicomputer implemented in discrete TTL technology. The reason for adding the stack-based capabilities was that compilers of the time could not produce efficient code. Stack architectures made code generation easier. The reason good code generation is important was to remove the impetus for programming in assembly language. The main memory stack was used for expression evaluation and parameter passing, with up to four stack elements buffered in registers.

MISC M17

Taxonomy category: MS0
Implementation: 16-Bit 2.0 Micron HCMOS gate array
Applications: Low cost real time control
Who and when: Minimum Instruction Set Computer, Inc., 1988
References: MISC (1988)

The MISC M17 microprocessor is a low cost, embedded micro-controller. The M17 instruction set is based on Forth primitives. In contrast with most other Forth machines, the M17 reduces hardware costs at some compromise in performance by keeping its two stacks in program memory with a few top-of-stack buffer registers on-chip.

MOTOROLA 680x0

Taxonomy category: MS2 (when used in stack mode)
Implementation: Family of 32-bit microprocessors
Applications: General purpose computing
Who and when: Motorola Corporation 1980's
References: Kane et al. (1981)

The 680x0 processor family, which includes the 68000, 68010, 68020, and 68030, is a family of microprocessors with a general purpose register architecture. Registers are divided into two groups: address registers and data registers. The address registers support postincremented and predecremented addressing modes. This allows a programmer to use up to eight stacks, one stack per address register. By convention, the A7 register is used as the stack frame pointer for most languages. Of course, the 680x0 family is usually not used as a multiple-stack machine, but nonetheless this capability exists.

MU5

Taxonomy category: SS1
Implementation: Minicomputer
Applications: Research
Who and when: University of Manchester, 1971
References: Morris & Ibbett (1979)

The MU5 used a 1-operand instruction format with a single stack in program memory. Stack instructions were used because they led to easy code generation, compact programs, and easily pipelined hardware. An interesting twist is that there were five registers accessible to the programmer, all of which were simultaneously at the "top-of-stack." Pushing a value into any register pushed the previous register value onto the single stack. This arrangement is subtly different from having the top five stack elements accessible as registers.

NC4016

Taxonomy category: ML0
Implementation: 16-Bit Gate Array processor
Applications: Real Time Control, direct support for Forth programming language
Who and when: Novix, 1985
References: Golden et al. (1985), Jennings (1985), Miller (1987), Novix (1985)

The NC4000, later renamed the NC4016, was the first chip designed to execute Forth. Since it is on a gate array, the two hardware stack memories reside off-chip, connected to the processor by dedicated stack busses. The top two data stack elements are buffered on-chip, as is the top return stack element. The processor executes most Forth primitives including subroutine call in a single clock cycle, and allows multiple primitive operations to be compressed into a single instruction in some circumstances.

NORMA

Taxonomy category: SL0
Implementation: Experimental machine using MSI/LSI standard logic and gate arrays
Applications: Functional programming/graph reduction
Who and when: Burroughs Corporation Austin Research Center, 1986
References: Scheevel (1986)

The Normal Order Reduction MAchine (NORMA) is a research processor developed by Burroughs for high speed graph reduction operations in support of functional programming languages. Five specialized functional units that handle arithmetic, graph memory, garbage collection, graph processing, and external I/O are connected using a central bus. The graph processor maintains a single stack used during the depth-first traversal of the tree-structured program graphs.

OPA (Pascal)

Taxonomy category: ML0
Implementation: Emulator running on Lilith computer
Applications: Support for Pascal & Modula-2 programs
Who and when: Federal Institute of Technology, Zurich, 1984
References: Schulthess (1984)

The Object Pascal Architecture (OPA) is a design for a machine that efficiently executes compiled Pascal code. The OPA contains three stacks: one for descriptors and expression evaluation, one for storing subroutine parameters, and one for return addresses. The OPA instruction set is billed as a "reduced high level language" instruction set, since it supports Pascal constructions with a small number of opcodes.

PASCAL MACHINE

Taxonomy category: ML0
Implementation: Experimental processor
Applications: Direct execution of Tiny-Pascal source code
Who and when: University of Maryland, 1981
References: Lor & Chu (1981)

The Pascal interactive computer is an experimental system for direct execution of Pascal source code. Since the system includes a hardware compiler as well as execution unit, hardware stacks in the system abound. Some of the stacks are used to store return addresses, operator precedence, expression evaluation values, and subprogram nesting levels. Since expressions are evaluated as they are interpreted, the actions taken by the execution unit are the same as would be taken by a 0-operand stack architecture.

PDP-11

Taxonomy category: MS1 (when used in stack mode)
Implementation: Family of mini & microcomputers (also, later the VAX family)
Applications: General purpose mini-computer
Who and when: Digital Equipment, 1970
References: Bell et al. (1970)

The DEC PDP-11 was an early general-purpose computer to integrate stack usage into a general-purpose register machine. While the machine is clearly register-oriented, it includes as a subset of its capabilities those of a one-address stack machine. By using register-indirect addressing with auto-postincrement and auto-predecrement, a general-purpose register can be used as a stack pointer for an evaluation stack. The PDP-11 also has a stack pointer for use with interrupts, traps, and subroutine calls. Later, the VAX line of computers introduced hardware support for single-stack dynamic frame allocation for block-oriented languages. Of course the PDP-11 is really a general-purpose register machine, but Bell's article describes how it can be used in an MS1 stack mode.

POMP PASCAL

Taxonomy category: SS1
Implementation: Bit-sliced processor (AMD 290x)
Applications: Research into emulating intermediate forms for block structured languages
Who and when: Stanford University, 1980
References: Harris (1980)

The Pascal Oriented MicroProcessor (POMP) project used a bit-sliced processor to execute stack code. Stack code was chosen to reduce program size from 3 to 8 times smaller than traditional compiler outputs. In fact, the POMP code was claimed to be only 50% larger than Flynn's ideal DEL encoding, but is much easier to decode since it was encoded in byte-wide blocks. The stack machine could accesses up to 8 local variables for operations, making it a 1-operand machine.

PSP

Taxonomy category: ML2
Implementation: Architectural proposal
Applications: General purpose computing
Who and when: University of Illinois, 1985
References: Eickemeyer & Patel (1985)

The Parallel Stack Processor (PSP) architecture is an attempt to preserve the function of a normal general purpose register machine yet reap the benefits of having hardware stacks for saving registers on a subroutine call. To accomplish this, the machine hides a stack behind every register in the machine. Whenever a subroutine call is encountered, each register is pushed onto its own stack simultaneously, performing a single-cycle multiple register save. Strictly speaking, this is more of a register machine that has hardware to save registers than a stack processor architecture, but the idea is intriguing for other stack applications.

PYRAMID 90X

Taxonomy category: SL2
Implementation: 32-Bit minicomputer
Applications: General purpose RISC processor
Who and when: Pyramid Technology, 1983
References: Ragan-Kelley & Clark (1983)

The Pyramid 90x was one of the first commercial processors to have many RISC attributes. The 90x uses a register stack that is organized as 16 non-overlapped windows of 32 registers plus 16 global registers for a total of 528 registers. The registers are spilled to memory if subroutine nesting is more than 15 levels deep.

QFORTH

Taxonomy category: ML0
Implementation: Architectural study
Applications: Direct support for Forth programming language
Who and when: Queens College of CUNY, 1984
References: Vickery (1984)

The QFORTH architecture was built for multitasking single-user execution of the Forth programming language. The internal architecture included two source busses (which could be read the top two elements of the data stack) and a single destination bus to write the top-of-stack back. The stack management unit internally buffered the top stack elements in high speed registers, and allowed for a single stack memory to be partitioned into several simultaneously used stacks.

REDUCTION LANGUAGE MACHINE

Taxonomy category: ML0
Implementation: Laboratory model
Applications: Execution of reduction language programs
Who and when: GMD Bonn, 1979
References: Kluge & Schlutter (1980)

Reduction languages use structures of the form: apply function to argument. These structures are well represented by subtrees with a function node having children that are its operands. Since the execution of a program involves evaluating these tree structures, three major stacks are central to the operation of the machine. One stack acts as a program source, another as a program sink, and the third as a temporary evaluation stack area. An interesting feature of the machine is that there is no program memory, and the operation of the machine does not involve any addresses as such. All programs are shuffled between the source and sink stack memories.

REKURSIV

Taxonomy category: ML0
Implementation: 1.5 Micron CMOS using 3 gate arrays
Applications: Object oriented programming
Who and when: Linn Products, 1984-88
References: Pountain (1988)

Rekursiv is designed for fast execution of object-oriented programs. It supports a very high level instruction set that may be extended using a large amount of off-chip microcode, and has extensive support for memory management designed into the system. An evaluation stack is used for expression evaluation, while a control stack is used for microcode procedure return address storage.

RISC I

Taxonomy category: SL2
Implementation: 32-Bit microprocessor
Applications: RISC processor for C and other high level languages
Who and when: University of California, Berkeley, 1981
References: Patterson & Piepho (1982), Patterson & Sequin (1982), Sequin & Patterson (1982), Tamir & Sequin (1983)

The RISC I was the first highly publicized RISC computer. It owes a substantial amount of its performance to the use of register windows. The "gold" RISC I chip uses an overlapped register window scheme with 78 registers. At any given time, there are 32 addressable registers: 10 global registers, 6 registers shared with the calling subroutine, 10 private registers, and 6 registers used to pass parameters to subroutines at the next deeper nesting level. The registers are accessed using normal 2-operand register-to-register instructions. The RISC I allows accessing the contents of a register as a memory location by automatically mapping the memory access into the register space. This solves the up-level addressing problem that can occur in languages like Pascal.

ROCKWELL MICROCONTROLLERS

Taxonomy category: MS0
Implementation: Forth-in-ROM on 6502 and 68000 microcontrollers.
Applications: Embedded controllers that run Forth programs.
Who and when: Rockwell International, 1983
References: Dumse (1984)

While not strictly speaking hardware-supported stack machines, microcontrollers that have Forth burned into their ROM's are an interesting member of the stack-based computer family. The R65F11, based on the 6502 processor, and the F68K processor, based on the 68200 microcontroller of the 68000 processor family, are general purpose microcontrollers that come with preprogrammed Forth primitives. These chips in effect emulate a two-stack Forth engine, using variables and program memory to provide the emulation. Other dedicated Forth microcontrollers have been made since (including the Zilog Super8 chip), but Rockwell was the first to do it.

RTX 2000

Taxonomy category: ML0
Implementation: 16-Bit, 2 micron standard cell CMOS microprocessor
Applications: Semicustom design for application-specific designs. Optimized for Forth programming language
Who and when: Harris Semiconductor, 1987-89
References: Danile & Malinowski (1987), Harris Semiconductor (1988a), Harris Semiconductor (1988b), Jones et al. (1987)

The RTX (Real Time Express) is a macrocell in the Harris standard cell library. This allows the processor to be built as a stand-alone microprocessor, or as an integrated microprocessor with I/O devices, hardware multiplier and stack memory on-chip. The instruction set directly corresponds to FORTH programming language primitives. The design uses an unencoded instruction format that allows multiple operations to be compacted into each instruction. As with many Forth processors, the RTX 2000 supports single-cycle subroutine calls.

RTX 32P

Taxonomy category: ML0
Implementation: 32 Bits, 2.5 micron CMOS
Applications: Stack-based processing for real time control and expert systems.
Who and when: Harris Semiconductor and WISC Technologies, 1987-89
References: Koopman (1987c), Koopman(1987d), Koopman (1989)

The Harris RTX 32P is a prototype 32-bit stack processor chip set. A unique feature of the RTX 32P is the combination of an opcode with a next-address field in every instruction. This allows zero-cost subroutine calls, returns, and unconditional branches by overlapping the next address computation with the opcode execution. The system can execute one opcode and a subroutine call each memory cycle.

RUFOR

Taxonomy category: ML0
Implementation: 16-Bit AM2901 bit-slice microcoded processor
Applications: Research processor for Forth language
Who and when: Wright State University, 1984
References: Grewe & Dixon (1984)

The RUFOR system is a conventional bit-sliced approach to building a machine optimized for the Forth programming language. There are two hardware stacks, one for data and one for return addresses. The top entry of each stack is held in one of the 2901 internal registers, so that only a single input bus to the ALU and a single output bus back to the stacks is required.

SF1

Taxonomy category: ML2
Implementation: 3-Chip, 32-bit microprocessor using 3 micron CMOS
Applications: High level language support for real time control
Who and when: Wright State University, 1987-88
References: Dixon (1987), Longway (1988)

The SF1 (which stands for Stack Frame computer number
1) is an experimental multi-stack processor designed to efficiently execute high level languages, including both Forth and C. The current implementation has five stacks, any two of which may be selected as the source and destination for an instruction. The SF1 allows arbitrary access to its stack elements by using a 13 bit address relative to the top stack element in the instruction format.

SOAR

Taxonomy category: SL2
Implementation: Microprocessor
Applications: Support for Smalltalk-80 language
Who and when: University of California, Berkeley, 1984
References: Bush et al. (1987)

The Smalltalk On A RISC project (SOAR) modified the Berkeley RISC II architecture to adapt it to Smalltalk-80. Since Smalltalk-80 is a stack-oriented bytecode language, this is an exercise in mapping stack code onto a register-oriented RISC, which in turn has its registers arranged in an overlapped window register stack. The window size of the register stack was only 16 registers, half that of RISC II, since Smalltalk methods tend to be smaller than procedures in traditional programming languages.

SOCRATES

Taxonomy category: ML2
Implementation: Conceptual design
Applications: Use of bubble memories for main program storage
Who and when: University of Massachusetts/Amherst, 1975
References: Foster (1975)

SOCRATES (Stack-Oriented Computer for Research and Teaching) was a design that proposed using magnetic bubble memories as its main storage. At the time of the design, bubble memories were projected to cost 100 times less per bit than other memories. The only problem was that they could only be accessed sequentially. SOCRATES took advantage of this situation by proposing 64 addressable registers of 32 bits, with each register being the top element of a 32K word bubble memory configured as a LIFO stack.

SOVIET MACHINE

Taxonomy category: ML1
Implementation: Conceptual design
Applications: Execution of block-structured languages
Who and when: Academy of Sciences of the USSR, 1968
References: Myamlin & Smirnov (1969)

This paper presented a design for a stack computer for executing block-structured languages. The design had two stacks: one for holding arithmetic operations and one for holding operands. While not a directly interpreting machine, it was apparently intended to have source programs maintain an infix format with infix to postfix conversion done on-the-fly. Stacks could be addressed as part of program memory if desired, but were physically separate components.

SYMBOL

Taxonomy category: MS0
Implementation: Discrete TTL prototype machine
Applications: Research
Who and when: Iowa State University, 1971
References: Ditzel & Kwinn (1980), Hutchison & Ethington (1973)

The SYMBOL project constructed an operational computer using no software. The editor, debugger, and compiler were all implemented using random logic circuits. User programs were entered in source code, then compiled and executed using hardwired control circuits. The compilation unit transformed code into a stack-based intermediate form before execution. Several other stacks were used elsewhere as required by the compiler.

TRANSPUTER

Taxonomy category: SS0
Implementation: Family of 16- and 32-bit microprocessors
Applications: Parallel processing
Who and when: INMOS Limited, 1983
References: Whitby-Strevens (1985)

The Transputer is a single-chip microprocessor system designed for parallel processing. Since replicating a complete processor with memory and peripherals is very expensive, the Transputer attempts to squeeze an entire functional system onto a single chip to hold costs down for systems with large numbers of processors. This constraint places program memory space at a premium, so a stack-based instruction set was selected to reduce program size. The Transputer uses 3 registers to form an expression evaluation stack.

TM

Taxonomy category: ML0
Implementation: Simulated design
Applications: Research
Who and when: Carnegie Mellon University, 1980
References: Harbison (1982)

The Tree Machine (TM) architecture was an attempt to make compilers simpler by performing common compiler optimizations using a value cache. This cache would do common subexpression elimination and invariant code motion in hardware by caching results to recently computed expressions. A stack-based architecture was chosen because this allowed better operation with the value caching hardware and eliminated the compiler complexity associated with register allocation. The TM used two stacks: a data stack for expression evaluation, and a control stack for dependency information and return address storage.

TREE MACHINE

Taxonomy category: MS0
Implementation: Conceptual design
Applications: Executing block-structured languages
Who and when: Massey University, New Zealand, 1971
References: Doran (1972)

Doran's tree machine recognized that good programs have an inherent tree structure, and was tailored to execute these well-structured programs. The machine had three stacks resident in program memory: a control stack for return addresses, a value stack to store intermediate results for non-tree-leaf nodes, and a data stack for scratch storage allocation. An interesting feature of the machine was that conditional branches are not required. All conditional execution were accomplished with a conditional procedure return to the parent program node.

VAUGHAN & SMITH'S MACHINE

Taxonomy category: ML0
Implementation: Conceptual design
Applications: Support for Forth programming language
References: Vaughan & Smith (1984)

This paper discusses the design of a Forth-based computer. The architecture was chosen because Forth is good at representing the tree nature of structured programs. Forth's small subroutine size allows good code compaction through subroutine reuse. The proposed design featured two independent hardware stacks. The return stack had one top-of-stack register, while the data stack had two registers.

WD9000 P-ENGINE

Taxonomy category: SS0
Implementation: 5-Chip LSI set
Applications: Direct execution of Pascal P-code
Who and when: Western Digital, 1979
References: O'Neill (1979)

The Western Digital Pascal micro-engine (the WD9000 chip set) was built to execute Pascal P-code. Since P-code presumes the existence of a single data stack, the WD9000 supported a single program memory resident stack for expression evaluation and parameter passing.

WISC CPU/16

Taxonomy category: ML0
Implementation: Discrete LS-TTL, 16-bit data paths
Applications: Stack-based processing
Who and when: WISC Technologies, 1986
References: Haydon & Koopman (1986), Koopman (1986), Koopman (1987b), Koopman & Haydon (1986)

The WISC CPU-16 is a user-microcodable processor with a Forth-language machine heritage. It has both a data stack and a return address stack. Additionally, it has a 2K word by 30 bit writable control store for user-defined microcode. The architecture is general, and allows supporting other languages besides Forth. An interactive single-step capability is intended for use in teaching microcode techniques to students.

WISC CPU/32

Taxonomy category: ML0
Implementation: 32 Bits, discrete TTL
Applications: Stack-based processing for real time control and expert systems.
Who and when: WISC Technologies, 1986-87
References: Koopman (1987c), Koopman(1987d)

The WISC CPU/32 is the discrete TTL system upon which the Harris RTX 32P is based. The RTX 32P and CPU/32 are microcode and instruction set compatible.

Other references

Bulman (1977):
A general tutorial on stack architectures with emphasis on the B5500 and HP3000 as example architectures. Also mentions the Data General Eclipse and PDP-11 as examples of conventional machines incorporating some stack concepts.

Carlson (1975):
A good survey of various high level language computer architectures, many of which are stack-oriented.

Doran (1975):
Reviews the use of stacks for expression evaluation, data tree traversal, and subroutine return address saving, concentrating on the Burroughs architectures.

McKeeman, W. (1975):
A comprehensive tutorial on the operation of stack-based computers and the role of stacks in general purpose computing.

Myers (1982):
While not specifically about stack machines, this text describes many of the architectural innovations that are pertinent to discussions on stack machines. Of particular interest is the discussion of semantic gap.

Siewiorek, Bell & Newell (1982):
This computer architecture text contains many chapters on stack machines.

Yamamoto, M. (1981):
Gives a large list of high level language machines developed in Japan, many of which are stack-oriented.