Part of the reasoning is that by writing JVM bytecode, the differences between the various JVM languages become largely irrelevant, though in some ways it becomes slightly less convenient if calling, for example, Scala or Clojure code from Pharo. The other is inherent JVM limitations and discrepancies between Java as a semantic spec and various specific implementations as dynamic systems, particularly since the latter differ both by Java version and by which frameworks might be in use, and dynamically create further discrepancies contingently based not only on the above, but also specifics of the system and its current state. Cheers Andrew Sent from Mail for Windows 10 From: Stephane Ducasse Sent: Saturday, October 28, 2017 10:06 AM To: Any question about pharo is welcome Subject: Re: [Pharo-users] Binary Decision Diagram Package in Smalltalk 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 <merkste@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.self@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 <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