# 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 number^{2}).

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.