Learning Ado

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 procedures¹ for building and deconstructing pairs, and a special form² 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).³ 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.⁴ 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.⁵ (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.

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.⁶ 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.⁷ 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.

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,⁸ 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!