CBV vs CBN

Call by Value - the most common evaluation strategy. Things are reduced before evaluating.
Call by Name - Things are passed down until they are needed to be evaluated.

Fresh Start for Functional Programming

Starting today, I plan to really focus on functional programming in Scala and commit myself to finishing the 7 week course on Coursera.

Lists

A fundamental data structure is the immutable linked list. It is composed of two parts:

1. Nil: the empty set
2. Cons: a cell containing an element and the rest of the list

trait IntList ...
class Cons(val head: Int, val tail: IntList) extends IntList ...
class Nil extends IntList

The use of val is syntactic sugar for:

class Cons(_head: Int, _tail: IntList) extends IntList {
      val head = _head
      val tail = _tail
}

This saves the use of _head and _tail. 

Pathological Data Sets and Universal Hashing Motivation

The load of a hash table is the total number of elements in the hash table divided by total amount of space in the table. This is usually denoted as alpha. Alpha=O(1) is necessary for operations to run in constant time. With open addressing we need alpha << 1. For good performance, we need to control load.

Secondly, for good performance, we need a good hash function, i.e. spreads the data evenly across buckets. However, a hash table that spreads out every data set does not exist. That is, for every hash function, there is a pathological data set.

Pathological Data in the Real World
Reference: Crosby and Wallach, USENIX 2003.
You can paralyze several real-world systems (like network intrusion detection) by exploiting badly designed hash functions. Two characteristics of these breakable systems were:

1. Open source
2. Overly simplistic hash function designed for speed (easy to reverse engineer a pathological data set)

So what should we do to solve this problem? 

Object Oriented Programming

All OOP languages implement dynamic method dispatch. This means that the code invoked by a method call depends on the runtime type of the object that contains the method.

This dynamic dispatch is analogous to calls to higher-order-functions. Can we implement objects in terms of higher-order-functions? Can we implement higher-order-functions in terms of objects?

Traits

For a class that wants to inherit from more than one superclass, it can use inherit from traits. Traits are like abstract classes defined as:

trait name {}

Classes and objects can only inherit from one superclass, but many traits. For example,

class Square extends Shapes with Planar with Movable ...

Traits are like interfaces in Java, but are more powerful since they can contain fields and concrete methods. However, they cannot have valued parameters.

 

Functions returning Functions

In Scala, we can use multiple parameter lists. Before

def sum(f: Int => Int): (Int, Int) => Int = {
     def sumF(a: Int, b: Int): Int =
          if (a > b) 0
          else f(a) + sumF(a+1, b)
     sumF
}

Now, we can turn that into

def sum(f: Int => Int)(a: Int, b: Int): Int =
     if (a>b) 0 else f(a) + sum(f)(a+1, b) 

This way, we can still use sum without the second parameter list such as sum(cube).