Добрый день! Мне видится, что проблема успешно разбивается на последовательные части: * Описать и обсудить с сообществом строгую математическую модель ссылки: что это, какие возможны с ней действия и т.п.; * В соответствии с моделью расширить промежуточный язык; * Оставить в компиляторе возможность обрабатывать ссылки по-прежнему — опционально; * Добавить в оптимизацию отключаемую опцию обработки ссылок;
Такой подход не испортит того, что есть, пока идёт проработка и исследование новой возможности. И всегда можно сравнить подходы. Это как кнопка «Турбо» на старых персоналках. Машина работает быстрее, но не гарантирует работу всех программ. Стоит отметить, что п.1 здесь самый ответственный, наверное. Потом 2. А остальное — дело техники. >Среда, 19 мая 2021, 10:52 +03:00 от Александр Коновалов >a.v.konovalov87_AT_mail.ru <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 >>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-встречи! > >Андрей Климов С уважением, Александр Гусев gusev_aleksa...@mail.ru
