Re: Вопрос к выпускникам физматшкол или математикам/программистам

[Anton Orlov orlovan_AT_gmail . com]

Чт, 13 мая 2021 г. в 08:04, Sergei M. Abramov abram_AT_botik.ru <
refal@botik.ru>:

>
> PS.  А почему 42? ;-)  Два раза "очко"...


Любое конкретное число лучше, чем N -- когда дети видят, что сумма каких-то
чисел равна букве, они пугаются и не могут решать задачку.

А кто какие константы любит -- это тоже интересная тема для исследования.
Как Сосинский со своим "возьмём произвольное число, например 17".

Число 42 стало знаменитым вслед за книжкой Дугласа Адамса "Автостопом по
Галактике".  Там его выдал специально построенный компьютер в качестве
ответа на "главный вопрос жизни, Вселенной и всего остального" (после чего
пришлось строить ещё более мощный  компьютер, чтобы узнать, на какой же
всё-таки вопрос это ответ, и этот компьютер -- Земля).

Антон

Re: Вопрос к выпускникам физматшкол или математикам/программистам

[Anton Orlov orlovan_AT_gmail . com]

Добрый день!

Мне показалось, что задачки примерно одинаковые по сложности (над обоими
пришлось сосредоточенно поразмышлять минуту-две).

Не смотрел видео, но вижу в заголовке "профессора не справились" -- видимо,
речь про вторую задачку, и это меня не удивляет.
Мне она напомнила другую задачку, про которую тоже утверждалось, что
академик в здравом уме решить её не в состоянии, при этом дети, не
испорченные ещё всякими иррациональностями, решают её на ура (это я сам
наблюдал):

Есть таблица, в которой написаны числа. Сумма чисел в каждой строке равна
42. И сумма чисел в каждом столбце тоже равна 42. Надо доказать, что
таблица квадратная.

Антон

On Tue, May 11, 2021 at 2:22 PM Sergei M. Abramov abram_AT_botik.ru <
refal@botik.ru> wrote:

> Не бейте сильно за офф-топик!
>
> https://www.facebook.com/sergei.abramov.96/posts/10225409374317673
>
> Вопрос к выпускникам физматшкол или математикам/программистам
>
> Вот внизу есть две задачи.  И еще ссылка на видео про историю этих
> задач (просьба поставить на паузу в 6:30).
>
> Автор ролика (да и я сам) интересуется, для какой доли выпускников
> физматшкол (или просто математиков, программистов) первая задача проще
> второй задачи.
>
> Буду благодарен за Ваши мысли и репосты (для более широкого опроса).
> Мне история (про чаепитье академиков с этой парой задач) показалась
> удивительной.
>
> PS.  В видео есть мой комментарий на эту тему...  Но его стоит читать
> когда для Вас все закончится ;-)
>
> ==
>
> Задача 1.  Придумайте непрерывную функцию, которая была бы определена
> на всей действительной оси, принимала рациональные значения в
> рациональных точках, иррациональные значения в иррациональных точках,
> и при этом не являлась бы линейной ни на каком промежутке.
>
> Задача 2.  Шоколадка имеет размер 6×10 клеток.  За один ход
> разрешается разломать один из уже имеющихся кусков на два по
> какой-нибудь ложбинке.  За какое наименьшее число ходов можно разбить
> всю шоколадку на единичные клетки?
>
> https://youtu.be/GyruSwKAro0
>
> С уважением,
>
> Абрамов С.М.
> ab...@botik.ru
> мобильный: +7(903)2928308
>
>

Re: Список всех простых чисел

[Anton Orlov orlovan_AT_gmail . com]

Добрый день!

Прошу прощения, продолжу оффтоп про Хаскель.

Два небольших соображения:

1) primesA сильно быстрее, чем primesE, за счёт прыжков до следующего
квадрата. Если это реализовать для primesE, то разница в производительности
между ними уже не такая драматическая:

primesE2 = sieve [2..] 4 primesE2
where sieve (n:ns) lim ~ps@(p1:p2:ps3)
| n < lim   = n : sieve ns lim ps
| otherwise = sieve (filter ((/=0).(`mod`p1)) ns) (p2*p2)
(p2:ps3)

(Пришлось поизворачиваться, чтобы раскрутиться)

*Main> primesA!!16000
176087
(0.16 secs, 168,810,848 bytes)
*Main> primesE2!!16000
176087
(0.33 secs, 169,225,768 bytes)

2) Решето Эратосфена -- оно же не про делимость, а про вычёркивание с
определённым шагом. Эффективная запись этого на Хаскеле выглядит так:

primes = 2 : 3 : Data.List.Ordered.minus [5,7..]
(Data.List.Ordered.unionAll [[p*p, p*p+2*p..] | p <- tail primes])

*Main> primes!!16000
176087
(0.03 secs, 54,413,416 bytes)

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

Эта unionAll -- довольно хитрая штука. Я подсмотрел определение primes выше
вот на этой страничке: https://wiki.haskell.org/Prime_numbers
Там эффективная реализация решета выводится последовательно, и можно
понять, что происходит.

С наивной реализацией unionAll всё, конечно, гораздо хуже:

minus l@(l1:ls) r@(r1:rs)
  | l1 < r1   = l1:(minus ls r)
  | l1 > r1   = minus l rs
  | otherwise = minus ls rs

unionAll ((l1:ls):xs) = l1 : (unionAll $ f ls xs)
  where f l@(l1:ls) ((r@(r1:rs)):xs)
  | l1 < r1   = l:r:xs
  | otherwise = r:(f l xs)

primes = 2 : 3 : minus [5,7..] (unionAll [[p*p, p*p+2*p..] | p <- tail
primes])

*Main> primes!!16000
176087
(0.75 secs, 642,165,016 bytes)

Антон

On Thu, Oct 10, 2019 at 1:52 PM Sergei M. Abramov abram_AT_botik.ru <
refal@botik.ru> wrote:

> > Мог ошибиться в границах, но смысл должен быть понятен: каждая
> > следующая граница (lim) получается из предыдущей примерно
> > возведением в квадрат, так ведь?
>
> Так, так, именно!
>
> > Поколение - то, что выходит после очередной фильтрации как кусок
> > списка простых и служит сомножителями в следующем pp.  Меня
> > интересует сколько (какую долю) отсеивает каждая следующая
> > фильтрация.  Понятно, что сначала это 1/2, далее 1-(2/3)*(4/5),
> > далее 1-(6/7)*(10/11)*...*(22/23) и т.д.  Произведение - это доля
> > остающихся.  Просто хотел бы увидеть десятичные числа, как они
> > меняются, наверно, убывают к 0.  Насколько быстро?
>
> Алик, я думаю, мое второе письмо (про bs) отвечает на этот вопрос.
> Хотя и не напрямую.
>
> >> Интересно, для Хаскела это тоже актуально, или там умножение pp*n
> ленивое?
> >
> >  Ленивое, несомненно.
>
> > Неужели?
>
> Ну да.  Пока кому-то не понадобиться это значение...
>
> > Значит на Хаскеле будет автоматически накапливаться в форме терма
> 7*11*13*..., да?
>
> Да.  А понадобиться это только, когда действительно случится
> прохождение через lim и начнется первый gcd с накопленным, но не
> посчитанным, произведением.  Вот там случится need результата.
>
> Все жадные операции перечислены в Haskell-е.  И я не вижу среди них
> умножения, тем более Integer.
>
> Всего доброго,
>
> Сергей Абрамов
>
>

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

[Anton Orlov orlovan_AT_gmail . com]

On Fri, Mar 1, 2019 at 4:08 AM Sergei M. Abramov abram_AT_botik.ru <
refal@botik.ru> wrote:

> День добрый, Антон, Юра!
>
> Я там как-то невнимательно следил.
>
> 1.  Р+ с $iter должен быт лучше (не хуже) чем рекурсия.  Но не сильно
> (хвостовая рекурсия мало уступает $iter).
>

$iter не хуже, чем хвостовая рекурсия. Но, конечно, может быть хуже, если
пытаться выразить не хвостовую рекурсию и эмулировать стек на
рефал-выражениях, например.

Вообще, на мой взгляд, $iter оправдан по двум причинам:
1) Ситуации, когда рекурсия по сути хвостовая, но не является таковой из-за
смежных конкатенаций: (e1 )
2) Отсутствие вложенных функций/замыканий. Выносить каждый простой
внутренний цикл во внешнюю функцию (передавая туда все нужные локальные
переменные) -- слишком тяжеловесно.


> 2.  Р+ с рекурсией не должен жрать стек (точнее, жрать и освобождать
> сразу, так как хвостовая).
>
> Так и есть?  А если не так, то поясните, плз.
>

Так и есть.

Антон


>
> Всего доброго,
>
> Сергей Абрамов
>
>

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

[Anton Orlov orlovan_AT_gmail . com]

On Fri, Mar 1, 2019 at 8:57 AM Arkady Klimov arkady.klimov_AT_gmail.com <
refal@botik.ru> wrote:

> Чтобы понять, лучше ли iter чем рекурсия, я переделал последний вариант
> EX1 (хотя рекурсия там тоже не настоящая, хвостовая) через $iter. Антон или
> Юра, сможете пропустить? А то я пока не умею этого.
> Правда, вряд ли заметно ускорится, поскольку основное время здесь,
> по-видимому, уходит все-таки на образец vA vA e.
>
> // Result () indicates that such string does not exist
>  // Iter variable sP : { T - expression eS is ok; F - eS must be rebuild;
> U - unknown }
>  $func EX2 s = e;
>  EX2  sN, T sN /* empty */ $Iter { sP eS : {
>   T e= U  'a' eS;
>   U vA vA e  = F sN eS;
>   U e= T sN eS;
>   F sa es, 'abc' : e sa sb e = U sN sb es;
>   F sc es= F  es;
>   }} :: sP sN eS, sP sN eS : \{ T 0 e = eS; F s = (); };
>
> Чтобы выразить все через единый цикл, пришлось ввести три состояния sP,
> которые характеризуют имеющуюся информацию о допустимости текущей строки:
> T - допустима, U - неизвестно, F - недопустима или все продолжения
> оказались недопустимыми.
>

Код правильный. Внешние фигурные скобки можно опустить.
Этот вариант быстрее:
MeanStd.Dev.Min Median  Max
real0.415   0.006   0.406   0.415   0.429

EX1 (хвостовая рекурсия):
MeanStd.Dev.Min Median  Max
real0.617   0.005   0.609   0.617   0.625

Вызовы функций съедают всё же прилично.

Антон


> Конечно, нет уверенности, что написано правильно и без ошибок. Для
> "отладки" я пропустил аналогичный вариант на р6, где вместо $iter
> вспомогательная функция XX:
>
>   EX3 sN = ;
>   XX {
>  T  0 eS= eS;
>  T sN eS   =  'a' eS>;
>  U sN vA vA eS = ;
>  U sN eS   = ;
>  F sN sa es, 'abc' : e sa sb e = ;
>  F sN sc es=  es>;
>  F sN= ();
>  };
>
> Он работает примерно как и EX1 раньше. 1 - 1 сек, 10 - 94 сек на
> свежезагруженном интерпретаторе. По мере тасования памяти скорость падает
> до 2 раз.
>
> Аркадий
>
>
>
>
> пт, 1 мар. 2019 г. в 12:08, Sergei M. Abramov abram_AT_botik.ru <
> refal@botik.ru>:
>
>> День добрый, Антон, Юра!
>>
>> Я там как-то невнимательно следил.
>>
>> 1.  Р+ с $iter должен быт лучше (не хуже) чем рекурсия.  Но не сильно
>> (хвостовая рекурсия мало уступает $iter).
>>
>> 2.  Р+ с рекурсией не должен жрать стек (точнее, жрать и освобождать
>> сразу, так как хвостовая).
>>
>> Так и есть?  А если не так, то поясните, плз.
>>
>> Всего доброго,
>>
>> Сергей Абрамов
>>
>>
>
> --
> ___
> *С уважением, *
> *Аркадий Климов,*
> *с.н.с. ИППМ РАН,*
> *+7(499)135-32-95*
> *+7(916)072-81-48*
>

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

[Anton Orlov orlovan_AT_gmail . com]

On Tue, Feb 26, 2019 at 5:41 AM Yuri Klimov yuri_AT_klimov.net <
refal@botik.ru> wrote:

> Добрый день!
>
> Пример Аркадия на Рефал+:
>
> $func? EX sN eS = eS;
> EX \{
>   0 eS = eS;
>   sN eS , 'abc' : e sX e , sX eS :: eR, # \{ eR : vA vA e; },  1> eR>;
> };
>
> Я ошибся. По умолчанию в компиляторе были выключены оптимизации и включен
> режим отладки. Теперь время около 0.62 секунд.
>
> Пример с двумя iter из документации в приложении. Требует heap'а чуть
> поменьше (1ГБ против 2ГБ). Считает 10.5 секунд.
>

Это, кстати, очень интересно, потому что пример с двумя $iter делает по
сути всё то же самое (только выражение растит в другую сторону).
И такая разница во времени получается из-за накладных расходов на вызовы
функций (самой Unacceptable и селекторов -- Middle, Right). Хотя они и не
копируют выражения, но надо поместить аргументы на стек, вызвать, убрать со
стека, привести длинный Int к обычному (в аргументе) и т.п. -- всё это
действия, которые отсутствуют при сопоставлении eR : vA vA e.

Антон



>
> Второй пример Аркадия на Рефал+ считает без heap'а за около 0.76 секунд:
>
> $func EX1 sN eS = eS;
> EX1 sN eS, sN eS : {
>   sN vA vA e = ;
>   0 e = eS;
>   sN e =  'a' eS>;
> };
>
> $func Next sN eS = eS;
> Next {
>   sN = ();
>   sN sX eS = {
> 'abc' : e sX sY e = ;
> =  eS>;
>   };
> };
>
>
> С уважением,
>  Юрий Климов
>
> P.S. Во втором примере ошибка:
>
>> EX1 sN eS : {
>> // Goal!
>>0 e = eS;
>> // eS is unacceptable
>>sN vA vA e = ; // tail recursion, eS is not empty
>> (otherwise previous sentence works)
>> ...
>
> Надо эти два случая переставить местами, а то иначе последних (самый левый
> в строке) символ не проверяется на повторы.
>
> On Tue, 26 Feb 2019 at 09:29, Sergei M. Abramov abram_AT_botik.ru <
> refal@botik.ru> wrote:
>
>> День добрый,
>>
>> > Запустил исходный пример Аркадия на Рефале+ (с компиляцией C++).
>> > Heap пришлось увеличить до 2GB. Время - 2.05 секунды.
>>
>> Юра, сделайте с двумя $iter-ами, пожалуйста.  Хочется и на текст
>> полюбоваться, и на прогон.
>>
>> Под руками системы нет, а в сухую (без воды в бассейне) и облажаться
>> могу...
>>
>> Всего доброго,
>>
>> Сергей Абрамов
>>
>>

Re: Re[4]: Немного статистики

[Anton Orlov orlovan_AT_gmail . com]

On Fri, Feb 22, 2019 at 6:38 AM Arkady Klimov arkady.klimov_AT_gmail.com <
refal@botik.ru> wrote:

> Антон, спасибо,
> я тоже решил на этом коде немного поупражняться в чтении и понимании
> Рефала-Плюс, что дается мне нелегко. Вроде все разобрал, но при этом мне
> показалось, что тут есть ошибка (в смысле, что результат не лучший). А
> именно, что будет в результате
> 
> ?
>
Я бы ожидал результат (VVAR), но тут  вроде получится (EVAR). Корректно,
> конечно, но обобщение не лучшее (не самое тесное).
>

Аркадий, да Вы правы. Основной смысл этой операции был в том, чтобы не
склеивать выражения там, где не нужно (по выходу из блока). Обобщение
(EVAR)...(EVAR) я либо оставил на потом и забыл, либо не стал делать из
каких-то ещё соображений (но сейчас, даже подумав некоторое время, не смог
сообразить, из каких).

Антон

P.S. Юра Климов восстановил доступ к сайту с исходниками. Например,
обсуждаемый код здесь:
http://trac.botik.ru/refal/browser/to-imperative/trunk/compiler/refal/org/refal/plus/compiler/rfp_format.rf


Или я что-то не понимаю в этом коде?
> Или такого входа быть не может? Например, если комбинации e t e заранее
> заменяются на v?
> Аркадий
>
>
>
>>
>> *From:* Anton Orlov orlovan_AT_gmail.com 
>> *Sent:* Friday, February 22, 2019 9:43 AM
>> *To:* refal@botik.ru
>> *Cc**:* Александр Гусев 
>> *Subject:* Re: Re[4]: Немного статистики
>>
>>
>>
>> Александр,
>>
>>
>>
>> Я, пожалуй, просто вставлю сюда код :)
>>
>> Он не самодостаточен, но алгоритм из него читаем.
>>
>> */**
>>
>> * * MSG-Exprs (e.Format1) e.Format2*
>>
>> * * Return e.Format3 -- most specific generalizing of formats 1 and 2.*
>>
>> * */*
>>
>> *MSG_Exprs* {
>>
>>   ((*FAIL*)) *e*.Fe2 = *e*.Fe2;
>>
>>   (*e*.Fe1) (*FAIL*) = *e*.Fe1;
>>
>>   (*t*.Ft1 *e*.Fe1) *t*.Ft2 *e*.Fe2 \*?*
>>
>> */**
>>
>> * * IF both t.Ft1 and t.Ft2 are hard terms and aren't $const'ants then*
>>
>> * * split them out with MSG-Terms.*
>>
>> * */*
>>
>> {
>>
>>   *t*.Ft1 : \{ (*EVAR*); (*VVAR*); (*CONST* *e*); } \*!* *$fail*;
>>
>>   *t*.Ft2 : \{ (*EVAR*); (*VVAR*); (*CONST* *e*); } \*!* *$fail*;
>>
>>   <*MSG_Terms* *t*.Ft1 *t*.Ft2> <*MSG_Exprs* (*e*.Fe1) *e*.Fe2>;
>>
>> };
>>
>>   (*e*.Fe1 *t*.Ft1) *e*.Fe2 *t*.Ft2 \*?*
>>
>> */**
>>
>> * * IF both t.Ft1 and t.Ft2 are hard terms and aren't $const'ants then*
>>
>> * * split them out with MSG-Terms.*
>>
>> * */*
>>
>> {
>>
>>   *t*.Ft1 : \{ (*EVAR*); (*VVAR*); (*CONST* *e*); } \*!* *$fail*;
>>
>>   *t*.Ft2 : \{ (*EVAR*); (*VVAR*); (*CONST* *e*); } \*!* *$fail*;
>>
>>   <*MSG_Exprs* (*e*.Fe1) *e*.Fe2> <*MSG_Terms* *t*.Ft1 *t*.Ft2>;
>>
>> };
>>
>>   ((*CONST* *t*.name) *e*.Fe1) *e*.Fe2, {
>>
>> *e*.Fe2 : (*CONST* *t*.name) *e*.Rest = (*CONST* *t*.name) <*MSG_Exprs* 
>> (*e*.Fe1) *e*.Rest>;
>>
>> <*MSG_Exprs* (<*Format_Exp* <*Lookup* &*Const* *t*.name>> *e*.Fe1) 
>> *e*.Fe2>;
>>
>>   };
>>
>>   (*e*.Fe1 (*CONST* *t*.name)) *e*.Fe2, {
>>
>> *e*.Fe2 : *e*.Rest (*CONST* *t*.name) = <*MSG_Exprs* (*e*.Fe1) *e*.Rest> 
>> (*CONST* *t*.name);
>>
>> <*MSG_Exprs* (*e*.Fe1 <*Format_Exp* <*Lookup* &*Const* *t*.name>>) 
>> *e*.Fe2>;
>>
>>   };
>>
>>   (*e*.Fe1) (*CONST* *t*.name) *e*.Fe2 =
>>
>> <*MSG_Exprs* (*e*.Fe1) <*Format_Exp* <*Lookup* &*Const* *t*.name>> 
>> *e*.Fe2>;
>>
>>   (*e*.Fe1) *e*.Fe2 (*CONST* *t*.name) =
>>
>> <*MSG_Exprs* (*e*.Fe1) *e*.Fe2 <*Format_Exp* <*Lookup* &*Const* 
>> *t*.name>>>;
>>
>>   (*e*.Fe1) *e*.Fe2, {
>>
>> <*IsEmpty_Expr* *e*.Fe1>, <*IsEmpty_Expr* *e*.Fe2> = */*empty*/*;
>>
>> */* *
>>
>> * * If both e.Fe1 and e.Fe2 have non-(EVAR) terms then we can unify*
>>
>> * * them to (VVAR). Be VERY careful! We can meet , but it easy can be*
>>
>> * * that it points to empty expression.*
>>
>> * */*
>>
>> \*?*
>>
>> *e*.Fe1 : *e* *t*.Ft1 *e*, *t*.Ft1 : \{
>>
>>   (*VVAR*);
>>
>>   (*CONST* *t*.name), # <*IsEmpty_Const* *t*.name>;
>>
>> } \*!*
>>
>>   *e*.Fe2 : *e* *t*.Ft2 *e*, *t*.Ft2 : \{
>>
>> (*VVAR*);
>>
>> (*CONST* *t*.name), # <*IsEmpty_Const* *t*.name>;
>>
>>   } =
>>
>>   (*VVAR*);
>>
>> */**
>>
>> * * Else at least one of expressions has form of (EVAR)...(EVAR). So we*
>>
>> * * should return (EVAR).*
>>
>> * */*
>>
>> (*EVAR*);
>>
>>   };
>>
>> };
>>
>>
>>
>> *MSG_Terms* {
>>
>>   (*PAREN* *e*.Fe1) (*PAREN* *e*.Fe2) = (*PAREN* <*MSG_Exprs* (*e*.Fe1) 
>> *e*.Fe2>);
>>
>>   *t*.Ft *t*.Ft = *t*.Ft;
>>
>>   *s* *s* = (*SVAR*);
>>
>>   (*SVAR*) *s* = (*SVAR*);
>>
>>   *s* (*SVAR*) = (*SVAR*);
>>
>>   (*SVAR*) (*SVAR*) = (*SVAR*);
>>
>>   (*REF* *e*) *s* = (*SVAR*);
>>
>>   *s* (*REF* *e*) = (*SVAR*);
>>
>>   (*REF* *e*) (*SVAR*) = (*SVAR*);
>>
>>   (*SVAR*) (*REF* *e*) = (*SVAR*);
>>
>>   *t* *t* = (*TVAR*);
>>
>> };
>>
>>
>>
>> Хотел бы просто дать ссылку на исходники, но, к сожалению, сайт с ними
>> лежит (что с ним довольно регулярно случается, так как никто не замечает,
>> когда он падает).
>>
>>
>>
>> Антон
>>

Re: Re[4]: Немного статистики

[Anton Orlov orlovan_AT_gmail . com]

Александр,

Я, пожалуй, просто вставлю сюда код :)
Он не самодостаточен, но алгоритм из него читаем.

*/*
 * MSG-Exprs (e.Format1) e.Format2
 * Return e.Format3 -- most specific generalizing of formats 1 and 2.
 */**MSG_Exprs* {
  ((*FAIL*)) *e*.Fe2 = *e*.Fe2;
  (*e*.Fe1) (*FAIL*) = *e*.Fe1;
  (*t*.Ft1 *e*.Fe1) *t*.Ft2 *e*.Fe2 \*?*
*/*
 * IF both t.Ft1 and t.Ft2 are hard terms and aren't $const'ants then
 * split them out with MSG-Terms.
 */*
{
  *t*.Ft1 : \{ (*EVAR*); (*VVAR*); (*CONST* *e*); } \*!* *$fail*;
  *t*.Ft2 : \{ (*EVAR*); (*VVAR*); (*CONST* *e*); } \*!* *$fail*;
  <*MSG_Terms* *t*.Ft1 *t*.Ft2> <*MSG_Exprs* (*e*.Fe1) *e*.Fe2>;
};
  (*e*.Fe1 *t*.Ft1) *e*.Fe2 *t*.Ft2 \*?*
*/*
 * IF both t.Ft1 and t.Ft2 are hard terms and aren't $const'ants then
 * split them out with MSG-Terms.
 */*
{
  *t*.Ft1 : \{ (*EVAR*); (*VVAR*); (*CONST* *e*); } \*!* *$fail*;
  *t*.Ft2 : \{ (*EVAR*); (*VVAR*); (*CONST* *e*); } \*!* *$fail*;
  <*MSG_Exprs* (*e*.Fe1) *e*.Fe2> <*MSG_Terms* *t*.Ft1 *t*.Ft2>;
};
  ((*CONST* *t*.name) *e*.Fe1) *e*.Fe2, {
*e*.Fe2 : (*CONST* *t*.name) *e*.Rest = (*CONST* *t*.name)
<*MSG_Exprs* (*e*.Fe1) *e*.Rest>;
<*MSG_Exprs* (<*Format_Exp* <*Lookup* &*Const* *t*.name>> *e*.Fe1) *e*.Fe2>;
  };
  (*e*.Fe1 (*CONST* *t*.name)) *e*.Fe2, {
*e*.Fe2 : *e*.Rest (*CONST* *t*.name) = <*MSG_Exprs* (*e*.Fe1)
*e*.Rest> (*CONST* *t*.name);
<*MSG_Exprs* (*e*.Fe1 <*Format_Exp* <*Lookup* &*Const* *t*.name>>) *e*.Fe2>;
  };
  (*e*.Fe1) (*CONST* *t*.name) *e*.Fe2 =
<*MSG_Exprs* (*e*.Fe1) <*Format_Exp* <*Lookup* &*Const* *t*.name>> *e*.Fe2>;
  (*e*.Fe1) *e*.Fe2 (*CONST* *t*.name) =
<*MSG_Exprs* (*e*.Fe1) *e*.Fe2 <*Format_Exp* <*Lookup* &*Const* *t*.name>>>;
  (*e*.Fe1) *e*.Fe2, {
<*IsEmpty_Expr* *e*.Fe1>, <*IsEmpty_Expr* *e*.Fe2> = */*empty*/*;
*/*
 * If both e.Fe1 and e.Fe2 have non-(EVAR) terms then we can unify
 * them to (VVAR). Be VERY careful! We can meet , but it easy can be
 * that it points to empty expression.
 */*
\*?*
*e*.Fe1 : *e* *t*.Ft1 *e*, *t*.Ft1 : \{
  (*VVAR*);
  (*CONST* *t*.name), # <*IsEmpty_Const* *t*.name>;
} \*!*
  *e*.Fe2 : *e* *t*.Ft2 *e*, *t*.Ft2 : \{
(*VVAR*);
(*CONST* *t*.name), # <*IsEmpty_Const* *t*.name>;
  } =
  (*VVAR*);
*/*
 * Else at least one of expressions has form of (EVAR)...(EVAR). So we
 * should return (EVAR).
 */*
(*EVAR*);
  };
};
*MSG_Terms* {
  (*PAREN* *e*.Fe1) (*PAREN* *e*.Fe2) = (*PAREN* <*MSG_Exprs*
(*e*.Fe1) *e*.Fe2>);
  *t*.Ft *t*.Ft = *t*.Ft;
  *s* *s* = (*SVAR*);
  (*SVAR*) *s* = (*SVAR*);
  *s* (*SVAR*) = (*SVAR*);
  (*SVAR*) (*SVAR*) = (*SVAR*);
  (*REF* *e*) *s* = (*SVAR*);
  *s* (*REF* *e*) = (*SVAR*);
  (*REF* *e*) (*SVAR*) = (*SVAR*);
  (*SVAR*) (*REF* *e*) = (*SVAR*);
  *t* *t* = (*TVAR*);
};


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

Антон


On Thu, Feb 21, 2019 at 12:29 AM Александр Коновалов
a.v.konovalov87_AT_mail.ru  wrote:

> Доброе утро, Антон!
>
> *«В компиляторе (на уровне преобразования AS → AS) есть фаза порождения
> возвращаемых форматов — делается наиболее тесное обобщение результатных
> выражений (Most Specific Generalization — дуальная операция к Most General
> Unifier — как НОК/НОД).»*
>
> *«Это нужно, в частности, для более качественной компиляции блоков: {
> Exp1; Exp2; ... } : Pattern.»*
>
> Я правильно понимаю, что в выражениях Exp1, Exp2… вместо скобок активации
> подставляются выходные форматы соответствующих функций, после чего
> обобщению подвергаются фактически образцовые выражения?
>
> А где можно прочитать про алгоритм вычисления наиболее тесного обобщения?
> (Можно даже ссылку на исходник, я пойму.) Просто я занимался аналогичной
> задачей применительно к оптимизации сопоставления с несколькими образцами,
> вот записка моего дипломника, где алгоритм описан:
>
>
> https://github.com/bmstu-iu9/refal-5-lambda/blob/c48cf0179b66c407a5932c03cd8bf38958a8c477/doc/OptPattern/Савельев_Записка_2018.pdf
>
> Вот более лаконичное (но менее понятное) описание задачи в таск-трекере:
>
> https://github.com/bmstu-iu9/refal-5-lambda/issues/154
>
> Поясню к последнему. Рассматриваются только жёсткие выражения. Образцы,
> содержащие e-переменную на верхнем уровне (например, A s.1 *e**.2* t.3 (e.4)
> s.3), названы образцами класса (M, N), где M и N — количество термов
> до и после e-переменной соответственно, образцы, не содержащие e-переменной
> на верхнем уровне (например, A s.1 (e.2 t.3) (e.4) s.3) названы образцами
> класса (K), где K — длина терма. ГСО — глобальное сложнейшее обобщение,
> ЛСО — локальное сложнейшее обобщение. Сложность — количество элементарных
> операций отождествления. Локальное-глобальное — по аналогии с локальным
> и глобальным максимумом в математике.
>
>
>
> С уважением,
> Александр Коновалов
>
>
>
>
>
> *From:* 

Re: Рефал Плюс – Was: Синтаксический анализ в Рефале

[Anton Orlov orlovan_AT_gmail . com]

Александр,

Да, всё верно. Я глянул в исходники (сам уже подзабыл и не был уверен) --
там применяется эвристика при конкатенации выражений, когда пришлось
выделить новый чанк: если левое выражение длиннее, то результат помещается
в начало чанка, если правое, то в конец. То есть, в моём конкретном примере
будет таки O(N) присваиваний.

Вместо эвристики в рантайме можно было бы попробовать дотащить эту
информацию из компилятора.

Ещё можно было бы всегда выделять чанк по крайней мере в 2 раза больший,
чем выражение. Если не смущаться, что перерасход памяти будет иногда почти
в 4 раза.

Антон


On Thu, Feb 21, 2019 at 4:41 AM Александр Коновалов
a.v.konovalov87_AT_mail.ru  wrote:

> Доброе утро, Антон!
>
> Я кое-что не понял про оценку сложности:
>
> *«В алгоритме близнецов все выделяемые куски имеют размер 2^n. Выражение
> помещается посередине нового куска, а справа и слева естественным образом
> получается запас по месту. При конкатенации, если этой дырки рядом с одним
> из выражений достаточно, то копируется только одно из выражений, а новая
> память не выделяется.*
>
> *Например, если выражение длины N строится дописыванием в конец/начало
> по одному терму, то это требует O(log N) аллокаций (амортизированная
> стоимость O(1)).»*
>
> Но ведь стоимость аллокации для близнецового метода практически
> константная, зачем её считать? Имеет значение стоимость присваивания
> значения.
>
> Для близнецового метода и размещения куска посередине наилучший случай —
> размер куска, равный 2^n+1 — слева и справа дырки будут иметь длину 2^n/2
> (ну, одна — 2^n/2, вторая — 2^n/2−1, не суть). Соответственно, к такому
> куску можно с каждой стороны приписать (2^n)/2 термов без
> перераспределения.
>
> Наихудший случай — кусок размером 2^n — любое приписывание 1 терма
> потребует реаллокации и копирования 2^n+1 термов (2^n было и ещё 1,
> который мы приписали).
>
> Если мы приписываем термы, например, в начало, и начинаем с наилучшего
> случая (2^n+1, дырка имеет длину 2^n/2), то мы сможем приписать по одному
> терму 2^n/2 раз до перераспределения. Перераспределение потребует 2^n/2 +
> 2^n + 1 операций присваивания, в новом куске обе дырки будут иметь длину
> уже 2^n/4. А это значит, что теперь мы сделаем только n^2/4 копирований.
>
> Продолжая в том же духе, получим, что приписывание к выражению длиной 2^n+1
> термов 2^n раз по одному терму мы действительно выполним O(n) аллокаций,
> но с каждой из них будет сопряжено O(2^n) присваиваний. Действительно,
> пусть после очередной переаллокации у нас занято L ячеек, с обоих сторон
> имеем H=(2^n−L)/2 свободных ячеек — дырок. Тогда до следующей
> переаллокации мы выполним H присваиваний, сама переаллокация потребует
> присваивания L+H ячеек. Всего за один цикл будет выполнено L +
> 2×(2^n−L)/2 = 2^n присваиваний. За каждый цикл дырка уменьшается в два
> раза, значит, число циклов будет O(n).
>
> Таким образом, удлинение выражения длины L = 2^n+1 до L′=2^(n+1)+1
> требует O(n×2^n) = O(L log L) присваиваний.
>
> Можно показать, что построение выражения длины L=2^n начиная с пустого
> также требует O(n×2^n) = O(L log L) присваиваний. Могу эти выкладки
> написать, если интересно. Для L≠2^n тоже будет O(L log L) (оценка снизу),
> тоже могу доказать, если кто-то мне не верит. Аллокаций, кстати, на самом
> деле потребуется O(log² L), логарифм в квадрате.
>
> Так что, если выражение длины N строится дописыванием в конец/начало
> по одному терму, то это потребует *O**(**N* *log* *N**) присваиваний
> (амортизированная стоимость **O**(**log* *N**)).*
>
>
>
> Если бы дырок не было вообще, то потребовалось бы O(N) аллокаций и O(N²)
> присваиваний. Амортизированная стоимость — O(N).
>
> Если бы мы знали, что приписывание терма выполняется только в конец,
> то могли бы распределять память степенями двойки и размещать занятое место
> с начала. Количество аллокаций было бы O(log N), количество присваиваний O
> (N), амортизированная стоимость — O(1).
>
> Так что близнецовый метод (вернее, распределение памяти по степеням двойки
> с размещением куска посередине) существенно лучше наивного варианта без
> дырок, но чуть хуже идеального варианта.
>
>
>
> *«P.S. Помимо списков и массивов есть ещё потенциально интересные
> структуры данных для представления выражений. Например, rope
>  и Finger tree
> , но серьёзно для рефальского
> применения их никто не исследовал, насколько я знаю.»*
>
> К слову, в той же задаче — построении строки длиной N путём
> последовательного приписывания термов по одному — обе упомянутые структуры
> данных потребуют O(N log N) времени, поскольку приписывание одного
> символа в обоих видах строк требует O(log N) времени.
>
> Я когда-то давал на курсовой проект задачу — реализовать Простой Рефал
> с использованием rope’ов для представления объектных выражений. Студент
> не осилил сделать, задача оказалась слишком сложной для курсового (я
> по неопытности не смог оценить объём 

Re: Nicolas Stucki, Tiark Rompf, Vlad Ureche, and Phil Bagwell. 2015. RRB vector: a practical general purpose immutable sequence.

[Anton Orlov orlovan_AT_gmail . com]

Интересно было бы сравнить с реализацией векторов в Clojure, которая
опирается на работу того же Phil Bagwell. Статьи нормальной я не нашёл, но
есть подробный блог-пост:
https://hypirion.com/musings/understanding-persistent-vector-pt-1
(и исходники).

Антон

On Thu, Feb 21, 2019 at 4:18 PM Sergei Romanenko
sergei.romanenko_AT_supercompilers.ru  wrote:

> Nicolas Stucki, Tiark Rompf, Vlad Ureche, and Phil Bagwell. 2015. RRB
> vector: a practical general purpose immutable sequence. In *Proceedings
> of the 20th ACM SIGPLAN International Conference on Functional Programming*
> (ICFP 2015). ACM, New York, NY, USA, 342-354. DOI=
> http://dx.doi.org/10.1145/2784731.2784739
>
> State-of-the-art immutable collections have wildly differing performance
> characteristics across their operations, often forcing programmers to
> choose different collection implementations for each task. Thus, changes to
> the program can invalidate the choice of collections, making code evolution
> costly. It would be desirable to have a collection that performs well for a
> broad range of operations. To this end, we present the RRB-Vector, an
> immutable sequence collection that offers good performance across a large
> number of sequential and parallel operations. The underlying innovations
> are: (1) the Relaxed-Radix-Balanced (RRB) tree structure, which allows
> efficient structural reorganization, and (2) an optimization that exploits
> spatio-temporal locality on the RRB data structure in order to offset the
> cost of traversing the tree. In our benchmarks, the RRB-Vector speedup for
> parallel operations is lower bounded by 7x when executing on 4 CPUs of 8
> cores each. The performance for discrete operations, such as appending on
> either end, or updating and removing elements, is consistently good and
> compares favorably to the most important immutable sequence collections in
> the literature and in use today. The memory footprint of RRB-Vector is on
> par with arrays and an order of magnitude less than competing collections.
> 
>
> В порядке информации.
>
> СР
>
>

Re: Re[4]: Немного статистики

[Anton Orlov orlovan_AT_gmail . com]

On Wed, Feb 20, 2019 at 8:08 AM Arkady Klimov arkady.klimov_AT_gmail.com <
refal@botik.ru> wrote:

> Вопрос интересный, попытаюсь ответить за Антона как я планировал, если б
> занялся погружением рефала-6 в ту инфраструктуру.
> Первый вариант - да, все функции имеют общий формат
> $func eX = eX;
> Затем, возможны варианты, один из которых - что-то типа псевдокомментариев.
> Интересен также вариант отображения после полусуперкомпилятора, который
> форматы порождает.
> Но более продвинутая схема - проводить анализ на уровне абстрактного
> синтаксиса и повышать арность автоматически, и тогда это можно было б
> сделать один раз на все входные диалекты. Собственно, в этом и была задумка
> - чтобы писать разные сложные анализы и преобразования уже в
> диалекто-независимой
>
форме.
>

Отчасти это сделано. В компиляторе (на уровне преобразования AS -> AS) есть
фаза порождения возвращаемых форматов -- делается наиболее тесное обобщение
результатных выражений (Most Specific Generalization -- дуальная операция к
Most General Unifier -- как НОК/НОД).

Это нужно, в частности, для более качественной компиляции блоков: { Exp1;
Exp2; ... } : Pattern.

Запустить более продвинутый повышатель арности, который глобальнее на
программу смотрит, тоже можно было бы на этом уровне.

Антон



> С уважением,
> Аркадий Климов
>
> PS. Соглашусь с Антоном,  что более сложной будет задача поддержки
> стандартных функций, которую предполагалось решать попросту путем написания
> "переходников" на рефале. Что-то подобное было сделано в среде Рефал-6 для
> поддержки входного языка Рефал-5. Конечно, эффективность будет ущербной.
>
> ср, 20 февр. 2019 г. в 12:51, Александр Коновалов
> a.v.konovalov87_AT_mail.ru :
>
>> Добрый день, Антон!
>>
>> *«С исполнением разных диалектов на одной платформе основная проблема —
>> не входной язык, а библиотека стандартных функций. Они везде разные, и все
>> их поддержать — довольно много возни.»*
>>
>> А проблему отсутствия форматов функций в других диалектах (Рефал-5,
>> Рефал-6) Вы как решили (или предполагали решать)? Считать все функции как
>>
>> $func eX = eX;
>>
>> и плевать на производительность? Или форматы задаются
>> в псевдокомментариях?
>>
>>
>>
>> С уважением,
>> Александр Коновалов
>>
>> *From:* Anton Orlov orlovan_AT_gmail.com 
>> *Sent:* Thursday, February 14, 2019 9:49 PM
>> *To:* refal@botik.ru
>> *Cc:* Александр Гусев 
>> *Subject:* Re: Re[4]: Немного статистики
>>
>>
>>
>>
>>
>>
>>
>> On Thu, Feb 14, 2019 at 7:27 AM Arkady Klimov arkady.klimov_AT_gmail.com
>>  wrote:
>>
>> Насколько я знаю, в каком-то законченно-оформленном виде такой информации
>> сейчас нет.
>>
>>
>>
>> Сейчас у меня появилась мысль, и хочу всем апологетам того или иного
>> диалекта, написать небольшой текст в свободной форме на 2-3-5 страниц с
>> описанием особенностей их "любимых" версий языка и их реализаций - что было
>> бы полезно знать потенциальным юзерам. Эти тексты (ссылки) можно было бы
>> разместить на сайте refal.net на страницах, связанных с каждой
>> версией-диалектом. В этой переписке по рефалу+ уже много информации
>> появилось, осталось ее собрать и оформить. Наверно, это было бы полезно.
>>
>>
>>
>> А также неплохо бы единый бенчмарк составить. И какие-то сравнительные
>> таблицы.
>>
>>
>>
>> А еще когда-то была установка на создание единого инструментария по
>> реализации разных диалектов с единым промежуточным синтаксисом AST, с
>> возможностью любой входной диалект на любую платформу положить. Насколько я
>> понимаю, рефал+ свою часть пути в основном прошел и там это представление
>> задокументировано. Хотел бы пройти свою часть для рефала-6, но на это
>> конечно нужно время. Которого, увы, нет.
>>
>>
>>
>> Кстати, AST, используемый в Р+ (
>> http://wiki.botik.ru/Refaldevel/AbstractImperativeLanguage), специально
>> в какой-то момент правился, чтобы включить особенности Рефала-6 (но
>> поскольку парсер из Рефала-6 так и не был приделан, то, возможно, ещё
>> какие-то тонкости остались).
>>
>>
>>
>> С исполнением разных диалектов на одной платформе основная проблема -- не
>> входной язык, а библиотека стандартных функций. Они везде разные, и все их
>> поддержать -- довольно много возни.
>>
>>
>>
>> Антон
>>
>>
>>
>>
>>
>> Аркадий
>>
>>
>>
>> чт, 14 февр. 2019 г. в 09:59, Александр Гусев gusev_aleksandr_AT_mail.ru <
>> refal@botik.ru>:
>>
>> Спасибо, Аркадий!
>>
>> А существует где-то краткая информация по сравнению веток рефала? Статья,
>> может быть какая-то.
>>
>> А то есть рефал-2, рефапл-5, рефал-6 и рефал-плюс - это только те, что
>> поименованы.
>>
>> У каждой версии свои сторонники и блюстители. Или всё-таки придётся в
>> каждую вникать?
>>
>> Среда, 13 февраля 2019, 20:41 +03:00 от Arkady Klimov
>> arkady.klimov_AT_gmail.com :
>>
>> Здравствуйте, Александр!
>>
>> Прошу прощения за некоторую задержку, пришлось немного повозиться,
>> приводя в порядок версию дистрибуции. В принципе, есть все на сайте
>> refal.net, но сильно старое, с тех пор довольно много было правок. Вот
>> та страничка:
>>

Re: Коллапсируюшее представление данных

[Anton Orlov orlovan_AT_gmail . com]

On Wed, Feb 13, 2019 at 6:13 AM Andrei Klimov andrei_AT_klimov.net <
refal@botik.ru> wrote:

> Александр, еще раз добрый день!
>
> Я понял, о чем вы писали и зачем требуется отношение порядка. Объясню
> своими словами на подвешенных скобках.
>
> Пусть (eX) и (eY) входят в два выражения e1(eX)e2 и e3(eY)e4, и при их
> сравнении выяснилось, что (eX) = (eY).
> И пусть на представления (eX) и (eY) есть еще ссылки из других выражений.
> Тогда замена ссылки на (eX) в первом выражении на ссылку на (eY) не
> освобождает память представления (eX).
> И наоборот, замена ссылки на (eY) во втором на ссылку на (eX) не
> освобождает память представления (eY).
> Более того, теряется информация про равенство (eX), или соответственно
> (eY), равным термам в других выражениях.
>
> Хотелось бы, чтобы был разумный способ выбрать, что на что заменять, чтобы
> какое-то из представлений равных термов лидировало и затягивало бы в себя
> ссылки с других.
> Например, в реализации со счетчиками ссылок на скобочный терм, можно
> переносить на представление с большим счетчиком.
>

В Рефале+ (в рантайме Андрея Слепухина) именно так и сделано.
Чтобы ответить на вопрос, много ли это даёт, хорошо было бы прогнать на
представительном наборе программ на Рефале+, которого, однако, не
наблюдается :).

Антон

А если есть отношение порядка между представлениями, то можно выбирать
> наименьшее.
> Если сборка мусора не меняет расположение представлений в памяти (что, как
> правило, имеет место быть), то подходящий порядок задают адреса.
> Но все равно процесс "затягивания" ссылок на самое "тяжелое" представление
> будет медленным и плохо предсказуемым.
>
> Чтобы не терять информацию об уже обнаруженных равенствах термов, лучший
> (как мне помнится) вариант, который был придуман такой:
> Головная ячейка представления скобочного терма может быть прокси, то есть
> ссылкой на окончательное представление или снова на прокси.
> Тогда при выяснении равенства (eX) и (eY) в вышеприведенном примере
> головная ячейка, скажем, (eY) становится прокси, ссылающимся на головную
> ячейку (eX). Подмена ссылки в выражении тоже делается.
>
> Теперь при каждом вхождении в скобки нужно проверять, не на прокси ли мы
> попали, и, если да, идти дальше. Одновременно спрямлять ссылки.
>
> Вот такая сложность картины, плюс ее непредсказуемость для
> Рефал-программиста, и привели к тому, что эти идеи остались в истории.
> Теперь я вспомнил, что отсутствие "идеальных" решений и есть главная
> причина, из-за которой идея не пошла в массы = в реализации Рефала.
> Спасибо, вот сейчас мы нечаянно на них вышли и запротоколировали.
> Может, где-то когда-то кому-то пригодится.
>
> И по-прежнему, интересно узнать, использовалось ли такое коллапсирование
> или обсуждавшаяся табуляция в каких-нибудь системах.
> Если кто наткнется или уже знает, напишите, пожалуйста.
>
> Всего наилучшего,
> Андрей
>
> On Wed, Feb 13, 2019 at 1:08 PM Andrei Klimov andrei.klimov_AT_gmail.com <
> refal@botik.ru> wrote:
>
>> Александр, тогда я видимо совсем вас не понял – ни псевдокод, ни
>> объяснение словами в предыдущем письме:
>>
>> ср, 13 февр. 2019 г., 0:18 Александр Коновалов a.v.konovalov87_AT_mail.ru
>>> :
>>> Добрый вечер, Сергей!
>>> > 2.  Наконец, если нам пришлось делать длинное сравнение и в конце
>>> выяснилось, что термы таки равны, то мы делаем "коллапсирующие джунгли" --
>>> делаем присваивание: p2 = p1, L2=L1 (второе лишнее, но пусть будет).  Тут и
>>> память освободилась и следующий раз сравнение на равенство пройдет быстрее
>>> ;-)
>>> *А если у нас в поле зрения есть несколько экземпляров одинаковых пар
>>> (p1, L1), (p2, L2). В первый раз сравниваются пары в порядке (p1, L1) ==
>>> (p2, L2) и мы присвоили p1 := p2. В другой раз (другие экземпляры)
>>> сравнились в порядке (p2, L2) == (p1, L1) и коллапсировались уже p2 := p1.
>>> Тогда память не освободится. Такое может быть?*
>>
>>
>> По-видимому, я не сообразил, про какое представление рефал-выражений идет
>> речь.
>> И я тоже виноват, что не пояснил, что подразумевал. Договорю.
>>
>> Лучше всего рассмотреть "подвещенные" скобки: скобочный терм (e0)
>> представляется ссылкой на представление e0. Это ссылка хранится в месте
>> терма (e0) в выражениях, в которые он входит. То есть,
>>
>>- <представление выражение e1(e0)e2> = <представление e1> <ссылка на
>>(e0)> <представление e2>
>>
>> Заметим, что это рассуждение не зависит от того, массивное представление
>> выражений или одно- или двунаправленное списочное.
>>
>> Если в процессе отождествления повторных переменных были обнаружены
>> равные термы (e0), входящие в два выражения, то в одном из выражений ссылка
>> на (e0) заменяется на вторую, а второе представление (e0) может
>> освободиться (сборкой мусора или по счетчику ссылок).
>>
>> Александр, тонкость, о которой вы пишите, присутствует в таком
>> представлении с такой операцией сравнения?
>>
>> Если речь о том, что отнюдь не все равные термы будут сколлапсированы, а
>> только те, что когда-то пройдут через операцию