Pattern matching з допомогою макросів

Мова Julia не підтримує таку техніку програмування, що добре зарекомендувала себе в мовах Haskell, Prolog, Erlang, Scala, Mathematica, як pattern matching. Але дозволяє писати макроси, які дозволяють виправити цей фатальний недолік. Виглядає це приблизно так:
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,n,p) =
if(length(p) == 0)
c
else
(r,d) = p[1]
n1 = pcomp(c,n,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)


Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.