Computer Programming Languages -- Functional Programming

By 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)
• 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 arg1 arg2 ... argn )
• Function definition --
( function_name ( LAMBDA ( arg1 arg2 ... argn ) 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) )
• 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