Hello,
I wonder how one usually deals with union structures in Lisp.
For example, how would you define the following expression structure in Lisp?
Do you just define a structure of two fields type and val? But this requires
two make-XXXX (make-et and make-cnst/make-et/make-bin). I would prefer
a single make-XXXX to handle all these.
A side issue. Does Lisp provide a way to ensure that when type is ET_Const,
the val field must be a CNST struct?
typedef struct et {
ET_TYPES type;
union {
CNST *pConst;
struct expr *pEt;
struct {
struct et *pLEt;
struct et *pREt;
} bin;
} val;
} ET;
Thanks.
Wei Jen Yeh ···@cs.purdue.edu
Department of Computer Science
Purdue University
West Lafayette, Indiana
In article <·····@ector.cs.purdue.edu> ···@cs.purdue.EDU (Wei Jen Yeh) writes:
> I wonder how one usually deals with union structures in Lisp.
In Lisp, all structures are "unions" by default. Lisp doesn't require you
to declare the type of slots, so they can hold references to any type.
If you want to include a type declaration, a union type corresponds to the
OR type specifier: (OR type1 type2 ...).
>For example, how would you define the following expression structure in Lisp?
>Do you just define a structure of two fields type and val? But this requires
>two make-XXXX (make-et and make-cnst/make-et/make-bin). I would prefer
>a single make-XXXX to handle all these.
>typedef struct et {
> ET_TYPES type;
> union {
> CNST *pConst;
> struct expr *pEt;
> struct {
> struct et *pLEt;
> struct et *pREt;
> } bin;
> } val;
> } ET;
Here's one way that uses the OR type specifier. Since Common Lisp doesn't
have anonymous structure types, I needed to break out the type of the bin
variant into a real type.
(defstruct et
(type nil :type et-types)
(val nil :type (or cnst expr bin-struct)))
(defstruct bin-struct
(let nil :type et)
(ret nil :type et))
Here's another way to do it, using :INCLUDE. I think this is what you were
referring to when you talked about having to have three different
constructors.
(deftype et (or et-const et-expr et-bin))
(defstruct et-header
(type nil :type et-types))
(defstruct (et-const (:include et-header))
(const nil :type cnst))
(defstruct (et-expr (:include et-header))
(et nil :type expr))
(defstruct (et-bin (:include et-header))
(let nil :type et)
(ret nil :type et))
>A side issue. Does Lisp provide a way to ensure that when type is ET_Const,
>the val field must be a CNST struct?
No, there's no automatic mechanism to do this. You can encapsulate this in
several ways, though. You could define a type specifier that uses
SATISFIES to check for consistency:
(defun valid-et-p (et)
(typep (et-val et)
(ecase (et-type et)
(et-const 'cnst)
(et-expr 'expr)
(et-bin 'bin-struct))))
(deftype valid-et () (satisfies valid-et-p))
Then various functions can use (check-type et valid-et-p) to check for
consistency at entry.
When creating et structures, you could provide an alternate constructor
function that checks the consistency of its arguments and then calls the
constructor that DEFSTRUCT created.
I better way might be to use CLOS classes rather than DEFSTRUCT. Then you
can define :BEFORE methods on the constructor and updater functions that
check for consistency.
--
Barry Margolin
System Manager, Thinking Machines Corp.
······@think.com {uunet,harvard}!think!barmar
In article <············@early-bird.think.com> ······@think.com (Barry Margolin) writes:
> Here's another way to do it, using :INCLUDE. I think this is what you were
> referring to when you talked about having to have three different
> constructors.
>
> (deftype et (or et-const et-expr et-bin))
>
> (defstruct et-header
> (type nil :type et-types))
>
> (defstruct (et-const (:include et-header))
> (const nil :type cnst))
>
> (defstruct (et-expr (:include et-header))
> (et nil :type expr))
>
> (defstruct (et-bin (:include et-header))
> (let nil :type et)
> (ret nil :type et))
You could make the header be an abstract struct, obviating the need
for the deftype (and significantly accelerating type checks). And CL
has runtime typing, so the TYPE slot is redundant. Care must also be
taken to ensure the default slot value matches its type declaration.
(defstruct (et (:constructor nil)))
(defstruct (et-const (:include et))
(const nil :type (or cnst null)))
(defstruct (et-expr (:include et))
(et nil :type (or expr null)))
(defstruct (et-bin (:include et))
(let nil :type (or et null))
(ret nil :type (or et null)))
> >A side issue. Does Lisp provide a way to ensure that when type is ET_Const,
> >the val field must be a CNST struct?
>
> No, there's no automatic mechanism to do this. You can encapsulate this in
> several ways, though. [ ... ]
Eliminating the TYPE slot also eliminates the chance of this mismatch.
Doug
In article <····················@skye.parc.xerox.com> ·······@skye.parc.xerox.com (Doug Cutting) writes:
>You could make the header be an abstract struct, obviating the need
>for the deftype (and significantly accelerating type checks). And CL
>has runtime typing, so the TYPE slot is redundant.
Yes, both you and Rob found this. I was being too literal in my
translation to Lisp.
Note that if one were to implement it first my way, and later change to use
manifest types, the change could be made transparent to client programs by
writing:
(defun et-header-type (et)
(type-of et))
> Care must also be
>taken to ensure the default slot value matches its type declaration.
Only if clients are permitted to let the slot values default. If the
default value is never used, it doesn't have to match its declaration.
This rule is necessitated by the brain-damaged syntax of slot specifiers,
which requires that a default be specified in order to specify options.
The problem with using (or null ...) as the :type option is that it also
permits the client to use NIL as the slot value explicitly, which is
probably not intended. And it probably destroys any chance of optimization
that the implementation might have done if the type were more limited (e.g.
fixnum).
Unfortunately, there are some implementations that check the type of the
default at compile time. Perhaps a good convention would be to write:
(defun shouldnt-default ()
(error "Invalid DEFSTRUCT default slot initialization attempted."))
(defstruct name
(slot (shouldnt-default) :type whatever ...))
>> >A side issue. Does Lisp provide a way to ensure that when type is ET_Const,
>> >the val field must be a CNST struct?
>>
>> No, there's no automatic mechanism to do this. You can encapsulate this in
>> several ways, though. [ ... ]
>
>Eliminating the TYPE slot also eliminates the chance of this mismatch.
All you've done is replace the TYPE slot with the type of the structure;
you can still mismatch this with the slot type. Implementations aren't
required to check that a slot matches its :TYPE option. Some do the check
when SAFETY is high, but you can't depend on it.
--
Barry Margolin
System Manager, Thinking Machines Corp.
······@think.com {uunet,harvard}!think!barmar
In article <·····@ector.cs.purdue.edu> ···@cs.purdue.EDU (Wei Jen Yeh) writes:
>Hello,
> I wonder how one usually deals with union structures in Lisp.
Well, barmar offers one solution, but I don't consider it to be particularly
idiomatic Lisp. If the "type" of an ET is immutable after creation, then there
are cleaner solutions which use the CL type system to enforce consistency.
For example:
(defstruct et)
(defstruct (et-const (:include et))
(cnst nil :type const))
(defconstant (et-expr (:include et))
(expr nil :type et))
(defstruct (et-bin (:include et))
(bin-LEt nil :type et)
(bin-REt nil :type et))
Of course, you can do the same thing with CLOS classes, but only
single-inheritance is required for this use.
Rob