|
June 2008 - Posts
-
In our previous post on pattern-matching and ADTs we used Scala for illustrating the idea of pattern extension as a complement to the notion of extractors as defined in Scala (See Post). We want to deepen and discuss some interesting points and derivations related to this requirement that we consider a key one.
By pattern extension we mean the possibility of adding or changing a pattern or combining it with other patterns in different new ways, in other words to have more modularity at this level of the programming or specification language. We know that patterns are available in several (no mainstream) languages however patterns are not usually treated as first-order citizens of such languages. A pattern is usually a sort of notation that the compiler traduces in normal code but not a value in the language. We consider that as an important limitation to the reuse and modularity of application in cases where patterns are numerous as in rule based systems with big amounts of rules. A pattern is actually that important as a query in an information system is, so it is related to a use case and might deserve being handled correspondingly.
Scala provides a nice way to connect patterns with classes as we know. However, Scala does not directly support extensibility at the pattern level as we are figuring out. In this post, we want to illustrate our ideas by developing a simple case using Scala. We want to reify patterns using objects to make the requirement more evident, we exploit many of the facilities that Scala provides but show a limitation we come across as well.
Suppose we want to define our pattern language as an idiom and to have more control over some operational facets of pattern-matching those we might be willing to change or customize. For instance, we would like to code a pattern that matches floating-point values but allows that the pattern matches approximately the muster (with a certain error margin). We want that such functionality would be cleanly a part of a "new" pattern. That is, although things like pattern guards could be used for such a purpose, we want to encapsulate this form of "fuzzy matching" and eventually parameterize it in a class of objects. Notice that for some class of classification problems fuzzy matching can be helpful, hence the example is not completely artificial. Other examples are evidently possible, too. Naturally, if we define our own atomic patterns, we should be able to construct our (boolean) combinations of them, too.
For our purposes, we will define a model of pattern by means of standard OO classes. We assume a very simple protocol (interface) to be satisfied by our family of patterns. We denote this protocol, by the following Scala trait:
trait IPattern[T]{
val value:T
def transduce(e:Any)=e
def matches(e:Any):Option[T] = None
def handle(c:Option[T]) = c
def `:>`(e:Any) = handle(matches(transduce(e)))
}
abstract class AnyPattern extends IPattern[Any]
The matching function is actually located in the method `:>`. The idea is that a pattern is allowed to first transduce the object to match before matching takes place; then the pattern matches the object and finally the "handle" functionality can be added to eventually cope with some particular condition after matching to transducer the result. As seen, we keep the design quite simple according the scope of this post. We assume the transduction does not change the type of neither the object nor the result. Results are given as instances of Scala class Option[T]. The instance field "value" is used by constant patterns those like numbers. We only handle patterns without binding just for simplicity; it can be easily extended for such a purpose.
Now, we can add a wildcard pattern (that matches every object, like _ in Scala)
object TruePattern extends AnyPattern{
val value = null;
override def matches(e:Any):Option[Any] = Some(e)
}
Similarly a class for exact pattern matchin of integers can be defined:
case class IntPattern(val value:Int) extends AnyPattern{
override def matches(e:Any):Option[Int] =
if(value==e) Some(value) else None
}
Let us present our fuzzy pattern for floating point:
case class FloatPattern(val value:Double) extends AnyPattern{
var epsilon:Double=0.01;
private def dmatches(e:Double):Option[Double]={
val diff = Math.abs(value - e );
if(diff<epsilon) return Some(diff)
else return None
}
private def imatches(e:Int):Option[Double]=matches(e.asInstanceOf[Double])
override def matches(a:Any):Option[Double] = a match{
case a:Int => imatches(a)
case a:Double => dmatches(a)
case _ => None
}
}
The pattern accepts integers and values that are at the 0.01 (a default for variable epsilon) distance of the pattern value, a parameter of the pattern. We return as value of the match this difference in absolute value.
As additional examples we define additional pattern combinators (in our algebra of own patterns) for "not", "and" and "or". We show the first two of them, nicely expressible in Scala. Notice that an expression (p `:>` e) produces the matching from pattern p with element e in our notation.
case class NotPattern(val value:AnyPattern) extends AnyPattern{
override def matches(e:Any):Option[Any]= {
val res:Option[Any] = (value `:>` e);
res match {
case Some(_) => return None
case _ => return Some(e)
}
}
}
case class AndPattern(val value:AnyPattern*) extends AnyPattern{
override def matches(e:Any):Option[Any]= {
val res:Option[Any] = Some(e);
for(v <- value){
val res = (v `:>` e);
res match {
case Some(z) => ;
case _ => return None
}
}
return res;
}
}
A guard pattern is also possible too (in this case the value is a Boolean lambda representing the guard):
case class GuardPattern(val value:(Any => Boolean)) extends AnyPattern{
override def matches(e:Any):Option[Unit]={
if(value(e)) return Some()
else return None
}
}
Now, let us add some sugar:
object _Patterns{
def _t = TruePattern;
def _$(x:Int) = IntPattern(x);
def _$(x:Double) = FloatPattern(x);
def _not(x:AnyPattern) = NotPattern(x);
def _and(x:AnyPattern) = AndPattern(x:_*);
def _or(x:AnyPattern*) = OrPattern(x:_*);
def _when(x:Any=>Boolean) = GuardPattern(x);
}
def even(x:Any) = x match{
case x:Int => x%2==0
case _ => false
}
Using this, we might write: _and(_not(_when(even)), _or(_$(1), _$(2)))
to denote a silly pattern that checks for a not even number that is 1 or 2; in other words matches just a 1.
As a final remark, we can be tempted to model these pattern classes adding extractors for representing them as Scala patterns. However, Scala limitations on "objects" (they have to be parameter less) and the "unapply" functions (they are unary) avoid such a possibility. Once again we identify an interesting feature for the language around this limitation.
|
-
As a continuation of our previous posts on ADTs, rules and pattern-matching, we go on with our work studying some alternatives to pattern extensibility and generation (see post 1 and post 2). For the extensibility case, we considered delegation by inheritance as an alternative, where we are currently using the programming language Scala for our illustration. In our previous post, we supported the claim the Scala compiler could be able to help in this aspect. In this post we consider pattern generation out from classes, once again, we identify a potential requirement for the programming languages under our study.
In general, we recall our goal is to discover features or their eventual absence in programming languages that give support to an ADT modeling style within a OOP environment. Our motivation and justification comes from the field of automated software transformation (as understood in www.artinsoft.com) and specifically exploring features in languages that properly help to specify transformation rules in a modular and reusable way. The ability to write rules is certainly a central and distinctive element of software transformation tools; especially in the case the feature is available to the final user in order to customize his/her own transformation tasks (as approached for instance in www.aggiorno.com ).
We have already seen how a pattern can be associated with a class in Scala which provides a very natural bridge between rules based programming and OOP. Patterns are views of objects that allow an easy access to its relevant subparts in a particular context, as we know. However, it is programmer’s responsibility to manually build the pattern, in the general case. And knowledge about the set of relevant destructors of the object is required, obviously. And this is usually a matter of domain specific semantics, thus we cope with a task that is difficult to automate.
The notion of destructor is central to ADTs and very particularly when compiling pattern matching. In OOP, destructors are usually implemented as so-called getters (or properties) but, interestingly, neither particular syntax nor semantics in mainstream OOP languages distinguishes them as such from other kind of methods, as we do have for the (class) constructors. In Scala, however, destructors can be automatically generated in some cases which is a fine feature. For instance, consider a simple model for symbolic expressions, defined as follows:
trait ISexp
class Sexp(val car:ISexp, val cdr:ISexp) extends ISexp{
}
class Atom(val value:String) extends ISexp
In this case Scala injects methods for accessing car and cdr fields, thus, in this case destructors are easily recognized. In the case the class would be a case-class the corresponding pattern is indeed generated as indicated by the constructor declaration. But what happens when the class specification is not Scala code or is not given by this explicit way, as in example.
Thus, an interesting question arises if we would want to support semi automated generation of patterns out of classes which are not available in a form that clearly exhibits its destructors.
In ADTs, a destructor is an operator (functor) f that gives access to one parameter of a constructor c. In other words, following invariant should hold in the ADT theory:
Forall x:T: f(c(…, x, ….)) = x
Or if we prefer using an OOP notation:
(new c(…,x,…)).f() = x
In terms of the type system we should have f: () => T where T is the declared type of formal parameter position where x occurs in c.
This provides us with a criterion for guessing candidates for destructors given a class. However, in order to generate code for a pattern, we would need to query the class implementing the ADT looking for such kind of candidates. However, in the case of Scala, we only have reflection as an alternative to perform the required query because there is no code model exposed as class model. Fortunately, the reflection facilities of Java fill the gap. The nice thing is the full interoperability of Scala with Java. The flaw is that we have to generate source code, only.
In order to evaluate the concept, we have developed a very simple Scala prototype that suggests destructors for Java and Scala classes and for generating patterns for such candidates.
For instance, for the classes of the Sexp model given above we automatically get as expected
object Atom {
def unapply(x:sexps.Atom)=Some(x.value)
}
object Sexp {
def unapply(x:sexps.Sexp)=Some(x.car, x.cdr)
}
For a class like java.lang.Integer we get something unexpected:
object Integer {
def unapply(x:java.lang.Integer)=Some(x.intValue, x.toString, x.hashCode)
}
Likewise for the class java.lang.String:
object String {
def unapply(x:java.lang.String)=
Some(x.toCharArray, x.length, x.getBytes, x.hashCode)
}
The overloading of constructors plays at this time an important role on the results. Unfortunately, Scala pattern abstraction does not correctly work if we use overloading for the unapply method. Thus, we have to pack all the possibilities in just one definition. Essential was actually, that we have identified additional requirements which are interesting to get attention as a potential language features.
|
-
We are reviewing some programming languages which provide explicit support for the integration between OO, ADTs (i.e. rules and pattern-matching). We refer to Part 1 for an introduction. We currently focus on Scala and TOM in our work. Scala provides the notion of extractor as a way to pattern-matching extensibility. Extractors allow defining views of classes such that we can see them in the form of patterns. Extractors behave like adapters that construct and destruct objects as required during pattern-matching according to a protocol assumed in Scala. By this way, it results possible to separate a pattern from the kind of objects the pattern denotes. We might consider pattern-matching as an aspect of an object (in the sense of Aspect Oriented Programming, AOP). The idea behind is really interesting, it is clarified in more detail in Matching Objects in Scala . We want to perform some analysis in this post. Our main concern in this part, as expected, is pattern extensibility, we leave the ADT aside just for a while. We will consider a situation where more support for extensibility is required and propose using delegation to cope with it, without leaving the elegant idea and scope of extractors offered by Scala. Pattern-matching by delegation could be more directly supported by the language.
Let us now see the example. Because of the complete integration between Scala and Java, extractors in Scala nicely interact with proper Java classes, too. However, let us use just proper Scala class declarations in our case study, as an illustration. In this hypothetical case, we deal with a model of “beings” (“persons”, “robots”, societies” and the like. We want to write a very simple classifier of beings using pattern-matching. We assume that classes of model are sealed for the classifier (we are not allowed to modify them). Hence, patterns need to be attached externally. We start with some classes and assume more classes can be given, so we need to extend our initial classifier to cope with new kinds of beings.
Thus, initially the model is given by the following declarations (we only have “person” and “society” as kinds of beings):
trait Being
class Person extends Being {
var name:String = _
var age:Int = _
def getName() = name
def getAge() = age
def this(name:String, age:Int){this();this.name=name;this.age=age}
override def toString() = "Person(" + name+ ", " +age+")"
}
class Society extends Being{
var members:Array[Being] = _
def getMembers = members
def this(members:Array[Being]){this();this.members=members}
override def toString() = "Society"
}
We have written classes in a Java-style, to remark that could be external to Scala. Now, let us introduce a first classifier. We encapsulate all parts in a class for our particular purposes, as we explain later on.
trait BeingClassifier{
def classify(p:Being) = println("Being classified(-):" + p)
}
class BasicClassifier extends BeingClassifier{
object Person {
def apply(name:String, age:int)= new Person(name, age)
def unapply(p:Person) = Some(p.getName)
}
object Society{
def apply(members:Array[Being]) = new Society(members)
def unapply(s:Society) = Some(s.getMembers)
}
override def classify(b:Being) = b match {
case Person(n) => println("Person classified(+):" + n)
case Society(m) => println("Society classified(+):" + b)
case _ => super.classify(b)
}
}
object SomeBeingClassifier extends BasicClassifier{
}
Method “classify(b:Being)”, based on pattern-matching, tries to say whether “b” could or not be recognized and displays a message, correspondingly. Notice that objects “Person” and “Society” within class “BasicClassifier” are extractors. In each case, we have specified both “apply” and “unapply” methods of the protocol, however, just “unapply” is actually relevant here. Such methods uses destructors to extract those parts of interest for the pattern being defined. For instance, in this case, for a “Person” instance we just take its field “name” in the destruction (“age” is ignored). Thus, the pattern with shape “Person(n:String)” differs from any constructor declared in class Person. That is, pattern and constructor can be, in that sense, independent expressions in Scala, which is a nice feature.
Now, let us suppose we know about further classes “Fetus” and “Robot” deriving from “Being”, defined as follows:
class Fetus(name:String) extends Person(name,0)
{
override def toString() = "Fetus"
}
class Robot extends Being{
var model:String = _
def getModel = model
def this(model:String){this();this.model=model}
override def toString() = "Robot("+model+")"
}
Suppose we use the following object for testing our model:
object testing extends Application {
val CL = SomeBeingClassifier
val p = new Person("john",20)
val r = new Robot("R2D2")
val f = new Fetus("baby")
val s = new Society(Array(p, r, f))
CL.classify(p)
CL.classify(f)
CL.classify(r)
CL.classify(s)
}
We would get:
Person classified(+):john
Person classified(+):baby
Being classified(-):Robot(R2D2)
Society classified(+):Society
In this case, we observe that “Robot” instances are negatively classified while “Fetus” instances are recognized as “Person” objects. Now, we want to extend our classification rule to handle these new classes. Notice, however, we do not have direct support in Scala for achieving that, unfortunately. A reason is that “object”-elements are final (instances) and consequently they can not be extended. In our implementation, we would need to create a new classifier extending the “BasicClassifier” above, straightforwardly. However, we notice that the procedure we follow is systematic and amenable to get automated.
class ExtendedClassifier extends BasicClassifier{
object Fetus {
def apply(name:String) = new Fetus(name)
def unapply(p:Fetus) = Some(p.getName())
}
object Robot {
def apply(model:String) = new Robot(model)
def unapply(r:Robot) = Some(r.getModel)
}
override def classify(p:Being) = p match {
case Robot(n) => println("Robot classified(+):" + n)
case Fetus(n) => println("Fetus classified(+):" + n)
case _ => super.classify(p)
}
}
object SomeExtendedClassifier extends ExtendedClassifier{
}
As expected, “ExtendedClassifier” delegates parent “BasicClassifier” performing further classifications that are not contemplated by its own classify method. If we now change our testing object:
object testing extends Application {
val XCL = SomeExtendedClassifier
val p = new Person("john",20)
val r = new Robot("R2D2")
val f = new Fetus("baby")
val s = new Society(Array(p, r, f))
XCL.classify(p)
XCL.classify(f)
XCL.classify(r)
XCL.classify(s)
}
We would get the correct classification:
Person classified(+):john
Fetus classified(+):baby
Robot classified(+):R2D2
Society classified(+):Society
As already mentioned, this procedure could be more directly supported by the language, such that a higher level of extensibility could be offered.
|
-
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))
}
}
|
|
|
|