Brainfuck интерпретатор на Python

Brainfuck — это один из эзотерических языков программирования, придуманный Урбаном Мюллером в 1993 году, и он известен своим минимализмом. Название языка можно перевести как “вынос мозга”, оно напрямую происходит от английского выражения “brainfuck” (где “brain” означает мозг, а “fuck” — вынос), подразумевая занятие нелепостями. В Brainfuck всего восемь команд, каждая из которых представлена одним символом. Исходный код программы на Brainfuck представляет собой простую последовательность этих символов без дополнительного синтаксиса.

Одним из основных мотивов создания Brainfuck было стремление Урбана Мюллера создать язык с наименьшим возможным компилятором. Вдохновение он черпал, в частности, из языка FALSE, для которого существовал компилятор размером всего 2044 байта. На сегодняшний день существуют компиляторы Brainfuck размером менее 200 байт. Написание программ на языке Brainfuck сложно, что иногда заставляет называть его языком для мазохистов. Тем не менее, Brainfuck является естественным, полным и простым языком, который может использоваться для определения понятия вычислимости.

FALSE — эзотерический язык программирования, созданный в 1993 году Ваутером ван Ортмерссеном с двумя, по его словам, целями: чтобы можно было написать компилятор для него размером не более одного килобайта. придумать синтаксис, который бы выглядел шифровкой, случайным набором символов.

Байт (Byte) — единица хранения и обработки цифровой информации; совокупность битов, обрабатываемая компьютером одновременно.

Cписок восьми команд языка программирования Brainfuck:

Эти простые команды позволяют управлять памятью, изменять ее содержимое и выполнять циклические операции, что достаточно для реализации алгоритмов любой сложности.

Несмотря на свою примитивность, Brainfuck с его бесконечным набором ячеек обладает тьюринговской полнотой. Следовательно, по потенциальным возможностям он не уступает “настоящим” языкам программирования, таким как С, Pascal или Java.

Тьюринговская полнота - это концепция, связанная с теорией вычислимости, которая определяет способность системы (обычно вычислительной) выполнить любое вычисление, которое может быть выполнено с помощью машины Тьюринга. Машина Тьюринга - это абстрактная модель компьютера, предложенная Аланом Тьюрингом в 1936 году. Она состоит из бесконечной ленты, разделенной на ячейки, и управляющего устройства, способного читать/писать на этой ленте и перемещать головку.

Система считается тьюринговски полной, если она может быть использована для эмуляции машины Тьюринга, то есть если она способна выполнять любой алгоритм, который может быть представлен в виде машины Тьюринга. Практически это означает, что система может решать широкий класс задач, включая вычисление любой рекурсивной функции или выполнение любого алгоритма.

Системы с тьюринговской полнотой широко используются в компьютерах и программном обеспечении, поскольку они предоставляют универсальный способ выполнения разнообразных задач. В том числе, они обычно используются для оценки вычислительной мощности различных языков программирования и архитектур компьютеров.

Brainfuck подходит для проведения экспериментов в области генетического программирования из-за своей простоты синтаксиса и, как следствие, легкости генерации исходного кода.

В “классическом” варианте Brainfuck, созданном Мюллером, размер ячейки составляет один байт, а количество ячеек равно 30 000. При начальной установке указатель находится в крайней левой позиции, а все ячейки заполнены нулями. Увеличение или уменьшение значений ячеек происходит по модулю 256. Ввод-вывод также происходит побайтно, используя кодировку ASCII. Например, при операции ввода (,) символ “1” будет записан в текущую ячейку как число 0x31 (49), а операция вывода (.) над ячейкой, содержащей 0x41 (65), напечатает латинскую букву “A”. В других вариантах языка размер и количество ячеек могут отличаться. Существуют версии, где значения ячеек не являются целочисленными (с плавающей точкой).

Пример программы Hello World

Пошаговая программа на языке Brainfuck, печатающая Hello World! с переносом строки (в виде ASCII-кода: 72 101 108 108 111 32 87 111 114 108 100 33 10):

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

Разбор программы:

Реализация интерпретатора на Python

Реализация интерпретатора Brainfuck на Python не так уж сложна благодаря простоте языка.

Вот простая реализация интерпретатора Brainfuck на Python:

class BrainfuckInterpreter:
    def __init__(self):
        # 30000 ячеек памяти, как в стандарте Brainfuck
        self.memory = bytearray(30000)
        self.pointer = 0  # Указатель на текущую ячейку
        self.input = ''   # Ввод
        self.output = ''  # Вывод

    def interpret(self, code, input_str=''):
        self.code = code
        self.input = input_str
        self.pointer = 0
        self.output = ''
        
        # Стек для отслеживания начала и конца циклов
        loop_stack = []

        i = 0
        while i < len(self.code):
            instruction = self.code[i]

            if instruction == '>':
                self.pointer += 1
            elif instruction == '<':
                self.pointer -= 1
            elif instruction == '+':
                self.memory[self.pointer] += 1
            elif instruction == '-':
                self.memory[self.pointer] -= 1
            elif instruction == '.':
                self.output += chr(self.memory[self.pointer])
            elif instruction == ',':
                if self.input:
                    self.memory[self.pointer] = ord(self.input[0])
                    self.input = self.input[1:]
                else:
                    # Если ввод закончился, просто устанавливаем значение ячейки в 0
                    self.memory[self.pointer] = 0
            elif instruction == '[':
                if self.memory[self.pointer] == 0:
                    depth = 1
                    while depth > 0:
                        i += 1
                        if self.code[i] == '[':
                            depth += 1
                        if self.code[i] == ']':
                            depth -= 1
                else:
                    loop_stack.append(i)
            elif instruction == ']':
                if self.memory[self.pointer] != 0:
                    i = loop_stack[-1]
                else:
                    loop_stack.pop()
            else:
                # Игнорируем любые другие символы, которые могут встретиться
                pass

            i += 1

        return self.output

Такая реализация является базовой и может быть расширена для обработки дополнительных функций, таких как ввод-вывод файлов, оптимизация производительности и т.д.

Примеры использования

Программа для вывода: Hello World!

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

interpreter = BrainfuckInterpreter()
code = '++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.'
input_str = ''
result = interpreter.interpret(code, input_str)

print(result)  # Hello World!

Программа для копирования ввода в вывод

,[.,]

interpreter = BrainfuckInterpreter()
code = ',[.,]'
input_str = 'Hello, Brainfuck!'
result = interpreter.interpret(code, input_str)

print(result)  # Hello, Brainfuck!

Программа которая выводит обратный ввод

>,[>,]<[.<]

interpreter = BrainfuckInterpreter()
code = '>,[>,]<[.<]'
input_str = 'Hello'
result = interpreter.interpret(code, input_str)

print(result)  # olleH

Программа для очистки командной консоли

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

interpreter = BrainfuckInterpreter()
code = '++++++++++[>++++++++++>+<<-]>[>.<-]'
input_str = ''
result = interpreter.interpret(code, input_str)

print(result)  # Консоль будет очищена.

Программа кодирования строки ввода в Brainfuck

+++++[>+++++++++<-],[[>—.++>+<<-]>+.->[<.>-]<<,]

interpreter = BrainfuckInterpreter()
code = '+++++[>+++++++++<-],[[>--.++>+<<-]>+.->[<.>-]<<,]'
input_str = "42"
result = interpreter.interpret(code, input_str)

print(result)  # ++++++++++++++++++++++++++++++++++++++++++++++++++++.----------------------------------------------------++++++++++++++++++++++++++++++++++++++++++++++++++.--------------------------------------------------