I think that andrew would like to improve smacc when parsing inputs containing utf-8 characters.
On Sat, Oct 28, 2017 at 1:46 PM, Steffen Märcker <merk...@web.de> wrote: > I see. What is the task in detail? Are some of the set fixed or known in > advance? What's the argument against a bitset-based solution? > > Cheers, Steffen > > > > Am 27. Oktober 2017 19:10:35 MESZ schrieb Stephane Ducasse > <stepharo.s...@gmail.com>: >> >> 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 >>>>> >>>>> >>>>> >>>>> >>>> >>> >> >
