OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Вторник, 19 Март, 2024 14:53

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




Начать новую тему Ответить на тему  [ Сообщений: 19 ] 
Автор Сообщение
СообщениеДобавлено: Вторник, 08 Сентябрь, 2009 23:12 
Модератор
Аватара пользователя

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

Пример - знаем, что в разбираемом тексте впереди нас ждёт вьюшка:
Цитата:
r.ReadChar(ch);
WHILE ~(rd.view # NIL) DO
.. что-то делается с ch..
rd.ReadChar(ch)
END


Теперь представим, что указанный фрагмент программы получает неверный фрагмент текста, где вьюшки нет. Получаем зависание. И можем долго ломать голову, что не так. Ещё неприятнее, если это дойдёт до конечного продукта.

Вместо этого всегда используем линейный поиск с двумя исходами, только если мы знаем, что исход должен быть один (найдено), то вместо IF в конце ставим ASSERT с кодом инвариантного утверждения (от 100):

Цитата:
r.ReadChar(ch);
WHILE ~rd.eot & ~(rd.view # NIL) DO
.. что-то делается с ch..
rd.ReadChar(ch)
END;
ASSERT(~rd.eot, 100);


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

Пример - из реальной ситуации. Человек разрабатывает компонент системы, и сейчас мы разбирали вот это место. И пришли к изложенному здесь правилу.
А компонент-то серверного назначения... И останов нормально обработается, а вот зависание - уже хуже; необходим перезапуск экземпляра ББ.

Ещё один важный вывод:
Пока мы остаёмся в рамках двух базовых схем - полный проход и линейный поиск, зависаний при некоторых входных данных можно не опасаться..
Подкреплено длительным опытом. Ошибок на зависание в своей практике не припоминаю. Т.е. если изменение в цикле сделано неверно - то он зависает в принципе, независимо от входных данных.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 09 Сентябрь, 2009 13:47 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Илья Ермаков писал(а):
Даже если вы знаете, что поиск у вас с одним исходом (элемент будет в последовательности), лучше не вырождать цикл WHILE до полного прохода.
Вы сначала определитесь с предусловиями, а потом уж пишите программу. А то получаются рекомендации уровня сантехника, а не математика - "Так лучше возьмет".
Кроме этого, еще раз наглядно демонстрируется "ценность" шаблона "Линейный поиск им. Ткачева". Предлагается писать
WHILE ~(rd.view # NIL) DO
вместо
WHILE rd.view = NIL DO

Илья, Вы находитесь на неверном пути. Прочтите, наконец, классиков.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 19 Сентябрь, 2009 08:45 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Peter Almazov писал(а):
Илья Ермаков писал(а):
Даже если вы знаете, что поиск у вас с одним исходом (элемент будет в последовательности), лучше не вырождать цикл WHILE до полного прохода.
Вы сначала определитесь с предусловиями, а потом уж пишите программу. А то получаются рекомендации уровня сантехника, а не математика - "Так лучше возьмет".


Программист всегда должен исходить из того, что предусловие может быть нарушено надсистемой.
Именно для этого мы используем ASSERT, не так ли?
Но я не могу написать до цикла ASSERT("в тексте есть вьшка").
Значит, хорошо бы составить цикл так, чтобы он обеспечил аварийный останов по нарушению предусловия.

Цитата:
Кроме этого, еще раз наглядно демонстрируется "ценность" шаблона "Линейный поиск им. Ткачева". Предлагается писать
WHILE ~(rd.view # NIL) DO

Это не линейный поиск. Это простой линейный проход (линейный просмотр Дейкстры).

Не предлагается. Я не имею окончательного мнения на сей счёт. Пробую и так, и так.
Для меня критерий "правильности" всегда за пределами формализма. Формализм - способ выражения семантики.
По семантике мозг строит цикл "пока не нашли требуемый элемент". Например, WHILE rd.view # x DO.. "не равен искомому". У нас искомый элемент - любой. Любой - "не NIL". Не-нашли-не-NIL. WHILE ~ANY_VALID(rd.view) DO .. Отсюда и двойное отрицание.
Если мы будем записывать выкладки под ход мыслей, оно в таких случаях будет возникать. Вопрос в том, упрощать его или нет. Аргумент "за" - короче, как бы правильней и т.п. Аргумент "против" - если неупрощённый вариант ближе к исходной мысли, из которой спроектирован цикл, то он понятнее для чтения-проверки, может быть. А может и не быть.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 19 Сентябрь, 2009 08:49 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Peter Almazov писал(а):
Прочтите, наконец, классиков.


Не всё дадено в готовом виде. Например, о специфике управляющих алгоритмов написано весьма мало. (Много ли книг, где рядом с определением алгоритма можно увидеть слова "система", "поведение"? В учебнике Дейкстры, в первой главе, кстати можно. Именно так, естественнонаучно, он и вводит понятие алгоритма. Но дальше управляющие алгоритмы не затрагиваются вообще - да и задачи он такой для своих книг не ставил.)
А управляющие алгоритмы очень сильно отличаются от вычисляющих. (Отсюда, кстати, Ваше непонимание Дракона. Претензии того характера, что конечный автомат люди представляют не структурными конструкциями, да ещё нетекстово :) ).


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 19 Сентябрь, 2009 09:05 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Решил в этом году для студентов "первого года программирования" (у нас нек. специальности - 2 курс, некоторые - 3-й) выкинуть FOR ффтопку. Раньше на этапе до переменных, при работе с исполнителями, использовал. Теперь подумал - счётчик так и так объявлять.

Но
Код:
i := 0;
WHILE i < 5 DO

  INC(i)
END

с пояснением, что счётчик i показывает число раз, которое мы уже сделали - гораздо понятней, чем "запаянная" конструкция FOR. При этом сам привык писать FOR. Но с чистой точки зрения... Нафиг, нафиг.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 20 Сентябрь, 2009 21:22 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Илья, спасибо ответы.
Илья Ермаков писал(а):
Программист всегда должен исходить из того, что предусловие может быть нарушено надсистемой.
Именно для этого мы используем ASSERT, не так ли?
Мне такие рассуждения не нравятся. Так можно очень далеко зайти. Например: а если "чуть-чуть" сбойнет процессор? А если повредится содержимое памяти? А если оно ещё сильнее повредится? И т. п.
Если есть вероятность нарушения предусловия надсистемой, то нужно так и формулировать предусловие.

Илья Ермаков писал(а):
Это не линейный поиск. Это простой линейный проход (линейный просмотр Дейкстры).
Мне вот непонятно, нахрена было устраивать на ровном месте путаницу с термином "линейный поиск". Зачем "отменять" Дейкстру и Гриса? Ну использовали бы другой термин – "последовательный поиск", что ли. А теперь с любой публикацией будете иметь проблемы, придется постоянно объяснять, что имеется в виду под термином "линейный поиск". Буржуи уж точно сочтут таких авторов дебилами.
Кроме того, незаметно произошла подмена метода Дейкстры на два частных случая. Остальные случаи вообще не рассматриваются, я вижу постоянные попытки свести всё к "двум базовых схемам".

По поводу цикла вида
Код:
WHILE rd.view = NIL DO
  .. что-то делается с ch..
  rd.ReadChar(ch)
END
все очень просто: в заголовке цикла стоит охрана, тело цикла выполняется только тогда, когда охрана истинна. Продвигаемя вперед, пока это можно делать, это же классика. Отрицания нет даже в "ходе мыслей".

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 20 Сентябрь, 2009 21:43 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Peter Almazov писал(а):
Илья, спасибо ответы.
Илья Ермаков писал(а):
Программист всегда должен исходить из того, что предусловие может быть нарушено надсистемой.
Именно для этого мы используем ASSERT, не так ли?
Мне такие рассуждения не нравятся. Так можно очень далеко зайти.
Если есть вероятность нарушения предусловия надсистемой, то нужно так и формулировать предусловие.


Есть идеальный случай, а есть реальность. В которой всегда будут опечатки. Поэтому стопоры ошибок в виде ASSERT необходимы всюду, где только возможно.
Составляем процедуру - мы не знаем, когда и откуда она будет использована. Это - внешний мир, его всегда надо проверять. Хороший стиль - алгоритм должен отказаться работать, если предусловия не соблюдены.
Т.е. из нарушения предусловий следует не непредсказуемое поведение, а строгий авост.


Цитата:
Илья Ермаков писал(а):
Это не линейный поиск. Это простой линейный проход (линейный просмотр Дейкстры).

Мне вот непонятно, нахрена было устраивать на ровном месте путаницу с термином "линейный поиск". Зачем "отменять" Дейкстру и Гриса? Ну использовали бы другой термин – "последовательный поиск", что ли.

Так в переводе Дейкстры термин "линейный просмотр", если мне память не изменяет.

Цитата:
Кроме того, незаметно произошла подмена метода Дейкстры на два частных случая. Остальные случаи вообще не рассматриваются, я вижу постоянные попытки свести всё к "двум базовых схемам".


Так кто виноват, что большинство циклов - это обработка последовательностей. Некий dataflow. Расчётные циклы с варьированием по некоторому закону нескольких величин - редкость в массовом программировании.
А ПП и ЛП сами вытекают, как только у нас в постусловии возникло A или E.

Цитата:
По поводу цикла вида
Код:
WHILE rd.view = NIL DO
  .. что-то делается с ch..
  rd.ReadChar(ch)
END
все очень просто: в заголовке цикла стоит охрана, тело цикла выполняется только тогда, когда охрана истинна. Продвигаемя вперед, пока это можно делать, это же классика. Отрицания нет даже в "ходе мыслей".

Извините, это как раз технарские рассуждения. "Цикл крутится пока...". "Классика" - это то, что назначение каждого блока программы - обеспечить постусловие. Решить уравнение в предикатах, можно так сказать.
Поэтому интересует ЦЕЛЬ, для которой построен цикл. Целевой предикат.

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


Хотите верьте - хотите нет. Поведение во времени и вычисление, как трансформация данных, - разные вещи. Структурный алгоритм и конечный автомат - различающиеся формализмы.

Попробуйте перепишите структурно мне автомат вот этого протокола:
viewtopic.php?f=62&t=1148

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

Автоматное программирование - это широкий арсенал формальных методов и инструментов. Для встроенки это практически стандарт.

http://ru.wikipedia.org/wiki/%D0%90%D0% ... 0%B8%D0%B5

http://softcraft.ru/auto.shtml


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 21 Сентябрь, 2009 06:40 
Аватара пользователя

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 21 Сентябрь, 2009 07:48 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
Илья Ермаков писал(а):
Решил в этом году для студентов "первого года программирования" выкинуть FOR ффтопку. Раньше на этапе до переменных, при работе с исполнителями, использовал. Теперь подумал - счётчик так и так объявлять.

Но
Код:
i := 0;
WHILE i < 5 DO

  INC(i)
END

с пояснением, что счётчик i показывает число раз, которое мы уже сделали - гораздо понятней, чем "запаянная" конструкция FOR. При этом сам привык писать FOR. Но с чистой точки зрения... Нафиг, нафиг.

ИМХО абсолютно правильно! Есть циклы с предусловием и постусловием. Остальные - дополнительные удобства.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 21 Сентябрь, 2009 08:09 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Info21 писал(а):
Peter Almazov писал(а):
я вижу постоянные попытки свести всё к "двум базовых схемам".
Ну, не знаю. Смотря куда Вы смотрите :)
На этот вопрос могу ответить предельно точно: я смотрю на посты Ильи Ермакова. Остальных эти проблемы, похоже, не волнуют.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 21 Сентябрь, 2009 08:44 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Илья Ермаков писал(а):
Извините, это как раз технарские рассуждения. "Цикл крутится пока...". "Классика" - это то, что назначение каждого блока программы - обеспечить постусловие. Решить уравнение в предикатах, можно так сказать.
Поэтому интересует ЦЕЛЬ, для которой построен цикл. Целевой предикат.
Вот эта цитата как раз и демонстрирует непонимание основ. Цель цикла - продвинуться к постусловию, сохраняя при этом инвариант. Продвижение указателя по файлу вперед (тело цикла) приближает нас к решению. Охрана гарантирует, что продвигаться можно, инвариант не будет разрушен.
"Решить уравнение в предикатах" - эти слова как раз и отпугивают громадное большинство практических программистов от метода Дейкстры. Это то, что реально не надо делать, это слишком сложно.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 21 Сентябрь, 2009 10:41 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Peter Almazov писал(а):
Info21 писал(а):
Peter Almazov писал(а):
я вижу постоянные попытки свести всё к "двум базовых схемам".
Ну, не знаю. Смотря куда Вы смотрите :)
На этот вопрос могу ответить предельно точно: я смотрю на посты Ильи Ермакова.
Тогда и обобщения формулировать нужно с такой же степенью предельной точности.

Peter Almazov писал(а):
Остальных эти проблемы, похоже, не волнуют.
Проблемой Вашего диспута с ИЕ действительно нелегко взволноваться :)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 21 Сентябрь, 2009 20:41 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
Peter Almazov писал(а):
Илья Ермаков писал(а):
Извините, это как раз технарские рассуждения. "Цикл крутится пока...". "Классика" - это то, что назначение каждого блока программы - обеспечить постусловие. Решить уравнение в предикатах, можно так сказать.
Поэтому интересует ЦЕЛЬ, для которой построен цикл. Целевой предикат.
Вот эта цитата как раз и демонстрирует непонимание основ. Цель цикла - продвинуться к постусловию, сохраняя при этом инвариант.
Это у Вас непонимание основ. Цель цикла - как и любой другой команды - обеспечить истинность постусловия при допустимом слабейшем предусловии. А то, о чём Вы говорите, позволяет обеспечить корректное завершение работы цикла, принимая во внимание специфику его работы.
Впрочим, Илья тоже понаввёл неопределённых терминов... В книге говориться о командах, а не о блоках (являющихся частным случаем команд).


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 21 Сентябрь, 2009 21:05 
Модератор
Аватара пользователя

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 22 Сентябрь, 2009 17:09 

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
Валерий Лаптев писал(а):
Есть циклы с предусловием и постусловием. Остальные - дополнительные удобства.
ИМХО, термины "цикл с предусловием" и "цикл с постусловием" не совсем корректны, если не сказать большего.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 22 Сентябрь, 2009 17:21 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Вообще есть сложившиеся термины: цикл с условием продолжения работы и цикл с условием завершения работы...


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 23 Сентябрь, 2009 12:02 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
igor писал(а):
Валерий Лаптев писал(а):
Есть циклы с предусловием и постусловием. Остальные - дополнительные удобства.
ИМХО, термины "цикл с предусловием" и "цикл с постусловием" не совсем корректны, если не сказать большего.

Да, согласен. Это жаргон уже так сложился. Женяпро уже правильно сформулировал.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 24 Сентябрь, 2009 10:02 
Модератор
Аватара пользователя

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

viewtopic.php?f=62&t=1899


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 01 Октябрь, 2009 10:36 
Модератор
Аватара пользователя

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

Н.Вирт, "Алгоритмы и структуры данных"

Код:
1.8.1  Линейный поиск
   Если нет никакой дополнительной информации о данных, то очевидное реше?ние — последовательно проходить по массиву, шаг за шагом увеличивая вели?чину той части массива, где искомый элемент заведомо отсутствует. Это решение известно как линейный поиск. Поиск прекращается при одном из двух условий:
   1. Элемент найден, т.е. ai = x.
   2. Просмотрен весь массив, но элемент не найден.
Приходим к следующему алгоритму:
   i := 0;
   WHILE (i < N) & (a[i] # x) DO INC(i) END


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 19 ] 

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


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

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


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

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