CMSC 23300: Functional Programming
David MacQueen, Sneha Popley (TA)
Spring, 2012
Ryerson 276, 11:30am, MWF
http://www.classes.cs.uchicago.edu/current/22300-1/

================================================================================

Why study functional programming?
---------------------------------

External signs of importance of functional "paradigm"

first-class functions
  - added to C++ (C++11), Objective C, Visual Basic, ...
    (approximated by anonymous inner classes in Java?)
  - found in scripting languages: Perl, Python, Ruby?(closures)

MapReduce at Google, Twitter, etc.

use of ML and Haskell in financial industry

applications in graphics programming

OO vs FP
  (OCaml, Moby, Scala)

Real reason: power with simplicity (doing things the easy way)

----------------------------------------------------------------------

Really simple computing
-----------------------

  * elementary mathematics, e.g. arithmetic on whole numbers (natural
    numbers), rationals or reals (floating point):
    - number constants:  3, 17, 587
    - basic, or "pimitive" operations:  + , *, -, /  (div, rem)
    - tests, relations:  3 = 5;  2 > 0, ...
       (which can be true or false)

  * what sort of things do we want to compute?
     - given x, is x an even number
     - given x, what is its factorial
     - given x and y, what is their greatest common divisor
     - given x and y, what is the area of a rectangle of dimensions
        x by y inches
     - given x degrees Farenheit, what is the corresponding temperature
        in Celcius?

  * how do we put these ingredients together in order to do simple
    computations?
    - need to be able to define functions
    - need to be able to branch on conditions (if, case analysis)
      (compute something conditionally)
    - need to be able to iterate (loops, recursion)
  
  * functions: abstract over a parameter

    5 * (f - 32) / 9
      e.g. f = 32:  5 * (32 - 32) / 9 ==> 0
      e.g. f = 68:  5 * (68 - 32) / 9 ==> 20

    FtoC f = 5 * (f - 32) / 9   -- a function
      FtoC 32 = 5 * (32 - 32) / 9 ==> 0
      FtoC 68 = 5 * (68 - 32) / 9 ==> 20

  Can't do much interesting computing without conditionals and
  iteration (which usually go together)

    even n = if n = 0 then true else odd(n - 1)   (n >= 0)
    odd n = if n = 1 then true else even(n - 1)   (n >= 0)

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

    gcd (x, y) = if x = y then x
                 else if x < y then gcd(x, y-x)
                 else if y < x then gcd(x-y, y)

    Mutually recursive functions:

    even n = if n = 0 then true else odd(n - 1)    (n >= 0)
    odd n = if n = 0 then false else even(n - 1)   (n >= 0)


  Here are some other variations on fact:

    fact x = 1   if x = 0
           = x * fact(x - 1)  otherwise

    fact 0 = 1
    fact x = x * fact(x - 1)

    fact x = prod [1 .. x]
       where prod = foldl (*) 1

  fact is "primitive recursive". But this is not enough:

    Ackermann Function
    A(m,n) = n + 1 if m = 0
           = A(m-1,1) if m > 0 and n = 0
           = A(m-1,A(m,n-1)) if m > 0 and n > 0    


  This requires Goedel's General Recursive Functions (1934),
  which turned out to be equivalent to Church's Lambda Calculus (1932).
  which turned out to be equivalent to Turing Machines (1936).

  * fancy features:

    - higher-order functions (functions as arguments/results, etc)
    - data structures: products, sums, sequences, lists, trees, ...
    - types and type checking
    - polymorphism (types as parameters)
        type inference (Hinley-Milner)
        type classes (Haskell)
    - abstract types, interpreted types
    - lazy evaluation, infinite data structures
    - mutable state (ML), or monads (Haskell)
    - modules (SML)
    - processes
   (- continuations)


Functional Languages
  * LISP family: Scheme, Common LISP
  * ML family: ISWIM, LCF/ML, Standard ML, Caml, F#
  * Haskell and its precursors (SASL, KRC, Miranda)
  * Esoteric: Agda, Cayenne (Augustssen) ...
  * FP/OO combos: OCaml, Scala

  See History graph in FP_History.pdf.