УДК 681.322.068:658.512.22.011.56
ГОРДИЕНКО А. П.
УДОВЛЕТВОРЕНИЕ ГЕОМЕТРИЧЕСКИМ ОГРАНИЧЕНИЯМ В ГРАФИЧЕСКОМ РЕДАКТОРЕ, РЕАЛИЗОВАННОМ СРЕДСТВАМИ ФУНКЦИОНАЛЬНОГО ПРОГРАММИРОВАНИЯ
В статье предлагается эффективный метод пересчёта геометрических ограничений в графическом редакторе, реализованном средствами функционального программирования. Эффективность достигается применением ленивых потоков состояний. Полученный алгоритм по скорости выполнения и по расходу памяти имеет одинаковые показатели с императивным аналогом, но при этом сохраняет прозрачность ссылок.
Ключевые слова: графический пользовательский интерфейс, геометрические ограничения, функциональное программирование, ленивый поток состояния, монада.
The paper proposes an effective method of conversion of geometric constraints in a graphical editor, realized by means of functional programming. Efficiency is achieved by using lazy functional state threads. The resulting algorithm for execution speed and memory consumption has the same performance with imperative analogue, but it preserves the reference transparency.
Keywords: graphical user interface, geometric constraints, functional programming, lazy functional state threads, monad.
ВВЕДЕНИЕ
Современные графические редакторы, используемые в системах автоматизированного проектирования, вместе с задачей построения элементов чертежа решают задачу и учёта геометрических требований. Так, в процессе черчения по мере построения геометрических объектов должны выявляться и геометрические соотношения между ними, такие как принадлежность прямой или окружности, параллельность и перпендикулярность отрезков, касание дуги окружности отрезком или другой дугой. Простановка размеров на чертеже тоже налагает геометрические ограничения на объекты чертежа.
Вся совокупность геометрических требований составляет исходные данные для системы построения плана действий по построению чертежа. Если чертёж плоский, то эти действия напоминают процесс построения с помощью циркуля и линейки.
К алгоритмам, работающим с ограничениями, предъявляются повышенные требования к их корректности, поскольку в них должно учитываться огромное множество вариантов ветвей вычислений, которые все протестировать очень трудно. Таким образом, становится оправданным использование формальных методов при разработке алгоритма. Это, на наш взгляд, лучше всего сделать на основе чистого функционального программирования, реализованного в языке Хаскель [1]. Целесообразность такого подхода была показана нами в предыдущих работах.
В этой работе сформулирована задача удовлетворения геометрическим ограничениям в графическом редакторе, дано её решение на основе функциональной парадигмы, предложен эффективный алгоритм выполнения плана по построению чертежа с использованием ленивых потоков состояний.
ФОРМУЛИРОВКА ЗАДАЧИ
Исходные данные: два массива координат x и y соответственно; массив точек, представленных парами индексов координат; план построения чертежа — список действий, каждое из которых содержит индекс точки, координаты которой в нём вычисляются и список ограничений, каждое из которых ограничивает одну степень свободы указанной точки.
Выходные данные: если план выполним, то два новых массива координат x и y соответственно, удовлетворяющих ограничениям; два списка точек, имеющих соответственно одну и две степени свободы. Если какое-либо действие не имеет решения, то должно быть сформировано сообщение об ошибке.
Алгоритм. В соответствии с указанными входными и выходными данными требуется определить функцию, которая имеет тип:
recalc::
Array Int Float -> -- Координаты x
Array Int Float -> -- Координаты y
Array Int (Int, Int) -> -- Точки
[(Int,[FixPoF])] -> -- Список действий (план)
Either -- Результат
-- В случае неудачи
[GrPrim] -- – графическое сообщение об ошибке
-- В случае удачи – четвёрка:
(Array Int Float, -- массив координат x,
Array Int Float, -- массив координат y,
[Int], -- список точек с одой степенью свободы,
[Int]) -- список точек с двумя степенями свободы.
Операцию вычисления одной точки обозначим функцией calcPnt. Её тип:
calcPnt::
Array Int Float -> -- Координаты x
Array Int Float -> -- Координаты y
(Int,[FixPoF]) -> -- Действие
Either -- Результат
-- того же типа
[GrPrim] -- что и у функции recalc
(Array Int Float,
Array Int Float,[Int], [Int])
Функция recalc может быть определена через рекурсивную функцию recalc'. В последнюю, для хранения массивов координат, введём два накапливающих параметра: axs и ays. Для формирования списков недоопределённых точек, введём ещё два накапливающих параметра: lm1 для списка точек с одной степенью свободы и lm2– с двумя. Функция recalc', в базовом случае, когда список действий пуст, успешно завершает работу, формируя результат из значений накапливающих параметров. В общем случае, когда список действий имеет вид (act:acts), если действие act будет успешно выполнено функцией calcPnt, то далее план будет выполняться с новыми значениями накапливающих параметров, иначе – в случае неуспеха – процесс вычисления точек прерывается и выдаётся сообщение об ошибке.
recalc axs ays aps = recalc' axs ays [] []
where
recalc' axs ays lm1 lm2 [] = Right (axs, ays, lm1, lm2)
recalc' axs ays lm1 lm2 (act:acts) =
case r of
Right (axs', ays', lm1', lm2') ->
recalc' axs' ays' (lm1'++lm1) (lm2++lm2) acts
Left grprs -> Left grprs
where r = calcPnt axs ays lm1 lm2 act
Приведённый алгоритм имеет один существенный недостаток: после вычисления каждой точки в динамической памяти создаются два новых массива координат точек, а старые превращаются в мусор. Очевидно, что в такой ситуации целесообразнее было бы просто занести в массивы координаты полученной точки. Однако, явная модификация данных, как это делается в императивных языках, запрещена в языках функциональных, поскольку она нарушает прозрачность ссылок — главное достоинство функциональных языков, позволяющую выполнять с программами алгебраические преобразования. Сохранить прозрачность ссылок и модифицировать данные в императивном стиле можно применив ленивые потоки состояний [2].
ЛЕНИВЫЕ ПОТОКИ СОСТОЯНИЙ
Если есть уверенность, что в программе одно значение получается взамен другого, то есть если старое значение непременно должно стать мусором, то можно для нового значения не запрашивать новый блок памяти, а использовать старый, предназначенный для утилизации. Таким образом, появляется возможность использования модифицируемых данных без нарушения прозрачности ссылок. Такая возможность особенно важна, если используются сложные структуры данных, такие как массивы. Это мы покажем на примере решаемой в данной работе задаче.
Данные можно изменять на месте, если есть уверенность, что старое значение уже никогда не понадобится. Такую уверенность даёт условие, что данные изменяются в потоке, шаг за шагом. Тогда при переходе к новому шагу старое значение становится явно ненужным.
Поток состояний реализуется на основе монады с состоянием, которая строится конструктором типа ST s a. Вычисление такой монады приводит к изменению состояния типа s и к выдаче результата типа a. Для этой монады определены все стандартные операции и синтаксические расширения. Она определена в библиотеке Control. Monad. ST.
Если состояние будет абстрагировать динамическую память, то для операций создания, чтения и записи, выполняемых с изменяемой переменной, используют встроенный тип STRef s a, значения которого — изменяемые переменные в потоке состояний s, содержащие значения типа a.
Для работы с изменяемыми переменными используются следующие функции.
newSTRef :: a -> ST s (STRef s a) — создаёт в текущем потоке состояний новое обращение к изменяемой переменной.
readSTRef :: STRef s a -> ST s a — читает значение изменяемой переменной.
writeSTRef :: STRef s a -> a -> ST s () - присваивает новое значение изменяемой переменной.
Пример:
do v <- newSTRefсоздние новой переменной v
-- с начальным значением 10.
val <- readSTRef v -- чтение её значения
-- в обычную переменную val.
writeSTRef v (val+2) -- запись в переменную v
-- значения выражения (val+2).
Названные функции определены в стандартном модуле Data. STRef.
Есть аналогичные функции и для работы с массивами. Для преобразования неизменяемого массива в изменяемый используется функция
thaw :: (Ix i, IArray a e, MArray b e m) => a i e -> m (b i e),
которая, получив параметр — неизменяемый массив, формирует действие потока состояний, результатом которого будет изменяемый массив с таким же содержимым. Для чтения элемента массива используется функция
readArray :: (MArray a e m, Ix i) => a i e -> i -> m e,
которая, получив массив и индекс, формирует действие потока состояний, результатом которого будет содержимое заданной ячейки массива. Для записи значения элемента в массив используется функция
writeArray :: (MArray a e m, Ix i) => a i e -> i -> e -> m (),
которая, получив массив, индекс и значение для записи формирует действие потока состояний, побочным эффектом которого будет занесение заданного содержимого в массив. Для преобразования изменяемого массива в неизменяемый используется функция
freeze :: (Ix i, MArray a e m, IArray b e) => a i e -> m (b i e),
которая, получив параметр — изменяемый массив, формирует действие потока состояний, результатом которого будет неизменяемый массив с таким же содержимым. Названные функции определены в стандартном модуле Data. Array. MArray.
С использованием изменяемых данных алгоритм пересчёта точек можно сделать более эффективным.
АЛГОРИТМ, ИСПОЛЬЗУЮЩИЙ ИЗМЕНЯЕМЫЕ ДАННЫЕ
Для эффективного пересчёта координат точек, хранящихся в изменяемых массивах, нужно использовать поток состояния. Новая функция recalc — это описание последовательности шагов изменения состояний, использующее do-нотацию:
recalc axs ays aps acts = do (1)
mxs <- thaw axs; mys <- thaw ays (2)
lm1 <- newSTRef []; lm2 <- newSTRef [] (3)
let
calcPnt act =
doPlan [] = do (5)
axs' <- freeze mxs; ays' <- freeze mys (6)
lm1 <- readSTRef lm1; lm2 <- readSTRef lm2 (7)
return (Right (axs',ays',lm1,lm2)) (8)
doPlan (act:acts) = do (9)
res <- doStep act (10)
maybe (doPlan acts) (\e-> return (Left e)) res (11)
doStep act@(ip, fixes) = do (12)
case length fixes of (13)
0 -> modifySTRef lm2 (\l->ip:l) (14)
1 -> modifySTRef lm1 (\l->ip:l) (15)
otherwise -> return () (16)
calcPnt act (17)
doPlan act (18)
Входными параметрами функции recalc, как и в исходной версии, являются: axs и ays - массивы координат x и y соответственно, aps — массив точек и acts — список действий (1). Массивы axs и ays преобразуются в изменяемые массивы mxs и mys (2). Далее создаются две изменяемые переменные lm1 и lm2, которые будут накапливать в списках точки, соответственно с одной и двумя степенями свободы (3).
Функция calcPnt (4), в отличие от предыдущей реализации является действием, которому доступны изменяемые массивы axs и ays. Результатом действия может быть изменение в массивах координат или сообщение о неудаче в форме списка графических примитивов типа [GrPrim]. Таким образом, результат действия calcPnt будет иметь тип Maybe[GrPrim].
План действия исполняется рекурсивной функцией doPlan (5-11), которая для выполнения каждого действия вызывает функцию — действие doStep (12-17). Последняя, получив описание действия act, содержащее индекс вычисляемой точки ip и список ограничений степени свободы fixes, делает следующее.
Функция doPlan, в случае, когда список действий пуст, возвращает в конструкторе Right вычисленное состояние, а в противном случае — выполняет шаг плана. Если он удачен — продолжается вычисление, иначе — передаётся сообщение об ошибке.
ЗАКЛЮЧЕНИЕ
На примере задачи удовлетворения геометрическим ограничениям было показано, что чистое функциональное программирование применимо при решении задач из области интерактивной машинной графики. Программа, написанная на функциональном языке, имеет вид строгих математических определений, с которыми можно выполнять алгебраические преобразования, о которых можно рассуждать формально и доказывать свойства программы. На основе функционального программирования можно решать существенно более сложные задачи, не теряя при этом ясности описания алгоритмов. Вместе с тем, возможности функциональных языков с каждым годом расширяются и, как было показано в данной статье, применение ленивых потоков состояний позволило построить эффективный алгоритм, когда, казалось бы, без императивного подхода не обойтись.
ЛИТЕРАТУРА
1. Hudak, P. Haskell 98 Language and Libraries. The Revised Report [Text] / P. Hudak, S. Peyton Jones, P. Wadler // Technical report. – Yale University and Glasgow University. – 2002. – 151 p.
2. Launchbury, John. Lazy Imperative Programming [Text]/ John Launchbury //Proceedings ACM Sigplan Workshop on State in Programming Languages. – 1993. – P. 46-56.
Сведения об авторе:
, к. т.н., доцент, доцент. e-mail: *****@***ru.
