Subject: Re: Re:Re:SCP's
From: Andrei P. Nemytykh (nemytykh@math.botik.ru)
Date: Sat Mar 11 2000 - 15:43:56 MSK
Добрый день, Роман.
> Меня заинтересовала поставленная Вами, Андрей, проблема:
> "На мой взгляд, синтаксическое выделение подмножеств программ про которые
можно было бы делать те или иные точные утверждения относительно данного
преобразователя программ -- есть очень важная и интересная задача".
> Но, насколько это реально, и в какой мере, в ближайшее время? Какие мысли
по поводу методов и/или подходов к решению этой проблемы у Вас возникают и
имеются? Если у Вас есть примеры, кроме работ Wadler-а, пожалуйста,
поделитесь ими.
-- спасибо.
-- Если иметь ввиду конкретный обсуждаемый преобразователь программ ,
то я не знаю ни одного текста, который бы ставил перед собой
подобную задачу.
-- В то же время, ограничения Рефала, предложенные ранее Валентином
Фёдоровичем Турчиным, хотя и были сделаны с целью упростить построение
суперкомпилятора, могут рассматриваться в контексте данной задачи: эти
ограничения сокращают число понятий, которые возникают при реальных
преобразованиях. Одним из таких важных ограничений является плоский Рефал.
Это базисный Рефал, в котором в правых частях предложений допустимо лишь
либо полностью пассивное выражение , либо выражение вида <F e.passive>,
где аргументы не содержат вызовов функций.
-- Если говорить более конкретно, то следующая задача кажется мне
простой:
среди демонстрационных примеров Scp4 есть пример, показывающий
возможность автоматического преобразования некоторых реальных рекурсий в
хвостовую рекурсию. Этому примеру в демонстрации соответствуей bat-файл
d_tail_r.bat (примера пока нет в on-line версии демонстрации -- он появился
недавно и туда ещё не внесён). Причина, по которой происходит такое
преобразование, очень близка к причинам преобразований описанных Wadler-ом.
Но сам он таких преобразований не рассматривает. Задача: указать
подмножество Рефал-программ, для которого реальные рекурсии будут
преобразовываться в хвостовые. ( правильно отталкнуться от текстов
Wadler-а).
-- Вспоминается так же классическая работа John Backus. The algebra of
functional programs: function level reasoning, linear equestions, and
extended definitions. Lect. Notes in Comp. Sci., 1981, v. 107, p. 1-43.
Имеется перевод в сборнике статей "Математическая логика в программировании"
(Москва, "Мир", 1991). Можно ли в ней что-то позаимствовать ?
Спасибо за внимание, Андрей Немытых.
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:24:58 MSD