Создание интерпретатора Brainfuck с помощью JavaScript
Для своего первого урока (и в духе откладывания реальной работы) я решил написать кое-что интересное: мы собираемся создать интерпретатор Brainfuck, который будет работать в нашем браузере, в JavaScript, в комплекте с графическим интерфейсом. Это руководство предполагает базовые знания JavaScript, HTML, CSS и программирования в целом.
Готовый продукт можно увидеть на страницах GitHub здесь и в репозитории с исходным кодом здесь.
Примечание: Настоящей официальной спецификации языка нет. Все, что у нас есть, - это оригинальная реализация и группа общепринятых рекомендаций. При этом будут приняты некоторые вольности в отношении реализации для простоты, поэтому некоторые программы Brainfuck, которые вы можете увидеть в Интернете, могут давать неожиданные результаты при запуске в этом интерпретаторе, поскольку они ожидают таких функций, как перенос переполнения.
Примечание 2: В этом руководстве будут использоваться конструкции ES5,6 +, такие как объявления «const», Array.prototype.fill () и другие. Если ваш код не запускается, возможно, вы используете устаревший браузер!
Какого хрена Brainfuck?
Brainfuck - это T uring Complete, эзотерический язык программирования. То есть странный, экспериментальный или шутливый язык. На первый взгляд это кажется сложным (название, конечно, не помогает), но с базовым пониманием программирования становится ясно (вроде). Синтаксис языка состоит только из следующих символов:
А вот и образец программы Brainfuck: классический Hello World.
Красиво, не правда ли? А теперь давайте разберемся, что все это значит.
Brainfuck работает с блоком памяти, разделенным на «ячейки». Обычно это реализуется как массив чисел (в нашем случае целых чисел), инициализированный значением 0, причем ячейки являются элементами массива.
Символы > и < перемещают указатель, который, если вы не знакомы с концепцией программирования, представляет собой просто число (обычно адрес), указывающее на ячейку памяти. Точно так же мы будем использовать число, указывающее на текущую ячейку памяти (индекс массива). Когда используется команда «переместить указатель влево», мы уменьшаем индекс на 1. И наоборот, мы увеличиваем его на 1, когда используется команда «переместить указатель вправо».
Символы + и - увеличивают или уменьшают ячейку (элемент массива), на которую в настоящий момент указывает указатель.
Давайте посмотрим на пример того, что у нас есть на данный момент:
Memory:[ 0, 0, 0, 0, 0] Pointer: 0
Допустим, мы должны были выполнить следующие инструкции: >>>+++++<<+, что на английском языке переводится как: «Переместите указатель на три ячейки вправо, увеличьте эту ячейку на единицу 5 раз, переместите ее дважды влево, увеличьте эту ячейку на единицу один раз» состояние памяти теперь будет:
Memory: [ 0, 1, 0, 5, 0] Pointer: 1
Надеюсь, это (вроде) имеет для вас смысл! Давай продолжим.
Символ , считывает символ из ввода и присваивает его значение (в соответствии с его значением ASCII) ячейке, на которую в данный момент указывает. Способ ввода зависит от реализации. Некоторые реализации требуют, чтобы входные данные передавались вместе с исходным кодом самой программы, обычно разделенные каким-либо символом. Мы будем использовать поле ввода как своего рода поток, который программа потребляет каждый раз, когда встречает символ ,.
Символ . просто выводит символ, значение которого соответствует числу, хранящемуся в ячейке, на которую мы сейчас указываем.
Наконец, у нас есть символы [ и ]. Они используются для потока управления (цикл, условия и т. Д.). Когда левая скобка встречается в коде, если текущая ячейка памяти не равна нулю, он будет продолжать выполнение до тех пор, пока не достигнет соответствующей правой скобки, в которой точка указатель вернет назад в левую скобку, если снова указанная ячейка не равна нулю.
Поначалу все это может показаться запутанным, но я обещаю, что скоро все обретет смысл. (Или не.)
Приступим к кодированию!
Ну еще нет. Как и в случае с любой проблемой программного обеспечения, давайте разберем проблему на части и определим, что нам понадобится.
- Обычные реализации содержат 30000 ячеек для памяти. Мы также позволим памяти расширяться, если это необходимо.
- Нам нужно отслеживать текущее положение указателей как для памяти, так и для инструкций.
- Подобно тому, как программы хранят адреса памяти в стеке, чтобы знать, куда вернуться после, например, вызова функции, нам понадобится собственный стек, чтобы отслеживать адреса (или индексы массивов), где мы встречаем символы
[. - Нам нужно будет сохранить исходный код программы, а также ее ввод и вывод.
- Чтобы интерпретировать программу, нам нужно пройти по исходному коду, по одному символу за раз, и выполнить операции с ячейками или указателями в соответствии с инструкциями.
Мы собираемся начать без графического интерфейса, сосредоточившись на функциональности и используя консоль Dev Tools нашего браузера для взаимодействия с кодом.
Приступим к кодированию! (На этот раз по-настоящему)
Начнем с объявления некоторых переменных:
Здесь у нас есть все необходимые переменные. У нас есть два указателя: один на ячейки памяти, второй на инструкции (исходный код). У нас есть адресный стек для отслеживания мест возврата, массив из 30 000 ячеек (который может расширяться, будет реализован в интерпретирующей части кода) и три строки: программа, ввод и вывод.
Все эти значения инициализируются так, как они должны быть, когда программа готова к запуску, но давайте добавим функцию для их сброса, чтобы нам не приходилось перезагружать страницу каждый раз, когда мы хотим запустить программу.
Сброс состояния
Далее мы должны решить, как мы будем обрабатывать программу. Доступ к строкам в JavaScript можно получить так же, как к массивам с синтаксисом string[index], поэтому нам не нужно беспокоиться о преобразовании нашего исходного кода в массив. Есть несколько вариантов того, как решить, какую операцию выполнить в зависимости от инструкции. Я выбрал оператор переключения, поскольку он намного чище, чем цепочка if-else if-else, а также в целом быстрее (за исключением Microsoft Edge, в этом случае он на 40% медленнее (WTF ???)).
Ввод, вывод
Вход и выход - это строки. Есть разные способы обойти программирование поведения ввода. Мы предпочтем предоставить исходные данные вместе с программой, как и большинство интерпретаций.
Код довольно прост. Поскольку в ячейках памяти хранятся числа, мы должны преобразовывать коды символов и обратно.
sendOutput()преобразует значение текущей ячейки в символ и добавляет его к нашей выходной строке.getInput()удаляет первый символ входной строки и устанавливает значение текущей ячейки на код этого символа. У нас есть значение по умолчанию 0 на случай, если ввод недоступен.
Базовый код интерпретатора
Здесь у нас есть функция interpret(), которая будет вызываться, когда мы хотим запустить программу. У нас есть оператор switch, который смотрит на значение в текущей инструкции (символ с индексом ipointer) и выбирает соответствующий ему путь. Все это завершается while(!end) циклом с приращением ipointer++ в конце для перехода к следующей инструкции. Если мы получаем неопределенное значение, это означает, что указатель инструкции указывает на значение за пределами диапазона строки и, следовательно, программа завершена, поэтому мы устанавливаем end to true. Как и в большинстве других реализаций Brainfuck, мы будем игнорировать любой символ, не являющийся частью синтаксиса, чтобы разрешить такие вещи, как комментарии и пробелы.
Функциональность программирования для инструкций
Давайте вспомним предыдущую таблицу (вы можете оставить ее открытой для дальнейшего изучения) и начнем писать код для каждой инструкции.
Пока я заполнил код только самых простых инструкций, первых шести. Код довольно понятен. > и < увеличивают или уменьшают на единицу указатель, в то время как + и - увеличивают или уменьшают на единицу значение, на которое указывает указатель. Вы также можете заметить условный оператор в инструкциях указателя, это позволяет памяти расширяться, если мы пытаемся пройти мимо 30000-й ячейки (на 5 за раз, совершенно произвольное число) и предотвращать попытки доступа к массиву при отрицательном индексе. Наконец, у нас есть инструкции вывода и ввода, которые просто отправляют текущее значение в нашу функцию вывода и устанавливают текущее значение, возвращаемое нашей функцией ввода, соответственно.
Здесь все может немного запутаться, но не волнуйтесь, мы справимся с этим. Символы [ и ] в основном используются для потока управления, такого как цикл и условия. Посмотрим на код.
Возможно, это единственная «сложная» часть кода. Давай пройдемся через это. Когда мы встречаем [, мы делаем одно из двух:
- Если значение, на которое в данный момент указывается, не равно нулю, мы помещаем указатель текущей инструкции на наш
astackи продвигаемся вперед, как обычно. - В противном случае мы должны перейти к соответствию
]. На первый взгляд это может быть сложно, потому что мы можем натолкнуться на вложенные скобки и, следовательно, заставили бы нас остановиться не в том месте, если бы мы просто искали следующий], поэтому мы ведем подсчет того, сколько левых скобок мы встречаем при перемещении. вперед по исходному коду и уменьшать его каждый раз, когда мы встречаем правую скобку, поэтому мы переходим к правильной области.
Когда мы встречаем ], мы просто извлекаем адрес из стека и назначаем его указателю инструкции, чтобы вернуться к левой скобке.
Мы завершаем функцию, выводя полученный результат на консоль и затем возвращая его (так как он нам понадобится при построении графического интерфейса в HTML).
Переводчик готов!
Это было не так уж плохо, правда? Вот все в одном куске:
Чтобы проверить это, либо скопируйте / вставьте код прямо в консоль (F12 в большинстве браузеров или CTRL + SHIFT + I) прямо здесь, на этой самой странице, либо создайте простой HTML-документ, который загружает исходный код в виде файла, например:
Чтобы взаимодействовать с ним, используйте консоль, чтобы установить переменную program для любой программы Brainfuck (например, в предыдущем примере Hello World):
Затем вызовите функцию interpret(), написав ее в консоли точно так же, и вы должны увидеть вывод «Hello World!».
Поскольку все переменные находятся в глобальной области, вы также можете ввести memory, например, в консоли и увидеть значения, содержащиеся в каждой ячейке.
Вот и все!
Надеюсь, вам понравилась моя первая статья, и вы узнали что-то полезное (ладно, полезно, возможно, это не прилагательное). Если да, хлопни меня в ладоши? (Так они называются? Извините, я здесь новенький.)
- С, как всегда, Шон.
