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 theprogn
. This is needed for macros which create multiple bindings. (Of otherwise marginal utility. Might be better to have aprog2
as primitive and letprogn
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-primitiveif
macro wrapping that around thunks.)
Derived procedures
=?
- Two pairs are
=?
if their cars and cdrs are=?
. Symbols are=?
if they’reatom=?
. The empty list is always=?
to itself. ¬
t
if argument isf
, otherwisef
. (TODO: Find a non-Unicode alias.not
is probably perfectly acceptable.)+
,-
,*
,/
, etc.- Mathematical operations on
int
andrat
. (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 notlet
.) 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:
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!)
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.