5
\$\begingroup\$

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
        --lets start with the begining of one
        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
            table.insert(self.compiled,{char = char,link=0})
            --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
            table.insert(self.compiled,{char=char,link=matching})
            --now that it is inserted we can update the starting of the loop so that it is properly linked to the end
            self.compiled[matching]["link"]  = #self.compiled
            --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
        local addToTable = value
        if type(value)=="table" then
            --the instruction is part of a loop, lets nicely print that
            if value.char=="[" or value.char=="]" then
                addToTable="{char="..value.char.."link="..value.link.."}"
            else
                --it is an compressed instruction, lets nicely print that
                addToTable="{char="..value.char..",count="..value.count.."}"
            end
        end
        --insert the nicely formatted instruction
        table.insert(niceCompiledTable,addToTable)
    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="[",link=7},
    {char=">",count=1},
    {char="+",count=3},
    {char="<",count=1},
    {char="-",count=1}
    {char="]",link=2},
    {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
            self.at=data.link
        end
    else
        if num ==0 then
            self.at= data.link
        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:add(data.count)end,
        ["-"]=function(inter,data) inter.memory:add(data.count*-1) 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
    local addToAt = 1*amount
    if direction=="left" then
        addToAt = -1*amount
    end
    if self.at +addToAt <= 0 then
        error("pointer went too low")
    end
    self.at = self.at+addToAt 
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
--add to the memory piece the programm has currently access to. Can be used to subtract instead by using negative numbers
function memory:add(amount)
    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
            local input = io.read()
            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:
{char=+,count=3}{char=[link=7}{char=>,count=1}{char=+,count=3}{char=<,count=1}{char=-,count=1}{char=]link=2}{char=>,count=1}{char=.,count=1}
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

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – kyrill Mar 31 '17 at 20:28
  • \$\begingroup\$ @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. \$\endgroup\$ – lenscas Mar 31 '17 at 20:36
  • \$\begingroup\$ Have you tried running FizzBuzz on this? \$\endgroup\$ – Simon Forsberg Mar 31 '17 at 21:51
  • \$\begingroup\$ @SimonForsberg Seems to be working without a problem... if very bad performance is not a problem. \$\endgroup\$ – kyrill Mar 31 '17 at 22:16
  • 1
    \$\begingroup\$ Actually it needs preprocessing on higher level than your interpreter does. See this post about different possible optimizations of BF code. \$\endgroup\$ – kyrill Apr 1 '17 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.