计算机代考 COMP 302

Programming Languages and Paradigms COMP 302
Prof. Errington

School of Computer Science Mc

Copyright By PowCoder代写 加微信 powcoder

Fall 2022 – Week 2, lesson 1

Announcements
􏰇 Elections: 3 October. Classes cancelled. (No effect to us.) 􏰇 Advance polling available. (See #announcements.)

Last time…
􏰇 Basic syntax: let creates new definitions
􏰇 Functions are defined the same as other values, but they
have parameters.
􏰇 Call a function with a space: f a is f applied to a.
􏰇 Multiple arguments, use more spaces: f a b
􏰇 Surround an argument with parens if it is complicated: f (n – 1) is f applied to n – 1
Otherwise, f n – 1 is f n minus one.

Last time…
􏰇 Basic syntax: let creates new definitions
􏰇 Functions are defined the same as other values, but they
have parameters.
􏰇 Call a function with a space: f a is f applied to a.
􏰇 Multiple arguments, use more spaces: f a b
􏰇 Surround an argument with parens if it is complicated: f (n – 1) is f applied to n – 1
Otherwise, f n – 1 is f n minus one.
let rec fib n =
if n = 0 then 0 else if n = 1 then 1 else fib (n-1) + fib (n-2)
The rec keyword is necessary to make a definition recursive.

Figuring out the types
let rec fib n =
if n = 0 then 0 else if n = 1 then 1 else fib (n-1) + fib (n-2)
􏰇 How does OCaml know that n : int?
􏰇 How does OCaml know that fib n : int?
i.e. how does it know that the return type of fib is int? 􏰇 How do we write the type of the function fib?

This time…
􏰇 More on variables, functions, and scope. 􏰇 Performance implications of recursion. 􏰇 Defining new types.
􏰇 Working with user-defined types.

let, let … in …, and let rec

􏰇 let x = e1 in e2 is an expression (e1, e2 arbitrary)

􏰇 let x = e1 in e2 is an expression (e1, e2 arbitrary) 1. Evaluate e1 to a value v

􏰇 let x = e1 in e2 is an expression (e1, e2 arbitrary) 1. Evaluate e1 to a value v
2. Evaluate e2 with x bound to v
(Occurrences of x in e2 become replaced by v)

􏰇 let x = e1 in e2 is an expression (e1, e2 arbitrary) 1. Evaluate e1 to a value v
2. Evaluate e2 with x bound to v
(Occurrences of x in e2 become replaced by v)
3. The overall result of the let-expression is whatever e2
evaluates to.

􏰇 let x = e1 in e2 is an expression (e1, e2 arbitrary) 1. Evaluate e1 to a value v
2. Evaluate e2 with x bound to v
(Occurrences of x in e2 become replaced by v)
3. The overall result of the let-expression is whatever e2
evaluates to.
1. let x = 2 + 2 in x * x → let x = 4 in x * x

􏰇 let x = e1 in e2 is an expression (e1, e2 arbitrary) 1. Evaluate e1 to a value v
2. Evaluate e2 with x bound to v
(Occurrences of x in e2 become replaced by v)
3. The overall result of the let-expression is whatever e2
evaluates to.
1. let x = 2 + 2 in x * x → let x = 4 in x * x 2. Withxboundto4evaluatex * x→16

􏰇 let x = e1 in e2 is an expression (e1, e2 arbitrary) 1. Evaluate e1 to a value v
2. Evaluate e2 with x bound to v
(Occurrences of x in e2 become replaced by v)
3. The overall result of the let-expression is whatever e2
evaluates to.
1. let x = 2 + 2 in x * x → let x = 4 in x * x
2. Withxboundto4evaluatex * x→16
3. And that’s the overall result of the let-expression.

􏰇 let x = e1 in e2 is an expression (e1, e2 arbitrary) 1. Evaluate e1 to a value v
2. Evaluate e2 with x bound to v
(Occurrences of x in e2 become replaced by v)
3. The overall result of the let-expression is whatever e2
evaluates to.
1. let x = 2 + 2 in x * x → let x = 4 in x * x
2. Withxboundto4evaluatex * x→16
3. And that’s the overall result of the let-expression.
􏰇 Whatisthetypeoflet x = e1 in e2 ?

􏰇 let x = e1 in e2 is an expression (e1, e2 arbitrary) 1. Evaluate e1 to a value v
2. Evaluate e2 with x bound to v
(Occurrences of x in e2 become replaced by v)
3. The overall result of the let-expression is whatever e2
evaluates to.
1. let x = 2 + 2 in x * x → let x = 4 in x * x
2. Withxboundto4evaluatex * x→16
3. And that’s the overall result of the let-expression.
􏰇 Whatisthetypeoflet x = e1 in e2 ?
Hint: evaluating an expression does not change its type.

􏰇 let x = e1 in e2 is an expression (e1, e2 arbitrary) 1. Evaluate e1 to a value v
2. Evaluate e2 with x bound to v
(Occurrences of x in e2 become replaced by v)
3. The overall result of the let-expression is whatever e2
evaluates to.
1. let x = 2 + 2 in x * x → let x = 4 in x * x
2. Withxboundto4evaluatex * x→16
3. And that’s the overall result of the let-expression.
􏰇 Whatisthetypeoflet x = e1 in e2 ?
Solution: same as the type of e2
let n = 330 in “class has ” ^ string_of_int n ^ ” students” has type string because the part after in has type string.

􏰇 let x = e1 in e2 is an expression (e1, e2 arbitrary) 1. Evaluate e1 to a value v
2. Evaluate e2 with x bound to v
(Occurrences of x in e2 become replaced by v)
3. The overall result of the let-expression is whatever e2
evaluates to.
1. let x = 2 + 2 in x * x → let x = 4 in x * x
2. Withxboundto4evaluatex * x→16
3. And that’s the overall result of the let-expression.
􏰇 Whatisthetypeoflet x = e1 in e2 ?
􏰇 Top-level definitions, e.g. let rec fib n = …, lack an explicit in part; the rest of the file is the implied in part. Only works for top-level definitions.

Shadowing ̸= variable update!
􏰇 We can shadow bindings in OCaml.
let x = 5 in let x = 2 in x + x evaluates to 4
􏰇 This doesn’t change the value associated to the first binding of x!

Compare: Python vs OCaml scoping
def f(y): return x + y x=8
(* ocaml *)
let f y = x + y let x = 8
let a = f 10

Compare: Python vs OCaml scoping
def f(y): return x + y x=8
(* ocaml *)
let f y = x + y let x = 8
let a = f 10
What is the value of a after running the program? Discuss with the person beside you.

Compare: Python vs OCaml scoping
def f(y): return x + y x=8
(* ocaml *)
let f y = x + y let x = 8
let a = f 10
Python. The variable x is updated (line 4)

Compare: Python vs OCaml scoping
def f(y): return x + y x=8
(* ocaml *)
let f y = x + y let x = 8
let a = f 10
Python. The variable x is updated (line 4)
The function f uses the latest value of the variable. Python evaluates f(10) to 18.

Compare: Python vs OCaml scoping
def f(y): return x + y x=8
(* ocaml *)
let f y = x + y let x = 8
let a = f 10
Python. The variable x is updated (line 4)
The function f uses the latest value of the variable. Python evaluates f(10) to 18.
OCaml. The variable x is shadowed.

Compare: Python vs OCaml scoping
def f(y): return x + y x=8
(* ocaml *)
let f y = x + y let x = 8
let a = f 10
Python. The variable x is updated (line 4)
The function f uses the latest value of the variable. Python evaluates f(10) to 18.
OCaml. The variable x is shadowed.
The definition of f can only “see” the binding for x above it. The below binding is not in scope. OCaml evaluates f 10 to 15.

Compare: Python vs OCaml scoping
def f(y): return x + y x=8
(* ocaml *)
let f y = x + y let x = 8
let a = f 10
We can shadow a definition, e.g. for x, by making a new one with the same name. This does not affect any definitions that were using the old definition of x.

Short break before moving on.

Rewriting fibonacci
let rec fib n =
if n = 0 then 0 else if n = 1 then 1 else fib (n-1) + fib (n-2)
We can do better than exponential time. Let’s see how!

􏰇 let rec sqrt (i : int) (n : int) : int = …
Finds the greatest integer whose square is less than or equal to n.
Called as sqrt 0 n, i.e. i starts at 0.
􏰇 let rec is_prime (i : int) (n : int) : bool = …
Decides whether n is a prime number, i.e. not divisible by any number other than 1 or n.
Called as is_prime 2 n, i.e. i starts at 2.
Write n mod i to calculate the remainder of dividing n by i.

Exercises – solutions

Short break before moving on.

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 → initial 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 → initial call
2. if 5 = 0 then 0 else 5 + sum (5 – 1) → 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 → initial call
2. if 5 = 0 then 0 else 5 + sum (5 – 1) → subst. 5 into fn 3. if false 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 → initial call
2. if 5 = 0 then 0 else 5 + sum (5 – 1) → subst. 5 into fn 3. if false then 0 else 5 + sum (5 – 1) →evalcondition 4. 5 + sum 4 → eval else branch; 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 → initial call
2. if 5 = 0 then 0 else 5 + sum (5 – 1) → subst. 5 into fn 3. if false then 0 else 5 + sum (5 – 1) →evalcondition 4. 5 + sum 4 → eval else branch; 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 → initial call
2. if 5 = 0 then 0 else 5 + sum (5 – 1) → subst. 5 into fn 3. if false then 0 else 5 + sum (5 – 1) →evalcondition 4. 5 + sum 4 → eval else branch; 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 → initial call
2. if 5 = 0 then 0 else 5 + sum (5 – 1) → subst. 5 into fn 3. if false then 0 else 5 + sum (5 – 1) →evalcondition 4. 5 + sum 4 → eval else branch; 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 → initial call
2. if 5 = 0 then 0 else 5 + sum (5 – 1) → subst. 5 into fn 3. if false then 0 else 5 + sum (5 – 1) →evalcondition 4. 5 + sum 4 → eval else branch; 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))))→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 → initial call
2. if 5 = 0 then 0 else 5 + sum (5 – 1) → subst. 5 into fn 3. if false then 0 else 5 + sum (5 – 1) →evalcondition 4. 5 + sum 4 → eval else branch; 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))))→recursivecall
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 → initial call
2. if 5 = 0 then 0 else 5 + sum (5 – 1) → subst. 5 into fn 3. if false then 0 else 5 + sum (5 – 1) →evalcondition 4. 5 + sum 4 → eval else branch; 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))))→recursivecall
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 → initial call
2. if 5 = 0 then 0 else 5 + sum (5 – 1) → subst. 5 into fn 3. if false then 0 else 5 + sum (5 – 1) →evalcondition 4. 5 + sum 4 → eval else branch; 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))))→recursivecall
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 → initial call
2. if 5 = 0 then 0 else 5 + sum (5 – 1) → subst. 5 into fn 3. if false then 0 else 5 + sum (5 – 1) →evalcondition 4. 5 + sum 4 → eval else branch; 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))))→recursivecall
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 → initial call
2. if 5 = 0 then 0 else 5 + sum (5 – 1) → subst. 5 into fn 3. if false then 0 else 5 + sum (5 – 1) →evalcondition 4. 5 + sum 4 → eval else branch; 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))))→recursivecall
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 → initial call
2. if 5 = 0 then 0 else 5 + sum (5 – 1) → subst. 5 into fn 3. if false then 0 else 5 + sum (5 – 1) →evalcondition 4. 5 + sum 4 → eval else branch; 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))))→recursivecall
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
14. 15 → 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 tr

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com