Введение к работе
Актуальность темы:
В последнее время стала актуальной задача построения и реализации языков символьной обработки. В нашей стране наряду с такими языками как Лисп и Пролог, широкое распространение получил язык Рефал. Он был использован з качестве инструментального ззыка в целом ряде практически важных программных комплексов, в том числе для построения трансляторов: СИМУЛА-67, транслятор с ПС-3000, транслятор с языка НОРМА, систем программирования ПСИ-ФОРТРАН. СЗ-ФОРТРАН и СЗХ-ФОРТРАН, системы аналитических вычислений САНТРА, АЛЬКОР, систем искусственного интеллекта. Неоднократно отмечались такие положительные . черты данного языка, как чрезвычайно высокий уровень, лаконичность и непроцедурность. Опыт программирования на языке Рефал свидетельствует о существенном сокращении времени разработки систем. Однако, серьезным недостатком Рефала является сравнительно малое быстродействие рабочих программ, а также большой объем памяти, требуемый при их выполнении.
Задача повышения эффективности символьной обработки возникает не только для языка Рефал. Актуальность задачи повышения эффективности вытекает, кроме всего прочего, еще и из того, что инструментальные языки символьной обработки составляют технологическую основу создания интеллектуальных программных систем, которые в настоящее время широко внедряется в промышленности, в том числе я для решения "задач управления в реальном масштаб"- времени. Например, по данным американских специалистов в ближайшее время некото- ме задачи, решаемые с использованием экспертных систем, потребует скорости обработки порядка 7 тысяч правил в секунду при общем числе правил порядка 6500. Имеющиеся в настоящее время экспертные системы содержат' в среднем около 2000 правил при скорости обработки порядка 50-100 правил в секунду! Это означает, что в одной из областей применения символьной обработки ожидается увеличение требований по памяти по крайней мере в 3-4 раза, а по быстродействие - з 70 раз.
В связи с этим особый интерес представляет исследование класса языков символьной обработки и методов их программной
ре? лизации. Желательно обобщить опыт реализаций языков данного класса и на основании этого выделить основные источники Пч вышения их эффективности.
Результаты исследования могут быть использованы для решения задачи повышения эффективности . программных реализаций Рефала для традиционных аппаратных средств, а также для разработки спецификаций аппаратных средств поддержки реализации Рефала, специализированных процессоров символьной обработки на основе Рефала (возможно, совместно с другими языками символьной обработки).
Цели диссертационной работы:
-
исследовать класс инструментальных языков символьной обработки, методы их программной реализации и выделить источники повышения их эффективности;
-
на основе проведенного теоретического исследования выполнить эффективную реализацию расширенного языка Рефал на односвязной списковой памяти;
Научная новизна:
1) теоретически исследована структура вычислительного процесса
символьной обработки и выделены универсальные источники
повышения эффективности программных реализаций языков данного
класса;
2) исследована подробная структура накладных расходов
реализации языка Рефал на односвязной памяти.
Практическая ценность:
1) выполнена программная реализация расширенного Рефала на
односвязной списковой памяти.
Проведена оценка предлагаемого подхода.
За счет односвязной списковой памяти достигнута унификация типов списковой памяти в реализациях Лиспа, Рефала и Пролога, что открывает возможность создания многоцелевого спецпроцессора символьной обработки.
Систематическое использование источников повышения эффективности в рамках реализации на односвязной памяти позволяет увеличить быстродействие рабочих программ в 2.5-3 раза и в 2.5-3 раза увеличить эффективность использования
памяти;
2) выделены основные ооъекты и базовые операции, используемые & реализации Рефала, и на их основе создан макроязык, существенно повышающий "технологичность" программной системы.
Реализация Рефала на односвязной списковой памяти внедрена в промышленную эксплуатации в ИПМ им. М.В. Келдыша АН СССР. НПО АП и НИИ "КВАНТ" и была использована для разработки компилятора системы СЗХ-Фортран для IBM PC, компилятора системы Фортран-ВП для ЭВМ ЕС-1195, синтезирующего транслятора с непроцедурного языка НОРНА и ряда других проектов.
Апробация_и_рубликации:
Результаты диссертации докладывались на:
- Всесоюзной научной студенческой конференции, г. Новосибирск,
1986;
- на заседании научно-исследовательского семинара 12 отдела
ИПМ им. U. В. Келдыша АН СССР, г. Москва, 1987;
на Всесоюзной пколе по проблемам математического обеспечения и архитектуры бортовых вычислительных машин, г. Ташкент, 1988;
на школе "Метавычисления в языке Рефал", г. Обнинск, 19S0;
на научно-исследовательском семинаре по автоматизации
программирования под руководством проф. М.Р.Шура-Буры,
г.Москва, 1990; ,
- на заседании кафэдры системного программирования МГУ,
г. Москва, 1990;
Основные результаты опубликованы в четырех работах.
Структура и обьеи диссертационной работы: Диссертация состоит из введения, трех глав, заключения, списка литературы, включающего 148 названий, и одного приложения. Основной без приложений текст диссертации занимает 150 машинописных страниц.