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

Н ц ид

1 0 1,1 А П 1203

Комитет по науке, высшей школе и технической Политике

Иркутский государственный университет

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

Петухип Вячеслав Алексеевич

Аналио логических программ и компиляция яаыка Флэиг

)5.13.16 - применение вычислительной техники, математического моделирования и математических методов п научных исследованиях (по отраслям наук)

Автореферат

диссертации на соискание ученой степени кандидата фиоико-математичсских наук .

Иркутск - 1903

РаГюгп выполнена п Иркутском государственной университете

Научние руководители -

(официальные (лшоненти

к шдндат фиоико-математических наук, доцент В.В. Блудов, кандидат физико-математических наук, доцент A.B. Манцивода

доктор физико-математических наук, профессор Морозов Андрей Сергеевич

кандидат физико-математических наук, старшгп научный сотруднцр Нньоленьо Алексей Борисович

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

.Московский государственный униыерситет

/р ЛГ ,1 /у

«Защита состоится 1993 г. в 1.}/ часов на заседании специа-

лизированного совеч'а К 003.32.06 при Иркутском государственном университете по адресу: 6С4003, Иркутск, б.Гагьрина, 20.

С диссертацией можно ознакомиться в Ьлблиогеке Иркутского государственного университета.

Аьгорефср^г раоо

слан • ^ P^l1U03 г.

Ученый секретарь иллшалигшривачниго совета I' .ф.-м.н , дощ нт

i.B. Бельтюков

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

Апробация

Репультаты диссертации докладывались па второй Российской конференции по логическому программированию (С.-Петербург, 1991), конференции по гон -струированию компиляторов (Падеборн, 1Э92), конф реицпп по прикладной логике (Новосибирск, 1992).

Публикации

Основные результаты диссертации опубликованы в трех работах [1 2, 3]. Работы написаны в сопато, ггве с A.B. Манцнводой.

Структура работы

Диссертация состоит «га введения, четырех глав, заключения, библиографии я приложений. Объем работы (оа исключением приложений) составляет 103 страницы. Список литературы содержит 5S няинеповшшп.

Краткое содержание

Птава 2 носиг вспомогательный характер. Она состоит из трех параграфов. Параграф 2.1 описывает некоторые работы по компиляции яяыха Пролог. В параграфе 2.2 перечислены отличия яоыка Флэнг от языка Пролог. В пора-графе 2.3 описывается основные термины, используемые в диссертации.

Глава 3. Абстрактная Флэнг-машина

В главе 3 описывается абстрактная машина, разработанная для реализации компилятора. Код абстрактной Фланг-машины (FAM) является проме жуточпыи результатом при компмяяцпп Флонг-программ. С одчой стороны, абстрактная машина поддерживает механизмы логического программирования, а, с другой стороны, — она достаточна близка к компьютеру. Оснсгной разработки новой абстоактнон машины .являлось досгилелтэ максимальной эффективности. ;

Несмотря не. большую специализацию, абс; .актная Фланг-машина (FAM) является вариантом WAM-машины. Машина расширена набором конструкций, обеспечивающих 6ov<> оптимальную работу. Многие конструкции спе-ппаллонреплш» для пспольоуемого процесса компиляции. Корректность применения специалпзироштых конструкций обепечивается инфорыац-лей, полу-

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

Общая направленность модификации, введенных а 7АМ, — приближение выполнения логических программ ь выполнению императивных программ (с точки арения эффективности). В главе о показывается, что затраты иа еы-полн'шлс логической программы во всех случаях очень блиоки к тону минимуму. который необходим с точки орешю машин фок-Неймана (то есть ЭВМ, ислочьпуемых в настоящее время).

Параграф 1 оппсыьаег архитектуру абстрактной машины. Описываются основные области данных; код, стек, куча и след. Перечисляются регистры FAM. Указывается соответствие мелду регистрами FAM и регистрами ЭВМ. Приводятся форматы управляющих структур FAM: ааписн активации, точки воакрмта и иаписп'следа.

I) параграфе 12 рассматривается представление данных а абстрактной ыа-шпне. Описывается представление целых чисел, а-хомов, структур, свободных переменны.:. Дли повышения вффектпвности введен формат компактного представления структур. Описание представления данных проводится в сравнение с нредстЕлешк'м соответствующих данных в нмпера гивных яаыках. Приведен алгоритм распознавание плачешь; переменной. Кроме того, в параграфе 2 приведена осщ.ш схема алгоритма, сборок мусора, применяемого в FAM.

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

Затем описан орлгиналыши алгоритм унификации (поц)цели и оаголовков правил. Основной посылкой для разработки данного алгорш ма является максимальное приближение унификация к проверкам, испольоуемым в императивных языках (а тех случаях, к» да ото воаыожно) [1]. Вводятся понятии, упрощенной унификации, перехода а ветвления. Вводился мехашмм установки точки возврата р два приема и связанное с ним понятие ближнего бэктрекинга. Kp'biuc тою, в параграфе 3 ана.п.оируются два способа возвращения пнлчешш и формулируются условия предпочтительности первого или второго способа.

В параграфе -1 FAM сравниваете.! с другими абстрактными машинами. Сравниваются механизмы унификации цели и ам оливка правила испольауе-

tue D FA M и других абстрактных машинах". Кроме ion,, обсужд.погся различия реализаций логических и пмперкгивных языков. Обосновывается теоис, :то потерн производительности логических программ, как правило, связаны 'ольхо с неточностями при вычислении свойств программы.

Глава ¿.Абстрактная iiiircjmp/tramin

Основные свойства программы, вычисляемые на атапз глобального вна-иов — детерминированность предикатов и шаблоны аргументов предикатов. 1дром глобального анализа, описываемого в гл-ве -1, является абстрактная нтерпретацг.я.

Под абстрактной интерпретацией поннмпют следующую технологию ана-нэа. Строится модель исполнения программы, отражающий аналнш'оуемые войства прог рамм!.'. Алгоритмы i-^полненця программы моделируются со-тветственно области их действия. Пос троенная модель должна сохранять войства анализируемой программы и позволять выполнение абстрактной нн-ерпретации з конечное Бремя.

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

В параграфе 1 главы 4 предлагается новый подход к абстрактной интер-ретащш, позволяющий (значительно ускорить рроцссс абстрактной интер-ретацпн Этот подход основан на использовании графового представления роцедурнои семантики языков логического программирования и проведения налпза отдельно на максимально суженных областях. Подход называется апдельноп абстрактной интерпретацией. Область анн.чгаа разбивается па пкпртово произведение отдельных областей и интерпретация производится а отдельны^ областях. Предложение 4.1 утверждает, что корректность аб-грактной интерпретации на всей области анализа следует ¡и корректности Гн'трактной интерпретации па отдельных областях.

13 параграфе 2 описывается реализация данного подхода к аб< . рактпой нтерпретации для Фланг-компилятора. Строится модель области анализа, 'писана модель выполнение программы, называемая абстрактным выиолне-

8 M. Calisson. Он the f.'ífiriem-y of Ojitiniisin/f Shallow H,uktiak¡n¡¡ in (!um¡>Heil ruhig. Olli liiU'l national ConfcNMi'-e un I.oj'ic Programming, .1щш P.14ÍI, |>|>.Ii-IC).

A.K. T.irk.r.'i)iiip)i('i Optimizations fur tin: W.\M ,'lnJ ¡4ti iii.ihoaa/ Conference on og¡с /'rograiiiiiii'i«, .Inly 1086, pp.(¡57 !¡02.

нием. Приводится .алгоритм рбстрактяого выполнения правил, содержат» предикаты, определенные в программе.-Для предиката унифицируемости других встроенных предикатов абстрактное выполнение строится сиецмал: ными способами. В конце параграфа 2 приводится пример абстрактного bi полнения. Для данной реализации получена следующая сценка времени ai страктного выполнения: время абстрактного выполнения растет не быстр( линейной функции относительно длины программы при условии, что кол] чесгво переменных в заголовках правил программы ограничено константо!

D параграфе 3 описываются другие методы птоЯального анализа. Наибож важная информация, получаемая с помощью этих методов — информация детерминированности предикатов и правил.

о

D параграфе 4 дается сравнение с другими подходами к глобальному ан липу. Результаты тестов показывают, что проблем с временем абстрактно: выполнения во Флэнг-хомпиляторе но возникает. Более гого, яри истюльзов нии компилятора не отмечено случая, когда бы суммарное время глобально] анализа превосходило время синтаксического анализа. Значение Такого р оультата становится понятно, если учесть, что обычно приходится идти i компромисс между гранулнрованностью анализа и временем его выполнени ТЬк, в работе А. Тейлора9 алгоритм абстрактного выполнения был получен результате двух последовательных преобразований алгоритма, ослабляк>Щ1 гранулнрованностью анализа.

Информация, которую дает глобальный анализ для предиката р арное! а, определяемого т правилами, описывается следующим образом:

< (<,,f3,..., «„), f,s,d,с, (tri, , di, с,),..., (trm, s n > £¿rn j Cfn) »

где

<!,...,<„ € { gTound+rderef, (¡round, unground+rdtTtj, ungraund, fret-by-valut, free-by-pointer, yfiknown freiere/, unknown };

/ 6 { функция, предикат };

6 { нет-точки-вотрата, стлаится-точка-аозчрата. };

c,С],..., cm € { безилътернхтиеность, нст-бепалыпсрнатиапости}-,

d, dt,..., dm 6 { детерминированность, не()стсрм,чнироранносп>,ь };

tri,...,trm€ { хвостовал-ргкурсия, нет-хпостовой-рскт/рспи }.

Гиава й. Компиляция в Флэнг-мшшшу

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

9 А. Taylor. High Performance Prolog huplfiucntaticu. ¡J!iD. Dissertation, Das.1 Department of Computer Science, Vmversity of Sydi.cy, June 1091.

ические деревья. Синтаксические деревья явмются гправньш объектом :ри компиляции не только языков логического программирования. Без син-акснческого анализа не может обойтись реализация ни одного но языков про раммированпя. Оатем синтаксические деревья преобрапуются в некую нор-[алиаованную форму, упрощающую аналио и последующую компиляцию. На гапе глобального анализа вычисляются свойства программы (детерминиро-анность предикатов, шаблоны аргументов и т.д.). Данными основного отапа омпидяцли — компиляции в абстрактную Флэнг-машнну являются как син-аксическне деревья, так II свойства программы, вычисленные на отапе гло-алького анализа. Ре /льтат этапа компиляции в абстрактную Флэнг-маишну - код Фпэнг-маишны. На последнем отапе код Флэнг-машины компилируется машинный код.

Параграф 1 описывает преобраоовання на уровне исходных программ (или эриоонтальную компиляцию), параграф 1 — компиляцию в абстрактную Флэцг-ашину (или вертикальную компиляцию). В параграфе 3 обсуждаются во-росы, связанные с компиляцией в машинный код. Пример компиляции, про-теживающнй все этапы юмпиляцшг, приведен в параграфе 4.

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

• сокращение операций отслеживания ссылок аа счет локального вычисление шаблонов переменных (пункт 5.2.3);

« оптимизация алгоритма сопоставления правил цели, и связанная с ней оамена общего алгоритма унификации на ¡значительно более эффективную схему — условного перехода (ветвления) (пункт 3.3.2 главы 3);

• оптимизация установки точки возврата, приводящая к установке точки возврата в два приема, (пункт 3.3.3 главы 3).

Стандарт ый алгоритм компиляции в абс 1 ¡¡нктиугю мащднУ Логически не [ень сложен. Глубина рекурсии алгоритма для атого втапа компиляции огра-1Чена глубиной вложенности термов в правилах. Компиляция выполняется 'дельно для каждого правила. Однако необходимость порождения специали-[ровашшх версий кода некоторых предикатов приводит к значительному ложнеиию алгоритма компиляции. Еще более усиливают сложность оптими-гцш, переставляющие вызовы предикатов и устанавливающие соответствие :жду аргументами и регистрами.

D.II.D. Warren. Implementing Prolog -- С'ошрШт; i'miicaie Log!с Programs, chnical Report, 3!), 40, University of Ediulmrgli, May 1977, 4Gp.