Subject: Re: Об отсечениях внутри блока
From: Arkady Klimov (klark@bagirra.net)
Date: Mon Nov 27 2000 - 15:38:30 MSK
АРК:
Я присоединяю к данному письму ответ на вопрос, заданный мне Андреем К. См. внизу.
(Андрей, я почему-то не получил это твое исходное письмо.)
----- Original Message -----
From: Anton Yu. Orlov <orlov@mccme.ru>
To: Andrei Klimov <Andrei.Klimov@supercompilers.com>
Cc: <refal-plus@botik.ru>; Fedor Romanenko <fedor@blues.ru>
Sent: Saturday, November 25, 2000 9:16 PM
Subject: Re: Об отсечениях внутри блока.
| Здравствуйте, Андрей и Сергей!
|
| Прежде всего, хочу поблагодарить вас за замечательные ответы на мой вопрос
| и объяснение ситуации с той семантикой, которая сейчас принята. Тем не менее,
| мне бы не хотелось мириться с существующим положением вещей, и поэтому у меня
| есть предложение (см. ниже).
|
| 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?
| >
Сначала вопрос поставил меня в тупик, с одной стороны, потому, что я уже
не помню (давно это было), и к сожалению, в свое время
не доделал описание формальной семантики рефала-6: не распространил
ее на отсечения и заборы, которые уже были реализованы. А с другой стороны,
не сделал я этого не потому, что так уж это было бы трудно или некрасиво, а
потому, что мне тогда казалось, что этот элемент языка вообще лишний, а ввел
я его в стремлении достичь "совместимости" с рефалом Плюс. (Взял это слово
в кавычки, поскольку в строгом смысле она все равно не была обеспечена).
Я не мог (да и сейчас не взялся) бы четко обосновать это свое отношение, но
готов подписаться под всем тем, что высказал Сергей Романенко в своем
сегодняшнем письме на эту тему.
Возвращаясь к заданному вопросу, могу предложить выдержку из документации
(неформальной) по рефалу-6, из которой в принципе можно что-то вывести:
Для гибкого управления неуспехами вводятся знаки "/" и "\", которые могут ставиться между действиями.
Знак "/" усиливает неуспех, проходящий через него справа налево так, что этот усиленный неуспех не может быть перехвачен предшествующим образцом или очередным окончанием объемлющего блока. Таким образом, неуспех выходит на уровень вызова функции, где и теряет свою избыточную силу.
Знак "\" ослабляет усиленный неуспех, проходящий через него справа налево, после чего он может быть перехвачен обычным образом. Неуспех может быть многократно усилен при помощи нескольких знаков "/". В этом случае до полного ослабления он должен пересечь столько же знаков "\".
Рассмотрим действие знаков "/" и "\" в случае простого окончания, состоящего из участков A1 - A5 (каждый участок - последовательность действий):
A1 \ A2 \ A3 / A4 / A5
Неуспех в A5 может быть перехвачен только на участке A1, неуспех в A4 - на участках A2 и A1, но не в A3. Можно считать, что знаки "/" и "\", стоящие вдоль одного пути как бы образуют скобочную структуру: неуспех передается от правой скобки "/" сразу к соответствующей левой скобке "\". Чтобы не перепутать знаки "/" и "\" следует представлять себе, что усиленный неуспех проходит как бы снизу.
Напомню, что под "действием" здесь понимается образец, результат или блок (образцовый или результатный).
Здесь, к сожалению, явно не сказано, что при движении справа налево блоки обходятся, но это, конечно, подразумевается (поскольку ни о каком входе в блоки по неуспехам вообще нет речи). Подразумевается также, что если неуспех возник внутри блока, то при движении влево он может выйти за пределы блока через его начало - все блоки в рефале-6 прозрачны: изначально они вводятся лишь как средство группировки. Поэтому, как я понимаю, решение получилось именно то, которое и предложил Андрей К как "третий вариант".
Аркадий.
This archive was generated by hypermail 2b25 : Mon Nov 27 2000 - 15:41:16 MSK