Пишем неправильный компилятор. Часть 0
Последние две недели пролетели в крайне интересном занятии: написании компилятора. Язык еще будет расти и облагораживаться, но все главное и основное уже реализовано и работает, теперь можно рассказать.
Сперва о результате. Пример компилирующегося и работающего кода:
nat = new byte[20]
for i in nat.range nat[i] <- i + 1 end # теперь в nat числа от 1 до 20
map(f, xs) = { # составной оператор заключается в {...} или do ... end
t = new int[ |xs| ]
for i in xs.range, x in xs
t[i] <- f(x)
end
t
}
iter(f, xs) = for x in xs f(x) end # применить функцию f ко всем элементам xs
show(xs) = iter(\x -> print(x), xs) # вывод всех элементов. первый параметр - лямбда
even = map(\x -> 2 * x, nat)
# even - массив интов с четными числами от 2 до 40
show(even) # выводит 2 4 6 ... 40
show(1..10) # выводит 1 2 3 ... 10
# 1..10 - это не массив и не список, это интервал, заданный двумя числами.
sq(x) = x * x
squares = map(sq, 1..10) # теперь массив squares содержит 1 4 9 .. 100
sum(xs) = do
loop(s, xs) = if |xs| > 0 then loop(xs.head + s, xs.tail) else s
loop(0, xs)
end
print( sum(1..10) ) # выводит 55
print( sum(nat) ) # выводит 210
print( sum(squares ) ) # выводит 385
squares[3..7] <- nat[0..4] # копирует 5 элементов из nat в squares
m = new int[9]
m <- squares # копирует 9 элементов из squares в m
rng = 6..9
m[rng] <- even[rng]
show(m) # выводит 1 4 9 1 2 3 14 16 18
Пояснения:
|xs| - число элементов в xs.
xs.range - это 0, 1, 2 ... |xs|-1.
xs.head - первый элемент xs, xs.tail - элементы со второго по последний. Применимы и к массивам, и к последовательностям (интервалам).
Здесь в map передается функция по имени и в виде лямбды. А sum вызывается с аргументами трех разных типов - массив байт, массив интов и последовательность чисел, заданная началом и концом.
Синтаксис с минимумом шума, но без чувствительности к отступам. Вдохновлен Руби и ML. Стейтменты разделяются переходом на следующую строчку или точкой с запятой. Аргументы функций записываются в скобках, так ближе к математике и мэйнстримным языкам.
Типизация статическая. Как видите, имеется вывод типов, функции высшего порядка, параметрический полиморфизм, автоматическое управление памятью. Выделение памяти О(1), освобождение О(0). Есть оптимизация хвостовой рекурсии - sum здесь работает в constant space. Язык императивный, но с некоторыми функциональными удобствами. Компилируется в байткод. Вся виртуальная машина и рантайм - сотня строк на Си. Скорость компиляции: данный пример разобрался и скомпилился за 0.05 секунды, типичные целевые программы также компилируются за сотые доли секунды. Скорость работы: втрое быстрее Lua и двое быстрее окамловского байткода (сравнивал на комплексном тесте с нахождением всех простых чисел до 10^7). Причем ВМ на базе while-switch, никакого шитого кода и computed gotos.
Язык специально заточен на низкоуровневую работу с массивами байт и интов. Применяться будет для защиты моего софта от крякеров путем переноса кода, разбор которого хочется усложнить, в байткод ВМ. Такую защиту успешно применяю уже несколько лет, но до этого момента виртуализируемый код писался на Си-образном DSEL на Руби с арифметикой указателей. DSEL, он конечно сильно гибкий и метапрограммистский, но его использование требовало сильного напряжения головного ганглия. И вообще, что это я, два года уже пишу на Окамле for fun & profit, а ни одного компилятора на нем еще не написал. :)
А, да. Сам компилятор написан на Окамле - ~1700 строк. При этом он вдоль и поперек неправильный. Как обычно компилируют подобные языки? Берется генератор парсеров, вроде яка, бизона или муравлера, им разбирают текст. Типы или заставляют описывать явно, или делают их вывод имени Хайнекен-Миллера Хиндли-Милнера. Для ФВП делают или первоклассные функции и замыкания, с представлением функций парой указатель-данные, или хотя бы объекты с виртуальными функциями. Для автоматического управления памятью делают сборку мусора или хотя бы подсчет ссылок. Для генерации кода используют промежуточное представление SSA. ВМ делают стековую или, реже, регистровую... Ничего этого у меня нет. А что есть вместо - расскажу в следующих постах.
Писался компилятор тоже неправильно. Как устроены все книжки на эту тему? Сначала парсим исходный текст, получаем дерево, потом из него промежуточное представление, из него целевой код. Это все здорово, конечно, когда делаешь очередной Паскаль или Джаву. А если четкой целевой платформы еще нет, хочется высокоуровневых фишек в языке, но совсем не хочется суперсложный рантайм с санками, кучами и сборщиками трупов мусора? Я так полгода назад начал, но сразу после разбора текста яком оказался перед пропастью между уровнями исходного языка и ВМ, так и бросил. Сейчас же пошел другим путем - снизу-вверх: сперва ВМ и ассемблер для нее, потом в нем ветвления и циклы, потом уже почти-Си с переменными, вложенными выражениями, описанием и вызовом функций, потом уже трансляцию AST исходного языка в этот недо-Си и лишь в последнюю очередь парсинг текста.
Ну и название, оно тоже неправильное. Приличные люди придумывают аббревиатуры или остроумные имена, часто повторяясь. Мой же язык назван в честь этого:
Зато, в отличие от гугла и многих других, я заглянул в список языков программирования и убедился, что такого имени еще не было.
Дальше: Часть 1. Як, слон и древесная крыса
Сперва о результате. Пример компилирующегося и работающего кода:
nat = new byte[20]
for i in nat.range nat[i] <- i + 1 end # теперь в nat числа от 1 до 20
map(f, xs) = { # составной оператор заключается в {...} или do ... end
t = new int[ |xs| ]
for i in xs.range, x in xs
t[i] <- f(x)
end
t
}
iter(f, xs) = for x in xs f(x) end # применить функцию f ко всем элементам xs
show(xs) = iter(\x -> print(x), xs) # вывод всех элементов. первый параметр - лямбда
even = map(\x -> 2 * x, nat)
# even - массив интов с четными числами от 2 до 40
show(even) # выводит 2 4 6 ... 40
show(1..10) # выводит 1 2 3 ... 10
# 1..10 - это не массив и не список, это интервал, заданный двумя числами.
sq(x) = x * x
squares = map(sq, 1..10) # теперь массив squares содержит 1 4 9 .. 100
sum(xs) = do
loop(s, xs) = if |xs| > 0 then loop(xs.head + s, xs.tail) else s
loop(0, xs)
end
print( sum(1..10) ) # выводит 55
print( sum(nat) ) # выводит 210
print( sum(squares ) ) # выводит 385
squares[3..7] <- nat[0..4] # копирует 5 элементов из nat в squares
m = new int[9]
m <- squares # копирует 9 элементов из squares в m
rng = 6..9
m[rng] <- even[rng]
show(m) # выводит 1 4 9 1 2 3 14 16 18
Пояснения:
|xs| - число элементов в xs.
xs.range - это 0, 1, 2 ... |xs|-1.
xs.head - первый элемент xs, xs.tail - элементы со второго по последний. Применимы и к массивам, и к последовательностям (интервалам).
Здесь в map передается функция по имени и в виде лямбды. А sum вызывается с аргументами трех разных типов - массив байт, массив интов и последовательность чисел, заданная началом и концом.
Синтаксис с минимумом шума, но без чувствительности к отступам. Вдохновлен Руби и ML. Стейтменты разделяются переходом на следующую строчку или точкой с запятой. Аргументы функций записываются в скобках, так ближе к математике и мэйнстримным языкам.
Типизация статическая. Как видите, имеется вывод типов, функции высшего порядка, параметрический полиморфизм, автоматическое управление памятью. Выделение памяти О(1), освобождение О(0). Есть оптимизация хвостовой рекурсии - sum здесь работает в constant space. Язык императивный, но с некоторыми функциональными удобствами. Компилируется в байткод. Вся виртуальная машина и рантайм - сотня строк на Си. Скорость компиляции: данный пример разобрался и скомпилился за 0.05 секунды, типичные целевые программы также компилируются за сотые доли секунды. Скорость работы: втрое быстрее Lua и двое быстрее окамловского байткода (сравнивал на комплексном тесте с нахождением всех простых чисел до 10^7). Причем ВМ на базе while-switch, никакого шитого кода и computed gotos.
Язык специально заточен на низкоуровневую работу с массивами байт и интов. Применяться будет для защиты моего софта от крякеров путем переноса кода, разбор которого хочется усложнить, в байткод ВМ. Такую защиту успешно применяю уже несколько лет, но до этого момента виртуализируемый код писался на Си-образном DSEL на Руби с арифметикой указателей. DSEL, он конечно сильно гибкий и метапрограммистский, но его использование требовало сильного напряжения головного ганглия. И вообще, что это я, два года уже пишу на Окамле for fun & profit, а ни одного компилятора на нем еще не написал. :)
А, да. Сам компилятор написан на Окамле - ~1700 строк. При этом он вдоль и поперек неправильный. Как обычно компилируют подобные языки? Берется генератор парсеров, вроде яка, бизона или муравлера, им разбирают текст. Типы или заставляют описывать явно, или делают их вывод имени Хайнекен-Миллера Хиндли-Милнера. Для ФВП делают или первоклассные функции и замыкания, с представлением функций парой указатель-данные, или хотя бы объекты с виртуальными функциями. Для автоматического управления памятью делают сборку мусора или хотя бы подсчет ссылок. Для генерации кода используют промежуточное представление SSA. ВМ делают стековую или, реже, регистровую... Ничего этого у меня нет. А что есть вместо - расскажу в следующих постах.
Писался компилятор тоже неправильно. Как устроены все книжки на эту тему? Сначала парсим исходный текст, получаем дерево, потом из него промежуточное представление, из него целевой код. Это все здорово, конечно, когда делаешь очередной Паскаль или Джаву. А если четкой целевой платформы еще нет, хочется высокоуровневых фишек в языке, но совсем не хочется суперсложный рантайм с санками, кучами и сборщиками трупов мусора? Я так полгода назад начал, но сразу после разбора текста яком оказался перед пропастью между уровнями исходного языка и ВМ, так и бросил. Сейчас же пошел другим путем - снизу-вверх: сперва ВМ и ассемблер для нее, потом в нем ветвления и циклы, потом уже почти-Си с переменными, вложенными выражениями, описанием и вызовом функций, потом уже трансляцию AST исходного языка в этот недо-Си и лишь в последнюю очередь парсинг текста.
Ну и название, оно тоже неправильное. Приличные люди придумывают аббревиатуры или остроумные имена, часто повторяясь. Мой же язык назван в честь этого:
Зато, в отличие от гугла и многих других, я заглянул в список языков программирования и убедился, что такого имени еще не было.
Дальше: Часть 1. Як, слон и древесная крыса