В 2019 году, в ноябре месяце, я взял Юлию, просматривая доступные языки на Exercism. Я написал статью, рассказывающую о некоторых изящных функциях, с которыми мне пришлось поиграть, и довольно много людей в сообществе Julia это увидели. Вскоре после этого я начал работать над написанием кода для Джулии на стажировке, и с тех пор с удовольствием занимаюсь этим.
Сегодня, чтобы отпраздновать полгода обучения у добрых, ловких людей на моей работе и в Джулии Слэк, я собираюсь показать вам веселый небольшой проект выходного дня, над которым я работаю. Он позволяет запускать код Brainfuck внутри файла Julia без использования интерпретатора времени выполнения. Это достигается путем преобразования программы Brainfuck в функцию Julia перед компиляцией. Он крошечный, занимает менее 80 строк кода. Еще очень забавно показывать людям:
Давайте посмотрим, как это работает, и посмотрим, что мы можем с этим сделать.
Оглавление
- Что такое Brainfuck
- Код Джулии - это структура данных: создание кода во время синтаксического анализа
- Lexing and Parsing Brainfuck с множественной отправкой
- Собираем все вместе
- Взгляд в бездну: вложение программ внутри программ
- Часто задаваемые вопросы и ресурсы
1. Понимание Brainfuck
Brainfuck - это эзотерический язык программирования, известный своим крайним минимализмом и именем ха-ха-смешно-ругаться. Не вдаваясь в подробности обработки ограничений размера или интерпретации данных, вот краткое изложение того, как работает программа, написанная на Brainfuck:
- Сначала инициализируйте массив байтов, каждый с нулевым значением, со ссылкой, указывающей на первый элемент в этом массиве. В программе есть точки ввода и вывода для чтения и записи байтов информации (обычно это stdin и stdout).
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ..., 0] ^ | Reference
2. Прочтите инструкции слева направо. Это следующие:
>и<перемещают ссылку вправо и влево на один пробел.+и-увеличивают и уменьшают ссылочный байт на единицу.,считывает байт из ввода и устанавливает для указанного байта его значение..записывает указанный байт в вывод.[является условным: если указанный байт равен нулю, перейти к соответствующей инструкции]и продолжить выполнение программы. В противном случае переходите к следующей инструкции как обычно.]также является условным: если указанный байт не равен нулю, перейти к соответствующей инструкции[и продолжить выполнение программы. В противном случае переходите к следующей инструкции как обычно.
3. Вот и все.
Проницательные читатели заметят, что [ и ] вместе образуют цикл while. Например, набор инструкций типа [>+] можно примерно перевести в следующий код:
while memory[index] != 0
index += 1
memory[index] += 1
end
Несмотря на свой абсолютный минимализм, Brainfuck является полным по Тьюрингу без ограниченной памяти, и, хотя его чрезвычайно сложно программировать, написание интерпретаторов для его восьми инструкций - тривиальная задача, которая превращает проект в увлекательный выучите новый язык после того, как вы получите ваши Hello Worlds и FizzBuzzes вне вашей системы. Интерпретаторы уже существуют для Java, C ++, Python, Haskell и, да, Julia.
Так почему же я не сделал переводчика вместо транспилятора? Ответ заключается в том, что многие встроенные языковые функции Джулии позволяют нам находить более элегантные решения. Поговорим о метапрограммировании.
2. Код Джулии - это структура данных: генерация кода во время синтаксического анализа.
В зависимости от того, кого вы спросите, Джулия либо происходит от Лиспа, либо является тайно замаскированным Лиспом (шшшш, никому не говори). Один из наиболее заметных способов, с помощью которых Lisp дает программисту контроль над своим кодом, - это макросы, которые позволяют программистам на Lisp генерировать код любым количеством способов, от реализации синтаксиса понимания списка до создания совершенно новых предметно-ориентированных языков. . Метапрограммирование, как следует из названия, - это программирование самой программы, и в Julia у нас есть доступ к инструментам, которые могут дать нам некоторую силу, которую эти забавные волшебники Lisp создавали на протяжении десятилетий.
По своей сути программа Brainfuck - это единственная функция с входом и выходом, выделенным пространством для памяти и заданным количеством инструкций для управления этой памятью. Чтобы перевести программу Brainfuck в код Джулии, нам нужно определить такую функцию и заменить программу Brainfuck на перенесенное определение функции во время синтаксического анализа.
Вот наша первая попытка:
Давайте разберемся с этим.
- Мы добавляем к тегу bf суффикс str, чтобы воспользоваться встроенной поддержкой Джулии нестандартных строковых литералов. Регулярные выражения, например, могут быть построены с использованием префикса
r, что позволяет использовать краткие представления, такие какr"\s+", в процедурах сопоставления с образцом. Здесь это позволит нам встраивать команды Brainfuck в строковый литерал. Например:bf">>+>>+[-<]" - Мы обертываем нашу функцию, используя синтаксис блока
quote, чтобы гарантировать, что мы возвращаем сам код, а не оцениваемую функцию. Если наша функция былаf(x) = 2 * x, например, и мы хотели сгенерировать выражениеf(3), это гарантирует, что мы вернем самf(3), а не вычисленное значение6. - Мы определяем нашу функцию анонимно, чтобы ее можно было назначить как переменную в контексте чего-то вроде
foo = bf"->+++,<.", которое позже может называтьсяfoo(; input=stdin)или что-то подобное. - Согласно исходному распределению языка, размер памяти по умолчанию составляет 30000 ячеек, но его можно настроить для программ, требующих большего пространства.
- Мы позволяем вводить любую абстрактную строку в дополнение к источнику ввода-вывода для удобства пользователя. Внутренне строка преобразуется в источник ввода-вывода.
esc- это способ избавиться от макрогигиены. Поскольку все наши переменные определены в локальной области видимости, нет необходимости беспокоиться о конфликтах области видимости переменных, поэтому мы не ограничиваем область действия наших переменных модулем, в котором мы определяем наш макрос. Не делайте этого, если только вы абсолютно уверен, что он будет работать без непредвиденных побочных эффектов.
После всего этого у нас есть макрос, который генерирует функцию. Эта функция инициализирует область памяти программы Brainfuck, а затем ничего не возвращает. Мы можем сгенерировать выражения для программы Brainfuck, если поймем, как их вставлять в выражение функции. Это просто, потому что код Julia - это структура данных. Давайте углубимся в Expr.
Выражения Julia имеют head, Symbol, обозначающий тип выражения, и args, переменное количество других объектов. Возьмите этот цикл while:
while i != 0
i -= 1
end
Запуск dump для этого выражения позволяет нам увидеть, как Джулия видит этот синтаксис.
julia> dump(:(while i != 0; i -= 1; end))
Expr
head: Symbol while
args: Array{Any}((2,))
1: Expr
head: Symbol call
args: Array{Any}((3,))
1: Symbol !=
2: Symbol i
3: Int64 0
2: Expr
head: Symbol block
args: Array{Any}((2,))
1: LineNumberNode
line: Int64 1
file: Symbol none
2: Expr
head: Symbol -=
args: Array{Any}((2,))
1: Symbol i
2: Int64 1
Мы видим, что в верхней части дерева есть символ while, обозначающий начало конструкции цикла. Отсюда args - это условное выражение и выражение блока, которое используется для создания многострочных блоков операторов.
Давайте запустим dump для указанной функции. Я сократил определения функций для пространства и добавил несколько подсказок, на что следует обратить внимание.
julia> dump(quote
function (; <parameters>)
<memory initialization>
<IO initialization>
end
end)
Expr
head: Symbol block
args: Array{Any}((2,))
1: LineNumberNode
line: Int64 2
file: Symbol none
2: Expr
head: Symbol function
args: Array{Any}((2,))
1: Expr
head: Symbol tuple
args: Array{Any}((1,))
1: Expr
head: Symbol parameters <-- <parameters>
args: Array{Any}((4,))
1: Expr
2: Expr
3: Expr <we want to insert expressions here>
4: Expr |
2: Expr |
head: Symbol block v
args: Array{Any}((4,)) <function body>
1: LineNumberNode
line: Int64 4
file: Symbol none
2: Expr <----- <memory initialization>
head: Symbol =
args: Array{Any}((2,))
1: Symbol memory
2: Expr
3: LineNumberNode
line: Int64 5
file: Symbol none
4: Expr <----- <IO initialization>
head: Symbol =
args: Array{Any}((2,))
1: Symbol characters
2: Expr
Посмотри на это! У нас есть дерево выражений, и мы точно знаем, где находится тело функции! Это немного уродливо, но теперь мы можем получить доступ к телу функции по адресу
last(last(brainfuck_function.args).args).args
Наш код - это просто структура данных, и теперь все, что нам нужно сделать, это скормить ей выражения, которые эквивалентны инструкциям Brainfuck, которые мы получим в нашем program. Для этого нам нужно будет преобразовать и проанализировать наш код Brainfuck на серию выражений.
3. Lexing и Parsing Brainfuck с множественной рассылкой
Теперь, когда мы знаем фундаментальную структуру функции, в которую будет переводить наша программа Brainfuck, нам нужно будет фактически перевести эти инструкции. К счастью, система типов Джулии и множественная отправка сделали нас здесь успешными. Используя отправку по типам значений, мы можем напрямую отображать инструкции в отдельные экземпляры инструкции. Сначала мы конвертируем программную строку в вектор Char структур, а затем конвертируем каждое из этих Char значений в Symbol, которое мы затем можем отправить с помощью lex(Val(symbol)). Сначала мы определяем наши типы инструкций, наши символы и наши коды операций.
Затем мы заархивируем два константных списка и перебираем их, генерируя инструкцию и соответствующую lex функцию для каждого кода операции:
Например, для второй итерации в этом цикле у нас есть (:-, :Decrement), который генерирует следующий код:
struct Decrement <: AbstractBFInstruction end
lex(::Val{:-}) = Decrement()
Что, если мы встретим символ, не соответствующий инструкции? А пока мы назначаем его резервному типу, который не наследуется от AbstractBFInstruction. Наконец, мы отправляем lex на итерации Chars, которая, в свою очередь, отправляет lex поэлементно для каждого символа в программе:
Большой! Теперь у нас есть список инструкций. Единственное, что осталось сделать, прежде чем мы снова соберем все это вместе, - это проанализировать инструкции в коллекцию выражений, которые мы можем вставить обратно в тело функции. Вот вся процедура синтаксического анализа:
После инициализации наших стеков выражений и циклов эта функция обрабатывает каждую инструкцию в два этапа: анализирует следующую инструкцию и добавляет результат в наш список выражений.
- Парсинг
Мы заканчиваем существующий цикл? Давайте проверим, действительно ли мы запустили цикл - и если нет, выдадим ошибку, потому что это означает, что наша программа недействительна. С другой стороны, если мы запустили хотя бы один цикл, мы можем извлечь последнее добавленное выражение цикла из стека циклов и использовать его для шага 2.
В противном случае давайте разберем нашу текущую инструкцию в выражение. Здесь множественная отправка снова спасает нас, давая нам краткий способ сопоставить каждую инструкцию с выражением:
2. Выяснение того, куда можно вставить выражение.
Наша инструкция - начало цикла? Нет проблем - мы можем просто поместить его в стек цикла. В противном случае давайте проверим, пуст ли стек цикла. Это означает, что наше выражение находится на верхнем уровне локальной области видимости функции, и вместо этого мы можем просто вставить его в стек выражений. Но что, если мы находимся в середине цикла? Хорошо, помните, когда я ранее в статье сбрасывал выражение цикла while? Давайте посмотрим на это еще раз:
julia> dump(:(while i != 0; i -= 1; end))
Expr
head: Symbol while
args: Array{Any}((2,))
1: Expr
head: Symbol call
args: Array{Any}((3,))
1: Symbol !=
2: Symbol i
3: Int64 0 <we want to put our expressions here!>
2: Expr |
head: Symbol block v
args: Array{Any}((2,)) <---- <while loop body>
1: LineNumberNode
line: Int64 1
file: Symbol none
2: Expr
head: Symbol -=
args: Array{Any}((2,))
1: Symbol i
2: Int64 1
Эй, эй! Мы нашли тело цикла while. Помещение нашего выражения в тело самого последнего while выражения в нашем стеке циклов всегда будет помещать наше выражение в правильную область видимости, так как все циклы, которые уже завершились, были извлечены из стека и помещены в список выражений к настоящему моменту. На этом мы обработали все наши инструкции и готовы отправить их в тело функции.
4. Собираем все вместе
Поприветствуйте GalaxyBrain.jl:
Давайте завершим вызов макроса и запустим несколько примеров.
Некоторые ключевые дополнения:
- Отфильтруйте любые инструкции, которые не являются действительными инструкциями Brainfuck.
- Найдите тело функции и добавьте туда наши инструкции.
- Добавьте
return nothing, потому что я любитель YASGuide.
Чтобы проверить, что мы возвращаем полное определение функции, давайте создадим программу, которая использует каждую инструкцию хотя бы один раз. Используя @macroexpand, мы видим, что сгенерировали правильную функцию:
julia> @macroexpand bf">,<-[+>[<.]]" <not a meaningful program>
quote
function ($(Expr(:parameters, <formatted for medium>
:(input::Union{IO, AbstractString}=""),
:(output::IO=stdout),
:(index::Int=1),
:(memory_size::Int=30000))),)
memory = repeat([zero(UInt8)], memory_size)
characters = if input isa AbstractString
IOBuffer(input)
else
input
end
index += 1
memory[index] = if eof(characters)
memory[index]
else
first(read(characters, 1))
end
index -= 1
memory[index] -= one(UInt8)
while !(iszero(memory[index]))
memory[index] += one(UInt8)
index += 1
while !(iszero(memory[index]))
index -= 1
print(output, Char(memory[index]))
end
end
return nothing
end
end
Вот и все! Полностью встроенный транспилятор Brainfuck-to-Julia, занимающий менее 80 строк. Давай проверим.
Мы можем объявить buffer = IOBuffer() и передать его в качестве точки вывода нашей программе, что позволит нам проверить, дает ли программа правильный результат. Начнем с программы «Hello World» из раздела примеров Википедии.
Боковое примечание: поскольку массив памяти инициализирует каждое значение до 0, программы Brainfuck всегда будут пропускать первую инструкцию цикла, что позволяет нам вводить любые символы внутри цикла. «Заголовки комментариев» - обычное дело.
Теперь давайте введем программу и посмотрим, как она работает.
Прохладный! Но можем ли мы пойти глубже?
5. Взгляд в бездну: вложение программ внутри программ
Эта программа не является интерпретатором времени выполнения, и я принял это решение на раннем этапе, потому что я считал, что существуют способы перевода Brainfuck, которые задействуют сильные стороны Джулии как языка и позволяют получить уникальный конечный продукт. Но что, если бы мы решили, что действительно действительно хотим написать интерпретатор для Brainfuck на Julia? Для этого мы могли бы довольно легко переписать наш код, но несколько дней назад у меня возникла мысль:
Кто-нибудь написал интерпретатор Brainfuck в Brainfuck?
Да, у кого-то есть. Вот последний штрих: интерпретатор Brainfuck, написанный на Brainfuck, транслировался в Джулию, обрабатывая его ввод, который сам по себе является второй программой Brainfuck и его вводом.
Мне больше нечего добавить. Это очень глупый пакет.
6. Часто задаваемые вопросы и ресурсы
часто задаваемые вопросы
Каковы ограничения транспайлера?
Я попытался найти баланс между соблюдением исходных ограничений языка (размер памяти по умолчанию, чтение ввода на побайтовой основе), в то же время конкретизируя некоторые параметры для удобства и гибкости (настраиваемый ввод-вывод / источники, регулируемый размер памяти, интерпретация байтов как без знака вместо подписи и т. д.). Это означает, что программный ввод-вывод обычно ограничивается символами ASCII. Кроме того, я не реализую какую-либо обработку границ памяти, выбрасывая ошибку, если программа выходит за пределы - вызывающий функцию должен выделить достаточно большой массив для выполнения своей функции. Это были компромиссы, которые я чувствовал себя комфортно, принимая во внимание масштабы этого проекта.
Какая ваша любимая интерпретация устного перевода?
Я лично большой поклонник реализации Rust, в которой используются сильные стороны Rust как языка в отношении сопоставления с образцом.
Почему вы не использовали никаких оптимизационных стратегий?
Мне это не потребовалось - поскольку функция генерируется до времени компиляции, компилятор Джулии достаточно умен, чтобы выполнить за меня многие из описанных в статье оптимизаций. Первые два примера включают объединение групп похожих инструкций в одну инструкцию. Вот что делает компилятор Джулии:
julia> a = function (x); x += 1; x += 1; return x; end #13 (generic function with 1 method) julia> @code_llvm a(3) ; @ none:1 within `#13' define i64 @"julia_#13_17607"(i64) { top: ; ┌ @ int.jl:53 within `+' %1 = add i64 %0, 2 <-- <one instruction, not two> ; └ ret i64 %1 } julia> b = function (x); x[1] += 1; x[1] += 1; return x[1]; end #19 (generic function with 1 method) julia> @code_llvm b([1, 2]) ; @ none:1 within `#19' define i64 @"julia_#19_17627"(%jl_value_t addrspace(10)* nonnull align 16 dereferenceable(40)) { top: ; <miscellaneous indexing instructions> oob: ; preds = %top <bounds checking instructions> idxend8: ; preds = %top %8 = bitcast %jl_value_t addrspace(11)* %1 to i64 addrspace(13)* addrspace(11)* %9 = load i64 addrspace(13)*, i64 addrspace(13)* addrspace(11)* %8, align 8 %10 = load i64, i64 addrspace(13)* %9, align 8 ; └ ; ┌ @ int.jl:53 within `+' %11 = add i64 %10, 2 <-- <again, one instruction instead of two!> ; └ ; ┌ @ array.jl:782 within `setindex!' store i64 %11, i64 addrspace(13)* %9, align 8 ; └ ret i64 %11 }
Статью по оптимизации по-прежнему интересно читать, и вам следует изучить аналогичные стратегии для любой программы, которую вы пишете - просто так случилось, что она мне не нужна, и у меня были инструменты для проверки.
Не могли бы вы просто вернуть выражение с помощью `lex` вместо` parse`? Почему бы не сделать это вместо этого?
Это был скорее стилистический выбор. Я обнаружил, что мой код лучше всего читается, когда я сопоставляю каждый символ с определенной инструкцией, а затем эта инструкция становится выражением. Промежуточное представление делает функцию parse_instructions очень простой для чтения, позволяя мне использовать isa, который отлично подходит для того, чтобы ваш код читался как проза.
Почему?
Это было там, никто этого не делал, и это казалось забавным. Я начал программировать не ради радости - как многие люди, окончившие бакалавриат по CS, я делал это в надежде, что у меня будет стабильная карьера. Я думаю, это вполне веская причина для вступления в эту область, но может быть полезно находить радость в программировании на этом пути, даже если вы начали не с этого.
Не искушай меня.
Ресурсы
Если вы хотите проверить еще несколько забавных примеров и увидеть полный исходный код, вот еще раз GalaxyBrain.jl.
Спасибо за прочтение. Вот где вы можете меня найти:
"YouTube"
