Re: Сравнение веток Рефала

[swi_AT_cnshb . ru]

Уважаемые господа!
Я тоже дочитал...
А тест Аркадия меня подвиг его повторить.
У меня на рефале/2 получилась следующая программа:

a =/0/k/P/k/EX//10000/..

EX /0/eS=eS

   sN eS=k/EX1/('abc'sN)eS.

EX1 (sa eb sN)eS=k/EXc/(eb sN)sa eS.

    (sN)saeS=k/EX1p/k/P1/sN.sa('abc')eS.

EX1p sN sa(e1 sa eb)eS=k/EX1/(eb sN)eS.

EXc w0 sa eA sa eA ee=k/EX1/w0 eA sa eA ee.

    (eb sN)eR=k/EX/k/M1/sN.eR.

 

я старался использовать идентификаторы переменных как на рефале-6...

 

Кстати, ех 10000 у меня прошло, и менее чем за минуту (разница во времени файла результата "компиляции" и результата) см. приложенный файл.

 

25.02.2019, 16:51, "Arkady Klimov arkady.klimov_AT_gmail.com" <refal@botik.ru>:

Я не только дочитал, наконец, но и внес свои правки-дополнения (в раздел по Рефал-6, и чуток по Рефал Плюс), поместив этот замечательный текст в doc-файл, который можно взять по ссылке:

 

https://www.dropbox.com/s/eq4yv9g7atu59d7/CompareRefals.doc?dl=0

 

Я подумал, что хорошо бы моему примеру последовали и "держатели" других диалектов.

Александр, поручаю Вам быть "хозяином" этого файла, можете забрать его и выложить где-то от себя. Мои добавки, помеченные цветом и префиксом "АрК", можете в своем стиле адоптировать.

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

***

Я по ходу решил еще раз почитать документацию-руководство по Рефалу Плюс. У меня сложное отношение к нему, то есть он как-то всегда был сложен для меня. Как я сейчас понял, возможно это из-за специфического описания синтаксиса, содержащего понятия "тропы" и "хвосты". Они очень похожи, и я всегда их путал и не мог привыкнуть различать. Для этого было бы полезно видеть их семантическое различие, чем я не владею. А описание языка такового не предлагает. Остается только "зазубривать" формальные особенности, напрягая свою внутреннюю "нейросеть". Хорошо бы те, кто владеют семантическим пониманием хвостов и троп Рефала Плюс, если таковое существует, его как-то эксплицировали.

***

В руководстве мне встретился интересный пример - задача "о цепочках" (из Вирта), раздел 1.10. Надо породить строку из трех знаков (a, b, c), чтобы в ней не было одинаковых смежных подстрок.

Решение довольно мутное, тем более оно дважды использует $Iter, который я не люблю (вероятно, авторы, хотели именно его иллюстрировать этим примером). И мне захотелось переписать его в более "чистых" терминах. И вот что у меня получилось:

---------------------------------------------------------------------------------------------------------- файл abc.ref

// <EX sN eS> - расширить строку eS влево sN знаками a,b,c,

//                        не допуская повторов смежных подстрок

EX {

   0 eS = eS;

   sN eS , 'abc' : e sX e , sX eS : eR : # vA vA e, <EX <SUB sN 1> eR>;

   };

------------------------------------------------------------------------------------------------------------

Это рефал-6, но думаю, можно по аналогии и на Плюсе написать (может даже и так пройдет).

Функция EX откатная, при успехе выдает продолженную строку, иначе откат. Образец e sX e перебирает три варианта продолжения, образец vA vA e под отрицанием проверяет, что выражение не начинается с двух одинаковых непустых подстрок, дальше идет рекурсивный вызов, все через запятую прозрачно для откатов. 

Назвал функцию заглавными покороче, чтобы в интерактивной моде вызывать:

d:\ref6\TEST>d:\ref6\rix.exe i+abc+*ask -S1000000 -T1000000 -H1000000

#>ex 5

'acaba'

#>ex 10

'bcacbacaba'

#>ex 100

'cacbacabacbabcabacabcbabcacbacabacbabcabacabcacbabcabacbabcacbacabacbabcabacabcacbacabacbabcacbacaba'

#>ex 1000

'acbabcacbacabacbabcbacbcabacbabcacbacabacbabcabacabcbabcabacbabcacbacabacbabcabacabcacbabcabacbabcacbacabacbabcabacabcbabcacbacabacbabcbacbcabacbabcabacabcacbabcabacbabcbacabacbabcabacabcacbabcabacbabcacbacabacbabcabacabcacbabcabacbabcbacabacbabcacbacabacbabcbacabacbcacbacabacbabcacbacabacbcacbabcabacabcacbabcabacbabcbacabacbabcabacabcacbabcabacbabcacbacabacbabcabacabcacbabcabacbabcbacabacbabcacbacabacbabcbacbcabacbabcabacabcacbabcabacbabcbacabacbabcabacabcacbabcabacbabcacbacabacbabcabacabcacbabcabacbabcbacabacbabcacbacabacbabcbacabacbcacbacabacbabcacbacabacbcacbabcabacabcacbabcabacbabcbacabacbabcabacabcacbabcabacbabcacbacabacbabcabacabcacbabcabacbabcbacbcabacbabcabacabcacbabcabacbabcbacabacbabcabacabcacbabcabacbabcacbacabacbabcabacabcacbabcabacbabcbacabacbabcacbacabacbabcbacbcabacbabcabacabcacbabcabacbabcbacabacbabcabacabcacbabcabacbabcacbacabacbabcabacabcacbabcabacbabcbacabacbabcabacabcacbacabacbabcabacabcbabcacbacabacbabcabacabcacbabcabacbabcacbacabacbabcabacabcacbacabacbabcacbacaba'

#>ex 10000

EVAL: *** SYSTEM: Reference counter overflow

The referenced object is: *EX

EVAL: Act Vf Fre Run [n]Step [n]Trc Evl Chg Kil New Inf M W D H cLr Quit>

 

Пришлось задать большой стек S и таблицу элементов Т (по 1000000 элементов, по 16 и 8 байтов соответственно), и 1 ГБ (H Kb) общей памяти, иначе стеки быстро переполнялись. Здесь на каждый следующий элемент строки вводится уровень в стеке из-за возможности откатов. Но все равно на аргументе 10000 сломалось - по переполнению счетчика ссылок на объект *EX (символ функции). По-видимому, каждый уровень стека содержал несколько экземпляров ссылок, а всего в реализации счетчик ссылок не может превысить 2^15. 

 

Хороший тест получился. Показал некоторые пределы реализации.

 

Решение на Рефал Плюс из руководства тоже жадно до стека. Интересно, какие там пределы?

 

На получение строки наибольшей длины (около 6500) ушло чуть меньше секунды. По-видимому, на последней версии Рефала Плюс будет быстрее: либо из-за не копирований eS и eR (благодаря "дыркам"), либо из-за более оптимального отождествления vA vA e: уравнения на длинах должны ограничить удлинение переменной vA только до половины длины аргумента, а в Рефале-6 она тупо продолжает удлиняться до конца аргумента.

 

Надеюсь, было не скучно.

Аркадий

ex10000.rar
Description: application/rar