Gabriel's software development blog

Phantom types in Java

noreply@blogger.com (Anonymous) — Sun, 09 Sep 2012 03:15:00 +0000

Introduction
One of the things that I like about types in programming languages is that they're there to help you (although sometimes feels the opposite). The more things you can check at compile time, the less you need to do during tests (if you need to do it at all!).

One of those techniques are Phantom Types, and although well known in advanced languages (Haskell, Scala, OCaml, etc.) it seems to be relativelly unknown in Java despite the fact it can be perfectly used.

Since Java 1.5, we have parametric types (generics). Once you have that, you can add types parameters to other types...

public class MyTpye <TypeParameter> { ....

you can have methods with generic parameters

public <T> Result doSomething( MyType<T> p){
.... do something with p ...
}

or require specific type parameters on your methods (called a generic type invocation ).

public Result doSomethingStringy( MyType<String> p){
.... do something with p ...
}

A ghost in the (type) machine
So, what are phantom types?. Now, normally when you require a specific type in the parameter you use it in the method body (say, when you have sum(List<Integer> xs) you'll use the fact that you have a list of Integers to sum them) , but what happen if you don't? Now you have a parameter type that never appears in the body, although is there, requiring that specific parameter in the type and preventing compilation if doesn't match. That's a phantom type :)

A simple example
Here an example: let's model a plane that can be either flying or landed and a takeOff and land methods that can only be applied to landed and flying planes respectively.
First, let's define the different flight status as marker interfaces:

Now, our plane class parametrized by the flight status:

And finally, our flight controller class with the takeOff and land methods:

The interesting part is in the land and takeOff methods. For example, in the land method, we require a Plane<Flying> but we just return a landing plane, (without using the Flying interface in the body). That's how we enforce that a plane must be flying to be able to land.
What I wanted to show with this is pretty silly example is how you can use phantom types to enforce some rules.

What are they good for?
Ok, now you have a way to require at compile type certain parameter on a type, what can you use it for?
Turns out it you can use to enforce many constraints:
Enforce a particular state: in the previous example, we used phantom types to require a specific state in a method (flying/landing in this case). In the same way we can require a connection to be open when we do a query or close it:

public ResultSet execute( Connection<Open> c, Query q) ....

public void close( Connection<Open> c) ....

(but is not safe, will work a better example)

You can also use it for safer Ids:
Usually Ids are Int or Strings, and is very easy to mix them up, e.g. in buy(String productId, String customerId) you can swap the Ids by mistake and you can get subtle bugs (the productId might match a customerId). With phantom types you can define an Id class parametrized by the entity and you get buy(Id<Product> productId, Id<Customer> customerId) and you'll get a compiler error if you pass a product id where you expect a customer id.
The full example (in Scala):

Go ahead and Type!
As you see, phantom types are pretty straightforward and gives you more expressive power (in particular, will allow you to get more mileage from Java's type system). I hope they get more use in Java...

Some useful links:
https://michid.wordpress.com/2008/08/13/type-safe-builder-pattern-in-java/
http://maniagnosis.crsr.net/2010/06/phantom-types-in-java.html
http://www.haskell.org/haskellwiki/Phantom_type
http://en.wikipedia.org/wiki/Phantom_types
https://ocaml.janestreet.com/?q=node/11
http://stackoverflow.com/questions/5881301/implementing-phantom-types-in-c-sharp

Edit:
There's an interesting discussion in reddit

Note:
The connection example is a misleading, as you'll still can hold a reference to the open connection and attempt stuff, I will work a better example.

A (purely functional) Turing Machine simulator in Scala

noreply@blogger.com (Anonymous) — Fri, 06 Apr 2012 08:17:00 +0000

Why?

While preparing for the exam for a Language Theory course I took, I have many exercises requiring to draw turing machines. Having to verify them manually is pretty cumbersome, so just for fun I set out to write one in Scala and stay in a pure functional style.

If you want a definition of a turing machine you can always go to wikipedia , but simplifying (a lot), you can see it as a finite state machine with a read/write head over an infinite tape.

The implementation

First we need to model the tape. We just need four operations: move left, move right, read, and write. Your typical functional immutable list is not the best for that, as there's no way to go back (left) and moving ahead (right) is O(n). Doing it with an array or double linked list is trivial but they're mutable, we're stuck!

If you think about it, we need to go step by step forward and change the head, for that the normal immutable list is perfect, but how we go back step by step?
Any idea?
What if we keep another list with the elements we'll find if we go backwards? Then, advancing thought the list is just a matter of taking the head of the forward list and adding as head of the backward list and vice-versa. As a plus, to add/update/remove we just change the head of the forward list.
Does it make sense? Congratulations, we just reinvented/discovered the List Zipper ! (as usual, there's a nice explanation in "Learn you a Haskell..." )

A Zipper

Simple zipper implementation in Scala will look like:

The Tape

We're going to adapt the idea to model our tape with a couple of tweaks: first to better represent the concept of the read/write head in the tape, we're going to keep the element under focus separated form the list (actually is the same as working with the head of the list in the zipper, but when I started with the implementation I thought it could be easier to understand this way ). The important tweak is that the previous list zipper implementation works on a finite list, but our turing machine operates on an infinite list, so we need to adapt the left/right (or forward/back) operations to check when the list is empty and add a new blank element, so we never "fall off". So, our tape will look like:

To make things easier on notation, we can also define two vals holding the right and left functions:

The interpreter

Once the infinite tape is in place, the rest of the turing machine is easy: we need a state machine that based on the current symbol under the head and the current machine state, decides whether to write, move the head right or left and what's the next state. Using maps for those transitions is very straightforward: We use a map from the current state to a map from the current symbol

You can think of the transition as a function T: State x Symbol => (State, Symbol,Move)

Or in types:

With that, the core of our Turing Machine (the interpreter), is pretty simple:

We have q: the current state, t:the tape (and head), tm is the transition matrix and qf is the final state, because we need to know when to stop. If we're in the final state, we return the tape, if not, we look-up the state, symbol and move for the current state and symbol on the head of the tape and recursively call step again with the new state, the result of writing the new symbol on the tape and the same transition matrix and final state. Because the call to step is the last function we call, we can optimize the recursive call with @tailrec.

An example

Here is an example, the turing machine I wanted to test is the following:

Given an imput string in the form bn#1^k , where bn is a binary representation of number n and 1^k are '1' repeated k times, we want to calculate the binary number bn+k . ( i.e. incrementing bn by k)

If we run the program, you'll see the expected results:

10
100
1010
10000
11
100

You can check the full code in github: https://gist.github.com/1258371

Well, that's all :)

Conclusion

There's an important conclusion to this: we implemented a Turing Machine in a purely functional way.

If we encode the Universal Turing machine in the transition table, we can feed the program itself on the tape. Because is purely functional, we can directly translate our program to lambda calculus, thus proving* that the lambda calculus is as powerful as a turning machine. If we come up with a lambda calculus implementation in a turing machine, you have the equivalence of the turing machine/lambda calculus models. Hint: implementing the lambda calculus interpreter in a turing machine is not far from what the Scala compiler and the JVM are doing in this case (or a Haskell interpreter for what is worth)

*some handwaving required (or a lot), we're just fleas standing in the shoulder of gigants

Yes, Virginia, Scala can save you from Null Pointer Exceptions.

noreply@blogger.com (Anonymous) — Sat, 08 Oct 2011 04:26:00 +0000

First, Virginia, let me tell you that I don't know why everybody in the Scala community is writing to to you, I guess is because you're curious and want to learn about it, or maybe you know where to find the mythical "average programmer". But I digress...

Let's focus on the subject of this post: how you can prevent null pointer exceptions with Scala. Suppose you have your tidy Scala code in functional flavor with all the fixes, and you need to do a series of calls to a Java library, where each value depends on the previous value: let's say you want to call functions A,B,and C.
val x=A(in)
val y=B(x)
val z=C(y)

(or C(B(A(in))) if you like )

Now, is common in Java to return null when no value can be returned or even throw an exception if something goes wrong. How we prevent that? The naive approach will be to chain the ifs:

   val x=A(in)
   if (x != null){
   val y=B(x)
     if (x != null){
   val z=C(y)
   }
   }

I don't know you, but for me that style doesn't cut it anymore, is too verbose! And now our flow is littered with null checks, obscuring the purpose.
So, what we can do? I know! Let's use Scala's Option and write a small function that returns "Some" value or "None" if we got null or something wrong happened:

Nothing fancy here, Option(x) will evaluate x and return Some(x) if it has a value or None if is null. The only noteworthy thing here is in the signature: it defined as " x:=> T " that roughly means "any function that returns something of type T", so x will be evaluated when we actually use it and not when we call the function, otherwise we risk getting the exception before entering the try block.

Ok, so now we wrap every function call with our unsafeCall function, but now we have a problem, the types don't match! We can't just chain the calls, we need to extract the value from the Option first!
We can try with pattern matching:

A(x) match {t
case None => _
case Some(y) => B(y) match {
case None => _
case Some(z) => C(z)
}
}

But it looks clumsy and we don't gain much compared to the "if not null" version, what we can do?
Let's take a step back and look at the types: we want to chain a series of function with T=>Option[T] ... does it ring a bell? What if we write as T=>M[T] ? If you've said the M-word, bingo!
Some[_] is a monad, and that means we can use Scala's "for" notation.
Let's tie everything together in one example:

ADENDUM: This is a toy example for illustrative purposes. I guess I should have left out the exceptions, otherwise is almost the same result as surrounding everything with a try/catch. Also, is an exception happens, we want to know what happens, for that Either is more suitable than Option (I'll leave that for another blog post). Still, when you need to chain a series of functions that return Some/None, for comprehensions gives you a nice sugar ;)

Functors, Applicative Functors, and Monads aren't that scary

noreply@blogger.com (Anonymous) — Thu, 18 Aug 2011 05:38:00 +0000

I'm currently reading "Learn You a Haskell for Great Good" (really great book, if you want to learn Haskell, you can read it online or better, buy it now! ) and it has a very good explanation of Functors, Applicative Functors, and Monads. I refuse to write another Monad tutorial (I'm not knowledgeable enough) but I'll write about what I've understood so far. (Be kind enough to correct me)

Here is all you need to know about functors, applicative functors, and monads (Haskell code):

Or it's equivalent Scala code:

Crystal clear, isn't it? Just kidding.
IMPORTANT NOTE:THIS ARE ONLY THE THE TYPE SIGNATURES, ANY IMPLEMENTATION HAVE TO COMPLY WITH THE FUNCTOR/MONAD LAWS (see ADENDUM at the bottom)

The TL;DR version
Want to apply a function to things in some "context"? Use a functor.
The functions are already in some "context"? Use applicative functor.
What if your function put things in the "context"? Use a Monad (... and flatMap that shit!)
That's all you need to know.

Functor
Let's start with the functor.
First, the trait has a type parameter, T[_] (it's a polymorphic type constructor or higher kinded type, but you aren't the type that get scared easily, right?)
For now, you can consider it as a "context": it can be a data structure, like a list, or something else that holds the parameter type inside plus whatever you want to add.
Let's look now at the method signature:
def fmap[A,B](f:A=>B)(ta:T[A]):T[B]
You take a function f from A to B, and ta context of A and returns a context of B.
In Scala collections is the map function. It transforms T[A] into T[B] by applying f to the elements wrapped "inside" T[A].
That's all you need for a functor! It doesn't look that scary...

Applicative Functor
Now let's look at the applicative functor. For starters, the applicative functor is also a functor (I guess the "functor" in the name is a big hint) so we have the map function available.
With map, you can apply functions to things already in some context, but what if what you have in the context are functions? you need more than fmap to apply them.
Enter the applicative functor.
The applicative functor defines two methods pure and <*>:
def pure[A](a:A):T[A]
Pure is for putting things in the context, it takes an element of A and returns that element in the minimal context that makes sense (e.g. for lists, would be a list with a single element a).
The next function, "apply" or <*> (you can call it advanced TIE fighter or clenched angle arse if you want) takes functions already in the context and applies them to values in the context, yielding the results also in the context. The way it combines the functions with the values depends on the implementation of the applicative functor itself (e.g. for lists, it applies every function in the list of functions to every value in the list of values).
You can see Tony's message to the Scala mailing list for an amazing example of why the applicative functor is useful.

Monad
And now, the famous Monad !. Monads are applicative functors, but with another method ">>=" (in Scala, you know it as flatMap ). We saw that applicative functors are like functors but the <*> allows you to apply functions already in a context unlike fmap wich needs the functions directly. But what if you have a function that takes a value of A (outside a context) and returns a value of b in the context? (they're pretty common: think of a function that may fail, returning Option[A] ). To apply those kind of functions to things already in the context is why we have >>= function: is pretty similar to the applicative functor's "apply" but instead of a function already in context, it takes a function from A to a context of B.

For my next post, I want to show that using Option as a monad in Scala CAN save you from NullPointerExceptions...

Notes:

Eric explained most of this way better than me in "The essence of the iterator pattern"
The traits above are just for illustrative purposes, for the real thing use Scalaz
I'm no authority, take all I've said with a grain of salt, I just hope it helps in your explorations. For me, applicative functor was the missing piece in my understanding of monads.

ADENDUM: There's a great (and WAY better than mine) explanation of all of this in Haskell's Typeclassopedia. I don't know why nobody called me on it, but to actually have an instance of Functor/Applicative/Monad the implementation has to obey the following laws:

Functor laws
fmap id = id
fmap (g . h) = fmap g . fmap

Applicative Functor laws
pure id <*> v = v -- Identity
pure (.) <*> u <*> v <*> w = u <*> (v <*> w) -- Composition
pure f <*> pure x = pure (f x) -- Homomorphism
u <*> pure y = pure ($ y) <*> u -- Interchange

Monad laws
m >>= return = m -- right unit
return x >>= f = f x -- left unit
(m >>= f) >>= g = m >>= (\x -> f x >>= g) -- associativity

Short break for a long hiatus

noreply@blogger.com (Anonymous) — Fri, 16 Jul 2010 02:40:00 +0000

Hi! Anybody out there?
I guess twitter totally killed whatever energy I had for blogging :)
For lazy people like me, the fact that instead of inaccurately express your idea in a couple of paragraph you're able to slap one phrase and that's enough is fantastic... it doesn't even need to be coherent!

Noteworthy things that happen in between (in no particular order whatsoever):

I'm learning Scheme by the AWESOME book "The Little Schemer" (Amazon link: The Little Schemer - 4th Edition) and using PLT Scheme / Racket. I'm getting over to my aversion to prefix notation and now I can somehow understand Lisp code and I'm getting ready to learn Clojure
I'm back in my home country, Uruguay (go team! we made it to the semifinals!!)
I badly broke my ankle, had two surgeries and I still limp after a couple of months
I'm expecting another baby!
Scala 2.8 is out!!!!!!! Go get it while still hot
I need to learn Haskell
I went to the east coast Scala lift-off and meet awesome people
Don't be afraid of powerful languages, believe it or not, they make your life easier
I bought more Star wars legos than I needed
I have a couple of unfinished blog posts that someday I'll finish :)

Thanks for stopping by, I'll promise more useful posts in the future.
(I'm adding a totally unrelated picture of a alien spider I found lying on a wall)

Boolean Algebra Internal DSL in Scala (aka fun with Unicode names )

noreply@blogger.com (Anonymous) — Tue, 02 Jun 2009 23:17:00 +0000

In Scala, operator names can be characters from the unicode set of mathematical symbols (Sm) or other symbols (So). That can lead to interesting possibilities:

val Π = Math.Pi def √(x:Double)=Math.sqrt(x) val x= √(9*Π)

Here, "Π" is just another constant and "√" is a function like "q".
(To use unicode in eclipse, you have to go to Preferences->General->Workspace, and change the text encoding to UTF-16)

Another example: with the ∑ and ∏ you can have define summation and the product of a sequence as follows:

def ∑(r:Range)(f:Int =>Int)=r.reduceLeft(_+ f(_)) def ∏(r:Range)(f:Int =>Int)=r.reduceLeft(_* f(_))

And now we can write:

val s= ∑(1 to 100)(x=>x^2) val p= ∑(1 to 100 by 2)(x=>x^2) val y= ∏(1 to 30 by 3)(_)

Of course, I'm not advocating using Scala as a substitute of a specific mathematical tool, besides, there's already a "language with symbols" (btw, I wonder if one can make a Scala "skin" that looks like APL). I'm not sure how other languages can do this (except APL maybe?), but this goes to show the power of Scala for "internal DSL".

For a slightly more complex example, let's define an internal DSL for boolean logic, with the appropriate symbols: ¬,V,Λ,and →.

class LogicBoolean(val value:Boolean) { import LogicBoolean.¬ override def toString=value.toString def V(b:LogicBoolean)=new LogicBoolean(this.value || b.value) def Λ(b:LogicBoolean)=new LogicBoolean(this.value && b.value) def →(b:LogicBoolean)=(¬(this)) V (this Λ b) } object LogicBoolean { def ¬(a:LogicBoolean)=new LogicBoolean(!a.value) implicit def boolToLogicBool(x:Boolean)=new LogicBoolean(x) }

The only prefix operators that can be defined in Scala are ‘+’, ‘’, ‘!’ or ‘~’, so no luck for ¬. But we if we define it as a function, we can import it and use it (almost) like a prefix op. As we want an implicit conversion from boolean to our LogicBoolean class, a companion object is the ideal place to put both. By importing all the methods in the companion, we bring the ¬ operator and the implicit conversion into scope:

import LogicBoolean._ val A=true val B=false println("¬A :"+ ¬(A)) println("¬B :"+ ¬(B)) println("A Λ B :"+ (A Λ B)) println("A V B :"+ (A V B)) println("A → B :" + (A → B)) println("B → A :" + (B → A))

With everything in place, with a for comprehension is very easy to print the truth tables of any complex formula (just be careful with the precedence, use parenthesis):

import LogicBoolean._ val r=List(true,false) def expr(a:Boolean,b:Boolean,c:Boolean,d:Boolean)= ( (a Λ b) V ¬(a Λ c) ) Λ ((c V d) Λ ¬(b) ) //let's print the truth table println ("\na\tb\tc\td\t(a Λ b) V ¬(a Λ c) ) Λ ((c V d) Λ ¬(b)") for ( a <- r; b <- r; c <- r; d <- r ) println (a+"\t"+b+"\t"+c+"\t"+d+"\t"+expr(a,b,c,d))

If you run the examples you get:

¬A :false ¬B :true A Λ B :false A V B :true A → B :false B → A :true a b c d (a Λ b) V ¬(a Λ c) ) Λ ((c V d) Λ ¬(b) true true true true false true true true false false true true false true false true true false false false true false true true false true false true false false true false false true true true false false false false false true true true false false true true false false false true false true false false true false false false false false true true true false false true false true false false false true true false false false false false

The ability to easily adapt the language to looks like the domain is one of the main selling features of languages like Lisp. Though Scala is no way like Lisp, it can go very far in the "internal DSL" direction and provides many features to make that easy.

EDIT: Something very similar in Ruby

My take on 99 problems in Scala (23 to 26)

noreply@blogger.com (Anonymous) — Fri, 22 May 2009 00:07:00 +0000

I have lot of things going on, but a quick post. Here are 5 more problems solved in Scala.
Note: in all this and the previous solutions, I've left out (most of the time) boundary conditions checks, to keep the code simple and as elegant as possible.

P23: Random select. We reuse P20 (removeAt) and remove a random element of the list recursively.



//P23

  def randomSelect[A](n: Int, xs: List[A]): List[A] = (n, xs) match {
    case (_, Nil) => Nil
    case (0, _) => Nil
    case (_, _) => {
      val x = removeAt(new Random().nextInt(xs.size), xs)
      x._2 :: randomSelect(n - 1, x._1)
    }
  }

P24: lotto. we create a list (well, actually is a range converted to a list) of the numbers and use P23 to select a random draw.



//P24

def lotto(n:Int,max:Int):List[Int] =randomSelect(n,(1 to max).toList)

P25: random permute. That's easy: we use P23 to do a randomSelect on the whole list



//P25

def randomPermute[A](xs:List[A]):List[A] =randomSelect(xs.size,xs)

P26: combinations. That one wasn't straightforward, I actually had to think! :)
But the solution can be defined recursively:
to get the combinations of size n, take one element of the set and append it to all the combinations of sets of size n-1 of the remaining elements, union the combinations of size n of the remaining elements.
I had to create an auxiliary function that "lift" a list into a list of lists, (kind of the opposite of flatten).



//P26

  def combinations[A](n: Int, xs: List[A]): List[List[A]] = {
    def lift[A](xs: List[A]): List[List[A]] = xs.foldLeft(List[List[A]]())((ys, y) => (List(y) :: ys))

    (n, xs) match {
      case (1, ys) => lift(ys)
      case (i, xs) if (i == xs.size) => xs :: Nil
      case (i, ys) => combinations(i - 1, ys.tail).map(zs => ys.head :: zs) ::: combinations(i, ys.tail)
    }
  }

My take on 99 problems in Scala (first 22)

noreply@blogger.com (Anonymous) — Tue, 28 Apr 2009 04:24:00 +0000

A while ago I saw 99 problems in Prolog they looked really good and I started trying to solve them in Scala. Now, thanks to Tony Morris I found that there's a Scala version!
Nice stuff to get your skills up to shape. It helped me to improve my understanding of folds, maps, flatMaps, zips, etc. Also I learned new pattern matching techniques (tuples and guards).
You must really give the exercises a shot!
Here are my solutions:

package exercises

object NinetyNine {
  //P01
  def last[A](xs: List[A]): A = xs match {
    case x :: Nil => x
    case x :: xs => last(xs)
    case Nil => throw new NoSuchElementException
  }

  //P02
  def penultimate[A](xs: List[A]): A = xs match {
    case x :: y :: Nil => x
    case x :: xs => penultimate(xs)
    case _ => throw new NoSuchElementException
  }

  //P03
  def nth[A](i: Int, xs: List[A]): A = xs match {
    case x :: xs => if (i == 0) x else nth(i - 1, xs)
    case _ => throw new NoSuchElementException
  }

  def nth2[A](i: Int, xs: List[A]): A = xs match {
    case x :: xs if (i == 0) => x
    case x :: xs if (i > 0) => nth(i - 1, xs)
    case _ => throw new NoSuchElementException
  }

  //P04
  def length[A](xs: List[A]): Int = xs match {
    case x :: xs => 1 + length(xs)
    case Nil => 0
  }

  //Although straight recursion is fun, using folds is more effective
  // folds are abstractions for recursion over data structures

  //P04
  def length1[A](xs: List[A]): Int = xs.foldLeft(0)((a, b) => a + 1)

  //P05
  def reverse[A](xs: List[A]): List[A] = xs.foldLeft(Nil: List[A])((a, b) => b :: a)

  //P06
  def isPalindrome[A](xs: List[A]): Boolean = reverse(xs) == xs

  //P07
  def flatten[A](xs: List[List[A]]): List[A] = xs.foldRight(Nil: List[A])(
    (xs, acc) => xs match {
      case ys: List[A] => ys ::: acc
      case y: A => y :: acc
    })

  //P08
  def compress[A](xs: List[A]): List[A] =
    xs.foldRight(List[A]())((y, ys) =>
      if (ys != Nil && ys.head == y) ys else y :: ys)

  //P09
  def pack[A](xs: List[A]): List[List[A]] = xs match {
    case Nil => Nil
    case _ => xs.takeWhile(_ == xs.head) :: pack(xs.dropWhile(_ == xs.head)) //can use span too, see P13
  }

  //P10
  def encode[A](xs: List[A]): List[(Int, A)] =
    pack(xs).map(y => (y.length, y.head))

  //P11
  def encodeModified[A](xs: List[A]): List[Any] =
    pack(xs).map(
      y => if (y.length == 1) y.head else (y.length, y.head))

  //Type safe version
  def encodeModifiedTypSafe[A](xs: List[A]): List[Either[A, (Int, A)]] =
    pack(xs).map(
      y =>
        if (y.length == 1) Left(y.head)
        else Right(y.length, y.head))

  //P12
  def decode[A](xs: List[(Int, A)]): List[A] = {
    def expand(i: Int, a: A): List[A] = if (i == 0) Nil else a :: expand(i - 1, a)
    flatten(xs.foldRight(List[List[A]]())((y, ys) => expand(y._1, y._2) :: ys))
  }
  //is better with flatMap
  def decode1[A](xs: List[(Int, A)]): List[A] =
    xs.flatMap(ny => List.make(ny._1, ny._2))

  //P13
  def encodeDirect[A](xs: List[A]): List[(Int, A)] = xs match {
    case Nil => Nil
    case _ => {
      val ys = xs.span(_ == xs.head)
      (ys._1.length, xs.head) :: encodeDirect(ys._2)
    }
  }

  //P14
  def duplicate[A](xs: List[A]): List[A] =
    xs.foldRight(Nil: List[A])((y, ys) => y :: y :: ys)
  //is better with flatMap
  def duplicate1[A](xs: List[A]): List[A] = xs.flatMap(y => y :: y :: Nil)

  //P15
  def duplicateN[A](n: Int, xs: List[A]): List[A] =
    xs.foldRight(Nil: List[A])((y, ys) => (1 to n).toList.map(_ => y) ::: ys)
  //is better with flatMap
  def duplicateN1[A](n: Int, xs: List[A]): List[A] =
    xs.flatMap(y => List.make(n, y))

  //P16
  def drop[A](n: Int, xs: List[A]): List[A] =
    xs.zipWithIndex.filter(_._2 % n != 0).map(_._1)

  //P17
  def split[A](n: Int, xs: List[A]): (List[A], List[A]) =
    xs.splitAt(n) // or (xs.take(n),xs.drop(n))

  //ok, that was too easy, let's try recursion
  def splitRec[A](n: Int, xs: List[A]): (List[A], List[A]) =
    (n, xs) match {
      case (0, _) => (Nil, xs)
      case (_, y :: ys) => {
        val rec = splitRec(n - 1, ys)
        (y :: rec._1, rec._2)
      }
      case (_, Nil) => (xs, Nil)
    }

  //P18
  def slice[A](s: Int, e: Int, xs: List[A]): List[A] =
    xs.slice(s, e) // or xs.drop(s).take(e-s)

  //with recursion
  def sliceRec[A](s: Int, e: Int, xs: List[A]): List[A] =
    (s, e, xs) match {
      case (0, 0, xs) => Nil
      case (0, _, y :: ys) => y :: sliceRec(0, e - 1, ys)
      case (_, _, y :: ys) => sliceRec(s - 1, e - 1, ys)
    }

  //P19
  def rotate[A](n: Int, xs: List[A]): List[A] = {
    val s = split((if (n > 0) n else n + xs.length), xs)
    s._2 ::: s._1
  }

  //P20
  def removeAt[A](n: Int, xs: List[A]): (List[A], A) = {
    val (heads, tails) = split(n, xs)
    (heads ::: tails.tail, tails.head)
  }

  //P21
  def insertAt[A](e: A, n: Int, xs: List[A]): List[A] = {
    val (heads, tails) = split(n, xs)
    heads ::: e :: tails
  }
  //with recursion
  def insertRecAt[A](e: A, n: Int, xs: List[A]): List[A] =
    (n, xs) match {
      case (0, ys) => e :: ys
      case (_, y :: ys) => y :: insertRecAt(e, n - 1, ys)
    }

  //P22
  def range[A](s: Int, e: Int): List[Int] = (s to e).toList

  //I don't think is the purpose of the exercise! Again, let's try recursion
  def rangeRec(s: Int, e: Int): List[Int] = if (e - s == 0) e :: Nil else s :: rangeRec(s + 1, e)

  //recursion and pattern matching with guards
  //a little more readable
  def rangeRecPm(s: Int, e: Int): List[Int] = (e - s) match {
    case x if (x > 0) => s :: rangeRecPm(s + 1, e)
    case x if (x == 0) => e :: Nil
    case _ => error("Invalid range")
  }

[EDIT: fixed problem 20 ]

Spare change at the whole Static-vs-Dynamic thingy

noreply@blogger.com (Anonymous) — Tue, 07 Apr 2009 20:50:00 +0000

(NOTE: I'm a software developer, I have a blog, clearly I MUST write about static-vs-dynamic ... I guess soon I'll be writing a monads tutorial)

With all the fuss about Twitter migrating (the back-end) from Ruby to Scala (w00t!), the whole static-vs-dynamic debate has been re-ignited.
As a disclaimer, I'm in the static typing "camp". I've tried Ruby but didn't spark anything. In "dynamic languages", I have more experience with JavaScript (and for the record, I think is awesome: a true underdog of programming languages).
While I can appreciate the freedom and speed of development of dynamic languages, and I think is a matter of personal styles than about which one is better ("choose your own poison"), I think static typing suits better my frame of mind while creating software.
Anyhow, I felt something was missing in the debate and Twitter's use of "kind_of?" points to one of the reasons for static typing I been trying to articulate for a while.
(First and foremost: if you're going to complain "static typing forces me to add a lot of boilerplate and cruft", look into Haskell, ML, Scala, or F# and then come back or you'll force me to do evil things to cute creatures. And if you want to learn how a type system can be used to PROVE that a program is correct, look into Coq)

Types reduces the possible combinations between components
Any software program can be seen as a system of interconnected elements (modules/functions/objects, etc.), by adding type information you're restricting the ways those elements can connect to each other and the possible execution paths of the system. By doing that, you're loosing some of the valid combinations, you're also trimming many invalid ones.
The argument is with good unit tests you can check for the same things, but you have to actually write the code for that. While you should have unit tests for your module, without type restrictions, you have to write and test more execution paths. Moreover, writing the test, executing it and analyzing the result are separate steps, where your brain has to switch contexts.

Types as a Poka-Yoke
There's a lot of influence of Lean Manufacturing in software development (all the "Agile" stuff ), and from that perspective, having more restrictions on how you can use the available components acts like a poka-yoke mechanism: "a behavior-shaping constraint, or a method of preventing errors by putting limits on how an operation can be performed in order to force the correct completion of the operation". The same Lean / Total Quality Management recommends catching defects as early as possible and not use testing as a product quality measure. How more agile can you be when you don't have to write and run test to achieve a basic level of integration quality?

Types as (kind-of) contracts
By using static typing you get self-documenting self-enforcing operation contracts (for a price). I believe the larger and more complex the system, the more static typing can help than hinder your work.
NASA could have saved some money if they were able to write:



class MarsObiter {

def setThrust(v:Thrust[MetricUnits])= ...

There's no way you can use a Thrust[ImperialUnits] instead. (For extra points, you can define an implicit conversion in Scala :D )
But even if you have a basic type system like Java, don't just suffer it, use it at your advantage, create the types that can help you to write better code.
Check Stephan's excellent post on what do you loose if you use only primitive types with no semantic meaning (or no types at all)

Enough!
But enough babbling, I can show some examples using the "lowly" Java language:
Suppose we have a method to book a shipment for a customer and a container on a specific date.
Let's start without any typing information:



public bookShipment(customerId, containerId, shipmentDate){...

Totally valid, but... is "1234-321" a valid customerId? can I use a string as shipmentDate? in which format? What I get back?
Let's improve things a little by adding some basic typing information:



public boolean bookShipment(int customerId, int containerId, Date shipmentDate){...

Well, now I now that "X123Z" is not a valid customer or that "MRSK0023" is not a valid container, the date must be a proper date object, and it doesn't take a PhD to infer that will return true if the booking is successful.
But still, nothing prevents me to swap customerId with containerId and get a nasty but subtle bug. Wouldn't be nice if the compiler can prevent that? Well, it can if you don't use primitives and use more domain meaningful types, giving you a DDD flavor (and that's a win-win situation)



public boolean bookShipment(Customer customer, Container container, Date time){...

By examining the signature we know we can't pass a Container when a Customer is expected, and the method reflects better the domain of the application and tries to move towards "an ubiquitous language". But we can improve that:



public bookShipment(customer, container, shipmentDate) { ...

Here Hindley-Milner type inference takes care of identifying the input and output paremeters. No need to declare a thing and still type safe!
(although for documentation/readability purposes, I prefer explicit type declarations, and seems that the Haskell community agrees... that's why I don't mind typing the types of methods in Scala)

The whole point about all this? Go back and get things done, use whatever suites you best and don't waste your time reading blogs and stuff ;-)
If you excuse me, I need to step down from my tittle soapbox and go to do some coding...

Quote of the month

noreply@blogger.com (Anonymous) — Thu, 02 Apr 2009 00:07:00 +0000

"Bad programming is easy. Idiots can learn it in 21 days, even if they are dummies."

How to Design Programs, 2nd Edition

Flavors of Curry: Scala vs Haskell

noreply@blogger.com (Anonymous) — Mon, 09 Feb 2009 00:44:00 +0000

Scala is a nice language to explore functional programming, and for me it was easy to use it as a “stepping stone” and jump to Haskell with all the purity and laziness (I think is because I'm the kind of guy that enter slowly in the cold water...). I'm using Haskell to learn the theory and tools of functional programming (in a language that forces you to), so I can use them in Scala.

To that end, I'm going through “Learn You a Haskell for Great Good!” (I seem to have a fondness for technical books with silly images). Usually I'll try to do the same exercises in Scala to compare.

I was going through the chapter about higher order functions and currying. What are curried functions? You can find a very good explanation in wikipedia (of course!). Basically is the transformation of a function with multiple parameters into another function with only one parameter that returns a function of the remaining parameters. With that, your language can care only about functions with only one parameter and still be equally powerful. The advantage is if you call a function with less parameters, you get a partially applied function.

One of the examples on the “Learn you...” is a “flip” function: a function that exchanges the first and second parameter of a given function. In Haskell is as easy as:

flip1 f x y = f y x

That's all! Hindley-Milner type inference ensures the type safety:

flip1 :: (t1 -> t -> t2) -> t -> t1 -> t2

As an example:



f x y =x/y

f 1 2

0.5



g= flip1 f

g 1 2

2.0

BTW, there's something odd:



Prelude> let flip1 f x y = f y x

Prelude> :t flip1

flip1 :: (t1 -> t -> t2) -> t -> t1 -> t2

Prelude> let f x y =x/y

Prelude> :t f

f :: (Fractional a) => a -> a -> a

Prelude> let g=flip f

Prelude> :t g

g :: Double -> Double -> Double

Prelude> :t flip1 f

flip1 f :: (Fractional t1) => t1 -> t1 -> t1

The type of flip1 f is (Fractional t1) => t1 -> t1 -> t1, meaning that t1 is restricted to be of Fractional typeclass, but if I bind g to flip f, now the type is Double... that's not what one would expect! (Any Haskell expert can tell me what's happening?)

As usual, I'll tried to do the same in Scala to see how far it can goes.
The main difference is of course, type inference: in Scala you need to declare the function types. The other major difference is Haskell every function is curried by default, in Scala you need to explicitly curry the function by separating each parameter between parentheses.

In Scala, our (curried) f function will be:



def f(x:Int)(y:Int)=x/y

f: (Int)(Int)Int

The flip function in Scala would be:



def flip1[A,B,C]( f:A=>B=>C)(x:B)(y:A) =f(y)(x)

flip1: [A,B,C]((A) => (B) => C)(B)(A)C

Is clearly more verbose than the Haskell version, but equally powerful:



def g = flip1 (f) _

g: (Int) => (Int) => Int

The underscore is needed to get the partially applied function and the f must be in parentheses (again, all curried parameters must have their own parentheses).

Conclusion? Nothing. Haskell and Scala are obviously different, but they share some common ground... just wanted to show it :)

Playing with Scala 5 ½: More variations

noreply@blogger.com (Anonymous) — Fri, 19 Dec 2008 03:22:00 +0000

As James pointed out, the implicit conversion creates a new object every time we convert the Node to Ordered[Node], and although the JVM and the GC can deal pretty well with that kind of scenario, it will be better if we can avoid the creation of the object (BTW, the fact that Scala can leverage years of work on JIT optimizations is something that shouldn't be taken lightly... I still want tail call optimization, though)

We need to add the Ordered trait for Node somewhere in the hierarchy. The reasonable place is when we add the Weight trait (once we have weight we can compare the nodes):

class DfsNode extends NodeImpl with Weight with Ordered[DfsNode]{

...

def compare(y: Node): Int = this.weight.compare(y.weight)

}

Now we can compare the nodes by their weight: “lighter” nodes are before “heavier” nodes, but the comparation is not what we need for the priority queue, we need to reverse the the ordering.

The most immediate way is just reverse DfsNode's comparation function:

def compare(y: Node): Int = -this.weight.compare(y.weight)

but this has the undesirable effect of reversing all the node comparations, and most of the time I'll bet we want to have the lighter nodes before the heavier ones, the reverse is counter-intuitive (and the potential source of nightmares). The solution? Let's create our particular flavor of DfsNode with the comparation reversed to use it in the PriorityQeue:

class PQNode extends DfsNode {

override def compare(y: Node): Int = -super.compare(y)

}

And we just need to change our newNode method to return PQNodes instead of DfsNodes:

protected def newNode: Node = new PQNode

For extra points on modularization, we can extract those changes and the code related to the algorithm in a subclass of DfsGraph.

Here is the complete code:


package dfs2;
 
abstract class Graph {
  type Edge
  type Node <: NodeIntf
  abstract class NodeIntf {
   def connectWith(node: Node): Edge
  }
  def nodes: Set[Node]
  def edges: Set[Edge]
  def addNode: Node
}
 
abstract class DirectedGraph extends Graph {
  type Edge <: EdgeImpl
  class EdgeImpl(origin: Node, dest: Node) {
    def from = origin
    def to = dest
  }
 
  class NodeImpl extends NodeIntf {
    self: Node =>
    def connectWith(node: Node): Edge = {
     val edge = newEdge(this, node)
     edges = edges + edge
     edge
    }
  }
  
  protected def newNode: Node
  protected def newEdge(from: Node, to: Node): Edge
  
  var nodes: Set[Node] =Set()
  var edges: Set[Edge] =Set()
  def addNode: Node = {
    val node = newNode
    nodes = nodes + node
    node
  }
}
 
trait Weight {
  var weight= Float.PositiveInfinity
}
 
import scala.collection.mutable.PriorityQueue;
 
class DfsGraph extends DirectedGraph {
  class DfsNode extends NodeImpl with Weight with Ordered[DfsNode]{
  var previous: DfsNode = _
  var label:String = _
  var nodeEdges: Set[Edge] = Set()
  
  override def connectWith(node: Node): Edge = {
    val newEdge=super.connectWith(node)
    nodeEdges = nodeEdges + newEdge
    newEdge
  }
    def -->(n2:Node):DfsEdge =connectWith(n2)
 
    override def toString()= label+ " w:"+weight
    def compare(y: Node): Int = this.weight.compare(y.weight)
  }
  
 
  class DfsEdge(origin:Node, dest:Node) extends EdgeImpl(origin, dest) with Weight {
    override def toString()= from.label+"-->"+to.label+" w:"+weight
  }
 
  def addNewNode(l:String):Node={
    val newNode=super.addNode
    newNode.label=l
    newNode
  }
 
  type Node= DfsNode
  type Edge= DfsEdge
 
  protected def newEdge(from: Node, to: Node): Edge = new DfsEdge(from,to)
  protected def newNode: Node = new DfsNode
  
}
 
class DijkstraSPGraph extends DfsGraph {
  
  class PQNode extends DfsNode {
    override def compare(y: Node): Int = -super.compare(y)
  }
  
  override protected def newNode: Node = new PQNode
  
  def shortestPath(start: DfsNode, end: DfsNode) = {
  val unvisited=new PriorityQueue[Node]()
    unvisited++=(nodes)
  start.weight=0
  while (!unvisited.isEmpty) {
    val vertx=unvisited.dequeue
        for (v <- vertx.nodeEdges if canImprove(v)){
          unvisited+improveDistance(v)
        }
  }
  }
  
  def canImprove(a:Edge)=(a.from.weight+a.weight< a.to.weight)
  
  def improveDistance(a:Edge) ={
    val v=a.to
  v.weight=a.from.weight+a.weight
  v.previous=a.from
    v
  }
 
  def pathToStart(end:DfsNode):List[DfsNode] = {
    if (end == null)
      Nil
    else
        end :: pathToStart(end.previous)
  }
}
 
 
object Example extends Application {
 
  val graph = new DijkstraSPGraph
 
  val n1=graph addNewNode "start"
  val n2=graph addNewNode "n2"
  val n3=graph addNewNode "n3"
  val n4=graph addNewNode "n4"
  val n5=graph addNewNode "n5"
  val n6=graph addNewNode "end"
  graph addNewNode "alone"
  
  n1-->n2 weight=2
  n1-->n3 weight=1
  n2-->n4 weight=1
  n3-->n4 weight=3
  n2-->n5 weight=1
  n4-->n6 weight=1
  n5-->n6 weight=3
  
  n1-->n6 weight=7
  n1-->n4 weight=10
  
  graph.shortestPath(n1,n6)
  println("Path")
  graph.pathToStart(n6).reverse.map(println(_))
  
}

Playing with Scala 5: improving code, use of views and comprehensions

noreply@blogger.com (Anonymous) — Mon, 15 Dec 2008 03:28:00 +0000

After reading about different optimization to pathfinding algorithms, I decided to improve my Dijkstra implementation by using a priority queue instead of a set for the unvisited nodes. Using the “weight” of the vertex as the priority, we can avoid searching the whole set for the minimum and we reduce the cost of the operation from O(n) to O(log n).

The first change is replace the set with Scala's priority queue:

val unvisited=new PriorityQueue[Node]()

But as it is, it will not compile: the priority queue's signature is

class PriorityQueue[A](implicit view$1 : (A) => Ordered[A]) extends ResizableArray[A] with CloneableCollection

You need to provide an implicit conversion from the parameter type A to the type Ordered[A]. But nothing to worry about: is as easy as

implicit def node2ordered(n: Node): Ordered[Node] = new Ordered[Node] {

//reverse the comparation so highest priority = lower cost

def compare(y: Node): Int = -(n.weight.compare(y.weight))

}

Look at the improveDistance function, it does two things: filters the nodes and updates the distance if we can improve it. I think is better if we split into two different functions, separating the filtering from the updating, so instead of:

def improveDistance(a:Edge) ={
if (a.from.weight+a.weight< a.to.weight) {
a.to.weight=a.from.weight+a.weight
a.to.previous=a.from
}
}

we get:

def canImprove(a:Edge)=(a.from.weight+a.weight< a.to.weight)

and

def improveDistance(a:Edge) ={

a.to.weight=a.from.weight+a.weight

a.to.previous=a.from

a.to

}

Then, instead of a function map over the nodeEdges, we have to filter and then map:

vertx.nodeEdges.map(improveDistance(_))

is replaced by

vertx.nodeEdges.filter(canImprove(_))).map(improveDistance(_)

that gives a better picture of the steps involved.

As we need to add the updated nodes to the priority queue so they can “float” to the top, the line would look like:

unvisited++ (vertx.nodeEdges.filter(canImprove(_))).map(improveDistance(_))

But I don't really think the explicit use of map and filter helps readability.

Enter Scala's for comprehensions: we can replace the map/filter with a comprehension:

for (v <- vertx.nodeEdges if canImprove(v)){

unvisited+improveDistance(v)

}

Nothing fantastic, but an improvement, isn't it?

For future posts, I'm planning on generalizing the algorithm into a A* pathfinding with different heuristic functions... stay tuned!

Simple Java tricks to protect your web application against SQL injection

noreply@blogger.com (Anonymous) — Thu, 23 Oct 2008 01:46:00 +0000

Your application is vulnerable to SQL Injection when you send unfiltered strings to the database. Most modern ORM frameworks should take care of it (but don't take my word!... go ahead and check how secure your framework is).
Sometimes, you have to work with plain JDBC (or ODBC). Here is a couple of tricks that help:

First and foremost, avoid concatenating strings for SQL queries. Use prepared statements unless is not possible (i.e. cases when you have undefined number of parameters)
Leverage the language type system: If you're passing a number, use Integer instead of String... any invalid character will fail the conversion and will not reach the DB.
If there's no option but concatenate strings, make sure the database comment quotes are escaped (for example, in DB2 you have to replace the single quote character with 2 single quote characters: instead of "SELECT * FROM users WHERE name='"+param+"'" use "SELECT * FROM users WHERE name='"+param.replaceAll("'","''")+"'"

For something a little more advanced, you can wrap the strings in some kind of "EscapedString" class, and use that class in the signature of the DAOs (related to 2. )

Note: by no means this is a comprehensive list. Application security is very hard, check your database documentation...

Java: The programming tool of choice for discriminating hackers

noreply@blogger.com (Anonymous) — Thu, 25 Sep 2008 03:49:00 +0000

In spite of all the Java bashing that's so in vogue this days, Team Smartass won the ICFP Programming Contest using Java, giving bragging rights to say that Java is "The programming tool of choice for discriminating hackers".
while(tongue in cheek){
take(this);
(lisp (snobs all))
fuctional_programing = Maybe[zealots]
ruby('fanboys')
}
Another proof of what matters is not the tool, is how you use it...

State machines using "Fluent interfaces/ DSL" in Java

noreply@blogger.com (Anonymous) — Tue, 26 Aug 2008 00:02:00 +0000

I always found state machines very useful for describing particular aspects of object behavior. A classic example can be a shopping order: it can be "pending","in progress", "shipped", etc.
In my previous project, I started with a simple design using a transition matrix. I must confess it didn't work well. It was hard to explain and it grew more complex as new requirements were added. I though it would be simpler if I didn't use any "fancy OO stuff" and advanced idioms. I've should know better!
This time I wanted to try something different, and based in my previous experiments with internal DSLs with Scala and my (very limited) knowledge of the patters to achieve that in java, I just went ahead and tried to come up with something useful and understandable. This time seems to be working: although it has some "magic" behind curtains is only in the creation and is very easy to add or modify the configuration class for new or updated states and events. Other members of my project were able to add and remove states and transitions with only a brief explanation.

The basic classes are pretty simple: State and Event.

package statemachine;

public class Event {

final private String label;

public Event(String newLabel){

label=newLabel;

}

/**

* @return Returns the label.

public String getLabel() {

return label;

}

public String toString(){

return label;

}

package statemachine;

import java.util.HashMap;

import java.util.Map;

public class State {

private final String label;

private final Map<Event,Transition> transitions= new HashMap<Event,Transition>();

//no public access to the constructor, must be in the same package

State(String newLabel){

this.label=newLabel;

}

void addTransition(Transition t){

transitions.put(t.getEvent(),t);

}

public State doEvent(Event e){

return (transitions.get(e)).getDestination();

}

/**

* @return Returns the label.

public String getLabel() {

return label;

}

/**

* @return Returns the transitions.

public Map<Event,Transition> getTransitions() {

return transitions;

}

You send a event to a sate and it returns the next state:
State newState=state.doEvent(event);
The State class holds a map of [event->state] (with the Transition class in the middle, for added effect :) )
As an extra safety measure, the State constructor and the addTransition method is accessible only to the package (well, unless you subclass it)
The "fluency" is provided by the Transition class (the useful methods return this to allow method chaining), so you can write:
new Transition(event).from(origin).to(destination)

package statemachine;

class Transition {

private State origin,destination;

private Event event;

public Transition(Event e){

event=e;

}

public Transition from(State orig){

origin=orig;

origin.addTransition(this);

return this;

}

public Transition to(State dest){

destination=dest;

return this;

}

/**

* @return Returns the destination.

public State getDestination() {

return destination;

}

/**

* @return Returns the event.

public Event getEvent() {

return event;

}

/**

* @return Returns the origin.

public State getOrigin() {

return origin;

}

How this will look? Suppose you have a pretty simple FSM:

Using the previous pseudoDSL/Fluent interface will look like:

package statemachine;

public class FSMDef {

public final static State SUBMITTED=new State("Submitted");

public final static State OPEN= new State("Open");

public final static State CANCELLED= new State("Cancelled");

public final static State CLOSED= new State("Closed");

//Events

static class Events {

public final static Event OPEN = new Event("Open");

public final static Event CLOSE = new Event("Close");

public final static Event REOPEN = new Event("Re-Open");

public final static Event CANCEL = new Event("Cancel");

}

static {

new Transition(Events.OPEN).from(SUBMITTED).to(OPEN);

new Transition(Events.CLOSE).from(OPEN).to(CLOSED);

new Transition(Events.REOPEN).from(CLOSED).to(OPEN);

new Transition(Events.CANCEL).from(OPEN).to(CANCELLED);

}

Doesn't seems too complex, right?
I'm just starting with this, and probably barely skim the surface (sure it has some drawbacks), but so far it worked :)

[EDIT: Fixed the generics declarations that were eaten by the HTML format. BTW, if anybody knows a good code formatter for blog posts, let me know ]

Scala: fold/reduce cheatsheet

noreply@blogger.com (Anonymous) — Tue, 22 Jul 2008 00:23:00 +0000

My fold/reduce 'cheat sheet' is something like:

For the list (a,b,c,d) fold/reduce is:

reduceLeft(f) => f(f(f(a,b),c),d)

foldLeft(Z)(f) => f(f(f(f(Z,a),b),c),d)

("applies the function from the left")

reduceRight(f) => f(a,f(b,f(c,d)))

foldRight(Z)(f) => f(a,f(b,f(c,f(d,Z))))

("applies the function from the right")

[EDIT: as you see, fold and reduce are essentially the same, but fold starts with an outside element ]

Questions, only questions

noreply@blogger.com (Anonymous) — Sat, 31 May 2008 02:26:00 +0000

Today I'm full of questions. Software development and programming is hard. Is a close encounter with layers and layers of complexity. Once we master one level, we open a whole new level. To tackle it one must employ multiple techniques. But they always involve trade-offs. How to balance programming using standard and maybe cumbersome idioms vs more elegant but more obscure idioms? What if the programming style is too personal and strange to others? Shall we settle for the lowest common denominator ? How do we balance the conflict between something harder to understand at first but easier to extend and maintain against something more familiar but with exponential complexity growth after each change? How do we maintain the "conceptual integrity" (F. Brooks) through the life of the system? As the project complexity grows, the need for sophisticated techniques increases. (I'm coming to the conclusion that if a developer can't comprehend some level of complexity, shouldn't be allowed to participate in the project without close mentoring). Refactoring is necessary because entropy. Every code base starts to degrade and loose integrity as evolves. I wonder if there's a code entropy metric... At what point a refactoring is good enough? When do you stop? At least your architecture should be stable, or you didn't validate it. I guess complexity is in the eye of the beholder. I found that a system composed of smaller simple pieces with complex interactions is easier to evolve than bigger pieces with simple interactions because each piece is internally complex and the limited interactions means its harder to combinate them in new ways. Of course, gratuitous complexity should be avoided at all costs. Sometimes I look for a "zen" approach to coding. At the end, I always take a pragmatic approach and find a trade-off that balances the forces. Isn't coding about that? Each line you write is a choice you need to make... At some point we need to use "introspection" and "metaprogramming" but not the programming techniques: introspection on how we approach problem solving and programming and metaprogramming on what we can do to program better.

Playing with Scala 4: Abstract types and Self-types

noreply@blogger.com (Anonymous) — Mon, 04 Feb 2008 01:45:00 +0000

Thanks to the scala mailing list, and to Eric, I have a satisfying enough model of a graph to be used by the Dijkstra's algorithm.
(well, there already was a generic graph and directed graph written in Scala... talking about reinventing the wheel!. The solution in Eric's comment works great too... is almost the same, but he was faster than me on coming up with it :D )
http://www.scala-lang.org/intro/abstracttypes.html
http://www.scala-lang.org/intro/selfrefs.html
I just used the same code, and changed the nodes and edges to use sets instead of lists (really, we don't care about the order)
The Scala example of Graph uses abstract types: it declares type Node and type Edge as type "parameters" to be defined by concrete implementation. Even more, by declaring type Node <: NodeIntf, we're restricting Node to be subtypes of NodeIntf. The declaration "self: Node =>" tells "I'll use self as Node type"
Then I declared the trait Weighted and extended the class DirectedGraph adding my extensions to NodeImpl and EdgeImpl to use weighted trait and add the node label and the previous property. I had to add a collection of the adjacent arcs, because they weren't in the original Graph and is easier for the algorithm. I overrode the connectWith method to keep track of the adjacent arcs as they're added, also I defined our --> operator to call the connectWith method.

class DfsNode extends NodeImpl with Weighted {

var previous: DfsNode = _
var label:String = _
var nodeEdges: Set[Edge] = Set()

override def connectWith(node: Node): Edge = {
val newEdge=super.connectWith(node)
nodeEdges = nodeEdges + newEdge
newEdge
}

def -->(n2:Node):DfsEdge =connectWith(n2)

override def toString()= label+ " w:"+weight

}

Edges are simpler, just add the weight and override toString:
class DfsEdge(origin:Node, dest:Node) extends EdgeImpl(origin, dest) with Weighted {
override def toString()= from.label+"-->"+to.label+" w:"+weight
}

All are enclosed in the DfsGraph class extending the DirectedGraph class, now I can assign the concrete types for Node and Edge:
type Node= DfsNode
type Edge= DfsEdge

The DirectedGraph class has a addNode method. To keep the DSL-ish quality of the construction of the graph, I added the method addNewNode to take the node label as parameter
def addNewNode(l:String):Node={
val newNode=super.addNode
newNode.label=l
newNode
}

So we can write: graph addNewNode "nodeLabel".

The example looks like this:

object Example extends Application {

val graph = new DfsGraph

val n1=graph addNewNode "start"
val n2=graph addNewNode "n2"
val n3=graph addNewNode "n3"
val n4=graph addNewNode "n4"
val n5=graph addNewNode "n5"
val n6=graph addNewNode "end"

n1-->n2 weight=2
n1-->n3 weight=1
n2-->n4 weight=1
n3-->n4 weight=3
n2-->n5 weight=1
n4-->n6 weight=1
n5-->n6 weight=3

graph.shortestPath(n1,n6)
println("Path")
graph.pathToStart(n6).reverse.map(println(_))

}

Pretty easy to read, don't you think?
In the next post, I'll show you how we can use this algorithm to solve the "Abbott's revenge" type of maze. Ideally, I want to create an interpreter for the input, exploring Scala's features for creating language interpreters.
Here is the complete code:

package dfs2;

abstract class Graph {
type Edge
type Node <: NodeIntf
abstract class NodeIntf {
def connectWith(node: Node): Edge
}
def nodes: Set[Node]
def edges: Set[Edge]
def addNode: Node
}

abstract class DirectedGraph extends Graph {
type Edge <: EdgeImpl
class EdgeImpl(origin: Node, dest: Node) {
def from = origin
def to = dest
}

class NodeImpl extends NodeIntf {
self: Node =>
def connectWith(node: Node): Edge = {
val edge = newEdge(this, node)
edges = edges + edge
edge
}
}

protected def newNode: Node
protected def newEdge(from: Node, to: Node): Edge

var nodes: Set[Node] =Set()
var edges: Set[Edge] =Set()
def addNode: Node = {
val node = newNode
nodes = nodes + node
node
}
}

trait Weighted {
var weight= Float.PositiveInfinity
}
class DfsGraph extends DirectedGraph {
class DfsNode extends NodeImpl with Weighted {
var previous: DfsNode = _
var label:String = _
var nodeEdges: Set[Edge] = Set()

override def connectWith(node: Node): Edge = {
val newEdge=super.connectWith(node)
nodeEdges = nodeEdges + newEdge
newEdge
}

def -->(n2:Node):DfsEdge =connectWith(n2)

override def toString()= label+ " w:"+weight
}

class DfsEdge(origin:Node, dest:Node) extends EdgeImpl(origin, dest) with Weighted {
override def toString()= from.label+"-->"+to.label+" w:"+weight
}

def addNewNode(l:String):Node={
val newNode=super.addNode
newNode.label=l
newNode
}

type Node= DfsNode
type Edge= DfsEdge

protected def newEdge(from: Node, to: Node): Edge = new DfsEdge(from,to)
protected def newNode: Node = new DfsNode

def shortestPath(start: DfsNode, end: DfsNode) = {
var unvisited=nodes
start.weight=0
while (!unvisited.isEmpty) {
val vertx=min(unvisited)
vertx.nodeEdges.map(improveDistance(_))
unvisited=unvisited-vertx
}
}

def improveDistance(a:Edge) ={
if (a.from.weight+a.weight< a.to.weight) {
a.to.weight=a.from.weight+a.weight
a.to.previous=a.from
}
}

def min(nodes: Set[DfsNode]): DfsNode = {
nodes.reduceLeft((a:DfsNode,b:DfsNode)=>if (a.weight<b.weight) a else b )
}

def pathToStart(end:DfsNode):List[DfsNode] = {
if (end == null)
Nil
else
end :: pathToStart(end.previous)
}
}

Playing with Scala 3: OO, Traits, and Views

noreply@blogger.com (Anonymous) — Wed, 23 Jan 2008 05:25:00 +0000

Look at graph classes my previous post:

class Node (val label:String) {
var transitions: List[Arc] = Nil
var previous: Node = _
var weight= Float.PositiveInfinity
var visited = false
...

and

class Arc(var start: Node, var end: Node) {
var weight: Float = _
...
Don't you feel that something doesn't really fit? What are previous, visited, and weight are doing in Node? And weight in Arc?

Those properties doesn't really belong to a generic Node or Arc, they're specific for our algorithm. So, why having them there? Let's put those attributes on special cases of Node and Arc: DfsNode and DfsArc. But wait! Putting weight in both doesn't seem right either... we're defining the same thing twice! Weight is some kind of "cross-cutting" attribute.

Traits

Luckily modern OO languages had a very elegant way of solving this kind of problems by means of traits (usually are described as "interfaces with implementation" but a very powerful concept), so let's define our weight as a trait:

trait Weighted {
var weight= Float.PositiveInfinity
}

So we can clean our Node and Arc classes:

class Node(val label:String) {
var transitions: List[Arc] = Nil

override def toString()= {
label
}

def --> (end: Node):Arc={
transitions = new Arc(this,end) :: transitions
transitions.head
}
}

class Arc(var start: Node, var end: Node) {

override def toString()= {
start.label+"-->"+end.label
}
}

Now they look useful for any graph application, and we can define our particular versions for the Dfs algorithm:

class DfsNode (label:String) extends Node(label) with Weighted {
var previous: DfsNode = _
var visited = false

override def toString()= {
super.toString+" w:"+weight+" p:"+previous
}
}

class Arc(var start: Node, var end: Node) {
override def toString()= {
start.label+"-->"+end.label
}
}

And I just need to change the signatures of the functions of the algorithm:

object Dijkstra {

def shortestPath(graph:Set[DfsNode], start: DfsNode, end: DfsNode) = {
var unvisited=graph
start.weight=0
while (!unvisited.isEmpty) {
val vertx=min(unvisited)
vertx.transitions.map(improveDistance(_))
unvisited=unvisited-vertx
}
}

def improveDistance(a:DfsArc) ={
if (a.start.weight+a.weight< a.end.weight) {
a.end.weight=a.start.weight+a.weight
a.end.previous=a.start
}
}

def min(nodes: Set[DfsNode]): DfsNode = {
nodes.reduceLeft((a:DfsNode,b:DfsNode)=>if (a.weight<b.weight) a else b )
}

def pathTo(end:DfsNode):List[DfsNode] = {
if (end == null)
Nil
else
end :: pathTo(end.previous)
}
}

What? It doesn't compile! node.transitions returns a list of Nodes and not DfsNodes! Argh! We've been bitten by the static typing! ("Ha-ha" will shout the Dynamic typing Nelson). I could use a .asInstanceOf[type] everywhere (like a Java cast) but it looks like a kludge and you have to put everywhere! There must be a better solution, after all, Scala is supposed to look elegant, right?

Views (implicit conversions)

Scala has a very interesting way of dealing with that kind of problem: by creating views using implicit conversions, we can convert from one type to other, the compiler will insert the appropriate call when needed. So I defined a conversion from Arc to DfsArc and Node to DfsNode:

object Implicits {
implicit def node2DfsNode(node:Node):DfsNode={
if (node.isInstanceOf[DfsNode])
node.asInstanceOf[DfsNode]
else {
var dfsNode=new DfsNode(node.label)
dfsNode.transitions=node.transitions
dfsNode
}
}

implicit def arc2DfsArc(arc:Arc):DfsArc={
if (arc.isInstanceOf[DfsArc])
arc.asInstanceOf[DfsArc]
else {
new DfsArc(arc.start,arc.end)
}
}
}

And now, everything will happly compile. The only caveat is as I defined the method --> returning an Arc and arc2DfsArc creating a new instance if I pass an Arc, the use of n1-->n2 weight=2 sets the weight in a new object and not in the object in the transitions collection. I'm sure there's a better solution, but meanwhile if we overrride the --> method in DfsNode will work:
def --> (end: DfsNode):DfsArc={
transitions = new DfsArc(this,end) :: transitions
transitions.head.asInstanceOf[DfsArc]
}

(Let me know if you want the full code posted)