Programming Languages and Paradigms COMP 302
Prof. Errington
School of Computer Science Mc
Copyright By PowCoder代写 加微信 powcoder
Fall 2022 – Week 2, lesson 2
Announcements
Elections: 3 October. Classes cancelled. (No effect to us.) Advance polling available. (See #announcements.)
TA office hours posted. (See #info.)
My office hours: Tuesday 2:45 – 4 and Friday 3 – 4.
Last time…
let … in … expressions: operational and static semantics.
Code writing: using recursion instead of loops.
This time…
Performance of recursion.
Tracing recursive functions.
Defining new types.
Working with user-defined types.
Functions: an abstraction Background
CPU doesn’t know what a “function” is.
CPU only has, essentially, goto statements to jump to a particular instruction to execute.
Functions: an abstraction Background
CPU doesn’t know what a “function” is.
CPU only has, essentially, goto statements to jump to a
particular instruction to execute.
Set aside a chunk of memory for keeping track of function calls: this is the call stack.
Functions: an abstraction Background
CPU doesn’t know what a “function” is.
CPU only has, essentially, goto statements to jump to a
particular instruction to execute.
Set aside a chunk of memory for keeping track of function calls: this is the call stack.
To perform a call:
Functions: an abstraction Background
CPU doesn’t know what a “function” is.
CPU only has, essentially, goto statements to jump to a
particular instruction to execute.
Set aside a chunk of memory for keeping track of function calls: this is the call stack.
To perform a call:
1. Push the current instruction address on the call stack.
Functions: an abstraction Background
CPU doesn’t know what a “function” is.
CPU only has, essentially, goto statements to jump to a
particular instruction to execute.
Set aside a chunk of memory for keeping track of function calls: this is the call stack.
To perform a call:
1. Push the current instruction address on the call stack. 2. Push the arguments of the function onto the call stack.
Functions: an abstraction Background
CPU doesn’t know what a “function” is.
CPU only has, essentially, goto statements to jump to a
particular instruction to execute.
Set aside a chunk of memory for keeping track of function calls: this is the call stack.
To perform a call:
1. Push the current instruction address on the call stack.
2. Push the arguments of the function onto the call stack. 3. Jump to the code of the function.
Functions: an abstraction Background
CPU doesn’t know what a “function” is.
CPU only has, essentially, goto statements to jump to a
particular instruction to execute.
Set aside a chunk of memory for keeping track of function calls: this is the call stack.
To perform a call:
1. Push the current instruction address on the call stack.
2. Push the arguments of the function onto the call stack. 3. Jump to the code of the function.
To return from a call:
Functions: an abstraction Background
CPU doesn’t know what a “function” is.
CPU only has, essentially, goto statements to jump to a
particular instruction to execute.
Set aside a chunk of memory for keeping track of function calls: this is the call stack.
To perform a call:
1. Push the current instruction address on the call stack.
2. Push the arguments of the function onto the call stack. 3. Jump to the code of the function.
To return from a call:
1. Pop all arguments off of the stack.
Functions: an abstraction Background
CPU doesn’t know what a “function” is.
CPU only has, essentially, goto statements to jump to a
particular instruction to execute.
Set aside a chunk of memory for keeping track of function calls: this is the call stack.
To perform a call:
1. Push the current instruction address on the call stack.
2. Push the arguments of the function onto the call stack. 3. Jump to the code of the function.
To return from a call:
1. Pop all arguments off of the stack.
2. Pop the return address off of the stack.
Functions: an abstraction Background
CPU doesn’t know what a “function” is.
CPU only has, essentially, goto statements to jump to a
particular instruction to execute.
Set aside a chunk of memory for keeping track of function calls: this is the call stack.
To perform a call:
1. Push the current instruction address on the call stack.
2. Push the arguments of the function onto the call stack. 3. Jump to the code of the function.
To return from a call:
1. Pop all arguments off of the stack.
2. Pop the return address off of the stack. 3. Jump to the return address.
Call stack visualization: tracing
let rec sum n =
if n = 0 then 0 else n + sum (n-1)
sum n adds up all integers from 0 to n Tracing
Let’s trace the evaluation of sum 5.
A trace shows every step of the computation until we reach a value, where no more evaluation is possible.
Call stack visualization: tracing
let rec sum n =
if n = 0 then 0 else n + sum (n-1)
sum n adds up all integers from 0 to n 1. sum 5 → subst. 5 into fn
Call stack visualization: tracing
let rec sum n =
if n = 0 then 0 else n + sum (n-1)
sum n adds up all integers from 0 to n
1. sum 5 → subst. 5 into fn
2. if 5 = 0 then 0 else 5 + sum (5 – 1)→evalcondition
Call stack visualization: tracing
let rec sum n =
if n = 0 then 0 else n + sum (n-1)
sum n adds up all integers from 0 to n
1. sum 5 → subst. 5 into fn
2. if 5 = 0 then 0 else 5 + sum (5 – 1)→evalcondition
3. if false then 0 else 5 + sum (5 – 1) → choose else-branch
Call stack visualization: tracing
let rec sum n =
if n = 0 then 0 else n + sum (n-1)
sum n adds up all integers from 0 to n
1. sum 5 → subst. 5 into fn
2. if 5 = 0 then 0 else 5 + sum (5 – 1)→evalcondition
3. if false then 0 else 5 + sum (5 – 1) → choose else-branch 4. 5 + sum 4 → recursive call
Call stack visualization: tracing
let rec sum n =
if n = 0 then 0 else n + sum (n-1)
sum n adds up all integers from 0 to n
1. sum 5 → subst. 5 into fn
2. if 5 = 0 then 0 else 5 + sum (5 – 1)→evalcondition
3. if false then 0 else 5 + sum (5 – 1) → choose else-branch 4. 5 + sum 4 → recursive call
5. 5 + (4 + sum 3) →recursivecall
Call stack visualization: tracing
let rec sum n =
if n = 0 then 0 else n + sum (n-1)
sum n adds up all integers from 0 to n
1. sum 5 → subst. 5 into fn
2. if 5 = 0 then 0 else 5 + sum (5 – 1)→evalcondition
3. if false then 0 else 5 + sum (5 – 1) → choose else-branch 4. 5 + sum 4 → recursive call
5. 5 + (4 + sum 3) →recursivecall
6. 5 + (4 + (3 + sum 2)) →recursivecall
Call stack visualization: tracing
let rec sum n =
if n = 0 then 0 else n + sum (n-1)
sum n adds up all integers from 0 to n
1. sum 5 → subst. 5 into fn
2. if 5 = 0 then 0 else 5 + sum (5 – 1)→evalcondition
3. if false then 0 else 5 + sum (5 – 1) → choose else-branch 4. 5 + sum 4 → recursive call
5. 5 + (4 + sum 3) →recursivecall
6. 5 + (4 + (3 + sum 2)) →recursivecall
7. 5 + (4 + (3 + (2 + sum 1))) →recursivecall
Call stack visualization: tracing
let rec sum n =
if n = 0 then 0 else n + sum (n-1)
sum n adds up all integers from 0 to n
1. sum 5 → subst. 5 into fn
2. if 5 = 0 then 0 else 5 + sum (5 – 1)→evalcondition
3. if false then 0 else 5 + sum (5 – 1) → choose else-branch 4. 5 + sum 4 → recursive call
5. 5 + (4 + sum 3) →recursivecall
6. 5 + (4 + (3 + sum 2)) →recursivecall
7. 5 + (4 + (3 + (2 + sum 1))) →recursivecall
8. 5 + (4 + (3 + (2 + (1 + sum 0)))) → return; add
Call stack visualization: tracing
let rec sum n =
if n = 0 then 0 else n + sum (n-1)
sum n adds up all integers from 0 to n
1. sum 5 → subst. 5 into fn
2. if 5 = 0 then 0 else 5 + sum (5 – 1)→evalcondition
3. if false then 0 else 5 + sum (5 – 1) → choose else-branch 4. 5 + sum 4 → recursive call
5. 5 + (4 + sum 3) →recursivecall
6. 5 + (4 + (3 + sum 2)) →recursivecall
7. 5 + (4 + (3 + (2 + sum 1))) →recursivecall
8. 5 + (4 + (3 + (2 + (1 + sum 0)))) → return; add
9. 5 + (4 + (3 + (2 + (1 + 0)))) → return; add
Call stack visualization: tracing
let rec sum n =
if n = 0 then 0 else n + sum (n-1)
sum n adds up all integers from 0 to n
1. sum 5 → subst. 5 into fn
2. if 5 = 0 then 0 else 5 + sum (5 – 1)→evalcondition
3. if false then 0 else 5 + sum (5 – 1) → choose else-branch 4. 5 + sum 4 → recursive call
5. 5 + (4 + sum 3) →recursivecall
6. 5 + (4 + (3 + sum 2)) →recursivecall
7. 5 + (4 + (3 + (2 + sum 1))) →recursivecall
8. 5 + (4 + (3 + (2 + (1 + sum 0)))) → return; add
9. 5 + (4 + (3 + (2 + (1 + 0)))) → return; add
10. 5 + (4 + (3 + (2 + 1)))→return;add
Call stack visualization: tracing
let rec sum n =
if n = 0 then 0 else n + sum (n-1)
sum n adds up all integers from 0 to n
1. sum 5 → subst. 5 into fn
2. if 5 = 0 then 0 else 5 + sum (5 – 1)→evalcondition
3. if false then 0 else 5 + sum (5 – 1) → choose else-branch 4. 5 + sum 4 → recursive call
5. 5 + (4 + sum 3) →recursivecall
6. 5 + (4 + (3 + sum 2)) →recursivecall
7. 5 + (4 + (3 + (2 + sum 1))) →recursivecall
8. 5 + (4 + (3 + (2 + (1 + sum 0)))) → return; add
9. 5 + (4 + (3 + (2 + (1 + 0)))) → return; add
10. 5 + (4 + (3 + (2 + 1)))→return;add 11. 5 + (4 + (3 + 3)) →return;add
Call stack visualization: tracing
let rec sum n =
if n = 0 then 0 else n + sum (n-1)
sum n adds up all integers from 0 to n
1. sum 5 → subst. 5 into fn
2. if 5 = 0 then 0 else 5 + sum (5 – 1)→evalcondition
3. if false then 0 else 5 + sum (5 – 1) → choose else-branch 4. 5 + sum 4 → recursive call
5. 5 + (4 + sum 3) →recursivecall
6. 5 + (4 + (3 + sum 2)) →recursivecall
7. 5 + (4 + (3 + (2 + sum 1))) →recursivecall
8. 5 + (4 + (3 + (2 + (1 + sum 0)))) → return; add
9. 5 + (4 + (3 + (2 + (1 + 0)))) → return; add
10. 5 + (4 + (3 + (2 + 1)))→return;add 11. 5 + (4 + (3 + 3)) →return;add
12. 5 + (4 + 6) →return;add
Call stack visualization: tracing
let rec sum n =
if n = 0 then 0 else n + sum (n-1)
sum n adds up all integers from 0 to n
1. sum 5 → subst. 5 into fn
2. if 5 = 0 then 0 else 5 + sum (5 – 1)→evalcondition
3. if false then 0 else 5 + sum (5 – 1) → choose else-branch 4. 5 + sum 4 → recursive call
5. 5 + (4 + sum 3) →recursivecall
6. 5 + (4 + (3 + sum 2)) →recursivecall
7. 5 + (4 + (3 + (2 + sum 1))) →recursivecall
8. 5 + (4 + (3 + (2 + (1 + sum 0)))) → return; add
9. 5 + (4 + (3 + (2 + (1 + 0)))) → return; add
10. 5 + (4 + (3 + (2 + 1)))→return;add 11. 5 + (4 + (3 + 3)) →return;add
12. 5 + (4 + 6) →return;add
13. 5 + 10 → return; add
Call stack visualization: tracing
let rec sum n =
if n = 0 then 0 else n + sum (n-1)
sum n adds up all integers from 0 to n
1. sum 5 → subst. 5 into fn
2. if 5 = 0 then 0 else 5 + sum (5 – 1)→evalcondition
3. if false then 0 else 5 + sum (5 – 1) → choose else-branch 4. 5 + sum 4 → recursive call
5. 5 + (4 + sum 3) →recursivecall
6. 5 + (4 + (3 + sum 2)) →recursivecall
7. 5 + (4 + (3 + (2 + sum 1))) →recursivecall
8. 5 + (4 + (3 + (2 + (1 + sum 0)))) → return; add
9. 5 + (4 + (3 + (2 + (1 + 0)))) → return; add
10. 5 + (4 + (3 + (2 + 1)))→return;add 11. 5 + (4 + (3 + 3)) →return;add
12. 5 + (4 + 6) →return;add
13. 5 + 10 → return; add
Where is the call stack exactly?
2. 5 + sum 4
let rec sum n =
if n = 0 then 0 else n + sum (n-1)
3. 5 + (4 4. 5 + (4 5. 5 + (4 6. 5 + (4 7. 5 + (4 8. 5 + (4 9. 5 + (4
10. 5 + (4 11. 5 + 10 12. 15
+ (2 + sum 1)))
+ (2 + (1 + sum 0))))
+ (2 + (1 + 0))))
+ (2 + 1)))
Where is the call stack exactly?
2. 5 + sum 4
let rec sum n =
if n = 0 then 0 else n + sum (n-1)
3. 5 + (4 4. 5 + (4 5. 5 + (4 6. 5 + (4 7. 5 + (4 8. 5 + (4 9. 5 + (4
10. 5 + (4 11. 5 + 10 12. 15
+ (2 + sum 1)))
+ (2 + (1 + sum 0))))
+ (2 + (1 + 0))))
+ (2 + 1)))
The stack appears in the trace as the nested parentheses!
Stack overflow: not only a website
What happens if we try to evaluate sum 10000000 (ten million)?
Stack overflow: not only a website
What happens if we try to evaluate sum 10000000 (ten million)? boom
Stack overflow: not only a website
What happens if we try to evaluate sum 10000000 (ten million)?
Is there any hope for recursive algorithms on large inputs?
Trick: tail calls
let rec sum n =
if n = 0 then 0 else n + sum (n-1)
Stack growth is a consequence of our code structure:
There is something to do after the recursive call completes, i.e. adding n.
If there were nothing to do, then the stack frame could be recycled!
Efficient sum: sum’
Tracing sum’
Before: build up a stack of pending additions then do them. After: add up along the way with a partial sum argument.
Tracing sum’
let rec sum ‘ partial_sum n =
if n = 0 then partial_sum else sum’ (partial_sum + n) (n – 1)
1. sum’ 0 5 → subst. args. into body
Tracing sum’
let rec sum ‘ partial_sum n =
if n = 0 then partial_sum else sum’ (partial_sum + n) (n – 1)
1. sum’ 0 5 → subst. args. into body
2. if 5 = 0 then 0 else sum’ (0+5) (5-1) → eval. cond.
Tracing sum’
let rec sum ‘ partial_sum n =
if n = 0 then partial_sum else sum’ (partial_sum + n) (n – 1)
1. sum’ 0 5 → subst. args. into body
2. if 5 = 0 then 0 else sum’ (0+5) (5-1) → eval. cond.
3. if false then 0 else sum’ (0+5) (5-1) → choose else-branch
Tracing sum’
let rec sum ‘ partial_sum n =
if n = 0 then partial_sum else sum’ (partial_sum + n) (n – 1)
1. sum’ 0 5 → subst. args. into body
2. if 5 = 0 then 0 else sum’ (0+5) (5-1) → eval. cond.
3. if false then 0 else sum’ (0+5) (5-1) → choose else-branch 4. sum’ (0 + 5) (5 – 1) → add; recursive call
Tracing sum’
let rec sum ‘ partial_sum n =
if n = 0 then partial_sum else sum’ (partial_sum + n) (n – 1)
1. sum’ 0 5 → subst. args. into body
2. if 5 = 0 then 0 else sum’ (0+5) (5-1) → eval. cond.
3. if false then 0 else sum’ (0+5) (5-1) → choose else-branch 4. sum’ (0 + 5) (5 – 1) → add; recursive call
5. sum’ (5 + 4) (4 – 1) → add; recursive call
Tracing sum’
let rec sum ‘ partial_sum n =
if n = 0 then partial_sum else sum’ (partial_sum + n) (n – 1)
1. sum’ 0 5 → subst. args. into body
2. if 5 = 0 then 0 else sum’ (0+5) (5-1) → eval. cond.
3. if false then 0 else sum’ (0+5) (5-1) → choose else-branch 4. sum’ (0 + 5) (5 – 1) → add; recursive call
5. sum’ (5 + 4) (4 – 1) → add; recursive call
6. sum’ (9 + 3) (3 – 1) → add; recursive call
Tracing sum’
let rec sum ‘ partial_sum n =
if n = 0 then partial_sum else sum’ (partial_sum + n) (n – 1)
1. sum’ 0 5 → subst. args. into body
2. if 5 = 0 then 0 else sum’ (0+5) (5-1) → eval. cond.
3. if false then 0 else sum’ (0+5) (5-1) → choose else-branch 4. sum’ (0 + 5) (5 – 1) → add; recursive call
5. sum’ (5 + 4) (4 – 1) → add; recursive call
6. sum’ (9 + 3) (3 – 1) → add; recursive call
7. sum’ (12 + 2) (2 – 1) → add; recursive call
Tracing sum’
let rec sum ‘ partial_sum n =
if n = 0 then partial_sum else sum’ (partial_sum + n) (n – 1)
1. sum’ 0 5 → subst. args. into body
2. if 5 = 0 then 0 else sum’ (0+5) (5-1) → eval. cond.
3. if false then 0 else sum’ (0+5) (5-1) → choose else-branch 4. sum’ (0 + 5) (5 – 1) → add; recursive call
5. sum’ (5 + 4) (4 – 1) → add; recursive call
6. sum’ (9 + 3) (3 – 1) → add; recursive call
7. sum’ (12 + 2) (2 – 1) → add; recursive call
8. sum’ (14+1) (1-1) → add; rec. call; subst. args. into body
Tracing sum’
let rec sum ‘ partial_sum n =
if n = 0 then partial_sum else sum’ (partial_sum + n) (n – 1)
1. sum’ 0 5 → subst. args. into body
2. if 5 = 0 then 0 else sum’ (0+5) (5-1) → eval. cond.
3. if false then 0 else sum’ (0+5) (5-1) → choose else-branch 4. sum’ (0 + 5) (5 – 1) → add; recursive call
5. sum’ (5 + 4) (4 – 1) → add; recursive call
6. sum’ (9 + 3) (3 – 1) → add; recursive call
7. sum’ (12 + 2) (2 – 1) → add; recursive call
8. sum’ (14+1) (1-1) → add; rec. call; subst. args. into body 9. if 0 = 0 then 15 else sum’ (15 + 0) (0 – 1) → eval. cond.
Tracing sum’
let rec sum ‘ partial_sum n =
if n = 0 then partial_sum else sum’ (partial_sum + n) (n – 1)
1. sum’ 0 5 → subst. args. into body
2. if 5 = 0 then 0 else sum’ (0+5) (5-1) → eval. cond.
3. if false then 0 else sum’ (0+5) (5-1) → choose else-branch 4. sum’ (0 + 5) (5 – 1) → add; recursive call
5. sum’ (5 + 4) (4 – 1) → add; recursive call
6. sum’ (9 + 3) (3 – 1) → add; recursive call
7. sum’ (12 + 2) (2 – 1) → add; recursive call
8. sum’ (14+1) (1-1) → add; rec. call; subst. args. into body 9. if 0 = 0 then 15 else sum’ (15 + 0) (0 – 1) → eval. cond.
10. if true then 15 else … → choose then-branch
Tracing sum’
let rec sum ‘ partial_sum n =
if n = 0 then partial_sum else sum’ (partial_sum + n) (n – 1)
1. sum’ 0 5 → subst. args. into body
2. if 5 = 0 then 0 else sum’ (0+5) (5-1) → eval. cond.
3. if false then 0 else sum’ (0+5) (5-1) → choose else-branch 4. sum’ (0 + 5) (5 – 1) → add; recursive call
5. sum’ (5 + 4) (4 – 1) → add; recursive call
6. sum’ (9 + 3) (3 – 1) → add; recursive call
7. sum’ (12 + 2) (2 – 1) → add; recursive call
8. sum’ (14+1) (1-1) → add; rec. call; subst. args. into body 9. if 0 = 0 then 15 else sum’ (15 + 0) (0 – 1) → eval. cond.
10. if true then 15 else … → choose then-branch 11. 15
Where did the call stack go?
let rec sum ‘ partial_sum n =
if n = 0 then partial_sum else sum’ (partial_sum + n) (n – 1)
1. sum’ 0 5 2. sum’ 5 4 3. sum’ 9 3 4. sum’ 12 2 5. sum’ 14 1 6. sum’ 15 0 7. 15
One stack frame is allocated for the initial call to sum’. Recursive calls to sum’ reuse the same stack frame because the result of the recursive call is immediately returned.
Tail calls
The result of the recursive call is immediately returned.
In other words, the recursive call is a tail call.
Recap: tail calls and tail recursion
Tail call optimization (TCO) recycles the stack frame of the current function.
Recap: tail calls and tail recursion
Tail call optimization (TCO) recycles the stack frame of the current function.
Only possible when the last step of evaluating a function is to call another function.
Recap: tail calls and tail recursion
Tail call optimization (TCO) recycles the stack frame of the current function.
Only possible when the last step of evaluating a function is to call another function.
Very important for recursive algorithms! Enables running in constant stack space.
Recap: tail calls and tail recursion
Tail call optimization (TCO) recycles the stack frame of the current function.
Only possible when the last step of evaluating a function is to call another function.
Very important for recursive algorithms! Enables running in constant stack space.
An extra parameter is often needed to build up the result, often called an accumulator.
Recap: tail calls and tail recursion
Tail call optimization (TCO) recycles the stack frame of the current function.
Only possible when the last step of evaluating a function is to call another function.
Very important for recursive algorithms! Enables running in constant stack space.
An extra parameter is often needed to build up the result, often called an accumulator.
Recap: tail calls and tail recursion
Tail call optimization (TCO) recycles the stack frame of the current function.
Only possible when the last step of evaluating a function is to call another function.
Very important for recursive algorithms! Enables running in constant stack space.
An extra parameter is often needed to build up the result, often called an accumulator.
A recursive algorithm that uses only tail calls is called tail-recursive.
let rec sum ‘ partial_sum n =
if n = 0 then partial_sum else sum’ (partial_sum + n) (n – 1)
partial_sum is an accumulator.
Rewrite the following function to be tail-recursive.
let rec factorial (n : int) : int =
if n = 0 then 1 else n * factorial (n – 1)
Short break before moving on.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com