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