Subject: Re: Об отсечениях внутри блока
From: Anton Yu. Orlov (orlov@mccme.ru)
Date: Sat Nov 25 2000 - 21:16:08 MSK
Здравствуйте, Андрей и Сергей!
Прежде всего, хочу поблагодарить вас за замечательные ответы на мой вопрос
и объяснение ситуации с той семантикой, которая сейчас принята. Тем не менее,
мне бы не хотелось мириться с существующим положением вещей, и поэтому у меня
есть предложение (см. ниже).
Andrei Klimov wrote:
> Антон и Сергей, добрый день!
>
> Большое спасибо за интереснейший пример на тонкости
> Рефала Плюс! Жизнь такова, что сложностей нет только
> у слабых языков, скажем, у машины Тьюринга. ;-)
>
> А все-таки хочется разобраться по существу:
> Интересно, из каких соображений была выбрана такая семантика? --
>
> 0 |- S
> k |- R
> --------
> k |- S R
>
> Это было сделано просто ради какого-то частного упрощения или
> возникают какие-то нетривиальные "противоречия"?
>
> Задав вопрос, сам же попытаюсь дать на него ответ.
> Для начала обобщим пример, наставив букв, обозначающих
> некоторые правильные фрагменты программы:
>
> A \? B \{ C \! D; E}, F;
>
> Теперь представим операционную семантику, то есть процесс вычислений.
> После вычисления A проходим \?. Это означает, что в стеке
> возвратов отмечается текущее точка. После того, как
> пройдем С и \!, стек возвратов будет сброшен до этой точки.
> В результате, возвраты из D пойдут куда-то в A, а не в C или E.
> Хитро, но пока все разумно: именно для таких "трюков"
> и были \? и \! внесены в язык.
>
> А вот с F -- тонкость:
> - куда должны идти возвраты из F: в B или сразу в A?
>
> Если не заглядывать в скобки (понадеявшись на
> "композиционность" языка -- то есть, что вложенные конструкции
> в разумных пределах не влияют на семантику объемлющих),
> то наивно хочется, чтобы возвраты из F шли в B.
Да, это именно так. И, кажется, есть способ этого добиться (см. ниже).
Сразу хочу сделать замечание о целесообразности вообще рассмотрения семантики
отсечений, отличной от существующей. У меня уже неоднократно возникало желание
использовать отсечения таким образом. Это желание (как я понимаю после
предыдущего прекрасного объяснения) возникало в тех случаях, когда возвраты в B
автоматически становятся возвратами в A (например, когда B просто отсутствует).
И всякий раз приходится как-то выкручиваться. Особенно неприятна в этом смысле
ситуация, когда хочется сделать возврат из блока, котырый инциализуриет
какие-нибудь переменные в последующем паттерне, после чего идет долгое
вычисление, использующее эти переменные. Поэтому я и задал свой вопрос
(невнимательно, как выяснилось, прочитав книжку ;-).
>
>
> - А если мы попали в F, пройдя С \! D, то что?
>
> Операционная семантика подсказывает, что
> стек уже сброшен до уровня, отмеченного знаком \?.
>
> - А если мы попали в F, сделав возврат из C на Е и выйдя
> из скобок без отсечения возвратов, то что?
>
> Операционная семантика подсказывает, что
> стек возвратов не сбрасывался, и из F можно вернуться в C.
>
> Получаем противоречие принципу (использованному в Рефале Плюс),
> что в каждой точке статически известно, куда идут возвраты.
>
> Какие могут быть способы снять это противоречие?
>
> Мне в голову приходят 2:
>
> 1) Тот, что приняли авторы Рефала Плюс:
>
> Продолжение пути после \{...} требует, что внутри скобок
> \? и \! были сбалансированы. То есть в этом случае
> блок целиком не отсекает возвраты.
>
> Что здесь нам режет глаза? -- То, что свойства блока
> определяются не фактом закрытия в скобки,
> а наличием продолжения после правой скобки.
> То есть, как бы различаются два вида скобок \{...}
> - \{...}; -- те, после которых идет точка с запятой
> - \{...}, и \{...}: -- те, после которых стоит запятая или двоеточие
>
> Ну, что ж: два вида так два. Если на самом деле надо столько,
> чтобы обеспечить желаемую семантику, то пусть будут.
> Можно считать, что по логике все нормально,
> а претензии -- к дизайну Рефала Плюс.
>
> 2) Но можно обобщить и довести "до точки и до ручки":
>
> Как известно, в конце путей перед всеми точками с запятой
> подразумевается необходимое число закрытий стека \!.
> Это правило можно обобщить, чтобы правые скобки --
> и перед точкой с запятой, и запятой, и двоеточием, --
> всегда подразумевали закрытие стека возвратов.
> А до какого уровня? - Здесь возможны варианты.
> Рассмотрим самый "смелый":
>
> Правые скобки закрывают стек возвратов до максимального
> уровня вхождений \! в тело блока -- так, чтобы можно
> было говорить о "глубине отсечения" для блока целиком.
>
> Звучит разумно и "композиционно". По логике все чисто.
> А что же здесь плохого, что авторы Рефала Плюс не решились
> пойти на этот вариант (не считая, что они до него "не догадались")?
> Я не автор, но с большой вероятностью берусь предсказать их ответ:
>
> Слишком много подразумеваний,
> а правило снятия этих подразумеваний слишком сложное:
> нужно найти все \! в теле и вычислить максимум их вложений.
>
> Но заметим, что критика этого решения не по _логике_ языка, а по _дизайну_.
> Находясь в рамках той же логики, можно попытаться улучшить дизайн:
>
> Как и в нынешней семантике, все операторы
> (как простые, так и составное) и пути
> характеризуется "глубиной отсечения стека":
> - все простые кроме \! -- 0
> - \! -- 1
> - путь -- сумма числа \! за вычетом соответствующих \?
> - блок \{...; ...; ...;} -- глубина отсечения каждого пути,
> при условии, что они _равны_.
> (Если не равны, компилятор выдает ошибку).
>
> По логике вроде бы все разумно,
> но дизайн все равно труден для человека.
>
> Вот поэтому (смею предположить) авторы Рефала Плюс
> и пошли на компромиссный вариант с ограничением:
>
> - В теле блока, стоящего в конце пути, -- \{...}; -- можно
> отсекать возвраты (иначе этот механизм обесценивается).
> - Блоки, стоящие в середине пути, -- \{...}, и \{...}: --
> всегда имеют "глубину отсечения" равную 0.
>
> Что и объясняет, откуда взялся 0 в правилах, приведенных Сергеем:
>
> 0 |- S
> k |- R
> --------
> k |- S R
>
На мой взгляд, есть еще третий вариант, который представляется вполне
разумным. Он состоит в том, что блок всегда характеризуется "глубиной отсечения
стека" равной 0, но отсекать возвраты в нем все равно можно ;-). Т.е. после
прохождения блока тропа оказывается на том же уровне, что и до блока,
независимо от находящихся в нем отсечений. Иначе говоря, всякое отсечение
действует только до конца текущего предложения (в терминах абстрактного
синтаксиса; в терминах статьи Сергея Романенко про компиляцию в виртуальный
код, до конца текущего предложения или текущей тропы). Такая семантика
совпадает с принятой, в случае, если блок - это последнее действие в
предложении, и добавляет приятную возможность, в случае неуспеха "выброситься"
куда-нибудь даже из источника. И "дизайн", вроде бы, достаточно прост для
написания/понимания программ.
С уважением,
Антон.
> Аркадий, интересно, а какое решение ты принял в аналогичном месте Рефала-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 : Sat Nov 25 2000 - 21:10:56 MSK