CS 536: Science of Programming - HW 3: Syntax, Operational Semantics, Denotational Semantics, Runtime Errors

Language Syntax, Semantics, Runtime Errors CourseNana.COM

CS 536: Science of Programming, Spring 2023 Due Thu Feb 9, 11:59 pm CourseNana.COM

Problems [60 points]
Class 5: Language Syntax/Operational Semantics CourseNana.COM

1. [12 = 2 * 6 points] Translate the program below into our programming language.
a. m=x=0;y=1;while(m++<n){y=++x;y*=x;};m=m*m b. m=n;p=y=1;while(––m<n){p=p*(y++);} CourseNana.COM

For Problems 2 and 3, write out the operational semantics as a directed graph. With 〈 S , σ〉 →
〈 S′ , σ 〉 , the two configurations become nodes and the semantics → becomes a graph → .. For these problems, it's okay to draw your answers on paper and scan it in to be part of your pdf. If the same configuration occurs more than once, don't write it out as two separate nodes; make it just one node. CourseNana.COM

2. [10=2*5 points] Let S ≡ if x>0 then x:=x*z fi; y:=y*z
Evaluate 〈S, {x=–5, y=–2, z=–2}〉 to completion. [Hint: remember to expand the if-then] CourseNana.COM

3. [8points] LetW ≡whilem≠n doSodwhereS ism:=m+1; x:=x+m*m. Letσ0= {m=0, x=1, n=4. Evaluate 〈W,σ0〉 to completion. Show all configurations of the form 〈W, state〉 and the final 〈 E , state 〉 . You can use → n to skip other configurations if you like, or you can show them (your choice). CourseNana.COM

Class 6: Denotational Semantics, Runtime Errs CourseNana.COM

4. [12=2*6 points] As in Problem 2, let IF be if x>0 then x:=x*z fi fi; y:=y*z. For both parts below, write your answer as a succession of M ( ... ) steps. (See Example 1 in the Class 6 notes). CourseNana.COM

1. What is M(IF, {x=3, y=5, z=9}) ?
2. What is M(IF, {x=0, y=2, z=8}) ?

5.  [14pointstotal] LetW ≡whilem≠n doSodwhereS ism:=m+1; x:=x*x.
1. [3 points] Let τ(m)=α and τ(x)=β. Calculate M(S,τ).
2. [3points] Letσ0={m=0,x=2,n=δ}. WhatvaluesofδmakeM(W,σ0)=⊥d? Briefly

explain. CourseNana.COM

3. [8 points] Consider the σ0 where δ isn't one of the ones in part b. That is, M(W,σ0)=τ for

someτ≠⊥. Giveasimpledescriptionoftheτ(x)values—somethingatthelevelof“τ(x) is the sum of the even integers ≥ 0 and < δ ” (Except that that's a wrong answer.) CourseNana.COM

6. [4points] LetS ≡ x:=b[m+1] / sqrt(k) andletσ={m=α,k=β,b=δ}. Letηbethelength of b, so β(0), ..., β(η-1) are the values of b[0], b[1], ... in σ. Describe the set of all σ that makeM(S,σ) ={⊥e}.

  CourseNana.COM