Есть мнение, что каждый программист должен написать в жизни хотя бы один язык программирования, либо реализовать уже существующий, но своими руками. В качестве примера мы начнем с самого простого и создадим Brainfuck. Согласно Вики:
Brainfuck — один из известнейших эзотерических языков программирования, придуман Урбаном Мюллером (нем.Urban Müller) в 1993 году, известен своим минимализмом. Название языка можно перевести на русский как вынос мозга, оно напрямую образовано от английского выражения brainfuck (brain — мозг, fuck — иметь половое сношение), т. е. заниматься ерундой.
Язык имеет восемь команд, каждая из которых записывается одним символом. Исходный код программы на Brainfuck представляет собой последовательность этих символов без какого-либо дополнительного синтаксиса. Википедия.
Описание 8 команд:
| Начало программы | выделяется память под 30 000 ячеек с нулевыми начальными значениями |
| > | перейти к следующей ячейке |
| перейти к предыдущей ячейке | |
| + | увеличить значение в текущей ячейке на 1 |
| — | уменьшить значение в текущей ячейке на 1 |
| . | напечатать значение из текущей ячейки |
| , | ввести извне значение и сохранить в текущей ячейке |
| [ | если значение текущей ячейки ноль, перейти вперёд по тексту программы на ячейку, следующую за соответствующей ] (с учётом вложенности) |
| ] | если значение текущей ячейки не нуль, перейти назад по тексту программы на символ [ (с учётом вложенности) |
Язык программирования Brainfuck за 100 секунд [перевод на русский]
Реализация интерпретатора на Python
Интерпретатор читает программу и выполняет ее сразу на лету.
Первым делом надо прочитать целиком файл с исходником на BF, имя которого мы передаем первым параметром командной строки:
if __name__ == ‘__main__’: if len(sys.argv) == 2: # один аргумент — имя файла, который надо выполнить with open(sys.argv[1], ‘r’) as f: code = f.read() run(code) # запустить код else: print(f’usage: python file.bf’)
После того, как код прочитан, мы создаем память из 30 000 ячеек, заполненными нулями. Устанавливаем счетчик команд и указатель на ленте ячеек на 0. Инициализация имеет такой вид:
mem_size = 30000 memory = [0] * mem_size # оперативная память программы data_ptr = 0 # индекс текущей ячейки памяти (memory) instr_ptr = 0 # индекс текущей инструкции кода (code)
Далее в цикле читаем ячейку, если это одна из наших 8 команд, то выполняем, иначе пропускаем (это могут быть пробелы и переносы строк, их просто игнорируем). После выполнения команды, указатель сдвигается вправо по коду (увеличивается на единицу). Программа выполняется до тех пор, пока счетчик инструкций не выйдет за пределы размера кода.
С командами типа «+», «-«, «» проблем в понимании быть не должно, они делают простые действия. Разве что, вам следует обратить внимание на то, что я зацикливаю оперативную память, если команда смещения переходит границу (команда от 0 сдвинет на 29999 ячейку, а команда > с ячейки номер 29999 сдвигает на 0 ячейку).
BrainF*ck Programming Tutorial — Can You Code in BrainF*ck?
# выполняем — пока не вылетели за пределы кода while instr_ptr < len(code): command = code[instr_ptr] # текущая команда if command == ‘+’: memory[data_ptr] += 1 elif command == ‘-‘: memory[data_ptr] -= 1 elif command == ‘>’: data_ptr = (data_ptr + 1) % mem_size # циклическая память elif command == ‘
Команда точка «.» печатает на экране единственный символ из текущий ячейки памяти. Я использую функцию chr, чтобы из числа получить символ. end=» указывает, что не надо переводить строку. Команда запятая «,» вводит символ из потока ввода. Считываю строку, беру первый символ и получаю его код функцией ord. Дополним код цикла обработкой ввода и вывода:
. elif command == ‘.’: # печатаем символ с кодом = значения текущей ячейки print(chr(memory[data_ptr]), end=») elif command == ‘,’: # ввод — берем код первого символа или 0, если ввод пустой inp = input() memory[data_ptr] = ord(inp[0]) if inp else 0 .
Это еще не все. Осталось самое сложное – обработка циклов (они же играю роль ветвлений в BF).
Открывающая квадратная скобка «[« в code – команда, говорит нам, что нужно проверить текущую ячейку памяти в memory на равенство нулю. Если нуль, то прыгаем за пределы цикла – на соответствующую закрывающую скобку «]». Если не нуль, то дальше просто выполняем тело цикла. Когда натакливаемся на «]», тут тоже нужно проверить условие цикла, и если оно даст не ноль – вернуться к началу цикла, а иначе продолжить выполнять код дальше за скобкой.
Каждый раз во время выполнения кода искать нужную скобку – неудобно и медленно. Можно оптимизировать код, заранее пройдя по нему и запомнив, где какая скобка и где ее подруга – парная скобка. Для этого заведем словарь bracket_map. Для учета вложенности будем пользоваться структурой данных – стэк (из обычного списка):
# ключ и значения — индекс байта в коде # по любой скобке находим ей пару bracket_map = <> stack = [] for pos, symbol in enumerate(code): # открыли скобку — положим на вершину стэка ее позицию if symbol == ‘[‘: stack.append(pos) elif symbol == ‘]’: # вершина стэка — как раз наша парная скобка — была последней # удалим ее с вершины last_open_pos = stack.pop() # создадим парные записи bracket_map[pos] = last_open_pos bracket_map[last_open_pos] = pos
На иллюстрации ниже показано, что хранит этот словарь на примере простой программы.
Теперь мы готовы добавить в цикл исполнения обработку скобок. Просто проверяем условие, и когда нужно перемещаем указатель текущий команды на парную скобку: из начала цикла в конец, если ячейка содержит 0, и из конца цикла в начало, если не 0:
. elif command == ‘[‘: # начало цикла — проверка текущей ячейки if not memory[data_ptr]: # == 0 # значит надо перейти на ячейку за соответствующей ей закрывающей скобкой instr_ptr = bracket_map[instr_ptr] elif command == ‘]’: # проверяем тоже условие, если выполняется, то скачем на начало цилка if memory[data_ptr]: # не ноль # перемещаем на конец цикла instr_ptr = bracket_map[instr_ptr]
Готово! Интерпретатор завершен! Выполним простую программу hello_world.bf:
(venv) ➜ bf python bf_interpretator.py hello_world.bf Hello World!
Работает! А вот как вам сортировка вставками на Brainfuck:
Запускаем. Пишем по очереди символы по одному, энтер после каждого. Чтобы завершить ввод массива – просто энтер без символа:
(venv) ➜ bf python bf_interpretator.py isort.bf 8 4 6 1 9 14689
Код программы и примеры загрузил на gist.
Компилятор Brainfuck на Python
Компилятор берет исходный код и превращает его в машинный исполняемый код. Не бойтесь, мы не будем писать в сложные по формату исполняемые файлы ассемблерные команды в виде байт. Поступим хитро. Сначала транслируем программу на BF в код на языке С, а потом обычным компилятором С транслируем код С в исполняемый файл.
Код обрамляется прелюдией, где мы подключаем стандартную библиотеку и инициализируем память. А также завершающими командами:
PRELUDE = «»»// brainfuck generated: #include int main() < const int mem_size = 30000; char mem[mem_size]; memset(mem, 0, mem_size); int cur = 0; «»» ENDING = «»» return 0; >»»»
Далее код компилятора BF в Си. Все по таблице из Википедии:
def compile_to_c(bf_code): instr_ptr = 0 # индекс текущей инструкции кода (code) indent = 4 # смещение пробелами — для красоты c_code = PRELUDE # выполняем — пока не вылетели за пределы кода for command in bf_code: content = » if command == ‘+’: content = ‘mem[cur]++;’ elif command == ‘-‘: content = ‘mem[cur]—;’ elif command == ‘>’: content = ‘cur++;’ elif command == » instr_ptr += 1 # сдвигаем к следующей команде if content: if command == ‘]’: indent -= 4 c_code += ‘ ‘ * indent + content + ‘n’ if command == ‘[‘: indent += 4 c_code += ENDING return c_code
Сохраняем С-код на диск и вызывем компилятор cc:
c_code = compile_to_c(code) c_file = f’.c’ with open(c_file, ‘w’) as f: f.write(c_code) os.system(f’cc -o .out’)
(venv) ➜ bf python bf_compiler.py hello_world.bf . тут какое-то предупреждение от компилятора. (venv) ➜ bf ./hello_world.bf.out Hello World!
Код на Си получится примерно такой (я сократил его значительно, чтобы не занимать много места в статье):
// brainfuck generated: #include int main() < const int mem_size = 30000; char mem[mem_size]; memset(mem, 0, mem_size); int cur = 0; mem[cur]++; mem[cur]++; mem[cur]++; mem[cur]++; mem[cur]++; while(mem[cur]) < cur++; mem[cur]++; mem[cur]++; mem[cur]++; cur++; mem[cur]++; cur—; cur—; cur—; cur—; mem[cur]—; >cur++; mem[cur]++; mem[cur]++; putchar(mem[cur]); cur++; mem[cur]++; putchar(mem[cur]); mem[cur]++; mem[cur]++; mem[cur]++; mem[cur]++; mem[cur]++; mem[cur]++; putchar(mem[cur]); cur++; putchar(mem[cur]); return 0; >
Код компилятора в том же самом gist.
Замечания. В это варианте запятая будет работать не так, как в интерпретаторе выше. Поэтому код с сортировкой будет вести себя иначе. И второе: проверял компилятор на своей системе macOS, на Windows компилятор скорее всего не будет работать, если только вы его не запускаете из подсистемы Linux или Cygwin или подобных.
Источник: tirinox.ru
Мини-задание 239: brainfuck
Brainfuck — эзотерический язык программирования. Он не используется как удобный инструмент решения практических задач (ввиду своей неудобности и непрактичности), но решать простые задачи на нем может быть интересно и полезно — так же как решать любую головоломку. К тому же brainfuck является наглядным примером тьюринг-полного языка.
Описание и синтаксис
В этом языке нет переменных и функций, модель языка гораздо проще:
Есть большой массив 8-битных значений (т.е. каждый элемент от 0 до 255) — так называемая лента памяти. Есть указатель на ячейку памяти. При запуске программы он указывает на первую ячейку. Значения всех ячеек в момент запуска программы равны нулю.
Команды языка brainfuck:
- > — сдвинуть указатель ячейки памяти вправо к следующей ячейке
- < — сдвинуть указатель ячейки памяти влево к предыдущей ячейке
- + — увеличить значение текущей ячейки на 1
- — — уменьшить значение текущей ячейки на 1
- . — напечатать символ из текущей ячейки в соответствии с ASCII-таблицей
- , — считать в текущую ячейку символ из консоли
- [ — если значение текущей ячейки ноль, то перейти вперёд по тексту программы на команду, следующую за соответствующей ] , иначе продолжить исполнение
- ] — если значение текущей ячейки не ноль, то вернуться назад на команду, следующую за соответствующей [ , иначе продолжить исполнение
Интерпретаторы
Интерпретатор написать очень просто, их существует очень много. Например есть интерпретатор с визуализацией доступный из браузера. Или другой интепретатор тоже из браузера, но этот вычисляет быстро. Есть также интепретатор который требует установки, но обладает расширенным функционалом.
Как с этим жить
Давайте подумаем как напечатать тривиальный Hello world .
Для начала нам надо руководствуясь ASCII-таблицей понять, какие это символы в представлении ASCII-кодов:
Hello world = 72, 101, 108, 108, 111, 32, 119, 111, 114, 108, 100
P.S. Это можно делать не обязательно глазами и руками, а например с помощью онлайн-конвертера
Можно было бы напечатать огромное число операций + (и небольшое количество . ) и напечатать заветный Hello world , но можно воспользоваться умножением и циклами:
// H = 72 = 9*8 // Давайте в первой ячейке положим число 9 +++++++++ [ // Этот блок кода будет выполняться пока в текущей ячейке не ноль (в данном случае текущая = первая) // И будем 9 раз увеличивать вторую ячейку на 8 // Тогда во второй ячейке окажется 72 а это та буква которая нам нужна > // Переходим ко второй ячейке ++++++++ // Увеличиваем ее на 8 // Возвращаемся к первой ячейке — // Уменьшаем ее на единицу ведь еще одна итерация прошла успешно ] // Раз мы пришли сюда значит цикл исполнился 9 раз значит во второй ячейке лежит 72 проверяем: > // Переходим ко второй ячейке . // Выводим символ // Дальше в том же духе
Заметим, что можно сэкономить, ведь при переходе от буквы e к l (т.е. от 101 к 108 ) достаточно увеличить значение всего лишь на 7, а третья и четвертая буквы совпадают.
Еще несколько примеров:
[-] // Зануляет текущую ячейку
[->+ // Сдвигает переменную в соседнюю ячейку
[->+>+ >>[->] // Копирует ячейку в сосденюю
[. [-]] // Выводит текущую ячейку, если она не ноль (обратите внимание, что если ее не занулить, или не сдвинуть вместо этого указатель — то этот цикл зависнет)
Упражнение 1
Условие: Выведите Hello world
Упражнение 2
Условие: Выведите английский алфавит (заглавные буквы): ABCDEFGHIJKLMNOPQRSTUVWXYZ
- Обратите внимание, что английские буквы в ASCII-таблице — символы от 65 до 90 ( 26 символов).
- Попробуйте минимизировать число инструкций (онлайн счетовод символов, пробелы в исходном коде за символы не считаются)
- Посоревнуйтесь с друзьями у кого программа короче (у меня заняло 38 инструкций: ++++++++[->++++++++>++++>++[<.+>-] )
Упражнение 3
Условие: Пользователь вводит два символа — выведите наименьший
- Пример выводящий второй введенный символ: ,>,.
- Пример выводящий первый введенный символ: ,>,
- Придумайте сначала как сделать операцию Если текущая ячейка x == 0, то делаем А
- Спойлер про предыдущий комментарий: пусть справа от текущей лежат 0 1 0 , тогда подумайте что сделает инструкция [>]>> , заметьте что в случае если изначальная клетка была ноль, то указатель теперь на единице, если же изначально был не ноль — то теперь указатель на нуле
- Спойлер2 итого чтобы сделать предложенную в комментарии выше операцию надо положить справа от текущей ячейки 0 1 0 и выполнить код [>]>> [ A ]
Упражнение 4
Условие: Пользователь вводит буквы одну за другой, пока не введет символ точки (код 46 ). Выведите введенные символы в алфавитном порядке (с повторениями)
- Попробуйте алгоритм ищем максимум, поднимаем его вверх или делаем n^2 сравнений соседей, если они в неправильном порядке — swap между собой или сортировкой подсчетом
- Поймите сколько вам нужно было бы переменных, и оставьте между хранящамися на ленте символами зазор в столько ячеек, сколько вам нужно переменных
- Пока вы будете реализовывать — постоянно будет оказываться что зазор надо было брать больше, так что удобнее брать зазор с запасом 🙂
Отправка решения
Если вы сделали второе/третье/четвертое упражнение, то можете отправить мне ваше решение письмом:
- Пример темы письма: Brainfuck 16-1 Полярный Николай Упражнение 4 (в конце темы номер самого сложного упражнения, которое вы осилили)
- Если ваше решение короче лучшего на данный момент — ваше решение будет выложено ниже
- Исходный код можно прилагать либо файлом, либо прямо в тексте письма (желательно хоть как-то форматированный)
Лучшие результаты:
Ниже приведены самые короткие решения. (считаются только символы являющиеся корректными инструкциями, онлайн счетовод символов, интерпретатор, подобные задачки решают на codegolf)
P.S. По клику появляется исходный код
Упражнение 1 (Hello World)
131 символов (11-1 Думпис Сергей)
Упражнение 2 (Алфавит)
- 35 символов: +++++++++++++[>++>+++++[>.+
- 36 символов: +++++++++++++[>+++++>++>[<.+>-] (10-1 Олейник Иван)
- 36 символов: +++[>+++++[>++>+++++[>.+
Упражнение 3 (Минимум)
33 символов (11-1 Кохась Дмитрий)
155 символов (11-1 Вирачев Арсений)
Упражнение 4 (Сортировка)
116 символов (10-1 Олейник Иван)
3092 символа. С комментариями. (11-1 Вирачев Арсений)
//формат глобально такой: //Адрес 0: 1 если надо сделать ещё итерацию(и) вычитания единицы //1) Дальше много фблоков вида //2) (флаг начала/конца массива (0=начало/конец))010 //3) число //4) (число для уменьшения)010 //5) (флаг вывода числа (1=выведено))010 //6) (вспомогательный флаг)010 //В самом конце вводим точку (46) и устанавливаем для неё флаг вывода в 1 и флаг конца в 0 +> //записываем в первую ячейку 1 (это нужно потом) >>+ //делаем нулевой фиктивный блок 0010 0 0010 1010 0010 >>>>>+ >>+ //флаг вывода = 1 >>+ >>>>+ >> //вводим остальные числа + //1 в начале блока [ >>+> , [ //делаем 1010aaa >+>+>+ >> //вычитаем 46=7*7 минус 3 из последней a >+++++++ [ — ] <+++ //делаем 1010aa(a минус 46)010 >>+ >>>>>>>>>+]>>[ //если a=46 >>>>>>>>>->>+>>>>>>> >] + >- >>>+ >>>>+ >> //перешли в начало следующего блока ] //в начало нулевого блока >>>>>>>>>>>>>>>>> //в начало первого блока [ //цикла пока не дойдём до последнего блока >>>>> [>]>>[ //если текущее уменьшенное число = 0 >> [>]>>[ //если флаг вывода = 0 >>>>+ //флаг вывода = 1 >> >] ] > [>]>>[ //если флаг вывода = 0 >>>>>>>+ //вспомогательные флаг = 1 ] >>>>> //в начало следующего блока ] >>>>>>>>>>>>>>>> //17 вперёд — [>]>>[ //если есть следующий блок (не фиктивный) >>>>>>>>>>> //вспомогательный флаг следующего блока [ //обнуляем этот флаг если он не = 0 — ]>>[ //если он = 0 > >] >>>>>>>>>>>>>> //17 минус 3 вперёд ] <<<<<<] //обнуляем нулевую ячейку >>>>>>>>>>>>>>>>> //17 вперёд >>>>>>>>>>>>> //вспомогательный флаг первого блока [ //если там 1 //теперь опять обратно >>>>>>>>>>>>>>>>> //17 вперёд >>>>>>>>>>>>> //вспомогательный флаг первого блока — //обнуляем его ]
Источник: www.polarnick.com
Hello, Brainfuck!
Давайте напишем свою первую программу на Brainfuck, которая будет выводить текст “Hello World!”. Алгоритм прост:
1. Увеличиваем значение в ячейке до тех пор, пока оно не будет равно нужному символу
2. Выводим значение в ячейке (наш символ)
3. Переходим к следующей ячейке
4. Повторяем, пока все символы не будут выведены
Реализуем алгоритм и на php — скрипт будет генерировать исходный код на Brainfuck, который выводит нужный текст:
“Hello World!” вышел довольно таки большим по размеру, попробуем его оптимизировать. Необязательно каждый раз переходить в новую ячейку и начинать «путь» к нужному символу с нуля — мы можем использовать текущее значение ячейки. Новый алгоритм:
1. Увеличиваем значение в ячейке до тех пор, пока оно не будет равно нужному символу
2. Выводим значение в ячейке (наш символ)
3. Если следующий нужный символ больше текущего, то увеличиваем значение в ячейке, если меньше – уменьшаем, пока не получим нужное
4. Выводим значение в ячейке (наш символ)
5. Повторяем, начиная с п. 3, пока все символы не будут вывдены
Уже меньше 🙂 Вот код на php, генерирующий подобный исходник:
Можно ли еще оптимизировать получившийся код на Brainfuck? Можно! Теперь мы опять будем использовать несколько ячеек, но реализуем и используем умножение. А помогут в этом ранее неиспользованные нами команды [ и ]. Умножение — с помощью суммы, 5*10=10+10+10+10+10. Тоесть, нам надо повторить прибавление 10 к ячейке 5 раз. Алгоритм программы:
1. Увеличиваем значение в ячейке до тех пор, пока оно не будет равно 10 – счетчик для цикла, множитель
2. Цикл начинается [
3. Увеличиваем значение в ячейке до тех пор, пока оно не будет равно n – результату целочисленного деления кода нужного символа на 10
4. Переходим к следующей ячейке
5. Повторяем п.3-4 для всех символов
6. Уменьшаем счетчик цикла (первую ячейку)
7. Цикл окончен ]
8. Переходим к следующей после счетчика ячейке
9. Прибавляем к ячейке остаток целочисленного деления кода нужного символа на 10 (для «H» в ячейке у нас будет 70, надо прибавить 2 = 72 % 10. Тоесть в итоге получим «H»=(72 / 10)+(72 % 10))
11. Выводим значение в ячейке (наш символ) и переходим к следующей ячейке
12. Повторяем п.9-11 для всех символов
Вуаля! Код php-генератора:
Итог
Вот такой вот интересный и замечательный язык Brainfuck 🙂 В заключение, приведу генератор, написанный мной на самом Brainfuck. Эта програма считывает введенный текст и генерирует код на Brainfuck (оптимизированный), который этот текст выведет.
Источник: habr.com