20110225

:constructor tricks

Every once in a while I discover things in CL that somehow I had not thought about before. They have been there sometimes since CLtL1 but, somehow, I did not register them before. (I am slow, I know; and I am not claiming that this is anything new. But this is the Internet :) )

Fancy :constructor uses are one of these things.

Suppose you wanted to construct a immutable tree node structure which recorded the height of the sub-tree upon construction. Here is an iteration of what you may do.

(defstruct node
   (height 0)
   left
   right)

Now you need to create the constructor for nodes. Not worrying about nil nodes, you may start by doing the obvious (assuming a max* function capable of dealing with nil values):

(defun build-node (l r)
   (make-node :left l
              :right r
              :height (1+ (max* (node-height l) (node-height r)))))
Ok. Fine. But why having two constructors, with the standard make-node essentially useless (you would not want to advertise it, as height is a computed slot)?

However, you can do the following:

(defstruct (node
           (:constructor make-node (left right
                                    &aux
                                    (height (1+ (max* (node-height left) (node-height right))))))
   (height 0)
   left
   right)
This will work as expected; the key trick is to leverage the &aux parameter to collect the computation. Adding the appropriate :read-only declarations, you end up with:
(defstruct (node
           (:constructor make-node (left right
                                    &aux
                                    (height (1+ (max* (node-height left) (node-height right))))))
   (height  0 :read-only t :type (mod 42))
   (left  nil :read-only t :type (or null node))
   (right nil :read-only t :type (or null node))
A perfectly fine immutable node structure.


(cheers)

20110224

NEW structure and class constructor handling?

In a previous post I mused about having a new new operator for Common Lisp.

The only rub in the scheme I came up with was the handling of DEFSTRUCT constructors, which had to be somehow recorded in the system in order to make them known to the new operator.

The solution was less than satisfactory, and I had been thinking about how to come up with something more pleasant. Now I believe I found something acceptable by relaxing the basic new invariant (cfr., the spec) and admitting two "pseudo" types as arguments. Suppose we had a "pseudo" type (class class-name) and a "pseudo" type (struct structure-class-name). Now I could write:

cl-prompt> (defclass foo () ())
#<STANDARD CLASS FOO>

cl-prompt> (newq (class foo))
#<FOO @ 42>
The twist is that now I have the right structure to plug in the constructor for structures.
cl-prompt> (defstruct baz q w e)
BAZ

cl-prompt> (newq (struct baz) :q 42)
#S(BAZ :Q 42 :W NIL :E NIL) ; The standard MAKE-BAZ constructor is called.

cl-prompt> (defstruct (bar (:constructor barify (a s &optional d)
                           (:constructor new-bar))
               a s d)
BAR

cl-prompt> (newq (struct bar :by barify) 1 2)
#S(BAR :A 1 :S 2 :D NIL)

cl-prompt> (newq (struct bar :by new-bar) :s 2 :a 1)
#S(BAR :A 1 :S 2 :D NIL)

I think this does it and it is not so bad. Any comments?


(cheers)

20110216

EQUALITY and COMPARISON to CDR

I submitted the proposal for equality and comparison (cfr. my previous post) to the CDR discussion fora.
(cheers)