Learning Ado

This is a work in progress!

Ado is a dialect of the Lisp programming language. It’s still in early development, so practically everything you read below might change at some point.

When learning (or designing, or implementing) a new programming technology, there’s always a question: Should we start at the highest level of abstraction and work our way down? Or at the lowest level of abstraction, working our way up? I usually find it’s helpful to design from the bottom up. In the case of Ado, that’s more-or-less what we’ll do, although as we’ll learn later, there are some layers below what I’ll initially present here.


When we learn a new programming language, the first thing we want to know is: what features does it have? Ado doesn’t have many to start with. All it knows about are pairs (2-tuples) and symbols (which are like variable names in other languages, but we can treat them as data objects in themselves and not just as the things they refer to). It has procedures1 for building and deconstructing pairs, and a special form2 for using symbols (and other things) as symbols and not as variable names.

The procedure to construct a pair is called cons, and the special form to use a symbol without using it as a variable name is called ' (a single quote mark).3 In most programming languages, procedure calls look like f(x, y), but in Lisp they look like (f x y), and using special forms looks the same. (cons (' a) (' b)) builds a pair out of the symbols a and b. This pair is written out to us (a . b); by using ' around that, we can use that pair as a literal and not as a constructed pair. (' (a . b)) also gives us back the pair (a . b) when we evaluate it.

We can get back the two elements of a pair with the procedures car (for the first item in the pair) and cdr (for the second item), so (car (' (a . b))) gives us a back, and (cdr (' (a . b))) gives us b back. These are arbitrary names with a very long history.4 Their meaninglessness is actually an advantage, because pairs are a very general data structure with a lot of applications, and other names would more . Also, the names have traditional and simple compositions in Lisp: the car of a pair which is in turn stored in another pair’s cdr can be accessed with cadr (short for (car (cdr ...))). Names which are apparently clearer, like first and second, can’t be so concisely composed.

Despite the apparent sparseness of this set-up, we can actually do more with it than you might imagine. This is because we can use pairs to implement linked lists — in other words, 2-tuples alone are enough to implement n-tuples for any n! We can use the car field of a pair for a value in the list, and the cdr field for the next node in the linked list. We need a sentinel value to put in the cdr field when we’re at the end of the list, and Ado actually gives us one: the empty list, spelt (). It also gives us a way to write lists conveniently as an application of pairs: (a b c) is short for the pairs (a . (b . (c . ()))).

Of course, a programming language isn’t much of a programming language without a way to build our own procedures. In Ado, this is done with the λ special form.5 (Because this is tricky to type, the Ado editor in Emacs changes the letter \ to a λ when you type it as the first thing after an open parenthesis.) We can use procedures by using λ to construct them in the place where you’d normally expect a procedure name; for instance, if we have a procedure (λ (x y z) (cons x (cons y (cons z ())))) which makes a list out of three arguments, we can use it like this:

((λ (x y z) (cons x (cons y (cons z ())))) (' red) (' green) (' blue))

This evaluates to the list (red green blue).

We can also give names to our procedures, which is a lot more convenient in most cases. The way to give names to things is with the := special form:

(:= list3 (λ (x y z) (cons x (cons y (cons z ())))))

(list3 (' red) (' green) (' blue))


If we have a way to test whether two things are the same, and to do something different with depending on whether they are or not, we can already do quite a lot with this system! We can use the =? procedure to test whether two lists or pairs are the same, and the if special form to do something different depending what =? says.

Using this, we can write a procedure ++ which appends one list to another. We use ++ and not + because appending two lists is not a commutative operation, unlike numeric addition. (That is, appending a to b is different from appending b to a, but adding a and b is the same as adding b and a.)

(:= ++ (λ (xs ys)
         (if (=? xs ()) ;; If we’re attempting to do (++ () ys) ... 
               ys       ;; ... that’s equivalent to ys on its own.
             else       ;; Otherwise, ...
               (cons (car xs) (++ (cdr xs) ys)))))
                        ;; ... the list returned by (++ xs ys) has the
                        ;; first element of xs as its own first element,
                        ;; followed by the rest of xs appended (++) to ys.
                        ;; When we reach the end of xs, the recursive call
                        ;; to ++ will be (++ () ys), triggering the base
                        ;; case defined above.

And in fact Ado already gives us a procedure like this, defined exactly this way.

Building more derived types with pairs

Above I wrote that the only things Ado knows about are symbols and pairs. At the point when we read something like that, we disgruntled programmers sigh and mutter something about how programming languages don’t have any useful features these days, and realize we’re going to have to implement numbers ourselves from scratch.

How do we do this? We’ll start with the simplest number of all: zero. We’ll use the symbol zero to mean zero, like () represents the empty list.6 Then we need a way to . We could just give every number its own symbolic name, like one, two, three, etc, up to forty-two and one-million — but we want arithmetic! Adding and subtracting and stuff! If we did it that way, we’d have to define addition for every combination of symbolic number names: one plus one, one plus two, etc. Even Roman numerals were better than this.

Instead we’ll build an abstraction on top of pairs and lists. To get further positive integers, we need a way to add one to zero, and then a way to add another one to that one, etc.7 So we’ll use increasing numbers of nested lists to represent increasing integers! The first thing in these lists will also be a symbol (succ, because this list represents the number which succeeds another number), and the second thing will be the nested list for the previous number. So 1 is written (succ zero), 2 is written (succ (succ zero)), etc.

(:= + (λ (a b)  ;; Defining addition for the numbers as we just defined them.
        (if (=? a (' zero)) ;; If we’re trying to calculate
                            ;; 0 + another number ...
              b             ;; ... the answer is just that other number.
            else            ;; Otherwise, ...
              (+ (cadr a)   ;; ... the answer is (a - 1) + ...
                 (list (' succ) b))))) ;; ... (b + 1).
                            ;; As above, this recursion will eventually reach
                            ;; the base case where a is zero, at which point
                            ;; we know we finished adding.

;; Example: (+ (' (succ (succ zero))) (' (succ (succ zero)))) i.e. 2 + 2
;;        ⇒ (succ (succ (succ (succ zero)))) i.e. 4

What about negative numbers? Easy: we just use a symbol other than succ and start counting downwards from 0 using that. So (prec zero) is -1, (prec (prec zero)) is -2, etc.

I should note here that Ado actually provides this abstraction of lists into numbers for us, and associates it with the decimal notation for integers, so that typing 3 into Ado is actually a shorthand for writing (succ (succ (succ zero))). (You will already have seen this if you tried these examples in the Ado interpreter.) This is just to show how pairs and lists are useful abstractions on which any data value you can think of can be based, including things we normally think of as being primitive things the language would give us.

One problem is that we now have infinitely many different representations of every number (including zero). For instance, I can write 1 as (succ zero) as usual, but (succ (succ (prec zero))) is also equally valid. (We can also introduce garbage into a list that otherwise looks like a valid number, for example if we make a typing mistake and write zreo instead of zero.) In order to avoid this situation, we need to introduce type constructors that make sure that succ is only combined with other succ or with zero, and prec is only combined with other prec or with zero.

Type definitions

Ado is a statically-typed language in which all types of values are inferred. Unlike in some other languages, there’s no way to tell the compiler ‘this is a number’ or ‘this is a string’ — it has to work that out for itself. Another odd thing is that typed values are an application of lists,8 so we don’t need to change how succ, prec, and zero.

The first thing we do is define our type for zero: (type zero). That was easy! As a nice side-effect, we no longer need to quote zero; the evaluator knows that it it’s a type name, and it evaluates to itself.

Then we need to define the types for succ and prec. We’ll do the latter first, defining the natural i.e. positive integers. A positive integer is either the succ of another positive integer, or the succ of zero:

(type nat            ;; A nat is ...
        (succ nat)   ;; ... either the succ of another nat ...
        (succ zero)) ;; ... or the succ of zero (i.e. one).

We’ve just defined succ to be a type constructor, so we no longer need to quote things like (succ zero) any more either. Type constructors are basically procedures that return a list of the type name followed by all the type’s arguments. This means that if we did (:= one (succ zero)), we can then also do (:= two (succ one)), referring to our previous definition of one instead of having to tediously write it out again.

Let’s do the rest:

(type neg            ;; A neg (negative integer) is ...
        (prec neg)   ;; ... either the prec of another neg ...
        (prec zero)) ;; ... or the prec of zero (i.e. negative one).

(type int     ;; And an int (integer) is ...
        zero  ;; ... either zero ...
        nat   ;; ... or a positive integer ...
        neg)  ;; ... or a negative integer.

That’s it for now. More to come!



Procedures are called functions in some other dialects of Lisp, and in many other functional languages, but we call them procedures because that’s the name used in Scheme, the most direct inspiration for Ado within the Lisp family itself. Historically, I believe Scheme uses this term because of Algol’s influence on Scheme, even though Scheme procedures are by convention (like functions in dialects of Lisp that use the name ‘function’) closer to mathematical pure functions than side-effectual algorithmic subroutines; in Ado, they’re even guaranteed to be pure functions, but out of habit and lineage the name ‘procedure’ has stuck for now.


In Lisp, the term ‘special form’ means something that looks like a function, but doesn’t quite behave like one. In other languages, ‘special forms’ tend to look completely different from functions as well as behaving differently: they’re things like if statements and so on.


The quote mark behaves differently in Ado compared to other dialects of Lisp. In other dialects of Lisp, ' is special notation and doesn’t need brackets around it.


Lisp is a very old language, originally developed in 1958. The very first version was written for the IBM 704 (also famous as the real ‘singing computer’ which inspired the scene in 2001: A Space Odyssey). car and cdr were originally the names of assembler macros on that computer: car was a macro to get the Content of the Address part of a Register, and cdr got the Content of the Decrement part of a Register. Lispers occasionally continue this tradition further: a proposal for the next version of the Scheme programming language adds a procedure cpr, which (apart from being a nice visual pun on cdr, since cpr reads backwards through a list while cdr reaches fowards) was actually the name for the next part in the sequence on the 704 (the prefix part of the register).


The use of the Greek lambda symbol as the function constructor is even older than Lisp itself, dating back to the work of Alonzo Church on the lambda calculus in the 1930s. (Alan Turing’s work on Turing machines was done to solve the same problem as Church’s lambda calculus, and the two systems are completely equivalent in computational power.) The relationship between Lisp and the lambda calculus is interesting: lambda calculus knows about symbols and procedures as its basic building blocks, and can use procedures to make lists; Lisp knows about symbols and lists (really, pairs) as its building blocks, and can use lists to build procedures. The relationship between Lisp (and other practical programming languages) and the lambda calculus was explored in the 1970s and 1980s in the so-called ‘lambda papers’ in which the design of the Scheme language was laid out, and it was shown that programming languages where procedure calls are the fundamental means of variable binding and flow control are no less efficient than traditional assignments, conditionals, and loops. Most classical Lisps (including Scheme) tend to use the spelt-out form lambda as the name for the form which creates procedures; newer Lisps use abbreviations (ususally fn); but some new implementations of classic Lisps (like the Racket implementation of Scheme) offer λ as an alias for lambda, and some Lispers like to use special modes in their editors which display lambda as λ. In Ado, λ is the canonical and only name for the procedure constructor.


At this point, seasoned functional programmers will already start rolling their eyes at yet another purist abstraction astronaut too far away from the machine. But no fear: the semantics of Ado are defined such that, at the implementation level, zero can actually be a machine zero, and subsequent numerals also machine integers. Real (i.e. non-toy) implementations will certainly want to do this.


Another equally valid option would be to add a one and make number lists represent binary numerals, where the first element is the ones position, the second the twos position, the third the fours position, etc. This approach is taken by one of the minor programming languages which inspired Ado, Bel.


This has the benefit that type inference and checking can be done as a completely separate stage from compilation or interpretation. (Ado isn’t quite unique in this regard: the MyPy type checker for Python also operates completely independently of the Python interpreter.) In other words, if you know a program is well-typed (i.e. you have asked a type checker to prove that it is so), you can feed it into an implementation of Ado that doesn’t check types at all and know that it will run fine.