Subject: Re: unarnoe vychitanie
From: Sergei M. Abramov (at home) (abram@botik.ru)
Date: Sun Oct 15 2000 - 19:53:29 MSD
День добрый, Валентин Федорович!
Я позволил себе копию для общественности...
>Ja vernulsja iz otpuska i pogruzilsja v e-mail.
Рад Вас слышать!
>Pravil'no li ja ponjal chto u tebja s Antonom
>proshlo URA-obrashchenije unarnogo
>slozhenija v vychitanije?
Да, похоше на то--прошло.
Автор Антон, и я не сильно понимаю детали (реализации).
Н примерно так.
(1) Ура для язычка TSG бы переписан с Хаскеля на Рефал-5;
(2) Потом была двухмесячная война, чтобы Scp4 "прожевал" эту суперкомпиляцию.
Здесь очень помогла поддержка АНдрея!
Думаю, Антону, и АНдрею, и Scp4 -- всем было полезно: как я понял на этой задаче
вылезли явные новый ошибки в Scp4 и АНдрей их исправил.
Короче говоря: с любой стороны -- серьезный и полезный тест на суперкомпиляцию.
Ну и Ура "подкручивался" -- сначала из него выкинули все, что не используется в
задаче унарбного сложения... Потом, вроде бы, возвращали все это обратно (но не
уверен, что все вернули ;-).
Вот эту деталь я и не ведаю:
1?. насколько сегодня Ура TSG/Рефал-5 далек от исходного (Ура TSG/Хаскелл)?
2?. Не выкинуто ли теперь из Ура чего-то важного, так, что теперь Ура не
универсальный (способен работать только для бинарного сложения, например? ;-)
3?. Вообще говоря, на данной задаче исконный (Хаскелный) Ура ведет себя так:
выдает (единственный) ответ, а затем ищет (бесконечно) другие ответы (которых
нету). Меня удивило, что Scp-4 преобразовало "это самое" в Рефал-программу,
которая всегда терминируется.
(3) Но это детали (разберемся). А факт, что после суперкомпиляции Ура (внутри
которого стояло TSG-программа унарного сложения) автоматически получена
Рефал-программа, которая действительно делает унарное вычитание...
Прилагаю таблицу вычитания [0..3]x[0..3] и текст программы (все что ниже
"=========" -- построил Scp-4, выше--я написал "пускач").
У программки забавная структура: два невложенных цикла с аккамулятором.
"Чистое" вычитание построить способен только ScpWalk (слияние двых невложенных
циклов). По этому поводу я в конце цитирую себя (из переписки с Робертом: прдон
за варварский английский, Роберт терпит...)
>Eto gde-nibud' izlozheno? Mozhno posmotret'?
Пока это нигде не изложено, кроме как в письмах (которые Вы видели).
Я очень хочу, чтобы Антон добил это до публикуемого вида.
А для застолбления приоритета я готов в одну из двух (до конца года) пишущихся
мною с Робертом статей вставить (попробовать вставить) секцию (два-три-четыре
абзаца)---сухой отчет о том, что:
"Тогда-то и тогда-то... на Scp-4 ...те-то и те-то... сделали ...то-то и
то-то... Результат--см. на картинке."
Но это требует небольшого "до"-вылизывания результата.
Удачи, низкий поклон Вам и Татьяне Ивановне!
Сергей
=================== 1 ====================
(1) A student ---a yang refalists from Moscow State
University,--was fighting during last two months (after the Summer school)
with:
Scp4 <Ura AddUn [ e.1, Xe_1 ]::Class e.2>
where
Scp4 -- current version of (Refal5->Refal5/Refal5)-supercompiler;
(*** In fact, there are two backends, so it's possible output Refal5 or Refal+
code from Scp4. I prefer Refal+ dialect ***)
Ura -- (TSG/Refal5)-ura: manually rewritten ura from Haskell to Refal5;
AddUn-- unary addition.
Today the result is:
Scp4 returns small enough Refal+ program, that is unary-subtraction.
The structure of the program is:
INV-REF tX tY -- main function;
F1 ...Z... ...X... ...Y... -- first loop
F1 is decreasing Y, increasing Z (initialized as ("XE" 1) ;-)
when Y==0, the F2 is started
Thus F1 is just "reverse" of Y, and Z == Y in F2 (in some sense).
F2 ...Z... ...X... -- second loop
F1 is decreasing X and Z by one
when Z is ("XE" 1) the rest of X is the result.
Please note:
F1-loop is residual for ppt development recursion;
F2-loop is residual for Clash (unification) recursion.
A one-loop subtraction program cannot be achieved by Scp4 -- for this goal we
need... Yes, ScpWalk-technology!
I am not sure in the details, and I need a discussion with the student:
-- is Ura the perfectly rewritten from Haskell (may be some
``simplification'' was made);
-- is it possible improve the result to support automatic TSG-backend for
Scp4 (to output Refal-graph as TSG-program)
-- etc.
After then, maybe in some paper we can just add a few words about ``the first
inverse compilation was .... by ....''.
=================== 2 ====================
>> Scp4 <Ura AddUn [ e.1, Xe_1 ]::Class e.2>
[...]
>>Please note:
>> F1-loop is residual for ppt development recursion;
>> F2-loop is residual for Clash (unification) recursion.
>>
>>A one-loop subtraction program cannot be achieved by Scp4 -- for this goal we
>>need... Yes, ScpWalk-technology!
>
>Very interesting structure. There may be several sources for this effect...
The ura structure is following:
-- regursion(s) from root to the leaves with >>accamulating<< all splits;
-- then clash -- also recursion, if $d_out$ is not atom
(is a list [_, _, ....]).
Thus we have classic ``two unnested iteration with accamulator'' -- this is
subject for ScpWalk.
>... for example, is URA flat itself a flat/recursive program, is it
>organized breadth/depth-first, how is unary addition written
>(flat/recursive) ...
Yes! I know that the student has a lot of experiments of this kinds and try all
permutations over Scp4 options (lazy/strict, etc...) In most cases he has huge
residual program...
This is the best what he reached now.
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:24:58 MSD