writing

The BLAST programming language

BLAST is an extension of LAST that adds one crucial extra instruction:

• Bind which accepts a name and two expressions. The first expression is bound to the name. That expression can then be referenced in the second expression using that name.

Bind provides a convenient way for defining variables.

Recall the syntax of LAST:

Term = "L" Term / "A" Term Term / "S" Term / "T"

In BLAST, this is extended to:

Term = "B" Name Term Term / "L" Name Term / "A" Term Term / "S" Name Term / "T"

Where Name is an identifier. For now let’s say we only allow lowercase ASCII alphanumeric characters and single spaces (BLAST then allows multiword identifiers with spaces!).

A Names can be empty and we can get by without ever using Bind – in that case BLAST behaves exactly like LAST – all valid LAST programs are also valid BLAST programs and have the same meaning. In other words, BLAST is a superset of LAST.

However using Names is very convenient and makes our programs much easier to handle by humans.

In fact, we will make the programs even easier to handle for humans, by using symbols instead of letters for the instructions, like so:

• B -> :
• L -> /
• A -> @
• S -> <
• T -> >

Now we’re ready to write an example program.

Example program

The following BLAST program defines a few numbers, encoded with Zermelo-Lynn numerals, defines the add and fib functions, and then calculates the 7th Fibonacci number:

:nil //>
:succ /n /f /x @<f><n>
:pred /n @@<n> /nt <nt> <n>
:one @<succ><nil>
:two @<succ><one>
:three @<succ><two>
:four @<succ><three>
:five @<succ><four>
:six @<succ><five>
:seven @<succ><six>
:add /n /m 
  @@<n> /nt
      @@<m> /mt
          @<succ> @@<add> m<mt> n<n>
        <n>
    <m>
:fib /n
  @@<n> /nt
      @@<nt> /nnt
          @@<add> @<fib><nt> @<fib><nnt>
        <n>
    <n>
@<fib><seven>

Unshadowing

A unique property of BLAST is that it allows “unshadowing” of variables, e.g.:

:a //>
:a //<>
@<a><a<a>

This program calls the second a with the first a as an argument.

This unshadowing will work to arbitrary depth.