Subclassing and Inheritance in generic documents

From owner-xml-dev@ic.ac.uk  Tue Oct  7 22:58:45 1997
Subject: Subclassing and Inheritance in generic documents

         ------------------------------------------------------

This is something I wrote in response to clarify my own ideas about
inheritance, subclassing, architectural forms and SGML documents. I hope
it is useful to others and will make it into a web page if it seems
useful to do so. Please ignore typos. Conversation on the document
should be in XML-DEV (or in private email) since inheritance is not on
the XML WG's immediate agenda (AFAIK).

Thanks to Steven Newcomb and Peter Newcomb for their individual 
comments on some of the ideas. This does *not* represent an 
expression of concensus however. :)

----
Ideas about Subclassing and Inheritance in generic documents
==============================================================

The concept of subclassing is an important one in modern object oriented
software design, but the idea of "subclasses" and "superclasses" is 
fundamental to how we think about our world. These concepts are
reinvented in DTD after DTD through parameter entities and deserve a
direct expression that could be used throughout an SGML authoring and
processing system.

There is a lesser notion, of inheritance, which has practical utility
but is not as crucial. Inheritance allows one set of objects to get the
properties of another set of object "for free". In SGML this would 
probably mean that one element would "inherit" the attribute 
declarations and content model of another element. SGML DTDs also 
use parameter entities to model inheritance. Inheritance is 
basically just a code saving device which allows different parts 
of the DTD to evolve independently. 

The concept of inheritance is not as old or well established as that of
subclassing and I do not think that it is as important in SGML.
Inheritance is only a code saving device. Subclassing has implications
that can allow us to build more interesting editors, processors and
other tools. Code saving is important, but not as important as being
allowed to express new kinds of type relationships naturally.

Programming language research has found that there are times when you
want to subclass without inheriting and even inherit without
subclassing. Early object oriented programming languages did not make a
distinction. Modern programming languages give you some options in this
regard. C++ allows "private" inheritance which is inheritance 
("inheriting code") without subclassing (claiming to always be 
replaceable for elements of the parent class). Java's "interfaces" 
allows subclassing without inheritance. I believe that the problems that 
have led to this need for a separation are all related to multiple 
inheritance and are also applicable to markup languages. More on this
later.

This essay will outline the ideas without making concrete proposals for
extensions for SGML. The goal is to get people thinking and to expose
the flaws in our current mechanisms, parameter entities and
architectural forms. 

A Straw Person Syntax
=====================
For our purposes, an element type is a subclass of another element type
if it is substitutable where ever the first element is and declared to
be a subclass. So if I have an animal element type, cat would be an 
appropriate subclass because any content model that needs an animal 
could be fulfilled with a cat. Here's an example of a syntax that 
would allow this:

<!ELEMENT animal ANY>
<!ATTLIST animal FOOD CDATA #REQUIRED
		 HABITAT NAME #REQUIRED>

<!ELEMENT cat TYPEOF (animal) (#PCDATA)>
<!ATTLIST cat FOOD NAME #REQUIRED
		HABITAT NAME #REQUIRED>

Now there are a few important things buried in this syntax. 

	Subclassing
	===========

The first is that the subclass must implement the base class's interface
faithfully. Since animal has ANY content model, cat can have ANY content
model. But cat may also have a more restricted content model. In this
case they do. Cats may only have text content. Animal allows food to be
any string of SGML characters, but cat restricts the set to only the
name characters. One important thing to note is that before a single
document has been created, this DTD can be checked to guarantee complete
conformance of element type subclasses to element type superclasses so
that any element of type "cat" that is created is absolutely guaranteed
to be also valid as an "animal". This means that cats are guaranteed to
be substituable for animals.

So this is now a valid document:

<!DOCTYPE ZOO[
<!ENTITY % animals SYSTEM "http://www.animalsRUs.com/animal.dtd">
%animal;
<!ELEMENT ZOO (ANIMAL+)>
]>
<ZOO>
<CAT FOOD="Nibbles" HABITAT="Domestic">
<CAT FOOD="Rats" HABITAT="Barn">
<CAT FOOD="People" HABITAT="Jungle">
</ZOO>

It would be illegal for "cat" to extend "HABITAT" to type CDATA or
NUMBER because there exist CDATA strings and NUMBERs that are not valid
NAMEs. This is a little bit of an inversion from OOP, because in OOP a
subclass must accept any "input" that a parent class can. We think of
content models as "accepting input". 

The reason for this inversion is that the content of an element is 
actually "output", not input. It is input by the human, but output
by the parser. 

Think of each element as an object that implicitly has methods to 
retrieve each attribute and its content. For instance in Python 
I might make a rule for animals that absolutely depended on HABITAT 
being a name, and not random CDATA:

def ANIMAL( FOOD, HABITAT ):
	print "I eat", Cdata2String( FOOD )
	print "I live in", Name2String( HABITAT )

Now you can see why it is so important that cat not be more "flexible"
about the properties it has in common with animal. This would be even
more vital if the property were declared to be a number and I were
going to use the language's built-in coercion tools to convert the
string representation of the number to an integer. More generally,
an important reason that SGML has DTDs is so that software can depend
on documents conforming to them. We cannot weaken those guarantees
in moving adding inheritance and subclassing to SGML.

On the other hand, cat could create new attributes that would be totally
ignored when it was being treated as an animal. Generally speaking,
attributes seem more intrinsically amenable to concepts of subclassing
than content, because they are "random access" in some sense, as are
methods in OOP. Perhaps in adding OO features to SGML we will also 
choose to make attributes more powerful (for instance by allowing them
to have content models and explicit substructure like elements).

Substitutability also works in the DTD. That means that a subclass of
ZOO could have a content model that was restricted to subclasses of
ANIMAL:

<!DOCTYPE FLEA-CIRCUS[
<!ENTITY % zoo SYSTEM "http://www.zoosRUs.com/zoo.dtd">
%zoo;
<!ELEMENT FLEA TYPEOF ANIMAL>
<!ELEMENT FLEA-CIRCUS TYPEOF ZOO (FLEA+)>
]>

The flea-circus element type is a special subclass of zoo that can only
accept fleas.

We say that each element type listed in a content model has a "role". 
When you create an SGML document, each element in the
document "matches up" against some element in the DTD unambiguously.
I say that it fulfills that "role". Content models in subclasses 
are also "matched" against content models in their superclasses. 
Matching element types must be subclasses of the element type that they 
match in in the superclass, just as "FLEA" in "FLEA-CIRCUS" is a
subclass 
of "ANIMAL" in "ZOO".

	Inheritance
	===========

Note also that the subclass in my proposal does not inherit anything.
It re-declares a content model and an attribute list. I do not have any
particular problem with a system in which things which are not
redeclared in subclasses are presumed to be inherited from superclasses
unchanged. But it is important to me that we understand that inheritance
and subclassing are two different things and one can occur without the
other. From here on in this essay, I *will* pretend that an inheritance
rule has been designed. If an element declaration does not have a
content model, it means that the content model is inherited. If it does
not repeat a particular one of its superclasses' attributes, it means 
that the attribute has been inherited. This is just a convenience
measure 
and does not change the basic concept of subclassing. Still convenience
is 
important. Without inheritance, changes to the base classes must be 
manually propogated down to subclasses. In practice, this makes 
maintainance more difficult. 

	Multiple Inheritance/Subclassing
	==================================

There is an interesting inversion in the document OO model vs. OOP. In
OOP, multiple subclassing is widely understood to be useful, but 
multiple inheritance is highly controversial because of confusion that
can be caused repeated inheritance and the repeated instance variables
that repeated inheritance causes. In documents, the problem seems to be
the opposite. Multiple subclassing is dangerous as inheritance is in 
OOP, because it may be ambiguous what role a subclassed element plays in 
a superclass's content model:

<!ELEMENT FOO (IMAGE|LINK|P)+>
<!ELEMENT CLICKABLE-LINK TYPEOF (IMAGE,LINK)>

<FOO><CLICKABLE-LINK><CLICKABLE-LINK></FOO>

The "archform" solution to this problem is to require an attribute to 
specify what base class each element should be converted to, and thus
what role it plays. I think that this requires authors to have too 
much knowledge of base classes.

Another solution would be merely to outlaw multiple subclassing which
introduces ambiguity. This may be too restrictive in some cases. A 
third solution might describe some form of "subclassing in context."
This last solution is inspired by architectural forms and their use
with SGML's Link feature to describe a particular SGML element as a
subclass of one element when it appears in one context and of another
in another context.

These options must be thought through some more and tested with real
DTDs. Multiple subclassing may turn out to be a point of weakness 
or confusion in our system just as multiple inheritance is in OOP.

Motivation
==========
You might be wondering: "is all of this just angels on the head of a
pin?" Am I just trying to align SGML with OOP just for the sake of doing
so? No not all. Real world SGML documents emulate subclassing and 
inheritance with parameter entities all of the time. 

Let me use as evidence the world's most popular DTD, HTML. The version I 
will use for my demonstration is HTML 3.2.

	Subclassing
	===========

HTML has a heading class defined like this:

<!ENTITY % heading "H1|H2|H3|H4|H5|H6">
<!ELEMENT ( %heading )  - -  (%text;)*>
<!ATTLIST ( %heading )
        align  (left|center|right) #IMPLIED
        >

As you can see, headings have absolutely the same content model and
attributes no matter where they occur. So their properties of completely
inheritable. It turns out that one heading is always usable anywhere
another is. They are *always* completely interchangable in content
models. This would be modeled in a true subclassing/inheritance system
like this:

<!CLASS heading (text)*>
<!ATTLIST heading align  (left|center|right) #IMPLIED>
<!ELEMENT (H1|H2|H3|H4|H5|H6) TYPEOF heading>

Each of the individual types of headings would inherit the attributes
and content model from the parent. Headings would also be completely
interchangable as they are now. The declaration for heading uses a 
"CLASS" keyword instead of an "ELEMENT" declaration because headings
cannot be inserted in documents themselves. You must choose some 
subclass of heading to insert (H1 through H6).

There are a few major benefits here over parameter entities.

 * For DTD designers, it allows easier construction of DTDs where there
are places where elements are interchangable.

 * It now becomes possible to extend HTML by incorporating the HTML DTD
into another, let's say, HTML-EXTENDED DTD. You can create a new heading
type (let's say H7) merely by inheriting from heading. Your new heading
will be treated as a heading by software that understands headings and
is ignored by software that is specific to H1 through H6. This is
exactly as you would expect. This easy extensibility of DTDs is the most
interesting, powerful feature of subclassing.

 * For document authors, it presents the interesting possibility of
class-organized element pick-lists in SGML authoring tools. There are
points in HTML where there are many valid elements, as many as 20. Using
classes, DTD designers could organize these into "headings", "lists",
"multimedia" etc. The HTML DTD already emulates these classes but they
are not available to SGML authoring tools because parameter entities
have no real semantic beyond textual replacement.

 * Subclassing allows programmers to organize their programs to take
advantage of the class hierarchy. We've already seen how this might work
in Python. Let's look at DSSSL for this example:

(element heading 
    (make paragraph
	font-size: (- 20 (HEADING-LEVEL (gi (current-node))))))

This code would be triggered on any occurence of a heading element,
including subclasses of heading. It would check the numeric suffix of
the heading and choose an appropriate font size. The code continues to
work with heading extensions as long as they continue the naming pattern
(e.g. H7 and H8). If you didn't want to depend on this convention, you
could treat other subclasses as H6.

The equivalent DSSSL code for SGML as we know it would require a
construction rule for each heading and there would be no easy way to
handle new subclasses.

	Inheritance
	===========

Now here's a case from the same DTD where you want inheritance, but not
subclassing. There are many objects in HTML that have href attributes
that point to resources. Examples include A, AREA, LINK, BASE and so
forth. We might want to define this attribute in one place and reuse it.
OO programmers call this a "mixin". We also might not to. DTD authors
should be careful. It is easy to abuse inheritance and inheriting one
attribute at a time from various places can make DTDs hard to read, just
as overuse of parameter entities can. Nevertheless, it may be useful to
do this to centralize the definition of HREF. I will also demonstrate
inheritance from a "shape" base class. Shape is a mixin that introduces
"width" and "height" attributes.

<!ELEMENT has-href ANY>
<!ATTLIST has-href href CDATA #IMPLIED>

<!ELEMENT sizeable ANY>
<!ATTLIST sizeable height NUMBER #IMPLIED
		   width NUMBER #IMPLIED>

<!ELEMENT area INHERITS (sizeable, has-href) EMPTY>

Now area inherits both sets of attributes. This means that a change to
one of those base classes propogates down to the children classes. Of
cousre if you make a change to the base that is incompatible with your
documents, they will break, just as with parameter entities or classes
in an OO language. On the other hand, the benefit of inheritance without
subclassing is that you can always unhook area from one or both of its
base classes without anything breaking. Inheritance relationships aren't
reflected in content models of other elements or in the document itself.
They are just a maintenance facility for DTD designers. Still, the
direct encoding of inheritance hierarchies in DTDs would present
interesting opportunities for graphical SGML DTD editing tools. Right
now they emulate inheritance hierarchies with parameter entities.
Inheritance hierarchy information is thus lost in the transmission from
one such program to another. This would not be the case if SGML had a
first-class inheritance feature.

A Word About Architectural Forms
================================

Architectural forms were invented in the 10 years between SGML's
creation and the time it was allowed to be revised. In the author's 
opinion, they reflect those limitations. Archforms allow subclassing
at the application level, but do not convey any subclass information
to the parser itself.

Now SGML is up for revision, not just correction, but revision. In XML, 
we should take advantage of that fact and do the job right. We have 
a great opportunity here that was not available when archforms were 
invented.

	Subclassing
	============
Architectural forms do not directly express the notion that element type
A ISA subclass of element type B at the SGML parser level. 

Since archforms do not have parser level subclassing, the parser cannot
check subclasses for conformance as OO language parsers do. Nor can 
DTDs be checked for conformance to meta-DTDs.

More subtly, I don't think the true subclassing relationship finds any 
direct expression in the archform concept at all. Rather archforms 
allow you to express that individual elements of type A ARE-ALSO-OF 
type B. If every single element of type A conforms to this
relationship, then you could *conclude* that element type A ISA subclass
of element type B, but there is no direct relationship. This has some
interesting implications: first there is no sense in which an
"architectural DTD" is a "meta-DTD". It was never a DTD for DTDs (which
is, I think, the most obvious meaning for meta-DTD), but it is not even
a "DTD superclass" or "DTD base class" or anything similar. There need 
not be any relationship between element types in the DTDs at all and if 
there is, the relationship is by convention, not language features. 

To put this in terms of the model above, every element type in a derived
"by default" subclasses from *every* element type in the base DTD. You
must restrict the subclassing of a particular element by setting an 
attribute. You may restrict the subclassing of all of an element type 
by using a fixed attribute.

Another problem is that there is absolutely no way to express that an
element within the same DTD conforms to the interface (content model and
attributes) defined by another element in the same DTD and is a valid
replacement for that element. There are tricks that you can use
with parameter entities to subclass from another DTD in the same
physical
file. You can even share may elements. But if we define a DTD to be 
a set of declarations, then you *cannot* directly inherit from an 
element type in the same logical DTD.

	Inheritance
	===========

Architectural forms do not allow any inheritance of element type
"properties" at all. You cannot inherit attribute values or content
models at the parser level. Even at the application level, the 
accuracy of calling what goes on in Architectural Forms "inheritance"
is dubious. Rather it seems more like delegation, as in Microsoft's
COM model. A particular element can support many "interfaces" and 
using attributes you can "delegate" between them so that a method
(attribute) that is called one thing in one interface (architectural
form) is called another thing in another.

	Safety
	======

Architectural form "subclasses" (element types with fixed attributes) 
are not constrained by the architectural form mechanism to be strict
element type subclasses. This means that in some cases an 
inappropriate or merely insufficiently strict mapping will allow an 
author to make a docuemnt which conforms to its DTD, but not to some
architectural DTD. Disturbingly, there is almost nothing that, for 
instance, an SGML editor can do to meaningfully report this error.
When I say "meaningfully report", I mean report in the terms of the 
DTD that the author is familiar with. After all, the error is not
caught in this DTD and thus is not expressible in those terms. Instead
you will get an error message like "XML-LINK not allowed at this point
in content of RDF-AUTHOR-INFO element in RDF-SPEC meta-DTD" when the 
author's actual mistake was putting  an element named "WebLink" in an 
element named "BiblioInfo" before an element named "AuthorInfo" instead 
of after it in a DTD called "THESIS-MARKUP-LANGUAGE".

Proponents of architectural forms will argue that allowing non-strict
subclassing allows flexibility that DTD designers need for mapping
one DTD to another. This is a good point. One of Architectural forms 
great strengths is that they provide a (relatively) simple syntax
for expressing mappings from documents conforming to one DTD to
documents conforming to another. This is absolutely vital to maintain
the balance between generic markup's extensibility and the need to
standardize on particular DTDs expected by software. This role cannot
be completely filled by constrained inheritance. Element types must
be *designed* to be subclasses of other element types. But 
architectural mapping can be done even for documents that just "happen"
to always conform.

My argument in response is that XML already has a transformation 
language. XSL can be used to transform from generic XML to HTML. It 
would be a tiny extension to allow it to be used for generic 
XML -> XML transformations. If we then take a declarative, 
no-lookahead subset, we will have something that can be implemented 
right in the parser to build a grove conforming to a different DTD. 
It would also be more powerful than architectural forms. Though 
archforms mappings can theoretically be set up after both DTDs 
have been designed, my experience is that this rarely works in 
practice unless the superclass DTD is very flexible and 
non-prescriptive, because archforms are not a full transformation 
language and have very little power to move things around. 

So in a practical sense, I think that a standardized, simple 
transformation language is still needed and that subclassing will
suffice for most of the cases where archforms work now.

	Syntax
	======

I feel that attributes are a confusing place to put type information. 
People (rightly, IMO) expect element type information to be explicit in
the
DTD and invisible in the instance. I also think that people rightly 
expect the language to support specific keywords that provide 
inheritance, and not have inheritance "implied" through
special "magical" attributes. Attributes made sense for archforms
because
SGML could not be changed. But times have changed. 

I believe that we need keywords and a parser-level understanding of
subclassing semantics.

 Paul Prescod


xml-dev: A list for W3C XML Developers. To post, mailto:xml-dev@ic.ac.uk
Archived as: http://www.lists.ic.ac.uk/hypermail/xml-dev/
To (un)subscribe, mailto:majordomo@ic.ac.uk the following message;
(un)subscribe xml-dev
To subscribe to the digests, mailto:majordomo@ic.ac.uk the following message;
subscribe xml-dev-digest
List coordinator, Henry Rzepa (mailto:rzepa@ic.ac.uk)