ADTs, OOP, rules and Pattern-matching (1)

CarlosLoria — Sat, 07 Jun 2008 00:57:00 GMT

Abstract (or algebraic) Data Types (ADTs) are well-known modeling techniques for specification of data structures in an algebraic style.
Such specifications result useful because they allow formal reasoning on Software at the specification level. That opens the possibility of automated verification and code generation for instance as we may find within the field of program transformation (refactoring, modernization, etc.). However, ADTs are more naturally associated with a declarative programming languages (functional (FP) and logic programming (LP)) style than an object-oriented programming one (OOP). A typical ADT for a tree data structure could be as follows using some hypothetical formalism (we simplify the model to keep things simple):

adt TreeADT<Data>{

   import Integer, Boolean, String;
   signature:
       sort Tree;
       oper Empty : -> Tree;
       oper Node : Data, Tree, Tree|-> Tree;
       oper isEmpty, isNode : Tree-> Boolean;
       oper mirror : Tree -> Tree
       oper toString : -> String
   semantics:
       isEmpty(Empty()) = true;
       isEmpty(Node(_,_,_)) = false;

       mirror(Empty()) = Empty()
       mirror(Node(i, l, r)) = Node(i, mirror(r), mirror(l))

   }
As we see in this example, ADTs strongly exploit the notion of rules and pattern-matching based programming as a concise way to specify requirements for functionality. The signature part is the interface of the type (also called sort in this jargon) by means of operators; the semantics part indicates which equalities are invariant over operations for every implementation of this specification. Semantics allows recognizing some special kinds of operations. For instance, Empty and Node are free, in the sense that no equation reduces them. They are called constructors.
If we read equations from left to right, we can consider them declarations of functions where the formals are allowed to be complex structures. We also use wildcards (‘_’) to discard those parts of the parameters which are irrelevant in context. It is evident that a normal declaration without using patterns would probably require more code and consequently obscure the original intention expressed by the ADT. In general, we would need destructors (getters), that is, functions to access ADT parts. Hence, operation mirror might look like as follows:
   Tree mirror(Tree t){
       if(t.isEmpty()) return t;
        return new Node( t.getInfo(),
                  t.getRight().mirror(),
      t.getLeft().mirror() );
   }
Thus, some clarity usually could get lost when generating code OOP from ADTs: among other things, because navigation (term destruction, decomposition) needs to be explicit in the implementation.

Rules and pattern-matching has not yet been standard in main stream OOP languages with respect to processing general data objects. It has been quite common the use of regular expressions over strings as well as pattern-matching over semi structured data especially querying and transforming XML data. Such processing tends to occur via APIs and external tools outside of the proper language. Hence, the need for rules does exist in very practical applications, thus, during the last years several proposals have been developed to extend OOP languages with rules and pattern-matching. Some interesting attempts to integrate ADTs with OOP which are worthy to mention are Tom (http://tom.loria.fr/ ) and Scala (http://www.scala-lang.org/ ). An interesting place to look at with quite illustrating comparative examples is http://langexplr.blogspot.com/.

We will start in this blog a sequence of posts studying these two models of integration of rules, pattern-matching and OOP in some detail. We first start with a possible version of the ADT above using Scala. In this case the code generation has to be done manually by the implementer. But the language for modeling and implementing is the same which can be advantageous. Scala explicit support (generalized) ADTs, so we practically obtain a direct translation.
   object TreeADT{
       trait Tree{
           def isEmpty:boolean = false
           override def toString() = ""
           def mirror : Tree = this
           def height : int = 0
       }
       case class Node(info:Any, left:Tree, right:Tree)
               extends Tree{
           override def toString() =
              "("+info+left.toString() + right.toString()+")"

       }

       object Empty extends Tree{
           override def isEmpty = true
       }

       def isEmpty(t : Tree) : boolean =
              t match {
           case Empty => true
           case _    => false
       }

       def mirror(t : Tree):Tree =
               t match{
               case Empty       => t
               case Node(i, l, r) => Node(i,mirror(r), mirror(l))
       }
      }

Carlos Loría-Sáenz Blog : rules, pattern-matching

ADTs, OOP, rules and Pattern-matching (1)