Добрый вечер, Александр!
«1. Описать и обсудить с сообществом строгую математическую модель ссылки: что
это, какие возможны с ней действия и т.п.;»
На самом деле, про математическую модель ссылки подробно рассказывал Андрей
Климов на нескольких предыдущих семинарах. Анонсы этих семинаров в рассылку не
публиковались. Если Андрей Валентинович сочтёт нужным, он может дать ссылку на
слайды тех докладов.
То, о чём я рассказывал на семинаре (решение № 1), отчасти вдохновлено
семинарами Андрея Валентиновича.
«2. В соответствии с моделью расширить промежуточный язык;»
Расширение промежуточного языка описано в решении № 1:
$NEW : s.R
{{ s.R := &Func e.Content }}
Но это расширение в псевдокоде, синтаксисе для документирования. Во внутреннем
синтаксисе скорее всего будет что-то вроде
t.Closure ::= (ClosureBrackets t.RefId ":=" e.Expression)
e.Result ::= (New t.RefId*) e.Expression
t.RefId ::= t.Variable
И дальше потребуется все компоненты компилятора, работающие с внутренним
языком, использовать новое представление правых частей.
«3. Оставить в компиляторе возможность обрабатывать ссылки по-прежнему —
опционально;
4. Добавить в оптимизацию отключаемую опцию обработки ссылок;»
А вот это не надо. В компиляторе и так уже слишком много режимов компиляции,
чтобы добавлять ещё один.
«Такой подход не испортит того, что есть, пока идёт проработка и исследование
новой возможности. И всегда можно сравнить подходы.»
Всегда можно откатиться на более ранний коммит. И при сравнении можно
сравнивать старый коммит с актуальным.
У меня в этом году два дипломника развивают компилятор: один переделывает
оптимизацию прогонки, другой — оптимизацию специализации. Сначала я думал
добавить для них дополнительные режимы работы, но отказался от этой идеи. И так
у меня есть грёбаная куча режимов. Для тестирования нужно проверять почти
декартово произведение, т.к. некоторые ошибки вылезали только при комбинации
режимов. Добавлять ещё два — это значит, увеличивать время работы тестов на
2×2=4 раза, ибо декартово произведение. Поэтому я не стал добавлять режимы,
решил, что для тестов производительности достаточно сравнивать текущий код с
коммитом, помеченным тегом.
Новая возможность, по идее, ничего не должна ломать. Единственный побочный
эффект — экземпляры будут получать дополнительный бесполезный параметр, но
оверхед на него, скорее всего, будет едва заметен.
С уважением,
Александр Коновалов
From: Александр Гусев gusev_aleksandr_AT_mail.ru <refal@botik.ru>
Sent: Wednesday, May 19, 2021 11:16 AM
To: refal@botik.ru
Subject: Re[2]: Рефал-семинар 17 мая 2021 в 10:30 в Zoom'e
Добрый день!
Мне видится, что проблема успешно разбивается на последовательные части:
1. Описать и обсудить с сообществом строгую математическую модель ссылки:
что это, какие возможны с ней действия и т.п.;
2. В соответствии с моделью расширить промежуточный язык;
3. Оставить в компиляторе возможность обрабатывать ссылки по-прежнему —
опционально;
4. Добавить в оптимизацию отключаемую опцию обработки ссылок;
Такой подход не испортит того, что есть, пока идёт проработка и исследование
новой возможности. И всегда можно сравнить подходы. Это как кнопка «Турбо» на
старых персоналках. Машина работает быстрее, но не гарантирует работу всех
программ.
Стоит отметить, что п.1 здесь самый ответственный, наверное. Потом 2. А
остальное — дело техники.
Среда, 19 мая 2021, 10:52 +03:00 от Александр Коновалов
a.v.konovalov87_AT_mail.ru <refal@botik.ru <mailto:refal@botik.ru> >:
Добрый день всем!
Публикую слайды прошедшего семинара:
https://mazdaywik.github.io/direct-link/2021-05-17-Konovalov-Closures-and-Optimizations-Refal-5-lambda.pdf
Краткое содержание: я рассказал про Рефал-5λ, про оптимизации, реализованные в
нём, привёл примеры того, что оптимизации реализуют неэквивалентные
преобразования программ, рассмотрел два способа решения этой проблемы.
Доклад не только занял весь семинар, но и растянул семинар примерно на три
часа. Поэтому обсудить, какой из двух рассмотренных способов лучше, мы не
успели.
Проблема связана с тем, что замыкания — ссылочные данные, а оптимизации
(прогонка и специализация, включая специализацию замыканий) умеют работать
только с данными-значениями. Более того, промежуточный язык, в котором
выполняются преобразования, не отражает того факта, что замыкания — ссылочные
данные. В неоптимизированной программе это сходит с рук, а в оптимизированной
возможны проблемы (в презентации приведены 4 разных примера).
Было предложено два пути решения:
* расширить промежуточный язык поддержкой ссылочных типов,
соответственно, усложнить оптимизации и генерацию кода,
* отказаться от ссылочных типов вовсе, сделав замыкания типами-значениями
— равенство будет проверяться не по ссылке, а по содержимому.
Оба варианта имеют свои преимущества и недостатки, ни один из них существенно
не превосходит другой. Поэтому, как исправить проблему, я не знаю. В разные
моменты времени я склоняюсь то к одному, то к другому решению.
С уважением,
Александр Коновалов
From: Andrei Klimov andrei_AT_klimov.net <refal@botik.ru>
Sent: Sunday, May 16, 2021 11:06 PM
To: refal@botik.ru
Subject: Рефал-семинар 17 мая 2021 в 10:30 в Zoom'e
Добрый вечер!
В понедельник 17 мая 2020 в 10:30 часов соберемся на онлайн-семинар по Рефалу:
* Александр Коновалов (МГТУ имени Н.Э. Баумана)
Проблемы ссылочной эквивалентности замыканий при эквивалентных преобразованиях
программ в Рефале-5λ
Zoom-сеанс:
<https://us02web.zoom.us/j/86888134690?pwd=ZTlnUWQvSUVPN3RVUk1UdU8rZjB6Zz09>
https://us02web.zoom.us/j/86888134690?pwd=ZTlnUWQvSUVPN3RVUk1UdU8rZjB6Zz09
Meeting ID: 868 8813 4690
Passcode: Yaq97A
Аннотация:
Диалект Рефал-5λ является расширением Рефала-5 безымянными функциями. Внутри
безымянных функций можно ссылаться на переменные, связанные вне её. Для
безымянной функции во время выполнения программы создается объект замыкания,
содержащий указатель на код данной функции и значения захваченных переменных.
Эти объекты с точки зрения языка являются символами (сопоставляются с
s-переменными) и сравниваются на равенство по ссылке.
Пример программы с замыканиями:
Map {
s.Func t.Next e.Rest = <s.Func t.Next> <Map s.Func e.Rest>;
s.Func /* пусто */ = /* пусто */;
}
$ENTRY CartProd {
(e.Xs) (e.Ys)
= <Map { t.X = <Map { t.Y = (t.X t.Y) } e.Ys> } e.Xs>
}
Переменные, захваченные замыканиями, подчеркнуты.
Компилятор Рефала-5λ поддерживает две оптимизации: специализации и прогонки
функций. Оптимизация специализации для специально помеченных функций создает
специализированные экземпляры функций, учитывающие информацию о вызове,
известную во время компиляции. В частности, для обоих вызовов Map в функции
CartProd будут строиться экземпляры, учитывающие тот факт, что аргументами
являются конкретные замыкания:
$ENTRY CartProd {
(e.Xs) (e.Ys) = <Map
<file://e.mail.ru/compose/%3fmailto=mailto%253aMap@1%252520%2528e.Ys%2529%2526nbsp%253be.Xs>
@1 (e.Ys) e.Xs>;
}
Map@1 {
(e.Ys) t.Next e.Rest = <{ t.X = <Map
<file://e.mail.ru/compose/%3fmailto=mailto%253aMap@2%2526nbsp%253bt.X%2526nbsp%253be.Ys>
@2 t.X e.Ys> } t.Next> <Map
<file://e.mail.ru/compose/%3fmailto=mailto%253aMap@1%252520%2528e.Ys%2529%2526nbsp%253be.Rest>
@1 (e.Ys) e.Rest>;
(e.Ys) /* пусто */ = /* пусто */;
}
Map@2 {
t.X t.Next e.Rest = <{ t.Y = (t.X t.Y) } t.Next> <Map
<file://e.mail.ru/compose/%3fmailto=mailto%253aMap@2%2526nbsp%253bt.X%2526nbsp%253be.Rest>
@2 t.X e.Rest>;
t.X /* пусто */ = /* пусто */;
}
Оптимизация прогонки встраивает функции в точки их вызова. Это преобразование
программ было описано Турчиным (для подмножества Рефала) в 1972 (тезисы
конференции Киев-Алушта) и в 1974 (сборник ЦНИПИАС) годах. В рассмотренном
примере оптимизация прогонки встроит вызовы вложенных функций:
$ENTRY CartProd {
(e.Xs) (e.Ys) = <Map
<file://e.mail.ru/compose/%3fmailto=mailto%253aMap@1%252520%2528e.Ys%2529%2526nbsp%253be.Xs>
@1 (e.Ys) e.Xs>;
}
Map@1 {
(e.Ys) t.Next e.Rest = <Map
<file://e.mail.ru/compose/%3fmailto=mailto%253aMap@2%2526nbsp%253bt.Next%2526nbsp%253be.Ys>
@2 t.Next e.Ys> <Map
<file://e.mail.ru/compose/%3fmailto=mailto%253aMap@1%252520%2528e.Ys%2529%2526nbsp%253be.Rest>
@1 (e.Ys) e.Rest>;
(e.Ys) /* пусто */ = /* пусто */;
}
Map@2 {
t.X t.Next e.Rest = (t.X t.Next) <Map
<file://e.mail.ru/compose/%3fmailto=mailto%253aMap@2%2526nbsp%253bt.X%2526nbsp%253be.Rest>
@2 t.X e.Rest>;
t.X /* пусто */ = /* пусто */;
}
В текущей реализации эти две оптимизации хорошо работают только с
данными-значениями — преобразования программы остаются эквивалентными.
Замыкания являются ссылочными данными и можно написать пример программы, где
эквивалентность преобразований нарушается.
На семинаре мы рассмотрим примеры нарушения эквивалентности преобразований и
рассмотрим пути решения этой проблемы. Сразу скажу, что каждый из предлагаемых
мною вариантов имеет свои недостатки. Надеюсь, на семинаре мы сможем найти
приемлемый способ решения этой проблемы.
До Zoom-встречи!
Андрей Климов
С уважением,
Александр Гусев
gusev_aleksa...@mail.ru <mailto:gusev_aleksa...@mail.ru>
