thedeemon | Entries tagged with leo

Я тут когда-то писал о компиляторе своего языка и виртуальной машине к нему. Сейчас он у нас активно используется для обработки видео, т.к. оказался очень удобен в связке с AviSynth. Однако ВМ там - простой интерпретатор байткода, потому все работало не слишком быстро: Y-PSNR для кадра 1920х1080 вычислялся около секунды. Решил прикрутить туда JIT-компиляцию. Взял AsmJit, посмотрел примеры, собрал простой тест, с первого взгляда все работает и выглядит неплохо. Но стоило взяться за дело( Read more... )

Делал недавно по просьбам общественности 64-битную версию своего нового плагина для VirtualDub. Собрать-то его для x64 проблем нет (разве что пару функций на асме с MMX пришлось выкинуть, на скорости это не отразилось), да только внутри у него ~~неонка~~ виртуальная машина, а в ней указатели и целые числа вперемешку хранятся и используются, так что пришлось ее перевести на int64. Добавил в компилятор новый режим - компиляция в 64 бита, там всех изменений - только работа с массивами, т.к. размер элементов другой. Плюс, добавил в Leo новый тип - int32, чтобы с RGB32 работать нормально (а обычный int сделался 64-битным). На простых тестах все заработало сразу, а "боевая" программа стала в 64-битном режиме падать. Там байткода на десятки тысяч команд, как узнать в чем ошибка? Стал добавлять в компилятор то, что обязано быть в каждом приличном компиляторе, но что обычно оставляют за кадром во всех книжках и примерах - протаскивание информации о координатах в исходнике через все фазы компиляции. Чтобы если ошибка происходит при IP=2345, знать, к какой строке исходной программы на Leo это относится.
( Read more... )

Давно хотел простой способ попиксельно работать с видео, теперь вот, когда очередной раз понадобилось, наконец организовал себе таковой. Сохраняю в текстовом редакторе скрипт, переоткрываю файл в VirtualDub и сразу вижу результат. Для этого потребовалось написать один маленький плагин для AviSynth, который берет в качестве параметра имя файла с исходником на Leo, при загрузке вызывает мой компилятор, тот выдает байткод, который плагин исполняет с помощью LeoVM при обработке каждого кадра. Ависинтовский скрипт выглядит так:
LoadPlugin("leovid.dll")
AviSource("source.avi").ConvertToRGB32().RunLeo("fire.leo")
Его-то я и открываю в VirtualDub'e.

В качестве теста вспомнил детство, когда мы во времена DOS'a и VGA мониторов дергали прерывание 10h для перехода в режим 13h (320x200, 256 цветов) и рисовали там всякие штуки, например, огонь. Помнится, на первом курсе мы соревновались у кого короче получится реализация - рисующая огонь программа занимала около сотни байт. Сейчас модифицировал его алгоритм, чтобы картинка исходного видео задавала вероятности и интенсивности появления источников огня, получился довольно симпатичный эффект:

( Видео )

В оригинале видео более зернистое, ютюб его размазал. Исходник эффекта.

Поскольку нерекурсивные функции в Leo раскрываются подстановкой, и лишь потом это дело типизируется и компилируется в LeoC, сам собой получился вариант лямбда-исчисления, позволяющий делать всякие штуки в compile-time. Поскольку язык лишь частично функциональный, в нем пока нет карринга и возможности возвращать функции, поэтому выглядит это не очень красиво, но терпимо. Пример:

# Church numerals
zero(f, x) = x
add1(n, f, x) = f(n(f, x))
add(a, b, f, x) = a(f, b(f, x))
mul(a, b, f, x) = a(\t -> b(f, t), x)

one(f, x) = add1(zero, f, x)
two(f, x) = add(one, one, f, x)
three(f, x) = add(one, two, f, x)
four(f, x) = add(two, two, f, x)
six(f, x) = mul(two, three, f, x)
seven(f, x) = add(four, three, f, x)
c42(f, x) = mul(six, seven, f, x)

inc(x) = x + 1
z = c42(inc, 0)
print(z)

Благодаря новым оптимизациям, все это компилируется в одну сточку LeoC: print(42). И, соответственно, одну команду ВМ.

Использовать это можно для генерации кода. Например, функция, которая в compile-time создает массив байтов и заполняет его значениями 1..n:

to_int(n) = n(inc, 0)

make(n) = do # на входе - число Черча с количеством требуемых элементов
  m = new byte[ to_int(n) ] # создать массив
  f(x) = { t = x+1; m[x] <- t; t }
  n(f, 0) # f будет вызван и подставлен n раз
  m # вернуть массив
end

ten(f,x) = add(four, six, f, x)
a = make(ten)
print(a[|a|-1])

Компилируется в такой код на LeoC:

var m_287
m_287 <- new [10]
$Mem[m_287] <-b- 1
$Mem[m_287 + 1] <-b- 2
$Mem[m_287 + 2] <-b- 3
$Mem[m_287 + 3] <-b- 4
$Mem[m_287 + 4] <-b- 5
$Mem[m_287 + 5] <-b- 6
$Mem[m_287 + 6] <-b- 7
$Mem[m_287 + 7] <-b- 8
$Mem[m_287 + 8] <-b- 9
$Mem[m_287 + 9] <-b- 10
var a
a <- m_287  
print(byte($Mem[a + 9]))

Ранее у меня была реализована простая оптимизация, когда арифметические операции с константами вычислялись при компиляции. Она работает в пределах выражения LeoC, чего раньше вполне хватало. В ходе прошлого рефакторинга код верхнего уровня компилятора (Leo -> LeoC) сильно сократился, потому что в ряде мест (циклы, присваивания) набор сочетаний частных случаев был заменен более универсальным кодом. Это привело к генерации менее оптимального результата, в частности, стало генериться много подобного кода LeoC:

bound_12 = 19
i_13 = 0
end_13 = bound_12 + 1
while i_13 < end_12 ...

Поэтому вчера добавил еще пару простых оптимизаций: copy propagation и удаление неиспользуемых переменных и вычислений. Первая заключается в том, чтобы пройтись по дереву сгенеренного LeoC-кода и для каждой встреченной переменной запоминать ее "значение":

type var_value =  Undefined | Copy of rvalue | Complex

Undefined она после объявления и до первого присваивания. Если в присваивании слева стоит переменная, а справа - константа или переменная, то для присваиваемой переменной запоминается, копией чего она является, в противном случае она помечается как Complex. Когда переменная встречается в выражении, смотрится ее "значение" и, если она содержит копию чего-то, то вместо нее подставляется это что-то. После этого выражение упрощается путем constant folding. Кроме этого контекст содержит множество переменных, измененных в текущем блоке кода. Когда встречается if с двумя блоками-ветками, то после него все измененные в ветках переменные помечаются как Complex, т.е. их значения перестают быть известными. Аналогично для цикла, только там сначала делается один проход по телу и собирается набор измененных переменных, а потом во втором проходе уже тело оптимизируется.

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

Вместе они добавили еще 170 строк к компилятору и, во-первых, сделали генерируемый код не таким позорным, а во-вторых, в сочетании с always-inline подходом к компиляции нерекурсивных функций позволили делать прикольные compile-time вычисления, о которых в следующем посте.

Кто-то из мэтров, вроде Хейлсберга, говорил, что сложность развития компиляторов квадратичная: если уже есть N фич и нужно добавить еще одну, приходится продумывать и аккуратно реализовывать взаимодействие новой фичи со всеми N старыми. Не берусь пока это подтвердить или опровергнуть, но в моем случае добавление в Leo структур привело к серьезному рефакторингу модулей Leo и LeoC: косяки исходной реализации стали выпирать и мешаться слишком сильно, пришлось исправлять. В итоге общий размер исходников увеличился всего на 7 строк: небольшой рост модулей парсинга и LeoC был компенсирован заметным сокращением и упрощением модуля Leo в ходе рефакторинга.

Структуры мне нужны для более удобного взаимодействия кода на Leo с кодом программы-хоста. Выглядит это так:

type point = { x : int; y : int }

type indata = {
 len : int
 str : byte[len] # кстати, это похоже на частный случай зависимых типов ;)
 ints : int[10]
 p : point
 out : byte[len]
}
 
args : indata
args.p.x <- 50; args.p.y <- 60

for i in args.ints.range  args.ints[i] <- i+1 end

for i in args.str.range
 args.out[i] <- args.str[|args.str| - 1 - i]
end

args - имя входного параметра программы на Leo (наподобие argc и argv).

В процессе тестирования всплыла очень смешная ошибка: описанный тут метод разбора делал арифметические операции правоассоциативными, в результате чего выражение 3 - 1 - 1 разбиралось как 3 - (1 - 1). Получилось так в ходе борьбы с левой рекурсией в грамматике, правило для сумм и разностей выглядело как

E = P + E | P - E | P

Если поменять местами P и E, ассоциативность станет нормальной, но возникнет левая рекурсия, что недопустимо. Проблема была решена путем преобразования таких правил в форму

E = P (+ P | - P)*

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

and expr_r s = ( 
  product >>= fun e1 ->  p_seq0  
    ((tok Lplus >>> product >>= fun e2 -> return (Add, e2)) |||  
     (tok Lminus >>> product >>= fun e2 -> return (Sub, e2)))  
    >>= fun ps -> return (List.fold_left (fun e1 (op, e2) -> Leo.Arith(op, e1, e2)) e1 ps) 
  ) s

Аналогично для делений с умножениями.

Дальше: оптимизация.

Current Location: 9 28' 28" N, 100 03' 49" E

К моменту появления работающего компилятора LeoC у меня примерно сформировалось представление о том, какой язык я хочу получить в итоге. Пришло время эти мысли записать формально и воплотить в коде.

Программы на Leo будут запускаться внутри "настоящих" программ и производить какие-то действия с переданными им данными: проверять валидность регистрационных ключей, проверять контрольные суммы исполняемых файлов, рисовать или не рисовать watermark'и на картинках, расшифровывать строки, расшифровывать байткод других частей, менять структуры программы-хоста (например, сейчас в одном из продуктов код на ВМ динамически меняет тип существующего COM-объекта путем изменения его таблицы виртуальных методов). Т.е. нужно уметь работать с массивами и структурами (по началу хватит и массивов), да нужна целочисленная арифметика. При этом хорошо бы минимизировать количество потенциальных багов, в частности, связанных с выходом за границы массивов и изменяемым состоянием. Плюс, хорошо бы иметь то, что делает функциональные языки (ФЯ) столь удобными, - возможность параметризовать функции другими функциями, в том числе описываемыми прямо в месте передачи, т.е. хорошо бы иметь функции высшего порядка (ФВП) и лямбды.

Итак,
( Read more... )

Итак, получив работающую виртуальную машину, я принялся за написание компилятора снизу-вверх. Первым делом система команд ВМ была описана в виде набора типов:


type dst = RegDest of int | PntDest of int;; 
type src = Reg of int | Pnt of int | Val of int;; 
 
type 'loc command =  
  | Arith of oper * dst * src * src 
  | Mov of dst * src 
  | Movb of dst * src 
  | Jmple of 'loc * src * src 
  | Jmpeq of 'loc * src * src 
  | Jmp of 'loc 
  | Print of src 
...

Сделал вывод ее в текст в форме, которую можно вставить в текст на Си: int prg[] = { ... };
Тут оказался очень полезен окамловский паттерн-матчинг, особенно когда появились команды, являющиеся частными случаями других:( Read more... )

Чуть менее, чем все виртуальные машины, которые я встречал и делал, были стековыми или регистровыми. В первом случае у нас есть некий стек значений, в него можно складывать всякие константы, а разные операции берут из него значения, проводят над ними какие-то действия, и результат кладут вместо взятых. При этом большинство команд в байткоде не имеют аргументов, т.к. их аргументы уже лежат на стеке, будучи положены туда другими командами. Соответственно, даже простые действия представляются целой серией операций (положить в стек один аргумент, положить другой, совершить действие...), и все время туда-сюда изменяется stack pointer, в простейшем случае - индекс в массиве. В случае регистровых ВМ у нас есть массив регистров, а у команд есть аргументы, указывающие из каких регистров брать исходные значения и куда сохранять результат операции. Количество операций, необходимых для совершения тех же действий, у регистровой ВМ меньше, но если мы хотим иметь вызовы функций, особенно рекурсивных, то возникают отдельные сложности - нужно или сохранять нужные регистры на стеке, или иметь целый стек регистровых массивов.

Виртуальная машина, которая использовалась у меня до этого момента, и в код которой компилился тот DSEL на Руби, была регистровой, причем вообще без стека. Все функции там инлайнились, а рекурсивные функции не поддерживались. Выделением памяти она тоже не занималась - все необходимые буферы должны были быть выделены вызывающей программой и переданы через регистры. Такие ограничения создавали ряд неудобств, поэтому было решено, что в LeoVM нужен какой-то стек и какое-то управление памятью. ( Read more... )

Почти все классические книжки и курсы по компиляторостроению начинаются с приемов разбора текста. И, я смотрю, многие разработчики тоже начинают писать свои компиляторы с парсинга. Не делайте этого! Это имеет смысл, только если разбираемый язык дан свыше каким-нибудь уважаемым божеством, а жрецы уже написали к нему сутры, шастры и кандидатские диссертации с комментариями. В противном случае дизайн языка начинает подчиняться ограничениям используемых инструментов парсинга, а сформулировать нормально грамматику становится очень сложно. Да и в выборе инструментов легко ошибиться. Вот вам мой совет: сперва опишите язык в виде структуры данных (алгебраического типа, например), реализуйте логику самого компилятора (в процессе структура может не раз поменяться), и лишь потом из нее уже делайте текст, перевод такой структуры в грамматику уже прост и линеен.
( Read more... ) Запомните, дети, такие парсер-комбинаторы годятся только для очень простых грамматик.

Но тут во всякую голову придет простая мысль: если проблема в том, что одна и та же работа делается пицот раз, почему бы не делать ее один раз и не запоминать результат. Мысль совершенно очевидная, однако в 2002 году кто-то на ней защитил диплом и дал особое название - ( Read more... )
В итоге весь парсинг языка ~~Панкратом~~ Packrat'ом занял 150 строк, т.е. менее 10% всего компилятора. ( Read more... )

Последние две недели пролетели в крайне интересном занятии: написании компилятора. Язык еще будет расти и облагораживаться, но все главное и основное уже реализовано и работает, теперь можно рассказать.

Сперва о результате. Пример компилирующегося и работающего кода:


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

( Read more... )
Типизация статическая. Как видите, имеется вывод типов, функции высшего порядка, параметрический полиморфизм, автоматическое управление памятью. Выделение памяти О(1), освобождение О(0). Есть оптимизация хвостовой рекурсии - sum здесь работает в constant space. Язык императивный, но с некоторыми функциональными удобствами. Компилируется в байткод. Вся виртуальная машина и рантайм - сотня строк на Си. Скорость компиляции: данный пример разобрался и скомпилился за 0.05 секунды, типичные целевые программы также компилируются за сотые доли секунды. Скорость работы: втрое быстрее Lua и двое быстрее окамловского байткода (сравнивал на комплексном тесте с нахождением всех простых чисел до 10^7). Причем ВМ на базе while-switch, никакого шитого кода и computed gotos.

( Read more... )