символическое вычисление - PullRequest
Новая
       2

символическое вычисление

9 голосов
/ 21 апреля 2011

Моя проблема: манипулирование символическими выражениями.

Символическое выражение строится, начиная с целочисленных констант и переменных, с помощью таких операторов, как +, -, *, /, min, max.Точнее, я бы представлял выражение следующим образом (код Caml): 

type sym_expr_t = 
  | PlusInf
  | MinusInf
  | Const of int
  | Var of var_t
  | Add of sym_expr_t * sym_expr_t
  | Sub of sym_expr_t * sym_expr_t
  | Mul of sym_expr_t * sym_expr_t
  | Div of sym_expr_t * sym_expr_t
  | Min of sym_expr_t * sym_expr_t
  | Max of sym_expr_t * sym_expr_t

Я представляю это для выполнения полезных и эффективных вычислений (например, a + b - a = 0 или a + 1> а) Мне нужно иметь какую-то нормальную форму и оперировать ею.Представленное выше представление, вероятно, не будет работать слишком хорошо.

Может кто-нибудь указать мне, как я должен подходить к этому?Мне не нужен код.Это можно легко написать, если я знаю, как.Ссылки на статьи, которые представляют представления для нормальных форм и / или алгоритмы для построения / упрощения / сравнения, также помогли бы.

Кроме того, если вы знаете о библиотеке Ocaml, которая делает это, сообщите мне.

Ответы [ 2 ]

4 голосов
/ 21 апреля 2011

Если вы пропустите Min и Max, нормальные формы будут просты: они являются элементами поля дробей ваших переменных, я имею в виду P[Vars]/Q[Vars], где P, Q - полиномы. Для Мин и Макса я не знаю; Я полагаю, что самый простой способ - рассмотреть их как тесты if / then / else и заставить их всплывать в верхней части ваших выражений (дублируя материал в процессе), например, P(Max(Q,R)) будет переписан в P(if Q>R then Q else R), а затем в if Q>R then P(Q) else P(R).

Я знаю два разных способа найти нормальные формы для ваших выражений expr:

  • Определите правила перезаписи expr -> expr, которые соответствуют вашей интуиции, и покажите, что они нормализуются. Это можно сделать, направив уравнения, которые, как вы знаете, верны: из Add(a,Add(b,c)) = Add(Add(a,b),c) вы получите либо Add(a,Add(b,c)) -> Add(Add(a,b),c), либо наоборот. Но тогда у вас есть система уравнений, для которой вам нужно показать Черч-Россер и нормализацию; грязное дело действительно.

  • Используйте более семантический подход для предоставления «семантики» ваших значений: элемент в expr действительно является обозначением для математического объекта, который живет в типе sem. Найдите подходящее (уникальное) представление для объектов sem, затем функцию оценки expr -> sem, и, наконец, (если вы хотите, но вам не нужно, например, для проверки на равенство) определение sem -> expr. Композиция обоих преобразований, естественно, даст вам процедуру нормализации, не беспокоясь, например, о направлении перезаписи Add (произвольный выбор естественным образом возникнет из вашей функции reification). Например, для полиномиальных дробей семантическое пространство будет выглядеть примерно так:

. 

  type sem = poly * poly
  and poly = (multiplicity * var * degree) list
  and multiplicity = int
  and degree = int

Конечно, это не всегда так просто. Я не понимаю, правильно знаю, какое представление дают семантическому пространству с функциями Min и Max.

Редактировать: Что касается внешних библиотек, я не знаю ни одной, и я не уверен, что есть. Возможно, вам следует поискать привязки к другому программному обеспечению символической алгебры, но я не слышал об этом (несколько лет назад был летний проект на Джейн-стрит, но я не уверен, что был произведен какой-либо результат).
Если вам это нужно для производственного приложения, возможно, вам следует рассмотреть возможность написания привязки самостоятельно, например. Мудрец или Максима. Я не знаю, на что это будет похоже.

3 голосов
/ 21 апреля 2011

Обычный подход к такой проблеме:

  1. Начните со строки, такой как "a + 1 > a"
  2. Пройдите через лексер и разделите ваш ввод на отдельные токены: [Variable('a'); Plus; Number(1); GreaterThan; Variable('a')]
  3. Разобрать токены в синтаксическое дерево (что у вас сейчас). Здесь вы используете правила приоритета операторов: Max( Add( Var('a'), Const(1)), Var('a'))

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

    let eval_expr expr = match expr with
    | Number n -> n
    | Add a b -> (eval_expr a) + (eval_expr b)
    ...

Извините за синтаксис, я давно не использовал Ocaml.

Что касается библиотек, я не помню ни одной из них, но наверняка есть хорошие, легко доступные - это та задача, которую любит выполнять сообщество FP.

...