Как я сделал свой язык программирования Tokype

Всем привет! Сегодня я расскажу о своём пет-проекте на Go - Tokype, покажу результаты бенчмарков, а также раскрою его главный секрет.

Tokype - это интерпретатор, который парсит код в AST и выполняет его, обходя узлы дерева. Обычно чистые AST выполняются дольше, чем языки с байт-кодом (например, Python, Lua, PHP) или JIT-компиляцией (LuaJIT, Java, JavaScript, C#).

Мой язык сначала был медленным. Он мог выполнять код в 3-5 раз медленнее Python (прошлые тесты я не могу предоставить. Их результаты потерялись). Я не умел и не умею делать компилятор байт-кода или JIT-компилятор, поэтому я пошёл другим путём.

Сейчас многие языки используют байт-код компиляторы (у Lua - luac, у Erlang - erlc, у Java - javac). Они превращают код в байты. Этот байт-код выполняется в виртуальной машине языка программирования, что делает код быстрее, но не настолько, чтобы выдавать скорость компилируемых языков (вроде C++ или Go).

это очень мощная оптимизация для интерпретаторов. JIT (Just-In-Time) компилирует байт-код в машинный код, что делает код быстрее, но он компилирует не всё, только "горячие зоны" (циклы, часто вызываемые функции). Это даёт высокий прирост скорости выполнения. Но чтобы получить максимальную скорость, JIT надо "разогреть", тогда он даст высокую оптимизацию.

Поскольку я не умею делать компиляторы байт-кода и JIT, я подумал: "А можно ли встроить оптимизатор компиляторов в интерпретатор? И какую скорость тогда получит мой Tokype?".

Я решил этому оптимизатору сделать название, и я выбрал TitanJerboa(титан-тушканчик). Jerboa(тушканчик) я выбрал потому что это быстрый зверёк из семейства тушканчиковых, а Titan(титан) для солидности.

Самая базовая, но очень полезная оптимизация. Если в коде есть выражение, которое можно вычислить прямо сейчас - зачем вычислять его в рантайме?

Было:

x = 7 + 6 + 5 y = x * 2 + 10

Стало:

x = 18 y = 46

Как это работает:

func (o *Optimizer) evaluateConstant(expr ast.Expression) ast.Expression { tempEnv := evalut.NewEnvironment() result := evalut.Eval(expr, tempEnv) if !o.hasVariables(expr) { return o.valueToLiteral(result) } return nil }

То есть всё, что можно посчитать на этапе анализа - считается. Это касается не только арифметики, но и логических выражений, строковых конкатенаций и так далее.

Эта оптимизация смотрит на if/elif/else и циклы. Если условие вычисляется в константу, зачем тащить в исполняемый код все ветки? Оставляем только ту, которая реально сработает.

Как это выглядит в коде:

func (o *Optimizer) simplifyIf(ifExpr *ast.IfExpression) ast.Node { result := evalut.Eval(ifExpr.Condition, tempEnv) if result.Type == value.ValBool && !o.hasVariables(ifExpr.Condition) { if result.Bool { return ifExpr.Consequence } else { return ifExpr.Else } } return ifExpr }

То есть если условие всегда истинно или всегда ложно, мы просто заменяем весь if на одну из его веток. В рантайме интерпретатор даже не увидит, что там был какой-то выбор. С циклами аналогично: если условие заведомо ложно, цикл превращается в пустой блок.

Здесь всё просто. Если код никогда не достижим (например, после return или внутри условия, которое всегда false), он удаляется.

Представьте, что вы заполняете список в цикле:

arr = [] for i = 1, 1000000: push(arr, 42) end

Вместо того чтобы выполнять миллион итераций, оптимизатор замечает этот паттерн и превращает его в одно действие:

arr = repeat(42, 1000000)

Как это реализовано:

func (o *Optimizer) optimizeListCreation(forStmt *ast.ForStatement) ast.Node { if len(forStmt.Body.Statements) == 1 { call, ok := forStmt.Body.Statements[0].(*ast.CallExpression) if ok && call.Function.Value == "push" { count := endVal.Value - startVal.Value + 1 return &ast.CallExpression{ Function: &ast.Identifier{Value: "repeat"}, Arguments: []ast.Expression{value, &ast.IntegerLiteral{Value: count}}, } } } return forStmt }

Сложность падает с O(n) до O(1). Вот это я называю оптимизацией!

Если вы в цикле считаете сумму чисел от 1 до N, зачем гонять процессор через все итерации? Формула Гаусса была придумана не зря.

Было:

sum = 0 for i = 1, 1000000: sum = sum + i end

Стало:

sum = 500000500000

Интерпретатор даже не увидит цикл - он получит готовое число.

Вложенные циклы - это боль. Особенно когда они оба итерируются по константам.

Было:

for i = 1, 1000: for j = 1, 1000: sum = sum + j end end

Стало:

for j = 1, 1000000: sum = sum + j end

Реализация:

func (o *Optimizer) mergeNestedLoop(outerLoop *ast.ForStatement) ast.Node { innerLoop := outerLoop.Body.Statements[0].(*ast.ForStatement) outerCount := outerEnd - outerStart + 1 innerCount := innerEnd - innerStart + 1 totalCount := outerCount * innerCount newCondition := &ast.InfixExpression{ Left: &ast.Identifier{Value: innerLoop.Initialization.Name.Value}, Operator: "<=", Right: &ast.IntegerLiteral{Value: totalCount}, } innerLoop.Condition = newCondition return innerLoop }

Вместо миллиона итераций получаем... ну, технически всё ещё миллион, но с одним циклом вместо двух. На практике это даёт прирост за счёт уменьшения накладных расходов на переходы между циклами.

Вызов функции - это дорого. Особенно если функция маленькая и вызывается часто. Инлайнинг заменяет вызов функции на её тело.

Было:

funct add(a, b): return a + b end add(5, 3)

Стало:

return 5 + 3

А потом в дело вступает свёртка констант, и мы получаем:

return 8

В результате интерпретатор даже не знает, что в коде была функция - он просто выполняет её тело как обычные инструкции. Прирост скорости может быть огромным, особенно в циклах.

Всё просто: если функция внутри пустая, она удаляется.

funct empty(): end

Такую функцию просто вырезаем из программы. Зачем хранить то, что не делает ничего полезного?

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

P.S. Он всё считает и оптимизирует ДО начала запуска кода.

И теперь мы подошли к самому главному - бенчмаркам.

funct main(): n = 10000000 start = get_time() a = 1 b = 2 sum = 0 for i = 1, n: sum = sum + a * b + i end print(sum) stop = get_time() print("Time: " + (stop - start) + " sec") end main()

Терминал:

50000025000000 Time: 0 sec

funct main(): n = 1000000 start = get_time() sum = 0 for i = 1, n: sum = sum + i end print(sum) stop = get_time() print("Time: " + (stop - start) + " sec") end main()

Терминал:

500000500000 Time: 0 sec

funct main(): n = 1000 start = get_time() sum = 0 for i = 1, n: for j = 1, n: sum = sum + i * j end end print(sum) stop = get_time() print("Time: " + (stop - start) + " sec") end main()

Терминал:

250500250000 Time: 0 sec

funct main(): n = 1000 start = get_time() a = 0 b = 0 c = 0 for i = 1, n: for j = 1, n: a = i + j b = i * j c = a + b end end print(c) stop = get_time() print("Time: " + (stop - start) + " sec") end main()

Терминал:

1002000 Time: 0 sec

Да, все бенчмарки показывают 0 секунд. Это не потому, что интерпретатор супербыстрый, а потому что оптимизатор вырезал все циклы ещё до запуска.

Я рассказал почти всё о своём языке. Больше можно узнать в README в моём репозитории GitHub. А также мой язык унаследовал несколько функций из Go (например, многопоточность, +Inf / -Inf, NaN).

Репозиторий

github.com

GitHub - MrArtem5/Tokype: Tokype is an interpreted programming language that traverses the AST but features its own optimizer, providing a performance boost.

Надеюсь, вы оцените мой проект.

К версии 0.0.3 я хочу добавить:
1. Импорт соседних файлов.
2. Импорт библиотек.
3. Встроенные библиотеки.
4. Сделать стабильнее.
5. Добавить значение Null.

Как я сделал свой язык программирования Tokype

Справка для тех, кто не знает, что такое байт-код, JIT-компилятор

Компилятор байт-кода:

JIT-компилятор (Just-in-time):

Что входит в TitanJerboa?

constantFold (свёртывание констант)

optimizeControlFlow (оптимизация if/elif/else, а также for/while)

removeDeadCode (удаление мёртвого кода)

optimizeCollections (оптимизация списков)

foldArithmeticProgression (сворачивание арифметических прогрессий)

mergeNestedLoop (объединение вложенных циклов)

inlineFunctionCalls (инлайнинг функций)

removeEmptyFunctions (Удаление пустых функций)

Результаты бенчмарков

Бенчмарк 1:

Бенчмарк 2:

Бенчмарк 3:

Бенчмарк 4:

Предупреждение!

Tokype пока нестабилен из-за оптимизатора. Для продакшена пока не рекомендуется, но для экспериментов - самое то.