Discussion 10 (4/1)
¡ñ If you didn¡¯t have time to review lexing and parsing from last week, do that first! Let them ask questions as well
¡ñ Evaluation / Operational Semantics
¡ð Goal of operational semantics: to add meaning to whatever we just parsed, to
Copyright By PowCoder代写 加微信 powcoder
evaluate it
¡ð A basic operational semantic rule has 3 parts:
¡ö Expression ¡ö Hypothesis ¡ö Result
¡ð Example 2
¡ö For the second rule
¡ñ Input expression is e1 + e2
¡ñ Hypothesis is the stuff above the line (3 hypotheses here)
¡ñ Result is n3
¡ñ By these rules, given two expressions to add, we get n3 by the
hypotheses
¡ð Why do we need this? When we write programs, we need formal rules to show
¡ð To show that our program is following the rules, we can draw a tree that
evaluates the given expression
¡ð Example 2
¡ö Weareevaluating1+(2+3)=>6,sothatwillbeatthebottomofthetree
¡ö This maps to the second rule, so looking at the second rule, we see e1 =
1 and e2 = (2 + 3)
¡ö First, we evaluate e1 = 1 using the first rule (1 => 1)
¡ö To evaluate e2 = (2 + 3), we will need to use the second rule again to
break it down. For this second instance, e1 = 2 and e2 = 3.
¡ö Wecanevaluatee1=2ande2=3usingthefirstruleagain(2=>2,3=>
¡ö Wegettheresult,5,bysummingn1andn2(5is2+3),sothewhole
expression (2 + 3) evaluates to 5
¡ö We return to the original evaluation to get 6 is 1 + 5
¡ö Thus, the whole expression evaluates to 6!
¡ð This was a pretty simple example, but in the context of programming we also will
have an environment of variables we could draw from
¡ð This is usually represented by an uppercase A, followed by any variables stored
in the environment. We call this evaluating the expression under environment A
¡ð Example 4
¡ö The rule for let expressions starts with environment A for the first
hypothesis, but after processing the first hypothesis we see our
environment A now also contains x : v1
¡ö Now, if e2 needs information about x, we can reference v1 from the
environment
¡ð Keeping track of environments will be crucial for P4b, and will help in
understanding real programming environments
¡ð Example 4
¡ö WeareevaluatingA;lety=1inletx=2inx=>2,sothatisourinput expression
¡ö This matches to the rule for let expressions, so we start by evaluating e1 under A, e1 being 1
¡ö Note that A corresponds to whatever A we started with, so it could already have existing variables in it. We would have to keep those unless we explicitly have a rule that says otherwise
¡ö Now our environment contains y : 1, and we want to evaluate e2, which is the second let statement
¡ö We use the let expression rule again to evaluate e2, but this time the environment will contain y : 1 already
¡ö Now we will evaluate e2 for the second let expression, which is x
¡ö This time, we will need to use the updated environment to get the value of
x, which is 2
¡ö Thus, overall we evaluate the expression to 2
if we have two let statements that both declare x? Then, our environment would have two instance of x values. We would shadow by only using the most recent (rightmost) value of x
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com