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 <merk...@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 <bl...@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.s...@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 <bl...@cs.pdx.edu> >>> wrote: >>>> >>>> Does anyone know of a BDD — that’s Binary Decision Diagram — package >>>> written in Smalltalk? >>>> >>>> Andrew >>>> >>>> >>> >> >
