# brainF*** interperter in lua

For a personal project I may need to load and execute something that will basically be a very simple programming language. Though I am not at all close to this part of the project yet and I can most likely use something that already exist (just embedding lua is probably an option) it got me interested to write a simple interpreter for a simple language just to get a very basic feel for it.

As a result I decided against translating the brainf*** into lua as that would feel boring and like cheating and instead decided to create an table containing instructions based upon the brainf*** that then gets looped over and executed.

Though I believe I at least did the very obvious optimization on the brainf*** code I am curious if I missed some obvious ones. I am however not specifically looking for optimizations of the interpreter itself they are welcomed.

The first important file is compiler.lua. This is used to turn the raw code into the table that then can gets executed

    local comp= {}
comp.indexesOfStartingLoops = {}
comp.compiled = {}
function comp:insertIntoCompiled(char,amount)
--amount is not always set, in that case it is safe to assume that it is 0
amount = amount or 0
-- the loop characters need special tables, lets filter those out
if char ~= "[" and char ~= "]" then
--make sure that the amount is higher then 0, then insert the correct table
if amount >0 then
table.insert(self.compiled,{char=char,count=amount})
end
else
--we need to compile a loop
if char=="[" then
--insert the table representing the start of a loop.
--at this point in time we do not know to what index it will be linked to
--we then put the key of this loop in this table enabling us to more easily find to what start an end piece of a loop belongs to
table.insert(self.indexesOfStartingLoops,#self.compiled)
--now lets compile the end of a loop
elseif char=="]" then
--the last value of this table is the place of the nearest opening of a not linked loop
--we need this as that is what the closed part will be linked to
local matching = self.indexesOfStartingLoops[#self.indexesOfStartingLoops]
--now lets insert it
--now that it is inserted we can update the starting of the loop so that it is properly linked to the end
--we now have processed the start as well thus we can remove it from the list of start's that need to be processed
table.remove(self.indexesOfStartingLoops,#self.indexesOfStartingLoops)

end
end
end
function comp:compile(str)
print("compiling:")
print(str)
--all the characters that need to be compiled.
local chars = {[">"]=true,["<"]=true,["+"]=true,["-"]=true,["."]=true,[","]=true,["["]=true,["]"]=true}
--these 2 are used to be able to compress multiple of the same instructions into 1
local lastChar  =""
local lastCount =0
--loop over the string
for c in str:gmatch"." do
--look if the current character is a character that needs to be compiled
if chars[c] then
--check if the character can be compressed
if lastChar == c then
lastCount = lastCount+1
else
--they are not the same, thus lets insert the last character
self:insertIntoCompiled(lastChar,lastCount)
--because the loop characters can't be compressed we are not even going to try that
if c~="[" and c~="]" then
--mark the lastChar to the current character so that it can be compressed
lastChar  = c
lastCount = 1
else
--we are dealing with loop characters, remove the lastChar as there is no compression possible and insert the current character directly
self:insertIntoCompiled(c)
lastCount=0
lastChar=""
end
end
end
end
--after the loop ends the last character is still waiting to be inserted as the loop marked it to compress it
self:insertIntoCompiled(lastChar,lastCount)
print("compiled to:")
--nicely print the compiled version
--we use a table to hold it before we print it as that is faster
local niceCompiledTable = {}
--loop over the compiled version
for key,value in ipairs(self.compiled) do
--we can't print compressed instructions directly
if type(value)=="table" then
--the instruction is part of a loop, lets nicely print that
if value.char=="[" or value.char=="]" then
else
--it is an compressed instruction, lets nicely print that
end
end
--insert the nicely formatted instruction
end
--now we actually print it all
print(table.concat(niceCompiledTable,""))
return self.compiled
end
return comp


As an example, running comp:compile() on the following brainf***

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


will create a table something like like

{
{char="+",count=3},
{char=">",count=1},
{char="+",count=3},
{char="<",count=1},
{char="-",count=1}
{char=">",count=1},
{char=".",count=1}
}


This table then gets used by inter.lua which runs it.

local inter = {}
--the memory for the brainf program
inter.memory = require("memory")
--this will hold the program
inter.program={}
--hodls at what instruction the interperter is currently at
inter.at = 1
--this moves the instruction pointer by 1 to dir
function inter:moveChar(dir)
dir = dir or "right"
if dir =="right" then
self.at=self.at+1
elseif dir=="left" then
self.at=inter.at-1
end
if self.at <= 0 then
return false
elseif self.at > #self.program then
return false
end
return true
end
--this is just here to nicely get the current instruction
function inter:getCurChar()
return self.program[inter.at]
end
--this is the old method to "jump" to diffrent parts of the loop
function inter:jumpToMatch(searchFor)
searchFor = searchFor or "["
local foundOtherSymbol = 0
repeat
local hasJumped = false
if searchFor=="]" then
self:moveChar()
elseif searchFor=="[" then
self:moveChar("left")
else
error("Not a valid jump char")
end
--check if found
local char = self:getCurChar()
if char == searchFor and foundOtherSymbol ==0 then
hasJumped =true
elseif searchFor =="[" and char=="]" then
foundOtherSymbol = foundOtherSymbol+1
elseif searchFor=="]" and char=="[" then
foundOtherSymbol=foundOtherSymbol+1
else

end
until(hasJumped)
end
--this checks if the programneeds to make a jump and does so if needed
function inter:checkJump(stayAtChar,data)
stayAtChar = stayAtChar or false
local num= inter.memory:getValueRaw()
if stayAtChar then
if num ~=0 then
end
else
if num ==0 then
end
end
end
--this loads the program and runs it
function inter:run(prog)
self.program = prog
local commands = {
[">"]=function(inter,data) inter.memory:shift("right",data.count) end,
["<"]=function(inter,data) inter.memory:shift("left",data.count) end,
["."]=function(inter,data) inter.memory:print(data.count); end,
[","]=function(inter,data) inter.memory:getInput(data.count) end,
["["]=function(inter,data) inter:checkJump(false,data) end,
["]"]=function(inter,data) inter:checkJump(true,data) end
}
print("running")
repeat
local reachedEnd=false
local curCommand = self:getCurChar()
commands[curCommand.char](self,curCommand)
if not self:moveChar() then
reachedEnd = true
end
until(reachedEnd)
print("\nDone")
local mem = self.memory:getAllMemory()
for key,value in ipairs(mem) do
io.write("["..key.."]=>"..value.." ")
end
io.write("\n")
end
return inter


It uses memory.lua to manipulate the memory of the running program

local memory = {}
--the memory of the brainf program
memory.stored= {}
--what part of the memory the program can currently access
memory.at= 1
--this changes the part of the memory the program can access
function memory:shift(direction,amount)
amount = amount or 1
if direction=="left" then
end
if self.at +addToAt <= 0 then
error("pointer went too low")
end
end
--this function is used to get the value of the memory piece the program currenty has access to
function memory:getValueRaw()
return self.stored[self.at] or 0
end
self.stored[self.at] = self:getValueRaw()+amount
end
--prints the current piece of memory x times, by default x =1
function memory:print(times)
times = times or 1
for i=1,times do
io.write(string.char(self:getValueRaw()))
end
end
--gets 1 char of input x times, by default x=1
function memory:getInput(times)
times = times or 1
for i=1,times do
repeat
local valid = false
if #input ==1 then
memory.stored[memory.at] = string.byte(input)
valid=true
end
until(valid)
end
end
function memory:getAllMemory()
return self.stored
end
return memory


The output of the example brainf*** will be

compiling:
+++[>+++<-]>.
compiled to:
running

Done
[1]=>0 [2]=>9


Is there some (obvious) improvement to the generated data that I can make? I do realize that there are no checks for incorrect syntax errors as of yet like not having an even amount of "[" and "]" characters but I am not really that worried about that specifically as of right now.

I also realize that trying to print a value that is higher then string.char() accepts causes the program to crash. I am not sure if I should simulate overflows, cause a crash the moment you want to exceed this number or keep is similar to how it is now but make it a nicer error.

The whole project can be found here https://github.com/lenscas/brainf for those that are interested

• Have you measured performance improvements against a bare interpreter with no optimizations? I once tried to do something very similar in Python, only to find that the resulting code is horribly inefficient (in fact slower than any other version I had at hand). If you're interested, you can compare performance with this version. As a benchmark, you can use the Mandelbrot set plotter. – kyrill Mar 31 '17 at 20:28
• @kyrill the first version (not available on github) just removed the comments and put each character in a table as that is easier to loop over. It takes several minutes for that version to even start printing when it tries to run ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++. while the current version is pretty much instant. I haven't tried with just making the loop faster though. – lenscas Mar 31 '17 at 20:36
• Have you tried running FizzBuzz on this? – Simon Forsberg Mar 31 '17 at 21:51
• @SimonForsberg Seems to be working without a problem... if very bad performance is not a problem. – kyrill Mar 31 '17 at 22:16
• Actually it needs preprocessing on higher level than your interpreter does. See this post about different possible optimizations of BF code. – kyrill Apr 1 '17 at 9:25