[SOLVED] CS scheme chain data structure algorithm interpreter 2021/2/15 COMP3007: Ch3

2021/2/15 COMP3007: Ch3
HOME COMP 3007
Course Notes
COMP 3007
Outline
Lectures
Assignments
Schedule
3 PROCEDURES
Whats 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
Newtons 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 AbstractionA 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: Ch3Users of procedure may not have written itUsers 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 getthe expected result.Similarly… the following implementations of square should be equivalent to the userA. (define (square x)(* x x)) B. (define (square y)(* y y))That is, procedure usage should be independent of the parameter names chosenScopeA variable binding is an assocation of a name with a valueIn purely functional languages, variable bindings are considered constantProcedure application binds its formal parameters to the values of its argumentsThe set of expressions for which a given binding is valid is called the scope of that variableThe 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 variablesBlock StructureNamespace pollution occurs when a programmer overloads the global scope with bindingsHow 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 structureE.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-iterationFree variablesNested procedures means nested scopesIn Scheme, the nesting of scopes matches the nesting of the program’s block structureThis is called lexical scoping.The scope of a variable spans all nested scopesVariables 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 VisibilityThe scope of a variable is the set of expressions for which the variable existsThe visibility of a variable is the set of expressions for which the variable can be reachedFree variables can be hidden by local variables (e.g. the x in average). Special Form: LetThe 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)))RepetitionRepetition is a fundamental mechanism of control flow in programming languages 3.2RECURSION& I TERATIONpeople.scs.carleton.ca/~arunka/courses/comp3007/lectures/03-Procedures/307Notes3.html 5/12 2021/2/15 COMP3007: Ch3Without repetition the program (text) would closely match theprocess (execution) in terms of length and space requirements The two principal means to accomplish repetition are recursion and iterationFunctional languages tend towards recursive language featuresImperative languages tend towards iterative language features For an introductory discussion on recursion see: (Morton, J., 1976)Example: Factorial functionFactorial definition:n! = n * (n – 1) * (n – 2) * … * 3 * 2 * 1Equivalently…n! = n * (n – 1)!1! = 1Linear Recursive Process(define (factorial n) (if (= n 1)1(* n (factorial (- n 1)))))Substitution model for the recursive processThis is a recursive process:Expansion followed by contractionThe interpreter keeps track of a chain of deferred operations to perform laterState of the process is stored on the stackThe 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)
Dont 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)13Numbers and other primitive data types are considered first-class data types in most languagesCan be passed into functions as argumentsCan be returned from functionsCan be assigned to a variable, or stored in a data structure Can be represented as literal values3.3FIRST- CLASS& HIGHERORDERPROCEDURESProcedures 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: Ch3A higher order procedure is one which:Takes one or more procedures as argument, and/or Returns a procedure as a resultProcedures as ArgumentsHigher order procedures support abstractionFor example, look for a pattern in the following problemsCompute 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 function
;a simple function
;a cubing function
;a simple function
(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 weve 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 procedures enclosing scope.
The closure contains the necessary information to evaluate the procedure whenever its 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