Введение к работе
АКТУАЛЬНОСТЬ ТЕМЫ. Развитие языков программирования прошло путь от программирования в кодах ЭВМ до программирования .на языках высокого уровня, позволяющих достигать высокого уровня абстракции при программировании. Для решения существенно различных задач необходимы различные типы алгоритмического мышления. Разным типам мышления, как правило, соответствуют и разные языки программирования высокого уровня. Каждый класс языков предлагает свою парадигму программирования. Кожно выделить несколько групп языков, различающихся парадигмами программирования:
императивные (процедурные) языки - Паскаль, Ада, Си, Алгол-68 и т.д. ;
рефлексивно-функциональные языки - ЛИСП, Планер, Scheme, Miranda, Haskell;
логические (декларативные) языки - Пролог;
объектно-ориентированные языки - SmallTalk, SIMULA.'
На практике оказывается, что для многих задач отдельные подзадачи решаются наиболее эффективно при использовании средств, специфических для разных классов языков. Ранним способом решения этой проблемы было применение средств, позволяющих в рамках одного языка использовать отдельные процедуры, написанные на других языках, посредством компановки на уровне объектного кода, а программно выражаемые как внешние процедуры. Так, в языке Турбо Пролог допускается в разделе GLOBAL PREDICATES описывать предикаты, по существу являющиеся отдельно транслируемыми процедурами на языках Паскаль, Си и Фортран. В современных версиях языков Турбо Паскаль и Турбо Си разрешается писать целые процедуры или фрагменты программ на встроенном ассемблере. Тем самым, у программиста появляется возможность наиболее полно использовать ресурсы компьютера. Для современной практики программирования характерно слияние различных парадигм. Примером слияния парадигм монет служить появление объектно-ориентированных версий императивных языков Си (C++), Паскаль (Турбо Паскаль с версии 5.5), ЛИСП (Common Lisp Object System). В области объединения императивной и логической парадигм следует отметить язык Leda, сочетающий элементы языка йлгол с элементами программирования языка Пролог. Расширение языка Паскаль концепциями абстрактных типов данных и распределенного программирования привело к созданию и реализации
- 4 -язика flT-Паскаль. Среди современник отечественных разработок можно отметить расширение императивних языков (Си. Паскаль, Фортран) средствами компьютерной алгебры, средствами для работы на параллельных, векторных и суперскалярных компьютерах, соединение функциональной и логической парадигм. При объединении императивной и логической парадигм возникают определенные трудности, связанные с тем. что класс рекурсивных схем программ, к которым относятся языки логического программирования, не допускает прямой трансляции в класс схем последовательных программ без использования специальных средств управления памятью (стеков, массивов и др.), позволяющих моделировать работу интерпретатора рекурсивных программ. Обратный переход является более простым. Несмотря на появление специальных компьютеров, ориентированных на логические и функциональные языки, основная масса компьютеров по-прежнему остается в рамках фон-Неймановской модели. Поэтому представляется наиболее обоснованным выбор императивного языка программирования как базового языка для внесения в него средств, развитых в других парадигмах. В настоящей работе в качестве такого языка выбран Турбо Паскаль (версии 6.0).
Паскаль - язык с хорошим синтаксическим определением, позволяющий транслировать программу за один проход, с развитыми типами данных и строгой типизацией, понятный и легкий для освоения и использования. Трансляторы с языка Паскаль имеются практически для всех типов ЭВМ. Паскаль является основой для ряда новых языков программирования (Ада, Модула-2, Оберон) и остается одним из наиболее распространенных и используемых языков. Другим направлением развития языка Паскаль является внесение в него средств объектно-ориентированного программирования (язык Турбо Паскаль, начиная с версии 5.5). Использование в данной работе объектно-ориентированного подхода для описания древовидных структур дает возможность пользователю в дальнейшем с легкостью дополнять их новыми типами данных. Современные реализации Турбо Паскаль и Борланд Паскаль предоставляют пользователю не только язык программирования, но и удобную среду разработки и отладки программ. Неслучайно в новом программном комплексе DeIphi95, предназначенном для разработки приложений с архитектурой "клиент-сервер". интенсивно использующих базы данных, компания Borland International использовала язык Паскаль как основу. Компилятор языка Паскаль, встроенный в Delphi, обеспечивает высокую производительность,
необходимую для построения приложений в архитектуре "клиент-сервер". Этот компилятор в настоящее время является самым быстрым в мире, его скорость компиляции составляет свыше 120 тысяч строк в минуту. Он обеспечивает легкость разработки и тестирования готового программного блока, характерную для языков четвертого поколения, и в то же время обладает качеством оптимизации кода, присущим для компилятора языков третьего поколения. Внесение в язык Турбо Паскаль концепций логических и функциональных языков программирования делает возмояным создание на языке Паскаль компактных, читабельных и даже элегантно запрограммированных переборных алгоритмов. В частности, выразительная сила языка Паскаль может быть усилена внесением в него некоторых идей, родственных средствам языка Турбо Пролог. Специальные конструкции, подобные конструкциям языка Пролог, смогут тогда стать составной частью императивного языка программирования, включающего, в частности, глобальные переменные, функции, присваивание, операторы и выражения, выдающие нелогические значения. Программы для решения ряда задач искусственного интеллекта методами перебора, написанные на языке Паскаль, станут более эффективными, если появится возмоаность задать точный порядок перебора и явно управлять возвратами на основе ясных и компактных средств логического и Функционального программирования. Установление связей между языками, внесение возможностей одних языков программирования в другие позволяет существенно облегчить программирование алгоритмов и тем самым - решение разнообразных задач.
ЦЕЛЬ РАБОТЫ. Разработка синтаксиса веерно-возвратных конструкций, генераторов и строковых образцов, совместимого с синтаксисом языка Турбо Паскаль. Создание препроцессора для перевода на язык Турбо Паскаль разработанного синтаксиса.
НАУЧНАЯ НОВИЗНА. Впервые осуществлена экспериментально-исследовательская реализация расширения языка Турбо Паскаль на основе образцов с переменными для подбора, веерно-возвратных конструкций, являющаяся надстройкой транслятора с языка Турбо Паскаль. Показано, что любая простая программа функционально эквивалентна программе, составленной из элементов базисного множества (последовательность, возвратная конструкция, оператор ?П с использованием функций и предикатов исходной программы, а также присваиваний и тестов над дополнительным счетчиком. На основе : оператора ?! определен и реализован набор операторов управления, позволяющий кратко и удобно записывать традиционные
- б -
управляющие структуры. В настоящей работе впервые введена и реализована концепция генераторов перебора, использование которых позволяет определять порядок перебора и описывать перечислимые типы данных. Впервые реализован обобщенный вариант имеющейся в языке Рефал схемы сопоставления выраяения с образцом, синтаксически совместимый с языком Турбо Паскаль.
ПРАКТИЧЕСКАЯ ЦЕННОСТЬ. Веерно-возвратная конструкция может быть применена для решения задач искусственного интеллекта логико-математическими методами. В частности, реализация на языке Паскаль алгоритмов решения задач дискретного программирования становится короче и "прозрачней" в результате использования генераторов и веерно-возвратной конструкции. Представляется целесообразным использовать препроцессор при обучении программированию, так как работа с веерно-возвратной конструкцией позволяет лучше освоить и понять основные концепции парадигмы логического и функционального языка программирования, находясь при этом в среде языка Турбо Паскаль.
МЕТОДЫ ИССЛЕДОВАНИЯ. При реализации препроцессора использовались методы синтаксического анализа: метод рекурсивного спуска и просмотр на один символ вперед без возврата. При разработке концепции генератора использовались аналогии, имеющиеся в развитых функциональных языках и называемые генераторами бесконечных списков. Веерно-возвратная конструкция является обобщением управляющих конструкций алгоритмических языков. Основная идея веерно-возвратной конструкции была предложена и опубликована Н.К.Косовским.
АПРОБАЦИЯ РАБОТЫ. Основные материалы диссертационной работы докладывались и обсуждались на Международном конгрессе по информатике и прикладной математике (Санкт-Петербург, 1993). Результаты диссертации неоднократно сообщались на научном семинаре кафедры математического обеспечения ЭВМ Санкт-Петербургского университета.
ПУБЛИКАЦИИ: Klimov A.A, Kossousky N.K. Extension of Fan-Backtracking by Generators and Conditional Termination. International Congress on Computer Systems and Applied Mathematics, CSAM-93, St Petersburg, 1994. p 207.
Климов А.А. Внесение средств сопоставления с образцом в язык Турбо Паскаль, Депонировано в ВИНИТИ N139-B96, от 15.0І.96 Klimov A.A, Kossovsky N.K. Extension of Pascal by Fan-backtracking, Generators, and Patterns. International Journal
of Intelligent Control, Neurocomputing and Fuzzy Logic. N3, New York, 1996.
СТРУКТУРА И ОБЪЕМ РАБОТЫ. Диссертация состоит из введения, пяти глав, пяти приложений, списка литературы из 55 названий. Она содержит 102 страницы печатного текста и 38 страниц приложений, содержащих распечатки программ.
