Functional Programming lecture notes.

00_FunctionalProgramming.md

• Lecture

01_LISP.md

• specified in 1958

• oldest functional programming language

• favored for artificial intelligence

• Dialects

  • Common LISP
  • Scheme

• Scheme @ repl.it

• learn common-lisp in y minutes

• Language

  • Atoms
  • S-expressions

• Name binding

  • static: definition environment
    • some older dialects
  • dynamic: calling environment
    • common-lisp
  • DynamicBindingVsLexicalBinding

• Closure:

  • the amount of bindings of unbound variables of a function

01_LISP_Examples.lisp

;Atoms
t ;true
f ;false
nil ;empty list
<NUMBER>
<DESIGNATOR>

;S-expressions
(list 1 2 3 4) ;create list
(cons 1 (list 3 4 5)) ;add element to list
(car l) ;head
(cdr l) ;tail
(null l)
(eq 1 2)
(+ 1 2 3 4) ;sum of atoms

(cond ((< 2 1) 'yes)
      (#t 'no)) ;conditions, not strict, left-to-right until true

(quote test) ;do not evaluate => test
'test

(lambda (a, b, c) (+ a b c)) ;anonymous function definition
((lambda (a b c) (+ a b c)) 5 5 5) ;call
(defun add_three (a b c) (+ a b c)) ;function definition
(add_three 5 5 5) ;call

(map (lambda (n) (cons n (cons n '()))) '(1 2 3)) ;call function on each element

(let ((a 1)) (+ a a)) ;name binding

(let ((x 1))
    ((lambda (a b) (+ a x b)) 5 6) ;unbound variable x
)

02_SML.md

• Standrard ML
• popular among compiler writers and programming language researchers
• functions, calls, expressions
• no variables, no control structure
• no side effects, no program state
• expression oriented
• statically typed
• Semantic
  • call-by-vallue (strict)
  • call-by-need (lazy)
• Declaration val <pattern> = <expression>;
• Tupel (,)
• List ::
• Unbound _
• Function fn <name> <parameter_patern> = <expression>
• Polymorphic functions
• SML, Some Basic Examples

02_SML_Examples.sml

fun foo x = (x, x);

val x = sqr 3;

val (c, d) = foo 42;
val h::_ = [1, 2, 3];

val (a, b) = (sqr 2, sqr 3);
val (x, y)::z = [foo 41, (3, 4), (5, 6)];

val rec Fac = fn n => if n <= 1 then 1 else n * Fac (n-1); (* recursive finction declaration *)

fun app (nil, lr) = lr
|   app (ll, nil) = ll
|   app (h::t, r) = h :: (app (t, r)); (* merge two lists *)

val today = (25, "Mai", 2013); (* tupel *)
type vec2 = real * real; (* type definition *)
val today = {year=2013, day=25, month="Mai"}; (* record *)

fun fst (x, y) = x; (* polymorphic *)

fun (* mutually recursive function definitions *)
=   odd (n) = if n=0 then false else even (n-1)
= and
=   even (n) = if n=0 then true else odd (n-1);

03_Lists.md

Lists in SML

• homogeneous, all elements have the same type
• accumulating parameters

03_Lists_Examples.sml

nil;  (* = [] *)
1 :: 2 :: 3 :: nil; (* = [1,2,3] *)
length [1,2,3]; (* = 3 *)
hd [1,2,3]; (* = 1 *)
tl [1,2,3]; (* = [2,3] *)
null []; (* = true *)
null [1]; (* = false *)
rev [1,2,3]; (* = [3,2,1] *)
[1,2,3] @ [4,5,6]; (* = [1,2,3,4,5,6] *)

fun upto (n, m) = if n > m then [] else n :: upto(n+1, m);
upto (2, 6); (* = [2,3,4,5,6] *)

(* recursion patterns *)
fun prod nil = 1
|   prod (h::t) = h * prod t;

fun append (nil, r) = r
|   append (l, nil) = l
|   append (h::t, r) = h :: append (t, r);

fun maxl [m] = m
|   maxl (m::n::ns) = if m > n then maxl (m::ns) else maxl (n::ns);

(* accumulating parameter *)
fun alength (nil, n) = n
|   alength (_::t, n) = alength (t, n+1);

(* concatenate a list of lists *)
fun concat (nil) = nil
|   concat (h::t) = h @ concat t;

(* create list of pairs *)
fun zip (x::xs, y::ys) = [x, y] :: zip (xs, ys)
|   zip _ = nil;

fun unzip nil = (nil, nil)
|   unzip ((x, y)::pairs) = let val (xs, ys) unzip pairs in (x::xs, y::ys) end;

local fun rev_unzip (nil, xs, ys) = (xs, ys)
      |   rev_unzip ((x,y)::pairs, xs, ys) = rev_unzip (pairs, x::xs, y::ys);
in fun iunzip (l) = rev_unzip (l, nil, nil) end;

fun all_change (coins, _, 0) = [coins]
|   all_change (coins, [], _) = []
|   all_change (coins, c::coinvals, amount) =
        if amount < 0 then []
        else all_change (c::coins, c::coinvals, amount-c) @
             all_change (coins, coinvals, amount);

all_change ([], [1,2,5], 9);

(* polynomial sum *)
fun sum ([], us) = us
|   sum (ts, []) = ts
|   sum ((m,a)::ts, (n,b)::us) =
        if m > n then (m,a)::sum (ts, (n,b)::us)
        else    if m < n then (n,b)::sum ((m, a)::ts, us)
                else    if a+b=0.0 then sum (ts, us)
                        else (m, a+b)::sum (ts, us);

(* polynomial product *)
fun termprod ((m,a), []) = []
|   termprod ((m,a), (n, b)::ts) =
        (m+n, a*b)::termprod ((m,a), ts);

(* polynomial multiplication with divide and conquer *)
fun prod ([], us) = []
|   prod ([(m,a)], us) = termprod ((m,a), us)
|   prod (ts, us) =
        let val k = lenght ts div 2
        in sum (prod (List.take(ts, k), us),
                prod (List.drop(ts, k), us))
        end;

04_TypesAndModules.md

Types and Modules

• discriminated union a data structure used to hold a value that could take on several different, but fixed types

• Types

  • type different name for existing type
  • datatype new type with constructor
  • abstypenew type with methods and hidden construtor

• Modul

  • structure modul wizh own namespace
  • signature interface
  • functor generic structure (type safe)

• Exception

  • exception

04_TypesAndModules_Examples.sml

type tupel = int * int;

datatype order = LESS | EQUAL | GREATER;
datatype 'a list = nil | :: of ('a * 'a list);

abstype AbsSet = absset of int list with
    val empty = absset([])
    fun insert(x, absset(s)) = absset(x::s)
    fun member(x, absset([])) = false
        member(x, absset(h::t)) = (x = h) orelse member(x, absset(t))
end;

exception Failure;
exception Fail of string;

exception Undefined
fun max [x] = x
|   max (x::xs) = let val m = max xs in if x > m then x else m end
|   max [] = raise Undefined
 fun main xs = let
    val msg = (Int.toString (max xs)) handle Undefined => "empty list...there is no max!"
   in
     print (msg ^ "\n")
end

05_FunctionsAsData.md

Functions as Data

31_EWG1.md

• Higher order function are functions which take a functions as arguments.
• Currying is the technique of transforming a function that takes multiple arguments in such a way that it can be called as a chain of functions, each with a single argument.
• Functional languages do not have a state.
• Alter complex data structure using a recursive function.

32_EWG2.md

• "A is evaluated": the value of are is determined are used
• conditional expressions are not evaluated strictly
• Static/dynamic binding of x
  • static: x is defined in the definition environment
  • dynamic: x is defined in the calling environment
• fun ggt (a, b) = if a > b then ggt(a, b-a) else if a > b then ggt(a-b, b) else a;

33_EWG3.md

• substitution
  • call-by-value: from inside-to-outside
  • call-by-name: from outside-to-inside
  • call-by-need: from outside-to-inside, argument values are memoized and not re-evaluted on multiple uses
• see examples
• see examples
• polymorphism
  • sml: type
  • java: object

34_EWG4.md

• recursive substition auf the type definition defines the resulting type
• ('a * 'b * 'c)

fun aRev (ts, []) = ts
|   aRev (ts, h::t) = aRev (ts @ [h], t);