Functional Programming Principles in Scala #
Week 1: Functions and Evaluation #
Evaluation #
Evaluation of a nonprimitive expression:
 Take the leftmost operator
 Evaluate its operands (left before right)
 Apply the operator to the operands
A name is evaluated by replacing it with the right hand side of its definition The evaluation process stops once it results in a value
Evaluation of Function Applications #
Application of parametrized functions are evaluated in a similar way as operators:
 Evaluate all function arguments from left to right
 Replace the function application by the functions’s righthand side, and, at the same time
 Replace the formal parameters of the function by the actual arguments.
Substitution model #
 Principal idea: Evaluation should reduce an expression to a value
 Applicable to all expressions, as long as they have no side effects
 Formalized in the λcalculus
Different evaluation strategies:
 callbyvalue: Reduces function arguments to values before rewriting the function application. Advantage: Evaluates every function argument only once.
 callbyname: Apply the function to unreduced arguments, Advantage: Function argument is not evaluated if the corresponding parameter is unused in the evaluation of the function body
Both strategies reduce to the same final values as long as
 the reduced expression consists of pure functions, and
 both evaluations terminate
Example callbyvalue: sumOfSquares(3, 2+2) sumOfSquares(3, 4) square(3) + square(4) 3 * 3 + square(4) 9 + square(4) 9 + 4 * 4 25
Example callbyname: sumOfSquares(3, 2+2) square(3) + square(2+2) 3 * 3 + square(2+2) 9 + square(2+2) * (2+2) 9 + 4 * (2+2) 9 + 4 * 4 25
Termination:
 If callbyvalue evaluation of an expression e terminates, then callbyname evaluation of e terminates, too.
 The other direction is not true
Example: def first(x: Int, y: Int) = x first(1, loop)
Value vs. Function Definitions #
 The def form is “byname”, its right hand side is evaluated on each use
 The val form is “byvalue”, its right hand side is evaluated at the point of the definition itself. After the evaluation, the name refers to the value, not the definition.
Example: def loop: Boolean = loop def x = loop // Is OK val x = loop // Will lead to an infinite loop
Blocks #
 A block is delimited by braces
 It contains a sequence of definitions or expressions
 The last last element of a block is an expression that defines its value
 Blocks are themselves expressions  a block may appear everywhere an expression can
Week 2: Higher Order Functions #
Anonymous Functions are Syntactic Sugar #
An anonymous function (x~1~ : T~1~, …, x~n~ : Tn) => E can always be expressed using def as follows: def f(x~1~ : T~1~, …, x~n~ : T~n~) = E; f
Expansion of Multiple Parameter Lists #
In general, a definition of a function with multiple parameter lists def f(args~1~)…(args~n~) = E where n > 1, is equivalent to def f(args~1~)…(args~n1~) = {def g(args~n~) = E; g} where g is a fresh identifier. Or for short def f(args~1~)…(args~n1~) = (args~n~ => E)
Preconditions #
require(<condition>, <error message>)
assert(<condition>, <error message>)
require
throws an IllegalArgumentException
if false, assert
an AssertionError
require
is used to enforce a precondition on the caller of a functionassert
is used as to check the code of the function itself
Constructors #
 A class implicitly introduces a constructor: The primary constructor of the class. It
 takes the parameters of the class
 and executes all statements in the class body
Syntactical Rules for Identifiers #
 Alphanumeric: starting with a letter, followed by a sequence of letters of 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
Prefix (Unary) Operator Notation #
Only four identifiers can be used as prefix: ~
, !
, 
and +
. In order to define them, a special notation has to be used: unary_~
, unary_!
, unary_
and unary_+
.
Precedence Rules #
Increasing order of priority:
 (all letters)
 
 ^
 &
 < >
 = !
 :



 / %
 (all other special characters)
Week 3: Data and Abstraction #
Dynamic Binding #
Objectoriented languages (including Scala) 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.
Automatic Imports #
Some entities are automatically imported in any Scala program:
 All members of package
scala
 All members of package
java.lang
 All members of the singleton object
scala.Predef
The Nothing Type #
Nothing
is a subtype of every other type. There is no value of type Nothing
 Signals abnormal termination or
 element type of empty collections
The Null Type #
 Every reference class type also has
null
as a value  The type of
null
isNull
Null
is a subtype of every class that inherits fromObject
; it is incompatible with subtype ofAnyVal
.
Example: val y: String = null // y: String val z: Int = null // error: type mismatch
Types and Evaluation #
 Type parameters do not affect evaluation in Scala
 All type parameters and type arguments are removed before evaluating the program (type erasure)
Polymorphism #
In programming it means that
 the function can be applied to arguments of many types, or
 the type can have instances of many types.
Two principal forms:
 Subtyping: Instances of a subclass can be passed to a base class
 Generics (parametric polymorphism): Instances of a function or class are created by type parametrization.
Week 4: Types and Pattern Matching #
Expansion of Function Values #
An anonymous function such as
(x: Int) => x * x
is expanded to:
{ class AnonFun extends Function1[Int, Int] {
def apply(x: Int) = x * x
}
new AnonFun
}
or, shorter, using anonymous class syntax:
new Function1[Int, Int] {
def apply(x: Int) = x * x
}
Expansion of Function Calls #
A function call, such as f(a, b)
, where f
is a value of some class type, is expanded to
f.apply(a, b)
So the OOtranslation of
val f = (x: Int) => x * x
f(7)
would be val f = new Function1[Int, Int] { def apply(x: Int) = x * x } f.apply(7)
Functions and Methods #
A method such as def f(x: Int): Boolean = ...
is not itself a function value, but if f
is used in a place where a Function type is expected, it is converted automatically to the faunction value (x: Int) => f(x)
or its expanded form respectively (see above).
Mixed Bounds #
It is also possible to mix a lower bound with an upper bound.
For instance,
[S >: NonEmpty <: InstSet]
would restrict S to any type on the interval betweeen NonEmpty
and IntSet
.
The Liskov Substitution Principle #
The following principle, stated by Barbara Liskov, tells us when a type can be a subtype of another. If A <: B, then everything one can do with a value of type B one should also be able to do with a value of type A. Or the actual definition: Let q(x) be a property provable about objects x of type B. Then q(y) should be provable for objects of type A where A <: B.
Variance #
General rule:
 A mutable type should be nonvariant.
 An immutable type can be covariant, if some conditions on methods are met.
Say C[T]
is a parametrized type and A
, B
are type such that A <: B
.
In general, there are three possible relationships between C[A]
and C[B]
:
C[A] <: C[B]
C is covariantC[A] >: C[B]
C is contravariant neither
C[A]
norC[B]
is a subtype of the other C is nonvariant
Typing Rules for Functions #
Generally, we have the following rule for subtyping between function types:
If A2 <: A1
and B1 <: B2
, then
A1 => B1 <: A2 => B2
So functions are contravariant in their argument type(s) and covariant in their result type.
This leads to the following definition for the Function1
trait:
package scala
trait Function1[T, +U] {
def apply(x: T): U
}
Variance Checks #
The Scala compile will check that there are no problematic combinations when compiling a class with variance annotations. Roughly,
 covariant type parameters can only appear in method results.
 contravariant type parameters can only appear in method parameters.
 invariant type parameters can appear anywhere.
(The precise rules are a bit more involved)
Prepend Violates LSP #
trait List[+T] {
def prepend(elem: T): List[T] = new Cons(elem, this)
}
does not type check. Why?
prepend
violates the Liskov Substitution Principle. Here’s something one an do with a list xs
of type List[IntSet]
:
xs.prepend(Empty)
But the same operation on a list ys
of type List[NonEmpty]
would lead to a type error:
ys.prepend(Emtpy) // type mismatch; required: NonEmpty; found: Empty
So, List[NonEmpty]
cannot be a subtype of List[IntSet]
.
How can we make the method variancecorrect?
We can use a lower bound:
trait List[+T] {
def prepend[U >: T] (elem: U): List[U] = new Cons(elem, this)
}
This passes variance checks, because:
 covariant type parameters may appear in lower bounds of method type parameters
 contravariant type parameters may appear in upper bounds of method