Part 2 Summer 2014 Web.pdf-Part II: Func...
Part_2_Summer_2014_Web.pdf-Part II: Functional Programming with LISP
Showing 1-4 out of 53
Part 2 Summer 2014 Web.pdf-Part II:...
Part_2_Summer_2014_Web.pdf-Part II: Functional Programming with LISP
##### Page 1
1
Part II:
Functional Programming with
LISP
COMP 348/1: Principles of Programming
Languages
Dr. Jamal Bentahar
Acknowledgement: Dr. C. Constantinides
Concordia University
2
Mathematical Definition: Function
Suppose A and B are sets and for each element in A we
associate exactly one element in B. Such an association
is called a
function
from A to B.
If
f
is a function from A to B, we write
f: A
B
We also say that
f
has type
A
B
.
The set A is called
the domain
of
f
, and B is the
codomain
of
f
.
The range
of
f
is the set of elements in B that are
associated with some element of A.

##### Page 2
2
3
Functional Programming
Functional programming
where everything is a function.
A program is
an evaluation
of a function.
For example
(* 3 4)
will invoke the
*
function on the
arguments
3
and
4
and will return 12.
Pure functional programming disallows the use of
side-
effects
.
4
Side Effects
In computer science, a function or expression is said
to produce a
side effect
if it modifies some state in
For example a function might:
– modify a global or a static variable,
– modify one of its arguments,
– write data to a display or file, or
– read some data from other side-effecting
functions.

##### Page 3
3
5
Pure Functions
A function may be described as
pure
if both these
1.
The function always evaluates the same result value given the
same argument value(s).
2.
The evaluation of the result does not cause any semantically
observable side effect or output, such as mutation of mutable
objects or output to I/O devices.
Examples:
length(s)
is pure because returns the size of a string
s
.
today()
is impure because at different times it will yield
different results.
print()
is impure because it causes output as an effect.
6
Example 1: Optimization through
Common Subexpression Elimination
y = f(x) * f(x);
A compiler can perform an optimization by factoring out
f(x)
if it is pure, transforming the program to
z = f(x);
y = z * z;
and eliminating the second evaluation of the (possibly
costly) call to
f(x)
.
This optimization strategy is called common subexpression
elimination.

##### Page 4
4
7
Example 2
If a function is not pure, the function call cannot be
eliminated:
y = random() * random();
The second call to
random()
cannot be eliminated,
because its return value may be different from that
of the first call.
8
Idempotence
Idempotence is a property of a mathematical operation
that has the same effect if used multiple times as it does
if used only once.
For example, the absolute value,
abs()
,
function is
idempotent, as
abs(x) = abs(abs(x))
= abs(abs(abs(x)))
= ... for all x.
In other words, applying
abs
exactly once yields the
same value as repeatedly applying
abs
any number
of times.

Browse thousands of Study Materials & Solutions from your Favorite Schools
Concordia University
Concordia_University
School:
Principles_Of_Programming_Lang
Course:
Great resource for chem class. Had all the past labs and assignments
Leland P.
Santa Clara University
Introducing Study Plan
Using AI Tools to Help you understand and remember your course concepts better and faster than any other resource.
Find the best videos to learn every concept in that course from Youtube and Tiktok without searching.
Save All Relavent Videos & Materials and access anytime and anywhere
Prepare Smart and Guarantee better grades