Рефал-семинар 17 мая 2021 в 10:30 в Zoom'e
Andrei Klimov andrei_AT_klimov.net
Добрый вечер!
В понедельник 17 мая 2020 в 10:30 часов соберемся на онлайн-семинар по Рефалу:
Александр Коновалов (МГТУ имени Н.Э. Баумана)
Проблемы ссылочной эквивалентности замыканий при эквивалентных преобразованиях программ в Рефале-5λ
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 /* пусто */ = /* пусто */;
}
$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 /* пусто */ = /* пусто */;
}
На семинаре мы рассмотрим примеры нарушения эквивалентности преобразований и рассмотрим пути решения этой проблемы. Сразу скажу, что каждый из предлагаемых мною вариантов имеет свои недостатки. Надеюсь, на семинаре мы сможем найти приемлемый способ решения этой проблемы.
Александр Гусев gusev_aleksandr_AT_mail.ru
Отправлено из мобильной Почты Mail.ru
вторник, 18 мая 2021 г., 17:53 +0300 от Александр Коновалов <a.v.kon...@mail.ru>:
Александр!
Цель перевода рантайма на Си — переход на более низкоуровневый язык. Не смотря на то, что на C++ можно писать также, как и на Си, всё-таки стиль программирования на обоих языках различается. На C++ проще вводить новые абстракции: классы с методами, шаблоны, у C++ есть богатая библиотека шаблонов и т.д. И из-за этого код пишется с избыточным числом абстракций, более высокоуровневый и, возможно, более медленный. А использование стандартных библиотечных контейнеров ещё и замедляет компиляцию. Бедность выразительных возможностей Си (по сравнению с C++, конечно) приводит к тому, что код получается более плотным и более низкоуровневым. Когда пишешь, больше думаешь об эффективности и экономии ресурсов.
Ну, вот такие у меня ощущения и такое восприятие Си и C++. И исходя из этих ощущений, думаю, что Си лучше подходит как язык реализации рантайма языка.
С Golang’ом я знаком и считаю его слишком высокоуровневым для написания рантайма. Для каждой конструкции языка Си можно догадаться, в какой машинный код она откомпилируется, для Golang’а это не всегда верно (на мой взгляд). К тому же в Golang’е есть сборка мусора, а тут мне хочется управлять памятью самому. У Си рантайм очень тонкий. У Golang’а рантайм наоборот толстый.
С уважением,
Александр Коновалов
From: Александр Гусев <gusev_a...@mail.ru>
Sent: Tuesday, May 18, 2021 3:28 PM
To: Александр Коновалов <a.v.kon...@mail.ru>
Cc: Andrei Klimov <and...@klimov.net>; Arkady Klimov <arkady...@gmail.com>; Yuri Klimov <yu...@klimov.net>; Antonina Nepeivoda <a_n...@mail.ru>; Igor Adamovich <i.a.ad...@gmail.com>; Sergei Romanenko <sergei.r...@gmail.com>; Boyko Bantchev <boy...@gmail.com>; Михаил Апахов <m_ap...@mail.ru>; Владислав Пичугин <vlad19...@yandex.ru>
Subject: Re: RE: RE: Рефал-семинар 17 мая 2021 в 10:30 в Zoom'e
Добрый день, Александр!
Интерес, конечно, есть! Я завёлся на масштабный проект по Рефалу, а одной моей головы на всё не хватает. Приходится исследовать и чужой опыт.
Относительно языка реализации рекомендую ознакомиться с golang - он очень напоминает С, не требует переучиваться с нуля и гораздо легче в разработке, для меня по крайней мере.
И очень неплохо интегрирован в современные технологии.
Мой личный интерес тут - использование различных диалектов внутри одного серверного продукта, которым занимаюсь последнее время. Это бы повысило его качество, я думаю, и конкурентоспособность. Я очень заинтересован в возможности интеграции с другими разработчиками. И у меня в основе - golang.
Отправлено из мобильной Почты Mail.ru
вторник, 18 мая 2021 г., 14:53 +0300 от Александр Коновалов <a.v.kon...@mail.ru>:Добрый день, Александр!
Спасибо Вам за интерес к моей деятельности! Мне приятно, что интересное мне интересно и другим.
«Лично я — противник использования ссылок в Рефале.»
В общем-то я тоже. Поэтому в компиляторе до сих пор нет ссылочных типов данных вроде динамических ящиков. Единственные ссылочные данные, которые есть — это замыкания и они иммутабельны. В Рефале-2, Рефале Плюс и Рефале-6 мутабельные ссылочные данные есть.
«Для сравнения на равенство двух сложных объектов интересно использование хеш-кодов (или контрольных сумм). Интересно бы тут найти математику для определения операций над хешами, не заставляющими делать полный пересчёт „тяжёлых“ объектов.»
Математика такая есть — это так называемые кольцевые хеши (rolling hashes). Кольцевые хеши позволяют эффективно обновлять хеш, если к строке приписывается символ (с обеих сторон) или символ стирается (с обеих сторон), а также эффективно вычислять хеш конкатенации строк, если хеши самих строк известны.
Если в скобочных термах кэшировать хэш содержимого, то хеши переменных можно эффективно вычислять при сопоставлении с образцом, при условии, что известен хеш всего аргумента. Эффективно в том смысле, что порядок сложности при этом не меняется. На каждый элементарный акт сопоставления (включая накладные расходы на одну итерацию удлинения открытой e-переменной) будет требоваться констатное время для обновления хешей.
Но мне не очевидно, не превысят ли затраты на поддержку хешей потенциальную экономию при сравнениях на равенство.
«Рефал — достаточно требователен к качеству кода — найти ошибку в сложном рекурсивном дереве непросто.»
Не замечал, что Рефал сложнее в отладке по сравнению с другими языками программирования. Мне кажется, наоборот, аварийный останов при невозможности отождествления очень здорово помогает отлаживать.
«Поэтому меня удивила сама возможность появления логических ошибок при оптимизации.»
Ну, вот они есть. Чем сложнее система, тем больше шансов, что какие-то компоненты между собой противоречат. Здесь противоречит ссылочная эквивалентность и то, что высокоуровневые оптимизации умеют работать только с типами-данными. На семинаре было предложено два варианта решения проблемы: научить оптимизации (и не только их) работать с ссылочными типами или вообще от замыканий-ссылок отказаться.
Но, на мой взгляд, эти ошибки не критичные. Хотя, можно придумать стиль программирования, где эти проблемы будут существенными.
«Оптимизация, имеющая описываемые в презентации неопределённости, должна быть исключена.»
Ну, эти оптимизации довольно неплохо повышают производительность. При самоприменении по-моему процентов на 10–20 ускоряется (не помню, давно мерял).
«Возможно, я пропустил (немного сломался ноутбук именно сегодня), но интересно на чём реализована оптимизация: на Рефале-5л или на базовом для компилятора языке.»
Компилятор написан на себе, может генерировать интерпретируемый байткод или код на C++. Рантайм и интерпретатор написаны на C++. В будущем надеюсь переписать на чистый Си.
Преобразование кода выполняется не в терминах входного языка, а в терминах промежуточного, о котором я рассказывал на слайдах.
С уважением,
Александр Коновалов
From: Александр Гусев <gusev_a...@mail.ru>
Sent: Monday, May 17, 2021 11:17 PM
To: Александр Коновалов <a.v.kon...@mail.ru>
Cc: Andrei Klimov <and...@klimov.net>; Arkady Klimov <arkady...@gmail.com>; Yuri Klimov <yu...@klimov.net>; Antonina Nepeivoda <a_n...@mail.ru>; Igor Adamovich <i.a.ad...@gmail.com>; Sergei Romanenko <sergei.r...@gmail.com>; Boyko Bantchev <boy...@gmail.com>; Михаил Апахов <m_ap...@mail.ru>; Владислав Пичугин <vlad19...@yandex.ru>
Subject: Re: RE: Рефал-семинар 17 мая 2021 в 10:30 в Zoom'e
Уважаемые коллеги,
Я был не готов высказаться во время семинара, но сейчас несколько мыслей рвутся наружу.
1. Очень радует, что семинар состоялся. Сейчас в эпоху разобщения это очень важно для нас.
2. Мой любимый вопрос в курсе истории партии (ВКПБ): «чем творческое развитие марксизма отличается от ревизионизма?» - только точкой зрения оценивающего. Поэтому нет и не должно быть единого диалекта Рефала, пока есть диалекты, язык развивается.
3. Лично я - противник использования ссылок в Рефале. Оставьте их языкам близким к машинному уровню. Здесь же «ссылка» должна быть просто отсылкой к функции или объекту, но не адресом. Даже если в низкоуровневой основе это и адрес. Это как использование goto в императивных языках понижает качество кода. Goto - это для низкоуровневого кода, ассемблера и естественно присутствует в любой программе, но на машинном уровне.
4. Для сравнения на равенство двух сложных объектов интересно использование хеш-кодов (или контрольных сумм). Интересно бы тут найти математику для определения операций над хешами, не заставляющими делать полный пересчёт «тяжёлых» объектов.
5. Рефал - достаточно требователен к качеству кода - найти ошибку в сложном рекурсивном дереве непросто. Поэтому меня удивила сама возможность появления логических ошибок при оптимизации. Оптимизация, имеющая описываемые в презентации неопределённости, должна быть исключена. Возможно, нужно произвести реинжиниринг до постановки задачи и продолжать только при полной гарантии определённости. Например, избавиться от ссылок в имеющемся смысле. ))
5. Возможно, я пропустил (немного сломался ноутбук именно сегодня), но интересно на чём реализована оптимизация: на Рефале-5л или на базовом для компилятора языке.
Отправлено из мобильной Почты Mail.ru
понедельник, 17 мая 2021 г., 22:11 +0300 от Александр Коновалов <a.v.kon...@mail.ru>:Добрый вечер всем!
Ещё про ООП в Рефале. Забыл, что я когда-то кратко описал идиому ООП для Рефала-5:
https://mazdaywik.github.io/Refal-05/2-syntax.html#лирическое-отступление-ооп-врефале-05
С уважением,
Александр Коновалов
From: Александр Коновалов <a.v.kon...@mail.ru>
Sent: Monday, May 17, 2021 9:11 PM
To: 'Andrei Klimov' <and...@klimov.net>; 'Arkady Klimov' <arkady...@gmail.com>; 'Yuri Klimov' <yu...@klimov.net>; 'Antonina Nepeivoda' <a_n...@mail.ru>; 'Александр Гусев' <gusev_a...@mail.ru>; 'Igor Adamovich' <i.a.ad...@gmail.com>; 'Sergei Romanenko' <sergei.r...@gmail.com>; 'Boyko Bantchev' <boy...@gmail.com>; 'Михаил Апахов' <m_ap...@mail.ru>; 'Владислав Пичугин' <vlad19...@yandex.ru>
Subject: RE: Рефал-семинар 17 мая 2021 в 10:30 в Zoom'e
Добрый вечер, Андрей Валентинович!
Ошибку в имени файла поправил, теперь старая ссылка не работает. Новая:
В обновлённой презентации исправлены недочёты и опечатки, обнаруженные в ходе доклада.
«Вроде кто-то еще участвовал в начале. Владислав Пичугин досидел до конца, но у меня нет его адреса.»
Ещё участвовал Бойко Банчев, добавил его в список получателей.
Также добавил обоих дипломников, которые развивают рассмотренные оптимизации: Владислава Пичугина и Михаила Апахова. Рассмотренные на семинаре проблемы на их дипломы непосредственно не влияют, однако для лучшего понимания и представления предметной области им послушать это было полезно. (Ссылка на видео доклада в предыдущем письме Андрея Валентиновича.)
По рассмотренной проблеме есть заявка (issue) в багтрекере/тасктрекере репозитория Рефал-5λ:
Древесные оптимизации нарушают семантику · Issue #276 · bmstu-iu9/refal-5-lambda (github.com)
Там написано о проблеме и возможных решениях, но не так чётко и внятно, как на сегодняшнем докладе. Зато можно почитать, как развивалась моя мысль об этом.
Вообще, в тасктрекере Рефала-5λ много интересного. Например, вот задачи на дипломы (редкие задачи, назначенные не на меня):
https://github.com/bmstu-iu9/refal-5-lambda/milestone/16
Во время доклада Аркадий Валентинович задался вопросом: можно ли в Рефале сделать ООП с типами-значениями. Мой ответ — можно:
Добавить неполное ООП в Модульный Рефал · Issue #1 · Mazdaywik/mrefal (github.com)
Проект Модульного Рефала уже давно заглох, изредка в него раз в год что-то коммичу.
Абстрактные типы данных (квадратные скобки) изначально появились в нём и позже были перенесены в Рефал-5λ (он тогда назывался Простым Рефалом и служил back end’ом для Модульного). По ссылке выше написано, как можно абстрактным скобкам добавить методы. Ещё 4 года назад я придумал, как реализовать полиморфизм, а в прошлом месяце (последние комментарии) — как добавить и наследование. По заявке ничего не сделано — пока это только пустые размышления.
Реализация и полиморфизма, и наследования существенно использует модульность Модульного Рефала, поэтому в языках, где используется $EXTERN (Рефал-5, Рефал-6) её реализовать нельзя. Но можно реализовать в языке, где есть директива $IMPORT, например, в Рефале Плюс (только в нём ещё нужно запретить циклический импорт для корректной работы).
С уважением,
Александр Коновалов
From: Andrei Klimov <and...@klimov.net>
Sent: Monday, May 17, 2021 5:12 PM
To: Александр Коновалов <a.v.kon...@mail.ru>; Arkady Klimov <arkady...@gmail.com>; Yuri Klimov <yu...@klimov.net>; Antonina Nepeivoda <a_n...@mail.ru>; Александр Гусев <gusev_a...@mail.ru>; Igor Adamovich <i.a.ad...@gmail.com>; Sergei Romanenko <sergei.r...@gmail.com>
Subject: Re: Рефал-семинар 17 мая 2021 в 10:30 в Zoom'e
Александр и все, добрый вечер,
Я положил видео-запись семинара сюда (300M):
Файл презентации, использованной на семинаре (то есть еще с неисправленными опечатками, если Александр не обновит исправленным на этом же месте) лежит здесь:
В имени файла "2021-05-21" ошибочно. Сегодня 2021-05-17.
Посылаю только тем, кто реально участвовал, без цели широкого распространения. Скрин-шот списка участников я сделал на втором часу. Вроде кто-то еще участвовал в начале. Владислав Пичугин досидел до конца, но у меня нет его адреса.
Всего наилучшего,
Андрей
Александр Коновалов a.v.konovalov87_AT_mail.ru
Добрый день всем!
Публикую слайды прошедшего семинара:
Краткое содержание: я рассказал про Рефал-5λ, про оптимизации, реализованные в нём, привёл примеры того, что оптимизации реализуют неэквивалентные преобразования программ, рассмотрел два способа решения этой проблемы.
Доклад не только занял весь семинар, но и растянул семинар примерно на три часа. Поэтому обсудить, какой из двух рассмотренных способов лучше, мы не успели.
Проблема связана с тем, что замыкания — ссылочные данные, а оптимизации (прогонка и специализация, включая специализацию замыканий) умеют работать только с данными-значениями. Более того, промежуточный язык, в котором выполняются преобразования, не отражает того факта, что замыкания — ссылочные данные. В неоптимизированной программе это сходит с рук, а в оптимизированной возможны проблемы (в презентации приведены 4 разных примера).
Было предложено два пути решения:
- расширить промежуточный язык поддержкой ссылочных типов, соответственно, усложнить оптимизации и генерацию кода,
- отказаться от ссылочных типов вовсе, сделав замыкания типами-значениями — равенство будет проверяться не по ссылке, а по содержимому.
Оба варианта имеют свои преимущества и недостатки, ни один из них существенно не превосходит другой. Поэтому, как исправить проблему, я не знаю. В разные моменты времени я склоняюсь то к одному, то к другому решению.
С уважением,
Александр Коновалов
Александр Гусев gusev_aleksandr_AT_mail.ru
- Описать и обсудить с сообществом строгую математическую модель ссылки: что это, какие возможны с ней действия и т.п.;
- В соответствии с моделью расширить промежуточный язык;
- Оставить в компиляторе возможность обрабатывать ссылки по-прежнему — опционально;
- Добавить в оптимизацию отключаемую опцию обработки ссылок;
Такой подход не испортит того, что есть, пока идёт проработка и исследование новой возможности. И всегда можно сравнить подходы. Это как кнопка «Турбо» на старых персоналках. Машина работает быстрее, но не гарантирует работу всех программ.
Среда, 19 мая 2021, 10:52 +03:00 от Александр Коновалов a.v.konovalov87_AT_mail.ru <re...@botik.ru>:
Александр Коновалов a.v.konovalov87_AT_mail.ru
Добрый вечер, Александр!
«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 раза, ибо декартово произведение. Поэтому я не стал добавлять режимы, решил, что для тестов производительности достаточно сравнивать текущий код с коммитом, помеченным тегом.
Новая возможность, по идее, ничего не должна ломать. Единственный побочный эффект — экземпляры будут получать дополнительный бесполезный параметр, но оверхед на него, скорее всего, будет едва заметен.
С уважением,
Александр Коновалов
Александр Гусев gusev_aleksandr_AT_mail.ru
Добрый день, Александр!
Всегда можно откатиться на более ранний коммит. И при сравнении можно сравнивать старый коммит с актуальным.
У меня в этом году два дипломника развивают компилятор: один переделывает оптимизацию прогонки, другой — оптимизацию специализации. Сначала я думал добавить для них дополнительные режимы работы, но отказался от этой идеи. И так у меня есть грёбаная куча режимов. Для тестирования нужно проверять почти декартово произведение, т.к. некоторые ошибки вылезали только при комбинации режимов. Добавлять ещё два — это значит, увеличивать время работы тестов на 2×2=4 раза, ибо декартово произведение. Поэтому я не стал добавлять режимы, решил, что для тестов производительности достаточно сравнивать текущий код с коммитом, помеченным тегом.
Александр Коновалов a.v.konovalov87_AT_mail.ru
Добрый вечер, Александр!
«Моя логика такова: использование персоналок будет однозначно сокращаться, а код, на них ориентированный, плохо переносится в другие перспективные нынче среды, такие как интернет-серверы, интернет-клиенты и различные гаджеты.»
Вероятно, Вы правы, нужно думать о поддержке серверного ПО.
Но у меня компилятор самоприменимый и разрабатывается на персональной машине, поэтому основной пользователь работает на персоналке. Также компилятор может собрать и запустить два суперкомпилятора, написанные на Рефале-5: SCP4 и MSCP-A, они тоже предназначены для запуска на персоналках в первую очередь.
Так что имеет смысл в первую очередь сделать собственную работу комфортной: оптимизировать компилятор для сборки себя.
«Хотя я, при отсутствии тестировщика (или хотя бы „ночной сборки“)»
Для начала достаточно организовать набор самопроверяющихся тестов. Т.е. папку, в которой лежит батник и исходники-тесты. Батник перебирает все файлы, каждый исходник собирает и запускает — файл должен без ошибок откомпилироваться и не упасть. В самом исходнике может быть проверка вроде (пишу для примера на Рефале-5, т.к. не знаю ваш синтаксис):
$ENTRY Go { = <Check <Mul 2 2>> }
Check { 4 = }
Программа перемножает 2 на 2 и сверяет результат с 4. Если результат работы будет чем-то другим, то функция Check упадёт с ошибкой невозможности отождествления. Так исходник будет сам себя проверять.
После этого время от времени запускать батник и убеждаться, что ничего не сломалось. Можно запускать или перед каждым коммитом, или после каких-то серьёзных изменений в коде.
Рекомендую написать батник так, чтобы, если он вызывается без аргументов, то запускаются все тесты, иначе запускаются тесты, перечисленные в аргументах командной строки. Отлаживать будет удобнее.
В дальнейшем можно набор тестов расширить тестами на синтаксические ошибки — на них компилятор/интерпретатор не вылетает, а корректно сообщает об ошибке (и дальше не компилирует/не интерпретирует), и на намеренное падение (такие у меня тоже есть).
У меня вот эти автотесты распухли настолько, что требуют около часа времени. И распухли от декартова произведения различных режимов.
Вот так они у меня выглядят: refal-5-lambda/autotests at master · bmstu-iu9/refal-5-lambda (github.com).
Вот более простые и обозримые тесты в других моих проектах:
• refal-5-framework/tests/parser at master · Mazdaywik/refal-5-framework (github.com)
• Refal-05/autotests at master · Mazdaywik/Refal-05 (github.com)
Тесты не надо специально сидеть и сочинять. Начальный набор тестов насочинять, конечно, нужно, так, чтобы он охватывал основные возможности системы. А дальше тесты пишутся в двух случаях: ошибки и новая функциональность.
Выявили какую-то ошибку. Воспроизводим её. Тест для воспроизведения уменьшаем. Уменьшаем. Уменьшаем. Получается маленький автотест. Исправляем ошибку — новый автотест стал проходить. Коммитим его одновременно с исправлением ошибки. Появился ещё один автотест.
Хотим добавить новую функцию. Скажем, новую встроенную функцию или новую синтаксическую конструкцию. Пишем автотест, её проверяющий (один или несколько). Реализуем функциональность, чтобы автотест проходил. Коммитим одновременно новую функцию и автотест к ней. Появился ещё один автотест.
«сломал систему так, что уже месяц, наверное, не могу восстановить работоспособность»
Если бы были автотесты, можно было бы при помощи git bisect быстро найти коммит, который всё ломает.
Не исключаю, что автотесты Вы и без меня хорошо знаете, и уже давно их используете. Я пишу в рассылку, а в ней не все подписчики могут быть знакомы с этой полезной практикой.
С уважением,
Александр Коновалов
From: Александр Гусев gusev_aleksandr_AT_mail.ru <re...@botik.ru>
Sent: Thursday, May 20, 2021 11:32 AM
To: re...@botik.ru
Александр Гусев gusev_aleksandr_AT_mail.ru
Отправлено из мобильной Почты Mail.ru
Александр Коновалов a.v.konovalov87_AT_mail.ru
Добрый день всем!
(Те, кто был на семинаре, могут прочитать только вторую половину письма. Оно про то, что решение № 1 имеет две немного разные реализации и про то, что вариант № 1Б допускает реализацию именованных вложенных функций.)
Александр Гусев в предыдущем письме расписал по шагам этапы реализации решения № 1. Но проблема у меня не в том, чтобы решение № 1 реализовать, а в том, чтобы выбрать между № 1 и № 2. Сейчас я, кстати, склоняюсь к первому решению.
Хочу заметить вот ещё что, о чём было вскользь замечено на семинаре и чего на слайдах нет. А именно, решение № 1 имеет два варианта реализации.
Напомню проблему, прежде чем говорить о решении. Вот есть такая программа
$ENTRY Go {
e.X = <Prout <Eq <Dup { e.Y = e.X e.Y }>>>
}
Dup { s.X = s.X s.X }
Eq {
s.X s.X = True;
s.Y s.Z = False;
}
Создаётся замыкание, оно копируется и две копии сравниваются на равенство. Программа на входном языке переводится во внутренний язык:
$ENTRY Go {
e.X = <Prout <Eq <Dup {{ &Go\1 (e.X) }}>>>;
}
Go\1 { (e.X) e.Y = e.X e.Y }
…
Двойные фигурные скобки — конструктор замыкания. Они создают динамический ящик, ссылка на который помещается в поле зрения. Две такие ссылки сравниваются на равенство по ссылке: указывают на один и тот же ящик — равны, указывают на разные — не равны. Функция Dup копирует ссылку, получаются две ссылки на один ящик, функция Eq возвращает True.
Функция Dup встраивается:
$ENTRY Go {
e.X = <Prout <Eq {{ &Go\1 (e.X) }} {{ &Go\1 (e.X) }}>>;
}
В результате в правой части оказываются два конструктора замыкания, которые создают два разных статических ящика. Функция Eq уже видит две разные ссылки и теперь возвращает False.
Решение № 1 предлагает разбить создание замыкания на две фазы: создание уникальной ссылки при помощи генератора $NEW и связывания с этой ссылкой замыкания. Два замыкания сравниваются по этим новым ссылкам, и в статике (при трансформациях программ), и в динамике (во время выполнения):
$ENTRY Go {
e.X, $NEW : s.R = <Prout <Eq <Dup {{ s.R := &Go\1 (e.X) }}>>>
}
После встраивания Dup получим код
$ENTRY Go {
e.X, $NEW : s.R = <Prout <Eq {{ s.R := &Go\1 (e.X) }} {{ s.R := &Go\1 (e.X) }}>>
}
Получатся два замыкания, связанные с одной ссылкой s.R. В динамике они будут равны, т.к. ссылка s.R для них одна и та же. В статике будут равны, т.к. сравниваются по имени переменной перед «:=», а она одинаковая.
Когда я готовил презентацию, я предполагал, что оператор $NEW создаёт пустой динамический ящик, а конструкция {{ s.R := e.X }} записывает в этот ящик новое значение (старое выбрасывается). В коде выше оператор $NEW создаст пустой ящик, первый конструктор замыкания запишет в него выражение &Go\1 (e.X), положив в поле зрения ссылку s.R на этот ящик, второй конструктор перезапишет его содержимое выражением &Go\1 (e.X), т.е. тем же самым, тоже положит в поле зрения ссылку s.R. Таким образом, второй конструктор просто выполнит лишнюю работу, а в поле зрения окажутся две одинаковые ссылки. Функция Eq вернёт True, также как для неоптимизированного варианта. Назовём это решение решением № 1А.
Но в процессе доклада Андрей и Аркадий Климовы подсказали мне, что конструкцию {{ s.R := e.X }} можно с математической точки зрения рассматривать как пару из двух значений. При этом равенство определено так, что пары сравниваются на равенство по первым компонентам. Эту семантику можно закодировать дословно. $NEW порождает некий уникальный идентификатор (вовсе не динамический ящик), конструкция {{ s.R := e.X }} порождает новый динамический ящик, в содержимое которого добавлен уникальный идентификатор. Т.е. в предложении
e.X, $NEW : s.R = <Prout <Eq {{ s.R := &Go\1 (e.X) }} {{ s.R := &Go\1 (e.X) }}>>
оба конструктора замыканий создадут два разных динамических ящика, но помечены они будут одинаковым идентификатором. Идентификатор одинаковый, поэтому функция Eq сочтёт их равными, оптимизация тоже сохранит семантику. Назовём это решение решением № 1Б.
До семинара я колебался между двумя решениями, после — между тремя: № 1А, № 1Б, № 2.
Вложенные функции в Рефале-5λ безымянные из-за технических ограничений. Память для замыканий управляется обычным счётчиком ссылок — когда на замыкание исчезает последняя ссылка, оно удаляется. Если бы функции были именованными (как в Рефале-7), они могли бы быть рекурсивными и даже взаимно-рекурсивными. А циклические связи счётчик ссылок обработать не может, потребовалась бы сборка мусора. Впрочем, в ограниченных случаях рекурсивные и даже взаимно-рекурсивные именованные вложенные функции реализовать можно, но эта тема достойна ещё одно семинара.
К чему всё это. К тому, что решение № 1Б позволяет достаточно просто реализовать именованные вложенные функции даже если рантайм управляет памятью при помощи счётчика ссылок. Решение № 1А не позволяет.
С уважением,
Александр Коновалов
From: Александр Гусев gusev_aleksandr_AT_mail.ru <re...@botik.ru>
Sent: Wednesday, May 19, 2021 11:16 AM
To: re...@botik.ru
Subject: Re[2]: Рефал-семинар 17 мая 2021 в 10:30 в Zoom'e