OberonCore

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

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




Начать новую тему Ответить на тему  [ Сообщений: 165 ]  На страницу Пред.  1, 2, 3, 4, 5 ... 9  След.
Автор Сообщение
 Заголовок сообщения: Re: Оберон-07
СообщениеДобавлено: Понедельник, 27 Октябрь, 2008 21:58 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Не удержусь - нарисую дейкстровский цикл для предыдущего примера на Драконе:

Вложение:
DrakonDijkstra.png
DrakonDijkstra.png [ 936 байт | Просмотров: 11538 ]


Как выразительно выглядят конъюнкции и дизъюнкции. Сразу видно, что выход вниз происходит по конъюнкции условий (вопросы и ответы "нет" нанизаны один за другим). Продолжение цикла - по дизъюнкции (вправо уходят два пути, от каждого из вопросов по ответу "да"). Для анализа постусловий в каждой точке схемы - красота.

Кстати, у Паронджанова введена спец. конструкция - переключающий цикл. Частный случай дейкстровского, сочетание WHILE и CASE.

Вложение:
CaseCycle.png
CaseCycle.png [ 1.14 КБ | Просмотров: 11504 ]


А сконцентрированы в Драконе суровые реалии систем реального времени.


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

Зарегистрирован: Суббота, 19 Ноябрь, 2005 15:59
Сообщения: 803
Откуда: Зеленоград
Илья Ермаков писал(а):
Вот вам и пример поведения с неоднородными действиями, вот вам и цикл Дейкстры:
Код:
WHILE СлеваСвободно() DO
  Влево
ELSIF СверхуСвободно() DO
  Вверх
END
Илья, спасибо за действительно интересный пример.
Вместе с тем, один момент у меня вызывает сомнение.
Борьба с EXIT и RETURN "где попало" опирается на правило "один вход - один выход".
А ведь исполнение этого правила для цикла Дейкстры сомнительно.
Например, я хотел бы проверить выполнение инварианта цикла в точке входа (или выхода). Куда мне поставить ASSERT?
Для других циклов это не составляет большого труда.
Например,
Код:
WHILE cond DO
    ASSERT(инвариант);
    ...
END
и даже, страшно сказать :) ,
Код:
LOOP
    ASSERT(инвариант);
    IF cond1 THEN ...
    ELSIF cond2 THEN ...
    ELSE EXIT
    END
END


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

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Да, ASSERT придётся ставить на каждой из веток. Однако инвариант такого цикла дизъюнктивен, можно разделить на части и вставить ASSERT по каждому дизъюнкту в соотв. ветку.
В конце концов ведь ASSERT в цикле обычно убирается (это не контракт с (априори) агрессивным окружением, а самоконтроль).
И оставляется только комментарий перед циклом (* INV ... *).

Со входами-выходами как раз всё в порядке. То, что у конструкции внутри ветвится несколько путей, ничего не меняет.


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

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
Илья Ермаков писал(а):
Вот вам и пример поведения с неоднородными действиями, вот вам и цикл Дейкстры:
Код:
WHILE СлеваСвободно() DO
  Влево
ELSIF СверхуСвободно() DO
  Вверх
END

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

К тому же, я уже как будто сейчас вижу такие циклы с неправильной реализацией:
Код:
WHILE p = NIL DO
  NEW(p)
ELSIF p.attr = base_type DO
  DoSomeWork(p)
END
Такое возможно и сейчас практикуется у нас за счёт использования внутри цикла конструкции IF. Также, встречался с этим в интернете при чтении исходников.


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

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


На тех четырех циклах LOOP? :)


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

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


Не, бездоказательные обобщения - это ваш конек.

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


А зря. Лучше один раз увидеть. Или боитесь, что там окажется все намного проще, чем вы думаете? :)


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

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
Илья Ермаков писал(а):
Влад, Вы обобщаете на пустом месте (отсутствии собств. опыта в этом плане). Мы уже говорили как-то, что у Вас (как и у меня, просто задачи такие) большинство циклов базовые - как Вы их называете, типа foreach и search (полный проход и лин. поиск). Ну-ка, припомните, когда последний раз приходилось строить цикл, в котором изменяются в связке много величин по нек. соотношению?


Да, возможно вы правы. Я не помню, когда последний раз строил сложный цикл. Поэтому и хотелось бы увидеть пример.

Илья Ермаков писал(а):
Теперь касательно общего WHILE. Цикл, вообще говоря, это описание некоторого процесса, по достижению какой-то цели (постусловия).


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

Илья Ермаков писал(а):
Вот вам и пример поведения с неоднородными действиями, вот вам и цикл Дейкстры:


Ну и чем это выразетельнее "while (step_t s = get_next_step()) do_step(s);"? Или даже while (true) с break'ом? :)

Илья Ермаков писал(а):
Дейкстровский WHILE - обратная связь для случая с составными целями и неоднородными действиями по их достижению.


"Дейкстровский WHILE" без потери выразительности сводится к обычному WHILE. Следовательно нафиг не нужен.

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


Жду следующий пример :)


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

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Vlad писал(а):
"Дейкстровский WHILE" без потери выразительности сводится к обычному WHILE. Следовательно нафиг не нужен.

Представьте вполне реальную ситуацию, что дизъюнктов не два, а несколько. Из своего опыта не приведу (по уже названным причинам). В серьёзных алгоритмах (хотя бы численные методы) будет наверняка. Мне, например, вспоминается почему-то что-нибудь типа градиентного спуска.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Воскресенье, 02 Ноябрь, 2008 23:12 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл
Vlad писал(а):
P.S. Ну а дейкстровский WHILE - видимо из любви к искусству, практической ценности (хоть с учетом специфики ARM, хоть без) в нем никакой.
Vlad писал(а):
info21 писал(а):
Ну вот опять, пытаетесь сделать мину... С обоснованиями, как всегда, напряженка...
Всё еще не видно Вашего обоснования


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

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Илья Ермаков писал(а):
Не удержусь - нарисую дейкстровский цикл для предыдущего примера на Драконе:
Изображение
Как выразительно выглядят конъюнкции и дизъюнкции. Сразу видно, что выход вниз происходит по конъюнкции условий (вопросы и ответы "нет" нанизаны один за другим). Продолжение цикла - по дизъюнкции (вправо уходят два пути, от каждого из вопросов по ответу "да"). Для анализа постусловий в каждой точке схемы - красота.
Вообще-то это не совсем цикл Дейкстры. В цикле Дейкстры важная фишка в том, что выбор ветки цикла недетерменирован, то есть по сути случаен.
У Вас же чётко указано, что сначала идёт проверка "Слева свободно?", и в случае если нет -- то проверка "Сверху свободно?"
Цикл WHILE в Обероне-07 по сути не цикл Дейкстры...


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

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2449
Откуда: Россия, Томск
Geniepro писал(а):
Цикл WHILE в Обероне-07 по сути не цикл Дейкстры...
А где этот цикл описан у самого Дейкстры?


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

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

http://khpi-iip.mipk.kharkiv.edu/librar ... ewdx01.pdf стр. 40, "первый пример":
Цитата:
...

if x >= y -> m := x [] y >= x -> m := y fi
...

Поскольку (x>=y and y>=x) <> F, наша программа необязательно детерменирована. Если первоначально x=y, то оказывается неопределённым, какое из двух присваиваний будет выбранно для исполнения; такая недетерменированность совершенно корректна, так как мы показали, что выбор не имеет значения.

Конкретно в этой книге "Дисциплина программирования" я сейчас при беглом просмотре не нашёл упора на недетерменированность веток в его цикле, но по крайней мере в каких-то его же статьях это встречал...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Понедельник, 03 Ноябрь, 2008 10:28 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Да, Дейкстра отмечает недетерминированность как значимое качество (у него и IF-ELSIF также недетерминирован).
Однако на доказуемость-выразительность это никак не влияет. Влияет только на то, будет ли программист явно выписывать доп. конъюнкты к условиям или уже предполагать их априори ложными. Более техничен, видимо, всё же детерминированный вариант (условия упрощаются). Хотя недет. дисциплинирует программиста (если не указано что-то явно, то нельзя ни на что надеяться, система ведёт себя непредсказуемо).

P.S. Хотя недетерминированный открывает интересные выразительные возможности для приложений с нечёткой логикой (если ещё вероятность вешать на ветки...). В принципе, недет. ЦД выражает то поведение, когда система при нескольких доступных для выбора вариантах свободна в выборе из них.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Понедельник, 03 Ноябрь, 2008 13:55 
Аватара пользователя

Зарегистрирован: Суббота, 19 Ноябрь, 2005 15:59
Сообщения: 803
Откуда: Зеленоград
Лирическое отступление.
По поводу роли недетерминированности вдруг вспомнилась старая передача Гордона Программирование недетерминированных игр.
Там шахматам противопоставляются "короткие нарды" (точнее, Backgammon). Как полагает Б.Ф.Мельников (участник передачи), недетерминированность Backgammon, снижая роль перебора (а факт ли это?), повышает значимость качественной оценки позиции.
Это может представлять некоторый (IMHO, не слишком большой) интерес для теории info21 о двух типах ума. (BTW, существуют детерминированные игры, хуже поддающиеся алгоритмизации, чем Backgammon. Например - го.)

По поводу цикла Дейкстры.
Мне кажется, что детерминированность цикла WHILE...ELSIF...END не препятствует считать его циклом Дейкстры. Это просто особенность реализации ("фича" :) ).
А вообще нам в Обероне для счастья только недерминированности и не хватало. :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Понедельник, 03 Ноябрь, 2008 15:00 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
- Если будет дальнейшее обсуждение темы недерминированности-игр-..., то целесообразно идти в отдельную ветку. -


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Воскресенье, 16 Ноябрь, 2008 20:53 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Недели две назад пришёл в голову ещё возможный пример применения цикла Дейкстры. Написал сообщение, но отправлять раздумал. Поскольку сейчас наткнулся на тот же пример у Гриса "Наука программирования" (с. 191), то публикую.

=======================================
Ещё возможный пример.

Линейный поиск в неоднородной последовательности (т.е. где на некоторых шагах требуется сделать особый переход к следующему элементу). Блочный буфер, например, где блоки с массивами связаны в список.
Или рассмотрим пример с лин. поиском в матрице, построчным перебором элементов:
Код:
i := 0; j := 0;
WHILE (j < m) & ~ПредикатПоиска(matrix[i, j]) DO
  INC(j)
ELSIF (j >= m) & (i + 1 < n) THEN
  INC(i); j := 0
END
(* Post: (i = n) => <не найден>)
(i < n) => (j <  m) & ПредикатПоиска(matrix[i, j]) & <в предыдущих эл-х не найден>
*)


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

Вариант с обычным линейным поиском:

Код:
WHILE (j < m) & ~ПредикатПоиска(matrix[i, j]) DO
  INC(j);
  IF (j >= m) & (i + 1 < n) THEN
    INC(i); j := 0
  END
END


Неграмотный программёр обычно на этом примере будет бить себя пяткой в грудь, что нету жизни без двух вложенных FOR с брейком, ибо иначе "нужно лишние переменные заводить для выхода из внешнего цикла". (О чём Грис как раз и пишет).

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Воскресенье, 16 Ноябрь, 2008 22:22 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Чисто из интереса для сравнения написал аналогичное решение на Хаскелле (разумеется!), немного изменив задачу, что бы она стала более идеоматичной для Хаскелла. Вместо матрицы (двумерного массива) даётся список списков, а результат имеет два явно выраженных значения: не найдено (Nothing) или найдено по конкретным координатам (Just (i, j)), ну и сам этот код выделен в отдельную функцию для упрощения его повторного использования...
Код:
search :: (a -> Bool) -> [[a]] -> Maybe (Int, Int)

search p matrix = search' 0 0 matrix
  where
    search' _ _     []                  = Nothing
    search' i j ((x:xs):ms) | p x       = Just (i, j)
                            | otherwise = search'   i   (j+1) (xs:ms)
    search' i _ (  []  :ms)             = search' (i+1)   0      ms
Подфункция search' здесь является именно циклом Дейкстры, при чём как раз в его, Дейкстры, понимании -- все ветви цикла равноправны и, в принципе, могут выбираться недетерменированно...

Ну и пример использования:
Код:
Prelude Main> let matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]
Prelude Main> search (== 0) matrix
Nothing
Prelude Main> search (/= 1) matrix
Just (0,1)
Prelude Main> search (== 8) matrix
Just (2,1)
Prelude Main> let Just (i, j) = search (== 9) matrix
Prelude Main> matrix !! i !! j
9


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Воскресенье, 16 Ноябрь, 2008 22:53 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Видите, как интересно: реально существенные паттерны будут воспроизводиться даже при принципиально разной внешней форме... Уметь бы нам ещё их хорошо видеть, находить глубинную суть за шелухой :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Воскресенье, 16 Ноябрь, 2008 23:11 
Аватара пользователя

Зарегистрирован: Суббота, 19 Ноябрь, 2005 15:59
Сообщения: 803
Откуда: Зеленоград
Илья Ермаков писал(а):
Неграмотный программёр обычно на этом примере будет бить себя пяткой в грудь, что нету жизни без двух вложенных FOR с брейком, ибо иначе "нужно лишние переменные заводить для выхода из внешнего цикла". (О чём Грис как раз и пишет).
Так ли уж неправ неграмотный программёр?
Всё-таки хорошо бы определиться, что для нас структурное программирование: техника пошагового уточнения программы (одно из главных приложений принципа "разделяй и властвуй") или "вечный бой" с goto?
У меня крепнет подозрение, что Дейкстру читать вредно. :roll:

Илья Ермаков писал(а):
P.S. Вообще, во многих задачах, которые якобы требуют вложенных циклов, на самом деле логика условий строго одномерная. Поэтому естественно просто развёртывать многомерную последовательность в линейную и строить общий цикл, идущий по ней.
Идея использовать цикл Дейкстры для устранения вложенных циклов весьма любопытна.
IMHO, стоит задуматься.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Воскресенье, 16 Ноябрь, 2008 23:34 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
AVC писал(а):
Так ли уж неправ неграмотный программёр?
Всё-таки хорошо бы определиться, что для нас структурное программирование: техника пошагового уточнения программы (одно из главных приложений принципа "разделяй и властвуй") или "вечный бой" с goto?
У меня крепнет подозрение, что Дейкстру читать вредно. :roll:

Пошагового уточнения исходя из чего? Из целей-постусловий. При проектировании от постусловий, с использованием инварианта goto просто не возникает. Никаким образом. Он просто ненужен.
Инвариант не для борьбы с goto придуман, а для выражения смысла циклов.


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

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


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

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


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

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