Добрый день всем!
Мне в личке справедливо пожаловались на «многабукаф — ниасилил», поэтому даю
конспект письма про прогонку и неуспехи.
В первой части письма я кратко написал что такое прогонка, как её определил
Турчин, и разобрал прогонку на примере. На этом примере было показано, что
прогонка по Турчину для ограниченного Рефала (подмножество базисного Рефала)
может расширять область определения программы.
Во второй части письма я предложил другое подмножество Рефала — ограниченный
Рефал-6, в котором прогонка по Турчину уже не расширяет область определения
программы. Ограниченный Рефал-6 является базисным подмножеством Рефала-6, в
котором разрешены только L-образцы и, что главное, вместо равенства части
предложения разделяются запятой.
В третьей части письма я спекулирую на тему того, что суперкомпилятор
ограниченного Рефала расширяет область определения программы и предлагаю
несколько способов это расширение обуздать.
С уважением,
Александр Коновалов
From: Александр Коновалов a.v.konovalov87_AT_mail.ru <refal@botik.ru>
Sent: Wednesday, December 18, 2019 1:13 AM
To: refal@botik.ru
Subject: Прогонка по Турчину и неуспехи
Доброй ночи всем!
Пришло в голову одно интересное соображение. Но сначала контекст.
В 1974 году Турчин описал прогонку как эквивалентное преобразование программы
на Рефале (Москва: ЦНИПИАСС, 1974 (
<https://pat.keldysh.ru/~roman/doc/Turchin/1974-Turchin--E'kvivalentnye_preobrazovaniya_programm_na_Refale--CNIPIASS--ru.pdf>
pdf)). На самом деле прогонка была описана на два года раньше (Киев-Алушта,
1972 (
<https://pat.keldysh.ru/~roman/doc/Turchin/1972-Turchin--E'kvivalentnye_preobrazovaniya_rekursivnyx_funkcij__opisannyx_na_yazyke_Refal--ru.pdf>
pdf)), но там термина «прогонка» ещё не было.
В этих работах описывается подмножество базисного Рефала — ограниченный Рефал,
в котором в образцах запрещены любые t-переменные и открытые и повторные
e-переменные. Для этого подмножества определена прогонка — замена одного из
предложений функции F, содержащей вызов функции G на эквивалентный набор
предложений (в том числе и пустой), в которых вызов G отсутствует. При этом
семантика функции F на исходной области определения не меняется. Однако,
область определения функции F при этом может расшириться — если ранее программа
вылетала с ошибкой невозможности отождествления, то после прогонки одного из
вызовов функции программа может перестать падать (вместо чего выдавать какой-то
результат или зацикливаться).
Алгоритм прогонки я здесь описывать не буду, поскольку он есть в статьях по
гиперссылкам выше. Лучше читать работу Киев-Алушта, 1972 (
<https://pat.keldysh.ru/~roman/doc/Turchin/1972-Turchin--E'kvivalentnye_preobrazovaniya_rekursivnyx_funkcij__opisannyx_na_yazyke_Refal--ru.pdf>
pdf), поскольку она короче. Прогонка в ней — правило EF1.
Покажу на примере, как прогонка расширяет область определения. Пример простой,
но расписан подробно, читать рекомендуется по диагонали.
Буду использовать синтаксис Рефала-5, поскольку мне он более привычен.
F {
A e.Z = 1 e.Z;
s.X e.Z = <G s.X> e.Z;
t.X e.Z = 100 e.Z;
}
G {
P = 10;
Q = 20;
}
При прогонке мы комбинируем левые части предложений прогоняемой функции G с
левой частью предложения, содержащего вызов прогоняемой функции. Сам вызов
прогоняемой функции заменяем на соответствующие правые части. В результате
получится такая функция F:
F {
A e.Z = 1 e.Z;
P e.Z = 10 e.Z;
Q e.Z = 20 e.Z;
t.X e.Z = 100 e.Z;
}
Но, можно заметить, что область определения расширилась. Если ранее вызов <F X
Y Z> падал:
<F X Y Z> → <G X> Y Z → ошибка
то теперь он выдаёт ответ:
<F X Y Z> → 100 Y Z
Почему так происходит?
Рассмотрим сначала корректный случай, например, <F Q R S>.
До прогонки:
<F Q R S> → <G Q> R S → 20 R S
В исходной функции F аргумент сопоставится с левой частью второго предложения.
Вызов заменится на правую часть, где уже будет располагаться вызов <G Q>. Для
этого вызова применится второе предложение G, поскольку первое будет
неприменимо. Т.е. сначала второе предложение F, а затем второе предложение G.
После прогонки:
<F Q R S> → 20 R S
После прогонки сразу активируется третье предложение новой функции F, которое
является комбинацией исходного второго предложения F и исходного второго
предложения G. Второе предложение новой функции F здесь тоже будет неприменимо,
поскольку оно является комбинацией исходного второго предложения и первого
предложения функции G.
Теперь вернёмся к примеру <F X Y Z>. До прогонки активировалось второе
предложение F, после чего вызов G падал, поскольку ни одно из его предложений
не применимо. После прогонки становятся неприменимыми второе и третье
предложения новой функции F (т.к. неприменимы их прообразы в G) и управление
передаётся на четвёртое предложение.
Т.е. область определения может расширяться на те случаи, где прогоняемый вызов
должен был падать. (А может и не расширяться, если, к примеру, прогоняемый
вызов никогда не падает или предложение с этим вызовом самое последнее.)
Теперь перехожу к сути письма.
Условимся, что прогонять мы будем только самый первый вызов с пассивным
аргументом — в этом случае мы избежим нарушения порядка вычислений функций для
неленивого Рефала. При этом вот ограничении прогонка будет сохранять область
определения, если дополнить ограниченный Рефал неуспехами.
Определим такой ограниченный Рефал-6 — подмножество Рефала-6, в котором
предложения могут иметь вид «L-образец, результат». Т.е. в отличие от базисного
Рефала, в ограниченном Рефале-6 правая часть отделена от левой не равенством, а
запятой.
Что это даёт. Если в Рефале-6 ни одно из предложений функции оказалось
неприменимо, то программа аварийно не завершается, вместо этого функция
вырабатывает особое значение — «неуспех». Если функция возвратила неуспех в
результатном выражении после знака «=», то программа уже падает с ошибкой
«неперехваченный неуспех». Если неуспех возник в результатном выражении после
знака «,», то он может быть перехвачен и обработан программой. Я здесь не буду
подробно описывать семантику неуспехов, она есть в
<http://refal.ru/~arklimov/refal6/M3-six.htm> руководстве к Рефалу-6. Отмечу
лишь, что в программах ограниченного Рефала-6 управление в случае неуспеха
будет передаваться на следующее предложение.
Рассмотрим такую программу на ограниченном Рефале-6:
F {
A e.Z , 1 e.Z;
s.X e.Z , <G s.X> e.Z;
t.X e.Z , 100 e.Z;
};
G {
P , 10;
Q , 20;
};
Рассмотрим вызов <F X Y Z>. Первое предложение F окажется неприменимо.
Применится второе предложение. В правой части будет выполняться вызов <G X>.
Оба предложения функции G окажутся неприменимы — этот вызов вернёт неуспех.
Поскольку правая часть второго предложения вернула неуспех, управление будет
передано на третье предложение. Третье предложение успешно вычислится в 100 Y Z.
Для вызова <F> ни одно из предложений F окажется неприменимо, поэтому такой
вызов выработает неуспех.
Если мы для ограниченного Рефала-6 будем применять прогонку, как она описана у
Турчина, то область определения меняться не будет. Для этого примера мы получим:
F {
A e.Z , 1 e.Z;
P e.Z , 10 e.Z;
Q e.Z , 20 e.Z;
t.X e.Z , 100 e.Z;
}
Нетрудно заметить, что область определения не изменилась. Почему? Если до
прогонки активировалось второе предложение F, но ни один из образцов G не был
применим, то вырабатывался неуспех и управление передавалось на третье
предложение старой F. После прогонки оказываются неприменимы оба новых
предложения и управление естественным путём передаётся на четвёртое предложение
новой F.
Неуспехи были введены в Рефале-4 (Романенко, 1987 (
<https://pat.keldysh.ru/~roman/doc/1987-Romanenko--Refal-4_-_rasshirenie_Refala-2.pdf>
pdf)), правда там они назывались неудачами. Особенностью Рефала-4 было то, что
он замкнут относительно операции прогонки, при этом допускает образцы общего
вида (в отличие от L-образцов в ограниченном Рефале). Позже из Рефала-4
неуспехи перекочевали в Рефал Плюс, а оттуда уже в Рефал-6. Поэтому то, о чём я
пишу, не новость — это должно было быть очевидно Сергею Романенко, когда он
проектировал Рефал-4 и Рефал Плюс. Когда-то давно разрабатывался
суперкомпилятор-оптимизатор для Рефала-6. Если в Рефале-6 на тот момент уже
были неуспехи, то эта особенность прогонки тоже могла быть известна авторам
суперкомпилятора.
Так что я не претендую на эпохальное открытие, а делюсь, как мне кажется,
интересным наблюдением.
Суперкомпилятор для ограниченного Рефала будет расширять область определения
программы по двум причинам. Во-первых, Рефал язык аппликативный, а
суперкомпилятор реализует ленивую семантику. А вторая причина была подробно
разобрана в этом письме. И если первая — плата за бо́льшую глубину
преобразований, то вторую можно преодолеть несколькими способами.
Можно в исходных программах использовать только ортогональные образцы +
условия-неравенства. Любую программу на ограниченном Рефале (не ограниченном
Рефале-6) можно преобразовать в эквивалентную с непересекающимися образцами с
условиями-неравенствами.
Можно к каждой функции неявно добавлять предложение вида
F {
...
e.X = <F$fail e.X>;
}
где F$fail — (примитивная) функция, которая падает на любом аргументе. Такие
вызовы будут падать в остаточную программу ради сохранения области определения.
Так сделано в оптимизаторе-прогонщике Рефала-5λ (он не суперкомпилятор, но
прогонка в нём есть).
И, наконец, можно вместо ограниченного Рефала использовать ограниченный
Рефал-6. А если определить ограниченный ленивый Рефал-6, то область определения
программы будет сохраняться всегда.
С уважением,
Александр Коновалов
