Tuesday, November 1, 2011

Chewy code : scala TicTacToe part 1

Authored by Win Myo Htet


First of all, I would like to thanks Oleg for permission to write a blog about his Scala Tic Tac Toe code. I got to his code through Tony Morris' Scala exercise with types and abstraction which defines the requirement.

I have started learning Scala 10 days ago after getting some inspiration from a friend who is poking around Haskell on a side. With my background in java and after a few R&D on the web, I have chosen Scala, my language of choice for functional programming. Since, I have never been exposed to functional programming in  any form before, I might be making an ignorance assumption and I would be glad to be enlightened.

When I first saw Oleg's Tic Tac Toe code, I have barely finished reading the first 3 chapters and half of Chapter 8 of "Programming Scala" by Dean Wampler and Alex Payne. Scala run on JVM and is credited with having a similar syntax to Java. Yet, the code looks very foreign to me at first sight. I don't even know how to run the program. So before I can digest the Scala really well, I have to chew this code thoroughly. As I chew, I am able to increase the performance of the code 80%-120% (my own guesstimate.) Let's the chewing begin.

God bless StackOverFlow! SO have been such a great resource for me in this journey of understanding the code. I am a bit eager and overwhelmed, and does not know how to run the program, while running the code should have been as easy as follow :

aunndroid@ubuntu:/host/linux/learning_scala$ scalac TicTacToe.scala 
warning: there were 1 deprecation warnings; re-run with -deprecation for details
one warning found
aunndroid@ubuntu:/host/linux/learning_scala$ scala TicTacToeGame
Welcome to Tic Tac Toe!

  |   |  
--+---+--
  |   |  
--+---+--
  |   |  
X>

Scala does not require that the file name be the class name (though "Programming Scala" has already mentioned about that in the chapters I have read.) and the real execution begin in the singleton TicTacToeGame, thus, a bit of confusion ensues and I have to run to SO and still have to figure them out myself. (The deprecation is because I am compiling with Scala 2.9.) I have fixed that in my learning code. I am able to run the program, Yay!

Since, I have not read the chapter 4 of "Programming Scala", I don't know much about trait, one of the major feature of Scala. I didn't know the keyword sealed also, I just take a brief look at the object structure of the inheritance (I even didn't notice the keyword case, which go in hands with sealed, being there at that time.) For now, I am more interested in the moving part and the flow. So, I get into TicTacToeGame object scope. First method, createGame, which return a Board with the data structure being Seq[Seq[Option[Move]]] (which can be similar to Option<Move>[][] in java lingua) created using for and yield. OK, I am able to follow them.

Next come method prompt, then method draw. Because I don't know that mkString is like Java's StringUtil.Join, (mkString is used in the book in Chapter 2 and I just don't remember.) I was a bit lost on how those lines are drawn nicely but all is good when I google "scaladoc mkString" and find this. All is well.

Then came method whoseTurn, where I am stuck for a day.

def whoseTurn(game: InProgress[Board]): Move =
    game.board.flatMap(_.flatten).foldLeft((0, 0)) {
      case ((x, o), X) => (x + 1, o)
      case ((x, o), O) => (x, o + 1)
    } match {
      case (x, o) if x - o <= 0 => X
      case _ => O
    }

I have seen foldLeft in the book but not flatMap and flatten. Again, SO to my rescue! game.board of Seq[Seq[Option[Move]]], has been changed from 2 dimension collection to 1 dimension collection of Seq[Option[Move]] by flatMap. After that, flatten has unboxed Option so that the collection will become Seq[Move], on which foldLeft has iterated through for data processing. Wow, quite easy to narrate these two process now. Easier said than done, I guess.

We still have foldLeft to talk about. I have to refer back to the book cause I  have basically been skimming that chapter 8 : "Functional Programming in Scala" to the half way where it has touched the subject, folding. It covers folding but not in conjunction with matching.  foldLeft's parameter is a seed value and also is "the end result data type(and value)" (that is my wording, correct me if I am wrong.) Through foldLeft(or foldRight), the collection can be manipulated/processed to be a single variable or a totally different form of collection as a result. Here we are feeding Seq[Move] to foldLeft where it will give us a pair of integers as an "end result data type" as its parameter(seed value) (0,0) dictates.

Usually inside foldLeft scope, the data to be processed is in the form of (foldLeftSeedValue,foldLeftElement) upon which the expression is applied. So we will have ((Int,Int),Move). I have to express using the data type because the variable names: x and o along with unhelping object types:X and O can confuse the beginner (it sure does to me.) Here the developer has used pattern matching to check Move type to powerful effect. If element Move is of object type X, variable x is incremented by 1 (Java's x++ won't work) maintaining the form of  (Int,Int) thus (x+1,o). Then the seed value (Int,Int) is passed along for the next iteration. The case will be the same for object O.

Finally, we finish the folding and get to the line with keyword match where it is doing the matching again. If the end result is of (Int,Int) tuple with the if condition, then the object X of descendant of Move is returned. Otherwise, for anything else, the object O is returned. The variable x,o of (x,o) inside this match has nothing to do with the  x and o of the previous foldLeft scope. Can you imagine the kind of effect these x,o,X,O,x,o, <=,=>; and double matching and double flattening has on me ? I sure would never turn back to Scala, if Oleg, the developer, had used operator /: instead of method name foldLeft. :) (Please tweet using hashtag #dietscala to discuss about it)


Having chewed through this code and compiled some note on flatmap, flatten and foldLeft from my research, I thought I get foldLeft good. I am in for surprise by more chewy code of foldLeft coming up, along with the delight in enabling performance enhancement and some find on debugging. 


http://blog.aunndroid.com/2011/11/chewy-code-scala-tictactoe-part-2.html


Authored by Win Myo Htet

No comments:

Post a Comment