Функциональное и процедурное программирование пути объединения

Известия ТРТУ

Тематический выпуск

Литература

1. Кутепов В.П., Фальк В.Н. Направленные отношения: теория и приложения // Известия РАН. Техническая кибернетика. - N 4, 5 1994.

2. Карпова H.H. Особенности написания функционально-логических параллельных программ с использованием языка FLOGOL. Известия ТРТУ. Тематический выпуск Интеллектуальные САПР «Материалы Всероссийской научно-технической конференции с участием зарубежных представителей «Интеллектуальные САПР-96». Таганрог: ТРТУ, 1997, № 3(6).

3. D. Saunders: Databases: Models, Modelling and Languages, QMW, Computer Science Department, 1995.

УДК 658.512

Карпова H.H.

Функциональное и процедурное программирование - пути объединения

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

Одним из классических примеров интеграции двух языков процедурного программирования является механизм, реализованный в Microsott С 6.0. Этот компилятор позволяет подключать библиотеки, написанные на языке Fortran (Microsoft Fortran 5.0). При создании на языке Fortran описывалась специальная конструкция, реализованная только в данном компиляторе, под названием COMMON, в которую включались имена и типы всех переменных, используемых в данной библиотеке. При написании программы на С в ней описывалась структура, имя и поля которой полностью совпадали с описанием блока COMMON. Все функции из Fortran-библиотеки в С-программе помечались как внешние и начинались с ключевого слова Fortran. При компиляции С-программы компилятор пропускал все функции, начинающиеся со слова Fortran. Подключение библиотеки происходило при компоновке. Использование конструкции COMMON позволяло производить обмен данными через оперативную память, не прибегая к помощи файловой системы.

Созданная компанией Amzi! среда разработки позволяет совместное использование языков С и Prolog [1]. Данная система используется для построения экспертных систем и систем автоматизированного проектирования. Prolog используется для описания внутренних логических связей экспертной системы, создания ее основы. С используется для создания пользовательского интерфейса и описания процедур, специфичных для конкретной экспертной системы. Использование языка Prolog позволяет значительно сократить длину исходного кода.

На кафедре ПМ МЭИЯУ/ разработана система функционально-логического программирования, ядром которой является язык FLOGOL [2]. Возможности языка FLOGOL могут быть существенно расширены с помощью интеграции его с языками процедурного программирования. Модуль, позволяющий осуществлять подобную интеграцию, является внешним по отношению к ядру системы. Подобные модули могут быть реализованы для интеграции языка функционально-логического программирования с различными языками процедурного программирования. В настоящее время ведется работа над реализацией подобного модуля для языка С.

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

Материалы Всероссийской конференции

“Интеллектуальные САПР-97”

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

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

Литература

1. Dennis Merritt. Extending С with Prolog. Dr. Dobb’s journal, #217, August, 1994.

2. Бенеташвили А.Г Некоторые аспекты реализации языка FLOGOL как основы интегрированной системы функционально-логического программирования. Известия ТРТУ. Тематический выпуск Интеллектуальные САПР «Материалы Всероссийской научно-технической конференции с участием зарубежных представителей «Интеллектуальные САПР-96». Таганрог: ТРТУ, 1997, № 3(6).

УДК 658.512

Бондалетов A.B.

Применение группирующего генетического алгоритма для решения задач

одномерной упаковки.

Группирующий генетический алгоритм (ГГА) (Grouping Genetic Algorithm (GGA)) - это генетический алгоритм, измененный для решения задач группировки. Цель таких задач найти лучшее разбиение множества или сгруппировать вместе членов данного множества, используя различные критерии группировки. Задача упаковки (ЗУ) (Bin Packing Problem (ВРР)) является NP-сложной задачей группировки элементы различного размера должны быть сгруппированы в минимальное количество блоков (bin) фиксированного размера.

Задача упаковки (ЗУ) определяется следующим образом: дано конечное множество чисел (размеров элементов) £ и константа МАХ (размер блока), цель найти разбиение множества Е на минимальное количество подмножеств, таких, что сумма элементов в каждом подмножестве не будет превышать МАХ (размера блока).

Однако эту задачу можно рассматривать как задачу цель которой: сгруппировать члены множества U в одну или больше (максимум |U|) группу элементов, причем каждый элемент должен находиться только в одной группе, т.е. сгруппировать элементы.

Основными отличиями предлагаемого метода является использование группоориентированного подхода к задаче вместо элемнтно-ориентированного и использование хромосом состоящих из двух частей: элементной части (фиксированной длины равной количеству элементов) и групповой части (переменной длины).

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

В данной работе предлагаются ориентированные на решение задач группировки генетические операторы: скрещивания и мутаии.