Introduction and Overview

Computing and Programming

Computing

the study of algorithmic processes that describe and transform information.
"What can be (efficiently) computed?" - 1989 ACM report on Computing as a Discipline

Basic components of computing

a program that describes the intended transformation of information
a machine that executes the program

Nota Bene: There can be many machines and many ways of writing the same program.

Hilbert's decision problem (1928)

Can we devise a process to determine in a finite number of operations, whether a first order logic statement is valid?

Turing machine

Alan Turing answers Hilbert's question in 1936 inventing the Turning machine.
It is the theoretical foundation of modern computers and imperative programming
Tape: Addressable read-write memory with stored program automaton (microprocessor)

Turing machines and imperative programming

In an imperative program, we read, write, perform operations, and take decisions based on contents of memory cells that hold the contents of variables like c, res, n, in the following example:

public class Factorial{
    public static int compute(int n){
        int res = 1;
        for(int c=1; c<=n; c++)
            res *= c;

        return res;
    }
}

Church

Alonzo Church also answers Hilbert's question in 1936 with a completely different approach, inventing the lambda calculus.

(abstraction) $\lambda x.M \rightarrow$ nameless function with formal parameters $x$ and body $M$
(application) $MN \rightarrow$ call function $M$ with actual parameter $N$

Theoretical foundation of functional programming

$(\lambda x.M) N \xrightarrow{\beta} M[x:=N]$

The $\beta$ reduction rule is the one and only computational device in the system.

The $\lambda$-calculus and Functional Programming

In a functional programming language we can define (possibly recursive) functions, and compose and apply them to compute the expected results.

Example:

let rec fact =
    function n -> if n=0 then 1 else n*(fact(n-1))

In a truly functional programming language, functions are first clas citizens. They can be:

named
evaluated
passed as arguments
returned as results
used everywhere an expression can fit

Using Church's original notation one could write the same example as:

lambda n. if n=0 then 1 else n(fact(n-1))

Church-Turing Thesis

Equivalence of Turning machines and $\lambda$-calculus (Turning, 1937).
A function is computable by a Turning machine, if and only if it is computable using $\lambda$-calculus.
All general programming languages are computationally equivalent

Why Functional Programming Languages

Functional programs are easier to prove correct than imperative ones.
Harnessing the power of parallel computation. Example, map and reduce are higher order functions used in distributed computing.
A carefully chosen set of higher order functions allows to write programs that are easily parallelisable.
Power and expressivity:
- Java 1.8 introduces lambda expressions
- C++11 introduces lambda expressions

The OCaml language: a bit of history

OCaml belongs to the family of statically strongly typed functional programming languages, started by Sir Robin Milner's ML.
Core features of the ML family:
- Hindley-Milner polymorphic types
- Damas-Milner type inference
- First class functions
- Algebraic datatypes
- Pattern matching

The OCaml System: a bird's eye view

A typical interaction with the OCaml shell:



In [7]:

    
List.map(fun x -> x+1) [1; 2; 3; 4; 5; 6];;









    Out[7]:




- : int list = [2; 3; 4; 5; 6; 7]

Key features

safety from strong static typing and pattern matching.
conciseness from polymorphic typing and type inference.
expressiveness from higher order functions.

Lists data structure

OCaml builtin lists
[] is the empty list
a::l is a list having a as first element,a nd list l as rest.

Type inference

A function to sum all elements in an integer list:



In [16]:

    
let rec suml =
    function
        []        -> 0
        | a::rest -> a + (suml rest)
;;

suml [1; 2; 3; 4; 5];;









    Out[16]:




val suml : int list -> int = <fun>







    Out[16]:




- : int = 15

All types are computed, and enforced at compile time.



In [14]:

    
suml [1; 2; 3];;

suml ["1"; "2"; "3"];; (* Error *)









    Out[14]:




- : int = 6







    Out[14]:




File "[14]", line 3, characters 6-9:
Error: This expression has type string but an expression was expected of type
         int
Characters 24-27:
  suml ["1"; "2"; "3"];; (* Error *)
        ^^^

Polymorphic types, and higher order



In [28]:

    
let rec fold op e =
    function
        []        -> e
        | a::rest -> op a (fold op e rest)
;;

fold (+) 0 [1; 2; 3; 4; 5];;

fold (^) "" ["1"; "2"; "3"; "4"; "5"];;

fold (fun(x, y) a-> x+a) 0 [(2, 4); (3, 5); (6, 7)];;









    Out[28]:




val fold : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b = <fun>







    Out[28]:




- : int = 15







    Out[28]:




- : string = "12345"







    Out[28]:




- : int = 11

Pattern matching

Pattern matching ensures all cases are handled. Consider the following function to remove all consecutive duplicates from a list of elements.



In [33]:

    
let rec destutter =
    function
        | []         -> []
        | x::[]      -> x::[]
        | x::y::rest ->
            if x=y then destutter(y::rest)
            else x::destutter(y::rest)
;;

destutter [1; 1; 2; 2; 2; 3; 1; 4; 2; 2];;









    Out[33]:




val destutter : 'a list -> 'a list = <fun>







    Out[33]:




- : int list = [1; 2; 3; 1; 4; 2]