By Herbert J. Bernstein

© Copyright 2000 Herbert J. Bernstein

Functional programming is based on the concepts of mappings and functions as used in mathematics. The results of applying each function depend entirely on the values of the arguments. There are no side-effects to deal with, and it is much easier to verify the correctness of a functional program than to check the action of an imperative program. Another name for functional programming is applicative programming.

• Mathematical concepts
  • Mapping -- gives a value in a range for each value in a domain
  • Notations:
    • M:D -> R
    • y = M(x)
    • y = xM
    • (M x)
  • one-to-one -- any given value in the range appears for only one value in the domain
  • onto -- every value in the range is the result of mapping some value in the domain
  • invertible (one-to-one onto) -- there is an inverse mapping from the range to the domain such that inverse(mapping(value)) = value
  • Composition
    • f:S -> T
    • g:T -> U
    • f•g S -> U OR g•f S -> U
      (two approaches, reading one way or the other)
• Avoiding side-effects
  • In imperative languages, the same sequence of statements may operate differently on different invocations, because of changes in the contents of variables
  • Side effects -- changes in that state of varibales other than as function returns
  • Difficult to verify the operation of a program
• Functions, lambda notation
  • Function -- representation of a mapping -- returns a consistent value for any given set of values of its arguments
  • Lambda notation (Church)
    • l x • B
    • parameter x -- said to be bound in the lambda expression l x • B
    • body B -- describes the mapping done on x to obtain the result
    • variables other than x in B are said to be free
    • multiple arguments -- l x • l y •B
    • See http://www.numeric-quest.com/haskell/hcompanion/abstraction.html#Lambda-calculus
• Lisp, Scheme, ML, Haskell
  • Lisp -- first functional programming language, now has imperative features as well
    http://www.nyu.edu/pages/linguistics/nlcp/lisp.html
    • List processing language
    • Lists as parenthesized list of elements
    • Function call --
      ( function_name arg₁ arg₂ ... arg_n )
    • Function definition --
      ( function_name ( LAMBDA ( arg₁ arg₂ ... arg_n ) expression ) )
    • EVAL -- a function which evaluates functions
    • CAR and CDR decompose lists --
      CAR of (A B C ...) is A
      CDR of (A B C) is (B C ...)
    • CONS constructs lists
    • QUOTE protects from evaluation
    • Dynamic scoping
  • Scheme -- static scoped Lisp dialect
    See http://swissnet.ai.mit.edu/projects/scheme/
    • Arithmetic operations
      • + - * / SQRT
      • (+ A B C ... Z) -- A+B+C+...+Z
      • (- A B C ... Z) -- A-B-C-...-Z
      • (* A B C ... Z) -- A*B*C*...*Z
      • (/ A B C ... Z) -- A/B/C/.../Z
    • EVAL -- evaluate arguments, then the function
    • QUOTE -- quote to protect argument from evaluation
      • (QUOTE arg) or 'arg evaluates to arg
      • (CAR '(A B C)) evaluates to A
      • (CDR '(A B C)) evaluates to (B C)
      • (CONS 'A '(B C)) evaluates to (A B C)
    • LIST -- makes its arguments into a list
    • Booleans
      • #T -- any non-empty list
      • #F -- an empty list
      • EQ? NULL? LIST? -- tests for symbolic lists
      • = <> > < >= <= EVEN? ODD? ZERO? -- tests for numeric atoms
      • EQV? -- EQ? or = as appropriate
    • DEFINE -- binds value to a symbol
      • LAMBDA handled implicitly
        (DEFINE (Conv_Rad deg) ( * deg 0.0174533) )
        (Conv_Rad 180) -- 3.141594
      • Recursion
        (DEFINE (factorial n)
        (IF ( <= n 0 ) 1 (* n ( factorial ( - n 1 ) ) ) ) )
    • COND -- multiple selector
    • SET! -- imperative style setting of variable value
    • SET-CAR!, SET-CDR! -- imperative style changes to existing lists -- side effects
  • ML -- strongly typed
    Pascal-like syntax
    See http://www.cs.cmu.edu/afs/cs.cmu.edu/project/fox/mosaic/sml.html
  • Haskell -- purely functional
    See http://haskell.org/
    • Static scope
    • Strongly typed
    • Lazy evaluation
    • Infinite lists represented through list comprehensions