Awesome

The Bel Language

This is a mirror of the Bel language web page.

While the original web page is in plain text, this page adds minor Markdown-based typographical improvements and syntax highlighing (based on the existing Lisp syntax highlighting rules). The purpose of creating this page on Github was to make Bel language documentation easier to read - for my own convenience as well as to promote the awareness and discussion of the Bel language and Paul Graham's logic and ideas behind its creation.

• Below is the text of the language guide in Markdown.
• This is Bel's source code (.lisp extension is added for syntax highlighting);
• This is the file of Bel code examples.

The Bel Language guide

By Paul Graham, 12 Oct 2019

In 1960 John McCarthy described a new type of programming language called Lisp. I say "new type" because Lisp represented not just a new language but a new way of describing languages. He defined Lisp by starting with a small set of operators, akin to axioms, and then using them to write an interpreter for the language in itself.

His goal was not to define a programming language in our sense of the word: a language used to tell computers what to do. The Lisp in his 1960 paper was meant to be a formal model of computation, like a Turing Machine. McCarthy didn't realize it could be used on computers till his graduate student Steve Russell suggested it.

The Lisp in the 1960 paper was missing features you'd need in a programming language. There were no numbers, for example, or errors, or I/O. So when people used it as the basis for languages used to program computers, such things had to be added. And when they were, the axiomatic approach was dropped.

So the development of Lisp happened in two parts (though they seem to have been interleaved somewhat): a formal phase, represented by the 1960 paper, and an implementation phase, in which this language was adapted and extended to run on computers. Most of the work, as measured by features, took place in the implementation phase. The Lisp in the 1960 paper, translated into Common Lisp, is only 53 lines of code. It does only as much as it has to in order to interpret expressions. Everything else got added in the implementation phase.

My hypothesis is that, though an accident of history, it was a good thing for Lisp that its development happened in two phases — that the initial exercise of defining the language by writing an interpreter for it in itself is responsible for a lot of Lisp's best qualities. And if so, why not do more of it?

Bel is an attempt to answer the question: what happens if, instead of switching from the formal to the implementation phase as soon as possible, you try to delay that switch for as long as possible? If you keep using the axiomatic approach till you have something close to a complete programming language, what axioms do you need, and what does the resulting language look like?

I want to be clear about what Bel is and isn't. Although it has a lot more features than McCarthy's 1960 Lisp, it's still only the product of the formal phase. This is not a language you can use to program computers, just as the Lisp in the 1960 paper wasn't. Mainly because, like McCarthy's Lisp, it is not at all concerned with efficiency. When I define append in Bel, I'm saying what append means, not trying to provide an efficient implementation of it.

Why do this? Why prolong the formal phase? One answer is that it's an interesting exercise in itself to see where the axiomatic approach leads. If computers were as powerful as we wanted, what would languages look like?

But I also believe that it will be possible to write efficient implementations based on Bel, by adding restrictions. If you want a language with expressive power, clarity, and efficiency, it may work better to start with expressive power and clarity, and then add restrictions, than to approach from another direction.

So if you'd like to try writing an implementation based on Bel, please do. I'll be one of your first users.

I've ended up reproducing a number of things in previous dialects. Either their designers got it right, or I'm too influenced by dialects I've used to see the right answer; time will tell. I've also tried to avoid gratuitous departures from existing Lisp conventions. Which means if you see a departure from existing conventions, there is probably a reason for it.

Data

Bel has four fundamental data types: symbols, pairs, characters, and streams.

Symbols are words:

foo

The names of symbols are case-sensitive, so foo and Foo are distinct symbols.

Pairs are pairs of any two things, and are represented thus:

(foo . bar)

That's a pair of two symbols, foo and bar, but the two halves of a pair can be anything, including pairs:

(foo . (bar . baz))

That's a pair of the symbol foo, and the pair (bar . baz).

A character is represented by prepending a backslash to its name. So the letter a is represented as

\a

Characters that aren't letters may have longer names. For example the bell character, after which Bel is named, is

\bel

There is no way of representing a stream. If Bel has to display a stream, it prints something that will cause an error if it's read back in.

Anything that's not a pair is called an atom. So symbols, characters, and streams are atoms.

Instances of the four fundamental types are called objects.

Lists

We can use pairs to build lots of different data structures, but the most fundamental way they're used is to make lists, as follows:

1. The symbol nil represents the empty list.

2. If y is a list, then the pair (x . y) is a list of x followed by the elements of y.

Here's a list made from a pair:

(a . nil)

According to rule 2, this is a list of the symbol a followed by the elements of nil, of which according to rule 1 there are none. So it is a list of one element, the symbol a.

By nesting such pairs we can create lists of any length. Here is a list of two elements, the symbols a and b:

(a . (b . nil))

And here is a list of a, b, and c:

(a . (b . (c . nil)))

This would be an awkward way to express lists, but there is an abbreviated notation that's more convenient:

1. The symbol nil can also be represented as ().

2. When the second half of a pair is a list, you can omit the dot before it and the parentheses around it. So (a . (b ...)) can be written as (a b ...).

By repeated application of these two rules we can transform

(a . (b . (c . nil)))

into

(a b c)

In other words, a list can be expressed as its elements within parentheses. You wouldn't use dot notation for a list like (a b c) unless there was some special reason to.

Because any object can be part of a pair, the elements of lists can themselves be lists. All these are lists too:

(a (b) c)
((a b c))
(nil)

Pairs like these, where if you keep looking at the second half you eventually hit a nil, are called proper lists. This is a proper list:

(a b c)

and this is not:

(a b . c)

The empty list is also a proper list.

A pair that's not a proper list is called a dotted list (because you need to use dot notation to represent it).

A proper list of characters is called a string, and can also be represented as those characters within double-quotes. So the list

(\h \e \l \l \o)

can also be represented as

"hello"

and will when possible be displayed that way.

Truth

The symbol nil represents falsity as well as the empty list. The symbol t is the default representation for truth, but any object other than nil also counts as true.

It may seem strange to use the same value to represent both falsity and the empty list, but in practice it works well. Lisp functions often return sets of answers, and the empty set of answers is falsity.

Functions

Bel programs consist mostly of functions. Functions take zero or more objects as arguments, perhaps do something (e.g. print a message), and return one object.

Functions are represented using lists. For example, here is a function that takes one argument, and returns that plus 1.

(lit clo nil (x) (+ x 1))

The first element, lit, says that this is a literal object, not to be evaluated.

The second, clo, says what kind of literal it is: a closure.

The third is the local enviroment, a list of variables that already have values from having been parameters of functions. This example has an empty environment.

The fourth, (x), is the function's parameters. When the function is called, the value of x will be whatever it was called with.

The fifth and last element, (+ x 1), defines the value that the function returns.

You would not ordinarily express a function using its literal representation. Usually you'd say

(fn (x) (+ x 1))

which yields the function above.

Evaluation

The execution of a Bel program consists of the evaluation of expressions. All Bel objects are expressions, so the word "expression" is merely a statement of intention: it means an object that you expect to be evaluated.

When an expression is evaluated, there are three possible outcomes:

1. It can return a value: (+ 1 2) returns 3.

2. It can cause an error: (/ 1 0) will.

3. It can fail to terminate: (while t) will.

Some expressions also do things in the process of being evaluated. For example,

(prn 1)

will return 1, but before doing so will print it.

Some atoms evaluate to themselves. All characters and streams do, along with the symbols nil, t, o, and apply. All other symbols are variable names, and either evaluate to some value, or cause an error if they don't have a value.

A proper list whose first element evaluates to a function is called a function call. For example, the expression

(+ x 1)

is a function call, because the value of + is a function. The value of a function call is the object that the function returns.

Function calls are evaluated left to right. For example, when

(+ 8 5)

is evaluated,

1. First + is evaluated, returning a function that returns the sum of its arguments.

2. Then 8 is evaluated, returning itself.

3. Then 5 is evaluated, also returning itself.

4. Finally, the two numbers are passed to the function, which returns 13.

If we want to show what expressions evaluate to, it's conventional to show them being evaluated in a repl:

> (+ 8 5)
13

Expressions can be nested. The rule of evaluating left to right means that nested function calls are evaluated depth-first. For example, when

(+ (- 5 2) 7)

is evaluated, the subexpressions that get evaluated are, in order, +, (- 5 2), -, 5, 2, 7.

Not all expressions are evaluated left to right, however. There is a small set of symbols called special forms, and an expression whose first element is a special form is evaluated according to rules defined for that special form.

For example, if is a special form, and when an expression of the form

(if test then else)

is evaluated, only one of the last two elements will be evaluated, depending on whether the second element, test, returns true or not.

Things meant to be used as the first element of an expression are called operators. So functions and special forms are operators. But like the term "expression," this is just a statement of intention. You can put anything first in an expression so long as you specify what happens when you do.

Bindings and Environments

There are three ways a variable can have a value. It can have a value globally, as for example + does, meaning that by default it has this value everywhere. Such a variable is said to be globally bound, and the set of global bindings is called the global environment.

Another way a variable can have a value is by being a parameter in a function. When the function

(fn (x) (+ x 1))

is called, the variable x will, within it, have as its value whatever argument the function was called with. That's called a lexical binding, and the current set of lexical bindings is the lexical environment.

Finally, variables can have dynamic bindings, which are visible everywhere, like global bindings, but temporary: they persist only during the evaluation of whatever expression created them.

Dynamic bindings take precendence over lexical bindings, which take precedence over global ones.

If you do an assignment to a variable that has one of the three kinds of bindings, you'll modify whichever binding is currently visible. If you do an assignment to a variable that's not bound, you'll create a global binding for it.

Errors

Errors are signalled by calling err with one argument describing the error. Bel doesn't specify a global binding for err; this is something for a programming environment built on top of Bel to do. But some error-catching code in the Bel source does dynamically bind err.

Axioms

Like McCarthy's Lisp, Bel is defined starting with a set of operators that we have to assume already exist. Then more are defined in terms of these, till finally we can define a function that is a Bel interpreter, meaning a function that takes a Bel expression as an argument and evaluates it.

There are two main types of axioms: primitives and special forms. There are also a few variables that come predefined.

In the following sections, the descriptions of primitives are their definitions. The descriptions of special forms, however, are merely summaries of their behavior; special forms are defined by the code that implements them in the Bel source.

Variables and Constants

1. t nil o apply

Evaluate to themselves.

2. chars

A list of all characters. Its elements are of the form (c . b), where c is a character and b is its binary representation in the form of a string of \1 and \0 characters. Bel doesn't specify which characters are in chars, but obviously they should include at least those in the Bel source.

3. globe scope

The current global and lexical environments, represented as lists of (var . val) pairs of variables and their values.

4. ins outs

The default input and output streams. Initially nil, which represents the initial input and output streams. Bel doesn't specify what those are, but if you started Bel at a prompt you'd expect them to be the terminal.

Quote

The quote operator is a special form, but it has to be described first because so many code examples use it.

It returns its argument without evaluating it. Its purpose is to prevent evaluation.

> (quote a)
a

Prepending ' to an expression is equivalent to wrapping a quote around it.

> 'a
a

Why do you need to prevent evaluation? To distinguish between code and data. If you want to talk about the symbol a, you have to quote it. Otherwise it will be treated as a variable, and you'll get its value. E.g. if a has been set to 10:

> a
10
> 'a
a

Because the symbols nil, t, o, and apply evaluate to themselves, you don't have to quote them. Ditto for strings.

Primitives

Primitives can be called like functions, but are assumed to exist, rather than defined in the Bel source. As with function calls, the arguments in calls to primitives are all evaluated, left to right. Missing arguments default to nil. Extra arguments cause an error to be signalled.

1. (id x y)

Returns true iff x and y are identical.

> (id 'a 'a)
t
> (id 'a 'b)
nil

Identity is stricter than equality. While there is only one of each symbol and character, there can be any number of different pairs with the same elements. So two pairs can look the same without being identical:

> (id '(a b) '(a b))
nil

Because id is so strict, it's not the function you'd usually use to test for equality. Usually you'd use =.

2. (join x y)

Returns a new pair whose first half is x and second half is y.

> (join 'a 'b)
(a . b)
> (join 'a)
(a)

A pair returned by join will not be id to any existing pair.

> (id (join 'a 'b) (join 'a 'b))
nil

3. (car x)

Returns the first half of a pair:

> (car '(a . b))
a
> (car '(a b))
a

The car of nil is nil,

> (car nil)
nil

but calling car on any atom other than nil will cause an error.

The name "car" is McCarthy's. It's a reference to the architecture of the first computer Lisp ran on. But though the name is a historical accident, it works so well in practice that there's no reason to change it.

4. (cdr x)

Returns the second half of a pair:

> (cdr '(a . b))
b
> (cdr '(a b))
(b)

As with car, calling it on nil yields nil, calling it on any other atom causes an error, and the name is McCarthy's.

When operating on pairs used to represent lists, car and cdr get you the first element and the rest of the list respectively.

5. (type x)

Returns either symbol, pair, char, or stream depending on the type of x.

> (type 'a)
symbol
> (type '(a))
pair
> (type \a)
char

6. (xar x y)

Replaces the car of x with y, returning y. Signals an error if x is not a pair.

If we assume that the value of x is (a . b), then

> x
(a . b)
> (xar x 'c)
c
> x
(c . b)

7. (xdr x y)

Like xar, except that it replaces the cdr of x.

> x
(c . b)
> (xdr x 'd)
d
> x
(c . d)

8. (sym x)

Returns the symbol whose name is the elements of x. Signals an error if x is not a string.

> (sym "foo")
foo

9. (nom x)

Returns a fresh list of the characters in the name of x. Signals an error if x is not a symbol.

> (nom 'foo)
"foo"

10. (wrb x y)

Writes the bit x (represented by either \1 or \0) to the stream y. Returns x. Signals an error if it can't or if x is not \1 or \0. If y is nil, writes to the initial output stream.

11. (rdb x)

Tries to read a bit from the stream x. Returns \1 or \0 if it finds one, nil if no bit is currently available, or eof if no more will be available. Signals an error if it can't. If x is nil, reads from the initial input stream.

12. (ops x y)

Returns a stream that writes to or reads from the place whose name is the string x, depending on whether y is out or in respectively. Signals an error if it can't, or if y is not out or in.

13. (cls x)

Closes the stream x. Signals an error if it can't.

14. (stat x)

Returns either closed, in, or out depending on whether the stream x is closed, or reading from or writing to something respectively. Signals an error if it can't.

15. (coin)

Returns either t or nil randomly.

16. (sys x)

Sends x as a command to the operating system.

Special Forms

Expressions beginning with special forms are not always evaluated in the usual left-to-right way.

1. (quote x)

Described above.

2. (lit ...)

Returns the whole lit expression without evaluating it. A lit is like a persistent quote; evaluation strips the quote off a quote expression, but leaves a lit expression intact.

> (quote a)
a
> (lit a)
(lit a)

The name stands for literal, and it can take any number of arguments. This is how you make things that evaluate to themselves, the way characters or nil do. Functions are lits, for example, as are numbers.

The value of a primitive p is (lit prim p).

> car
(lit prim car)

3. (if ...)

An if expression with an odd number of arguments

(if a1 a2 a3 a4 ... an)

is equivalent to

if a1 then a2 else if a3 then a4 ... else an

I.e. the odd numbered arguments are evaluated in order till we either reach the last, or one returns true. In the former case, its value is returned as the value of the if expression. In the latter, the succeeding argument is evaluated and its value returned.

An if expression with an even number of arguments

(if a1 a2 ... an)

is equivalent to

(if a1 a2 ... an nil)

Falsity is represented by nil, and truth by any other value. Tests generally return the symbol t when they can't return anything more useful.

As a rule I've tried to make axioms as weak as possible. But while a 3-argument if would have sufficed, an n-argument version didn't require significantly more code, so it seemed gratuitously fussy to insist on 3 arguments.

4. (apply f ...)

An expression of the form

(apply f x y ... z)

is equivalent to

(f 'a 'b ... 'c1 ... 'cn)

where a is the value of x, b the value of y, and the ci the elements of the value of z.

> (join 'a 'b)
(a . b)
> (apply join '(a b))
(a . b)
> (apply join 'a '(b))
(a . b)

The last argument to apply can be a dotted list if it matches the parameters of the first.

5. (where x)

Evaluates x. If its value comes from a pair, returns a list of that pair and either a or d depending on whether the value is stored in the car or cdr. Signals an error if the value of x doesn't come from a pair.

For example, if x is (a b c),

> (where (cdr x))
((a b c) d)

6. (dyn v x y)

Evaluates x, then causes y to be evaluated with the variable v dynamically bound to the value of x.

For example, if x is a,

> x
a
> (dyn x 'z (join x 'b))
(z . b)
> x
a

7. (after x y)

Evaluates both its arguments in order. The second will be evaluated even if the evaluation of the first is interrupted (e.g. by an error).

8. (ccc f)

Evaluates f and calls its value on the current continuation. The continuation, if called with one argument, will return it as the value of the ccc expression (even if you are no longer in the ccc expression or in code called by it).

9. (thread x)

Starts a new thread in which x will be evaluated. Global bindings are shared between threads, but not dynamic ones.

Reading the Source

Starting with the foregoing 25 operators, we're going to define more, till we can define a Bel interpreter. Then we'll continue, defining numbers, I/O, and several other things one needs in programs.

These definition are in the Bel source, which is meant to be read in parallel with this guide.

In the Bel source, when you see an expression of the form

(set v1 e1 ... vn en)

it means each vi is globally bound to the value of ei.

In the source I try not to use things before I've defined them, but I've made a handful of exceptions to make the code easier to read.

When you see

(def n p e)

treat it as an abbreviation for

(set n (lit clo nil p e))

and when you see

(mac n p e)

treat it as an abbreviation for

(set n (lit mac (lit clo nil p e)))

The actual def and mac operators are more powerful, but this is as much as we need to start with.

Treat an expression in square brackets, e.g.

[f _ x]

as an abbreviation for

(fn (_) (f _ x))

In Bel, underscore is an ordinary character and _ is thus an ordinary variable.

Finally, treat an expression with a prepended backquote (`) as a quoted list, but with "holes," marked by commas, where evaluation is turned back on again.

> (set x 'a)
a
> `(x ,x y)
(x a y)
> `(x ,x y ,(+ 1 2))
(x a y 3)

You can also use ,@ to get a value spliced into the surrounding list:

> (set y '(c d))
(c d)
> `(a b ,@y e f)
(a b c d e f)

Now let's look at the source. The first expression defines a function no that takes one argument, x, and returns the result of using id to compare it to nil. So no returns t if its argument is nil, and nil otherwise.

> (no nil)
t
> (no 'a)
nil

Since nil represents both falsity and the empty list, no is both logical negation and the test for the empty list.

The second function, atom, returns true iff its argument is not a pair.

> (atom \a)
t
> (atom nil)
t
> (atom 'a)
t
> (atom '(a))
nil

Next come a pair of similar functions, all and some. The former returns t iff its first argument returns true of all the elements of its second,

> (all atom '(a b))
t
> (all atom nil)
t
> (all atom '(a (b c) d))
nil

and the latter returns true iff its first argument returns true of any element of its second. However, when some returns true, it doesn't simply return t. It returns the remainder of the list starting from the point where f was true of the first element.

> (some atom '((a b) (c d)))
nil
> (some atom '((a b) c (d e)))
(c (d e))

Logically, any value except nil counts as truth, so why not return the most informative result you can?

In all and some we see the first use of if. Translated into English, the definition of all might be:

If xs is empty, then return t.

Otherwise if f returns true of the first element, return the result of calling all on f and the remaining elements.

Otherwise (in which case xs has at least one element of which f returns false), return nil.

This technique of doing something to the car of a list and then perhaps continuing down the cdr is very common.

Something else is new in all and some: these are the first functions in the Bel source that you could cause an error by calling.

> (all atom 'a)
Error: can't call car on a non-nil atom.

I made up that error message; Bel doesn't specify more about errors in primitives than when they occur, and doesn't specify anything about repls. But some error will be signalled if you call all with a non-nil atom as the second argument, because in the second test within the if

(f (car xs))

car is called on it, and it's an error to call car on anything except a pair or nil.

One other thing to note about these definitions, now that we're getting to more complex ones: these functions are not defined the way they would be in idiomatic Bel. For example, if all didn't already exist in Bel you could define it as simply

(def all (f xs)
  (~some ~f xs))

But since we haven't defined functional composition yet, I didn't use it.

The next function, reduce, is for combining the elements of its second argument using nested calls to its first. For example

(reduce f '(a b c d))

is equivalent to

(f 'a (f 'b (f 'c 'd)))

If xs has only one element, reduce returns it, and if it's empty, reduce returns nil; since (cdr nil) is nil, we can check both these possibilities with (no (cdr xs)). Otherwise it calls f on the first element and reduce of f and the remaining elements.

> (reduce join '(a b c))
(a b . c)

This is not the only way to reduce a list. Later we'll define two more, foldl and foldr.

The definition of reduce shows another way of indenting ifs. Indentation isn't significant in Bel and only matters insofar as it helps humans read your code, but I've found three ways of indenting ifs that work well. If an if has more than two tests and the arguments are sufficiently short, it works well to say

(if test1 then1
    test2 then2
          else)

We saw this in all and some. But if you only have one test, or some arguments are too long to fit two on one line, then it works better to say

(if test1
    then1
    test2
    then2
    else)

or if an if is long,

(if test1
     then1
    test2
     then2
    test3
     then3
     else)

The next function, cons, has the name that join had in McCarthy's Lisp. It's the function you use to put things on the front of a list.

> (cons 'a '(b c))
(a b c)

If you only want to put one thing on the front of a list, you could use join.

> (join 'a '(b c))
(a b c)

With cons, however, you can supply more than one thing to put on the front:

> (cons 'a 'b 'c '(d e f))
(a b c d e f)

Since cons is a generalization of join, it's rare to see join in programs.

We see something new in the definition of cons: it has a single parameter, args, instead of a list of parameters. When a function has a single parameter, its value will be a list of all the arguments supplied when the function is called. So if we call cons thus

(cons 'a 'b '(c d))

the value of args will be

(a b (c d))

The parameter list of a Bel function can be a tree of any shape. If the arguments in the call match its shape, the parameters will get the corresponding values; otherwise an error is signalled.

So for example if a function f has the parameter list

(x . y) 

and it's called

(f 'a 'b 'c)

then x will be a, and y will be (b c).

If the same function is called

(f 'a)

then x will be a, and y will be nil. And if it's called

(f)

you'll get an error because there is no value for x.

If a function f has the parameter list

((x y) z)

and is called

(f '(a (b c)) '(d))

then x will be a, y will be (b c), and z will be (d). Whereas if it's called

(f '(a) '(d))

you'll get an error because there is no value for y, and if it's called

(f '(a b c) '(d))

you'll get an error because there is no parameter for c.

The next function, append, joins lists together:

> (append '(a b c) '(d e f))
(a b c d e f)
> (append '(a) nil '(b c) '(d e f))
(a b c d e f)

Its definition will be easier to understand if we look first at a two-argument version.

(def append2 (xs ys)
  (if (no xs)
      ys
      (cons (car xs) (append2 (cdr xs) ys))))

In English, if xs is empty, then just return ys. Otherwise return the result of consing the first element of xs onto append of the rest of xs and ys. I.e.

(append2 '(a b c) '(d e f))

becomes

(cons 'a (append2 '(b c) '(d e f)))

and so on. The definition of append in the Bel source is the same principle applied to any number of arguments.

In it we see the first use of apply. Like if, apply is a special form, meaning an operator whose behavior has to be defined as a special case in the interpreter. Unlike if, apply has a value; it evaluates to itself, like t and nil. This lets you use it as an argument like an ordinary function.

Its purpose is in effect to spread out the elements of a list as if they were the arguments in a function call. For example

(apply f '(a b))

is equivalent to

(f 'a 'b)

In the general case apply can take one or more arguments, and is equivalent to calling apply on the first argument and all the intervening arguments consed onto the last. I.e.

(apply f x y z)

is equivalent to

(apply f (cons x y z))

It's common to use apply in functions like append that take any number of arguments. Using apply is in a sense the converse of using a single parameter to collect multiple arguments.

Now let's look at append. It takes any number of arguments. Collectively (i.e. as a list) they'll be the value of args. If args is empty or only has one element, then the result is (car args). We saw the same sort of test in the first clause of reduce. That's two base cases, and there is also a third: when args has more than one element but the first element is nil. In that case we can ignore it, and apply append to the rest of args.

Finally in the last clause we see the general case. It uses the same strategy we saw in append2: cons the first element of the first argument onto a recursive call to append on the rest of the first argument and the remaining arguments. Unlike append2, append has to make this call using apply, because it has a varying number of arguments in a list, instead of exactly two.

Once we have append it's easy to define snoc, which as its name suggests is like a reverse cons,

> (snoc '(a b c) 'd 'e)
(a b c d e)

and list, which returns a list of its arguments.

> (list)
nil
> (list 'a)
(a)
> (list 'a 'b) 
(a b)

Or more precisely, returns a newly made list of its arguments. If you're wondering why we bother appending args to nil rather than simply returning it, the reason is that appending a list to nil will also copy it.

If we defined list as

(def list args args)

and it was called thus

(apply list x)

then the value that list returned would be the same list as x — not merely a list with the same elements, but the same pair — meaning if we modified the value we got from list, we'd also be modifying the object up in the calling code.

After list we see map, which in the simplest case returns a list of calling its first argument on each element of its second.

> (map car '((a b) (c d) (e f)))
(a c e)

However, map can take any number of lists, and calls its first argument on successive sets of elements from the others.

> (map cons '(a b c) '(1 2 3))
((a . 1) (b . 2) (c . 3))

It stops as soon as one list runs out

> (map cons '(a b c) '(1 2))
((a . 1) (b . 2))

Like append, map is easier to understand if we start with a version that takes exactly two arguments.

(def map2 (f xs)
  (if (no xs)
      nil
      (cons (f (car xs))
            (map2 f (cdr xs)))))

If there are no xs left, then return nil, otherwise cons f of the first element onto map2 of f and the remaining elements. Pretty simple.

All the additional complexity of map comes from the need to take multiple lists. The parameter list becomes (f . ls) so that all the lists can be collected in ls. We need an additional base case in case there are zero of them. Checking for the end of the list, which in map2 was

(no xs)

now becomes

(some no ls)

because we stop as soon as any list runs out.

Then we have yet another base case, the one in which we have just one list. That's what map2 does, and not surprisingly, the code is the same as in map2 except that xs becomes (car ls).

Finally in the general case we call f on all the first elements (which we collect using map) and cons that onto map of f on all the rests of the lists.

Notice that map calls itself recursively in two ways: there is the usual "do this to the rest of the list" recursive call in the last line. But in the preceding line we also use (map car ls) to collect the arguments for f. And that's why we need the single-list base case. Without it, we'd get an infinite recursion.

Next comes our first macro, fn. There are two concepts to explain first, though: macros and scope.

A macro is essentially a function that generates code. I would have liked the first example of a macro to be something simpler, but fn is the one we need first. So I'll introduce macros using a simpler macro that isn't part of Bel, then explain fn.

Here is a very simple macro:

(mac nilwith (x)
  (list 'cons nil x))

This definition says that whenever you see an expression like

(nilwith 'a)

transform it into

(cons nil 'a)

and then evaluate that and return its value as the value of the call to nilwith.

> (nilwith 'a)
(nil . a)

So unlike the evaluation of a function call, the evaluation of a macro call has two steps:

1. First use the definition of the macro to generate an expression, called the macro's expansion. In the case above the expansion is (cons nil 'a).

2. Then evaluate the expansion and return the result. The expansion above evaluates to (nil . a).

Beneath the surface, what's going on is quite simple. A macro is in effect (or more precisely, contains) a function that generates expressions. This function is called on the (unevaluated) arguments in the macro call, and whatever it returns is the macro expansion.

For example, the value of nilwith will be equivalent to

(lit mac (lit clo nil (x) (list 'cons nil x))))

If we look at the third element, we see the function that generates expansions

(lit clo nil (x) (list 'cons nil x))

which looks just like the definition of nilwith.

Macros often use backquote to make the code that generates expressions look as much as possible like the resulting expressions. So if you defined nilwith you'd probably do it not as we did above but as

(mac nilwith (x)
  `(cons nil ,x))

Now let's work our way up to fn, starting with the following simplified version:

(mac fn- (parms expr)
  `(lit clo nil ,parms ,expr))

This is less powerful than the actual fn macro in two ways.

1. It doesn't capture the local lexical environment, but instead simply inserts a nil environment.

2. It can only take a single expression.

But if we don't need either of these things, the functions made by fn- work fine:

> ((fn- (x y) (cons x y)) 'a 'b)
(a . b)

All the extra complexity in the definition of fn is to get those two features, the local environment and a body of more than one expression.

A function with a lexical environment stored within it is called a closure. That's why literal Bel functions begin (lit clo ...); the clo is for "closure." If a closure includes an environment with a value for x, then x will have a value within the closure even if it isn't a parameter.

So far the literal functions we've seen have had nil enviroments. Let's try making one by hand with some variable bindings in it. An environment is a list of (var . val) pairs, so to make a closure we put such a list in the third position of a clo, like this:

(lit clo ((x . a)) (y) (cons x y))

This closure includes an environment in which x has the value a. It has one parameter, y, and when called returns the value of x consed onto whatever we give as an argument.

> ((lit clo ((x . a)) (y) (cons x y)) 'b)
(a . b)

Notice that the b was all we passed to the function. The a came from within it.

It turns out to be very useful if functions include the lexical environment where they're created. And that is what the fn macro does.

In Bel you can get hold of the global and lexical environments using the variables globe and scope respectively. So for example if we define foo as

(def foo (x)
  scope)

then it will work something like this

> (foo 'a)
((x . a))
> (foo 'b)
((x . b))

I say "something like" because a repl may have some variables of its own, but we know that scope will at least have a value for x.

If you compare the definitions of fn- and fn, you'll notice that while fn- expands into a lit expression, fn expands into a call to list that yields a lit expression. It works fine to use a call to list rather than an actual list in a function call; functions are just lists after all.

> ((list 'lit 'clo nil '(x) '(+ x 1)) 2)
3

The reason the definition of fn expands into a call to list is so that we can incorporate the local environment, which we get by including scope in the arguments to list.

Here's an example where we do this manually:

(def bar (x)
  ((list 'lit 'clo scope '(y) '(+ x y)) 2))

Within bar we call a hand-made closure that includes scope, which, as we know from the example of foo above, will include a value for x.

> (bar 3)
5

The fn macro generates as its expansion exactly what we just made by hand. So this is equivalent to the definition above:

(def bar (x)
  ((fn (y) (+ x y)) 2))

The fn macro has two different expansions depending on how many arguments we pass to it. That's so that functions can have bodies of more than one expression.

If we call fn with two arguments, meaning a parameter list and an expression, as in e.g.

(fn (x) (cons 'a x))

then (cdr body) will be false, so the expansion will be

(list 'lit 'clo scope '(x) '(cons 'a x))

If we call fn with three or more arguments, meaning a parameter list plus two or more expressions, e.g.

(fn (x) 
  (prn 'hello) 
  (cons 'a x))

Then the expansion wraps a do around the expressions.

(list 'lit 'clo scope '(x) '(do (prn 'hello) (cons 'a x)))

We haven't seen do yet, but it's coming soon. It makes multiple expressions into a block of code.

Next comes something unusual: vmark is set to a newly created pair made by join. Missing arguments to primitives default to nil, so (join) is equivalent to (join nil nil), and when you see a call like this, it's usually for the purpose of creating a fresh pair to mark the identity of something.

Any pair with vmark in its car is treated by Bel as a variable. The next function, uvar, thus returns a new, unique variable each time it's called. The reason we need such a thing is so that when we're manipulating user code, we can add variables without worrying they'll accidentally share the names of variables created by users.

Now we see the definition of do, which we used in the expansion of fn. The do macro uses nested function calls to represent blocks of code.

Suppose you want to evaluate two expressions in order and then return the value of the last.

e1
e2

You can make this happen by embodying e2 in a function that you then call on e1.

((fn x e2) e1)

When this expression is evaluated, e1 will be evaluated first, and its value passed to the function in the car of the call:

(fn x e2)

Then e2 will be evaluated, ignoring the value of e1 passed in the parameter, and its value returned. Result: e1 and then e2 get evaluated, as if in a block. (You cannot of course safely use x as the parameter in case it occurs within e2, but I'll explain how to deal with that in a minute.)

This technique generalizes to blocks of any size. Here's one with 3 expressions:

((fn x ((fn x e3) e2)) e1)

You can use reduce to generate this kind of expression as follows

(def block args
  (reduce (fn (x y)
            (list (list 'fn 'x y) x))
          args))

> (block 'e1 'e2 'e3)
((fn x ((fn x e3) e2)) e1)

and this is almost exactly what the do macro does. If you look at its definition, it's almost identical to that of block.

One difference is that do is a macro rather than a function, which means that the nested call gets evaluated after it's generated.

The other difference is that we call uvar to make the parameter instead of using x. We can't safely use any symbol as the parameter in case it occurs in one of the expressions in the do. Since we're never going to look at the values passed in these function calls, we don't care what parameter we use, so long as it's unique.

If you want to establish a lexical binding for some variable, you do it with let, which is a very simple macro upon fn.

> (let x 'a 
    (cons x 'b))
(a . b)

Since let expands into a fn, you have the full power of Bel parameter lists in the first argument.

> (let (x . y) '(a b c) 
    (list x y))
(a (b c))

The macro macro is analogous to the fn macro in that it returns a literal macro. You'll rarely use these directly, but you could if you wanted to.

> ((macro (v) `(set ,v 'a)) x)
a
> x
a

Next we see the definition of def itself, which does nothing more than set its first argument to a fn made using the rest of the arguments, and also of mac, which does the same with macro.

(I like it when I can define new operators as thin, almost trivial seeming layers on top of existing operators. It seems a sign of orthogonality.)

If you were wondering why fn needs two cases — why we don't just always wrap a do around the body — the reason is that do calls reduce, which is defined using def, which expands into a fn. So to avoid an infinite recursion we either have to define reduce as a literal function, or make either fn or do consider the single expression case, and making fn do it was the least ugly.

Now that we have let, we can define or, which returns the first non-nil value returned by one of its arguments. Like most ors in programming languages, it only evaluates as many arguments as it needs to, which means you can use it for control flow as well as logical disjunction.

> (or 'a (prn 'hello))
a

The definition of or is the first recursive macro definition we've seen. Unless it has no arguments, an or will expand into another or.
This is fine so long as the recursion terminates, which this one will because each time we look at the cdr of the list of arguments, which will eventually be nil. (Though you could spoof or by constructing a circular list and applying or to it.)

In effect

(or foo bar)

expands into

(let x foo
  (if x 
      x
      (let y bar
        (if y
            y
            nil))))

except that we can't actually use variables like x and y to hold the values, and instead have to use uvars.

Notice incidentally that the expression above could be optimized

(let x foo
  (if x
      x
      bar))

but the definition of or doesn't try to; like every definition in Bel, its purpose is to define what or means, not to provide an efficient implementation of it.

In Bel, macros are applyable just like functions are, though if you do that you get only the logical aspect of or and not the control aspect, since in a call to apply the arguments have already all been evaluated.

> (apply or '(nil nil))
nil
> (apply or '(nil a b))
a

The and macro is similar in spirit to or, but different in its implementation. Whereas or uses recursion to generate its expansion, and uses reduce. Since

(and w x y z) 

is equivalent to

(if w (if x (if y z)))

it's an obvious candidate for reduce.

Notice the function given to reduce has a single parameter. A function given as the first argument to reduce will only ever be called with two arguments, so usually such a function will have a list of two parameters, but in this case we just want to cons an if onto the front of the arguments each time.

The other interesting thing about and is what we do when it has no arguments. While we want (or) to return nil, we want (and) to return t. So in the second argument to reduce, we replace an empty args with (t).

The next function, =, is the one that programs usually use to test for equality. It returns true iff its arguments are trees of the same shape whose leaves are the same atoms.

> (id '(a b) '(a b))
nil
> (= '(a b) '(a b))
t

In Bel, everything that's not a symbol, character, or stream is a pair. Numbers and strings are pairs, for example. So you'd never want to use id for comparison unless you were specifically looking for identical list structure.

In the definition of = we see the first instance of square bracket notation.

(all [id _ (car args)] (cdr args))

This is equivalent to

(all (fn (x) (id x (car args))) 
     (cdr args))

I.e., is everything in the cdr of args id to the car? You know you can use id to test equality at this point, because if one of the args is an atom, they all have to be for them to be =, and you can use id to test equality of atoms.

If id took any number of arguments (it doesn't, because I want axioms to be as weak as possible), the preceding all expression could have been simply

(apply id args)

The next four functions are predicates for the four types. All use = for this test even though all could use id. My rule is to use = unless I specifically need id. That way the appearance of id is a signal that code is looking for identical structure.

Then we see proper, which tells us whether something is a proper list. Informally, a proper list is one that we don't need a dot to display.

> (proper nil)
t
> (proper '(a . b))
nil
> (proper '(a b))
t

Formally, something is a proper list if it's either nil or a pair whose cdr is a proper list, which is exactly what the definition says.

In Bel, a proper list of characters is called a string, and has a special notation: zero or more characters within double quotes.

> (string "foo")
t

The next function, mem, tests for list membership.

> (mem 'b '(a b c))
(b c)
> (mem 'e '(a b c))
nil
> (mem \a "foobar")
"ar"

Since it uses some, it returns the rest of the list starting with the thing we're looking for, rather than simply t.

In the definition of mem we see the first use of an optional parameter. If in a parameter list you see a list beginning with the symbol o, then the parameter following the o is an optional one. It can be followed by an expression, and if no value is supplied for the parameter in the call, it gets the value of that expression instead (or nil if there isn't one). So

> ((fn (x (o y)) y) 'a)
nil
> ((fn (x (o y 'b)) y) 'a)
b

The optional parameter doesn't have to be a single symbol; it can be a full parameter list. An example will be easier to understand if we use let:

> (let (x (o (y . z) '(a . b))) '(f)
    (list x y z))
(f a b)

In the definition of mem, the optional parameter is a comparison function, which defaults, as such functions usually will, to =. By supplying different comparison functions we can get different behaviors out of mem.

> (mem 3 '(2 4 6 8) >)
(4 6 8)

The next function, in, is effectively a generalization of =. It returns true iff its first argument is = to any of the rest.

Then come three common combinations of car and cdr: cadr, which gets the second element of a list, cddr, which takes two elements off the front, and caddr, which gets the third element. We'll have other ways to do these things once we've defined numbers.

The case macro takes an initial expression e, followed by alternating keys (which are implicitly quoted) and expressions, and returns the result of evaluating the expression following the key that's = to the value of e.

If case is given an even number of arguments, the last one is the default. Otherwise the default is nil.

E.g. this function

(def sname (s)
  (case s 
    + 'plus
    - 'minus
      'unknown))

returns the name of a sign represented by a symbol:

> (sname '+)
plus

The iflet macro lets you use the result of a test in an if. It works like an ordinary if, except that it takes an initial variable, which in any then expression will be lexically bound to the value returned by the preceding test expression.

> (iflet x nil      'foo
           '(a b c) (car x)
                    'bar)
a

Notice how similar the definitions of case and iflet are, despite their different purposes. They're both recursive macros, like or, and both work through their arguments two at a time.

We use iflet to define aif, which implicitly binds the variable it to the value of the preceding test expression.

> (map (fn (x)
         (aif (cdr x) (car it)))
       '((a) (b c) (d e f) (g)))
(nil c e nil)

The function given to map here tests whether x has a non-nil cdr, and if so returns the car of it.

With aif and some, it's trivial to define find, which returns the first element of a list that matches some test.

> (find [= (car _) \a] 
        '("pear" "apple" "grape"))
"apple"

The begins function returns true iff its first argument is a list that begins with its second argument:

> (begins '(a b c d e) '(a b))
t

Like mem, it takes an optional comparison function that defaults to =.

It's used in caris, which returns true iff its first argument is a pair whose car is its second.

> (caris '(a b) 'a)
t

This is one of those functions you end up using surprisingly often, because it's so common for the car of a list to have some special significance.

Our next function, hug, applies a function to pairs of elements of a list. Since the default function is list, by default it simply returns pairs of elements.

> (hug '(a b c d e))
((a b) (c d) (e))
> (hug '(1 2 3 4 5) +)
(3 7 5)

This too is something you need surprisingly often, especially when operating on expressions, where it's common to have subexpressions that form implicit pairs. We've seen this already in if, case, and iflet, and we see it implemented with hug in the next macro, with, which is a multi-variable let.

> (with (x 'a 
         y 'b) 
    (cons x y))
(a . b)

It binds the variables in parallel in the sense that the bindings of previous variables are not visible in the expressions defining the values of later ones.

> (let x 'a
    (with (x 'b
           y x)
      y))
a

The next function, keep, returns all the elements of a list that pass some test

> (keep odd '(1 2 3 4 5))
(1 3 5)

and rem removes its first argument from a list

> (rem \a "abracadabra")
"brcdbr"

or more precisely, since it takes an optional comparison function f, all the elements of the list that fail [f _ x], where x is the first argument.

> (rem 4 '(5 3 1 2 4) >=)
(3 1 2)

The next two functions, get and put, are for operating on key-value stores represented as lists of pairs like this one:

> (set x '((a . 1) (b . 2) (c . 3)))
((a . 1) (b . 2) (c . 3))

The first, get, retrieves entries,

> (get 'a x)
(a . 1)
> (get 'z x)
nil

and the second, put, creates them.

> (put 'z 26 x)
((z . 26) (a . 1) (b . 2) (c . 3))
> (put 'a 9 x)
((a . 9) (b . 2) (c . 3))

The reason get returns the whole pair instead of just the associated value is so that we can distinguish between a key having a value of nil and having no value.

Notice that put doesn't change the value of x, just as consing something onto x wouldn't change the value of it.

The function rev reverses a list,

> (rev "able")
"elba"

and snap breaks off a piece of its second argument that's as long as its first, returning both parts:

> (snap '(a b) '(1 2 3 4 5))
((1 2) (3 4 5))

It's used in udrop (for "unary drop"), which returns just the remaining part:

> (udrop '(a b) '(1 2 3 4 5))
(3 4 5)

Then we get the identity function, idfn:

> (map idfn '(a b c))
(a b c)

You wouldn't call this directly (why bother?) but you often end up using it as a default or when operating on functions.

The function is is a little unusual in that it returns a function for comparing its argument to something.

> ((is 'a) 'a)
t

An is is a partially applied =, so in principle we won't need it after we define partial application later on. But this case is so common that it's convenient to have a separate operator for it.

Now come several macros for dealing with errors. The first, eif, introduces several new concepts, so I'll explain them first, then eif itself.

One thing we see being used for the first time here is dynamic binding. To show how it works, we'll define a function that refers to a variable with no global value:

(def foo ()
  snerg)

If we call foo normally, we'll get an error saying snerg has no value. But if we call foo within a dyn expression that creates a dynamic binding for snerg, it will work:

> (dyn snerg 'a 
    (foo))
a

We couldn't get the same result by saying

(let snerg 'a
  (foo))

because a lexical binding created by let (or more precisely by a function call) is only visible within its body. And whereas lexical bindings get saved in closures (as in e.g. is), dynamic bindings, like global ones, don't.

Another concept we're seeing for the first time is that of a continuation. A continuation is basically a computation in the middle of happening. (Or more prosaically, it's a copy of the stack.) A continuation is callable, like a function, and if you call one, you restart the computation where it was created.

You can get your hands on the current continuation by calling the ccc special form with a function of one argument. It will be the current continuation, which you can then save. Let's try making one.

Here's some simple code that makes a list:

> (list 'a 'b)
(a b)

Now let's try replacing the 'b with an expression that saves the current continuation before returning b:

> (list 'a (ccc (fn (c) 
                  (set cont c) 
                  'b)))
(a b)

It returns the same value, but in the process we've set cont to the continuation at the point where the ccc occurred. If we call cont with some value, our old computation will be restarted as if that value had been returned by the ccc expression:

> (cont 'z)
(a z)

Continuations work any number of times:

> (cont 'w)
(a w)

One thing we can use continuations for is aborting computations. If we save a continuation before starting something, then by calling the continuation we can escape from the middle of it.

> (ccc (fn (c) 
         (dyn abort c 
           (do (abort 'a)
               (car 'b)))))
a

Here we bind abort to the continuation before we start evaluating the do expression. The second expression within the do

(car 'b)

would cause an error if it were evaluated. But we never get to it, because we call abort first.

When an error occurs, err is called on a value representing the error. So if the variable that we dynamically bind is err instead of abort, we can take over what happens when an error is signalled.

Here we rebind err to return hello when an error occurs:

> (ccc (fn (c) 
         (dyn err (fn (x) (c 'hello))
           (car 'b))))
hello

This time the car expression does get evaluated, which causes an error to be signalled. But by establishing a dynamic binding for err, we've ensured that it's our function that gets called when the error is signalled. And our function simply returns hello from the ccc expression.

You can probably imagine how you'd write a macro to evaluate an expression in an error-proof way: just make the expansion put the expression within something like

(ccc (fn (c)
       (dyn err (fn (x) (c nil))
         expression)))

except of course you'd want to use a uvar instead of c.

Now let's look at eif. It's like if except that which of its arguments get evaluated depends not on whether its test expression returns true, but whether it causes an error.

> (eif x (car 'a)
         'oops
         x)
oops
> (eif x (car '(a b))
         'oops
         x)
a

The variable before the test expression (in this case x) will be lexically bound either to the value returned by the test expression, or to whatever err was called with if an error occurred.

The expansion of the first eif above looks like

(let v (join)
  (let w (ccc (fn (c)
                (dyn err [c (cons v _)] (car 'a))))
    (if (caris w v id)
        (let x (cdr w) 'oops)
        (let x w x))))

except of course v, w, and c will be uvars. When we look at the code above, we can see how eif tells whether the value it got back from the test expression represents an error or not. The variable v is bound to a newly created pair. Within the continuation, err is bound to a function that returns v consed onto whatever err was called with. So to decide which of the two succeeding expressions to evaluate, we just check whether the car of w is v. (And of course we check using id, not =.)

The eif macro is the most general error-catching macro, but there are two more, onerr and safe, that are more commonly used. The onerr macro takes two expressions and returns the value of the first if the second causes an error:

(onerr 'oops (car 'a)) oops

and the safe macro simply returns nil if the expression within it causes an error:

> (safe (car '(a b)))
a
> (safe (car 'a))
nil

The next function, literal, returns true iff its argument evaluates to itself,

> (map literal (list nil "foo" car))
(t t t)

while variable returns true iff its argument is a variable, meaning an ordinary symbol or a uvar:

> (map variable (list 'x (uvar) t))
(t t nil)

And isa is for checking whether something is a particular kind of lit. Like is, isa doesn't do the check, but returns a function that does

> ((isa 'clo) map)
t

The operators we've defined so far, together with the axioms, will now enable us to define a function that acts as a Bel interpreter: a function that will take any Bel expression as an argument and evaluate it.

(We don't need all the operators we've defined so far to define a Bel interpreter. These are, rather, the minimum set we need to define an interpreter in a way that's not too ugly.)

Much of the code in the interpreter operates on the same set of structures, and these always have the same parameter names.

Each thread is a list

(s r)

of two stacks: a stack s of expressions to be evaluated, and a stack r of return values.

Each element of s is in turn a list

(e a)

where e is an expression to be evaluated, and a is a lexical environment consisting of a list of (var . val) pairs.

The variable p holds a list of all the threads (usually other than the current one).

The other thing we need to pass around in the interpreter is the global bindings, which is another environment represented as a list of (var . val) pairs. I use the variable g for this.

The most common parameter list we'll see is

(s r m)

where s is the current expression stack, r is the current return value stack, and m is a list (p g) of the other threads and the global bindings.

The interpreter itself begins with the function bel, which takes an expression e and starts the interpreter running with a single thread in which e is to be evaluated. The arguments it sends to ev represent the usual (s r m) triple. So

(list (list e nil))

is an expression stack containing nothing except e, to be evaluated in a null environment. The second argument, nil, is the return value stack, which is empty because we're not returning from anything. And the third argument is m, aka (p g), a list of the other threads (currently nil) and an environment to use as the global bindings.

If we jump ahead a few definitions to ev, we come to the core of the interpreter. This function plays the role eval did in McCarthy's Lisp. Its parameters implicitly pull an (e a) expression-environment pair off the expression stack. There are only five things the expression can be:

1. A literal, in which case we return it.

2. A variable, in which case we call vref to look up its value.

3. An improper list, in which case we signal an error.

4. A list beginning with a special form, in which case we call the associated function stored in forms.

5. An ordinary call, in which case we call evcall on it.

I'm going to follow the trail of evaluating a literal to explain some things about how evaluation works, then come back and examine the other cases.

One of the most important things to understand about the interpreter is that it never returns a value till it terminates. The way it implements returning a value in the program it's evaluating is not by returning a value itself, but by a recursive call to the interpreter with a shorter expression stack and the return value consed onto the return stack. And that's what we see happening in the code that runs when e is a literal:

(mev s (cons e r) m)

That is what returning a value looks like.

The function mev (m = multi-threaded) is what the interpreter calls to continue evaluation after doing something. Its purpose is to check whether interpretation should terminate, and if not, to allow another thread to run.

The first thing mev does is check if the current thread has run out of work to do. If so, if s is nil, it checks whether there are other threads in p. If there are, it calls sched to run one. If not, if this is the only thread and we've just finished it, then it returns whatever's on top of the return value stack as the value of calling the interpreter.

If we haven't finished the current expression stack, then we have to check whether we should stay in this thread or switch to another one. Ordinarily you want to give other threads a chance to run, but sometimes you can't, if you're doing something that requires multiple steps to complete, and in the middle is in an inconsistent state.

The way a program signals that it doesn't want to be interrupted is by dynamically binding lock to a non-nil value. If lock is on, we put the current thread on the front of the list of threads, and if not we put it on the end. Since sched always runs the first thread on the list, if we keep the current thread on the front, it keeps running.

Now that we've seen how mev and sched work, let's return to ev. If e is a variable, we call vref to evaluate it. And what vref ordinarily does is this:

(aif (lookup v a s g)
     (mev s (cons (cdr it) r) m)
     (sigerr 'unbound s r m))

You may now recognize that kind of call to mev: that's returning a value. If the lookup succeeds, it returns the (var . val) pair it found, so the value is the cdr of it. If lookup fails, it returns nil, in which case we've just encountered a reference to an unbound variable, and we should signal an error.

Let's skip down to lookup and see what it does. It checks, in order, whether the variable has a dynamic binding, a lexical binding, or a global binding. At the end there are special cases for the two variables globe and scope; for them the interpreter simply "leaks" the corresponding parameter. Leak is an apt metaphor in this situation because data is going from one layer of Bel to another: from the interpreter running in Bel to the Bel program it's evaluating.

We use binding to check whether a variable has a dynamic binding. It checks by searching the expression stack looking for an entry binding that variable. As we'll see when we get to its definition, dyn works by inserting a special entry on the expression stack listing the variable it wants to bind and its value. There are other operators that insert special entries on the expression stack too. These entries are distinguishable from ordinary expressions by beginning with a pair called smark.

While we're here, let's look at sigerr. This is how the interpreter signals an error. As we saw earlier in the examples of continuations, it begins by looking for a dynamic binding for err, and if there is one, it calls it using applyf, which we'll get to later. If there isn't a binding for err, then there's an error in the interpreter itself, and we call err about it.

This sort of code where things happen at two different levels -- the Bel instance running the interpreter, and the Bel program that the interpreter is evaluating — is inevitably a bit confusing, but that comes with the territory when a language is written in itself. For errors, at least, there is a simple rule of thumb: when there's an error in a program you're evaluating, you call sigerr, and when there's an error in yourself, you call err.

Calling sigerr is like a parent reporting that the baby is crying. Calling err is crying oneself.

But what about the first half of vref, the one in which (inwhere s) returns true? This code is for handling assignments. In Bel, any value that lives in a pair can be assigned using set. For example,

> (let x '(a b c)
    (set (cadr x) 'z)
    x)
(a z c)

This code in vref is what makes it happen. It works as follows. When we're in a set, another special entry (beginning as usual with smark) is put on the stack saying that we're not looking for the value of something, but its location. The function inwhere checks for one of these, and if it finds one, we return not the value we're looking up, but the pair it occurs in, plus either a or d to say whether it's in the car or the cdr.

New global variables are created implicitly by assigning values to them, and this is where that happens. The special stack entry found by inwhere says whether a new global binding should be created (it should be for set, but not for push for example) and if it should, we create a new pair to hold its name and value, and splice it into the global variables.

Notice that in this case the first argument to mev, at the end, is (cdr s) rather than s. We're discarding the special stack entry found by inwhere.

Incidentally, this is a case where we need lock, because when this new binding is created, the value is nil initially. So if code in another thread looked up this variable, there would be a window during which it seemed to have the value nil. The code that handles locking is in the definition of set, which we'll see later.

Now back up to ev. The next case is when e isn't a proper list. We know by this point that e not an atom, because every atom is either a literal or a variable. So e must be a list, but we have to make sure it's a proper one. If it isn't we call sigerr.

By the next line we know that e is a nonempty proper list. So the next question is, is the first element a special form? The variable forms is a list of (name . function) pairs telling the interpreter what to do when it encounters an expression beginning with name.

The first of these is smark, the pair we created for marking stack entries that are not just ordinary expressions. The initial value of forms

(set forms (list (cons smark evmark)))

means that when the expression we've just taken off the stack begins with smark, we should call evmark. And in the definition of evmark we see the four types of stack entries we use smark for, each indicated by the symbol that comes after smark in the expression we put on the stack.

One of these, bind, we've already talked about. This is what dyn puts on the stack to establish a dynamic binding. When we return back through one, all that should happen is that the dynamic binding ceases to exist. The bind entry itself is a no-op; we just call (mev s r m) and get on with things.

We're also familiar with the idea of a loc entry; that's what we were just looking for in inwhere. We made a point of removing it from the stack once we'd found it. So if we return up through a loc entry, that means we were unable to find a pair to modify, and we should signal an error. E.g.

> (set \a 5)
Error: unfindable

A fut (future) stack entry contains a closure to be called on (s r m). The interpreter inserts these when it needs to do something in several steps. This happens so often that there's a special fu macro (the resemblance to fn is intentional) for creating these closures.

There's one of them in the prot clause of evcall. A prot (protect) stack entry means that an expression should be evaluated even when calling a continuation throws control back over it. You'd use this for example to make sure a file you opened eventually got closed. Since these protected expressions aren't supposed to return values, the code for evaluating them includes a fu for throwing away the value that gets put onto the return value stack after the expression is evaluated: all this fu does it turn a call of the form (mev s r m) into (mev s (cdr r) m). We'll learn more about protected expressions when we get to the code for creating them.

The rest of the special forms are defined using the form macro, which runs its arguments through formfn and then puts the result in an entry in forms. Let's start by looking at an example of a special form defined with it. The first is the definition of quote, which is about as simple as a special form can get. The first parameter, (e), is the parameter list of the form as it will be called. So (e) means that quote will take exactly one argument. We call it e, for expression, because it won't have been evaluated. The remaining arguments, a s r m, represent the lexical environment plus the usual s r m state of the world.

The body of the form is a familiar type of call to mev, representing a return. So this definition says that quote takes one argument, e, and returns it unevaluated.

The definition of quote will be transformed by formfn into the equivalent of

(fn v
  (eif w (apply (fn (e) (list e))
                (car v))
         (apply sigerr 'bad-form (cddr v))
         (let (e) w
           (let (a s r m) (cdr v) 
             (mev s (cons e r) m)))))

The test expression in the eif accumulates all the form's parameters. If an error occurs while doing that, we signal an error. (We know (cddr v) will be the familiar (s r m).) Otherwise we bind the parameters and evaluate the body of the form.

The reason we do this in two parts is in case someone calls the form with the wrong arguments. If you're using form to define a form, you can (and must) catch all other errors yourself, but you can't catch that one. At least not short of using a single parameter to hold all the arguments, and then teasing them out manually. Since that would make form definitions ugly, the form macro does it for you.

> (quote a b)
Error: bad-form

Next comes the definition of if. Unlike quote, if does several things, and when we do several things in a form, we don't just evaluate a block of code; we put the things we need to do on the stack and call mev.

In the base case, if the if has no arguments, we just return nil, using the familiar formula. Otherwise we want to evaluate the first argument and then, if there are more arguments, evaluate the appropriate one depending on the value of the first. Which is basically the code translated into English. Putting

(list (car es) a)

on the stack is "evaluate the first argument," and the conditional that puts a closure that calls if2 on the stack, but only if (cdr es) is true, is "if there are more arguments, evaluate the appropriate one."

Notice that if2 is just an ordinary function, not a form. It handles the second part of evaluating an if, the choice of which subsequent expression to evaluate depending on the value returned by the first.

If the value on top of the return stack is true, then the test expression returned true, and the whole if returns the value of the succeeding expression, so we just put (car es) onto the stack and go.

But if the first expression returned nil, we need to keep going. If we're evaluating

(if a b c d e)

and a returns nil, then the value of the if expression is the value of

(if c d e)

and that is exactly what if2 is doing when it puts

(cons 'if (cdr es))

on the stack. So the if form is recursive in the sense that it can cause another if expression to end up on the stack, where it will of course be handled by the if form.

Regardless of what we put on the stack in if2, we need to discard the value returned by the test expression, which is why the second argument to mev in if2 is (cdr r).

The if in if2 is where conditionalness (for lack of a better word) gets "leaked" from the Bel in which the interpreter is running to the Bel program that the interpreter is evaluating.

The next form, where, is the one that creates the stack entries that inwhere looks for. It takes an expression e followed by an optional argument saying whether to create a new binding for a variable if there isn't one already. It asks for e to be evaluated by putting the conventional

(list e a)

on the stack. But also, adjacent to this, it puts a special loc entry on the stack saying that what we want when evaluating e is its location, not its value. This will be seen by inwhere in functions like vref and handled accordingly.

> (let x 'a
    (where x))
((x . a) d)

This return value is a list of the actual lexical binding created by that let, plus a d indicating that the value in question is in the cdr of the pair. It's hard to imagine a reason to call where in ordinary code; you use it in macros like set that modify things.

Notice incidentally that the second, optional argument to where isn't evaluated. It's inserted directly into the loc entry built by where.

After where, we see another form we're somewhat familiar with: dyn, which establishes dynamic bindings. This definition is like that of if in the sense that there's a function, dyn2, that does the second half of the work. The first half is to put the first expression, e1 on the stack to get it evaluated. Its value will be what we bind the variable to.

In dyn2 we see this binding being created, in the form of a stack entry being put on the stack. We also ask for the evaluation of the second expression, and we put that request, (e2 a), in front of the bind entry. If we see a reference to v during the evaluation of e2, the bind entry will be sitting on the stack to tell us it has a dynamic binding.

Notice that the payload of the bind entry will be a (var . val) pair of the familiar form, just like we find in lexical and global environments. This is not a coincidence. It means the code that sets global or lexical variables also sets dynamic bindings; in fact, the code doesn't even know which type it's operating on; all it knows is that it's doing something to the cdr of a pair.

> (dyn x 'a
    (do (set x 'b) 
        x))
b

This wasn't a deliberate design choice. Like many other aspects of Bel, it's just a consequence of making the interpreter as simple as possible. I tried to let simplicity make as many decisions for me as I could.

Like where and dyn, after works by putting a special entry on the stack — this time a prot entry. We saw what a prot entry means when examining evmark. All the after form does is create the prot entry; the real work happens elsewhere.

The ccc form creates a continuation, or more precisely generates code that calls a function on a continuation. A continuation itself is a simple thing — basically just s and r, which between them are a complete representation of the state of the current thread.

Finally, the thread form takes an expression and starts evaluating it in a new thread. Unusually, nearly all the work is in the last argument to mev, where we build new expression and return value stacks much as we did up in bel. The second argument (cons nil r) means the thread expression itself returns nil in the thread in which it occurs.

Along with lit and apply, those seven operators — quote, if, where, dyn, after, ccc, and thread — are all the special forms. But if you need more you can easily define them with form.

Now we come to the code that handles the last case in ev, an ordinary call. Its definition looks a lot like the code we saw in the forms. All the code in the interpreter is either calls to mev or to things that call mev. By now we're used to reading this sort of thing: evcall puts the car of the expression on the stack to be evaluated, plus a closure that calls evcall2 to do the rest of the work.

The rest of the work, as we see in evcall2, begins with checking whether the value of the car of the expression is a macro. If it is, we call applym. If it isn't, we know we can evaluate the arguments, so we put them all on the expression stack, along with a closure that will snap the corresponding number of values off the top of the return stack, and then send them plus the operator to applyf.

When we look at applym, we see that the evaluation of a macro call also goes through applyf, but with different arguments. We apply the function within the macro, (caddr mac), to the unevaluated arguments, args. This generates the macroexpansion. But the macroexpansion then has to be evaluated, and that's the purpose of this closure we put on the stack:

(fu (s r m)
  (mev (cons (list (car r) a) s)
       (cdr r)
       m)

The (car r) within it is a sign of something unusual happening: we're moving something (the macroexpansion) from the return value stack to the expression stack.

There's a slight surprise waiting in applyf: the apply special form is implemented as a clause here. What it does is pretty simple: apply is a recursive call to applyf with the arguments joined together. The next case is the general one, when f is a lit, and in that case we call applylit.

Functions aren't the only thing you can apply in Bel. You can apply anything if you define a way to do it. We haven't gotten to this yet, but numbers for example return the corresponding element of a list:

> (3 '(a b c d))
c

Such expressions are also settable:

> (let x '(a b c d)
    (set (3 x) 'z)
    x)
(a b z d)

Since the thing we're about to apply might be a settable reference, the first thing we need to check in applyprim is whether we're in a where, just as we do when looking up the value of a variable. If we are, then we look in a list called locfns to see if there's one that matches, and if so we call the corresponding function on the function and its arguments.

Let's skip down to the locs defined after applyprim to see some of these. The loc operator defines new locfns, and after its definition we see the loc for car. Or more precisely, a loc whose test will match the symbol car; the keys of locs are predicates, not symbols.

We don't need many locs; knowing how to set the car or cdr of a pair will handle most cases. When we look at the loc for car, it's pretty simple: it just "returns" (by consing onto the return stack) a list of the argument and an a, to indicate we're looking in the car.

> (let x '(a b c) 
    (where (car x)))
((a b c) a)

The loc for cdr is similarly simple.

After the inwhere check, we see cases for the four predefined applyable things in Bel: primitives, closures, macros, and continuations.

To apply a primitive, we call applyprim. Let's skip down to it and see what it does. The first thing applyprim does is look the prim up in a list of prims to see if it really is one. If you're wondering why prims is organized the way it is, the primitives are grouped by the maximum number of arguments they take. This is frankly a trick to get around not having numbers yet; we can use udrop with the position of the prim in prims to detect calls with too many arguments.

Since primitives can take at most two arguments, we pick out two, which we call a and b. Since car and cdr of nil both yield nil, this is how we make missing arguments to primitives default to nil.

> (join)
(nil)

If the call is a legal one, we call the primitive with the same name. This is another place where behavior leaks from the instance of Bel in which the interpreter is running to the code it's evaluating: when the interpreter sees a call to car in the code it's evaluating, the interpreter calls car itself.

The primitive might signal an error, if for example we call car on an atom. So the case expression containing the calls to the primitives is wrapped in an eif, and if there's an error, we leak the same error object (whose nature is unspecified) up into the program we're evaluating. Otherwise we just "return" whatever the call returns, by consing it onto the return stack.

Since primitives are one of the cases where it's most confusing to have things happening at two levels, I want to be as clear as possible about how they work. The interpreter can call car. That's true by assumption. Up in the program being evaluated, we want car to have a value. So we give it a sort of placeholder value, the list (lit prim car), which means, in effect, "please call car for me, interpreter," which the interpreter does whenever it encounters one of these placeholders being called like a function.

Now back up to applylit. The next clause handles all the functions that aren't prims, and it's implemented by calling applyclo. But since functions are just lists and there's nothing to stop someone from trying to call an ill-formed clo, we have to check the validity of every component of this supposed closure first.

If it checks out, we send it and the arguments to applyclo. This function does two things, in the sense of putting two things on the expression stack. The first fu on the stack calls pass to get a lexical environment representing the parameter bindings onto the top of the return stack, and the second simply puts the body of the function (which is a single expression) on the stack, with those bindings as its environment.

The real work is done by pass and its subroutines typecheck and destructure. Between them these take a parameter list and a list of arguments, and turn them into an environment consisting of (var . val) pairs.

Before we look at them I should explain a feature of Bel parameter lists that we haven't encountered yet: type checking. A parameter of the form

(t v f)

means that unless f is true of the value passed to v, an error will be signalled. So if we define

(def consa ((t xs pair)) 
  (cons 'a xs))

and we call it with an argument that's not a pair, we'll get an error:

> (consa 'z)
Error: mistype

If the variable and test in a t parameter are symbols, you can simply conjoin them with a vertical bar.

(def consa (xs|pair)
  (cons 'a xs))

The reader expands x|y into (t x y).

You can nest t parameters, o parameters, and parameters that are pairs without restriction.

(def foo ((o (t (x . y) [caris _ 'a]) '(a . b)))
  x)

> (foo '(b b))
Error: mistype
> (foo)  
a

Though as you can see, programs get hard to read if you do too much computation in the parameter list.

The way pass works is by descending depth-first through the parameter list, trying to match it up with the arguments. It takes six arguments. The last three are the familiar (s r m), and the first three represent a part of the parameter list, the corresponding part of the argument list, and the environment we've accumulated so far.

The reason we have to give pass (s r m) as well is that the work it does can't be done as a simple subroutine. It's not simply matching parameters and arguments. The default expressions for optional parameters mean we're really running the interpreter when we call pass. And pass doesn't return the result of matching parameters with arguments, but rather ensures that one ends up on the top of the return value stack. (In other words, it causes a value to be returned in the Bel program that the interpreter is evaluating, rather than returning a value within the Bel instance in which the interpreter is running.)

It starts by defining a local function, ret, that returns a value in the sense of calling mev with the new value consed onto the return stack. Then we have a bunch of cases to consider. If there are no parameters left, then we check whether there are any arguments left. If there are, the function has been called with too many arguments, and we should signal an error; if there aren't, then we've finished, and we can put the environment we've built onto the return stack.

If we get past that test, we know pat, the parameter or parameters, is non-nil. Is it a literal? If so that's an error, because you can't use a literal (other than nil) as a parameter. Whereas if it's a variable, we can just add a new (var . val) pair of it and whatever the arguments are to the env we've built so far, and "return" it using ret.

Since literal and variable between them cover all atoms, if we get past these tests we know pat must be a pair, so there are three possibilities left: that's it's a t parameter, that it's an o` parameter, or that it's an ordinary list.

If it's a t parameter, we call typecheck, and what that does is put a call to the test function on the expression stack, followed by a closure that checks whether that call returned true, and if so recursively calls pass with the var stripped of the type check. Otherwise it signals an error.

Whereas if pat is an optional parameter, since we know we have a value for it (whatever arg is), we can ignore the default expression and call pass recursively as if it were an ordinary parameter.

How do we know we have a value for pat? What if arg is nil? This is not the point where we check whether we've run out of arguments. If arg is nil at this point, that means the value being passed as an argument is nil, not that there are no arguments.

In the final case in pass, the parameter is a list, and we need to call destructure to go inside it and the arguments to see if they match. When you call a function with a parameter list (rather than a parameter like args that's a single variable), this is the case you go through the first time through pass.

This is where you notice if you've run out of arguments, and that is the first thing destructure checks. If the first parameter is an optional parameter, you're ok so far, because you can evaluate its default expression to get a value for it. In that case put the default expression on the stack, followed by a pair of closures that in effect do a depth-first traversal of the parameter list, one calling pass on the first parameter (with the value returned by the default expression as the "argument"), and a second calling pass on the remaining parameters, with nil as the argument, since we already know it's empty.

If arg is nil and the first parameter in our list isn't an optional one, then we know the function was called with too few arguments, and we signal an error.

> ((fn (x y) x) 'a)
Error: underargs

The other error case is when arg is a non-nil atom. We can match such an argument with a single parameter, but not with a list of parameters. So if arg is an atom, we signal an error.

> ((fn ((x y)) x) 'a)
Error: atom-arg

The default clause of destructure is the "normal" case where we have a non-empty list of arguments. Here we also use mev to do a depth-first traversal of the parameters, very much like the one we saw in the first clause of destructure.

The fact that pass uses the environment it's in the process of building as the environment when it puts expressions on the stack means the bindings of earlier parameters are visible to the code in later ones:

> ((fn (x (o y x)) y) 'a)
a
> ((fn (f x|f) x) pair 'a)
Error: mistype

Now to continue with our own depth-first traversal of the interpreter, back up in applylit, which we're halfway through. The next clause is for macros. The difference between applying a macro and an ordinary macro call is that when you apply an operator, the arguments have already been evaluated. But you can generate a macro call easily by consing the macro onto the front of a list of quoted arguments. So you just call applym on that. (You could send it to mev, but you know it will end up in applym, so you might as well go straight there.)

The next clause in applylit is for continuations. After checking the validity of a continuation, we call applycont to call it.

In the definition of ccc we saw that making a continuation is simple: it's just a list of s and r. The work is done when the continuation is called. But even then it's not that much work. If a continuation is

(lit cont s2 r2)

you could call it on an argument a simply by saying

(mev s2 (cons a r2) m)

except for two things. One is that you have to check that the form of the continuation is valid, just as you do with a closure. The other is that there may be prot entries in your current evaluation stack, and the whole point of prots is that those expressions get evaluated even if evaluation is interrupted before you reach them.

So you can't just use s2 as the first argument to mev. You have to combine s2 with everything that you need to keep from your current expression stack. That includes prots and also binds, since the code in a prot could refer to a dynamically bound variable.

Those two possibilities account for all the complexity of calling continuations. Otherwise it would be one line in applylit.

Finally, in the last clause of applylit, we see the code that makes it possible, for example, to use a number in functional position:

> (2 '(a b c))
b

The variable virfns (for virtual functions) is a list of (n . f) pairs where n is a type of lit and f is a function that generates an expression to be evaluated when such a lit is encountered in functional position. Since these functions generate expressions, they're a lot like macros.

Although we haven't introduced numbers yet, here's the virtual function for them, so you can see what one looks like:

(vir num (f args)
  `(nth ,f ,@args))

It looks like a macro definition, and does much the same thing. It will turn

(2 '(a b c))

into

(nth 2 '(a b c))

There's a good deal more of the language still to come, including numbers and I/O, but we have now seen the entire Bel interpreter.

Next come several functions for operating on functions. The first, function, tells whether something is a function and if so what kind.

> (map function (list car append 'foo))
(prim clo nil)

The next, con, returns a constant function:

> (map (con 'yo) '(a b c))
(yo yo yo)

Then comes an important one, compose, which takes any number of functions and returns their composition. For example, cadr is equivalent to a composition of car and cdr:

> ((compose car cdr) '(a b c))
b

When the names of what you're composing are symbols or numbers, Bel lets you abbreviate calls to compose with colons.

> (car:cdr '(a b c))
b

Functional composition lets you eliminate a lot of unnecessary variables. I warned earlier that the definitions that occur early in the Bel source are not in truly idiomatic Bel, because that would require things that hadn't been defined yet. Composition is one of them. If you had to define cadr in idiomatic Bel you'd say

(set cadr car:cdr)

There's a special abbreviation for composing no, which is to prepend a tilde.

> (map ~cdr '((a) (a b c) (a b)))
(t nil nil)

Now we can understand the idiomatic definition of all that I gave early on:

(def all (f xs)
  (~some ~f xs))

It's actually inaccurate to say that compose operates on functions, because it can operate on anything that we can call like a function.

> (2:or nil '(a b c))
b

I could solve this problem by inventing some new term for things that can be called like functions, but that seems a bit bogus, so instead I'm going to be irresponsible and just talk about functions when I mean things callable like functions. Because the fact is that just about anywhere you can use a function, you can use anything else that's callable.

The next function, combine, produces something more general: it takes one argument, f, and returns a function that combines functions using f. So this for example

((combine and) car cdr)

will yield a function equivalent to

(fn (x)
  (and (car x) (cdr x)))

> (map ((combine and) car cdr)
       '((a . nil) (a . b) (nil . b)))
(nil t nil)

Since combine of and and or are so frequently needed, we predefine two functions, cand and cor, for those cases.

> ((cand pair cdr) '(a b))
(b)
> ((cor char pair) 'a)
nil

Next come the two classic reduction functions, left and right fold. Once again, their definitions are complicated by taking any number of arguments, and they're easier to understand if we start with three-argument versions:

(def foldl3 (f base xs)
  (if (no xs)
      base
      (foldl3 f (f (car xs) base) (cdr xs))))

(def foldr3 (f base xs)
  (if (no xs)
      base
      (f (car xs) (foldr3 f base (cdr xs)))))

When we look at these versions it's clear that left fold works by growing the base case and then returning it when we get to the end of the list, and right fold works by growing a recursive call tree that builds its value on the way back up.

Here is a series of equivalent calls showing how a left fold plays out:

(foldl3 cons nil '(a b))
(foldl3 cons (cons 'a nil) '(b))
(foldl3 cons (cons 'b (cons 'a nil)) nil)

This yields (b a). The corresponding right fold,

(foldr3 cons nil '(a b))
(cons 'a (foldr3 cons nil '(b)))
(cons 'a (cons 'b (foldr3 cons nil nil)))

yields (a b).

For comparison, the reduce function we already have is a right fold where the base case is the last element of the list.

The next function, of, is for situations like the following:

(+ (car x) (car y) (car z))

With it you can write

((of + car) x y z)

And upon is a sort of reverse call, in the sense that it saves an argument, and then tells you what calling things on that argument will return:

> (map (upon '(a b c)) 
       (list car cadr cdr))
(a b (b c))

The next function, pairwise, returns true iff its first argument is true of every two-element window in the second. For example

(pairwise f '(a b c d))

is equivalent to

(and (f 'a 'b) (f 'b 'c) (f 'c 'd))

That expression

(all [id _ (car args)] (cdr args))

in the definition of = would have been

(pairwise id args)

if we'd had pairwise then.

The next function, fuse, takes a function that's expected to return a list, plus one or more lists, and returns the result of appending together the results of calling the function on successive elements of the lists. Which description incidentally demonstrates the advantage of source code over natural language in a spec.

> (fuse [list 'a _] '(1 2 3))
(a 1 a 2 a 3)

We use it in letu, which is for creating uvars. In eif we had to say

(with (v (uvar)
       w (uvar)
       c (uvar))
  ...)

With letu that becomes

(letu (v w c)
  ...)

You can also make one uvar by using a single variable instead of a list of variables.

We use letu in pcase, which is like a case statement but with predicates as the keys.

> (map [pcase _
         no   'empty
         atom 'atom
              'pair]
       '(a nil '(b c)))
(atom empty pair)

The next function, match, is like = except that functions occurring in the second argument are treated as predicates, and ts match everything.

> (match '(a (b) c d) (list 'a pair 'c t))
t

The split function breaks its second argument at the point where its first argument returns true.

> (split (is \a) "frantic")
("fr" "antic")

The next two macros are for conditionally evaluating blocks of code: when's body is evaluated when the test is true, and unless's when it's false.

Now we come to the code that implements numbers. Before we continue I'd like to remind the reader of the principle that when something is defined in the Bel source, the goal is to specify what it means and not to provide an efficient implementation.

Numbers in Bel take the form

(lit num (sign n d) (sign n d))

where the first (sign n d) is the real component and the second the imaginary component. A sign is either + or -, and n and d are unary integers (i.e. lists of t) representing a numerator and denominator.

So 2/3 is

(lit num (+ (t t) (t t t)) (+ () (t)))

and 4-1/2i is

(lit num (+ (t t t t) (t)) (- (t) (t t)))

You'll never see this representation unless you go looking for it, because Bel reads and writes numbers in the conventional way.

> (lit num (+ (t t) (t t t)) (+ () (t)))
2/3

We're going to build numbers up from the bottom, starting with operators for unary integers and finally defining the operators one actually uses in programs.

We start with a selection of constant unsigned integers. Then come a set of operators for them. Operators for unsigned integers have names beginning with i. Notice how with unary numbers, arithmetic operations turn out to be familiar list operations. E.g. + is append, and * is a fold of a fuse. One quirk: since these numbers are unsigned, i- has to return two values: the result and an indication of whether it's positive or negative.

The next level of numbers is unsigned rationals, which are (n d) pairs of unsigned integers. Functions for operating on them begin with r.

The next level up from that is signed rationals, which are (s n d), triples where s is + or - and (n d) is an unsigned rational. Operators on signed rationals begin with s.

The top level, the numbers that programs actually use, are complex numbers. These have the form shown above. Operators for complex numbers have names beginning with c.

Now that we've defined numbers, we get a series of functions for making them, recognizing them, and taking them apart.

The one nontrivial one is simplify, which simplifies a rational by dividing both components by their greatest common factor. This is called by buildnum after reading numbers and after every arithmetic operation.

After buildnum and recip we see the definitions of the +, -, *, and / functions that are actually used in programs.

> (+ .05 (/ 19 20)) 
1

Now that we have numbers we can define some common functions that use them, like len for finding the length of a list

> (len "foo")
3

and pos for finding the position of something in one

> (pos \a "ask")
1

(In Bel, lists are one-indexed.)

We use pos in charn, which returns a unique integer for each character based on its position in chars, a list of all the characters.

> (map charn "abc")
(97 98 99)

We can also define functions for comparing numbers, and more generally for comparing things that can be transformed into numbers or lists of them.

The comparison operators used in programs are the familiar < and >. These are defined in terms of bin<, which compares two objects by looking up a comparison function for them.

The comparison functions for different kinds of objects are kept in comfns, which is a list of pairs of functions (f . g) where f is a predicate (e.g. real) and g is a function of two arguments that returns true iff the first is less than the second.

Comparison functions are defined using com, and following its definition we see the four predefined comparison functions, for reals, chars, strings, and symbols. So < and > work for arguments of those types,

> (> 3/4 2/3)
t
> (< 'apple 'apply)
t

and if you use com to define a comparison function for other kinds of objects, < and > will work for them too.

Notice that bin< has an explicit test for nil arguments. That's because nil is both a symbol and a string (the empty string).

Then come a few more predicates on numbers which are mostly used in type checking — int, whole, and pint (positive integer).

Next comes a familiar name, yc. This is the Y combinator, which is used to generate recursive functions. It's used in rfn to make a recursive function with a name,

> ((rfn foo (x) (if (no x) 0 (inc:foo:cdr x))) '(a b c))
3

and rfn in turn is used to define afn, which lets you refer to a function within itself as self.

> ((afn (x) (if (no x) 0 (inc:self:cdr x))) '(a b c))
3

We use afn in wait, which takes a function and calls it till it returns a non-nil value.

> (set x '(nil nil a b c))
(nil nil a b c)
> (wait (fn () (pop x)))
a
> x
(b c)

(We haven't defined pop yet but it's the usual pop.)

The function runs takes a function and a list and breaks up the list into stretches for which the function returns true or false.

> (runs pint '(1 1 0 0 0 1 1 1 0))
((1 1) (0 0 0) (1 1 1) (0))

Using whitec, which returns true of whitespace characters, we can use runs to pick the words out of a string:

> (tokens "the age of the essay")
("the" "age" "of" "the" "essay")

But since tokens can take any function or object to treat as a break, you can use it for more than picking out words.

The function dups returns all the elements of a list that occur more than once in it.

> (dups "abracadabra")
"abr"

The next function, simple, is a predicate true of atoms and numbers. You need this for e.g. the base case of tree traversals.

The do1 macro is like do except that it returns the value of the first expression in its body rather than the last. We'll see an example soon when we get to the queue functions.

The consif function conses something onto the front of a list only if it's non-nil.

> (consif (cadr '(a)) '(x y))
(x y)

The check macro evaluates an expression and returns its value only if its second argument returns true of it.

> (check (car '(1 2 3)) odd)
1
> (check (car '(1 2 3)) even)
nil

The optional third argument is an expression to evaluate to get an alternate value in case the function returns false.

> (check (car '(1 2 3)) even 2)
2

The withs macro is like with except that the bindings of the preceding variables are visible in the expressions defining the values of later ones.

> (let x 'a
    (withs (x 'b
            y x)
      y))
b

The bind macro is like a call to dyn with a body. Since bind is a generalization of dyn, you would not ordinarily use dyn in programs.

The atomic macro uses bind to bind lock during the evaluation of its body. As we saw earlier in mev, the current thread won't be interrupted so long as lock is dynamically bound in it to a non-nil value. So if you have a series of expressions that you don't want interrupted because they'd leave something in an inconsistent state, you can protect them by wrapping an atomic around them.

The tail function returns the rest of its second argument from the point where its first argument returns true of it, if any.

> (tail [caris _ \-] "non-nil")
"-nil"

The function dock takes the last element off a list

> (dock '(a b c))
(a b)

while lastcdr returns the last non-nil cdr of a list

> (lastcdr '(a b c))
(c)

and last uses it to get the last element.

> (last '(a b c))
c

Now come three functions for manipulating queues. A queue is represented as a list within a list. That way several variables can be set to the same queue.

If you modify the middle of a list that is the value of several variables, the modification is shared:

> (set x '(a b c) y x)
(a b c)
> (set (cadr x) 'z)
z
> y
(a z c)

But there is no way to put something on the front of a list in a way that will be shared by multiple variables that were set to it. We haven't gotten to push yet, but I'll use it anyway to make this clear. When you push something on the front of a list, you're modifying the value of a variable, not the list structure itself.

> (push 'hello x)
(hello a z c)
> x
(hello a z c)
> y
(a z c)

To modify a value that several variables share, you have to be able to translate it into changing the car or cdr of some existing pair. And if the shared value is a list within a list, you can.

> (set x '((a)) y x)
((a))
> y
((a))
> (push 'hello (car x))
(hello a)
> y
((hello a))

That's why queues are represented as lists within lists.

You make a new queue with newq, put something in a queue with enq, and take something off with deq.

> (set x (newq))
(nil)
> (enq 'a x)
((a))
> (enq 'b x)
((a b))
> (deq x)
a
> x
((b))

Notice enq and deq use atomic. Otherwise you could get errors if code in another thread did something to a queue while you were in the middle of doing something to it.

Next we see the set macro itself. This calls hug to assemble the implicit pairs of arguments, and then for each pair (p e) generates an expression in which a where is wrapped around p, and then the appropriate half of the resulting pair is set to the value of e. So e.g.

(set (car x) 'a)

is expanded into the equivalent of

(atomic (let v 'a 
          (let (cell loc) (where (car x) t)
            ((case loc a xar d xdr) cell v))))

We also have a more general macro, zap, that modifies the value of something by applying a function to it.

> (let x '(a b c)
    (zap cdr x)
    x)
(b c)

It's instructive to compare the definitions of set and zap. They're much the same, except that zap has to wrap a call to apply around the current value of the appropriate half of the pair returned by where.

One subtle difference: the second argument to where in set is t, whereas in zap it's omitted (and thus defaults to nil). That's because setting an unbound variable should create a binding for it, but zapping one shouldn't.

With zap it becomes easy to write a whole class of other macros we need, like ++ and --, which increase and decrease the value of something

> (let x '(1 2 3)
    (++ (car x) 10)       
    (-- (cadr x))
    x)
(11 1 3)

and push and pull, which put something onto the front of a list and remove something from one

> (let x '(a b c)
    (push 'z x)
    (pull 'c x)
    x)
(z a b)

Since pull passes the optional comparison function to rem, we can say

> (let x '(7 3 0 9 2 4 1)
    (pull 4 x >=)
    x)
(3 0 2 1)

I think this sort of "porosity" is in general a good idea. There's a case to be made for treating functions as black boxes, but with macros you often want to acknowledge what a macro expands into and pass through its optional arguments if you can.

Now we have all the operators we need to write the Bel reader. This is like an inverted pyramid built upon the rdb primitive, which reads a single bit.

We want to be able both to read a character from a stream and also to look at the stream to see what character is waiting to be read. We simulate that with a global list of "unconsumed" characters, one for each open stream, kept as a list of (stream . char) pairs in cbuf. At first the only open input stream is the initial one, represented by nil, so cbuf starts out with one entry, (nil . nil), which is (nil).

After cbuf we see open and close, which call the ops and cls primitives respectively, but also create and delete cbuf entries for the streams involved.

Next comes peek, which tells you the next character waiting to be read from a stream. As well as streams, the Bel I/O functions take queues of characters (i.e. strings within lists), and that's what the first test in peek is checking for. If s is a queue, peek just returns the first element. Otherwise it begins by checking cbuf to see if it contains a character for this stream. If it does, peek returns it. Otherwise it calls bitc to try to read a new character.

The bitc function is where bits returned by rdb get turned into characters. It accumulates bits in bbuf, which is a list of (stream . bits) pairs. Once bits = the representation of some character in chars, bitc returns that character.

The rdb primitive is non-blocking, meaning if no bit is currently available from the stream passed to it, it returns nil instead of waiting for one. Since bitc does the same, returning nil immediately if it gets nil back from rdb, it's non-blocking too. But the wait expression in peek means it won't return till bitc gives it a character or eof. If peek gets an eof, it returns nil.

Next comes rdc, which is like peek but consumes the character it returns. I.e. if a source has characters waiting to be read, repeated calls to peek will return the same character, and repeated calls to rdc will return successive ones.

> (let s '("abc")
    (list (peek s) (peek s)))    
"aa"
> (let s '("abc")
    (list (rdc s) (rdc s)))
"ab"

The structure of rdc is similar to that of peek. First check if the argument is a stream. If it is, either return whatever's stored in cbuf (wiping the cbuf entry in the process) or call bitc.

Like peek, rdc waits till bitc gives it a character or eof, and returns nil in the latter case.

Then come some functions for recognizing types of characters. Whether a character is a digit depends on the base, which is why digit takes an optional base argument.

> (digit \a)
nil
> (digit \a i16)
t

The next function, breakc, returns true iff a character signals the end of a symbol or number. Among the characters treated as breakcs are those used as keys in syntax; we'll see soon which those are.

The signc function returns true iff its argument is a numeric sign, and intrac is for detecting characters that have a special meaning if they occur within symbols. I'll explain what they do when we get to that part of the reader.

The source function returns true iff its argument is something that can be read from, i.e. either nil (representing the initial input and output streams), an object of type stream, or a queue of characters.

Then comes read itself. All its arguments are optional: a source to read from, which defaults to ins, the default input stream; a base to read numbers in, which defaults to 10; and a value to return in case of eof, which defaults to nil.

In read we see the first parameters with type restrictions; the first argument has to be a source, and the second has to be between 2 and 16 inclusive. You can use type checking however you like, but I personally use it only to catch errors that won't be caught otherwise.

Then comes saferead, which is like read but returns an alternate value if there's an error or we get an eof from the stream.

Finally comes the actual reader, rdex, which is to reading what ev is to evaluation. There is one new parameter in rdex: share, which is a list of shared structure we've encountered so far.

Sometimes it matters when the same pair occurs multiple times in a tree. For example, when we used smark to mark special stack entries in the interpreter, it mattered that the cars of such entries were id to smark and not merely = to it. The Bel printer and reader use labels of the form #n, where n is whole number, to mark shared pairs. For example:

> (let x '(a) 
    (list x x))
(#1=(a) #1)
> (set x '(a #1=(b) #1 c))
(a #1=(b) #1 c)
> (id (2 x) (3 x))
t

The share parameter keeps track of shared objects we've read so far, and their labels. It's passed to most functions in the reader, and most return two values: whatever has been read, and the share list.

The first thing rdex does is call eatwhite to consume any whitespace before the object it's trying to read. There are two kinds of whitespace, corresponding to the two clauses in eatwhite: invisible characters like spaces and linefeeds, and comments, which begin with semicolons and continue till the end of the current line. In the latter case we call charstil to consume all the characters up to the next linefeed.

When it has finished reading whitespace, rdex can do one of three things depending on what rdc sees next. If rdc returns nil, that means the stream is out of characters, and we return whatever we've been told to return in case of eof. Otherwise the value returned by rdc is either a syntax character, like e.g. a left parenthesis or a double quote, in which case we have something special to do, or an ordinary character, in which case we call rdword, which reads a word (roughly a symbol or number).

The syntax characters are for rdex what special forms are for ev. Like forms, syntax is a list of (char . function) pairs that describe what to do if each character is encountered. There is a syn operator, akin to form, that defines the behavior of each character. The first syn, for example, defines what happens when the reader encounters a left parenthesis: it calls rdlist to read the elements, stopping when it encounters a right parenthesis.

If we skip down to rdlist, we see that it too begins with an eatwhite. Then there are several cases depending on what predicate is true of whatever's seen by peek. If there's no character, then we have a read error, because we at least need to see the list terminator (e.g. right parenthesis) before we're done. If it's a period, then we call rddot to handle that case. If it's the list terminator we were looking for, then we're done reading this list, which we've been accumulating in acc, and we can return it. Otherwise the character is the beginning of the next element of the list, so we call rdex to read it, and then call rdlist recursively with the new object snocced onto the end of acc.

Let's take a look at rddot, which is not simply for reading dotted lists, because we could also be seeing something (e.g. a decimal number) that begins with a period. Which it is depends on whether there's a breakc after the period. If there is, we call hard-rdex to read whatever object is in the cdr of the list. This function is like rdex but signals an error if it can't read anything.

If we look at the syn for a right parenthesis, on the other hand, all it does is call error. That's because a syn says what to do when you're starting to read something, and since rdlist always reads all the way to the matching right parenthesis, if you encounter a right parenthesis when you're starting to read something, what you're seeing must be an unbalanced parenthesis.

There's a similar pattern for \[ and \], except that we do something with the list we've read: we make it into a fn expression.

> (read '("[cons _ 'b]"))
(fn (_) (cons _ (quote b)))

The sym for \\ shows how characters are represented. A backslash can either be followed by the character itself, or the name of one. The names of characters like \bel that have them are kept in namecs.

Next come the syns for quote, backquote, and comma. They all call rdwrap, which does a hard-rdex, and then wraps the corresponding operator around it.

Then comes the syn for \", which calls rddelim to read a sequence of characters up to the next \". Within the sequence of characters, a backslash acts as an escape character, meaning whatever occurs next is treated as part of the sequence, even if it's the delimiter that would otherwise signal the end.

> "foo\"bar"
"foo\"bar"

The escape character is not part of the string, just something used in its representation.

> (mem \\ "foo\"bar")
nil

The character \¦ acts as a delimiter for symbol names that could not otherwise be read. It works just like \" except that we call sym on the result.

> '¦foo bar¦
¦foo bar¦

As we saw earlier, the character \# indicates shared list structure. If the #n occurs alone, it refers to a previously seen object; if it's followed by =, then it becomes the label for whatever is read next.

In the latter case we call rdtarget to read it. This function does some slightly odd things. It creates the pair (cell) to represent the object it will read before it's read, then when it does read something (e), it writes its car and cdr into the car and cdr of cell, and returns that. Why? Why not just return e? So that we can read lists that contain themselves. If we want to be able to read something like

#1=(a #1 b)

we need to add it to the list of shared objects before reading it. Or more precisely, add to the list of shared objects a pair that we will later turn into it.

Now we come to rdword, which reads either a number, a symbol, or several numbers or symbols joined by intrasymbol characters like \:.

Unlike many other parts of the reader, this code knows from the start which characters it's dealing with: everything up to the next breakc. It first tries to parse those characters as a number, by calling parsenum. If that fails, the next level of precedence is the vertical bar used in type specs. There is nothing specific to parameter lists about this bar, incidentally; it's just something the reader expands into a list beginning with t.

> 'for|2  
(t for 2)

If there's no vertical bar, we look for the intrasymbol characters \. and \!. These are expanded by the reader into common expressions.

a.b expands into (a b)

a!b expands into (a 'b)

So for example if you wanted to insist that a parameter was a continuation, instead of expressing the parameter as

(t c (isa 'cont))

you could just write

c|isa!cont

and our recent example

(id (2 x) (3 x))

could have been written

(id 2.x 3.x)

I haven't used this notation so far in the Bel spec, but it's quite convenient. Any combination of \. and \! is allowed.

> 'a!b.c
(a (quote b) c)

If there is nothing before the first \. or \!, the missing symbol is treated as an implicit upon.

> '!a
(upon (quote a))
> (let x '(a . b)
    (map .x (list car cdr)))
(a b)

The next level of precedence, represented by parsecom, is intrasymbol colons. These, as we've seen, are abbreviations for compose expressions.

> 'a:b:c
(compose a b c)

The next level of precedence is prepended tildes, which as we've also seen are abbreviations for no expressions. Here's some of each:

> 'x|~f:g!a
(t x ((compose (compose no f) g) (quote a)))

The lowest level of precedence is the else clause of parseno, where we try to parse a number, and failing that (since there can now be no intrasymbol characters in it), treat whatever we've got left as a symbol.

That's the end of the reader. Next comes the definition of the bquote macro. This is not part of the reader per se; the syns for \`` and `, merely yield bquote and comma expressions; but it feels like a part of the reader in the sense that you never use bquote or comma expressions directly.

The bquote macro is the biggest in the Bel source, and gives a taste of how macros, as they become more powerful, can become like compilers.

The general goal of backquote is to turn an expression containing backquotes, commas, and comma-ats into calls to the familiar list-building functions cons and append. To get an idea of what we're aiming at, here are some backquoted expressions followed by their expansions:

  `(x ,y)          (cons (quote x) (cons y nil))

  `(x ,@y)         (cons (quote x) (append y nil))

  `(,x ,@y)        (cons x (append y nil))

  `(,@x ,@y)       (append x (append y nil))

  `(x . ,@y)       (apply cons (quote x) y)

  `(,@x . ,@y)     (apply append x y)

These are not quite the expansions generated by bquote. I've cut some error-checking code to make them clearer.

Much of the complexity of bqex is due to the need to handle nested backquotes. We'll find it easier to understand bqex if we start with a version that doesn't:

(def bqex1 (e)
  (if (no e)   (list nil nil)
      (atom e) (list (list 'quote e) nil)
               (case (car e)
                 comma    (list (cadr e) t)
                 comma-at (list (list 'splice (cadr e)) t)
                          (bqexpair1 e))))

(def bqexpair1 (e)
  (with ((a achange) (bqex1 (car e))
         (d dchange) (bqex1 (cdr e)))
    (if (or achange dchange)
        (list (if (caris d 'splice)
                  (if (caris a 'splice)
                      `(apply append (spa ,(cadr a)) (spd ,(cadr d)))
                      `(apply cons ,a (spd ,(cadr d))))
                  (caris a 'splice)
                  `(append (spa ,(cadr a)) ,d)
                  `(cons ,a ,d))
              t)
        (list (list 'quote e) nil))))

Now it's easier to follow what will happen to an expression as it gets expanded.

The bqex1 function returns two values: an expansion, and a second value indicating whether anything changed in generating it. For example, if we expand an expression containing no commas or comma-ats, nothing need change.

> (bqex1 '(x y z))
((quote (x y z)) nil)

That call will go through the last clause of bqex1, and then, since the recursive calls to bqex1 on the car and cdr at the start of bqexpair1 will get nil values for both achange and dchange, we'll go through the last clause of bqexpair1 as well.

Now suppose we do have a comma or comma-at in our expression. The base cases of bqex1 are for when the whole of e is a comma or comma-at expression. When it's a comma expression, the expansion is simply its argument.

> (bqex1 '(comma x))
(x t)

But when it's a comma-at expression, the expansion is a call to splice:

> (bqex1 '(comma-at x))
((splice x) t)

What's splice? If we look at its definition, it simply signals an error. Why generate an expansion that signals an error? Because if the expression we're expanding is a naked comma-at, meaning one that's not within a list, we should signal an error; there's nothing to splice the value into.

> (let x '(a b c)
    `,@x)
Error: comma-at-outside-list

Now let's see what happens when we have comma and comma-at expressions within a list. In that case we call bqexpair1, which generates expansions for its car and cdr, and then puts them together to make an expansion for the whole list.

Suppose we're expanding

`(,x . ,@y)

The car and cdr of this list are the two cases we just examined. I.e. within bqexpair1

(a achange)

will be

(x t)

and

(d dchange)

will be

((splice y) t)

What happens when these get put together? Since the car of d is a splice expression and the car of a isn't, we go through this clause

`(apply cons ,a (spd ,(cadr d)))

yielding

(apply cons x (spd y))

Notice that the splice put on the front of its return value by bqex1 is taken back off when the return value gets back to bqexpair1. That's why expansions of comma-ats don't always signal errors; it's only a "leftover" splice that signals an error.

The call to spd is the error-checking code that I mentioned I cut from the examples above. As long as y is the right sort of value, meaning a list of one element, spd simply returns it. But it also signals an error if it's not.

> (let x '(b c)
    `(a . ,@x))
Error: splice-multiple-cdrs

You can't splice anything except a one-element list into the cdr of a pair. The case above is like writing (a . b c), which is ill-formed.

Here's an example of this expansion in action:

> (with (x 'a y '(b))
    `(,x . ,@y))
(a . b)

All the code that you see in the Bel source but not in bqex1 is for dealing with nested backquotes. The additional argument, n, is the nesting level, represented by an actual nested list. The function bqthru is for going through comma and comma-at operators to get at the ones within that need to be expanded, since the outermost backquote matches the innermost comma or comma-at. We increment the nesting level (by saying (list n)) each time we go through a bquote, and decrement it (by saying (car n)) each time we go through a comma or comma-at. Until the nesting level is nil, whereupon we expand the comma or comma-at as in the examples above.

> (bqex '(bquote (comma (comma x))) nil)
((list (quote bquote) (list (quote comma) x)) t)

Notice here for example we expand the innermost comma expression, but leave the outer one "intact," in the sense of turning it into a call to list that makes a new comma expression.

Like the splice macro, the comma and comma-at macros signal errors if they're ever called. In a well-formed backquote expression they never do get called, because they're expanded away. They only get called when there are "leftover" commas or comma-ats that don't have matching backquotes.

> (let x '(a b c)
       `,,x)
Error: comma-outside-backquote

Now we come to the printer. The print function takes an object and an optional stream and prints the object to the stream. There are two other optional parameters, names and hist, which programs are unlikely to supply explicitly; the first is a list of shared structure, which as we saw in read has to be displayed in a special way, and hist is a list of pairs printed so far.

There are four cases in print. If the thing we're printing is simple, meaning an atom or number, we call prsimple to print it. In prsimple there are four cases; two of them, chars and streams, are handled right there.

In the clause for chars we're down to printing individual characters with prc. This in turn uses wrb to write the bits in the character's binary representation (or simply enqueues the character, if printing to a queue).

Notice that prsimple doesn't print streams in a way that can be read back in, or even distinguished from one another. Streams have no readable representation.

Nearly all the complexity in prsymbol is for dealing with symbols that need to have \¦s around their names because otherwise they'd be unreadable. If it weren't for that possibility, prsymbol could be

(map [prc _ s] (nom x))

The way we check if a symbol needs to have \¦s around its name is by calling read on the characters in its name. If we don't get the same symbol back, we need to wrap it in \¦s. In the middle of which we call presc to print the characters in the symbol with backslashes before any \¦s.

To print a number we call prnum on its real and imaginary components. This in turn calls rrep to generate fractional representations of unsigned rationals. Bel can read numbers in decimal format, but internally they're rationals and are displayed that way.

> 1.5
3/2

Now back up to print, where the next clause is for printing strings. This is complicated by the fact that strings are lists and can thus share structure with other things we're printing. If ustring says that our string is a unique one, meaning one that doesn't share structure with anything in names, then we can simply print it as a series of characters between double quotes (using presc in case there is a double quote in the string).

> "foo"
"foo"

The next clause in print checks whether the thing we're printing is one of the shared objects in names. If it is, we have to display it using either #n=... if it's not in hist (meaning this is the first time we're printing it) or as #n if it is.

> (let x '(a b c)
    (list x x))
(#1=(a b c) #1)

To print a pair we call prpair. This prints parentheses around a call to prelts that prints the contents of the pair. In prelts we begin by calling print recursively on the car. Then we have to decide how to print the cdr. If it's simple, or a unique string, or shared structure, we display the list as a dotted list.

> (cons 'a 5)
(a . 5)
> (let x '(a b c)
    (cons x x))
(#1=(a b c) . #1)

Otherwise we print a space and call prelts recursively on rest.

> (append '(a b c) 5)
(a b c . 5)

Finally come a couple of functions for printing in specific situations. The first is prn, which is used to display data, e.g. for debugging. It takes any number of arguments and prints them separated by spaces, followed by a newline.

> (with (x "foo" y 'bar)
    (prn 'x x 'y y))
x "foo" y bar 
bar

It returns the value of the last, so you can wrap a call to prn around any expression in your code without changing what it returns.

The second, pr, is for displaying messages to humans. If you're looking at data, you want to print strings in double quotes, but if you're printing a message to a user, you probably don't. E.g.

(let user 'Dave 
  (pr "I'm sorry, " user ". I'm afraid I can't do that."))

will print

I'm sorry, Dave. I'm afraid I can't do that.

It calls prnice to print its arguments in a readable form.

The remaining definitions in the Bel source aren't needed to write the interpreter or read or print, but are useful in programs.

The drop function takes n elements off the front of a list

> (drop 2 '(a b c d e))
(c d e)

and nth returns the nth element of one.

> (nth 2 '(a b c d e))
b

As I mentioned earlier, lists in Bel are 1-indexed.

We use nth in the virtual function for numbers, which I also included earlier.

> (2 '(a b c))
b

We see this in use in nchar, which is the converse of charn. It converts a number to a character.

> (nchar 65)  
\A

The first function is the complement of drop. It returns a list of the first n elements of a list.

> (first 2 '(a b c d e))
(a b)

The catch macro is used to establish a continuation to which we can throw control if we want to abort a computation. It dynamically binds throw to the continuation, so whatever argument we give to throw will be returned as the value of the catch expression.

> (catch 
    (throw 'a)
    (/ 1 0))
a

The cut function returns the elements of a list from its second argument to its third inclusive,

> (cut "foobar" 2 4)
"oob"

unless the second argument is negative, in which case it indicates how many elements to take off the end of the list.

> (cut "foobar" 2 -1)
"ooba"

The whenlet macro is to when as iflet is to if. It's used in awhen, which is to when as aif is to if.

The each macro causes its body to be evaluated with a variable bound to successive elements of a list.

> (let x nil
       (each y '(a b c)
         (push y x))
       x)
(c b a)

Now come several functions on functions. The first, flip, takes a function and returns a function that calls it with the parameters reversed.

> ((flip -) 1 10)
9

The next, part, is for partial application. It takes a function and several arguments, and returns a function that will call it with those arguments plus whatever additional ones are supplied.

> ((part cons 'a) 'b)
(a . b)

As its name suggests, trap is a backwards part; it puts the newer arguments first.

> ((trap cons 'a) 'b)
(b . a)

Finally, only takes a function and returns a function that calls it only if its first argument is non-nil. So instead of

(let x (f)
  (if x (g x)))

or

(aif (f) (g it))

you can say just

(only.g (f))

So for example find, which we defined

(def find (f xs)
  (aif (some f xs) (car it)))

could with only and composition be defined

(set find only.car:some)

Incidentally, these examples show the sort of situation where intrasymbol dot notation is useful. You wouldn't want to use it for every expression in a program, but it's readable when used with a "modifier" like only.

These are followed by some functions involving numbers, including >= and <=, floor, which returns the largest integer <= its argument, and ceil, which returns the smallest integer >= its argument.

> (map (upon 3.5) (list floor ceil))
(3 4)

The mod function returns its first argument modulo its second,

> (mod 17 3)
2

Then come a group of macros for iteration. The first, whilet, evaluates its body while a test expression returns true, with a variable bound to its value.

> (let x '(a b c)
    (whilet y (pop x)
      (pr y))
    x)
abcnil

Then comes the general loop macro, which sets a variable to an initial value, then updates the value on successive iterations, so long as some test expression is true.

> (loop x 1 (+ x 1) (< x 5) 
    (pr x))
1234nil

Several other iteration macros can then be defined in terms of loop, starting with while

> (let x '(a b c)
    (while (pop x)
      (pr x)))
(b c)(c)nilnil

The til macro evaluates its body with a variable bound to the value of one expression till another expression returns true.

> (let x '(a b c d e)  
    (til y (pop x) (= y 'c)
      (pr y))
    x)
ab(d e)

While it might seem as if you could define whilet simply as

(mac whilet (var expr . body)
  `(til ,var ,expr (no ,var) ,@body))

this would fail if var were a pair.

The for macro starts a variable at some initial value and then increments it by 1 on each succeeding pass through the loop, till it exceeds some threshold.

> (for x 1 10 
    (pr x))
12345678910nil

The repeat macro simply evaluates its body a certain number of times.

> (repeat 3 
    (pr 'bang))
bangbangbangnil

And the poll macro evaluates an expression till a function is true of the result, at which point it's returned.

> (let x '(a b c d e)
    (poll (pop x) is!c)
    x)
(d e)

The accum macro takes a variable and a body of code and evaluates the body with the variable lexically bound to a function that accumulates all the values it's called on. It returns the list of values.

> (accum a
    (map (cand odd a) '(1 2 3 4 5)))
(1 3 5)

It's used in nof, which takes a number and an expression and returns the result of evaluating the expression that number of times.

> (nof 10 (rand 10))
(9 7 6 2 9 1 7 0 0 0)

(Sequences of random numbers never look random enough.)

The drain function is a combination of poll and accum. It evaluates some expression till it returns nil, or a value passing some other optional test, and returns a list of all the values the expression returned.

> (let x '(a b c d e)
    (drain (pop x)))
(a b c d e)
> (let x '(a b c d e)
    (drain (pop x) is!d))
(a b c)

The ^w function returns a number raised to a whole power.

> (^w 2+3i 3)
-46+9i

The randlen function returns a random number that can be represented in n binary digits, which is the same as saying a random integer between 0 and 2^n-1 inclusive. It works by generating such a digit string and calling read on it. Within randlen we see the first use of the coin primitive, which randomly returns t or nil.

The clog2 function returns the ceiling of the logarithm base 2 of its argument. It and randlen are used to build the general rand function, which takes a positive integer n and returns a random integer between 0 and n-1 inclusive.

Next come a group of macros for assignment, starting with wipe, which sets multiple things to nil.

> (let x '(a b c d e)
    (wipe 2.x 4.x)
    x)
(a nil c nil e)

Then we get the familiar pop macro, which takes the first element off a list and returns it.

> (let x '(a b c)  
    (list (pop x) x))
(a (b c))

Like any macro that uses where for assignment, pop can operate on any pair that you can find a way to refer to.

> (let x '(a b c)
    (pop (cdr x))
    x)
(a c)

The clean macro removes everything from a list for which its first argument returns true:

> (let x '(1 2 3 4 5)
    (clean odd x)
    x)
(2 4)

And swap rotates the values of its arguments

> (let (x y z) '(a b c)
    (swap x y z)
    (list x y z))
(b c a)

as a degenerate case of which, if there are two arguments, it swaps their values.

> (let x '(a b c d e)
    (swap 2.x 4.x) 
    x)
(a d c b e)

The adjoin function conses something onto a list only if it's not already an element of it.

> (adjoin 'a '(a b c))
(a b c)
> (adjoin 'z '(a b c))
(z a b c)

It's used in pushnew, which pushes an element on a list if it's not already an element.

> (let x '(a b c d e)
    (pushnew 'a x)
    (pushnew 'z x)
    x)
(z a b c d e)

The dedup function returns a version of list without the later instances of duplicate elements.

> (dedup "abracadabra")
"abrcd"

Next come a group of functions involving sorting. The first inserts an element into a (presumably sorted) list according to a comparison function f.

> (insert < 3 '(1 2 4 5))
(1 2 3 4 5)

Then we get sort itself, which uses insert to sort a list.

> (sort < '(5 1 3 2 4))
(1 2 3 4 5)

As much as possible of the original order is preserved.

> (sort (of > len) '((a b) (c) (d e) (f)))
((a b) (d e) (c) (f))

The best function takes a function and a list and returns the element of the list that beats the others according to the function.

> (best > '(5 1 3 2 4))
5

In case of ties it will return the first.

> (best (of > len) '((a) (b c) (d e) (f)))
(b c)

It's used by max to return the largest of its arguments

> (max 3 7 2 1)
7

and by min to return the smallest.

> (min 3 7 2 1)
1

Sometimes you want to use max and min on individual arguments and sometimes on a list. If we define them for the former case we can get the latter with apply.

The even function returns true of even numbers, and odd of odd ones.

> (map upon.3 (list even odd))
(nil t)

And round rounds its argument to the nearest integer, choosing even integers in case of ties.

> (map round '(-2.5 -1.5 -1.4 1.4 1.5 2.5))
(-2 -2 -1 1 2 2)

Next come a group of functions for operating on files. The first is a sort of let for files; it opens one, lexically binds the resulting stream to a variable within the body, then uses an after to make sure the stream gets closed. If we evaluate

(withfile s "foo" 'out
  (print 'hello s)
  (prc \  s)
  (print 'filesystem s))

The file "foo" will contain

hello filesystem

It's used in from and to, which dynamically bind ins and outs (the default input and output streams) to the newly opened file. So if we say

(to "foo" 
  (map prn '(a b c)))

then "foo" will end up containing

a
b
c

and thus

> (from "foo"  
    (drain (read)))
(a b c)

The function readall uses the same technique to read all the objects in a file, except it uses a unique pair to signal eof so that it can return nil as well.

> (from "foo"
    (readall))
(a b c)

The load function reads all the objects in a file and also evaluates them. This is how you load a file of code.

> (to "example.bel"    
    (print '(def foo (x) (cons 'a x))))
nil
> (load "example.bel")
nil
> (foo 'b)
(a . b)

The record macro is used for making a transcript. It binds outs to a newly created queue, then at the end returns the characters it contains.

> (record
    (pr 'what)
    (pr \ )
    (pr "he said"))
"what he said"

The function prs uses it to print its arguments to a string.

> (prs 'what \ "he said")
"what he said"

Then come functions for operating on arrays. Bel arrays are recursively defined in the sense that an n dimensional array is a list of n-1 dimensional arrays.

We can get a new array by giving array a list of dimensions and an optional default value.

> (set a (array '(2 3) 0))
(lit arr (lit arr 0 0 0) (lit arr 0 0 0))

Now a is a 2x3 array of zeros.

The vir for arrs means we can use arrays as if they were functions on lists of indices, as implemented by aref. Vectors are one-indexed.

> (a 1 1)
0

If we supply fewer indices than the array has dimensions, we get an array back instead of a scalar.

> (a 1)
(lit arr 0 0 0)

Like any reference to part of a pair, array references are settable.

> (++ (a 1 1) 5)
5
> a
(lit arr (lit arr 5 0 0) (lit arr 0 0 0))

Including references to subarrays:

> (swap (a 1) (a 2))
(lit arr 5 0 0)
> a
(lit arr (lit arr 0 0 0) (lit arr 5 0 0))

Next come a set of functions for operating on tables, which are key-value stores.

We make a new one by giving table a list of (key . value) pairs.

> (set k (table '((a . b) (c . d))))
(lit tab (a . b) (c . d))

The vir for tabs means we can use tables as virtual functions on keys.

> (k 'a)
b
> (k 'z)
nil
> (map k '(a c))
(b d)

Because we define a loc whose test is isa!tab and which expands into a tabloc expression, we can set table entries and also create new ones implicitly.

> (set k!a 1 k!z 2)
2
> k
(lit tab (z . 2) (a . 1) (c . d))

Finally, tabrem removes all entries with certain keys from a table.

> (tabrem k 'z)
((a . 1) (c . d))
> k
(lit tab (a . 1) (c . d))

The last code in the Bel source is for defining objects with named fields. First we define templates describing these objects, which are stored in a global list. The templates can then be used to define instances.

We call tem with the name of the template followed by pairs of field names and expressions to generate default values for those fields. E.g. this defines a two-dimensional point:

(tem point x 0 y 0)

Although we used 0s here, you can use any code in a default expression. It will be stored in a closure and called each time a default value is needed.

Having defined point, we can make new instances with make

> (set p (make point))
(lit tab (x . 0) (y . 0))

We can supply initial arguments if we want, and if we do they override the defaults.

> (set q (make point x 1 y 5))
(lit tab (x . 1) (y . 5))

Notice that nothing in a point says that it is a point. You can easily change that by adding a field called e.g. type, but for maximum flexibility the language doesn't do it for you.

Since instances are tables, we can do to them everything we can do to tables.

> p!x
0
> (++ p!x)
1
> (swap p!x p!y)
1
> p
(lit tab (x . 0) (y . 1))

We can even add and remove fields, which is either powerful or alarming depending on how you feel about such things.

We start to see the potential of intrasymbol characters and upon in functions like this one

(set above (of > !y))

which tells if points are above another in the sense of having greater y-coordinates.

> (above q p (make point))
t

Finally, the function readas reads a table as an instance of a template. The fields that we read are treated as if they were initial arguments to make, which means if fields have been added to a template since what we're reading was written, it will automatically get the new fields with the default values. In my experience that's a convenient feature to have.

Thanks to Kartik Agaram, Trevor Blackwell, Patrick Collison, Daniel Franke, Joel Franusic, Jared Friedman, Daniel Gackle, Michael Hartl, Matt Knox, Shriram Krishnamurthi, Kevin Lacker, Jessica Livingston, Bill Moorier, Olin Shivers, Nick Sivo, and especially Robert Morris for help with Bel.