Subject: Re: Об отсечениях внутри блока
From: Andrei Klimov (Andrei.Klimov@supercompilers.com)
Date: Sat Nov 25 2000 - 00:18:38 MSK
Антон и Сергей, добрый день!
Большое спасибо за интереснейший пример на тонкости
Рефала Плюс! Жизнь такова, что сложностей нет только
у слабых языков, скажем, у машины Тьюринга. ;-)
А все-таки хочется разобраться по существу:
Интересно, из каких соображений была выбрана такая семантика? --
0 |- S
k |- R
--------
k |- S R
Это было сделано просто ради какого-то частного упрощения или
возникают какие-то нетривиальные "противоречия"?
Задав вопрос, сам же попытаюсь дать на него ответ.
Для начала обобщим пример, наставив букв, обозначающих
некоторые правильные фрагменты программы:
A \? B \{ C \! D; E}, F;
Теперь представим операционную семантику, то есть процесс вычислений.
После вычисления A проходим \?. Это означает, что в стеке
возвратов отмечается текущее точка. После того, как
пройдем С и \!, стек возвратов будет сброшен до этой точки.
В результате, возвраты из D пойдут куда-то в A, а не в C или E.
Хитро, но пока все разумно: именно для таких "трюков"
и были \? и \! внесены в язык.
А вот с F -- тонкость:
- куда должны идти возвраты из F: в B или сразу в A?
Если не заглядывать в скобки (понадеявшись на
"композиционность" языка -- то есть, что вложенные конструкции
в разумных пределах не влияют на семантику объемлющих),
то наивно хочется, чтобы возвраты из F шли в B.
- А если мы попали в F, пройдя С \! D, то что?
Операционная семантика подсказывает, что
стек уже сброшен до уровня, отмеченного знаком \?.
- А если мы попали в F, сделав возврат из C на Е и выйдя
из скобок без отсечения возвратов, то что?
Операционная семантика подсказывает, что
стек возвратов не сбрасывался, и из F можно вернуться в C.
Получаем противоречие принципу (использованному в Рефале Плюс),
что в каждой точке статически известно, куда идут возвраты.
Какие могут быть способы снять это противоречие?
Мне в голову приходят 2:
1) Тот, что приняли авторы Рефала Плюс:
Продолжение пути после \{...} требует, что внутри скобок
\? и \! были сбалансированы. То есть в этом случае
блок целиком не отсекает возвраты.
Что здесь нам режет глаза? -- То, что свойства блока
определяются не фактом закрытия в скобки,
а наличием продолжения после правой скобки.
То есть, как бы различаются два вида скобок \{...}
- \{...}; -- те, после которых идет точка с запятой
- \{...}, и \{...}: -- те, после которых стоит запятая или двоеточие
Ну, что ж: два вида так два. Если на самом деле надо столько,
чтобы обеспечить желаемую семантику, то пусть будут.
Можно считать, что по логике все нормально,
а претензии -- к дизайну Рефала Плюс.
2) Но можно обобщить и довести "до точки и до ручки":
Как известно, в конце путей перед всеми точками с запятой
подразумевается необходимое число закрытий стека \!.
Это правило можно обобщить, чтобы правые скобки --
и перед точкой с запятой, и запятой, и двоеточием, --
всегда подразумевали закрытие стека возвратов.
А до какого уровня? - Здесь возможны варианты.
Рассмотрим самый "смелый":
Правые скобки закрывают стек возвратов до максимального
уровня вхождений \! в тело блока -- так, чтобы можно
было говорить о "глубине отсечения" для блока целиком.
Звучит разумно и "композиционно". По логике все чисто.
А что же здесь плохого, что авторы Рефала Плюс не решились
пойти на этот вариант (не считая, что они до него "не догадались")?
Я не автор, но с большой вероятностью берусь предсказать их ответ:
Слишком много подразумеваний,
а правило снятия этих подразумеваний слишком сложное:
нужно найти все \! в теле и вычислить максимум их вложений.
Но заметим, что критика этого решения не по _логике_ языка, а по _дизайну_.
Находясь в рамках той же логики, можно попытаться улучшить дизайн:
Как и в нынешней семантике, все операторы
(как простые, так и составное) и пути
характеризуется "глубиной отсечения стека":
- все простые кроме \! -- 0
- \! -- 1
- путь -- сумма числа \! за вычетом соответствующих \?
- блок \{...; ...; ...;} -- глубина отсечения каждого пути,
при условии, что они _равны_.
(Если не равны, компилятор выдает ошибку).
По логике вроде бы все разумно,
но дизайн все равно труден для человека.
Вот поэтому (смею предположить) авторы Рефала Плюс
и пошли на компромиссный вариант с ограничением:
- В теле блока, стоящего в конце пути, -- \{...}; -- можно
отсекать возвраты (иначе этот механизм обесценивается).
- Блоки, стоящие в середине пути, -- \{...}, и \{...}: --
всегда имеют "глубину отсечения" равную 0.
Что и объясняет, откуда взялся 0 в правилах, приведенных Сергеем:
0 |- S
k |- R
--------
k |- S R
Аркадий, интересно, а какое решение ты принял в аналогичном месте Рефала-6?
Ну, а по поводу вреда формальных спецификаций при разработке
языков -- я бы не согласился. Дело не в спецификациях как таковых,
а в их "правильном" использовании без "болезней левизны" и "перегибов". ;-)
Естесвенно, когда в процессе шлифовки семантики формальной
системы подбирается и средства описания семантики.
И конечно, их "синэнергизм" часто получается далеко не сразу.
Живое использование приводит к дальнейшему развитию.
Что и происходит сейчас с Рефалом Плюс!
Успехов!
Андрей.
----- Original Message -----
From: "Sergei Romanenko" <roman@integrum.ru>
To: "Anton Yu. Orlov" <orlov@mccme.ru>
Cc: "Ruten Gurin" <ruten@caspur.it>; <refal-plus@botik.ru>; "Andrei Klimov" <andrei.klimov@supercompilers.com>; "Fedor Romanenko"
<fedor@blues.ru>
Sent: Friday, November 24, 2000 14:11
Subject: Re: Об отсечениях внутри блока.
>
> ----- Original Message -----
> From: "Anton Yu. Orlov" <orlov@mccme.ru>
> To: "Sergei Romanenko" <roman@integrum.ru>
> Cc: <refal-plus@botik.ru>
> Sent: Friday, November 24, 2000 9:27 AM
> Subject: Об отсечениях внутри блока.
>
> > У меня к Вам следующий вопрос по Рефалу+. Если попытаться
> > скомпилировать такую программу:
> > Main = \? \{ \!; },;
> > то компилятор выдаст ошибку: ERROR: '\!' without corresponding '\?'.
> > Дело здесь в последней запятой. Если ее убрать, то все будет хорошо. В
> > книжке по P+ я не нашел соответствующих ограничений на такое
> > использование отсечений. Это ошибка в компиляторе?
>
> Ну что, же... Этот пример лишний раз свидетельствует, что дизайн Рефала
> Плюс - слишком утонченный и заумный. Заодно это показывает ВРЕД
> использования формальных спецификаций при разработке языков! (Хотя, конечно,
> спецификации полезны для фиксации смысла языка после того, как его
> разработка закончена.)
>
> Язык должен быть таким, чтобы его смысл был интуитивно понятен простому
> народу, и чтобы его конструкции мжно было объяснить "на пальцах", без
> привлечения формальных спецификаций.
>
> При этом наблюдается интересная закономерность: если язык прост и понятен с
> точки зрения здравого смысла, то его формальная спецификация, как правило,
> оказывается вычурной и утонченной. И наоборот, изящные спецификации обычно
> генерируют нечто контро-интуитивное...
>
> (Кстати, ведь процесс обучения математике, в основном и состоит в том, чтобы
> поставить обучаемого на уши: чтоб он ходил не ногами, а на руках. Чтобы
> тривиальное ему показалось сложным, и заумное - простым и естественным.
> "Точка - это то, что не имеет частей, линия - это длина без ширины", и т.п.)
>
> Если же вернуться к вышеприведенной программе, то ей соответствует следующее
> правило вывода из (Глава 2, раздел 13.5):
>
> 0 |- S
> k |- R
> --------
> k |- S R
>
> Т.е. "\{ \!; }" - это "источник" S, а "," - это "хвост" R. Из правила вывода
> следует, что, с точки зрения отсечений, S рассматривается как находящийся на
> уровне 0, а R - на уровне k. Поэтому компилятор пожаловался правильно.
>
> (Впрочем, если я сам запутался в спецификации, то не возражаю, если меня
> поправят...)
>
> Сергей
This archive was generated by hypermail 2b25 : Thu Nov 30 2000 - 07:25:22 MSK