MCPL

MCPL is a typeless systems programming language designed by Martin Richards at the University of Cambridge Computer Laboratory, best known as the creator of BCPL. It keeps BCPL’s view of the machine: every value is a word, there are no declared types, programs run on a contiguous stack, and there is no garbage collector. On top of that it adds the pattern matching of ML and Prolog, so functions are written as lists of match cases. Richards’ own manual (in its 2007 revision) says the name “incorporates the letters ML, C and P” in recognition of the languages it borrows from, and the “CPL” ending also points back to BCPL and CPL.

There is no sign that MCPL was ever used much beyond its author’s own research and teaching programs. Still, it is a rare case of the designer of a typeless 1960s systems language coming back decades later to ask what that model would look like with modern pattern matching.

History and Origins

From BCPL to MCPL

Richards designed BCPL in the late 1960s, and it went on to influence B and therefore C. He kept using BCPL for decades through his Cintcode and Tripos/Cintpos work at Cambridge. Meanwhile he taught ML, C and Prolog. The MCPL manual says the language’s concepts come from his “experience of using BCPL for the past 30 years and from lessons learnt using and teaching languages such as ML, C and Prolog.”

MCPL first appears in print in May 1992 as Cambridge Computer Laboratory Technical Report 256, the MCPL Programming Manual. Its abstract describes “a systems programming language having much in common with BCPL but augmented by the pattern matching ideas of both ML and Prolog.” That 32-page report gave a complete definition of the language and ended with example programs.

A note on dates. Some catalogues, including the master list behind this encyclopedia, date MCPL to 1966 and describe it as a language that influenced BCPL. That is backwards. The 1966-67 dates belong to BCPL itself, and the language that preceded BCPL was Strachey’s CPL. MCPL is a much later descendant of BCPL. The earliest dated document this page could find is the May 1992 report.

The 1997 Manual and the CMU Talks

A much larger MCPL Programming Manual and User Guide (TR 431, 70 pages) followed in July 1997. Besides the language definition, it covers the library, a command language, an interactive debugger and installation instructions for a free interpretive implementation. Later that year Richards was at Carnegie Mellon University, where, according to his home page, he gave an SCS seminar on portable target codes for compilers on 6 October 1997, and a POP seminar, Pattern Matching in a Typeless Language, on 10 December 1997.

The CMU slides put MCPL’s case directly. They contrast ML and Prolog programs with their MCPL translations and end with four conclusions: typeless pattern matching is possible; it is readable; it is simple to implement and efficient; and the MCPL compiler is small. They give its size as 35,268 bytes and say it compiles itself in 0.4 seconds on a 200 MHz Pentium Pro. The slides give no comparison figure, so this is a statement about a small self-hosting compiler on 1997 hardware, not a benchmark against other compilers.

Design Philosophy

Typelessness on Purpose

MCPL is unapologetically typeless, just as BCPL was. Every expression yields a value of the machine’s natural word size, usually 32 bits, though the manual allows for a 64-bit word on some machines. Packed 8-bit characters are still easy to reach. Richards argues in the manual that types often clutter programs, and that most data can be represented “by means of integers, strings, bit patterns and pointers to vectors composed of these kinds.” On the usual objection he says: “Although some say that lack of compile time type checking makes programs difficult to debug, I have not found this to be the case in practice.”

His CMU talk makes the same point with a mock FAQ. To “It must be really difficult to construct a large system that is completely bug free in a typeless language?” the answer is “Yes”, followed by: “It is really difficult to construct a large system that is completely bug free in any language.”

Pattern Matching without Types

ML’s pattern matching works on typed data constructors. MCPL’s question was whether the same style works when a value is only a word that might be a number, a character or a pointer. Its answer is to give patterns concrete, low-level meanings:

• A constant, a range ('A'..'Z') or an alternation (2 | 3 | 5 | 10..20) tests the word’s value
• ? or an empty pattern matches anything
• A bare name always matches and binds that name to the argument’s location
• [p1, p2, ...] treats the argument as a pointer and matches the consecutive words it points to, nested to any depth
• A relational operator and an expression (<a, =c, >a+b) compares the argument with a computed value
• An assignment operator and an expression (+:= 1) always succeeds and runs the assignment when the whole match succeeds
• Writing two patterns side by side applies both to the same argument, so coins[v] names the pointer coins and also binds v to the word it points to

Staying Close to C

MCPL has its own function-calling sequence, but it is designed so that MCPL and C functions can call each other. Its low-level operators and its GET "mcpl.h" header convention will look familiar to both C and BCPL programmers.

Key Features

Functions as Match Lists

A function definition is the word FUN, a name, and a list of match items, ended with a dot. This example from the start of the manual classifies a triangle by sorting its sides through tail-recursive calls and then pattern-matching on the sorted values:

GET "mcpl.h"

FUN start
: => writef "Enter three lengths: "
     LET a=readn(), b=readn(), c=readn()
     writef("\nTriangle entered: %d %d %d", a, b, c)
     writef("\nThis is %s triangle\n",
            sort_of_triangle(a,b,c))
.

FUN sort_of_triangle
: a, b(<a), c  => sort_of_triangle(b, a, c)
: a, b, c(<b)  => sort_of_triangle(a, c, b)
// At this point we know that a <= b <= c
: a, b, >a+b   => "not a"
: a, ?, =a     => "an equalateral"
: a, =a, ?     => "an isosceles"
: ?, =c, c     => "an isosceles"
: a, b, c      => c*c=a*a+b*b -> "a right angled",
                                 "a scalene"
.

The pointer patterns let MCPL take apart data structures with no type declarations. The manual’s coin-counting program walks a zero-terminated table of denominations:

GET "mcpl.h"

FUN ways
: 0, ?          => 1
: ?, [0]        => 0
: s, coins[>s]  => ways(s, @coins!1)
: s, coins[v]   => ways(s, @coins!1) + ways(s-v, coins)
.

Here coins[>s] matches when the first denomination is larger than the remaining sum. @coins!1, a BCPL-style subscript with an address-of operator, passes a pointer to the rest of the table.

MATCH, EVERY and Exceptions

Pattern matching also works inside function bodies:

• MATCH args : ... . tries each match item in order and runs the first one that succeeds. If none matches, it raises the PATERR exception
• EVERY args : ... . has the same syntax but runs the command list of every match item that succeeds, in order
• RAISE args raises an exception with up to three arguments, and C HANDLE : ... . catches exceptions with the same match-item syntax. Exception handlers are pattern matchers too

BCPL Heritage

Much of the rest will be familiar to BCPL programmers: VALOF expressions, MANIFEST and STATIC declarations, global declarations, vectors allocated with VEC, the ! subscript operator and % for byte access. The library also offers coroutines, stream I/O and a BCPL-style writef.

Implementation

MCPL follows the pattern of Richards’ BCPL Cintcode system. The compiler, mcpl.b, is itself a BCPL program, so the BCPL Cintcode system has to be installed first. It compiles MCPL to Mintcode, a compact interpretive code. The Mintcode interpreter is written in C. The bootstrap, library and command-line interpreter (MBOOT, MLIB and MCLI) are written in MCPL. The system includes an interactive debugger that can display Mintcode instructions, set breakpoints and single-step.

The distribution also contains an experimental native-code system, natmcpl. It translates MCPL’s internal assembly language (MIAL) into GNU assembler for Intel 386/486/Pentium machines running Linux, and a DEC Alpha syslib.s is included alongside the Linux one. The native-code README calls it a prototype and says the DEC Alpha version “will be added later”. For the distribution as a whole, Richards’ README says it was developed under Linux and “should be (easily?) transferable” to other machines, and it also ships a Windows mintsys.exe for the interpretive system; his web page describes the distribution as “only tested under Linux”.

Evolution

MCPL changed slowly and never had numbered releases:

The surviving distribution archive has file dates running from 1996 to 2016. Most of the demonstration and research programs date from 1997-2000.

Current Relevance

MCPL is a historical curiosity rather than a working tool. Richards still links it from his Cambridge home page as “a typeless language with features taken from BCPL, C, ML and Prolog”, and the manual and the 2016 archive can still be downloaded. The distribution has always called itself unpolished and under development. It is free for private and academic use only, and it depends on a matching version of the BCPL Cintcode system. There is no Docker image, package-manager build or community around it.

BCPL is better maintained. Richards’ Cintcode BCPL is still updated and runs on modern systems including the Raspberry Pi, so MCPL’s prerequisite is easier to get than MCPL itself.

Why It Matters

MCPL is a small but telling experiment. Pattern matching usually goes with strong static types, as in ML, Haskell, Rust and Scala, and with garbage-collected algebraic data. MCPL shows that the ergonomic part, writing a function as a list of cases that test and take apart their arguments, can be separated from the type system and grafted onto a language that sees memory as raw words and pointers. Range patterns, relational patterns, pointer destructuring and assignment-on-match are all designs for a machine-level language rather than a mathematical one.

It also completes a family line. BCPL came from CPL and led to B and C. MCPL is what BCPL’s designer built when he looked back at that lineage after decades of teaching ML and Prolog. It keeps BCPL’s minimalism and adds the feature he chose to build it around.