thedeemon | Часть 4. ФВП, полиморфизм и вывод типов без матана

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

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

Итак,
Не, все гораздо проще. :) Девиз этого компилятора - максимум бенефитов при минимуме имплементационных усилий.

В плане борьбы с ошибками, вызванными изменяемым состоянием, мне нравится подход ФЯ, где мы оперируем не столько переменными, сколько именованными значениями, по умолчанию неизменяемыми. Выражение а = с*3 рассматривается как математическое обозначение, объявление имени и его значения. Если все же нужно изменить значение, то для этого есть отдельный оператор <-, как в ML, но им стоит пользоваться поменьше.

Для работы с массивами в языке были сделаны конструкции для создания массивов (с указанием типа и числа элементов), обращения к элементу (name[expr]), изменения элемента (name[expr] <- expr). Компиляция их в LeoC с его арифметикой указателей очевидна. Чтобы минимизировать число ошибок, связанных с индексами, компилятор всегда знает размер массива: константу или целочисленную переменную (точнее, именованное значение, ведь менять эту переменную никто не может). Когда массив создается с явным указанием длины, компилятор просто запоминает это число. Если длина при создании вычисляется, то создается переменная для хранения длины. Если массив передается в функцию, то передаются два значения: в первом адрес начала, во втором длина. В язык были добавлены три специальных операции: получение длины массива, получение первого элемента и получение хвоста - элементов со второго по последний. Хвост при этом не копируется, просто создается новая пара (указатель, длина), отличающаяся от исходной на (размер элемента, -1). Для работы с частями массивов, а также других целей, был добавлен специальный тип: последовательность. Изначально замысел был в том, что это может быть последовательность чего угодно, над которой можно проводить всякие операции, вроде map и filter, тем самым получив что-то вроде ленивых списков (но которые нигде не хранятся) или IEnumerable, причем массив тоже будет считаться такой последовательностью. Но для начала был сделан более простой вариант: последовательностью в Leo считается либо массив, либо отрезок из целых чисел от А до Б, например 1..10. Такой отрезок представляется двумя числами - своими границами. Для них работают те же операции взятия длины (Б-А+1), первого элемента (А) и хвоста (А+1 .. Б). Для массивов была добавлена операция range, возвращающая отрезок допустимых индексов - от 0 до длины-1. Таким образом, массивы и отрезки стали во многом взаимозаменяемы, что может быть использовано для написания универсального кода, работающего с тем и другим. В язык были добавлены циклы:

for name1 in seq1, name2 in seq2, ...
 code
end

где seq - последовательность, т.е. массив или отрезок. В цикле могут крутиться сразу несколько переменных, каждая в своих пределах. В случае for x in arr x поочередно принимает значения из массива arr, т.е. это аналог foreach. Кроме этого был добавлен синтаксический сахар:

name[seq] <- expr

превращается в

for i in seq
 name[i] <- expr
end

А name <- something, когда слева массив, а справа тоже массив или отрезок, превращается в

for i in name, j in something
 i <- j
end

Также была добавлена операция получения части массива: name[range] - это массив из элементов name с индексами из range (как и хвост, вычисляется без копирования). Благодаря этому можно лаконично записывать операции с кусками массивов:

arr1[2..5] <- arr2
arr <- 1..5
arr1 <- arr2
arr1[5..7] <- arr2[2..4]
a <- a.range

и т.д.

Благодаря тому, что можно использовать a.range и подобные сокращенные операции, где число итераций компилятор вычисляет исходя из размеров массивов и отрезков (беря минимум, если длина отличается), количество потенциальных ошибок с индексами должно быть заметно меньше, чем в случае ручного написания циклов и их границ.

Теперь, когда были арифметические выражения и циклы, появилась необходимость в параметризованных выражениях, т.е. функциях. Если раньше были объявления name = expr, то теперь к ним добавляются name(args) = expr, где expr может содержать args. Если не нужно имя, а только само выражение, то для этого есть безымянные функции, т.е. лямбды: \args -> expr. Надо ли их все компилировать в функции LeoC? Совсем не обязательно! Если у нас есть объявление f(x) = x*x и выражение 2 + f(3), то можно просто выполнить подстановку и получить выражение 2 + 3*3. Размер байткода экономить не требуется, даже наоборот, чем его будет больше, тем сложнее в нем будет разобраться взломщикам. Чем больше функций будет проинлайнено, тем больше нужно усилий для их изменения. Поэтому все, что можно, в Leo инлайнится. А что нельзя? Рекурсивные функции. Вот только они компилируются в функции LeoC. Поскольку процедуре подстановки все равно, что подставлять, то аргументом функции может быть имя другой функции или лямбда. Переданная в качестве параметра функция просто вставляется на места, где к ней идут обращения. Все это раскрывается дальше, пока больше ничего раскрыть нельзя. Так, код

iter(f, xs) = for x in xs f(x) end
show(xs) = iter(\t -> print(t), xs)
show(1..10)

Раскрывается сперва в

iter(\t -> print(t), 1..10)

затем в

f(t) = print(t)
for x in 1..10 f(x) end

и наконец в

for x in 1..10 print(x) end

И это уже компилируется в LeoC в виде цикла while.

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

f(x) = x*x
z = f(5+5)

Превращается в

t = 5+5
z = t*t

Такой подход бесплатно дает один хороший бонус: полиморфизм. Например, описанную выше функцию show можно вызвать с аргументами разных типов: отрезком и массивами байт и интов. Каждый вызов будет заменен на цикл, и в каждом конкретном случае for будет реализован по-разному.

А, да. Типы. Программа состоит из набора объявлений, циклов и нескольких простых операторов (вроде print и <-). Типы нужно указывать только в одном месте: при создании нового массива. Все остальное элементарно выводится без всяких Хиндли-Милнеров, просто снизу-вверх: числовые константы имеют тип инт. Результат арифметической операции имеет тип инт. Элемент массива имеет тип, описанный при его создании. Переменная цикла имеет либо тип элемента массива, по которому идет цикл, или инт, если цикл по отрезку. Определенное через = имя имеет тип выражения из правой части. Происходит такой вывод типов после раскрытия всех параметризованных выражений, поэтому специально их типизировать, вводя с учетом полиморфизма всякие 'a, не нужно. Отдельная история с рекурсивными функциями. Когда встречается параметризованное объявление, делается проверка на рекурсивность. Если имеется рекурсия, то инлайнить нельзя, ибо зациклимся. Поэтому определение функции просто запоминается как есть, а когда дальше в программе встречается ее вызов, то к этому моменту уже известны типы аргументов. Для каждой функции для каждого встреченного набора типов аргументов компилятор помнит результат ее компиляции. Если с такими типами аргументов ее еще не вызывали, то она компилируется и запоминается с уникальным именем. Вызов такой функции компилируется именно в вызов. После завершения компиляции области видимости, где она описана, в том месте, где было ее описание, вставляются все откомпилированные варианты с разными именами, по одному для каждого использованного набора типов аргументов. Например,

sum_loop(sum, xs) = if |xs| > 0 then sum_loop(sum + xs.head, xs.tail) else sum
sum_loop(0, 1..10)
arr = new int[5]
sum_loop(0, arr)

Компилируется в

fun sum_loop_5(sum, xs, xs_len)
{
 if 0 < xs_len {
  var arr_len_7
  arr_len_7 <- (xs_len - 1)
  return sum_loop_5((sum + *xs), (xs + 4), arr_len_7)
 } else {
  return sum
 }
}
fun sum_loop_1(sum, xs, xs_end)
{
 if 0 < ((xs_end - xs) + 1) {
  var bound_3
  bound_3 <- (xs + 1)
  return sum_loop_1((sum + xs), bound_3, xs_end)
 } else {
  return sum
 }
}
sum_loop_1(0, 1, 10)
var arr
arr <- new [20]
sum_loop_5(0, arr, 5)

(реальный вывод pretty-printer'a LeoC)
В такой схеме есть одна большая дыра: при компиляции рекурсивной функции известны типы аргументов и всех внутренних выражений, кроме типа самой функции. А поскольку она рекурсивная, то содержит вызов себя, и получается, что для того, чтобы вывести ее тип, нужно знать ее тип. Делать более умный алгоритм вывода не хотелось (см. девиз компилятора), заставлять описывать тип функций явно - тоже. Но тут вспомнился еще один момент: мы же не должны допускать возврата из функции указателей на выделенную внутри нее память. Поэтому был сделан простой и грязный хак: в процессе компиляции предполагается, что функция возвращает инт. С этим предположением можно вывести типы всех выражений внутри нее, а значит и настоящий возвращаемый тип. При этом возвращать что-то сложное, вроде массива, просто запрещается. Такое искусственное ограничение только для рекурсивных функций, которых на практике немного, и для них оно вполне выносимое.

Поскольку в функции LeoC компилировались только рекурсивные функции, то жизненно важно стало наличие оптимизации хвостовой рекурсии. Реализована она очень просто:

return sum_loop_1((sum + xs), bound_3, xs_end)

превращается в

sum <- sum + xs
xs <- bound_3
goto sum_loop_1

Т.е. находим хвостовой вызов себя, смотрим, какие параметры изменяются, если надо сохраняем старые значения во временных регистрах, записываем в параметры новые значения и прыгаем на начало функции. Аналогично делается произвольный хвостовой вызов. При этом есть одна проблема: превратив return/call в цикл, мы перестали освобождать память. Пока функция крутится в рекурсии, выделяемая память накапливается, а когда наконец делается настоящий возврат, вся выделенная память разом освобождается. Получается, constant space на стеке, но O(n) на куче. Это я поленился как-то разруливать, ибо реальных рекурсивных функций, выделяющих память, у меня вряд ли будет много, если вообще будут.

Вот такой получился неправильный компилятор. Если допустить ряд ограничений и не пытаться делать все фичи универсальными, то вполне можно обойтись довольно простыми решениями и быстро получить работающий язык с фишками "как у больших", но без сложностей компиляторов и рантаймов "больших" языков.

Дальше: Структуры, рефакторинг.