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

Твердыня модульных языков
Текущее время: 29 мар 2024, 01:59

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




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

Сообщения: 1019
Откуда: Днепропетровская обл.
Да, согласен. Там должно быть IF n > n+Step THEN EXIT END;

Кроме того, если все значения цикла — константы, то ещё до вхождения в цикл можно исправить B с тем, чтобы не было переполнения (и, соответственно, не вставлять код проверки). (это не сработает для WHILE n <= B если в последней итерации цикла n = MAX(T)).

Ещё можно оптимизировать цикл если вычислять количество его повторений тоже заранее, и просто уменьшать значение внутреннего счётчика (как это делает Дельфи), ведь сравнение числа с константой (особенно если она = 0) — более быстрая операция, чем сравнение двух чисел. Мне кажется, для небрежного кодинга (если программист изменит переменную цикла ручками) вариант с внутренним счётчиком гораздо более ненадёжен, т.к. не прощает халатного построения циклов. Всё же стандарт Оберона (с WHILE n <= B) более лоялен к построителям корявых циклов, чем всякие оптимальные внутренние счётчики. Так что — надо быть или строгим, или очень строгим. :)


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

Сообщения: 273
Откуда: Россия
Zorko писал(а):
Кроме того, если все значения цикла — константы, то ещё до вхождения в цикл можно исправить B с тем, чтобы не было переполнения (и, соответственно, не вставлять код проверки). (это не сработает для WHILE n <= B если в последней итерации цикла n = MAX(T)).
Если A и B - константы (константные выражения), то можно заранее, еще при трансляции, сделать кучу оптимизаций.
Далее считаем, что Step>0 (для отрицательного шага нетрудно провести аналогичные рассуждения).
Если цикл выполнится хотя бы раз (A<=B), то значение параметра на последней итерации Nlast=B-(B-A) MOD Step. Тогда из "структурного" варианта получится такой
Код: "OBERON"
  1.  
  2. n := A; (* можно объединить с декрементом*)
  3. (* проверка IF n <= B уже не нужна, мы при трансляции знаем, что A<=B *)
  4. (* а если A>B, то весь цикл трансляция вообще отбрасывает *)
  5. DEC(n, Step); (* А можно сразу присвоить n := A-Step = константа вычисляемая при трансляции*)
  6. REPEAT
  7. INC(n, Step); (* Если был заём, то этот инкремент его компенсирует *)
  8. (* (с переполнением, которое обязательно нужно игнорировать). *)
  9.  
  10. (* Тело цикла. *)
  11.  
  12. (* Ловить возможное переполнение уже не нужно *)
  13. UNTIL n = Nlast;
Неструктурный аналогично, они вообще отличаются только методом «впрыгивания» внутрь цикла — инкремент обходится или с помощью GOTO или путем его «отключения» при помощи обратной операции (декремента).

А что, если A и B – не константы? Если Step=1, то Nlast=B, тут всё очень просто. Но в общем случае динамическое вычисление Nlast дорого обходится, если у процессора нет операции MOD (и если Step – не степень двойки).

И, конечно, программист не должен вмешиваться в автоматическую работу цикла (не присваивать значение переменной вручную), иначе можно перескочить через Nlast, а цикл не остановится, хотя и выйдет за B.

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


Последний раз редактировалось Saferoll 08 апр 2013, 20:45, всего редактировалось 1 раз.

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

Сообщения: 273
Откуда: Россия
Цитата:
Ещё можно оптимизировать цикл если вычислять количество его повторений тоже заранее, и просто уменьшать значение внутреннего счётчика

Можно вычислить количество итераций: NumIters=(B-A) DIV Step + 1, при Step>0, A<=B. Если это количество = 0 (A>B), то весь цикл вообще транслируется в ничто, при NumIters=1 от цикла остается только его тело (c присвоением n:=A перед ним).
Даже при NumIters=2 можно придумать что-то особое, ведь тело цикла должно выполняться 2 раза - при x=A и x#A. А это условие всегда можно свести к проверке значения 1 байта (даже 1 бита из этого байта), даже если тип x многобайтовый.
А цикл, действительно, можно построить на внутреннем счетчике. Есть даже специальные конструкции для этого (у Z80 есть DJNZ, хотя она может не дотянуться до начала тела цикла).
Но опять-таки, хорошо когда А,В-константы и всё вычисляет компилятор. А динамически? Это очень просто при единичном шаге, не так сложно для Step=2. Ну и, вообще, для степени двойки можно выполнить несколько сдвигов. Но в общем случае DIV — тяжелая операция для Спектрума и прочих «малышей».

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


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

Сообщения: 273
Откуда: Россия
Пусть А вычисляется динамически, а В-константа. Даже в этом случае можно кое-что заранее (при трансляции) рассчитать.

Если В=МАХ(Т), то очевидно, всегда А<=B, поэтому нет необходимости в проверке выполнения цикла хотя бы 1 раз (условие IF n <= B не нужно).

Если В=МIN(Т), то весь цикл запишется как n := A;IF n=МIN(Т) THEN тело цикла END и не нужно больше никаких итераций с инкрементами.

Если B-Step<MIN(T), то цикл выполнится 0 или 1 раз в зависимости от значения А. Транслируем его во фрагмент n := A; IF n<=B THEN тело цикла END.

Если же B-Step>=MIN(T), то цикл можно записать так
Код: "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. UNTIL n > ( B - Step) (* (B-Step) = константа, вычисляемая при трансляции *);
  11. END;
Здесь уже не может произойти никакое переполнение, инкремент либо нейтрализуется для n=A, либо применяется для n<=B-Step (тогда в самом крайнем случае инкремент даст n=B и выход из цикла).

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


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

Сообщения: 273
Откуда: Россия
Насколько же всё-таки уродлив стандартный обероновский FOR! :twisted: Особенно по сравнению с остальным изяществом, присущим Оберон-технологиям. Или это не сам язык виноват, а только реализация BlackBox?
Я про принцип «В цикле FOR n:= A TO B BY Step выражения A,B и Step должны иметь тот же тип ,что и переменная n » (хотя вроде бы явно это нигде не описано, но в BlackBox именно так).

Я согласен насчет А и B - это значения, которые может принимать n, поэтому требование однотипности вполне естественно. А вот шаг - другое дело, по самому своему смыслу шаг это не значение, это разница значений - смещение от одного элемента к другому. Почему разница (протяженность) насильно совмещена с самим элементом (точечной отметкой)? Потому что это числа? Но эти числа представляют сущности разной природы!
Так в кинотеатре в данном ряду есть кресло №3, которое имеет сиденье, спинку, ножки и подлокотники, на кресле можно сидеть и смотреть фильм. И есть в данном ряду разница (смещение) между креслами. Вот у разницы ни ножек, ни спинок, ни сидений нет (подлокотников, конечно, тоже) и сидеть на этой разнице нельзя, пусть даже для 10-го и 13-го кресел она тоже равна 3.

Хуже того, константное выражение после BY определяет не только (абсолютную) величину смещения на каждой итерации, но и направление в котором идет цикл. Получается, что, строго следуя этому правилу, мы не сможем организовать перебор беззнаковых чисел в нисходящем порядке, потому, что не сможем написать FOR n:=255 TO 0 BY -1, ведь (-1) вне диапазона 0..255!

В Паскале таких проблем не было, потому что у цикла FOR было только 2 возможных шага - «+1» и «-1». Или вернее так — был только единичный шаг, но он мог или прибавляться (с контролем правой границы) или вычитаться (с контролем левой). И никого не смущало (даже никто и не задумывался), что в байте нет отрицательных чисел, а шаг (-1) есть. Ведь и для беззнаковых чисел есть декремент и операция вычитания. В диапазоне 0..255 нет отрицательных чисел, но вычесть из одного байта другой мы можем (и даже остаться в том же диапазоне, если вычитаем из большего меньшее).
А вот,оказывается, нельзя вычитать, в Обероне только прибавлять можно (n:=n + Step). И если у нас в диапазоне значений есть отрицательные — хорошо, можно это отрицательное прибавить и тем самым «вычесть». А если диапазон с нуля-извините...
«— Извинить не могу!» (М.Булгаков Мастер и Маргарита). Даже для знаковых типов это слишком ...Ну ладно, опять скажу «уродливо», вместо слов за которые я, как честный модератор, должен был бы сам себя отлучить. :) Почему в положительном направлении мы можем двигаться с шагом от 1 до 127, а в отрицательном от 1 до 128? Набор смещений по элементам должен определяться количеством этих элементов, а не их значением.

Я не призываю вводить в цикл FOR Оберона специальные слова для обозначения направления (хотя, по-моему, это было бы гораздо красивее и нагляднее), но диапазон возможных шагов после BY должен быть иным!

Итак, пусть в цикле FOR n:= A TO B BY Step компилятор вычислит константное выражение Step, используя свой самый большой диапазон целых чисел. Знак Step определяет направление цикла: «+» - возрастание , «-» - убывание, нулевой шаг недопустим. А вот абсолютную величину шага нужно сравнить с мощностью (количеством значений) типа переменной n. Если ABS(Step) >MAX(T)-MIN(T), то мы заведомо не можем шагнуть без вылета из цикла (цикл вообще не выполнится ни разу или выполнится 1 раз для n=A). А тогда зачем вообще этот цикл? Думаю, тут компилятор должен сразу схватить программиста за руку и сообщить, что с шагом или с типом переменной что-то не так. А вот если шаг (по абсолютной величине) принадлежит диапазону 1..MAX(T)-MIN(T), то цикл FOR транслируется как обычно, с соблюдением всех вышеизложенных оптимизаций.

Кстати, надо пересмотреть вышеизложенное, с учетом условия 1<=ABS(Step) <=MAX(T)-MIN(T). Не перескочит ли какой-нибудь шаг из этого диапазона «забор» Nlast или «контрольно-следовую полосу» (B-Step), что мы возвели для предотвращения переполнений? Учесть нужно как знаковые так и безнаковые типы.

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


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

Сообщения: 1019
Откуда: Днепропетровская обл.
FOR byte:=255 TO 0 BY -1 в BlackBox'е невозможно, главным образом, потому, что тип BYTE — знаковый. А значит 255 уже невозможно присвоить байту (как и 0FFH). Но 0FFX — можно присвоить, что иногда бывает полезно (тип BYTE совместим по присваиванию с SHORTCHAR).


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

Сообщения: 273
Откуда: Россия
Zorko писал(а):
FOR byte:=255 TO 0 BY -1 в BlackBox'е невозможно, главным образом, потому, что тип BYTE — знаковый. А значит 255 уже невозможно присвоить байту (как и 0FFH). Но 0FFX — можно присвоить, что иногда бывает полезно (тип BYTE совместим по присваиванию с SHORTCHAR).
Я имел в виду FOR byte:=255 TO 0 BY -1 невозможно будет записать, когда мы создадим "настоящий" беззнаковый байт 0..255, но сохраним принцип "шаг цикла должен быть такого же типа, что и переменная цикла".
Сейчас - да, сейчас байт -128..127, поэтому (-1) в диапазон входит, 255 - нет. Кстати ТО 0 ВY -1 даст зацикливание. Чтобы на это не отвлекаться возьму TO 1.
Сейчас можно написать FOR byte := P.Unsigned(255) TO 1 BY -1 DO и получим перебор значений с шагом (-1). Но (-1) допустима потому, что байт у нас всё равно знаковый. А вот FOR byte := P.Unsigned(255) TO 1 BY -129 DO вызовет протест компилятора.
Я предлагаю отбросить принцип "шаг может принимать лишь те значения, что и переменная цикла", а использовать для шага диапазон 1..MAX(T)-MIN(T) и для знаковых и для беззнаковых типов, как я писал выше (знаком шага задаётся направление).

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


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

Сообщения: 1019
Откуда: Днепропетровская обл.
Saferoll писал(а):
Я имел в виду FOR byte:=255 TO 0 BY -1 невозможно будет записать, когда мы создадим "настоящий" беззнаковый байт 0..255, но сохраним принцип "шаг цикла должен быть такого же типа, что и переменная цикла".
Ну дык. Этот принцип как раз хорош, если в языке совсем нет беззнаковых типов.


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

Сообщения: 273
Откуда: Россия
Zorko писал(а):
Ну дык. Этот принцип как раз хорош, если в языке совсем нет беззнаковых типов.
Плох этот принцип! Даже сам по себе, безотносительно к знаковости типов плох. И для знаковых плох, просто у беззнаковых это ярче проявляется. Цикл должен перебирать элементы или в порядке возрастания или в порядке убывания. Эти направления равноправны, для целого типа есть и инкремент и декремент, есть и сложение и вычитание. При возрастании надо шаг прибавлять и проверять правую границу, при убывании - вычитать и проверять левую. И лучше бы это было выражено специальными служебными словами, а не знаком после BY. Было бы гораздо нагляднее.

А абсолютная величина этого шага (возможный набор этих величин) определяется количеством элементов, а какие это элементы для шага неважно. "1,2,3" можно перебрать с шагом 1 в прямом или обратном порядке и совершить при этом 3 итерации. "-456,-455,-454" можно точно также перебрать в прямом или обратном порядке и совершить при этом тоже 3 итерации (и тоже с шагом 1). Можно оба этих отрезка перебрать с шагом 2 (тоже в обоих направлениях), совершив 2 итерации. А с шагом 3 уже не получится (сразу выскочим), там 1 итерация только выйдет. А вот теперь скажите, как количество итераций или возможный набор шагов связано с числом "-455"? Ясно, что тут главное, что элементов три (т.е. количество).

"Шаг должен быть равен значению одного из элементов типа" - это так же неестественно, как "Количество одновременно перевозимых пассажиров должно равняться возрасту одного из них". Шаг определятся количеством элементов, а вместимость автобуса количеством сидений.

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


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

Сообщения: 1019
Откуда: Днепропетровская обл.
Но какой практический смысл иметь шаг цикла, значение которого превышает разрядность типа? Нет, позволить описать его наверное всё-таки нужно, но хорошо если компилятор предупредит, что вот здесь:
Код: "OBERON"
  1. FOR byte := 1 TO 255 BY 10000
цикл FOR лучше вообще не использовать (поскольку тело цикла исполняется один раз), ничего плохого в этом не вижу. Поскольку шаг цикла FOR всё равно не получить аргументом извне. Ведь он константа! Так что имеет смысл предупредить программиста, что в цикле есть какой-то недочёт. Это будет полезно. Но предупреждать надо, конечно же, не только когда значение шага вышагнуло за пределы типа счётчика цикла, а вообще хорошо бы давать warning если цикл исполняется только один раз. Это будет по-оберонски.

И по сравнению с Паскалем цикл FOR в Обероне гораздо более функционален, как раз за счёт шага, который может быть отличен от 1 и -1. Это незначительно усложняет компилятор, но, в целом, гораздо удобнее для использования. Ещё круче было бы, если бы шаг можно было бы задавать не константой, но Вирт предпочёл компромисс между эффективностью и универсальностью (метки CASE тоже могли бы быть не константами, но это значительно повысило бы сложность реализации).


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

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


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

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


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

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
© VEDAsoft Oberon Club