Mazdaywik / Refal-05

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

Собрать Рефалом-05 (прямо или косвенно) некоторые программы для Рефала-5 #28

Open Mazdaywik opened 6 years ago

Mazdaywik commented 6 years ago

Преамбула

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

Если в программу добавить псевдокомментарии *$ENUM/*$EENUM и дополнительные $EXTERN’ы, то класс допустимых программ можно расширить практически до базисного подмножества Рефала-5 (с исключениями для несовместимого использования Mu). И это всё.

Но у нас есть препроцессор, которым можно преобразовывать программы на полном Рефале-05 к его базисному подмножеству: 5-to-basis. И он умеет сохранять псевдокомментарии. С его помощью можно расширить класс программ, к которым применим Рефал-05.

Задача

Задача состоит в том, чтобы при помощи 5-to-basis и дополнительной разметки псевдокомментариями собрать некоторые сторонние программы, при необходимости расширить набор встроенных функций. Некоторые встроенные функции добавить не получится в принципе, прежде всего, это Implode.

Предлагается перенести следующие программы:

Mazdaywik commented 5 years ago

Обнаружилась программа с функциями Cp и Lenw:

https://groups.google.com/d/msg/refal/Bc429ngDJf4/1LsOCFieBwAJ

Mazdaywik commented 4 years ago

Модульный Рефал использует следующие встроенные функции:

От функции Implode избавиться несложно. Остальные нужно реализовать в Рефале-05.

Mazdaywik commented 4 years ago

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

Зерном является значение текущего времени.

Поэтому, если программа начинается, например, с <Prout <Random 10>>, несколько последовательных запусков (с последовательными значениями текущего времени: t, t+1, t+2…) будут выдавать одинаковое количество случайных чисел (хотя они на разных запусках будут разными) — остаток будет одинаковым.

Mazdaywik commented 4 years ago

Теперь Рефал-05 при компиляции Модульного Рефала жалуется на необъявленные идентификаторы.

Mazdaywik commented 4 years ago

Подавляющее большинство необъявленных функций укрощено предыдущим коммитом — для имён скобок и идентификаторов генерируются функции.

Но есть некоторое количество идентификаторов, явно описанных в нативных вставках:

D:\AKonovalov\Documents\MRefal\Sources\Bin>refal05c MRefal.r5.ref Library refal05rts
*Compiling MRefal.r5.ref:
MRefal.r5.ref:3:1:ERROR: Undefined symbol FreeHandles in function Go
MRefal.r5.ref:3:1:ERROR: Undefined symbol Handles in function Go
MRefal.r5.ref:3:1:ERROR: Undefined symbol Finalizers in function Go
MRefal.r5.ref:8:1:ERROR: Undefined symbol Finalizers in function E4
MRefal.r5.ref:555:1:ERROR: Undefined symbol FreeHandles in function E1Y
MRefal.r5.ref:555:1:ERROR: Undefined symbol Handles in function E1Y
MRefal.r5.ref:563:1:ERROR: Undefined symbol rb in function L2H
MRefal.r5.ref:563:1:ERROR: Undefined symbol wb in function L2H
MRefal.r5.ref:563:1:ERROR: Undefined symbol ab in function L2H
MRefal.r5.ref:569:1:ERROR: Undefined symbol NF in function L2I
MRefal.r5.ref:588:1:ERROR: Undefined symbol FreeHandles in function E22
MRefal.r5.ref:932:1:ERROR: Undefined symbol True in function L3Z
MRefal.r5.ref:932:1:ERROR: Undefined symbol False in function L3Z
MRefal.r5.ref:1567:1:ERROR: Undefined symbol NF in function E3H
MRefal.r5.ref:2076:1:ERROR: Undefined symbol True in function L8I
MRefal.r5.ref:2076:1:ERROR: Undefined symbol False in function L8I
+Linking D:\AKonovalov\Documents\Refal-05\lib/Library.c
+Linking D:\AKonovalov\Documents\Refal-05\lib/refal05rts.c
*** COMPILATION FAILED ***

При этом «системными» являются Finalizers и NF, а «прикладными» все остальные. Для системных можно явно сгенерировать комментарии *$ENUM, а что делать с прикладными — не очень прозрачно.

Есть синтаксис ALIAS для нативного кода:

$NATIVE Refal5 FUNCTION $ENTRY True ALIAS True;

и через него, в частности, объявлены True и False. Можно в дополнение к ALIAS добавить ALIAS-EXTERN или даже просто EXTERN, который будет не только добавлять указанное имя как псевдоним, но и добавлять директиву $EXTERN. Это позволит не только «побороть» True и False (а также, rb, wb и ab), которые объявлены в Library, но и использовать внешние RSL-ки динамической компоновки (через + в командной строке).

Handles и FreeHandles можно убрать, переписав CoreBE.MFileIO.Open. Дамп копилки может потерять наглядность, ну и ладно.

К слову, если развивать совместимость Модульного Рефала с Рефалом-05, то FS-Extent можно подключать как внешнюю RSL-ку — для целевой компиляции в Рефал-05 она будет нормальным исходником на Си, реализующим функции файловой системы.

Mazdaywik commented 4 years ago

Модульный Рефал собрать удалось! Т.е. файл MRefal.r5.ref удалось откомпилировать и собрать Рефалом-05, полученная программа работает точно также, как и классический Рефал-5.

Цели обеспечить поддержку Рефала-05 на back-end’е Модульного Рефала пока не ставится. Хотя можно добавить параметр конфигурации, предписывающий вызывать не refc, а refal05c. Но это, если будет время и настроение и отсутствие настроения для решения других поставленных задач.

Во всяком случае цель собрать Рефалом-05 Модульный Рефал выполнена. На одну галку меньше.

Mazdaywik commented 4 years ago
*Compiling rmcc.ref:
rmcc.ref:231:25:ERROR: function Upper is not declared
rmcc.ref:235:25:ERROR: function Upper is not declared
rmcc.ref:239:40:ERROR: function Upper is not declared
rmcc.ref:337:27:ERROR: function Put is not declared
rmcc.ref:338:15:ERROR: function Put is not declared

Но вместе с Upper имеет смысл ввести и Lower, Ord, Chr, а вместе с Put — Print.

Mazdaywik commented 4 years ago

Функции Ord и Chr уже были, причём были написаны методом копипаста, никакого обобщения обхода узлов не было. Тем же методом копипаста были добавлены Upper и Lower.

RMCC перенести удалось. Потребовались следующие правки:

SSub { s.X s.Y , : { '-' = '-' ; s.Other = ; } }

Они вызываются всего в двух местах. В принципе, можно было бы исправить программу так, чтобы они были уже не нужны. Но я принципиально не менял логику, да и лениво было разбираться.

К слову, нашлась программа, на которой классическая реализация быстрее:

*** Number of Steps = 62314 Elapsed system time: 1.359 seconds Memory allocated = 851968 Bytes

Total program time: 3.219 seconds (100.0 %). (Total refal time): 3.047 seconds (94.7 %). Repeated t-var match time (inside e-loops): 1.502 seconds (46.7 %). Open e-loop time (clear): 1.357 seconds (42.2 %). Builtin time: 0.172 seconds (5.3 %). t- and e-var copy time: 0.172 seconds (5.3 %). Linear pattern time: 0.016 seconds (0.5 %). Step count 67519 Memory used 52961 nodes, 52961 * 16 = 847376 bytes

Т.е. в Рефале-05 медленные циклы по открытым переменным и сопоставления с повторными t-переменными. Первое ожидаемо: язык сборки образцов унаследован от Простого Рефала. А вот повторные переменные реализуются кодом на Си:
https://github.com/Mazdaywik/Refal-05/blob/a908b363ea1cc21c6d96b5d088d01ec9656be4f6/lib/refal05rts.c#L366-L398
Возможно, он написан неэффективно, функции `r05_empty_seq()`, `move_left()`, `equal_nodes()` следовало вручную заинлайнить.

Кстати, компиляция с `bcc32 -O` почти не ускоряет:

Total program time: 3.234 seconds (100.0 %). (Total refal time): 3.062 seconds (94.7 %). Repeated t-var match time (inside e-loops): 1.484 seconds (45.9 %). Open e-loop time (clear): 1.407 seconds (43.5 %). Builtin time: 0.172 seconds (5.3 %). t- and e-var copy time: 0.156 seconds (4.8 %). Linear result time: 0.015 seconds (0.5 %). Step count 67519 Memory used 52961 nodes, 52961 * 16 = 847376 bytes



Но важен сам факт: RMCC работает.
Mazdaywik commented 4 years ago

Генератор случайных программ Немытых (тот, который включён в Рефал-5λ):

D:\…\src\nemytykh-random-program-generator>refal05c random.ref Library refal05rts
*Compiling random.ref:
random.ref:55:14:ERROR: function Rp is not declared
random.ref:55:32:ERROR: function Rp is not declared
random.ref:58:14:ERROR: function Rp is not declared
random.ref:65:26:ERROR: function RandomDigit is not declared
random.ref:68:32:ERROR: function RandomDigit is not declared
random.ref:75:19:ERROR: function Rp is not declared
random.ref:76:47:ERROR: function RandomDigit is not declared
random.ref:164:35:ERROR: function RandomDigit is not declared
random.ref:164:61:ERROR: function RandomDigit is not declared
random.ref:174:2:ERROR: function RandomDigit is not declared
random.ref:195:26:ERROR: function RandomDigit is not declared
random.ref:195:50:ERROR: function RandomDigit is not declared
random.ref:228:45:ERROR: function RandomDigit is not declared
random.ref:229:44:ERROR: function RandomDigit is not declared
random.ref:234:26:ERROR: function RandomDigit is not declared
random.ref:253:34:ERROR: function RandomDigit is not declared
random.ref:257:19:ERROR: function Implode is not declared
random.ref:259:36:ERROR: function RandomDigit is not declared
random.ref:266:10:ERROR: function RandomDigit is not declared
random.ref:266:63:ERROR: function RandomDigit is not declared
random.ref:267:60:ERROR: function RandomDigit is not declared
random.ref:272:8:ERROR: function Implode_Ext is not declared
random.ref:272:27:ERROR: function Explode_Ext is not declared
random.ref:278:16:ERROR: function Rp is not declared
random.ref:279:9:ERROR: function RandomDigit is not declared
random.ref:279:43:ERROR: function Rp is not declared
random.ref:284:15:ERROR: function RandomDigit is not declared
random.ref:343:4:ERROR: function RandomDigit is not declared
random.ref:643:52:ERROR: function Rp is not declared
random.ref:662:55:ERROR: function Rp is not declared
random.ref:701:69:ERROR: function Rp is not declared
random.ref:702:8:ERROR: function Rp is not declared
+Linking D:\Mazdaywik\Documents\Refal-05\lib/Library.c
+Linking D:\Mazdaywik\Documents\Refal-05\lib/refal05rts.c
*** COMPILATION FAILED ***

Функция Implode везде используется с корректным аргументом, поэтому проверку на то, что аргумент начинается с буквы, делать не нужно. В единственном вызове Implode_Ext аргумент тоже является корректным образом идентификатора, поэтому его можно заменить на Implode.

Корректные значения идентификаторов для корректности программы не так важны. Достаточно чтобы функция реализовывала взаимно однозначное отображение строчек символов на символы. Поэтому можно просто написать фальшивую Implode, которая для нового идентификатора выбирает очередной символ из фиксированного пула enum’ов. Если пул исчерпался, то не судьба.

Mazdaywik commented 4 years ago

Возник любопытный момент: программа random.ref вычисляет <Sub …> и сопоставляет его с '-' e.n — это условие является выходом из рекурсии. Но в Рефале-05 вычитание из меньшего большего просто приводит к арифметическому переполнению.

Поэтому предлагается наделить функции Add и Sub умением реагировать на переполнение. Функция Add может вернуть или s.NUMBER, или 1 s.NUMBER. Функция Sub, соответственно, s.NUMBER или '-' s.NUMBER.

Для функции умножения расширять семантику не надо — это неоправданно сложно.

Mazdaywik commented 4 years ago

Удалось перенести генератор случайных программ Немытых. Я его приложу к комментарию (random-ported-to-05.ref.txt).

Правки вполне предсказуемые:

Самое важное: уточнилась семантика Add и Sub, теперь они более совместимы с Рефалом-5.

Mazdaywik commented 4 years ago

Сделал черновую попытку собрать MSCP-A. Предсказуемо потребовалось добавить enum’ы, их набралось около 200. Но выявились и более существенные проблемы.

Есть предложение добавить Implode и Implode_Ext. В Рефале-05 нет идентификаторов. Есть только функции, которые могут быть пустыми. Поэтому обе эти функции будут возвращать новый символ-функцию.

Предлагается следующая семантика. Если образ символа, возвращаемый Implode/Implode_Ext совпадает с именем встроенной функции — возвращается дескриптор встроенной функции. Иначе создаётся новая пустая функция. Два последовательных вызова с одним и тем же именем должны возвращать один и тот же символ. Пользователь должен понимать, что enum’ы, возвращаемые Implode/Implode_Ext, являются локальными (*$ENUM) в какой-то своей области видимости, и поэтому не равны никаким пользовательским функциям с теми же именами.

И это очередное тонкое отличие от Рефала-5. В Рефале-5 можно записать

<Mu <Implode e.Name> e.Arg>

и вызвать функцию с заданными именем. В Рефале-05 предыдущий код будет работать только если e.Name является именем встроенной функции. Очередной аспект общего подмножества: идентификаторы, построенные при помощи Implode/Implode_Ext, вызывать нельзя (за исключением встроенных функций). Но большинство программ, использующих Implode, их, как правило, не вызывают.

Mazdaywik commented 2 years ago

Поддержку Implode/Implode_Ext удалость реализовать естественным образом благодаря реализации #38.

Удалось скомпилировать MSCP-A с исправлением особых ошибок Рефала-05, часть тестов запускаются, часть валятся. Валятся они так:


RECOGNITION IMPOSSIBLE

STEP NUMBER 3416542

PRIMARY ACTIVE EXPRESSION:

<Add '-' 10 10 >
VIEW FIELD:
[FIRST] 
<c-prefal 
 ('test_web_eng\\rsd_test_ABmoved.ref' )
 ((EXTERN )

RECOGNITION IMPOSSIBLE

STEP NUMBER 5446

PRIMARY ACTIVE EXPRESSION:

<Sub '-' 1 1 >
VIEW FIELD:
[FIRST] 
<c-prefal 
 ('test_web_eng\\rsd_test_look.ref' )
 ((EXTERN )

Похоже, что нужно реализовывать знаковую арифметику, как минимум, для функций Add и Sub.

Если удастся запустить все тесты, то нужно будет сравнить быстродействие Рефала-05 с Рефалом-5. @TonitaN, самый медленный тест — test_finiteletter.ref?

TonitaN commented 2 years ago

Из этих да, именно он.

Mazdaywik commented 2 years ago

А у меня как раз


RECOGNITION IMPOSSIBLE

STEP NUMBER 3596212

PRIMARY ACTIVE EXPRESSION:

<Add '-' 10 10 >
VIEW FIELD:
[FIRST] 
<c-prefal 
 ('test_web_eng\\rsd_test_finiteletter.ref' )
 ((EXTERN )
  <TransformIntoRefal 
   <YieldProgramGeneration 
   .<UnfoldMain_check36 
   . ((Format1 
Mazdaywik commented 2 years ago

Окончания теста test_finiteletter.ref я не дождался, но нашёл другой тест, тоже медленный — test_web_eng\test_script00.ref.

D:\Mazdaywik\Documents\MSCP-A5>mscpdo.bat test_web_eng\test_script00.ref

D:\Mazdaywik\Documents\MSCP-A5>refgo prefal+c-prefal+basics+Unfold_SCP+Generalize+Drive+Stack+residual+accessMSCP+AnalyzeFunDef+DiofEqs+WordEquations+WordEqsCases test_web_eng\test_script00.ref  -l1024 -nt -V4 -C4
11
Pretty print of Refal-5 programs encoded in the prefal-output syntax.
Version: 11.10.2016

Your result file is: test_web_eng\rsd_test_script00.ref
*** Number of Steps = 33915028
Elapsed system time: 46.778 seconds

D:\Mazdaywik\Documents\MSCP-A05>mscp-a.exe test_web_eng\test_script00.ref
11
Pretty print of Refal-5 programs encoded in the prefal-output syntax.
Version: 11.10.2016

Your result file is: test_web_eng\rsd_test_script00.ref

Total program time: 47.875 seconds (100.0 %).
(Total refal time): 44.291 seconds (92.5 %).
t- and e-var copy time: 18.077 seconds (37.8 %).
Linear result time: 10.029 seconds (20.9 %).
Linear pattern time: 9.422 seconds (19.7 %).
Open e-loop time (clear): 4.156 seconds (8.7 %).
Builtin time: 3.584 seconds (7.5 %).
Repeated t-var match time (inside e-loops): 1.387 seconds (2.9 %).
Repeated e-var match time (inside e-loops): 0.703 seconds (1.5 %).
Repeated t-var match time (outside e-loops): 0.093 seconds (0.2 %).
Repeated e-var match time (outside e-loops): 0.093 seconds (0.2 %).
Step count 43515217
Memory used 236442 nodes, 236442 * 16 = 3783072 bytes

Первый скомпилирован при помощи crefal’а, т.к. в исходниках очень длинные строки в кодировке UTF-8, компиляция при помощи refc может давать другой результат.

Второй скомпилирован при помощи Рефала-05 (актуальные коммиты https://github.com/Mazdaywik/Refal-05/commit/d5bb60127f816a0f4d65c012f66690623b360a0c и https://github.com/Mazdaywik/refal-5-framework/commit/171a994a1e0070f098f267ec6e65ad4ea5b8a4ed), компилятор языка Си — BCC 5.5.1 без флагов оптимизации (командная строка bcc32 -w -DR05_SHOW_STAT).

Расхождения в числе шагов связаны с тем, что условия и блоки рассахариваются до базисного Рефала. При реализации #35 производительность может измениться как в ту, так и в другую сторону.

Интересно то, что замеры времени почти совпадают:

…
Elapsed system time: 46.778 seconds
…
Total program time: 47.875 seconds (100.0 %).
…

Откомпилировал с созданием профиля (опция -DR05_PROFILER):

Total steps: 43515217
Total time: 48.562 secs
Mean step time: 1.116 us

  1. GetIneqPars                                     6687.000 ms ( 13.77 % +=  13.77 %),    8833530 calls,      0.678 steps
  2. GetIneqPars0                                    4189.000 ms (  8.63 % +=  22.40 %),    4086552 calls,      0.919 steps
  3. SubstituteAux_cont3                             2542.000 ms (  5.23 % +=  27.63 %),    1499573 calls,      1.519 steps
  4. ScreenNegatives_next2                           2131.000 ms (  4.39 % +=  32.02 %),     123459 calls,     15.467 steps
  5. IfInstance_cont                                 2050.000 ms (  4.22 % +=  36.24 %),    1570652 calls,      1.170 steps
  6. EmbeddingPatterns                               1521.000 ms (  3.13 % +=  39.37 %),     624553 calls,      2.182 steps
  7. ScreenNegatives_cont4                           1196.000 ms (  2.46 % +=  41.84 %),      52679 calls,     20.344 steps
  8. SubstituteAux                                   1143.000 ms (  2.35 % +=  44.19 %),    3303394 calls,      0.310 steps
  9. Putout                                          1123.000 ms (  2.31 % +=  46.50 %),      36952 calls,     27.232 steps
 10. SubstituteInNegative                            1059.000 ms (  2.18 % +=  48.68 %),    1120571 calls,      0.847 steps
 11. SubstituteInClashes                             1026.000 ms (  2.11 % +=  50.79 %),    1499490 calls,      0.613 steps
 12. ScreenNegatives_check4                           932.000 ms (  1.92 % +=  52.71 %),     123459 calls,      6.765 steps
 13. IfInstance                                       891.000 ms (  1.83 % +=  54.55 %),    1708989 calls,      0.467 steps
 14. SubSetRel                                        823.000 ms (  1.69 % +=  56.24 %),    1182036 calls,      0.624 steps
 15. ScreenNegatives_next3                            793.000 ms (  1.63 % +=  57.88 %),      40894 calls,     17.376 steps
 16. ClashLeft                                        650.000 ms (  1.34 % +=  59.22 %),      43077 calls,     13.521 steps
 17. EmbeddingPatterns0                               623.000 ms (  1.28 % +=  60.50 %),     584451 calls,      0.955 steps
 18. ClashLeft_cont1                                  581.000 ms (  1.20 % +=  61.69 %),      33596 calls,     15.496 steps
 19. ClashLeft_cont0                                  566.000 ms (  1.17 % +=  62.86 %),      34751 calls,     14.595 steps
 20. ClashLeft_cont                                   564.000 ms (  1.16 % +=  64.02 %),      39450 calls,     12.811 steps
 21. Br                                               530.000 ms (  1.09 % +=  65.11 %),     946774 calls,      0.502 steps
 22. ClashLeft_cont6                                  502.000 ms (  1.03 % +=  66.15 %),      28703 calls,     15.672 steps
 23. ClashLeft_cont9                                  483.000 ms (  0.99 % +=  67.14 %),      28150 calls,     15.375 steps
 24. ClashLeft_cont4                                  474.000 ms (  0.98 % +=  68.12 %),      31350 calls,     13.548 steps
 25. Dg                                               469.000 ms (  0.97 % +=  69.08 %),     939315 calls,      0.447 steps
…

Целиком: __profile-05.txt.


Функции с суффиксом ‹цифра› (вроде GetIneqPars0) образуются при рассахаривании блоков. Функции с суффиксами _cont‹цифра›? и _check‹цифра›? — при рассахаривании условий, _next‹цифра›? — условий при открытых переменных.

Чтобы увидеть результат рассахаривания, нужно собрать рассахариватель из папки src фреймворка и скормить ему исходный файл. Для сборки рассахаривателя нужно в папке src выполнить команду

rlmake -d ..\lib -o desugar.exe main.ref

Затем перенести файл desugar.exe в папку с исходниками суперкомпилятора и выполнить, например,

desugar.exe WordEquations.ref WordEquations-desugar.ref