Notes of Scala course on Coursera -- Week 2 (3)

Here are my notes for the week 2’s lecture of Functional Programming Principles in Scala on Coursera.

1. Functions and Data

1.1 Classes

In Scala, a class ia defined like this:

class Rational(x: Int, y: Int) {
  def numer = x
  def denom = y
}

This definition introduces two entities:

A new type, named Rational .
A constructor Rational to create elements of this type.

1.2 Objects

We call the elements of a class type objects.

We create an object by prefixing an application of the constructor of the class with the operator new.

new Rational(1, 2)

1.3 Members of an Object

Objects of the class Rational have two members, numer and denom .

We select the members of an object with the infix operator ‘.’ (like in Java).

val x = new Rational(1, 2)    // x: Rational = Rational@2abe0e27, cbv
x.numer    // 1
x.denom    // 2

1.4 Rational Arithmetic

We can now define the arithmetic functions that implement the standard rules.

$\frac{n_1}{d_1}+\frac{n_2}{d_2}=\frac{n_1d_2+n_2d_1}{d_1d_2}$
$\frac{n_1}{d_1}-\frac{n_2}{d_2}=\frac{n_1d_2-n_2d_1}{d_1d_2}$
$\frac{n_1}{d_1}\cdot\frac{n_2}{d_2}=\frac{n_1{\cdot}n_2}{d_1d_2}$
$\frac{n_1}{d_1}/\frac{n_2}{d_2}=\frac{n_1d_2}{d_1n_2}$
$\frac{n_1}{d_1}=\frac{n_2}{d_2}{\iff}n_1d_2=d_1n_2$

1.5 Implementing Rational Arithmetic

def addRational(r: Rational, s: Rational): Rational =
  new Rational(
    r.numer * s.denom + s.numer * r.denom,
    r.denom * s.denom)
def makeString(r: Rational) =
  r.numer + ”/” + r.denom

makeString(addRational(new Rational(1, 2), new Rational(2, 3)))     // => 7/6

1.6 Methods

One can go further and also package functions operating on a data abstraction in the data abstraction itself.

Such functions are called methods.

class Rational(x: Int, y: Int) {
  def numer = x
  def denom = y
  def add(r: Rational) =
    new Rational(numer * r.denom + r.numer * denom,
                 denom * r.denom)
  def mul(r: Rational) = ...
  ...
  override def toString = numer + ”/” + denom
}

Remark: the modifier override declares that toString redefines a method that already exists (in the class java.lang.Object ).

Calling Methods:

val x = new Rational(1, 3)
val y = new Rational(5, 7)
val z = new Rational(3, 2)
x.add(y).mul(z)

Exercise

(1) In your worksheet, add a method neg to class Rational that is used like this:

x.neg

(2) Add a method sub to subtract two rational numbers.

(3) With the values of x , y , z as given in the previous slide, what is the result of x - y - z?

Answer

object WorkSheet {
  class Rational(x: Int, y: Int) {
    def numer = x
    def denom = y
    def add(r: Rational) =
      new Rational(numer * r.denom + r.numer * denom,
                   denom * r.denom)

    def mul(r: Rational) =
      new Rational(numer * r.numer, denom * r.denom)

    def neg: Rational = new Rational(-numer, denom)

    def sub(that: Rational) = add(that.neg)

    override def toString = numer + "/" + denom
  }
  val x = new Rational(1, 3)                      //> x  : greeter.WorkSheet.Rational = 1/3
  val y = new Rational(5, 7)                      //> y  : greeter.WorkSheet.Rational = 5/7
  val z = new Rational(3, 2)                      //> z  : greeter.WorkSheet.Rational = 3/2
  x.add(y).mul(z)                                 //> res0: greeter.WorkSheet.Rational = 66/42
  x.sub(y).sub(z)                                 //> res1: greeter.WorkSheet.Rational = -79/42
}

2. More Fun with Rationals

2.1 Data Abstraction

One would expect the rational numbers to be simplified:

reduce them to their smallest numerator and denominator by dividing both with a divisor.

We could implement this in each rational operation, but it would be easy to forget this division in an operation.

A better alternative consists of simplifying the representation in the class when the objects are constructed:

class Rational(x: Int, y: Int) {
  private def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
  private val g = gcd(x, y)
  def numer = x / g
  def denom = y / g
  ...
}

It is also possible to call gcd in the code of numer and denom :

class Rational(x: Int, y: Int) {
  private def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
  def numer = x / gcd(x, y)
  def denom = y / gcd(x, y)
}

This can be advantageous if it is expected that the functions numer and denom are called infrequently.

It is equally possible to turn numer and denom into vals, so that they are computed only once:

class Rational(x: Int, y: Int) {
  private def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
  val numer = x / gcd(x, y)
  val denom = y / gcd(x, y)
}

This can be advantageous if the functions numer and denom are called often.

2.2 The Client’s View

Clients observe exactly the same behavior in each case.

This ability to choose different implementations of the data without affecting clients is called data abstraction.

It is a cornerstone of software engineering.

2.3 Self Reference

On the inside of a class, the name this represents the object on which the current method is executed.

class Rational(x: Int, y: Int) {
  ...
  def less(that: Rational) =
    numer * that.denom < that.numer * denom
  def max(that: Rational) =
    if (this.less(that)) that else this
}

Note that a simple name x , which refers to another member of the class, is an abbreviation of this.x . Thus, an equivalent way to formulate less is as follows.

def less(that: Rational) =
  this.numer * that.denom < that.numer * this.denom

2.4 Preconditions

Let’s say our Rational class requires that the denominator is positive.

class Rational(x: Int, y: Int) {
  require(y > 0, ”denominator must be positive”)
  ...
}

require is a predefined function.

It takes a condition and an optional message string.

If the condition passed to require is false , an IllegalArgumentException is thrown with the given message string.

2.5 Assertions

Besides require , there is also assert .

assert also takes a condition and an optional message string as parameters.

val x = sqrt(y)
assert(x >= 0)

Like require , a failing assert will also throw an exception, but it’s a different one: AssertionError for assert , IllegalArgumentException for require .

This reflects a difference in intent

require is used to enforce a precondition on the caller of a function.
assert is used as to check the code of the function itself.

2.6 Constructors

In Scala, a class implicitly introduces a constructor. This one is called the primary constructor of the class.

The primary constructor

takes the parameters of the class
and executes all statements in the class body (such as the require a couple of slides back).

2.7 Auxiliary Constructors

Scala also allows the declaration of auxiliary constructors.

These are methods named this.

class Rational(x: Int, y: Int) {
  def this(x: Int) = this(x, 1)
  ...
}
new Rational(2) // => 2/1

3. Evaluation and Operators

3.1 Classes and Substitutions

We previously defined the meaning of a function application using a computation model based on substitution. Now we extend this model to classes and objects.

Question: How is an instantiation of the class new C(e_1 ,..., e_m) evaluted?

Answer: The expression arguments e_1 ,..., e_m are evaluated like the arguments of a normal function. That’s it.

The resulting expresion, say, new C(v_1 ,..., v_m), is already a value.

Now suppose that we have a class definition,

class C(x_1 ,..., x_m){ ... def f(y_1 ,..., y_n) = b ... }

where

The formal parameters of the class are x_1 ,..., x_m .
The class defines a method f with formal parameters y_1 ,..., y_n .

(The list of function parameters can be absent. For simplicity, we have omitted the parameter types.)

Question: How is the following expression evaluated?

new C(v_1 ,..., v_m).f(w_1 ,..., w_n)

Answer: The expression new C(v_1 ,..., v_m).f(w_1 ,..., w_n) is rewritten to:

[w_1/y_1 ,..., w_n/y_n] [v_1/x_1 ,..., v_m/x_m] [new C(v_1 ,..., v_m)/this] b

There are three substitutions at work here:

the substitution of the formal parameters y_1 ,..., y_n of the function f by the arguments w_1 ,..., w_n ,
the substitution of the formal parameters x_1 ,..., x_m of the class C by the class arguments v_1 ,..., v_m ,
the substitution of the self reference this by the value of the object new C(v_1 ,..., v_n).

3.2 Object Rewriting Examples

new Rational(1, 2).numer
-> [1/x, 2/y] [] [new Rational(1, 2)/this] x
= 1

new Rational(1, 2).less(new Rational(2, 3))
-> [1/x, 2/y] [new Rational(2, 3)/that] [new Rational(1, 2)/this]
    this.numer * that.denom < that.numer * this.denom
= new Rational(1, 2).numer * new Rational(2, 3).denom <
    new Rational(2, 3).numer * new Rational(1, 2).denom
->> 1 * 3 < 2 * 2
->> true

3.3 Operators

In principle, the rational numbers defined by Rational are as natural as integers.

But for the user of these abstractions, there is a noticeable difference:

We write x + y , if x and y are integers, but
We write r.add(s) if r and s are rational numbers.

In Scala, we can eliminate this difference. We procede in two steps.

Step 1: Infix Notation

Any method with a parameter can be used like an infix operator.

It is therefore possible to write

r add s    //  <=> r.add(s)    
r less s   //  <=> r.less(s)    
r max s    //  <=> r.max(s)

Step 2: Relaxed Identifiers

Operators can be used as identifiers.

Thus, an identifier can be:

Alphanumeric: starting with a letter, followed by a sequence of letters or numbers
Symbolic: starting with an operator symbol, followed by other operator symbols.
The underscore character ’_’ counts as a letter.
Alphanumeric identifiers can also end in an underscore, followed by some operator symbols.

Examples of identifiers:

x1    *    +?%$    vector_++    counter_=

3.4 Operators for Rationals

class Rational(x: Int, y: Int) {
  private def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
  private val g = gcd(x, y)
  def numer = x / g
  def denom = y / g
  def + (r: Rational) =
  new Rational(
    numer * r.denom + r.numer * denom,
    denom * r.denom)
  def - (r: Rational) = ...
  def * (r: Rational) = ...
  ...
}

Now rational numbers can be used like Int or Double :

val x = new Rational(1, 2)
val y = new Rational(1, 3)
x * x + y * y    // what is the priority? => (x * x) + (y * y)

3.5 Precedence Rules

The precedence of an operator is determined by its first character.

The following table lists the characters in increasing order of priority precedence:

(all letters)
|
^
&
< >
= !
:
+ -
* / %
(all other special characters)

Yilin's Blog