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

гв

азссийская академия наук

Сибирское отделение Институт систем информатики

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

Кочетов Дмитрий Викторович

Эффективная специализация алголоподобных программ

Специальность 05.13.11 - математическое и программное ¡беспечение вычислительных машин, комплексов, систем и

сетей

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

Новосибирск 1995

Работа выполнена, в Институте систем информатики Сибирск го отделения Российской академии наук (ИСИ СО РАН).

Научный руководитель: М.А.Бульонков,

кандидат физико-математически:

Официальные оппоненты: В.К.Сабельфельд,

доктор физико-математических н И.Н.Скоппн

кандидат физико-математически:

Ведущая организация: Санкт-Петербургский государств

университет

Защита состоится декабря 1995 г. в 14 час. 30 мин.

заседании специализированного совета К0003.93.01 в Институ систем информатики Сибирского отделения РАН по адресу:

630090, Новосибирск, пр. ак. Лаврентьева, 6.

С диссертацией можно ознакомиться в читальном зале 6 блиотеки ВЦ СО РАН (пр. ак. Лаврентьева, 6).

Автореферат разослан " 2.0 " Ноября 1995 г.

Ученый секретарь специализированного совета К0003.93.01 к.ф.-м.н.

М.А.Бульон?

Общая характеристика работы

Актуальность темы. Специализация (смешанные вычисления) программ нплнеггл одним из наиболее мощных и перспективных м< I од.а! автоматического построения качественного программно! о обеспечения, позволяющим совместить надежность универсальных алгоритмов с эффективностью алгоритмов, ориентированных на заданный контекст использования, и, в конечном итоге, позволяющим быстро разрабатывать корректные программы ('мешанные вычисления теоретически применимы в любом языке программирования. Но для практического программирования особенно важны смешанные вычисления для план ранги анш языков, наиболее интенсивно используемых при решении реальных задач. В го же время, те результаты теории '.метанных вычислений, на основе которых стала возможной разработка аффективных инструментов программирования, были получены для функциональных и логических языков, а для к (леса императивных языков известны лишь экспериментальны';: разработки для отдельных представителей этого класса, характеризующиеся ограниченностью специализируемого языка и области приложения. Результаты применения таких лропегсоров для решения реальных задач оказываются неудовлетворительными.

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

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

ских программных процессоров для реальньч я ыков.

Целью диссертационной работы являются исс.ге. ■ 'ание принципов эффективных смешаннывкчисгений алголо! г лобных программ, построение основанной на этих 1ринцип<1\ '-.еоре-тической схемы специализации, нахождение алгоритмов pea..' озации этой схемы, не снижающих ее эффективность, и создание практического специализашора для реального языка пр .гъаммирсчания.

Научная новизна работы состоит в с лед; ю. дем:

• разработана новая схема поливариантнои ^псциализац; ^ алго-лоподобных программ, основанная на макеимальн м приближении процесса смешанных вычислений к пр' цессам трансляции и интерпретации и позволяющая суы> ствен-но уменьшить размеры и количество используемы* состояний памяти,

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

• разработаны методы специализации вычислений над динамически размещаем ми и внешними данными.

• разработаны миподы специализации модульных программ

Практическая ценность работы. На основе разработанных методов смешанных вычислений были созданы специализа-тор MixLan для модельного языка, включающего все основные свойства класса алгчлоподобных языков, и практический спе-циализатор M2Mix для языка Modula-2, не изучавшегося ранее в контексте смешанных вычислений. На базе этих процессоров был построен прототип операционной среды смешанных вычислений. Проведенная в рамках обоих проектов серия экспериментов показывает, что разработанная в диссер тации схема позволяет успешно применять смешанные вычисления для решении реальных задач в самых различных предмечных областях

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

Апробация работы и публикации Результаты работы докладывались и обсуждались на объединенном семинаре ИСИ СЮ РАН, НФ ИТМ и ВТ, НГУ "Системное программирование"

(май 1995 г., сентябрь 1995 г.). По теме диссертации опубликованы 3 научные ркботы. Работа частично поддерживалась грантом РФФИ N <М-1'1-0Ш7.

Структура и объем работы. Диссертационная работа состоит ия введения, рех глал, заключения, списка литературы из 64 наименований и д )ух приложений. Объем основной части рабо : — 149 страниц, оСъем приложений — 20 страниц. Работа включает 14 таблиц и 11 рисунков.

Содержание работы

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

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

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

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

ализации. Таким образом, основные элементы схемы — это расщепление каждой последовательности на те подпоследовательности, исполнение которых при специализации возможно в интерпретационном режиме, и нахождение тех точек, через которые переход в интерпретационном режиме не возможен.

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

специализации. Сравнивал значения этих переменных, специ-ализатор решает проблему сраинения вариантов исполнения и определяет, был ли порожден новый или уже известный вариант.

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

задержанные метки — метки, в момент исполнения переходов на которые возможны незаконченные действия по генерации остаточного кода или обработке оставшихся вариантов исполнения. Такие переходы откладываются до завершения всех неоконченных действий в последовательности, охватывающей соответствующую метку. Множество конфигурационных переменных задержанной метки определяется на основе множеств конфигурационных переменных в точке перевода и аппроксимации множества переменных, значения которых могут изменяться в промежутке между откладыванием задержанного перехода и его исполнением К задержанным переходам сводится проблема специали ¡ации задержанных циклов, т.е. циклов с задержанными условиями, но непустым множеством доступных результатов;

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

Возникновение гичек специализации во вложенных кон-

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

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

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

Далее изучается свойство эксплицируемости типов данных, т.е. возможность литерального изображения значения этого типа. Классическими примерами неэксплицируемых типов являются указатели и инкапсулированные типы данных. В целом, эксплицируемость типа определяется наличием эффективных способов генерации константных значений этого типа в программе и синтаксической позицией использования значения этого типа. Для специализатора эксплицируемость некоторого типа данных играет важную роль в связи с зависимостями по экспликации. Выражение в зависит по экспликации от выражения ei, если из задержанности ej следует необходимость эксплицировать в остаточной программе значение е. При этом, если выражение е — неэксплицируемого типа, то оно также должно быть задержано.

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

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

включение необходимой информации в типовую спецификацию внешней процедуры, этот "количественный" подход использовался в проекте ЛПхЬап, и классификация внешних процедур, достаточная для анализа периода связывания и выражающая качественные характеристики внешней процедуры, этот подход использовался в проекте М2М1Х, для которого была введена следующая классификация:

прозрачные внешние процедуры, которые не используют и не меняют внешних объектов; вызовы этих процедур аннотируются по тем ?ке правилам, что и стандартные операции языка;

задержанные внешние процедуры, которые используют задержанные внешние объекты, не описанные в исходной программе; вызовы этих процедур всегда задержаны,

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

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

В разделе 2.1 формально определяется входной язык (подмножество языка М1хЬап), на основе которого проводится дальнейшее изложение.

В разделе 2.2 описывается анализ синонимов. Для представления множеств синонимов используются механизм грамматик элементов памяти и понятие абстрактного терма доступа. При таком подходе две переменных программы объявляются синонимами, если соответствующие им абстрактные термы выводимы в одной грамматике. С помощью операции слияния элементов памяти определяется эффект синонимизации двух абстрактных термов. Пути исполнения программы моделируются цепями элементов памяти, получаемыми в результате последовательных применений операции слияния. Находится верхняя граница всех цепей — некоторое семейство грамматик элементов памяти и доказывается (теорема 2.2.1), что выводимость двух абстрактных термов в одной и той же грамматике из этого семейства является необходимым условием для

включения этой пары в отношение синонимов.

В разделе 2.3 анализ периода связывания определяется как построение и решение системы логических ограничений относительно времен связывания множеств синонимов, включающей начальную разметку переменных исходной программы в виде равенств [¡3s = false] для всех множеств синонимов S, в которые входят переменные, объявленные задержанными в исходной программе. Описываются ограничения, определяемые информационными зависимостями. Формально определяются понятия зависимостей по экспликации и управлению. Описываются способы нахождения ограничений для несохраняе-мых данных и вызовов внешних процедур. Затем обсуждаются способы решения этой системы и ее минимизации С помощью лемм 2.3.1, 2.3.2, 2.3.3 доказываются основные свойства аннотации анализа периода связывания — конгруентность, согласованность со свойством экспликации, согласованность со свойством сохраняемости. Завершает этот раздел описание правил вычисления остаточных типов частично-определенных структур данных.

В разделе 2.4 формально излагается анализ конфигураций. Сначала описываются нахождение различающих переменных и расстановка точек специализации (SP-аннотация). Для этого используются функции 6, определяющая множество различающих переменных после исполнения выражения (оператора) программы, и 7, определяющая неоднозначность значения выражения в различных вариантах исполнения. 5Р-аннотация разбивает программу на множество фрагментов, на котором определяется отношение достижимости — фрагмент fi достижим из f, если при специализации f возможна генерация конфигурации для fj. Для каждого фрагмента определяется множество результатов t. Для каждых фрагмента f и достижимого из него фрагмента f j определяются множество обязательных результатов на пути из t в f; и множество аргументов на пути из f в fj. На основе этих множеств строится система относительно множеств аргументов специализации фрагмента, т.е. переменных, являющихся аргументами данного фрагмента или фрагмента, достижимого из данного. Эти множества являются верхней оценкой множеств конфигурационных переменных, которая затем уточняется за счет сужения на множества тех аргументов специализации фрагмента, которые могут измениться в npojv .

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

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

В разделе 2.6 проводится доказательство корректности описанной схемы специализации. Для этого основной алгоритм разделяется на несколько шагов. На первом шаге вычисляется структура остаточной программы и выполняются действия, связанные с конфигурациями, но никакой редукции программы не проводится. Каждой вершине полученной таким образом программы р' сопоставляется сужение того состояния доступной памяти, на котором это выражение специализировалось, на множество аргументов этой вершины (/т-аннотация). С помощью теоремы 2.6.1 доказывается структурная эквивалентность (эквивалентность в смысле операционно-логической истории) исходной программы р и р'. Затем доказывается (теорема 2.6.1), что аннотация 1т является инвариантом исполнения р' для любых значений задержанных данных программы, т.е. для любого протокола исполнения р' и для любого элемента протокола е состояние памяти перед вычислением этого элемента, суженное на доступные аргументы, будет совпадать с хранящимся в 1т(е). Этот факт обеспечивает сохранение эквивалентности при выполнении дальнейшего преобразования р' — замены всех вхождений доступных переменных. как аргументов выражений на их значения хранящиеся в 1т В полученной таким образом программе р" проводятся редукция константных выражений, удаление неиспользуемых присваиваний, переменных, процедур и формальных параметров, редукция условных выражений с константными условиями. чистка операторов перехода. В результате этих преобразований, также сохраняющих эквивалентность, вычисляется

программа, совпадающая с остаточной программой рге.,, вычисляемой основным алгоритмом. Поэтому справедлива основная теорема:

Исходная программа р и остаточная программа ргes эквивалентны.

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

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

специализация машины Поста MPost(p.x) относительно программы р удвоения числа х;

специализация интерпретатора ассемблера для машины с сумматором Asm(p.s) относительно программы р обращения последовательности s;

специализация интерпретатора детерминированного автомата Fa(a.s), где s — входная последовательность, относительно языка а = (а6)*6; этот пример полностью приведен в приложении 1; специализации программы двоичного поискаSearch(x,а) относительно образца х в задержанном массиве а;

специализация программы Match(p,s) поиска по образцу р в строке s относительно образца р= ababb.

Наиболее интересным примером является специализация интерпретатора подмножества MixLan lnt(p,d) относительно программы р (d — данные программы р). Сравнение р и специали-

жированной на р ве рсии этого интерпретатора определяет близость нашего специализатора к гипотетическому "идеальному" по эффективности специализатору. Этот пример описывается в приложении 2.

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

Тест 1 2 3 4

MPost 58 108 2891 4956

Asm 312 871 17472 48298

Fa 5C 88 60 1005

Search 214 406 336 592

Match 26] 707 493 1450

Int 10965 29025 51765 261870

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

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

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

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

Завершают эту главу разделы, посвященные разработанным в рамках проекта М2№Пх методам построения генерирующих расширений для строго структурированных программ и постобработки остаточных программ.

В заключении перечисляются основные результаты работы.

Основные результаты

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

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

3. На основе разработанной теоретической модели впервые создан эффективный смешанный вычислитель для языка программирования \lodula-2.

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

1. Д В. Кочетов. Эффективная специализация алголоподобных программ (неформальное описание) // Средства и ин-с.труме.пти окружения программирования. — Новосибирск, 1995 - С.65-84

2. Д.В. Кочетов Алгоритмы анализа для специализации алголоподобных программ JJ Ср<дства и инструменты окружения программирования. — Новосибирск, 1995. — С.85-100.

3. М.А. Бульонков, Д.В. Кочетов Схема эффективной специализации императивных программ // Программирование.

Публикации по теме диссертации

1995. — № 5. — С.33-45.