Functional Programming Principles in Scala

Functional Programming Principles in Scala #

Week 1: Functions and Evaluation #

Evaluation #

Evaluation of a non-primitive expression:

  1. Take the leftmost operator
  2. Evaluate its operands (left before right)
  3. 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:

  1. Evaluate all function arguments from left to right
  2. Replace the function application by the functions’s right-hand side, and, at the same time
  3. 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:

  • call-by-value: Reduces function arguments to values before rewriting the function application. Advantage: Evaluates every function argument only once.
  • call-by-name: 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 call-by-value: sumOfSquares(3, 2+2) sumOfSquares(3, 4) square(3) + square(4) 3 * 3 + square(4) 9 + square(4) 9 + 4 * 4 25

Example call-by-name: 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 call-by-value evaluation of an expression e terminates, then call-by-name 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 “by-name”, its right hand side is evaluated on each use
  • The val form is “by-value”, 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~n-1~) = {def g(args~n~) = E; g} where g is a fresh identifier. Or for short def f(args~1~)…(args~n-1~) = (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 function
  • assert 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 #

Object-oriented 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 is Null
  • Null is a subtype of every class that inherits from Object; it is incompatible with subtype of AnyVal.

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 OO-translation 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 covariant
  • C[A] >: C[B] C is contravariant
  • neither C[A] nor C[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 variance-correct? 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
Calendar 08.07.2022
Edit Edit this page