How do you do "foo" in Bertrand

[wm]

People often ask me questions about how to do something in Bertrand.
For example, in the thread "Some beginner's questions" Nat asked me
how to represent the empty list in Bertrand. I was reading this
again, and it got me thinking.

Nat's question is entirely reasonable, but questions like this are
difficult to answer for Bertrand. And this is a feature!

There are basically two answers to questions like these: one for the
underlying Bertrand system, and one for a language built on top of
Bertrand, and there are problems with both answers. Bertrand isn't so
much of a language itself (even though it is a Turing complete
language) it is a system for implementing other languages (typically
constraint languages). So to (not) answer Nat's question, the
underlying Bertrand system does not have a representation for the
empty list. Furthermore, Bertrand has no idea of what a list is (empty
or not). In fact, Bertrand itself pretty much has no semantics at all,
so it has little idea of anything. Even numbers are (theoretically)
unknown in Bertrand, although in this case we cheat and implement
things like addition, even though (again theoretically) addition
*should* be implemented as (millions of) rules like 1 + 1 { 2 }

The second answer is for a language built on top of Bertrand. And
indeed, the standard libraries (bops and beep) do define languages
that understand things like true, false, and conditionals, arithmetic
(including equation solving) and stuff like that. You then use
Bertrand (along with the standard libraries) to define further
languages, such as a language for solving electrical circuits.
Likewise, you could define a library that has list functions, and make
them look however you like. You can even add operators (including
outfix operators), so you can pick whatever syntax you want for
defining lists. So the answer to the question about how you represent
the empty list in Bertrand is "however you want" or "however the
library you are using represents it".

I know this feels completely weird, but it is not so different from
questions in normal languages like "how do you represent a tree
structure" (or a queue, or whatever). Most languages do not have tree
structures built into the language. They might have a library (or
multiple libraries) that implement tree structures, and you might pick
the best one for your particular application.

The point is that Bertrand has pushed this flexibility all the way
down to its lowest level (on purpose) so that there basically is no
semantics in Bertrand. Even things like true and false are just
symbols (syntax) that have no meaning, until you supply rules that
"give" them meaning. You can even think of the rules as having no
meaning at all, and everything is just symbolic manipulation, although
this makes things even more confusing. After all Bertrand Russell
wrote a whole book trying to give meaning to the expression 1 + 1, but
failed.

The reason this was done in Bertrand was because constraint languages,
by their nature, are domain specific. I wanted a very flexible system
that could be used to create domain-specific constraint languages. Up
until Bertrand, every constraint system was very domain specific. For
example, Sketchpad only knew about lines and about relationships like
perpendicular. Sketchpad knew nothing about arithmetic, so you could
not define constraints like "make that line an inch longer than this
line" unless you could create a geometric construction using
Sketchpad's existing (fixed) constraints. Even worse, Sketchpad cannot
be extended by the user to express new constraints.

In the book "Constraint programming languages" I take a number of
examples from other constraint languages, and implement them in
Bertrand -- first by creating a new constraint language (using rules)
that mimics the other constraint language, and then implementing the
example program in the new language. This is very easy to do in
Bertrand. But none of those constraint languages had a notion of a
list, so I never implemented it (although there are some examples,
such as the factorial examples, that use lists, but I never gave them
any fixed syntax; I just made it up as necessary).

The only actual semantics in Bertrand are the rules. Rules can be used
recursively, so we have a semantics for recursion (although the
semantics of recursion are very simple). Because rules do matching,
we can also implement conditionals. So there are the two big things we
need to make a computer language: conditionals (what if-then-else
statements do in normal languages) and loops (implemented using
recursion). Bertrand adds two things to this: types, which are used as
guards on rules (but again, the semantics of these types in extremely
simple) and single-assignment binding of free variables. The latter is
the most complicated semantics in Bertrand, although compared to most
languages it is very simple. In the book, the formal semantics of
Bertrand is written in a fairly short appendix -- for most languages,
it would require an entire book (if you could do it at all). The fact
that you can write a complete formal semantics for Bertrand is not
because of any elegance of the language, it is because Bertrand has
almost no semantics at all (although I personally consider the lack of
any semantics beautiful, and perhaps even elegant).

But we programmers are used to computer languages that have big and
complicated semantics, so we find it confusing when something is so
simple. We want our languages to know about complicated things like
floating point arithmetic (I remember when the first formal semantics
was written for an implementation of floating point arithmetic -- it
was for the transputer -- it was a very big deal, and took lots and
lots of work). We want our languages to know what addition means, and
true and false. But in reality, computers only know how to manipulate
symbols, in the form of sequences of bits. Computers don't really know
what addition means, any more than they know what a poem represented
by a string of ASCII characters means. (Incidentally, I never got
around to defining any rules for strings in Bertrand)