OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Суббота, 19 Октябрь, 2019 14:54

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




Начать новую тему Ответить на тему  [ Сообщений: 165 ]  На страницу 1, 2, 3, 4, 5 ... 9  След.
Автор Сообщение
 Заголовок сообщения: Цикл Дейкстры
СообщениеДобавлено: Суббота, 25 Октябрь, 2008 17:41 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8185
Откуда: Троицк, Москва
AVC писал(а):
ОТ МОДЕРАТОРА: Вольно процитировал из ветки про Оберон-07

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


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

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

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оберон-07
СообщениеДобавлено: Воскресенье, 26 Октябрь, 2008 00:36 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8185
Откуда: Троицк, Москва
AVC писал(а):
Не понимаю попыток info21 защищать цикл Дейкстры.
Даже в излюбленном (заведомо выигрышном) примере голландца - алгоритме Евклида - он проигрывает по ясности виртовскому варианту на Модуле-2.

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оберон-07
СообщениеДобавлено: Воскресенье, 26 Октябрь, 2008 10:14 
Аватара пользователя

Зарегистрирован: Суббота, 19 Ноябрь, 2005 15:59
Сообщения: 803
Откуда: Зеленоград
По поводу цикла Дейкстры.
Рассмотрим простой пример (в чём-то родственный алгоритму Евклида) - поиск в двоичном дереве.
Код:
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:


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оберон-07
СообщениеДобавлено: Воскресенье, 26 Октябрь, 2008 12:12 
Аватара пользователя

Зарегистрирован: Суббота, 19 Ноябрь, 2005 15:59
Сообщения: 803
Откуда: Зеленоград
Давайте разберёмся, откуда такая любовь к циклу Дейкстры. :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.
Желательны примеры.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оберон-07
СообщениеДобавлено: Воскресенье, 26 Октябрь, 2008 15:52 
Модератор
Аватара пользователя

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оберон-07
СообщениеДобавлено: Воскресенье, 26 Октябрь, 2008 17:51 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8185
Откуда: Троицк, Москва
AVC писал(а):
... Единственное достоинство цикла Дейкстры в том, что (по сравнению с циклом LOOP) он позволяет сохранить понятие инварианта. ...

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

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

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оберон-07
СообщениеДобавлено: Воскресенье, 26 Октябрь, 2008 18:03 

Зарегистрирован: Понедельник, 05 Июнь, 2006 09:49
Сообщения: 327
Откуда: Ленинград, Емельянов Алексей Николаевич
Илья Ермаков писал(а):
"Дублирование" кода - псевдопроблема.
Ведь дублирование возникает там, где некоторое действие (продвижение по последовательности, например) выполняется на один раз больше, чем сопряжённое с ним ("полезная нагрузка" цикла, обработка, например).
Так бывает очень часто.
И хорошо, что это явно видно. ...

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оберон-07
СообщениеДобавлено: Воскресенье, 26 Октябрь, 2008 18:08 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9147
Откуда: Россия, Орёл
Да нет ведь никакого дублирования!

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оберон-07
СообщениеДобавлено: Воскресенье, 26 Октябрь, 2008 22:46 
Аватара пользователя

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оберон-07
СообщениеДобавлено: Воскресенье, 26 Октябрь, 2008 23:15 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8185
Откуда: Троицк, Москва
AVC писал(а):
... BTW, один из современных аргументов против подхода Дейкстры - использование исключений. Мол, не получается, чтобы был один выход.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оберон-07
СообщениеДобавлено: Понедельник, 27 Октябрь, 2008 09:18 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1202
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 *)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оберон-07
СообщениеДобавлено: Понедельник, 27 Октябрь, 2008 11:09 
Аватара пользователя

Зарегистрирован: Суббота, 19 Ноябрь, 2005 15:59
Сообщения: 803
Откуда: Зеленоград
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).
А ведь пример построен по той же схеме, что и алгоритм Евклида.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оберон-07
СообщениеДобавлено: Понедельник, 27 Октябрь, 2008 13:39 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8185
Откуда: Троицк, Москва
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.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оберон-07
СообщениеДобавлено: Понедельник, 27 Октябрь, 2008 16:28 

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


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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оберон-07
СообщениеДобавлено: Понедельник, 27 Октябрь, 2008 17:48 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8185
Откуда: Троицк, Москва
Vlad писал(а):
... Ну а дейкстровский WHILE - видимо из любви к искусству, практической ценности (хоть с учетом специфики ARM, хоть без) в нем никакой.

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оберон-07
СообщениеДобавлено: Понедельник, 27 Октябрь, 2008 18:09 

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


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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оберон-07
СообщениеДобавлено: Понедельник, 27 Октябрь, 2008 19:07 

Зарегистрирован: Понедельник, 19 Март, 2007 09:40
Сообщения: 142
Откуда: USA, Israel, Belarus
Вирт не смахивает на теоретика, готового обсуждать ради обсуждения.
Не сомневаюсь, что он это (WHILE Дейкстры) обкатал на очередном проекте.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оберон-07
СообщениеДобавлено: Понедельник, 27 Октябрь, 2008 19:27 
Аватара пользователя

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

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оберон-07
СообщениеДобавлено: Понедельник, 27 Октябрь, 2008 19:30 
Аватара пользователя

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Оберон-07
СообщениеДобавлено: Понедельник, 27 Октябрь, 2008 21:16 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9147
Откуда: Россия, Орёл
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 КБ | Просмотров: 14982 ]


(Обращаю внимание, что по логике обучения у Кушниренко дети к моменту решения таких задач ещё не знают 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. В функциональных абстракциях аналог обычного цикла - рекурсия, а аналог дейкстровского цикла - косвенная рекурсия. Кстати, наверняка многие случаи, настойчиво "просившие" рекурсии именно в силу неоднородности действий, выразятся отлично дейкстровским циклом.


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

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


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

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


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

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