OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Суббота, 16 Ноябрь, 2019 01:37

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




Начать новую тему Ответить на тему  [ Сообщений: 72 ]  На страницу 1, 2, 3, 4  След.
Автор Сообщение
 Заголовок сообщения: Базовые паттерны циклов
СообщениеДобавлено: Суббота, 18 Апрель, 2009 00:05 
Модератор
Аватара пользователя

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

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

Схема "полный проход"

Код:
взять_первую_ситуацию;
WHILE ~конец_ситуаций (* т.е. "удалось взять очередную ситуацию" *) DO
  (* Предусловие: имеем текущую ситуацию, подлежащую обработке *)
  полезное_действие_в_текущей_ситуации;
  переход_к_следующей_ситуации
END


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

Пример с потоковым чтением. Правильно организованный интерфейс потокового чтения предоставляет функцию "считать очередной элемент" и признак, который показывает, было ли считывание успешным.
Код:
reader.Read(elem);
WHILE reader.Done() DO
  ...работаем с elem...
  reader.Read(elem)
END

Очевидно, что попыток чтения и должно быть на одну больше, чем оборотов цикла с полезным действием. И "дублирование" как раз по этой причине возникает, и любые попытки его "убрать" не приведут к прояснению ситуации, а только к запутыванию и потере прозрачности.

В других случаях начальное действие и переход могут быть разными:
Код:
it := items;
WHILE it # NIL DO
  ...работаем с it...
  it := it.next
END


Действия "взять_начальную", "перейти_к_следующей", не говоря про само полезное действие, могут быть сколь угодно необычными, самое главное - узнать саму семантику полного прохода, и без фантазий написать по шаблону.

Схема "линейный поиск"

Та же история - последовательность чего угодно... Задача - найти такую ситуацию, которая удовлетворяет условию поиска, или показать, что её нет (достигли конца последовательности).

Код:
взять_первую_ситуацию;
WHILE ~конец_ситуаций & ~( ... условие поиска ..) DO
  ... возможно, но не очень часто встречается  - действие над текущей ситуацией ...
  взять_следующую_ситуацию
END;
IF ~конец_ситуаций THEN
  ... нашли, делаем что надо, с той ситуацией, на которой остановился цикл...
ELSE
  ... не нашли, делаем что-то, если нужно
END


Важно, чтобы & вычислялся сокращённо (в нормальных языках так и есть), т.к. условие поиска может не иметь смысл в случае конец_ситуаций.

Касательно Дракона - там не нужно повторять IF после цикла, там за счёт разделения конъюнкции WHILE на две последовательных проверки получается два параллельных исхода из цикла - "нашли" и "не нашли", на которые и нанизываем дальнейшие действия. Очень выразительно.
viewtopic.php?p=21377#p21377

Касательно этого был ещё тут пример - viewtopic.php?f=7&t=1443
Про то, что как только узнали стандартную схему, дальше лучше "без фантазий".

Пример с "узнаванием" линейного поиска (Из программки одного моего студента)

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

Нужно написать для узла графа функцию ReadyForCalc(node): BOOLEAN.
Понимающий студент сразу видит, что это = "для любого непосредственного предка node выполнено defined".
Т.е. A anc : anc IN Ancestors(node) : anc.defined, где A - квантор всеобщности, A. Точно так же он знает, что это эквивалентно ~ ( E anc : anc IN Ancestors(node) : ~anc.defined, т.е. "среди предков не существует такого, для которого ~defined". Т.е. чтобы доказать, что "для любого..." нужно построить "опровергающий" линейный поиск обратного условия и вернуть отрицание результата этого поиска.
Ну и конкретно это отображается в код (граф хранится на квадратной матрице, так, как его вводят в редакторе - для простоты, чтоб не грузить студента ещё задачей авторазмещения элементов на листе):

Код:
   PROCEDURE ReadyForCalc (g: Flow.Grid; ref: Flow.Ref): BOOLEAN;
      VAR j: INTEGER; cell: Flow.Cell;
   BEGIN
      (* A cell : cell IN Anc(g[ref]) : cell.defined *)
      (* ~ ( E cell : cell IN Anc(g[ref]) : ~cell.defined *)
      (* т.е. линейный поиск ячейки с ~cell.defined. RETURN поиск_не_удался *)
      ASSERT (g[ref.x, ref.y].argCount > 0, 20);
      cell := g[ref.x, ref.y];
      j:= 0;
      WHILE (j < cell.argCount) & g[cell.args[j].x, cell.args[j].y].defined DO
         INC(j);    
      END;
      RETURN j = cell.argCount
   END ReadyForCalc;


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

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

Заведём две операции: Calc ищет в стопке те узлы, которые ReadyForCalc и выполняет расчёт их значений.
Step ищет в стопке обсчитанные вершины (они там могут оказаться в середине витка цикла, когда инвариант временно нарушен после Calc), выбрасывает их из стопки, а взамен помещает их непосредственных последователей (тех, которые ещё не попали).
Имеем полный проход:
Код:
поместить_в_стопку_начальные_аргументы;
Step;
WHILE количество_в_стопке > 0 DO
  Calc;
  Step
END


Как всегда, с помощью первой части тела цикла мы продвинулись вперёд, но нарушили соотношение-инвариант, с помощью второй - восстановили инвариант, после чего идёт проверка условия окончания.

Всего-то и делов.

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

Вот тут ещё было об инварианте:
viewtopic.php?p=21375#p21375

Ну что, неужто такая "жуткая математика"? Простые, естественные рассуждения, ровно настолько формальные, насколько это удобно, чтобы "иметь почву под ногами".


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

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

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


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

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

2. Язык как средство (дополнительное) формирования этих общих соображений, - "умственный велосипед".


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

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
2 sia:

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

У нас с Вами много общего. Я так же "носился" на втором курсе с перфокартами. Специальность "Радиотехника".
Так же многие мои убеждения "дошли" до меня не через голову, а через руки. Помню как-то один из своих первых проектов я переписывал с нуля не меньше десяти раз. Жуткий привереда. :) Всё искал выход из очередного "кризиса жанра". И, кстати, нашёл :!:

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


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

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
Илья Ермаков писал(а):
Ветка подходящая... Давайте зафиксируем для новичков два базовых паттерна циклов.
...
"В рамочку, и на стену!" :D

Илья, Вы не поверите! Закопипастил в отдельный документик, заPDFил, и на полочку, для своего сына.
Несмотря на обилие компьютерной литературы, почитать по самой дисциплине программирования практически нечего :( ! Подчёркиваю, не по какому-нибудь языку или системе, а именно по самой дисциплине программирования. Имхо, в этой нише образовался такой информационный голод, что любой захудалый учебник будет проглочен вместе с потрохами.
Другой такой пример -- книжки по оберонам. Книгу Свердлова я зачитал до дыр.

PS Извините за OFFTOP. Наболело, знания приходиться собирать буквально по крупицам. Да ещё сильно фильтровать, потому что пишущих "спецов-умников" много, а истина одна :)


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8196
Откуда: Троицк, Москва
igor писал(а):
Илья Ермаков писал(а):
Ветка подходящая... Давайте зафиксируем для новичков два базовых паттерна циклов.
...
"В рамочку, и на стену!" :D

Илья, Вы не поверите! Закопипастил в отдельный документик, заPDFил, и на полочку, для своего сына.
Давно уж заPDFено на стене для юношей:
http://www.inr.ac.ru/~info21/08.pdf


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 18 Апрель, 2009 13:01 

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
Info21 писал(а):
Давно уж заPDFено на стене для юношей:
http://www.inr.ac.ru/~info21/08.pdf
Спасибо! Качнул.
Только сейчас расшарили :) ? Файл ".../07.pdf", например, не доступен. И другие.


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8196
Откуда: Троицк, Москва
igor писал(а):
Info21 писал(а):
Давно уж заPDFено на стене для юношей:
http://www.inr.ac.ru/~info21/08.pdf
Спасибо! Качнул.
Только сейчас расшарили :) ? Файл ".../07.pdf", например, не доступен. И другие.
Почему же только сейчас. Вон Илья Евгеньевич давно уже интернализовал :)

Остальное просто не выкладывалось.


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

Зарегистрирован: Среда, 04 Июль, 2007 16:43
Сообщения: 233
Info21 писал(а):
Остальное просто не выкладывалось.

И не планируется выложить или опубликовать?


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

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
igor писал(а):
Закопипастил в отдельный документик, заPDFил, и на полочку, для своего сына.
Это Вы поторопились : ).

Цитата:
Код:
(* Предусловие: имеем текущую ситуацию, подлежащую обработке *)
Это инвариант а не предусловие.


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

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1040
Откуда: Россия, Чебоксары
Илья Ермаков писал(а):
Важно, чтобы & вычислялся сокращённо (в нормальных языках так и есть), т.к. условие поиска может не иметь смысл в случае конец_ситуаций.
Не ожидал такого безобразия - делаем неявные предположения о существенных свойствах исполнителя?!


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

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


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

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


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

Зарегистрирован: Вторник, 17 Июнь, 2008 12:13
Сообщения: 28
Info21 писал(а):
QWERTYProgrammer писал(а):
Info21 писал(а):
Остальное просто не выкладывалось.
И не планируется выложить или опубликовать?
Планируется. К сожалению, приведение понимания внутри головы к виду буков на бумаге -- труднорешаемая задача. Т.е. буквы на бумаге сделать можно, но в какой степени они будут передавать понимание -- непонятно.

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


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

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

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

3) Формат лекций и формат книжки -- разные по смыслу и цели. Преобразование достаточно трудоемко, и тут мы возвращаемся к 1)


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

Зарегистрирован: Вторник, 17 Июнь, 2008 12:13
Сообщения: 28
К умным себя никак не причисляю, поэтому на звание "дурак" не обижаюсь :) . Если серьезно, то остается только сожалеть. Но это позиция Автора, и ее следует уважать.


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

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


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

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9154
Откуда: Россия, Орёл
Valery Solovey писал(а):
Цитата:
Код:
(* Предусловие: имеем текущую ситуацию, подлежащую обработке *)
Это инвариант а не предусловие.

Валерий, обратите внимание, где это стоит. Это предусловие для очередной итерации цикла. Следующее, конечно, из инварианта - но инвариант более широкий - "имеем текущую ситуацию OR (count = 0)"


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

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3109
Откуда: Астрахань
Info21 писал(а):
stern писал(а):
... несомненный интерес.
Спасибо за комплимент. Проблемы две. 1) основная работа.

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

3) Формат лекций и формат книжки -- разные по смыслу и цели. Преобразование достаточно трудоемко, и тут мы возвращаемся к 1)

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


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

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


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

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


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

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


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

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