Functional Scala: Expressions, Extensions and Extractors

Welcome back to another episode of Functional Scala.

This one is the sequel to our extended sample on representing and resolving arithmetic expressions using algebraic datatypes and pattern matching. In this second part i try to answer a legitimate question: what are the advantages and disadvantages of algebraic datatypes (consisting of pure data, no behaviour), espacially if we wanna expand our expression language  – and what’s that all to do with the visitor pattern?

The expansion of our expression language might come in two flavors: on the one hand we might add some new functionality (for most of us are highly influenced by an object oriented paradigm, let’s call it behaviour), like simplifying arbitrary expressions before evaluating them. On the other hand, we might wanna extend the building blocks of our expression language itself, like mixing in some more operations or adding some variables beside our integer literals.

Extending functionality

First, let’s see how easy it is to add some new functionality. You may remember our function reduce (and with it function resolve for a stepwise reduction of an arbitrary expression). Let’s repeat that again, using a rather complex expression:

val expr = Mult(
            Sub(Literal(6), Mult(Sub( Literal(5), Literal(3)), Literal(3))),
            Add(Literal(3), Mult(Literal(5), Literal(8))))

for( e <- resolve( expr ) ) println( format( e ) )

// will print ...
// ( ( 6 - ( ( 5 - 3 ) * 3 ) ) * ( 3 + ( 5 * 8 ) ) )
// ( ( 6 - ( 2 * 3 ) ) * ( 3 + ( 5 * 8 ) ) )
// ( ( 6 - 6 ) * ( 3 + ( 5 * 8 ) ) )
// ( 0 * ( 3 + ( 5 * 8 ) ) )
// ( 0 * ( 3 + 40 ) )
// ( 0 * 43 )
// 0

Now take a closer look at line 11. While the first sub-expression’s already evaluated to zero, we still continue to reduce the second sub-expression, only to discover that the whole expression comes down to zero finally. Let’s say that executing a single reduction step (and with it the evaluation of a basic expression) is real expensive. What we need is a way to simplify a given expression, if we detect some trivial patterns which let us skip further reduction (like multiplying an arbitrary expression with zero finally results in zero). In other words, let’s add that functionality. Going the functional way by using algebraic datatypes and pattern matching, this is a rather easy task: we don’t need to touch the different building blocks of our language, but simply add another function which scans for some trivial patterns to reduce:

val simplify : Expression => Expression
    =
    ( expr :Expression) => expr match {

        case Add( Literal(0), expr ) => expr
        case Add( expr, Literal(0) ) => expr
        case Add( left, right ) => Add( simplify( left ), simplify( right ) )

        case Mult( Literal(0), _ ) => Literal(0)
        case Mult( _, Literal(0) ) => Literal(0)
        case Mult( Literal(1), expr ) => expr
        case Mult( expr, Literal(1) ) => expr
        case Mult( left, right ) => Mult( simplify( left ), simplify( right ) )

        case Sub( Literal(x), Literal(y) ) if x == y => Literal(0)
        case Sub( left, right ) => Sub( simplify( left ), simplify( right ) )

        case _ => expr
}

Ok, in order to make use of those simplifications, we need to adapt our function reduce. We could do that in a way of just composing those two functions:

val simplifiedReduce = ( expr :Expression ) => reduce( simplify( expr ) )

This works fine while calling our new function directly. But what about our function stepResolve, which still calls reduce directly? Well, in this case we just won the silver medal. We might need to adapt stepResolve and all other functions which might also rely on resolve, which clearly violates open closed principle! So another option left would be to adapt function resolve directly:

val reduce : Expression => Expression
    =
    ( expr :Expression ) => simplify( expr ) match {

        case Literal(_) => expr
        ...
}

Ahhh, ok – before we’re going to pattern match, we just simplify the given expression. Everything ok? If we did pattern matching the right way, everything would be fine. But take a closer look at line 5. Do you spot the risk? This will result in a nice but nevertheless endless recursion when doing stepwise reduction! Again, watch what we’re returning in that case. It’s the original expression, not the simplified one! So while simplification results into a literal, the original expression might be a more complex, nested one. And since we return the original expression, stepwise reduction wouldn’t stop. So is there a possible escape? of course! Everything would be fine, if we just return the literal, we were matching against. Observe:

val reduce : Expression => Expression
    =
    ( expr :Expression ) => simplify( expr ) match {

        case lit @ Literal(_) => lit
        ...
}

Wow, that was easy again. If we don’t rely on the given functions argument (that is expr) but instead stay local and only refer to those elements we’re matching against (that is lit) we’re free to transform the ingoing value in every which way we want while not compromising pattern matching!

With our adapted function at hand , let’s see if we can save some reduction steps:

val expr = Mult(
            Sub(Literal(6), Mult(Sub( Literal(5), Literal(3)), Literal(3))),
            Add(Literal(3), Mult(Literal(5), Literal(8))))

for( e <- resolve( expr ) ) println( format( e ) )

// will print ...
// ( ( 6 - ( ( 5 - 3 ) * 3 ) ) * ( 3 + ( 5 * 8 ) ) )
// ( ( 6 - ( 2 * 3 ) ) * ( 3 + ( 5 * 8 ) ) )
// ( ( 6 - 6 ) * ( 3 + ( 5 * 8 ) ) )
// ( 0 * ( 3 + ( 5 * 8 ) ) )
// 0

Well, it seems that we in fact saved some reduction steps! Praise to simplification!

Extending data

While we have seen, that it’s relatively easy to extend functionality by more or less adding some new functions, let’s see how easy it is to extensd our language itself. Say we wanna add another binary operation, like a modulo operation. First we need to extend our algebraic datatype:

sealed abstract case class Expression
...
case class Mod( x :Expression, y :Expression ) extends Expression

Now this was the easy part! What about our functions which are build upon our language blocks? For example, let’s take a closer look at our function eval. Since we declared our datatype as sealed, the compiler has the chance to detect all possible value constructors and see if we’ve matched against all possible cases. In this situation, the compiler complains that our match is not exhaustive! missing combination Mod! So let’s give what he deserves:

val eval : Expression => Int
    =
    _ match {
        ...
        case Mod( leftExpr, rightExpr ) => eval( leftExpr ) % eval( rightExpr )
}

It turns out, that possibly every function, which is based on our language needs to be adapted! So we can’t stop with eval, but also need to consider reduce, simplify (if we detect some patterns for simplifying expressions, based on modulo) , format and so on. This may become really ugly! For example let’s take a look at a rather worst case scenario: let’s focus on function reduce! There, we might add a whole bulk of new case expressions for every new operation:

val reduce : Expression => Expression
    =
    ( expr :Expression ) => simplify( expr ) match {

        case lit @ Literal( _ ) => lit

        case Add( Literal(_), Literal(_) ) => Literal( eval(expr) )
        case Add( left @ Literal(_), rightExpr ) => Add( left, reduce( rightExpr ) )
        case Add( leftExpr, right @ Literal(_) ) => Add( reduce( leftExpr ), right )
        case Add( leftExpr, rightExpr ) => Add( reduce( leftExpr ), rightExpr )

        // case Sub ... cases omitted

        // case Mult ... cases omitted

        case Mod( Literal(_), Literal(_) ) => Literal( eval(expr) )
        case Mod( left @ Literal(_), rightExpr ) => Mod( left, reduce( rightExpr ) )
        case Mod( leftExpr, right @ Literal(_) ) => Mod( reduce( leftExpr ), right )
        case Mod( leftExpr, rightExpr ) => Mod( reduce( leftExpr ), rightExpr )
}

Oh my god! Such functions gets bigger and bigger with every new binary operation we’re going to add to our expression language! If we take a closer look to those case expressions for Add and those case Expressions for Mod (as also to those for Sub and Mult) we can clearly see some similarities: in fact we could abstract away from the concrete binary operation and concentrate on the reduction of its operands in a rather polymorph way.

One Extractor to match them all

Unfortunately we need to match against those different value constructors! Well, do we really need to? It turns out, that Scala provides the idea of a so called Extractor, which gives some kind of independence when it comes to pattern matching. You can think of an Extractor as a way to deconstruct a given value in an arbitrary way, not determined by the structure of your datatype. This is all done by a simple method unapply which takes a value of any type and returns an Option, containing a tuple for the single parts which gets revealed by the process of deconstruction. On the other side, we’re allowed to simply return None as a way to show that we can’t deconstruct a given value – in this case, there won’t be a successful match! Sounds confusing? All gets better with a simple example. Just watch:

object BinaryOp{

    def unapply( x :Any ): Option[ Tuple2[Expression,Expression] ] = {

        x match{

            case Add( l, r ) => Some( ( l, r ) )
            case Sub( l, r ) => Some( ( l, r ) )
            case Mult( l, r ) => Some( ( l, r ) )
            case Mod( l, r ) => Some( ( l, r ) )
            case _ => None
        }
    }
}

Our first Exctractor! As said, it’s simply an object with a single method unapply, taking any value and resulting in an Option of an arbitrary tuple. In our case, we try to match the given value against all known binary operations. If we get a match, we simply return the left and right operand of the given operator. Otherwise we just return None, showing that the given value can’t be deconstructed into the operations operands. With our new Extractor at hand, we might happily try to give a more concise, polymorph implementation for our function reduce:

val reduce : Expression => Expression
    =
    ( expr : Expression ) =>  simplify( expr ) match {

        case lit @ Literal( _ ) => lit

        case BinaryOp( left @ Literal(_), right @ Literal(_) ) => Literal( eval( ??? ) )

        case BinaryOp( left @ Literal(_), rightExpr ) => ???( left, reduce( rightExpr ) )
        ...
}

Uhm, what started so promising turns out to be useless, since we also need to refer to (or to know at least) the concrete operation on the right side of our case expressions! So this is a dead end? Hm, what prevents us to return the operation as a whole within our Extractor, too? Nothing? Then let’s extend it:

object BinaryOp{

    def unapply( x: Any ): Option[ Tuple3[Expression,Expression,Expression] ] = {

        x match{

            case add @ Add( l, r ) => Some( ( add, l, r ) )
            case sub @ Sub( l, r ) => Some( ( sub, l, r ) )
            case mult @ Mult( l, r ) => Some( ( mult, l, r ) )
            case mod @ Mod( l, r ) => Some( ( mod, l, r ) )
            case _ => None
        }
    }
}

Aahhh, now we’re able to also refer to the operation as a whole! But wait a minute. This is just not enough. Sometimes, we need to construct a new operator value on the right side of a case expression which will carry some reduced argument (like at line 9 of our new implementation for reduce). But since we’re able to refer to the old operator, we can think of a function, which just constructs a new operation based on a given one and some operands. You might think of it as a kind of a factory function:

val construct : (Expression, Expression, Expression ) => Expression
    =
    ( op :Expression, fst :Expression, snd :Expression ) => op match {

        case a :Add => Add( fst, snd )
        case s :Sub => Sub( fst, snd )
        case m :Mult => Mult( fst, snd )
        case mo :Mod => Mod( fst, snd )
}

There you go! We just leveraged another mechanism for doing pattern matching in Scala. This time we just matched the given operation expression against its type. Since Scala is also an object oriented language, everything is an object (during runtime) in Scala. And while every object belongs to a type, so values of our datatype, too.

Now that we’ve got all ingredients to write some new functions in a more polymorphic way, let’s see how to do with our function under focus:

val reduce : Expression => Expression
    =
    ( expr : Expression ) =>  simplify( expr ) match {

        case lit @ Literal( _ ) => lit
        case BinaryOp( binOp,  left @ Literal(_), right @ Literal(_) ) => Literal( eval( binOp ) )
        case BinaryOp( binOp, left @ Literal(_), rightExpr ) => construct( binOp, left, reduce( rightExpr ) )
        case BinaryOp( binOp, leftExpr, right @ Literal(_) ) => construct( binOp, reduce( leftExpr ), right )
        case BinaryOp( binOp, leftExpr, rightExpr ) => construct( binOp, reduce( leftExpr ), rightExpr )
}

That’s all! Our function shrinked to only 5 cases. We never need to touch it again when adding some new binary operations. Of course we need to extend eval and construct with every new operation, but that’s all left to do. All other functions based on operations of our little expression language might stay stable, as long as they operate on a more abstract level (that is not need to act upon a concrete operation)! Take a look at this example, were i added another operation Pow (for power) and only extended our Extractor BinOp plus functions eval and build:

val expr = Mult(
            Add(Literal(6),Mult(Sub(Literal(5),Mod(Literal(5),Add(Literal(2),Literal(1)))),Literal(3))),
            Add(Literal(3),Mult(Pow(Sub(Literal(10),Literal(6)),Literal(5)),Literal(8))))

for( e <- resolve( expr ) ) println( format( e ) )

// will print ...
// ( ( 6 + ( ( 5 - ( 5 % ( 2 + 1 ) ) ) * 3 ) ) * ( 3 + ( ( ( 10 - 6 ) ^ 5 ) * 8 ) ) )
// ( ( 6 + ( ( 5 - ( 5 % 3 ) ) * 3 ) ) * ( 3 + ( ( ( 10 - 6 ) ^ 5 ) * 8 ) ) )
// ( ( 6 + ( ( 5 - 2 ) * 3 ) ) * ( 3 + ( ( ( 10 - 6 ) ^ 5 ) * 8 ) ) )
// ( ( 6 + ( 3 * 3 ) ) * ( 3 + ( ( ( 10 - 6 ) ^ 5 ) * 8 ) ) )
// ( ( 6 + 9 ) * ( 3 + ( ( ( 10 - 6 ) ^ 5 ) * 8 ) ) )
// ( 15 * ( 3 + ( ( ( 10 - 6 ) ^ 5 ) * 8 ) ) )
// ( 15 * ( 3 + ( ( 4 ^ 5 ) * 8 ) ) )
// ( 15 * ( 3 + ( 1024 * 8 ) ) )
// ( 15 * ( 3 + 8192 ) )
// ( 15 * 8195 )
// 122925

Now that we extended our operations, is it also possible to extend the atoms within our language? Until now, we can only express some integer literals, making the whole expression kind of static.

Let’s be variable …

What about introducing a variable as another atom? It could look like this:

sealed abstract class Expression
...
case class Var( x :String ) extends Expression

Hurray! We’re just added the possibility to also note some variable parts within our expressions. We simply state a variable and give’em a name:

val expr = Mult(
            Add( Literal( 6 ), Mult( Sub( Var( "x" ), Literal( 3 ) ), Literal( 3 ) ) ),
            Add( Literal( 3 ), Mult( Literal( 5 ),  Var( "y" ) )  ) )

Wow, that looks really good! But ask yourself what the result of e.g. Mult( Literal( 5 ), Var( “y” ) ) may be? Well, in order to resolve such an expression, we need to extend our model in a more fundamental way: along with the expression, we also need an environment, which delivers a concrete integer value for every variable. Let’s first define what we understand under an environment and how we could deliver a certain value from of a given environment (for a given variable name):

type Environment = List[ ( String, Int ) ]

val lookup : ( String, Environment ) => Int
    =
    (  Key :String, env :Environment ) => env match {

        case Nil => 0
        case ( Key, i ) :: _  => i
        case  _ :: xs => lookup( Key, xs )
}

Wowowow! Now that needs a little bit of explanation, don’t you think? First we just give a description of what we understand of an environment. It’s just a type alias for a list of pairs, where each pair consist of a String value (which might be interpreted as our variable name) and an integer value (which might be consisdered as the value to substitude for a given variable). We also could have used another data structure called Map, but we just wanna restrict ourself to some core data structures here!

Next is our function lookup, which takes a String (let’s say a variable name for which we’re interested in the related integer value) and an environment and results into an integer value. So far, we’ve cheated a little bit: in case there is an empty environment (that is, we can’t substitude a variable name), we simply return zero (we’ll use an Option for such cases in the near future, so don’t be worried). The second case expression tries to match the first (head) pair of the environments list against the given Key. If we have a match, we can deliver the assigned integer value. Did you note the first letter of our given key is in upper case? That’s because Scala interprets a name solely in lower cases within a pattern as a variable name (to bind the deconstructed, revealed part of the given pattern). That’s not what we want here! We wanna match against a concrete value – that’s the Key, given as the functions first argument.

Since the introduction of variables is such a fundamental extension (also forcing the introducing of an environment to substitute variables by an integer value), we also need to adapt our functions. For evaluating an arbitrary expression, we now also need a certain environment in order to resolve some variables within it:

val eval : (Expression, Environment) => Int
    =
    (exp :Expression, env: Environment) => simplify ( exp ) match {

        case lit @ Literal( x ) => lit
        case Var( x ) => lookup( x, env )
        case Add( leftExpr, rightExpr ) => eval( leftExpr, env ) + eval( rightExpr, env )
        case Mult( leftExpr, rightExpr ) => eval( leftExpr, env ) * eval( rightExpr, env )
        case Sub( leftExpr, rightExpr ) => eval( leftExpr, env ) - eval( rightExpr, env )
        case Mod( leftExpr, rightExpr ) => eval( leftExpr, env ) % eval( rightExpr, env )
}

But that’s not enough! Let’s get back to our worst case function reduce. Similarly to our binary operations, we also might want do handle atoms in a more polymorphic way (that is to act on literals and variables in the same way without differentiating between them). Wait a minute. Didn’t we discovered a way to pattern match on a datatype without relying on their real structure? Yeah, extractors to the rescue, again!

object Atom{

    def unapply( x: Any ): Option[Expression] = {

        x match{

            case literal @ Literal(_) => Some( literal )
            case variable @ Var(_) => Some( variable )
            case _ => None
        }
    }
}

Aaahhh, we only have a match if there’s a literal or a variable. Only in this two cases, we return an expression, which is just the found literal or atom. In all other cases we’ll return None, so there will be no match in an arbitrary case expression. Now we can adapt reduce like so:

val reduce : ( Expression, Environment) => Expression
    =
    ( exp : Expression, env :Environment ) => simplify( exp ) match {

        case Atom( variable @ Var(_) ) => Literal( eval( variable, env ) )
        case Atom( a ) => a
        case BinaryOp( binOp, Atom(variable @ Var(_)), rightExpr ) => construct( binOp, reduce( variable,env ), rightExpr )
        case BinaryOp( binOp, leftExpr, Atom(variable @ Var(_)) ) => construct( binOp, leftExpr, reduce( variable, env ) )
        case BinaryOp( binOp, Atom(_), Atom(_) ) => Literal( eval( binOp, env ) )
        case BinaryOp( binOp, left @ Atom(_), rightExpr ) => construct( binOp, left, reduce( rightExpr, env ) )
        case BinaryOp( binOp, leftExpr, right @ Atom(_) ) => construct( binOp, reduce( leftExpr, env  ), right )
        case BinaryOp( binOp, leftExpr, rightExpr ) => construct( binOp, reduce( leftExpr, env ), rightExpr )
}

Ok, let’s inspect that function. We see that it’s possible to use pattern binding even within a pattern declared by extractors. Take a look at lines 5, 7 and 8 for example: there we wanna be sure that the atom really is a variable so we can transform it into an equivalent integer literal just by evaluating the variable to it’s value. There are other cases (e.g. line 9, 10 and 11) where we’re not interested in the concrete form of that atom. There, we only wanna be sure that the operands are just arbitrary atoms, so we don’t need to reduce them any more! There also, you might have seen, that we’re allowed to nest some patterns using multiple extractors: we simply used the BinaryOp pattern to extract the operator and its operands while matching against an arbitrary operator. Now within the extracted parts (so within the BinaryOp pattern) we additionally match the extracted operands against another extractor pattern Atom.

Now it’s time to try our extended language. We could have a single expression featuring some variables and provide multiple environments for assigning variables in some diffeent ways:

val expr = Mult(
            Add( Literal( 6 ), Mult( Sub( Var( "x" ), Literal( 3 ) ), Literal( 3 ) ) ),
            Add( Literal( 3 ), Mult( Literal( 5 ),  Var( "y" ) )  ) )

for( exp <- resolve( expr,  ( "y", 8 ) :: ( "x", 1) :: Nil ) )  println( format( exp ) )

// will print
// ( ( 6 + ( ( x - 3 ) * 3 ) ) * ( 3 + ( 5 * y ) ) )
// ( ( 6 + ( ( 1 - 3 ) * 3 ) ) * ( 3 + ( 5 * y ) ) )
// ( ( 6 + ( -2 * 3 ) ) * ( 3 + ( 5 * y ) ) )
// ( ( 6 + -6 ) * ( 3 + ( 5 * y ) ) )
// ( 0 * ( 3 + ( 5 * y ) ) )
// 0
...

for( exp <- resolve( expr1_2,  ( "y", 42 ) :: ( "x", 17 ) :: Nil ) ){ println( format( exp ) ) }

// will print
// ( ( 6 + ( ( x - 3 ) * 3 ) ) * ( 3 + ( 5 * y ) ) )
// ( ( 6 + ( ( 17 - 3 ) * 3 ) ) * ( 3 + ( 5 * y ) ) )
// ( ( 6 + ( 14 * 3 ) ) * ( 3 + ( 5 * y ) ) )
// ( ( 6 + 42 ) * ( 3 + ( 5 * y ) ) )
// ( 48 * ( 3 + ( 5 * y ) ) )
// ( 48 * ( 3 + ( 5 * 42 ) ) )
// ( 48 * ( 3 + 210 ) )
// ( 48 * 213 )
// 10224

Works like a charm! We only needed to touch almost every function …

Summary

Whew! What a journey! We’re at the end of our extended example. Most of the given data and functionality are based on two concepts: algebraic datatypes and pattern matching. We almost saw every possible way to do pattern matching in Scala: we pattern matched against the natural structure of some case classes (which we leveraged as a kind of description for some value constructors of an algebraic datatype) and deconstructed their nested components, using variable binding, wildcards (remember the underscore) or some concrete values. We pattern matched against some artificial patterns, provided by some custom extractors. We matched against types and used variables to bind whole or part of some patterns.

We saw that pattern matching is a more easy task when adding some new functionality while the number of value constructors for our datatype remains stable. This way you might wanna compare the whole construct to the visitor pattern. There also, you may have a number of (non subtype-polymorphic) types where you need to define a certain functionality upon a composite structure for some nested values of those types. The visitor will also kind of deconstruct the given nested structure while visiting each node. You can see each visit method as a kind of case expression which gets called if the visitor hits a value of the right kind.

Like with the visitor pattern, it’s more easy to add new visitors (providing another functionality), but it’s extremely inconvenient if you add some new types. This would mean that you need to visit and adapt each existing visitor implementation, adding another visit method to handle the new type!

The same is true for algebraic datatypes and pattern matching. If your datatype appears to be very fragile, then it may be the wrong choice, since you also need to potentially update all your functions based on that datatype. You might soften that pain by introducing some custom extractors to kind of abstract over some of your value constructors! If your datatype remains more stable on the other side, pattern matching might be an elegant way to add some new functionality over time. Only it provides some more options for using different patterns and pattern semantics at your own neeed (while a visitor might only match against a certain type). I hope you’ve seen some of its flexibility within the last two episodes …