Добрый день всем! Публикую слайды прошедшего семинара:
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 <mailto:Map@1%20(e.Ys) e.Xs> @1 (e.Ys) e.Xs>; } Map@1 { (e.Ys) t.Next e.Rest = <{ t.X = <Map <mailto:Map@2 t.X e.Ys> @2 t.X e.Ys> } t.Next> <Map <mailto:Map@1%20(e.Ys) e.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 <mailto:Map@2 t.X e.Rest> @2 t.X e.Rest>; t.X /* пусто */ = /* пусто */; } Оптимизация прогонки встраивает функции в точки их вызова. Это преобразование программ было описано Турчиным (для подмножества Рефала) в 1972 (тезисы конференции Киев-Алушта) и в 1974 (сборник ЦНИПИАС) годах. В рассмотренном примере оптимизация прогонки встроит вызовы вложенных функций: $ENTRY CartProd { (e.Xs) (e.Ys) = <Map <mailto:Map@1%20(e.Ys) e.Xs> @1 (e.Ys) e.Xs>; } Map@1 { (e.Ys) t.Next e.Rest = <Map <mailto:Map@2 t.Next e.Ys> @2 t.Next e.Ys> <Map <mailto:Map@1%20(e.Ys) e.Rest> @1 (e.Ys) e.Rest>; (e.Ys) /* пусто */ = /* пусто */; } Map@2 { t.X t.Next e.Rest = (t.X t.Next) <Map <mailto:Map@2 t.X e.Rest> @2 t.X e.Rest>; t.X /* пусто */ = /* пусто */; } В текущей реализации эти две оптимизации хорошо работают только с данными-значениями — преобразования программы остаются эквивалентными. Замыкания являются ссылочными данными и можно написать пример программы, где эквивалентность преобразований нарушается. На семинаре мы рассмотрим примеры нарушения эквивалентности преобразований и рассмотрим пути решения этой проблемы. Сразу скажу, что каждый из предлагаемых мною вариантов имеет свои недостатки. Надеюсь, на семинаре мы сможем найти приемлемый способ решения этой проблемы. До Zoom-встречи! Андрей Климов
