Is there a better way to store this?
John Thingstad
This game uses a binary deduction tree.
The thing is this tree needs to be stored to and loaded from disk. This
is a simple game and I don't want it to depend on external libraries like
object-store. I figure the best way to do this is to store the CLOS tree
as the code I would write to contruct the tree. That way I can just use
read to recontruct it. Never the less the code here looks a bit uggy at
least in (defmethod store ((item tree-node))).
Do you see a better way to do this?
(defmacro awhen (predicate &body body)
`(let ((it ,predicate))
(when it
,@body)))
;;; Commentary
;;;
;;; The data structure used is a binary deduction tree.
;;; From the tunk on down are questions.
;;; At the leaf nodes are animals.
;;; The deduction treee needs to set up a toxonometry so that
;;; it from a yes or no answers can deduce a unique animal.
;;; If it is not find it after traversing to the leafes
;;; it askes the user to same questions again.
;;; This makes the cursor travers to a leaf node of the tree.
;;; If there is already a animal there it askes for a
;;; question that will distinguish them.
(defclass item ()
())
(defclass question (item)
((question :accessor text :initarg :text)))
(defclass animal (item)
((animal :accessor species :initarg :species)))
(defclass tree ()
((root :accessor root :initarg :root :initform nil)
(cursor :accessor cursor :initform nil)))
(defclass tree-node (item)
((item :accessor item :initarg :item)
(left-child :accessor left-child :initarg :left-child :initform nil)
(right-child :accessor right-child :initarg :right-child :initform
nil)))
(defmethod initialize-instance :after ((item tree) &key &allow-other-keys)
(setf (slot-value item 'cursor) (slot-value item 'root)))
(defgeneric store (class stream))
(defmethod store ((item question) stream)
(print `(make-instance 'question :text ,(text item)) stream))
(defmethod store ((item animal) stream)
(print `(make-instance 'animal :species ,(species item)) stream))
(defmethod store ((item tree-node) stream)
(write-string "(make-instance 'tree-node " stream)
(write-string ":item " stream)
(store (item item) stream) (values)
(awhen (left-child item)
(write-string ":left-child " stream)
(store it stream))
(awhen (right-child item)
(write-string ":right-child " stream)
(store it stream))
(write-string ")" stream)
(values))
Pillsy
> I am writing a 'guess the animal' game for my Lisp book of games.
> This game uses a binary deduction tree.
> The thing is this tree needs to be stored to and loaded from disk. This
> is a simple game and I don't want it to depend on external libraries like
> object-store. I figure the best way to do this is to store the CLOS tree
> as the code I would write to contruct the tree. That way I can just use
> read to recontruct it.
It might be easier to make the tree out of conses or STRUCTURE-CLASS
instances, both of which can be printed readably?
STRUCTURE-CLASSes even support (single) inheritance and generic
function methods can specialize on them, in case you want to retain
that functionality.
Cheers,
Pillsy
John Thingstad
I have not made myself clear. In each of my games I try to use different
tecniques and different approaches. I want to use classes it is just the
way it stores itself I don't like. In particular I don't like write-
string and would have prefered princ.
Basically just one huge line. To pprint it would look nice but would
require the entire structure to be held in RAM and that is just to
wastfull. (Call me old fashioned, but I hate waste.)
Pascal J. Bourguignon
I would avoid using write-string to print something that will be read
back. Build a sexp, and print it. (Avoid pprint for serialization
since it's slower).
If you have really a lot of data, you could just write one "(" at the
start, and one ")" at the end, and in the middle print several sexps
in a loop (they'll be garbage collected once printed if it is meed).
Of course, this works better if you can linearize the data structure.
Happily, it is easy to put a tree in prefix or suffix form.
--
__Pascal Bourguignon__
Barry Margolin
Backquote is useful for this:
(defmethod store-expression ((item tree-node))
`(make-instance 'tree-node
:item ,(store-expression (item item))
,@(awhen (left-child item)
`(:left-child ,(store-expression it)))
,@(awhen (right-child item)
`(:right-child ,(store-expression it)))))
(defmethod store ((item tree-node) stream)
(prin1 (store-expression item) stream))
You might also want to look at PRINT-OBJECT methods.
--
Barry Margolin, bar...@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
Rob Warnock
+---------------
| I am writing a 'guess the animal' game for my Lisp book of games.
| This game uses a binary deduction tree.
| The thing is this tree needs to be stored to and loaded from disk.
In the "Guess the Animal" game included in the CLLIB subsection of
CLOCC[1], the data is stored as a simple tagged binary tree, that is:
(LIST* question-string if-yes-subtree if-no-subtree).
with leaves being subtrees that are strings [instead of conses], e.g.:
(defvar *animals-default-data*
'("Is it an insect" ("Can it sting" "a bee" . "a roach")
"Can it fly" "a duck" . "a penguin"))
That means that the data is *very* easy to write out and read back...
-Rob
[1] http://clocc.cvs.sourceforge.net/*checkout*/clocc/clocc/src/cllib/animals.lisp
-----
Rob Warnock <rp...@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
John Thingstad
> John Thingstad <jpt...@online.no> wrote: +---------------
> | I am writing a 'guess the animal' game for my Lisp book of games. |
> This game uses a binary deduction tree. | The thing is this tree needs
> to be stored to and loaded from disk. +---------------
>
> In the "Guess the Animal" game included in the CLLIB subsection of
> CLOCC[1], the data is stored as a simple tagged binary tree, that is:
>
> (LIST* question-string if-yes-subtree if-no-subtree).
>
> with leaves being subtrees that are strings [instead of conses], e.g.:
>
> (defvar *animals-default-data*
> '("Is it an insect" ("Can it sting" "a bee" . "a roach")
> "Can it fly" "a duck" . "a penguin"))
>
> That means that the data is *very* easy to write out and read back...
Agreed. It annoys me though that classes are just about the only thing
where what is printed can't be read back.I never really understood the
assymetry that there is a print-object but no read-object.
Also it's about the only object where structural equality (equalp)
doesn't work.
This is what makes CLOS the problem rather than the solution. Guess all
this customization comes at a price.
I would have liked a simple-class metaclass (alla simple array) where the
two propositions were furfilled. Maybe I'll write one..
Vassil Nikolov
On Sat, 07 Nov 2009 06:44:34 -0600, John Thingstad <jpt...@online.no> said:
> ...
> there is a print-object but no read-object.
There is, but the correspondence is not that trivial: PRINT-OBJECT
is to PRINT & Co. [*] as readtable manipulation is to READ &
Co. [+].
_________
[*] including PRIN1, PRIN1-TO-STRING, WRITE, etc.
[+] READ, READ-FROM-STRING, READ-PRESERVING-WHITESPACE
---Vassil.
--
"Even when the muse is posting on Usenet, Alexander Sergeevich?"
Thomas F. Burdick
> I am writing a 'guess the animal' game for my Lisp book of games.
> This game uses a binary deduction tree.
> The thing is this tree needs to be stored to and loaded from disk. This
> is a simple game and I don't want it to depend on external libraries like
> object-store. I figure the best way to do this is to store the CLOS tree
> as the code I would write to contruct the tree. That way I can just use
> read to recontruct it. Never the less the code here looks a bit uggy at
> least in (defmethod store ((item tree-node))).
> Do you see a better way to do this?
Do you really need to use defclass here? If you can get by with
structures, they serialize and de-serialize nicely as is.
Pascal Costanza
> I am writing a 'guess the animal' game for my Lisp book of games.
> This game uses a binary deduction tree.
> The thing is this tree needs to be stored to and loaded from disk. This
> is a simple game and I don't want it to depend on external libraries like
> object-store. I figure the best way to do this is to store the CLOS tree
> as the code I would write to contruct the tree. That way I can just use
> read to recontruct it. Never the less the code here looks a bit uggy at
> least in (defmethod store ((item tree-node))).
> Do you see a better way to do this?
Are you aware of the following link?
http://web.archive.org/web/20040815123650/http://lecture.pentaside.org/paper/persistence-lemmens.txt
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Timofei Shatrov
confuse everyone with this message:
>I am writing a 'guess the animal' game for my Lisp book of games.
>This game uses a binary deduction tree.
>The thing is this tree needs to be stored to and loaded from disk. This
>is a simple game and I don't want it to depend on external libraries like
>object-store. I figure the best way to do this is to store the CLOS tree
>as the code I would write to contruct the tree.
No, this is a bad idea. If you're going to store objects, using external
libraries such as CL-STORE is the way to go. But in your case, you can easily
store all your data as a list, which is trivial to save or read from disk.
--
|Don't believe this - you're not worthless ,gr---------.ru
|It's us against millions and we can't take them all... | ue il |
|But we can take them on! | @ma |
| (A Wilhelm Scream - The Rip) |______________|
John Thingstad
Yes, that's what I ended up doing.
(defstruct (animal-name (:type list))
item
left-child
right-child)
(defun questionp (string) (char= (aref string (1- (length string)) #\?))
(defun animalp (string) (not (questionp string))
--
John Thingstad
Thomas F. Burdick
Why the (:type list)? Structure objects serialize just fine.
John Thingstad
It's easier to debug when you can see the entire tree.
Remeber in the animal guessing game it tries to learn the new animal if
it can't guess it and it is easier to just look at a dump of the list
than to drill through it with the inspector. Oh, and the structure name
should be node, not animal-name.
--
John Thingstad