Functional Programming
(TDA 452/DIT 142)

• Study Period 2
• Course homepage. Shortcut: bit.ly/tda452-home
• Lecturer: Thomas Hallgren
• These slides: bit.ly/2otsGS5

Why learn Functional Programming?

• It will make you think differently about programming.
  • Mainstream programming is all about state and how to transform state.
  • Functional programming is all about values and how to construct values using functions.
• It will make you a better programmer
  • whatever programmer language you use in the future.

Functional Programming Languages

Advantanges of high-level languages

• Programmer productivity
• Software quality
• Security

Functional Programming Language History

• 1930s: Lambda Calculus (Alonzo Church)
• 1966: ISWIM (Peter Landin: The next 700 programming languages)
• 1970s: ML, Hope, SASL, ...
• 1977: FP (John Backus: Can programming be liberated from the von-Neumann Style?)
  • Turing award lecture
• 1980s: FPCA (a conference), Standard ML, Lazy ML, Miranda, ...
• 1990: Haskell 1.0
• 1990s: HBC (The first Haskell compiler, from Chalmers), GHC, ICFP (a conference)
• 2010: Haskell 2010

Example

Scalar product

• von Neumann style, word-at-a-time programming:
  scalarProduct(a,b,n) { s=0; for(i=0;i<n;i++) s=s+a[i]*b[i]; return s; }
• Whole-value programming:

  • scalarProduct = sum . map (×) . zip
    

  • Leaves room for parallel implementations

Haskell

• The language used in this course.
• Home page: www.haskell.org.
• The most widely used pure functional language
  • Functions have no side effects
  • Good for modularity, helps testing and debugging
• Provides the most "uncompromising" approach to functional programming

Haskell key features

• Light-weight, concise syntax
• Easy-to-use lists and user-defined data types
  • with pattern matching & automatic memory management
• Powerful type system
  • Parametric polymorphism
  • Automatic type inference
• Higher order functions
• An advanced optimising compiler (GHC)
• An interpreter for interactive testing during development

What can Haskell be used for?

• It's a general purpose programming language, so you can use it for almost anything!
• Particularly good for working with large, complex data structures
  • E.g. advanced compilers (like GHC)
• Used by a growing community
• See Hackage: lots of free Haskell libraries and applications. Top list.
• 

Some Haskell software I have worked on

• These slides: formatting and syntax high-lighting.
• Fudgets: GUI library in Haskell (early 1990s)
• WebFudgets (2017)
• Alfa: GUI for the proof assisant Agda (mid 1990s)
• A web browser in Haskell (mid 1990s)
• Programatica project: Haskell compiler front-end (2001-2006)
• House: a prototype operating system in Haskell (2004-2006)
• Hardware emulation (6502, 8-bit processor, used in C-64)
• An e-commerce system in Haskell (2006-2009)

A small example

Quicksort

• Efficient divide-and-conquer sorting algorithm, invented by Tony Hoare in 1959
• O(n log n)
  • Best known before this: O(n²)

Quicksort in an imperative language

• Sorting an array (from Wikipedia)
• quicksort(A, lo, hi) is if lo < hi then p := partition(A, lo, hi) quicksort(A, lo, p – 1) quicksort(A, p + 1, hi) partition(A, lo, hi) is pivot := A[hi] i := lo - 1 for j := lo to hi - 1 do if A[j] ≤ pivot then i := i + 1 swap A[i] with A[j] swap A[i+1] with A[hi] return i + 1

Quicksort in Haskell

• Sorting the elements of a list

• quickSort []      = []
  quickSort (x1:xs) = quickSort [x | x<-xs, x<=x1]
                      ++ [x1] ++
                      quickSort [x | x<-xs, x>x1]
  

The type of Quicksort in Haskell

• quickSort :: Ord a => [a] -> [a]
  

• The compiler automatically infers this generic type
  • The argument is a list with elements of an arbitrary type
  • The result is a list with elements of the same type
  • It must be possible to compare the elements with the

    <=

    and

    >

    operators

A more general sorting function in Haskell

• sortBy :: (a -> a -> Ordering) -> [a] -> [a]
  

• A generic, higher order function
  • The first argument is a function for comparing the elements of the list
  • The second argument is the list to be sorted

A generic sorting function in C

• void qsort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *));
• void * means "a pointer to anything".
• Example of an unsafe API.
• The never-ending stream of critical security vulnerabilities in software like Firefox can be directly blamed on the use of unsafe languages like C...

Course organisation

• Lectures
• Self-study exercises & drop-in office hours
• Weekly assignments:
  • 1: a small warmup exercise to get started with Haskell
  • 2A & 2B: A Card Game
  • 3A & 3B: Sudoku solver
  • 4: you choose!
    • Standard lab: a graph drawing calculator (a web application).
• Written exam

Related courses

• TDA 342: Advanced Functional Programming
• DAT 280: Parallel Functional Programming

Questions?

The End

These slides: bit.ly/2otsGS5