RE: Суперкомпилятор, который знает математику

2018-12-20 Пенетрантность Александр Коновалов 
Доброй ночи, Сергей!

Вот здесь вот на страницах 5 и 6

http://conf.nsc.ru/files/conferences/Lyap-100/fulltext/69293/69928/nemytykh_supercompilation_Lyapunov100.pdf

упоминаются работы Футамуры про обобщённые частичные вычисления. В частности, 
там написано:

«По-видимому, наименее разработанными на данный момент нужно считать идеи 
generalized partial computation. В отличие от частичных вычислений и 
суперкомпиляции, подход generalized partial computation к специализации 
незамкнут. Например, анонсированный Ё. Футамурой в 2002 году [11] 
экспериментальный полуавтоматический специализатор WSDFU обращается к внешней 
системе доказательств теорем TPU [4] и внешней базе знаний для доказательств 
свойств преобразуемых программ. Особенный интерес представляют примеры 
специализации программ с числовыми аргументами, в которых в результате 
generalized partial computation понижается порядок временно́й сложности [9], 
[11]. В методах частичных вычислений и суперкомпиляции работа с числовыми 
данными развита крайне слабо; здесь основное внимание уделяется программам, 
преобразующим бинарные деревья (частичные вычисления) и конечные 
последовательности произвольных деревьев (суперкомпиляция).»

Но работ Футамуры я не читал (даже не гуглил), этот пример с числами Фибоначчи 
придумал спонтанно, независимо и неожиданно для себя. И написал в рассылку, 
надеялся, что кто-нибудь здесь мне подкинет свежих (или наоборот, 
«классических») работ по этой теме.

 

С уважением,
Александр Коновалов

 

From: Sergei Grechanik [mailto:sergei.grecha...@gmail.com] 
Sent: Thursday, December 20, 2018 11:01 PM
To: metacomputation...@googlegroups.com
Cc: refal@botik.ru
Subject: Re: Суперкомпилятор, который знает математику

 

 

В принципе, многоуровневая суперкомпиляция (как в суперкомпиляторе Ильи 
Ключникова и, в меньшей степени, как в моём варианте насыщения равенствами) 
делает нечто подобное - применяет леммы. Проблема в том, что эти леммы не 
являются чем-то заданным извне, а обнаруживаются в процессе суперкомпиляции, 
доказываются при помощи суперкомпиляции, да ещё и не сохраняются между 
запусками. Инструменты типа HipSpec решают задачи обнаружения и доказательства 
таких лемм или правил переписывания гораздо эффективнее, поэтому в какой-то 
момент стало понятно, что в суперкомпилятор надо встраивать возможность задания 
дополнительных правил переписывания, которые бы подавались на вход. Насколько я 
помню, у Ильи тоже были мысли в ту сторону, но ни у кого руки так и не дошли. 
Работ на эту тему в рамках суперкомпиляции я тоже не знаю, поэтому тоже хотел 
бы услышать о них, если кто знает.

Re: Суперкомпилятор, который знает математику

2018-12-20 Пенетрантность Sergei Grechanik 
В принципе, многоуровневая суперкомпиляция (как в суперкомпиляторе Ильи
Ключникова и, в меньшей степени, как в моём варианте насыщения равенствами)
делает нечто подобное - применяет леммы. Проблема в том, что эти леммы не
являются чем-то заданным извне, а обнаруживаются в процессе
суперкомпиляции, доказываются при помощи суперкомпиляции, да ещё и не
сохраняются между запусками. Инструменты типа HipSpec решают задачи
обнаружения и доказательства таких лемм или правил переписывания гораздо
эффективнее, поэтому в какой-то момент стало понятно, что в суперкомпилятор
надо встраивать возможность задания дополнительных правил переписывания,
которые бы подавались на вход. Насколько я помню, у Ильи тоже были мысли в
ту сторону, но ни у кого руки так и не дошли. Работ на эту тему в рамках
суперкомпиляции я тоже не знаю, поэтому тоже хотел бы услышать о них, если
кто знает.

RE: Суперкомпилятор, который знает математику

2018-12-20 Пенетрантность Александр Коновалов 
Добрый день, Аркадий!

«Именно, можно взять в качестве исходной … и выходная программа … будет 
эквивалентна исходной при любой операции g, даже некоммутативной … А уж как 
получить это суперкомпиляцией, не используя „школьной алгебры“, не знаю — карты 
вам в руки.»

Существуют методы, которые могут вывести из этой исходной программы с 
экспоненциальной сложностью программу с линейной сложностью, даже если g не 
коммутативна и не ассоциативна. Это те самые таплинг, джунгли и дистилляция, 
упомянутые ранее. Вот статьи, где я встречал этот набивший оскомину пример с 
Фибоначчи:

· Wei-Ngan Chin. Towards an automated tupling strategy. In Proceeding 
of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program 
Manipulation, pages 119–132, Copenhagen, Denmark, 14-16 June 1993. ACM Press

· Secher J.P. (2001) Driving in the Jungle. In: Danvy O., Filinski A. 
(eds) Programs as Data Objects. PADO 2001. Lecture Notes in Computer Science, 
vol 2053. Springer, Berlin, Heidelberg

· http://www.numdam.org/article/ITA_1991__25_5_445_0.pdf

· https 
 
://research.jetbrains.org/files/material/57d7cced3d025.pdf (слайд 104)

· http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.645 

 =rep1=pdf (но тут оно выводится полуавтоматически — пользователем 
вводится подсказка-«эврика»)

(Долго отвечал на письмо, поскольку искал эти ссылки. Первые две у меня есть на 
жёстком диске, но в открытом доступе я не нашёл.)

Смысл моего примера в том, что эффективная программа выводится 
суперкомпиляцией, даёт итеративное решение и сам пример при этом достаточно 
простой (скорее всего, поймёт даже школьник). Единственные два допущения — не 
разбиваем конфигурацию fib(k+1)+fib(k), а продолжаем прогонять (в статье 
Wei-Ngan Chin’а это как-то сложно обосновывается), и, самое главное — мы 
пользуемся правилами школьной алгебры. Это отличается от методов, 
рассматриваемых в статьях выше — у них операция сложения рассматривается как 
чёрный ящик.

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

В общем, существует много способов 
  
оптимизировать n-е число Фибоначчи. 

«А не удастся ли так же получить более простую эквивалентную программу …?»

Мне пока не очевидно, как это сделать. Но хочу обратить внимание, что Ваша 
более простая эквивалентная программа делает больше шагов, чем исходная, как 
минимум на fib(1) (для других значений не уверен). В моём случае остаточная 
программа делает не больше шагов (в смысле Рефал-машины), чем исходная, на всей 
области определения.

 

На счёт насыщения равенствами — к Гречанику. Я читал его препринт давно и уже 
почти забыл его содержание. Надо будет перечитать.

 

Спасибо за интерес,
Александр Коновалов

 

From: Arkady Klimov  
Sent: Thursday, December 20, 2018 3:54 PM
To: metacomputation...@googlegroups.com
Cc: refal@botik.ru
Subject: Re: Суперкомпилятор, который знает математику

 

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

fib(0) = 1
fib(1) = 1
fib(k+2) = g(fib(k+1),fib(k))  

 

и выходная программа

 

fib(0) = 1
fib(1) = 1
fib(k+2) = f(k, 1, 1)

f(0, n, m) = g(n,m)
f(k+1, n, m) = f(k, g(m,n), n)

 

будет эквивалентна исходной при любой операции g, даже некоммутативной, хотя в 
этом случае я не ручаюсь за порядок аргументов в обращениях к ней (подозреваю, 
что во втором обращении надо писать g(n,m) ). Проверьте! А уж как получить это 
суперкомпиляцией, не используя "школьной алгебры", не знаю - карты вам в руки.

 

А не удастся ли так же получить более простую эквивалентную программу:

 

fib(0) = 1
fib(k+1) = f(k, 1, 1)
f(0, n, m) = n
f(k+1, n, m) = f(k, g(n,m), n)

 

?

 

Кстати, неплохой тест на эквивалентность. Как там насчет насыщения равенствами?

Аркадий

 

пн, 17 дек. 2018 г. в 18:58, 'Александр Коновалов' via Метавычисления и 
специализация программ mailto:metacomputation...@googlegroups.com> >:

Добрый день всем!

Прошу прощения за возможный «баян», просто мне хочется поделиться этой мыслью. 

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

fib(0)

Re: Суперкомпилятор, который знает математику

2018-12-20 Пенетрантность Arkady Klimov 
Александр, я не знаю, где читать про это, надо искать, но хочу предложить
Вам эту идею развить. Как мне кажется, полученный результат преобразований
эквивалентен исходной программе даже без учета "школьной алгебры". Именно,
можно взять в качестве исходной
fib(0) = 1
fib(1) = 1
fib(k+2) = g(fib(k+1),fib(k))

и выходная программа

fib(0) = 1
fib(1) = 1
fib(k+2) = f(k, 1, 1)

f(0, n, m) = g(n,m)
f(k+1, n, m) = f(k, g(m,n), n)

будет эквивалентна исходной при любой операции g, даже некоммутативной,
хотя в этом случае я не ручаюсь за порядок аргументов в обращениях к ней
(подозреваю, что во втором обращении надо писать g(n,m) ). Проверьте! А уж
как получить это суперкомпиляцией, не используя "школьной алгебры", не знаю
- карты вам в руки.

А не удастся ли так же получить более простую эквивалентную программу:

fib(0) = 1
fib(k+1) = f(k, 1, 1)
f(0, n, m) = n
f(k+1, n, m) = f(k, g(n,m), n)

?

Кстати, неплохой тест на эквивалентность. Как там насчет насыщения
равенствами?
Аркадий

пн, 17 дек. 2018 г. в 18:58, 'Александр Коновалов' via Метавычисления и
специализация программ :

> Добрый день всем!
>
> Прошу прощения за возможный «баян», просто мне хочется поделиться этой
> мыслью.
>
> Подумалось тут, что если суперкомпилятор будет знать математику, хотя бы
> на уровне школьной алгебры, то он сможет делать весьма интересные
> преобразования. Вот например, функция вычисления k-го числа Фибоначчи:
>
> fib(0) = 1
> fib(1) = 1
> fib(k+2) = fib(k+1) + fib(k)
>
> Знакомый хрестоматийный пример, на котором в разных статьях демонстрируют
> способы разной степени хитрости по снижению алгоритмической сложности
> (таплинг, джунгли, дистилляция…). Функция имеет линейные затраты памяти
> (стека) и экспоненциальные затраты времени.
>
> Попробуем просуперкомпилировать его вручную, используя знания школьной
> алгебры (не зря же нас учили приводить подобные члены, выносить за скобки
> и т.д.) Граф в GraphViz мне рисовать лень, поэтому буду использовать
> обозначения, которые я видел в некоторых статьях Турчина.
>
> Начальная конфигурация
>
> [C0]: fib(k).
>
> Прогонка по первым двум ветвям тривиальна:
>
> [C0] k → 0 [C1]
> [C0] k → 1 [C2]
> [C1, C2]: 1
>
> Прогонка по третьей ветви
>
> [C0] k → k+2 [C3]
> [C3]: fib(k+1) + fib(k)
>
> Тут можно разбить конфигурацию на две и получить остаточную программу,
> идентичную исходной. Но мы продолжим прогонку:
>
> [C3] k → 0 [C4]
> [C4]:fib(0+1) + fib(0)
> fib(1) + fib(0)
> 1 + 1
> 2
>
> [C3] k → k+1 [C5]
> [C5]:fib(k+2) + fib(k+1)
> fib(k+1) + fib(k) + fib(k+1)
> 2·fib(k+1) + fib(k)
>
> Да, мы знаем школьную алгебру и сгруппировали подобные члены. Конфигурации
> C3 и C5 похожи, не так ли? Можно записать их обобщение:
>
> [C6]: n·fib(k+1) + fib(k)
>
> Да, обобщение мы тоже записали, зная правила школьной алгебры.
>
> Отбрасываем C4 и C5, обобщаем C3, прогоняем C6:
>
> [C3] 1 ← n [C6]
>
> [C6] k → 0 [C7]
> [C7]:n·fib(0+1) + fib(0)
> n + 1
>
> [C6] k → k+1 [C8]
> [C8]:n·fib(k+2) + fib(k+1)
> n·fib(k+1) + n·fib(k) + fib(k+1)
> (n+1)·fib(k+1) + n·fib(k)
>
> Конфигурации C6 и C8 похожи, их обобщение n·fib(k+1) + m·fib(k). Снова
> отбрасываем поддерево и начинаем заново:
>
> [C9]: n·fib(k+1) + m·fib(k)
>
> [C6] 1 ← m [C9]
>
> [C9] k → 0 [C10]
> [C10]:  n·fib(0+1) + m·fib(0)
> n+m
>
> [C9] k → k+1 [C11]
> [C11]:  n·fib(k+2) + m·fib(k+1)
> n·fib(k+1) + n·fib(k) + m·fib(k+1)
> (m+n)·fib(k+1) + n·fib(k)
>
> Конфигурация [C11] вкладывается в [C9]:
>
> [C11] (m+n, n) ← (n, m) [C9]
>
> Граф построен полностью, запишем остаточную программу:
>
> fib(0) = 1
> fib(1) = 1
> fib(k+2) = f(k, 1, 1)
>
> f(0, n, m) = n+m
> f(k+1, n, m) = f(k, m+n, n)
>
> Получилась программа, линейная по времени и константная по стеку. Что
> интересно, в графе конфигураций возникли операции умножения, которые,
> однако, не попали в остаточную программу.
>
>
>
> Старая народная мудрость гласит: если к вам в голову пришла идея, значит
> в интернете на эту тему уже есть форум. В том смысле, что эту тему уже
> копали до меня, и наверняка такие суперкомпиляторы уже написаны. Но я
> об этом ничего не знаю, поскольку даже не знаю, по каким ключевым словам
> гуглить.
>
> В общем, посоветуйте мне пожалуйста, *что почитать на эту тему.*
>
>
>
> С уважением,
> Александр Коновалов
>
> --
> Вы получили это сообщение, поскольку подписаны на группу "Метавычисления и
> специализация программ".
> Чтобы отменить подписку на эту группу и больше не получать от нее
> сообщения, отправьте письмо на электронный адрес
> metacomputation-ru+unsubscr...@googlegroups.com.
> Чтобы отправлять сообщения в эту группу, отправьте письмо на электронный
> адрес metacomputation...@googlegroups.com.
> Чтобы зайти в группу, перейдите по ссылке
> https://groups.google.com/group/metacomputation-ru.
> Чтобы посмотреть обсуждение на веб-странице, перейдите по ссылке
>

Re[2]: Об остановке суперкомпилятора Рефала

2018-12-20 Пенетрантность А Н 
Квадрат - просто чтобы подчеркнуть, что вес числа констант и конструкторов 
больше, чем минус числа е-параметров. 

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

Антонина Непейвода


>Четверг, 20 декабря 2018, 14:37 +03:00 от Александр Коновалов 
>:
>
>Добрый день, Антонина!
>Рад видеть тебя в рассылке! И, наверное, не только я.
>«При каждом обобщении величина (3*K)^2+(3*K − E) может только уменьшаться.»
>Я, наверное, туплю сегодня, но откуда там квадрат? Он связан с наличием 
>повторных переменных, которые при обобщении могут перестать быть повторными?
> 
>Кстати, о повторных переменных. Мне кажется, что такая конфигурация имеет 
>право существовать:
>< F ( e .1)  e .1  e .2 ( e .2)>
>и если её обобщить с
>< F ( e .1)  e .1  X e .2 ( e .2)>
>то может получиться
>
>Но анализировать такие вещи будет сложнее.
> 
>Спасибо,
>Александр Коновалов
>P . S . Андрей К., проверьте, пожалуйста, отлупы. Письмо Антонины мне не 
>пришло на ящик @ mail . ru .
> 
>From: А Н < a_ne...@mail.ru > 
>Sent: Thursday, December 20, 2018 1:28 PM
>To: refal@botik.ru
>Subject: Re: Об остановке суперкомпилятора Рефала
> 
>Добрый день, Александр!
>
>Насколько я знаю, в SCP4 используется стратегия, запрещающая построение 
>обобщений, в которых два е-параметра стоят подряд. Каждые такие два 
>е-параметра сливаются в один. И это гарантирует конечную длину цепочки 
>обобщений у выражения. Что можно попробовать доказать, построив оценку 
>"обобщаемости" выражения. Например, такую (грубую): пусть K - суммарное 
>количество термов (на любом скобочном уровне), вызовов функций, скобочных 
>конструкторов в выражении, E - суммарное количество е-параметров. Оно не может 
>превысить 3*K, поскольку каждый терм (конструктор, вызов) разбивает выражение 
>максимум на три области. Если количество е-параметров станет больше, чем 3*K, 
>какие-то два из них окажутся рядом (принцип Дирихле).
>
>И всё. При каждом обобщении величина (3*K)^2+(3*K - E) может только 
>уменьшаться.
>
>Наверное, и другие стратегии, запрещающие бесконечное обобщение, можно 
>придумать. А может, они даже где-то описаны.
> 
>>Четверг, 20 декабря 2018, 12:33 +03:00 от Александр Коновалов < 
>>a.v.konovalo...@mail.ru >:
>>Добрый день всем!
>>Пишу в две рассылки, поскольку вопрос и про суперкомпиляцию, и про Рефал.
>>В рассылке  metacomputation - ru @… я встретил ссылку на препринт Сергея 
>>Романенко:
>>С.А. Романенко. Суперкомпиляция: гомеоморфное вложение, вызов по имени, 
>>частичные вычисления // Препринты ИПМ им. М.В.Келдыша. 2018. № 209. С. 1-32.  
>>doi:10.20948/prepr-2018-209 link PDF
>>В нём неформально обосновывается остановка суперкомпилятора  SCPS , который 
>>работает с модельным языком  SLL . Один из ключевых моментов — обобщение не 
>>может выполняться бесконечное количество раз:
>>Таким образом, вместо поступательного построения дерева получается некоторая 
>>последовательность попыток: строим поддерево, «разочаровываемся» в нём, 
>>уничтожаем его, обобщаем конфигурацию, из которой оно выросло, строим 
>>поддерево заново, и т.д.
>>Возникает вопрос: а не будет ли этот процесс продолжаться бесконечно? К 
>>счастью, как показал Сёренсен [16], в случае языка SLL, с которым работает 
>>суперкомпилятор SPSC [14], этот процесс рано или поздно завершается.  Дело в 
>>том, что в случае SLL для любой конфигурации существует только конечное число 
>>обобщений (с точностью до переименования переменных). Таким образом, 
>>«верхняя» конфигурация может подвергнуться обобщению только конечное число 
>>раз.
>> 
>>В случае с Рефалом всё не очевидно. На первый взгляд, для произвольной 
>>конфигурации — выражения с переменными и вызовами функций — можно построить 
>>бесконечное число обобщений, натыкивая в разные места  e -переменные. Так ли 
>>это на практике? Можно ли бесконтрольно вставлять в выражение  e- переменные?
>> 
>>С уважением,
>>Александр Коновалов
>> 
>> 
>
>
>-- 
>А Н

-- 
А Н

RE: Об остановке суперкомпилятора Рефала

2018-12-20 Пенетрантность Александр Коновалов 
Добрый день, Антонина!

Рад видеть тебя в рассылке! И, наверное, не только я.

«При каждом обобщении величина (3*K)^2+(3*K − E) может только уменьшаться.»

Я, наверное, туплю сегодня, но откуда там квадрат? Он связан с наличием 
повторных переменных, которые при обобщении могут перестать быть повторными?

 

Кстати, о повторных переменных. Мне кажется, что такая конфигурация имеет право 
существовать:



и если её обобщить с



то может получиться



Но анализировать такие вещи будет сложнее.

 

Спасибо,
Александр Коновалов

P.S. Андрей К., проверьте, пожалуйста, отлупы. Письмо Антонины мне не пришло на 
ящик @mail.ru.

 

From: А Н mailto:a_ne...@mail.ru> > 
Sent: Thursday, December 20, 2018 1:28 PM
To: refal@botik.ru  
Subject: Re: Об остановке суперкомпилятора Рефала

 

Добрый день, Александр!

Насколько я знаю, в SCP4 используется стратегия, запрещающая построение 
обобщений, в которых два е-параметра стоят подряд. Каждые такие два е-параметра 
сливаются в один. И это гарантирует конечную длину цепочки обобщений у 
выражения. Что можно попробовать доказать, построив оценку "обобщаемости" 
выражения. Например, такую (грубую): пусть K - суммарное количество термов (на 
любом скобочном уровне), вызовов функций, скобочных конструкторов в выражении, 
E - суммарное количество е-параметров. Оно не может превысить 3*K, поскольку 
каждый терм (конструктор, вызов) разбивает выражение максимум на три области. 
Если количество е-параметров станет больше, чем 3*K, какие-то два из них 
окажутся рядом (принцип Дирихле).

И всё. При каждом обобщении величина (3*K)^2+(3*K - E) может только уменьшаться.

Наверное, и другие стратегии, запрещающие бесконечное обобщение, можно 
придумать. А может, они даже где-то описаны.
 

Четверг, 20 декабря 2018, 12:33 +03:00 от Александр Коновалов 
mailto:a.v.konovalo...@mail.ru> >:

Добрый день всем!

Пишу в две рассылки, поскольку вопрос и про суперкомпиляцию, и про Рефал.

В рассылке metacomputation-ru@… я встретил ссылку на препринт Сергея Романенко:

С.А. Романенко. Суперкомпиляция: гомеоморфное вложение, вызов по имени, 
частичные вычисления // Препринты ИПМ им. М.В.Келдыша. 2018. № 209. С. 1-32. 
doi:10.20948/prepr-2018-209 link PDF 
 

В нём неформально обосновывается остановка суперкомпилятора SCPS, который 
работает с модельным языком SLL. Один из ключевых моментов — обобщение не может 
выполняться бесконечное количество раз:

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

Возникает вопрос: а не будет ли этот процесс продолжаться бесконечно? К 
счастью, как показал Сёренсен [16], в случае языка SLL, с которым работает 
суперкомпилятор SPSC [14], этот процесс рано или поздно завершается. Дело в 
том, что в случае SLL для любой конфигурации существует только конечное число 
обобщений (с точностью до переименования переменных). Таким образом, «верхняя» 
конфигурация может подвергнуться обобщению только конечное число раз.

 

В случае с Рефалом всё не очевидно. На первый взгляд, для произвольной 
конфигурации — выражения с переменными и вызовами функций — можно построить 
бесконечное число обобщений, натыкивая в разные места e-переменные. Так ли это 
на практике? Можно ли бесконтрольно вставлять в выражение e-переменные?

 

С уважением,
Александр Коновалов

 

 



-- 
А Н

RE: Об остановке суперкомпилятора Рефала

2018-12-20 Пенетрантность офис 
Добрый день, Антонина!

Рад видеть тебя в рассылке! И, наверное, не только я.

«При каждом обобщении величина (3*K)^2+(3*K − E) может только уменьшаться.»

Я, наверное, туплю сегодня, но откуда там квадрат? Он связан с наличием 
повторных переменных, которые при обобщении могут перестать быть повторными?

 

Кстати, о повторных переменных. Мне кажется, что такая конфигурация имеет право 
существовать:



и если её обобщить с



то может получиться



Но анализировать такие вещи будет сложнее.

 

Спасибо,
Александр Коновалов

P.S. Андрей К., проверьте, пожалуйста, отлупы. Письмо Антонины мне не пришло на 
ящик @mail.ru.

 

From: А Н  
Sent: Thursday, December 20, 2018 1:28 PM
To: refal@botik.ru
Subject: Re: Об остановке суперкомпилятора Рефала

 

Добрый день, Александр!

Насколько я знаю, в SCP4 используется стратегия, запрещающая построение 
обобщений, в которых два е-параметра стоят подряд. Каждые такие два е-параметра 
сливаются в один. И это гарантирует конечную длину цепочки обобщений у 
выражения. Что можно попробовать доказать, построив оценку "обобщаемости" 
выражения. Например, такую (грубую): пусть K - суммарное количество термов (на 
любом скобочном уровне), вызовов функций, скобочных конструкторов в выражении, 
E - суммарное количество е-параметров. Оно не может превысить 3*K, поскольку 
каждый терм (конструктор, вызов) разбивает выражение максимум на три области. 
Если количество е-параметров станет больше, чем 3*K, какие-то два из них 
окажутся рядом (принцип Дирихле).

И всё. При каждом обобщении величина (3*K)^2+(3*K - E) может только уменьшаться.

Наверное, и другие стратегии, запрещающие бесконечное обобщение, можно 
придумать. А может, они даже где-то описаны.
 

Четверг, 20 декабря 2018, 12:33 +03:00 от Александр Коновалов 
mailto:a.v.konovalo...@mail.ru> >:

Добрый день всем!

Пишу в две рассылки, поскольку вопрос и про суперкомпиляцию, и про Рефал.

В рассылке metacomputation-ru@… я встретил ссылку на препринт Сергея Романенко:

С.А. Романенко. Суперкомпиляция: гомеоморфное вложение, вызов по имени, 
частичные вычисления // Препринты ИПМ им. М.В.Келдыша. 2018. № 209. С. 1-32. 
doi:10.20948/prepr-2018-209 link PDF 
 

В нём неформально обосновывается остановка суперкомпилятора SCPS, который 
работает с модельным языком SLL. Один из ключевых моментов — обобщение не может 
выполняться бесконечное количество раз:

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

Возникает вопрос: а не будет ли этот процесс продолжаться бесконечно? К 
счастью, как показал Сёренсен [16], в случае языка SLL, с которым работает 
суперкомпилятор SPSC [14], этот процесс рано или поздно завершается. Дело в 
том, что в случае SLL для любой конфигурации существует только конечное число 
обобщений (с точностью до переименования переменных). Таким образом, «верхняя» 
конфигурация может подвергнуться обобщению только конечное число раз.

 

В случае с Рефалом всё не очевидно. На первый взгляд, для произвольной 
конфигурации — выражения с переменными и вызовами функций — можно построить 
бесконечное число обобщений, натыкивая в разные места e-переменные. Так ли это 
на практике? Можно ли бесконтрольно вставлять в выражение e-переменные?

 

С уважением,
Александр Коновалов

 

 



-- 
А Н

Re: Об остановке суперкомпилятора Рефала

2018-12-20 Пенетрантность А Н 
Добрый день, Александр!

Насколько я знаю, в SCP4 используется стратегия, запрещающая построение 
обобщений, в которых два е-параметра стоят подряд. Каждые такие два е-параметра 
сливаются в один. И это гарантирует конечную длину цепочки обобщений у 
выражения. Что можно попробовать доказать, построив оценку "обобщаемости" 
выражения. Например, такую (грубую): пусть K - суммарное количество термов (на 
любом скобочном уровне), вызовов функций, скобочных конструкторов в выражении, 
E - суммарное количество е-параметров. Оно не может превысить 3*K, поскольку 
каждый терм (конструктор, вызов) разбивает выражение максимум на три области. 
Если количество е-параметров станет больше, чем 3*K, какие-то два из них 
окажутся рядом (принцип Дирихле).

И всё. При каждом обобщении величина (3*K)^2+(3*K - E) может только уменьшаться.

Наверное, и другие стратегии, запрещающие бесконечное обобщение, можно 
придумать. А может, они даже где-то описаны.
 
>Четверг, 20 декабря 2018, 12:33 +03:00 от Александр Коновалов 
>:
>
>Добрый день всем!
>Пишу в две рассылки, поскольку вопрос и про суперкомпиляцию, и про Рефал.
>В рассылке  metacomputation - ru @… я встретил ссылку на препринт Сергея 
>Романенко:
>С.А. Романенко. Суперкомпиляция: гомеоморфное вложение, вызов по имени, 
>частичные вычисления // Препринты ИПМ им. М.В.Келдыша. 2018. № 209. С. 1-32.  
>doi:10.20948/prepr-2018-209 link PDF
>В нём неформально обосновывается остановка суперкомпилятора  SCPS , который 
>работает с модельным языком  SLL . Один из ключевых моментов — обобщение не 
>может выполняться бесконечное количество раз:
>Таким образом, вместо поступательного построения дерева получается некоторая 
>последовательность попыток: строим поддерево, «разочаровываемся» в нём, 
>уничтожаем его, обобщаем конфигурацию, из которой оно выросло, строим 
>поддерево заново, и т.д.
>Возникает вопрос: а не будет ли этот процесс продолжаться бесконечно? К 
>счастью, как показал Сёренсен [16], в случае языка SLL, с которым работает 
>суперкомпилятор SPSC [14], этот процесс рано или поздно завершается.  Дело в 
>том, что в случае SLL для любой конфигурации существует только конечное число 
>обобщений (с точностью до переименования переменных). Таким образом, «верхняя» 
>конфигурация может подвергнуться обобщению только конечное число раз.
> 
>В случае с Рефалом всё не очевидно. На первый взгляд, для произвольной 
>конфигурации — выражения с переменными и вызовами функций — можно построить 
>бесконечное число обобщений, натыкивая в разные места  e -переменные. Так ли 
>это на практике? Можно ли бесконтрольно вставлять в выражение  e- переменные?
> 
>С уважением,
>Александр Коновалов
> 
> 

-- 
А Н

Об остановке суперкомпилятора Рефала

2018-12-20 Пенетрантность Александр Коновалов 
Добрый день всем!

Пишу в две рассылки, поскольку вопрос и про суперкомпиляцию, и про Рефал.

В рассылке metacomputation-ru@… я встретил ссылку на препринт Сергея Романенко:

С.А. Романенко. Суперкомпиляция: гомеоморфное вложение, вызов по имени, 
частичные вычисления // Препринты ИПМ им. М.В.Келдыша. 2018. № 209. С. 1-32. 
doi:10.20948/prepr-2018-209 link PDF 
 

В нём неформально обосновывается остановка суперкомпилятора SCPS, который 
работает с модельным языком SLL. Один из ключевых моментов — обобщение не может 
выполняться бесконечное количество раз:

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

Возникает вопрос: а не будет ли этот процесс продолжаться бесконечно? К 
счастью, как показал Сёренсен [16], в случае языка SLL, с которым работает 
суперкомпилятор SPSC [14], этот процесс рано или поздно завершается. Дело в 
том, что в случае SLL для любой конфигурации существует только конечное число 
обобщений (с точностью до переименования переменных). Таким образом, «верхняя» 
конфигурация может подвергнуться обобщению только конечное число раз.

 

В случае с Рефалом всё не очевидно. На первый взгляд, для произвольной 
конфигурации — выражения с переменными и вызовами функций — можно построить 
бесконечное число обобщений, натыкивая в разные места e-переменные. Так ли это 
на практике? Можно ли бесконтрольно вставлять в выражение e-переменные?

 

С уважением,
Александр Коновалов