hey-
I'm trying to get to the point where I'm as comfortable using common lisp as
I
am using C or C++ (actually, I would like to be more comfortable with common
lisp). so I wrote some quick code for a binary tree- just some trivial toy
code to let me get the feel of CLOS, something I haven't played with much up
to
this point. if y'all could comment on the style or offer any suggestions,
I'd
appreciate it. also, along those lines, I was wondering- what's the
difference
between defclass and defstruct in usage? would you generally be able to get
away with using defstruct for trivial data structures (like my btree)
instead
of defclass? what is the intended use of defclass v. defstruct (code
examples
welcome :) )?
thanks,
j.d.
(defclass tree-node ()
((parent-node :initform nil :accessor parent)
(left-node :initform nil :accessor left)
(right-node :initform nil :accessor right)
(node-data :initarg :data :reader data)))
;; I only wrote one function because I just wanted enough practice to get
the syntax down ;)
(defun add-leaf (tree-root new-data)
(let ((current-node tree-root)
(new-node (make-instance 'tree-node :data new-data))
(new-parent nil))
(loop until (eql current-node nil)
do (cond ((> new-data (data current-node))
(setf new-parent current-node)
(setf current-node (right current-node)))
((< new-data (data current-node))
(setf new-parent current-node)
(setf current-node (left current-node)))
(t (return-from add-leaf
(format nil "Node containing ~A already present."
new-data)))))
(if (> new-data (data new-parent)) (setf (right new-parent) new-node)
(setf (left new-parent) new-node))
(setf (parent new-node) new-parent)))
"J.D. Hollis" <········@resnet.gatech.edu> wrote in message
·················@news-int.gatech.edu...
> difference
> between defclass and defstruct in usage? would you generally be able to get
> away with using defstruct for trivial data structures (like my btree)
> instead
> of defclass?
Yes, but I find myself wishing I'd made a defstruct a defclass much more often
than vice versa!
> thanks,
> j.d.
>
> (defclass tree-node ()
> ((parent-node :initform nil :accessor parent)
> (left-node :initform nil :accessor left)
> (right-node :initform nil :accessor right)
> (node-data :initarg :data :reader data)))
>
> ;; I only wrote one function because I just wanted enough practice to get
> the syntax down ;)
>
> (defun add-leaf (tree-root new-data)
> (let ((current-node tree-root)
> (new-node (make-instance 'tree-node :data new-data))
> (new-parent nil))
> (loop until (eql current-node nil)
this would usually be (null current-node)
> do (cond ((> new-data (data current-node))
> (setf new-parent current-node)
> (setf current-node (right current-node)))
the setf form can have multiple bindings in it, I usually like to group them
that way ie:
(setf new-parent current-node
current-node (right current-node))
> ((< new-data (data current-node))
> (setf new-parent current-node)
> (setf current-node (left current-node)))
> (t (return-from add-leaf
> (format nil "Node containing ~A already present."
> new-data)))))
As a user of this function I would more likely prefer to have a nil returned
rather than a string with a message. (format t "...") will return nil as it
prints your message as a side effect...
> (if (> new-data (data new-parent)) (setf (right new-parent) new-node)
> (setf (left new-parent) new-node))
> (setf (parent new-node) new-parent)))
>
Those are all nit-picks, it looks just fine to me..
--
Coby
(remove #\space "coby . beck @ opentechgroup . com")
>>>>> On Tue, 15 Jan 2002 19:35:59 -0500, J D Hollis ("J") writes:
J> what is the intended use of defclass v. defstruct
A good rule of thumb is: DEFSTRUCT is a spelling error,
where you really must have intended to use DEFCLASS instead.
Historically, the class ("object") features in Lisp were predated by a
fancy "structure macro" system (DEFSTRUCT). People had lots of legacy
code that was written using DEFSTRUCT, and were also afraid that maybe
the object-oriented programming features would not be efficient.
But the reality turned out to be that there's really no advantage
to DEFSTRUCT, so you just might as well say DEFCLASS all the time.
(Besides, then when you wish you could write some DEFMETHODS for
the object, you can do so without having to go back and rewrite the
DEFSTRUCT into the DEFCLASS that you should have written originally!)
If you are worried about efficiency, consider the following.
In general, different Lisp implementations from different vendors might
make some things more efficient than other things, and the Lisp language
doesn't define how things are implemented at that level. This means it is
only truthful to compare *implementations*, and not make generalizations
about the *language*. Aside from algorithmic choices such as arrays versus
lists versus hash-tables, you can't intuit what will be more efficient.
To wit, here's an object lesson from one popular commercial Lisp compiler:
(defclass foo () ((a) (b) (c)))
(defstruct (bar) a b c)
(defstruct (baz (:type list)) a b c)
(defstruct (quux (:type vector)) a b c)
(make-instance 'foo) => #<FOO 2040D754> ; 51 total bytes
(make-bar) => #S(BAR A NIL B NIL C NIL) ; 68 total bytes
(make-baz) => (NIL NIL NIL) ; 77 total bytes
(make-quux) => #(NIL NIL NIL) ;152 total bytes
All of the above examples took the same amount of time (0.0 seconds).
However, using DEFCLASS always results in a more efficient program than
using a DEFSTRUCT, which gets even worse when you specify the data type
to be used when implementing the structure (and also loses its manifest
type identity)!
"Christopher Stacy" <······@spacy.Boston.MA.US> wrote in message
··················@spacy.Boston.MA.US...
> >>>>> On Tue, 15 Jan 2002 19:35:59 -0500, J D Hollis ("J") writes:
> J> what is the intended use of defclass v. defstruct
>
> A good rule of thumb is: DEFSTRUCT is a spelling error,
> where you really must have intended to use DEFCLASS instead.
>
> Historically, the class ("object") features in Lisp were predated by a
> fancy "structure macro" system (DEFSTRUCT). People had lots of legacy
> code that was written using DEFSTRUCT, and were also afraid that maybe
> the object-oriented programming features would not be efficient.
>
> But the reality turned out to be that there's really no advantage
> to DEFSTRUCT, so you just might as well say DEFCLASS all the time.
> (Besides, then when you wish you could write some DEFMETHODS for
> the object, you can do so without having to go back and rewrite the
> DEFSTRUCT into the DEFCLASS that you should have written originally!)
>
Well, now its my turn : )
I wrote the same thing a couple of weeks ago, it was pointed out that yes you
*can* write methods specialized on structure types. Perhaps, like me, you are
thinking of accessors not being generic functions? That is what usually bites
me.
--
Coby
(remove #\space "coby . beck @ opentechgroup . com")
Christopher Stacy <······@spacy.Boston.MA.US> writes:
> >>>>> On Tue, 15 Jan 2002 19:35:59 -0500, J D Hollis ("J") writes:
> J> what is the intended use of defclass v. defstruct
>
> A good rule of thumb is: DEFSTRUCT is a spelling error,
> where you really must have intended to use DEFCLASS instead.
I disagree.
> (Besides, then when you wish you could write some DEFMETHODS for
> the object, you can do so without having to go back and rewrite the
> DEFSTRUCT into the DEFCLASS that you should have written originally!)
DEFSTRUCT (if you don't prevent it from defining a manifest type at
all) defines classes, just like DEFCLASS, does (classes defined via
DEFSTRUCT will have a metaclass of STRUCTURE-CLASS). You can write
methods specialized on STRUCTURE-CLASS instances just as fine as you
can on instances of STANDARD-CLASS.
I use DEFSTRUCT in cases were I explicitly want to define classes with
the given restrictions of STRUCTURE-CLASS. E.g. when implementing
cons-like datastructures, like e.g. the nodes of splay trees, etc. It
also offers several convenient defaults and features that DEFCLASS
doesn't. So why shun it? There are very few features of CL that I
_explicitly_ shun, namely features that have been rightfully
superceded or deprecated, like e.g. the :test-not keywords (but not
the -if-not functions).
Contrary to the experiences reported by others, there have been few
cases where I "mistakenly" decided on using a DEFSTRUCT, and had to
change over to a DEFCLASS form, and even in those few cases, CL
provides enough support to make such changes with minimum impact on
existing code.
Regs, Pierre
[ Member of the society against minimalism and subsettism in language design ]
--
Pierre R. Mai <····@acm.org> http://www.pmsf.de/pmai/
The most likely way for the world to be destroyed, most experts agree,
is by accident. That's where we come in; we're computer professionals.
We cause accidents. -- Nathaniel Borenstein
"J.D. Hollis" <········@resnet.gatech.edu> writes:
> I'm trying to get to the point where I'm as comfortable using common lisp as
> I am using C or C++ (actually, I would like to be more comfortable with common
> lisp). so I wrote some quick code for a binary tree- just some trivial toy
> code to let me get the feel of CLOS, something I haven't played with much up
> to this point. if y'all could comment on the style or offer any suggestions,
> I'd appreciate it.
IMHO, your code doesn't seems as trivial as your said because it
doesn't follows the classic Lisp idioms. The representation of Lisp
datas is already a tree. So for your problem, it is eaysiest to map
your datas to the Lisp representation than to use pure OO in the
Java/C++ style. OO it not always the best solutions to solve a
problem. Here is a ad-hoc grammar for that representation:
tree := node
node := (value left-child right-child)
left-child := node | nil
right-child := node | nil
Try to use recursive algorithms in that structure, it will avoid all
the side-effect operations!
--
Frederic Brunel
Software Engineer
In-Fusio, The Mobile Fun Connection
Frederic Brunel wrote:
>
> "J.D. Hollis" <········@resnet.gatech.edu> writes:
>
> > I'm trying to get to the point where I'm as comfortable using common lisp as
> > I am using C or C++ (actually, I would like to be more comfortable with common
> > lisp). so I wrote some quick code for a binary tree- just some trivial toy
> > code to let me get the feel of CLOS, something I haven't played with much up
> > to this point. if y'all could comment on the style or offer any suggestions,
> > I'd appreciate it.
>
> IMHO, your code doesn't seems as trivial as your said because it
> doesn't follows the classic Lisp idioms. The representation of Lisp
> datas is already a tree. So for your problem, it is eaysiest to map
> your datas to the Lisp representation than to use pure OO in the
> Java/C++ style. OO it not always the best solutions to solve a
> problem. Here is a ad-hoc grammar for that representation:
>
> tree := node
> node := (value left-child right-child)
> left-child := node | nil
> right-child := node | nil
The "best solution" depends on the requirements of the program and the
resources you have for writing it. However, I agree that lists (conses)
are a very convenient way to represent trees, and it's often a good
start for experiments and prototypes.
> Try to use recursive algorithms in that structure, it will avoid all
> the side-effect operations!
Actually, writing functions in a recursive way may help you notice or
avoid side effects, but it will not prevent you from side effects. Here
is a recursive function that destructively adds an element to a binary
search tree:
(defun bintree-add (node elt)
(if (null node)
(list elt nil nil)
(let ((node-elt (first node)))
(cond ((< elt node-elt)
(setf (second node) (bintree-add (second node) elt)))
((> elt node-elt)
(setf (third node) (bintree-add (third node) elt))))
node)))
--Matthieu
On Thu, 17 Jan 2002, Matthieu Villeneuve wrote:
> Frederic Brunel wrote:
>> [trees as lists]
>> problem. Here is a ad-hoc grammar for that representation:
>>
>> tree := node
>> node := (value left-child right-child)
>> left-child := node | nil
>> right-child := node | nil
>
> The "best solution" depends on the requirements of the program and
> the resources you have for writing it. However, I agree that lists
> (conses) are a very convenient way to represent trees, and it's
> often a good start for experiments and prototypes.
I disagree. I've seen far too much code from apparently bad lisp
programmers that tend to stick to such prototype code. Sooner or
later, they will get lost using car and friends and the code is barely
readable, it's usually a maintainance nightmare. The problem is that
using lists as a representation for trees does not enforce any kind of
abstraction for accessing and modifying them. So, just like Graham
says that OO is good as it structures spaghetti code, I too believe
that there are people how actually need some external force to achieve
some structure.
Of course, when learning lisp, one should certainly be aware of the
flexibility of lists and how to use them as a representation for
trees. However, this doesn't imply that they should be used all over.
Holger
--
--- http://www.coling.uni-freiburg.de/~schauer/ ---
Fachbegriffe der Informatik - Einfach erkl�rt
163: SMD
Schwer Montierbare Dinger (Holger K�pke)
Holger Schauer <··············@gmx.de> writes:
> I disagree. I've seen far too much code from apparently bad lisp
> programmers that tend to stick to such prototype code. Sooner or
> later, they will get lost using car and friends and the code is barely
> readable, it's usually a maintainance nightmare. The problem is that
> using lists as a representation for trees does not enforce any kind of
> abstraction for accessing and modifying them. So, just like Graham
> says that OO is good as it structures spaghetti code, I too believe
> that there are people how actually need some external force to achieve
> some structure.
In my previous example I tough it was evident that simple accessors
should to be defined, such as:
(defun node-value (node)
(car node))
(defun node-left-child (node)
(cadr node))
...
--
Frederic Brunel
Software Engineer
In-Fusio, The Mobile Fun Connection
Frederic Brunel <··········@in-fusio.com> writes:
> Holger Schauer <··············@gmx.de> writes:
>
> > I disagree. I've seen far too much code from apparently bad lisp
> > programmers that tend to stick to such prototype code. Sooner or
> > later, they will get lost using car and friends and the code is barely
> > readable, it's usually a maintainance nightmare. The problem is that
> > using lists as a representation for trees does not enforce any kind of
> > abstraction for accessing and modifying them. So, just like Graham
> > says that OO is good as it structures spaghetti code, I too believe
> > that there are people how actually need some external force to achieve
> > some structure.
>
> In my previous example I tough it was evident that simple accessors
> should to be defined, such as:
>
> (defun node-value (node)
> (car node))
>
> (defun node-left-child (node)
> (cadr node))
Yes. But (unlike Scheme - sorry, I couldn't resist) you should, in
this case do
(defstruct (node (:type list)) value left right)
Cheers
--
Marco Antoniotti ========================================================
NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488
719 Broadway 12th Floor fax +1 - 212 - 995 4122
New York, NY 10003, USA http://bioinformatics.cat.nyu.edu
"Hello New York! We'll do what we can!"
Bill Murray in `Ghostbusters'.
On 18 Jan 2002, Frederic Brunel wrote:
> Holger Schauer <··············@gmx.de> writes:
>
>> I disagree. I've seen far too much code from apparently bad lisp
>> programmers that tend to stick to such prototype code. Sooner or
>> later, they will get lost using car and friends and the code is
>> barely readable, it's usually a maintainance nightmare.
>
> In my previous example I tough it was evident that simple accessors
> should to be defined, such as: [...]
That's exactly the problem. You thought it was evident and I think so,
too. Bad (or newbie) programmers (often) don't.
Holger
--
--- http://www.coling.uni-freiburg.de/~schauer/ ---
Fachbegriffe der Informatik - Einfach erkl�rt
163: SMD
Schwer Montierbare Dinger (Holger K�pke)
Holger Schauer wrote:
>
> On Thu, 17 Jan 2002, Matthieu Villeneuve wrote:
> > Frederic Brunel wrote:
> >> [trees as lists]
> >> problem. Here is a ad-hoc grammar for that representation:
> >>
> >> tree := node
> >> node := (value left-child right-child)
> >> left-child := node | nil
> >> right-child := node | nil
> >
> > The "best solution" depends on the requirements of the program and
> > the resources you have for writing it. However, I agree that lists
> > (conses) are a very convenient way to represent trees, and it's
> > often a good start for experiments and prototypes.
>
> I disagree. I've seen far too much code from apparently bad lisp
> programmers that tend to stick to such prototype code. Sooner or
> later, they will get lost using car and friends and the code is barely
> readable, it's usually a maintainance nightmare. The problem is that
> using lists as a representation for trees does not enforce any kind of
> abstraction for accessing and modifying them. So, just like Graham
> says that OO is good as it structures spaghetti code, I too believe
> that there are people how actually need some external force to achieve
> some structure.
I agree, and I don't think that goes against my point. I would never
write (or read) any non-trivial program that uses bare lists to
represent trees, and car, cdr, cadr,... (or first, rest, second,...) to
access node slots. However, if the goal is to write a short prototype to
test an algorithm or another program, then I don't have any problem with
using lists. As long as that prototype is to be thrown away right after
the tests, or kept only to validate future changes made to the
algorithm.
> Of course, when learning lisp, one should certainly be aware of the
> flexibility of lists and how to use them as a representation for
> trees. However, this doesn't imply that they should be used all over.
True. And many "real world" programs don't use lists at all in their
main parts.
--Matthieu
"J.D. Hollis" wrote:
> ... also, along those lines, I was wondering- what's the
> difference
> between defclass and defstruct in usage?
I don't see that anyone has actually answered this question. Here are
some differences between structure-class and standard-class with regard
to portable ANSI CL semantics:
- A structure-class allows only single inheritance. standard-class
supports multiple inheritance.
- The semantics of redefinition of a structure-class is essentially
completely undefined. It is well defined what happens when a
standard-class is redefined -- in particular, existing instances are
updated when first touched. The update mechanisms can be customized.
- standard-class supports change-class. structure-class doesn't. Ditto
reinitialize-instance, although that is less important.
- There is a de-facto standard metaobject protocol for standard-class,
allowing most facets of the object system to be customized. No such
thing is defined for structure-class.
- Slots of a structure-object do not support an unbound state.
- Slot readers and writers for standard-class are guaranteed to be
first-class generic functions and can therefore exploit inheritance
(combined methods) and even use specialized gf classes. Slot readers
for structure-class are regular functions, and writers are not even
necessarily functions (because they may be implemented by the setf
expansion machinery).