Last time we took a look at the basics of how Brainfuck works and how we can perform some basic operations with it. This time we’ll continue to expand on that and look at how we can use Lua as a “macro language” to make it easier to write Brainfuck code.

So, let’s just dive into using Lua to generate Brainfuck code and then we’ll use that to do some more complex stuff with Brainfuck.

We’ll start by creating some Lua functions that will help us write Brainfuck code:

local buffer = {}

local function emit(s)
    if s then table.insert(buffer, s) end
end

local function emitln(s)
    emit(s)
    emit("\n")
end

local function emitn(s, n)
    assert(type(s) == "string")
    if not n then n = 1 end
    for i = 1, n do table.insert(buffer, s) end
end

local function inc(n)   emitn("+", n) end
local function dec(n)   emitn("-", n) end
local function left(n)  emitn("<", n) end
local function right(n) emitn(">", n) end
local function read()   emit(",")     end
local function write()  emit(".")     end
local function open()   emit("[")     end
local function close()  emit("]")     end
local function clear()  emit("[-]")   end

This is a good start.

In Brainfuck, memory is not random-access; one can not simply go to an arbitrary memory address unless one knows where the data pointer is already at. Basically, if you know what the data pointer is, you can set it to anything you want. Once you lose track of the data pointer, you can’t set it to any arbitrary value. This is why unbalanced loops can be risky to use; they can lead to losing the data pointer. Therefore, if you use them, you should know what you’re doing so that you know where the data pointer will end at after the loop.

However, if you always know where the data pointer is, you can move it around memory arbitrarily. Therefore, we can extend our Lua code to keep track of where the data pointer is to allow moving it to arbitrary memory addresses.

local pointer = 0

local function left(n)
    if not n then n = 1 end
    emitn("<", n)
    pointer = pointer - n
end

local function right(n)
    if not n then n = 1 end
    emitn(">", n)
    pointer = pointer + n
end

local function to(addr)
    if addr == pointer then return end

    local dist = math.abs(addr - pointer)

    if addr < pointer then
    	left(dist)
    else
    	right(dist)
    end

    pointer = addr
end

So, for example:

to(2)
to(1)
to(3)

print(table.concat(buffer))

This prints >><>>.

Note: if an unbalanced loop is used, pointer will likely become invalid, and thus, the to function won’t work properly. We could extend our code to warn the user when this happens and allow the user to correct the problem. We can even allow unbalanced loops but mark the pointer as invalid, and then warn the user if they try to use it without re-validating it. But I won’t bother showing this.

Next, we’ll create a way to manage memory. Basically, a memory allocator to use while generating our Brainfuck code. It will keep track of which cells are in use and which ones aren’t.

local cells = {}
local cellsInUse = 0
local maxCells = 30000

local function alloc()
    if cellsInUse < maxCells then
        for i = 0, maxCells - 1 do
            local j = i + 1
            if not cells[j] then
                cells[j] = true
                return i
            end
        end

        error("should not be here")
    else
        error("out of memory")
    end
end

local function free(addr)
    if addr < 0 or addr >= maxCells then error("out of bounds: " .. addr) end

    local j = addr + 1
    if not cells[j] then error("cell already free: " .. addr) end
    cells[j] = false
end

This is about the simplest possible solution; certainly not a great one. I’ll leave improving it to the reader. Either way though, it will serve our purposes. We can use it to allocate cells to use in our Brainfuck code and then free them when we’re done using them.

So, let’s take a look at how we can use this:

local function copy(src, dst)
    local tmp = alloc()

    to(src)
    open()
        to(dst)
        inc()
        to(tmp)
        inc()
        to(src)
        dec()
    close()

    to(tmp)
    open()
        to(src)
        inc()
        to(tmp)
        dec()
    close()

    free(tmp)
end

local a, b = alloc(), alloc()

to(a)
inc(5)

copy(a, b)

print(table.concat(buffer))

This example prints +++++[>+>+<<-]>>[<<+>>-]. I’ll leave it as an exercise for the reader to see if it actually works.

Now that we have this, let’s take a look at how we can do some more basic operations.

First, say we want to create an “if/then” “macro”:

local function if_then(cond, t)
    to(cond)
    open()
        t()
        to(cond)
        clear()
    close()
end

Notice that the cond cell gets stomped on by this function. Say we wanted to create a version that preserves the condition:

local function if_then(cond, t)
    local tmp = alloc()

    copy(cond, tmp)

    to(cond)
    open()
        t()
        to(cond)
        clear()
    close()

    copy(tmp, cond)

    free(tmp)
end

So, to use it you pass the address of the condition cell and a function which generates the code for the body of the if statement. Like this:

local a, b = alloc(), alloc()

to(a)
inc()

if_then(a, function()
    to(b)
    inc(4)
end)

print(table.concat(buffer))

Another interesting thing to notice is that when we allocate and free temporary cells, we aren’t necessarily clearing them. This means that when you allocate a cell, you can’t necessarily assume its value.

As we’ve seen, there are many details to consider when writing Brainfuck like this. Should functions take their result cells in as arguments or return them? Should functions preserve their input cells or are they allowed to stomp them? Should cells be cleared when allocated or freed, or should you just assume that a cell could have any value when allocated? There’s a lot to consider when trying to come up with a coding style to use for this, and, obviously, I don’t have all the answers. I haven’t figured this all out yet.

One thing I am considering doing is switching the language I use from Lua to Urn (a really nice Lisp implementation in Lua).

Aaaaand, with that, I’m going to cut this article short. I’ll leave you with a link to FrainBuck, my project on GitHub where I have all this code and more. In the next article, we might tackle arrays. We shall see.

That’s all for now.