Optimal boolean expressions evaluation

Discussion of Common Lisp

Optimal boolean expressions evaluation

Postby makia » Tue Oct 13, 2009 10:02 am

What is known tactic for creating optimal boolean query expressions, for example if i have this query:
(OR (AND (= A B) (= C D))
(AND (= A B) (= Y P)))

faster evaluation would be:
(AND (= A B)
(OR (= C D) (= Y P)))
, this is not only lisp related but it's natural to solve this in lisp form
Thanks
makia
 
Posts: 25
Joined: Tue Jul 22, 2008 2:37 am

Re: Optimal boolean expressions evaluation

Postby makia » Tue Oct 13, 2009 10:08 am

btw. i posted this here because it's part of something i'm doing in Common Lisp and i'm interested in CL solutions (also it's natural to do this in sexp) .... wiki link can help too :)
makia
 
Posts: 25
Joined: Tue Jul 22, 2008 2:37 am

Re: Optimal boolean expressions evaluation

Postby Ramarren » Tue Oct 13, 2009 10:52 am

I don't know that much about prepositional logic, but this seems to be an NP-hard problem. Some relevant Wikipedia links: Circuit minimization (note that digital circuits are equivalent to boolean expressions), Karnaugh maps,Quine–McCluskey algorithm, Espresso heuristic logic minimizer.

I haven't seen any code for doing that in CL, but I haven't looked. It is quite likely that there might be some in some older archives like CMU Common Lisp Repository.
Ramarren
 
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland

Re: Optimal boolean expressions evaluation

Postby nuntius » Tue Oct 13, 2009 2:03 pm

A couple things to watch for:
- Short-circuiting operators (AND fails after first nil, OR passes after first t) may change the optimal result, especially if you can accurately predict truth frequencies.
- If short-circuiting operators protect mutating tests, refactoring may be impossible.
User avatar
nuntius
 
Posts: 497
Joined: Sat Aug 09, 2008 10:44 am
Location: Burlington, MA

Re: Optimal boolean expressions evaluation

Postby Kohath » Tue Oct 13, 2009 9:03 pm

This makes me want to be able to tell if a particular form is a mutating/side-effect one or not. I suppose it would be kinda cool to have a compiler macro for this kind of thing.
User avatar
Kohath
 
Posts: 50
Joined: Mon Jul 07, 2008 8:06 pm
Location: Brisbane, Queensland, Australia

Re: Optimal boolean expressions evaluation

Postby makia » Tue Oct 13, 2009 11:31 pm

of course there is no mutating tests here, we can simplify this:
Code: Select all
(OR (AND (= A B) (= C D))
    (AND (= A B) (= Y P)))


to
Code: Select all
(OR (AND a b)
    (AND a c))


and this should lead to:

Code: Select all
(AND a (OR b c))
makia
 
Posts: 25
Joined: Tue Jul 22, 2008 2:37 am

Re: Optimal boolean expressions evaluation

Postby gugamilare » Wed Oct 14, 2009 6:48 am

This kind of problem reminds me the type inference made by SBCL.

Internally, SBCL transforms a type specifier (like 'array or 'string) into an object. The function that retrieves such object is sb-kernel:specifier-type. The function that gives the specifier back is sb-kernel:type-specifier. Types like '(and string array) and '(or integer character) are constructed using sb-kernel:type-intersection and sb-kernel:type-union.

I believe this is much similar to what you want to do, since SBCL can simplify some nested type unions / intersections similarly to the simplification of boolean expressions. You may refer to these functions (using M-. using Slime) and see if it helps.

Code: Select all
cl-user> (sb-kernel:type-specifier
          (sb-kernel:type-intersection (sb-kernel:type-union (sb-kernel:specifier-type 'array)
                                                             (sb-kernel:specifier-type 'fixnum))
                                       (sb-kernel:type-union (sb-kernel:specifier-type 'array)
                                                             (sb-kernel:specifier-type 'integer))))
(or array fixnum)
cl-user> (sb-kernel:type-specifier
          (sb-kernel:type-union (sb-kernel:type-intersection (sb-kernel:specifier-type '(integer -2 1))
                                                             (sb-kernel:specifier-type '(integer -1 2)))
                                (sb-kernel:type-intersection (sb-kernel:specifier-type '(integer -2 1))
                                                             (sb-kernel:specifier-type '(integer 0 3)))))
(integer -1 1)
cl-user> (sb-kernel:type-specifier
          (sb-kernel:type-intersection (sb-kernel:type-union (sb-kernel:specifier-type 'character)
                                                             (sb-kernel:specifier-type 'fixnum))
                                       (sb-kernel:type-union (sb-kernel:specifier-type 'character)
                                                             (sb-kernel:specifier-type 'array))))
character
cl-user> (sb-kernel:type-specifier
          (sb-kernel:type-intersection (sb-kernel:type-union (sb-kernel:specifier-type 'character)
                                                             (sb-kernel:specifier-type '(satisfies foo)))
                                       (sb-kernel:type-union (sb-kernel:specifier-type 'character)
                                                             (sb-kernel:specifier-type '(satisfies bar)))))
(or character (and (satisfies bar) (satisfies foo)))


Unfortunately, it seems not to be able to simplify the following expression, which is what you would want it to do:

Code: Select all
cl-user> (sb-kernel:type-specifier
          (sb-kernel:type-union (sb-kernel:type-intersection (sb-kernel:specifier-type 'fixnum)
                                                             (sb-kernel:specifier-type '(satisfies foo)))
                                (sb-kernel:type-intersection (sb-kernel:specifier-type 'fixnum)
                                                             (sb-kernel:specifier-type '(satisfies bar)))))
(or (and fixnum (satisfies foo)) (and fixnum (satisfies bar)))
;;; it would be better if it was (and fixnum (or (satisfies foo) (satisfies bar)))
;;; like in your example
gugamilare
 
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil


Return to Common Lisp

Who is online

Users browsing this forum: Bing [Bot] and 1 guest