09 July, 2014 by Denise << scala, functional-programming >>

Interesting Scala Compiler Features

I've learnt a number of interesting things about the Scala compiler recently, the first of which is the @annotation.tailrec annotation - if you add this to a method which you expect to be tail call optimised, and the compiler can't perform the optimisation, then it will generate an error. Usage of it looks like this:

  def factorial(n: Int): Int = {
    def go(n: Int, acc: Int): Int =
      if (n <= 0) acc
      else go(n-1, n*acc)
    go(n, 1)

The other one I came across when doing an exercise with currying was where I had written the following two functions:

  def curry1[A,B,C](f: (A, B) => C): A => (B => C) =
    (a: A) => f(a, _)

  def curry2[A,B,C](f: (A, B) => C): A => (B => C) =
    (a: A) => (b: B) => f(a, b)

I wanted to prove that the two functions were equivalent. After some research I found that I could pass a flag to the Scala compiler when compiling my class like this:

scalac -Xprint:typer Currying.scala

This command prints out the abstract syntax tree of the code after the compiler phase where types are assigned has been run. This is what was printed out:

[[syntax trees at end of                 refchecks]] // Currying.scala
package  {
  object Currying extends scala.AnyRef {
    def (): Currying.type = {
    def curry1[A, B, C](f: (A, B) => C): A => (B => C) = ((a: A) => ((x$1: B) => f.apply(a, x$1)));
    def curry2[A, B, C](f: (A, B) => C): A => (B => C) = ((a: A) => ((b: B) => f.apply(a, b)))

So yes, they are equivalent!

Then, I started wondering how many phases there were in the Scala compiler, and found that the command:

scalac -Xshow-phases

will list each phase. I am using version 2.11.1 of the compiler and my output looked like this:

    phase name  id  description
    ----------  --  -----------
        parser   1  parse source into ASTs, perform simple desugaring
         namer   2  resolve names, attach symbols to named trees
packageobjects   3  load package objects
         typer   4  the meat and potatoes: type the trees
        patmat   5  translate match expressions
superaccessors   6  add super accessors in traits and nested classes
    extmethods   7  add extension methods for inline classes
       pickler   8  serialize symbol tables
     refchecks   9  reference/override checking, translate nested objects
       uncurry  10  uncurry, translate function values to anonymous classes
     tailcalls  11  replace tail calls by jumps
    specialize  12  @specialized-driven class and method specialization
 explicitouter  13  this refs to outer pointers
       erasure  14  erase types, add interfaces for traits
   posterasure  15  clean up erased inline classes
      lazyvals  16  allocate bitmaps, translate lazy vals into lazified defs
    lambdalift  17  move nested functions to top level
  constructors  18  move field definitions into constructors
       flatten  19  eliminate inner classes
         mixin  20  mixin composition
       cleanup  21  platform-specific cleanups, generate reflective calls
    delambdafy  22  remove lambdas
         icode  23  generate portable intermediate code
           jvm  24  generate JVM bytecode
      terminal  25  the last phase during a compilation run

Who knew there were so many different phases, and how interesting!

08 July, 2014 by Denise << functional-programming >>

Iterative to Functional Recursion

So I'm working through a book called 'Functional Programming in Scala' and one of the exercises was to implement a recursive method for checking whether an array is sorted. The signature given was:

def isSorted[A](as: Array[A], gt: (A,A) => Boolean): Boolean

My first attempt looked like this:

 def isSorted[A](as: Array[A], gt: (A,A) => Boolean): Boolean = {

    def loop(index: Int): Boolean = {
      if (index >= (as.length - 1)) true
      else if (gt(as(index), as(index + 1))) loop(index + 1)
      else false

but the array indexing was bothering me and I thought there must be a 'more functional' way. So I asked for a code review and was told that using a list might help, I reimplemented it as follows:

      def isSorted2[A](as: Array[A], gt: (A,A) => Boolean): Boolean = {

    def loop(as: Array[A]): Boolean = {
      if (as.length == 1 || as.length == 0) true
      else if (gt(as.head, as.tail.head)) false
      else loop(as.tail)

I think this reads a lot cleaner, and I don't need to keep track of the index in my head anymore. These imperative ways of thinking are hard to break though!

15 June, 2014 by Denise << functional-programming >>

For loops and functional programming

I feel like this was probably obvious to everyone except me, but I just realised that the functional programmer's aversion to the for loop is because it has side effects, i.e. in the following code:

for (int i = 0; i < 10; i++) {
    //do stuff

the value of i is modified each time the code loops, which is a side effect.