Hope

Hope is a small, strongly typed functional programming language designed at the University of Edinburgh by Rod Burstall, David MacQueen and Don Sannella, and presented to the world at the 1980 LISP Conference at Stanford. Its authors described it as an experiment rather than a finished product, but it introduced a combination of features that every modern typed functional language now takes for granted: user-defined algebraic data types, functions defined by pattern-matching equations over those types, and polymorphic static typing. The History of Haskell calls Hope “the language that introduced algebraic data types”, and Standard ML took its datatype mechanism directly from it.

History & Origins

From NPL to Hope

Hope’s roots lie in Rod Burstall’s work on program transformation. In the mid-1970s Burstall and his student John Darlington built a system for transforming simple, clear recursive programs into efficient ones while preserving correctness, published in the Journal of the ACM in January 1977. The programs it worked on were written in a tiny first-order equational language. Burstall extended that language with a simple form of data type and pattern matching, calling the result NPL, and described it in his 1977 paper “Design Considerations for a Functional Programming Language”.

According to MacQueen, Harper and Reppy’s history of Standard ML, Hope was developed by Burstall’s group “just after LCF/ML from 1977 to 1980”. MacQueen and Burstall, later joined by Sannella, took NPL and added the polymorphic types and first-class functions of Robin Milner’s ML, the metalanguage of the LCF theorem prover being built in the same university. The 1980 paper credits Milner and Michael Gordon with showing the team how to handle polymorphic types, Darlington with helping develop NPL, and Michael Levy with part of the implementation, and adds that “Peter Landin’s influence was pervasive”.

The name

Despite being written in capitals in the original paper, HOPE is not an acronym. It refers to Hope Park Square in Edinburgh, the building where the language was developed.

The 1980 system

The original implementation was a compiler from Hope to code for an abstract stack machine, together with a simulator for that machine. Both were written in POP-2, the language Burstall had co-designed with Robin Popplestone, and in 1980 the system ran in about 55K words (plus a 15K shareable segment) on a DEC KI-10. The authors expected the compiled code to be portable, since only the abstract machine would need rewriting, but noted that the compiler itself depended on POP-2.

They were candid about speed. Their preliminary tests found that a Hope program ran approximately 9 times slower than the same algorithm in LISP under the Rutgers/UCI interpreter, and 23 times slower than compiled LISP, on that DEC KI-10 system; a larger program ran slower still, which they attributed to page thrashing. They expected a machine-code implementation of the abstract machine to be much faster, and saw program transformation as the route to acceptable efficiency.

Design Philosophy

The 1980 paper opens with a list of features the authors considered important “in a language for writing correct and flexible programs”, and Hope was designed to demonstrate them:

• No assignment. Variables are given a value once; recursion replaces loops. The authors acknowledged this slows execution but argued it greatly simplifies programs.
• Maximum use of user-defined types. Programmers should define types such as age rather than encode everything as integers, and the machine should check them.
• Polymorphic types, so that code can work over “list of alphas” rather than only lists of numbers.
• Overloaded operators resolved by the type checker.
• Exhaustive case analysis, so a compiler can check that every constructor of a type is handled.
• Avoiding unnecessary names. Instead of separate functions to construct (cons), test (null) and take apart (car, cdr) data, the constructor name alone serves all three roles through pattern matching.
• Packaging recursion in higher-order functions such as LISP’s mapcar, rather than writing explicit recursion everywhere.
• Lazy sequences as data objects, giving coroutine-like behaviour and a possible basis for interactive I/O.
• Modularity and data abstraction, with control over which types and constructors a module exports.

The authors stressed that they “were not trying to be original” but sought “a judicious selection of well-understood ideas”, aiming for “some blend of LISP power with the discipline of strong typing and modularity”. They reported that it was “significantly easier to construct programs in HOPE than in any other programming language we know”, and that it was “rather easy to write programs which are absolutely correct the first time they are run”.

Key Features

Data declarations

A data declaration introduces a type and its constructors, separated by ++. Constructors with several fields take a tuple, written with # in the type:

data tree alpha == empty ++ node(tree alpha # alpha # tree alpha);

Here tree is a type constructor and alpha a type variable, so the same declaration gives trees of numbers, trees of lists and trees of trees. The History of Haskell points out that Hope and Standard ML kept sums (algebraic types) and products (tuple types) separate in exactly this way, whereas Miranda and Haskell later treated each alternative as a product of fields.

Equational function definitions

Every function is first declared with its type using dec, then defined by one or more equations, each introduced by ---, whose left-hand side is a pattern:

dec fact : num -> num;
--- fact 0 <= 1;
--- fact n <= n * fact(n - 1);

dec insert : num # tree num -> tree num;
--- insert(n, empty) <= node(empty, n, empty);
--- insert(n, node(l, m, r)) <=
        if n < m then node(insert(n, l), m, r)
                 else node(l, m, insert(n, r));

dec flatten : tree alpha -> list alpha;
--- flatten empty <= [];
--- flatten(node(l, m, r)) <= flatten l <> (m :: flatten r);

Run under Ross Paterson’s interpreter, fact 10; prints 3628800 : num and flatten(insert(3, insert(1, insert(2, empty)))); prints [1, 2, 3] : list num. The interpreter reports both the value and its type.

Strong, polymorphic typing

The 1980 system included what its authors called “a polymorphic typechecker (a modification of the algorithm in [Milner 1978]) which is able to detect all type errors at compile time”. Functions must have their types declared with dec, and the type checker infers the types of their definitions and compares the two. In Paterson’s interpreter a mismatch is reported with both types:

1
2
3

  declared type: num -> num
  inferred type: list num -> list num
line 2: type error - 'bad': does not match declaration

Hope also had an unusually general overloading scheme. The Standard ML history notes that functions, constants and data constructors could all be overloaded, resolved against the full contextual type, so that even a constant could be overloaded on its result type. The scheme coexisted with polymorphism but its resolution algorithm was non-trivial, and Standard ML did not adopt it.

Higher-order functions and lambdas

Functions are first-class values, and anonymous functions are written with lambda:

dec twice : (alpha -> alpha) -> alpha -> alpha;
--- twice f x <= f (f x);

twice (lambda n => n * 3) 7;     ! gives 63 : num

Lazy lists

In the 1980 implementation, lazy evaluation was provided only for lists, through a special constructor lcons that behaved like :: but left its arguments unevaluated until needed, allowing infinite lists. The paper sketched, but had not yet implemented, input and output functions built on lazy lists for interactive I/O. Later implementations varied: Paterson’s interpreter is fully lazy, so ordinary recursive definitions can produce infinite lists:

dec from : num -> list num;
--- from n <= n :: from(n + 1);

dec take : num # list alpha -> list alpha;
--- take(0, xs) <= [];
--- take(succ n, []) <= [];
--- take(succ n, x :: xs) <= x :: take(n, xs);

take(5, from 1);                 ! gives [1, 2, 3, 4, 5] : list num

Modules

Any sequence of declarations could be wrapped in module name ... end. Only types listed with pubtype and constants listed with pubconst were visible outside, and a module could use other modules only through an explicit uses statement. Hiding a type’s constructors made the module a true abstract data type: in the paper’s tree-sort example, the node constructor stays private, so outside code can only build ordered trees through empty and insert, which preserve the ordering.

Evolution

Imperial College and Hope+

Hope found a second home at Imperial College London, where John Darlington had founded the Functional Programming Section. By the November 1982 meeting at the Rutherford Appleton Laboratory, Hope already existed as the original POP-2 system, a Lisp port by MacQueen and compilers for the ALICE parallel reduction machine being built in Darlington’s group. A BYTE column in August 1985 reported that the Edinburgh system ran as a compiler on a DEC-10, that an Imperial College group had produced an interpreter for a large subset of Hope on the VAX under VMS, and that research assistant Victor Wu had written a Pascal version of that interpreter for the IBM PC.

Imperial’s extended language, Hope+, added features such as evaluation annotations (described by John Kewley and Kevin Glynn at the 1989 Glasgow workshop) that let programmers choose between strict and lazy evaluation. Nigel Perry’s 1991 Imperial College thesis described his implementation of Hope+, including a type-system extension that the History of Haskell identifies as an early demonstration of existential data constructors - a feature later offered by GHC.

Teaching and popularisation

Hope became a teaching language in the late 1980s. Roger Bailey of Imperial College wrote the BYTE tutorial in 1985 and the book Functional Programming with Hope in 1990, and Field and Harrison’s 1988 textbook Functional Programming introduced the subject through Hope. Ross Paterson wrote a lazy interpreter in C for an undergraduate course in 1988 and developed it over the following decade, adding operator sections, a Krivine-machine back end, curried definitions, recursive type synonyms, Unicode characters and automatically generated map functions. Its reference manual says that when patterns overlap, more specific patterns are preferred, so the order of equations normally does not matter in that dialect; descriptions of earlier implementations, such as the one in the History of Haskell, say equations were tried from top to bottom.

Hope into Standard ML

Hope’s most lasting legacy came through ML. When Robin Milner drafted his proposal for “Standard ML” in April 1983, the notable changes to LCF/ML included “HOPE-style algebraic datatypes, pattern matching over datatype constructors, and clausal (or equational) function definitions”. The Standard ML module system grew from MacQueen’s 1981 module design for Hope, which had itself been inspired by the parameterised theories of Burstall and Goguen’s Clear specification language. The SML history also notes that the efficient, non-backtracking compilation of pattern matching was part of the first Hope compiler and was refined later in SML/NJ.

Current Relevance

Hope is no longer developed, and it never had a standard or a commercial implementation. It can still be run: Paterson’s interpreter, whose last revision is dated 16 April 1999 and which was released under the GNU GPL, vanished from its City University web page around 2013 but was recovered from the Internet Archive and is preserved in public GitHub repositories with patches to build on current Unix-like systems. One of those repositories also contains a newer C++ reimplementation. These are community preservation efforts rather than official releases, and no official Docker image exists.

Why It Matters

Hope is a short chapter in the history of programming languages with long consequences:

• Algebraic data types and pattern matching. NPL had the first, first-order version of the idea; Hope combined it with polymorphic types and higher-order functions into a fully developed form. The History of Haskell notes that algebraic types were absent from the original ML and from KRC but appeared in their successors, Standard ML and Miranda, and they are now a standard feature of typed functional languages.
• The road to Standard ML. Hope was one of three Edinburgh precursors of Standard ML, alongside LCF/ML and Cardelli’s ML, and contributed both its datatypes and the ancestor of its module system.
• Functional programming in the classroom. Through Imperial College, BYTE, and textbooks by Bailey and by Field and Harrison, Hope was for a time one of the main ways programmers in Britain met typed functional programming.
• Parallel functional hardware. As a source language for ALICE, Hope was part of early experiments in exploiting the fact that, without assignment, the arguments of a function can be evaluated in parallel - a possibility its designers pointed out in 1980.

The authors closed their 1980 paper hoping that their work would “contribute to a better understanding of the structure of large programs and their development”. Through ML and its descendants, it did.