constraint programming

[Haris Bogdanovich]

Hi.

Can someone recommend a library for constraint programing ?

Thanks

[Pascal J. Bourguignon]

"Haris Bogdanovich" <fbogd...@xnet.hr> writes:

> Can someone recommend a library for constraint programing ?

I recently wrote this:

http://paste.lisp.org/display/125450

It'll be included in com.informatimago.common-lisp.cesarum soon.


The exported function is SOLVE-CONSTRAINTS:

(defun solve-constraints (edges propagate)
"
DO: Calls PROPAGATE on each edge until PROPAGATE returns NIL
for all arcs.
EDGES: A list of edges (from to).
The nodes FROM and EDGE must be comparable with EQL.
PROPAGATE: A function taking the nodes FROM and TO of an edge as argument,
and returning whether changes occured.
")



Here is an example of usage.


(defun compute-follow-sets (grammar)
"
PRE: The GRAMMAR must be normalized.
(ie. containly only SEQ rules)
RETURN: A hash-table containing the follow-set for each non-terminal
of the grammar.
"
(let ((base-constraints '())
(recursive-constraints '()))
(flet ((first-set (item) (first-set grammar item)))
;; {$EOF$} ⊂ (follow-set start)
(push `(subset (set ,*eof-symbol*) (follow-set ,(grammar-start grammar)))
base-constraints)
(dolist (rule (grammar-rules grammar))
(destructuring-bind (non-terminal (seq symbols action)) rule
(declare (ignore seq action))
(when symbols
(loop
:for (n . beta) :on symbols
:do (when (non-terminal-p grammar n)
(let ((m (first-set beta)))
(when beta
;; (first-set beta)∖{ε} ⊂ (follow-set n)
(push `(subset (set ,@m) (follow-set ,n)) base-constraints))
(when (and (not (eql n non-terminal)) (nullablep grammar beta))
;; (follow-set non-terminal) ⊂ (follow-set n)
(push (list non-terminal n) recursive-constraints)))))))))
(let ((follow-sets (make-hash-table)))
;; initialize the follow-sets:
(dolist (non-terminal (grammar-all-non-terminals grammar))
(setf (gethash non-terminal follow-sets) '()))

;; apply the base-constraints:
(loop
:for constraint :in base-constraints
:do (destructuring-bind (subset (set &rest elements) (follow-set non-terminal)) constraint
(declare (ignore subset set follow-set))
(setf (gethash non-terminal follow-sets)
(union (gethash non-terminal follow-sets)
(remove nil elements)))))

;; resolve the recursive constraints:
(solve-constraints recursive-constraints
(lambda (subset superset)
(let ((old-cardinal (length (gethash superset follow-sets))))
(setf (gethash superset follow-sets)
(union (gethash subset follow-sets)
(gethash superset follow-sets)))
(/= (length (gethash superset follow-sets)) old-cardinal))))
follow-sets)))

--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.

[Captain Obvious]

HB> Can someone recommend a library for constraint programing ?

Screamer isn't good enough?

[John Thingstad]

screamer comes to mind
http://cl-user.net/asp/oe0W/sdataQGn9tSxtNwMhDQ3jQRpX8yBX8yBXnMq=/sdataQu3F$sSHnB==

[Haris Bogdanovich]

> Screamer isn't good enough?

I asked before that I can't find Screamer mailing list ?

[Raffael Cavallaro]

On 2011-10-24 10:48:02 +0000, Haris Bogdanovich said:

> I asked before that I can't find Screamer mailing list ?

Using the magical google incantaion "screamer common lisp," the first
hit is the common lisp directory listing for screamer which points to:

offical download:
<https://github.com/nikodemus/screamer>

screamer maintainer page:
<http://nikodemus.github.com/screamer/>

google group for discussion linked from that page:

<http://groups.google.com/group/screamer/>

hth

warmest regards,

Ralph

--
Raffael Cavallaro

[Haris Bogdanovich]

> <http://groups.google.com/group/screamer/>

Sorry. I never used google groups. I was expecting a mailing list.
Thanks