Выполнен второй этап проекта, направленного на разработку методов и средств функционального программирования поддержки супервычислений в рамках современных технологий, связанных с развитием телекоммуникационных сетей и центров коллективного пользования (ЦКП).

Проведены работы по развитию моделей и методов преобразования программ, ориентированных на эффективное исполнение функциональных программ на ЭВМ различных параллельных архитектур, уточнен набор промежуточных представлений транслируемых программ и входной язык системы параллельного программирования SFP.

Разрабатывается макет и технический проект системы поддержки параллельного программирования SFP. Система включает следующие компоненты: интерфейс, отладчик, front-end транслятор, блоки промежуточных представлений IR1, IR2 и IR3, блоки анализа, преобразования и визуализации IR1, IR2 и IR3, конверторы промежуточных представлений, back-end трансляторы.

Kasyanov V.N., Evstigneev V.A., Malinina J.V., Birjukova J.V., Markin V.A., Haritonov E.V., Tsikoza S.G. Support tools for supercomputing and networking // Lect. Notes Comput. Sci. – 1999. – Vol.1593.

Kasyanov V.N. Support tools for supercomputing // ICIAM-99: The Fourth International Congress on Industrial and Applied Mathematics, Edinburg. – 1999.

Евстигнеев В.А., Мирзуитова И.Л. Анализ циклов: выбор кандидатов на распараллеливание. / Препринт ИСИ СО РАН.. № 58. 1999. – Новосибирск.

Евстигнеев В.А. Основы параллельной обработки. Векторизация программ. – Новосибирск: НГУ, 1999. – 116 с.

Лобив И.В., Мурзин Ф.А. О распараллеливании PIC-метода // Проблемы систем информатики и программирования. – Новосибирск, 1999. – С. 146-155.

Бурдонов И.В., Мурзин Ф.А. О распараллеливании метода "МЕДУЗА" // Междунар. конф.: Математические модели и методы их исследования (задачи механики сплошной среды, экологии, технологических процессов, экономики). – Красноярск, 1999.

Выполнен первый этап проекта, посвященный разработке и формированию открытой информационной системы "ПАРАДИГМЫ", предназначенной для анализа и интеграции систем, направленных на фундаментальные исследования в области информатики.

Фактически проделанная работа заключается в определении ядра информационной системы, разработке ее эскизного проекта и отборе материалов для ее наполнения.

Подготовлен обзор наиболее значимых для фундаментальных исследований по информатике парадигм программирования, отражающих требования прикладного, теоретического, учебного и экспериментального программирования, а также парадигм программирования в рамках современных информационных технологий. Подобрана библиография для начального знакомства с концепциями информатики. Сформулированы требования к заполнению формуляров на компоненты системы.

Проектирование макетного образца ориентировано на методику раскрутки информационной системы из минимального ядра с помощью комплекта типовых компонентов. Определен состав ядра и номенклатура компонентов. Отлажены структуры табличных форм и разработаны интерфейсные механизмы и семантика запросов для применения информационной системы при специализации в области информатики и программирования.

В результате построен макетный образец информационной системы ПАРАДИГМЫ, обеспечивающий начала специализации студентов в области системного программирования и образовательной информатики. Макетный образец ориентирован на дистанционное применение.

Городняя Л.В., Калинина Н.А. О формировании информационных систем области информатики и программирования // Тез. докл. конф. Сибирского Энергетического Института. – Иркутск, 1999. – С. 9.

Калинина Н.А., Хегай Ж.Э. Информационно-образовательная среда на базе систем компьютерной алгебры: опыт разработки // Дистанционное образование. – 1999. – № 5. – C. 18-23.

В 1999 году в рамках данного проекта разработана комплексная формальная модель представления и обработки знаний, включающая аппарат управления по данным и событиям. Эта модель построена путем интеграции основных классических (фреймы, семантические сети, продукционные системы) и ряда современных средств и методов представления знаний и включения средств, поддерживающих процессы вывода/обработки данных и знаний на основе оригинальной схемы управления по данным и событиям. Аппарат управления по данным основан на методе недоопределенных вычислительных моделей (одном из универсальных методов программирования в ограничениях), а аппарат управления по событиям построен на основе развития аппарата управления по данным.

Основным средством представления декларативных знаний в модели является семантическая сеть, состоящая из объектов, связанных бинарными отношениями. Важной особенностью объектов является то, что их слоты (атрибуты) могут иметь недоопределенные (неточные) значения. Для автоматического уточнения значений слотов на них задаются ограничения – логические выражения, связывающие значения слотов объекта (или нескольких объектов). Активация и интерпретация ограничений реализуется на основе аппарата управления по данным.

Процессы вывода и обработки информации главным образом задаются в виде системы агентов. Агент – это объект специального вида, действия которого определяются не командами централизованного императивного управления, а состоянием среды и происходящими в ней событиями. Активация каждого агента осуществляется ассоциативным потоковым механизмом, реагирующим только на относящиеся к этому агенту события (появление объектов и/или изменение их атрибутов, установление между ними новых отношений). Срабатывание агента может привести к появлению в сети новых объектов или изменению значений параметров существующих. Это, в свою очередь, повлечет активацию других агентов, связанных с появившимися или изменившимися объектами и т.д. В соответствии с этой схемой, агенты активируются параллельно и асинхронно по мере появления (изменения) объектов семантической сети. При этом потоковый механизм активации агентов целиком основывается на общем механизме управления по данным.

Введение в модель средств управления по событиям вместо ресурсоемкого аппарата продукционных правил должно значительно повысить эффективность обработки знаний и данных. Что касается продукционных правил, то они играют вспомогательную роль и могут использоваться в исполнительной части агентов с целью повышения гибкости данной модели. При этом они не снижают общую эффективность предлагаемых средств, так как необходимость операции поиска по образцу практически отсутствует из-за того, что область действия таких правил локализуется в спецификации агента.

Благодаря тому, что интеграция средств представления и обработки знаний осуществлена на основе развития объектно-ориентированного подхода, весь спектр указанных средств доступен в виде единого языка представления и обработки знаний.

Эксперименты показали удобство и эффективность использования этого языка для решения задач обработки коротких текстов в ограниченных предметных областях. В частности, макетная версия языка опробована при разработке экспериментальной системы понимания метеорологических телеграмм.

Zagorulko Yu.A., Popov I.G., Karakozova O.B. An approach to the Development of a Knowledge Representation and Processing System with the Use of Agent-Based Technique. // Proc. of the 1-st Inter. Workshop of Central and Eastern Europe on Multi-Agent Systems (CEEMAS-99), St.Peterburg. – 1999. – P. 313-320.

Kononenko I.S., Popov I.G., Zagorulko Yu.A. Approach to understanding weather forecast telegrams with agent-based technique. // Proc. of the 3^rd Intern. Andrei Ershov Memorial Conf. "Perspectives of System Informatics", Novosibirsk, 1999. – Berlin a.o.: Springer, 2000. – P. 506-511. – (Lect. Notes Comput. Sci.; 1755).

Popov I., Shvetsov I., Zagorulko Yu. Strategic knowledge in Integrated Knowledge Representation Model // Proc. of the 2-nd International Workshop on Strategic Knowledge and Concept Formation (SKW'99), Iwate, Japan, October 1999. – P. 73-84.

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

Gaudel M.–C., Khoury C., Zamulin A.V. Dynamic systems with implicit state // Proc. of the 2-nd Intern. Conf. on Fundamental Approaches to Software Engineering (FASE/ETAPS'99), Amsterdam. – Berlin a.o.: Springer, 1999. – P. 114-128. – (Lect. Notes Comput. Sci.; 1577).

Lellahi K., Zamulin A.V. Dynamic Systems Based On Update Sets. / Tech. Report N99-03, LIPN, Univ. Paris 13, France. – 1999. – 21 p.

Zamulin A.V. Adding genericity to object-oriented ASMs. // Preprint IIS SB RAS. № 60. – Novosibirsk, 1999. – 28 pp.

Gaudel M.–C., Zamulin A.V. Algebraic Imperative Specifications // Proc. of the 3^rd Intern. Andrei Ershov Memorial Conf. " Perspectives of System Informatics ", Novosibirsk, 1999. – Berlin a.o.: Springer, 2000. – P. 17-39. – (Lect. Notes Comput. Sci.; 1755).

Zamulin A.V. Algebraic specification language Ruslan 99. // Preprint IIS SB RAS. № 66. – Novosibirsk, 1999. – 34 pp.

Годель Т.–К., Хури К., Замулин А. Динамические системы с неявным состоянием // Программирование. – 1999. – № 4. – С. 30-42.

Замулин А.В. Механизм для формального описания динамических систем // Программирование. – 1999. – № 5. – С. 3-14.

Lellahi K., Zamulin A. Dynamic Systems with Update Sets // Proc. 2^nd Int. Conf. on Computer Science and Information Technolodies, Erevan, 1999. – P. 346-349.

Замулин А. В. Формальные методы спецификациии программ. – Новосибирск: НГУ, 1999. -83 стр.

Завершена работа по точной формулировке критериев добротности императивных программ. Конструктивная формулировка этих критериев включает 5 классов критериев, условия удовлетворения которым формулируются в терминах пред- и постусловий и информационных влияний.

Для языков Оберон-2, Модула-2 и Java реализован межпроцедурный контекстно-чувствительный потоковый анализ с четкой дифференциацией обязательных и возможных информационных связей и контекстно-чувствительной мультиинтервальной аппроксимацией значений скалярных переменных. Впервые обосновано, что именно такой анализ необходим, чтобы работающий на его базе статический анализатор ошибок был бы практически эффективным.

В целях оптимизации потокового анализа разработан многофазный анализ, в котором результаты контекстно-нечувствительного анализа используются для ускорения контекстно-чувствительного; причем контекстно-нечувствительный анализ разработан посредством специализации контекстно-чувствительного.

Разработана модель статического анализа ошибок. Сформулированы необходимые условия, а также эффективно распознаваемые достаточные условия того, что обнаруженная анализатором потенциальная ошибочная ситуация является достоверной ошибкой.

На базе потокового анализа разработан статический анализатор ошибок OSA для языков Оберон-2, Модула-2 и Java в окружении системы программирования XDS для OS/2, Windows 95/NT и SunSparc. Анализатор OSA контролирует все виды ошибок, определяемых динамической семантикой языков, а также нарушения критериев добротности программы. В рамках оболочки системы программирования XDS реализован визуализатор сообщений, обеспечивающий автоматическое позиционирование в тексте программы для сообщений анализатора ошибок. На базе гиперграфового представления анализируемой программы разработаны алгоритмы потокового анализа Java-программ при наличии исключительных ситуаций.

Разработан функционирующий смешанный вычислитель для языка программирования Модула-2. Смешанный вычислитель обеспечивает нетривиальную поливариантную специализацию всех конструкций языка, гарантированно сохраняя эквивалентность исходной и остаточной программы в рамках контекста специализации, который, помимо частично известных доступных данных, включает свойства операционной системы, конкретной системы программирования и т.п. Разработана и доведена до уровня продукта конечного пользования операционная обстановка смешанных вычислений, обеспечивающая, помимо собственно процесса специализации, визуализацию результатов анализа программ, производимых смешанным вычислителем, сравнение качества остаточных и исходных программ.

Работы по проблематике тестирования проводились в рамках разработки прототипа системы автоматического построения тестов с "заданными" свойствами. Разработана статическая модель программы для автоматического построения тестов, реализация которой выполнена с использованием потокового анализатора OSA. Разработан прототип системы, в котором в качестве пакетно-диалоговой среды использовался доработанный вариант отладчика XD (в системе программирования XDS для Модулы-2), реализован цепочечный метод автоматического построения тестов.

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

Поттосин И.В. "Хорошая программа", попытка точного определения понятия // Программирование. – 1997. – № 2. – С. 3-17.

Pottosin I.V. A "Good Program": An Attempt at an Exact Definition of the Term // Programming and Computer Software. – 1997. – N 2. – P. 59-69.

Поттосин И.В. О критериях добротности программ // Системная информатика. Вып.6. – Новосибирск: Наука, 1998. – С. 90-122.

Поттосин И.В. Добротность программ и информационных потоков // Открытые системы. – 1998. – Т. 6. – С. 41-45.

Куксенко С.В., Шелехов В.И. Статический анализатор семантических ошибок периода исполнения // Программирование. – 1998. – № 6. – С.23-43.

Shelekhov V.I., Kuksenko S.V. Data Flow Analysis of Java Programs in the Presence of Exceptions // Proc. of the 3^rd Intern. Andrei Ershov Memorial Conf. " Perspectives of System Informatics ", Novosibirsk, 1999. – Berlin a.o.: Springer, 2000. – P. 385-391.. – (Lect. Notes Comput. Sci.; 1755).

Shelekhov V.I., Kuksenko S.V. On the Practical Static Checker of Semantic Run-time Errors // Proc. of the 6-th Asia Pacific Software Engineering Conf. APSEC'99, Takamatsu, Japan, 1999. – IEEE Computer Society Press, 1999.

Кауфман А.В, Черноножкин С.К. Критерии тестирования и система оценки полноты набора тестов // Программирование. – 1998. – № 6. – С. 44-59.

Черноножкин С.К. Меры сложности программ. Обзор // Системная информатика. Вып. 5. – Новосибирск: Наука, 1997. – С. 188-227.

Кауфман А.В., Черноножкин С.К. ОСТ: система контроля тестированности Модула-2-программ. // Препринт ИСИ СО РАН. № 38.– Новосибирск, 1997. – 47 стр.

Бульонков М.А., Кочетов Д.В. Визуализация свойств программ. /Препринт ИСИ СО РАН.. № 51. – Новосибирск, – 1997.

Емельянов П.Г. Абстрактная интерпретация императивных программ // Системная информатика. Вып.6. – Новосибирск: Наука, 1997. – С. 7-47.

Емельянов П.Г. Методы и средства статического анализа семантических свойств программ. Автореф. канд. дисс. Новосибирск: ИВМиМГ СО РАН. – 1997.

Emelianov P.G., Baburin D.E. Semantic analyzer of Modula-programs // Proc. of the Fourth International Static Analysis Symposium, 1997. – P. 361-363. – (Lect. Notes Comput. Sci.; 1302).

Emelianov P.G. Analysis of equality relationships: proofs and examples // Joint Bulletin of NCC&IIS. Ser.: Comp. Sci. -1999. – N 9. – P. 15-38.

Были проведены исследования по уточнению концепции создания однородного поля документов, включая документы типа библиографических карточек. В результате исследования была выяснена необходимость определения и фиксации базовых свойств идентификации документов и коллекций в пространстве Интернет, а также стандартизации структуры метаданных для документов произвольного вида. Такая концепция сформировалась и была изложена в докладе на Первой Всероссийской научной конференции "Электронные библиотеки: перспективные методы и технологии, электронные коллекции" (19-21 октября 1999 г., Санкт-Петербург) и в статье, принятой к публикации в журнале "Программирование".

Были получены следующие важнейшие результаты: исследованы возможности применения идей объектно-ориентированного программирования, интероперабельных, клиент-серверных и PROXY систем для построения целостной системы идентификации и регистрации документов и коллекций в пространстве Интернет. Основой подхода является взгляд на документ как на объект в смысле объектно-ориентированного программирования.

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

Определена роль регистрации документов в информационном пространстве. Зарегистрированный документ приобретает свойство перемещаемости оригинала. Это означает, что для него логическое имя документа дает способ достижения текущего оригинала вне зависимости от физической привязки оригинала к тому или иному хранилищу. Регистрация также дает возможность отделить метаинформацию о документе от информационной составляющей документа.

Рассмотрена задача синхронизации доступа к документу, предложен простой в реализации подход, удобный для квазистатических объектов, которыми являются документы. Изучена возможность использования копий экземпляров документов вместо оригиналов. Такая возможность позволяет уменьшать нагрузку на ресурсы в неоднородном по доступу информационном пространстве, а также решать другие аналогичные задачи.

Осуществлена экспериментальная реализация предложенного подхода для XML-документов. Анализ свойств реализованной системы позволяет рассчитывать на возможность успеха в создании ряда программных систем, построенных по опробованным принципам.