CHAPTER 14
FUNCTIONAL PROGRAMMING LANGUAGES
INTRO:
- The functional
programming paradigm, which is based on mathematical functions, is the
design basis for one of the most important non-imperative styles of
languages. This style of
programming is supported by functional, or applicative, programming
languages.
- Lisp began as a purely
functional language, but it soon acquired some important imperative
features that increased its execution efficiency. It is still the most important in
functional languages.
- Scheme is a small,
static-scoped dialect of Lisp
- COMMON Lisp is an
amalgam of several early 1980’s dialects of Lisp
- ML is a strongly typed
functional language with more conventional syntax than Lisp and Scheme
- Haskell is partially
based on ML but is purely a functional language.
MATHEMATICAL FUNCTIONS
- A mathematical function
is a mapping of members of one
set, called the domain set, to
another set called the range set.
- A function definition
specifies the domain and range sets, either explicitly or implicitly, along
with the mapping
- Functions are often
applied to a particular element of the domain set
- A function yields or
returns an element of the range set.
- A mathematical function
defines a value, rather than specifying a sequence of operations on values
in memeory t produce a value.
SIMPLE
FUNCTIONS
- function definitions
are often written as a function name, followed by a list of parameters in
parentheses, followed by the mapping expression
- ex, cube(x) º x * x * x where x is a real number
- here, the domain and range sets
are the real numbers
- Early theoretical work
on functions separated the task of defining a function from that of naming
the function.
- Lambda notation which
is devised by Alonzo Church provides a method for defining nameless
functions
- A lambda expression
specifies the parameter and the mapping of a function. The lambda expression is the function
itself
- Ex, l (x) x * x * x
- When a l expression is
evaluated for a given parameter, the expression is said to be applied to
that parameter.
FUNCTIONAL
FORMS
- A higher order
function, or functional form,
is one that either takes functions as parameters or yields a function as
its result, or both.
- One common kind of
functional form is function composition,
which has 2 functional parameters and yields
- a function whose value
is the first actual parameter function applied to the result of the
second.
Ex, h º
f ° g
- Construction is a functional form that takes a list
of functions as parameters
- Apply to all is a function form that takes a single
function as a parameter.
- Apply to all is denoted
by a
Ex,
h(x) º x*x
then a (h, (2, 3, 4)) yields
(4, 9, 16)
FUNDAMENTALS OF FUNCTIONAL PROGRAMMING LANGUAGES
- A purely functional
programming language does not use variables or assignment statements
- Without variables,
iterative constructs are not possible, for they are controlled by
variables
- Repetition must be done
by recursion rather than by repetition
- Programs are function
definitions and function application specifications, and executions
consists of evaluating the
function applications
- The execution of a
function always produces the same result when given the same parameters –
this is called referential
transparency.
- A functional language
provides a set of primitive functions, a set of functional forms to
construct complex functions from those primitive functions, a function
application operation, and some structure or structures for representing
data.
- Functional languages
are often implemented with interpreters but they are also compiled.
THE FIRST FUNCTIONAL
LANGUAGE: LISP
The
oldest and most widely used functional language is Lisp
DATA
TYPES AND STRUCTURES
- There are 2 types of
data objects in the original Lisp: atoms and lists.
- Atoms, which have the
form of identifiers, are the symbols of Lisp
- Numeric constants are
also considered atoms
- Lisp rarely requires
the operations of insertions or deletions
- Lists are specified by
delimiting their elements within parentheses
Ex, (A B C D)
- Nested list structures
are also specified by parentheses
Ex, (A (B C) D (E (F G)))
- The above list contains
4 elements: the first element is
A, the second is (B C), the third is D and the fourth is (E (F G))
- Internally, lists are
usually stored as single-linked list structures, in which each node has 2
pointers and represents an element
THE
FIRST LISP INTERPRETER
- The first requirements
for the universal Lisp function was a notation that allowed functions to
be expressed in the same way data was expressed
- Function calls are
specified in a prefix list form
Ex, (function_name arg_1 … arg_n)
- ex, if a + is a
function that takes 2 numeric parameters, ( + 5 7)
evaluates to 12.
- The function Evaluation
could evaluate any other function and was itself in the form of an
expression.
- A feature of early Lisp
systems was the use of dynamic scoping
AN INTRO TO SCHEME
- The scheme language
emerged from MIT in mid 70’s
- It is characterized by
its small size and use of static scoping
- As first class
entities, Scheme functions can be the values of expressions and elements of
lists, and they can be assigned
- Scheme is well suited
for educational applications
- Names in Scheme can
consist of letters, digits, and special characters except parentheses;
they are
- EXPRESSION
VALUE
42 42
(* 3 7 ) 21
(+ 5 7 8 ) 20
(- 5 6 ) -1
(- 15 7 2 ) 6
(-24 ( * 4 3 ) 12
- Eval is the basis of all
function evaluation in Scheme, whether primitive or otherwise
- To avoid evaluation a
parameter, it is first given as a parameter to the primitive function
QUOTE, which simply returns it with out change
- Ex, (QUOTE A ) returns A
- Ex, (QOUTE (A B C) returns
(A B C)
- The above could be done
as ‘(A B)
- There are 2 primitive
list selectors in Scheme: CAR and
CDR
- The CAR function
returns the first element of a given list
- (CAR ‘(A
B C)) - A
- (CAR ‘((A
B ) C D)) - (A B)
- (CAR ‘A) -
ERROR
- The CDR function
returns the remainder of a given list after its CAR is removed
- (CDR ‘(A
B C )) - (B C)
- (CDR ‘((A
B) C D))
- (C D)
- (CDR ‘A) - ERROR
- (CDR ‘(A)) -
( )
- CAR -- contents of address register
- CDR -- contents of decrement register
- CONS is the primitive
list constructor
- it builds a list from
its 2 arguments, the first is which can be either an atom or a list; the
second is usually a list
- (CONS ‘A
‘( )) - (A)
- (CONS ‘A
‘(B C)) - (A B C)
- (CONS ‘( )
‘(A B)) - (A B C)
- (CONS ‘( )
‘(A B)) - (( ) A B)
- (CONS ‘(A B) ‘(C D))
- ((A B) C
D)
- The CONS is the inverse
of CAR and CDR
- CAR and CDR take a list
apart, and CONS constructs a new list from given list parts
- LIST is a function that
constructs lists from a variable number of parameters
COMMON LISP
·
A combination of several dialects of Lisp
·
The list of features of COMMON Lisp are:
o
A large number of data types and structures, including such things as
records, arrays, complex numbers, and character strings
o
Powerful input and output operations
o
A form of packages for modularizing collections of functions and data
o
Providing access control