Как реализовывать ленивые вычисления?

[Sonic86]

Всем привет!
Задача у меня была такая: наклепать формочку, в которую клиент будет вводить формулы расчета всяких важных ему сумм в некотором не очень бедном синтаксисе (операции $+;-;\cdot;:$ а также PLSQL-функции и т.ч. вызовы функций пакетов).
Сделал я просто: клиент создает неупорядоченную кучу формул. Каждая формула содержит имя вычисляемого терма и формулу расчета. Вычисления я намеренно старался реализовать в функциональном стиле. Т.е. вычислитель (транслятор, если угодно) сам должен разобраться, что в каком порядке вычислять, а если клиент допустил циклическую ссылку в формулах, то вычислитель должен клиента явно обругать.
И я в итоге облажался, порядок вычисления я определелил, но поскольку мануалы я до конца не дочитал, то я реализовал энергичное вычисление формул (за счет execute immediate мне даже синтаксический анализатор не потребовался). И клиент для расчета некоей величины A только при выполнении условия P написал формулу вида A=dbase.iif(P,F,A), т.е. формулу, содержащую циклическую ссылку (ну а что ему оставалось делать, да и довольно разумно), которую невозможно вычислить энергичной стратегией вычисления. (dbase.iif(P,F,A)=F, если P истинно, иначе равно A).
Я конечно сейчас хочу сделать ленивый порядок вычислений. Но мне теперь надо понять, как и в какой мере я вообще могу это сделать? Нагуглил вот это: https://softwareengineering.stackexchan ... tion-of-if, но здесь довольно кратко. Можно конечно сделать дополнить язык отдельной синтаксической конструкцией ЕСЛИ(А,В,С) и ее обрабатывать отдельно, но похоже в любом случае придется делать синтаксический анализ и аппликацию функции.

И собственно основной вопрос: насколько широк список функций, для которых нужны ленивые вычисления? Например, я могу в своем вычислителе отдельно обработать любую формулу, начинающуюся с dbase.iif. Но ведь этих dbase-ов в формуле может быть уйма, есть другие ленивые функции типа coalesce, decode, умножение на нуль и вообще клиент может писать и вставлять свои функции. Не могу же я искать и парсить его функции - это же смерть.
И насколько сложно охватить этот список? Если число таких функций - изначально известное фиксированное множество, то ладно - я могу вшить разбор всех случаев в код вычислителя. А если он более широк?
Важное замечание: вычислитель реализован на PL/SQL, язык бедный, указателей и прочих веселых вещей там нет (да, можно их эмулировать, но зачем же издеваться?). Решение не должно выводить за его пределы.

[arseniiv]

Не понял, что значит «вычислять величину только при условии» — если побочных эффектов нет, или если величине можно в противном случае присвоить произвольное значение (по идее, если условие не выполняется, должно же быть не важно, какое у неё тогда значение?), вычисление которого не имеет их (скажем, константы 0). И стратегия call by need всё равно не спасёт от зацикливания при вычислении A с определением A = if(false, …, A). Раз уж уже имеется определение порядка вычислений, циклические ссылки при этом должны определяться, и надо сообщать клиенту, что он неправ, когда они есть.

Sonic86 в сообщении #1270242 писал(а):

и вообще клиент может писать и вставлять свои функции

А в исходном-то языке какая стратегия вычислений? (Забыл. Пару процедур на PL/SQL составлял когда-то, но этой детали не помню.) Если call by value, то он, разумеется, не сможет написать ничего того, о чём вам стоило бы беспокоиться. Возможно, опять же, что-то недопонимаю.

Sonic86 в сообщении #1270242 писал(а):

Решение не должно выводить за его пределы.

Сочувствую.

-- Чт ноя 30, 2017 01:21:01 --

Пояснение к тому, что выше: в общем случае от той величины, которую иногда может быть «не надо» вычислять, могут зависеть другие. Что тогда делать с ними? А если от неё никто не зависит, можно вычислять её в константу, как указано выше, что совершенно недорого. Если в языке есть что-то типа null, величины с таким значением можно не выводить там, где их значения выводятся под конец, если клиент хотел, чтобы она ему не мозолила глаза при некотором условии. В общем, это видится как проблема XY: вместо невычисления при условии вполне может быть лучше что-то иное.

[rockclimber]

Я, честно говоря, ничего не понял.
Но я тоже пробовал писать трансляторы на PL/SQL.
Грубо говоря, после парсинга у вас получается дерево, а раз уж там все равно Oracle, то это дерево складываем в таблицу вида (id, parent_id, <все остальное>), а потом рекурсивный WITH:

Используется синтаксис Oracle 11 SQL

WITH t (id, parent_id, <все остальное>) AS (
  SELECT id, parent_id, <все остальное>
    FROM source_tree
   WHERE id = :START_POINT
   UNION ALL
  SELECT id, parent_id, <все остальное + расчеты>
    FROM source_tree s
   WHERE s.parent_id = t.id)
SELECT *
  FROM t

Хотя я вообще без понятия, насколько это будет "лениво".

-- 30.11.2017, 00:34 --

Кстати, ленивые вычисления придумали для оптимизации производительности вроде, да? Просто в PL/SQL execute immediate, coalesce и decode - это прямо противоположные производительности вещи. Последние два лучше на CASE заменить...

[Sonic86]

arseniiv в сообщении #1270245 писал(а):

А в исходном-то языке какая стратегия вычислений? (Забыл. Пару процедур на PL/SQL составлял когда-то, но этой детали не помню.) Если call by value, то он, разумеется, не сможет написать ничего того, о чём вам стоило бы беспокоиться. Возможно, опять же, что-то недопонимаю.

PL/SQL - обычный императивный язык с энергичной стратегией вычисления. Хотя там есть ленивые встроенные coalesce и decode, но это - исключение, а заставить клиента писать формулы через них не представляется возможным + это даже проблемы не решит.
Я руками пишу ленивый расчет. Т.е. мне на вход приходит строка, я ее парсю как хочу, в частности теоретически могу ленивый расчет сделать.

arseniiv в сообщении #1270245 писал(а):

Не понял, что значит «вычислять величину только при условии» — если побочных эффектов нет, или если величине можно в противном случае присвоить произвольное значение (по идее, если условие не выполняется, должно же быть не важно, какое у неё тогда значение?), вычисление которого не имеет их (скажем, константы 0).

Присвоить $0$ могу, но для этого придется разбираться в формуле и определять, можно или не можно, а это выглядит сложнее даже, чем исходная задача.

arseniiv в сообщении #1270245 писал(а):

И стратегия call by need всё равно не спасёт от зацикливания при вычислении A с определением A = if(false, …, A). Раз уж уже имеется определение порядка вычислений, циклические ссылки при этом должны определяться, и надо сообщать клиенту, что он неправ, когда они есть.

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

arseniiv в сообщении #1270245 писал(а):

в общем случае от той величины, которую иногда может быть «не надо» вычислять, могут зависеть другие. Что тогда делать с ними?

У меня такой проблемы пока нет К сожалению, даже на на анализ уже нет времени.

rockclimber в сообщении #1270248 писал(а):

Кстати, ленивые вычисления придумали для оптимизации производительности вроде, да? Просто в PL/SQL execute immediate, coalesce и decode - это прямо противоположные производительности вещи. Последние два лучше на CASE заменить...

Мне надо не для оптимизации (какая м.б. у меня оптимизация, если я для расчета $a=1+2$ строки парсю). Мне надо для расчета A=dbase.iif(P,F,A)

rockclimber в сообщении #1270248 писал(а):

Но я тоже пробовал писать трансляторы на PL/SQL.
Грубо говоря, после парсинга у вас получается дерево, а раз уж там все равно Oracle, то это дерево складываем в таблицу вида (id, parent_id, <все остальное>), а потом рекурсивный WITH:

Спасибо, я запишу себе, если понадобится - применю. "Ленивость" парсера неважна, важна стратегия вычисления "снаружи внутрь" в том языке, в котором работает клиент - именно для расчета штук вида A=dbase.iif(P,F,A).

Вообще, я поспал, и сейчас мне кажется самым простым написать аппликативный расчет только для внешнего dbase.iif.
Ввести в язык Если было бы хорошо, но тогда даже то, что сейчас вычисляет execute immediate, придется считать руками.
До чего я докатился

[arseniiv]

Sonic86 в сообщении #1270287 писал(а):

Присвоить $0$ могу, но для этого придется разбираться в формуле и определять, можно или не можно, а это выглядит сложнее даже, чем исходная задача.

Вам и не надо присваивать чему-нибудь ноль насильно, пусть клиент это делает, если ему не нужно что-то вычислять, вместо подстановки самой вычисляемой переменной. Это как-то совершенно нелогично делать, скажите ему, чтобы не писал A=dbase.iif(P,F,A), а писал A=dbase.iif(P,F,0).

[rockclimber]

Sonic86 в сообщении #1270287 писал(а):

A=dbase.iif(P,F,A)

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

[arseniiv]

Как я понял, тут модель вычислений, где переменные — типа ячеек электронной таблицы (забыл название). То есть не совсем даже переменные, их можно считать постоянными. Предполагается, что когда изменяется одна из них, все зависящие от неё пересчитываются и так далее. Тут, видимо, динамическое пересчитывание упоминать не нужно, раз всё считается каждый раз целиком, но зато оно говорит, что граф зависимостей не может содержать петли, если ему нужно быть «реализуемым», если понимать вычисление именно так.

[rockclimber]

arseniiv
Спасибо, теперь дошло! Но ведь тогда всё совсем просто: пишем запрос с connect by и ловим исключение ORA-01436: CONNECT BY loop in user data. А CONNECT_BY_ISCYCLE вроде бы должен даже сказать, в каком месте петля.

-- 30.11.2017, 15:02 --

Вот:

  with t as (select 1 id, 3 parent_id from dual union all
             select 2 id, 1 parent_id from dual union all
             select 3 id, 2 parent_id from dual)
  select t.*, connect_by_iscycle
    from t
 connect by nocycle prior id = parent_id 
 start with id = 1;

        ID  PARENT_ID CONNECT_BY_ISCYCLE
---------- ---------- ------------------
         1          3                  0 
         2          1                  0 
         3          2                  1 

Или вот:

  with t as (select 1 id, 3 parent_id from dual union all
             select 2 id, 1 parent_id from dual union all
             select 3 id, 2 parent_id from dual)
  select *
    from t
 connect by prior id = parent_id 
 start with id = 1
Error report -
SQL Error: ORA-01436: CONNECT BY loop in user data
01436. 00000 -  "CONNECT BY loop in user data"

[Sonic86]

arseniiv в сообщении #1270358 писал(а):

Sonic86 в сообщении #1270287 писал(а):

Присвоить $0$ могу, но для этого придется разбираться в формуле и определять, можно или не можно, а это выглядит сложнее даже, чем исходная задача.

Вам и не надо присваивать чему-нибудь ноль насильно, пусть клиент это делает, если ему не нужно что-то вычислять, вместо подстановки самой вычисляемой переменной. Это как-то совершенно нелогично делать, скажите ему, чтобы не писал A=dbase.iif(P,F,A), а писал A=dbase.iif(P,F,0).

Тогда в БД в случае $\neg P$ запишется $A=0$, а должно ничего не изменится.

rockclimber в сообщении #1270360 писал(а):

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

По-честному парсить язык PLSQL - это все-таки достаточно суровое требование . Ну я вот сегодня такое написал при условии, что $F,A$ - атомарные термы, а $P$ не содержит запятую.

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

[rockclimber]

Sonic86 в сообщении #1270460 писал(а):

По-честному парсить язык PLSQL - это все-таки достаточно суровое требование

Так вы же не честный PL/SQL парсите, а

Sonic86 в сообщении #1270242 писал(а):

формулы расчета всяких важных ему сумм в некотором не очень бедном синтаксисе (операции $+;-;\cdot;:$ а также PLSQL-функции и т.ч. вызовы функций пакетов).

То есть вам надо распознавать только арифметические операции и вызовы функций. Или ваш клиент и execute immediate использует?

И кстати, вы что-нибудь из этого читали?

Pavia в сообщении #935035 писал(а):

Пожалуй посоветую классику:
1) Альфред Ахо,Рави Сети,Джеффри Ульман. Компиляторы. 2-е издание, Вильемс 2003
Но по каждой теме главе надо смотреть и искать и читать дополнительный материал.
2) Т. Пратт, М. Зелковиц Языки программирования разработка и реализация. 4-е издание, Питер 2002

[arseniiv]

Sonic86 в сообщении #1270460 писал(а):

Тогда в БД в случае $\neg P$ запишется $A=0$, а должно ничего не изменится.

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

Ну или нет, не пас. Вам ведь, по сути, нужно условное присваивание — если условие не выполнилось, не присваивать. Вот его и нужно реализовать и придать ему какой-то понятный синтаксис. В каком-то языке, слышал, есть конструкции вида var = expr if cond, вот можно как-то так. Не очень корректно «отменять» присваивание, если выражение вычислилось во что-то особенное. Вот если при вычислении выкинулось исключение — резонно, но вам вряд ли захочется писать поддержку исключений, хотя в данном случае от них требуется всего ничего — некоторая функция error, при вычислении которой надо будет выставить какой-то флаг и пропускать вычисления всех остальных подвыражений текущего определения, а потом ничего не присвоить его LHS и пойти к следующему определению, сбросив, конечно, флаг. Нет, на мой взгляд, условное присвоение проще.

[Sonic86]

arseniiv в сообщении #1270473 писал(а):

Вам ведь, по сути, нужно условное присваивание — если условие не выполнилось, не присваивать. Вот его и нужно реализовать и придать ему какой-то понятный синтаксис. В каком-то языке, слышал, есть конструкции вида var = expr if cond, вот можно как-то так.

По идее да, следовало бы так сделать. Проблема чисто практическая - как только я введу новую синтаксическую конструкцию, у меня сразу перестанет работать execute immediate и сразу даже для расчета 1+2 придется парсить строку и вычислять дерево.
А хотя нет, не придется, довольно легко проверить, есть ли синтаксическая конструкция в тексте или нет, если ей придать вид функции Если(. Просто подстроку искать + еще одно небольшое условие проверить.

rockclimber в сообщении #1270470 писал(а):

То есть вам надо распознавать только арифметические операции и вызовы функций

Да, действительно, Вы правы, мне будет сильно легче.
Наверное я так и поступлю: напишу свою человекочитабельную функцию Если(А,В) и сделаю ее парсинг руками. Все равно даже для реализации "ленивости dbase.iif" мне это уже нужно. Хоть усложнять не буду.
Всем большущее спасибо! А то блин и спросить не у кого было.

(про литературу)

rockclimber в сообщении #1270470 писал(а):

И кстати, вы что-нибудь из этого читали?

rockclimber в сообщении #1270470 писал(а):

Пожалуй посоветую классику:
1) Альфред Ахо,Рави Сети,Джеффри Ульман. Компиляторы. 2-е издание, Вильемс 2003
Но по каждой теме главе надо смотреть и искать и читать дополнительный материал.

Вот это я читал, правда где-то до 200-300 страницы. И есть бэкграунд в виде регулярных и КС-языков (по учебникам тех же авторов). Я и писал что-то свое, дошел до синтаксического анализатора. Но времени не хватило. Сильно обломало в моменте, когда надо было выписывать грамматику, лишать ее левой рекурсии, лишать ее $\epsilon$-продукций и т.п. - а там их валом было. Т.е. конкретно для моей грамматики я делал это руками, а надо было писать алгоритмы автоматической нормализации грамматики.

Самое интересное, что на мой вопрос

Sonic86 в сообщении #1270242 писал(а):

И собственно основной вопрос: насколько широк список функций, для которых нужны ленивые вычисления? ...
И насколько сложно охватить этот список? Если число таких функций - изначально известное фиксированное множество, то ладно - я могу вшить разбор всех случаев в код вычислителя. А если он более широк?

ответа я так и не узнал.
Т.е. возьмем например PLSQL. Там 2 ленивые функции: decode и coalesce. Ну и м.б. and, or. Их - заранее известное полностью фиксированное множество, я могу себе представить, как их реализовали в компиляторе: просто в лоб при обработке дерева пишут что-то типа

if(Term == 'coalesce'){
  if(Eval(Var1) != 'null'){
    Value = Eval(Var1);
  }
  else if(Eval(Var2) != 'null'){
    Value = Eval(Var1);
  }
  else if(...){
    ...
  }
}

В частности, это означает, что программист на языке не может реализовать свою ленивую функцию.
А как дело обстоит в других языках с ленивым вычислением. Так же? Или в них программист может написать свою ленивую функцию F? Если да, то как тогда расчет с F(x1, ..., xn) обрабатывает компилятор?

А хотя мне теперь ответ уже не нужен - я же буду все энергично вычислять, да и все, ля-ля!!!

[arseniiv]

Sonic86 в сообщении #1270911 писал(а):

Проблема чисто практическая - как только я введу новую синтаксическую конструкцию, у меня сразу перестанет работать execute immediate и сразу даже для расчета 1+2 придется парсить строку и вычислять дерево.

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

Sonic86 в сообщении #1270911 писал(а):

А хотя нет, не придется, довольно легко проверить, есть ли синтаксическая конструкция в тексте или нет, если ей придать вид функции Если(. Просто подстроку искать + еще одно небольшое условие проверить.

Да. Если каждое определение у вас имело вид var = expr, а станет иметь вид var = expr [if cond]*, то всё действительно проще некуда. В другие конструкции при этом это if cond входить не может, если внутри expr не могут входить присваивания (что-то подсказывает, что нет).

* Здесь курсив — нетерминалы, болд — терминалы, простой шрифт — метасимволы.

[Sonic86]

(чем все закончилось)

Я все-таки избежал вообще разбора. Правда, это не сразу произошло и недопарсер свой я сохранил на всякий случай, чтобы в любой момент его легко было вставить.
Получилось сделать проще, но как-то даже неинтересно. (хотя я не проверял досконально и очень надеюсь, что я не ошибся)
Есть список имен переменных для старых значений $X=\{x_i\}$, есть список имен переменных для значений $Y=\{y_i\}$, которые надо вычислить, $X\cap Y\neg \varnothing$ (иначе - тривиально). Клиент задает множество формул вида $y_j=F(y_{j1},...,y_{jk_j})$, которым должны удовлетворять новые значения. Множество соответствий $\{y_{j1},...,y_{jk_j}\}\to y_j$ дает орграф расчета. Если орграф содержит нетривиальные циклы, то ругаемся - это легко проверить. Остаются петли. И только петлям соответствуют допустимые формулы вида $y=f(y)$. Для того, чтобы не было реальной циклической ссылки, надо чтобы $y\in X\cap Y$, т.е. $y_{new}=f(y_{old})$. И все. Т.е. я в итоге просто проверяю, что в формуле расчета нет других невычисленных переменных, а если есть та же самая, я подставляю старое значение. $X$ в итоге - это множество вершин с петлями в объединении со множеством вершин, в которых нет входящих дуг, отличных от петель, т.е. функция от $Y$.
Есть другие мелкие проблемы, типа клиент может написать формулу $y=y+1$ и выполнять вычисление много раз и потом говорить мне, что это моя ошибка. Конечно, в общем случае проверить идемпотентность $f$ не представляется возможным, но на практике я с этим разберусь малой кровью.

Навряд ли я написал точно и понятно. Просто если вдруг кому-то понадобится, постараюсь объяснить максимально подробно.