Alef

Alef was a compiled concurrent programming language for systems software, designed by Phil Winterbottom at Bell Labs for the Plan 9 operating system. It kept C’s expression syntax but added channels, processes, tasks, tuples, abstract data types, exceptions and parameterized types. Its main idea came from Rob Pike’s Newsqueak: channels as first-class values that can be sent, received and multiplexed. Alef put that idea into a native-code language used for real system software. Plan 9 shipped Alef in its First and Second Editions and dropped it in 2000. It still matters because it links Newsqueak to Limbo and, eventually, to Go.

History and Origins

From Squeak to Newsqueak to Alef

Concurrent languages at Bell Labs have a long lineage. In 1985, Luca Cardelli and Rob Pike published Squeak, a small language for writing user-interface code with ideas taken from Tony Hoare’s Communicating Sequential Processes (CSP). Pike then turned it into Newsqueak, a full interpreted language whose channels are first-class objects. They can be stored in variables, passed to functions and sent over other channels.

Russ Cox, a later Plan 9 contributor, describes the next step: Alef “was a language designed by Phil Winterbottom to apply the Newsqueak ideas to a full-fledged systems programming language.” Newsqueak was a research language. Alef was meant to compile to native code and run the operating system’s own tools. According to the Plan 9 FAQ, Alef “is named analagously to B and C, just choosing from a new alphabet”. Aleph is the first letter of the Hebrew alphabet.

Dating the language

Encyclopedias, including Wikipedia, give 1992 as Alef’s first appearance. That is the year usually given for Plan 9’s First Edition, which went only to universities. The dates are a little uncertain:

• The First Edition Programmer’s Manual is copyrighted 1993, and all its pages are dated 20 January 1993. It includes an alef(1) page for the kal and val compilers, so Alef was working and documented by the start of 1993. It must have been built during 1992 or earlier.
• The Plan 9 FAQ on 9p.io says the First Edition was “released in 1993”. Wikipedia’s Plan 9 article says 1992.
• In his 2012 talk “Go Concurrency Patterns”, Rob Pike lists “Alef (Winterbottom, 1995)”. That is the year of the Second Edition, when the reference manual and User’s Guide were published in the widely distributed Volume Two.

This page uses 1992. The firmest evidence of a public release is the January 1993 manual.

Second Edition, 1995

The Second Edition was the first version of Plan 9 available beyond universities. Alef was a central part of it. The manual preface (March 1995) says Plan 9 “has its own programming languages: a dialect of C with simple inheritance, a simplified shell, and a CSP-like concurrent language, Alef”. It credits “Winterbottom, Alef”. Two papers documented the language in Volume Two:

• Alef Language Reference Manual by Phil Winterbottom, the formal definition.
• Alef User’s Guide by Bob Flandrena, a tutorial on the concurrency features.

Bell Labs’ Plan 9 source archive still has extra/alef.tgz. It contains the compiler, libraries, headers, manual pages and documentation, with files dated 4 April 1995. It includes compiler back-ends for 8 (x86), k (SPARC) and v (MIPS).

Abandonment

Alef did not survive into the Third Edition. The June 2000 preface explains why:

Alef is gone, a casualty of the cost of maintaining multiple languages, compilers, and libraries in a diverse world, but its model for processes, tasks, and communication lives on in a new thread library for C.

Rob Pike made the same point in his slides on the rio window system: “although Alef was a fruitful language, it proved too difficult to maintain a variant language across multiple architectures, so we took what we learned from it and built the thread library for C.” Every new Plan 9 processor port needed a new Alef compiler back-end and separate Alef libraries. Wikipedia, citing a later Pike talk, reports that he also blamed Alef’s lack of garbage collection, which he and others had reportedly urged Winterbottom to add.

Russ Cox writes that the thread library, libthread, “was originally created to port Alef programs to C, so that the Alef compilers could be retired”. Sape Mullender wrote it for the Third Edition. Alef’s procs and tasks became libthread’s procs and threads.

Design Philosophy

The reference manual summarizes the language in one paragraph:

Alef is a concurrent programming language designed for systems software. Exception handling, process management, and synchronization primitives are implemented by the language. Programs can be written using both shared variable and message passing paradigms. Expressions use the same syntax as C, but the type system is substantially different. Alef supports object-oriented programming through static inheritance and information hiding. The language does not provide garbage collection, so programs are expected to manage their own memory.

Three principles shaped the design:

1. Concurrency in the language, not in a library. Creating processes, sending and receiving on channels, and waiting on several channels at once are all built into the syntax. The compiler turns them into calls to the run-time system.
2. Stay close to C. The User’s Guide says that “an Alef program looks like a C program: the syntactic structure is similar and the expression syntax is almost identical”. Alef even runs its source through the ANSI C preprocessor.
3. Offer both concurrency styles. Programmers can pass messages over channels or share memory and use locks. The User’s Guide says “the styles can be freely mixed”.

Key Features

Procs and tasks

Alef has two levels of concurrency:

A task switches only on channel sends and receives, alt, QLock.lock or Rendez.sleep. Tasks in the same proc can therefore share data without locks between those points. Pike’s Acme and rio designs relied on this. On Plan 9, the run-time creates procs with rfork and synchronizes them with the rendezvous system call. The default stack for each task was 16,000 bytes, set by the ALEFstack variable.

Channels and alt

Channels are typed and can be synchronous or buffered, like chan(int)[10] for a 10-element buffer. <-= sends and <- receives. The alt statement waits on several channel operations and runs whichever one is ready first. A channel can also carry a variant protocol of several types, and alt can branch on the type of the received value.

This message-passing program comes from the Alef User’s Guide:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include	<alef.h>

void
receive(chan(byte*) c)
{
	byte *s;

	s = <-c;
	print("%s\n", s);
	terminate(nil);
}

void
main(void)
{
	chan(byte*) c;

	alloc c;
	proc receive(c);
	c <-= "hello world";
	print("done\n");
	terminate(nil);
}

The main process allocates a channel that carries a string address. It starts a new process with the channel as an argument, sends the string, prints a message and terminates.

Tuples

Functions can return several values in a tuple and unpack them by assignment. This example comes from the reference manual:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

(int, byte*, byte)
func()
{
    return (10, "hello", 'c');
}

void
main()
{
    int   a;
    byte* str;
    byte  c;

    (a, str, c) = func();
}

Abstract data types

An adt declares data members and member functions together. By default, data members are private to member functions and member functions are public. extern exports a data member and intern hides a member function. A member function declared with *Point automatically receives a pointer to the value it is called on, which the manual compares to Smalltalk’s self:

1
2
3
4
5
6
7

adt Point
{
            int   x;             /* member functions only */
    extern  int   y;             /* everybody */
            Point set(*Point);   /* receives &p implicitly */
    intern  Point tst(Point);    /* member functions only */
};

Polymorphism and parameterized types

Alef had a polymorphic type. Its values are “fat pointers” that hold a type tag and a pointer to the value. It also had parameterized ADTs, which the manual compares to generics in Ada and Eiffel. (alloc Poly) 10 boxes a value, and the zerox operator makes a separate copy of a boxed value.

Exceptions and assertions

rescue blocks define error-recovery code, and raise jumps to the nearest earlier rescue in the same function. Named rescues and chains of rescues allow layered cleanup. check expr, "message"; is a run-time assertion: it calls a replaceable handler and by default exits with status ALEFcheck.

1
2
3
4
5
6
7
8

alloc a, b;
rescue {
    unalloc a, b;
    return 0;
}
dostuff();
if(error)
    raise;

Other features

• Iterators: the :: operator creates an implicit loop around a statement. This copies a string: to[0::strlen(from)+1] = *from++;
• Guarded blocks: !{ ... } introduces a guarded block. The manual says “only one thread may be executing the statements contained in the guarded block at any instant”. alt and switch case lists can be guarded the same way.
• Explicit memory: alloc and unalloc statements replace malloc and free. A failed allocation raises a check condition, and freeing an object twice is reported as “arena corrupted”.
• Built-in lock types: Lock is a spin lock and QLock is a blocking lock.

Implementations and Platforms

Alef source files use the .l extension. As in Plan 9 C, the compilers are named after their target (8al produces .8 object files for the 8l loader). There is no official or community Docker image.

Evolution and Legacy

Successors inside Bell Labs

• Limbo (1996): Inferno’s language was designed by Dorward, Pike and Winterbottom, and Alef’s author was one of its three designers. Russ Cox writes that Limbo “was heavily influenced by Alef” but removed the difference between procs and tasks, so all its parallelism is preemptive. Unlike Alef, Limbo ran on a virtual machine.
• libthread (2000): The Third Edition’s C thread library kept Alef’s process, task and channel model. Acme and the window system were converted to it, and the model continues in Plan 9 from User Space (plan9port).

Go and Rust

Pike’s 2012 talk “Go Concurrency Patterns” lists Alef in the history of CSP-based languages and says: “Go is the latest on the Newsqueak-Alef-Limbo branch, distinguished by first-class channels.” cat-v.org’s Plan 9 documentation archive also calls Go “another descendant of Alef”. Go’s own FAQ names only Newsqueak and Limbo as the sources of its concurrency, so Alef’s influence on Go is best understood as coming through that lineage.

The Rust Reference’s “Influences” page lists “Newsqueak, Alef, Limbo: channels, concurrency”. The page notes that its list includes design elements Rust has since removed.

Current Relevance

Alef is a historical language. No maintained Bell Labs or Plan 9 Foundation implementation exists, and no Plan 9 release since 2000 has included it. What survives:

• The 1995 reference manual and User’s Guide, preserved on doc.cat-v.org and in the Plan 9 source archive.
• The original source archive (extra/alef.tgz) on 9p.io.
• Hobbyist ports by Pavlovskii Anton for FreeBSD/i386 (via plan9port libraries) and for Plan 9 Fourth Edition. They are small projects, and the Unix port is still incomplete.

Why It Matters

Alef was among the first languages to put first-class CSP channels into a compiled, C-like systems language used for real operating-system software. Acme and the Brazil window system showed that complex interactive programs could be built from simple communicating processes. Pike reported that Acme’s concurrent I/O code “worked the first time”.

Its failure was instructive too. Maintaining a separate compiler and library set for every processor architecture cost too much for a small research group, and manual memory management clashed with the lightweight channels and processes that programmers wanted. Limbo added garbage collection and a virtual machine, libthread moved the model into a C library, and Go later combined garbage collection, native compilation and first-class channels.