Symbolic computation system for dynamical application programming

The system of symbolical computation intended for embedding in the industrial applications with the purpose of maintenance to their flexibility and tenability on the varied requirements and a condition of functioning is described. The method of immersion of adjusted program systems in industrial com...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2015
Автори:	Doroshenko, A.Yu., Shevchenko, R.S.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут програмних систем НАН України 2015
Теми:	UDC 51.681.03
Онлайн доступ:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/24
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Problems in programming

Репозитарії

Problems in programming

id	pp_isofts_kiev_ua-article-24
record_format	ojs
resource_txt_mv	ppisoftskievua/97/16240a76884a1506b5d0766c1af6e497.pdf
spelling	pp_isofts_kiev_ua-article-242018-10-09T11:50:31Z Symbolic computation system for dynamical application programming Система символьных вычислений для программирования динамических приложений Система символьних обчислень для програмування динамічних застосувань Doroshenko, A.Yu. Shevchenko, R.S. UDC 51.681.03 УДК 51.681.03 УДК 51.681.03 The system of symbolical computation intended for embedding in the industrial applications with the purpose of maintenance to their flexibility and tenability on the varied requirements and a condition of functioning is described. The method of immersion of adjusted program systems in industrial complexes based on use of declarative means of programming at the description of interactions a program component with the environment is offered. The method allows considerably to reduce cost of development of the complex software and also to solve problems of the analysis and maintenance of reliability of a program code. Описана система символьных вычислений, предназначенная для встраивания в промышленные приложения с целью обеспечения их гибкости и настраиваемости соответственно изменяющимся требованиям и условиям функционирования. Предложен метод погружения настраиваемых программных систем в промышленные комплексы, основанный на использовании декларативных средств программирования при описании взаимодействий программных компонент со своим окружением. Метод позволяет значительно уменьшить стоимость разработки сложного программного обеспечения, а также решать задачи анализа и обеспечения надежности программного кода. Описано систему символьних обчислень, призначену для вбудовування в промислові застосування з метою забезпечення їх гнучкості і настроюваності на вимоги, що змінюються, і умови функціонування. Запропоновано метод занурення настроюваних програмних систем у промислові комплекси, заснований на використанні декларативних засобів програмування при описі взаємодій програмних компонент зі своїм оточен- ням. Метод дозволяє значно зменшити вартість розробки складного програмного забезпечення, а також вирішувати задачі аналізу і забезпечення надійності програмного коду. Інститут програмних систем НАН України 2015-07-01 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/24 PROBLEMS IN PROGRAMMING; No 4 (2003) ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 4 (2003) ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 4 (2003) 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/24/28 Copyright (c) 2015 ПРОБЛЕМИ ПРОГРАМУВАННЯ
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2018-10-09T11:50:31Z
collection	OJS
language	Ukrainian
topic	UDC 51.681.03
spellingShingle	UDC 51.681.03 Doroshenko, A.Yu. Shevchenko, R.S. Symbolic computation system for dynamical application programming
topic_facet	UDC 51.681.03 УДК 51.681.03 УДК 51.681.03
format	Article
author	Doroshenko, A.Yu. Shevchenko, R.S.
author_facet	Doroshenko, A.Yu. Shevchenko, R.S.
author_sort	Doroshenko, A.Yu.
title	Symbolic computation system for dynamical application programming
title_short	Symbolic computation system for dynamical application programming
title_full	Symbolic computation system for dynamical application programming
title_fullStr	Symbolic computation system for dynamical application programming
title_full_unstemmed	Symbolic computation system for dynamical application programming
title_sort	symbolic computation system for dynamical application programming
title_alt	Система символьных вычислений для программирования динамических приложений Система символьних обчислень для програмування динамічних застосувань
description	The system of symbolical computation intended for embedding in the industrial applications with the purpose of maintenance to their flexibility and tenability on the varied requirements and a condition of functioning is described. The method of immersion of adjusted program systems in industrial complexes based on use of declarative means of programming at the description of interactions a program component with the environment is offered. The method allows considerably to reduce cost of development of the complex software and also to solve problems of the analysis and maintenance of reliability of a program code.
publisher	Інститут програмних систем НАН України
publishDate	2015
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/24
work_keys_str_mv	AT doroshenkoayu symboliccomputationsystemfordynamicalapplicationprogramming AT shevchenkors symboliccomputationsystemfordynamicalapplicationprogramming AT doroshenkoayu sistemasimvolʹnyhvyčislenijdlâprogrammirovaniâdinamičeskihpriloženij AT shevchenkors sistemasimvolʹnyhvyčislenijdlâprogrammirovaniâdinamičeskihpriloženij AT doroshenkoayu sistemasimvolʹnihobčislenʹdlâprogramuvannâdinamíčnihzastosuvanʹ AT shevchenkors sistemasimvolʹnihobčislenʹdlâprogramuvannâdinamíčnihzastosuvanʹ
first_indexed	2025-07-17T10:04:58Z
last_indexed	2025-07-17T10:04:58Z
_version_	1837888122929545216
fulltext	Методы программирования © А.Е. Дорошенко, Р.С. Шевченко, 2003 24 ISSN 1727-4907. Проблемы программирования. 2003. № 4 УДК 51:681.03 А.Е. Дорошенко, Р.С. Шевченко СИСТЕМА СИМВОЛЬНЫХ ВЫЧИСЛЕНИЙ ДЛЯ ПРОГРАММИРОВАНИЯ ДИНАМИЧЕСКИХ ПРИЛОЖЕНИЙ Описана система символьных вычислений, предназначенная для встраивания в промышленные приложения с целью обеспечения их гибкости и настраиваемости со- ответственно изменяющимся требованиям и условиям функционирования. Предложен метод погружения настраиваемых программных систем в промышленные комплексы, основанный на использовании декларативных средств программирования при описа- нии взаимодействий программных компонент со своим окружением. Метод позволяет значительно уменьшить стоимость разработки сложного программного обеспечения, а также решать задачи анализа и обеспечения надежности программного кода. Введение Системы символьных вычисле- ний имеют богатую историю и приме- няются для различных целей с первых лет существования компьютерной нау- ки как самостоятельной области. Од- ним из направлений в разработке сис- тем символьных вычислений являются системы переписывающих правил (re- writing rules systems) [1]. На сегодня в мире существует более сотни систем переписывающих правил, которые под- держиваются как исследовательскими группами, так и коммерческими орга- низациями и используются в различ- ных областях приложений. В Киберне- тическом центре НАН Украины имеют- ся большие традиции построения таких систем: одной из первых была система ”Аналитик” [2], широко известна так- же система алгебраического програм- мирования AПС [3, 4]. В этой статье представлена еще одна система симво- льных вычислений, основанная на па- радигме переписывания TermWare и предназначенная для решения задач программной инженерии. Существует некоторая типология систем переписывания, отражающая как эволюцию программного обеспе- чения (ПО), так и области применения. Традиционной сферой применения яв- ляется обработка строк, в качестве примера можно привести Рефал [5]. Здесь фундаментальной математичес- кой моделью являются алгорифмы Мар- кова, а вычисления – это последова- тельное применение правил к началь- ной цепочке строк. Подобное ПО встроено в почти каждую существую- щую систему морфологического ана- лиза. C развитием программной инже- нерии появилась потребность автома- тического анализа и преобразования программ, где объектами преобразова- ний являются синтаксические деревья конструкций языка программирования. Спектр применения таких систем – от автоматического генерирования доку- ментации до систем анализа ПО и ав- томатического перевода программ с одного языка программирования на другой. Автоматизация построения ло- гических доказательств это одно из наиболее естественных применений символьных вычислений. Здесь в осно- ве математической модели лежит логи- ческая редукция: шаг вычислений соот- ветствуют шагу логического вывода в некоторой системе аксиом в соответ- ствии с определенными правилами вы- вода. Известными формальными моде- лями в этом направлении являются комбинаторная логика [6] и π-исчис- ление [7]. На этой основе построен це- лый класс языков программирования и разработаны классы промышленных применений, в частности системы про- ектирования логических микросхем, высокоуровневые языки программиро- вания, экспертные системы. Особый класс составляют уни- версальные системы переписывающих правил, который появился в последние годы как альтернатива систем логиче- ского программирования. Характерной его особенностью является наличие Методы программирования 25 правил представления либо преобразо- вания объектов предметной области произвольной структуры в виде алгеб- раических термов, а также стратегий применения правил вывода, основан- ных на внелогических принципах, час- то в виде императивного алгоритма по- следовательности поиска и примене- ний правил. TermWare принадлежит к по- следнему типу систем наряду с APS [3], Maude [8] и Stratego [9]. В данной ста- тье описывается синтаксис и семанти- ка языка, демонстрируется примене- ние системы к задачам программиро- вания динамических приложений, ха- рактеризуемых, с одной стороны, вы- сокой степенью взаимодействий со средой, а с другой – высокой измен- чивостью требований и необходимо- стью перепрограммирования таких систем. 1. Назначение и особенности системы TermWare Система TermWare нацелена на разработку высокодинамичных при- кладных систем, к которым предъявля- ются повышенные требования как к встроенному интеллекту для обеспече- ния интерактивности разрабатываемых систем, так и к удешевлению разработ- ки, сокращению сроков проектирова- ния и улучшения характеристик по- вторного их использования (реинжени- ринга) и сопровождаемости. Она отли- чается от большинства других систем этого класса как назначением и семан- тикой используемых средств, так и тех- нологией их реализации. Язык Term- Ware не является универсальным язы- ком программирования в том смысле, что он не предназначен для написания полнофунциональных программных си- стем. Это координационный язык- оболочка [10], предназначенный для написания предметно-ориентированных частей приложений, встраиваемых в прикладную систему для реализации функций взаимодействия этой системы с программным окружением. Существенны также семантиче- ские особенности языка TermWare, от- личающие его от других разработок в данной области. Традиционное декла- ративное программирование с помо- щью парадигмы переписывания осно- вано на таком образце применения для написания программной системы, при котором строится формальная модель предметной области, в рамках этой формальной модели описываются ос- новные понятия и структуры данных предметной области, переписывающие правила применяются для реализации классического алгоритма, преобра- зующего вход в выход, и операции ввода/вывода и взаимодействия с дру- гими программами не представлены в декларативном описании в явном виде, а представляют собой побочные эф- фекты. Такой устоявшийся подход ма- лоприменим в индустрии программи- рования по следующим причинам. Во-первых, построение полного формального определения предметной области часто представляет собой слишком трудоемкий процесс для практического применения. Как пра- вило, предметная область включает в себя много уже построенных элемен- тов окружения, например реляцион- ные базы данных (БД), объектные мо- дели, протоколы межпрограммного взаимодействия. Для того чтобы ис- пользовать декларативное программи- рование, нужно представить все эти компоненты в одной формальной мо- дели, придавая формальную семантику уже построенным императивным мо- делям. Это делает процесс построения формальной модели слишком сложным и дорогостоящим. Во-вторых, совре- менные программные комплексы не могут быть прямо описаны как алго- ритмы в классическом смысле, т.е. как преобразователи входной информации в выходную. Очень часто программная система представляет собой некоторое поведение, включающее в себя взаи- модействие с внешней средой. И в- третьих, операции ввода/вывода, обычно представленные в декларатив- ном программировании как побочные эффекты, имеют слишком большое значение чтобы быть проигнорирован- Методы программирования 26 ными в формальной модели вычисле- ний. Отсутствие ввода/вывода в моде- ли означает невозможность анализиро- вать и преобразовывать механизмы взаимодействия программ с окружени- ем, что делает традиционные системы логического программирования мало- мощными и непригодными для важных классов приложений. В TermWare предложен новый формализм для декларативного описа- ния предметной области программиро- вания распределенных программных комплексов – термальные системы. Он включает в себя описание в виде термов как функциональности частей программных комплексов, подобно традиционным системам, так и их взаимодействия со внешней средой. Последнее представляет собой динами- ческую базу фактов во внутренней ло- гике системы, например состояние внешней среды в системе управления либо перечень текущих бизнес-про- цессов в системе управления потоками работ. Таким образом, вместо сокры- тия императивного стиля программи- рования в побочных эффектах в TermWare происходит погружение им- перативных операций в логику декла- ративной программы. Термальная сис- тема является открытой в том смысле, что она интерактивна и ее поведение определяется не только программным кодом, но и состоянием среды. Технологические отличия Term- Ware связаны с тем, что в современной индустрии разработки ПО уже не рас- сматривается отдельно от таких эле- ментов технологической платформы программного окружения, как базы данных, системы мониторинга тран- закций и унаследованные библиотеки. Однако большинство существующих систем предоставляют свое окружение, подразумевая, что конечный пользова- тель работает в оболочке системы сим- вольного программирования. TermWare оформлена как библи- отека языка Java, встраиваемая в про- граммное приложение. Для разработ- чика система термов выглядит как со- вокупность экземпляров класса ITerm- System, с возможностью управления набором правил и редуцирования тер- мов. База знаний также может содер- жать императивные элементы, описан- ные как Java-классы. Таким образом, имеется возможность использовать де- кларативную модель программирова- ния в программных комплексах, осно- ванных на Java-платформе в тех случа- ях, когда это необходимо. Разработчик может использовать термальную сис- тему как программный агент, встраи- ваемый в общую инфраструктуру про- граммной системы. Встраивание систем обработки правил в Java-платформу в последнее время быстро развивается и даже стандартизируется. Существует пред- ложение к стандарту языка Java (jsr94 [11]) и несколько систем, встраивае- мых в Java по тому же принципу, что и TermWare. Среди них можно выделить Jess [12] (порт CLISP) и ASDF [12], представляющие собой системы пере- писывающих правил, предназначенные для построения экспертных систем и преобразований деревьев синтаксиче- ского разбора соответственно. Поэтому разработка TermWare своевременна и необходима. 2. Формальная модель Формальная модель TermWare построена как обычная алгебра термов, где объектами языка являются термы, т.е. выражения вида f(x1, ..., xn), пере- менные и элементарные типы данных, подобно другим языкам функциональ- ного программирования. Единственное отличие от стандартного подхода со- стоит в том, что конструктор упорядо- ченного множества является выделен- ным термом и операции подстановки на этих термах сохраняют порядок. Вычисления определяются наборами переписывающих правил вместе со стратегией применений по такой же схеме, как и в АPS [3] или Strategо[9]. Основное отличие TermWare от языков алгебраического программиро- вания (таких, как OBJ и Maude [8]) со- стоит в том, что модель вычислений в TermWare определяется в терминах Методы программирования 27 поведения программ, т.е. входных воз- действий и реакций, а не в терминах входа и выхода, как это происходит при традиционном подходе. Иными словами, в традиционных системах пе- реписывающих правил вычисления яв- ляются преобразованиями входного терма в некоторую каноническую форму с помощью набора переписы- вающихся правил. Тем самым язык оп- ределяет функциональные зависимости вида f(x) = y, где x – вход алгоритма; y – выход в терминах классической теории алгоритмов. В TermWare набор переписывающих правил определяет не вычисления целиком, а один шаг вычислений, в терминах теории дина- мических систем [14] – вида f(x, s) → → (s', y), где x – входной сигнал; y – выходной, s – внутреннее состояние. В этом разделе представлена от- носительно простая синтаксическая формальная модель и показано, как на ее основе можно организовать работу с более общими структурами. Считаем, что алфавит языка включает (везде, если это не оговорено особо, нижние индексы принадлежат перечислимому множеству): • множество констант ci, при- надлежащих одному из примитивных типов (INT, BOOL, STRING, ATOM); с каждой константой связано значение на множестве соответствующего при- митивного типа; • INT – множество целых чисел, представляемое константами 1, 2, ....; • BOOL – множество булевых значений, представляемое константами true и false; • STRING – множество строк в алфавите Unicode; • ATOM – множество атомар- ных неинтерпретируемых значений; среди атомов выделим NIL, играющий специальную роль. Кроме того, язык включает так- же множество терминальных символов t1, ..., tN, множество пропозициональных переменных xi, скобки '(' и ')' и знак зяпятой ',' множество функциональных символов fi, символ среды S, множество ϕ модельных символов операций чте- ния информации из среды, а также множество δ модельных символов воз- действия на среду. Термы языка строятся по сле- дующей схеме. Сначала определяется множество конкретных термов Tc: • ci ∈ Tc; • если x1 ∈ Tc, ..., xN ∈ Tc, то и f есть функциональный символ, f(x1, ..., xN) ∈ Tc, а также множество подстановочных термов Tv: • x∈Tc ⇒ x∈Tv; • xi ∈Tv; • x1 ∈ Tv, ..., xN ∈ Tv ⇒ f(x1, ..., xN) ∈ Tv. Терм, принадлежащий разности множеств Tv\Tc, назовем термом со сво- бодными переменными, а для каждого терма t множество входящих в него нетерминальных символов – множе- ством свободных переменных этого терма и обозначим ν(t). Далее на системе термов опреде- лим следующие синтаксические функ- ции и их свойства: • функция typename0: Tv → STRING возвращает синтаксический тип терма; это может быть: наименование одного из типов "BOOL", "INT", "ATOM" или "STRING" для примитивных термов; ”x” для пропозициональных переменных; ”T” для сложных термов; • функция name: Tv → STRING возвращает имя головного символа терма; • функция arity: Tv → STRING возвращает арность символа терма; • функция subterm: Tv × INT → Tv вычисляет индекс подтерма начиная с нуля: если t ∈ Tv, i < arity(t), то sub- term(t) возвращает i-й субтерм t; если i > arity(t), то subterm(t) = = NIL; • функция equal: Tv × Tv → BOOL возвращает истинное значение в слу- чае тождественного совпадения x = y; Методы программирования 28 • функция less: Tv × Tv → BOOL определяется такими случаями: если x ≠ NIL, то less(NIL, x); если typename0(x) < typena- me0(y), то less(NIL , x); если x, y – константы, то less(x, y) представляет собой естест- венное упорядочение; если x, y – атомы, то less(x, y) представляет собой лексикографи- ческое упорядочение их имен; если x, y – пропозицио- нальные переменные, то имеет ме- сто ¬less(x, y) ∧ ¬less(y, x); если x, y – составные тер- мы и arity(x) < arity(y), то less(x, y) = = true; если x, y – составные тер- мы и arity(x) = arity(y) ∧ less(name(x), name(y)), то less(x, y) = true; если x, y – составные тер- мы и arity(x) = arity(y) ∧ name(x) = = name(y), то less(x, y) представляет собой лексикографический порядок кортежей элементов. Таким образом, множество тер- мов (с точностью до перенумерации пропозициональных символов) являет- ся полностью упорядоченным. Это по- зволяет выделить конструктор упоря- доченного множества set(x1, …, xN), т. е. терм, обозначающий упорядоченное множество из N элементов. Отсюда можно полагать, что если t = set(x1, …, xN), subterm(i, t) = x, subterm(j, t) = y, o < i < j < < arity(t), то less(x, y). Теперь ν(t) можно определить уже на синтаксическом уровне: ν(ci) = NIL, ν(xi) = {xi}, ν(f(t1, ..., tN)) = )( 1 i n i xU = ν . Выражение subst(t, x, s) есть под- становка s в t вместо свободной пере- менной x. Будем также употреблять для подстановки обозначение t[x, s]. Терм bound_unify(t1, t2) означает операцию унификации t1 и t2 со множеством свя- занных пропозициональных перемен- ных, входящих в t1 и t2, free_unify(t1, t2) – операцию унификации t1 и t2, при ко- торой свободные переменные t1 и t2 предварительно переименовываются таким образом, чтобы v(t1) ∩ v(t2) = ∅. Семантика правила переписыва- ния без взаимодействия со средой оп- ределяется в виде apply(t, x→ y) = subst(y, free_unify(x,t)), где x → y – правило пе- реписывания терма х в у. Любую среду S можно представить как БД фактов, определив акты взаимодействия терма со средой с помощью функций ϕ: S × Tc → → Tc (получение информации из S) и δ: S × Tc → S (передача информации в S). Наконец, определим основной объект нашего рассмотрения – тер- мальную систему. Термальная система τ есть пара τ = (S, R), где S – модель сре- ды, а R – набор переписывающих правил, представляющий взаимодейс- твие со средой. Переписывающее пра- вило из R – это терм с четырьмя ар- гументами вида rule(x, in, y, out), кото- рое для удобства обозначим x[in] → → y//out. Такое выражение можно про- читать как “переписать x при условии in в у, применив к среде операцию out”. С использованием введенных выше обозначений схему выполнения правила переписывания можно запи- сать в виде apply((S, t), x[ϕ] → y//δ) = = (δ(S, free_unify(z, out)), z), где z = subst(y, free_unify(x, t, ϕ(S, in))). Наконец, последний шаг – доба- вим в модель понятие имени системы и множества систем. Имя системы – это атом либо специальный терм _name(x1, ..., хn), где x1, …, xn – атомы. Считаем, что интерпретация терма _name(x1, ..., хn) определяется функцией именования φ: Tc → Φ, которая возвра- щает определение термальной системы в некотором (иерархическом) про- странстве имен Φ. Саму терминальную систему можно определить как терм вида System(name, ruleset, facts, strategy), где name – имя системы; ruleset – множество правил переписывания со взаимодействием; facts – база данных фактов среды; strategy – стратегия Методы программирования 29 применения переписывающих правил, определяющая последовательность при- менения правил. Функция редуцирова- ния терма в системе выражается в ви- де терма reduce(s, t), где t – терм, реду- цируемый в системе с именем s. Таким образом, TermWare – это непосредственное отображение логи- ческой модели взаимодействий в язык программирования, обладающее анало- гами современных средств поддержки наследования и иерархической систе- мы имен. Ниже покажем, что такие системы более естественно отражают типичные проблемы программирова- ния на уровне архитектуре и пригодны для описания не только вычислитель- ных алгоритмов, но и поведения про- граммных комплексов, состоящих из нескольких взаимодействующих под- систем. 3. Реализация языка Формальная модель, изложенная выше, отображается в языке програм- мирования с помощью следующих средств и соглашений. Терминальные символы: • константы – это числа, логи- ческие значения и строки Unicode с обычной семантикой; • пропозициональные перемен- ные начинаются знаком доллара и продолжаются последовательностью букв или цифр, например $x10, $saved_args; • идентификаторы – последова- тельности из букв и цифр; • конструкторы термов имеют традиционный функциональный вид f(x1, ..., xn); • в языке используются знаки →, [\| \|], &, \|, &&, \|\|, +, -, *, /, //, ^, <<, >>, <, <=, >, =>, ==, !=, !; • комментарии – это строки, начинающиеся знаком #. В целях удобочитаемости в TermWare определен синтаксис, по- добный языку C. Выражение x [\| y\| ] → → z // v является сокращением для rule(x, y, z, v) и обозначает переписы- вающее правило с входным образцом x, условием y, выходным образцом z и действием v. В случае, если один или несколько элементов отсутствуют, они могут быть опущены. Далее установле- но соответствие для других выражений языка и их сокращений: {x \| y} – явля- ется сокращением для set_pattern(x, y); {x1, ..., xN} – для set(x1, ..., xN); x in y – для _in(x, y); [x1, ...., xN] – для cons(x1, cons(... cons(xN)...); x ? y: z – для ifelse(x, y, z); x + y – для plus(x, y) и аналогично для всех инфиксных операторов языка C. Переписывающие правила объе- диняются в наборы с помощью терма ruleset, например, набор правил, описы- вающий булеву алгебру, описывается так: ruleset( $x & ($x => z) -> $z, not($x & $y) -> not($x) \| not($y), not($x \| $y) -> not($x) & not($y), $x & ($y \| $z) -> ($x & $y) \| ($x & $z), not(not($x)) -> $x, ). Термальная система описывается с помощью выражения System(x, y, z, v), например: System(BooleanAlgebra, default, ruleset( $x & ($x => z) -> $z, not($x & $y) -> not($x) \| not($y), not($x \| $y) -> not($x) & not($y), $x & ($y \| $z) -> ($x & $y) \| ($x & $z), not(not($x)) -> $x, ), FirstTop); Здесь первый подтерм – это имя системы, второй – имя базы данных фактов, после чего следуют набор пра- вил переписывания и стратегия при- менения. В приведенной выше схеме использована пустая баз данных и стратегия переписывания FirstTop. База данных фактов и стратегия переписывания определяются на уров- не процедурного языка в зависимости от предметной области. Как это проис- ходит, покажем в следующем разделе, Методы программирования 30 а пока обратим внимание еще на две особенности языка. Система имен в TermWare представляет собой иерар- хию с целью структуризации инфор- мации: подсистемы можно организо- вывать в области (domains) так же, как в Java классы объединять в пакеты (packages). Термальные системы могут повторно использовать информацию с помощью механизма импорта правил аналогично механизму наследования в объектно-ориентированных языках. System(BooleanLogic, defaut, ruleset(import(BooleanAlgebra), true => $x -> $x, false => $x -> not($x), true \| $x -> true, false \| $x -> $x, true & $x -> $x, false & $x -> false, not(true) -> false, not(false) -> true ), FirstTop) 4. Встраивание в приложения Предыдущие примеры систем несколько ограничены и не использу- ют основные элементы новизны дина- мической модели – БД фактов и дей- ствия. Отчасти это вызвано тем, что TermWare предназначается для встраи- вания в приложения, а БД фактов и набор действий зависит от конкретных особенностей приложений. Встраива- ние элементов логического вывода в приложения и проектирование набора БД фактов и действий при использова- нии TermWare обычно осуществляются по следующей стратегии: • в программе выделяется под- система, где уместно использовать дек- ларативные правила; • определяется взаимодействие с остальной частью комплекса в виде набора функций получения информа- ции (условий) и передачи информации (действий); • полученный набор взаимодей- ствий представляется в виде Java- класса (который должен реализовать интерфейс IFacts); • определяется стратегия при- менения правил: при этом либо выби- рается одна из существующих, либо программируется реализация интер- фейса IStrategy; • происходит встраивание Term- Ware в приложение либо с помощью прямого вызова конструктора объекта ItermSystem, либо путем определения на языке TermWare соответствия меж- ду именами БД фактов (стратегий) и реализующими их классами Java. Общая схема создания БД фак- тов путем реализации интерфейс Ifacts имеет следующий вид: public interface IFacts { public String getDomainName(); public boolean check(ITerm t) throws TermWareException; public void set(ITerm t) throws TermWareException; public void remove(ITerm t) throws TermWareException; } Когда при интерпретации правил переписывания встречается запрос информации из внешней среды, TermWare вызывает метод check ассо- циированной базы данных фактов; ес- ли встречается действие, вызывается метод set. Существует вспомогатель- ный класс DefaultFacts, который с по- мощью рефлективного прикладного интерфейса Java самостоятельно осу- ществляет разбор аргументов. Собственно термы представля- ются разработчику как объекты, реа- лизующие интерфейс ITerm. В сигна- туре ITerm определены операции опре- деления типа, доступа к типизирован- ным значениям, унификации, эквива- лентности и лексикографического сравнения. Объем статьи не позволяет привести здесь эту сигнатуру полно- стью. Для демонстрации возможностей программирования приведем в качест- ве примера описание широко извест- Методы программирования 31 ной игры Конвея "жизнь" [15], исполь- зуя БД фактов для представления ин- формации о поле. Соответствующая термальная система выглядит следую- щим образом: domain(examples, system(Life1,LifeDB, ruleset( # $T - set of pairs to test. { l($i,$j) \| $T} [\| existsCell($i, $j)) && (n($i,$j)==2\|\|n($i,$j)==3) \|] -> $T // putCell($x,$y), { l($i,$j) \|$T } [\| n($i,$j) == 3 \|] -> $T // putCell($x,$y), { l($i,$j) \|$T } [\| n($i,$j) <2 \|\| n($i,$j)>3 \|] -> $T // remove- Cell($x,$y), { } -> $T // showGeneration() && createNewTestSet($T) ), FirstTop) ); Как видно, из БД запрашивают- ся следующие факты и условия: 1) existsCell(i, j) – существует ли клет- ка по адресу i, j и 2) n(i, j) – количе- ство соседей клетки. К действиям от- носятся: • putCell(i, j) – поместить клетку в ячейку i, j; • removeCell(i, j) – удалить клетку; • showGeneration() – показать на экране следующее поколение; • createNewTestSet($T) – сгене- рировать новое тестовое множество клеток. В сокращенном виде соответст- вующий класс БД выглядит следующим образом: class LifeFieldFacts exstends DefaultFacts { private int nX_; private int nY_; private boolean[][] field_; private boolean[][] nextField_; private Canvas drowing_; public ITerm existsCell(ITerm tx, ITerm ty) throws TermWare- Exception { int x = tx.getInt(); int y = ty.getInt(); return ITermFactory.create- Boolean(field_[x%nX][y%nY]); } public void putCell(ITerm tx, ITerm ty) throws TermWareException { int x = tx.getInt(); int y = ty.getInt(); nextField_[x%nX][y%nY] = true; } public void generateNewTest- Set(ITerm t) throws TermWareException { if (!t.isX()) { throw new TermWareException (”ar- gument of generateNewTestSet mus be propositional variable”); } SetTerm retval = ITermFac- tory.createSet(); field_ = nextField_; nextField_ = createNewField(); for(int i=0; i<nX; ++i) { for(int j=0; j<nY; ++j) { if (field_[i][j]) { retval.insert(createComplex- Term2(”l”, (i-1)%nX,(j-1)%nY)); retval.insert(createComplex- Term2(”l”,(i-1)%nX,(j )%nY)); retval.insert(createComplex- Term2(”l”,(i-1) %nX,(j+1)%nY)); retval.insert(createComplex- Term2(”l”,(i ) %nX,(j-1 )%nY)); retval.insert(createComplex- Term2(”l”,(i ) %nX,(j )%nY)); retval.insert(createComplex- Term2(”l”,(i ) %nX,(j+1)%nY)); Методы программирования 32 retval.insert(createComplex- Term2(”l”,(i+1) %nX,(j-1)%nY)); retval.insert(createComplex- Term2(”l”,(i+1) %nX,(j )%nY)); retval.insert(createComplex- Term2(”l”,(i+1) %nX,(j+1)%nY)); } } } // fill the value of the proposi- tional variable. tx.subst(tx.minFv(),retval); } } Обратим внимание на подста- новку вместо пропозициональной пе- ременной множества в действии generateNewTestSet. Этот пример иллю- стрирует передачу информации из им- перативной части программы в ее ло- гическую часть. Выводы Таким образом, разработанная система дает возможность проектиро- вать интеллектуальную составляющую приложений с учетом существующих технологических платформ и естест- венно сочетать императивный и логи- ческий стили программирования с по- мощью общей объектно-ориенти- рованной среды. Это облегчает как проектирование приложений, так и модификацию бизнес-логики, которую можно задавать независимо от внеш- ней среды. В настоящее время TermWare применяется в системах организации потока работ, где с помощью логиче- ских правил описываются бизнес- процессы, а в качестве БД фактов вы- ступает взаимодействие с исполните- лями и данными о текущем состоянии бизнес-процессов [16]. Еще одна об- ласть применения – это анализ структур программ, позволяющая вы- делять шаблоны проектирования [17] и проводить анализ корректности кода относительно известного множества типичных погрешностей проектирова- ния [18]. Особенный интерес пред- ставляет семантический анализ моде- лей UML[19] в распределенных про- граммных комплексах [20], [21]. Система TermWare реализована в ООО Град-Софт. Более детальное описание и некоторые приложения доступны на Web-странице: http://- www.gradsoft.kiev.ua 1. Dershowitz N., Jouannaud J.-P. Rewrite Sys- tems // Handbook of Theoretical Computer Science. Vol. B: Formal Models and Seman- tics / Ed. J. van Leeuwen. – Boston: Elsevier and MIT Press, 1990. – P. 243—320. 2. АНАЛИТИК—74 / В.М. Глушков, Т.А. Грин- ченко, А.А. Дородницына и др. // Кибер- нетика. – 1978. – № 5. – С. 114—147. 3. Капитонова Ю.В., Летичевский А.А. Мето- ды и средства алгебраического программи- рования // Кибернетика и системный ана- лиз. – 1993. – № 3. – C. 7—12. 4. Parallel Symbolic Simulation Using the Alge- braic Programming System / A.A. Letichevsky, J.V. Kapitonova, A.E. Doroshenko, V.A. Volkov // Algebraic Engineering: Proc. Intern. Conf. on Semigroups and Algebraic Engineering. – Sin- gapore: World Scientific, 1999. – P. 350—360. 5. Refal-5: Programming Guide and Reference Manual. – Holyoke MA: New England Publishing Co., 1989. – 342 p. 6. Semantics of Constraint Logic Programs / J. Jaffar, M.J. Maher, K.G. Marriott, P.J. Stu- ckey // J. of Logic Programming, – 1998. – 37. – P. 1—46. 7. Milner R. Communicating and Mobile Sys- tems: the π-calculus. – Cambridge: Univer- sity Press, 1999. – May. – 174 p. 8. Winkler T. Programming in OBJ and Maude // Functional Programming, Concurrency, Simu- lation and Automated Reasoning / Ed. P. Lauer. – LNCS. – 1993. – 693. – P. 229—277. 9. Visser E. Stratego: A language for program transformation based on rewriting strategies. System description of Stratego 0.5 // Rewrit- ing Techniques and Applications (RTA'01) / Ed. A. Middeldorp, Ibid. – 2001. – 2051. – P. 357—361. 10. Gelernter D. Carriero N. Coordination Lan- guages and Their Significance // Comm. ACM. – 1992. – 35, № 2. – Р. 97—107. 11. JSR-000094 JavaTM Rule Engine API. – http://www.jcp.org/aboutJava/communitypro- cess/ review/jsr094/. 12. Jess – the expert system shell for the Java Platform. – http://herzberg.ca.sandia.gov/- jess/ri_overview.shtm. 13. Efficient annotated terms / M.G.J. van den Brand, H. de Jong, P. Klint, P. Olivier // Soft- ware, Practice & Experience. – 2000. – 30(3). – P. 259—291. 14. Капитонова Ю.В., Летичевский А.А. Мате- матическая теория проектирования вычис- Методы программирования 33 лительных систем. – М.: Наука, 1988. – 296 c. 15. Эндрюс Г.Р. Основы многопоточного, па- раллельного и распределенного програм- мирования. – М.: Вильямс, 2003. – 506 c. 16. Shevchenko R., Doroshenko A. Managing Busi- ness Logic with Symbolic Computation // Information Systems Technology and Applica- tions: Proc. 2-nd Intern. Conf. ISTA'2003, June 19—21, 2003, Kharkiv, Ukraine. – Kharkiv, 2003. – P. 143—152. 17. Design Patterns: Elements of Reusable Object Oriented Software / E. Gamma, R. Helm R. Jonhson, J. Vlissides. – Reading, MA: Addi- son-Wesley, 1995. –329 p. 18. Liang, M., Harrold J. Light-Weight Context Recovery for Efficient and Accurate Program Analysis // ICSE 2000: Proc. 22-nd Intern. Conf. Software Engineering, June 4—11, 2000, Limerick, Ireland. – New York: ACM Press, 2000. – P. 366—406. 19. UML 2.0 Specification. – http://www.omg.- org/technology/uml/. 20. Shevchenko R., Doroshenko A. Evolution of CORBA Framework: An Experience Study, Case studies of CSMR 2002, Workshop Proc. 6-th European Conf. on Software Maintenance and Reengineering, March 11—13, 2002, Bu- dapest, Hungary. – Budapest, 2002. – P. 3—9. 21. Shevchenko R., Doroshenko A. A Method of Mediators for Building Web Interfaces of CORBA Distributed Enterprise Applications // Information Systems Technology and its Ap- plications: Proc. Intern. Conf. ISTA-2001, June 13—15, 2001, Kharkiv, Ukraine. – Kharkiv, 2001. – 4. – P. 53—63. Получено 23.11.03 Об авторах Дорошенко Анатолий Ефимович, доктор физ.-мат.наук, профессор, заместитель директора по научной работе Шевченко Руслан Сергеевич, аспирант Место работы авторов Институт программных систем НАН Украины, просп. Академика Глушкова, 40, Киев-187, 03680, Украина Тел. 266 1538 E-mail: dor@isofts.kiev.ua, Ruslan@Shevchenko.kiev.ua

Symbolic computation system for dynamical application programming

Репозитарії

Схожі ресурси