4.3. Inheritance hierarchies#
In the foregoing sections, we studied two kinds of graphs: trees represented by Prolog terms, and graphs generated by predicate definitions. In both cases, the main inference step is to search for a path satisfying certain conditions. In this section, we study a type of structured knowledge called an inheritance hierarchy, which differs from the previous cases in that it requires a more elaborate kind of reasoning. Basically, this is because a node in such a hierarchy is a more complex entity with various kinds of properties. Lower nodes in the hierarchy inherit properties from ancestor nodes, unless they are assigned a property of their own. Thus, reasoning about inheritance hierarchies not only requires searching for a path, but also collecting properties found along a path.
Figure 4.3 An inheritance hierarchy of musical instruments. Nodes in the tree denote classes; at the bottom, instances for each class are listed.#
Figure 4.3 displays an inheritance hierarchy of a variety of musical instruments. The topmost node represents the class of all instruments in the Universe of Discourse, which has three subclasses: wind instruments, string instruments, and percussion instruments. In turn, wind instruments are divided into woodwinds and brass instruments, and so on. At the bottom of the figure, instances are listed for each most specific subclass. Thus, guitar, lute and harp are instances of the class ‘plucked instruments’, and thus also of the classes ‘string instruments’ and ‘instruments’.
If we want to represent such hierarchies in Prolog, we have to choose a representation for instances and classes. By far the most natural choice is to represent an instance by a constant, and a class by a unary predicate. A class–superclass relation is then expressed by a clause, and an instance–class relation is expressed by a ground fact:
% Classes
instrument(X):-wind(X).
instrument(X):-string(X).
instrument(X):-percussion(X).
wind(X):-woodwind(X).
wind(X):-brass(X).
string(X):-plucked(X).
string(X):-bowed(X).
string(X):-keyboard(X).
percussion(X):-tuned(X).
percussion(X):-untuned(X).
% Instances
woodwind(recorder).
woodwind(flute).
woodwind(oboe).
woodwind(saxophone).
brass(trumpet).
brass(trombone).
brass(horn).
plucked(guitar).
plucked(lute).
plucked(harp).
bowed(violin).
bowed(cello).
keyboard(harpsichord).
keyboard(piano).
tuned(triangle).
tuned(kettledrum).
untuned(cymbal).
untuned(snaredrum).
With these clauses, it is possible to ask questions about instances and (super)classes. For example, we can find out what instruments there are by means of the query
?-instrument(X).
As was remarked above, nodes (and instances) in an inheritance hierarchy can be assigned properties, where a property is an attribute–value pair. For instance, the material an instrument is made of can be an attribute, with possible values ‘wood’ and ‘metal’. The statement ‘saxophones are made of metal’ is represented by the ground fact
material(saxophone,metal).
The statement ‘instances of the class of string instruments are made of wood’ is represented by the clause
material(X,wood):-string(X).
Since string(piano) is a logical consequence of the previous clauses expressing the hierarchy, we can now prove material(piano,wood). Thus, the chosen representation takes care of the inheritance of properties, as required.
In our musical Universe of Discourse, we consider three attributes: the function of an instrument (all instruments have a musical function), the material of an instrument (wood or metal), and the way the instrument produces sound, expressed by the attribute action:
function(X,musical):-instrument(X).
% Materials
material(flute,metal).
material(saxophone,metal).
material(X,wood):-woodwind(X).
material(X,metal):-brass(X).
material(X,wood):-string(X).
material(X,metal):-percussion(X).
% Actions
action(oboe,reed(double)).
action(saxophone,reed(single)).
action(harpsichord,plucked).
action(piano,hammered).
action(X,reed(lip)):-brass(X).
action(X,plucked):-plucked(X).
action(X,bowed):-bowed(X).
action(X,hammered):-percussion(X).
For instance, all brass instruments have lip-reeds, while some woodwinds have a double reed (oboes, for example) or a single reed (saxophones).
Note that there is a potential conflict in the above clauses: woodwinds are generally made of wood, but flutes and saxophones are made of metal. Thus, the query
?-material(flute,M).
has two answers:
M = metal;
M = wood
The order in which these answers are found is, of course, determined by the order of the clauses above. Since we put the ground facts listing properties of instances before the clauses listing properties assigned to classes (and the clauses pertaining to classes before those pertaining to superclasses), the answers are found by climbing the inheritance hierarchy from bottom to top, and the first property found is the desired one. It should be noted, however, that things are not always that simple. If more sophisticated inheritance strategies are needed, alternative representations, like the ones to be discussed later in this section, are to be preferred.
A typical thing one would like to know regarding an inheritance hierarchy is: what are the properties of a given instance? In principle, this requires a second-order query
?-Attr(Inst,Value).
which is not allowed in Prolog if Attr is not instantiated. We can get around this by maintaining a list of all attributes, and constructing the appropriate goal for each attribute by means of the predicate get_value/3:
properties(Inst,Props):-
attributes(Attrs),
properties(Attrs,Inst,Props).
properties([],Inst,[]).
properties([Attr|Attrs],Inst,[Attr=Value|Props]):-
get_value(Attr,Inst,Value),!, % only first answer
properties(Attrs,Inst,Props).
attributes([function,material,action]).
get_value(A,B,C):-
Goal =.. [A,B,C],
call(Goal).
For instance, the query ?-properties(saxophone,P) yields the answer
P = [function=musical,material=metal,action=reed(single)]
Only the most specific property regarding material is found, because of the cut in the recursive clause of properties/3.
Tip
Here is a slightly different version that gets around SWISH’s sandbox restrictions:
properties(Inst,Props):-
attributes(Attrs),
properties(Attrs,Inst,Props).
properties([],_Inst,[]).
properties([Attr|Attrs],Inst,[Attr=Value|Props]):-
get_value(Attr,Inst,Value),!, % only first answer
properties(Attrs,Inst,Props).
attributes([function,material,action]).
get_value(A,B,C):-
( A=function -> function(B,C)
; A=material -> material(B,C)
; A=action -> action(B,C)
).
Instance–class vs. class–superclass#
In this representation there appears to be no difference between instance–class relations and class–superclass relations. Indeed, we could have treated instances just as classes, and use the isa/2 predicate for both. However, this obscures the semantic difference between instances and classes, which can lead to problems. For example, instances of one class can be composed of instances of other classes (a bicycle is composed of two wheels and a frame), but this is not true for classes (the class of bicycles is not composed of the class of wheels and the class of frames).
As indicated above, the representation of inheritance hierarchies by means of clauses only allows a relatively simple inheritance strategy. Moreover, since classes are represented by predicates, reasoning about classes becomes a second-order logical inference. For example, the question ‘what are the subclasses of the class of instruments’ is not easily handled in the above representation. Both shortcomings can be alleviated if classes and attributes are represented by terms instead of predicates. In effect, this will result in a clearer separation of declarative knowledge describing the hierarchy, and procedural knowledge describing the inheritance strategy. This can be done in several ways; two possibilities are worked out below.
The first idea is to represent the tree in Figure 4.3 according to the first method in Section 4.2, i.e. by a set of ground facts listing the arcs in the tree. Thus, nodes (classes) are represented by constants, and arcs (class–superclass relations) are represented by means of the predicate isa/2:
% Classes
isa(wind,instrument). isa(string,instrument).
isa(percussion,instrument). isa(woodwind,wind).
isa(brass,wind). isa(plucked,string).
isa(bowed,string). isa(keyboard,string).
isa(tuned,percussion). isa(untuned,percussion).
Instances are listed by means of the predicate inst/2:
% Instances
inst(recorder,woodwind). inst(flute,woodwind).
inst(oboe,woodwind). inst(saxophone,woodwind).
inst(trumpet,brass). inst(trombone,brass).
inst(horn,brass). inst(guitar,plucked).
inst(lute,plucked). inst(harp,plucked).
inst(violin,bowed). inst(cello,bowed).
inst(harpsichord,keyboard). inst(piano,keyboard).
inst(triangle,tuned). inst(kettledrum,tuned).
inst(cymbal,untuned). inst(snaredrum,untuned).
The difference between inheritance hierarchies and ordinary graphs lies in the additional meaning assigned to classes and instances by means of properties. Therefore, a graph extended with properties is commonly called a semantic network. Properties are represented by means of the predicate prop/3:
% Class properties
prop(instrument,function,musical).
prop(string,material,wood).
prop(percussion,material,metal).
prop(percussion,action,hammered).
prop(woodwind,material,wood).
prop(brass,material,metal).
prop(brass,action,reed(lip)).
prop(plucked,action,plucked).
prop(bowed,action,bowed).
% Instance properties
prop(flute,material,metal).
prop(oboe,action,reed(double)).
prop(saxophone,material,metal).
prop(saxophone,action,reed(single)).
prop(harpsichord,action,plucked).
prop(piano,action,hammered).
Since we will be using a more sophisticated inheritance strategy, the order of these facts is now immaterial.
The inheritance strategy is to collect the properties of instances before properties inherited from classes:
properties_sn(Inst,Props):-
props(Inst,InstProps), % properties of instance
inst(Inst,Class),
inherit_sn(Class,InstProps,Props). % inherit the rest
props(IC,Props):-
findall(Attr=Value,prop(IC,Attr,Value),Props).
In turn, inherited properties are collected from bottom to top in the hierarchy, so that specific properties are found before general properties:
inherit_sn(top,Props,Props).
inherit_sn(Class,SpecificProps,AllProps):-
props(Class,GeneralProps), % properties of this class
override(SpecificProps,GeneralProps,Props),
isa(Class,SuperClass), % climb hierarchy
inherit_sn(SuperClass,Props,AllProps). % inherit rest
top refers to the root of the universal inheritance hierarchy, which should be added as the root of any sub-hierarchy:
isa(instrument,top).
The predicate override/3 checks for every general property whether a more specific property has already been found. If so, we say that the specific property overrides the general property:
override(Props,[],Props).
override(Specific,[Attr=_Val|General],Props):-
member(Attr=_V,Specific), % overriding
override(Specific,General,Props).
override(Specific,[Attr=Val|General],[Attr=Val|Props]):-
not(member(Attr=_V,Specific)), % no overriding
override(Specific,General,Props).
Again, the query ?-properties_sn(saxophone,P) yields the answer
P = [function=musical,material=metal,action=reed(single)]
What we gained with this representation, however, is a declarative specification of the inheritance strategy, which is therefore also amenable to change. For instance, if the inheritance hierarchy is not a tree, a class could be a subclass of two or more other classes. In this case, different values for the same attribute could be inherited along different paths; this is called multiple inheritance. Such conflicts need to be resolved (or at least signalled) by the inheritance strategy.
Exercise 4.7 #
Implement a multiple inheritance strategy.
A slightly different but related representation is obtained if we group all information about one class or instance together in a so-called frame. A frame representation is obtained from the semantic network representation by adding a list of properties to each arc in the network. Below, class frames are defined by the predicate class/3, and instance frames are defined by the predicate instance/3:
% Classes
class(instrument,top,[]).
class(wind,instrument,[function=musical]).
class(string,instrument,[material=wood]).
class(percussion,instrument,[material=metal,
action=hammered]).
class(woodwind,wind,[material=wood]).
class(brass,wind,[material=metal,action=reed(lip)]).
class(plucked,string,[action=plucked]).
class(bowed,string,[action=bowed]).
class(keyboard,string,[]).
class(tuned,percussion,[]).
class(untuned,percussion,[]).
% Instances
instance(recorder,woodwind,[]).
instance(flute,woodwind,[material=metal]).
instance(oboe,woodwind,[action=reed(double)]).
instance(saxophone,woodwind,[material=metal,
action=reed(single)]).
/* etcetera... */
instance(cymbal,untuned,[]).
instance(snaredrum,untuned,[]).
Inheritance is as easily implemented as in the semantic network representation:
properties_fr(Inst,Props):-
instance(Inst,Class,InstProps), % instance properties
inherit_fr(Class,InstProps,Props). % inherit the rest
inherit_fr(top,Props,Props).
inherit_fr(Class,SpecificProps,AllProps):-
class(Class,SuperClass,GeneralProps), % this class
override(SpecificProps,GeneralProps,Props),
inherit_fr(SuperClass,Props,AllProps). % inherit rest
Historically, semantic network and frame-based representations were proposed in quite different contexts. We see that their representation in Prolog is very similar.