Диссертация (1150902), страница 13
Текст из файла (страница 13)
Притаком подходе программные точки исходной программы, подлежащие специализации, называют точками специализации, а получаемые на их основе с учётомзначений статических данных их специализированные версии называют специализированными программными точками. Примером точек специализации могут служить базовые блоки низкоуровнего императивного языка программирования, а также объявления функций в функциональных языках программирования(см.
[68]). Построение оптимального множества точек специализации являетсянетривиальной задачей, от конкретного решения которой существенно зависитрезультат самой специализации (см. [68]).5.2. Проекции Футамуры или проекции Футамуры–Ершова–ТурчинаЧастичный вычислитель называется самоприменимым, если он способен специализировать себя самого на некоторую программу.
Естественно, это подразумевает, что язык реализации частичного вычислителя не отличается от языка,для которого он написан. Классическим применением самоприменимых частичных вычислителей являются проекции Футамуры, использующие специализациюдля компиляции программ, генерации компиляторов и генераторов компиляторов [69]. Пусть даны произвольные языки S, T, L0 , L1 , L2 , программа s на языкеS 21 , интерпретатор int языка S на языке T 22 и частичные вычислители mixTL0 ,mixLL01 и mixLL12 23 , тогда24 :21Мы будем обозначать sS программу s, написанную на языке S.Мы будем обозначать intST интерпретатор int языка s, написанный на языке T .23Мы будем обозначать mixST частичный вычислитель mix языка s, написанный на языке T .24Запись [[s]]S означает семантику программы s в языке S.22741.
Первая проекция Футамуры: специализация интерпретатора на программу суть программа на языке реализации интерпретатора.[[mixTL0 (intST , sS )]]T = tT : ∀x . [[tT ]]T x = [[intST ]]T (sS , x)Первая проекция Футамуры производит компиляцию программы s, реализованной на языке S, в программу t на языке T путём специализации интерпретатора для языка S на языке T . Сгенерированная и исходная программыt и s реализованы на разных языках, но имеют одинаковое поведение на всехвходных данных.2. Вторая проекция Футамуры.tT = [[mixTL0 ]]L0 [intST , sS ]I проекция Футамуры= [[[[mixLL01 ]]L1 [mixTL0 , intST ]]]L0 sS по определению mix= [[compLS→T]]L0 sS0по определению компилятораВторая проекция Футамуры генерирует компилятор25из языка S в языкT путём специализации частичного вычислителя mix на интерпретатор.Для любой программы на языке S сгенерированный компилятор генерирует программу, обладающую тем же поведением, что программа, сгенерированная первой проекцией Футамуры.
Таким образом, вторая проекция Футамуры может быть сформулирована следующим образом: специализацияспециализатора на интерпретатор суть компилятор из исходного языка вязык реализации интерпретатора.comp = [[mix]][mix, int]3. Третья проекция Футамуры.compS→T= [[mixLL01 ]]L1 [mixTL0 , intST ]L0II проекция Футамуры= [[[[mixLL12 ]]L2 [mixLL01 , mixTL0 ]]]L1 intST по определению mix= [[cogenTL1 ]]L1 intSTпо определениюПо определению компилятором называется такая программа comp, что [[compS→T]]L [sS ] = tTLD .
[[sS ]]S [d] = [[tT ]]T [d]25:∀d ∈75Третья проекция Футамуры генерирует генератор компиляторов cogen путём специализации частичного вычислителя на другой частичный вычислитель. Тогда по интерпретатору произвольного языка S, реализованного наязыка T , cogen генерирует компилятор из языка S в язык T . Таким образом,третья проекция Футамуры может быть сформулирована следующим образом: специализация специализатора на специализатор суть генератор компиляторов, который по интерпретатору языка генерирует компилятор изинтерпретируемого языка в язык реализации интерпретатора.cogen = [[mix]][mix, mix]4. Четвёртая проекция Футамуры.Изначально Футамура сформулировал только первые две проекции [67].Ещё одна проекция была сформулирована А.П.
Ершовым, а её авторство отдавалось В.Ф. Турчину. В 2009 году R. Glück сформулировал и четвёртуюпроекцию Футамуры [97]. В действительности четвёртая проекция утверждает, что генератор компиляторов, порождённый оптимальным самоприменимым частичным вычислителем, должен быть способен сгенерироватьсам себя.[[cogen]]mix = cogenОдним из основных свойств частичного вычислителя является то, что оптимальный частичный вычислитель способен устранить накладные расходы, появляющиеся при интерпретации [68]. А именно, частичный вычислитель называется оптимальным по Джонсу (Jones optimal), если ∀p, ∀d ∈ D, tp′ (d) ≤ tp (d), гдеsint — самоинтерпретатор26 , p′ = [[mix]] sint p, а tp (d) обозначает время исполнения программы p на данных d.26Самоинтерпретатором называется интерпретатор языка, на котором он сам реализован.765.3.
Компиляциянетипизированноголямбда-исчисления путём специализации алгоритматрассирующей нормализацииИтак, частичные вычисления могут быть использованы для специализацииалгоритма нормализации на входное лямбда-выражение (см. [68]). Будучи применённым к алгоритму трассирующей нормализации для нетипизированноголямбда-исчисления UNP, частичный вычислитель произведёт компиляцию этоговыражения в эквивалентный код на языке низкого уровня, не содержащий следовсинтаксиса лямбда-исчисления.5.3.1.
Преобразование нормализирующей процедуры в компиляторЧастичные вычисления способны преобразовать нормализирующую процедуру N P нетипизированного лямбда-исчисления (далее ULC) равно как и простоготипизированного лямбда-исчисления (далее STLC) в программу, реализующуюфункцию, сохраняющую семантику:f : ULC → LLL (or f : STLC → LLL).Это утверждение является прямым следствием второй проекции Футамуры, которое может быть записано с помощью диаграмм следующим образом (см. [68]):Если N P ∈LCL, то [[spec]](spec,NP) ∈LC-LLLL.Здесь LC означает либо ULC, либо STLC, L — язык реализации частичного вычислителя и процедуры нормализации, а LLL — под-язык языка L такой,что его выразительной силы достаточно для представления всех динамических (всмысле частичных вычислений) операций, содержащихся в N P .Развитие этого направления и реализация вышеописанного подхода для рядасуществующих языков программирования может привести к созданию универсального языка промежуточного представления, предназначенного для описания77семантик языков программирования и автоматической генерации компиляторов,основанной на семантике (semantics-directed compiler generator, дальнейшие детали см.
[74, 75]).5.3.2. Специализация UNP на входной лямбда-термВ процессе специализации нормализирующей процедуры UNP на входнойлямбда-терм M частичный вычислитель должен устранить все операции, зависящие только от M . Таким образом, результат такой специализации, U N PM , навходных данных d не произведёт операций, зависящих от M . Он будет содержатьлишь операции по расширению текущего обхода, а также проверки токенов насинтаксическое равенство, чтобы следовать правилам построения указателей. Заметим, что токены в данном случае используются как метки (имена) и не имеютникакой связи с лямбда-исчислением.
Иными словами, подвыражения исходноготерма не встречаются в специализированной программе. Множество же токеновявляется конечным ввиду конечности числа точек специализации, а сами токеныиспользуются как метки, и для проверки токенов на равенство, они могут бытьзаменены, например, на числовые метки.Для успешной специализации сначала необходимо произвести анализ времени связывания (binding time analysis). А именно, разбить всё множество операцийнормализирующей процедуры UNP, приведённой на рисунке 19, на два вида: статические и динамические.
Анализ времени связывания не зависит от входноголямбда-терма M . Стандартным способом построения такого разбиения является аннотирование кода специализируемой программы (детали могут быть найдены в [68]). Вычисления в UNP помечаются как динамические, также называемые остаточными, т.е.
такие для которых будет сгенерирован остаточный код вU N PM , или статические, т.е. подлежащие развёртке (unfold) во время специализации.В процессе специализации некоторые динамические по определению переменные могут быть рассмотрены как статические, если множество значений, которые они могут принимать, является конечным. Такие переменные называютсяпеременными со статически ограниченным множеством значений (variables ofbounded static variation в терминологии из [68]).
Например, в случае процедуры78трассирующей нормализации, приведённой на рисунке 19, переменная e являетсяпеременной со статически ограниченным множеством значений: она может принимать только значения подвыражений исходного терма M , которых для каждогоданного терма, конечно, конечное число. Также все логические флаги, очевидно,являются переменными со статически ограниченным множеством значений. Дляпеременных со статически ограниченным множеством значений в целях улучшения результата специализации в её процессе может быть применён так называемый “The Trick” (см.
[68]).Суть приёма “The Trick” заключается в следующем. Каждое возможное значения переменной со статически ограниченным множеством значений рассматривается как отдельная точка специализации. С целью уменьшения множествавозможных значений переменной со статически ограниченным множеством значений в общем случае используются различные эвристики или методы статического анализа. Таким образом, для всех возможный значений такой переменнойв специализированной программе будет создана специализированная версия вычислений, в которые эта переменная вовлечена.Динамическими же в случае UNP являются переменные bh и ch, представляющие связывающий указатель и указатель потока управления.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
