search

Mazdaywik / Refal-05

Очень минималистичный компилятор Рефала
https://mazdaywik.github.io/Refal-05/
Other
3 stars 2 forks source link

Нагруженные идентификаторы #38

Open Mazdaywik opened 2 years ago

Mazdaywik commented 2 years ago

Проблема

На актуальной реализации Рефала-05 программировать неудобно и часто непросто переносить другие программы (см. https://github.com/Mazdaywik/Refal-05/issues/28). Причина — объявления *$ENUM’ов и *$EENUM’ов.

Причина появления пустых функций — (подразумеваемая) цель разработки, как она была описана в https://github.com/Mazdaywik/Refal-05/issues/33:

Сделать Простой Рефал совместимым с Рефалом-5, эффективным и компилирующимся в Си.

В Простом Рефале пустые функции были (по аналогии с Рефалом-2). Пустые функции допускали простую и эффективную реализацию символических имён при компиляции в язык Си (для сравнения — идентификаторы вида # Имя не выжили, т.к. эффективной реализации в Си не было).

Как и в Простом Рефале и в Рефале-5λ, такая реализация допускала библиотечные функции высшего порядка (например, Map в LibraryEx), это тоже важный для меня критерий. Если функции Map не будет, то мне программировать на Рефале будет грустно.

Простой Рефал предполагался как исследовательский проект — я его делал для себя, чтобы лучше понять Рефал и то, как его компилировать. А для исследовательского прототипа некоторые недостатки входного языка несущественны и вполне терпимы, цель у него другая.

Рефал-05 является точным синтаксическим подмножеством Рефала-5 и почти во всём он совместим с ним семантически. Ряд программ для Рефала-5 (при реализации соответствующих встроенных функций, см. #28), вполне может быть запущен и Рефалом-05, для этого требуется лишь определить пустые функции для используемых идентификаторов.

Требуется лишь определить. На практике оказалось, что для MSCP-A потребовалось определить несколько десятков идентификаторов, я замучался их определять и так и не довёл дело до конца. SCP4 собирать Рефалом-05 я даже не пробовал. Кроме того, в программах на Рефале-5 часто используются функции Implode/Implode_Ext, мне эти функции не нравятся, но факт остаётся фактом. Чтобы запустить некоторые программы, их использующие, в #28 мне пришлось сооружать костыли.

Ради совместимости с Рефалом-05 мне пришлось фреймворк refal-5-framework засорить всеми этими *$EENUM’ами, что, в свете вышеизложенного, уродливо.

Предлагаемое решение

Предлагается вместо функций в роли имён использовать идентификаторы, сравниваемые по текстовому представлению. Их объявлять явным образом не надо (псевдокомментарии *$(E)NUM становятся комментариями и уходят в прошлое), одинаковые имена, записанные в разных единицах трансляции, являются равными.

Примитивнейший способ проверки на равенство — strcmp(), но тут возможны оптимизации (хотя интересно сделать замер и с одним strcmp() тоже).

А как же тогда быть с функциями высшего порядка? А предлагается вместе с идентификатором нести невидимую полезную нагрузку — указатель на одноимённую функцию, видимую из точки построения идентификатора. Пример:

$EXTERN Extern;

$ENTRY Entry {
  /* пусто */
    = Extern /* полезная нагрузка — ссылка на внешнюю функцию */
      Entry /* полезная нагрузка — ссылка на entry-функцию */
      Local /* полезная нагрузка — ссылка на локальную функцию */
      NoPayload /* нет функции NoPayload в области видимости, нет полезной нагрузки */
}

Local { … }

Полезная нагрузка не участвует в сравнении на равенство при сопоставлении с образцом, потому и названа невидимой.

Функция Mu смотрит на полезную нагрузку и вызывает соответствующую функцию. В ненагруженные идентификаторы можно класть либо NULL, либо функцию, которая для любого аргумента выдаёт ошибку невозможности отождествления.

На нагруженный идентификатор — кортеж из имени и опционального указателя — можно посмотреть и с другой стороны, буквально. Фактически, здесь предлагается для неопределённых имён функций (в позициях, кроме после <) неявно генерировать *$ENUM и сравнивать символы-функции не по ссылкам на дескрипторы, а по именам. То есть, рантайм существенно не изменится (изменится только проверка на равенство для одного из типов символов), компилятор вместо выдачи ошибок будет генерировать недостающие пустые функции.

Историческое замечание

Подобная идея была предложена Скоробогатовым, он мне сообщил об этом в личной беседе много лет назад, когда он сам ещё разрабатывал Рефал-7 (в конце 2000-х — в начале 2010-х). В Рефале-7 предлагались именованные вложенные функции. Я спросил:

— А как сравниваются на равенство вложенные функции? — По именам. — А безымянные? — Они вообще ничему не равны, даже сами себе.

Диалог не дословный, но суть передал насколько помню. Данный подход мне не понравился — в те годы Скоробогатов также планировал реализовать специализатор для Рефала-7, а тут с аксиоматикой равенства возникали существенные проблемы (например, что копия значения не равна себе). Вообще, с функциями высшего порядка, их равенством и глубокими трансформациями программ есть много сложностей — см., например, https://github.com/bmstu-iu9/refal-5-lambda/issues/276.

Но здесь описанные проблемы несущественны — цель обеспечить совместимость с Рефалом-5 в практически значимых случаях, а глубокие преобразования для программ на Рефале-05 не планируются.

Возможные оптимизации

Постоянно дёргать strcmp() для проверки на равенство может быть неэффективно (но надо померять!). Поэтому можно предложить следующие оптимизации.

Расширение семантики Mu

Семантику Mu можно приблизить к семантике Рефала-5 — генерировать таблицу из функций текущей единицы трансляции. В этом случае Mu сначала ищет функцию в таблице без учёта нагрузки, а затем, если не нашлось, вызывает нагрузку.

UPD: не нужно, https://github.com/Mazdaywik/Refal-05/issues/38#issuecomment-1253225207.

Пример на несовместимость с Рефалом-5

Не смотря на то, что предложенная семантика стала ещё ближе к Рефалу-5, несовместимость остаётся всё равно. Пусть s.Func содержит имя некоторой entry-функции программы. Тогда <Mu s.Func …> в Рефале-5 вызовет эту функцию, если одноимённого имени не было в точке вызова, а в Рефале-05 — если при создании этого имени в области видимости было либо определение этой функции с $ENTRY, либо объявление с $EXTERN.

* file1.ref
$ENTRY A { = <Prout 'Aaaa!'> }
$EXTERN B;
$EXTERN C;

$ENTRY Get1 { = A B C }
* file2.ref
$EXTERN A;
$ENTRY B { = <Prout 'Bbbb!'> }

$ENTRY Get2 { = A B C }

Обе функции Get1 и Get2 вернут нагруженные идентификаторы A и B, однако только Get1 вернёт C как нагруженный. Get2 вернёт пустой.

* file3.ref

$ENTRY Go { = <Run <Get1>> <Run <Get2>> }

Run {
  s.F e.Fs = <Mu s.F> <Run e.Fs>;
  /* пусто */ = /* пусто */;
}

B { = <Prout 'BbBbB???'> }
$ENTRY C { = <Prout 'Ccccc!'> }

Эта программа на Рефале-5 напечатает

Aaaaa!
BbBbB???
Ccccc!
Aaaaa!
BbBbB???
Ccccc!

В Рефале-05 напечатает

Aaaaa!
Bbbbb!
Cccccc!
Aaaaa!
Bbbbb!

и аварийно упадёт из-за вызова ненагруженного идентификатора. Если же расширить Mu, как предложено выше, то получим

Aaaaa!
BbBbB???
Ccccc!
Aaaaa!
BbBbB???
‹RECOGNITION IMPOSSIBLE›

Преимущества

Недостатки

Альтернативный путь

Чтобы обеспечить семантику Mu Рефала-5 с идентификаторами, можно пожертвовать раздельной трансляцией, как это предложено в https://github.com/bmstu-iu9/refal-5-lambda/issues/324 и https://github.com/bmstu-iu9/refal-5-lambda/issues/197. Однако, это выглядит слишком громоздким для Рефала-05.

Этапы

Mazdaywik commented 2 years ago

Несколько дополнительных замечаний

Неожиданная привязка к невызываемым $EXTERN’ам

Обнаружен ещё один аспект несовместимости Рефала-5 и Рефала-05. Рассмотрим такую программу из единственного исходника:

$EXTERN NotCalled;

$ENTRY Go {
  = <Prout NotCalled>
}

В исходном файле функция NotCalled нигде не вызывается, поэтому Рефал-5 (и Рефал-5λ) объявление $EXTERN для неё проигнорирует. Отсутствие entry-функции NotCalled нигде в программе Рефал-5(λ) не смутит, программа успешно запустится и выполнится.

Но у Рефала-05 будут проблемы. Имя NotCalled окажется нагруженным идентификатором — неявно привяжется к $EXTERN’у. Соответственно, при попытке собрать мы увидим соответствующую ошибку компоновщика языка Си.

Считать это проблемой, требующей решения, мы не будем, будем считать особенностью Рефала-05. Рефал-05 может быть у́же, чем Рефал-5, в частности, не компилировать некоторые корректные программы Рефала-5 — см. следующий раздел.

Сообщение об ошибках на неиспользуемые $EXTERN'ы

Актуальная версия Рефала-05 достаточно строга — она выдаёт ошибки там, где компилятор Рефала-5 должен либо молчать, либо выдавать предупреждения. Это ошибки:

Первая ошибка нас сейчас не интересует, интересует вторая.

Проверка на неиспользуемые функции была добавлена из-за того, что компилятор BCC 5.5.1 выдавал предупреждения на неиспользуемые статические функции, а мне хотелось, чтобы компиляция back end’а всегда проходила гладко. Таким образом, я решил явно запретить во входном файле неиспользуемые локальные функции — это полезно и с точки зрения стиля тоже.

Проверка на неиспользуемые функции была добавлена коммитами cc65ec6b166dbab4c4a6befea2924037b957e435 и 10a94ba51fb5d6b15a875fde07d4bd7241d8fcd6, причём, как следует из сообщения первого коммита:

Во-вторых, сообщает о неиспользуемых $EXTERN’ах. Зачем? А почему бы и нет?

проверка на неиспользуемые объявления была добавлена совершенно произвольно. Технической потребности (в отличие от неиспользуемой функции) у неё не было, она была добавлена из стилистических соображений и простоты реализации (легко реализовать «заодно»).

Проблема может быть в том, что программист, привыкший к Рефалу-5, может удивиться, что на одни $EXTERN’ы компилятор ругается (они действительно никак не используются), а на другие — нет, хотя соответствующие функции нигде не вызываются (но есть одноимённые идентификаторы).

✔ Проблемой это также не является, т.к. язык другой, в нём другие правила, хотя синтаксис и похож.

Семантика Рефала-2?

ЕМНИП, в Рефале-2 используется точно такая же семантика для символов-имён — они сравниваются по именам, но при этом несут с собой указатель на функцию, видимую из точки их создания.

Отличие состоит в том, что в Рефале-2 пустые функции должны создаваться при помощи EMPTY, в предлагаемой редакции Рефала-05 это делать не требуется (компилятор сам определит пустые функции).

Но вообще, надо сверить с документацией и реализацией Рефала-2, память может подводить.

Mazdaywik commented 2 years ago

Всё-таки делать буду. Так от Рефала-05 будет больше пользы.

Mazdaywik commented 1 year ago

Ещё несколько дополнительных замечаний.

Привязка к невызываемым $EXTERN’ам и предупреждения

В комментарии выше (https://github.com/Mazdaywik/Refal-05/issues/38#issuecomment-1250591131) я рассуждал на тему того, что у нас могут быть внешние объявления, которые избыточны в Рефале-5 (т.к. такие функции не вызываются), но при этом учитываются в Рефале-05 (т.к. упоминаются имена-функции-идентификаторы).

Это может удивлять не только программистов. Если для Рефала-5 будут реализованы диагностические инструменты, сообщающие о неиспользуемых $EXTERN’ах (например, предупреждения в Рефале-5λ или во фреймворке), то на такие $EXTERN’ы они тоже будут выдавать диагностику.

Сначала я подумал, что для этого стоит оставить псевдокомментарий *$EXTERN, который и будет использоваться для такого рода ссылок на имена, но потом отказался от этой идеи. Можно даже требовать, чтобы ссылки на вызываемые функции были в директиве $EXTERN, а ссылки на идентификаторы — в псевдокомментарии. (т.е. выдавать синтаксическую ошибку на обратное). Достоинство у неё только одно:

Недостатков больше, причём один из них существенный.

Таким образом, псевдокомментарии для *$EXTERN не нужны.

Все псевдокомментарии — в топку

Так что из соображений минимализма удаляем долой всю поддержку псевдокомментариев.

Семантика Рефала-2

Выше я написал:

ЕМНИП, в Рефале-2 используется точно такая же семантика для символов-имён — они сравниваются по именам, но при этом несут с собой указатель на функцию, видимую из точки их создания.

Я был неправ. Рассмотрим такую программу из трёх модулей:

Листинги кода ```refal2 mod1 START entry GetPtr1 GetPtr1 = /Local/ Local = 'mod1' END ``` ```refal2 mod2 START entry GetPtr2 GetPtr2 = /Local/ Local = 'mod2' END ``` ```refal2 ModTest START extrn GetPtr1,GetPtr2,Proutm entry GO GO = + + + Compare sX sX = sX sY = END ```

(В компиляторе какой-то глюк со вложенными угловыми скобками, поэтому здесь мешанина < … > и k … ..)

Здесь в модулях mod1 и mod2 имеется по локальной функции с именем Local, entry-функции в них возвращают составной символ — имя этой функции. Функция GO распечатывает их и сравнивает на равенство при помощи Compare. Вывод программы говорит сам за себя:

/LOCAL/'mod1'
/LOCAL/'mod2'
'Equal'/LOCAL/('mod1')
'Not equal'/LOCAL/('mod1')/LOCAL/('mod2')
Concretization is executed
Total steps number = 20

Так что семантика Простого Рефала до внедрения # Меток и актуальная семантика Рефала-05 идентичны семантике Рефала-2.

Кстати, в документации нигде не заостряется внимание на семантике равенства составных символов, для авторов руководства это, по-видимому, считается самим собой разумеющимся.

О семантике Mu

Не надо генерировать лишнюю Mu

Выше предлагалось:

Расширение семантики Mu

Семантику Mu можно приблизить к семантике Рефала-5 — генерировать таблицу из функций текущей единицы трансляции. В этом случае Mu сначала ищет функцию в таблице без учёта нагрузки, а затем, если не нашлось, вызывает нагрузку.

Не нужно, т.к. это противоречит минимализму.

Так что не надо её генерировать.

Новая семантика для Mu уже описана! Турчиным!

Она описана в учебнике, в разделе 6.1. Скопирую текст из русского перевода учебника:

Обширная цитата > Модульная структура программ в РЕФАЛе-5 привносит некоторое усложнение в простую идею функции `Mu`. Предположим, функция `Mu` уже применена для того, чтобы определить некоторую функцию `Callmu` в одном модуле, а затем `Callmu` используется как внешняя функция в другом модуле. Может случиться так, что некоторое имя функции используется в обоих модулях для определения различных локальных функций. Какую из этих функций следует тогда вызывать посредством `Mu`? Рассуждая подробнее, рассмотрим следующие два модуля — `Mod1`: > > ```refal5 > * This module is the main module Mod1. > * It uses the function Callmu defined in Mod2. > * It also defines function F > * which has a different definition in Mod2. > $ENTRY Go { = > > > } > $EXTRN Callmu; > F { e.1 = 'Mod1' } > ``` > и `Mod2`: > > ```refal5 > * This auxiliary module is Mod2. It defines > * a simple interpreting function Callmu, > * which uses Mu. It also defines function F > * which is defined differently in Mod1. > $ENTRY Callmu { s.F e.X = ; } > F { e.1 = 'Mod2' } > ``` > > Можно определить две версии метафункции `Mu`: `Mu`-Статическую (`MuS`) и `Mu`-Динамическую (`MuD`). Согласно статическому определению функциональное значение символического имени определяется модулем, где _записана_ функция, использующая `MuS`; в нашем случае этим модулем является `Mod2`. Общее правило таково: когда бы ни появился вызов `MuS`, он может активизировать только функцию, _видимую_ из этой точки (т.е., либо локально определенную, либо входящую в список `$EXTERN`), и вызываемая функция будет функцией, определенной в этой точке. При динамическом определении функциональное значение символического имени определяется во время выполнения, т.е. в главном модуле: в нашем случае это `Mod1`. Пусть выполняется: > > ``` > refgo Mod1+Mod2 > ``` > > Если `Mu` определена статически (как `MuS`), программа выдаст на принтер: > > ``` > Mu: Mod1 > Callmu: Mod2 > ``` > > Если же `Mu` определена динамически (`MuD`), будет напечатано: > > ``` > Mu: Mod1 > Callmu: Mod1 > ```

Таким образом, можно говорить, что предлагаемая семантика функции Mu, является «Mu-Динамической (MuD)», как она описана Турчиным!

Mazdaywik commented 1 year ago

Ещё соображение.

Идентификаторы в кавычках

В Рефале-5 составные символы могут быть записаны как в идентификаторной форме — имя, начинающееся с буквы (или прочерка — недокументировано) и состоящее из букв, цифр, прочерков и минусов, так и в виде составного символа в двойных кавычках. В последнем допустимы вообще любые символы, т.к. можно использовать escape-последовательности.

Актуальная реализация такие составные символы поддерживает, и, если они могут быть записаны в идентификаторной форме и одноимённая функция есть в области видимости, программа скомпилируется:

$ENTRY Go {
  = "Go" "\x47\x6f" /* Go * в hex-кодах */
}

Если в исходной программе будет записан идентификатор в «закавыченной» форме, не представимый в идентификаторной, то для него одноимённой функции заведомо не найдётся — имя функции должно быть в идентификаторной форме.

Реализация настящей задачи предполагает автоматическую генерацию пустых функций для идентификаторов.

Проблема здесь в том, что идентификаторы в «закавыченной» форме нужно будет как-то представлять в исходном тексте программы. Варианты:

Промежуточный вывод: нужно проверить, приводят ли слишком длинные идентификаторы к проблемам с компилятором Си (например, он в длинных именах может учитывать только первые 64 знака) и, если приводят, выбрать вариант с переименованием.

Mazdaywik commented 1 year ago

Был сделан замер производительности в двух вариантах: сравнение по указателю или с использованием strcmp(). Для выбора варианта использовалась условная компиляция:

https://github.com/Mazdaywik/Refal-05/blob/3c02e94031456ea233a42f2b50cdcebba20c05b9/lib/refal05rts.c#L74-L82

В обоих случаях есть накладные затраты на вызов функции equal_functions(), поэтому различия в производительности компилятора демонстрируют только разницу между сравнением указателей и сравнением имён.

Использовался компилятор Borland C++ Compiler 5.5.1:

D:\Mazdaywik\Documents\Refal-05\src>bcc32
Borland C++ 5.5.1 for Win32 Copyright (c) 1993, 2000 Borland

Компиляция осуществлялась без какой-либо оптимизации:

D:\Mazdaywik\Documents\Refal-05\src>set R05CCOMP
R05CCOMP=bcc32 -w

Было выполнено по 15 прогонов (надо было 13 или 17, но перепрогонять уже было неохота) для #if 0 и #if 1:

В качестве медианы брался 8-й замер (очевидно, 15 // 2 == 8), в качестве доверительного интервала — 4-й и 12-й (т.е. 4-й с конца). Это несколько шире, чем квартили.

Общее время работы:

Чистое время сопоставления с образцом:

Время сопоставления с повторными e-переменными в циклах по открытым e-переменным:

Вывод. Достоверного замедления не обнаружено, а то, что выявлено — влияет на производительность ничтожно (0,7 %). Дополнительных оптимизаций производить не требуется.

STrusov commented 1 year ago

Промежуточный вывод: нужно проверить, приводят ли слишком длинные идентификаторы к проблемам с компилятором Си (например, он в длинных именах может учитывать только первые 64 знака) и, если приводят, выбрать вариант с переименованием.

В стандарте языка Си есть требования к длине имени. Из черновика C99:

— 31 significant initial characters in an external identifier (each universal character name specifying a short identifier of 0000FFFF or less is considered 6 characters, each universal character name specifying a short identifier of 00010000 or more is considered 10 characters, and each extended source character is considered the same number of characters as the corresponding universal character name, if any. — 4095 external identifiers in one translation unit

В N2176.pdf (2017-й год) требование не изменилось.

Mazdaywik commented 1 year ago

Я реализовал схему с декорированием, но если это когда-нибудь приведёт к проблемам, буду думать, что делать дальше.

Если я правильно понимаю стандарт, мне больше актуален этот абзац:

63 significant initial characters in an internal identifier or a macro name (each universal character name or extended source character is considered a single character)

Для идентификаторов неявно определяются пустые функции в целевом файле с модификатором static. Если я правильно понимаю стандарт (лень сейчас вникать), то это не внешнее имя.

STrusov commented 1 year ago

Имя макроса (macro name) — это про стадию препроцессора, задаётся директивой #define.

static — идентификаторы с т.н. internal linkage, в стандарте количество значащих символов было определено только для старого ANSI C как 31 (есть по ссылке на MSVC). Стандарт не разделяет транслятор и линкер, но по сути требование выставляет к последнему (внешние символы приходится сохранять в объектном файле, а при внутреннем связывании для любой длины можно хранить хеш).

Из документации по популярным трансляторам:

MSVC: the Microsoft C compiler allows 247 characters in an internal or external identifier name.

GCC: For internal names, all characters are significant. For external names, the number of significant characters are defined by the linker; for almost all targets, all characters are significant.

Microsoft пишет о допустимом количестве символов, а GNU — о значащих, как в стандарте. Для последнего ограничений в количестве не вижу, для препроцессора заявляют, что лишь бы уместилось в память.

Для Clang не нашёл, но они стремятся к совместимости с GCC. Зато попался Sun WorkShop Compiler C 5.0: The first 1,023 characters are significant.

Похоже, если проблемы и возможны, то с очень старыми либо слишком экономными трансляторами.

Mazdaywik commented 1 year ago

Исследовал мой любимый компилятор BCC 5.5.1 2000-го года выпуска:

int a123456789b123456789c123456789d123456789e123456789f123456789g123456789h123456789i123456789j123456789k123456789l123456789m123456789n123456789o123456789p123456789q123456789r123456789s123456789t123456789u123456789v123456789w123456789x123456789y123456789z123456789;

В идентификаторе в исходном файле 26 × 10 = 260 знаков. В объектном файле только 250 — кусочек z123456789 срезался:

image