OberonCore
https://forum.oberoncore.ru/

WHILE-ообразный LOOP - вычисления между конъюнктами
https://forum.oberoncore.ru/viewtopic.php?f=82&t=6581
Страница 1 из 1

Автор:  Илья Ермаков [ Понедельник, 09 Март, 2020 15:54 ]
Заголовок сообщения:  WHILE-ообразный LOOP - вычисления между конъюнктами

Когда нужно между конъюнктами WHILE что-то дополнительно сделать, а уходить на вложенную функцию-предикат накладно:

Вложения:
Снимок экрана от 2020-03-09 15-53-33.png
Снимок экрана от 2020-03-09 15-53-33.png [ 15.74 КБ | Просмотров: 2623 ]

Автор:  Comdiv [ Понедельник, 09 Март, 2020 22:52 ]
Заголовок сообщения:  Re: WHILE-ообразный LOOP - вычисления между конъюнктами

"Накладно" в смысле экономии тактов?

Автор:  adimetrius [ Понедельник, 09 Март, 2020 23:24 ]
Заголовок сообщения:  Re: WHILE-ообразный LOOP - вычисления между конъюнктами

Если я правильно понял, вот эту условную программу надо было изобразить?

Код:
WHILE (i < cnt) & (S.GET(src + offs) # p) DO INC(i); INC(src, elemSize) END;


Почему бы не вот так:
Код:
i := 0; done := i >= cnt;
WHILE ~done DO
   S.GET(src + offs, val); done := val = S.VAL(Mem.AddrInt, p);
   IF ~done THEN INC(i); INC(src, elemSize) END
END


Двойной LOOP - тяжело понимать.

Автор:  Artyemov [ Вторник, 10 Март, 2020 01:23 ]
Заголовок сообщения:  Re: WHILE-ообразный LOOP - вычисления между конъюнктами

adimetrius писал(а):
done := i >= cnt;...
done := val = S.VAL(Mem.AddrInt, p);

Здравствуй криптосинтаксис ;-) скобочки дорого.
Ну и вызывать S.VAL(Mem.AddrInt, p) столько раз, сколько цикл прокрутим как-то не очень...

Автор:  Trurl [ Вторник, 10 Март, 2020 08:21 ]
Заголовок сообщения:  Re: WHILE-ообразный LOOP - вычисления между конъюнктами

"вызывать" для VAL слишком почетно.

Автор:  Илья Ермаков [ Вторник, 10 Март, 2020 12:28 ]
Заголовок сообщения:  Re: WHILE-ообразный LOOP - вычисления между конъюнктами

adimetrius писал(а):
Если я правильно понял, вот эту условную программу надо было изобразить?

Код:
WHILE (i < cnt) & (S.GET(src + offs) # p) DO INC(i); INC(src, elemSize) END;


Почему бы не вот так:
Код:
i := 0; done := i >= cnt;
WHILE ~done DO
   S.GET(src + offs, val); done := val = S.VAL(Mem.AddrInt, p);
   IF ~done THEN INC(i); INC(src, elemSize) END
END


Двойной LOOP - тяжело понимать.


Так он не двойной там! Он одинарный - и два IF. В том и идея, что для каждого конъюнкта цикла ставим вложенный IF чисто механически - и так же механически несколько раз в конце ELSE EXIT.
Виды условий сохраняются такими же, как были бы в WHILE. Вводить доп. переменные и выискивать, как они там выставляются, не нужно.

Автор:  adimetrius [ Вторник, 10 Март, 2020 18:48 ]
Заголовок сообщения:  Re: WHILE-ообразный LOOP - вычисления между конъюнктами

Упс, ошибочка, надо так:

adimetrius писал(а):
Код:
i := 0;
WHILE (i < cnt) & ~done DO
   S.GET(src + offs, val); done := val = S.VAL(Mem.AddrInt, p);
   IF ~done THEN INC(i); INC(src, elemSize) END
END


Я полагаю, варианты с WHILE/done и LOOP эквиваленты, и оба нехороши тем, что, фактически, несколько точек выхода из конструкции. Что нарушает принцип стрктрного программирования: у каждой штуковины один вход - один выход. В LOOP они отмечены словом EXIT, в WHILE/done - перевычислением done. В обоих случаях нужно "следовать" за вычислителем, чтобы понять, почему мы тут оказались.
С предикатной процедурой была бы совсем другая - ясная - песня: один вход - один выход. Если, канешн, она будет без особо побочных эффектов ).

И оба варианта подходят для формального использования. Вот мой:
Код:
WHILE A & (P)B DO C END

done := FALSE;
WHILE A & ~done DO
   P;
   done := ~B;
   IF ~done THEN C END
END


adimetrius писал(а):
Двойной LOOP - тяжело понимать.
Илья Ермаков писал(а):
Так он не двойной там! Он одинарный - и два IF.

О, а я не заметил! случайность ⋁ непривычность ⋁ неясность

А вы студентам преподаете такие шаблоны проектирования циклов?

Автор:  PSV100 [ Пятница, 13 Март, 2020 19:18 ]
Заголовок сообщения:  Re: WHILE-ообразный LOOP - вычисления между конъюнктами

adimetrius писал(а):
Я полагаю, варианты с WHILE/done и LOOP эквиваленты, и оба нехороши тем, что, фактически, несколько точек выхода из конструкции. Что нарушает принцип стрктрного программирования: у каждой штуковины один вход - один выход. В LOOP они отмечены словом EXIT, в WHILE/done - перевычислением done. В обоих случаях нужно "следовать" за вычислителем, чтобы понять, почему мы тут оказались.
С предикатной процедурой была бы совсем другая - ясная - песня: один вход - один выход. Если, канешн, она будет без особо побочных эффектов ).

Предикатные процедуры в подобной задаче будут сплошь с побочными эффектами (в общем, не предикаты как таковые по сути). Вспомнилась задачка по поводу:
* http://oberspace.org/index.php/topic,425.msg13047.html#msg13047
* http://oberspace.org/index.php/topic,425.msg13278.html#msg13278

По ссылкам выше тело цикла состоит лишь из инкремента счётчика, а все реальные "циклические действия" -- внутри "предикатов". На блок-схеме/Дракон-е все "действия" были бы упрятаны в "вопросах" (которые формально должны заниматься лишь опросом текущего состояния, да еще в приправу само выражение отношения следования действий по сути есть паразитизм на short-circuit evaluation логических операций).

Тем не менее, решение на псевдопредикатах, по-видимому, будет самым распространённым (оставляя за рамками аля for-ы с break/return-ами), а то и вынужденным при забаненном операторе вида LOOP с EXIT.
Аналогично частенько такие "монады" выстраиваются и в условиях для "if".
Но, всё же, показать реальный цикл иногда нужно (вероятно, в этом суть исходного тезиса "накладно применять предикаты").

Автор:  PSV100 [ Пятница, 13 Март, 2020 19:28 ]
Заголовок сообщения:  Re: WHILE-ообразный LOOP - вычисления между конъюнктами

adimetrius писал(а):
Илья Ермаков писал(а):
Так он не двойной там! Он одинарный - и два IF.

О, а я не заметил! случайность ⋁ непривычность ⋁ неясность

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

Вспоминаются попытки "обобщенного цикла" с операторами CHECK, АndWhile (операторы "верхнего уровня" в блоке-цикле, разрезающие блок на части):
* https://forum.oberoncore.ru/viewtopic.php?p=57745#p59240
* http://oberspace.org/index.php/topic,425.msg13272.html#msg13272

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


Сейчас появляется мода на явный оператор "защитного выражения". Напр., таковой ввели в Swift -- оператор guard:
https://www.programiz.com/swift-programming/guard-statement

По сути, это "if", но с пустым телом then-части, нет elsif-альтернатив, else-часть (срабатывающая, если условие не истинно) должна предусматривать выход из текущей синтаксической области. В общем, узаконенный способ для "раннего выхода", небезосновательно, однако:
* https://blog.timoxley.com/post/47041269194/avoid-else-return-early
* https://habr.com/ru/post/348074/

Структурные решения вида "return только в конце" с проверками для каждого этапа "монады" (с целью уменьшения вложенности условных блоков) аля:
* https://forum.oberoncore.ru/viewtopic.php?f=27&t=3175#p57990
* https://forum.oberoncore.ru/viewtopic.php?f=6&t=2290

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

В "компонентном ассемблере" Недори есть аналог оператора guard как "проверить Условие завершить [ Выражение ]" -- стиль: "отбрось лишнее, потом работай" ("в каком-то смысле, оператор проверить является инструментом реализации «главного маршрута алгоритма» в Дракон диаграммах"):
http://digital-economy.ru/stati/komponentnyj-assembler-chast-2-dukh-yazyka

Однако, Недоря декларирует применение "проверить" лишь в начале процедуры -- "защитное выражение" всей подпрограммы. Видимо, по аналогии с циклом выше и из-за таких же потребностей, напрашивается расширение допустимой области, но только в пределах верхнего уровня процедуры, не внутри каких-либо операторов (в таком случае досрочные выходы должны быть подкреплены некими механизмами аля defer или scope exit как в D, секция finally, деструкторы или финализаторы). Вид оператора пусть будет таким:
Код:
GUARD condition ELSE
  ...
  RETURN ...
END

Тогда для LOOP вместо EXIT также можно предусмотреть свои "защитные выражения", но в отличие от защит процедуры, оператор GUARD защищает дальнейшие, именно циклические, действия (недолжно быть "нециклических" операций, связанных с прерыванием цикла). Вместо ELSE используется DO:
Код:
LOOP GUARD c1 DO
  p1;
  GUARD c2 DO
    p2;
  ELSIF c3 DO
    p3;
  END
END END

В операторе GUARD DO нет ELSE, возможны ELSIF-альтернативы. Если условие ложно, цикл прерывается. После GUARD не допускается следование каких-то иных операций.

Операторы WHILE (в т.ч. и как "цикл Дейкстры"), FOR (с защитой вида "для всех ..."), фактически, по сути есть синтаксический сахар как частные случаи обобщённого цикла LOOP-GUARD.
Возможна краткая форма цикла с единственным GUARD в конце (без DO) как аналог do-while:
Код:
LOOP
  ...
GUARD condition END

В таком случае исключается потребность в REPEAT...UNTIL, и тогда существует единая методология для всех форм цикла.

По сравнению с исходным примером цикла в данном случае нет "ELSE EXIT" и наблюдается явное ключевое слово GUARD.
Вот такие вот защиты действий и защиты циклических операций (в общем, прям классика ...).

Автор:  PSV100 [ Пятница, 13 Март, 2020 19:31 ]
Заголовок сообщения:  Re: WHILE-ообразный LOOP - вычисления между конъюнктами

В докладе на Дне Оберона был представлен концепт метапрограммирования. Любопытно, предполагает ли некая техника макропостроений возможность внедрения операторов, подобных выше с учётом семантического контекста (на чём был акцент в докладе)? Т.е., в частности, с контролем области применения (включая недопустимость следования операций), может ли условное макрорасширение "циклы" корректно взаимодействовать с неким иным (независимым и изначально неизвестным разработчикам) макрорасширением "defer" (по мотивам Go) и пр.

Автор:  PSV100 [ Вторник, 17 Март, 2020 20:13 ]
Заголовок сообщения:  Re: WHILE-ообразный LOOP - вычисления между конъюнктами

PSV100 писал(а):
По сравнению с исходным примером цикла в данном случае нет "ELSE EXIT" и наблюдается явное ключевое слово GUARD

Однако, оператор GUARD как защитное выражение верхнего уровня ограничивает "вычислительную мощность". В случае сложных условий, м.б. с несколькими уровнями вложенности, с применением операторов вида CASE...OF и др., потребуются вспомогательные средства, напр., дополнительные "управляющие" переменные как в примере с WHILE/done выше (от чего, собственно то, была попытка избавиться с помощью GUARD).

В целом, есть вариант борьбы со сложными условиями с помощью конъюнктов, но иным способом.

Относительно недавно на форуме Дракон-а была тема как раз по поводу -- демонстрация Дракон-схем как лучшего способа "выращивания деревьев решений":
Преимущества языка ДРАКОН для деревьев принятия решений

Рассмотрим "самым тяжёлый" случай -- с "неструктурным" переплетением "вопросов" (основная фишка Дракон-а):
https://forum.drakon.su/viewtopic.php?f=228&t=6666#p103696
Изображение

По ссылке выше имеется полноразмерная картинка с кодом и краткой постановкой задачи -- обработчик события нажатия левой кнопки мыши для виджета TreeView. Итоговый генерируемый код переварить, в самом деле, сложнее, чем схему. Если оперировать текстовой формой алгоритма, то необходимо кардинально всё перекручивать, вероятно, с дополнительными "управляющими" переменными и пр. (или же goto). Однако и сама схема в данном случае из разряда: "нельзя понять одним махом, как можно понять анекдот" (там же рядом по ссылке). В данном варианте схемы не удалось избавиться от дублирования предикатов (в частности: machine.state === "expanding"). Попробовать найти альтернативный вариант схемы без возникающих пересечений линий и соответственно без разнесения функционала по веткам силуэта (иначе исходные явные отношения между условиями визуально разрываются) -- непростая задача, однако... Есть топологические ограничения и требования, но единственная методология построения схем -- метод "научного тыка".

Меня впечатлила методика Esterel/Lustre. В одном из диалектов Lustre (ML-вариация для dataflow) введена дополнительная форма "сопоставления с образцом", точнее -- специальный оператор тестирования событий. Упрощённо суть в следующем:
Код:
let node sum x y = z where
  present
  | x(v) & y(w) -> do emit z = v + w done
  | x(v1) -> do emit z = v1 done
  | y(v2) -> do emit z = v2 done
  | _ -> do done
  end

Выше "let node ..." -- объявление типа как аналога "активной ячейки" (active cell, а также и cellnet) из A2, с входными портами "x", "y" и выходным портом "z". Оператор present...end -- некий аналог CASE...OF или match...with в ML, но тестируется не указанный элемент-операнд, а любые доступные объекты. Так выражение "x(v)" -- извлечь значение из порта "x" в переменную "v", если порт содержит данные ("emit z" -- операция "эмиссии" сигнала, в данном случае для выходного порта, "do...done" -- аналог "begin...end" в ML). Семантика этого оператора основана на мотивах "join calculus" -- в отличие от прочих "защит" в виде логических выражений в данном случае образцы событий допускают только операцию конъюнкции. Тестирование вариантов событий упорядоченно (сверху вниз), методика предполагает указание сначала наиболее полных образцов событий, возможна ситуация "иначе" (компилятор способен проконтролировать охват всех вариантов событий если нет "иначе"). Все дублирования в тестировании/проверках компилятор должен ликвидировать -- это его забота построить эффективную лапшу из goto или чего там требуется на конкретной платформе.

Так достигается свёртка уровней и компактизация (теоретически и эффективность).

Автор:  PSV100 [ Вторник, 17 Март, 2020 20:18 ]
Заголовок сообщения:  Re: WHILE-ообразный LOOP - вычисления между конъюнктами

Подобную "защиту" можно внедрить и в рядовую императивщину, а в случае наличия такого оператора как WITH в Modula (определяющий алиасы) -- в т.ч. и с "ленивыми вычисленими" в явном виде (когда это удобно). Если фантазировать, в гипотетической Modula для всего блока BEGIN...END (вместо отдельного оператора) можно ввести "защитные выражения" на конъюнктах (аля "pattern matching" верхнего уровня). Плюс оператор WITH сразу "привязывается" к блоку BEGIN...END (как VAR), алиас может быть ассоциирован с произвольным выражением.
Фантазия может быть примерно в таком виде -- псевдокод для задачи выше про обработчик события в TreeView:
Код:
PROCEDURE Tree_itemClick(machine, item, event)
BEGIN
  IF event.button = 0 THEN
    VAR
      now := getUnixTime();
    WITH
      lastClick := item.lastClick;
      threshold := now - item.lastClick > DoubleClickThreshold;
      expanding := machine.state = "expanding";
    BEGIN
    | lastClick & threshold:
        item.lastClick = now;
        IF event.ctrlKey THEN
          Tree_ctrlClick(machine, item)
        ELSE
          IF item.leaf THEN
            Tree_singleClick(machine, item, event)
          ELSE
            Tree_clearSelection(machine);
            Tree_selectItem(machine, item);
            Tree_toggleExpand(machine, item, event);
          END   
        END
    | lastClick & expanding:
        machine.postponedDClick = item.id
    | lastClick:
        Tree_doubleClick(machine, item, event)
    ELSE
      (* skip *)
    END
  END
END

Если блок BEGIN начинается с "|" -- весь блок "нарезается" на варианты конъюнктов условий (с возможностью ELSE). Необязательный оператор WITH вводит имена-алиасы для компактизации записи, в отличие от VAR -- выражения "ленивые" и вычисляются по требованию (в контексте тестирования событий, т.е. не предполагается какой-то механизм в стиле thunk-ов в "ленивых" функциональных языках). В целом в образцах событий возможны любые выражения (не только алиасы), в случае применения процедур возникают нюансы с поддержкой свойства "быть предикатом или чистым" -- отсутствие побочных эффектов (гипотетически решаемо).

Такая линеаризованная расшифровка условий помогает прочитать и Дракон-схему выше. Вариант на Р-схеме будет таким:
Изображение

Выше используется двойная дуга-блок с разрывом. Ранее здесь на форуме при разборе полётов вокруг Р-схем не было акцента на таком типе дуг. Так раньше задавался "pattern matching", аля "CASE OF" (а если нет надписи на дуге -- будет WITH, с подписями под дугой):
Изображение

В целом, таковы защиты "вычислительно мощнее" оператора GUARD ранее. Если вдруг иметь "наколенную Nemerle" с возможностью создания "Modula для себя", то, пожалуй, предпочтительнее конъюнкты...

Автор:  PSV100 [ Вторник, 17 Март, 2020 20:21 ]
Заголовок сообщения:  Re: WHILE-ообразный LOOP - вычисления между конъюнктами

Тогда для циклов вида LOOP (без общего предиката для всего блока) можно ввести ограничения (кому нужно) -- нельзя размещать операции после оператора EXIT или любого блока, его содержащего. В отношение Р-схем (что нагляднее) -- дуга со структурным выходом (с "*") должна "упираться" в правую границу циклической структуры:
Код:
LOOP IF c1 THEN
  p1;
  BEGIN
  | c2 & c3 & c4:
      p2; p3
  | c3:
      p4
  ELSE EXIT
  END
ELSE EXIT
END END

Вложение:
loop_bg_ex.png
loop_bg_ex.png [ 4.27 КБ | Просмотров: 2407 ]

Страница 1 из 1 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/