Subject: Conditions in Refal-5.
From: Savtchenko Maxim (savmaxru@gcnet.ru)
Date: Fri Feb 06 2004 - 12:56:59 MSK
Вашему вниманию предлагается краткое изложение одной мыслишки. Идея
вобщем-то тривиальная и совершенно не принципиальная. Вполне возможно она
уже использовалась в каком-то из диалектов пятого рефала. Дальнейший текст я
постарался подготовить в форме статьи, чтобы отдать в какой-нибудь
факультетский сборник, если идея окажется свежей и стоящей.
Поехали...
Новый взгляд на структуру предложений в языке Рефал-5.
Традиционно принято считать, что расширенный Рефал (Рефал-5) отличается от
базисного Рефала (Рефал-2) наличием where-конструкций (условий) и
with-конструкций (блоков). Я предлагаю взглянуть на семантику предложений
Рефала-5 иначе.
По определению данному В. Ф. Турчиным:
"... where-конструкция ... накладывает дополнительное условие на
применимость предложения".
"Условие является сопоставляемой парой, где образцом (правым операндом)
может служить любое выражение-образец, а аргументом (левым операндом) может
являться любое РЕФАЛ-выражение; единственным ограничением для аргумента
является то, что он должен включать только те переменные, которые имеют
определенные значения на момент проверки условия (связанные переменные). Для
условия, которое непосредственно следует за левой частью предложения, это
требование означает, что в его аргументе могут использоваться только те
переменные, которые появляются в левой части предложения. Выражение-образец
в правой части условия может включать как связанные переменные, так и
свободные переменные, которые еще не были определены и получают значения в
процессе сопоставления.
В предложении могут встретиться несколько последовательных
where-конструкций. Условия, введенные таким образом, будут вычисляться
(проверяться) в заданной последовательности.
Пусть задано условие Е : P. Оно вычисляется следующим образом. Во-первых,
РЕФАЛ-машина порождает новое поле зрения, помещает Е в это поле и заменяет
переменные из Е их значениями. Затем машина работает, как обычно, над этим
полем зрения до тех пор, пока его содержимое пассивно. В процессе вычислений
могут порождаться дополнительные поля зрения. Когда процесс завершается,
результат сопоставляется с образцом Р. При этом сопоставлении те переменные
в Р, которые являются уже связанными, заменяются на свои значения, в то
время как свободные переменные принимают значения в процессе сопоставления.
Если сопоставление является успешным, вычисляется следующее условие; если
больше нет условий, имеет место замена левой части предложения на правую его
часть. Если сопоставление терпит неудачу, объявляется тупиковая ситуация в
предшествующем сопоставлении, (которое могло относиться как к условию, так и
к левой части сопоставления с образцом). В этом случае открытые переменные в
образце будут удлиняться до тех пор, пока это возможно. Если больше не
остается переменных, подлежащих удлинению, тупиковая ситуация снова
переносится на предшествующее сопоставление; если это происходит при
сопоставлении в левой части, предложение неприменимо, как и в базисном
РЕФАЛе, и испытывается следующее предложение. После того как проверка
условия завершается успехом либо неудачей, временное поле зрения, созданное
для Е, уничтожается, и РЕФАЛ-машина возвращается к полю зрения, из которого
вызывалось Е.
Таким образом, каждый образец в последовательности условий может присваивать
значения новым переменным, которые становятся связанными в последующих
условиях. В конце концов, все эти переменные получат значения и смогут быть
использованы в правой части предложения".
В таком же духе описана БНФ предложений в справочнике по Рефалу-5:
block ::= sentence
sentence ;
sentence ; block
sentence ::= left-side conditions = right-side
left-side conditions , block-ending
left-side ::= pattern
conditions ::= empty
, arg : pattern conditions
arg ::= expression
right-side ::= expression
block-ending ::= arg : { block }
То есть, нам предлагается видеть предложения без with-конструкций таким
образом:
left-side [, arg : pattern] ... [, arg : pattern] = right-side
А предложения с with-конструкцией таким образом:
left-side [, arg : pattern] ... [, arg : pattern] , arg : { block }
Квадратными скобками я выделил "смысловые атомы". Однако предложения можно
разбивать на простые составляющие и по-другому. Я предлагаю в качестве
"смысловых атомов" выделять не "условия", как это делается традиционно, а
"базовые предложения":
[pattern , arg] : ... : [pattern , arg] : [pattern = right-side]
или
[pattern , arg] : ... : [pattern , arg] : { block }
Такое разбиение является вполне осмысленным, если термин "базовое
предложение" определить следующим образом:
Базовое предложение (БП) - вычислитель над пространством полей зрения с
одним входом и потенциально бесконечным (N0) числом выходов. Под полем
зрения понимается объектное выражение плюс множество всех связанных
переменных с их значениями. БП определяется парой <P, A>, где P -
выражение-образец, а A - общее выражение. БП работает так:
На выходе 0 - результат подстановки в A переменных связанных во входном поле
зрения, а так же связанных в результате сопоставления P с входным полем
зрения.
Результат на выходе N получается из результата на выходе N-1 удлинением
открытых переменных в процессе сопоставления. Если больше не остаётся
переменных подлежащих удлинению, то на выходе N - неудача.
Пример:
БП - <e.1 s.X e.2 s.X e.3, e.1 e.2 e.3>
Вход - <'diffident', {}>
Выходы: 0 - <'iffient', {s.X='d', e.1='', e.2='iffi', e.3='ent'}>
1 - <'dffdent', {s.X='i', e.1='d', e.2='ff', e.3='dent'}>
2 - <'diident', {s.X='f', e.1='di', e.2='', e.3='ident'}>
3 - Fail
Легко видеть, что результат применения простого предложения (без where- и
with-конструкций) к строке равен результату на выходе 0 применения
соответствующего БП к полю зрения, составленному из исходной строки и
пустого множества связанных переменных. Для описания более сложных
предложений (с условиями и блоками) составим такую БНФ:
transformer ::= sentence
{ block }
block ::= sentence
sentence ;
sentence ; block
sentence ::= base-sentence (*)
base-sentence : transformer
base-sentence ::= pattern , expression
(*) - из соображений совместимости здесь должен быть вариант "pattern =
right-side", однако в нашем случае последнее БП функционально ничем не
отличается от остальных, и поэтому его не стоит выделять синтаксически.
В полученной модели предложения бывают двух видов: простые (рассмотрены
выше) и составные. Алгоритм работы составных предложений описывает следующий
псевдокод:
Применить base-sentence к входному полю зрения;
if (результат на выходе 0 base-sentence - неудача)
Вернуть неудачу;
I = 0;
while (неудачно применение transformer к результату на выходе I
base-sentence)
{
I = I + 1;
if (результат на выходе I base-sentence - неудача)
Вернуть неудачу;
}
Вернуть результат transformer;
Приведённый выше алгоритм рассматривает предложение как простую рекурсивную
структуру (похожую на плоские ЛИСП-списки) и поэтому имеет ряд преимуществ
по сравнению с традиционным алгоритмом. Он значительно уменьшает число
сущностей (достаточно сравнить старую и новую БНФ) и поэтому более прост для
программирования. Он более универсален, так как ему нет нужды различать
предложения с with-конструкцией и без неё. По этой же причине он
обеспечивает прозрачность блоков для неуспехов (одно из свойств Рефала-6 и
Рефала+) чем расширяет функциональность языка.
По изложенным причинам я считаю, что эта модель представления предложений
является предпочтительной при программировании интерпретаторов Рефала-5 и
его диалектов. Я собираюсь использовать её для создания диалекта Рефала-5 в
рамках проекта Intelib.
Конец статьи.
Благодарю за внимание.
Andrei Klimov <klimov@keldysh.ru> wrote:
> А по существу (если я правильно понял, что Вы имеете в виду),
> я могу только заметить, что подобная работа по "регуляризации"
> синтаксиса Рефала была проделана на рубеже 80-х и 90-х
> при разработке Рефала Плюс, а затем шлифовалась дальше
> в Рефале-6 (теперь это Refal-J -- Рефал над Явой).
Андрей, вы наверное обратили основное внимание на фразу:
"... в нашем случае последнее БП функционально ничем не отличается от
остальных, и поэтому его не стоит выделять синтаксически."
Вопрос синтаксиса в моей идее наименее существенен, замеченное вами имело
целью просто чуть-чуть упростить БНФ и никакой смысловой нагрузки не несло.
Мне интересно иное - пробовал ли кто-нибудь взглянуть на СЕМАНТИКУ
предложений немного с другой стороны. Рассмотреть работу предложения не как
"сопоставляем вход с левой частью и заменяем на правую, если выполняются все
условия", а как на работу соединённых в последовательную цепочку "базовых
предложений". По-моему, получается довольно красивая модель мышления, чем-то
напоминающая Пролог. Признаюсь в том, что я долго пытался придумать
осмысленный пример предложения, которое в новой семантике проще чем в
традиционной, но увы, видимо я слишком привык думать по старому :-(. Может
вы чем поможете.
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:24:59 MSD