Subject: Re: A ref to "CRA-theorem"
From: Andrei Klimov (klimov@keldysh.ru)
Date: Mon Apr 30 2001 - 15:11:33 MSD
Сергей, добрый день!
Валентин Федорович появится 3 мая в Москве и можно будет
у него уточнить. Он уже не дома и почту не читает.
Сейчас я просмотрел работу {turv74} -- она же {Turchin:74}. Там этого не нашел.
И по идеям мне помнится, в 74 году, когда ВФ рассказывал нам
теорию суперкомпиляции на семинарах в АСУРыбПроекте,
симметричной формы сужений и ограничений вроде бы еще не было.
Наверное, первый раз эти понятия появились в Курантовском отчете-80
{Turchin:80:Courant}. Я его сейчас полистал, но места, где было бы написано
"теорема X.Y: любой путь можно привести к такому-то виду" не нашел.
Однако, в разделе 5.2 "Graph of States as a Production System" вводятся
все относящиеся сюда понятия и фактически доказывается эта теорема.
Формулировки есть внутри текста по ходу изложения. Возможно,
я плохо искал, но даже если этот результат не выделен
как "теорема номер X.Y", существо дела не меняется:
он здесь есть, так как описан алгоритм нормализации путей.
Стр. 156 (сверху): Понятие нормализации пути и утверждение о нормализации:
A walk is said to be in normal form if:
(1) it has no assignmetns, no composition rules;
(2) it has exactly one replacement, which makes it end;
(3) there is no more than one contraction for each variable.
Any walk may be brought to a normal form. [...]
Стр. 158 (сверху):
Thus we see that normalization of one walk may result in
several normalized walks. [...]
Мнемоники CRA я не нашел. Здесь это называется "нормализация".
Смотрим индекс:
normal form of ma walk 156
normalization fo walks 145-146
normalization rules 157-161
Сейчас я не проверял, но почти наверняка, все это
еще раз и более аккуратно сформулировано в основной
статье по суперкомпиляции {Turchin:86}.
Успехов!
Андрей.
PS. Ниже, цитируя твое письмо, оставляю только вышеупомянутые ссылки.
Еще раз: {turv74} и {Turchin:74} -- это одно и то же. Информацию нужно слить.
Но в обоих ссылках потерян кусок текста: в конце "места публикации" должно стоять
"Trudy TsNIPIASS, GOSSTROY, Moscow". (Так Турчин ссылается на нее в Отчете-80).
----- Original Message -----
From: "Sergei M. Abramov (at home)" <abram@botik.ru>
To: "refal" <refal@botik.ru>
Sent: Monday, 30 April 2001 09:25
Subject: A ref to "CRA-theorem"
> День добрый, коллеги!
>
> У меня такой вопрос:
>
> ?1. Подскажите ссылку на работу, где В.Ф.Турчин дает
> определение/доказывает CRA-теорему: теорему, что цепочку из сужений, подстановок
> и присваиваний--идут в любом порядке,---можно привести к виду: сначала сужения
> (C), затем рестрикции (R), в конце присваивания (A).
>
> Ссылку лучше в формате BibTeX или \bibitem{} -- или просто кусочек из
> нижеприведенного списка---привожу список некоторых публикаций...
>
> ?2. Называет ли он ее в этой работе как-нибудь? (Дает ли он ей имя
> "CRA"?)
>
> Зарание спасибо,
>
> Сергей
>
[...]
> @Article{turv74,
> Author = {Turchin, V. F.},
> Title = {Ehkvivalentnye preobrazovanija programm na {Refale}
> ({Equivalent} transformations of {Refal} programs)},
> Journal = {Avtomatizirovannaja Sistema upravlenija stroitel'stvom. Trudy C
> Volume = {6},
> Number = {},
> Pages = {36--68},
> note = {(In Russian)},
> Year = {1974}
> }
>
[...]
> @InProceedings{Turchin:74,
> author = "Valentin F. Turchin",
> title = "Ehkvivalentnye preobrazovanija programm na {Refale}
> ({Equivalent} transformations of Refal programs)",
> booktitle = "Avtomatizirovannaja Sistema upravlenija stroitel'stvom. Trudy
> year = "1974",
> pages = "36--68",
> note = "(In Russian)"
> }
>
[...]
> @TechReport{Turchin:80:Courant,
> Author="Turchin, Valentin F.",
> Title="The language {R}efal, the theory of compilation and metasystem analysi
> Institution="Courant Institute of Mathematical Sciences, New York University"
> Number="20",
> Type="Courant Computer Science Report",
> Year="1980"
> }
[...]
> @Article{Turchin:86,
> author = "Turchin, Valentin F.",
> title = "The concept of a supercompiler",
> journal = TOPLAS,
> year = "1986",
> volume = "8",
> number = "3",
> pages = "292--325"
> }
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:24:58 MSD