2021/2/15 COMP3007: Ch3
HOME COMP 3007
Course Notes
COMP 3007
Outline
Lectures
Assignments
Schedule
3 PROCEDURES
What’s in this set of notes?
First-class & Higher Order Procedures Lexical Closures
Problem: Computing Square Roots
Defined as: √ x = y, such that y2 = x
An Algorithm
Newton’s method of successive approximations: 1. Guess y for value of square root of number x 2. To get a better guess, average y with x/y
Building Abstractions with Procedures
Recursion & Iteration
3.1 P
B
UILDING
A
BSTRACTIONS
WITH
ROCEDURES
people.scs.carleton.ca/~arunka/courses/comp3007/lectures/03-Procedures/307Notes3.html 1/12
2021/2/15 COMP3007: Ch3
3. Stop when the guess (y) is good enough (y2 ≅ x) E.g. To compute the square root of 2:
Guess (y)
Quotient (x/y)
Average (((x/y) + y) / 2) => next guess
1.0
2/1.0 = 2.0
(2.0 + 1.0) / 2 = 1.5
1.5
2/1.5 = 1.333
(1.3333 + 1.5) / 2 = 1.4167
1.4167
2/1.4167 = 1.4118
(1.4167 + 1.4118) / 2 = 1.4142
1.4142
…etc…
…etc…
A Program
Computing square roots is an example of a process that can be defined by a set of mutually defined procedures
Problem breaks up naturally into subproblems: decomposition strategy
Solutions can be expressed for each subproblem individually: divide- and-conquer
(define (square y)
(* y y))
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
(define (average x y)
(/ (+ x y) 2))
(define (improve guess x)
(average guess (/ x guess)))
(define (sqrt-iteration guess x)
(if (good-enough? guess x)
guess
(sqrt-iteration (improve guess x) x)))
(define (sqrt x)
(sqrt-iteration 1.0 x))
Procedural Abstraction
A procedure definition should be able to suppress details (aka black box abstraction)
people.scs.carleton.ca/~arunka/courses/comp3007/lectures/03-Procedures/307Notes3.html 2/12
2021/2/15 COMP3007: Ch3
Users of procedure may not have written it
Users do not need to know how a procedure is implemented in order to use it!
Consider the procedure square: we know what it does, but how does it do it?
A. (define (square x) (* x x))
B. (define (square x) (exp (double (log x)))) C. Or, some recursive sequence of additions...
It doesn't matter, so long as it works we can call (square 3) and get
the expected result.
Similarly... the following implementations of square should be equivalent to the user
A. (define (square x)(* x x)) B. (define (square y)(* y y))
That is, procedure usage should be independent of the parameter names chosen
Scope
A variable binding is an assocation of a name with a value
In purely functional languages, variable bindings are considered constant
Procedure application binds its formal parameters to the values of its arguments
The set of expressions for which a given binding is valid is called the scope of that variable
The environment consists of many nested scopes.
Programming language provides a primitive environment: +, -, number?, etc.
The program begins in the global scope: (define (sqrt...))
The definition of a function creates a new local scope: parameters & local variables
Block Structure
Namespace pollution occurs when a programmer overloads the global scope with bindings
How does one hide the choice of procedure names from users of sqrt?
Allow procedures to have internal definitions of local procedures Such nesting of definitions to any depth is referred to as block structure
E.g.:
Developer's view of sqrt procedure:
people.scs.carleton.ca/~arunka/courses/comp3007/lectures/03-Procedures/307Notes3.html 3/12
2021/2/15 COMP3007: Ch3
(define (sqrt x)
(define (square y)(* y y))
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
(define (average x y)
(/ (+ x y) 2))
(define (improve guess x)
(average guess (/ x guess)))
(define (sqrt-iteration guess x)
(if (good-enough? guess x)
guess
(sqrt-iteration (improve guess x) x)))
(sqrt-iteration 1.0 x))
User's view of sqrt procedure:
(define (sqrt x)
...)
User cannot directly use procedures square, good-enough?, improve, or sqrt-iteration
Free variables
Nested procedures means nested scopes
In Scheme, the nesting of scopes matches the nesting of the program's block structure
This is called lexical scoping.
The scope of a variable spans all nested scopes
Variables that are used within a scope while being unbound in that scope (i.e., non-local variables) are called free variables.
E.g. In the following code, the symbol x refers to a free variable in the nested procedures good-enough? and improve.
(define (sqrt x)
(define (square y)(* y y))
(define (good-enough? guess)
(< (abs (- (square guess) x)) 0.001))
(define (average x y)
(/ (+ x y) 2))
(define (improve guess)
people.scs.carleton.ca/~arunka/courses/comp3007/lectures/03-Procedures/307Notes3.html 4/12
2021/2/15 COMP3007: Ch3
(average guess (/ x guess)))
(define (sqrt-iteration guess)
(if (good-enough? guess)
guess
(sqrt-iteration (improve guess))))
(sqrt-iteration 1.0))
Scope vs Visibility
The scope of a variable is the set of expressions for which the variable exists
The visibility of a variable is the set of expressions for which the variable can be reached
Free variables can be hidden by local variables (e.g. the x in average). Special Form: Let
The special form let provides the ability to define local variables. let syntax:
(let ((
.
.
.
(
)
Where vari is a symbol and expi is an expression.
Example: good-enough? with local variables
(define (good-enough? guess x)
(let ((tolerance 0.0001)
(difference (abs (- (square guess) x))))
(< difference tolerance)))
Repetition
Repetition is a fundamental mechanism of control flow in programming languages
3.2
RECURSION
& I
TERATION
people.scs.carleton.ca/~arunka/courses/comp3007/lectures/03-Procedures/307Notes3.html 5/12
2021/2/15 COMP3007: Ch3
Without repetition the program (text) would closely match the
process (execution) in terms of length and space requirements The two principal means to accomplish repetition are recursion and iteration
Functional languages tend towards recursive language features
Imperative languages tend towards iterative language features For an introductory discussion on recursion see: (Morton, J., 1976)
Example: Factorial function
Factorial definition:
n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
Equivalently...
n! = n * (n - 1)!
1! = 1
Linear Recursive Process
(define (factorial n) (if (= n 1)
1
(* n (factorial (- n 1)))))
Substitution model for the recursive process
This is a recursive process:
Expansion followed by contraction
The interpreter keeps track of a chain of deferred operations to perform later
State of the process is stored on the stack
The memory requirement grows linearly with the number of steps (n)
Linear Iterative Process
(define (factorial n)
(define (factorial-iteration product counter)
(if (> counter n)
product
(factorial-iteration (* counter product) (+ counter 1)))) (factorial-iteration 1 1))
(factorial 5) => ?
people.scs.carleton.ca/~arunka/courses/comp3007/lectures/03-Procedures/307Notes3.html 6/12
2021/2/15 COMP3007: Ch3
Substitution model for the iterative process
(factorial 5) => ?
This is an iterative process:
Process (execution) resembles a logically controlled loop
Initial value, increment, running total, stopping condition Each recursive call corresponds to one iteration
State of the process is stored in variables, passed from one iteration to the next
Program is tail-recursive
No deferred operations
Recursive call is the last operation of the procedure
Scheme uses tail-call optimization
The iterative process above is run in constant space
The number of steps still grows linearly with n, but memory remains constant
Comment:
The above programs are both recursive (syntactically the procedure refers to itself)
Don’t confuse this with the notion of a recursive process (semantics of the evolution of computation)
Tree Recursion
Example: Fibonacci Numbers
Fib(n) = 0
Fib(n) = 1
Fib(n) = Fib(n – 1) + Fib(n – 2)
0, 1, 1, 2, 3, 5, 8, 13, 21 ….
Recursive Process
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
if n = 0
if n = 1
otherwise
The process looks like a tree…
people.scs.carleton.ca/~arunka/courses/comp3007/lectures/03-Procedures/307Notes3.html 7/12
2021/2/15 COMP3007: Ch3
It is inefficient due to duplicate computation
Iterative Process
(define (fib n)
(define (fib-iteration n1 n2 count)
(if (= count n)
n1
(fib-iteration (+ n1 n2) n1 (+ count 1))))
(if (<= n 1) n
(fib-iteration 1 0 1))
Substitution model:
(fib 7)
(fib-iteration 1 0 1)
(fib-iteration 1 1 2)
(fib-iteration 2 1 3)
(fib-iteration 3 2 4)
(fib-iteration 5 3 5)
(fib-iteration 8 5 6)
(fib-iteration 13 8 7)
13
Numbers and other primitive data types are considered first-class data types in most languages
Can be passed into functions as arguments
Can be returned from functions
Can be assigned to a variable, or stored in a data structure Can be represented as literal values
3.3
FIRST-
CLASS
& H
IGHER
O
RDER
P
ROCEDURES
Procedures are first-class values in functional languages
people.scs.carleton.ca/~arunka/courses/comp3007/lectures/03-Procedures/307Notes3.html 8/12
2021/2/15 COMP3007: Ch3
A higher order procedure is one which:
Takes one or more procedures as argument, and/or Returns a procedure as a result
Procedures as Arguments
Higher order procedures support abstraction
For example, look for a pattern in the following problems
Compute the sum of integers from a to b: e.g.: 1 + 2 + 3 +... + 99 + 100
(define (sum-int a b)
(if (> a b)
0
(+ a
(sum-int (+ a 1) b))))
Compute the sum of cubes from a through b:
e.g.: 13 + 23 + 33 + … + 993 + 1003
(define (cube x) (* x x x ))
(define (sum-cubes a b)
(if (> a b)
0
(+ (cube a)
(sum-cubes (+ a 1) b))))
Compute the following series which converges to π/8 (1/(1 × 3)) + (1/(5 × 7)) + (1/(9 × 11)) + . . . :
(define (pi-sum a b)
(if (> a b)
0
(+ (/ 1.0 (* a (+ a 2)))
(pi-sum (+ a 4) b))))
We can abstract the pattern into a higher-order procedure:
(define (sum a b term next) (if (> a b)
0
(+ (term a)
(sum (next a) b term next))))
Now the sum-int, sum-cubes, and pi-sum examples can be expressed as instances of a generalized sum procedure
people.scs.carleton.ca/~arunka/courses/comp3007/lectures/03-Procedures/307Notes3.html 9/12
2021/2/15 COMP3007: Ch3
(define (sum-int a b)
(define (identity n) n)
(define (inc n) (+ n 1))
(sum a b identity inc))
(define (sum-cubes a b)
(define (cube n) (* n n n))
(define (inc n) (+ n 1))
(sum a b cube inc))
;a simple
;a simple
;a cubing
;a simple
(define (pi-sum a b)
(define (pi-term x) (/ 1.0 (* x (+ x 2))))
(define (pi-next x) (+ x 4))
(sum a b pi-term pi-next))
Anonymous functions
Create procedures without binding them to an identifier
Like using a literal value (e.g. 3) without of defining a variable (e.g. x) to hold it
More convenient than defining trivial or single-use procedures such as inc or cube
Use the special form lambda:
;syntax
(lambda (
For example:
(lambda (x) (* x x x))
;evaluates to a procedure that cubes its input
(lambda (x) (/ 1.0 (* x (+ x 2))))
;evaluates to a procedure that is like pi-term
Evaluating a lambda expression returns a procedure object
So, lambdas can be used wherever a procedure would be used:
((lambda (x) (+ x 4)) 2)
; => 6
Note: the syntax we’ve used up until now…
(define (plus4 x) (+ x 4))
…is equivalent to…
(define plus4 (lambda (x) (+ x 4)))
people.scs.carleton.ca/~arunka/courses/comp3007/lectures/03-Procedures/307Notes3.html 10/12
2021/2/15 COMP3007: Ch3
3.4
L
EXICAL
C
LOSURES
Recall: lexical scoping means nested functions can use the free variables in their enclosing scope(s)
How does this work when a nested function is returned by its enclosing scope?
E.g. What happens to the variable x in the following example? (define (multiplyBy x)
(lambda (y)(* x y)))
(define double (multiplyBy 2))
(define triple (multiplyBy 3))
The procedures double and triple both remember their own values of x! As though the lambda stores the values of the free variables.
A closure is a combination of a procedure, and the environment (non-local bindings) that it uses.
Consider the following substitution models:
> (define double (multiplyBy 2))
(define double (lambda(y)(* 2 y)))
> (define triple (multiplyBy 3))
(define triple (lambda(y)(* 3 y)))
> (double 7)
((lambda (y)(* 2 y)) 7)
(* 2 7)
14
> (triple 7)
((lambda (y)(* 3 y)) 7)
(* 3 7)
21
The procedures for double and triple were created in separate instances of multiplyBy
…so they have separate values for the free variable x
Note: this model assumes that the binding for each instance of x will never change.
What is a closure?
When a procedure is defined, a closure is created A closure is a pair of references:
people.scs.carleton.ca/~arunka/courses/comp3007/lectures/03-Procedures/307Notes3.html 11/12
2021/2/15 COMP3007: Ch3
To the procedure itself, and
to the referencing environment
The procedure contains the list of formal parameters and the body of instructions to evaluate.
The referencing environment is the visible set of bindings in effect when/where the procedure was defined
Note: due to lexical scoping, this matches the block structure where the lambda or define text appears
I.e., it is a pointer to the procedure’s enclosing scope.
The closure contains the necessary information to evaluate the procedure whenever it’s called.
The procedure can still use its free variables when invoked Even if its invoked from outside of its enclosing scope
Top
people.scs.carleton.ca/~arunka/courses/comp3007/lectures/03-Procedures/307Notes3.html 12/12