Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
3346 lines (2401 sloc) 68.3 KB
#LyX 1.3 created this file. For more info see http://www.lyx.org/
\lyxformat 221
\textclass article
\language english
\inputencoding auto
\fontscheme default
\graphics default
\paperfontsize default
\spacing single
\papersize Default
\paperpackage a4
\use_geometry 0
\use_amsmath 0
\use_natbib 0
\use_numerical_citations 0
\paperorientation portrait
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\defskip medskip
\quotes_language english
\quotes_times 2
\papercolumns 1
\papersides 1
\paperpagestyle default
\layout Title
Cells tutorial
\layout Standard
\begin_inset LatexCommand \tableofcontents{}
\end_inset
\layout Part
Cells
\layout Section
Introduction
\layout Subsection
What's cells?
\layout Standard
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 slots
\begin_inset Foot
collapsed false
\layout Standard
A slot is the Common Lisp equivalent of a class instance variable in other
languages
\end_inset
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
\emph on
relationship
\emph default
between the data, the burden of maintaining them true is handled automatically
by cells.
\layout Subsection
How could it improve your programs?
\layout Standard
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
applications
\begin_inset Foot
collapsed false
\layout Standard
See the cells-gtk project:
\begin_inset LatexCommand \htmlurl{http://common-lisp.net/project/cells-gtk}
\end_inset
\end_inset
, 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.
\layout Section
Installation
\layout Standard
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
\begin_inset Foot
collapsed true
\layout Standard
\begin_inset LatexCommand \htmlurl[SBCL]{http://www.sbcl.org}
\end_inset
\end_inset
.
First of all, download cells: you can get the latest version at
\begin_inset LatexCommand \htmlurl{http://common-lisp.net/cgi-bin/viewcvs.cgi/cells/?root=cells}
\end_inset
.
Then enter the directory ~/.sbcl/site and unpack cells:
\layout LyX-Code
$ cd ~/.sbcl/site
\layout LyX-Code
$ tar -zxvf ~/cells.tar.gz
\layout Standard
Now be sure that ASDF will be able to find it:
\layout LyX-Code
$ cd ~/.sbcl/systems
\layout LyX-Code
$ for a in `find ~/.sbcl/site/cells/ -name
\begin_inset Quotes eld
\end_inset
*.asdf
\begin_inset Quotes erd
\end_inset
`
\backslash
\begin_deeper
\layout LyX-Code
do ln -sf $a .
\backslash
\end_deeper
\layout LyX-Code
done
\layout Standard
After that, start SBCL and evaluate the following expressions:
\layout LyX-Code
> (require :asdf)
\layout LyX-Code
\layout LyX-Code
NIL
\layout LyX-Code
> (asdf:oos 'asdf:load-op :cells)
\layout LyX-Code
(some output will follow)
\layout Standard
If everything went right cells should be up and running.
\layout Section
Our first cells program
\layout Subsection
The program
\layout Standard
Write the following piece of code in a file named hello-cells.lisp:
\layout LyX-Code
(defmodel hello-cells ()
\layout LyX-Code
((num :accessor num :initarg :num :initform (c-in 0))
\layout LyX-Code
(square-num :accessor square-num
\layout LyX-Code
:initform (c? (* (num self) (num self))))))
\layout LyX-Code
\layout LyX-Code
(defun hello ()
\layout LyX-Code
(let ((h (make-instance 'hello-cells)))
\layout LyX-Code
(dolist (n '(10 20 30 40 50 60 60))
\layout LyX-Code
(setf (num h) n)
\layout LyX-Code
(format t "num is ~a and square-num is ~a~%" (num h) (square-num h)))))
\layout Standard
Now start the SBCL interpreter in the same directory and evaluate the following:
\layout LyX-Code
> (asdf:oos 'asdf:load-op :cells)
\layout LyX-Code
...
\layout LyX-Code
> (use-package :cells)
\layout LyX-Code
T
\layout LyX-Code
> (load
\begin_inset Quotes eld
\end_inset
hello-cells.lisp
\begin_inset Quotes erd
\end_inset
)
\layout LyX-Code
...
\layout LyX-Code
T
\layout LyX-Code
> (hello)
\layout LyX-Code
num is 10 and square-num is 100
\layout LyX-Code
num is 20 and square-num is 400
\layout LyX-Code
num is 30 and square-num is 900
\layout LyX-Code
num is 40 and square-num is 1600
\layout LyX-Code
num is 50 and square-num is 2500
\layout LyX-Code
num is 60 and square-num is 3600
\layout LyX-Code
num is 60 and square-num is 3600
\layout LyX-Code
NIL
\layout Standard
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
\layout LyX-Code
\begin_inset Formula $num*num=squarenum$
\end_inset
\layout Standard
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.
\layout Subsection
The program line-by-line
\layout Standard
Lets now analyze the program.
The very first line uses the construct defmodel:
\layout LyX-Code
(defmodel hello-cells ()
\layout Standard
defmodel is very similar to defclass and everything valid in a defclass
construct is valid within defmodel
\begin_inset Foot
collapsed false
\layout Standard
defmodel is a layer built on top of defclass
\end_inset
.
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.
\layout LyX-Code
((num :accessor num :initarg :num :initform (c-in 0))
\layout Standard
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
\begin_inset Quotes eld
\end_inset
input cells
\begin_inset Quotes erd
\end_inset
.
\layout LyX-Code
(square-num :accessor square-num
\layout LyX-Code
:initform (c? (* (num self) (num self))))))
\layout Standard
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:
\begin_inset Quotes eld
\end_inset
To calculate the value of square-num, evaluate the expression <expr>
\begin_inset Quotes erd
\end_inset
.
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
\begin_inset Quotes eld
\end_inset
ruled cells
\begin_inset Quotes erd
\end_inset
.
\layout LyX-Code
(let ((h (make-instance 'hello-cells)))
\layout Standard
Here we use the function (make-instance <model-name>
\emph on
args*
\emph default
), 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:
\layout LyX-Code
(let ((h (make-instance 'hello-cells :num (c-in 50))))
\layout Standard
Note that you
\emph on
must
\emph default
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.
\layout LyX-Code
(setf (num h) n)
\layout Standard
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.
\layout LyX-Code
(format t "num is ~a and square-num is ~a~%" (num h) (square-num h))
\layout Standard
Finally, we print the values of the two slots and discover that the value
of square-num is correctly the square of num.
\layout Standard
As a side note, you can reset the cells system by calling (cell-reset):
\layout LyX-Code
> (cells-reset)
\layout LyX-Code
NIL
\layout Standard
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.
\layout Section
The family system
\layout Standard
Objects whose type have been defined using defmodel can be organized in
families.
A family is a tree of model instances (
\emph on
not
\emph default
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,
\begin_inset Quotes eld
\end_inset
give me all the successors of type my-type
\begin_inset Quotes erd
\end_inset
.
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)
\begin_inset Foot
collapsed false
\layout Standard
In older releases of cells you had to use (md-value self) instead
\end_inset
.
The following example shows some of these things in action:
\layout LyX-Code
(defmodel node (family)
\layout LyX-Code
((val :initform (c-in nil) :initarg :val)))
\layout LyX-Code
\layout LyX-Code
(defun math-op-family ()
\layout LyX-Code
(let ((root
\layout LyX-Code
(make-instance
\layout LyX-Code
'node
\layout LyX-Code
:val (c? (apply #'+ (mapcar #'val (kids self))))
\layout LyX-Code
:kids
\layout LyX-Code
(c?
\layout LyX-Code
(the-kids
\layout LyX-Code
(make-kid 'node :md-name :n5 :val (c-in 5))
\layout LyX-Code
(make-kid
\layout LyX-Code
'node
\layout LyX-Code
:val (c? (apply #'* (mapcar #'val (kids self))))
\layout LyX-Code
:kids
\layout LyX-Code
(c?
\layout LyX-Code
(the-kids
\layout LyX-Code
(make-kid 'node :md-name :n7 :val (c-in 7))
\layout LyX-Code
(make-kid 'node :md-name :n9 :val (c-in 9))))))))))
\layout LyX-Code
(format t "value of the tree is ~a~%" (val root))
\layout LyX-Code
(setf (val (fm-other :n7 :starting root)) 10)
\layout LyX-Code
(format t "new value of the tree is ~a~%" (val root))))
\layout Standard
Write it in a file (in this case hello-cells.lisp) and load it:
\layout LyX-Code
> (load
\begin_inset Quotes eld
\end_inset
hello-cells.lisp
\begin_inset Quotes erd
\end_inset
)
\layout LyX-Code
T
\layout LyX-Code
> (math-op-family)
\layout LyX-Code
value of the tree is 68
\layout LyX-Code
new value of the tree is 95
\layout LyX-Code
NIL
\layout Standard
Lets' see the most important parts of the program:
\layout LyX-Code
(defmodel node (family)
\layout LyX-Code
((val :initform (c-in nil) :initarg :val)))
\layout Standard
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.
\layout LyX-Code
(make-instance
\layout LyX-Code
'node
\layout LyX-Code
:val (c? (apply #'+ (mapcar #'val (kids self))))
\layout Standard
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).
\layout LyX-Code
:kids
\layout LyX-Code
(c?
\layout LyX-Code
(the-kids
\layout Standard
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.
\layout LyX-Code
(make-kid 'node :md-name :n5 :val (c-in 5))
\layout Standard
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.
\layout LyX-Code
(make-kid
\layout LyX-Code
'node
\layout LyX-Code
:val (c? (apply #'* (mapcar #'val (kids self))))
\layout LyX-Code
:kids
\layout LyX-Code
(c?
\layout LyX-Code
(the-kids
\layout LyX-Code
(make-kid 'node :md-name :n7 :val (c-in 7))
\layout LyX-Code
(make-kid 'node :md-name :n9 :val (c-in 9)))))
\layout Standard
The second child of the main node has two children and its value is the
product of their values.
\layout LyX-Code
(format t "value of the tree is ~a~%" (val root))
\layout LyX-Code
(setf (val (fm-other :n7 :starting root)) 10)
\layout LyX-Code
(format t "new value of the tree is ~a~%" (val root))))
\layout Standard
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.
\layout Section
Defining an observer
\layout Standard
Cells lets you define a function to execute immediately after a c-in slot
is modified.
This function is called an
\begin_inset Quotes eld
\end_inset
observer
\begin_inset Quotes erd
\end_inset
.
To define it, use the defobserver construct:
\layout LyX-Code
(defobserver <slot-name> (&optional (<self> self)
\layout LyX-Code
(<new-value> old-value)
\layout LyX-Code
(<old-value> new-value)
\layout LyX-Code
(<old-value-boundp> old-value-boundp))
\layout LyX-Code
<function-body>)
\layout Standard
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.
\layout Standard
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:
\layout LyX-Code
(defobserver num ((self hello-cells))
\layout LyX-Code
(format t
\begin_inset Quotes eld
\end_inset
new value of num is: ~a~%
\begin_inset Quotes erd
\end_inset
new-value))
\layout Standard
Now reload the file and try running (hello) again:
\layout LyX-Code
> (load
\begin_inset Quotes eld
\end_inset
hello-cells.lisp
\begin_inset Quotes erd
\end_inset
)
\layout LyX-Code
T
\layout LyX-Code
> (hello)
\layout LyX-Code
new value of num is: 0
\layout LyX-Code
new value of num is: 10
\layout LyX-Code
num is 10 and square-num is 100
\layout LyX-Code
new value of num is: 20
\layout LyX-Code
num is 20 and square-num is 400
\layout LyX-Code
new value of num is: 30
\layout LyX-Code
num is 30 and square-num is 900
\layout LyX-Code
new value of num is: 40
\layout LyX-Code
num is 40 and square-num is 1600
\layout LyX-Code
new value of num is: 50
\layout LyX-Code
num is 50 and square-num is 2500
\layout LyX-Code
new value of num is: 60
\layout LyX-Code
num is 60 and square-num is 3600
\layout LyX-Code
num is 60 and square-num is 3600
\layout LyX-Code
NIL
\layout Standard
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!
\layout Standard
Now look at the following piece of code:
\layout LyX-Code
(defmodel str-model ()
\layout LyX-Code
((str :accessor str :initform (c-in "") :initarg :str)
\layout LyX-Code
(rev-str :accessor rev-str :initform (c? (reverse (str self))))))
\layout LyX-Code
\layout LyX-Code
(defobserver str ()
\layout LyX-Code
(format t "changed!~%"))
\layout LyX-Code
\layout LyX-Code
(defun try-str-model ()
\layout LyX-Code
(let ((s (make-instance 'str-model)))
\layout LyX-Code
(dolist (l `("Hello!" "Bye"
\layout LyX-Code
,(concatenate 'string "By" "e") "!olleH"))
\layout LyX-Code
(setf (str s) l)
\layout LyX-Code
(format t "str is
\backslash
"~a
\backslash
", rev-str is
\backslash
"~a
\backslash
"~%"
\layout LyX-Code
(str s) (rev-str s)))))
\layout Standard
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):
\layout LyX-Code
> (load
\begin_inset Quotes eld
\end_inset
hello-cells.lisp
\begin_inset Quotes erd
\end_inset
)
\layout LyX-Code
T
\layout LyX-Code
> (try-str-model)
\layout LyX-Code
changed!
\layout LyX-Code
changed!
\layout LyX-Code
str is "Hello!", rev-str is "!olleH"
\layout LyX-Code
changed!
\layout LyX-Code
str is "Bye", rev-str is "eyB"
\layout LyX-Code
changed!
\layout LyX-Code
str is "Bye", rev-str is "eyB"
\layout LyX-Code
changed!
\layout LyX-Code
str is "!olleH", rev-str is "Hello!"
\layout LyX-Code
NIL
\layout Standard
The reversed string is calculated
\emph on
every
\emph default
time we set (str s), even when we're changing it from
\begin_inset Quotes eld
\end_inset
Bye
\begin_inset Quotes erd
\end_inset
to
\begin_inset Quotes eld
\end_inset
Bye
\begin_inset Quotes erd
\end_inset
.
But
\begin_inset Quotes eld
\end_inset
Bye
\begin_inset Quotes erd
\end_inset
and
\begin_inset Quotes eld
\end_inset
Bye
\begin_inset Quotes erd
\end_inset
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
\layout LyX-Code
`("Hello!" "Bye" ,(concatenate 'string "By" "e") "!olleH")
\layout Standard
to
\layout LyX-Code
`("Hello!" "Bye" "Bye" "!olleH")
\layout Standard
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:
\layout LyX-Code
(str :accessor str :initform (c-in "") :initarg :str
\layout LyX-Code
:unchanged-if #'equal)
\layout Standard
Now we get the same expected result on any implementation:
\layout LyX-Code
changed!
\layout LyX-Code
changed!
\layout LyX-Code
str is "Hello!", rev-str is "!olleH"
\layout LyX-Code
changed!
\layout LyX-Code
str is "Bye", rev-str is "eyB"
\layout LyX-Code
str is "Bye", rev-str is "eyB"
\layout LyX-Code
changed!
\layout LyX-Code
str is "!olleH", rev-str is "Hello!"
\layout LyX-Code
NIL
\layout Standard
The equality function must accept two values: the new value of the slot
and the old one.
\layout Section
Lazy cells
\layout Standard
Ruled cells are evaluated, as we have already seen, at instance creation
time and after dependent cells change.
However, you may want to
\emph on
not
\emph default
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:
\layout Enumerate
: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.
\layout Enumerate
: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).
\layout Enumerate
:always this isn't evaluated/observed until read, and not reevaluated until
read after a dependency changes.
\layout Standard
There are two ways in which a cell can be lazy: by not being evaluated immediate
ly 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:
\layout LyX-Code
(defmodel lazy-test ()
\layout LyX-Code
((lazy-1 :accessor lazy-1 :initform (c-formula (:lazy :once-asked)
\layout LyX-Code
(append (val self) (list '!!))))
\layout LyX-Code
(lazy-2 :accessor lazy-2 :initform (c_? (val self)))
\layout LyX-Code
(lazy-3 :accessor lazy-3 :initform (c?_ (reverse (val self))))
\layout LyX-Code
(val :accessor val :initarg :val :initform (c-in nil))))
\layout LyX-Code
\layout LyX-Code
(defobserver lazy-1 ()
\layout LyX-Code
(format t "evaluating lazy-1!~%"))
\layout LyX-Code
\layout LyX-Code
(defobserver lazy-2 ()
\layout LyX-Code
(format t "evaluating lazy-2!~%"))
\layout LyX-Code
\layout LyX-Code
(defobserver lazy-3 ()
\layout LyX-Code
(format t "evaluating lazy-3!~%"))
\layout LyX-Code
\layout LyX-Code
(defun print-lazies (l)
\layout LyX-Code
(format t "Printing all the values:~%")
\layout LyX-Code
(format t "lazy-3: ~a~%" (lazy-3 l))
\layout LyX-Code
(format t "lazy-2: ~a~%" (lazy-2 l))
\layout LyX-Code
(format t "lazy-1: ~a~%" (lazy-1 l)))
\layout LyX-Code
\layout LyX-Code
(defun try-lazies ()
\layout LyX-Code
(let ((l (make-instance 'lazy-test :val (c-in '(Im very lazy!)))))
\layout LyX-Code
(format t "Initialization finished~%")
\layout LyX-Code
(print-lazies l)
\layout LyX-Code
(format t "Changing val~%")
\layout LyX-Code
(setf (val l) '(who will be evaluated?))
\layout LyX-Code
(print-lazies l)))
\layout Standard
As usual, load it and run it:
\layout LyX-Code
> (load
\begin_inset Quotes eld
\end_inset
hello-cells.lisp
\begin_inset Quotes erd
\end_inset
)
\layout LyX-Code
T
\layout LyX-Code
> (try-lazies)
\layout LyX-Code
evaluating lazy-1!
\layout LyX-Code
Initialization finished
\layout LyX-Code
Printing all the values:
\layout LyX-Code
evaluating lazy-3!
\layout LyX-Code
lazy-3: (LAZY! VERY IM)
\layout LyX-Code
evaluating lazy-2!
\layout LyX-Code
lazy-2: (IM VERY LAZY!)
\layout LyX-Code
lazy-1: (IM VERY LAZY! !!)
\layout LyX-Code
Changing val
\layout LyX-Code
evaluating lazy-2!
\layout LyX-Code
Printing all the values:
\layout LyX-Code
evaluating lazy-3!
\layout LyX-Code
lazy-3: (EVALUATED? BE WILL WHO)
\layout LyX-Code
lazy-2: (WHO WILL BE EVALUATED?)
\layout LyX-Code
evaluating lazy-1!
\layout LyX-Code
lazy-1: (WHO WILL BE EVALUATED? !!)
\layout LyX-Code
NIL
\layout Standard
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-evaluat
ed 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.
\layout Standard
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
\begin_inset Quotes eld
\end_inset
Functions & macros reference
\begin_inset Quotes erd
\end_inset
section).
\layout Section
Drifters
\layout Standard
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:
\layout LyX-Code
(defmodel counter ()
\layout LyX-Code
((how-many :accessor how-many
\layout LyX-Code
:initform (c...
(0)
\layout LyX-Code
(length (^current-elems))))
\layout LyX-Code
(current-elems :accessor current-elems
\layout LyX-Code
:initform (c-in nil))))
\layout LyX-Code
\layout LyX-Code
(defun try-counter ()
\layout LyX-Code
(let ((m (make-instance 'counter)))
\layout LyX-Code
(dolist (l '((1 2 3) (4 5) (1 2 3 4)))
\layout LyX-Code
(setf (current-elems m) l)
\layout LyX-Code
(format t "current elements: ~{~a ~}~%" (current-elems m))
\layout LyX-Code
(format t "~a elements seen so far~%" (how-many m)))))
\layout Standard
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:
\layout LyX-Code
> (load
\begin_inset Quotes eld
\end_inset
hello-cells.lisp
\begin_inset Quotes erd
\end_inset
)
\layout LyX-Code
T
\layout LyX-Code
> (try-counter)
\layout LyX-Code
elements: 1 2 3
\layout LyX-Code
3 elements seen so far
\layout LyX-Code
elements: 4 5
\layout LyX-Code
5 elements seen so far
\layout LyX-Code
elements: 1 2 3 4
\layout LyX-Code
9 elements seen so far
\layout LyX-Code
NIL
\layout Standard
The important passage in the code is the initialization of how-many:
\layout LyX-Code
(c...
(0)
\layout LyX-Code
(length (^current-elems)))
\layout Standard
(^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.
\layout Section
Cyclic dependencies
\layout Standard
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:
\layout LyX-Code
(defmodel cycle ()
\layout LyX-Code
((cycle-a :accessor cycle-a :initform (c-in nil))
\layout LyX-Code
(cycle-b :accessor cycle-b :initform (c-in nil))))
\layout LyX-Code
\layout LyX-Code
(defobserver cycle-a ()
\layout LyX-Code
(setf (cycle-b self) new-value))
\layout LyX-Code
\layout LyX-Code
(defobserver cycle-b ()
\layout LyX-Code
(setf (cycle-a self) new-value))
\layout LyX-Code
\layout LyX-Code
(defun try-cycle ()
\layout LyX-Code
(let ((m (make-instance 'cycle)))
\layout LyX-Code
(setf (cycle-a m) '(? !))
\layout LyX-Code
(format t "~a and ~a" (cycle-a m) (cycle-b m))))
\layout Standard
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:
\layout LyX-Code
> (load
\begin_inset Quotes eld
\end_inset
hello-cells.lisp
\begin_inset Quotes erd
\end_inset
)
\layout LyX-Code
T
\layout LyX-Code
> (try-cycle)
\layout LyX-Code
SETF of <2:A CYCLE-B/NIL = NIL> must be deferred by wrapping code in WITH-INTEGR
ITY
\layout LyX-Code
[Condition of type SIMPLE-ERROR]
\layout Standard
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
\layout LyX-Code
(defobserver cycle-a ()
\layout LyX-Code
(setf (cycle-b self) new-value))
\layout Standard
to
\layout LyX-Code
(defobserver cycle-a ()
\layout LyX-Code
(with-integrity (:change)
\layout LyX-Code
(setf (cycle-b self) new-value)))
\layout Standard
and
\layout LyX-Code
(defobserver cycle-b ()
\layout LyX-Code
(setf (cycle-a self) new-value))
\layout Standard
to
\layout LyX-Code
(defobserver cycle-b ()
\layout LyX-Code
(with-integrity (:change)
\layout LyX-Code
(setf (cycle-a self) new-value)))
\layout Standard
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.
\layout LyX-Code
> (cells-reset)
\layout LyX-Code
NIL
\layout LyX-Code
> (load
\begin_inset Quotes eld
\end_inset
hello-cells.lisp
\begin_inset Quotes erd
\end_inset
)
\layout LyX-Code
T
\layout LyX-Code
> (try-cycle)
\layout LyX-Code
(? !) and (? !)
\layout LyX-Code
NIL
\layout Section
Synapses
\layout Subsection
Built-in synapses
\layout Standard
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
\begin_inset Quotes eld
\end_inset
clock
\begin_inset Quotes erd
\end_inset
that changes only after a minimal amount of time:
\layout LyX-Code
(defmodel syn-time ()
\layout LyX-Code
((current-time :accessor current-time :initarg :current-time
\layout LyX-Code
:initform (c-in 0))
\layout LyX-Code
(wait-time :accessor wait-time :initarg :wait-time :initform (c-in 0))
\layout LyX-Code
(time-elapsed :accessor time-elapsed
\layout LyX-Code
:initform
\layout LyX-Code
(c?
\layout LyX-Code
(f-sensitivity :syn ((wait-time self))
\layout LyX-Code
(current-time self))))))
\layout LyX-Code
\layout LyX-Code
(defun try-syn-time ()
\layout LyX-Code
(let ((tm (make-instance 'syn-time :wait-time (c-in 2))))
\layout LyX-Code
(dotimes (n 10)
\layout LyX-Code
(format t "time +1~%")
\layout LyX-Code
(incf (current-time tm))
\layout LyX-Code
(format t "time-elapsed is ~a~%" (time-elapsed tm)))))
\layout Standard
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
\layout LyX-Code
(f-sensitivity :syn ((wait-time self))
\layout LyX-Code
(current-time self))
\layout Standard
Here we create a synapse named :syn.
It is of type f-sensitivity: (current-time self) is evaluated
\emph on
always
\emph default
, 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 propagate
d.
The expected result then will be:
\layout LyX-Code
> (load
\begin_inset Quotes eld
\end_inset
hello-cells.lisp
\begin_inset Quotes erd
\end_inset
)
\layout LyX-Code
T
\layout LyX-Code
> (try-syn-time)
\layout LyX-Code
time +1
\layout LyX-Code
time-elapsed is 0
\layout LyX-Code
time +1
\layout LyX-Code
time-elapsed is 2
\layout LyX-Code
time +1
\layout LyX-Code
time-elapsed is 2
\layout LyX-Code
time +1
\layout LyX-Code
time-elapsed is 4
\layout LyX-Code
time +1
\layout LyX-Code
time-elapsed is 4
\layout LyX-Code
time +1
\layout LyX-Code
time-elapsed is 6
\layout LyX-Code
time +1
\layout LyX-Code
time-elapsed is 6
\layout LyX-Code
time +1
\layout LyX-Code
time-elapsed is 8
\layout LyX-Code
time +1
\layout LyX-Code
time-elapsed is 8
\layout LyX-Code
time +1
\layout LyX-Code
time-elapsed is 10
\layout LyX-Code
NIL
\layout Standard
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.
\layout Subsection
Defining your own
\layout Standard
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.
\layout LyX-Code
(with-synapse <id> (&rest <vars>)
\layout LyX-Code
<body>)
\layout Standard
<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:
\layout LyX-Code
(defmodel my-syn-test ()
\layout LyX-Code
((num :accessor num :initform (c-in 0))
\layout LyX-Code
(odd-num :reader odd-num
\layout LyX-Code
:initform (c?
\layout LyX-Code
(with-synapse :odd-syn ()
\layout LyX-Code
(if (oddp (^num))
\layout LyX-Code
(values (^num) :propagate))
\layout LyX-Code
(values nil :no-propagate)))))))
\newline
\newline
(defobserver odd-num ()
\layout LyX-Code
(when old-value-boundp
\layout LyX-Code
(format t "Propagated!~%")))
\newline
\newline
(defun try-my-syn ()
\layout LyX-Code
(let ((m (make-instance 'my-syn-test)))
\layout LyX-Code
(dolist (n '(1 2 4 5 7 11 12 14 16 15))
\layout LyX-Code
(format t "Setting num to ~a~%" n)
\layout LyX-Code
(setf (num m) n)
\layout LyX-Code
(format t "odd-num is ~a~%" (odd-num m)))))
\layout Standard
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:
\layout LyX-Code
> (load
\begin_inset Quotes eld
\end_inset
hello-cells.lisp
\begin_inset Quotes erd
\end_inset
)
\layout LyX-Code
T
\layout LyX-Code
> (try-my-syn)
\layout LyX-Code
Setting num to 1
\layout LyX-Code
Propagated!
\layout LyX-Code
odd-num is 1
\layout LyX-Code
Setting num to 2
\layout LyX-Code
odd-num is 1
\layout LyX-Code
Setting num to 4
\layout LyX-Code
odd-num is 1
\layout LyX-Code
Setting num to 5
\layout LyX-Code
Propagated!
\layout LyX-Code
odd-num is 5
\layout LyX-Code
Setting num to 7
\layout LyX-Code
Propagated!
\layout LyX-Code
odd-num is 7
\layout LyX-Code
Setting num to 11
\layout LyX-Code
Propagated!
\layout LyX-Code
odd-num is 11
\layout LyX-Code
Setting num to 12
\layout LyX-Code
odd-num is 11
\layout LyX-Code
Setting num to 14
\layout LyX-Code
odd-num is 11
\layout LyX-Code
Setting num to 16
\layout LyX-Code
odd-num is 11
\layout LyX-Code
Setting num to 15
\layout LyX-Code
Propagated!
\layout LyX-Code
odd-num is 15
\layout LyX-Code
NIL
\layout Standard
You can see that odd-num changes only when we return :propagate
\begin_inset Foot
collapsed false
\layout Standard
We could have returned any other value.
The only requirement to propagate is to return something different from
:no-propagate.
\end_inset
.
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.
\layout Section
Example: playing sudoku
\layout Standard
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:
\layout LyX-Code
(defparameter *all-values* '(1 2 3 4 5 6 7 8 9))
\layout LyX-Code
(defparameter *row-len* 9)
\layout LyX-Code
(defparameter *sq-size* 3)
\layout LyX-Code
(defparameter *col-len* 9)
\layout Standard
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:
\layout LyX-Code
(defparameter *board*
\layout LyX-Code
#(#(? ? ? ? ? ? ? ? ?)
\layout LyX-Code
#(? ? ? ? ? ? ? ? ?)
\layout LyX-Code
#(? ? ? ? ? ? ? ? ?)
\layout LyX-Code
#(? ? ? ? ? ? ? ? ?)
\layout LyX-Code
#(? ? ? ? ? ? ? ? ?)
\layout LyX-Code
#(? ? ? ? ? ? ? ? ?)
\layout LyX-Code
#(? ? ? ? ? ? ? ? ?)
\layout LyX-Code
#(? ? ? ? ? ? ? ? ?)
\layout LyX-Code
#(? ? ? ? ? ? ? ? ?)))
\layout Standard
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.
\layout LyX-Code
(defmodel square-group ()
\layout LyX-Code
((constraining :initform (c-in nil) :initarg :constraining
\layout LyX-Code
:accessor constraining)))
\newline
\newline
(defmodel square ()
\layout LyX-Code
((group :accessor group :initform (c-in nil))
\layout LyX-Code
(exact-val :accessor exact-val :initform (c-in nil) :initarg :exact-val)
\layout LyX-Code
(possible-vals
\layout LyX-Code
:accessor possible-vals
\layout LyX-Code
:initform
\layout LyX-Code
(c?
\layout LyX-Code
(when (and (^group) (not (^exact-val)))
\layout LyX-Code
(let ((c (constraining (^group))))
\layout LyX-Code
;; a value must not be the same of the constraining
\layout LyX-Code
(remove-if-not
\layout LyX-Code
#'(lambda (v)
\layout LyX-Code
(every
\layout LyX-Code
#'(lambda (x)
\layout LyX-Code
(not (eql v (exact-val x))))
\layout LyX-Code
c))
\layout LyX-Code
*all-values*)))))))
\newline
\newline
(defun make-square (x)
\layout LyX-Code
(make-instance 'square :exact-val (c-in (if (eql x '?) nil x))))
\newline
\newline
(defmodel board ()
\layout LyX-Code
((complete :accessor complete
\layout LyX-Code
:initform
\layout LyX-Code
(c?_
\layout LyX-Code
(every #'(lambda (x) (every #'exact-val x)) (^squares))))
\layout LyX-Code
(squares :accessor squares :initarg :squares)))
\newline
\newline
(defmethod print-object ((self board) out)
\layout LyX-Code
(dotimes (r *col-len*)
\layout LyX-Code
(dotimes (c *row-len*)
\layout LyX-Code
(format out "~a " (exact-val (at (^squares) r c))))
\layout LyX-Code
(format out "~%")))
\layout Standard
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.
\layout LyX-Code
(defun at (board r c)
\layout LyX-Code
(elt (elt board r) c))
\newline
\newline
(defun next-pos (pos)
\layout LyX-Code
\begin_inset Quotes eld
\end_inset
next position in the board.
search only forward.
\layout LyX-Code
return NIL if the board is finished
\begin_inset Quotes erd
\end_inset
\layout LyX-Code
(destructuring-bind (r c) pos
\layout LyX-Code
(if (= c (1- *row-len*))
\layout LyX-Code
(if (= r (1- *col-len*))
\layout LyX-Code
nil
\layout LyX-Code
(list (1+ r) 0))
\layout LyX-Code
(list r (1+ c)))))
\newline
\newline
(defun next-to-try (board pos)
\layout LyX-Code
\begin_inset Quotes eld
\end_inset
find next position without a value searching forward.
\layout LyX-Code
return NIL if there is none
\begin_inset Quotes erd
\end_inset
\layout LyX-Code
(let ((pos (next-pos pos)))
\layout LyX-Code
(when pos
\layout LyX-Code
(let ((s (at board (first pos) (second pos))))
\layout LyX-Code
(if (exact-val s)
\layout LyX-Code
(next-to-try board pos)
\layout LyX-Code
pos)))))
\layout Standard
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.
\layout LyX-Code
(defun make-groups (squares)
\layout LyX-Code
(dotimes (r *col-len*)
\layout LyX-Code
(dotimes (c *row-len*)
\layout LyX-Code
(setf (group (at squares r c))
\layout LyX-Code
(make-instance 'square-group
\layout LyX-Code
:constraining
\layout LyX-Code
(c-in
\layout LyX-Code
(delete-duplicates
\layout LyX-Code
(nconc
\layout LyX-Code
(nth-col squares c)
\layout LyX-Code
(nth-row squares r)
\layout LyX-Code
(nth-block squares r c)))))))))
\newline
\newline
(defun nth-row (board n)
\layout LyX-Code
"return row n of board"
\layout LyX-Code
(coerce (elt board n) 'list))
\newline
\newline
(defun nth-col (board n)
\layout LyX-Code
"return column n of board"
\layout LyX-Code
(map 'list #'(lambda (x) (elt x n)) board))
\newline
\newline
(defun nth-block (board r c)
\layout LyX-Code
"return list of element in the same block of (at board r c)"
\layout LyX-Code
(let ((upper-left-r (* *sq-size* (floor (/ r *sq-size*))))
\layout LyX-Code
(upper-left-c (* *sq-size* (floor (/ c *sq-size*)))))
\layout LyX-Code
(apply #'concatenate 'list
\layout LyX-Code
(map 'list #'(lambda (x)
\layout LyX-Code
(subseq x upper-left-c
\layout LyX-Code
(+ upper-left-c *sq-size*)))
\layout LyX-Code
(subseq board upper-left-r
\layout LyX-Code
(+ upper-left-r *sq-size*))))))
\layout Standard
To create the board we map the input board and for every position we create
a square.
Then we build all the groups.
\layout LyX-Code
(defun make-board (b)
\layout LyX-Code
(let ((b (make-instance
\layout LyX-Code
'board
\layout LyX-Code
:squares
\layout LyX-Code
(c-in
\layout LyX-Code
(map 'vector #'(lambda (x) (map 'vector #'make-square x))
b)))))
\layout LyX-Code
(make-groups (squares b))
\layout LyX-Code
b))
\layout Standard
The following code looks for a solution, trying all the possible combinations.
Thanks to how we defined possible-vals, impossible combinations are never
tried.
\layout LyX-Code
(defun search-solution (b &optional (next
\layout LyX-Code
(next-to-try (squares b) (list 0 -1))))
\layout LyX-Code
(if next
\layout LyX-Code
(let ((s (at (squares b) (first next) (second next))))
\layout LyX-Code
(or (some ; find the first of the possible values that yields a
solution
\layout LyX-Code
#'(lambda (x)
\layout LyX-Code
(setf (exact-val s) x) ; try it
\layout LyX-Code
(search-solution b (next-to-try (squares b) next)))
\layout LyX-Code
(possible-vals s))
\layout LyX-Code
;; couldn't find any solution: reset the square and return
\layout LyX-Code
;; NIL to indicate failure
\layout LyX-Code
(setf (exact-val s) nil)))
\layout LyX-Code
;; tried all the positions: have we completed the board?
\layout LyX-Code
(complete b)))
\layout Standard
Finally the main function: it accepts an input board and prints a solution.
\layout LyX-Code
(defun sudoku (the-board)
\layout LyX-Code
(let ((b (make-board the-board)))
\layout LyX-Code
(search-solution b)
\layout LyX-Code
(format t "Solution:~%~a~%" b)))
\layout Standard
Save it in a file named
\begin_inset Quotes eld
\end_inset
sudoku.lisp
\begin_inset Quotes erd
\end_inset
and try it on the empty board:
\layout LyX-Code
> (load
\begin_inset Quotes eld
\end_inset
sudoku.lisp
\begin_inset Quotes erd
\end_inset
)
\layout LyX-Code
T
\layout LyX-Code
> (sudoku *board*)
\layout LyX-Code
Solution:
\layout LyX-Code
1 2 3 4 5 6 7 8 9
\layout LyX-Code
4 5 6 7 8 9 1 2 3
\layout LyX-Code
7 8 9 1 2 3 4 5 6
\layout LyX-Code
2 1 4 3 6 5 8 9 7
\layout LyX-Code
3 6 5 8 9 7 2 1 4
\layout LyX-Code
8 9 7 2 1 4 3 6 5
\layout LyX-Code
5 3 1 6 4 2 9 7 8
\layout LyX-Code
6 4 2 9 7 8 5 3 1
\layout LyX-Code
9 7 8 5 3 1 6 4 2
\layout LyX-Code
NIL
\layout Standard
It does find a solution, but it takes quite a while to print it:
\layout LyX-Code
> (time (sudoku *board*))
\layout LyX-Code
Solution:
\layout LyX-Code
1 2 3 4 5 6 7 8 9
\layout LyX-Code
4 5 6 7 8 9 1 2 3
\layout LyX-Code
7 8 9 1 2 3 4 5 6
\layout LyX-Code
2 1 4 3 6 5 8 9 7
\layout LyX-Code
3 6 5 8 9 7 2 1 4
\layout LyX-Code
8 9 7 2 1 4 3 6 5
\layout LyX-Code
5 3 1 6 4 2 9 7 8
\layout LyX-Code
6 4 2 9 7 8 5 3 1
\layout LyX-Code
9 7 8 5 3 1 6 4 2
\newline
\newline
Evaluation took:
\layout LyX-Code
2.476 seconds of real time
\layout LyX-Code
2.388149 seconds of user run time
\layout LyX-Code
0.076004 seconds of system run time
\layout LyX-Code
[Run times include 0.176 seconds GC run time.]
\layout LyX-Code
0 calls to %EVAL
\layout LyX-Code
0 page faults and
\layout LyX-Code
155,622,072 bytes consed.
\layout LyX-Code
NIL
\layout Standard
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 is 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:
\layout LyX-Code
> (load
\begin_inset Quotes eld
\end_inset
sudoku.lisp
\begin_inset Quotes erd
\end_inset
)
\layout LyX-Code
T
\layout LyX-Code
> (time (sudoku *board*))
\layout LyX-Code
Solution:
\layout LyX-Code
1 2 3 4 5 6 7 8 9
\layout LyX-Code
4 5 6 7 8 9 1 2 3
\layout LyX-Code
7 8 9 1 2 3 4 5 6
\layout LyX-Code
2 1 4 3 6 5 8 9 7
\layout LyX-Code
3 6 5 8 9 7 2 1 4
\layout LyX-Code
8 9 7 2 1 4 3 6 5
\layout LyX-Code
5 3 1 6 4 2 9 7 8
\layout LyX-Code
6 4 2 9 7 8 5 3 1
\layout LyX-Code
9 7 8 5 3 1 6 4 2
\newline
\newline
Evaluation took:
\layout LyX-Code
0.181 seconds of real time
\layout LyX-Code
0.16001 seconds of user run time
\layout LyX-Code
0.020001 seconds of system run time
\layout LyX-Code
[Run times include 0.012 seconds GC run time.]
\layout LyX-Code
0 calls to %EVAL
\layout LyX-Code
0 page faults and
\layout LyX-Code
9,517,528 bytes consed.
\layout LyX-Code
NIL
\layout Standard
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.
\layout Standard
One important thing to note about this example is that we
\emph on
had
\emph default
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.
\layout Section
Functions & macros reference
\layout Standard
Here follows a quick reference of the main functions and macros.
\layout Subsection
Main
\layout List
\labelwidthstring 00.00.0000
defmodel
\layout LyX-Code
(defmodel <model-name> (<superclass>*)
\layout LyX-Code
(<slot-definition>*)
\layout LyX-Code
<other-optional-arguments>)
\layout Standard
(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:
\layout Enumerate
:cell nil the slot will be ignored by the constraints-handling system
\layout Enumerate
: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.
\layout Standard
For every cell's accessor defmodel creates a macro ^<accessor-name> that
you can use as a shortcut for (<accessor-name> self).
\layout List
\labelwidthstring 00.00.0000
c-in
\layout LyX-Code
(c-in <expr>)
\layout Standard
(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.
\layout List
\labelwidthstring 00.00.0000
c-input
\layout LyX-Code
(c-input (&rest args) &optional value)
\layout Standard
(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.
\layout List
\labelwidthstring 00.00.0000
c?
\layout LyX-Code
(c?
\layout LyX-Code
<body>)
\layout Standard
(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
\layout List
\labelwidthstring 00.00.0000
c?+n
\layout LyX-Code
(c?+n
\layout LyX-Code
<body>)
\layout Standard
(Macro) Creates a ruled cell whose value can be setted.
\layout List
\labelwidthstring 00.00.0000
c?once
\layout LyX-Code
(c?once
\layout LyX-Code
<body>)
\layout Standard
(Macro) Creates a ruled cell that gets evaluated only once at initialization
time.
\layout List
\labelwidthstring 00.00.0000
c?1
\layout LyX-Code
(c?1
\layout LyX-Code
<body>)
\layout Standard
(Macro) Nickname for c?once.
\layout List
\labelwidthstring 00.00.0000
c_?
\layout LyX-Code
(c_?
\layout LyX-Code
<body>)
\layout Standard
(Macro) Creates a lazy ruled cell slot of type :until-asked.
\layout List
\labelwidthstring 00.00.0000
c?_
\layout LyX-Code
(c?_
\layout LyX-Code
<body>)
\layout Standard
(Macro) Creates a lazy ruled cell slot of type :always.
\layout List
\labelwidthstring 00.00.0000
c_1
\layout LyX-Code
(c_1
\layout LyX-Code
<body>)
\layout Standard
(Macro) Creates a lazy cell that gets evaluated only once.
\layout List
\labelwidthstring 00.00.0000
c...
\layout LyX-Code
(c...
(<initial-value>)
\layout LyX-Code
<body>)
\layout Standard
(Macro) Creates a drifter cell with initial value <initial-value>.
\layout List
\labelwidthstring 00.00.0000
c-formula
\layout LyX-Code
(c-formula (<options>)
\layout LyX-Code
<body>)
\layout Standard
(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.
\layout List
\labelwidthstring 00.00.0000
defobserver
\layout LyX-Code
(defobserver <slot-name> (&optional (<self> self)
\layout LyX-Code
(<new-value> old-value)
\layout LyX-Code
(<old-value> new-value)
\layout LyX-Code
(<old-value-boundp> old-value-boundp))
\layout LyX-Code
<function-body>)
\layout Standard
(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.
\layout List
\labelwidthstring 00.00.0000
with-integrity
\layout LyX-Code
(with-integrity (&optional <opcode> <defer-info>)
\layout LyX-Code
<body>)
\layout Standard
(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.
\layout List
\labelwidthstring 00.00.0000
without-c-dependency
\layout LyX-Code
(without-c-dependency
\layout LyX-Code
<body>)
\layout Standard
(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.
\layout Subsection
Family models
\layout Standard
The following only works for models that inherit from family.
\layout List
\labelwidthstring 00.00.0000
make-part
\layout LyX-Code
(make-part <md-name> <model-name> &rest <args>)
\layout Standard
(Function) Creates an instance of <model-name> with :md-name set to <md-name>.
<args> are passed to make-instance.
\layout List
\labelwidthstring 00.00.0000
mk-part
\layout LyX-Code
(mk-part <md-name> (<model-name>) &rest <args>)
\layout Standard
(Macro) Same as make-part, but sets the parent to self
\layout List
\labelwidthstring 00.00.0000
the-kids
\layout LyX-Code
(the-kids &rest <kids>)
\layout Standard
(Macro) Builds a list of kids.
<kids> may contain objects or nested lists of objects.
\layout List
\labelwidthstring 00.00.0000
make-kid
\layout LyX-Code
(make-kid <model-name> &rest <args>)
\layout Standard
(Macro) The same as (make-instance <model-name> <args> :fm-parent self).
\layout List
\labelwidthstring 00.00.0000
def-kid-slots
\layout LyX-Code
(def-kid-slots &rest <kids>)
\layout Standard
(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.
\layout List
\labelwidthstring 00.00.0000
kids
\layout LyX-Code
(kids <object>)
\layout Standard
(Method) Gives access to <object>'s children.
\layout List
\labelwidthstring 00.00.0000
kid1,kid2,last-kid
\layout LyX-Code
(kid1 <object>)
\layout LyX-Code
(kid2 <object>)
\layout LyX-Code
(last-kid <object>
\layout Standard
(Function) Gives access, respectively, to <object>'s first, second and last
child
\layout List
\labelwidthstring 00.00.0000
^k1,^k2,^k-last
\layout LyX-Code
(^k1)
\layout LyX-Code
(^k2)
\layout LyX-Code
(^k-last)
\layout Standard
(Macro) Shortcuts for (kid1 self), (kid2 self) and (last-kid self)
\layout List
\labelwidthstring 00.00.0000
fm-parent
\layout LyX-Code
(fm-parent &optional (<object> self))
\layout Standard
(Method) Gives access to <object>'s parent.
\layout List
\labelwidthstring 00.00.0000
fm-other
\layout LyX-Code
(fm-other <name> &optional (<starting-point> self))
\layout Standard
(Macro) Looks for an object named <name> within <starting-point>'s family.
\layout List
\labelwidthstring 00.00.0000
fm^
\layout LyX-Code
(fm^ <name> &optional (<starting-point> self))
\layout Standard
(Macro) Same as (fm-other <name> (fm-parent <starting-point>)), but doesn't
search <starting-point> and its children.
\layout List
\labelwidthstring 00.00.0000
fm-kid-typed
\layout LyX-Code
(fm-kid-typed <self> <type>)
\layout Standard
(Function) Finds the first <self>'s child whose type is <type>.
\layout List
\labelwidthstring 00.00.0000
fm-descendant-typed
\layout LyX-Code
(fm-descendant-typed <self> <type>)
\layout Standard
(Function) Finds the first descendant of <self> whose type is <type>.
\layout List
\labelwidthstring 00.00.0000
container
\layout LyX-Code
(container <object>)
\layout Standard
(Function) Gets <object>'s parent.
\layout List
\labelwidthstring 00.00.0000
container-typed
\layout LyX-Code
(container-typed <object> <type>)
\layout Standard
(Function) Gets <object>'s first ancestor of type <type>.
\layout List
\labelwidthstring 00.00.0000
upper
\layout LyX-Code
(upper <object> &optional (<type> t))
\layout Standard
(Function) Same as (container-typed <object> <type>).
\layout List
\labelwidthstring 00.00.0000
fm-ascendant-typed
\layout LyX-Code
(fm-ascendant-typed <parent> <type>)
\layout Standard
(Function) Gets the first ancestor of type <type>, searching from <parent>
included.
\layout List
\labelwidthstring 00.00.0000
fm-kid-named
\layout LyX-Code
(fm-kid-named <self> <name>)
\layout Standard
(Function) Gets <self>'s kids whose md-name is <name>.
\layout List
\labelwidthstring 00.00.0000
fm-ascendant-named
\layout LyX-Code
(fm-ascendant-named <self> <name>)
\layout Standard
(Function) Gets the first ancestor whose md-name is <name> starting from
<self> included.
\layout List
\labelwidthstring 00.00.0000
fm-descendant-named
\layout LyX-Code
(fm-descendant-named <self> <name> &key (<must-find> t))
\layout Standard
(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.
\layout List
\labelwidthstring 00.00.0000
not-to-be
\layout LyX-Code
(not-to-be <object>)
\layout Standard
(Function) Unregisters <object>.
\layout Subsection
Synapses
\layout List
\labelwidthstring 00.00.0000
f-sensitivity
\layout LyX-Code
(f-sensitivity <name> (<sensitivity> &optional <subtypename>)
\layout LyX-Code
<body>)
\layout Standard
(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.
\layout List
\labelwidthstring 00.00.0000
f-delta
\layout LyX-Code
(f-delta <name> (&key <sensitivity> (<type> 'number))
\layout LyX-Code
<body>)
\layout Standard
(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>.
\layout List
\labelwidthstring 00.00.0000
with-synapse
\layout LyX-Code
(with-synapse <syn-id> (<vars>)
\layout LyX-Code
<body>)
\layout Standard
(Macro) Creates a synapse.
<body> should return two multiple values, and when the second is :no-propagate,
the eventual change isn't propagated.
\layout Subsection
Misc
\layout List
\labelwidthstring 00.00.0000
cells-reset
\layout LyX-Code
(cells-reset)
\layout Standard
(Function) Resets the system.
\layout Section
Other resources
\layout Standard
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:
\begin_inset LatexCommand \htmlurl{http://common-lisp.net/cgi-bin/mailman/subscribe/cells-devel}
\end_inset
\layout Part
Cells-gtk
\layout Section
Introduction
\layout Subsection
Where's the GUI?
\layout Standard
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:
\layout Enumerate
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.
\layout Enumerate
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.
\layout Enumerate
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-fashioned
\begin_inset Foot
collapsed false
\layout Standard
There are ongoing efforts to use GTK and Cairo to bring to McCLIM a modern
look.
\end_inset
, and interfaces built with it are fundamentally different from the standard
widget-oriented way of doing GUIs these days, so it may not be what you
really want.
The biggest problem, though, is that CLIM is
\emph on
very
\emph default
complicated, and there is very little documentation to help you in the learning
process.
\layout Enumerate
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.
\layout Enumerate
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.
\layout Subsection
Cells-gtk
\layout Standard
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 tradition
al toolkits can be done in a more concise and
\emph on
localized
\emph default
way using ruled cells, input cells and observers.
\layout Section
Installation
\layout Standard
The installation of cells-gtk is similar to that of cells.
Before installing it you will need to install gtk+, a recent version of
CFFI and, of course, cells.
Before loading cells-gtk with ASDF, you may change its configuration to
enable some features that are disabled by default.
To do this, you need to uncomment some lines in cells-gtk/cells-gtk.asd
and gtk-ffi/gtk-ffi.asd.
For example, to be able to add widgets in the built-in dialogs you need
to uncomment the line
\layout LyX-Code
(pushnew :libcellsgtk *features*)
\layout Standard
from gtk-ffi/gtk-ffi.asd.
If during the installation your compiler complains about not being able
to load libcellsgtk, go in the directory gtk-ffi and type 'make' to recompile
libcellsgtk (to do so you must have installed gcc and the gtk+ headers).
To work with threads
\begin_inset Foot
collapsed false
\layout Standard
You also need to use (start-win <model> :terminate-on-close t)) instead
of (start-app <model>).
\end_inset
, you need to uncomment the line
\layout LyX-Code
(pushnew :cells-gtk-threads *features*)
\layout Standard
from cells-gtk/cells-gtk.asd.
\layout Section
A first application
\layout Standard
The following creates a window with a button labeled
\begin_inset Quotes eld
\end_inset
Hello, World!
\begin_inset Quotes erd
\end_inset
:
\layout LyX-Code
(defmodel my-app (gtk-app)
\layout LyX-Code
()
\layout LyX-Code
(:default-initargs
\layout LyX-Code
:md-name :app
\layout LyX-Code
:height 200
\layout LyX-Code
:width 300
\layout LyX-Code
:kids
\layout LyX-Code
(kids-list?
\layout LyX-Code
(mk-button :expand t :fill t :label "Hello, World!"))))
\layout LyX-Code
\layout LyX-Code
\layout LyX-Code
\the_end
You can’t perform that action at this time.