LINUX.ORG.RU

Вычислитель нерекурсивных выражений по дереву


0

1

Хрен знает, как это называется, поэтому нагуглить не могу. Требуется помощь зала^WЛОРа.

Дан набор выражений для вычисления значений переменных через другие переменные. Абстрактный пример:

a := 3
b := 200
c := sqrt(b) * a
d := b + c

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

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

Это была первая часть балета. Теперь усложняем. Переменные организованы в дерево наборов. Выражения могут содержать ссылки на переменные родительского набора, а также операции свертки по значениям переменных в дочерних узлах. Абстрактный пример:

root [a := 4; b := 25; x := reduce_with_children(sum, x)]
  |
  +-> first_child [x := parent.a + 1]
  |
  +-> second_child [x := parent.b * 2]

В принципе, как это реализовывать — понятно. Но самостоятельно возиться очень не хочется.

Вопросы:

Как описанное называется по-умному?

Есть ли какие-то готовые библиотеки, реализующие это? Юзаться библиотека будет из Си. Язык описания выражений для библиотеки не принципиален.

Как описанное называется по-умному?

dataflow

baverman ★★★ ()

Может тебе надо что-то типа интерпретатора лиспа встроить?

DesertFox ()
Ответ на: комментарий от DesertFox

Да я вот сам уже задумываюсь на эту тему. Сейчас пока ковыряю Io на предмет, можно ли на её основе построить такой вычислитель. Похоже, что в ней нельзя получить в виде синтаксического дерева тело выражения — только строкой. Это пичалька.

Погуглил насчёт dataflow и incremental computing, нихрена полезного не нашел.

geekless ★★ ()
Ответ на: комментарий от geekless

Если решишься на лисп, то Guile очень легко встраивается в программы на C. Вот туториал, который даст представление как оно все интегрируется: http://www.gnu.org/software/guile/docs/guile-tut/tutorial.html

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

DesertFox ()

Первую часть я когда-то реализовал на C#, но там задача немного была другая: инкрементально определить вычислимость системы ОДУ. Иначе говоря, там появляются задержки по времени через обратные связи, поэтому вводится еще одна характеристика. Не знаю, пригодится тебе или нет: http://sourceforge.net/projects/mapsim/. Алгоритмы все мои. Так что, пользуйся на здоровье :)

dave ★★★★★ ()
Ответ на: комментарий от dave

Да, волновой инкрементальный вычислитель находится в CompUnit.

dave ★★★★★ ()
Ответ на: комментарий от DesertFox

Уф, так, реализация простейшего ленивого вычислителя (с отслеживанием зависимостей, но без коллбеков и деревьев) на Io заняла одну экранную страницу крупным шрифтом. :-D Метапрограммирование рулит, да. Вот только скорость работы меня наверняка не порадует.

В принципе, если еще чуток повозиться, можно сделать полноценную реализацию со всем фичами. В качестве прототипа сгодится. А потом и на Си можно переписать.

geekless ★★ ()

Может тебе просто mozart-oz нужен?

DonkeyHot ★★★★★ ()

Такой вычислитель пишется за пару часов.

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

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

Чтобы вычислить значения всех переменных мы просто вычисляем их значения. При начале вычисления мы устанавливаем флаг, что переменная вычисляется. Если в процессе вычисления нам попалась переменная с установленным флагом, то мы нашли цикл. Просто откатываемся и запоминаем, какие переменные попали в цикл.

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.