Subject: Ленивость, бесконечные структура и суперкопиляция
From: Mike Potanin (potanin@mccme.ru)
Date: Thu Aug 02 2001 - 12:23:28 MSD
Здравствуйте!
Как известно ленивые вычисления позволяют работать с бесконечными
структурами в промежуточных результатах. Хотя это и не всегда проходит.
Так в 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