Пишем интерпретатор Brainfuck на Lua

Lua Logo
Каждый программист за свою жизнь успевает изучить множество языков, в нескольких из них специализируется и продолжает работать продолжительное время, а остальные проходят мимо. По разным причинам. Стоит ли тратить время на изучение новых языков, когда уже определился с областью в которой будешь работать? Лично я уверен что стоит, хотя, быть может, многие скажут что важны фундаментальные знания в computer science, а на каком языке писать код не критично. В сущности так и есть. И тем не менее изучать языки интересно и полезно.

Lua. Краткая история языка.

Своё начало язык Lua ([луа], порт. «луна») берёт в относительно далёком 1993 году. Его создали Роберто Иерусалимши (Roberto Ierusalimschy), Луис Энрике де Фигуэйредо (Luiz Henrique de Figueiredo) и Вальдемар Селес (Waldemar Celes), в то время члены группы разработки технологии компьютерной графики (Tecgraf) Епископального католического университета Рио-де-Жанейро (Pontifical Catholic University of Rio de Janeiro) в Бразилии. Это скриптовый язык, сочетающий свойства императивных и функциональных языков и обладающий объектно-ориентированными свойствами. Испытал влияние Scheme, SNOBOL, JavaScript, C/C++ и других. В результате получился встраиваемый, легко расширяемый скриптовый язык с простым синтаксисом.
За годы существования Lua обрёл популярность именно как встраиваемый язык: множество программ, но ещё больше игр используют его. Например Vim (с версии 7.3), World of Warcraft, Ragnarok Online и многие другие

Немного о языке

Лучше всего написано тут www.lua.ru/doc (rus) и тут www.lua.org/manual/5.1 (eng)

Устанавливаем Lua

Скачать Lua можно тут luabinaries.sourceforge.net/download.html
Под Linux (правда в репозитории Ubuntu 10.04 есть аж три версии)
sudo apt-get install lua5.1
sudo apt-get install lua50
sudo apt-get install lua40


Либо собрать из исходников (название пакета lua5.1 было совсем не очевидно, поэтому пришлось собрать)
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


Замечательно, теперь можно начинать развлекаться.

Hello World!

С чего начать изучение языка? С Hello world! не интересно. Давайте напишем интерпретатор. Есть такой замечательный язык Brainfuck, очень простой и очень интересный. Помогает размять мозг.

Ставим задачу:
  • Чтение brainfuck кода из файла
  • Базовая валидация кода
  • Исполнение Brainfuck кода


Описание Brainfuck

В «классическом» Brainfuck, описанном Урбаном Мюллером, размер ячейки — один байт, количество ячеек 30 000, ввод/вывод происходит побайтово, количество инструкций 8 шт. ниже краткое описание:

  • ">" перейти к следующей ячейке
  • "<" перейти к предыдущей ячейке
  • "+" увеличить значение в текущей ячейке на 1
  • "-" уменьшить значение в текущей ячейке на 1
  • "." напечатать значение из текущей ячейки
  • "," ввести извне значение и сохранить в текущей ячейке
  • "[" если значение текущей ячейки нуль, перейти вперёд по тексту программы на ячейку, следующую за соответствующей "]" (с учётом вложенности)
  • "]" если значение текущей ячейки не нуль, перейти назад по тексту программы на символ "[" (с учётом вложенности)


Пишем

Начнём с малого: создадим каталог для работы, файл brainfuck.lua в нём, сделаем его исполняемым

#!/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,
}


Также создадим файл hello.b (код на brainfuck. выводит Hello World! на экран. нужен для тестов)
++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.

Ну, теперь всё готово.

1. Чтение brainfuck кода из файла.

Пусть наш интерпретатор выполняет код из файла имя которого передано в командной строке
./brainfuck.lua hello.b
Документация скажет нам что Lua помещает параметры в массив arg

-- 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. Базовая валидация кода


-- 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. Исполнение Brainfuck кода


-- 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,


Готовая версия

Готово. Теперь можно запустить пример и убедиться что всё работает. Как видите Lua вполне пригоден для standalone использования)

Прошу прощения за отсутствие отступов. Утеряны при подстветке.
Блога о Lua не нашел, поэтому размещу в Ненормальное программирование.
Если статьи о Lua интересны сообществу могу написать ещё

Полезная литература

Поделиться публикацией
Похожие публикации
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 15
  • +1
    Лет 5-6 назад писал на LUA скрипты для PtokaX (сервер для пиринговых сетей) — было довольно-таки занимательно. Даже прибыльно, ввиду тогдашнего бума на хабы и отсутствие разнообразия скриптов, которыми и заманивали к себе пользователей их держатели. Особенно популярны были игрушки, вроде викторины и виселицы.

    Спасибо, вспомнил былые времена, а заодно и ознакомился с изменениями, которые претерпел язык за последние несколько лет.
    • +1
      >> Помогает размять мозг.
      Скорее, не размять, а разжижить :) А в целом, интересно написали.

      А вы не подскажете, какие редакторы распространены и удобны для lua?
      • +1
        Lua довольно компактный язык, так что, мне кажется, подойдёт любой удобный вам редактор, благо подсветка синтаксиса есть почти везде, а сам он очень прост (лично я использовал лёгкий Geany).
        Если честно, я не знаю специализированных IDE под Lua, но, учитывая его основное применение, полагаю это готовые SDK и редакторы игр.
        • +1
          Для Windows можно скачать заточеную версию SciTE с дебагером и прочими вкусностями.
          Я пишу на Lua в основном для Awesome, поэтому использую Emacs — обычный дебагер мне не нужен, там немного другой подход.
          • +1
            Уже 2 года работаю в QDE(http://www.quotixsoftware.com/programs.htm), ещё чуть более удобный редактор Decoda (http://www.unknownworlds.com/decoda).Decoda умеет аттачиться к любому процессу из диспетчера задач и открывать существующие там lua скрипты. Куча функций, ловит брейкпоинты.
            • 0
              В Intellij IDEA имеется плагин для Lua. Довольно таки активно развивается plugins.intellij.net/plugin/?idea&id=5055
            • +1
              Мне кажется, статья была бы уместнее в блоге «Языки программирования» — тема ненормальности не раскрыта :-)
              • 0
                Да, наверное вы правы. Хотя, наличие Brainfuck всё же позволяет, пусть и с некоторой натяжкой, отнести статью к ненормальному программированию) Спасибо за совет, последующие публикации о Lua буду размещать в блоге «Языки программирования»
              • 0
                К теме о ненормальности подходило бы ближе, если код был написан на С/С++. К сишному коду подключался интерпретатор lua (у lua есть такой интерфейс), в lua скрипте была функция, которая на вход принимает путь к брейнфак файлу и выполняла его :)
                • 0
                  Да, пожалуй так было бы ненормальнее) Правда я планировал в следующей статье написать о взаимодействии C и Lua и рассмотреть механизм передачи объектов между C и средой Lua. Вот там будет код на C который будет загружать Lua который сможет исполнить Brainfuck =)
                  • +1
                    Как насчёт обмена объектами между C++ и Lua? ;) Недавно я занимался встраиванием Lua в C++ проект и очень понадобилась следующая фича: объект C++ должен быть представлен в Lua тоже как объект, т.е. иметь методы. Это как бы проецирование C++ объекта на Lua. Хорошего решения я не придумал, а сделал неудобный костыль: к классу нужно было дописать статические методы и хитрым образом вызывать методы.

                    Например у нас есть класс (у этого класса может быть сотня методов):
                    class GF
                    {
                    public:
                      byte mul(byte, byte);
                    };
                    


                    Хочется сделать некое простое движение, чтобы в Lua можно было написать так:
                    local gf = ...
                    local xy = gf.mul(0x12, 0x76)
                    


                    Я не знаю как это сделать, чтобы было удобно. Может быть вы придумаете.
                • 0
                  А есть преимущество перед реализацией того же на более распространенных языках?
                  • 0
                    В сущности преимуществ нет. Brainfuck довольно прост и реализовать его можно, пожалуй, на любом языке (исключая особенно редкие и странные). Хотя, такую реализацию довольно легко можно встроить в некоторую игру-головоломку. Наверное это единственное стоящее преимущество.
                  • +21
                    А интерпретатор lua на Brainfuck'e?
                    • 0
                      Большое вам спасибо =)
                      Пока я писал свой интерпретатор с помощью вашего кода, я выучил Brainfuck!

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.