"class" constraints

[Torsten Anders]

Hi,

This is a somewhat longer posting, therefore I start with a short
abstract ;-)

			- - -

Abstract: I am working on means to describe a music score -- including
its form -- by means of constraints. I want to constrain the data type
of score entities. Therefore, I propose "class" constraints. I sketch an
implementation strategy, asking for comments and pointers to related
work.
 
			- - -

I am still working on the question "How to describe a music score by
constraints?". More precisely, I want to constrain not only the
parameters of the score elements (e.g. the pitches of notes) -- this has
been done already in several ways. Instead, I also want to constrain the
form of the score, which is a rather new research area. For clarity, I
describe a simplified problem below.

My solution score data structure forms a tree of non-terminal container
nodes and terminal element nodes. Elements are, e.g., notes with
features like duration, amplitude and pitch. Containers group elements
according some criterion (e.g. they represent a voice or a chord).

Constraining the form of a score therefore implies constraining the
shape of a tree. Luckily, you guys solved that already: you showed, how
dominance constraints can be implemented by finite set (FS) constraints
(see e.g.
http://www.ps.uni-sb.de/Papers/paper_info.php?label=dombool
http://www.ps.uni-sb.de/Papers/paper_info.php?label=duchier-esslli2000).

Using your means I can force a set of tree nodes to shape a tree
(well-formedness constraints), and I may constrain the tree further by
constraining dominance relations.

However, I also want to constrain the data types of my score entities
(i.e. tree nodes). The data types shall be organised in a hierarchy
(like a class hierarchy). In the following I therefore use the term
'class'. Nevertheless, my class here is not exactly a class in the OOP
sense. The main difference is: I want to instantiate objects without
specifying their class -- the class of each object is found later during
search.

"Class constraints" shall allow to constrain an object instance to
belong to a specific class or to an (possibly abstract) super class of
its final solution class. By this means I could, e.g., formulate a set
of well-formed-score constraints, which ensure the solution tree is also
a valid score. As an example, I want to constrain terminal nodes to be
score elements -- a super class of, e.g., notes. Further
well-formed-score constraint examples: all non-terminal nodes are
containers. A container must not contain a single container. etc.


I now want to sketch an implementation strategy for class constraints. I
want to define three constraints: IsClass, IsNotClass, IsExactlyClass:

Each class is represented by a unique numeric ID. Subclasses always have
higher IDs then their super classes. 

Each object instance has access to an own finite set (FS) which
specifies the instance class. A solution set of an instance contains
only the ID of its very class plus the IDs of all its super classes.


IsClass(x,c) <-> c in ClassSet_x

IsNotClass(x,c) <-> c notIn ClassSet_x

IsExactlyClass(x,c) <-> c in ClassSet_x and c=max(ClassSet_x)


As soon as it is known an instance belongs to a certain class, all super
classes of that class are added to the class set of the instance and all
features of that type are added to the instance.

forall s: 
  c in ClassSet_x and s in SuperClasses_c
    -> s in ClassSet_x

forall f: 
  c in ClassSet_x and f in Features_c
    -> tellFeature(x, f)


The distribution strategy will search for the class set of all
instances.



I also want to define methods for these classes. The method lookup for a
(kind of) generic function uses a 'cond' statement (committed choice). 

The guards of the cond statement check in parallel the signatures of all
defined methods of the generic function. Each guard checks the first
method argument to be of the class of the signature of some defined
method, but not to be of the class of the next specialised method
signature (i.e. the defined method for a subclass). 

If the class is not yet determined enough, the method lookup just
suspends. If a guard wins, then the procedure bound to its related
method is executed with the method arguments. If no guard wins, then an
exception is raised. 

BTW: extending this strategy, method dispatching could be dependent to
multiple arguments or to arbitrary other tests as well (e.g. eq
arguments as in CLOS).

A first sketch of an Oz implementation for the method creation
construct:

/**
%% MakeGeneric outputs a generic function according to Description.
%% Description is a list of the form 
%% [ ArgType1#Proc1 ... ArgTypeN#ProcN ]
*/
fun {MakeGeneric Description} 
   LenghtDescription={Length Description}
   SortedDescription={List.toTuple '#'
		      {Sort Description
		       fun {$ X#_ Y#_}
			  {IsSuperType X Y}
		       end}}
in
   %% the generic function 
   proc {$ X|Args}
      %% dynamic method dispatcher (executed at each method call)
      %% generate clauses for Combinator.'cond'
      CondClauses={Record.MapInt SortedDescription
		     fun {$ I ArgType#Proc}
			fun {$}
			   %% cond guard: check method argument
			   {IsOfType X ArgType}
			   if I <= LenghtDescription
			   then
			      MoreSpecializedType=SortedDescription.I.1
			   in
			      {IsOfType X MoreSpecializedType}
			   end
			   %% cond then: call method body
			   proc {$} {Proc X|Args} end
			end
		     end}
   in
      {Combinator.'cond' CondClauses
       %% cond else:
       proc {$}
	  raise
	     {NoMatchingMethodError X Args Description}
	  end
       end}
   end
end



Discussion: 

The proposed class constraints allow to define classes and method at an
level of abstraction OO programmers are familiar with. However, the
class of an object does not need to be known at the time the object is
instantiated. Instead, the class of the object can be constrained and
found by search.

I have not yet fully implemented this approach, I hope it does not
contain any error in reasoning ;-)

Certainly, the method lookup strategy is not very efficient. For every
method call the cond construct is first generated (perhaps I could do
some caching here?) and cond always needs to create some spaces.

Any comment i welcome!


Best,
Torsten


-- 
Torsten Anders
Sonic Arts Research Centre
Queens University Belfast
Tel: +44 28 9027 4831 (office)
     +44 28 9066 7439 (private)


-
Please send submissions to users at mozart-oz.org
and administriva mail to users-request at mozart-oz.org.
The Mozart Oz web site is at http://www.mozart-oz.org/.
Please send bug reports to bugs at mozart-oz.org.