Язык Julia не поддерживает такую технику программирования, хорошо зарекомендовавшую себя в языках Haskell, Prolog, Erlang, Scala, Mathematica, как pattern matching. Но разрешает писать макросы, которые позволяют исправить этот фатальный недостаток. Выглядит это примерно так:
Исходный код доступен на github.
Похожую (но гораздо более развитую и готовую для использования) можно взять здесь, но она слишком большая, что бы разбирать ее как пример в статье.
Как в Scala, на каждый альтернативный вариант, который надо распознать, создается тип (в данном случае как положено в функциональном программировании, неизменяемый, но этот код будет работать и с типами). При желании, их можно унаследовать от одного абстрактного.
Код на Julia, с которым работают макросы, представлен в виде Абстрактного Синтаксического Дерева (AST). В этом дереве листьями будут простые константы языка (числа, строки) и символы (имеющие тип Symbol), а узлы будут иметь тип Expr с полями head и args. Для создания объекта типа Expr или Symbol доступен синтаксический сахар: :v — это просто символ, а :(1+2) обозначает Expr(:call, :+, 1, 2) (Expr первый аргумент конструктора помещает в head, остальные в массив args). При конструировании выражений можно «цитировать» созадаваемое программой подвыражение: :($(a) + 1) — выражение, сложения подвыражения из переменной a с единицей. Цитирование (quotation) было изобретено в языке Lisp и оказалось восстребованным во многих языках, поддерживающих метапрограммирование.
Макрос 'case' первым аргументом получает анализируемое выражение, а остальные — пары образец->реакция. Посмотрим, как такие выражение выглядят в AST.
Рассмотрим код, который обрабатывает такие выражения
Функция casev принимает аргументы: v — символ связанный с анализируемым выраженим (а не само выражение, что бы не вычислять его несколько раз), e1 — образец->реакция, а np — что делать, если образец не будет распознан (прием, напоминающий программирование в продолжениях).
Сначала проверяется, что это выражение вида '->' и его аргументы сохраняются в переменных 'p' (образец) и 'c' (обрабатывающий его код).
Образец, похожий на вызов (call), разбирается на символ типа и выражения аргументов. Символ типа нужно конвертировать в сам тип (типы в Julia — «величины первого порядка»), что бы понять, что с ним можно делать. Вычислить символ можно функцией eval. (Она вычисляет выражение в контексте текущего модуля, по этому выделить макрос и вспомогательные функции в отдельный модуль у меня пока не получилось.)
Далее мы вызываем функцию 'spat' на каждую пару имя поля типа, соответствующий этому полю подобразец.
Это мультиметод, который диспечеризуется по типу подобразца. Для типов Symbol и Any (под это попадают все константы) генерируется код и пометка, что с ним потом делать. Для сложного подобразца (типа Expr) создается замыкание, которое рекурсивно создает распознаватель подобразца, оставляя реакцию свободной (аргумент замыкания 'm') — туда будет переданно продолжение обработки текущего образца.
Теперь можно создать обработку образца
'isa' проверяет, что анализируемая величена имеет тип 't' (символ которого мы получили из образца), 'pcomp' компилирует кусочки раскознающего образец кода в единое выражение, 'np' — «продолжение», которое распознает остальные образцы, если данный не будет распознан. Такой подход приводит к тому, что код «продолжения» будет продублирован при обработке каждой возможной неудачи распознавания. Пока этот макрос использует человек, это позволительная роскошь. Если код на Julia с pattern matching начнут писать роботы, надо будет оформить его в локальную функцию и передавать ее символ.
Функция получает массив кусочков, распознающих отдельные части образца. Если этот массив пуст, в этом месте генерируемой программы образец уже распознан и надо вызвать код реакции (из аргумента 'c').
Если в данном месте в образце был символ, надо оформить блок 'let' с инциализацией переменной с этим именем и поместить туда код дальнейшей обработки.
Если там была константа, создаем соответствующий 'if' (в альтернативе 'else' находится код «продолжения» при неудаче).
А если пришло замыкание, вызывем его, передав код распознавания остатка образца — оно само разберется, что с ним делать.
Теперь понятно, как обработать несколько альтернативных образцов и реализовать сам макрос:
Код, который он пораждает
julia> immutable X a end
julia> immutable Y a ; b end
julia> @case(Y(X(9),2), Y(4,3)-> 55, Y(X(k),2)->1+k)
10
Исходный код доступен на github.
Похожую (но гораздо более развитую и готовую для использования) можно взять здесь, но она слишком большая, что бы разбирать ее как пример в статье.
Как в Scala, на каждый альтернативный вариант, который надо распознать, создается тип (в данном случае как положено в функциональном программировании, неизменяемый, но этот код будет работать и с типами). При желании, их можно унаследовать от одного абстрактного.
Код на Julia, с которым работают макросы, представлен в виде Абстрактного Синтаксического Дерева (AST). В этом дереве листьями будут простые константы языка (числа, строки) и символы (имеющие тип Symbol), а узлы будут иметь тип Expr с полями head и args. Для создания объекта типа Expr или Symbol доступен синтаксический сахар: :v — это просто символ, а :(1+2) обозначает Expr(:call, :+, 1, 2) (Expr первый аргумент конструктора помещает в head, остальные в массив args). При конструировании выражений можно «цитировать» созадаваемое программой подвыражение: :($(a) + 1) — выражение, сложения подвыражения из переменной a с единицей. Цитирование (quotation) было изобретено в языке Lisp и оказалось восстребованным во многих языках, поддерживающих метапрограммирование.
Макрос 'case' первым аргументом получает анализируемое выражение, а остальные — пары образец->реакция. Посмотрим, как такие выражение выглядят в AST.
julia> :(Y(X(k),2)->1+k).head
:->
julia> :(Y(X(k),2)->1+k).args
2-element Array{Any,1}:
:(Y(X(k),2))
quote # none, line 1:
1 + k
end
Рассмотрим код, который обрабатывает такие выражения
casev(v,np,e1) = let
... Здесь описана вспомогательная функция spat
if(e1.head == :(->))
(p,c) = e1.args
if(p.head == :(call))
t = eval(p.args[1])
es = map(spat, t.names, p.args[2:end])
:(if(isa($v,$t)) ; $(pcomp(c,np,es)) else $np end)
end
end
end
Функция casev принимает аргументы: v — символ связанный с анализируемым выраженим (а не само выражение, что бы не вычислять его несколько раз), e1 — образец->реакция, а np — что делать, если образец не будет распознан (прием, напоминающий программирование в продолжениях).
Сначала проверяется, что это выражение вида '->' и его аргументы сохраняются в переменных 'p' (образец) и 'c' (обрабатывающий его код).
Образец, похожий на вызов (call), разбирается на символ типа и выражения аргументов. Символ типа нужно конвертировать в сам тип (типы в Julia — «величины первого порядка»), что бы понять, что с ним можно делать. Вычислить символ можно функцией eval. (Она вычисляет выражение в контексте текущего модуля, по этому выделить макрос и вспомогательные функции в отдельный модуль у меня пока не получилось.)
Далее мы вызываем функцию 'spat' на каждую пару имя поля типа, соответствующий этому полю подобразец.
spat(n::Symbol, p::Symbol) = (:(=), :($p = $v.$n))
spat(n::Symbol, p::Expr) = (:(m), let s = gensym() ; (m) ->
:(let
$s = $v.$n
$(casev(s,np,:($p->$m)))
end)
end)
spat(n::Symbol, p::Any) = (:(==), :($p == $v.$n))
Это мультиметод, который диспечеризуется по типу подобразца. Для типов Symbol и Any (под это попадают все константы) генерируется код и пометка, что с ним потом делать. Для сложного подобразца (типа Expr) создается замыкание, которое рекурсивно создает распознаватель подобразца, оставляя реакцию свободной (аргумент замыкания 'm') — туда будет переданно продолжение обработки текущего образца.
Теперь можно создать обработку образца
:(if(isa($v,$t)) ; $(pcomp(c,np,es)) else $np end)
'isa' проверяет, что анализируемая величена имеет тип 't' (символ которого мы получили из образца), 'pcomp' компилирует кусочки раскознающего образец кода в единое выражение, 'np' — «продолжение», которое распознает остальные образцы, если данный не будет распознан. Такой подход приводит к тому, что код «продолжения» будет продублирован при обработке каждой возможной неудачи распознавания. Пока этот макрос использует человек, это позволительная роскошь. Если код на Julia с pattern matching начнут писать роботы, надо будет оформить его в локальную функцию и передавать ее символ.
pcomp(c,np,p) =
if(length(p) == 0)
c
else
(r,d) = p[1]
n1 = pcomp(c,np,p[2:end])
if(r == :(=))
:(let $d ; $n1 ; end)
elseif(r == :(==))
:(if $(d) ; $n1 else $np end)
elseif(r == :(m))
d(n1)
end
end
Функция получает массив кусочков, распознающих отдельные части образца. Если этот массив пуст, в этом месте генерируемой программы образец уже распознан и надо вызвать код реакции (из аргумента 'c').
Если в данном месте в образце был символ, надо оформить блок 'let' с инциализацией переменной с этим именем и поместить туда код дальнейшей обработки.
Если там была константа, создаем соответствующий 'if' (в альтернативе 'else' находится код «продолжения» при неудаче).
А если пришло замыкание, вызывем его, передав код распознавания остатка образца — оно само разберется, что с ним делать.
Теперь понятно, как обработать несколько альтернативных образцов и реализовать сам макрос:
casen(v,el) = if(length(el) == 0)
:()
else
casev(v,casen(v,el[2:end]),el[1])
end
macro case(v,e1...)
if(isa(v,Symbol))
casen(v,e1)
else
let s = getsym()
:(let $(s) = $(v) ; $(casen(s,e1))
end
end
end
Код, который он пораждает
можно не читать
julia> macroexpand(:(@case(Y(X(9),2),Y(4,3)-> 55, Y(X(k),2)->1+k)))
:(let #246###11039 = Y(X(9),2) # line 48:
if isa(#246###11039,Y) # line 32:
if 4 == #246###11039.a # line 11:
if 3 == #246###11039.b # line 11:
begin # none, line 1:
55
end
else # line 11:
if isa(#246###11039,Y) # line 32:
let # line 21:
#244###11040 = #246###11039.a # line 22:
if isa(#244###11040,X) # line 32:
let #245#k = #244###11040.a # line 9:
begin # ADT.jl, line 22:
if 2 == #246###11039.b # line 11:
begin # none, line 1:
1 + #245#k
end
else # line 11:
()
end
end
end
else # line 32:
()
end
end
else # line 32:
()
end
end
else # line 11:
if isa(#246###11039,Y) # line 32:
let # line 21:
#244###11040 = #246###11039.a # line 22:
if isa(#244###11040,X) # line 32:
let #245#k = #244###11040.a # line 9:
begin # ADT.jl, line 22:
if 2 == #246###11039.b # line 11:
begin # none, line 1:
1 + #245#k
end
else # line 11:
()
end
end
end
else # line 32:
()
end
end
else # line 32:
()
end
end
else # line 32:
if isa(#246###11039,Y) # line 32:
let # line 21:
#244###11040 = #246###11039.a # line 22:
if isa(#244###11040,X) # line 32:
let #245#k = #244###11040.a # line 9:
begin # ADT.jl, line 22:
if 2 == #246###11039.b # line 11:
begin # none, line 1:
1 + #245#k
end
else # line 11:
()
end
end
end
else # line 32:
()
end
end
else # line 32:
()
end
end
end)