It was for test inclusion of UTF-8 characters so we do not want to rely on external libraries. On Fri, Oct 27, 2017 at 1:54 PM, Steffen Märcker <merkste@web.de> wrote:
Dear Andrew,
I didn't find time to answer earlier. Some time ago, I was looking for a (MT)BDD package in ST as well. I didn't found one. So the only two options left are
1) implementing a new BDD lib in ST and 2) doing FFI to some existing lib, e.g. CUDD, Sylvan, Jinc
I'd prefer 2) since the existing libraries are feature-rich and highly optimized - which took quite some time. As a bonus, a solution could potentially switch between those backends. The biggest hurdle, in my option, is memory management, since most libs use some sort of reference counting. And you do not want to end up with nightmarish dozens of ref(bddNode) deref(bddNode) in your application code (like the probabilistic model checker PRISM does). This introduces hard to track bugs easily. However, I have an idea in mind how to tackle this but I didn't found the time to put it into code yet.
May I ask, which sort of application do you have in mind?
Best, Steffen
Am .10.2017, 07:54 Uhr, schrieb Prof. Andrew P. Black <black@cs.pdx.edu>:
Thanks for the responses so far. I see that I need to clarify my enquiry.
B-Trees and BDDs are not the same. BDDs are an efficient and compact representations for Boolean functions, sometimes used in SAT-solvers and electronics design. The key idea is that since the output must be 0 or 1, you can represent any Boolean function as a tree whose depth is the same as the number of bits in the input.
To make the tree small and efficient, though, you need to eliminate any node whose two children are the same, and to share subtrees, so that you really get a DAG, not a tree. The full name for these efficient compressed trees is âReduced Order Binary Decision Diagramsâ, or ROBDDs. I was hoping that someone else had implemented the algorithms necessary to build this representation.
Because sets can be considered to be Booleans functions (true => argument is in the set), you can use ROBDDs to efficiently represent large sets.
To be clear, despite the word âdiagramâ in the name, one is not normally interested in drawing the BDD â except in the documentation for the package ;-). Normally, BDDs they are used to represent sets, or functions, where the drawing would be hopelessly large.
The BuDDy package (http://buddy.sourceforge.net/manual/main.html) is an example of what Iâm looking for, but unfortunately itâs in C++.
Andrew
On 25 Oct 2017, at 21:39 , Stephane Ducasse <stepharo.self@gmail.com> wrote:
Hi andrew
I think that Avi did a package about BDD (but I thought it was special binary trees) so this is probably the same. Did you check on Squeaksource? http://www.squeaksource.com/BTree.html If this is what you are looking for I can help porting it to Pharo.
Stef
On Wed, Oct 25, 2017 at 9:02 PM, Prof. Andrew P. Black <black@cs.pdx.edu> wrote:
Does anyone know of a BDD â thatâs Binary Decision Diagram â package written in Smalltalk?
Andrew