Синтаксис словарей в Рефале!
Александр Коновалов a.v.konovalov87_AT_mail.ru
Добрый день всем!
Аркадий Валентинович в соседнем письме писал:
«Однако сразу отмечу, чего здесь не хватает и что плохо даётся.
1. Таблицы, словари с быстрой выборкой по ключу (можно сделать внешними средствами, но это выглядит как чужеродный объект).»
У меня есть мысли, как добавить в синтаксис Рефала словари с синтаксисом в духе Рефала, в частности, поиск будет осуществляться при помощи сопоставления с образцом. Возможно, несколько лет назад я писал об этом, не помню.
Когда производительность не важна, программисты на Рефале словари выражают через ассоциативные списки — последовательности термов, в формате которых выделяются ключ и значение. Например, отобразим имена на числа:
('Алиса' 123) ('Борис' 456) ('Вера' 789) ('Глеб' 987)
Формат каждого терма — (e.Name s.Scores).
Поиск в таком словаре выражается через сопоставление с образцом с открытой переменной:
e.ScoreTable-B ('Вера' s.Scores) e.ScoreTable-E = <Prout 'У Веры ' s.Scores 'очков'>
(В случаях поиска обе половинки словаря я предпочитаю называть одним именем с суффиксами -B и -E соответственно. Такое наименование снижает риск потерять в правой части одну из половинок, однажды наблюдал такую ошибку в чужом коде.)
Добавление в словарь осуществляется путём добавления нового терма соответствующего формата:
e.ScoreTable ('Дарья' 654) ('Егор' <+ 300 21>)
Объединение словарей естественно выражается через конкатенацию:
e.ScoreTable1 e.ScoreTable2
Отметим некоторые особенности этой идиомы:
- Это мультисловарь, ключи в словаре могут повторяться. Словарные пары с равными ключами сохраняют относительный порядок. При поиске по открытой переменной будет находиться самое левое вхождение словарной пары с конкретным ключом. Некоторые диалекты (Рефал-2, -7, Плюс) допускают удлинения открытых переменных справа-налево, что позволяет находить самое правое вхождение.
- Вообще-то говоря, то, что словарные пары с равными ключами сохраняют свой относительный порядок, следует из того, что все словарные пары сохраняют свой относительный порядок. Но, эффективные реализации словарей порядок ключей по умолчанию не помнят — деревья сортируют по возрастанию, хеш-таблицы в непредсказуемом порядке, поэтому при реализации эффективных словарей в Рефале сохранять порядок всех словарных пар будет сложнее, нежели только пар с равными ключами.
- Идиома применима или для небольших словарей, или в случае, когда производительность некритична, т.к. сложность поиска O(n).
- Идиома вынуждена объединять в один терм два компонента словарной пары с использованием формата.
- Это и недостаток, и преимущество (в разных ситуациях можно осуществлять поиск по разным компонентам). У кого 456 очков?
e.ScoreTable-B (e.Name 456) e.ScoreTable-E - При поиске идиома вынуждена разбивать словарь на две переменные (с суффиксами -B и -E).
Один из путей эволюции языков программирования — добавление специального синтаксиса для идиом. Пойдём и мы этим путём.
Предлагается для словарей ввести новый тип значений с новым видом переменных (пусть будут d-переменные, от слова dictionary, вариант: m-переменные от map или multidict) и новыми скобками (пусть будут квадратными).
Словарь является мультисловарём — в нём допустимы словарные пары с равными ключами. Относительный порядок пар не определён, гарантируется лишь относительный порядок пар с равными ключами. В дальнейшем приставку «мульти-» писать не будем, будем просто писать «словарь».
Синтаксис. Словари, в отличие от выражений (e-переменных, содержимого круглых скобок), хранят всегда чётное количество термов. Причём термы в нечётных позициях играют роль ключей, в чётных — значений. Соответственно, пара соседних термов — словарная пара. Пример словаря:
[('Алиса') 123 ('Борис') 456 ('Вера') 789 ('Глеб') 987]
Внутри квадратных скобок допустимы лишь d-переменные или термы (символы, s- и t-переменные, (скобочные) и [словарные] термы), причём смежных термов должно быть чётное количество. Вызовы функций и e-переменные внутри квадратных скобок недопустимы. И наоборот — на верхнем уровне выражений и внутри круглых скобок недопустимы d-переменные.
Примеры правильных словарных термов:
[d.x]
[t.k1 t.v1 d.p1 t.k2 t.v2 t.k3 t.v3 d.p2]
[s.A (<F e.1>) s.B (e.2) d.ABC d.XYZ s.X (<G e.3>)]
[(e.1) [d.1] d.1 (<ReadKey>) (e.1)] /* словарь может использоваться и как значение */
[[A 1] [B 2]] /* словарь в качестве и ключа, и значения */
Возможно, последнее будет запрещено, если использование словарей внутри ключей окажется неоправданно сложным в реализации и неэффективным.
Примеры неправильных словарных термов и предложений:
[d.x t.1] /* нечётное количество термов */
[d.x t.1 t.2 t.3 d.y] /* тоже нечётное количество термов */
[t.1 t.2 t.3 d.x t.4] /* две группы нечётного количества термов */
[e.x] /* е-переменная в квадратных скобках */
[d.x <F> t.1 t.2] /* вызов функции в квадратных скобках */
<F d.x> /* d-переменная вне квадратных скобок */
(d.x) /* тоже самое */
d.x = d.x A B; /* d-переменная на верхнем уровне выражения */
Некоторые синтаксические ограничения можно ослабить, если язык поддерживает описания форматов функций (например, как Рефал Плюс). Тогда, если аргумент описан как d-значение, то в образце на верхнем уровне могут быть d-переменные, группы смежных термов должны иметь чётную длину — содержимое квадратных скобок без самих квадратных скобок снаружи. Аналогично и с правой частью, когда описан как d-значение результат. Внутри квадратных скобок в результатном выражении можно будет использовать и вызовы функций [d.1 <F e.X> d.2], если выходной формат описан или как d-значение, или как чётное количество термов (в том числе и нулевое).
Семантика. В правой части всё просто — из содержимого квадратных скобок создаётся новый (мульти)словарь. Запись
[t.Key t.Value d.Table]
означает добавление словарной пары t.Key t.Value к словарю d.Table слева, а запись
[d.Table t.Key t.Value]
соответственно, справа. Добавление слева и справа определяет положение новой словарной пары относительно других словарных пар с тем же ключом (не забыли про «мульти-»?), соответственно, перед или после.
Конкатенация d-переменных
[d.Table1 d.Table2]
означает объединение словарей, причём если ключ t.Key присутствует в обоих словарях, то в результирующем словаре пары из левого словаря будут предшествовать парам из правого.
Возможны и более сложные комбинации:
[s.K1 (e.V2) d.Local s.K2 (e.V2) s.K3 (e.V3) d.Global s.K4 (e.V4)]
С образцами немного хитрее. d-переменные ведут себя как e-переменные, в тривиальном случае [d.closed] ведёт себя как закрытая переменная — сопоставляется однозначно за константное время, а во всех остальных случаях — как открытая. Например, образец
[(s.1 s.2) (s.1 s.2 s.1) d.Table]
будет сканировать весь словарь d.Table в поисках словарной пары с ключом из двух символов и значением из трёх символов, начинающимся с ключа. Порядок перебора не определён, за исключением словарных пар с равными ключами — та, что левее, будет рассмотрена раньше, чем та, что правее — из-за того, что образец пары определён слева от d-переменной.
[d.ScoreTable ('Вера') s.Scores]
будет перебирать словарь в поисках пары с ключом ('Вера'), причём, если таких пар несколько, будет выбрана самая последняя, т.к. образец пары справа от d-переменной. Заметим, что здесь ключ определён полностью, а значит поиск будет выполняться эффективно (то, ради чего мы описываем словари).
Если образец сложный, то словарь может перехватывать откаты:
e.X [(e.X) (e.Y) d.Dict] (e.Y e.Z)
Разберём этот пример подробнее:
- Первой сопоставится и получает значение переменная e.X, т.к. она закрытая.
- Теперь у нас два неоднозначных подобразца — словарь и конкатенация неизвестных переменных e.Y e.Z, выбираем тот, что левее — словарь.
- В словаре ищем словарную пару уже определённым ключом (e.X) и неопределённым значением (e.Y), в результате переменная e.Y получает значение. Поиск выполняется эффективно, т.к. значение ключа известно. Если в словаре несколько словарных пар с ключом (e.X), выбирается самая левая.
- Происходит попытка сопоставления с повторной переменной e.Y. Если оно успешно, то закрытая переменная e.Z тоже получает своё значение. Если нет, происходит откат в словарь и ищется следующая словарная пара, подходящая под образец (e.X) (e.Y), т.е. следующая пара с ключом (e.X).
Понять семантику откатов в словарь будет проще, если мысленно заменить словарь на эквивалентный образец с ассоциативным поиском и открытой e-переменной, для примера выше это
e.X (e.Dict-B ((e.X) (e.Y)) e.Dict-E) (e.Y e.Z)
При неудаче сопоставления с повторной e.Y будет произведён откат к удлинению открытой переменной e.Dict-B.
В случае образцов вида [t.K t.V d.D] или [d.D t.K t.V], если переменные t.K и t.V не определены, будет выбрана словарная пара с произвольным ключом, если ключ повторяется, то самая левая или самая правая, соответственно. Переменная d.D сопоставится с остатком — исходным словарём за вычетом пары t.K t.V.
Повторные переменные должны сопоставляться с равными образцами без учёта относительного порядка пар с неравными ключами.
Сопоставление с образцом, по определению, это поиск таких значений переменных, при подстановке которых в образец получается выражение, равное сопоставляемому с образцом. Исходя из этого, образец [d.X d.Y] должен означать разбиение сопоставляемого образца на два подмножества словарных пар. При этом, если одна из переменных d.X или d.Y уже получила значение, то вторая получит значение разности сопоставляемого словаря и значения означенной переменной. Если же обе переменные не означились, и данный образец ловит откаты, то нужно будет сделать перебор O(2^N) всех возможных подмножеств (учёт повторяющихся ключей формулу немного усложнит, но показательная функция останется). Если же образец откаты не ловит, то d.X будет пустым, а d.Y съест всё (по аналогии с e.X e.Y).
Таким образом, образцы вида [d.X d.Y], где обе переменные не определены, имеет смысл запретить — из-за экспоненциального перебора и сложности реализации, когда образец принимает откаты, и бесполезности, когда не принимает. Если же одна из переменных определена, то такую конструкцию имеет смысл разрешить (вычитание/проверка на подмножество будет сравнимо по трудоёмкости реализации с объединением).
Кстати, заметим, что если значения сделать равными друг другу [t.K1 0 t.K2 0 … t.Kn 0], то мультисловарь обращается в мультимножество. Если сделать ключи равными друг другу [0 t.V1 0 t.V2 … 0 t.Vn] то словарь будет изоморфен объектному выражению t.V1 t.V2 … t.Vn, включая образцовые и результатные выражения со словарями — этот эффект достигается из-за уточнения семантики на ситуации с равными ключами.
Быстродействие. Данные Рефала — неизменяемые, сопоставление с образцом в левой части и конструирование значений в правой порождают новые значения, не меняя существующие. Словари должны вести себя также. Выражение
[Tk Tv d.D]
в роли образца должно искать словарную пару Tk Tv (слева направо) в аргументе и связывать переменную d.D с новым словарём — аргументом за вычетом найденной словарной пары. В роли результата это выражение должно порождать новый словарь, путём объединения словаря из единственной пары Tk Tv и словаря d.D. Аргумент при сопоставлении и словарь d.D при конструировании изменяться не должны.
Дерево допускает эффективную иммутабельную реализацию — при модификации (вставке, удалении) достаточно перестроить путь от корня к искомому листу (плюс возможная перебалансировка) — O(k×log n). где k — размер ключа, n — число элементов. Однако, поскольку ключи в общем случае являются строками, то при спуске по дереву можно отслеживать общий префикс верхней и нижней границы и их уже не сравнивать, что даёт сложность O(k + log n). Для иллюстрации: если вы ищете в орфографическом словаре слово «сельдь», страница начинается на слово «себялюбие» и заканчивается на «семиотика» [1, стр. 149], то вчитываться в первые две буквы не обязательно.
Поскольку данные Рефала суть строки с правильно расставленными скобками, можно использовать сжатый бор (луч, trie), сложность поиска/вставки/замены/удаления в котором тоже будет O(k×n′) или O(k×log n′), где k — размер ключа, n′ — среднее число дочерних ветвей. Вообще, в учебниках пишут, сложность поиска в боре O(k×m), где m — размер алфавита (который обычно фиксирован), но в данном случае алфавитом будут все возможные символы Рефала, и дочерние подветви при большом их количестве придётся искать двоичным поиском или даже организовывать вспомогательное двоичное дерево. В худшем случае, ключами могут быть, например, символы-числа и бор будет вырожденным.
Хеш-таблица подразумевает использование массива корзин, индексы в котором вычисляются при помощи хеш-функции. Наивная реализация должна будет копировать массив при каждой модификации, из-за чего сложность составит O(n). Использование реализации неизменяемого массива как дерева приведёт к тому, что сложность индексации и модификации этого массива станет логарифмической, соответственно, сложность будет O(k + log n), т.к. просмотр ключа потребуется один раз при вычислении хеш-функции и фиксированное количество раз при поиске в корзине.
В случае хеш-таблицы для эффективного поиска нужно иметь полностью определённый образец, для дерева или бора достаточно иметь префикс (если реализация просматривает ключи слева направо). Для примера отображения имён на очки образец
[('Вер' e.Suf) s.Score d.ScoresTable]
эффективно найдёт ключ ('Вера'), ('Вероника') или ('Вервольф').
Простая реализация может представлять словарь как несортированную последовательность пар, сложность всех операций будет та же, что и у ассоциативного списка. Преимуществом может быть, разве что, удобство использования.
Можно использовать отсортированную последовательность пар в виде «верёвки» (rope) или «пальцевого дерева» (finger tree, «гирляндное дерево»), сложность будет та же, что и у дерева поиска. Ведь, фактически, это дерево и будет. Этот вариант будет оправдан, если верёвка или пальцевое дерево используется также и для представления объектных выражений (такие реализации мне неизвестны).
Сложность объединения словарей [d.1 d.2] во всех перечисленных случаях будет O(n₁ + n₂), если размеры примерно равны, если же один словарь намного больше другого, скажем n₁ >> n₂, то сложность будет O(n₂×log n₁), т.к. может оказаться более эффективным поэлементная вставка пар меньшего словаря в больший, чем использование общего алгоритма объединения (граница между случаями определяется экспериментально).
Можете предлагать свои варианты эффективной реализации.
Выводы. Во-первых, мы описали, как можно органично расширить Рефал для поддержки мультисловарей.
Во-вторых, мы сделали это, опираясь на практику программирования на Рефале — идиому ассоциативного поиска. Выше были перечислены четыре её особенности, имеет смысл их сравнить:
- Точно также, как и ассоциативный список, словарь — мультисловарь, сохраняющий относительный порядок равных ключей.
- Быстродействие в удачных случаях (ключ определён полностью или в некоторых реализациях частично) O(k×log n) или O(k + log n), в неудачных случаях (поиск по значению, поиск ключа по шаблону) — O(n), как и для ассоциативного списка.
- В отличие от идиомы, два компонента словарной пары — два терма, формат придумывать не надо. Но поиск будет эффективен только по первому компоненту.
- Очевидно, нет проблемы с потерей половинки словаря, т.к. половинок нет.
Осталось сделать реализацию, хотя бы, модельную. Возможно, сам когда-нибудь сделаю или дам студентам на курсовую/диплом. Не буду возражать, если это воплотит кто-то другой в своей реализации Рефала.
Список литературы
- Ушаков Д.Н. Крючков С.Е. Орфографический словарь для учащихся средней школы. М.: Просвещение, 1975, — ≥222 с. /* в конце вырвано несколько страниц */
С уважением,
Александр Коновалов
Sergei Skorobogatov s.yu.skorobogatov_AT_gmail.com
В качестве индекса можно использовать любую реализацию неизменяемого ассоциативного массива. Для эффективности можно ещё как-то ограничить вид "ключей" -- например, будет разумно строить индекс только в том случае, если в ключах отсутствуют вложенные круглые скобки.
Александр Коновалов a.v.konovalov87_AT_mail.ru
Доброе утро, Сергей Юрьевич!
«На мой взгляд, существенное усложнение семантики языка ради эффективной реализации частной задачи поиска в словаре — не очень хорошая идея»
Ряд промышленных языков (Perl, Python, Go) поддерживают ассоциативные массивы на уровне синтаксиса, в ряде языков (JavaScript, PHP, Lua) встроенные массивы уже ассоциативные (целочисленные ключи — частный случай применения), стандартные библиотеки многих ЯВУ предоставляют типы ассоциативных массивов. Так что задача не такая уж и частная.
Но то, что усложнение семантики существенное — согласен.
«Особенно жалко тратить на неё квадратные скобки :-)»
Сергей Юрьевич, как обычно, бережёт квадратные скобки непонятно для какой великой цели. Я, кстати, не писал, что нужно использовать именно квадратные скобки, я писал
«…и новыми скобками (пусть будут квадратными)»
имея ввиду, что для иллюстрации я буду использовать именно их. Вариантов синтаксиса для ассоциативных массивов можно придумать много:
%( … )
${ … }
(/ … )
$dict ( … ) /* или $map ( … ) */
($D … ) /* или ($M … ) */
и ещё до кучи вариантов.
«Что, если к выражениям вида (t.1 t.2) (t.3 t.4) ... (t.M t.N), в которых первые компоненты пар различны, будет сбоку пристёгиваться индекс по этим первым компонентам пар? При этом реализация сопоставления с образцом будет использовать этот индекс для поиска, если он пристёгнут, или сваливаться в обычный поиск, если индекс отсутствует.
… Для эффективности можно ещё как-то ограничить вид „ключей“ — например, будет разумно строить индекс только в том случае, если в ключах отсутствуют вложенные круглые скобки.»
Фактически, предлагается добавить в компилятор/рантайм распознавание и оптимизацию идиомы. У этого подхода я вижу два недостатка:
- Программисты ради высокой производительности будут подстраиваться под эвристики конкретной реализации, что может отрицательно влиять на стиль кодирования (как при боязни копировать переменные в ряде реализаций Рефала). Кроме того, шаг влево, шаг вправо — проблемы. Где-то программист выйдет за рамки допустимого, индекс отбросится и придётся внимательно профилировать, вникая, где косяк. Либо реализация начнёт втыкать работу с индексом там, где он не нужен и тоже получим замедление выполнения.
- Не устраняется недостаток идиомы: ассоциативный список после сопоставления представлен двумя e-переменными, соответственно, префиксом и суффиксом искомой словарной пары. Во-первых, не очень естественно, что одна сущность (словарь) представляется двумя переменными. Во-вторых, это может приводить к ошибке потери одной из половин в правой части (встречал такую ошибку в одной крупной программе на Рефале-5).
Впрочем, при желании можно остаться буквально на грани идиомы и нового синтаксиса. Рефал-7 допускает указание направления сопоставления (ключевые слова $L и $R) не только на верхнем уровне, но и в любом скобочном терме. Пример из статьи [1]:
Alpha e.1 'x' e.1 ($R e.3 e.3 e.2) t.X s.Y
Можно в скобочные термы добавлять пометку $D (или $I от слова «index», или $M от «map» и т.д.), говорящую о том, что это индексированный терм, при сопоставлении с образцом индекс надо учитывать, при построении результата — создавать. Ну и в руководстве описать формальные правила, которым содержимое терма должно удовлетворять. Нарушение этих правил — не ошибка, просто индекс работать не будет (т.е. роль у $D примерно такая, как у ключевых слов register и inline в C++ — компилятор их учитывать не обязан). Компилятор в подобных случаях может выдавать предупреждения.
Список литературы:
- Скоробогатов С. Ю., Чеповский А. М. Разработка нового диалекта языка Refal // Информационные технологии. 2006. 9. C. 31–38.
С уважением,
Александр Коновалов
Sergei Skorobogatov s.yu.skorobogatov_AT_gmail.com
Ряд промышленных языков (Perl, Python, Go) поддерживают ассоциативные массивы на уровне синтаксиса, в ряде языков (JavaScript, PHP, Lua) встроенные массивы уже ассоциативные (целочисленные ключи — частный случай применения), стандартные библиотеки многих ЯВУ предоставляют типы ассоциативных массивов. Так что задача не такая уж и частная.
Но то, что усложнение семантики существенное — согласен.
Можно в скобочные термы добавлять пометку $D (или $I от слова «index», или $M от «map» и т.д.), говорящую о том, что это индексированный терм, при сопоставлении с образцом индекс надо учитывать, при построении результата — создавать. Ну и в руководстве описать формальные правила, которым содержимое терма должно удовлетворять. Нарушение этих правил — не ошибка, просто индекс работать не будет (т.е. роль у $D примерно такая, как у ключевых слов register и inline в C++ — компилятор их учитывать не обязан). Компилятор в подобных случаях может выдавать предупреждения.
Стеллецкий Василий sw710_AT_yandex.ru
> "(ну а что касается отдельной конструкции `del M[key]` для удаления словарной пары, то это за гранью добра и зла)"
С уважением,
Sergei Skorobogatov s.yu.skorobogatov_AT_gmail.com
> "(ну а что касается отдельной конструкции `del M[key]` для удаления словарной пары, то это за гранью добра и зла)"Ну почему же? Я этим часто пользуюсь на рефале. Если я знаю, что значения из списка (словарика) мне не понадобятся более одного раза, то после использования я их более в списке не оставляю... wb(ea(wbec)ed)... =... (eaed) ... (ec) ... * ;)
Александр Коновалов a.v.konovalov87_AT_mail.ru
Добрый вечер, Сергей Юрьевич!
«…скажу про Python и Go: это настолько развесистые языки по сравнению с рефалом…»
Если делать Рефал промышленным языком, то он тоже неизбежно станет развесистым. И тогда в него можно будет добавить и синтаксис для ассоциативных массивов тоже.
Рефал-2 был промышленным языком и в нём был, к примеру, выразительный синтаксис спецификаторов переменных. В задачах обработки текста вроде лексического анализа образцы со спецификаторами вполне заменяли регулярные выражения (кстати, регулярные выражения я бы в Рефал добавил). Также в нём были статические и динамические ящики, которых нет в Рефале-5.
Рефал-6 и Рефал Плюс тоже тяготеют к промышленным языкам и тоже в разы развесистее, чем Рефал-5. Перечислять их возможности я тут не буду.
Сравнение из мира Лиспа. Есть язык Scheme R⁵RS, который академический и очень компактный, и он очень неплох для обучения студентов разным интересным концепциям (рекурсия, высший порядок, код как данные, макросы, континуации и т.д.). И есть промышленный язык Racket, основанный на Scheme, и он крайне развесист (есть даже богатое сопоставление с образцом). Графическая IDE для Racket’а — DrRacket написана на Racket’е.
Надо просто понять, что мы хотим от Рефала. Если мы хотим академический язык, то у нас уже есть Рефал-5, на котором можно писать модельные и экспериментальные суперкомпиляторы, лабораторные работы по генерации модельного ассемблера для модельного императивного языка и т.д. Но что-то серьёзное на нём не напишешь. Если хотим промышленный — есть Рефал-2, Рефал-6 и Рефал Плюс.
«…а ограничиться одной конструкцией „generator comprehension“…»
Конечно, конструкции {a for b in c}, {a : b for c in d}, [a for b in c] вполне заменяются на set(a for b in c), dict((a, b) for c in d) и list(a for b in c), так что являются синтаксическим сахаром. Но списковые, словарные и множественные включения отличаются от генераторных включений только другими скобками вокруг (и двоеточием для словарей) и дополняют литералы соответствующих типов. Добавить их реализацию несложно, программистами понимаются легко, на практике позволяют писать код лаконичнее, т.к. списковые включения используются чаще генераторных.
«ну а что касается отдельной конструкции `del M[key]` для удаления словарной пары, то это за гранью добра и зла»
Более того, эта конструкция применима и к спискам — удаляет элемент в i-й позиции, разумеется, с линейной сложностью. Также применима к переменным — удаляет переменную из области видимости. Такая вот дичь.
«А вот это классная идея (если я её правильно понял)!»
Да, Вы всё правильно поняли.
С уважением,
Александр Коновалов
From: Sergei Skorobogatov s.yu.skorobogatov_AT_gmail.com <re...@botik.ru>
Sent: Monday, November 11, 2024 1:23 PM
To: re...@botik.ru
Subject: Re: Синтаксис словарей в Рефале!
Здравствуйте, Александр!
Sergei Skorobogatov s.yu.skorobogatov_AT_gmail.com
Если делать Рефал промышленным языком, то он тоже неизбежно станет развесистым. И тогда в него можно будет добавить и синтаксис для ассоциативных массивов тоже.
Надо просто понять, что мы хотим от Рефала. Если мы хотим академический язык, то у нас уже есть Рефал-5, на котором можно писать модельные и экспериментальные суперкомпиляторы, лабораторные работы по генерации модельного ассемблера для модельного императивного языка и т.д. Но что-то серьёзное на нём не напишешь. Если хотим промышленный — есть Рефал-2, Рефал-6 и Рефал Плюс.
«ну а что касается отдельной конструкции `del M[key]` для удаления словарной пары, то это за гранью добра и зла»
Более того, эта конструкция применима и к спискам — удаляет элемент в i-й позиции, разумеется, с линейной сложностью. Также применима к переменным — удаляет переменную из области видимости. Такая вот дичь.
«А вот это классная идея (если я её правильно понял)!»
Да, Вы всё правильно поняли.
Александр Коновалов a.v.konovalov87_AT_mail.ru
Добрый день, Сергей Юрьевич!
Спасибо за интересную мысль о соотношении «выразительность/сложность». С этого ракурса на Рефал я не смотрел. Хотя в своё время я поставил задачу на существенное упрощение синтаксиса Рефала-5λ:
https://github.com/bmstu-iu9/refal-5-lambda/issues/318
(А потом по ряду причин разработка Рефала-5λ приостановилась.)
«Ну, Рефал-5 имеет много недостатков, и путём минимальных изменений его можно сделать во много раз выразительней, чтобы серьёзные вещи на нём легче писались. Просто нужно стараться соблюдать баланс, чтобы коэффициент „выразительность/сложность“ не уменьшался.»
И стараться избежать проблем в семантике (которые были в Рефале-7). Мы это обсуждали когда-то.
Кстати, на Ваш теперешний взгляд, это какие изменения?
С уважением,
Александр Коновалов
Sergei Skorobogatov s.yu.skorobogatov_AT_gmail.com
Кстати, на Ваш теперешний взгляд, это какие изменения?
Стеллецкий Василий sw710_AT_yandex.ru
Извините, ну какие функции высших порядков для программиста, который "на земле" и пишет программу?
Ему бы чем понятнее - тем лучше! И пишется быстрее, и отладка проще (если вообще понадобится)!
Да, я лет 20 назад смотрел рефал-5, и его не выбрал. В то время в моей версии рефала не хватало ввода-вывода, я посмотрел на рефол-6 (не прижился, написал свой ввод-вывод и успокоился...)
Тут было разграничение рефала на производственные (рефал-2, 6, plus) и академические (рефал-5)...
Возможно Вы правы!
Господа! Ну как реальные программы писать без ящиков? хотя бы статических (я динамическими так и не пользовался)?
Это ж умрешь в скобочной структуре! а отладка? Всё это будет вылезать ...
Конечно, с академической точки зрения, без ящиков можно обойтись... Но это на мой взгляд серьезное усложнение структуры обрабатываемых данных...
С уважением,
Добрый день, Саша!
Sergei Skorobogatov s.yu.skorobogatov_AT_gmail.com
Извините, ну какие функции высших порядков для программиста, который "на земле" и пишет программу?
Господа! Ну как реальные программы писать без ящиков? хотя бы статических (я динамическими так и не пользовался)?
Это ж умрешь в скобочной структуре! а отладка? Всё это будет вылезать ...
Конечно, с академической точки зрения, без ящиков можно обойтись... Но это на мой взгляд серьезное усложнение структуры обрабатываемых данных...
Стеллецкий Василий sw710_AT_yandex.ru
Да, раньше, когда мы под руководством В.Л.Топунова писали на рефале арифметику многочленов, и т.п., о ящиках и не думали...
Здравствуйте, Василий!
Александр Коновалов a.v.konovalov87_AT_mail.ru
Можно, используя условия:
/*
t.Expr ::=
(t.Pos Ident e.Name)
| (t.Pos Const e.Value)
| (t.Pos t.Expr s.BinOp t.Expr)
| …
t.PureExpr ::=
(Ident e.Name)
| (Const e.Value)
| (t.Expr s.BinOp t.Expr) -- намеренно нерекурсивно!
| …
*/
// <Pure t.Expr> == t.PureExpr -- нерекурсивная!
Pure { ... }
SomeParserFunc {
… t.Expr …
, <Pure t.Expr> : (Name e.VarName)
…
}
Немного многословно (есть некоторое количество синтаксического шума), но работать будет. Можно для этой идиомы придумать какой-нибудь синтаксический сахар, в котором будет меньше синтаксического шума — по аналогии с экстракторами в Scala (см. метод unapply). Скажем, как-то так:
SomeParserFunc {
… t.Expr @ <Pure (Name e.VarName)> …
}
Т.е. запись
… VAR @ <EXTR PATTERN> …является сокращённой записью
… VAR …, <EXTR VAR> : PATTERNнеуспех в экстракторе EXTR приводит к неуспеху образца. Если не нравятся угловые скобки в образце, можно использовать квадратные:
… VAR @ [EXTR PATTERN] …Добрый день, Саша!
On Wed, Nov 13, 2024 at 3:41 PM Александр Коновалов a.v.konovalov87_AT_mail.ru <re...@botik.ru> wrote:Кстати, на Ваш теперешний взгляд, это какие изменения?Если мы берём Рефал-5, то изменения такие:1. превращение блоков в функции высших порядков (как в Рефал-7);2. то, что я про себя уже много лет называю "линзы", т.е. некоторый механизм, позволяющий функции видеть не то объектное выражение, которое ей передали в качестве аргумента, а его преобразованный упрощённый вариант, и производить манипуляции с этим упрощённым вариантом, отображаемые на исходное объектное выражение (что-то наподобие views в реляционных базах данных, когда есть настоящие таблицы, а есть производные таблицы, построенные на основе настоящих, и при некоторых условиях запись в эти производные таблицы приводит к обновлению настоящих таблиц);
3. представление Рефал-кода в виде объектных выражений, т.е. возможность ана��иза, преобразования и выполнения Рефал-кода, представленного в виде объектных выражений.Вот как-то так :-)
Александр Коновалов a.v.konovalov87_AT_mail.ru
Стеллецкий Василий sw710_AT_yandex.ru
Вы безусловно правы! Про копилку в рефал-5 я подзабыл.
Конечно, копилка функционально вполне заменяет статические ящики. Только вопрос наглядности и эффективности...
Василий Игоревич и Сергей Юрьевич!
Sergei Skorobogatov s.yu.skorobogatov_AT_gmail.com
То, что Вы называете «линзы», другие называют парой из геттера и сеттера или акцессора и модификатора.
Александр Коновалов a.v.konovalov87_AT_mail.ru
Да, это синтаксический сахар к паре хранимых процедур. Точно также, как свойство — синтаксический сахар к геттеру и сеттеру. И это тоже даёт удобство и гибкость.
From: Sergei Skorobogatov s.yu.skorobogatov_AT_gmail.com <re...@botik.ru>
Sent: Thursday, November 14, 2024 1:03 AM
To: re...@botik.ru
Subject: Re: Синтаксис словарей в Рефале!
On Wed, Nov 13, 2024 at 7:31 PM Александр Коновалов a.v.konovalov87_AT_mail.ru <re...@botik.ru> wrote:
Sergei Skorobogatov s.yu.skorobogatov_AT_gmail.com
Да, это синтаксический сахар к паре хранимых процедур. Точно также, как свойство — синтаксический сахар к геттеру и сеттеру. И это тоже даёт удобство и гибкость.
Arkady Klimov arkady.klimov_AT_gmail.com
Александр Коновалов a.v.konovalov87_AT_mail.ru
перем @ [Геттер образец]
, <Геттер перем> : образец
[Геттер образец]
перем @ [Сеттер результат]
<Сеттер перем результат>
тип.индекс @ [Геттер образец]
[Геттер образец].индекс /* тип описывается в определении геттера */
тип[Геттер образец]индекс
Геттер.индекс @ [образец]
1) [Геттер образец]
2) перем @ [Геттер образец]
(e.Name) e.Table @ [AsIs e.1 (e.Name t.Value) e.2]
= <F e.Table> <G t.Value>;
(e.Name) e.Table
, e.Table : e.1 (e.Name t.Value) e.2
= <F e.Table> <G t.Value>;
Стеллецкий Василий sw710_AT_yandex.ru
[
(e.Name) e.Table @ [AsIs e.1 (e.Name t.Value) e.2]
= <F e.Table> <G t.Value>;(e.Name) e.Table
, e.Table : e.1 (e.Name t.Value) e.2
= <F e.Table> <G t.Value>;Если предлагаемое выражение длиннее уже имеющегося, зачем его вводить?
Извините. за ликбез.
«Геттер и сеттер -- это фиговый синтаксический сахар, потому что вызываемая функция должна знать, что ей передали выражение, к которому нужно применять геттер. А хотелось бы, чтобы ей казалось, что ей передали выражение, к которому уже применили геттер :-)»
Александр Коновалов a.v.konovalov87_AT_mail.ru
$ENTRY Go {
= <Modify <LoadDB 'sales.sqlite'>>
}
Modify {
e.Tables-B (CUSTOMER e.Cust-B (t.Name t.SurName 1234 t.Email) e.Cust-E) e.Tables-E
= <SaveDB
e.Tables-B
(CUSTOMER e.Cust-B (t.Name t.SurName 1234 "us...@test.ru") e.Cust-E)
e.Tables-E
>
}* форсирует SELECT:
Modify {
e.Tables-B (CUSTOMER e.Cust-B (t.Name t.SurName 1234 t.Email) e.Cust-E) e.Tables-E
= <Prout t.Name t.SurName t.Emal>
}
* форсирует DELETE:
Modify {
e.Tables-B (CUSTOMER e.Cust-B (t.Name t.SurName 1234 t.Email) e.Cust-E) e.Tables-E
= <SaveDB e.Tables-B (CUSTOMER e.Cust-B e.Cust-E) e.Tables-E>
}
* форсирует INSERT:
Modify {
e.Tables-B (CUSTOMER e.Customers) e.Tables-E
= <SaveDB
e.Tables-B
(CUSTOMER e.Customers ("Вася" "Пупкин" 2345 "vpoup...@test.ru"))
e.Tables-E
>
}
* форсирует DROP TABLE
Modify {
e.Tables-B (CUSTOMER e.Customers) e.Tables-E
= <SaveDB e.Tables-B e.Tables-E>
}
Александр Коновалов a.v.konovalov87_AT_mail.ru
@ [: …] `. Можно сравнить длину:(e.Name) e.Table @ [: e.1 (e.Name t.Value) e.2] = …
(e.Name) e.Table, e.Table : e.1 (e.Name t.Value) e.2 = …
Sergei Skorobogatov s.yu.skorobogatov_AT_gmail.com
Не представляю синтаксис для этой цели, кроме того, который я приводил выше
* (t.Pos Ident e.Name)
* | (t.Pos Const e.Value)
* | (t.Pos Let)
* | (t.Pos Assign)
* | …
* t.PureToken ::=
* (Ident e.Name)
* | (Const e.Value)
* | Let
* | Assign
* | …
*/
/* Линза преобразует список термов t.Token к списку t.PureToken */
Purify {
(t.Pos Let) e.Rest = Let <Purify e.Rest>;
(t.Pos Assign) e.Rest = Assign <Purify e.Rest>;
...
(t.Pos e.Data) e.Rest = (e.Data) <Purify e.Rest>;
}
/* Демонстрация вызова парсера с применением линзы */
CallParser {
e.Tokens = <Purify | Parse e.Tokens>;
/* Вызов функции с линзой -- единственное расширение синтаксиса */
}
/* Парсер принимает список термов t.PureToken */
Parse {
Let (Ident e.Name) Assign e.Expr
, <IsDeclared e.Name>: T
= ERROR (Ident e.Name) ': redefinition of variable';
/* Если парсер вызвали с линзой Purify, то на выходе
из функции Parse терм (Ident e.Name) преобразуется
обратно в (t.Pos Ident e.Name) */
...
}
Стеллецкий Василий sw710_AT_yandex.ru
Т.е. выгода из-за длины идентификатора Table, а если вместо него использовать T, - то выгоды никакой?
Александр Коновалов a.v.konovalov87_AT_mail.ru
e.1 @ [: e.2 s.X e.3] '+' (e.A s.X e.B) — здесь во внешнем цикле будет удлиняться e.2 , во внутреннем — e.A ,e.1 '+' (e.A s.X e.B), e.1 : e.2 s.X e.3 — здесь во внешнем цикле будет удлиняться e.A , во внутреннем — e.1 (да, на 1 знак длиннее😀)./*
Возврат скобочного терма означает успех извлечения,
любой другой возврат — неудача.
В языках с неуспехами (Рефал-6, -7, Плюс)
можно было бы возвращать неуспех.
*/
Pos {
(Ident t.Pos e.Name) = (t.Pos);
(Let t.Pos) = (t.Pos);
(Const t.Pos e.Value) = (t.Pos);
(Assign t.Pos) = (t.Pos);
…
e.Other = Fail;
}
Ident {
(Ident t.Pos e.Name) = (e.Name);
e.Other = Fail
}
Let {
(Let t.Pos) = ();
e.Other = Fail;
}
…аналогично для других разновидностей токенов…
Parser {
… t.Token @ [Pos t.Pos] …
t.[Let] t.[Ident e.Name] @ [Pos t.Pos] t.[Assign] e.Expr
, <IsDeclared e.Name> : T
= (Error t.Pos 'redefinition of variable');
}
Parser {
… t.Token …, <Pos t.Token> : (t.Pos) …
t.1 t.2 t.3 e.Expr
, <Let t.1> : ()
, <Ident t.2> : (e.Name)
, <Pos t.2> : (t.Pos)
, <Assign t.3> : ()
, <IsDeclared e.Name> : T
= (Error t.Pos 'redefinition of variable');
}Digit {
s.X, '0123456789' : e.1 s.X e.2 = ();
/* я помню про функцию Type, но в Рефале-5 она стрёмная */
s.Other = Fail;
}
NotADigit {
s.[Digit] = Fail;
s.Other = ();
}
Digits {
s.[Digit] e.Digits = <Digits e.Digits>;
/* пусто */ = ();
e.Other = Fail;
}
или так:
Digits {
e.1 s.[NotADigit] e.2 = False;
e.1 (e.2) e.3 = False;
e.1 = ();
}
SearchPhone {
e.1 '+7' e.Phone @ [Digits] s.[NotADigit] e.2 = e.Phone;
e.1 '+7' e.Phone @ [Digits] = e.Phone;
}Стеллецкий Василий sw710_AT_yandex.ru
[
Ну пусть она увидела eL (tK eV) eR [а как она узнала, что это нужный ей tK?], НО ОТКУДА ВЗЯЛИСЬ (t.K1 e.V1) в правой части?
Ой, ребята, извините за ликбез, Но может кому тоже станет яснее...
... Видимо последняя eL это eR...
Александр Коновалов a.v.konovalov87_AT_mail.ru
t.K1 и e.V1 они из «многоточий» в левой части. Я тоже подумал, что вторая eL — опечатка и должно быть eR .Sergei Skorobogatov s.yu.skorobogatov_AT_gmail.com
Сергей Юрьевич, такое совершенно непонятно, как реализовывать, плюс есть неочевидности по семантике (что для смутного наброска приемлемо). Но выглядит красиво.
Александр Коновалов a.v.konovalov87_AT_mail.ru
Parse {
…
Let (Ident e.Name) Assign e.Expr1 Let (Ident e.Name) Assign e.Expr2
= ERROR (Ident e.Name) ': double definition';
…
}(Ident e.Name) соответствует первому вхождению в образец или второму?Sergei Skorobogatov s.yu.skorobogatov_AT_gmail.com
Вопрос по семантике примерно такой: если мы в результатной части линзированной функции написали (Ident e.Name), то это имеется ввиду залинзированный терм из аргумента или совершенно новый независимый терм (который разлинзировать не нужно)? Ведь та же функция Parse может из цепочки термов порождать синтаксическое дерево, в котором буквально присутствует узел (Ident e.Name) без координат, и приписывание координат к нему будет ошибкой.
И второй вопрос, который лучше проиллюстрировать примером:Parse {
…
Let (Ident e.Name) Assign e.Expr1 Let (Ident e.Name) Assign e.Expr2
= ERROR (Ident e.Name) ': double definition';
…
}Вхождение(Ident e.Name)соответствует первому вхождению в образец или второму?
А как эту фичу предполагалось развивать?
Александр Коновалов a.v.konovalov87_AT_mail.ru
«При этом фрагменты образцов в результатных выражениях линзы не могут повторяться и должны сохранять своё взаимное расположение. Другими словами: линза всегда возвращает поддерево того упорядоченного дерева, которое передаётся ей в качестве аргумента. Это приводит к тому, что все термы на выходе линзы имеют ссылки на оригинальные термы, и эти ссылки назначаются тривиальным образом.»
С этого и надо было начинать, это было не очевидно. И, согласен, это жёсткое ограничение.
Я правильно понимаю, что относительный порядок сохраняться должен и в Purify, и в Parse?
/* Линза преобразует список термов t.Token к списку t.PureToken */
Purify {
(t.Pos Let) e.Rest = Let <Purify e.Rest>;
(t.Pos Assign) e.Rest = Assign <Purify e.Rest>;
...
(t.Pos e.Data) e.Rest = (e.Data) <Purify e.Rest>;
}
/* Демонстрация вызова парсера с применением линзы */
CallParser {
e.Tokens = <Purify | Parse e.Tokens>;
/* Вызов функции с линзой -- единственное расширение синтаксиса */
}
/* Парсер принимает список термов
t.PureToken */
Parse {
Let (Ident e.Name) Assign e.Expr
, <IsDeclared e.Name>: T
= ERROR (Ident e.Name) ': redefinition of variable';
/*
Если парсер вызвали с линзой Purify, то на выходе
из функции Parse терм (Ident e.Name) преобразуется
обратно в (t.Pos Ident e.Name) */
...
}
«4.2. Хотелось бы передавать линзам гиперпараметры, управляющие их работой. Как их передавать, в принципе, понятно. Вот так, например: <Purify SkipComments | Parse e.tokens>. Но не совсем понятно, как отделить гиперпараметры от обрабатываемого дерева в реализации линзы — мешает накладываемое ограничение.»
Не понял: SkipComments передаётся в Purify или в Parse?
From: Sergei Skorobogatov s.yu.skorobogatov_AT_gmail.com <re...@botik.ru>
Sent: Thursday, November 14, 2024 7:50 PM
To: re...@botik.ru
Subject: Re: Синтаксис словарей в Рефале!
1. Выбор термов, подвергающихся преобразованию на выходе из "линзированной" функции
Sergei Skorobogatov s.yu.skorobogatov_AT_gmail.com
«При этом фрагменты образцов в результатных выражениях линзы не могут повторяться и должны сохранять своё взаимное расположение. Другими словами: линза всегда возвращает поддерево того упорядоченного дерева, которое передаётся ей в качестве аргумента. Это приводит к тому, что все термы на выходе линзы имеют ссылки на оригинальные термы, и эти ссылки назначаются тривиальным образом.»
С этого и надо было начинать, это было не очевидно. И, согласен, это жёсткое ограничение.
Я правильно понимаю, что относительный порядок сохраняться должен и в Purify, и в Parse?
«4.2. Хотелось бы передавать линзам гиперпараметры, управляющие их работой. Как их передавать, в принципе, понятно. Вот так, например: <Purify SkipComments | Parse e.tokens>. Но не совсем понятно, как отделить гиперпараметры от обрабатываемого дерева в реализации линзы — мешает накладываемое ограничение.»
Не понял: SkipComments передаётся в Purify или в Parse?
Александр Коновалов a.v.konovalov87_AT_mail.ru
Ограничение на функцию Purify, мне кажется, можно сформулировать и так: если в правой части стереть все вызовы функций, то должна получиться подстрока строки токенов образца.
А как компилятор должен отличать — в функции Parse терм получен от линзы (а значит, должен быть восстановлен после выхода из линзы) или создан заново? Если я запишу (Ident 'm_' e.Name) — в этот терм позиция добавится на выходе?
Про гиперпараметры: если линзы добавляются в Рефал-7, то можно пользоваться каррированием — функция Purify получает гиперпараметры и возвращает функцию-линзу. <<Purify SkipComments> | Parse e.tokens>.
Про отношение «выразительность/сложность». Сложность определяется не только длиной БНФ, но и описанием семантики. Семантика линз довольно таки непростая.
From: Sergei Skorobogatov s.yu.skorobogatov_AT_gmail.com <re...@botik.ru>
Sent: Thursday, November 14, 2024 9:19 PM
To: re...@botik.ru
Subject: Re: Синтаксис словарей в Рефале!
On Thu, Nov 14, 2024 at 8:52 PM Александр Коновалов a.v.konovalov87_AT_mail.ru <re...@botik.ru> wrote:
Sergei Skorobogatov s.yu.skorobogatov_AT_gmail.com
Ограничение на функцию Purify, мне кажется, можно сформулировать и так: если в правой части стереть все вызовы функций, то должна получиться подстрока строки токенов образца.
А как компилятор должен отличать — в функции Parse терм получен от линзы (а значит, должен быть восстановлен после выхода из линзы) или создан заново? Если я запишу (Ident 'm_' e.Name) — в этот терм позиция добавится на выходе?
Про гиперпараметры: если линзы добавляются в Рефал-7, то можно пользоваться каррированием — функция Purify получает гиперпараметры и возвращает функцию-линзу. <<Purify SkipComments> | Parse e.tokens>.
Про отношение «выразительность/сложность». Сложность определяется не только длиной БНФ, но и описанием семантики. Семантика линз довольно таки непростая.
Александр Коновалов a.v.konovalov87_AT_mail.ru
«Не совсем так, если только не понимать под подстрокой подмножество символов строки. Правильнее так: если в правой части стереть все вызовы функций, то должна получиться конкатенация подстрок образца, взятых по одному разу в том порядке, в каком они входят в образец.»
Описка: я имел ввиду подпоследовательность. Если вычеркнуть из строки токенов образца некоторые токены и из строки токенов результата все угловые скобки (с именами функций), то должна получиться одинаковая строка. При этом круглые скобки должны вычёркиваться попарно. Как-то так. Но это необходимое условие. Более точное ограничение формулируется в терминах поддеревьев.
«При выполнении линзы к термам, которые она выдаёт наружу, добавляется информация о том, каким исходным термам они соответствуют. Достаточно при этом аннотировать только те термы, которые отличаются от исходных.»
Я так понимаю, что каждая функция должна компилироваться в двух режимах: в режиме линзы, когда она добавляет к термам аннотации, и в режиме линзированной функции (который ещё и общий случай), когда аннотации должны сохраняться (см. следующий абзац). Если функцию не удалось откомпилировать в первом режиме (она не соответствует синтаксическим требованиям, см. предыдущий абзац), то в её описателе добавляется соответствующий флаг и попытка использовать её в роли линзы приводит к аварийному завершению программы.
«Надо только следить, чтобы код, порождённый компилятором для „линзированной“ функции, не потерял аннотации термов.»
Собственно, вопрос в том, когда компилятор должен переносить аннотацию с терма из образца в терм результата.
Из предыдущей беседы я понял так. Аннотация переносится, если терм в одном из результатных предложений аргумента (результате после «=» или результатных выражениях условий) текстуально совпадает с записью терма в одном из образцовых выражений предложения (образца аргумента или образца условия). Если совпадений несколько, то выбирается текстуально самое левое в предложении (?). Тогда, если аннотацию обозначить нижними индексами, получится следующее:
(Ident e.Name)₁ (Ident e.Name)₂ = (Ident e.Name)₁ (Ident e.Name)₁ (Ident e.Name)₁;
(Ident e.NameA)₁ (Ident e.NameB)₂, e.NameA : e.NameB = (Ident e.NameB)₂ (Ident e.NameA)₁;
(Ident e.NameA), e.NameA : e.NameB = (Ident e.NameB); /* вообще не переносится */
«Несомненно. Я бы даже сказал, что такой показатель как сложность языка программирования не определяется каким-то объективным критерием, а является экспертным мнением. Но длина БНФ, на мой взгляд, влияет на экспертное мнение в сторону роста этого показателя, потому что когда мы добавляем новые синтаксические конструкции, возникают вопросы об их сочетании с уже имеющимися синтаксическими конструкциями и друг с другом, и объём документации, необходимой для их реализации в компиляторе и для их использования, в общем случае растёт нелинейно.»
Согласен!
Могу даже привести пример вопросов о взаимном сочетании. В Рефале есть встроенное в язык понятие равенства — два значения равны, если при сопоставлении с образцом их можно сопоставить с равными переменными. С точки зрения математики, две функции равны, если области определения совпадают и они одинаково отображают их на область значений. И при реализации вложенных функций у меня возникали вопросы, как же корректно в свете этих аксиом, определять их равенство, в том числе и с учётом оптимизаций (прогонки и специализации). Мы даже это обсуждали на семинаре в ИПМ РАН. Оказывалось, что имеющаяся реализация прогонки и специализации меняет поведение программ из-за вот этих тонкостей. Не помню, были Вы тогда на этом дистанционном семинаре или нет. В репозитории Рефала-5λ есть заявка с размышлениями о проблеме:
https://github.com/bmstu-iu9/refal-5-lambda/issues/276
https://mazdaywik.github.io/direct-link/2021-05-17-Konovalov-Closures-and-Optimizations-Refal-5-lambda.pdf (слайды доклада)
На мой экспертный😜 взгляд, простой синтаксический сахар не сильно повышает сложность, т.к. для него просто определяется эквивалентное преобразование в другие синтаксические конструкции. А значит, достаточно задокументировать эквивалентные преобразования синтаксического сахара в синтаксическое ядро и определить семантику только для последнего.
Arkady Klimov arkady.klimov_AT_gmail.com
Sergei Skorobogatov s.yu.skorobogatov_AT_gmail.com
«При выполнении линзы к термам, которые она выдаёт наружу, добавляется информация о том, каким исходным термам они соответствуют. Достаточно при этом аннотировать только те термы, которые отличаются от исходных.»
Я так понимаю, что каждая функция должна компилироваться в двух режимах: в режиме линзы, когда она добавляет к термам аннотации, и в режиме линзированной функции (который ещё и общий случай), когда аннотации должны сохраняться (см. следующий абзац). Если функцию не удалось откомпилировать в первом режиме (она не соответствует синтаксическим требованиям, см. предыдущий абзац), то в её описателе добавляется соответствующий флаг и попытка использовать её в роли линзы приводит к аварийному завершению программы.
«Надо только следить, чтобы код, порождённый компилятором для „линзированной“ функции, не потерял аннотации термов.»
Собственно, вопрос в том, когда компилятор должен переносить аннотацию с терма из образца в терм результата.
Александр Коновалов a.v.konovalov87_AT_mail.ru
«А, у вас компилятор заново строит результатное выражение, да? Т.е. если в образце — скобки, и в результатном выражении — скобки, то скобки в результатном выражении будут созданы заново? Тогда тяжело. В принципе, если навострить компилятор брать скобочные термы из образца и вставлять их (или их копию) в результатное выражение, то всё получится автоматически.»
Смотря какой компилятор. Рефал-5λ без оптимизаций в результатной части всё строит заново, кроме переменных (s-переменные, по-моему, копирует всегда, не помню). При компиляции с ключом -OR используется модифицированный алгоритм жадного строкового замощения, по максимуму использующий узлы из аргумента. При этом узлы он может при необходимости переинициализировать, например, превращать скобку в символ или символ в скобку. Если в образце есть (Ident e.Name) и в результате есть (Ident e.Name), то в режиме оптимизации, скорее всего, этот фрагмент аргумента не развалится. Однако, гарантий нет. Например, для предложения
F {
(Ident e.Name1) (Ident e.Name2) = (Ident e.Name1) () (Ident e.Name2);
}
он может выделить куски «(Ident e.Name1) (» и «Ident e.Name2)». Или, хуже того, выделит кусок «(Ident e.Name1) (Ident» и второй «Ident» превратит в «)». Алгоритм жадный ведь. А второй «(Ident» в результате может сделать из узлов «<F», переинициализировав угловую скобку в круглую и ссылку на функцию «F» в идентификатор «Ident».
Рефал-05 для простоты реализации заново аллоцирует всё, кроме t- и e-переменных (я делал замеры, s-переменные дешевле копировать всегда, т.к. перешивание двунаправленного списка накладнее, чем переинициализация узла).
Да, обе реализации используют классическое списковое представление.
Если делать оптимизирующий компилятор с массивным представлением или представлением с подвешенными круглыми скобками, то семантику из предыдущего письма сделать будет проще.
«4.3. Хотелось бы уметь переходить к оригинальным версиям термов в функциях, вызываемых из „линзированной“ функции. Как это сделать красиво, я не придумал.»
Линзирование может быть вложенным. Скажем, для того же лексического анализа первая линза может устранять координаты, вторая — устранять атрибуты, оставляя только теги доменов. Поэтому термы могут быть незалинзированы (если обе линзы его не меняли), залинзированы однократно одной или другой линзой и залинзированы двукратно (от них будет тянуться цепочка длины два).
Я бы предложил использовать встроенную функцию с именем «|»:
<| терм> — разлинзирует однократно,
<|| терм> — двухкратно,
<||| терм> — трёхкратно и т.д.
Разлинзировать можно неограниченное количество раз, т.к. если линзы кончились, терм перестаёт меняться.
Я правильно понял, что если линза трансформировала терм, то на выходе он восстановится, а если удалила, то уже нет?
Кстати, уже в третий раз замечаю, что Вы предпочитаете добавлять к объектным выражениям неявные атрибуты, т.е. невидимые для сопоставления с образцом — выражения, сопоставимые с одноимёнными переменными могут иметь разные атрибуты:
- Функции, приписываемые к идентификаторам в Рефале-7.
- Индексы-словари, приписываемые к подвыражениям для ускорения ассоциативного поиска.
- И здесь незалинзированные термы.
Недостаток неявных атрибутов в том, что выражения, сопоставимые с одноимёнными переменными, могут вести себя по-разному. Это усложняет программирование на языке и затрудняет написание оптимизирующих компиляторов. Программист вынужден учитывать, что где-то могут быть подвешены атрибуты, и писать код так, чтобы компилятор их не потерял. Это напоминает копирование переменных, но если копирование влияет только на эффективность, то потеря атрибутов (в случае функций и, особенно, в случае линз) может менять поведение программы. Учёт атрибутов также усложнит глубокие оптимизации, да и вообще генерацию кода.
From: Sergei Skorobogatov s.yu.skorobogatov_AT_gmail.com <re...@botik.ru>
Sent: Friday, November 15, 2024 12:39 AM
To: re...@botik.ru
Subject: Re: Синтаксис словарей в Рефале!
On Thu, Nov 14, 2024 at 10:56 PM Александр Коновалов a.v.konovalov87_AT_mail.ru <re...@botik.ru> wrote:
Sergei Skorobogatov s.yu.skorobogatov_AT_gmail.com
«А, у вас компилятор заново строит результатное выражение, да? Т.е. если в образце — скобки, и в результатном выражении — скобки, то скобки в результатном выражении будут созданы заново? Тогда тяжело. В принципе, если навострить компилятор брать скобочные термы из образца и вставлять их (или их копию) в результатное выражение, то всё получится автоматически.»
Смотря какой компилятор. <....>
Если делать оптимизирующий компилятор с массивным представлением или представлением с подвешенными круглыми скобками, то семантику из предыдущего письма сделать будет проще.
«4.3. Хотелось бы уметь переходить к оригинальным версиям термов в функциях, вызываемых из „линзированной“ функции. Как это сделать красиво, я не придумал.»
<...>
Я бы предложил использовать встроенную функцию с именем «|»:
<| терм> — разлинзирует однократно,
<|| терм> — двухкратно,
<||| терм> — трёхкратно и т.д.Разлинзировать можно неограниченное количество раз, т.к. если линзы кончились, терм перестаёт меняться.
Я правильно понял, что если линза трансформировала терм, то на выходе он восстановится, а если удалила, то уже нет?
Кстати, уже в третий раз замечаю, что Вы предпочитаете добавлять к объектным выражениям неявные атрибуты, т.е. невидимые для сопоставления с образцом <...>
Недостаток неявных атрибутов в том, что выражения, сопоставимые с одноимёнными переменными, могут вести себя по-разному. Это усложняет программирование на языке и затрудняет написание оптимизирующих компиляторов. Программист вынужден учитывать, что где-то могут быть подвешены атрибуты, и писать код так, чтобы компилятор их не потерял. Это напоминает копирование переменных, но если копирование влияет только на эффективность, то потеря атрибутов (в случае функций и, особенно, в случае линз) может менять поведение программы. Учёт атрибутов также усложнит глубокие оптимизации, да и вообще генерацию кода.
Александр Коновалов a.v.konovalov87_AT_mail.ru
«Ох, бедный парсер :-)
Выглядит неплохо, но на самом деле это получается не встроенная функция, а расширение синтаксиса.»
Снимать одновременно несколько линз одновременно, скорее всего, потребуется редко, поэтому создавать специальный синтаксис для этого неразумно, это верно.
Можно добавить и встроенную функцию <| терм>, в дополнение ко встроенным функциям арифметики: <+ …>, <* …> и т.д. Либо скучная встроенная функция <Unlens терм>.
«Также понятно, что вот я, например, давно перестал писать НА Рефале, потому что понимаю, что на других языках мне работать удобнее. И если выразительность Рефала существенно усилится, я с удовольствием снова на Рефал вернусь :-)»
Существенно усилится вложенными функциями, словарями и линзами? Рефлексией в виде доступа к коду на чтение и запись во время выполнения? Или что-то ещё?
Я долгое время разрабатывал (и, возможно, продолжу) компиляторы Рефала, т.к. их разработка ставит много интересных задач, прежде всего, по эффективной реализации всей этой выразительности. Вне этого я Рефалом почти не пользовался, т.к. нет библиотек и кучу всего базового приходится писать с нуля. Ну и плюс производительность. Ну и я бы не сказал, что код каких-то бытовых задач на Рефале будет компактнее кода на других языках, либо я пишу слишком «рыхло» с длинными именами переменных.
From: Sergei Skorobogatov s.yu.skorobogatov_AT_gmail.com <re...@botik.ru>
Sent: Friday, November 15, 2024 2:56 PM
To: re...@botik.ru
Subject: Re: Синтаксис словарей в Рефале!
On Fri, Nov 15, 2024 at 9:40 AM Александр Коновалов a.v.konovalov87_AT_mail.ru <re...@botik.ru> wrote:
Sergei Skorobogatov s.yu.skorobogatov_AT_gmail.com
«Также понятно, что вот я, например, давно перестал писать НА Рефале, потому что понимаю, что на других языках мне работать удобнее. И если выразительность Рефала существенно усилится, я с удовольствием снова на Рефал вернусь :-)»
Существенно усилится вложенными функциями, словарями и линзами? Рефлексией в виде доступа к коду на чтение и запись во время выполнения? Или что-то ещё?
- не вложенные функции, а функции высших порядков (захват окружения и передача его куда угодно);
- не словари, а разнообразные индексы (там может быть всё что угодно вплоть до суффиксных деревьев);
- не эти примитивные линзы, а настоящая мощная обратимая трансформация данных;
- не рефлексия, а полноценная динамическая генерация кода (квадратные скобки -- это на самом деле кавычки для "кодовых" литералов в программе, поэтому я так их берегу :-) ).
Александр Коновалов a.v.konovalov87_AT_mail.ru
«Если бы в Рефале было всё вышеперечисленное, мне было бы интересно на нём писать, да.»
Вы спеку напишите, а мы реализуем. Это же куча интересных курсовых и ВКР!
«квадратные скобки — это на самом деле кавычки для „кодовых“ литералов в программе, поэтому я так их берегу :-)»
А-а-а, теперь понятно.
From: Sergei Skorobogatov s.yu.skorobogatov_AT_gmail.com <re...@botik.ru>
Sent: Friday, November 15, 2024 11:38 PM
To: re...@botik.ru
Subject: Re: Синтаксис словарей в Рефале!
On Fri, Nov 15, 2024 at 10:52 PM Александр Коновалов a.v.konovalov87_AT_mail.ru <re...@botik.ru> wrote:
Sergei Skorobogatov s.yu.skorobogatov_AT_gmail.com
«Если бы в Рефале было всё вышеперечисленное, мне было бы интересно на нём писать, да.»
Вы спеку напишите, а мы реализуем. Это же куча интересных курсовых и ВКР!