Please add CL-CUDD

[guicho271828]

https://github.com/guicho271828/CL-CUDD

Common lisp bindings to CUDD (Colorado University Decision Diagram library).

What is BDDs and CUDD?

BDDs (Binary Decision Diagrams) are awesome datastructures that can compactly represent exponentially large number of datasets, as well as allowing the direct computation over the compressed representation, i.e., you can take the sum/product/union/intersection of the datasets without decompressing the data!

CUDD is a famous C implementation of BDDs and its relatives: Multi-Terminal Binary Decision Diagrams (MTBDDs, also known as Algebraic DD / ADDs) and Zero-suppressed Decision Diagrams.

Related work

trivialib.bdd is another common lisp library for BDDs, which is entirely written in lisp. CUDD is more on the state-of-the-art side.

[quicklisp]

I don't think this should perform a git checkout and build of a C library to work. Can you please omit that step?

[guicho271828]

it is not checking out git, just pulling the tarball by curl. Im guessing curl is commonly available on many systems.
I also don't like the idea of requiring the users to manually install a library, globally, by themselves.

Well, cudd_rust and hs-cudd have a local copy of cudd. Maybe I can directly include it, but the compilation is still necessary.

[quicklisp]

Please leave the foreign library management to the user, instead.

[guicho271828]

Would you kindly tell me about the motivation for that policy.
Note that CUDD package is officially available only on Fedora.

I understand your policy below, but CUDD is a state-of-the-art with a clean codebase and a very standard automake-based build system. It doesn't do complicated things: download, configure, make, and that's all.

There are a few exceptions: projects that require complicated or obscure foreign libraries, projects that can only be downloaded via some ad-laden link system like SourceForge, projects that use CVS, and anything else that makes it difficult for me to fetch or build the project.

By the way, I used the same scheme for cl-sat.minisat and cl-sat.glucose .

Alternatively, I can ask the user (when the repl/debugger is available) whether to install a library from the internet or use the preinstalled cudd.so file. Does this sound more reasonable?

[guicho271828]

As you see, this is tested on both Linux and OSX, and on SBCL, CCL, ECL.
https://travis-ci.org/guicho271828/CL-CUDD

[quicklisp]

In general, I simply don't like the idea of Quicklisp-provided projects pulling in additional stuff that must be built with some other development environment present. It reminds me of the unpleasant situation where, in the name of user convenience, projects would bundle a number of other projects in with their own sources. I appreciate the convenience, but it seems to me like it is an invitation for future trouble.

[guicho271828]

I agree with your policy, especially in prohibiting git submodules. I agree that it does not work especially for common lisp. Part of the reason is that the packages and ASDF systems are global in a lisp image and there is a possible conflicts in the namespace if multiple libraries bundle the different version of a same library. It becomes out of control.

However, things are different in foreign libraries. I believe bundling a pure C library does no harm to lisp ecosystem, and is better than forcing the global installation, especially when we consider the case that different CFFI libraries require the different versions of the same C library. It is no problem, since CFFI supports loading multiple .so images with the same C function symbol by storing them in the different namespace.

[quicklisp]

This was added in the latest Quicklisp dist update.

[binghe]

@guicho271828, I like the original version of CL-CUDD (after @rpgoldman [1]), because building CL-CUDD is not always successful given the default compiler and various characters of operating systems. Your automated CL-CUDD building scripts doesn't work on Mac OS X 10.11, while I can easily install it (version 2.5.0) from MacPorts. And on Mac OS X, dynamic libraries have *.dylib extensions, and LD_LIBRARY_PATH becomes DYLD_LIBRARY_PATH. Your scripts cannot support well all these details, so please just leave them to end users as suggested by Zach.

And I hate the way you put numbers before Lisp file names, e.g. 1-0-2-translators.lisp. Can you share the book in which you've learnt about such naming conventions? I want to know the author and send him an email.

[1] https://github.com/rpgoldman/CL-CUDD

[guicho271828]

the version 2.5 on ports is outdated. cl-cudd uses the latest version 3.0. Older versions misses some critical functions.

[guicho271828]

And on Mac OS X, dynamic libraries have *.dylib extensions, and LD_LIBRARY_PATH becomes DYLD_LIBRARY_PATH. Your scripts cannot support well all these details

Your assessment is wrong. I did not write the script for building CUDD. Makefile in my repository just calls the configure script in the CUDD and invokes make in that repository. If anything happens, then it is due to the CUDD's build script. However, looking into the configure script, it handles OSX-specific changes correctly.

I knew this. In fact, configure and Makefile are generated by Autotools. Autotools is a state of the art for writing OS-independent build scripts. It's sole purpose is to absorb such differences as ld_library_path/dyld_library_path between OSes and achieve a robust script. It should also build on BSD or Soralis. Autotools is not a product of a random hacker but a quite matured, stable project, backed by GNU and a large user base. I wasn't confident in my approach without a reason.

I tested CL-CUDD for OSX on Travis-CI and it builds fine. I believe there is just a minor problem in your environment that is failing your build, and I can help you out, and improve the documentation. For example, I would like to know what exactly happened in your terminal/emacs/vim when you loaded the library. Maybe you haven't install autotools in the first place or I was not listing some dependency (Dependencies are unavoidable).

It is not reasonable to go straight up complaining here rather than filing an issue in the repository. If I seem inactive or was inresponsive on github, that would be my fault, but I am active on github. And finally, if you need CUDD2.5 and rpgoldman/cl-cudd, you can install it locally (It was not on quicklisp when I submitted, anyways.)

[guicho271828]

By the way, the official website no longer provides CUDD2.5. This means that, while the Ports users can install CUDD2.5, people using other OSes should obtain CUDD2.5 source code from an unreliable resource. Are you sure it does not contain a Trojan? At the moment, rpgoldman/CL-CUDD is not useful to everyone because people can't install CUDD2.5 even manually.