Outline of Class 20: Introduction to Functional Programming
Held: Monday, March 9, 1998
- The language concepts we've looked at so far primarly relate to
imperative languages, which emphasize basic operations and control.
- As we know, there are a number of other important paradigms for programming.
One of the most important is the functional paradigm,
in which programs are collections of function definitions and function
- As always, we should try to define our basis of study.
- What is a function?
- A rule that associates members of one set (the domain)
with members of another set (the range).
- The domain and range may be the same.
- Each member of the domain is associated with at most one
member of the range.
- A (potentially infinite) set of domain/range pairs.
- How can/should/do we define functions?
- By listing all the pairs.
- By providing some sort of general form for pairs
(e.g., regular expressions?)
- In terms of already-defined functions.
- By writing "computer programs" that generate results.
- How do functions on the computer differ from "mathematical"
- In math, we assume that when we apply the same function to the same
value, we get the same result. We don't always make this assumption
in computer languages. For example,
be expected to return a different byte each time.
- In math, we often assume that domains and ranges are infinite.
- When people use the term "functional language", they often mean more
than just the ability to define and apply functions. Definitions of
"functional" often include
- Functions as basic values. That is, you can write functions that
take other functions as arguments or return functions.
- "Atomic symbols" as basic values (so that you can work with symbols
in addition to strings, integers, and such).
- Dynamic lists as built-in data structures.
- Different treatment of memory and variables?
- What are some of the key functional languages? Here are some we'll
study or that the book describes:
- Scheme is a dialect of LISP.
LISP (including its dialects and variants) is perhaps the most widely used
functional language for a number of reasons.
- It's the oldest functional language.
- It includes "nonfunctional" components which support traditional
- FP was defined by John Backus to illustrate some of
the possibilities of programming with functions and no notion of
an underlying architecture. FP provides no assignment or direct access
- ML is a popular functional lanuage originally
developed as part of a program verification system. It is currently
known for its use of modern lanugae concepts (an excellent type system,
exceptions, polymorphism, etc.)
- Haskell is one of the newest "big" functional languages.
Haskell is notable for making no comprimises on functional purity --
there are no side-effecting operations in Haskell. Haskell also uses
an intersting evaluation strategy called lazy evaluation.