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

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):

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

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

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

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

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

class BrainfuckInterpreter {
    constructor() {
        // 30000 ячеек памяти, как в стандарте Brainfuck
        this.memory = new Uint8Array(30000); 
        this.pointer = 0; // Указатель на текущую ячейку
        this.input = '';  // Ввод
        this.output = ''; // Вывод
    }

    interpret(code, input = '') {
        this.code = code;
        this.input = input;
        this.pointer = 0;
        this.output = '';

        // Стек для отслеживания начала и конца циклов
        let loopStack = [];

        for (let i = 0; i < this.code.length; i++) {
            let instruction = this.code[i];

            switch (instruction) {
                case '>':
                    this.pointer++;
                    break;
                case '<':
                    this.pointer--;
                    break;
                case '+':
                    this.memory[this.pointer]++;
                    break;
                case '-':
                    this.memory[this.pointer]--;
                    break;
                case '.':
                    this.output += String.fromCharCode(this.memory[this.pointer]);
                    break;
                case ',':
                    if (this.input.length > 0) {
                        this.memory[this.pointer] = this.input.charCodeAt(0);
                        this.input = this.input.substring(1);
                    } else {
                        // Если ввод закончился, просто устанавливаем значение ячейки в 0
                        this.memory[this.pointer] = 0;
                    }
                    break;
                case '[':
                    if (this.memory[this.pointer] === 0) {
                        let depth = 1;
                        while (depth > 0) {
                            i++;
                            if (this.code[i] === '[') depth++;
                            if (this.code[i] === ']') depth--;
                        }
                    } else {
                        loopStack.push(i);
                    }
                    break;
                case ']':
                    if (this.memory[this.pointer] !== 0) {
                        i = loopStack[loopStack.length - 1];
                    } else {
                        loopStack.pop();
                    }
                    break;
                default:
                    // Игнорируем любые другие символы, которые могут встретиться
                    break;
            }
        }

        return this.output;
    }
}

Этот код создает класс BrainfuckInterpreter, который содержит метод interpret, принимающий код Brainfuck и ввод, и возвращает результат выполнения кода. Мы используем массив memory, чтобы хранить состояние ячеек памяти, и указатель pointer, чтобы отслеживать текущую ячейку. Метод interpret выполняет каждую инструкцию из кода Brainfuck, изменяя состояние memory и pointer соответственно.

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

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

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

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

let interpreter = new BrainfuckInterpreter();
let code = '++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.';
let input = '';
let result = interpreter.interpret(code, input);

console.log(result); // Hello World!

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

,[.,]

let interpreter = new BrainfuckInterpreter();
let code = ',[.,]';
let input = 'Hello, Brainfuck!';
let result = interpreter.interpret(code, input);

console.log(result); // Hello, Brainfuck!

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

>,[>,]<[.<]

let interpreter = new BrainfuckInterpreter();
let code = '>,[>,]<[.<]';
let input = 'Hello';
let result = interpreter.interpret(code, input);

console.log(result); // olleH

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

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

let interpreter = new BrainfuckInterpreter();
let code = '++++++++++[>++++++++++>+<<-]>[>.<-]';
let input = '';
let result = interpreter.interpret(code, input);

console.log(result); 
// Консоль будет очищена.

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

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

let interpreter = new BrainfuckInterpreter();
let code = '+++++[>+++++++++<-],[[>--.++>+<<-]>+.->[<.>-]<<,]';

console.log(interpreter.interpret(code, "42")); 
// ++++++++++++++++++++++++++++++++++++++++++++++++++++.----------------------------------------------------++++++++++++++++++++++++++++++++++++++++++++++++++.--------------------------------------------------

Brainfuck Interpreter (Stepik)

Так как Stepik не поддерживает язык программирования Brainfuck, я добавил его реализацию на JavaScript в виде публичного урока. Теперь вы можете использовать этот урок как Brainfuck Interpreter!

Пройдите по ссылке и начните пользоваться этим интерпретатором Brainfuck. Этот интерпретатор позволит вам запускать программы на языке Brainfuck прямо в вашем браузере, просто вставив код и, при необходимости, ввод данных.

Теперь вам не придется искать другие ресурсы для работы с Brainfuck - у вас есть все необходимое прямо на Stepik! Наслаждайтесь программированием на этом удивительном эзотерическим языке и делитесь своими результатами с сообществом :)