Оберон-клуб «ВЄДАsoft»

Твердыня модульных языков
Текущее время: 17 сен 2019, 02:49

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




Начать новую тему Ответить на тему  [ Сообщений: 40 ]  На страницу 1, 2, 3, 4  След.
Автор Сообщение
 Заголовок сообщения: Мы наш, мы новый FOR построим
СообщениеДобавлено: 03 мар 2013, 21:05 
Не в сети
Администратор
Аватара пользователя

Сообщения: 269
Откуда: Россия
Решил начать новую ветку (конечно родственную теме viewtopic.php?f=8&t=83), потому что считаю необходимо как-то структурировать материал.
Если по вышеуказанной ссылке мы попадали в обсуждение недостатков стандартного FOR, то здесь задумаемся, как мог бы быть устроен этот оператор в идеале.
Сначала предлагаю обсудить семантику, т.е. как мог бы быть задан предмет обсуждения в "Сообщении об языке Оберон" (ну Оберон 2 , например).
Я бы вообще не задавал семантику FOR конкретным фрагментом кода, т.к. это провоцирует программиста на разные трюки (как я уже писал)).
Давайте для начала ограничимся циклом с шагом 1. Можно, опуская формалистику в виде Н(или ненормальных :))ФБН, семантику оператора:
Код: "OBERON"
  1. FOR x := A TO B DO
  2. тело цикла
  3. END
словесно определить так: "Тело цикла выполняется для всех значений переменной x из отрезка A..B в возрастающем порядке. Если A>B, то отрезок считается пустым и тело цикла не выполняется ни разу. Значение переменной цикла после выполнения цикла не определено, эффект изменения значения этой переменной внутри цикла не определен. На значение переменной при досрочном прерывании цикла тоже полагаться не следует." Стандартный FOR Оберона под эту семантику почти подходит. Почти - это,конечно же, зависание при B=MAX(T).
Способ реализации при таком описании семантики оставался бы за автором конкретной платформы. А неопределенность дает автору большую свободу для оптимизации (например, если переменная цикла вообще не используется в самом теле цикла, то вместо нее можно было бы реализовать счетчик в каком-нибудь регистре).
Но мудрость создателей Оберона, видимо, подсказала им, что программист очень любит трюки, и недосказанность (намеренная!) семантики подвигнет его на исследования. После этого исследователи посчитают неопределённость вполне определенной и ...И получат несовместимость программ разных версий на разных платформах!
Ну так бы им и надо, пусть научатся операторы по предназначению использовать. Но Вирт с Мёссенбёком, вздохнули «Если уж трюки, то пусть одинаково у всех работают» и задали семантику через эквивалентный фрагмент кода (упрощаю, т.к. не в temp:=B проблема):
Код: "OBERON"
  1. (* С0. стандартный FOR *)
  2. x:=A;
  3. WHILE x <= B DO
  4. ...
  5. INC(x)
  6. END
. Этот цикл, как легко видеть, аналог стандартного "сишного"
Код: "C"
for (x=A;x<=B;x++){};
и имеет дефект, подробно разобранный в соседней теме.
А как избавиться от этого дефекта, как должен выглядеть верный фрагмент? Мы не должны выполнять инкремент на последней итерации. Попробуем так:
Код: "OBERON"
  1. (* С1. без последнего инкремента *)
  2. x:=A; break:=FALSE;
  3. WHILE ~break & (x <= B) DO
  4. ...
  5. IF x < B THEN INC(x) ELSE break:=TRUE END
  6. END

На мой взгляд, самый правильный цикл — незачем брать следующий элемент, если все обработаны. На самой последней итерации инкремент не выполняется, после завершения цикла X=B (или А, если было A>B), в отличие от стандартного С0, где после завершения X=B+1.
Однако вспомним, что проблема зацикливания возникает только при B=MAX(T). Отсюда
Код: "OBERON"
  1. (* С2. без зацикливания *)
  2. x:=A;break:=FALSE;
  3. WHILE ~break & (x <= B) DO
  4. ...
  5. IF x < MAX(T) THEN INC(x) ELSE break:=TRUE END
  6. END
Здесь, как и в стандарте, инкремент происходит после каждой итерации. Отличия при B=MAX(T): С2 остановится с х=В=MAX(T), стандартный С0 зациклится, поэтому бессмысленно говорить о значении x по окончании (окончания вообще не будет).
Чем хорош вариант С2:
1)отличия от стандарта минимальные
2)сравнение x < MAX(T) реализовать легче, чем x < B (для этого есть даже специальное сложение с отсечением, правда в наборе команд ММХ, не у Спектрума). А умный компилятор может вообще убрать проверку, если увидит, что В всегда меньше MAX(T).

Кто-то предложит еще? Напоминаю, что обсуждаем пока семантику, поэтому фрагменты кода рассматриваем на самом высоком уровне, т. е. На Обероне. Ну и циклы пока берем с шагом 1.

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
 Заголовок сообщения: Re: Мы наш, мы новый FOR построим
СообщениеДобавлено: 05 мар 2013, 20:09 
Не в сети
Администратор
Аватара пользователя

Сообщения: 269
Откуда: Россия
В порядке самокритики. Я призывал всех не использовать трюки, мыслить структурно, составлять пред- и постусловия, а сам... А сам написал оператор выхода из цикла! См. фрагменты кода С1 и С2 выше. Да, в Обероне нет такого оператора, да, это присваивание булевой переменной. Но по смыслу это именно оператор выхода, о чем говорит имя break! То, что я смоделировал отсутствующий в ЯП оператор из имеющихся средств, не отменяет моего неструктурного подхода. Когда я писал break:=TRUE, я думал именно "а теперь выйдем из цикла" (уж я то знаю, о чем я думал :) ).
В оправдание замечу, что я не составлял программу заново, а пытался модифицировать фрагмент С0. Я пытался избежать лишнего инкремента на последней итерации, поэтому и принял решение досрочно прервать цикл. И зря! Чужую программу тоже надо представлять структурно: не "проверяем условие в заголовке, заходим внутрь, выполняем этот оператор, этот, а теперь выходим" , а "этот цикл служит для такой-то цели, поэтому у него такое-то постусловие, поэтому и в заголовке цикла вот этот предикат, а внутри вот этот оператор восстанавливающий инвариант".
Потерпите, я начал это сообщение не для того, чтобы похвастаться, что я структурно святее самого Дейкстры. :) Просто это повод переписать уже готовый (и работающий) фрагмент С2 , используя на этот раз структурный подход (схема "полный проход").И попытаюсь разобрать этот подход о-о-чень подробно, потому что вижу там некоторые ...гм...не ошибки, а скорее недоговоренности, напрямую связанные с проблемой взятия лишнего элемента в цикле FOR.

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
 Заголовок сообщения: Re: Мы наш, мы новый FOR построим
СообщениеДобавлено: 06 мар 2013, 21:24 
Не в сети
Администратор
Аватара пользователя

Сообщения: 269
Откуда: Россия
Представим, что мы вообще не видели код С0, а пытаемся запрограммировать обработку подобласти в указанных границах A..B. Сразу опознаём схему "полный проход"и пытаемся ее применить:
Код: "OBERON"
  1. взять_первую_ситуацию;
  2. WHILE ~конец_ситуаций (* т.е. "удалось взять очередную ситуацию" *) DO
  3. (* Предусловие: имеем текущую ситуацию, подлежащую обработке *)
  4. полезное_действие_в_текущей_ситуации;
  5. переход_к_следующей_ситуации
  6. END

В этой схеме есть некие ситуации\элементы\объекты\члены\единицы (то, из чего состоит последовательность) и переходы между ними. «Полезное_действие_в_текущей_ситуации» т. е. «обработка текущего элемента» для нас не так важны — это будет просто тело цикла FOR. Сосредоточимся на элементах и переходах. Элемент — это, конечно же, сами целые числа из отрезка А..В, последовательно сменяющие друг друга в переменной х. Переходы — это переход от текущего числа к следующему - у нас,видимо, это должно обеспечиваться инкрементом.
Итак «взять первую ситуацию» означает присвоить переменной первый элемент. Ладно, пусть будет x:=A; И что дальше? WHILE «удалось взять очередной (т. е. первый) элемент»? Но ведь первый всегда можно взять, потому, что А в границах типа, а значит присваивание всегда возможно. Хотя, если А>B, то отрезок А..В пустой и никакого первого элемента нет... :?
Ах, вот в чём дело! "Переход" в данной схеме — это всегда "попытка перехода" (с последующим выяснением ее успешности). Не «взять_первую_ситуацию», а «попытаться взять», не «переход_к_следующей», а «попытка перейти». Среда исполнителя гарантирует безопасное выполнение любого перехода (по крайней мере 1 раз подряд). Это дает нам право на ошибку- право сначала попробовать сделать, а потом узнать надо ли было.А как иначе,возможно, это единственный способ узнать? Сначала шагнем, потом поглядим куда; сначала схватим, потом разберемся наше или чужое. И ничего страшного при этом не произойдет, нигде не взорвется, нужная информация не потеряется, по рукам загребущим никто не даст. Только где-то какой-то флажок зафиксирует (не)успешность, мы потом на него поглядим и решим, что дальше.
Это обработка ( полезное_действие_в_текущей_ситуации) у нас стоит внутри цикла, а значит под охраной WHILE-условия, а переход может выскочить за границы (и даже должны мы когда-то выскочить, а то цикл бесконечный будет). Поэтому «удалось взять очередной элемент» следует понимать как «удалось взять очередной элемент для обработки ». Переходом мы предлагаем на обработку некого кандидата, а уж потом смотрим (условием в WHILE) подойдет он нам или нет. И поскольку подходящие элементы должны идти подряд, то первый же «забракованный», означает и прекращение всего прохода. Вот такое тонкое различие между тем, что положено в переменную и тем, что положено с этим «покладенным» делать.
Поэтому присваивание x:=A; технически возможно всегда (переход возможен всегда), но это именно попытка отдать А на обработку. Дальше нужно придумать условие «переход был успешным»(«не выскочили за границы», «кандидат подходит»). Мы можем выскочить лишь за правую границу, поэтому «в границах» эквивалентно x<=B. «Полезное действие», как уже сказано, просто тело цикла FOR. А вот с переходом к следующему интересней. INC(x) обеспечит, вроде бы, такой переход (выдаст «очередного кандидата»), но...Переход должен выполняться всегда, инкремент выполним не всегда. Если х станет равно максимальному значению в данном типе, то инкремент не определен. И переполнение ли тут произойдет, или ТРАП роли не играет, все равно неприятности. Даже молчаливое ничегонеделание в качестве эффекта INC(MAX(T)) плохо именно своей молчаливостью. Потому что: 1)все равно вне рамок ЯП, т. е. зависит от реализации; 2)переход должен быть не только безопасным, но и «отзывчивым» - должен сообщать об успешности своего выполнения, а поскольку флажок переполнение в самом Обероне недоступен, такой проверки нет.
Конечно, если заранее известно, что B<MAX(T), то проблем с инкрементом нет:переходы безопасны , проверка успешности есть. Применяем схему полного прохода и получим ... тот самый стандартный С0.
Получается, что схема полного прохода не всегда применима, потому что не всегда выполняются условия о свойствах переходов (взятии очередного элемента). Если это не учесть, то получим такой же дефект, как в цикле FOR.
Цитата:
«Правильно организованный интерфейс потокового чтения предоставляет функцию «считать очередной элемент» и признак, который показывает, было ли считывание успешным."
Вот только INC(x) у нас не совсем правильный, и дает сбой на границе типа.
Т.е. перед применением схемы полного прохода нужно не только найти в ней элементы и переходы, но и проверить свойства этих переходов при всех значениях параметров, определяемых предусловием. Если эти свойства выполняются не всегда, то либо усилить предусловие (по крайней мере, оговорить в комментариях, а лучше написать что-то вроде АSSERT (B<MAX(T)) ), либо сконструировать из имеющихся средств переходы именно безопасные и ...(вот не могу термин подобрать, как назвать наличие обратной связи, при помощи которой можно проверить был ли успешен этот переход?). Конструированием такого инкремента займемся в следующем сообщении (должно получиться что-то похожее на С1\С2).

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
 Заголовок сообщения: Re: Мы наш, мы новый FOR построим
СообщениеДобавлено: 13 мар 2013, 19:30 
Не в сети
Администратор
Аватара пользователя

Сообщения: 269
Откуда: Россия
Мы выяснили, что схема "полный проход"требует безопасных переходов на очередной элемент с возможностью дальнейшей проверки успешности такого перехода. Если наш переход не обладает такими качествами, то можно сконструировать требуемое из имеющихся средств. В общем случае безопасность можно обеспечить условным оператором
Код: "OBERON"
  1. IF в данный момент действие можно безопасно выполнить THEN
  2. выполнить это действие
  3. END
А более конкретно
Код: "OBERON"
  1. IF x < MAX(T) THEN INC(X) END
Да, такой «подправленный» инкремент не приведет к переполнению, но он всё еще имеет недостатки. Мы должны не просто безопасно выполнить переход к очередному элементу, но и проверить успешность такого действия.
Введем флажок (булеву переменную) overhead (переполнение), где будем фиксировать попытку перейти за границу целочисленного типа.
Код: "OBERON"
  1. IF x < MAX(T) THEN
  2. INC(X); (* безопасно сделали переход к очередному элементу*)
  3. overhead:=FALSE; (* переполнение при этом не возникло *)
  4. ELSE
  5. overhead:=TRUE; (* переполнение! Неудача при попытки перейти к очередному элементу*)
  6. END
Действие «взять первый элемент» (в нашем случае присваивание x:=A;) технически возможно всегда (переход возможен всегда), что отразим в нашем флажке overhead:=FALSE;
Условие «удалось взять очередной элемент» (не выскочили за границы обрабатываемой подобласти) запишется так: ~overhead & (x<=B). Потому что за границы подобласти мы можем выйти либо при попытке выскочить за пределы всего целочисленного типа (тогда в «логическом» смысле заведомо превысим В, хотя «технически» значение х не изменилось), либо, оставаясь в пределах типа, получим х=B+1 – элемент не подлежащий обработке.
Итак получаем С3
Код: "OBERON"
  1. (* С3. с безопасным инкрементом *)
  2. x:=A; (* берем первый элемент*)
  3. overhead:=FALSE; (* переполнения при этом не возникает *)
  4. WHILE ~overhead & (x <= B) DO (* WHILE находимся в границах *)
  5. ...
  6. IF x < MAX(T) THEN
  7. INC(x); (* безопасно сделали переход к очередному элементу *)
  8. overhead:=FALSE; (* переполнение при этом не возникло *)
  9. ELSE
  10. overhead:=TRUE (* переполнение! Неудача при попытки перейти к очередному элементу*)
  11. END
  12. END

Сравним с С2. Почти то же самое... Но насколько это разные фрагменты идеологически! В С2 неструктурный выход из цикла, а С3 — реализация схемы «полный проход» с действительно безопасным взятием следующего элемента. Есть правда еще «лишнее» присваивание overhead:=FALSE после инкремента. При реализации цикла на Си или Ассемблере, конечно, нужно выкидывать всё лишнее (тем более из циклов) из соображений эффективности, но сейчас это присваивание следует оставить. Опять таки из «идеологических» соображений: присваивание переменной overhead – это часть действия «взять очередной элемент», механизм обратной связи безопасного перехода (механизм, сообщающий об успешности\неуспешности); изменили (попытались изменить) х — зафиксируем успешность этого, чтобы затем проверить.

Замечание про условие ~overhead & (x <= B).
Может быть имеет смысл записать вместо этого (x <= B) & ~overhead ? Ведь переполнение возникает только на самой последней итерации, так зачем же все время проверять overhead? Опять же, если и следует переставить конъюнкты, то это следует сделать только при реализации цикла. На уровне Оберона именно условие ~& (x <= B) является идеологически (вот слово понравилось! :) ) верным. Потому что при overhead=TRUE (произошло переполнение) значение x уже не имеет значения, все равно оно не такое, как должно бы быть (так за 255 должно бы следовать 256, а не 0 или 255, но в байтовую переменную нельзя поместить 256). Так что, при переполнении уже не имеет смысла x с чем-то сравнивать. И "cокращенная" конъюнкция Оберона действительно на (x <= B) уже не смотрит.

UPD 15.03.13. Уточнение про "успешность перехода". В вышенаписаном есть некоторая путаница с термином "успешность". Присвоение переменной overhead говорит об успешности или неуспешности инкремента, сообщает выскочили ли мы за границу всего целого типа. Но это лишь часть условия "удалось взять очередной элемент для обработки" (удалось успешно сделать переход), потому что х может быть в пределах типа, но за границей В (тогда успешен инкремент, но переход на очередной элемент успеха не имел).
Коварна всё же задача о проходе подобласти, как-то не получается одновременно думать и о "высокоабстрактном" переходе к следующему элементу и о "низкотехнической" аварии из-за исчерпания целых чисел. Так что переписать FOR через WHILE не так просто, часто про случай "подобласть на краю всей области значений" забывают. Поэтому в ЯП обязательно должен быть FOR, но FOR правильный, где этот случай учтен.

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
 Заголовок сообщения: Re: Мы наш, мы новый FOR построим
СообщениеДобавлено: 20 мар 2013, 19:28 
Не в сети
Администратор
Аватара пользователя

Сообщения: 269
Откуда: Россия
Путаница с термином «успешность», допущенная в предыдущем сообщении, позволит плавно перейти к построению аналога С1 :) . Введем булеву переменную outOfRange – флажок, фиксирующий выход за границы подобласти, т. е. эту самую «(не)успешность взятия очередного элемента для обработки».
x:=A; - это попытка взять очередной элемент. При этом мы уже можем выйти из обрабатываемой подобласти (хотя в области Т заведомо находимся).
Условие выхода за рамки эквивалентно x>B, поэтому outOfRange:= x>B. Далее, думаю, можно подробно не пояснять, а сразу написать
Код: "OBERON"
  1. (* С4. Не выходим из подобласти*)
  2. x:=A; (* берем (вернее пытаемся взять) первый элемент*)
  3. outOfRange:=x>B; (* может и сразу вышли за рамки *)
  4. WHILE ~outOfRange DO (* WHILE не вышли за границы *)
  5. ...
  6. IF x < B THEN
  7. INC(x); (* безопасно сделали переход к очередному элементу *)
  8. outOfRange:=FALSE; (* всё еще в границах *)
  9. ELSE
  10. outOfRange:=TRUE;(*А вот теперь за границы вышли!*)
  11. END
  12. END
Сравните с С1. Функционально фрагменты эквивалентны, но С4 явно «структурнее».
Может быть нагляднее будет фрагмент с переменной inRange? Попробуем
Код: "OBERON"
  1. (* С4-1. Обработаем только подобласть*)
  2. x:=A; (* берем (вернее пытаемся взять) первый элемент*)
  3. inRange:=x<=B; (* всё еще в границах? *)
  4. WHILE inRange DO (* WHILE в границах *)
  5. ...
  6. IF x < B THEN
  7. INC(x); (* безопасно сделали переход к очередному элементу *)
  8. inRange:=TRUE; (* всё еще в границах, в крайнем случае НА границе *)
  9. ELSE
  10. inRange:=FALSE;(*А вот теперь за границы вышли!*)
  11. END
  12. END
Пожалуй С4-1 даже нагляднее.

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
 Заголовок сообщения: Re: Мы наш, мы новый FOR построим
СообщениеДобавлено: 20 мар 2013, 19:39 
Не в сети
Администратор
Аватара пользователя

Сообщения: 269
Откуда: Россия
Мы рассматривали цикл FOR c шагом 1. Цикл с шагом BY -1 принципиально не отличается. Достаточно заменить инкремент на декремент и знак «меньше\меньше или равно» в условиях на «больше\больше или равно» (и наоборот). Ах да, ещё вместо MAX(T) написать MIN(T). Понимающему достаточно, приводить конкретный код не буду. :)
С произвольным шагом BY C могут возникнуть несколько большие трудности. Конечно вместо INC(x) никто не мешает написать INC(x,С) или x:=x+C, но как быть с безопасностью? Нельзя написать IF x + С < MAX(T) , потому что сумма x + С уже может дать переполнение. Следует писать IF x < MAX(T) - С . Здесь переполнения возникнуть не должно, ведь если 0<С<=MAX(T), то MAX(T) - С находится в пределах 0..MAX(T) . Вернее 0..MAX(T)-1, потому что нулевой шаг не допускается (кстати, вспомним, что в Обероне шаг цикла FOR должен быть константным выражением).
Аналогично, проверка x > MIN(T) - С должна обеспечить безопасный переход при отрицательном шаге.
Но как переделать фрагменты С1, С4 (С4-1)? Как x+C , так и B-C могут вызвать переполнение при некоторых А,В,С. Получается достаточно сложное условие:
Код: "OBERON"
  1. IF (x<MAX(T)-C) & (x+C <B) (* для С>0 *)
  2. IF (x<MIN(T)-C) & (x+C >B) (* для С<0 *)

Да, нелегко следить за переполнением. Позавидуешь математикам, которые работают с «настоящими» целыми числами и ,слава Пеано!,на границы не натыкаются :).

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
 Заголовок сообщения: Re: Мы наш, мы новый FOR построим
СообщениеДобавлено: 03 апр 2013, 20:29 
Не в сети
Аватара пользователя

Сообщения: 967
Откуда: Днепропетровская обл.
Не будем также забывать об эффективности реализации цикла FOR n := A TO B BY Step, что имеет большое значение. Надо обобщить все мысли и вывести максимально эффективное решение. Причём их будет два:

1. Структурный вариант с игнорированием машинного заёма|переполнения и ручным отловом выхода счётчика цикла за пределы значений типа (привожу только цикл с шагом Step > 0):
Код: "OBERON"
  1. n := A;
  2. IF n <= B THEN
  3. DEC(n, Step); (* Здесь возможен заём при n = 0. *)
  4. REPEAT
  5. INC(n, Step); (* Если был заём, то этот инкремент его компенсирует *)
  6. (* (с переполнением, которое обязательно нужно игнорировать). *)
  7.  
  8. (* Тело цикла. *)
  9.  
  10. ASSERT(n < n+Step); (* Ловим возможное переполнение если n + Step > MAX(T). *)
  11. UNTIL n >= B;
  12. END;
Здесь эффективность на высоте, и как сделать лучше — пока не знаю. Но этот вариант подразумевает, что при переполнении MAX(T) + 1 = MIN(T), а заёме MIN(T) - 1 = MAX(T), впрочем, процессоры семейства 80x86 это обеспечивают (И другой вариант поведения процессоров мне неизвестен, хотя наверное можно сконструировать процессор, поведение которого в этих случаях будет отличаться).

Такая реализация цикла FOR получше стандартной оберонской тем, что конечное значение счётчика цикла может быть равно MAX(T), однако цикл будет уязвим против возможного переполнения при произвольном шаге (FOR shortint := 10000 TO 32767 BY 10000), если оно не будет обрабатываться (если убрать ASSERT). При генерации машинного кода обработать переполнение обычно легко, гораздо труднее это сделать при трансляции в Си (необходим дополнительный код для проверки и соответствующей реакции в случае переполнения).

2. Неструктурный вариант без игнорирования машинного заёма|переполнения и ручным/автоматическим отловом выхода счётчика цикла за пределы значений типа (с шагом Step > 0). Здесь применяю нотацию Си т.к. нужен безусловный переход вовнутрь тела цикла (для минимизации количества операций и повышения эффективности):
Код: "C"
n = A;
if(n <= B) goto jump_into_loop; else goto jump_loop_end;
do {
/* Здесь контролируем возможное переполнение: */
assert(n < (n+Step)); /* Эта проверка, в принципе, тоже полагается на MAX(T) + 1 = MIN(T). */
/* Ничего не имею против другого кода проверки на переполнение, более правильного. */
n += Step;
jump_into_loop:
 
/* Тело цикла. */
 
} while(n < B);
jump_loop_end:
Какой из этих вариантов предпочтительнее? Структурный вариант подходит если в языке, на который мы транслируем, не предусмотрен отлов переполнения при сложении/вычитании. А неструктурный прыжок вовнутрь цикла хорош только если время работы прыжка (goto jump_into_loop) будет меньше, чем время операции уменьшения переменной на шаг цикла (n -= Step), что весьма спорно для современных процессоров. А проверка на переполнение эффективнее всего на уровне машинного кода, где можно после операции проверить значение флага переноса|заёма (Carry flag). А работая с высокоуровневым кодом придётся вводить дополнительные операции, снижающие эффективность (assert). Вобщем, здесь ещё есть над чем подумать, но мы нашли решение для B=MAX(T), а с понижением эффективности на проверочные конструкции для обработки переполнения всё равно придётся мириться, т.к. это необходимо для надёжности кода. Ей не уделялось должного внимания раньше (в Turbo Pascal и Turbo C), но Обероны не должны здесь подкачать. Так что, полагаю, приведённые здесь варианты реализации цикла FOR вполне оптимальны. Дело за малым — за реализацией. :)

P.S. Кстати, а ведь проверку на выход счётчика цикла за пределы значений типа (и соответствующую коррекцию значения B) можно делать только один раз — ещё до вхождения в цикл.


Вернуться к началу
 Профиль  
Ответить с цитатой  
 Заголовок сообщения: Re: Мы наш, мы новый FOR построим
СообщениеДобавлено: 04 апр 2013, 21:31 
Не в сети
Администратор
Аватара пользователя

Сообщения: 269
Откуда: Россия
Zorko писал(а):
Не будем также забывать об эффективности реализации цикла FOR n := A TO B BY Step, что имеет большое значение. Надо обобщить все мысли и вывести максимально эффективное решение.
В предыдущих сообщениях я старался рассмотреть не "низкопрагматическую" реализацию, а "высокосемантическое" определение этой конструкции цикла. Семантика определялась через кусок кода на Обероне, но это не значит, что переводить в машинный код нужно именно эту последовательность операторов. Машинный код должен давать тот же результат, но построен может (и должен!) быть с применением различных оптимизаций. То, что при этом уходим от структурности - не страшно, на то и машинный код.
Так контролировать переполнение следует конечно же не при помощи булевой переменной overhead, а одноименным флажком процессора. Переполнение может возникнуть только при инкременте. Получим что-то подобное
Код: "OBERON"
  1. (* С5. низкоуровневый контроль *)
  2. x:=A;
  3. WHILE x <= B DO
  4. (*тело цикла*)
  5. INC(x);
  6. IF инкремент дал переполнение THEN выйти из цикла END
  7. END
В машинном коде конец цикла WHILE реализуют обычно через GOTO на заголовок цикла или через условный переход в начало тела цикла. Этот GOTO или условный переход скорее всего можно эффективно объединить с проверкой переполнения инкремента. Но это в машинном коде, а выразить контроль за флажком процессора через Си затруднительно. Разве что какую-то платформозависимую макроподстановку придумать.
Еще идея: объединить INC(x) и выход при переполнении в некий BreakINC(x). Это специальный инкремент, который действует как обычный, но если происходит переполнение, то дополнительно прерывает цикл WHILE, в котором находится. Кстати, тогда мы можем сказать, что у нас самый обычный стандартный обероновский цикл FOR C0. У нас инкремент необычный - вызывает выход из цикла при переполнении. А поскольку переполнение и эффекты при этом возникающие стандартом не определены, значит и такой выход стандарту не противоречит!
Обвинение: Но, Ваша Честь, противоречие заключается в нарушении эквивалентности. По стандарту выполнение цикла FOR должно быть эквивалентно выполнению фрагмента C0. Однако этот инкремент явную конструкцию WHILE зацикливает, а скрытый внутри цикла FOR - прерывает!
Защита:Требование эквивалентности - это тоже требование стандарта, эффекты возникающие при переполнении стандартом не описаны. Поэтому нарушение эквивалентности, возникающее в случае переполнения, стандарту также не противоречит. Это несколько необычный инкремент, но вполне допустимый (да и прерывание цикла на практике намного полезней зацикливания).
Обвинение: То, что переполнение не контролируется стандартом, еще не значит, что можно безнаказанно совершать всё что угодно! Да еще и утверждать при этом, что это "всё" - стандартное! А если кто-то реализует инкремент, форматирующий при переполнении весь жесткий диск? Это тоже будет стандарт Оберона?!
Судья:(стуча молотком) К порядку!

Действительно, давайте вернемся к делу. Итак, общая идея - упрятать машиннозависимое в особую процедуру, чтобы легко написать реализацию на Си, а внутренний машинный код из этой процедуры подставлялся бы только на окончательном этапе. Чтобы это сделать, может быть попробовать рассуждать в обратном порядке - от машинного кода к Си?
Вот у процессора Z80 есть флажки и CY и V , это значит можно контролировать переполнение и безнакового и знакового типов. Но инкремент байтового регистра влияют только на флаг V, но не на CY. А инкремент регистровой пары флажки вообще никак не задевает. Поэтому может быть более эффективно использовать в этом случае не инкремент, а сложение ADD. "Короткий" условный переход JR есть только для флажка СY, но не для V. Для знаковых типов придется использовать JP, что на целый байт длиннее :). Конечно, JP придется использовать и в случае "большого" тела цикла, когда не хватит дальнобойности относительного перехода, но относительного перехода заведомо хватит чтобы выскочить из цикла (перескочить GOTO на начало цикла). У процессора 8086 особенности этих флажков и наборов команд немного другие. Если вот так рассмотреть разные варианты для разных процессоров, потом выделить что-то общее, объединить куски машинных инструкций в более высокоуровневые команды, то может быть получится некая общая схема, шаблон для реализации FOR.

Цитата:
Но этот вариант подразумевает, что при переполнении MAX(T) + 1 = MIN(T), а заёме MIN(T) - 1 = MAX(T), впрочем, процессоры семейства 80x86 это обеспечивают (И другой вариант поведения процессоров мне неизвестен, хотя наверное можно сконструировать процессор, поведение которого в этих случаях будет отличаться).
Думаю, можно безусловно принять, что после самого большого числа опять идет самое маленькое (как в электросчетчике :)). Когда встретится экзотика, где это не так, и мы захотим эту экзотику включить в систему XDEV, вот тогда и подумаем о каком-то ином варианте. Пока считаем, что если n и Step принадлежат целому типу Т и Step>0, то n>n+Step тогда и только тогда, когда n+Step вызвало переполнение (в самом крайнем случае прибавление положительного числа вызовет переполнение не изменяющее счетчик цикла, но никогда не даст меньше).

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
 Заголовок сообщения: Re: Мы наш, мы новый FOR построим
СообщениеДобавлено: 05 апр 2013, 19:06 
Не в сети
Администратор
Аватара пользователя

Сообщения: 269
Откуда: Россия
В начале этой темы, я искал семантику верного FOR через указание эквивалентного фрагмента кода на Обероне. Но я не считаю, что FOR должен быть таким: "оператор FOR делает то же самое, что и вот этот фрагмент". Обязательно в семантике необходимо оговорить еще 2 условия:
Цитата:
1) После завершения FOR значение переменной цикла не определено. Оно может быть равно B, может быть B+Step, может равняться нулю, а может вообще какому-то значению вне диапазона А..В. Необходимо составлять программы не рассчитывая на какое-то конкретное значение x по окончании цикла.
2)Эффект от изменение переменной цикла во время выполнения цикла не определен. Т.е. переменная цикла меняется автоматически самим циклом, менять ее каким-то иным образом не следует. Если все-таки такое сделать, то цикл может либо зациклиться, либо прерваться, может выполнится иное число раз, чем мы ожидаем, либо вообще такое изменение может быть проигнорировано.
Эти не значит, что компилятор должен проверять выполнение обоих условий. Наоборот, это означает, что компилятор не обязан гарантировать, что x=B+1 по окончании цикла, или что присвоение x=x+1 пропустит следующую итерацию. Программист вполне может передать x в процедуру как параметр-переменную, никто это не запрещает, но пусть будет готов к чему угодно, если эта процедура изменит-таки значение x!

Такое ослабление постусловия ограничивает возможности неправильного применения конструкции FOR. Действительно, FOR нужен ,чтобы обработать элементы в заранее известных границах (перебрать подмножество целых чисел), обработать все элементы в восходящем или нисходящем порядке, от первого до последнего. Цикл завершен, все элементы а заданных границах обработаны, границы известны. Зачем тогда знать, что в переменной по окончании цикла? Знать это интересно, только если мы из цикла досрочно вышли, или сами этой переменной что-то присвоили. Но FOR не для этого, используйте тогда WHILE, REPEAT или LOOP. И зачем вручную что-то присваивать? Чтобы цикл прервать или следующую итерацию пропустить, или на предпредыдущую вернуться? Опять-таки это не FOR.
FOR - эквивалент математического утверждения «для всех х из отрезка N,M». И этот отрезок будет обработан c N по M; если N>M, то никакой обработки не будет; если отрезок N,M на краю целого типа, то тоже проблем быть не должно. Вот это FOR гарантирует, но обработка происходит автоматически. Единственно, как программист может (должен!) взаимодействовать с этим внутренним механизмом — во время выполнения цикла узнать какая сейчас происходит итерация через значение переменной х. Эта переменная — единственное окошечко к внутренностям FOR, причем окошечко «только смотреть, руками не трогать».

Вот так должна выглядеть семантика «нового» FOR'a. Свобода в выборе механизма реализации открывает широкие возможности для эффективности, мы можем выбирать любой фрагмент кода — через WHILE или REPEAT UNTIL, со входом в середину цикла и досрочным выходом, с использованием флагов процессора или с загрузкой из стека внутреннего счетчика повторений. Можно проверять окончание цикла до или после инкремента, ведь мы не обязаны гарантировать ни x=B, ни x=B+1 по окончании цикла. Можно заменить UNTIL n>=B на UNTIL n=B (при шаге 1), ведь мы не обязаны завершать цикл из-за «ручного» присвоения n=B+1 . А это позволит широко использовать флаги процессора: не только CY и V, но и Z и S (при B=0, например), а может даже P (при количестве итераций 2 и особом шаге).

Присоединяясь к участникам обсуждения Долой FOR(?), хочу сказать «Долой СТАРЫЙ FOR, наивно определенный стандартом через WHILE!», «Такой FOR нам не нужен!». Ведь если понадобится неправильно его реализовать, то всякий сможет легко записать эквивалентную дефектную конструкцию, с оговорками пригодную для массивов,но неверную как универсальное средство обработки отрезка целых чисел.

В то же время, решительно возражая участникам вышеприведенного обсуждения, говорю «Да здравствует НОВЫЙ, правильный FOR, не спотыкающийся о границу целочисленного типа, не провоцирующий автора программы на трюки!». Такой FOR нужен, нужен как самостоятельная конструкция ЯП, потому что реализовать его через WHILE без дефектов, как мы видим, не так-то просто. А раз эта очень употребительная конструкция трудно выражается через другие, значит она должна быть сама по себе.

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


Вернуться к началу
 Профиль  
Ответить с цитатой  
 Заголовок сообщения: Re: Мы наш, мы новый FOR построим
СообщениеДобавлено: 05 апр 2013, 19:26 
Не в сети
Администратор
Аватара пользователя

Сообщения: 269
Откуда: Россия
Во фрагментах
Zorko писал(а):
1. Структурный вариант с игнорированием машинного заёма|переполнения и ручным отловом выхода счётчика цикла за пределы значений типа
2. Неструктурный вариант без игнорирования машинного заёма|переполнения и ручным/автоматическим отловом выхода счётчика цикла за пределы
вместо оператора ASSERT(n < n+Step); аварийно завершающем всю программу, должно быть, вообще-то, безаварийное завершение:
Код: "OBERON"
  1. IF ~(n < n+Step) (* т.е. произошло переполнение*) THEN выходим из цикла END
Ведь выход за пределы диапазона всего целого типа - это не ошибка, это сигнал, что элементы кончились и цикл нужно прекратить. Так FOR shortint := 10000 TO 32767 BY 10000 должен обработать последний элемент shortint = 30000 и нормально завершиться, без ТРАПа.

_________________
А кроме того, я думаю, что корFORген должен быть разрушен!


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

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


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

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


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

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
Тех.поддержка phpBB