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

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

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




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

Сообщения: 1019
Откуда: Днепропетровская обл.
Saferoll писал(а):
А вот еще интересный вопрос. Что если у цикла FOR пустое тело? Обычно такие циклы пишут, чтобы тянуть время (реализация delay, PAUSE). Но в функциональной семантике (фрагмент кода превращает свое предусловие в постусловие, и неважно каким путем он это делает) FOR c пустым телом эквивалентен пустому оператору.

Ах да, нужно учесть возможные побочные эффекты от вычисления А и В. Если мы цикл вообще опускаем, то и побочные эффекты в выражениях А и В не срабатывают.Конечно, некрасиво на всякую "побочность" расчитывать, уж лучше явно вызвать.
Что же будем делать? Вообще этот цикл выкинем, вычислим только А и В (чтобы отработали побочные эффекты) или транслируем в полноценный цикл с проверками границ, шагом, но с пустым телом?
Значения A и B, мне кажется, нужно обязательно вычислить.

Saferoll писал(а):
Я склоняюсь к последнему варианту, пустые циклы могут понадобится на целевой платформе, для котором мы программы и создаем. К тому же, это самый легкий для компилятора вариант — просто ничего не нужно дополнительно делать, всё транслируется по общим правилам.
Но какие еще будут мнения?
В случае с Ofront'ом можно отдать эту задачу на откуп сишному компилятору. Хороший сишный компилятор должен превратить такой цикл в пустой. Или будем заниматься развёрнутой оптимизацией? :) Но тогда её надо делать по полной программе — "по всему периметру", а не только для пустых циклов. :)

"Тянуть время" с помощью цикла FOR (или серии из вложенных FOR) — это порождать платформенно-зависимый (от скорости процессора) код, притом загружающий процессор на 100%. Так делали для Z80 на ассемблере, но, работая на Обероне, такие задержки обязательно надо выносить хотя бы в отдельную (для Z80 — ассемблерную) процедуру Delay, Sleep, Wait или Pause.

Кстати, если B является константой, и её значение заведомо не равно предельному значению типа в сторону шага цикла (MAX(T) — для положительного шага; MIN(T) — для отрицательного), то компилятор может сводить цикл к такому (n := A; WHILE n <=B DO) как он есть сейчас. А переполнения — вопрос особый. Я начинаю склоняться к тому, что их надо обрабатывать более тотально, чем если в частном порядке это будет делать только FOR.


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

Сообщения: 273
Откуда: Россия
Zorko писал(а):
Значения A и B, мне кажется, нужно обязательно вычислить...
В случае с Ofront'ом можно отдать эту задачу на откуп сишному компилятору. Хороший сишный компилятор должен превратить такой цикл в пустой.
Т.е., получается, цикл с пустым телом просто никак не выделяем среди остальных. Согласен.

Цитата:
Или будем заниматься развёрнутой оптимизацией? :) Но тогда её надо делать по полной программе — "по всему периметру", а не только для пустых циклов. :)
И с этим согласен. Я прикинул частные случаи циклов для которых возможна оптимизация, но реализовать их следует постепенно. Сначала нужно научить Ofront транслировать самый общий цикл, куда частные случаи входят, хотя и не так эффективно выполняются.

Цитата:
"Тянуть время" с помощью цикла FOR (или серии из вложенных FOR) — это порождать платформенно-зависимый (от скорости процессора) код, притом загружающий процессор на 100%. Так делали для Z80 на ассемблере, но, работая на Обероне, такие задержки обязательно надо выносить хотя бы в отдельную (для Z80 — ассемблерную) процедуру Delay, Sleep, Wait или Pause.
С этим тоже не спорю, но ведь программист может написать пустой цикл, даже имея в своем распоряжении Delay, Sleep и пр.? Значит всё равно придется этот пустой цикл транслировать. Или будем выдавать предупреждение "Воспользуйтесь лучше Delay"?
Цитата:
Кстати, если B является константой, и её значение заведомо не равно предельному значению типа в сторону шага цикла (MAX(T) — для положительного шага; MIN(T) — для отрицательного), то компилятор может сводить цикл к такому (n := A; WHILE n <=B DO) как он есть сейчас.
Это верно только для единичного шага. Для большего шага я уже приводил контрпример.
Цитата:
А переполнения — вопрос особый. Я начинаю склоняться к тому, что их надо обрабатывать более тотально, чем если в частном порядке это будет делать только FOR.
Область целых чисел всегда ограничена, с этим ничего не поделаешь. FOR должен правильно выполниться для любого отрезка в этой области, даже если этот отрезок примыкает к краю или занимает всю область. Переполнения при этом может и вообще не возникнуть, если FOR не делает лишний шаг. Так что дело не в самом переполнении, а в лишнем инкременте. Но если уж реализация цикла делает этот лишний шаг и вызывает переполнение, то это переполнение нужно обнаружить и цикл прекратить. Не аварийно, а просто прекратить, т.к. это означает, что все элементы обработаны.

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


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

Сообщения: 1019
Откуда: Днепропетровская обл.
Saferoll писал(а):
Я прикинул частные случаи циклов для которых возможна оптимизация, но реализовать их следует постепенно. Сначала нужно научить Ofront транслировать самый общий цикл, куда частные случаи входят, хотя и не так эффективно выполняются.
Абсолютно верно. "Пусть сначала это заработает, потом можно сделать это эффективнее".

Saferoll писал(а):
Значит всё равно придется этот пустой цикл транслировать. Или будем выдавать предупреждение "Воспользуйтесь лучше Delay"?
Да не, просто вычислим A и B и сделаем пустой цикл, а сишный компилер пусть что хочет с ним, то и делает. Я не против оптимизации, даже большой оптимизации, но это крайне сложный труд, который частично уже проделан в другом трансляторе Оберона-2 в Си — OO2C. Стоит ли превращать простой и компактный Офронт в нечто подобное OO2C?

Saferoll писал(а):
Это верно только для единичного шага. Для большего шага я уже приводил контрпример.
Кстати, да, не поспоришь. :)

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


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

Сообщения: 273
Откуда: Россия
Еще одно замечание о шаге цикла FOR. Я по-прежнему считаю, что шаг цикла (по абсолютной величине) должен быть в диапазоне 1..MAX(T)-MIN(T), а знак этого шага задает направление - возрастание или убывание. Оба направления равноправны, т. к. у процессора есть и декремент и инкремент, есть и сложение и вычитание. Я бы хотел, чтобы знак «-» говорил о том, что надо двигаться в сторону убывания (вычитать |шаг|, контролировать левую границу ), а «+» о возрастании (прибавлять |шаг|, контролировать правую границу). А сам шаг рассматривался бы по абсолютной величине.

Но пока реализовать такой шаг затруднительно, реализация этого связана с реализацией беззнаковых чисел. Погоня одновременно за двумя зайцами, которых зовут FOR и Unsigned, приведет, скорее всего, к известному по поговорке результату. Поэтому пока будет "ловить" незацикливающийся FOR, а шаг у него пусть будет знаковым.

Но если шаг является знаковым, то направления не равноправны, потому что отрицательных чисел больше. Так в знаковом байте есть число «-128». И мы можем прибавить к текущему значению переменной отрицательное число «-128», но не можем вычесть положительное число 128, потому что в знаковом байте такого положительного нет! Конечно, у процессора найдется комбинация 8ми битов, вычитая которую из текущего числа мы получим уменьшение именно на 128. Но это у процессора, а вот в Обероне, Ofront'e или Си могут возникнуть какие-то сложности.

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

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


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

Сообщения: 1019
Откуда: Днепропетровская обл.
Saferoll писал(а):
Переполнения при этом может и вообще не возникнуть, если FOR не делает лишний шаг. Так что дело не в самом переполнении, а в лишнем инкременте. Но если уж реализация цикла делает этот лишний шаг и вызывает переполнение, то это переполнение нужно обнаружить и цикл прекратить. Не аварийно, а просто прекратить, т.к. это означает, что все элементы обработаны.
Под "переполнением FOR" я имел ввиду случай, когда программер вместо:
Код: "OBERON"
  1. FOR ubyte := 0 TO 200 BY 100
напишет:
Код: "OBERON"
  1. FOR ubyte := 0 TO 300 BY 100
И оно отработает так же. Т.е. вроде бы и ничего, и цикл должен прощать такое "переполнение" (сейчас в популярных реализациях Оберона и КП — не прощает), но можно же не баловать программера и "не доводить до греха". А то сперва хвостик, потом лапка, а потом и вся тушка. ;)

Почему Мёссенбёк (а в Обероне-07 — и Вирт) приняли в отношении FOR такое решение, а мы — другое? Вот что меня смущает...

А как цикл FOR в Модуле-2, Модуле-3 реализован? Интересно, учтены ли эти моменты?


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

Сообщения: 273
Откуда: Россия
Zorko писал(а):
Под "переполнением FOR" я имел ввиду случай, когда программер вместо:
Код: "OBERON"
  1. FOR ubyte := 0 TO 200 BY 100
напишет:
Код: "OBERON"
  1. FOR ubyte := 0 TO 300 BY 100
И оно отработает так же. Т.е. вроде бы и ничего, и цикл должен прощать такое "переполнение" (сейчас в популярных реализациях Оберона и КП — не прощает), но можно же не баловать программера и "не доводить до греха". А то сперва хвостик, потом лапка, а потом и вся тушка. ;)
Нет, под переполнением я подразумевал не это. Переполнение - следствие ограниченности целого типа и лишнего шага FOR. Как если бы красили забор и после последней доски попытались перенести кисть дальше. А дальше пути нет - вляпались в угол соседского гаража. Сосед выскочил и ...произошло "переполнение"! :)
Границы А и B должны быть в пределах типа, иное прощать нельзя. Если тип до 255, то "ТО 300" должно быть обнаружено и отвергнуто еще на этапе компиляции (даже если 300 задается выражением) - это контроль типов. FOR решает задачу обработки всех элементов отрезка в данной области целых чисел, поэтому этот отрезок должен принадлежать области. Зацикливание возникает не когда отрезок выходит за пределы типа, а когда он "на самом краю". Правильный FOR - не тот, который позволяет нарушить контроль типов, а тот, что учитывает и правильно обрабатывает частный случай "подобласть на краю области".

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


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

Сообщения: 1019
Откуда: Днепропетровская обл.
Saferoll писал(а):
Границы А и B должны быть в пределах типа, иное прощать нельзя. Если тип до 255, то "ТО 300" должно быть обнаружено и отвергнуто еще на этапе компиляции (даже если 300 задается выражением) - это контроль типов.
Ладно, с этим не поспоришь. :)
Тогда так: "переполнение FOR" — это когда из-за шага точное достижение значения B невозможно:
Код: "OBERON"
  1. FOR n := 0 TO 255 BY 200
и в какой-то момент n подойдёт к шагу, который приведёт к выходу за пределы конечных значений типа.

Это для меня сложно — удержать все эти вещи в голове, никак не могу целостную картинку составить.


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

Сообщения: 273
Откуда: Россия
Zorko писал(а):
Тогда так: "переполнение FOR" — это когда из-за шага точное достижение значения B невозможно:
Код: "OBERON"
  1. FOR n := 0 TO 255 BY 200
и в какой-то момент n подойдёт к шагу, который приведёт к выходу за пределы конечных значений типа.
Но целью цикла FOR не является точное достижение В. Цикл должен выполниться для значений n=А, А+Step,A+2Step,...,A+kStep, которые не превосходят В. Последнее значение (если оно вообще есть) Nlast=A+kStep<=В, т.е. может быть равно В, но может быть меньше его. А вот следующее после последнего Nlast+Step должно в идеале быть больше В, по какому признаку его и следует обнаружить и прекратить итерации. Однако, если Nlast+Step>MAX(T) , то произойдет переполнение, которое испортит значение n. В результате "наивное" условие продолжения цикла WHILE n<=B посчитает, что цикл еще не закончен, что приведет к зацикливанию. Чтобы этого избежать нужно либо заранее определить, что следующий шаг превысит В и этот шаг не делать, либо не полагаться только на значение n, а замечать каким-то образом переполнение (проверкой флагов процессора или в какой-то булевской переменной при инкременте). Выше были примеры и того и другого подхода.

Или под словами "точное достижение" ты подразумеваешь что-то другое? Ты хотел условие при котором стандартный обероновский FOR сработает без переполнения? Это произойдет, если за В существует "буферная зона" - место для маневра, позволяющее сделать еще 1 шаг и не свалиться в пропасть переполнения. Своего рода "ничейная земля": если мы туда попали, то это еще ничего страшного - увидим, что мы за граничным столбом (В) и примем меры, в чужое государство ("переполнение") мы еще не заехали. Поэтому нужное условие В+Step<=MAX(T), т.е. сделав шаг, мы не вызовем переполнение (в крайнем случае окажемся на самом краю целого типа n=MAX(T)). Для Step<0 аналогично: В+Step>=MIN(T). Если будем писать эти условия в программе, то лучше их выразить в форме:
Цитата:
В<=MAX(T)-Step, Step>0
В>=MIN(T)-Step, Step<0
потому что В+Step может вызвать переполнение, а MAX(T)-Step (MIN(T)-Step) нет.

Это достаточное условие отсутствия зацикливания, но не необходимое, потому что от А зависит как далеко мы выскочим за В на последнем шаге. Если недалеко, то может и простого B<MAX(T) хватит. При B=MAX(T) (или B=MIN(T) для отрицательного шага) зацикливание неминуемо!

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


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

Сообщения: 273
Откуда: Россия
Теоретические исследования цикла FOR, можно сказать, закончены. Осталось подвести итоги и наметить план реализации.
Итак, основная схема, подходящая для всех случаев, в т.ч. для самого трудного, где А,В-вычисляются динамически, а шаг не единичный — это «общий цикл». Не буду здесь повторять то, что доступно по ссылке, лучше приведу «неструктурный» аналог на Си:
Код: "C"
n = A;
if(n <= B) goto jump_into_loop; else goto jump_loop_end;
if(B >= MIN(T)+Step)limit=B-Step+1;else limit=MIN(T);
do {
n += Step;
jump_into_loop:
 
/* Тело цикла. */
 
} while(n < limit);
jump_loop_end:
Здесь приведен вариант для Step>0. Для отрицательного шага нужно заменить: знаки «< \ <=» на «> \ >=» (и наоборот), а также заменить MIN(T) на MAX(T). По указанным выше причинам пока не будем заменять инкремент на декремент. Итак, для Step<0 получим
Код: "C"
n = A;
if(n >= B) goto jump_into_loop; else goto jump_loop_end;
if(B <= MAX(T)+Step)limit=B-Step-1;else limit=MAX(T);
do {
n += Step;
jump_into_loop:
 
/* Тело цикла. */
 
} while(n > limit);
jump_loop_end:

Вот эти два фрагмента (или их «структурный» вариант) и следует реализовать в первую очередь.

В дальнейшая можно сделать оптимизацию по длине шага:

1)Для ABS(Step)=1 есть упрощенный структурный вариант (который легко переделать в неструктурный). Кроме того, для единичного шага можно заранее вычислить число итераций и использовать отдельный счетчик (как, например, в Дельфи).

2)Для ABS(Step)=2 тоже несложно вычислить количество итераций (можно применить сдвиг для деления на 2 в формуле NumIters=(B-A) DIV Step + 1). Также для Step=2 можно вычислить последнее значение Nlast, применив AND вместо MOD.

3) Для ABS(Step)=2^k чуть сложнее (несколько сдвигов), зато эти сдвиги выполняются 1 раз перед итерациями. Можно вычислить Nlast, применив AND (2^Step-1) вместо MOD Step.

Другое направление оптимизации — по «константности» параметров А и В:
1)Если А и В константы, то можно еще при трансляции вычислить количество итераций или последнее значение.
2)Когда А — константа, В — нет, можно также сделать ряд оптимизаций.
3) И, наконец, случай "В — константа, А — нет" также можно учесть особо.

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

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


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

Сообщения: 273
Откуда: Россия
Для практического воплощения наших теоретических выкладок необходимо изучить транслятор Ofront. Займемся этим в новой ветке.

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


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

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


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

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


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

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