OberonCore
https://forum.oberoncore.ru/

Цикл Дейкстры
https://forum.oberoncore.ru/viewtopic.php?f=30&t=1225
Страница 1 из 9

Автор:  Info21 [ Суббота, 25 Октябрь, 2008 17:41 ]
Заголовок сообщения:  Цикл Дейкстры

AVC писал(а):
ОТ МОДЕРАТОРА: Вольно процитировал из ветки про Оберон-07

... Цикл LOOP напрасно исключён Виртом из Оберона-07. Введённый вместо него цикл Дейкстры на практике бесполезен ...


Неверно, что цикл Дейкстры не встречается. Редко, но встречается. И именно для сложных случаев он позволяет с гарантией "разрулить" сложность. (Это по своему опыту, конечно.) Просто привычки к нему нет (тут, подозреваю, несколько как с привычкой к деструкторам из Ц++).

И как раз про "недоказанность" цикла Дейкстры говорить трудно.
Число логич. переменных он как раз уменьшает.
И "альтернативы с WHILE" никак искусственными быть не могут, если WHILE многоветочный (дейкстровский).

С циклом Дейкстры единственное известное мне применение LOOP -- оптимизация (сохранение частичных результатов при сложных условиях или исключение дублирования кода).
Затрудняюсь сказать, насколько это важное соображение для языка-ядра, но мое ощущение -- что не очень важное.

Вон, известный Eric Raymond ("Искусство программирования на Юниксе") активно пропагандирует питон + Ц(для кусков, где нужна оптимизация) вместо Ц++. При том, что питон сильно тормозной, судя по вот этому: http://shootout.alioth.debian.org/u32/b ... l&lang=all

В этом смысле Оберон-07+SYSTEM более чем конкурентоспособен.

Автор:  Info21 [ Воскресенье, 26 Октябрь, 2008 00:36 ]
Заголовок сообщения:  Re: Оберон-07

AVC писал(а):
Не понимаю попыток info21 защищать цикл Дейкстры.
Даже в излюбленном (заведомо выигрышном) примере голландца - алгоритме Евклида - он проигрывает по ясности виртовскому варианту на Модуле-2.

Если почитать книжки Дейкстры и Гриса :-)
то там можно найти гораздо более выигрышные примеры.

Алгоритм Евклида -- всем понятная, очень простая иллюстрация.

У меня был один тяжелый случай -- сложный цикл в переме(ж|ш)ку с рекурсией, который я смог понять и сделать, только после приведения к форме Дейкстры с явной формулировкой инварианта. Причем после переформулировки концептуальная трудность ушла как класс, осталась только громоздкость (там было три или четыре ветви в цикле).
С тех пор и люблю цикл Дейкстры :-)

Автор:  AVC [ Воскресенье, 26 Октябрь, 2008 10:14 ]
Заголовок сообщения:  Re: Оберон-07

По поводу цикла Дейкстры.
Рассмотрим простой пример (в чём-то родственный алгоритму Евклида) - поиск в двоичном дереве.
Код:
p := root;
WHILE (p # NIL) & (s # p.name) DO
    IF s < p.name THEN p := p.left ELSE p := p.right END
END;
RETURN p (* ставлю RETURN в конце процедуры :) *)
Как его переписать в виде цикла Дейкстры? :mrgreen:

Автор:  AVC [ Воскресенье, 26 Октябрь, 2008 12:12 ]
Заголовок сообщения:  Re: Оберон-07

Давайте разберёмся, откуда такая любовь к циклу Дейкстры. :roll:
При конструировании циклов используют комбинацию пред-(пост-)условия и инварианта цикла.
Единственное достоинство цикла Дейкстры в том, что (по сравнению с циклом LOOP) он позволяет сохранить понятие инварианта.
Код:
WHILE condition1 DO (* P = инвариант цикла *) ...
ELSIF condition2 DO (* и здесь выполняется P = инвариант цикла *)
END (* P & ~(condition1 OR condition2) *)
В этом всё (теоретическое) преимущество по сравнению с LOOP (если не считать того, что оператор EXIT привязан к LOOP контекстуально, а не синтаксически).
Цикл LOOP (в сочетании с IF...ELSIF...ELSE EXIT END) позволяет легко имитировать цикл Дейкстры, но не принуждает к использованию инварианта цикла в его крайней точке (начале или конце).
Вместе с тем, использование исключительно структурных циклов имеет свои недостатки. В одном месте вводится (необязательная) вспомогательная переменная, в другом - дублируется код.
Пообсуждаем? :)
Особенно интересно мнение info21.
Желательны примеры.

Автор:  Илья Ермаков [ Воскресенье, 26 Октябрь, 2008 15:52 ]
Заголовок сообщения:  Re: Оберон-07

"Дублирование" кода - псевдопроблема.
Ведь дублирование возникает там, где некоторое действие (продвижение по последовательности, например) выполняется на один раз больше, чем сопряжённое с ним ("полезная нагрузка" цикла, обработка, например).
Так бывает очень часто.
И хорошо, что это явно видно. Я эту ситуацию называю "случаем забора" (напоминает задачку из первого класса: сколько столбиков надо для забора из стольки-то секций). Сначала вбиваем первый столб забора, потом выполняем цикл DO "поставить часть забора; вкопать столб". Или наоборот бывает - цикл DO "вкопать столб; поставить часть забора" - и в конце вбиваем заключительный столб.
Вы же хотите затушевать тот факт, что действия выполняются неодинаковое число раз, имеют разный смысл (и добиваетесь этого либо EXIT-ом, либо вложенными в цикл проверками - чтоб заставить один раз недовыполниться другое действие).

Но если мы точно знаем, что действие выполняется один раз (добавочное действие, будет выполнено даже если цикл не выполняется вообще), то ему не место в цикле. Так же, например, как глупо выглядит обработка найденного элемента внутри цикла for ... if ... break endif endfor - ведь это ж, ёлки-палки, никакого отношения к циклу уже не имеет, цикл закончился - значит после должно делаться...

Автор:  Info21 [ Воскресенье, 26 Октябрь, 2008 17:51 ]
Заголовок сообщения:  Re: Оберон-07

AVC писал(а):
... Единственное достоинство цикла Дейкстры в том, что (по сравнению с циклом LOOP) он позволяет сохранить понятие инварианта. ...

Ни хрена себе "единственное". За него Тьюринга дали.
Провокация? :-)

Если найден инвариант, то пострение цикла становится straightforward: перечисляются все вообразимые предусловия, чтобы их дизъюнкция покрыла предусловие, и для каждой делается ветвь так, чтобы делать один (строго приближающий) шаг в направлении постусловия.

Исключительно прозрачная схема, являющаяся, кстати, блестящей реализацией принципа "разделяй и властвуй" -- потому что обоснование/построение каждой части схемы четко отделено от остальных:
что дизъюнкция покрывает...;
что конкретный шаг в каждой ветви строго приближает;
что в каждой ветки инвариант сохраняется
...

Схема дает полную уверенность даже в очень интуитивно неочевидных случаях.
Потом можно спокойно оптимизировать.

Примеров -- целые две книги -- Дейкстры и Гриса.

Автор:  Axcel [ Воскресенье, 26 Октябрь, 2008 18:03 ]
Заголовок сообщения:  Re: Оберон-07

Илья Ермаков писал(а):
"Дублирование" кода - псевдопроблема.
Ведь дублирование возникает там, где некоторое действие (продвижение по последовательности, например) выполняется на один раз больше, чем сопряжённое с ним ("полезная нагрузка" цикла, обработка, например).
Так бывает очень часто.
И хорошо, что это явно видно. ...

По моему не хорошо. Дублирование есть дублирование, а циклы для того и придуманы, чтобы избегать его.

Автор:  Илья Ермаков [ Воскресенье, 26 Октябрь, 2008 18:08 ]
Заголовок сообщения:  Re: Оберон-07

Да нет ведь никакого дублирования!

Есть отдельное действие, делаемое один раз.
И есть группа действий, повторяемая в цикле.

Неужели ж неясно, что A и [B, A] - это не одно и то же?
Поверхностно смотрим - и получаем назойливое желание "заоптимизировать", допихать это А внутрь цикла. А ему там не место, потому что цикл построен для повторения целой группы действий, которые выполняются как единое целое, синхронно, одинаковое число раз.

Автор:  AVC [ Воскресенье, 26 Октябрь, 2008 22:46 ]
Заголовок сообщения:  Re: Оберон-07

Info21 писал(а):
Ни хрена себе "единственное". За него Тьюринга дали.
Провокация? :-)
Провокация. :)
Но мне и правда интересно, так ли уж полезна "предельная строгость" принципа отказа от "нелокальных переходов".
BTW, один из современных аргументов против подхода Дейкстры - использование исключений. Мол, не получается, чтобы был один выход.

Автор:  Info21 [ Воскресенье, 26 Октябрь, 2008 23:15 ]
Заголовок сообщения:  Re: Оберон-07

AVC писал(а):
... BTW, один из современных аргументов против подхода Дейкстры - использование исключений. Мол, не получается, чтобы был один выход.

Сначала надо выяснить, против чего это аргумент:
против Дейкстры или против имеющих место быть практик. (Железные сбои не берем.)

Автор:  Trurl [ Понедельник, 27 Октябрь, 2008 09:18 ]
Заголовок сообщения:  Re: Оберон-07

AVC писал(а):
Рассмотрим простой пример (в чём-то родственный алгоритму Евклида) - поиск в двоичном дереве.
Как его переписать в виде цикла Дейкстры? :mrgreen:

Код:
p := root;
do  (p # NIL) & (s < p.name) -> p := p.left
[]  (p # NIL) & (s > p.name) -> p := p.right
od;
(* p = NIL or s = p.name *)

Автор:  AVC [ Понедельник, 27 Октябрь, 2008 11:09 ]
Заголовок сообщения:  Re: Оберон-07

Trurl писал(а):
Код:
p := root;
do  (p # NIL) & (s < p.name) -> p := p.left
[]  (p # NIL) & (s > p.name) -> p := p.right
od;
(* p = NIL or s = p.name *)
Бросается в глаза дублирование проверки условия (p # NIL).
А ведь пример построен по той же схеме, что и алгоритм Евклида.

Автор:  Info21 [ Понедельник, 27 Октябрь, 2008 13:39 ]
Заголовок сообщения:  Re: Оберон-07

AVC писал(а):
Trurl писал(а):
Код:
p := root;
do  (p # NIL) & (s < p.name) -> p := p.left
[]  (p # NIL) & (s > p.name) -> p := p.right
od;
(* p = NIL or s = p.name *)
Бросается в глаза дублирование проверки условия (p # NIL).

Известно, как много проблем в программировании возникает из-за преждевременных попиток оптимизации ... etc.

Дублирование тут (и в огромном большинстве других случаев) ничтожно.
Зато гарантия постусловия -- железная.

Автор:  Vlad [ Понедельник, 27 Октябрь, 2008 16:28 ]
Заголовок сообщения:  Re: Оберон-07

AVC писал(а):
На мой взгляд, Оберон-07 исключительно неудачная ревизия языка Оберон.


ИМХО, Вирт сделал язык под задачу. Причем задача включала в себя написание компилятора (не ну мог же он взять готовый сишный). Ну не нужны ему были динамические массивы - ну и не стал он их включать в язык. И т.д. Т.е. если убрать из контекста обсуждения "general purpose language", то ничего "странного" в обероне-07 нет.

P.S. Ну а дейкстровский WHILE - видимо из любви к искусству, практической ценности (хоть с учетом специфики ARM, хоть без) в нем никакой.

Автор:  Info21 [ Понедельник, 27 Октябрь, 2008 17:48 ]
Заголовок сообщения:  Re: Оберон-07

Vlad писал(а):
... Ну а дейкстровский WHILE - видимо из любви к искусству, практической ценности (хоть с учетом специфики ARM, хоть без) в нем никакой.

Вот еще одно кривое обобщение...

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

Автор:  Vlad [ Понедельник, 27 Октябрь, 2008 18:09 ]
Заголовок сообщения:  Re: Оберон-07

Info21 писал(а):
А рассматривая его в герменевтическом духе, делаем вывод о той конкретной практике, которая за сим обобщением стоит.


Ну вот опять, пытаетесь сделать мину... С обоснованиями, как всегда, напряженка...

P.S. А ведь достаточно одного (1) примера большей читабельности такого цикла по сравнению с другими.

Автор:  slava [ Понедельник, 27 Октябрь, 2008 19:07 ]
Заголовок сообщения:  Re: Оберон-07

Вирт не смахивает на теоретика, готового обсуждать ради обсуждения.
Не сомневаюсь, что он это (WHILE Дейкстры) обкатал на очередном проекте.

Если же мы не можем (и не готовы) понять эту великую идею, то это может потому, что сами пишем одни while'ы, да for'ы.
С нашим то опытом (for-break'ов) требовать "доказательств лучшей читабельности цикла Дейкстры"!?

Автор:  Info21 [ Понедельник, 27 Октябрь, 2008 19:27 ]
Заголовок сообщения:  Re: Оберон-07

Vlad писал(а):
Info21 писал(а):
А рассматривая его в герменевтическом духе, делаем вывод о той конкретной практике, которая за сим обобщением стоит.
Ну вот опять, пытаетесь сделать мину... С обоснованиями, как всегда, напряженка...

P.S. А ведь достаточно одного (1) примера большей читабельности такого цикла по сравнению с другими.
1) никаких мин я не делаю, а констатирую факт элементарной логики. Вы делаете сильнейшее обобщение, вы и обосновывайте. Почему кто-то должен париться и ваши лозунги опровергать.

2) Я уже рассказывал про пример, где не только читабельность, но и вообще правильное построение без цикла Дейкстры было проблематичным. Это сложный пример, там еще рекурсия замешана, и приводить здесь его не будут. У Дейкстры и Гриса полно примеров попроще, которых умному -- достаточно.

Любой себя уважающий профессионал должен хотя бы одну из книжек -- Дейкстры или Гриса -- проработать. Любое лозунгокидательство без этого -- просто пустая брехня.

Автор:  Info21 [ Понедельник, 27 Октябрь, 2008 19:30 ]
Заголовок сообщения:  Re: Оберон-07

slava писал(а):
Вирт не смахивает на теоретика, готового обсуждать ради обсуждения.
Не сомневаюсь, что он это (WHILE Дейкстры) обкатал на очередном проекте.

По крайней мере он пишет, что в компиляторе у него было "только четыре цикла LOOP" (цитирую по памяти), которые он и заменил.

Автор:  Илья Ермаков [ Понедельник, 27 Октябрь, 2008 21:16 ]
Заголовок сообщения:  Re: Оберон-07

Vlad писал(а):
P.S. Ну а дейкстровский WHILE - видимо из любви к искусству, практической ценности (хоть с учетом специфики ARM, хоть без) в нем никакой.

Влад, Вы обобщаете на пустом месте (отсутствии собств. опыта в этом плане). Мы уже говорили как-то, что у Вас (как и у меня, просто задачи такие) большинство циклов базовые - как Вы их называете, типа foreach и search (полный проход и лин. поиск). Ну-ка, припомните, когда последний раз приходилось строить цикл, в котором изменяются в связке много величин по нек. соотношению? А шашкой махать мы тут горазды, типа.

Теперь касательно общего WHILE. Цикл, вообще говоря, это описание некоторого процесса, по достижению какой-то цели (постусловия). Он обеспечивает "обратную связь" (пока не достигли цели, делаем...). В простом случае шаги этого процесса однородны (имеем просто последовательность неких состояний, по которой продвигаемся). Однако в общем случае шаги могут быть неоднородными.

Если наша цель выражается некоторым конъюнктом A & B, то условие продолжения цикла - дизъюнкт ~A OR ~B. А можно записать эквивалентно: цель - ~C & ~D, а условие - C OR D. Можно сказать, что до тех пор, пока есть одна из возможностей (C или D) для продвижения далее, то продвигаемся; когда возможности нет, то мы достигли цели. Так вот, вероятнее всего, что совершаемое действие будет различаться в зависимости от того, в силу какого дизъюнкта цикл продолжился. То есть, WHILE C OR D OR .. DO IF C THEN ... ELSIF D THEN ... ELSE ... END END.

Даю пример в студию. Из учебника Кушниренко (для школьников 8-9 кл. т.е.)

Вложение:
DijkstraCycle.png
DijkstraCycle.png [ 322.43 КБ | Просмотров: 14521 ]


(Обращаю внимание, что по логике обучения у Кушниренко дети к моменту решения таких задач ещё не знают IF. Проходится декомпозиция на вспомогательные алгоритмы, затем for, затем while. Приведённое решение имеет методической целью а) показать пример сложного условия б) в очередной раз отработать пошаговую детализацию с разбиением на подзадачи и сведением к ранее уже решёным задачам. Обратите, кстати, внимание, насколько фундаментален WHILE - с его помощью и без IF можно выразить многообразное поведение)

На самом деле, не "методическое", а обычное решение выглядит, конечно, так:
Код:
WHILE СлеваСвободно() OR СверхуСвободно() DO
  IF СлеваСвободно() THEN
    Влево
  ELSE
    Вверх
  END
END


Вот вам и пример поведения с неоднородными действиями, вот вам и цикл Дейкстры:
Код:
WHILE СлеваСвободно() DO
  Влево
ELSIF СверхуСвободно() DO
  Вверх
END

Насколько выразительно и отражающе существо дела. Не говоря про исключение набивающего так многим оскомину дублирования анализа условия.

Т.е. WHILE ELSIF END - такое же обобщение WHILE, как IF ELSIF END - обобщение IF (можно ведь описать всё и простым IF вообще без ELSE).

Резюме: эти фундаментальные структуры управления придуманы не от балды (в отличие от большинства артефактов современных языков). Они отражают важные аспекты реальности, реальных систем, алгоритмов как описания поведения этих систем. WHILE - простая обратная связь. Дейкстровский WHILE - обратная связь для случая с составными целями и неоднородными действиями по их достижению.

P.S. В функциональных абстракциях аналог обычного цикла - рекурсия, а аналог дейкстровского цикла - косвенная рекурсия. Кстати, наверняка многие случаи, настойчиво "просившие" рекурсии именно в силу неоднородности действий, выразятся отлично дейкстровским циклом.

Страница 1 из 9 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/