Subtyping and application of context-free classes

Object-oriented systems are usually not designed from scratch but
constructed using frameworks or class libraries. This construction
should lead to correct systems provided the reused classes are
locally correct. Therefore knowledge about the features that a
certain class provides is often not enough. It is additionally
necessary to know the correct semantics of classes, i.e. information
on how to use these features. Especially, we have to mind the
sequences of method calls that are acceptable by an object. Using
regular languages for the description of these sequences works
fine for some classes but is not adequate for others, e.g. for
stacks, buffers, queues or lists etc.

In this paper we present a more general approach for the
specification of the dynamic behavior of objects using context-free
grammars. We investigate questions of correctness in subtyping and
application of such classes. We define sufficient conditions for
class systems such that local correctness in subtyping and
application implies global correctness of the system.