|
|
|
Part 2 Summer 2014 Web.pdf
Part_2_Summer_2014_Web.pdf
Showing 1-4 out of 53
Part 2 Summer 2014 Web.pdf-Part II: Functional Pro...
Part_2_Summer_2014_Web.pdf-Part II: Functional Programming with LISP
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
is a programming paradigm
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
addition to its return value.
•
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
statements about the function hold.
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.
Ace your assessments! Get Better Grades
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
Know more
Students also viewed documents
lab 18.docx
lab_18.docx
Course
Course
3
Module5QuizSTA2023.d...
Module5QuizSTA2023.docx.docx
Course
Course
10
Week 7 Test Math302....
Week_7_Test_Math302.docx.docx
Course
Course
30
Chapter 1 Assigment ...
Chapter_1_Assigment_Questions.docx.docx
Course
Course
5
Week 4 tests.docx.do...
Week_4_tests.docx.docx
Course
Course
23
Week 6 tests.docx.do...
Week_6_tests.docx.docx
Course
Course
106
