Little Languages

I finished rereading The AWK Programming Language today and have been keeping myself entertained working some of the exercises, specifically a toy assembler and interpreter.

Relevance

I first purchased the book based entirely on the recommendation of Brandon Rhodes in a comment on Stack Overflow:

... the real reason to learn awk is to have an excuse to read the superb book The AWK Programming Language by its authors Aho, Kernighan, and Weinberger. You would think, from the name, that it simply teaches you awk. Actually, that is just the beginning. Launching into the vast array of problems that can be tackled once one is using a concise scripting language that makes string manipulation easy — and awk was one of the first — it proceeds to teach the reader how to implement a database, a parser, an interpreter, and (if memory serves me) a compiler for a small project-specific computer language! If only they had also programmed an example operating system using awk, the book would have been a fairly complete survey introduction to computer science!

I was excited at the thought of such a concise study of computer science in so short a book and it really has lived up to my expectations. I have been thinking about it again recently as a result of my interest in getting back to basics. Getting started with assembly using something like x86 is difficult due to its sheer size and scope. Doing any research online reveals plenty of people claiming no one writes x86 directly and it is best left to compilers - not a good place to position an entry-level exercise. What I really want is a more human instruction set, aimed at teaching more than doing. Which is, incidentally, exactly what I found in The AWK Programming Language.

The Assembler and Interpreter

The "instruction set" given is almost painfully limited, but dead simple to get started with:

With the exception of the references and use of DEBUG, the following is excerpted from the book directly:

# -*- awk -*-
# asm - assembler and interpreter for simple computer
#   usage: awk -v DEBUG=1 -f asm program-file data-files

BEGIN {
    srcfile = ARGV[1]
    ARGV[1] = ""  # remaining files are data
    tempfile = "asm.temp"
    n = split("const get put ld st add sub jpos jz j halt", x)
    for (i = 1; i <= n; i++)   # create table of op codes
        op[x[i]] = i-1

# ASSEMBLER PASS 1
    FS = "[ \t]+"
    while (getline <srcfile > 0) {
        sub(/#.*/, "")         # strip comments
        symtab[$1] = nextmem   # remember label location
        if ($2 != "") {        # save op, addr if present
            print $2 "\t" $3 >tempfile
            nextmem++
        }
    }
    close(tempfile)
    print ""

# ASSEMBLER PASS 2
    nextmem = 0
    while (getline <tempfile > 0) {
        if ($2 !~ /^[0-9]*$/)  # if symbolic addr,
            $2 = symtab[$2]    # replace by numeric value
        mem[nextmem++] = 1000 * op[$1] + $2  # pack into word
    }

# INTERPRETER
    for (pc = 0; pc >= 0; ) {
        addr = mem[pc] % 1000
        code = int(mem[pc++] / 1000)

        if(DEBUG) {
            split("const get put ld st add sub jpos jz j halt", x)
            printf "code: %-5s acc: %-5s addr: %-10s\n", x[code+1], acc, addr
        }

        if      (code == op["get"])  { getline acc }

        else if (code == op["put"])  {
            if(DEBUG)
                printf "OUTPUT: %10s\n", acc
            else
                print acc
        }

        else if (code == op["st"])   { mem[addr] = acc }
        else if (code == op["ld"])   { acc  = mem[addr] }
        else if (code == op["add"])  { acc += mem[addr] }
        else if (code == op["sub"])  { acc -= mem[addr] }
        else if (code == op["jpos"]) { if (acc >  0) pc = addr }
        else if (code == op["jz"])   { if (acc == 0) pc = addr }
        else if (code == op["j"])    { pc = addr }
        else if (code == op["halt"]) { pc = -1 }
        else                         { pc = -1 }
    }
}

Caveats

Anyone with even a modicum of experience with assembly is probably scratching their head at the lack of a stack or registers but it's like I said, painfully limited. I suppose there's nothing to prevent declaring variables named register1, because while there is nothing in the instruction set to directly support it, look-up times should be constant!

A Worked Example

I was a little stumped as to how best to practice with such a limited set of instructions but ultimately settled on the following program which accepts user input as a limit for which to calculate Fibonacci numbers.

# take as input a limit N and compute N fibonnacci numbers

        get             # read upper bound into acc.
        
        add   decrement # increment by 1 to avoid early termination
        st    limit     # in the >0 check

loop    ld    limit
        sub   decrement
        jz    done
                        # else haven't reached limit
        st    limit

        ld    last
        add   current
        st    sum

        ld    current   # this swap/dance feels like a glaring 
        st    last      # limitation of the instruction set!

        ld    sum
        st    current

        j     loop

done    ld    sum
        put             # print sum
        halt

counter    const 0
decrement  const 1

last       const 0
current    const 1
sum        const

limit      const

Curiosities

Almost immediately some limitations of the "architecture" become obvious the, the single "register" (closest word I can think of for the accumulator) requires an annoying amount of swapping across variables, rather than something like indirect references.

$ awk -v DEBUG=1 -f asm fib.asm <<<"5"

code: get   acc:       addr: 0
code: add   acc: 5     addr: 19
code: st    acc: 6     addr: 23
code: ld    acc: 6     addr: 23
code: sub   acc: 6     addr: 19
code: jz    acc: 5     addr: 15
code: st    acc: 5     addr: 23
code: ld    acc: 5     addr: 20
code: add   acc: 0     addr: 21
code: st    acc: 1     addr: 22
code: ld    acc: 1     addr: 21
code: st    acc: 1     addr: 20
code: ld    acc: 1     addr: 22
code: st    acc: 1     addr: 21
code: j     acc: 1     addr: 3
code: ld    acc: 1     addr: 23
code: sub   acc: 5     addr: 19
code: jz    acc: 4     addr: 15
code: st    acc: 4     addr: 23
code: ld    acc: 4     addr: 20
code: add   acc: 1     addr: 21
code: st    acc: 2     addr: 22
code: ld    acc: 2     addr: 21
code: st    acc: 1     addr: 20
code: ld    acc: 1     addr: 22
code: st    acc: 2     addr: 21
code: j     acc: 2     addr: 3
code: ld    acc: 2     addr: 23
code: sub   acc: 4     addr: 19
code: jz    acc: 3     addr: 15
code: st    acc: 3     addr: 23
code: ld    acc: 3     addr: 20
code: add   acc: 1     addr: 21
code: st    acc: 3     addr: 22
code: ld    acc: 3     addr: 21
code: st    acc: 2     addr: 20
code: ld    acc: 2     addr: 22
code: st    acc: 3     addr: 21
code: j     acc: 3     addr: 3
code: ld    acc: 3     addr: 23
code: sub   acc: 3     addr: 19
code: jz    acc: 2     addr: 15
code: st    acc: 2     addr: 23
code: ld    acc: 2     addr: 20
code: add   acc: 2     addr: 21
code: st    acc: 5     addr: 22
code: ld    acc: 5     addr: 21
code: st    acc: 3     addr: 20
code: ld    acc: 3     addr: 22
code: st    acc: 5     addr: 21
code: j     acc: 5     addr: 3
code: ld    acc: 5     addr: 23
code: sub   acc: 2     addr: 19
code: jz    acc: 1     addr: 15
code: st    acc: 1     addr: 23
code: ld    acc: 1     addr: 20
code: add   acc: 3     addr: 21
code: st    acc: 8     addr: 22
code: ld    acc: 8     addr: 21
code: st    acc: 5     addr: 20
code: ld    acc: 5     addr: 22
code: st    acc: 8     addr: 21
code: j     acc: 8     addr: 3
code: ld    acc: 8     addr: 23
code: sub   acc: 1     addr: 19
code: jz    acc: 0     addr: 15
code: ld    acc: 0     addr: 22
code: put   acc: 8     addr: 0
OUTPUT:          8
code: halt  acc: 8     addr: 0

What a mouthful! This disassembly is almost delightfully uncomplicated, which is not to say bug-free - I've managed to write an infinite loop at least twice in one evening. I must admit some surprise at how quickly the program actually runs (never mind the fact that it runs at all). For fun, I attempted a comparison against a similarly-coded solution in Python and tried reading the output of dis.dis:

def fib(n):
    a = 0; b = 1; i = 0;
    while i < n:
        a, b = b, a+b
        i += 1
    return b

if __name__ == '__main__':
    print(dis.dis(f))

With the following results:

  8           0 LOAD_CONST               1 (0)
              3 STORE_FAST               1 (a)
              6 LOAD_CONST               2 (1)
              9 STORE_FAST               2 (b)
             12 LOAD_CONST               1 (0)
             15 STORE_FAST               3 (i)

  9          18 SETUP_LOOP              43 (to 64)
        >>   21 LOAD_FAST                3 (i)
             24 LOAD_FAST                0 (n)
             27 COMPARE_OP               0 (<)
             30 POP_JUMP_IF_FALSE       63

 10          33 LOAD_FAST                2 (b)
             36 LOAD_FAST                1 (a)
             39 LOAD_FAST                2 (b)
             42 BINARY_ADD
             43 ROT_TWO
             44 STORE_FAST               1 (a)
             47 STORE_FAST               2 (b)

 11          50 LOAD_FAST                0 (n)
             53 LOAD_CONST               2 (1)
             56 INPLACE_SUBTRACT
             57 STORE_FAST               0 (n)
             60 JUMP_ABSOLUTE           21
        >>   63 POP_BLOCK

 12     >>   64 LOAD_FAST                2 (b)
             67 RETURN_VALUE

Which begins to reveal the decisions that drove the design of the Python virtual machine. Binary ADD - that's probably nice to have, my stringly-typed VM sure doesn't have anything like that (directly, the machinations of AWK are mostly¹ beyond the scope of this post).

1. But if you're interested...