ESOTERIC programming languages

In the now less likely case you have problems downloading files from my site, please e-mail me so that I can take measures.

This page features:

BFM - Macros for Brainf*ck, with an interpreter in Python
a Brainf*ck interpreter in Thue
a Thue interpreter in Python
notes on Pandora, a new unfinished language
Links

BFM - Macros for Brainf*ck, with an interpreter in Python

Brainf*ck (a.k.a. Brainfunct) is a small Turing-complete language with only eight instructions:

    +  -  <  >  [  ]  .  ,

These instructions are quite elementary, e.g. + is "increment content of current data cell" and > is "go to next data cell".

(Sorry I don't have the time to write down a decent introduction to Brainf*ck here; Frans Faase's pages are a very good place to start.)

With such elementary operations writing "interesting" programs becomes quickly difficult. Macros could ease the task. In his pages Frans Faase defines a macro syntax, but does not seem to have published any macro expander or interpreter. (Does he expand them by hand ? I doubt it.)

Anyway, I devised my own macro system, with a Brainf*ck+Macros ("BFM" for short) interpreter in Python.

Differences between the two systems include (to the best of my knowledge):

BFM has higher order macros; FF has none.
FF admits ordinary numbers as arguments (for use e.g. as absolute memory positions). BFM admits only Brainf*ck code or BFM macros as macro arguments. However, in BFM you can define so-called Church numbers: particular macros that play the role of ordinary numbers.
Less importantly, [ and ] instructions must be balanced in the body of each BFM macro; FF has no such requirement. (This requirement should be removed from BFM in the future).
Syntax is quite similar with slight differences.

Download BFM:

Download BFM here.

The package contains a BFM interpreter in Python and some lackish documentation about BFM. It requires the language Python, which is freely available (here) on most platforms, including Windows and Linux and BeOS and others. (If you have installed RedHat you probably already have installed Python even if you don't know about it - ask Ben !)

Quick introduction to BFM macros and higher-order macros:

(If the pace of this introduction goes too fast - please tell me ! What follows is essentially the content of file bfm_why.txt provided with the archive.)

In Brainf*ck, to add the two numbers "on top of stack" you would do something like this:

    [ - < + > ] <

This is nicely put into a macro add:

    & add = [ - < + > ] < ;  # macro definition

    add                     # macro invocation

But what if the numbers to add are separated by a longer distance ? you'll define for instance:

    & add2 = [ - < < + > > ] < < ;

    & add3 = [ - < < < + > > > ] < < < ;

now, you'd like to use the distance as parameter of your macro. The first idea is to provide as parameters the sequences "go left" <<< and "go right" >>>:

    & add_n ( go_left | go_right ) = [ - go_left + go_right ] go_left ;

so now, instead of add3:

    [ - < < < + > > > ] < < <

you can write

    add_n ( < < < | > > > )

(the vertical bar is the argument separator) but this has two drawbacks: first you have to put all these < and > in your call (even if that is already a big improvement, in cases more complicated than add); second, there are two parameters to represent your morally unique parameter 'distance': this is not clean, and is error-prone.

It would be nice if you could pass the distance itself to the macro:

    add_N(3)

No problem ! Imagine 3 is a macro that triples its argument:

    &3(x) = x x x;

then you can write:

    & add_N ( distance ) = [ - distance(<) + distance(>) ] distance(<) ;

where distance is now a macro parameter that you call in add_N's code.

By the way, you can define local macros, so the code of add_N can be made a bit clearer (?) as follows:

    & add_N ( distance ) =

        & go_left = distance(<);

        & go_right = distance(>);

        [ - go_left + go_right ] go_left

    ;

Of course the gain for add_N is weak, but imagine what you could do in bigger examples.

Even further: macros also return other macros, and this opens you the whole field of lambda calculus. The macro layer is actually lambda-calculus in disguise. See also the b5 macro system created by Panu Kalliokoski; it expands the ideas in BFM and more into a general-purpose Turing-complete macro system.

a Brainf*ck interpreter in Thue

You can view it as text or download as a zip archive which also contains my Thue interpreter written in Python, described in next section. It was written for the first Essies Awards in category 3 (best language implementation in an esoteric language). I'm afraid that it was their only entry in that category :-(

The Thue language, devised by John Colagioia (according to ideas of Thue ?), works by string rewriting according to rules given by the programmer.

A Thue program, in my experience, consists (at runtime) in a world where some rules govern propagation and interaction of messages. The messages have no absolute signification, you give them "meaning" and you device rules so that the messages act as specified by their intended "meaning". Part of the art is to prevent unwanted interactions, and to organize synchronization of messages that must be synchronized. I found it fun to write Thue programs.

For more information on Thue look at Cat's Eye.

a Thue interpreter in Python

Here is it (remove the .txt extension if you download it).

This interpreter has no arbitrary limitations, so it is suitable to (relatively) big programs like my Brainf*ck interpreter above. On the other hand it is not optimised for speed (who wants speed should not write Thue programs, anyway, let alone run Brainf*ck programs within Thue on top of Python.)

Should work with Python 1.5.1, Python 2 and above (and perhaps below too).

Pandora

Pandora is one of my two entries to the Essies in the "new esoteric language" category. Its design was not complete and, actually, I still do not understand how it should work. Hence I will not currently ship its current implementation (80K of OCaml code !) because it is to undergo deep rework, unless it simply dies.

As a primor here is a "Hello world" program:

   hello world

   forget

   come from "hello" print "Hello, " return

   come from "world" print "world !" return

Pandora was inspired from INTERCAL. The problem I wanted to address with INTERCAL is that "come from" can only steal the execution thread from labelled points (this makes the "come from" call sites too obvious). I wondered what would happen if we could "come from" any piece of code, designated by a pattern. When the pattern matches the code, the relevant "come from" piece of code is executed as a subprogram.

After some thinking, I got the idea that all Pandora code would be executed as a result of "come from" pattern matching. A "come from" subprogram could return Pandora code at the point of call for further pattern matching. This effectively makes Pandora a token stream rewriting language.

So the "hello world" example works like this: the execution starts at [hello] and executes the code after [come from "hello"]; that code prints "Hello, " and returns an empty stream to the caller. That return result is appended before the sequel of the program, [world forget come from .......]. So [come from "world"] is then executed. When [forget] is met, the program ends, by having its current (and only) thread killed. (Since "forget" actually means "forget about executing the current thread" ;-)

Of course if Pandora was only that, it would be easy to define... But I wanted more. I wanted it to embed parsing of expressions with operators of different priorities (more generally constructs of different priorities); eagerness vs laziness of pattern argument evaluation could be controlled by the programmer; simultaneous matches would yield concurrent threads (à la Threaded-INTERCAL); there would be variables and environments.

I could not find a good design for the whole thing. Priorities, specially, are a nightmare.