Comp 302, Programming Languages and Paradigms

These notes are based on lectures given by Professor Brigitte Pientka for COMP 302, Programming Languages and Paradigms at McGill University during the Fall 2024 semester.

Variables, Bindings, Types and Recursive Functions

• OCaml is a statically typed functional programming language.

Definition (Static Typing)

Static typing is a type system where once variables are assigned a data type (either through explicit type declarations or implicit type inference), the data type of the variable remains unchanged during program execution.

• Static typing allows for robust type checking at compile time and throws precise type errors.
• In OCaml, types are checked at compile time.
  • Since OCaml does not do type checking at runtime, the languages cannot support overloading functions/operators.

Definition (Functional Programming)

Functional programming is a programming paradigm when programs are built by applying and composing functions.

• A function is considered pure if the functions do not have side effects.
  • Haskell is an example of a pure language.
  • OCaml isn’t pure since it supports exception handling and stateful computation which are side effects.

Types, Expressions, and Operators

• OCaml has most of the basic types (e.g., int, float, string, bool, char, etc.)
• Arithmetic operators are not overloaded so there are different infix operators for int and float.
  • int uses the standard arithmetic operators: +, -, *, /
  • float uses the same operators followed by a dot: +., -., *., /.
  • e.g., 32 + 42
  • e.g., 3.2 +. 4.2
• The boolean operators || and && are also infix operators between two booleans.
• if-expressions in OCaml behave much like ternaries in other languages: if <boolean> then <value if true> else <value if false>.
  • Both values if true and if false must be of the same type since the type checker does not verify the boolean expression but still it must assign a type to the if-expression result.

Variables, Bindings, and Functions

• A let-expression is used to declare a top-level (global) variable: `let = .
• OCaml is a call-by-value language so variables are bound to values and not expressions.
• Variable binding is NOT assignment because it does not allocate memory in the stack but only creates a relationship between name and value.
• Variables can not be reassigned, they can only be overshadowed.
  • Bindings between a variable and its value is placed on the binding stack.
  • The current value of a variable is retrieved by peeking the top of the binding stack.
  • The garbage collector may remove earlier bindings when it is no longer needed.

Scoped Variables (Local bindings)

• We can use the following syntax to create a scoped variable: “let = <expression 1> in <expression 2>`.
  • The variable <name> is bound to the value of <expression 1> and it can be used in `<expression 2>.
  • The scope of <name> ends after <expression 2>.
  • Once <expression 2> is done being evaluated, the binding becomes out of scope and is popped from the binding stack.

Functions

• As a functional programming language, functions are first-class citizens.
• Just like values, they can be bound to a variable.
• Functions have a type expressed as <input type> -> <output type>.
  • OCaml has two ways of writing functions and their differences are discussed later.

let square: int -> int = function s -> s * s
let square: int -> int = fun s -> s * s

• As syntactic sugar, functions can be declared like this:

let square (s: int) = s * s

• Functions can be called by writing their name followed by their arguments like this: <function name> <arg1> <arg2> ....
• It is important to note that functions can only see values of the bindings when they were declared and the any overshadowing bindings. Consider the following example:

let two = 2
let double (n: int) = two * n
let two = 4
double 3 (* still returns 6 *)

Recursive Functions

• Functions can be recursive using the let rec keyword.
• Consider the factorial function:

• It can be expressed in OCaml as follows:

exception Domain
 
let rec fact n =
  if n < 0
  then raise Domain
  else if n = 0
  then 1
  else n * fact (n - 1)
;;

• In this current version, we check the n < 0 every recursive call which is an invariant that we don’t need to repeatedly check. We can use a local function to improve this program.

exception Domain
 
let fact n =
  if n < 0
  then raise Domain
  else (
    let rec f n = if n = 0 then 1 else n * f (n - 1) in
    f n)
;;

Tail Recursion

• Recursion is normally very memory intensive since each recursive call requires a new stack frame.

Definition (Tail Recursive)

A recursive function is considered tail recursive if the recursive call is the last step of the function and no further computation needs to be done with the result of the recursive call except return the value of the recursive call.

• If a language supports tail recursion optimization, it is able to run a recursive function without creating a new stack frame for each recursive call thus improving the space complexity.
  • This optimization works because the function the recursive call is the last thing that is done in a function and it doesn’t need to store the state for computation after the recursive call returns.
• It can be proven that every function in a functional programming language can be written as a tail-recursive function.
• The following code shows the fact function but written with tail recursion.

exception Domain
 
let fact n =
  if n < 0
  then raise Domain
  else (
    let rec f n acc =
      if n = 0 then acc else f (n - 1) (n * acc)
    in
    f n 1)
;;