P4b: Grammar for MicroCaml AST
Expressions e::=v|x|ebope|note
| let [rec]? x = e in e
It’s just decoration, but it comes from the lambda calculus, which we will discuss in a few weeks
Copyright By PowCoder代写 加微信 powcoder
Mutop directives
v::=n|s|true|false|(A,λx.e) bop::=+|-|>|<|>=|<=|=| !=|^|&&|||
d ::= def x = e;; | e;;
CMSC 330 Spring 2021
| if e then e else e | e e | fun x -> e
Expressions: Values, Not, Variables, Ifs
A;note⇒false
A;note⇒true
A;e1⇒v1 A,x:v1;e2⇒v2
A;letx=e1ine2 ⇒v2
Doesn’t cover recursion – will discuss later
A;e1⇒true A;e2⇒v
A;ife1thene2elsee3 ⇒v
A;e1⇒false A;e3⇒v
A;ife1thene2elsee3 ⇒v
CMSC 330 Spring 2021 2
Expressions: Binops
A;e1⇒v1 A;e2⇒v2 v3isv1bopv2
A;e1bope2⇒v3
• Arithmetic bop operators +, -, /, * work on ints Ø as do relational operators <, >, …
• Operators =, != require both arguments to have the same type
Ø … but only for ints, booleans, strings
Ø Not supported on closures (A’,λx.e). Non-support makes logical sense,
but also prevents implementation problems involving infinite loops, due to the use of references, shown later.
• Logical operators &&, || work on booleans only • Concatenation ^ works on strings only
CMSC 330 Spring 2021 3
Expressions: Closures
A; fun x -> e ⇒ (A,λx.e)
A;e1⇒(A’,λx.e) A;e2⇒v1 A’,x:v1;e ⇒v
A; e1 e2 ⇒ v
Implements lexical/static scoping
• Captures the environment when closure is created; uses that (and nothing else) when called
CMSC 330 Spring 2021 4
Mutop Directives (no rec)
A;def x = e;; ⇒ A,x:v;v
Doesn’t cover recursion – we explain in 2 slides
A;e;;⇒ A;v
Judgment A; d ⇒ A’ ; vopt
• Returns updated environment, optional value
No value to return
CMSC 330 Spring 2021 5
Let rec: Recursion
A; e1 ⇒ (A’,λx.e)
v1 = (A’{v1/x},λx.e) A,x:v1; e2 ⇒ v2
A; let rec x = e1 in e2 ⇒ v2
We evaluate e1 to a closure
• If it’s not a closure, it’s the same as non-recursive let
The second premise defines v1 via a recursive equation • v1 appears on the left and right-hand side of the =
The solution is a fixed point: every occurrence of x in A’ is v1, which can internally refer to itself
CMSC 330 Spring 2021 6
Implementing Recursion via References
r = newref(0) A,x:r; e1 ⇒ v1 update(r,v1) A,x:r; e2 ⇒ v2
A; let rec x = e1 in e2 ⇒ v2
We can implement the fixed point with OCaml references
• Create a reference placeholder for x (use int 0 as a dummy val) • Extend A with that placeholder, and evaluate e1
• Update the placeholder to the resulting value v1 Once we do this, we can evaluate e2
We do something similar for recursive defs
CMSC 330 Spring 2021 7
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com