NIL

NIL (Network Implementation Language) is a high-level programming language for distributed and communications systems. It was developed at IBM’s Thomas J. Watson Research Center in Yorktown Heights, New York, starting in the late 1970s. Most programming languages of its era assumed a single shared memory. NIL instead built every program from isolated processes that share no data and talk only by passing messages through typed ports. It also brought in typestate, a compile-time check that tracks which operations are legal on each variable at each point in a program. Typestate went on through NIL’s successor, Hermes, and the Rust Reference credits NIL and Hermes for Rust’s early typestate system.

Not to be confused with MIT’s NIL. “NIL” also names a different and unrelated language: MIT’s New Implementation of Lisp, a Maclisp successor for the VAX that Jon L White led from about 1979. This page covers the IBM language.

History & Origins

NIL came from the Distributed Systems Software Technology (DSST) group at IBM Research. According to Strom and Yemini’s status report, the language’s initial design took place between 1978 and 1981. The 1983 IBM Systems Journal paper credits the team responsible for developing NIL and its tools as W. Burger, M. H. Comer, N. Halim, F. N. Parr, J. A. Pershing, R. E. Strom and S. Yemini. At the time of that paper, Francis Parr was manager of the project developing the NIL methodology.

The language grew out of a practical problem. IBM’s Systems Network Architecture (SNA) defined protocols that had to run on very different machines: data-processing hosts, communications controllers and intelligent workstations. Each product group wrote its own implementation, usually in assembler or PL/S. Every time the architecture changed, the protocol logic was re-implemented several times by different teams. Parr and Strom described the result as “a profusion of subset implementations and an obligation to test all possible combinations.”

The DSST group’s answer was to write each protocol layer once, in a machine-independent language that was safe enough to run alongside untrusted code, and then compile it for each product. The group had first written NIL to implement experimental software for new and proposed communications protocols. It started from a technique for the formal specification of protocols and turned that technique into a full programming language.

A compiler for the full language, apart from real numbers, was finished early in 1982 for the IBM 370. It generated PL/S code that ran under OS/VS2 (MVS) and the Conversational Monitor System (CMS). IBM published the Draft NIL Language Reference Manual as Research Report RC-9732 in December 1982. Papers followed in 1983 at POPL, in the IBM Systems Journal and at the ACM SIGPLAN Symposium on Programming Language Issues in Software Systems.

Design Philosophy

The 1983 Systems Journal paper sets out three main strategies.

Representation-independent data

NIL programs describe what data means, never how it is laid out in memory. The paper’s example is a network routing table. In Pascal or PL/I, a fixed-size array version and a balanced-tree version of the same lookup share almost no code. In NIL the programmer writes the lookup once against an abstract table. The compiler then picks an array, a tree or some other representation, either on its own or as directed by a pragma. The language definition guarantees that the choice of representation affects only performance, never meaning.

The authors split development into two phases: a functional design phase, where algorithms are written and debugged with no thought for data layout, and an optimization phase, where representations are chosen to meet code-size, throughput or response-time targets.

Security without hardware protection

NIL uses Tony Hoare’s definition of a secure language: every syntactically incorrect program is rejected by the compiler, and every accepted program gives a result or an error message that can be explained in source terms. NIL extends this. A set of modules shown to work correctly must not be made to fail by other modules running beside them that have no language-defined interface to them.

To get that guarantee without memory-protection hardware or expensive run-time checks, NIL:

• forbids visible pointers. Programs never manipulate addresses directly.
• forbids shared variables. Every variable belongs to exactly one process.
• prevents detectable aliasing. Within a module, each variable name has an independent value.
• checks typestate at compile time, so invalid sequences of operations are rejected before the program runs.

As a result, the paper says, a NIL run-time system need not do garbage collection, check for uninitialized data, guard against concurrent access to a data item, or worry about a process ending without freeing its resources.

System concepts in the language

Tasking, loading new code and wiring processes together were language primitives, not operating-system calls. The designers argued that a language that forces programmers to “escape” into the operating system for dynamic connections cannot keep its security guarantees.

Key Features

Type families

Instead of building everything from arrays and pointers, NIL offered a fixed set of high-level type families. The 1983 paper lists fifteen, including:

Processes and ports

A NIL system is a dynamically changing network of processes, each with private memory. Processes talk in two ways:

• Asynchronous: a message is sent on a sendport and queued at the connected receiveport.
• Synchronous: a callport is connected to an acceptport or a procedure, giving rendezvous-style calls.

Ports are statically typed, but they are bound at run time. The operations publish, connect and create let a running system install new modules and connect them to existing ones, with a type-compatibility check when the connection is made. Access to ports is controlled by capabilities stored in catalogs. A module’s creator therefore decides which bindings the new module may ever make. Every module can be compiled and checked in isolation, without knowing what it will later be connected to.

Typestate

Typestate is NIL’s best-known contribution. For each type, the compiler builds a state machine whose states (typestates) say which operations are currently allowed on a variable. It then tracks every variable from statement to statement. A message variable, for example, is uninitialized before allocate or receive, and it becomes uninitialized again after send or discard, because the sender gives up all access to the message when it sends it.

The following valid NIL fragment is adapted from the 1983 IBM Systems Journal paper. The listing here is reconstructed from a scanned copy, so details of the original layout may differ:

1
2
3
4
5
6
7
8

-- MSG1_TYPE is a message type defined elsewhere with integer field F1
-- APORT is a declared variable of type "sendport of MSG1_TYPE"
block
  declare (MSG1: MSG1_TYPE)
  allocate MSG1;
  MSG1.F1 = 3;
  send MSG1 to APORT;
end block;

If the same statements are put in the wrong order, for example by setting a field after the message has been sent, every operation still has operands of the right type. A conventional type checker would accept the program. A NIL compiler rejects it as a typestate error.

To make this checkable at compile time, NIL adds a strict rule: the typestate of every variable must be the same at a given statement however that statement was reached. Where control-flow paths join, the compiler inserts coercions that bring each variable down to its “least initialized” state, such as an automatic discard, and it issues a warning. Combined with exception handling, these coercions give automatic clean-up. When an exception sends control to a handler, any variables that would be left in an inconsistent state are finalized for the programmer.

Exceptions

Many operations on high-level type families can fail, so each operation’s exceptions are listed in the language reference, together with their effect on typestate. An exception passes outward through the static block structure to the nearest handler that names it. The paper’s routing example handles a failed table lookup like this (adapted from the same scanned figure):

1
2
3
4
5
6

block
  find AROW in ROUTTAB key(MSG1.DEST_FIELD);
  send MSG1 to AROW.LINK;
on (NOT_FOUND)
  -- error action for unknown address
end block;

The same source works whether ROUTTAB ends up stored as an array, a tree or some other structure.

Evolution

After the first compiler, the NIL team worked on generalizing pragma support and on an interpretive execution scheme so NIL systems could run on small machines. Strom and Yemini’s status report, presented at the 1984 Seminar on Concurrency at Carnegie Mellon and published in 1985, described further research:

• a formal semantic theory for NIL, with Milner’s CCS (Calculus of Communicating Systems) under study as a candidate
• program transformations that map NIL programs to efficient distributed and parallel implementations

Strom and Yemini’s paper “Typestate: A programming language concept for enhancing software reliability” (IEEE Transactions on Software Engineering, January 1986) set the typestate idea out on its own terms.

NIL’s direct successor was Hermes, developed at IBM Research from about 1986 through 1992 and described in the 1991 Prentice-Hall book Hermes: A Language for Distributed Computing. Hermes kept NIL’s main ideas: processes and interprocess communication in the language, representation-independent tables, no pointers, and compile-time typestate checking.

Current Relevance

NIL is a historical language. Its compiler was an internal IBM Research tool, and no public implementation or source release is known. The language survives in its papers and its research reports.

Its ideas have outlived it:

• Typestate is still a research topic in program analysis and language design. The NIL papers are where it was first formalized as a language-wide invariant. The 1983 paper notes that, to the authors’ knowledge, no earlier work had tried “to formalize typestate and require it to be a general program invariant.”
• Rust briefly had a typestate system in its early design. The Rust Reference’s list of influences names “NIL, Hermes: typestate”, now struck through because the feature was removed.
• Several of NIL’s distributed-systems ideas are now common: isolated processes that communicate only by messages, ownership passing on send so the sender can no longer touch the data, and capability-controlled dynamic binding of typed interfaces.

Why It Matters

NIL took on a hard problem early: software that is safe, modular and portable across very different machines in a distributed system. It did so without garbage collection, hardware memory protection or heavy run-time checks. Its approach was to move safety into the compiler. The language hid pointers and kept data unshared, which gave the compiler enough information to prove properties that other languages could only check at run time or leave to programmer discipline.

The idea of a single owner for data that moves between processes, enforced statically, is close to how ownership and move semantics work in later languages. The only lineage directly documented is narrower: typestate passed from NIL to Hermes, and from both to Rust’s early design. Through that line, a 1970s IBM language for SNA protocol prototypes is part of the background of modern safe systems programming.

Sources and Notes

• F. N. Parr and R. E. Strom, “NIL: A high-level language for distributed systems programming,” IBM Systems Journal 22(1/2), 1983, pp. 111-127. This is the main source for the design, type families, typestate, compiler and uses described above.
• R. E. Strom and S. Yemini, “NIL: An integrated language and system for distributed programming,” ACM SIGPLAN Symposium on Programming Language Issues in Software Systems, June 1983, pp. 73-82.
• R. E. Strom, “Mechanisms for compile-time enforcement of security,” POPL ‘83, Austin, Texas, January 1983.
• R. E. Strom and S. Yemini, “The NIL distributed systems programming language: A status report,” Seminar on Concurrency, LNCS 197 (1985), pp. 512-523; see also “The NIL distributed systems programming language,” ACM SIGPLAN Notices 20(5), May 1985, pp. 36-44. The status report is the source of the 1978-1981 design dates and the early-1982 compiler date.
• R. E. Strom and S. Yemini, “Typestate: A programming language concept for enhancing software reliability,” IEEE Transactions on Software Engineering SE-12(1), January 1986.
• The Rust Reference, “Influences” chapter.

No performance figures are given above. The 1983 paper states that it was “not yet possible to offer any quantification of the software productivity gain achieved,” and no benchmark results for the NIL compiler have been found.