Tools for constraint based change propagation in Common Lisp


This library provides various tools that help dealing with constraint based change propagation in Lisp programs. One such tool is computed-class which is a metaclass for CLOS classes that support per instance lazy computation of slot values while keeping track of dependencies and managing invalidation of such computed results transparently. The engine behind this is fully integrated with CLOS but it is also independent from it. It makes it possible to use computed local variables that can even be captured by lambda's (see clet) and also to explicitly handle the computed-state structs (the cells) as first-class citizens.

(define-computed-universe compute-as :name "Default computed-class-test universe")

(deftest compute3 ()
  (let* ((object-1 (make-instance 'computed-test
                                  :slot-b (compute-as (1+ (slot-a-of -self-)))))
         (object-2 (make-instance 'computed-test
                                  :slot-a (compute-as (+ (slot-a-of object-1) (slot-b-of object-1)))
                                  :slot-b (compute-as (1+ (slot-a-of -self-))))))
    (signals unbound-slot (slot-a-of object-1))
    (setf (slot-a-of object-1) 0)
    (is (= 0 (slot-a-of object-1)))
    (is (= 2 (slot-b-of object-2)))
    (setf (slot-a-of object-1) 2)
    (setf (slot-b-of object-2) (compute-as (* 2 (slot-a-of -self-))))
    (is (= 5 (slot-a-of object-2)))
    (is (= 10 (slot-b-of object-2)))))

;; please note that the fake clet variables can even be captured by lambda's (actually that's happening in (compute-as (1+ a)))
(deftest clet4 ()
  (clet ((a (compute-as 2))
         (object (make-instance 'computed-test
                                :slot-a (compute-as (1+ a))
                                :slot-b (compute-as (1+ (slot-a-of -self-))))))
    (is (= a 2))
    (clet ((b (compute-as (+ a (slot-b-of object)))))
      (is (= b 6))
      (is (eq (cs-variable b-state) 'b))
      (is (= (slot-a-of object) 3))
      (is (= (slot-b-of object) 4))
      (setf (slot-a-of object) 42)
      (is (= a 2))
      (is (= b 45))
      (is (= (slot-a-of object) 42))
      (is (= (slot-b-of object) 43)))))

See test.lisp for more examples and/or read the Cells docs.


This is an example use of computed class to solve sudoku games. The idea is to have the 81 solution elements connected in a way that expresses the constraints between them and let computed-class do the rest. A constraint for an element is that it cannot have a value equal to the selected value of any other element in the same row, column or block. See the 90 LOC source for more details, and here is a test run.


Mailing Lists

Project members

Attila Lendvai
Tamás Borbély
Levente Mészáros


You can browse the computed-class darcs repository or get the tree with

darcs get