Fun with Leo: metaprogramming for free

[thedeemon]

Поскольку нерекурсивные функции в 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]))

Comments

[soonts.livejournal.com]

Привет.
Пара вопросов.

1. Оно у тебя до сих пор работает и не взломано?

2. Если я не буду делать свои язык и компилятор, а запилю только регистровую ВМ со своей системой команд и парой-тройкой стеков, и backend для LCC или LLVM.
И соответственно буду компилировать в свою VM С или C++ код.
Видишь недостатки по сравнению с LeoVM и custom высокоуровневым языком?
И почему ты так не сделал?
Вроде же сильно проще перетаскивать в ВМ имеющийся код потом, и свой, и сторонний, например nano-ecc или аналог для серийников и подписей.

Заранее спасибо!

[thedeemon.livejournal.com]

Привет!
Видел твое письмо, просто не успел еще ответить.

Да, у меня эта штука до сих пор используется в большинстве продуктов, только на этой неделе переводил интерпретатор ВМ на D и вставлял в Video Enhancer 2.0, выходящий совсем скоро (публичная бета уже на сайте). Я не слежу пристально за крэками, но из того что пока видел, регулярно появляются псевдовзломанные версии - люди убирают наг-скрин и думают что взломали, а проверить работоспособность проги не утруждаются. Она же, обнаружив себя измененной, при попытке обработать видеофайл тупо закрывается. Один крэк видел рабочий несколько лет назад, там смогли обойти вызов ВМ, но я потом сделал так, что если код на ВМ не отработал, то некоторые другия части программы перестают работать. После этого годных взломов уже давно не видел.

Я никогда не пробовал делать бэкенд для LLVM, но априори мне кажется, что это довольно много возни, и спектр вопросов, требующих решения, там намного шире чем в своей поделке на двадцать команд. Тут мне не надо думать о нуждах C Runtime, например. Если ты собираешься много существующего кода в ВМ переносить, то путь через clang-llvm весьма разумен, имеет смысл. У меня же все реальные программы на Leo меньше 200 строк. Сделать свой компилятор заняло две увлекательных недели до чего-то уже работающего, плюс потом периодически возвращался с дополнениями и модификациями. Полагаю, с clang'ом я б дольше возился, и без удовольствия.
Пожалуй, есть один момент, где пригодилось иметь свой компилятор, а не просто бэкенд. Он у меня не только оптимизирующий, но одновременно и пессимизирующий. Некоторые части кода хочется оптимизировать, чтобы работали побыстрее (подсчет чексумм и расшифровка данных), а некоторые другие части и общую логику хочется наоборот сделать более сложными и запутанными. И у меня в компиляторе есть преобразование AST, которое добавляет туда много новых вычислений и ветвлений, чтобы вместо простого
a[4] = 1
было что-нибудь вроде
x2 = 2
x7 = 66
x3 = x7 + 1
x13 = 8
x16 = 3
x5 = x13 * 6
x4 = x16 + x2
x12 = x13 * x13
x11 = 255 ^ 128
x1 = x12 + x11
x8 = x1 * 4
x9 = 765 - x8
x6 = x9+1
x7 = x4 - x16
x10 = x6*x7
if (x3 > x2) {
a[x10] = x9
} else {
a[x10] = x5
}
Только реально ветвлений там еще больше вставляется. Возможно, это можно делать на уровне блоком LLVM IR, но кажется на уровне AST это несколько проще и приятней.

[soonts.livejournal.com]

>надо думать о нуждах C Runtime, например
Конечно не пробовал пока, но мне кажется должно хватить минимального subset.
>много существующего кода в ВМ переносить
Ну хотелось бы страниц 5-10 перенести, в проекте более чем достаточно сложной математики для этого.

>Я никогда не пробовал делать бэкенд для LLVM
Я тоже.
>с clang'ом я б дольше возился, и без удовольствия
Да, LLVM intermediate language изрядно сложный в смысле много букв.
Но например LCC проще должен быть, весь компилятор 400kb, вот например какой-то парень запилил свой 16-битный проц и рассказывает, как LCC прикручивал: http://www.homebrewcpu.com/retargeting_lcc.htm

OK, большое спасибо за ответ!
Подумаю ещё, шо лучше сделать.