Subject: Re: Ленивость, бесконечные структура и супекомпиляция
From: korlyukov (korlyukov@grsu.grodno.by)
Date: Fri Aug 10 2001 - 09:59:29 MSD
Я всегда думал и говорил, что суперкомпиляция - это не просто оптимизация
программ с целью ускорения их исполнения, а гораздо более большее.
Данный пример показывает, что разумная с математической точки зрения, но не
исполняемая программа, обрабатывается суперкомпилятором содержательно.
Я попробовал повторить предлагаемые программы в варианте унарной системы
счисления (прибавление единицы - это приписывание одного символа). Все
отмеченное в письме сохранилось.
Думаю, что Андрей Немытых ответит на поставленные в письме вопросы чуть
позже.
Александр Корлюков
----- Original Message -----
From: "Mike Potanin" <potanin@mccme.ru>
To: <refal@botik.ru>
Sent: Thursday, 02 August 2001 11:23
Subject: Ленивость, бесконечные структура и суперкомпиляция.
>
> Здравствуйте!
> Как известно ленивые вычисления позволяют работать с бесконечными
> структурами в промежуточных результатах. Хотя это и не всегда проходит.
> Так в haskell операция filter (\x -> (x<100)) [1..] как и следует ожидать
> сама не завершается. В refal ленивые вычисления не поддерживаются (к
> сожалению) и программа
> *$ENTRY Go { = <Prout <Filt <Inf 1>>>; };
> Inf {
> e.1 s.2 = <Inf e.1 s.2 <+ s.2 1>>;
> }
> Filt {
> 5 e.1 = 5;
> s.1 e.2 = s.1 <Filt e.2>;
> }
> естественно зависает.
> Суперкомпилятор на этой программе тоже зацикливается.
> Однако если переписать функцию Inf с остаточной рекурсией
> Inf {
> e.1 s.2 = e.1 s.2 <Inf <+ s.2 1>>;
> }
> то суперкомпилятор эту программу обработает "правильно", хотя сама
> программа работать естественно не начнет.
> Если бы суперкомпилятор сам перевел рекурсию на остаточную, он мог бы
> обработать и начальную программу? На сколько я понимаю рано или поздно он
> проводит преобразование в остаточную рекурсию - это естественная
> оптимизация для функциональных языков. Почему бы не проводить ее сразу?
> Кстати, чтобы гипотетический суперкомпилятор для haskell обработал
> приведенное выше выражение, он должен "знать" математику - то есть
> учитывать что x < x+1. Вообще имеет ли смысл наделять суперкомпилятор
> такими знаниями (как с идеологической, так и с практической точки зрения)?
> Мне кажется что он мог бы проволить более эфективную оптимизацию, если бы
> "знал" алгебраические соотношения для встроеных функций, и мог бы работать
> быстрее, если бы пользователь мог эту базу знаний расширить.
>
>
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:24:59 MSD