OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Пятница, 19 Апрель, 2024 04:29

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 85 ]  На страницу Пред.  1, 2, 3, 4, 5  След.
Автор Сообщение
СообщениеДобавлено: Пятница, 14 Май, 2010 00:40 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
Цитата:
Зачем нужна альтернативная форма цикла Дейкстры, понять я так и не смог.

Нет никакой. LOOP - это не дейкстрин цикл.
Код:
Оптимизации в том смысле, что операнды конъюнкции в охранах могут быть сложными и вычисляться с побочными эффектами.

Побочный эффект - изменение процедурой нелокальных переменных. Тут я сильно думаю. В контексте модулей - это могут быть поля в модуле - и только. Хотя у меня такое чувство, то побочный эффект вообще запретить полезо было бы. И посмотреть, что получится. :)
Код:
Например, некое условие может получаться как OUT-результат процедуры.

Это не побочный эффект, а нормальное условие... :)
Код:
Во-первых, допускаются несколько веток. Для конкретности пусть будет ключевое слово BRANCH:
[code]
LOOP
   последовательность операторов
BRANCH
   последовательность операторов
......
END
[/code]
Начинаем выполнение в точке сразу после LOOP, куда возвращаемся после выполнения последовательности в любой ветке.

Смущает слово "любой". А если веток несколько?
Цитата:
Дальше: EXIT запретить, но вместо него требовать, чтобы в каждой ветке -- и обязательно только на самом верхнем уровне -- присутствовал хотя бы один оператор "охраны", аналогичный ASSERT, например, в таком виде:
GUARD( логич. условие );
Смысл оператора: при выполнении условия выполнение ветки продолжается;
в противном случае попадаем в точку сразу после следующего BRANCH, а если такого нет, то последнего END.

GUARD ничем не отличается от обычного expr/ Хотя для пущего подчеркивания смысла "охранны" может и пойдет.
А branch напоминает, и сильно, goto... :)

Цитата:
Например, лин. поиск
Код:
WHILE (ограничение поиска) & ~(условие поиска) DO
   перейти к след. кандидату
END;

переписывается так:
[code]
LOOP
GUARD( ограничение поиска );
GUARD( ~(условие поиска) );
перейти к след. кандидату
END

Ну да. Сложное условие разбивается на ряд более простых. Ошибок меньше совершается.

Цитата:
Можно и вообще выкинуть LOOP, разрешив такой GUARD в обычном WHILE ... DO ... ELSIF ... DO ... END

Ну так о том и речь. LOOP у нас только здесь, а WHILE у нас - везде!


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 14 Май, 2010 09:02 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Еще раз: в сложном расчете достаточно громоздкие части выражения в охране могут снова использоваться дальше. Редко, но бывает.

С.Г. прав, что раз они сложные, проблема оверхеда на вызов функции вроде как теряет остроту. Но зато появляется некая проблема разфокусирования взгляда программиста, когда чтобы разобраться с циклом, нужно лезть в какие-то отдельно стоящие процедурки-функции, да еще с побочными эффектами (хотя все эти побочные эффекты предполагаются локализованными в достаточно небольшом контексте).

То, что я предложил, выглядит достаточно гармонично -- нет ни разброса внимания, ни нарушений структурности.

Ведь выход один, и условия на выходе жестко определяются самими GUARD'ами, не считая побочных эффектов -- но тут это на том же уровне, на котором вообще побочность разрешена в Обероне.


--
В.Л.: да, из конца любой ветки возвращаемся в точку после LOOP. Ср. моделирование цикла Дейкстры в Компонентном Паскале (Приложение С в новых Алгоритмах и структурах данных):

LOOP IF ... THEN
...
ELSIF ... THEN
...
ELSE EXIT END END;


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 14 Май, 2010 09:13 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Валерий Лаптев писал(а):
Цитата:
Зачем нужна альтернативная форма цикла Дейкстры, понять я так и не смог.
Нет никакой.
"никакой" -- это про что?

Валерий Лаптев писал(а):
LOOP - это не дейкстрин цикл.
Это тут при чем?

Валерий Лаптев писал(а):
Цитата:
Например, некое условие может получаться как OUT-результат процедуры.

Это не побочный эффект, а нормальное условие... :)
Если условие нужно запихнуть в операнд, а процедура вычисляет что-то, и об успехе-неуспехе сообщает через OUT, то то, что она вычисляет, является с точки зрения вычисления логического условия побочным эффектом.

Валерий Лаптев писал(а):
Ну так о том и речь. LOOP у нас только здесь, а WHILE у нас - везде!
О чем "о том"?


Последний раз редактировалось Info21 Пятница, 14 Май, 2010 13:27, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 14 Май, 2010 12:35 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
Ага, прояснилось.
1. Я думал, что вы LOOP считаете каким-то вариантом дейкстриного цикла.
2. Начет побочного эффекта как результата выходного параметра. Да, это побочный эффект. Но при этом пройцедура должна все равно возвращать результат типа boolean, чтобы участвовать в логическом выражении. И тут еще интересный момент:
Код:
function(a) & a

Вопрос о порядке вычисления выражений, сокращенных вычислениях и вообще, допускать ли такую фигню... :)
3. к тому, что лучше все же while в силу его повсеместной распространенности.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 14 Май, 2010 13:29 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Валерий Лаптев писал(а):
Но при этом пройцедура должна все равно возвращать результат типа boolean, чтобы участвовать в логическом выражении.
А я о чем, когда говорил, что приходится "оборачивать"?

Валерий Лаптев писал(а):
3. к тому, что лучше все же while в силу его повсеместной распространенности.
А это к чему?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 14 Май, 2010 13:41 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл
Info21 писал(а):
Например, лин. поиск
Код:
WHILE (ограничение поиска) & ~(условие поиска) DO
   перейти к след. кандидату
END;

переписывается так:
Код:
LOOP
GUARD( ограничение поиска );
GUARD( ~(условие поиска) );
   перейти к след. кандидату
END
Долго думал и укрепился во мнении, что никаких других вариантов LOOP не должно быть нужно при систематическом построении циклов.

Можно и вообще выкинуть LOOP, разрешив такой GUARD в обычном WHILE ... DO ... ELSIF ... DO ... END,
-- вряд ли WHILE TRUE будет накладно, а может и компилятору будет нетрудно интерпретировать такое как чистый LOOP.
по-моему стоит сильно подумать, перед тем как выкидывать LOOP, который явно обозначает особый случай оптимизиации... Если разрешить GUARD в WHILE, то без вскрытия тела не увидеть - есть ли он внутри; это сродни обычному EXIT в WHILE.

См. также Убираю LOOP'ы


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 14 Май, 2010 18:00 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
Info21 писал(а):
Валерий Лаптев писал(а):
Но при этом процедура должна все равно возвращать результат типа boolean, чтобы участвовать в логическом выражении.
А я о чем, когда говорил, что приходится "оборачивать"?

А я откуда знаю, о чем вы говорили? Я и говорю - прояснилось.
Но что вы опять имеете ввиду, говоря об "оборачивать"?
Выражение целиком оборачивать или переменную а оборачивать?


Последний раз редактировалось Валерий Лаптев Пятница, 14 Май, 2010 18:49, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 14 Май, 2010 18:48 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Валерий Лаптев писал(а):
А я откуда знаю, о чем вы говорили?
По идее сначала нужно более-менее внимательно прочесть (чего Вы не сделали), потом прояснить, что непонятно (чего Вы опять же не сделали, и я должен был гадать и пытаться наобум прояснять), потом всё остальное.

Ваш длинный ответ, написанный, как Вы только что признали, без понимания изначального сообщения, только всё запутывает.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 14 Май, 2010 18:57 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Евгений Темиргалеев писал(а):
Если разрешить GUARD в WHILE, то без вскрытия тела не увидеть - есть ли он внутри; это сродни обычному EXIT в WHILE.
В этом есть пунктик, но всё же не окончательный аргумент:

О "вскрытии тела" говорит нет особого смысла, т.к. GUARD допустим только на верхнем уровне тела. В этом смысле GUARD сильно отличается от EXIT.

В общем с самого начала понятно, что пихать что-то в WHILE не выглядит кошерно а приори, хотя добавка имеет жесткий смысл, и вполне в духе общей логики.
Ведь LOOP здесь получается сильно ограниченным, совсем близким к WHILE, так что вариант с выкидыванием LOOP и добавкой GUARD заслуживает внимания хотя бы как проверка решения на устойчивость.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 11 Январь, 2011 07:02 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 2046
Сергей Прохоренко писал(а):
Спасибо за ссылку, Драконограф!

Воспроизвожу по полученной ссылке форму цикла Дейкстры в языке Promela из указанного источника:
Код:
proctype Euclid(int x, y){
do
    :: (x > y) -> x = x - y
    :: (x < y) -> y = y - x
    :: (x == y) -> goto done
od;
done: skip
}

Здесь skip - пустой оператор, перед которым стоит метка done.



А вот как будет выглядеть тот же пример в PureBuilder:
Код:
┌while
 │▼ x > y
 │    dec (x, y)
 │▼ x < y
└    dec (y, x)

Алгоритм функции записывается не внутри длинного программного кода, а в отдельной вкладке интерфейса. Поэтому заголовок функции отсутствует.

Объявление параметров и возвращаемого значения функции Euclid осуществляется в отдельной табличке.

Псевдографика не очень правильно передает скобку слева. На самом деле она непрерывная, с закругленными углами и полностью охватывает строки с while и dec (y, x).

Ключевые слова должны изображаться жирным шрифтом. Значки ▼ используются при необходимости сворачивания соответствующих ветвей цикла. При этом они принимают вид ►.
Верно я понимаю, что описание алгоритма процесса Euclid (т.е. импер-знания о нём) на Вашем языке (буду, как обычно, называть по сокращению от ника автора - СП-язык) делится между вкладкой с приведённым импер-СП-текстом и вкладкой с импер-СП-текстом другой категории? Каково точное содержание каждой категории (т.е. что в импер-СП-описании одного процесса/программы помещается на вкладки каждого из разных типов) и критерии такого деления? Ну и если я понял неверно - то куда девается заголовок (какими средствами и где в СП-описании представляется часть смысла процесса, отражаемая заголовочными реквизитами)?

Ну и к тому, о чём говорилось в этом соообщении. При уходе от чистого текста ключевые слова, отвечающие за представление структуры, эргономично заменять на графику (таблицы, графа - зависит от того, насколько далеко ушли :) ). Здесь же видим - и ключевые слова маршрутные (while) сохранились - и ещё добавились элементы нетекстового указания структуры (скобки). Т.е. избыточная сложность представления получилась. Если уж так исторически сложилось "для программистов" - пусть будет... как одна из форм показа (можно считать её "как бы текстовой") - но обязательно наряду с "неизбыточно сложными" :wink: .


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 11 Январь, 2011 14:48 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
Небольшое резюме по операторам:
Условный (Дейкстра)
Код:
if
      | условие: операторы;
      | условие: операторы;
      …
      | условие: операторы;
end;
Этот же оператор является переключателем – семантика Дейкстры.
Оператор позволяет задавать одиночный if:
Код:
if | условие: операторы;
end;

Обычный двухветочный if эквивалентен:
Код:
if | условие:   операторы;
   | ~условие: операторы;
end;

Вариант:
Код:
   if
   | условие: операторы;
   | условие: операторы;
   …
   | условие: операторы;
   else   операторы;      
   end;

Семантика: если не выполняется ни одно из условий, то выполняется ветка else
Цикл (Дейкстра)
Код:
do
      | условие: операторы;
      | условие: операторы;
      …
      | условие: операторы;
end;

вариант:
Код:
do
   | условие: операторы;
   | условие: операторы;
   …
   | условие: операторы;
   else операторы;
end;

Семантика: если нет ни одного истинного условия, то выполняется ветка else и цикл завершается

цикл while:
Код:
do | условие: операторы;
end;

цикл do while (repeat):
Код:
do   | true: операторы;
      | условие:    end;

вариант: true можно пропускать вместе со скобками


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 11 Январь, 2011 14:59 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл
Валерий Лаптев писал(а):
вариант:
Код:
do
   | условие: операторы;
   | условие: операторы;
   …
   | условие: операторы;
   else операторы;
end;

Семантика: если нет ни одного истинного условия, то выполняется ветка else и цикл завершается
Это чем-то отличается от
Код:
do
   | условие: операторы;
   | условие: операторы;
   …
   | условие: операторы;
end;
операторы;
?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 11 Январь, 2011 15:03 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
Похоже, что нет. При означенной семантике.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 11 Январь, 2011 15:36 
Аватара пользователя

Зарегистрирован: Воскресенье, 08 Июль, 2007 00:38
Сообщения: 778
Откуда: Москва
Драконограф писал(а):
... куда девается заголовок (какими средствами и где в СП-описании представляется часть смысла процесса, отражаемая заголовочными реквизитами)?


На самом деле заголовок функции не нужен, потому что алгоритм функции записывается не внутри длинного программного кода, а в отдельной вкладке интерфейса. Соответственно, название функции отображено на рисунке на веб-странице в строке Project_1 > Module_5 > Euclid. А что касается возвращаемого значения, то оно должно объявляться и специфицироваться ниже записи алгоритма функции - в отдельной таблице в панели элементов структуры.

Соответственно, на вкладке Project_1 > Module_5 функция Euclid будет отображаться отдельным элементом со своим именем. Можно будет прямо во вкладке этого модуля создать "пустую" функцию-заглушку с каким-нибудь именем, а подробной разработкой этой функции заняться как-нибудь потом, когда будет время. Щелкаем по элементу, отображающему новую функцию - и оказываемся в пустой вкладке этой функции, которую (вкладку) предстоит заполнить содержанием.

Драконограф писал(а):
Здесь же видим - и ключевые слова маршрутные (while) сохранились - и ещё добавились элементы нетекстового указания структуры (скобки).


Конечно, теоретически можно заменить ключевое слово while каким-нибудь значком или иероглифом. Но, во-первых, при этом потеряется возможность проговаривать и обсуждать код программы. Во-вторых, ключевое слово while и так воспринимается именно как значок, а не как исходное слово английского языка. Оно даже удобнее русского перевода, так как воспринимается как специфическая часть программы с особым значением, а не как слово с традиционными значениями (это аргумент против русского синтаксиса).


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 11 Январь, 2011 15:43 
Аватара пользователя

Зарегистрирован: Воскресенье, 08 Июль, 2007 00:38
Сообщения: 778
Откуда: Москва
Валерий Лаптев писал(а):
Небольшое резюме по операторам:


А как Вам такой вариант? Разумеется, лишние ветви могут быть удалены.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 13 Январь, 2011 12:44 
Аватара пользователя

Зарегистрирован: Воскресенье, 08 Июль, 2007 00:38
Сообщения: 778
Откуда: Москва
Пример цикла Дейкстры (алгоритм Эвклида) в PureBuilder - теперь в виде картинки:
Вложение:
Алгоритм Эвклида в PureBuilder.png
Алгоритм Эвклида в PureBuilder.png [ 2.87 КБ | Просмотров: 13823 ]


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 13 Январь, 2011 15:57 
Администратор

Зарегистрирован: Вторник, 15 Ноябрь, 2005 01:14
Сообщения: 4695
Откуда: Россия, Орёл
Вы себе шею сломаете при работе со сложным алгоритмом при таком подходе. Попробуйте представить.
Разумеется, это моё личное, частное мнение.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 13 Январь, 2011 16:22 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Борис Рюмшин писал(а):
Вы себе шею сломаете при работе со сложным алгоритмом при таком подходе. Попробуйте представить.
Человек же признавался не раз, что не программист.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 13 Январь, 2011 20:28 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Сергей Прохоренко писал(а):
Пример цикла Дейкстры (алгоритм Эвклида) в PureBuilder - теперь в виде картинки:
...

Выглядит симпатично.

Почему кто-то тут может сломать себе шею -- совершенно непонятно.
Пример таких языков, как Оккам, Питон, Хаскелл, F# показывают, что всё тут будет нормально, а для новичков в программировании -- просто отлично...


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 13 Январь, 2011 22:51 
Аватара пользователя

Зарегистрирован: Воскресенье, 08 Июль, 2007 00:38
Сообщения: 778
Откуда: Москва
Борис Рюмшин писал(а):
Вы себе шею сломаете...


Я буду не одинок. :D Такой вариант алгоритма Эвклида мне попадался много раз на разных языках программирования. Он уже стал почти столь же популярен для демонстрации цикла Дейкстры, как пресловутый "Hello, world". Единственное, что я сделал, это очистил его от лишней синтаксической шелухи, которая только увеличивала шансы сломать шею. :wink:

Если Вы имеете в виду, что в паре строчек кода содержится слишком много скрытого математического смысла, то я соглашусь. Писать так обычные программы, конечно, не стоит. А вот для библиотечных функций, которые можно отлаживать хоть неделю на каждую строчку кода, такие алгоритмы вполне нормальны. Для этого существуют яйцеголовые математики. :D Я же привел всего лишь демонстрационный пример, который многие используют для демонстрации цикла Дейкстры.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 85 ]  На страницу Пред.  1, 2, 3, 4, 5  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 13


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2024, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB