HAL/S

HAL/S is a high-level, real-time programming language that Intermetrics, Inc. designed for NASA in the early 1970s, mainly to write the flight software for the Space Shuttle. Most real-time languages of the time left mathematics to libraries. HAL/S makes vectors and matrices built-in data types and lets programmers schedule, signal and cancel concurrent tasks with ordinary statements. It also has an optional three-line source format that puts exponents and subscripts above and below the main line, as in printed mathematics. JPL’s 1981 summary describes it as “the NASA standard high-order real-time programming language for avionics applications” and says roughly 85% of the Shuttle software was coded in it. For thirty years, from STS-1 in 1981 to STS-135 in 2011, HAL/S code flew on the orbiter.

History & Origins

From Apollo assembly language to a flight language

The Apollo Guidance Computer was programmed in assembly language and an interpreted pseudo-language. In Computers in Spaceflight: The NASA Experience (1988), historian James Tomayko writes that the delays and expense of Apollo software development, and the realization that the Shuttle’s software would be “many times as complex”, led NASA to encourage a language “optimal for real-time computing”. Tomayko adds that, by the estimates of the time, such a language could cut the Shuttle software development cycle by 10% to 15%.

The language came from Intermetrics, a Cambridge, Massachusetts firm formed in 1969 by former Draper Laboratory staff who had worked on the Apollo software. Under NASA contract NAS9-10542, the company delivered The Programming Language HAL – A Specification to the Manned Spacecraft Center in Houston in June 1971. The NASA technical monitor named in it is Jack Garman. A follow-on report at the end of 1971 described a “HAL-in-HAL” experiment, which showed that the compiler could be written in HAL itself.

A 1985 account by JPL’s Allan Klumpp, quoted by the University of Toronto’s XPL archive, says the first version of HAL was a FORTRAN preprocessor. In 1972 that approach was dropped and the language was renamed HAL/S (“S” for Shuttle). From then on, compilers were written in XPL, a language for writing compilers, and emitted a machine-independent intermediate form called HALMAT, so that code generators could be added for new flight computers. Michael Ryer’s Programming in HAL/S says the language “was developed between 1970 and 1972” and that afterwards “changes which would invalidate existing HAL/S code have been resisted.” JPL’s 1981 history says HAL/S “was designed by Intermetrics, Inc., in 1972. Compilers became available in 1973.”

Winning over the assembly-language programmers

A high-level language for flight code was controversial. Tomayko writes that the proposal “met vigorous opposition from managers used to assembly language systems,” and that they made the same argument once made against FORTRAN: compiled code would be slower and larger than hand-written code. Richard Parten, first chief of the Johnson Space Center’s Spacecraft Software Division, responded with a benchmark. IBM chose its best assembly-language programmers to code a set of test programs. The same functions were written in HAL, and the two versions were run against each other. Tomayko reports that the running times differed by roughly 10% to 15%, which was close enough to quiet the objectors. He does not name the individual test programs, so the comparison covers only that set of programs as compiled by the HAL compiler of the time.

Parten later remarked that, given how often the requirements changed, NASA would still be trying to get the Shuttle “off the ground” if the software had been written in assembly language.

What does “HAL” stand for?

No official expansion exists. 2001: A Space Odyssey (1968), with its computer HAL 9000, was in cinemas while the language was being defined, but Tomayko notes that “NASA officials deny any relationship between the names.” The explanations in circulation are:

• Hal Laning. Both the 1971 HAL specification and the 2005 HAL/S specification acknowledge “the fundamental contribution” of Dr. J. Halcombe Laning of the Draper Laboratory to MAC, the language whose two-dimensional format HAL adopted. The Virtual AGC project reports that Intermetrics co-founder Ed Copps “is said to have named the HAL/S language in honor of Hal Laning”. NASA’s John R. (Jack) Garman told Tomayko the name may have come from “a fellow involved in the early development whose name was Hal.”
• An acronym. “High-order Assembly Language/Shuttle” is often repeated, and Tomayko also records “Higher Avionics Language”. Virtual AGC found one NASA report that calls it “Houston Aerospace Language”.

Design Philosophy

The 1971 specification gives three objectives, and the 2005 specification repeats them almost word for word:

1. Readability, “through the use of a natural two-dimensional mathematical format”
2. Reliability, “by providing for selective recognition of common data and subroutines, and by incorporating specific data-protect features”
3. Real-time control, “by including a comprehensive set of real-time control commands and signal conditions”

The specifications name PL/I and ALGOL as the main syntactic influences, and the two-dimensional notation comes from Draper Laboratory’s MAC/360. HAL/S was intended for engineers who think in vectors and coordinate frames. Ryer’s book assumes its readers know FORTRAN or PL/I.

Key Features

Program structure

A HAL/S compilation unit is a labelled PROGRAM, PROCEDURE, FUNCTION or COMPOOL block, closed by CLOSE. Declarations come first. A minimal program from Ryer’s book:

   SIMPLE: PROGRAM;
C  CODE IN THIS TYPEFACE IS
C  HAL/S SOURCE
   DECLARE PI CONSTANT (3.14159266);
   DECLARE R SCALAR;
   READ(5) R;
   WRITE(6) PI R**2;
   CLOSE SIMPLE;

Column 1 is reserved: C marks a comment line, D a compiler directive, and E, M and S the lines of the multi-line format. From column 2 onward the source is free-form. In PI R**2, the multiplication is written as juxtaposition; HAL/S has no multiplication operator for ordinary products. Inline comments use /* ... */.

Mathematics as data types

The declared types are INTEGER, SCALAR (floating point), VECTOR(n), MATRIX(m,n), BIT(n), BOOLEAN, CHARACTER(n) (varying length, with an implementation-defined maximum) and EVENT, each in SINGLE or DOUBLE precision where that applies. Data can be grouped into ARRAYs and STRUCTURE templates. The operators know linear algebra:

A plain MATRIX declaration means MATRIX(3,3), the usual size for a coordinate transformation.

The three-line format

A statement can be written on one line, or across an E (exponent) line, an M (main) line and an S (subscript) line. The single-line statement

   X = A**2 + B$(I)**2;

can also be written as

E       2     2
M  X = A  + B
S            I

According to one of the original developers, quoted by the Virtual AGC project, programmers almost always typed single-line source. However, the Intermetrics compiler always printed its listings in the multi-line form. It put type marks (“overpunches”) over each variable on the E line, such as a bar for vectors and an asterisk for matrices, so that a reviewer could see an expression’s types at a glance.

Real-time statements

Concurrency is part of the language. Ryer’s example sets up guidance, navigation and control tasks at different rates and priorities:

STARTUP: PROGRAM;
   GUIDANCE: TASK;
      /* ... */
   CLOSE GUIDANCE;
   NAVIGATION: TASK;
      /* ... */
   CLOSE NAVIGATION;
   CONTROL: TASK;
      /* ... */
   CLOSE CONTROL;
   SCHEDULE NAVIGATION PRIORITY(60), REPEAT EVERY 1.0;
   SCHEDULE GUIDANCE PRIORITY(70), REPEAT EVERY 1 / 6;
   SCHEDULE CONTROL PRIORITY(80), REPEAT EVERY 1 / 20;
CLOSE STARTUP;

The rest of the real-time vocabulary is WAIT, CANCEL, TERMINATE, UPDATE PRIORITY, and SET, RESET and SIGNAL on EVENT variables. Errors are handled with ON ERROR and SEND ERROR. On the Shuttle, Tomayko writes, “a key requirement” of the Flight Computer Operating System (FCOS) was to handle these statements. Shared data lives in COMPOOL blocks, and the LOCK attribute together with UPDATE blocks protects data that several processes access at once.

Systems-language extensions

Later versions of the specification add facilities for systems programming: NAME variables, which act as typed references, %macro built-ins, TEMPORARY loop variables and EQUATE statements. These sit beside the “applications” language that most flight code used.

Evolution

Compilers and targets

Intermetrics’ compilers were hosted mainly on IBM System/360 and 370 mainframes. Lytle’s 1981 table lists these targets:

Some of these compilers implemented only subsets of the language, and not every one was finished. The University of Toronto’s XPL archive, quoting Klumpp, says the Eclipse-hosted compiler fell out of use because address-space limits slowed compilation to about 30 lines a minute. The Shuttle’s own compiler, HAL/S-FC, ran on IBM mainframes and produced AP-101 object code. Klumpp’s survey also lists Spacelab and the Global Positioning System among HAL/S applications. A separate HAL/SM language specification for NASA Marshall followed in 1975.

Writing the compilers in XPL made new code generators easy to add but rehosting hard. Klumpp noted that XPL “was available for a very few machines”, so XPL itself had to be ported to a new host before HAL/S could follow.

HAL/S and Ada

In 1976 the Department of Defense’s High Order Language Working Group compared 23 existing languages, HAL/S among them, against its Tinman requirements. In January 1977 it concluded that none was suitable as it stood, and the effort went on to produce Ada. HAL/S reportedly fared relatively well: a DTIC evaluation report lists it among the languages not found inappropriate to serve as a base for the new language. Intermetrics entered the competition with the “Red” design, which lost to the “Green” design that became Ada. When NASA planned the Space Station in the mid-1980s, Klumpp set out the choice in IEEE Computer (March 1985) as “Space Station Flight Software: HAL/S or Ada?”. By 1986 JPL was writing Ada packages that reproduce “all of the vector-matrix, array, and arithmetic functions described in the HAL/S manuals,” so that avionics programmers could “code in Ada as they have coded in HAL/S.”

Maintenance through the Shuttle era

The Shuttle program stayed on HAL/S until the end. The compiler was maintained alongside the flight software and was a source of risk in its own right. Tomayko reports that just days before STS-7 in June 1983, an IBM employee found a bug in the latest compiler release. More than 200 flight modules had been recompiled with it, and all had to be checked before launch. United Space Alliance maintained the language documentation; the latest specification that is publicly available, revision 32.0/17.0, is dated November 2005. The program’s last flight, STS-135, was in July 2011.

Current Relevance

HAL/S has no active users, and no compiler is sold. Its preservation has been led mainly by Ron Burkey’s Virtual AGC project, which hosts the language manuals, Ryer’s book and the Basic HAL/S Programming course. Its repository holds the source of the HAL/S-FC Release 32 compiler; the folder was reorganised and its missing files added in April 2023. That source is written in Intermetrics’ extended dialect of XPL, which Burkey calls “XPL/I”. Intermetrics’ own XPL compiler apparently did not survive, so the project wrote a new XPL/I-to-C compiler, XCOM-I, to rebuild HAL/S-FC. It also hand-ported the compiler’s first pass to Python, and wrote a HALMAT emulator (yaHALMAT2) and an AP-101S assembler, linker and emulator. Simple HAL/S programs can be compiled and run with these tools. The Shuttle flight software itself is still not public: Burkey received PASS and partial BFS source only on condition that he not distribute it, and he treats it as ITAR-restricted.

Why It Matters

• It flew. HAL/S was the main language of the Space Shuttle’s flight software from STS-1 in 1981 to the end of the program in 2011, and its record showed that compiled high-level code could meet the timing and memory limits of crewed spacecraft.
• Domain types in the language. Tomayko notes that no other early-1970s language adequately provided either built-in vector arithmetic or priority-based task scheduling, and HAL/S combined both with shared-data locking.
• Readable source as a requirement. The multi-line notation and the compiler’s fixed listing format were designed for code that would be read and reviewed more often than it was written.
• A link to Ada. HAL/S was one of the 23 languages measured against the DoD’s requirements on the way to Ada, and NASA’s later move to Ada began with reproducing HAL/S’s built-in mathematics as Ada packages.

Sources and Verification Notes

• Year. The encyclopedia master list gives 1968, but no source supports it, and Intermetrics was not founded until 1969. The predecessor language HAL was specified in June 1971. Ryer gives 1970–1972 for HAL/S’s development, and JPL’s Lytle (1981) gives 1972 for its design and 1973 for the first compilers. This page uses 1972.
• “2 million lines”. Lytle’s figure covers “comments, data declarations and executable lines of code”, not executable statements alone.
• The 10–15% benchmark. This comes from Tomayko’s secondary account. The individual test programs and the compiler version are not documented there.