UP | HOME

Ado

(/​əˈduː/, not anything like /​ˈeɪdəʊ/. The name comes from an attempt to create something that takes even purer and more primitive primitives than Bel and show that by subtracting one from each letter of Bel’s name, but ‘Adk’ isn’t pronounceable.)

This is the Ado design document, where ideas evolve but don’t necessarily make sense without an understanding of context — context which may, for now, only be stored in my brain and nowhere else. For a step-by-step introduction to Ado, see Learning Ado.

The primitive things Ado knows about are symbols, pairs (a . b), and the empty list ().

Here’s how the integers are (apparently) defined:1

(type zero)
(type nat (succ nat)
          (succ zero))
(type neg (prec neg)
          (prec zero))
(type int nat neg zero)

Okay, but what if we need fractions?

(type rat (frac int nat))

Note that, unlike in Haskell, we aren’t naming the ‘slots’ of types. The fundamental type deconstructors are car and cdr. So the cadr of a frac is the numerator (an integer) and the caddr is the denominator (a natural number2).

Lists and strings come easily, too:

(type (list x) (x (list x)) ())
(type char (char nat)
           (char zero)) ;; Unicode codepoints are ≥ 0
(type str (list char))

As do basic booleans:

(type f)
(type t)
(type bool f t)

Evaluation

Type value expressions evaluate to themselves. So (rat 3 4) doesn’t need to have some special quoting or whatever to work.

Other expressions evaluate according to normal Lisp 1 rules. (TODO: Are lambdas and procedure calls implicitly curried?)

Primitive procedures

cons, car, cdr
As you expect.
atom?
t if argument is a symbol, f otherwise.
atom=?
t if the two symbols have the same name, f otherwise.
null?
t if the argument is the empty list, f otherwise.

Primitive special forms

'
quote, as you expect. (No read syntax! This is (' xyz), not 'xyz)
ƒ
Vau, somewhat as you expect. Details to be defined.
:=
Defines the strict name given by the first argument to refer to the value produced by evaluating the second argument. Can only define, not redefine.
progn
As you expect. This is primitive because, unlike λ (which it could otherwise be defined in terms of) it doesn’t create a new lexical contour, so e.g. invocations of := will create bindings in the context outside of the progn. This is needed for macros which create multiple bindings. (Of otherwise marginal utility. Might be better to have a prog2 as primitive and let progn be derived, or find another way to do this primitively.)

Might be a special form or not

if
In Strict Ado, this needs to be a special form; in Lazy Ado, it’s a regular procedure. I haven’t yet decided which evaluation order to consider canonical. (Even in Strict Ado, the actual primitive might be a procedure called choose, with a non-primitive if macro wrapping that around thunks.)

Derived procedures

=?
Two pairs are =? if their cars and cdrs are =?. Symbols are =? if they’re atom=?. The empty list is always =? to itself.
¬
t if argument is f, otherwise f. (TODO: Find a non-Unicode alias. not is probably perfectly acceptable.)
+, -, *, /, etc.
Mathematical operations on int and rat. (For an implementation which uses machine integers, these make sense as primitives.)

Derived special forms

λ
As you expect. Aliased to .\ (TODO: This complicates the parser a bit if . is also the pair separator.)
begin
As you expect. Creates a new lexical contour, unlike progn.
let
As you expect. (TODO: Maybe it should actually behave like let* and not let.)
type
As above. (For a compiler which properly type-checks, type probably has to be a primitive, but it can be derived for everyone else.)

Issues

  • It would be nice to have a name for things which might be primitive, depending on the implementation, but can also be defined non-primitively. ‘Opcode’, perhaps, after Chibi Scheme?
  • How does aliasing work? I think the easiest way is at read time.

Footnotes:

1

In reality, implementations are only required to behave as if integers were defined as the Peano numerals like this. They can internally use binary machine ints, where (car n) returns succ or prec or zero, and (cdr n) returns the integer one closer to zero, or the empty list for zero itself. (The standard example of a Lisp type error, taking the car of a number, isn’t a type error in Ado!)

2

Note that the naturals are defined to begin at 1. This definition uses the type system to ensure that only the numerator of a fraction can be zero or negative, both avoiding ‘rationals’ which are actually divisions by zero, and positive rationals irregularly expressed as the division of two negatives. What we can’t do with a non-dependent type system is avoid fractions like 1/1, 2/2, 2/4, etc.