OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Четверг, 17 Октябрь, 2019 09:25

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




Начать новую тему Ответить на тему  [ Сообщений: 25 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Обобщенный цикл
СообщениеДобавлено: Суббота, 15 Январь, 2011 07:29 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 530
Откуда: Москва
Я давно собирался написать статью по этому вопросу, да как-то все руки не доходят. Но, поскольку здесь viewtopic.php?f=27&t=3157&start=40 в очередной раз разгорелся базар по этому поводу, то напишу кое-какие тезисы.

Итак, имеем обобщенный цикл вида
Код:
цикл
   последовательность команд Х
   что-нибудь типа exit или break по условию
   последовательность команд Y
конец цикла
Середину с выходом можно гонять как слайдер вверх-вниз и получать граничные случаи: цикл while и цикл repeat..until. Это хорошо.
Плохо то, что формальный аппарат, описанный у Дейкстры-Грисса можно применять вроде бы только для циклов типа while.
В принципе, Кнут приводит аксиоматизацию Дала для обобщенного цикла:
Цитата:
Пусть: {P}S{Q} {Q & B}T{P}
Тогда: {P} loop: S; while B : T; repeat; {Q & ~B } (стр. 49)
В ней нет ничего сложного, но для простого программиста польза от этой записи равна строго нулю.
Тем не менее, все не так плохо. Надо только ответить на 2 вопроса.
1. Что является телом обобщенного цикла?
2. В какой точке цикла нужно проверять инвариант цикла?
Ответить на эти вопросы проще, чем их поставить.
Если немного подумать, то легко понять, что телом цикла является кусок Y;X. Т.е., чтобы рассуждать о таком цикле, нужно просто мысленно подставить вехний кусок X под нижний Y. А вся конструкция эквивалентна последовательности
Код:
X;
пока условие цикл
   Y;
   X;
конец цикла
Здесь как раз и вылезает то самое дублирование кода.

Что касается инварианта цикла, которой традиционно проверяется "перед циклом", то уже становится ясно, что в данном случае инвариант нужно проверять внутри цикла, в точке перед условием выхода.

Вот и все.
Все наработки для циклов while остаются в силе (в том числе и весь бред про линейный поиск, для любителей).

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


Последний раз редактировалось Peter Almazov Среда, 19 Январь, 2011 18:45, всего редактировалось 2 раз(а).

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Обобщенный цикл
СообщениеДобавлено: Суббота, 15 Январь, 2011 19:43 
Модератор
Аватара пользователя

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

===
Peter Almazov писал(а):
В заключение надо отметить, что с эстетической точки зрения цикл с выходом из середины выглядит, конечно, отвратно. И вреден для неокрепших умов. Здесь - самое главное иметь четкую картину в голове. И креплять ум(ы) :) .


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

===

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Обобщенный цикл
СообщениеДобавлено: Суббота, 15 Январь, 2011 19:52 

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Обобщенный цикл
СообщениеДобавлено: Суббота, 15 Январь, 2011 19:56 

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

Это решается привычкой, то есть воспитанием.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Обобщенный цикл
СообщениеДобавлено: Суббота, 15 Январь, 2011 20:01 

Зарегистрирован: Воскресенье, 06 Апрель, 2008 14:43
Сообщения: 557
.


Последний раз редактировалось ==== Воскресенье, 16 Январь, 2011 08:46, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Обобщенный цикл
СообщениеДобавлено: Суббота, 15 Январь, 2011 20:02 

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

Вложенные процедуры не всегда удобны и к месту выглядят.
Например, в сях их вообще нет.
В С#, правда, их можно делать по месту надобности лямбдами, то есть уже почти на уровне Хаскелла/Окамла.
В паскалевом семействе вложенные процедуры приходится делать чёрти где от того места, где нужно их тело, то есть при создании и изучении такой процедуры приходится сбивать контекст -- смотреть вверх-вниз. Неудобно.


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

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


В чём прогресс?

Я всегда считал, что рост профессионального уровня не является причиной для ослабления жесткой дисциплины, которая вводится для начинающих. Жёсткость рамок должна сохраняться навсегда.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Обобщенный цикл
СообщениеДобавлено: Суббота, 15 Январь, 2011 20:22 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Geniepro писал(а):
Илья Ермаков писал(а):
По поводу применимости: возможно, это полезно в случаях, когда повторяемый кусок большой, а есть причины не выносить его во вложенную процедуру. Вот, кстати, как раз в языках без вложенных процедур ? ...

Вложенные процедуры не всегда удобны и к месту выглядят.
Например, в сях их вообще нет.
В С#, правда, их можно делать по месту надобности лямбдами, то есть уже почти на уровне Хаскелла/Окамла.

http://valexey.blogspot.com/2009/09/blog-post_07.html
Geniepro писал(а):
В паскалевом семействе вложенные процедуры приходится делать чёрти где от того места, где нужно их тело, то есть при создании и изучении такой процедуры приходится сбивать контекст -- смотреть вверх-вниз. Неудобно.

На это принято отвечать, мол нефиг писать функции которые не умещаются на одном экране :-)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Обобщенный цикл
СообщениеДобавлено: Суббота, 15 Январь, 2011 20:29 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 530
Откуда: Москва
Если речь идет о том, чтобы преобразовать цикл с выходом из середины к виду цикл while, то нужно использовать вложенную функцию, которая всегда будет иметь побочный эффект. А функции с побочным эффектом "дурно пахнут".


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Обобщенный цикл
СообщениеДобавлено: Суббота, 15 Январь, 2011 20:36 
Модератор
Аватара пользователя

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

Конечно, в эпоху модности ФП за это будут смотреть криво :))


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Обобщенный цикл
СообщениеДобавлено: Суббота, 15 Январь, 2011 20:43 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Alexey Veselovsky писал(а):
Geniepro писал(а):
Вложенные процедуры не всегда удобны и к месту выглядят.
Например, в сях их вообще нет.
В С#, правда, их можно делать по месту надобности лямбдами, то есть уже почти на уровне Хаскелла/Окамла.

http://valexey.blogspot.com/2009/09/blog-post_07.html
Про C++ я и не упоминал. Там вроде тоже можно лямбды делать, делегатами симитировать.
А вариант, приведённый Вами в статье, -- это всё равно что чесать левой ногой правое ухо. Затуманивание смысла...


Последний раз редактировалось Geniepro Суббота, 15 Январь, 2011 20:44, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Обобщенный цикл
СообщениеДобавлено: Суббота, 15 Январь, 2011 20:43 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Илья Ермаков писал(а):
Если функция локальная, то про "дурной запах" - просто предрассудок, имхо.

Конечно, в эпоху модности ФП за это будут смотреть криво :))

Если в монаде IO, то нормально :-) Ну или в ST.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Обобщенный цикл
СообщениеДобавлено: Суббота, 15 Январь, 2011 20:45 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Geniepro писал(а):
Про C++ я и не упоминал. Там вроде тоже можно лямбды делать, делегатами симитировать.
А вариант, приведённый Вами в статье, -- это всё равно что чесать левой ногой правое ухо. Затуманивание смысла...

А по моему, всё как раз там получается однозначно и очевидно. Вот эти переменные у нас могут меняться локальными функциями, а вот эти нет. Соответственно локальные функции зависят от этих и этих переменных. Удобно для рефакторинга. Сразу видно что и где. По сути, явно огороженное замыкание получается.


Последний раз редактировалось Alexey Veselovsky Суббота, 15 Январь, 2011 20:46, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Обобщенный цикл
СообщениеДобавлено: Суббота, 15 Январь, 2011 20:46 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Alexey Veselovsky писал(а):
Если в монаде IO, то нормально :-) Ну или в ST.

У монад IO/ST суть не в том, что они разрешают побочные эффекты, а в том, что они их строго локализуют. То есть дают на ними, эффектами этими побочными, строгий контроль.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Обобщенный цикл
СообщениеДобавлено: Суббота, 15 Январь, 2011 20:47 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Geniepro писал(а):
Alexey Veselovsky писал(а):
Если в монаде IO, то нормально :-) Ну или в ST.

У монад IO/ST суть не в том, что они разрешают побочные эффекты, а в том, что они их строго локализуют. То есть дают на ними, эффектами этими побочными, строгий контроль.

Именно потому я и сказал, что нормально в них :-)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Обобщенный цикл
СообщениеДобавлено: Суббота, 15 Январь, 2011 20:47 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Alexey Veselovsky писал(а):
А по моему, всё как раз там получается однозначно и очевидно. Вот эти переменные у нас могут меняться локальными функциями, а вот эти нет. Соответственно локальные функции зависят от этих и этих переменных. Удобно для рефакторинга. Сразу видно что и где. По сути, явно огороженное замыкание получается.

Ну вообще интересно, надо подумать, попробовать...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Обобщенный цикл
СообщениеДобавлено: Понедельник, 31 Январь, 2011 10:22 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9147
Откуда: Россия, Орёл
Есть предложение ещё более общего цикла. Который бы как раз покрыл вариант Петра и ещё случай, разбиравшийся в теме viewtopic.php?f=27&t=3175 "AND THEN". И был бы в языке вместо LOOP. Мне кажется, Info21 даже предлагал такое что-то, но если вру, прошу извинить. :)

Проблема, которую решают иногда с помощью LOOP, как известно, в том, что между конъюнктами условия цикла надо бы что-то сложное вычислять. Цикл Петра как раз позволяет вычислять вообще перед всем условием, избегая дублирования и перенося такие вычисления из конца тела в более естественное место в начало.
Но иногда надо действовать между конъюнктами.

Код:
LOOP
  ... ; ... ;
CHECK Conjunct1 DO
  ...; ... ;
CHECK Conjunct2 DO
  ...; ... ;
END


В случае истинности конъюнкта выполнение проходит в следующую секцию цикла, уже под охраной условия конъюнкта.
В случае ложности, разумеется, цикл завершается.
Условие цикла и его отрицание легко собирается в уме.

В Аде есть такой цикл с exit when, но нужно, чтобы было именно условие продолжения, для грамотного построения цикла думать через него удобнее. И строить цикл почти как обычный WHILE, но с промежуточными вычислениями. В случае exit when программист вынужден думать наоборот, "через одно место": "а когда же мне спрыгнуть с цикла".

Ситуация из обсуждавшейся темы с цепочкой проверок и прерыванием решается с добавлением в конце CHECK FALSE DO END.
Этап, на котором прервалось, отслеживаем по спец. целой переменной.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Обобщенный цикл
СообщениеДобавлено: Понедельник, 31 Январь, 2011 11:21 
Аватара пользователя

Зарегистрирован: Воскресенье, 08 Июль, 2007 00:38
Сообщения: 778
Откуда: Москва
Предложенная Ильей Ермаковым конструкция обобщенного цикла добавлена в PureBuilder в несколько иной форме.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Обобщенный цикл
СообщениеДобавлено: Понедельник, 31 Январь, 2011 12:02 
Аватара пользователя

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Обобщенный цикл
СообщениеДобавлено: Понедельник, 31 Январь, 2011 13:55 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 530
Откуда: Москва
Илья Ермаков писал(а):
Есть предложение ещё более общего цикла. Который бы как раз покрыл вариант Петра и ещё случай, разбиравшийся в теме viewtopic.php?f=27&t=3175 "AND THEN".
Я довольно скептически отнесся к той ветке и изобретенным там конструкциям.
Но, могу заметить, что полный вариант статьи о циклах предусматривал также обсуждение циклов со многими выходами.
Однако эта часть пока не созрела для изложения.


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

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


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

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


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

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