xeno_by (xeno_by) wrote,
xeno_by
xeno_by

Category:

Квазицитаты, метауровни и всякая всячина

В последнее время меня увлекли квазицитаты, поэтому я отложил сторонку допиливание макросов и начал разбираться с КЦ (кстати, это меня поражает в нашей лабе, и я, похоже, уже заразился этой привычкой - куча народу просто занимается тем, что в данный момент интересно, без особого плана или принуждения себя делать что-то конкретное). На всякий случай вот недавний коммит: https://github.com/scalamacros/kepler/commit/28be76ac3f2893a12898eabca139e27d2b166a8b, но сейчас я постараюсь рассказать человеческим языком.

С давних времен (2.8+) у нас в компиляторе поддерживается экспериментальный Code.lift, который превращает кодяру внутри единственного параметра в эквивалентный AST, который можно проинспектировать в рантайме (аля Expression Trees в сишарпе). С появлением reflection api, динамической кодогенерации и макросов настало время причесать лифтинг и добавить ему туда одну штучку, которая абсолютно необходима для удобной работы с деревьями. Ага, точно - я имею ввиду сплайсинг. Про него и про интересные эффекты, которые им порождаются, и будет сегодняшний пост.

***

Немного введения. Лично я лучше всего учусь на примерах, поэтому вместо тонны слов про то, что такое квазицитаты и сплайсы, вот небольшой сниппет, который заодно проиллюстрирует нашу реализацию. Итак, в моем бранче scalac можно писать вот так:
def two = lift{2}                                   // Constant(Literal(2))
def four = lift{splice{two} + splice{two}}          // Apply(Select(two, newTermName("$plus")), List(two))

val reporter = new ConsoleReporter(new Settings)    // немного бойлерплейта - мы пока не заморачивались над API
val toolbox = new ToolBox(reporter)                 // само собой, к релизу 2.10 все будет более приятно в использовании
                                                    
val ttree = toolbox.typeCheck(four.tree)            // тайпчекает дерево из four, после этого вызова можно 
                                                    // пробежаться по результату и узнать типы фрагментов
                                                    // а также увидеть, к каким именно внешним символам что прибиндилось
                                                    // к примеру, если бы в лифченном коде мы вызывали println, то
                                                    // sym.fullName для println после тайпчека показал бы scala.Predef.println

println(toolbox.runExpr(ttree))                     // запускаем компилятор, минуя первую фазу, parser,
                                                    // результаты тайпчека будут стерты нафиг, т.е. предыдущая строчка была необязательна
                                                    // на выходе будет сгенерирован in-memory байткод
                                                    // который будет подхвачен и исполнен специальным класслоадером
Как можно видеть, лифт преобразует кодяру в соответствующий AST, который можно проанализировать, тайпчекнуть и даже исполнить в рантайме. Более подробно про скаловский AST можно почитать у Мигеля Гарсиа (http://www.sts.tu-harburg.de/people/mi.garcia/ScalaCompilerCorner/UntanglingScalaASTs1ofN.pdf), а я лишь замечу то, что, в отличие от сишарпа, меня порадовало небольшое количество и гибкость стройматериалов. Например, нет разделения на Call и Invoke - есть Select, который достает мембер по имени (в том числе это работает и для методов), а есть Apply, который применяет функцию к аргументам (неважно, делегат это или метод).

Даже сам по себе лифтинг очень интересен. Его реализация в сишарпе весьма ограничена (лифтятся только лямбды + в процессе лифтинга теряется информация о переменных, захваченных из лексического скоупа), но все равно он стал очень популярен для создания type-safe апи. Однако, поработав с деревьями выражений сишарпа, довольно быстро сталкиваешься с необходимостью собирать деревья из динамических кусочков. К сожалению, лифтинг здесь не помогает (ибо он работает только с тем, что известно во время компиляции) и приходится вручную конструировать деревья.

Проблема композиции деревьев решается при помощи сплайсинга. В примере выше мы берем ранее залифченный код (переменную two) и вставляем его в квазицитату (выражение под вторым лифтом). В результате компилятор создаст ссылку на two, а также сгенерирует дерево, соответствующее шаблону, в который мы вставляем two. На самом деле, компилятор сделает еще больше - так как тип переменной two известен (он выводится как Code[Int]), то мы знаем, что сложение в four будет соответствовать сложению двух интов, т.е. обе квазицитаты в примере будут статически тайпчекнуты!

Получается все очень симпатично и концептуально просто так что я бы на этом и закончил, но самое интересное только начинается!

***

Во-первых, а что, если перед тем, как что-то сплайснуть, мы хотим это что-то обработать напильником? Каноничный пример - printf. Перед вставкой аргумента в принт мы, возможно, захотим его отформатировать, например, обернув в Apply(Select(arg, "format"), List(...)). Пока что ничего страшного, ибо спецификаторы формата задают тип аргумента, поэтому результирующее дерево все еще можно типизировать.

Но что, если напильник деформирует дерево так, что его родная мама не узнает мы не будем знать статический тип результата? Это не то, что бы совсем уж высосанное из пальца желание. Например, в нашем кусочке большого дерева мы можем захотеть сослаться на переменную, которая объявлена в другом кусочке дерева. Причем эта переменная может иметь тип, который генерируется динамически в третьем фрагменте дерева. Да, получается затык - наша строго типизированная идиллия в стиле MetaML рушится и надо что-то с этим делать.

Для спасения ситуации многие системы метапрограммирования вводят понятие нетипизированных квазицитат. К примеру, F#. Или вот Немерле, в котором макросы и квазицитаты по умолчанию нетипизированные (правда, с опциональными аннотациями типов). Более подробно об этом дизайн-решении написано в диссере одного из создателей Немерле: http://nazgul.omega.pl/macros.pdf (см. главу 8.1.1 "Static typing vs run-time").

Ту же самую штуку я добавил в Скалу, но возникло небольшое затруднение. Очень хочется типизировать все по макисмуму (например, если в кц есть типизируемые фрагменты, то есть желание их проверить), но для этого надо вводить в систему типов специальный магический тип (в слинкованном выше патче я так его и назвал - Magic). Этот тип, прикасаясь к чему угодно, преобразует это что угодно в Magic. Логично в принципе - если мы вызываем метод у результата нетипизированного сплайса, то мы не можем типизировать этот вызов и вынуждены отложить решение до рантайма. А пока что надо убедить компилятор отвязаться. Очень интересно, есть ли для этого формализация, а то пока что мой подход уж сильно ад-хок.

***

Во-вторых, в честь того, что мы сделали стейджинг крайне легким (вызов магической функции - что может быть легче) и сняли все тормоза (программист может вызвать лифт/сплайс откуда угодно), перед нами начинает маячить знаменитая темная башня метауровней (вот мой миррор статьи, оригинал вроде бы сдох: http://dl.dropbox.com/u/10497693/Library/Computer%20Science/Metaprogramming/Macros/Quasiquotations/Metalevels/The%20Dark%20Tower%20of%20Meta-levels.html):



Дело в том, что метауровни логически разделены между собой, а мы только что дали программисту элементарную возможность их смешать в кучу при помощи лексических скоупов. Смотрим еще один пример:
def y: Tree = ...
lift {
  y;                 // metalevel 1 refers to metalevel 0 => okay, but need a translation
                     // we will generate something like: Ident(newTermName("y"))

  splice { y };      // metalevel 0 refers to metalevel 0 => okay, no need of a translation
                     // we just insert a reference to y in the tree generated in LiftCode
                     // so that the generated code will look like: y (yep, as simple as that)

  def x: Tree = ...

  x;                 // metalevel 1 refers to metalevel 1 => okay, no need for a translation
                     // just Ident(newTermName("x"))

  splice { x };      // metalevel 0 refers to metalevel 1 => uh-oh, no translation will help us
                     // exact value of x will be known only during the run-time
                     // so we can only perform the splice during the run-time
                     // for the state of the art JVM it's more like science fiction
}
Итак мы только что убедились на практике, что: а) метауровни могут использовать переменные предыдущих метауровней, б) метауровни не могут ссылаться на переменные старших метауровней. Надо как-то закодировать это ограничение в компиляторе, и для этого мы снова воспользуемся типами (по крайней мере, на это настроен Адриаан, мнение Мартина пока что узнать не удалось).

Основная идея заключается в том, чтобы кодировать метауровень символов (символ = переменная, функция, класс - все, что угодно, что можно объявить) в аннотации к их типам. Т.е. в приведенном выше примере декларация x выглядела бы вот так: "def x: @ml(1) Tree" (само собой, компилятор вполне способен самостоятельно вывести и @ml и 1, поэтому явное указание аннотации здесь только для примера). Тогда функцию Code.splice мы могли бы объявить как "splice[A](tree: @ml(0) Code[A]): @ml(1) A" и все как бы чотко, но снова возникают проблемы.

Во-первых, метауровней не два и не три, а бесконечное число. Лифт, вложенный в лифт, переносит нас на метауровень 2 и так далее, причем вложенные лифты тоже надо тайпчекать, поэтому наша красивая декларация сплайса ломается и превращается в монстрилу вида "splice[A](tree: @ml(N) Code[A]): @ml(M) A where N < M and M = currentml" (синтаксис исключительно гипотетический).

Во-вторых, снова возникает концепция протекания информации о типах типов через всю программу. Скажем, если мы складываем два @ml(0)-числа, то у нас должно получится @ml(0)-число. А вот если хотя бы одно из этих чисел - @ml(1), то тогда получается @ml(1). Опять же вопрос - есть ли для этого формализация? Реквестирую nponeccop.
Tags: macros2011, scala
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic
  • 12 comments