2010-04-30

subtype polymorphism replacing polymorphic records

4.22: adda/oop/subtype polymorphism replacing polymorphic records:

. the example in [cocoa patterns].book/hierarchy
of using a graphics tree to express subgraphics
reminded me of how expressions use trees:
. generic trees are intuitively implemented as
variant records, (I'm not sure why these aren't called
polymorphic records ...)
and, this had me realizing how oop subclasses
are using their subclass tag
as a variant record discriminant:
[4.28: for example,
an expression tree has an eval operation
for both the branch and leaf variants
of its variant record structure;
therefore, it's a candidate for replacement by
an oop structure:
the branch subclass's eval
has to eval all args's
then apply the given operation;
the leaf subclass's eval
has to return its immediate value .]
. in both the case of oop and of variant record,
the low-level implementation could involve
a tagged record:
a record where one of the fields
is a code indicating which variant or subclass
the current state belongs to .

. to see a record as an ADT (abstract datatype),
imagine its list of components rephrased as
the operations that come with those components .

. show how oop's subtype polymorphism can save space
the way a variant rec's polymorphism can .
[4.28: variant rec's assume
that the size of all variants
is known at compile time;
and if all the sizes are known to be
approx'ly the same,
then the implementation might use
an immediate placement
rather than a pointer .
. among oop cases, it's true for polymorphs (eg, numbers)
that the size of all variants is known at compile time;
but not generally true for evolvers
(because they can evolve after compile time)
so then, polymorphs can benefit from a
tag system that can indicate
whether the obj's placement is immediate
or found by a pointer .
. on the other hand, oop's polymorphism can be
a time waster:
if half the instances
implement an operation as null,
then it would be more efficient to
case the tag
and make the call only when the instance
supports that operation;
that, in fact,
is why oop allows both styles:
oop can do anything a variant record can
by allowing a client to ask an obj'
what subclass or variant
it currently belongs to .
. summary of variant discrimination
vs subclass polymorphism:
. every node visit can either case the tag
in order to decide on operations to apply;
or a visit can simply
use those operations that are
supported by every subclass .
so, when you ask an oop obj' to do an act,
you're asking a subtype
to do its version of the act .]