6.S050 Problem Set 4: Control Flow

\[ \newcommand{\target}[2]{\class{mathjax-symbol mathjax-symbol-#1}{#2}} \newcommand{\type}[3]{#1 \target{type}{\vdash} #2 \target{type}{:} #3} \newcommand{\abs}[3]{\target{abs}{\lambda} #1 \target{abs}{:} #2\target{abs}{.} #3} \newcommand{\tabs}[2]{\target{tabs}{\Lambda} #1 \target{tabs}{.} #2} \newcommand{\arrow}{\target{arrowT}{\rightarrow}} \newcommand{\subt}{\target{subT}{<:}} \]

\[ \newcommand{\target}[2]{\class{mathjax-symbol mathjax-symbol-#1}{#2}} \newcommand{\evalStmt}[2]{\langle #1 \rangle \target{evalStmt}{\Downarrow} #2} \newcommand{\evalStmtB}[2]{\langle #1 \rangle \target{evalStmtB}{\Downarrow} \langle #2 \rangle} \newcommand{\evalArrowK}{\target{evalStmtK}{\rightarrow}} \newcommand{\evalStmtK}[2]{\langle #1 \rangle \evalArrowK \langle #2 \rangle} \newcommand{\evalExpr}[2]{\langle #1 \rangle \target{evalExpr}{\Downarrow_{e}} #2} \newcommand{\while}[2]{\mathtt{while}\ #1\ \mathtt{do}\ #2} \newcommand{\if}[3]{\mathtt{if}\ #1\ \mathtt{then}\ #2\ \mathtt{else}\ #3} \newcommand{\updateStore}[3]{#1\target{updateStore}{[}#2 \target{updateStore}{\mapsto} #3\target{updateStore}{]}} \newcommand{\kseqd}{\target{kseqd}{\cdot}} \newcommand{\kstop}{\target{kstop}{\mathsf{Kstop}}} \newcommand{\kwhile}{\target{kwhile}{\mathsf{Kwhile}}} \]

1. Problem set 3 peer feedback (20 points)

Respond to the following prompts about your peer's submission and post your response as a comment on Canvas. You can find your response to review on the right column of the Scoping Design Challenge assignment.

  1. Summarize the proposed modification to J.
  2. Does this change make the semantics of J simpler or more complex? Why?

2. Programming with Generators (30 points)

Using generators, extend the provided code to support the following patterns.

  1. Wildcards. A wildcard Any() should match any single character.
  2. Kleene star. A star pattern Star(p) should match zero or more repetitions of pattern p.
  3. Conjunction. A conjunction Both(p1, p2) should match only when both p1 and p2 match.

We have given you some tests. We will run your code on those tests as well as a hidden test suite.

Please modify the provided code and upload your modified file to Canvas.

3. Continuation Semantics (50 points)

In lecture, we extended IMP to include while loops with break and continue. We showed that using continuations makes the semantics for this kind of control flow construct easy to extend. In this problem, you'll be extending the semantics of IMP with three new control flow features.

For convenience, the continuation semantics of IMP with break are as follows:

Syntax:

\begin{alignat*}{2} s &::=\ \mathtt{skip} \\ &|\ s ; s \\ &|\ x := e \\ &|\ \mathtt{if}\ e\ \mathtt{then}\ s\ \mathtt{else}\ s \\ &|\ \mathtt{while}\ e\ \mathtt{do}\ s \\ &|\ \mathtt{break} \\ &|\ \mathtt{multibreak}\ n \\ &|\ \mathtt{try}\ s\ \mathtt{catch}\ x\ \mathtt{then}\ s \\ &|\ \mathtt{throw}\ x \\ &|\ \mathtt{resume} \end{alignat*}

We omit the syntax and semantics of expressions because it doesn't matter for this problem. Just use the expression evaluation relation if you need to deal with expressions.

Evaluation relation: \[\evalStmtK{\text{Continuation}, \text{Store}}{\text{Continuation}, \text{Store}}\] \[\evalExpr{\text{Expression}, \text{Store}}{\text{Value}}\]

Continuations: \[ k : \text{Continuation} ::= \kstop ~|~ \mathsf{Kseq}\ s\ k ~|~ \kwhile\ e\ s\ k. \] We also define a shorthand for writing \(\mathsf{Kseq}\): \[\mathsf{Kseq}\ s\ k = s \kseqd k.\]

Semantics:

\begin{gather} \tag{K-Seq} \evalStmtK{(s; s') \kseqd k, \sigma}{s \kseqd s' \kseqd k, \sigma} \\[2ex] \tag{K-Assign} \frac{ \evalExpr{e, \sigma}{v} } { \evalStmtK{(x := e) \kseqd k, \sigma}{k, \updateStore{\sigma}{x}{v}} } \\[2ex] \tag{K-If-true} \frac{ \evalExpr{e, \sigma}{\mathtt{true}} } { \evalStmtK{(\if{e}{s}{s'}) \kseqd k, \sigma}{s \kseqd k, \sigma} }\\[2ex] \tag{K-If-false} \frac{ \evalExpr{e, \sigma}{\mathtt{false}} } { \evalStmtK{(\if{e}{s}{s'}) \kseqd k, \sigma}{s' \kseqd k, \sigma} } \\[2ex] \tag{K-Skip} \evalStmtK{\mathtt{skip} \kseqd k, \sigma}{k, \sigma} \\[2ex] \tag{K-While-1} \evalStmtK{\while{e}{s} \kseqd k, \sigma}{\kwhile\ e\ s\ k, \sigma} \\[2ex] \tag{K-While-2} \frac{ \evalExpr{e, \sigma}{\mathtt{true}} } { \evalStmtK{\kwhile\ e\ s\ k, \sigma}{s \kseqd \kwhile\ e\ s\ k, \sigma} } \\[2ex] \tag{K-While-3} \frac{ \evalExpr{e, \sigma}{\mathtt{false}} } { \evalStmtK{\kwhile\ e\ s\ k, \sigma}{k, \sigma} } \\[2ex] \tag{K-Break} \evalStmtK{\mathtt{break} \kseqd s_1 \dots s_j \kseqd \kwhile\ e\ s\ k, \sigma}{k, \sigma} \end{gather}

The initial state of a program \(p\) is \(\langle p \kseqd \kstop, \emptyset \rangle\), and final states are of the form \(\langle \kstop, \sigma \rangle\).

3.1. Multi-level break

Extend IMP with a new "multi-level" break construct. Written \(\mathtt{multibreak}\ n\), this multi-level break will break out of the \(n\) most enclosing loops. If there are fewer than \(n\) enclosing loops, it will break out of all of them. Give rules for the semantics of multi-level break. You should not need to extend the grammar of continuations.

3.2. Exceptions

Extend IMP with exceptions. We'll add two new kinds of statement: try-catch and throw. Try-catch is written \(\mathtt{try}\ s\ \mathtt{catch}\ x\ \mathtt{then}\ s\). Throw is written \(\mathtt{throw}\ x\). \(x\) is the name of the exception. (Exceptions aren't variables; they're a new kind of named entity.)

The semantics of try-catch and throw are fairly standard. When \(\mathtt{throw}\ x\) is executed, control jumps to the then clause of most enclosing try-catch for exception \(x\). If there is no enclosing try-catch, execution terminates.

Give rules for the semantics of try-catch and throw. You will need to extend the grammar of continuations. Give a new grammar of continuations or explain how you intend to extend it.

3.3. Resumable exceptions

Extend your semantics of exceptions with a \(\mathtt{resume}\) statement. When \(\mathtt{resume}\) is executed inside the then clause of a try-catch, control resumes immediately after the \(\mathtt{throw}\ x\) that raised the exception.

Give rules for the semantics of resume. You will likely need to modify your rules for try-catch and throw from the previous problem. You will also need to modify or extend the continuation grammar from the previous problem.

Last updated: 2023-04-11 Tue 13:10