автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Реализация расширенного языка Рефал на односвязной списковой памяти

РГО со

1.!оскоЕский«9р^нг|1.,Лсш!на, ордена Октябрьской Революции

и ор|ета красного Знамени государственный

университет имени М. В. Ломоносова п с л' с | Факул&тет вычислительной математики и кибернетики

1 Ь [¡АГк оЗ

На правах рукописи

МАНСУРОВ Николай Николаевич

РЕАЛИЗАЦИЯ РАСШИРЕННОГО ЯЗЫКА РЕФАЛ НА 0ДН0СВЯЗН0П СПИСКОВОЙ ПАМЯТИ

Спзциалькость 03.13.11 - Математическое и программное обеспеченна вычислительных систем, комплексов и сетей

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук'

Москва - 1992

Работа выполнена на кафедре системного программирования факультета Вычислительно!! математики и кибернетики Московского государственного университета инени Ц.В. Ломоносова.

Научный руководитель:

- кандидат физико-математических наук,

доцент ЗАДЫХАЙЛО И. Б.

Официальные оппоненты:

- доктор физико-математических наук,

профессор КАНОВИЧ М. И.

- кандидат физико-математических наук,

РОМАНЕНКО С. А.

Ведущая организация:

- Институт Проблем Управления

Защита состоится >3 1да? г в Л. { часов

на заседании Специализированного Совета Д.053.05.38 Н 4 по математике при МГУ им. М. В. Ломоносова по адресу: 119899, Москва, ГСП, В-234^ Ленинские горы, МГУ, факультет вычислительной математики и кибернетики, ауд. & У5"*

С диссертацией можно Вычислительной математики

Автореферат разослан

ознакомиться в библиотеке факультета и кибернетики МГУ.

1993 г

Ученый секретарь совета профессор

Н.П. ТРИФОНОВ

Актуальность темы:

В последнее время стала актуальной задача построения и реализации языков символьной обработки. В нашей стране наряду с такими языками как Лисп и Пролог, широкое распространение получил язык Рефал. Он был использован з качестве инструментального ззьпса в целом ряде практически важных программных комплексов, в том числе для построения трансляторов: СИМУЛА-67, транслятор с ПС-3000, транслятор с языка НОРМА, систем программирования ПСИ-ФОРТРАН, СЗ-ФОРТРАН и СЗХ-ФОРТРАН, системы аналитических вычислений САНТРА, АЛЬКОР, систем искусственного интеллекта. Неоднократно отмечались такие положительные . черты данного языка, как чрезвычайно высокий уровень, лаконичность и непроцедурность. Опыт программирования на языке Рефал свидетельствует о существенном сокращении времени разработки систем. Однако, серьезным недостатком Рефала является сравнительно малое быстродействие рабочих программ, а также большой объем памяти, требуемый при их выполнении.

Задача повышения эффективности символьной обработки возникает не только для языка Рефал. Актуальность задачи повышения эффективности вытекает, кроме всего прочего, еще и из того, что инструментальные языки символьной обработки составляют технологическую основу создания интеллектуальных программных систем, которые в настоящее время широко внедряется в промышленности, в том числе я для решения -задач управления в реальном масштаб«- времени. Например, по данным американских специалистов в ближайшее время некото- че задачи, решаемые с использованием экспертных систем, потребуют скорости обработки порядка 7 тысяч правил в секунду при общем числе правил порядка 6500. Имеющиеся в настоящее время экспертные системы содержат' в среднем около 2000 правил при скорости обработки порядка 50-100 правил в секунду! Это означает, что в одной из областей применения символьной обработки ожидается увеличение требований по памяти по крайней мере в 3-4 раза, а по быстродействию - з 70 раз.

В связи с этим особый интерес представляет исследование класса языков символьной обработки и методов их программной

ре? пизации. Желательно обобщить опыт реализаций языков данного класса и на основании этого выделить основные источники п. вышения их эффективности.

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

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

2) на основе проведенного теоретического исследования выполнить эффективную реализацию расширенного языка Рефал на односвязной списковой памяти;

Научная новизна:

1) теоретически исследована структура вычислительного процесса символьной обработки и выделены универсальные источники повышения эффективности программных реализаций языков данного класса;

2) исследована подробная структура накладных расходов реализации языка Рефал на односвязной памяти.

Практическая ценность:

1) выполнена программная реализация расширенного Рефала на односвязной списковой памяти.

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

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

памяти;

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

Реализация Рефала на односвязной списковой памяти внедрена в промышленную эксплуатации в ИЛМ им. М.В. Келдыша АН СССР, НПО АП и НИИ "КВАНТ" и была использована для разработки компилятора системы СЗХ-Фортран для IBM PC, компилятора системы Фортран-ВП для ЭВМ ЕС-1195, синтезирующего транслятора с непроцедурного языка НОРНА и ряда других проектов.

АТТРООЭНИЯ-И-РУблЩСЭЦИИ:

Результаты диссертации докладывались на:

- Всесоюзной научной студенческой конференции, г. Новосибирск,

1986;

- на заседании научно-исследовательского семинара 12 отдела

ИЛИ им. U. В. Келдыша АН СССР, г. Москва, 1987;

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

- на школе "Метавычисления в языке Рефал", г. Обнинск, 19S0;

на научно-исследовательском семинаре по автоматизации программирования под руководством проф. М.Р.Шура-Буры, г.Москва, 1990; ,

- на заседаний кафэдры системного программирования МГУ, г. Москва, 1990;

Основные результаты опубл..ковакы в четырех работах.

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

СОДЕРЖАНИЕ РАБОТЫ -Во.введении раскрывается тема диссертации, показывается ее научная новизна и актуальность, характеризуется место работы среди исследований по языкам символьной обработки. Определяется цель и основные задачи исследования.

характеризуются основные методы исследования, а также кратко излагается содержание отдельных глав диссертации. Дается характеристика полученные научных результатов и показывается их прэ- -ическая значимость.

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

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

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

Дальнейшее движение в данном направлении оказывается еще более сложным, поскольку. очевидно. что: 1) различным программам могут соответствовать различные вычислительные процессы; 2) для одной и той же программы символьной обработки вычислительный процесс в большой мере определяется исходными данными; 3) существуют различные языки символьной обработки, а также различные реализации одного и того же языка. Поэтому структура вычислительного процесса символьной обработки должна описываться обобщенно, на основе некоторой формальной модели.

В диссертации вводится понятие модель символьной обработки, состоящая их следующих трех компонент:

1) модель символьных данных;

2) модель вычислительного процесса;

3) механизмы символьной обработки.

Введение понятия модели символьной обработки задает некоторый уровень абстракции для рассмотрения управления,

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

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

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

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

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

Разработанная методиха позволяет выделить следующие девять групп оптимизаций, составляющих универсальные источники повышения эффективности символьной обработки: . Группа 1 - Машинно-зависи:,.е оптимизации; Группа 2 - Машинно-независимые оптимизации низкого уровня; Группа 3 - Оптимизации внутреннего представления данных; Группа 4 - Оптимизации команд абстрактной маоины; ' Группа 5 - Оптимизации управления; Группа 6 - Глубокая компиляция;

Группа 7 - Эквивалентные преобразования исходных программ;

Группа 8 - Улучшение модели символьной обработки;

Группа 9 - Объединение различных моделей символьной обработхи.

Первые пять групп (машинно-зависимые и машинно-независимые оптимизации низхого уровня, представленные группами 1 и 2, а также оптимизации абстрактной машины, представленные группами 3-5) предполагают модификацию системного программного обеспечения, но не затрагивают ни' конструкций языка программирования символьной обработки, ни исходного текста рабочей программы на данном языке. Между тем, источники наиболее значительного повышения эффективности возможно за счет оптимизаций . следующих четырех . групп (оптимизации высокого уровня), которые связаны либо с изменением исходной программы, например, путем глубокой компиляции, т. е. практически, переходом к эквивалентной программе на машинном языке, либо преобразованиями исходного текста программы, т. е. переходом к эквивалентной, но более эффект! -.ной программе на том же языке; либо связанных с изменением самой модели символьной обработки, например путем введения более адекватных и удобных языковых конструкций, либо за счет использования различных моделей для программирования различных частей общей задачи. Заметим, что в литературе имеется немало свидетельств растущей актуальности именно этого

• последнего подхода.

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

Машинно-независимые оптимизации включают ~ в себя следующие: .

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

2). упрощение действий, т.е. замена групп (как правило удаленных друг от друга), действий на группы, дающие тот же результат, но имеющих меньшую стоимость;

3) реализация действий, например, свертка констант, или распроцедуривание (open coding), т.е., открытая подстановка теяа процедуры в место ее вызова.

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

В первой главе рассматриваются различные внутренние представления символьных данных, в том числе и некоторые нетрадиционные методы, преимущественно по результатам исследований в рамках проехта' ESPRIT-1588* "SPAN: параллельные архитектуры для поддержки интегрированной символьной и численной обработки".

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

Основные результаты теории метавычислений хорошо известны и описаны в работах Й. Футамуры, В. Ф. Турчина, А. П. Ершова и ряда других авторов. Известно, что интерпретатор языка и его частич-ый вычислитель могут быть использованы в качестве компилятора исходного языка в язык реализации интерпретатора. Однако практическое применение этого принципа затруднительно, т. к. 1) интерпретатор оказывается достаточно сложным, что делает частичные вычисления практически непригодными; 2) обычно при интерпретации не происходит преобразования внутреннего представления данных на более эффективное. Одно из наиболее интересных современных направлений исследований является преодоление этих проблем и использование метавычислений как формальной основы для ведения целенаправленной оптимизации абстрактной машины. Это оказывается возможным за счет явного описания реализации мех^измов обработки и управления языка и явного задания отображения его модели данных в некоторое внутреннее представление. После явного включения в программу вызовов базовых механизмов (обогащение программы), производится ее частичное вычисление, з результате чего происходит выделение набора команд абстрактной машины, а, кроме того, осуществляется компиляция исходной программы в эти команды.

Оптимизации управления в системах символьной обработки рассматриваются в диссертации на примере реализаций языка Лисп. Исследования показывают, что в языках символьной обработки управление (например, в функциональных языках -вызов функции и возврат из нее) оказывается критическими для эффективности. Например, во многих реализациях Лиспа на вызовы функций приходится до 25/. времени выполнения. В реализациях Рефала эта цифра достигает 35'/..

В последних разделах главы проводится краткий обзор оптимизаций высокого уровня.

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

Во второй главе описываются основные алгоритмы нового подхода к реализации Рефала.

Традиционная схема программной реализации языка , зфал основывается на использовании для представления выражений дву<-вязных списков (рис. 1). Такое представление вполне логично с точки зрения языка. Вместе с тем, практика работы на Рефале показывает, что не все возможности используются одинаковым образом. Например, гораздо чаще выполняете., левосторонний, а не правосторонний просмотр выражений. Анализ статистики, собранной при работе компилятора Симула-1/АЛМО, написанного на Рефале, показал, что переходов с левого звена на правое - 80%. Из оставшихся 20У. значительная часть переходов реализует единственный частный случай, не связанный с необходимостью правостороннего просмотра выражения, для эффективного выполнения которого двусвязная списковая память не требуется, хотя нужно уметь быстро ' находить последний символ в выражении.

В реализациях таких языков символьной обработки, как Лисп и Пролог используются односвязные списки (рис. 2). Суть предлагаемого подхода состоит в использовании одноезязных списков в реализации Рефала (рис. 3). i

__ _ 1 1

а < 1 П ь _ 1 1 ±_ L \ £

Т Т 1 ? 1 1

L

Рис 1. Представление символьного выражения А ( В ) двусвязным списком (традиционная реализация Рефала)

( )

ггтн

Рис 2. Представление символьного выражения Л( В ) односвяэным списком (традиционная реализация Лиспа)

( )

.С

¡□Е-

Рис 3. Представлегие символьного выражения А ( В) одкосвязным списком с кольцевыми цепочками . (ранний вариант предлагаемой реализации Рефала!

°ис 4. Представление символьного выражения А ( В ) односвяэным списком (предлагаемая реализация Рефала)

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

Кроме того, предлагаемый подход позволяет унифицировать типы списковой памяти в реализациях Лиспа, Пролога и Рефала. Унификация схем распределения памяти может существенно

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

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

- отождествление закрытых Е-переменных;

- правостороннее отождествление;

- трансплантация значений Е-переменных;

- подстановка результата замены в поле зрения.

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

В подавляющем большинстве случаев сквозного просмотр» удается, избежать эа счет следующих решений:

использование правосторонних ссылок во внутреннем представлении структурных и функциональных скобок; '

- особое представление пустых значений переменных-выражений;

- изменения алгоритма трансплантации;

- изменение алгоритма правостороннего отождествления.

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

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

эффективности отдельных проектных решений.

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

Наиболее интересная оптимизация Рефала, из числа разработанных в рамках данного исследования, относится к группе оптимизаций управления и называется "быстрая конкретизация". Из логики работы Рефала следует, что ведущая конкретизация в результате замены на текущем шаге оказызается ведущей во всем поле зрения на следующем шаге. Вместе с тем, информагия о том, какая из конкретизации является ведущей в результате замены, известна статически для каждой Рефал-функции. Этот факт используется для упрощенного представления функциональных скобок для таких конкретизация и ускоренного начала следующего шага. Для упрощенного задания области "быстрой конкретизации" используются непосредственно рабочие указатели абстрактной машины (В1 и В2), причем левой функциональной скобке в данном случае вообще не соответствует никаких звеньев в поле зрения (вместо трех звеньев в обычном случае). Правой функциональной скобке соответствует одно звено (как и в обычном случае), однако для "быстрой конкретизации" не выполняется связывания скобок и формирования стека функциональных скобок. Вместо , этого, адрес функции запоминается в некоторой рабочей переменной и устанавливается флаг для ускоренного начала следующего шага.

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

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

описывается опыт

практического

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

Общая производительность предлагаемой реализации Рефала на процессоре Intel 80386-SX с тактовой частотой 20 МГц составляет около 3 KLIPS (3000 шагов в секунду). Измерени... выполненные на реальной программе компилирующего типа (система СЗХ-ФОРТРАН), показали, что по скорости предлагаемая системы оказывается всего в 1.35 раза медленнее реализации Рефала-2 на машине ЕС-1045. Для сравнения, реализация языка 0PS5 на машине VAX 11/780 имеет производительность 5-12 LIPS (правил в секугду). Производительность реализации языка MP-PR0L0G на машине SUN 3/60 составляет 2730 LIPS. Производительность реализации языка Пролог на машине Symbolics 3600, выполненной на уровне микрокода, составляет 5 KLIPS (5000 LIPS).

В работе проводится детальное исследование структуры вычислительного процёсса в предлагаемой реализации и приводятся конкретные временные характеристики его различных компонентов. Получены следующие оценки (в процентах от общего времени выполнения программы, среднее значение по набору бенчмарков): отождествление - 34.4 '/., замена - 21.4 управление - 44.2 "X ( из них на переходы по предложениям -13.4 X). Подробно, на уровне базовых механизмов символьной обработки, выделенных в главе 1, анализ констант - 2.9 '/., анализ структур - 3.4 '/., доступ к компонентам структур -3.5 '/., связывание переменных - 24.6 '/,, синтез констант -0.6 X, синтез структур - 3.1 7., использование переменных -17. 7 X.

Особый интерес представляет исследование вычислительного процесса на уровне отдельных макр'сопераций. В работе приводятся оценки времени выполнения наиболее часто используемых макроопераций и выделяется подробная структура некоторой группы накладных расходов на уровне макроопераций. Исследованная группа накладных расходов составляет около 30'/, от общего времени . лполнения Рефал-програ^мы. При этом до 11'/. общего времени выполнения программ!? затрачивается на дешифрацию кодов команд абстрактной машины. На работу с

таблицей элементов тратится в среднем 5. 7 X от общего времени, на работу со стеком переходов - 4.5 X, на выборку аргументов команд - 2 4 '/., на выделение свободных звеньев - 2. ? X, на передвижение указателя В1 по списку - 3.4 %. Перечисленные результаты получены впервые.

Рассмотрим подробно источники увеличения

производительности предлагаемой реализации на односвязной памяти по сравнению с традиционным подходом. Имеют место сле^ощие факторы: :

1) за счет использования односвязной памяти уменьшаются:

- время на инициализ ;ио интерпретатора (т.к. упрощается организация поля зрения);

- Бремя на управление памятью (т.к. расходуется меньше памяти);

- время выполнения команд абстрактной машины (см. ниже)

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

2) за счет оптимизаций вызовов функций уменьшается иакладные расходы на управление;

3 > за счет нового представления чисел:

-быстрее выполняются встроенные арифметические функции;

- выполняется меньше команд (т.к. удается избежать порождения лишних скобок);

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

1) уменьшается время выполнения команд замены из-за отсутствия накладных расходов по коррекции правосторонних ссылок в командах трансплантации, копирования выражений, связывания скобок;

2) несколько уменьшается время команд управления из-за упрощения организации поля зрения;

Кроме того, в предлагаемой реализации использование односвязной памяти не происходит к увеличению

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

трансплантации проекций переменных и представлениё структурных скобок, что обеспечило сохранение эффективности традиционной реализации в наиболее частотных случаях при ликви„;ции избыточности во внутреннем представлении данных (глава 2). В ц_лом, предлагаемая реализация оказывается в 2.5-3 раза быстрее традиционной.

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

1) за счет использования односвязной памяти уменьшается объем списковой памяти;

2) за счет реализации правостороннего отождествления с использованием левосторонних ссылок и отсутствия дублирования команд абстрактной машины уменьшается размер объектного кода интерпретатора;

3) за счет оптимизаций низкого уровня несколько уменьшается объем кодов Рефал-программы;

4) за счет нового представления чисел уменьшается количество скобок в списковой памяти;

Данная работа практически исчерпывает- машинно-независимые оптимизации низкого уровня (первая и вторая группы), а также часть оптимизаций абстрактной машины (третья, четвертая и пятая группы, выделенные в первой главе). Существуют дополнительные возможности повышения эффективности еще на 30-40%.

Дальнейшее повышение эффективности реализации Рефала (более чем на порядок) должно, по всей видимости, опираться на другие источники, выделенные в первой главе. Наиболее перспективными здесь представляется- глубокая компиляция Рефал-программ непосредственно в машинный код и трансформации Рефал-программ на основе частичных вычислений. Следует отметить, что работы по глубокой компиляции в машинный код в настоящее время активно ведутся для других функциональных языков (Лисп, Scheme, ML, Miranda и другие). Эффективность рабочих программ в таких системах в некоторых случаях превосходит аналогич; ые программы на языке Паскаль.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

2. Разработан метод реализации языка Рефал на односвязной списковой памяти.

3. выполнена программная реализация метода и его оценка.

За счет односвязной списковой памяти: - достигнута унификация типов списковой памяти в реализациях Лиспа, Рефала и Пролога, что открывает возможность создания многоцелевого спецпроцессора;

достигнуто сокращение объема памяти при работе Рефал-программ в 2.5-3 раза по сравнению с традиционной реализацией;

За счет систематического использования источников повышения эффективности удалось повысить быстродействие Рефал-программ в 2.5-3 раза по сравнению с традиционной реализацией.

4. Выделены основные объекты и базовые операции, используемые реализации Рефала, и на их основе разработан макроязык, существенно повышающий "технологичность'' системы.

Основные результаты опубликованы в работах:

1) Мансуров H.H. "Реализация расширенного языка Рефал с ориентацией на односвязную память".-/ Материалы XXIV Всесоюзной научной студенческой конференции, Новосибирск, 1986.

2) Мансуров H.H., Эйсымонт Л.К. "Реализация расширенного языка Рефал на односвязных- списках с кольцевыми цепочками. Часть I Списковая память и операторы отождествления". -М: ИПМ АН СССР, препринт 20, 1987.

3) Мансуров H.H., Эйсымонт Л.К. "Реализация расширенного языка Рефал на односвязных списках с кольцевыми цепочками. Часть II".- М: ИПМ АН СССР, препринт 203, 1987.

4) Анисков A.B. , Мансуров H.H. , Эйсымонт Л.К. "Возможности применения специализированных рабочих станций при разработке программ систем управления". -/ Материалы Всесоюзной школы по проблемам математического обеспечения и архитектуры бортовых вычислительных систем, Ташкент, 1388.