Programming Languages & Compilers
8/25/22 2
I
New
Programming
Paradigm
II
Language
Translation
III
Language
Semantics
Three Main Topics of the Course
Programming Languages & Compilers
8/25/22 3
I
New
Programming
Paradigm
II
Language
Translation
III
Language
Semantics
Order of Evaluation
Specification to Implementation
Programming Languages & Compilers
8/25/22 4
Functional
Programming
Environments
and
Closures
Continuation
Passing
Style
Patterns of
Recursion
I : New Programming Paradigm
Programming Languages & Compilers
8/25/22 5
Functional
Programming
Environments
and
Closures
Continuation
Passing
Style
Patterns of
Recursion
Order of Evaluation
Specification to Implementation
Programming Languages & Compilers
8/25/22 6
Lexing and
Parsing
Type
Systems
Interpretation
II : Language Translation
Programming Languages & Compilers
8/25/22 7
Lexing and
Parsing
Type
Systems
Interpretation
Order of Evaluation
Specification to Implementation
Programming Languages & Compilers
8/25/22 8
Operational
Semantics
Lambda
Calculus
Axiomatic
Semantics
III : Language Semantics
Programming Languages & Compilers
8/25/22 9
Operational
Semantics
Lambda
Calculus
Axiomatic
Semantics
CS422
CS426
CS477
Order of Evaluation
Specification to Implementation
Course TAs
8/26/22 11
John LeePaul Krogmeier
Haoqing Zhu
Dan Plyukhin
Luhao Wang
8/25/22 12
Course Website
n https://courses.engr.illinois.edu/cs421/fa2022
n Main page - summary of news items
n Policy - rules governing course
n Lectures - syllabus and slides
n MPs - information about assignments
n Exams
n Unit Projects - for 4 credit students
n Resources - tools and helpful info
n FAQ
Some Course References
n No required textbook
n Some suggested references
8/25/22 13
8/25/22 14
Some Course References
n No required textbook.
n Pictures of the books on previous slide
n Essentials of Programming Languages (2nd Edition)
by Daniel P. Friedman, Mitchell Wand and
Christopher T. Haynes, MIT Press 2001.
n Compilers: Principles, Techniques, and Tools, (also
known as "The Dragon Book"); by Aho, Sethi, and
Ullman. Published by Addison-Wesley. ISBN: 0-
201-10088-6.
n Modern Compiler Implementation in ML by Andrew
W. Appel, Cambridge University Press 1998
n Additional ones for Ocaml given separately
8/25/22 15
Course Grading
n Assignments 10%
n Web Assignments (WA) (~5%)
n MPs (in Ocaml) (5~%)
n All WAs and MPs Submitted by PrairieLearn
n Late submission penalty: 20% to total
8/26/22 16
Course Grading
n 2 Midterms - 25% each
n Sep 29, Nov 10
n BE AVAILABLE FOR THESE DATES!
n Final 40%
n Fall back: 7:00pm-10:00pm., Tuesday Dec.
13
n Percentages are approximate
8/25/22 17
Course Assingments – WA & MP
n You may discuss assignments and their solutions with
others
n You may work in groups, but you must list members
with whom you worked if you share solutions or
solution outlines
n Each student must write up and turn in their
own solution separately
n You may look at examples from class and other similar
examples from any source – cite appropriately
n Note: University policy on plagiarism still holds - cite
your sources if you are not the sole author of your
solution
n Do not have to cite course notes or me
8/25/22 20
References for OCaml
n Supplemental texts (not required):
n The Objective Caml system release 4.05, by
Xavier Leroy, online manual
n Introduction to the Objective Caml
Programming Language, by Jason Hickey
n Developing Applications With Objective
Caml, by Emmanuel Chailloux, Pascal
Manoury, and Bruno Pagano, on O’Reilly
n Available online from course resources
8/25/22 23
Why learn OCAML?
n Many features not clearly in languages you have
already learned
n Assumed basis for much research in programming
language research
n OCAML is particularly efficient for programming tasks
involving languages (eg parsing, compilers, user
interfaces)
n Industrially Relevant:
n Jane Street trades billions of dollars per day using OCaml
programs
n Major language supported at Bloomberg
n Similar languages: Microsoft F#, SML, Haskell, Scala
8/25/22 24
Session in OCAML
% ocaml
Objective Caml version 4.07.1
# (* Read-eval-print loop; expressions and
declarations *)
2 + 3;; (* Expression *)
- : int = 5
# 3 < 2;;
- : bool = false
8/25/22 25
No Overloading for Basic Arithmetic Operations
# 15 * 2;;
- : int = 30
# 1.35 + 0.23;; (* Wrong type of addition *)
Characters 0-4:
1.35 + 0.23;; (* Wrong type of addition *)
^^^^
Error: This expression has type float but an
expression was expected of type
int
# 1.35 +. 0.23;;
- : float = 1.58
No Implicit Coercion
# 1.0 * 2;; (* No Implicit Coercion *)
Characters 0-3:
1.0 * 2;; (* No Implicit Coercion *)
^^^
Error: This expression has type float but an
expression was expected of type
int
8/25/22 26
8/25/22 27
Sequencing Expressions
# "Hi there";; (* has type string *)
- : string = "Hi there"
# print_string "Hello world\n";; (* has type unit *)
Hello world
- : unit = ()
# (print_string "Bye\n"; 25);; (* Sequence of exp *)
Bye
- : int = 25
Declarations; Sequencing of Declarations
# let x = 2 + 3;; (* declaration *)
val x : int = 5
# let test = 3 < 2;;
val test : bool = false
# let a = 1 let b = a + 4;; (* Sequence of dec
*)
val a : int = 1
val b : int = 5
8/25/22 28
8/25/22 29
Booleans (aka Truth Values)
# true;;
- : bool = true
# false;;
- : bool = false
// r
7
= {c ® 4, test ® 3.7, a ® 1, b ® 5}
# if b > a then 25 else 0;;
- : int = 25
8/25/22 30
Booleans and Short-Circuit Evaluation
# 3 > 1 && 4 > 6;;
- : bool = false
# 3 > 1 || 4 > 6;;
- : bool = true
# (print_string "Hi\n"; 3 > 1) || 4 > 6;;
Hi
- : bool = true
# 3 > 1 || (print_string "Bye\n"; 4 > 6);;
- : bool = true
# not (4 > 6);;
- : bool = true
8/25/22 31
Functions
# let plus_two n = n + 2;;
val plus_two : int -> int = <fun>
# plus_two 17;;
- : int = 19
8/25/22 32
Functions
let plus_two n = n + 2;;
plus_two 17;;
- : int = 19
8/25/22 33
Nameless Functions (aka Lambda Terms)
fun n -> n + 2;;
(fun n -> n + 2) 17;;
- : int = 19
8/25/22 34
Functions
# let plus_two n = n + 2;;
val plus_two : int -> int = <fun>
# plus_two 17;;
- : int = 19
# let plus_two = fun n -> n + 2;;
val plus_two : int -> int = <fun>
# plus_two 14;;
- : int = 16
First definition syntactic sugar for second
8/25/22 35
Functions with more than one argument
# let add_three x y z = x + y + z;;
val add_three : int -> int -> int -> int = <fun>
# let t = add_three 6 3 2;;
val t : int = 11
# let add_three =
fun x -> (fun y -> (fun z -> x + y + z));;
val add_three : int -> int -> int -> int = <fun>
Again, first syntactic sugar for second
8/25/22 36
Using a nameless function
# (fun x -> x * 3) 5;; (* An application *)
- : int = 15
# ((fun y -> y +. 2.0), (fun z -> z * 3));;
(* As data *)
- : (float -> float) * (int -> int) = (<fun>,
<fun>)
Note: in fun v -> exp(v), scope of variable is
only the body exp(v)
8/25/22 37
Environments
n
Environments
record what value is associated with
a given identifier
n Central to the semantics and implementation of a
language
n Notation
r = {name
1
® value
1
, name
2
® value
2
, …}
Using set notation, but describes a partial function
n Often stored as list, or stack
n To find value start from left and take first match
Environments
8/25/22 38
X è 3
y è 17
name è “Steve”
b è true
region è (5.4, 3.7)
id è {Name = “Paul”,
Age = 23,
SSN = 999888777}
. . .
8/25/22 39
Global Variable Creation
# 2 + 3;; (* Expression *)
// doesn’t affect the environment
# let test = 3 < 2;; (* Declaration *)
val test : bool = false
// r
1
= {test ® false}
# let a = 1 let b = a + 4;; (* Seq of dec *)
// r
2
= {b ® 5, a ® 1, test ® false}
Environments
8/25/22 40
b è 5
test è true
a è 1
New Bindings Hide Old
// r
2
= {b ® 5, a ® 1, test ® false}
let test = 3.7;;
n What is the environment after this
declaration?
8/25/22 41
New Bindings Hide Old
// r
2
= {b ® 5, a ® 1, test ® false}
let test = 3.7;;
n What is the environment after this
declaration?
// r
3
= {test ® 3.7, a ® 1, b ® 5}
8/25/22 42
Environments
8/25/22 43
b è 5
test è 3.7
a è 1
Now it’s your turn
You should be able to do WA1-IC
Problem 1 , parts (* 1 *) - (* 3 *)
8/25/22 44
8/25/22 45
Local Variable Creation
// r
3
= {test ® 3.7, a ® 1, b ® 5}
# let b = 5 * 4
// r
4
= {b ® 20, test ® 3.7, a ® 1}
in 2 * b;;
- : int = 40
// r
5
= r
3
= {test ® 3.7, a ® 1, b ® 5}
# b;;
- : int = 5
b è 5
test è 3.7
a è 1
b è 5
test è 3.7
a è 1
b è 20
b è 5
test è 3.7
a è 1
// r
5
=r
3
={test ® 3.7, a ® 1, b ® 5}
# let c =
let b = a + a
// r
6
= {b ® 2} + r
3
// ={b ® 2, test ® 3.7, a ® 1}
in b * b;;
val c : int = 4
// r
7
= {c ® 4, test ® 3.7, a ® 1, b ® 5}
# b;;
- : int = 5
8/25/22 46
Local let binding
b è 5
test è 3.7
a è 1
// r
5
=r
3
={test ® 3.7, a ® 1, b ® 5}
# let c =
let b = a + a
// r
6
= {b ® 2} + r
3
// ={b ® 2, test ® 3.7, a ® 1}
in b * b;;
val c : int = 4
// r
7
= {c ® 4, test ® 3.7, a ® 1, b ® 5}
# b;;
- : int = 5
b è 5
test è 3.7
a è 1
8/25/22 47
Local let binding
b è 5
test è 3.7
a è 1
b è 2
// r
5
=r
3
={test ® 3.7, a ® 1, b ® 5}
# let c =
let b = a + a
// r
6
= {b ® 2} + r
3
// ={b ® 2, test ® 3.7, a ® 1}
in b * b;;
val c : int = 4
// r
7
= {c ® 4, test ® 3.7, a ® 1, b ® 5}
# b;;
- : int = 5
b è 5
test è 3.7
a è 1
8/25/22 48
Local let binding
b è 5
test è 3.7
a è 1
b è 2
b è 5
test è 3.7
a è 1
c è 4
8/25/22 49
Values fixed at declaration time
# let x = 12;;
val x : int = 12
# let plus_x y = y + x;;
val plus_x : int -> int = <fun>
# plus_x 3;;
What is the result?
X è 12
…
8/25/22 50
Values fixed at declaration time
# let x = 12;;
val x : int = 12
# let plus_x y = y + x;;
val plus_x : int -> int = <fun>
# plus_x 3;;
- : int = 15
8/25/22 51
Values fixed at declaration time
# let x = 7;; (* New declaration, not an
update *)
val x : int = 7
# plus_x 3;;
What is the result this time?
8/25/22 52
Values fixed at declaration time
# let x = 7;; (* New declaration, not an
update *)
val x : int = 7
# plus_x 3;;
What is the result this time?
X è 12
…
X è 7
…
8/25/22 53
Values fixed at declaration time
# let x = 7;; (* New declaration, not an
update *)
val x : int = 7
# plus_x 3;;
- : int = 15
8/25/22 54
Question
n Observation: Functions are first-class values
n Question: What value does the environment
record for a function variable?
n Answer: a closure
8/25/22 55
Save the Environment!
n A
closure
is a pair of an environment and an
association of a sequence of variables (the
input variables) with an expression (the
function body), written:
f ® < (v1,…,vn) ® exp, r
f
>
n Where r
f
is the environment in effect when f
is defined (if f is a simple function)
8/25/22 56
Closure for plus_x
n When plus_x was defined, had environment:
r
plus_x =
{…, x ® 12, …}
n Recall: let plus_x y = y + x
is really let plus_x = fun y -> y + x
n Closure for fun y -> y + x:
<y ® y + x, r
plus_x
>
n Environment just after plus_x defined:
{plus_x ® <y ® y + x, r
plus_x
>} + r
plus_x
Now it’s your turn
You should be able to do WA1-IC
Problem 1 , parts (* 4 *) - (* 7 *)
8/25/22 57
