From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-0.3 required=5.0 tests=BAYES_00,
	REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4
Path: 
 eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!news.eternal-september.org!mx02.eternal-september.org!feeder.eternal-september.org!aioe.org!.POSTED!not-for-mail
From: "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>
Newsgroups: comp.lang.ada
Subject: Re: BDD package in Ada.
Date: Wed, 8 Apr 2015 08:38:10 +0200
Organization: cbb software GmbH
Message-ID: <1miph3v72f4y2$.1u76w2ujg74zf$.dlg@40tude.net>
References: <44b2e375-8993-4a7e-b81a-6a7b512d2e3e@googlegroups.com>
Reply-To: mailbox@dmitry-kazakov.de
NNTP-Posting-Host: w2sqUGEBZqsVBYNL7Ky3Kg.user.speranza.aioe.org
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
X-Complaints-To: abuse@aioe.org
User-Agent: 40tude_Dialog/2.0.15.1
X-Notice: Filtered by postfilter v. 0.8.2
Xref: news.eternal-september.org comp.lang.ada:25460
Date: 2015-04-08T08:38:10+02:00
List-Id: <comp.lang.ada>

On Tue, 7 Apr 2015 13:35:53 -0700 (PDT), Vincent DIEMUNSCH wrote:

> Binary Decisions Diagram [1] is a key technology in computer science, for
> the verification of software and hardware designs.  Donald Knuth calls
> BDDs "one of the only really fundamental data structures that came out in
> the last twenty-five years" and mentions that Bryant's 1986 paper was for
> some time one of the most-cited papers in computer science.

I would not call it "fundamental". It is simply a tree with factored out
subtrees. Need not to be binary, BTW.

IMO, factoring out similar subtrees is merely a technique to save memory
and reduce overheard of some computations over the graph nodes. Sometimes
it pays off, sometimes it does not.

As for decision trees, they were known and used in AI for I don't know how
long, ever.

> There are many BDD libraries in C/C++, there are libraries in Lisp,
> Python, Java, Lua, OCaml, Prolog... all available on the Internet [2], but
> I couldn't find one in Ada. I am pretty sure that there must be excellent
> BDD libraries in Ada used in the Defense Industry, but it seems that no
> one is public.

Of course there exist Ada implementations. I have one in Ada

http://www.dmitry-kazakov.de/ada/fuzzy_ml_api.htm#Fuzzy.Graph

with binary and general case nodes.

> So I hesitate between developping a binding to an existing C library, and
> thus having access to the best and fastest implementations, or developping
> one myself, but the result might be less efficient, although easier to use
> from Ada and more portable.
> 
> Any piece of advice to give me? Would some of you be interested in using
> it? In contributing to the development as an Open Source? 

I don't think structures like trees and directed graphs could be packed in
a library. Each application of graphs is very specific. The abstraction
level is too low to make it a decent container. Memory management is always
different. Operations are always different. The impact of the
representation is so huge that different application almost always require
a different implementation.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de