Computer Programming Languages -- Functional Programming

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)

- Mapping -- gives a value in a
- 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_{1}arg_{2}... arg_{n}) - Function definition --

( function_name ( LAMBDA ( arg_{1}arg_{2}... 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 ) ) ) ) )

- LAMBDA handled implicitly
- COND -- multiple selector
- SET! -- imperative style setting of variable value
- SET-CAR!, SET-CDR! -- imperative style changes to existing lists --
**side effects**

- Arithmetic operations
- 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

- Lisp -- first functional programming language, now has imperative features as well

Last Updated on 24 April 2000

By Herbert J. Bernstein