cells-doc.txt

Cells tutorial


1 Introduction
    1.1 What's cells?
    1.2 How could it improve your programs?
2 Installation
3 Our first cells program
    3.1 The program
    3.2 The program line-by-line
4 The family system
5 Defining an observer
6 Lazy cells
7 Drifters
8 Cyclic dependencies
9 Synapses
    9.1 Built-in synapses
    9.2 Defining your own
10 Example: playing sudoku
11 Functions & macros reference
    11.1 Main
    11.2 Family models
    11.3 Synapses
    11.4 Misc
12 Other resources
13 Introduction
    13.1 Where's the GUI?
    13.2 Cells-gtk
14 Installation



Cells

1 Introduction

1.1 What's cells?

Cells is a Common Lisp library that extends the 
language, and in particular its object system, to let 
you write dataflow-driven programs. What does this 
mean? This means that the flow of control of the 
program depends no more on the sequence of 
function/method calls, but on the data. Cells lets you 
specify the dependence beetwen different slotsA slot is the Common Lisp equivalent of a class 
instance variable in other languages
 in a family of classes. Once these constraints have 
been registered, the cells system will take care of 
them, and will recalculate a value when some data on 
which it depends has changed. As a consequence, the 
programmer just has to tell the system the relationship 
between the data, the burden of maintaining them true 
is handled automatically by cells. 

1.2 How could it improve your programs?

Cells may not be the panacea of programming, but it 
sure helps a lot in contexts where keeping a set of 
values consistent is crucial. A particular set of 
applications where this is important are graphical applicationsSee the cells-gtk project: [http://common-lisp.net/project/cells-gtk]
, where you need to maintain consistency between what 
the user sees and the real values held by the program 
in its internal data structures. An example is the 
state of the 'Cut' menu entry in an editor: it is 
usually clickable when the user has selected a piece of 
text and not clickable in all the other cases. In a 
normal application, to achieve this behavior you would 
need to track all the methods and all the user actions 
that could modify the region of text currently being 
selected, and add activate/disactivate calls in all 
those places to keep the menu entry in a consistent 
state. With cells, you just need to tell the system 
that the state of the menu depends on the length of the 
current text selection: if the length is 0 then the 
state is 'deactivated', else it is 'activated'. Now you 
can safely work on the rest of the application ignoring 
the state of the menu: it will be automatically 
recalculated every time the length of the current 
selection varies. Moreover, everything relating to the 
menu entry is placed near its definition, and not 
scattered across different functions/methods.

2 Installation

The installation is quite simple once you have a 
working Common Lisp system. Here I will assume that 
you've got a working copy of SBCL[http://www.sbcl.org||SBCL]. First of all, 
download cells: you can get the latest version at [http://common-lisp.net/cgi-bin/viewcvs.cgi/cells/?root=cells]. 
Then enter the directory ~/.sbcl/site and unpack cells:

$ cd ~/.sbcl/site

$ tar -zxvf ~/cells.tar.gz

Now be sure that ASDF will be able to find it:

$ cd ~/.sbcl/systems

$ for a in `find ~/.sbcl/site/cells/ -name "*.asdf"` \

  do ln -sf $a . \

done

After that, start SBCL and evaluate the following expressions:

> (require :asdf)



NIL

> (asdf:oos 'asdf:load-op :cells)

(some output will follow)

If everything went right cells should be up and running.

3 Our first cells program

3.1 The program

Write the following piece of code in a file named 
hello-cells.lisp:

(defmodel hello-cells ()

  ((num :accessor num :initarg :num :initform (c-in 0))

   (square-num :accessor square-num 

               :initform (c? (* (num self) (num self))))))



(defun hello ()

  (let ((h (make-instance 'hello-cells)))

    (dolist (n '(10 20 30 40 50 60 60))

      (setf (num h) n)

      (format t "num is ~a and square-num is ~a~%" (num 
h) (square-num h)))))

Now start the SBCL interpreter in the same directory 
and evaluate the following:

> (asdf:oos 'asdf:load-op :cells)

...

> (use-package :cells)

T

> (load "hello-cells.lisp")

...

T

> (hello)

num is 10 and square-num is 100

num is 20 and square-num is 400

num is 30 and square-num is 900

num is 40 and square-num is 1600

num is 50 and square-num is 2500

num is 60 and square-num is 3600

num is 60 and square-num is 3600

NIL

What happens within the function 'hello'? First, an 
object of type hello-cells is created. After that the 
program iterates over the contents of the list '(10 20 
30 40 50 60 60), and every number is used to set the 
num slot of the object h. Then the num slot is printed 
together with the slot square-num. The printed value of 
the slot num gives us no surprise: it has the value we 
gave it. This doesn't hold for the slot square-num, 
though: we never gave it a value within the loop, but 
it always holds the square of the slot num! This is 
just cells working for us: we told the system that the relation

 num*num=squarenum 

must hold, and every time num changes, the expression 
(* (num self) (num self)) is re-evaluated. Note that 
the relation isn't a mathematical equation: you can't 
change square-num and expect to find its square root in num.

3.2 The program line-by-line

Lets now analyze the program. The very first line uses 
the construct defmodel:

(defmodel hello-cells ()

defmodel is very similar to defclass and everything 
valid in a defclass construct is valid within defmodeldefmodel is a layer built on top of defclass. 
The main difference is that all the slots defined 
within it will be tracked by cells, except slots that 
are explicitly declared to be ignored by the system by 
specifying :cell nil in the definition.

((num :accessor num :initarg :num :initform (c-in 0))

Here we define the slot num as we would do within a 
standard class declaration. The difference is in its 
initialization expression: instead of the number 0 we 
have (c-in 0). Why? (c-in <expr>) is a construct that 
tells cells that the value of num may be changed, so 
whenever it does change a re-evaluation of all the 
slots that depend on it must be triggered. If we did 
just write 0 instead of (c-in 0) a runtime error would 
have been raised during the execution of (setf (num h) 
...). So, when a slot is writable it must be signalled 
to cells with the (c-in ...) construct. This is 
necessary to let cells do some optimizations like 
avoiding to remember dependencies on slots that will 
never change. Slots initialized with c-in are usually 
called "input cells".

(square-num :accessor square-num 

            :initform (c? (* (num self) (num self))))))

Now we define the slot square-num. There are two things 
to note here: (c? <expr>) and 'self'.The first is a 
construct that says: "To calculate the value of 
square-num, evaluate the expression <expr>". Within (c? 
...) the variable self is bound to the object itself. 
(c? ...) automatically tracks any dependency, in this 
case the dependency on the value of num: when num 
changes, (* (num self) (num self)) will be 
re-evaluated. Slots initialized with c? are called "
ruled cells".

(let ((h (make-instance 'hello-cells)))

Here we use the function (make-instance <model-name> 
args*), to create an object of type <model-name>, in 
this case hello-cells, as we would do to instantiate a 
normal class. You could specify an initial value for 
num now: 

(let ((h (make-instance 'hello-cells :num (c-in 50))))

Note that you must repeat the (c-in ...) construct. 
This is because the behavior of the slot (input cell, 
constant, ruled cell) is decided on a per instance 
basis, not on a per class basis. This means that, in 
our example, we could have two objects of type 
hello-cells, one where the slot num is settable and one 
where it is has a constant value. When an object is 
created, all the values of its slots are computed for 
the first time, in this case the expression (* (num 
self) (num self)) is evaluated and the value given to 
the slot square-num.

(setf (num h) n)

This expression sets the value of the slot num to n. 
This is when cells comes into action: square-num 
depends on num, so (* (num self) (num self)) is 
re-evaluated after n has changed.

(format t "num is ~a and square-num is ~a~%" (num h) 
(square-num h))

Finally, we print the values of the two slots and 
discover that the value of square-num is correctly the 
square of num.

As a side note, you can reset the cells system by 
calling (cell-reset):

> (cells-reset)

NIL

This could be necessary after an error has corrupted 
the system and cells doesn't seem to work correctly 
anymore. It's also a good practice to reset the system 
before running code that uses cells.

4 The family system

Objects whose type have been defined using defmodel can 
be organized in families. A family is a tree of model 
instances (not of model classes!) that can reference 
each other using the functions (fm-other ...), (fm^ 
...) and others. You can specify the family tree at 
object creation time passing a list of children to the 
argument :kids. Alternatively, you can access the slot 
.kids (automatically created by defmodel) and set it at 
runtime to change the family components. .kids is, by 
default, a slot of type c-in, and you can access it 
through the method (kids object). You can change the 
.kids slot to be of a type other than c-in as you could 
do with any other slot. To access the members of a 
family you can give them a name with the argument 
:md-name and then reference them by their name. Another 
way to access them is through their type: you could 
say, for example, "give me all the successors of type my-type"
. To use these features your models must inherit from 
the model 'family'. Models that inherit from family 
have also a .value slot associated, which you can 
access through the method (value self)In older releases of cells you had to use (md-value 
self) instead
. The following example shows some of these things in action:

(defmodel node (family)

  ((val :initform (c-in nil) :initarg :val)))



(defun math-op-family ()

  (let ((root

         (make-instance

          'node

          :val (c? (apply #'+ (mapcar #'val (kids self))))

          :kids

          (c?

            (the-kids

              (make-kid 'node :md-name :n5 :val (c-in 5))

              (make-kid

               'node

               :val (c? (apply #'* (mapcar #'val (kids self))))

               :kids

               (c?

                 (the-kids

                  (make-kid 'node :md-name :n7 :val 
(c-in 7))

                  (make-kid 'node :md-name :n9 :val 
(c-in 9))))))))))   

    (format t "value of the tree is ~a~%" (val root))

    (setf (val (fm-other :n7 :starting root)) 10)

    (format t "new value of the tree is ~a~%" (val 
root)))) 

Write it in a file (in this case hello-cells.lisp) and 
load it:

> (load "hello-cells.lisp")

T

> (math-op-family)

value of the tree is 68

new value of the tree is 95

NIL

Lets' see the most important parts of the program:

(defmodel node (family)

  ((val :initform (c-in nil) :initarg :val)))

Here we define the model node: we plan to build a 
family of nodes, so we inherit from the model family. 
The slot val will contain the value of the node.

(make-instance 

 'node

 :val (c? (apply #'+ (mapcar #'val (kids self))))

Now we create the main node: its value is defined as 
the sum of all its children values. To get the children 
list we use the method (kids self).

:kids

(c?

  (the-kids

We specify the children list using the :kids argument. 
the-kids builds a list of children using the following 
arguments. the-kids also removes nil kids and if an 
argument is a list then it is flattened, e.g. (the-kids 
(list k1 (list (list k2 nil) k3))) will return a list 
with the kids k1, k2 and k3.

(make-kid 'node :md-name :n5 :val (c-in 5))

This is the first child of the main node: we give it a 
name with the :md-name argument to reference the node 
through it in the future. To create an instance of a 
model intended to be a child you must specify to 
make-instance its parent through the argument 
:fm-parent. make-kid does this for us passing self as 
the parent.

(make-kid

 'node

 :val (c? (apply #'* (mapcar #'val (kids self))))

 :kids

 (c?

   (the-kids

     (make-kid 'node :md-name :n7 :val (c-in 7))

     (make-kid 'node :md-name :n9 :val (c-in 9)))))

The second child of the main node has two children and 
its value is the product of their values.

(format t "value of the tree is ~a~%" (val root))

(setf (val (fm-other :n7 :starting root)) 10)

(format t "new value of the tree is ~a~%" (val root))))

The body of the function prints the value of the tree, 
and through the output you can see that it depends 
correctly on the values of its children. Then we change 
the value of the node named :n7 and see that the new 
output has changed accordingly. (fm-other <member-name> 
<starting-point>) searches the family tree starting 
from <starting-point>, and returns the object named 
<member-name>. If it is not found, and error is raised. 
<starting-point> is optional, and it defaults to 
'self'. We used fm-other outside of a defmodel, so 
there is no self and we must supply a starting point.

5 Defining an observer

Cells lets you define a function to execute immediately 
after a c-in slot is modified. This function is called 
an "observer". To define it, use the defobserver construct:

(defobserver <slot-name> (&optional (<self> self) 

                                    (<new-value> old-value)

                                    (<old-value> new-value)

                                    (<old-value-boundp> 
old-value-boundp))

  <function-body>)

This function will be executed every time the slot 
<slot-name> of an object of type <model-name> is 
modified. <old-value> will hold the previous value of 
the slot, <new-value> the new one and 
<old-value-boundp> will be nil if this is the first 
time the slot gets a value and t otherwise. If not 
given, <self>, <new-value>, <old-value> and 
<old-value-boundp> will default to 'self', 'new-value', 
'old-value' and 'old-value-bound-p'. In older releases 
of cells defobserver was called def-c-output.

Suppose we want to log all the values that the num slot 
assumes: we can do this defining an observer function. 
Add the following lines to hello-cells.lisp:

(defobserver num ((self hello-cells))

  (format t "new value of num is: ~a~%" new-value))

Now reload the file and try running (hello) again:

> (load "hello-cells.lisp")

T

> (hello)

new value of num is: 0

new value of num is: 10

num is 10 and square-num is 100

new value of num is: 20

num is 20 and square-num is 400

new value of num is: 30

num is 30 and square-num is 900

new value of num is: 40

num is 40 and square-num is 1600

new value of num is: 50

num is 50 and square-num is 2500

new value of num is: 60

num is 60 and square-num is 3600 

num is 60 and square-num is 3600

NIL

As you can see from the output, every time we set (num 
h) with a different value, the action previously 
defined is called. This also happens when (num h) is 
initialized for the first time at object creation time. 
You may have noted that when we set (num h) to 60 for 
the second time, the observer function isn't called: 
this is because when you set a slot to a new value that 
is the same (according to the function eql) as its old 
one, the change isn't propagated because there is no 
need to propagate it: it didn't change! 

Now look at the following piece of code: 

(defmodel str-model ()

  ((str :accessor str :initform (c-in "") :initarg :str)

   (rev-str :accessor rev-str :initform (c? (reverse 
(str self))))))



(defobserver str ()

  (format t "changed!~%"))



(defun try-str-model ()

  (let ((s (make-instance 'str-model)))

    (dolist (l `("Hello!" "Bye" 

                 ,(concatenate 'string "By" "e") "!olleH"))

      (setf (str s) l)

      (format t "str is \"~a\", rev-str is \"~a\"~%" 

              (str s) (rev-str s)))))

It does nothing new: it constrains rev-str to be the 
reverse of str, creates an instance of str-model and 
prints some strings together with their reverse. It 
also logs every time it needs to compute the reversed 
string. Note that the second and the third strings of 
the list are actually equal. Lets try to run the code 
(supposing you wrote it in hello-cells.lisp):

> (load "hello-cells.lisp")

T

> (try-str-model)

changed!

changed!

str is "Hello!", rev-str is "!olleH"

changed!

str is "Bye", rev-str is "eyB"

changed!

str is "Bye", rev-str is "eyB"

changed!

str is "!olleH", rev-str is "Hello!"

NIL

The reversed string is calculated every time we set 
(str s), even when we're changing it from "Bye" to "Bye". 
But "Bye" and "Bye" are equal! Why do we need to waste time 
reversing it twice? Because cells by default uses eql 
to test for equality and if two strings aren't the same 
string (i.e. they don't have the same memory address) 
eql considers them to be different. The following piece 
of code shows us another problem: suppose we change 

`("Hello!" "Bye" ,(concatenate 'string "By" "e") "!olleH")

to

`("Hello!" "Bye" "Bye" "!olleH")

depending on the Common Lisp implementation you run the 
program on you'll have a different output! Solving the 
problem is easy, we just need to use equal instead of 
eql as the equality function. To supply your own 
equality function pass it to the :unchanged-if argument 
in the slot definition:

(str :accessor str :initform (c-in "") :initarg :str 

     :unchanged-if #'equal)

Now we get the same expected result on any implementation:

changed!

changed!

str is "Hello!", rev-str is "!olleH"

changed!

str is "Bye", rev-str is "eyB"

str is "Bye", rev-str is "eyB"

changed!

str is "!olleH", rev-str is "Hello!"

NIL

The equality function must accept two values: the new 
value of the slot and the old one.

6 Lazy cells

Ruled cells are evaluated, as we have already seen, at 
instance creation time and after dependent cells 
change. However, you may want to not evaluate a ruled 
cell until it is really needed, i.e. when the program 
asks for its value. To achieve such a behavior, you can 
use lazy cells. There are three types of them, 
depending on their laziness:

1. :once-asked this will get evaluated/observed on 
  initialization, but won't be reevaluated immediately 
  if dependencies change, rather only when read by 
  application code.

2. :until-asked this does not get evaluated/observed 
  until read by application code, but then it becomes 
  un-lazy, eagerly re-evaluated as soon as any 
  dependency changes (not waiting until asked).

3. :always this isn't evaluated/observed until read, 
  and not reevaluated until read after a dependency changes.

There are two ways in which a cell can be lazy: by not 
being evaluated immediately after its creation and by 
not responding to dependencies change. In both cases, 
when the program asks for its value, the lazy cell is 
evaluated (if needed). The first type embodies only the 
second way, the second type only the first way and the 
third type is lazy in both ways. The following example 
shows the behavior of lazy cells:

(defmodel lazy-test ()

  ((lazy-1 :accessor lazy-1 :initform (c-formula (:lazy 
:once-asked)

                                        (append (val 
self) (list '!!))))

   (lazy-2 :accessor lazy-2 :initform (c_? (val self)))

   (lazy-3 :accessor lazy-3 :initform (c?_ (reverse 
(val self))))

   (val :accessor val :initarg :val :initform (c-in nil))))



(defobserver lazy-1 ()

  (format t "evaluating lazy-1!~%"))



(defobserver lazy-2 ()

  (format t "evaluating lazy-2!~%"))



(defobserver lazy-3 ()

  (format t "evaluating lazy-3!~%"))



(defun print-lazies (l)

  (format t "Printing all the values:~%")

  (format t "lazy-3: ~a~%" (lazy-3 l))

  (format t "lazy-2: ~a~%" (lazy-2 l))

  (format t "lazy-1: ~a~%" (lazy-1 l)))



(defun try-lazies ()

  (let ((l (make-instance 'lazy-test :val (c-in '(Im 
very lazy!)))))

    (format t "Initialization finished~%")

    (print-lazies l)

    (format t "Changing val~%")

    (setf (val l) '(who will be evaluated?))

    (print-lazies l)))

As usual, load it and run it:

> (load "hello-cells.lisp")

T

> (try-lazies)

evaluating lazy-1!

Initialization finished

Printing all the values:

evaluating lazy-3!

lazy-3: (LAZY! VERY IM)

evaluating lazy-2!

lazy-2: (IM VERY LAZY!)

lazy-1: (IM VERY LAZY! !!)

Changing val

evaluating lazy-2!

Printing all the values:

evaluating lazy-3!

lazy-3: (EVALUATED? BE WILL WHO)

lazy-2: (WHO WILL BE EVALUATED?)

evaluating lazy-1!

lazy-1: (WHO WILL BE EVALUATED? !!)

NIL

As you can see from the code, to declare a ruled cell 
to be lazy you just need to use the three constructs 
(c-formula (:lazy :one-asked) ...), (c_? ...) and (c?_ 
...) for :once-asked, :until-asked and :always lazy 
cells, respectively. lazy-1 is evaluated immediately, 
lazy-2 and lazy-3 only when they are needed by format. 
After setting (val l), on which all the lazy cells 
depend, lazy-2 is re-evaluated immediately because it 
is of type :until-asked, while lazy-1 becomes lazy and 
lazy-3 remains lazy, so these two postpone evaluation 
until we ask for their values in the call to format.

As a side note, such short names may not be very easy 
to remember and to read, but those constructs are so 
common that you'll find yourself using them a lot, and 
you'll appreciate their conciseness. If you still 
prefer long descriptive names, though, you can use the 
c-formula construct instead of c?/c_?/c?_ and c-input 
instead of c-in (see the "Functions & macros reference" section).

7 Drifters

Another type of cells are drifter cells. A drifter cell 
acts like a ruled cell, but the value returned by its 
body is interpreted as an increment, so after it has 
been re-evaluated its value becomes its previous one 
plus the one returned by the body. The following 
example shows drifter cells in action:

(defmodel counter ()

  ((how-many :accessor how-many

             :initform (c... (0)

                         (length (^current-elems))))

   (current-elems :accessor current-elems

                  :initform (c-in nil))))



(defun try-counter ()

  (let ((m (make-instance 'counter)))

    (dolist (l '((1 2 3) (4 5) (1 2 3 4)))

      (setf (current-elems m) l)

      (format t "current elements: ~{~a ~}~%" 
(current-elems m))

      (format t "~a elements seen so far~%" (how-many m)))))

try-counter iterates other a list setting current-elems 
to a list of values, and after each iteration how-many 
will hold the total number of the elements within the 
lists seen so far. The output will be:

> (load "hello-cells.lisp")

T

> (try-counter)

elements: 1 2 3

3 elements seen so far

elements: 4 5

5 elements seen so far

elements: 1 2 3 4  

9 elements seen so far

NIL

The important passage in the code is the initialization 
of how-many:

(c... (0)

  (length (^current-elems)))

(^current-elems) is just a shortcut for (current-elems 
self). The construct (c... (<initial-value>) <body>) 
creates a drifter cell whose initial value will be 
<initial-value>, in this case 0. When current-elems 
changes, (length (^current-elems)) is re-evaluated, and 
its value is summed to how-many, so how-many will hold 
the total number of elements that current-elems has 
held so far.

8 Cyclic dependencies

It is possible to write code with cyclic dependencies: 
when A changes you need to take some action that 
changes B, which in turn sets A, but A has still to 
complete running the code needed to keep it in a 
consistent state. The following code shows how this 
situation could arise:

(defmodel cycle ()

  ((cycle-a :accessor cycle-a :initform (c-in nil))

   (cycle-b :accessor cycle-b :initform (c-in nil))))



(defobserver cycle-a ()

  (setf (cycle-b self) new-value))



(defobserver cycle-b ()

  (setf (cycle-a self) new-value))



(defun try-cycle ()

  (let ((m (make-instance 'cycle)))

    (setf (cycle-a m) '(? !))

    (format t "~a and ~a" (cycle-a m) (cycle-b m))))

When try-cycle sets cycle-a, its observer gets called, 
which sets cycle-b which in turn sets cycle-a. This is 
not an infinite cycle as it may seem, because the 
second time we set cycle-a we give it the same value we 
gave it the first time, so the cells engine should stop 
the propagation. Lets see if this does actually work:

> (load "hello-cells.lisp")

T

> (try-cycle)

SETF of <2:A CYCLE-B/NIL = NIL> must be deferred by 
wrapping code in WITH-INTEGRITY

   [Condition of type SIMPLE-ERROR]

The message could vary depending on your Common Lisp 
implementation, but one thing is clear: the code 
doesn't work. This happens because when we set cycle-a 
for the second time, its observer is still running, so 
cycle-a could be in an inconsistent state. The error 
message tells us the solution: wrap the problematic 
code inside the with-integrity construct, which makes 
sure that cycle-a is consistent when that piece of code 
is run. The same problem exists for cycle-b and the 
solution is the same. We need then to change

(defobserver cycle-a ()

  (setf (cycle-b self) new-value))

to

(defobserver cycle-a ()

  (with-integrity (:change)

    (setf (cycle-b self) new-value)))

and 

(defobserver cycle-b ()

  (setf (cycle-a self) new-value))

to

(defobserver cycle-b ()

  (with-integrity (:change)

    (setf (cycle-a self) new-value)))

Now if we reload the code and run it we'll get the 
correct result. Make sure to call (cells-reset) after 
an error has occurred.

> (cells-reset)

NIL

> (load "hello-cells.lisp")

T

> (try-cycle)

(? !) and (? !)

NIL

9 Synapses

9.1 Built-in synapses

Suppose that you have a cell A that depends on another 
cell B, but you want A to change only when B changes by 
an amount over a given threshold, maybe because B 
receives data from an external probe and you don't want 
A to over-react to small fluctuations. Synapses let you 
do this, and they give you more control over the 
constraint propagation system. Basically, using 
synapses you can tell the system if a change should be 
propagated or not. The following example shows a "clock" 
that changes only after a minimal amount of time:

(defmodel syn-time ()

  ((current-time :accessor current-time :initarg :current-time

                 :initform (c-in 0))

   (wait-time :accessor wait-time :initarg :wait-time 
:initform (c-in 0))

   (time-elapsed :accessor time-elapsed

                 :initform

                 (c?

                   (f-sensitivity :syn ((wait-time self))

                     (current-time self))))))



(defun try-syn-time ()

  (let ((tm (make-instance 'syn-time :wait-time (c-in 2))))

    (dotimes (n 10)

      (format t "time +1~%")

      (incf (current-time tm))

      (format t "time-elapsed is ~a~%" (time-elapsed tm)))))

time-elapsed holds the same value of current-time, but 
it changes only when current-time changes by at least 
wait-time units. In the main function we simulate time 
with a loop that increments current-time by one unit 
and then shows elapsed-time. The most important part of 
the program is 

(f-sensitivity :syn ((wait-time self))

  (current-time self))

Here we create a synapse named :syn. It is of type 
f-sensitivity: (current-time self) is evaluated always, 
but if the difference between the previously propagated 
value (if there is one) and the value it returns is 
lesser than (wait-time self), then the slot 
elapsed-time won't change and, consequently, nothing 
will be propagated. The expected result then will be:

> (load "hello-cells.lisp")

T

> (try-syn-time)

time +1

time-elapsed is 0

time +1

time-elapsed is 2

time +1

time-elapsed is 2

time +1

time-elapsed is 4

time +1

time-elapsed is 4

time +1

time-elapsed is 6

time +1

time-elapsed is 6

time +1

time-elapsed is 8

time +1

time-elapsed is 8

time +1

time-elapsed is 10

NIL

time-elapsed changes only when the accumulated 
difference is at least wait-time (2 in this case). 
Other synapses available are f-delta, f-plusp, f-zerop.

9.2 Defining your own

As it frequently happens, you may need a type of 
synapse that is not available. In this case, you can 
define your own synapses using the construct with-synapse.

(with-synapse <id> (&rest <vars>)

  <body>)

<vars> is a valid variable declaration list such as 
that of the let form. These variables are created and 
initialized the first time <body> is executed, and they 
retain their value from call to call, so that you can 
use them to carry state between different 
re-evaluations of <body>. <body> should return two 
values: the value to return and one keyword out of 
:propagate and :no-propagate to indicate if the value 
should be propagated or not. For example, we could have 
a ruled cell that propagates only when another cell is odd:

(defmodel my-syn-test ()

  ((num :accessor num :initform (c-in 0))

   (odd-num :reader odd-num

            :initform (c?

                        (with-synapse :odd-syn ()

                          (if (oddp (^num))

                              (values (^num) :propagate))

                              (values nil :no-propagate)))))))

(defobserver odd-num ()

  (when old-value-boundp

    (format t "Propagated!~%")))

(defun try-my-syn ()

  (let ((m (make-instance 'my-syn-test)))

    (dolist (n '(1 2 4 5 7 11 12 14 16 15))

      (format t "Setting num to ~a~%" n)

      (setf (num m) n)

      (format t "odd-num is ~a~%" (odd-num m)))))

The crucial part is the values returned by 
with-synapse's body. When num is odd, we return it 
together with :propagate, otherwise we return a value 
that will be ignored (because it won't be propagated) 
and :no-propagate. Here is the output:

> (load "hello-cells.lisp")

T

> (try-my-syn)

Setting num to 1

Propagated!

odd-num is 1

Setting num to 2

odd-num is 1

Setting num to 4

odd-num is 1

Setting num to 5

Propagated!

odd-num is 5

Setting num to 7

Propagated!

odd-num is 7

Setting num to 11

Propagated!

odd-num is 11

Setting num to 12

odd-num is 11

Setting num to 14

odd-num is 11

Setting num to 16

odd-num is 11

Setting num to 15

Propagated!

odd-num is 15

NIL 

You can see that odd-num changes only when we return :propagateWe could have returned any other value. The only 
requirement to propagate is to return something 
different from :no-propagate. 
. When we return :no-propagate odd-num doesn't change. 
We didn't need to carry some state between different 
executions of the body, so we left the <vars> list empty.

10 Example: playing sudoku

We have seen a few example of using cells, but none of 
them actually did something beside showing cells 
behavior. Now we will see how to use cells to aid us 
resolving a sudoku puzzle. First of all, some constants:

(defparameter *all-values* '(1 2 3 4 5 6 7 8 9))

(defparameter *row-len* 9)

(defparameter *sq-size* 3)

(defparameter *col-len* 9)

The input board is a vector of vectors: every position 
contains either a number from 1 to 9 or a '? telling 
the program that it must find a value to fill in that 
position. The following is an empty board: 

(defparameter *board* 

  #(#(? ? ? ? ? ? ? ? ?)

    #(? ? ? ? ? ? ? ? ?)

    #(? ? ? ? ? ? ? ? ?)

    #(? ? ? ? ? ? ? ? ?)

    #(? ? ? ? ? ? ? ? ?)

    #(? ? ? ? ? ? ? ? ?)

    #(? ? ? ? ? ? ? ? ?)

    #(? ? ? ? ? ? ? ? ?)

    #(? ? ? ? ? ? ? ? ?)))

We will represent the playing board with the model 
board, which has two slots: complete is a boolean that 
tells if every position on the board has been filled 
with a value, and squares is a vector of vectors 
representing the actual board. The slot complete is a 
lazy cell because it is needed rarely and it would be a 
waste of time to recompute it whenever a single square 
changes. Every square in the board is represented by 
the model square, which has three slots: exact-val 
holds the actual value of the square and it is NIL if 
the square is empty, possible-vals holds a list of the 
values that the square could assume without conflicting 
with the exact-val of the squares in the same group, 
and group is a reference to an object of type 
square-group: squares in the same group cannot have the 
same exact-val.

(defmodel square-group ()

  ((constraining :initform (c-in nil) :initarg :constraining

                 :accessor constraining)))

(defmodel square ()

  ((group :accessor group :initform (c-in nil))

   (exact-val :accessor exact-val :initform (c-in nil) 
:initarg :exact-val)

   (possible-vals 

    :accessor possible-vals

    :initform 

    (c?

      (when (and (^group) (not (^exact-val)))

        (let ((c (constraining (^group))))

          ;; a value must not be the same of the constraining

          (remove-if-not 

           #'(lambda (v) 

               (every 

                #'(lambda (x) 

                    (not (eql v (exact-val x))))

                c))

           *all-values*)))))))

(defun make-square (x)

  (make-instance 'square :exact-val (c-in (if (eql x 
'?) nil x))))

(defmodel board ()

  ((complete :accessor complete

             :initform 

             (c?_

               (every #'(lambda (x) (every #'exact-val 
x)) (^squares))))

   (squares :accessor squares :initarg :squares))) 

(defmethod print-object ((self board) out)

  (dotimes (r *col-len*)

    (dotimes (c *row-len*)

      (format out "~a " (exact-val (at (^squares) r c))))

      (format out "~%")))

Some helper functions to get a value from the board and 
to find the next position without a value. A position 
is a list of two numbers: the row and the column.

(defun at (board r c)

  (elt (elt board r) c))

(defun next-pos (pos)

  "next position in the board. search only forward. 

return NIL if the board is finished"

  (destructuring-bind (r c) pos

    (if (= c (1- *row-len*))

        (if (= r (1- *col-len*))

            nil

            (list (1+ r) 0))

        (list r (1+ c)))))

(defun next-to-try (board pos)

  "find next position without a value searching forward.

return NIL if there is none"

  (let ((pos (next-pos pos)))

    (when pos

      (let ((s (at board (first pos) (second pos))))

        (if (exact-val s)

            (next-to-try board pos)

            pos)))))

We create a group for every square. The same square 
belongs to more than one group. We put in the same 
group of a certain square all the squares in the same 
line, in the same column or in the same block.

(defun make-groups (squares)

  (dotimes (r *col-len*)

    (dotimes (c *row-len*)

      (setf (group (at squares r c))

            (make-instance 'square-group

                           :constraining

                           (c-in

                            (delete-duplicates

                             (nconc

                              (nth-col squares c)

                              (nth-row squares r)

                              (nth-block squares r 
c))))))))) 

(defun nth-row (board n)

  "return row n of board"

  (coerce (elt board n) 'list))

(defun nth-col (board n)

  "return column n of board"

  (map 'list #'(lambda (x) (elt x n)) board))

(defun nth-block (board r c)

  "return list of element in the same block of (at 
board r c)"

  (let ((upper-left-r (* *sq-size* (floor (/ r *sq-size*))))

        (upper-left-c (* *sq-size* (floor (/ c *sq-size*)))))

    (apply #'concatenate 'list 

           (map 'list #'(lambda (x)

                          (subseq x upper-left-c

                                  (+ upper-left-c *sq-size*)))

                (subseq board upper-left-r 

                        (+ upper-left-r *sq-size*))))))

To create the board we map the input board and for 
every position we create a square. Then we build all 
the groups.

(defun make-board (b)

  (let ((b (make-instance 

            'board 

            :squares 

            (c-in

             (map 'vector #'(lambda (x) (map 'vector 
#'make-square x))  b)))))

    (make-groups (squares b))

    b))

The following code looks for a solution, trying all the 
possible combinations. Thanks to how we defined 
possible-vals, impossible combinations are never tried.

(defun search-solution (b &optional (next 

                                     (next-to-try 
(squares b) (list 0 -1))))

  (if next

      (let ((s (at (squares b) (first next) (second next))))

        (or (some ; find the first of the possible 
values that yields a solution

             #'(lambda (x)

                 (setf (exact-val s) x) ; try it

                 (search-solution b (next-to-try 
(squares b) next)))

             (possible-vals s))

            ;; couldn't find any solution: reset the 
square and return 

            ;; NIL to indicate failure

            (setf (exact-val s) nil)))

      ;; tried all the positions: have we completed the board?

      (complete b)))

Finally the main function: it accepts an input board 
and prints a solution.

(defun sudoku (the-board)

  (let ((b (make-board the-board)))

    (search-solution b)

    (format t "Solution:~%~a~%" b)))

Save it in a file named "sudoku.lisp" and try it on the 
empty board:

> (load "sudoku.lisp")

T

> (sudoku *board*)

Solution:

1 2 3 4 5 6 7 8 9

4 5 6 7 8 9 1 2 3

7 8 9 1 2 3 4 5 6

2 1 4 3 6 5 8 9 7

3 6 5 8 9 7 2 1 4

8 9 7 2 1 4 3 6 5

5 3 1 6 4 2 9 7 8

6 4 2 9 7 8 5 3 1

9 7 8 5 3 1 6 4 2 

NIL

It does find a solution, but it takes quite a while to 
print it:

> (time (sudoku *board*))

Solution:

1 2 3 4 5 6 7 8 9 

4 5 6 7 8 9 1 2 3 

7 8 9 1 2 3 4 5 6 

2 1 4 3 6 5 8 9 7 

3 6 5 8 9 7 2 1 4 

8 9 7 2 1 4 3 6 5 

5 3 1 6 4 2 9 7 8 

6 4 2 9 7 8 5 3 1 

9 7 8 5 3 1 6 4 2

Evaluation took:

  2.476 seconds of real time

  2.388149 seconds of user run time

  0.076004 seconds of system run time

  [Run times include 0.176 seconds GC run time.]

  0 calls to %EVAL

  0 page faults and

  155,622,072 bytes consed.

NIL

It takes 2.4 seconds and it allocates more than 155 MB 
of memory! We can do better by noticing that when we 
set exact-val in search-solution the slot possible-vals 
of every cell in the same group are recomputed, but we 
don't need all those values immediately, and a lot of 
them will change again before we will need them. The 
solution is to use a lazy cell and to do that we change 
the initform of possible-vals to use c?_ instead of c?. 
Change it and run the program again:

> (load "sudoku.lisp")

T

> (time (sudoku *board*))

Solution:

1 2 3 4 5 6 7 8 9 

4 5 6 7 8 9 1 2 3 

7 8 9 1 2 3 4 5 6 

2 1 4 3 6 5 8 9 7 

3 6 5 8 9 7 2 1 4 

8 9 7 2 1 4 3 6 5 

5 3 1 6 4 2 9 7 8 

6 4 2 9 7 8 5 3 1 

9 7 8 5 3 1 6 4 2 

Evaluation took:

  0.181 seconds of real time

  0.16001 seconds of user run time

  0.020001 seconds of system run time

  [Run times include 0.012 seconds GC run time.]

  0 calls to %EVAL

  0 page faults and

  9,517,528 bytes consed.

NIL 

Now the speed is much better (more than ten times 
faster), it allocates only 9.5 MB of memory, and we 
achieved this result with a really small change.

One important thing to note about this example is that 
we had to write the function search-solution to solve 
the puzzle, because cells has no constraints resolution 
engine. What it does is to propagate change to 
dependent slots. We used this feature to keep the board 
in a consistent state and to roll out impossible 
combinations while searching for a solution, without 
having to worry about dependencies. This way the 
searching function has been quite simple to write, 
because all the relations between different squares 
were managed automatically by the models we defined earlier.

11 Functions & macros reference

Here follows a quick reference of the main functions 
and macros.

11.1 Main

defmodel

(defmodel <model-name> (<superclass>*)

  (<slot-definition>*)

  <other-optional-arguments>)

(Macro) Defines a new model. It has the same structure 
and the accept the same options of a class definition. 
<slot-definition> accepts the special argument :cell 
that lets you declare what kind of slot it is. The 
default is a normal cell slot. Other options include:

1. :cell nil the slot will be ignored by the 
  constraints-handling system

2. :cell :ephemeral when an ephemeral slot is changed, 
  everything works as with a normal cell, but after the 
  propagation has ended, its value will become nil. 
  They are useful to model events.

For every cell's accessor defmodel creates a macro 
^<accessor-name> that you can use as a shortcut for 
(<accessor-name> self).

c-in

(c-in <expr>)

(Macro) Initializes a cell slot with the value expr. 
When a cell slot initialized with c-in changes, 
dependant cells will be recalculated. The value of a 
cell slot initialized with c-in can be setted.

c-input

(c-input (&rest args) &optional value)

(Macro) Same as c-in, but it lets specify extra 
arguments, and value is optional. If it is not given, 
the slot will be unbound and any access to it will 
result into an error. 

c?

(c?

  <body>)

(Macro) Initializes a cell slot with the value of 
<body>. If <body> references input cell slots, it will 
be recalculated whenever those slots change. Within c? 
you have access to the variable self, representing the 
current object

c?+n

(c?+n

  <body>)

(Macro) Creates a ruled cell whose value can be setted.

c?once

(c?once

  <body>)

(Macro) Creates a ruled cell that gets evaluated only 
once at initialization time.

c?1

(c?1

  <body>)

(Macro) Nickname for c?once.

c_?

(c_? 

  <body>)

(Macro) Creates a lazy ruled cell slot of type :until-asked.

c?_

(c?_ 

  <body>)

(Macro) Creates a lazy ruled cell slot of type :always.

c_1

(c_1

  <body>)

(Macro) Creates a lazy cell that gets evaluated only once.

c...

(c... (<initial-value>)

  <body>)

(Macro) Creates a drifter cell with initial value 
<initial-value>.

c-formula

(c-formula (<options>)

  <body>)

(Macro) Same as c?, but lets you specify extra options. 
For example, the option :inputp lets you build a cell 
that behaves like a cell initialized with both c? and 
c-in. Another useful option is :lazy that lets you 
specify the laziness of the cell: nil, t, :once-asked, 
:until-asked or :always.

defobserver

(defobserver <slot-name> (&optional (<self> self) 

                                    (<new-value> old-value)

                                    (<old-value> new-value)

                                    (<old-value-boundp> 
old-value-boundp))

  <function-body>)

(Macro) Defines a function that is called every time 
the slot <slot-name> changes. In previous versions of 
cells it were called def-c-output.

with-integrity

(with-integrity (&optional <opcode> <defer-info>)

  <body>)

(Macro) Makes sure to run <body> only when the system 
is in a consistent state. <opcode> tells what type of 
anomaly should be handled. Possible values are 
:tell-dependents, :awaken, :client, :ephemeral-reset 
and :change.

without-c-dependency

(without-c-dependency

  <body>)

(Macro) Executes body without tracing any dependency. 
I.e. if we are within a ruled cell and <body> 
references a cell slot, when that slot changes the 
change is not propagated to the ruled cell.

11.2 Family models

The following only works for models that inherit from family.

make-part

(make-part <md-name> <model-name> &rest <args>)

(Function) Creates an instance of <model-name> with 
:md-name set to <md-name>. <args> are passed to make-instance.

mk-part

(mk-part <md-name> (<model-name>) &rest <args>)

(Macro) Same as make-part, but sets the parent to self

the-kids

(the-kids &rest <kids>)

(Macro) Builds a list of kids. <kids> may contain 
objects or nested lists of objects.

make-kid

(make-kid <model-name> &rest <args>)

(Macro) The same as (make-instance <model-name> <args> 
:fm-parent self).

def-kid-slots

(def-kid-slots &rest <kids>)

(Macro) Creates a function of one argument that builds 
a list of kids with the given parent. Within 
def-kid-slots self is bound to the parent. 

kids

(kids <object>)

(Method) Gives access to <object>'s children.

kid1,kid2,last-kid

(kid1 <object>)

(kid2 <object>)

(last-kid <object>

(Function) Gives access, respectively, to <object>'s 
first, second and last child

^k1,^k2,^k-last

(^k1)

(^k2)

(^k-last)

(Macro) Shortcuts for (kid1 self), (kid2 self) and 
(last-kid self)

fm-parent

(fm-parent &optional (<object> self))

(Method) Gives access to <object>'s parent.

fm-other

(fm-other <name> &optional (<starting-point> self))

(Macro) Looks for an object named <name> within 
<starting-point>'s family.

fm^

(fm^ <name> &optional (<starting-point> self))

(Macro) Same as (fm-other <name> (fm-parent 
<starting-point>)), but doesn't search <starting-point> 
and its children.

fm-kid-typed

(fm-kid-typed <self> <type>)

(Function) Finds the first <self>'s child whose type is <type>.

fm-descendant-typed

(fm-descendant-typed <self> <type>)

(Function) Finds the first descendant of <self> whose 
type is <type>.

container

(container <object>)

(Function) Gets <object>'s parent.

container-typed

(container-typed <object> <type>)

(Function) Gets <object>'s first ancestor of type <type>.

upper

(upper <object> &optional (<type> t))

(Function) Same as (container-typed <object> <type>).

fm-ascendant-typed

(fm-ascendant-typed <parent> <type>)

(Function) Gets the first ancestor of type <type>, 
searching from <parent> included.

fm-kid-named

(fm-kid-named <self> <name>)

(Function) Gets <self>'s kids whose md-name is <name>.

fm-ascendant-named

(fm-ascendant-named <self> <name>)

(Function) Gets the first ancestor whose md-name is 
<name> starting from <self> included.

fm-descendant-named

(fm-descendant-named <self> <name> &key (<must-find> t))

(Function) Gets the first successor whose md-name is 
<name> starting from <self> included. If <must-find> is 
nil no error is raised if it isn't found.

not-to-be

(not-to-be <object>)

(Function) Unregisters <object>.

11.3 Synapses

f-sensitivity

(f-sensitivity <name> (<sensitivity> &optional <subtypename>)

  <body>)

(Macro) Creates a synapse named <name> that propagates 
changes only when the value returned by <body> differs 
by at least <sensitivity> from the value it had the 
last time it propagated.

f-delta

(f-delta <name> (&key <sensitivity> (<type> 'number)) 

  <body>)

(Macro) Creates a synapse named <name> that propagates 
changes only when the difference between the value 
returned by <body> and the value it returned the 
previous time is strictly greater than <sensitivity>. 

with-synapse

(with-synapse <syn-id> (<vars>)

  <body>)

(Macro) Creates a synapse. <body> should return two 
multiple values, and when the second is :no-propagate, 
the eventual change isn't propagated.

11.4 Misc

cells-reset

(cells-reset)

(Function) Resets the system.

12 Other resources

This tutorial just scratched the surface of cells. You 
can find more documentation about cells within the 
'doc' directory in the source tarball or by looking at 
the source files within the directories 'cells-test', 
'tutorial' and 'Use Cases'. A general overview of cells 
can be found in the file cells-manifesto.txt in the 
source tarball. You can also ask questions about cells 
on the project's mailing list: [http://common-lisp.net/cgi-bin/mailman/subscribe/cells-devel]

Cells-gtk

13 Introduction

13.1 Where's the GUI?

One classic question that a Common Lisp newcomer asks 
is what are the libraries available to build graphical 
interfaces. Some typical answers he/she would get are 
the following:

1. Use a commercial implementation. Commercial 
  implementations such as Allegro or LispWorks comes 
  with portable, stable and well documented GUI 
  libraries. The drawbacks are that you would be locked 
  with a particular vendor and that you should pay for 
  them. Depending on your particular situation, this 
  may or may not be a good choice.

2. No one uses GUI applications anymore. Web interfaces 
  are the new GUI. Given that there are really good 
  frameworks for web programming available for Common 
  Lisp, this is not the answer you were looking for.

3. McCLIM. Once upon a time (end of the 80s), CLIM was 
  the standard way to do graphical applications with 
  Common Lisp. McCLIM is an open source project that 
  implements almost the entire CLIM standard. The 
  default CLIM look-and-feel is quite old-fashionedThere are ongoing efforts to use GTK and Cairo to bring 
to McCLIM a modern look.
  , and interfaces built with it are fundamentally 
  different from the standard widget-oriented way of 
  doing GUIs this days, so it may not be what you 
  really want. The biggest problem, though, is that 
  CLIM is very complicated, and there is very little 
  documentation to help you in the learning process.

4. LTK, a port to Common Lisp of Tcl's Tk library. 
  Light, stable, cross-platform and now good looking 
  thanks to the 8.5 release of Tk.

5. Cells-inside GUI toolkits. These libraries use cells 
  to let you easily build graphical applications. You 
  can choose between celtk (based on Tk), cello (based 
  on OpenGL) and cells-gtk, that uses GTK as the 
  backend. The rest of this tutorial covers cells-gtk.

13.2 Cells-gtk

Cells-gtk is not a direct wrapper of the gtk+ API, 
instead it uses gtk+ just as a backend and offers a 
very high-level API to the programmer. Every widget is 
a model that inherits from family, so everything we 
have already seen about cells and the family model 
applies to widgets. The family tree mimics the 
graphical objects' hierarchy that the user sees, and 
properties of the widgets can be initialized to any 
type of cell. It is quite usual, for example, to make 
properties that give some kind of information to the 
user (such as list views or a progress bar) be ruled 
cells, and properties of widgets that the user can 
modify (such as the text of an entry or the state of a 
radio group) be input cells. The cells-gtk programmer 
makes a parsimonious use of event handlers, because 
most of the work that is usually done within an event 
handler in more traditional toolkits can be done in a 
more concise and localized way using ruled cells, input 
cells and observers.

14 Installation