![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
A fast interpreter in < 90 lines
У меня новая игрушка. Недавно в рамках праздных раздумий о языкостроении пошел я с пустым ведром зачерпнуть мудрости у лиспоакадемиков. Стал смотреть на Racket (который вырос из PLT Scheme), почитал книжку Beautiful Racket и немного поигрался с описанными там инструментами. А тут еще как раз Racket 8 вышел с новым бэкендом. В предыдущих версиях там компилятор делал байткод, а тот уже в рантайме JITился. А в 8.0 они перешли на компилятор и бэкенд от Chez Scheme, где сразу нативный код генерится.
Сам Racket преподносится как платформа для создания языков. И стандартный рецепт, которому придерживается Beautiful Racket, это если захотел ты сделать свой бэйсик, то регистрируешь свой пакет basic из двух определенных частей (парсер и экспандер), потом пишешь исходник на бейсике, ставишь в нем первой строчкой #lang basic и используешь компилятор Racket. Тот видит первую строчку, достает твой пакет, скармливает остаток файла твоему парсеру (тут у тебя полная свобода по синтаксису), твой парсер производит parse tree, которое передается второй части твоего пакета, которая то дерево преобразует в дерево кода на самом Рэкете. Полученный код на Рэкете уже компилируется, и вот твой бэйсик и скомпилирован.
Но есть один момент, который та книжка почти не упоминает, но который позволяет не опираться на компилятор Рэкета. Дело в том, что в Рэкете есть eval, и вся машинерия компилятора уже содержится в твоем бинарнике. Можно сделать свой один бинарник, который будет парсить новый язык, также разворачивать его в конструкции Рэкета, и тут же выполнять через eval. Под капотом там генерация нативного кода, и скорость получается ничуть не хуже.
В качестве proof of concept сделаем интерпретатор, который сможет выполнять код такого вида:
Назовем его silly. Это младший брат языка SIL, что я на работе делаю, только в оригинале точки с запятой не нужны, но тут проще было парсер сделать с ними. Для парсинга используем библиотеку brag из книжки. Достаточно сделать вот такой файл grammar.rkt:
Префиксы s- никто не заставлял делать, это я выбрал такую нотацию, чтобы в получаемых деревьях отличать узлы нашего AST от других конструкций. Если этот файл импортировать в нашу программу, то волшебным образом будет доступна функция parse, которая из потока токенов делает дерево нужного вида,
например "f(x,y) => { a = 1; b = 2 in x+b }" распарсится в s-expression
Но чтобы parse использовать, нужно ей передать лексер, который произведет поток токенов из входного потока, будь то строка или файл. Выглядит он так:
Тут простые комбинаторы, работающие как регекспы, матчат поток символов и для разных вариантов мы говорим, какой токен произвести.
Интерпретатор будет брать из командной строки имя файла с исходником на нашем языке, читать его и исполнять, заодно замеряя время исполнения (включая парсинг). Если имя файла не передали, выполним свою заготовку.
Тут (parse (tokenize input)) производит AST дерево, a (eval stx ns) выполняет его в нэймспейсе ns, в котором все узлы вроде s-fundef, s-block, s-assn, s-expr и print имеют смысл, а ничего лишнего там не будет. Для этого опишем подмодуль, где эти штуки определены, и его задействуем в качестве оного нэймспейса. И здесь трюк в том, что s-fundef, s-block, s-assn и т.п. это будут макросы, которые будут раскрываться в код на Рэкете (возможно, через другие макросы). Используя макросоописательные средства из книжки, выглядит это так:
Макросы такой формы матчат деревья заданного вида (маленькими буквами и литералами обозначается то, что в дереве должно стоять на заданном месте, большими буквами - переменные, принимающие любое значение/поддерево), и внутри #' отдают новые деревья или значения. Переменная с троеточием после нее означает последовательность, и в дереве-ответе тоже может задавать последовательность, в том числе преобразованную. Так (s-prog a b c d) здесь превратится в (begin (s-top a) (s-top b) (s-top c) (s-top d)). А (s-top something) уже раскрывается в разные вещи в завимости от something. Тут у меня top-level определения функций и констант раскрываются не так, как внутри блока с кодом. Например, "a = 1" в top-level превратится в (define a 1), а внутри блока в (let ((a 1)) остаток-блока).
print здесь не макрос, а обычная функция, выводящая на экран все аргументы в виде списка. Нам не обязательно все макросами описывать, мы можем любые функции в неймспейс для нашего интерпретируемого языка добавлять.
Еще момент: в грамматике есть правило для if then else, но тут мы его не упоминаем, т.к. "if a then b else c" парсер вернет как (if a b c), что уже годное выражение для Рэкета.
Собственно, это вся реализация. Весь код в двух файлах, 72 и 15 строк.
Делаем бинарник командой raco exe -o silly.exe silly.rkt.
Запускаем
где pi.txt
Цикл на 100 миллионов итераций с целочисленной и вещественной арифметикой, с работающей оптимизацией хвостовых вызовов. Работает 2.6 секунды. Аналогичный цикл на Питоне 3.7.5
у меня работает 30 секунд, более чем в 10 раз медленнее.
Похожий цикл на Ruby 3.0
у меня работает 16 секунд. Заметно быстрее Питона, но наш интерпретатор в 90 строк все равно в разы быстрее.
До полноценно типизированного нативного кода еще далеко, конечно, скомпилированная программа на Хаскеле тот цикл делает за полсекунды, еще в 5 раз быстрее. Но для интерпретатора все ж неплохо.
Еще занятный момент. Когда говорят про лисп, первым делом вспоминают гомоиконность, что дескать он такой удобный для преобразования программ за счет того, что синтаксис кода совпадает с синтаксисом данных, этот код описывающих. Но в Рэкете от этого по сути ушли. Парсер в Рэкете производит отнюдь не обычные списки с атомами, числами, строками и другими списками, и макросы на входе и на выходе тоже имеют дело не с обычными списками и атомами. Парсер производит syntax object, и все макросы на входе и на выходе имеют syntax object, который хотя по структуре своей и повторяет структуру дерева кода, но является совершенно отдельным типом данных, с множеством дополнительной информации. В первую очередь о том, где что было в оригинальном исходнике, чтобы если вдруг какая ошибка (не только при парсинге, но и при разворачивании), не говорить "у вас все сломалось где-то", а показать где именно. Т.е. у нас есть обычные деревья из списков, а есть отдельный тип для AST. И разница с другими языками, где можно оперировать AST, уже не так велика.
Сам Racket преподносится как платформа для создания языков. И стандартный рецепт, которому придерживается Beautiful Racket, это если захотел ты сделать свой бэйсик, то регистрируешь свой пакет basic из двух определенных частей (парсер и экспандер), потом пишешь исходник на бейсике, ставишь в нем первой строчкой #lang basic и используешь компилятор Racket. Тот видит первую строчку, достает твой пакет, скармливает остаток файла твоему парсеру (тут у тебя полная свобода по синтаксису), твой парсер производит parse tree, которое передается второй части твоего пакета, которая то дерево преобразует в дерево кода на самом Рэкете. Полученный код на Рэкете уже компилируется, и вот твой бэйсик и скомпилирован.
Но есть один момент, который та книжка почти не упоминает, но который позволяет не опираться на компилятор Рэкета. Дело в том, что в Рэкете есть eval, и вся машинерия компилятора уже содержится в твоем бинарнике. Можно сделать свой один бинарник, который будет парсить новый язык, также разворачивать его в конструкции Рэкета, и тут же выполнять через eval. Под капотом там генерация нативного кода, и скорость получается ничуть не хуже.
В качестве proof of concept сделаем интерпретатор, который сможет выполнять код такого вида:
fac(n) => if n < 2 then 1 else n * fac(n-1);
fib(n) =>
if n < 2 then 1
else {
a = fib(n-1);
b = fib(n-2)
in a + b
};
loop(x) =>
if x < 20 then {
print(fib(x), fac(x))
in loop(x+1)
} else 0;
loop(1)
Назовем его silly. Это младший брат языка SIL, что я на работе делаю, только в оригинале точки с запятой не нужны, но тут проще было парсер сделать с ними. Для парсинга используем библиотеку brag из книжки. Достаточно сделать вот такой файл grammar.rkt:
#lang brag
s-prog: s-stmt (/";" s-stmt)*
@s-stmt: s-assn | s-fundef | s-expr
s-funcall: NAME /"(" [s-expr (/"," s-expr)*] /")"
s-fundef: NAME /"(" [NAME (/"," NAME)* ] /")" "=>" s-expr
s-block: /"{" [s-stmt (/";" s-stmt)* /"in"] s-expr /"}"
s-assn: NAME /"=" s-expr
s-expr: s-compterm | if
if: /"if" s-expr /"then" s-expr /"else" s-expr
s-compterm: s-term [("<" | "==") s-term]
s-term: [s-term ("+" | "-")] s-summand
s-summand: [s-summand ("*" | "/")] s-factor
@s-factor: s-funcall | s-block | NUMBER | s-name | "-" s-summand | s-parens
@s-parens: /"(" s-expr /")"
s-name: NAME
Префиксы s- никто не заставлял делать, это я выбрал такую нотацию, чтобы в получаемых деревьях отличать узлы нашего AST от других конструкций. Если этот файл импортировать в нашу программу, то волшебным образом будет доступна функция parse, которая из потока токенов делает дерево нужного вида,
например "f(x,y) => { a = 1; b = 2 in x+b }" распарсится в s-expression
'(s-prog
(s-fundef
f
x
y
"=>"
(s-expr
(s-compterm
(s-term
(s-summand
(s-block
(s-assn a (s-expr (s-compterm (s-term (s-summand 1)))))
(s-assn b (s-expr (s-compterm (s-term (s-summand 2)))))
(s-expr (s-compterm (s-term (s-term (s-summand (s-name x))) "+" (s-summand (s-name b))))))))))))
Но чтобы parse использовать, нужно ей передать лексер, который произведет поток токенов из входного потока, будь то строка или файл. Выглядит он так:
(define-lex-abbrev digits (:+ numeric))
(define-lex-abbrev reserved-terms
(:or "+" "-" "*" "/" "=" "in" ";" "{" "}" "(" ")" "," "=>" "if" "then" "else" "==" "<"))
(define (tokenize ip)
(port-count-lines! ip)
(define my-lexer
(lexer-srcloc
[whitespace (token lexeme #:skip? #t)]
[reserved-terms (token lexeme lexeme)]
[(:seq digits "." digits)
(token 'NUMBER (exact->inexact (string->number lexeme)))]
[digits (token 'NUMBER (string->number lexeme))]
[(:seq alphabetic (:* (:or alphabetic numeric)))
(token 'NAME (string->symbol lexeme))]
[(eof) (void)] ))
(lambda () (my-lexer ip)))
Тут простые комбинаторы, работающие как регекспы, матчат поток символов и для разных вариантов мы говорим, какой токен произвести.
Интерпретатор будет брать из командной строки имя файла с исходником на нашем языке, читать его и исполнять, заодно замеряя время исполнения (включая парсинг). Если имя файла не передали, выполним свою заготовку.
(require 'm)
(define ns (namespace-anchor->namespace anchor))
(define (run input)
(define stx (parse (tokenize input)))
(eval stx ns))
(define argv (current-command-line-arguments))
(if ((vector-length argv) . > . 0)
(time (run (open-input-file (vector-ref argv 0))))
(run (open-input-string "print(4, 6, 2+2*3)")))
Тут (parse (tokenize input)) производит AST дерево, a (eval stx ns) выполняет его в нэймспейсе ns, в котором все узлы вроде s-fundef, s-block, s-assn, s-expr и print имеют смысл, а ничего лишнего там не будет. Для этого опишем подмодуль, где эти штуки определены, и его задействуем в качестве оного нэймспейса. И здесь трюк в том, что s-fundef, s-block, s-assn и т.п. это будут макросы, которые будут раскрываться в код на Рэкете (возможно, через другие макросы). Используя макросоописательные средства из книжки, выглядит это так:
(module m br
(provide anchor)
(define-namespace-anchor anchor)
(define-macro-cases s-term
[(_ VAL) #'VAL]
[(_ LEFT "+" RIGHT) #'(+ LEFT RIGHT)]
[(_ LEFT "-" RIGHT) #'(- LEFT RIGHT)])
(define-macro-cases s-summand
[(_ VAL) #'VAL]
[(_ LEFT "*" RIGHT) #'(* LEFT RIGHT)]
[(_ LEFT "/" RIGHT) #'(/ LEFT RIGHT)]
[(_ "-" VAL) #'(- VAL)])
(define-macro-cases s-compterm
[(_ VAL) #'VAL]
[(_ LEFT "<" RIGHT) #'(< LEFT RIGHT)]
[(_ LEFT "==" RIGHT) #'(eq? LEFT RIGHT)])
(define-macro (s-name X) #'X)
(define-macro (s-expr X) #'X)
(define-macro (s-prog STMT ...) #'(begin (s-top STMT) ... ))
(define-macro-cases s-top
[(s-top (s-assn V E)) #'(define V E)]
[(s-top (s-fundef FUN VS ... "=>" E)) #'(define (FUN VS ...) E)]
[(s-top (s-expr E)) #'E])
(define-macro-cases s-block
[(s-block E) #'E]
[(s-block (s-assn VAR VAL) MORE ... E) #'(let ((VAR VAL)) (s-block MORE ... E))]
[(s-block (s-fundef FUN VS ... "=>" VAL) MORE ... E)
#'(begin (define (FUN VS ...) VAL) (s-block MORE ... E))]
[(s-block (s-expr VAL) MORE ... E)
#'(begin VAL (s-block MORE ... E))])
(define-macro (s-funcall FUN ARGS ...) #'(FUN ARGS ...))
(define (print . xs) (displayln xs))
)
Макросы такой формы матчат деревья заданного вида (маленькими буквами и литералами обозначается то, что в дереве должно стоять на заданном месте, большими буквами - переменные, принимающие любое значение/поддерево), и внутри #' отдают новые деревья или значения. Переменная с троеточием после нее означает последовательность, и в дереве-ответе тоже может задавать последовательность, в том числе преобразованную. Так (s-prog a b c d) здесь превратится в (begin (s-top a) (s-top b) (s-top c) (s-top d)). А (s-top something) уже раскрывается в разные вещи в завимости от something. Тут у меня top-level определения функций и констант раскрываются не так, как внутри блока с кодом. Например, "a = 1" в top-level превратится в (define a 1), а внутри блока в (let ((a 1)) остаток-блока).
print здесь не макрос, а обычная функция, выводящая на экран все аргументы в виде списка. Нам не обязательно все макросами описывать, мы можем любые функции в неймспейс для нашего интерпретируемого языка добавлять.
Еще момент: в грамматике есть правило для if then else, но тут мы его не упоминаем, т.к. "if a then b else c" парсер вернет как (if a b c), что уже годное выражение для Рэкета.
Собственно, это вся реализация. Весь код в двух файлах, 72 и 15 строк.
Делаем бинарник командой raco exe -o silly.exe silly.rkt.
Запускаем
> silly.exe pi.txt cpu time: 2609 real time: 2596 gc time: 125 3.1415926380318524
где pi.txt
f(n, res) =>
if 200000000 < n then res
else f(n+2, res*n*n/((n+1)*(n-1)));
f(2, 2.0)
Цикл на 100 миллионов итераций с целочисленной и вещественной арифметикой, с работающей оптимизацией хвостовых вызовов. Работает 2.6 секунды. Аналогичный цикл на Питоне 3.7.5
res = 2.0 for n in range(2, 200000000, 2): res = res*n*n/((n+1)*(n-1)) print(res)
у меня работает 30 секунд, более чем в 10 раз медленнее.
Похожий цикл на Ruby 3.0
res = 2.0 n = 2 for i in 0..100000000 res = res*n*n/((n+1)*(n-1)) n += 2 end print(res)
у меня работает 16 секунд. Заметно быстрее Питона, но наш интерпретатор в 90 строк все равно в разы быстрее.
До полноценно типизированного нативного кода еще далеко, конечно, скомпилированная программа на Хаскеле тот цикл делает за полсекунды, еще в 5 раз быстрее. Но для интерпретатора все ж неплохо.
Еще занятный момент. Когда говорят про лисп, первым делом вспоминают гомоиконность, что дескать он такой удобный для преобразования программ за счет того, что синтаксис кода совпадает с синтаксисом данных, этот код описывающих. Но в Рэкете от этого по сути ушли. Парсер в Рэкете производит отнюдь не обычные списки с атомами, числами, строками и другими списками, и макросы на входе и на выходе тоже имеют дело не с обычными списками и атомами. Парсер производит syntax object, и все макросы на входе и на выходе имеют syntax object, который хотя по структуре своей и повторяет структуру дерева кода, но является совершенно отдельным типом данных, с множеством дополнительной информации. В первую очередь о том, где что было в оригинальном исходнике, чтобы если вдруг какая ошибка (не только при парсинге, но и при разворачивании), не говорить "у вас все сломалось где-то", а показать где именно. Т.е. у нас есть обычные деревья из списков, а есть отдельный тип для AST. И разница с другими языками, где можно оперировать AST, уже не так велика.