APL\3000

APL\3000
Developer	Hewlett-Packard
Released	November 15, 1976
Array model	flat without boxes
Index origin	0 or 1
Function styles	defined function
Numeric types	64-bit float
Unicode support	no
Platforms	HP 3000 Series II / III
Operating systems	HP MPE
Documentation	HP Journal (pdf) Reference Manual (pdf)
Influenced by	APL.SV

APL\3000 was an APL implementation for the Hewlett-Packard HP 3000 Series II and III minicomputers. Its design and new features were published in the July 1977 issue of HP Journal. Marketed as "the first time a large-machine APL has been available on a small computer" (that is, not a mainframe), APL\3000 followed the APL.SV model closely, and featured exactly the same set of primitives. However, it featured the new implementation techniques of a dynamic compiler and subscript calculus, usability features like a workspace transparently backed by disk space and improved interactive debugging, and the first commercially available APLGOL implementation. The development of APL\3000 was led by John Walters, and Rob Kelley worked on the compiler and APLGOL design. Larry Breed and Phil Abrams assisted in developing the APL compiler.

History

In the early 1970s, HP looked at IBM's success in running APL timesharing services and set out to develop an APL implementation for their new HP 3000 computer. While all other HP 3000 language products are named with a forward slash (BASIC/3000, COBOL/3000, etc.), APL\3000 was the only one that used a backslash in the name, presumably because of IBM's choice in naming APL\360.

The HP implementation dynamically compiled APL expressions into an intermediate byte-code for a virtual "emachine", and then executed that code with some assistance from special CPU microcode instructions that also supported an APL-specific 32-bit virtual memory system. The need for a virtual machine resulted from the HP 3000's strong separation of code and data and the developers did not have a low-overhead way to dynamically emit and execute native HP 3000 instructions. As a result, performance, especially on those very early HP-3000 models, was far from ideal and even with the system's unique compilation and unlimited workspace size, it quickly developed a reputation for poor performance among customers and especially so among HP sales-reps who showed little interest in marketing it.

Even though HP continued to invest in the product and make significant improvements through the '70s, by 1979 it was clear both that the performance was not going to dramatically improve, and that the internal HP community outside of the APL development team considered it a dead product. In one case it is reported that when a potential customer called up to ask about APL on the HP 3000 they were told "It doesn't work".

The relatively poor performance, the requirement for special microcode (which meant that APL could physically only run on machines that had that non-standard firmware installed), and a list price of $15,000 (substantially higher than the other available language products), meant that APL\3000 did not see wide adoption in the HP-3000 user community. After HP lost interest in APL they chose not to implement the special APL CPU instructions on any subsequent HP-3000 model, thus consigning APL\3000 to history with the eventual obsolescence of the last HP 3000 Series III in the 1980s. Only thirty-five years later have the special APL CPU instructions been reverse-engineered, allowing APL to run once again on a simulated HP-3000 Series III.

Implementation

APL\3000's implementation was an early example of dynamic compilation or just-in-time compilation. Every function was compiled on its first invocation, resulting in both executable code for that invocation and "signature instructions" to test whether the same code could be used for later invocations. On later calls to the function, the signature code would be run first: if it failed, then the function would be recompiled with less strict requirements so that the compiled code would work for the new invocation as well as previous ones. Compilation and recompilation were both performed using stored abstract syntax trees for statements called "D-trees". The compiler targetted a stack-based "software/firmware" instruction set including typical low-level instructions as well as APL scalar functions.

The system implemented Phil Abrams' subscript calculus by storing the rank and shape of an array, along with delta and offset vectors, separately from its data—that is, the ravel, but not necessarily in ravel order. This system allowed Take, Drop, Reverse, Transpose, and Reshape to be implemented only by manipulating the shape and other fields, not the data itself. In combination with APL\3000's reference counting system, this allowed even arrays with different shapes to share the same data. Arrays whose data was a linear function of the index were stored as arithmetic progression vectors, omitting the data entirely.

Multiple functions could be combined into a single step using dragalong and beating, also designed by Abrams. Dragalong was implemented by walking up a syntax tree to propagate rank and shape information before compilation, while beating refers to subscript calculus optimizations performed during this process. Combined functions such as RANK, produced from two adjacent Shape functions, and POLYCAT, from multiple copies of Catenate could be generated in this step.

APL\3000's unlimited workspace size was implemented using a virtual memory system capable of paging parts of the workspace to disk. The least recently accessed page was always chosen to be paged out. To implement the required flat 32-bit address space on a minicomputer with a segmented, stack-oriented architecture, where a process could normally only address up to 64KiB of memory, they developed ten new CPU instructions whose microcode was included with the purchase of APL\3000 as a set of PROM chips that would be installed in the host HP-3000 Series II or III by an HP Customer Engineer. These instructions included virtual load and store between the 16-bit stack and 32-bit virtual addresses of 16-bit words and 8-bit bytes, as well as word and byte moves between virtual and stack addresses. There was also a virtual to virtual move, and two special instructions to support the "emachine" virtual machine execution engine, a fetch-and-dispatch for the 8-bit ecode instructions, and a single word load that allowed unaligned addresses relative to the current ecode program pointer, which was used by the virtual machine to load ecode parameters and immediates. The virtual memory instructions operated by searching a list of VM pages (typically 24 pages of 512 or 1,024 bytes each) that were stored at a known location in the APL process stack. If the target address was not found, control was passed to a fault handler provided by the APL system. To resolve faults, the appropriate page would be read from the on-disk workspace file into the least-recently-accessed stack page. A []VM system variable was provided that allowed user code to access and dynamically reconfigure the paging scheme and page-search mechanism.

Four internal data types were used: 8-bit characters, packed 1-bit Booleans, 16-bit integers, and 64-bit floating-point values. APL\3000 had a maximum rank of 63 and a maximum bound that, like workspace size, was limited only by available disk space (and user patience).

HP2641A Terminal

To provide the interactive experience for APL\3000, HP produced a variant of their HP2645 terminal called the HP2641A that included an APL character set and which tightly integrated with APL\3000 on the HP 3000. Non-APL ASCII and 3rd-party terminals were supported through three-character equivalents to the special APL symbols. For example, quad would be entered as "QD, iota as "IO, and rho as "RO, etc.

APLGOL

In addition to the traditional APL language, APL\3000 provided an implementation of APLGOL, which incorporated ALGOL's structured programming as advocated by Dijkstra as a replacement for Branch-based control flow. APLGOL shared its underlying implementation with APL.

The following control structures were provided in APLGOL:

• BEGIN statement list END
• IF test DO statement
• IF test THEN statement ELSE statement
• WHILE test DO statement
• REPEAT statement list UNTIL test
• CASE expression OF constant BEGIN ... END CASE

Functions were written with the PROCEDURE command:

PROCEDURE header: statement list END PROCEDURE

An ASSERT command was also provided to allow the programmer to check conditions during execution.

ASSERT level: boolean expression

The level parameter allowed for inline execution.

Publications

• HP Journal (pdf)
• APL\3000 Reference Manual (1976) (pdf)
• Ronald L. Johnston. "The Dynamic Incremental Compiler of APL\3000". APL79. doi:10.1145/800136.804442.
• Alan M. Marcum. "Secure application environments in APL\3000". APL79. doi:10.1145/800136.804470.
• Dave Elliott. "Programming for performance in APL\3000".
• Alan M. Marcum. "Multiple execution environments in APL". APL80.