February 1, 2011 at 15:16

Writing a Brainfuck interpreter in Lua

Lua Logo
Each programmer in his life manages to learn many languages, specializes in several of them and continues to work for a long time, while the rest pass by. For different reasons. Is it worth it to spend time learning new languages ​​when you have already decided on the area in which you will work? Personally, I am sure what it costs, although perhaps many will say that fundamental knowledge in computer science is important, and in which language it is not critical to write code. In essence, it is. Nevertheless, learning languages ​​is interesting and useful.

Lua. A brief history of the language.

The language Lua ([lua], port. "Moon") originates in the relatively distant 1993. It was created by Roberto Jerusalem (Roberto Ierusalimschy), Luiz Henrique de Figueiredo and Waldemar Celes, then members of the Tecgraf team for computer graphics technology at the Pontifical Catholic University of Rio de Janeiro (Pontifical Catholic University of Rio de Janeiro) in Brazil. This is a scripting language that combines the properties of imperative and functional languages ​​and has object-oriented properties. Influenced by Scheme, SNOBOL, JavaScript, C / C ++ and others. The result is an embeddable, easily extensible scripting language with simple syntax.
Over the years, Lua has gained popularity precisely as an embedded language: many programs, but even more games use it. For example Vim (since version 7.3), World of Warcraft, Ragnarok Online and many others

A little bit about language

It is best written here www.lua.ru/doc (rus) and here www.lua.org/manual/5.1 (eng)

Install Lua

You can download Lua here luabinaries.sourceforge.net/download.html
Under Linux (although there are already three versions in the Ubuntu 10.04 repository)
sudo apt-get install lua5.1
sudo apt-get install lua50
sudo apt-get install lua40


Or build from source (the name of the lua5.1 package was not at all obvious, so I had to build it)
cd /tmp
wget http://www.lua.org/ftp/lua-5.1.4.tar.gz
tar -xf lua-5.1.4.tar.gz
cd lua-5.1.4
sudo apt-get install build-essential libreadline5-dev
make linux test
sudo checkinstall --fstrans=no --install=no --pkgname=lua --pkgversion "5.1.4" --default
sudo dpkg -i lua_5.1.4-1_i386.deb
lua -v
>>> Lua 5.1.4  Copyright (C) 1994-2008 Lua.org, PUC-Rio


Great, now you can start having fun.

Hello World!

Where to start learning a language? With Hello world! not interested. Let's write an interpreter. There is such a wonderful Brainfuck language, very simple and very interesting. Helps stretch the brain.

We set the task:
  • Reading brainfuck code from a file
  • Basic code validation
  • Brainfuck code execution


Description of Brainfuck

In the “classic” Brainfuck, described by Urban Muller, the cell size is one byte, the number of cells is 30,000, the input / output is byte-by-byte, the number of instructions is 8 pieces. Below is a brief description:

  • " > " go to next cell
  • " < " go to previous cell
  • " + " increase the value in the current cell by 1
  • " - " decrease the value in the current cell by 1
  • " . " print the value from the current cell
  • " , " enter the value from the outside and save in the current cell
  • " [ " if the value of the current cell is zero, go forward in the program text to the cell following the corresponding " ] " (including nesting)
  • " ] " if the value of the current cell is not zero, go back through the program text to the symbol " [ " (taking into account nesting)


We write

Let's start small: create a directory for work, the brainfuck.lua file in it, make it executable

#!/usr/bin/env lua
-- Lua Brainfuck Interpreter
Brainfuck =
{
    -- validate source
    -- Return 1 if closing bracket(s) missing.
    -- Return 2 if opening bracket(s) missing.
    -- Return 0 otherwise.
    validate = function (self, source)
        return 0
    end,
    -- debug function
    showError = function (self, errorCode)
    end,
    -- brainfuck function
    brainfuck = function (self, source)
    end,
}


We will also create the hello.b file (the code for brainfuck. Displays Hello World! On the screen. Needed for tests)
++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.

Well, now everything is ready.

1. Reading brainfuck code from a file.

Let our interpreter execute the code from the file whose name is given on the command line. The
./brainfuck.lua hello.b
documentation will tell us that Lua puts the parameters into the arg array.

-- start here
if arg[1] then
    -- read source from file in arg[1]
    source = io.input(arg[1]):read("*a")
    -- get error code (0 == no error)
    errorCode = Brainfuck:validate(source)
    -- if no error run source else show error
    if errorCode == 0 then
        Brainfuck:brainfuck(source)
    else
        Brainfuck:showError(errorCode)
    end
else
    print("Usage: ./brainfuck.lua script")
    Brainfuck:showError(3)
end


2. Basic code validation


-- validate source
-- Return 1 if closing bracket(s) missing.
-- Return 2 if opening bracket(s) missing.
-- Return 0 otherwise.
validate = function (self, source)
    local i, errorCode, l = 0, 0, 0
    for i = 1, string.len(source), 1 do
        -- [ 91
        if string.byte(source, i) == 91 then
            l = l + 1
            -- ] 93
        elseif string.byte(source, i) == 93 then
            l = l - 1
            if l < 0 then return 2 end
        end
    end
    if l > 0 then
        return 1
    elseif l < 0 then
        return 2
    else
        return 0
    end
end,
-- debug function
showError = function (self, errorCode)
    if errorCode == 1 then
        print("Error: Closing bracket(s) missing.")
    elseif errorCode == 2 then
        print("Error: Opening bracket(s) missing.")
    elseif errorCode == 3 then
        print("Error: No source file.")
    else
        print("Error: Unknown error code.")
    end
end,


3. Execution of Brainfuck Code


-- brainfuck function
brainfuck = function (self, source)
-- memSize: Brainfuck memory size (30k)
-- maxVal: Max memory value (255) byte
-- mem: Memory table (array)
-- pointer: default 0
-- l: default 0. braket level counter
    local memSize, maxVal, mem, pointer, l = 30000, 255, {}, 0, 0
    -- clear memory
    for i = 0, memSize, 1 do mem[i] = 0 end
    -- execute program
    i = 0
    while i <= string.len(source) do
        i = i + 1
        -- + 43 C eqv ++(*p);
        if string.byte(source, i) == 43 then
            if mem[pointer] < maxVal then
                mem[pointer] = mem[pointer] + 1
            end
            -- - 45 C eqv --(*p);
        elseif string.byte(source, i) == 45 then
            if mem[pointer] > 0 then
                mem[pointer] = mem[pointer] - 1
            end
            -- , 44 C eqv *p = getchar();
        elseif string.byte(source, i) == 44 then
            mem[pointer] = string.byte(io.stdin:read('*l'), 1)
            -- . 46 C eqv putchar(*p);
        elseif string.byte(source, i) == 46 then
            io.write(string.char(mem[pointer]))
            -- < 60 C eqv --p;
        elseif string.byte(source, i) == 60 then
            pointer = pointer - 1
            if pointer < 0 then pointer = 0 end
            -- > 62 C eqv ++p;
        elseif string.byte(source, i) == 62 then
            pointer = pointer + 1
            if pointer > memSize then pointer = memSize end
            -- [ 91 C eqv while (*p) {
        elseif string.byte(source, i) == 91 then
            if mem[pointer] == 0 then
                while (string.byte(source, i) ~= 93) or (l > 0) do
                    i = i + 1
                    if string.byte(source, i) == 91 then l = l + 1 end
                    if string.byte(source, i) == 93 then l = l - 1 end
                end
            end
            -- ] 93 C eqv }
        elseif string.byte(source, i) == 93 then
            if mem[pointer] ~= 0 then
                while (string.byte(source, i) ~= 91) or (l > 0) do
                    i = i - 1
                    if string.byte(source, i) == 91 then l = l - 1 end
                    if string.byte(source, i) == 93 then l = l + 1 end
                end
            end
        else
            -- print("Unknown symbol")
            -- return
        end
        -- print("Debug: l="..l.." cmd="..string.char(string.byte(source, i)))
    end
end,


Ready version

Done. Now you can run the example and make sure that everything works. As you can see, Lua is quite suitable for standalone use)

I apologize for the lack of indentation. Lost with highlighting.
I did not find a blog about Lua, so I will post it in Abnormal programming.
If articles about Lua are interesting to the community, I can write more

Useful literature

Tags:

Also popular now: