o A Python implementation:
>>> sum([1,2,3,4])
10
>>>
Computations is function application.
4. FPL Characteristics:
Functional programming languages are modeled on the
concept of mathematical functions, and use only
conditional expressions and recursion to effect
computation.
In the purest form they use neither variables nor
assignment statements, although this is relaxed somewhat
in most applied functional languages.
The concept of side effects is also alien to purely functional
programming: a function is given values and returns a
value, there are no variables to manipulate and hence no
possibility for side effects.
Programs are constructed by composing function
applications - the values produced by one or more functions
become the parameters to another.
For reasons of efficiency (because the underlying machine
is, in fact, imperative) most functional languages provide
some imperative-style capabilities, including variables with
A. Bellaachia Page: 5
assignment, sequences of statements, and imperative style
loop structures.
Note that the functional paradigm can also be used with
some imperative languages - e.g. C has both a conditional
expression and support for recursion - so the factorial
function code be coded in functional style in C (or C++ or
Java) as follows: int fact(int x){ return (x == 0) ? 1 : x *
fact(x - 1); }
Three primary components:
A set of data object: A single, high-level
data structure like a list
A set of built-in functions for object
manipulation: Building, deconstructing,
and accessing lists
A set of functional forms for building
new functions: Composition, reduction,
etc.
5. Lambda calculus (LC)
A method of modeling the computational aspects of
functions
It helps us understand the elements and semantics of
functional programming languages independent of
syntax
5.1. LC expressions forms
There are three LC expressions forms:
A. Bellaachia Page: 6
o e1: A single identifier (such as x, or 3)
o e2: A function definition of the form (x.e)
:The expression e, with x being a bound
variable
e is the body of the function, x
is a parameter
e may be any of the three types
of expressions
square( x ) would be written as
(x.x*x)
o e3: A function application of the form e1 e2
Meaning e1 applied e2
square applied to 2 would be
((x.x*x) 2)
Free and Bound Variables:
A variable appearing in a function F is
said to be free if it is not bound in F
Bound variables are like formal
parameters, and act like local variables
Free variables are like non-local variables
that will be bound at an outer level:
In the function x.xk, x is
bound and k is free
Substitution: Applying a function
o To apply a function, we rewrite the function,
substituting all occurrences of the bound
A. Bellaachia Page: 7
variable by the argument
o We use substitution to replace all occurrences of an
identifier with an expression:
[e/x]y means "substitute e for all
occurrences of x in expression y"
5.2. Semantic of Functional Computations:
We define the result of a function application in
terms of the following:
o Rewriting the definition
o Replacing bound variables with the
corresponding arguments
Rewrite rules:
o r1: Renaming
xi.e xj.[xj/xi]e, where xj is not free
in e
We can replace all occurrences of the
name of a bound variable with another
name without changing the meaning
o r2: Application
(x.e1)e2 [e2/x]e1
Replace the bound variable with the
argument to the application
A. Bellaachia Page: 8
