HW 3 Language Syntax, Semantics, Runtime Errors

CS 536: Science of Programming  HW 3
Language Syntax, Semantics, Runtime Errors
CS 536: Science of Programming

2022-09-21, 14:59: Restored problems 4 – 6. 2022-09-22, 14:37 Typo in #6
Problems [60 points]
Class 5: Language Syntax/Operational Semantics
1. [12 = 4 * 3 points] Translate the program below into our programming language.
a. m = x = 0; y = 1; while (m++ < n) { ++x; y *= x ; }
b. m = n; x = z = 1; while (––m < n) { x++; x += z ; }
c. m = n; v = x = 1; while (––m < n) { x++; v += x ; }
d. m = n; p = y = 1; while (––m < n) { ++p; p += y ; p++; p += z; }
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.
2. [12 = 3 * 4 points] Let S ≡ if x > 0 then x := x*z else if y > 0 then y := y*z f f.
a. Evaluate ⟨S, {x = 3, y = 5, z = 9}⟩ to completion.
b. Evaluate ⟨S, {x = –2, y = 4, z = 3}⟩ to completion.
c. Evaluate ⟨S, {x = –5, y = –2, z = –2}⟩ to completion.
3. [9 points] Let W ≡ while m ≠ n do S od where S ≡ m := m+1; x := x+m*m. Let σ₀ = {m = 0, x = 1,
n = 4}. Evaluate ⟨W, σ₀⟩ 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).
Class 6: Denotational Semantics, Runtime Errs [2022-09-21 restored]
4. [9 = 3 * 3 points] As in problem 2, let IF ≡ if x > 0 then x := x*z else if y > 0 then y := y*z f f.
a. What is M(IF, {x = 3, y = 5, z = 9}) ?
b. What is M(IF, {x = –2, y = 4, z = 3}) ?
c. What is M(IF, {x = –5, y = –2, z = –2}) ?
CS Dept., Illinois Institute of Technology – 1 – © James Sasaki, 2022
CS 536: Science of Programming Thu 2022-09-22, 14:38 HW 3: Classes 5 - 6
5. [10 points] As in Problem 3, let S ≡ m := m+1; x := x+m*m and let W ≡ while m ≠ n do S od.
a. [3 points] Let τ be an arbitrary state for S. What is M(S, τ) ? (You answer will be symbolic.)
b. [3 points] Let σ₀ = {m = 0, x = 0}. What values of β ∈ Z make M(W, σ0[n ↦ β]) = ⊥d?
c. [4 points] For the other values of β, write a simple description of the value of δ in
M(W, σ₀[n ↦ β]) = {{m = β, x = δ, n = β}}
Something at the level of “δ is the sum of all the odd integers between 1 and β” is fine.
(Except that it's a wrong answer, of course.)
6. [8 points] Let S ≡ x := b[m+1] / sqrt(k) and let σ = {m = α, k = β, b = γ}. Let δ be the length of b, so
[2022-09-22] γ(0), …, γ(δ-1) are the values of b[0], b[1], ... in σ. Describe the set of all σ that
cause M(S, σ) = {⊥e}. Recall dividing by zero and taking square roots of negative numbers cause
errors.
CS Dept., Illinois Institute of Technology – 2 – © James Sasaki, 2022