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

Твердыня модульных языков
Текущее время: 28 мар 2024, 22:03

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




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

Сообщения: 273
Откуда: Россия
Можно модифицировать частный случай цикла и вывести общий, когда и А и В вычисляются динамически.
Код: "OBERON"
  1. (* цикл для общего случая *)
  2. n := A;
  3. IF n <= B THEN
  4. IF B>=MIN(T)+Step THEN (* MIN(T)+Step - константа *)
  5. limit:=B - Step+1 (* =B – (Step-1), где (Step-1) - константа *)
  6. ELSE (* нельзя шагнуть даже 1 раз*)
  7. limit:=MIN(T) (* цикл должен выполниться только для n=A*)
  8. END;
  9. DEC(n, Step); (* Здесь возможен заём при n = 0. *)
  10. REPEAT
  11. INC(n, Step); (* Если был заём, то этот инкремент его компенсирует *)
  12. (* (с переполнением, которое обязательно нужно игнорировать). *)
  13.  
  14. (* Тело цикла. *)
  15.  
  16. UNTIL n>=limit (* при limit= MIN(T) сразу выходим*);
  17. END;
Это очень хорошая реализация цикла FOR: не использует дорогостоящих операций, проверки на переполнение делает до цикла, в цикле никаких проверок кроме как в UNTIL не производит. При этом не зацикливается при любых А и B!
Но допустим ли шаг в диапазоне 1..MAX(T)-MIN(T)? При Step=1 (или иных небольших величинах) переполнений из-за вычитания\прибавления Step не возникает. В самом крайнем случае, когда Step= MAX(T)-MIN(T) имеем:
Условие B>=MIN(T)+MAX(T)-MIN(T) =MAX(T) выполняется,только если В=MAX(T). Тогда limit=MAX(T)- (MAX(T)-MIN(T))+1=MIN(T)+1. И далее цикл выполнится либо только для n=A>MIN(T), либо для n=A=MIN(T) и n=A=MIN(T) +Step=MAX(T).
Если же B<MAX(T), цикл выполнится только для n=A. Всё верно, именно так и должно быть!

Так что этот цикл (или его «неструктурный» аналог) следует принять за основу реализации в общем случае. В частных случаях нужно применять оптимизированные варианты, рассмотренные выше. Не рассматривался еще частный случай, когда А- константа, В — нет. Его рассмотрим в следующий раз.

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


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

Сообщения: 76
Маленький оператор, а какое длинное обсуждение :)


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

Сообщения: 1019
Откуда: Днепропетровская обл.
sage писал(а):
Маленький оператор, а какое длинное обсуждение :)
Нутк. Мы даже надеемся убедить авторов AO и КП в том, что надо пересмотреть стандарты в части FOR. :)

Кстати, Олег, а ведь цикл со step > 0, если step > MAX(T):
Код: "OBERON"
  1. FOR n := A TO B BY step
ВСЕГДА будет исполняться 1 раз при любых значениях A и B если A <= B, и ни разу если A > B. Ровно так же, как и цикл со step < 0 и step < MIN(T) будет исполняться 1 раз если A >= B, и ни разу если A < B. По крайней мере, хорошо если он будет исполняться так, ибо так задумано. На деле если будут безконтрольные заёмы и переполнения, то это ещё хуже! А если шаг вылез за пределы типа, то они будут обязательно!

Ты видишь хоть какой-то смысл в таких циклах?

Я не вижу. Поэтому, считаю, ограничение на значение шага цикла по размеру типа со строгим контролем на этапе компиляции — хорошее решение (для типов со знаком).


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

Сообщения: 1019
Откуда: Днепропетровская обл.
Интересное кино получается. Решил проверить что будет, если конечное значение цикла (B - A) MOD step # 0, и вот такой код в BlackBox преспокойно себе зависает:
Код: "OBERON"
  1. MODULE Test;
  2. IMPORT Log;
  3.  
  4. PROCEDURE Do* ;
  5. VAR i : SHORTINT;
  6. BEGIN
  7. FOR i := 0 TO 32767 BY 10000 DO Log.Int(i) END
  8. END Do;
  9.  
  10. END Test.
В Ofront'е та же хрень! Я конечно понимаю умом, что согласно стандарту (FOR это WHILE n <= B) так оно и должно быть, но всё же тоже изъянчик!

Он может быть решён, если корректировать значение B до вхождения в цикл (для константных А и B — на этапе компиляции, для неконстантных — в рантайме). Что, с одной стороны, сделает наши программы чуть надёжнее (не будут зависать при недостаточно точно заданном значении B), с другой, — открывает неограниченные просторы шляповатым программистам-построителям корявых циклов. Эх, хотелось бы увидеть здесь золотую середину.

Кстати, цикл FOR таки можно сводить к WHILE n <= B, но если ничего не делать с этим переполнением, и B точно не на границе значения типов (B < MAX(T) для step > 0, B > MIN(T) для step < 0).


Вложения:
Комментарий к файлу: «Дойти до точного равенства = 127 любой ценой!» — но не дойдёт никогда, ибо A и step парные, а B — нет. Вот как в Обероне-2 работает цикл FOR если (B - A) MOD step # 0. Это безобразие какое-то!
FOR.png
FOR.png [ 9.75 КБ | Просмотров: 17198 ]
Вернуться к началу
 Профиль  
Ответить с цитатой  
 Заголовок сообщения: Re: Мы наш, мы новый FOR построим
СообщениеДобавлено: 13 апр 2013, 05:57 
Не в сети
Администратор
Аватара пользователя

Сообщения: 273
Откуда: Россия
Zorko писал(а):
Кстати, Олег, а ведь цикл со step > 0, если step > MAX(T)...ВСЕГДА будет исполняться 1 раз при любых значениях A и B если A <= B, и ни разу если A > B. Ровно так же, как и цикл со step < 0 и step < MIN(T) будет исполняться 1 раз если A >= B, и ни разу если A < B.
Совершенно верно, цикл со слишком большим шагом, таким, что даже 1 раз шагнуть нельзя, выполняется 0 или 1 раз, т.е. превращается в условный оператор.
Цитата:
Ты видишь хоть какой-то смысл в таких циклах?
Я не вижу. Поэтому, считаю, ограничение на значение шага цикла по размеру типа со строгим контролем на этапе компиляции — хорошее решение (для типов со знаком).
Можно было бы разрешить компилятору допускать такие шаги и автоматически делать превращение цикла в условный оператор, но, по-моему, всё таки лучше выдавать в этом случае ошибку компиляции. Ведь шаг задается константой, её программист явно пишет, заранее планируя тот или иной цикл. И если цикл - это фактически "не цикл", то, скорее всего, здесь какая-то ошибка в типе или в константном выражении. Единственный смысл может быть при отладке - программист намеренно ставит очень большой шаг, чтобы посмотреть, что будет при выполнении цикла только 1 раз. Но этого же он может достичь коррекцией В. Поэтому по-прежнему считаю, что шаг (по абсолютной величине) должен быть в диапазоне 1..МАХ(Т)-MIN(T), иначе должна быть ошибка компиляции.

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


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

Сообщения: 273
Откуда: Россия
Zorko писал(а):
Так что имеет смысл предупредить программиста, что в цикле есть какой-то недочёт. Это будет полезно. Но предупреждать надо, конечно же, не только когда значение шага вышагнуло за пределы типа счётчика цикла, а вообще хорошо бы давать warning если цикл исполняется только один раз. Это будет по-оберонски.
Да, предупреждения о странностях - это хорошо. Кстати, и в случае большого шага, возможно, "средний" вариант (не ошибка компиляции и не игнорирование, а предупреждение) будет лучше всего.

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

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


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

Сообщения: 273
Откуда: Россия
А вот еще интересный вопрос. Что если у цикла FOR пустое тело? Обычно такие циклы пишут, чтобы тянуть время (реализация delay, PAUSE). Но в функциональной семантике (фрагмент кода превращает свое предусловие в постусловие, и неважно каким путем он это делает) FOR c пустым телом эквивалентен пустому оператору. Даже присвоение n:=A можно не делать из-за постулата "значение n по окончании цикла не определено".
Ах да, нужно учесть возможные побочные эффекты от вычисления А и В. Если мы цикл вообще опускаем, то и побочные эффекты в выражениях А и В не срабатывают.Конечно, некрасиво на всякую "побочность" расчитывать, уж лучше явно вызвать.
Что же будем делать? Вообще этот цикл выкинем, вычислим только А и В (чтобы отработали побочные эффекты) или транслируем в полноценный цикл с проверками границ, шагом, но с пустым телом?

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

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


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

Сообщения: 273
Откуда: Россия
На сообщение Zorko:
Zorko писал(а):
Я конечно понимаю умом, что согласно стандарту (FOR это WHILE n <= B) так оно и должно быть, но всё же тоже изъянчик!
Он может быть решён, если корректировать значение B до вхождения в цикл (для константных А и B — на этапе компиляции, для неконстантных — в рантайме).
Вот цикл для общего случая как раз это и делает. До начала цикла вычисляется limit - это и есть "откорректированное В". Причем от А это значение совсем не зависит, т.е. для корректировки на этапе компиляции достаточно "константности" только В (частный случай).
Цитата:
Что, с одной стороны, сделает наши программы чуть надёжнее (не будут зависать при недостаточно точно заданном значении В), с другой, — открывает неограниченные просторы шляповатым программистам-построителям корявых циклов. Эх, хотелось бы увидеть здесь золотую середину.
Насчет "неограниченных просторов" не понял... Имелось в виду "недостаточно точно задать В, надеясь, что компилятор откорректирует"? Это можно неточно задать и сейчас, надеясь что шаг проскочит мимо ненужного. А вот если кто-то использует зацикливание при B=MAX(T) в качестве полезного эффекта в своей программе, то это гораздо худший трюк. Вообще, зацикливание при B=MAX(T) - вот самое плохое и корявое.
Цитата:
Кстати, цикл FOR таки можно сводить к WHILE n <= B, но если ничего не делать с этим переполнением, и B точно не на границе значения типов (B < MAX(T) для step > 0, B > MIN(T) для step < 0).
Не совсем так. FOR byte := 0 TO 123 BY 8 DO, где byte - знаковый (-128..127), зациклится точно также, хотя B не на границе.

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


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

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

Признаю, что, пожалуй, был слишком нетерпим относительно принципа шага в применении к знаковым числам. Знаковый тип симметричен относительно нуля (строже сказать, почти симметричен), поэтому позволяет шагать на половину диапазона. На практике этого более чем достаточно. Ну 3 итерации с половинным шагом получается, а не 2, как с "полнодиапазонным", так что же? Может лучше для больших шагов программисту вообще тело цикла в процедуру оформить с переменной цикла в качестве входного параметра и вызывать DoIter(MIN(T)); DoIter(MAX(T)) ?
Можно и так, но принцип выбора шага всё равно ошибочный, хотя бы методически (тип самого элемента и тип "разница элементов" по своей природе разный; двигаться в одном направлении можно большими шагами, чем в другом, хотя эти направления по смыслу равноправны). Но для знаковых типов эта ошибка приводит не к таким неприятностям как у беззнаковых.
На первых порах можно принять такой принцип "шаг цикла FOR знакового типа, даже если сама переменная цикла беззнаковая", что позволит без переделки Ofront шагать на полдиапазона в любом направлении для любого типа чисел.
Но всё-равно, по-моему, самый правильный диапазон для шага "плюс\минус 1 .. MAX(T)-MIN(T)"!

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


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

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

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

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

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

Если же A+Step<=MAX(T), то количество итераций (0,1 или более) зависит от B. Я не вижу, какие в этом случае можно провести оптимизации по сравнению с общим случаем.

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


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

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


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

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


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

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