Higher Order Functions

Functional languages treat functions as first-class values, that is, like any other value. Higher order functions take other functions as parameters or return value.

Let's make three functions that sum up a range of integers, a range of their cubes, and a range of their factorials.

def sumInts(a: Int, b: Int): Int =
     if (a>b) 0 else a + sumInts(a+1, b)
def sumCubes(a: Int, b: Int): Int =
     if (a>b) 0 else cube(a) + sumCubes(a+1, b)
def sumFactorials(a: Int, b: Int): Int =
     if (a>b) 0 else fact(a) + sumFactorials(a+1, b)

You notice that these three functions are nearly identical, except for one area: what they do at each value of a. We want to factor out the common things. How can we do this? Higher order functions!

We can make three functions to do the work at each level. Say,

1. def id(x: Int):Int = x
2. def cube(x: Int):Int = x * x * x
3. def fact(x: Int):Int = if (x==0) 1 else x * fact(x-1)

We can define a single function that can do all the work:
def sum(f: Int => Int, a: Int, b: Int):Int =
     if (a>b) 0
     else f(a) + sum(f, a+1, b)

def sumInts(a: Int, b: Int) = sum(id, a, b)
def sumCubes(a: Int, b: Int) = sum(cube, a, b)
def sumFactorials(a: Int, b: Int) = sum(fact, a, b)

In sum, f is the type of function that maps Int to Int. As you can see, this makes the code a lot more compact and breaks it down into more modules. However, we had to define 3 auxilliary functions: id, cube, and fact. These can be hidden using anonymous functions.

Tail Recursion

If an argument calls itself as its last action, the function's stack frame can be reused. This is called tail recursion. These are iterative processes and executive much like a loop.

However, if we have a function such as factorial(n) that calls n*factorial(n-1) last, it does not act as a tail recursive function.

It's best to refactor a function so that it is tail recursive because the JVM will only allow about 1000 stack frames to be used.

Blocks and Lexical Scope

In the sqrt example, the user does not need to see the sqrtIter, isGoodEnough, and other auxillary functions. Thus, we can wrap them in a block under sqrt so that sqrt is the only visible function. 

A block is delimited by braces. The last element in the block is an expression that defines its value. The definitions inside a block are only visible within the block and shadow definitions of the same names outside the block.

Definitions outside the block are clearly visible to the inside of a block so there is no need to redefine parameters (such as x for sqrt). Nesting method definitions makes code much more cleaner as well. Here is my code for sqrt:

  def abs(x: Double): Double = if (x > 0) x else -x
  def sqrt(x: Double): Double = {
    def isGoodEnough(guess: Double): Boolean =
      abs(guess * guess - x) / x < 0.001
    def improveGuess(guess: Double): Double =
      (guess + x / guess) / 2
    def sqrtIter(guess: Double): Double =
      if (isGoodEnough(guess)) guess
      else sqrtIter(improveGuess(guess))
    sqrtIter(1.0)
  }

Unlike Java, Scala does not require a semicolon at the end of every line. However, you do need it if you want to put more than one statement on one line. This raises the issue of multiline statements. You could wrap them in parentheses or put the operator on the first line. For example:
a. (long-expression1
        + long-expression2)
b. long-expression1 +
        long-expression2

Conditional Expressions

To choose between two values, we can use a conditional expression if-else which looks like Java's if-else but is used for expressions rather than statements. For example,

def abs(x:Int) = if (x > 0) x else -x

Expressions like && and || use short-circuit evaluation because their right operands are not always evaluated. 

When we define a function, we are using by-name since we evaluate parameters when we use them. When we define a val (val x = square(2)), we are using by-value. 

Therefore, def x = loop will work perfectly fine, but val x = loop will not work.

def and(x: Boolean, y: => Boolean): Boolean = if (x) y else false

def or(x: Boolean, y: => Boolean): Boolean = if (x) true else y

We have to remember to include the => to make the second parameter pass by-name. This will let the function use short-circuit evaluation. 

Evaluation Strategies and Termination

Call-By-Value termination always implies Call-By-Name termination. However, the converse is not true. For example, given a function {def foo(x: Int, y: Int) = x} and we call foo(1,loop) where loop does not terminate,

1. In CBV, we need to evaluate loop which does not terminate so this does not terminate
2. In CBN, we only need the first argument which it will readily return

Scala normally uses Call-By-Value because it is usually exponentially faster to compute. However, you can make a function use CBN by adding a => such as: {def constOne(x: Int, y: => Int) = 1}

If we call const(1+2, loop) we get const(3,loop) which evaluates to 1 since the parameter loop is CBN. On the other hand, if we call const(loop, 1+2), we will get an infinite cycle!

Elements of Programming

Every programming language has three things:

1. Primitives
2. Expressions to combine primitives
3. Ways to abstract expressions, introducing a name for the expression

Scala has an interactive shell that one can use to test simple expressions called a REPL (Read, Evaluate,  Print, Loop). You evaluate an expression by taking the leftmost operator, evaluating its operands, and applying the operator on the operands.

You can define a function in Scala as follows: def square(x:Double):Double = x * x. The second Double could be omitted. 

There are two ways of evaluating a function application. The first is called Call-By-Value.

1. Evaluate function arguments from left to right
2. Replace function application by function's RHS, and
3. Replace the formal parameters in the function by the actual arguments

The Call-By-Name method of evaluating a function is similar but it doesn't evaluate the arguments until the very end. This is beneficial because it will not evaluate arguments that are not used. However, there may be repeated evaluations of the same expressions. 

These schemes of expression evaluation are called substitution models. This can be applied to all expressions that do not have side effects (i.g., x++ is a side effect). 

Why Functioning Programming

I watched a keynote talk by Martin Odersky on YouTube about why Scala. Today, the problem in computing is not in the hardware but rather the software. Since hardware developers have firmly decided that the way to go with building hardware is not to add more clock cycles but rather increase the number of cores, we as programmers must deal with more parallelism and concurrency.

Parallelism is running a problem across multiple cores, even if they're not running at the same time. However, concurrency is running multiple threads at the same time.

So why is Scala over Java in some sense? Scala is much more precise and compact. Whereas just to construct a class and its constructor with one instance variables, you need to repeat the instance variable three times, Scala only needs to do it once. Whats even more is that to make some Java program run in parallel could take days while in Scala you can just add .par and be done. Scala is actually shorthand for "scalable language."

There are also more tools to utilize in Scala to give you more control over things. This video was definitely a great motivation for me to learn Scala and functional programming from the Coursera course taught by this keynote speaker.

Resources:
Video Link