Om mig

Mitt foto

I'm a software developer playing around with Scala, Lift and GWT along with a few DIY side projects.

måndag 26 juli 2010

Implementing Type Safe Roman Numerals in Scala (type parameter extravaganza!)

I figured I wanted to do some more stuff with the roman numerals and try and create a type safe way to count with them (integers are so 2000 were living in the MMX now ;-)). Anyway what I wanted was something that could be used to express roman numerals in source files and that the compiler would say no if I expressed them in a flawed manner. It should be possible to write something like: MM I (1001), but it should not be possible to write: I MM (since that is not a proper roman numeral).

I started out with a lass in Scala:

Then using some traits I could add the ability to express simple combinations of roman numerals:

After importing the RomanNumeral class and the traits along with the contents of the RomanNumerals object I was able to write M CD since scala interprets that as M.CD and since M (defined in the RomanNumerals object) extends the NumeralM trait it has a method CD. It would also not be possible to write I M since I only extends the trait NumeralI which does not define any M method. This is all well and good, but I wanted some more expressive power. I wanted to be able to write something along the lines of M CM X I (i.e. 1911), but that is not possible because the way scala interprets spaces M CM X I would be turned into: M.CM(X).I . That means my RomanNumeral would need an apply method that could take another RomanNumeral and return a new one. So I defined one:

Now atleast I was able to write M CM X (since that is "M.CM(X)") however I was also able to write M CM M (i.e. M.CM(M)), but that would be an illegal RomanNumeral (since the M CM is 1900 it doesn't make sense to have an M after it; L, X, V, I would all be valid but not M nor C). In addition I was not able to write M CM X I since the returned RomanNumeral from the apply method had no NumeralN mixed in when instantiated (using with). I would be able to write M.CM.X.I since that indicates to the compiler that I am calling a method on the return value of the previous method (i.e. calling the method X on the return value of the method CM and so on), but I wanted to do this without the dots :).

So first things first; how could I know in th eapply method which trait I should mixin with the returned RomanNumeral so that it would have the appropriate methods available? Enter the type parameters. I first tried redefining the RomanNumeral class as follows:

However that does not work. Why you ask? Well, first some explanation of the type parameters introduced. The type parameters for the RomanNumeral is specified with T<:Numeral the <:Numeral part is a upper bound on the type that can be used for the class. So instantiating a RomanNumeral I would atleast have to pass in a Numeral or a subclass thereof. In the apply method I specify an upper and a lower bounds for the type parameter of the RomanNumeral passed in as an argument to the method. The lower bounds on the type parameter is T and the upper bound is Numeral so the type used as a type parameter of the RomanNumeral being passed to the method has to atleast be a Numeral and at most be a T (which in turn has to be a subtype of Numeral). A few examples in the interpreter might be helpfull here... (lets ignore the "with N" part of the code above)

Since NumeralI is a super class of NumeralV and a subclass of Numeral the "five" value can be supplied with the "three" value to its apply method. Doing the reverse causes a type missmatch since NumeralV is not a superclass of NumeralI. Method apply would look like this in the first instance (with the type parameters spelt out):

and in the latter case:

All this is a ok. So why doesn't the RomanNumeral code above compile? Well, because of type erasure for one and also because N could be a concrete class and not a trait(only traits can be mixed in to classes at instantiation time). After type erasure there is no way of knowing what N is and therefore the RomanNumeral class above would not compile. At this point I tried alot of different version of the above to find something which did work. In the end I realized that I could have an apply method that took a NumeralN instead and have one for each trait. That way I would know which type should be mixed in with the RomanNumeral.

This worked fine, but allowed any Numeral to follow any other. Using the interpreter to illustrate:

As can be seen above a NumeralI could be followed by a NumeralV which should not be allowed. By changing the NumeralI and its subtypes to take a type parameter I was able to add the type bounds back to the apply methods and enforce the correct behaviour. The traits now looks like this:

And the RomanNumeral class looks like:

With these modifications I could now specify the values in ther RomanNumerals object as follows:

By importing all the classes and traits and then importing the contents of the RomanNumerals object (import RomanNumerals._) I can now write my roman numerals in a type safe way. I.e. M C X V I (which is equivalent of writing: M.C.apply(X).V.apply(I) ) is allowed but M CM C is not allowed. Why? Well, since the return value of the CM method is a RomanNumeral with the type parameters NumeralL[Numeral] (and with NumeralL[Numeral] mixed in) the apply methods all look like:

and C has the type RomanNumeral[NumeralC[Numeral]] with NumeralC[Numeral] there is no apply method where C is a valid argument (C is a NumeralC[Numeral] which is a subtype of NumeralL[Numeral] and as such violates the lower bounds on the type parameter).

Next I created a rollover so that when a RomanNumeral is created that is larger than 3999 it rolls over to a number which can be described with roman numerals (i.e. > 0 and < 4000). Then to wrapp things up I simply added a companion object with an apply/unapply method to my RomanNumeral so it can easily be used in pattern matching. I also added some methods for basic arithmatic (+-/*), implemented the Ordered trait and extended the Number class. Finally I added an implicit conversion from Number to a RomanNumeral[Numeral] so that I could add Integers and Doubles and such to a RomanNumeral and vice versa (with a result type of a RomanNumeral[Numeral]).

The final result can be seen below (now I only need to find a problem for my solution :-) ):

Inga kommentarer:

Skicka en kommentar