Subject: Re: SURA: от нас с Робертом всем -- трократное, симметричное URA
From: Arkady Klimov (klark@bagirra.net)
Date: Wed May 09 2001 - 15:07:31 MSD
Всем привет,
Сергей, спасибо.
Я попробую начать с самого простого примера. Но может реальные УРА, и старый и новый, уже такие, что это для них не проблема, не знаю, я исхожу из отстоявшегося у меня с 70-х образа "простого" УРА.
Имеем функцию
Rev {
s1 e2 = <Rev e2> s1;
=;
}
(прошу прощения, мне лень ставить точки в переменных)
Сначала рассмотрим задачу: <Rev ex> = 'abc'. Очевидно, что любой УРА с ней легко справляется и выдает, что есть одно и только одно решение: ex = 'cba'.
А теперь рассмотрим задачу: <Rev <Rev ex>> = 'abc'. Как мне кажется, сидящий у меня в голове УРА выдаст решение ex = 'abc', а потом будет бесконечно долго крутиться, пытаясь найти другие. И в этом и состоит проявление в данном случае той "проблемы композиции", о которой я писал. Наверно, можно подобрать и более хитрые примеры, причем не обязательно опирающиеся на возможность работы с выражением с обоих концов, как в этом примере.
Алик.
PS. К стыду должен признать, что не все понимаю в написанном Сергеем, а в статьях разбираться то ли слабо, то ли недосуг пока.
PPS. Сергей, у меня одно небольшое лингвистическое предложение: слово "лизон" по русски выглядит как-то неприлично, может лучше писать его "лиезон", или "лиазон", как больше нравится - первое ближе к произношению (ударение на е), второе - к написанию (liaison - в английском, про французский, чье это слово, ничего не могу сказать, может знатоки меня поправят). И для непосвященных в наш лексикон наверно будет узнаваемее.
----- Original Message -----
From: Sergei M. Abramov (at home)
To: Arkady Klimov ; refal
Sent: Tuesday, May 08, 2001 10:47 PM
Subject: Re: SURA: от нас с Робертом всем -- троекратное, симметричное URA!
День добрый, всем!
From: Arkady Klimov <klark@bagirra.net>
И что меня в этом подходе заинтриговало: не получится ли теперь "на УРА" композиция? Была, мне кажется, такая слабость у УРА: композиция функций, каждая из которых в отдельности решается легко, вместе могут составлять очень сложную проблему. А как с этим теперь обстоит? (Прошу прощения, что не могу столь же четко и ясно, как Сергей, выразить свою мысль).
Алик, попробую нащупть ответ:
1.. Я не до конца понял проблему. Если кто вспомнит конкретную задачу (пример)--будет легче.
2.. С композициями в TSG не очень здорово--язык хвостово-рекурсивный (плоский);
3.. Возможно вот о чем речь (это еще одна заготовка в закромах Родины--ну да среди своих...расскажу ;-)
Если язык не плоский, то любая (не только листовая) конфигурация имеет вид (пардон, я все про свои лизоны, SCPJ-шники меня поймут, у них конфигурация точно такая-же, в некотором смысле):
let [v1.1, ...,v1.k1] = F1(e1.1,....e1.n1) [v2.1, ...,v2.k2] = F2(e2.1,....e2.n1)
...
[vm.1, ...,vm.km] = Fm(em.1,....em.n1)in
[e(m+1).1,.....,e(m+1).k(m+1)]
Здесь v*.* -- лизон-переменные, e*.* -- выражения с с-переменными и с лизонами (определенными выше использования в e*.*).
Тогда можно, построив (ТАВ) класс достижимости cls_i для данной вершины-конфигурации, построить апроксимацию сверху всех IO-классов в таблице ТАВ, получаемых здесь и ниже этой вершины:
clsio_j = io( cls_i, [e'(m+1).1,.....,e'(m+1).k(m+1)])
где e'i.j получен из ei.j заменой всех лизонов v*.* на свежие (уникальные) с-переменные. Если пересечение clsio_j с желаемым clsiо пустое:
null (clsio *. clsio_j)
то нет никаких шансов, что под данной вершиной будет хоть какой-то ответ -- все поддерево можно откинуть. Это дает отсечение заведомо бесперспективных деревьев (в том числе--бесконечных).
Это (иногда) повысит скорость и повысит терминируемость SURA (пардон за терминалогию--все равно останется нетерминируемость и неразрешимость терминируемости, конечно).
Но это все штуки для вложенных языков (проект XSG как-то движется...)
From: korlyukov <korlyukov@grsu.grodno.by>
Но,... хоть какой-нибудь примерчик для прояснения существа дела для таких, как я, не очень знающего всю предысторию УРА. Чтоб на нем (примере) было видно, чем результат работы старого УРА отличается от результата работы симметричного УРА. Не буду возражать, если ответ будет послан по всему списку.
Тут по сути все просто: речь идет о расширении форматов решаемых задач.
Старый УРА умел решать только такие уравнения относительно С-переменных:
prog c-exps = const
где c-exps -- c-выражения (ну, с параметрами, рефальский образец), const -- данные (без с-переменных).
Пример уравнения, подвластного старому УРА:
(perm2 X (001 002 003 004 005 006 007)) = (002 003 004 005 006 007 001)
где perm2 -- программа вычисления двойного применения перестановки Х1 к элементам списка (001 002 003 004 005 006 007)
У нового (симметричного) УРА можно писать переменные слева и справа от знака равно. Можно и повторные. Тем самым, все старые примеры по формату доступны и новому УРА, но можно еще писать и такой пример:
(digits X1) = X1
где (digits A) ==> B -- вот такая функция: она берет число A и строит новое число В, у которого первая цифра равна тому, сколько в А было нулей, вторая цифра тому--сколько в А было единиц и т.д.
В старом УРА такой пример тоже бы взялся бы, но через Альпы -- за счет трюка: пришлось бы ручканми громоздить функцию EQ, строить бы композицию и решать такое вот уравнение:
(EQ (digits X1) X1) = True
В конце письма привожу пару (ну очень классических) примеров на УРА --- как для старого, так и для нового эти примеры подходят.
Ссылка на PDF рассматриваемой статьи:
http://www.futamura.info.waseda.ac.jp/~glueck/URA/AbrGlu2.pdf
Очень много примеров в китайской статье (нежное введение в обычный УРА, ссылка дается на вариант статьи до ее обработки китайскими верстальщиками):
http://www.botik.ru/~abram/AbrGlu-China.pdf (203,931 байтов)
Удачи
Сергей
------------------------------------------------------------------------------
Не в пику, а как секция Related Works:
Замечу, что все игры с УРА очень похожи на красивую серию Корлюкова "инвертирование при помощи SCP" за исключением некоторых разниц:
1.. УРА намного примитивнее SCP.
2.. В УРА не нужно писать подпрограммку EQ, которая пишется из примера в пример в SCP-инверсиях (при этом, в SCP надо каждый раз еще сообразить, с какой стороны--слева или справа,--надо сравнивать на равенство...)
3.. Про УРА все теоремы доказаны, все свойства известны. Про SCP... ну, вообще говоря, SCP расширяет область определения функций. Посему, в примерах "SCP-для-инверсии"
a.. либо надо озаботиться, что все входные функции (которые мы SCP-руем ради инверсии) были бы тотальными (что не есть верно для многих примеров),
b.. либо надо каждый "ответ" затем подставлять в уравнение и проверать (у нас в принципе могут быть лишние ответы--то бишь, SCP говорит <F Вася>=True, однако исходная функция не определена на Вася.... Особенно тяжело подставлять в исходную функцию выражения с с-переменными. Особенно, когда SCP смело обобщает такую функцию:
F { s1 ex = s1 <F ex>;
= ;
};
до такой:
F { ex = ex };
Как тут отсеять "лишние ответы" (на скобках исходная программа не определена)?
------------------------------------------------------------------------------
Мatch--наивная проверка вхождения подстроки в строку. При помощи УРА решаются две задачи "Что есть подстроки строки ABC?" и "Что не есть подстроки строки AАА?".
Переменные--почти как в рефале: Xe.i -- е-переменная (произвольный лисп-список); Xа.i -- атомарная переменная.
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:24:59 MSD