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