This assignment is a review exercise in preparation for a subsequent assessment activity.
This is a peer-quizzing activity with two students. Each section has an even number of exercises. Student A quizzes Student B on the odd numbered exercises, and Student B quizzes Student A on the even numbered exercises.
To the best of your ability, give feedback using the learning-levels rubric below on where your peer is in reaching or exceeding Proficient (P) on each question live. Guidance of what a Proficient (P) answer looks like are given.
There may or may not be a member of the course staff assigned to your slot. It is expected that regardless of whether a member of the course staff is present, this is a peer-quizzing activity. If a member of the course staff is present, you may ask for their help and guidance on answering the questions and/or their assessment of where you are at in your learning level.
It is not expected that you can complete all exercises in the allotted time. You and your partner may pick and choose which sections you want to focus on and use the remaining questions as a study guide. You and your partner may, of course, continue working together after the scheduled session.
At the same time, most questions can be answered in a few minutes with a Proficient (P) level of understanding. Aim for 3–4 sections in 30 minutes.
Your submission for this session is an overall assessment of where your partner is in their reaching-or-exceeding-proficiency level. Be constructive and honest. Neither your nor your partners grade will depend on your learning-level assessment. Instead, your score for this assignment will be based on the thoughtfulness of your feedback to your partner.
Submit on Gradescope as a pair. That is, use Gradescope’s group assignment feature to submit as a group. The submission form has a spot for each of you to provide your assessment and feedback for each other.
Please proactively fill slots with an existing sign-up to have a partner. In case your peer does not show up to the slot, try to join another slot happening at the same time from the course calendar. If that fails and a course staff member is present, you may do the exercise with the staff member and get credit. If there is no staff member present, you may try to find a slot at a later time if you like or else write to the Course Manager on Piazza timestamped during the slot.
Exercise 35.1 Consider the small-step reduction judgment form with memory
\[ \langle e, m \rangle \longrightarrow \langle e', m' \rangle \]
What is \(m\) and why do we need it? Why does having \(m\) indicate that the expression \(e\) language have imperative features?
A Proficient (P) answer will state that \(m\) is memory for some imperative expressions that mutate state. Having a separate state is an indication of imperative expressions because evaluation cannot be expressed only by transforming expressions.
Exercise 35.2 Why isn’t this the rule for \(\TirName{DoAssignVar}\):
\[ \inferrule[DoAssignVar]{}{ \langle x \mathrel{\texttt{=}}v, m \rangle \longrightarrow \langle v, m[x \mapsto v] \rangle } \]
An Approaching (A) answer says that the form of memory \(m\) does not map variables to values but instead maps addresses to values.
A Proficient (P) answer adds that addresses enable us to give unique names to each variable allocation, avoiding an issue that resembles dynamic scoping.
An Exceeding (E) answer might note that a memory mapping variables to values could be sufficient for a simple imperative language with a fixed, static set of distinctly named global variables (i.e., cannot have procedures).
Let us consider describing and implementing dynamically-allocated mutable arrays, a language feature similar to mutable objects. Mutable arrays allow for reading from and assigning to numeric indexes:
const a = [];
a[0] = 0;
a[1] = a[0] + 1;Hint: For all the exercises in this section, use the formalization and implementation of dynamically-allocated mutable objects (Section 33.3) as your guide.
We consider the following abstract syntax for mutable arrays:
\[ \begin{array}{rrrl} \text{types} & \tau& \mathrel{::=}& \tau_1\texttt{[}\texttt{]} \\ \text{expressions} & e& \mathrel{::=}& \texttt{[}\, \overline{e} \,\texttt{]} \mid e_1\texttt{[}e_2\texttt{]} \mid e_1 \mathrel{\texttt{=}}e_2 \end{array} \]
The value of an array-creation expression \(\texttt{[}\, \overline{e} \,\texttt{]}\) is the address \(a\) at which the array is stored in memory. The array-indexing expression \(e_1\texttt{[}e_2\texttt{]}\) indexes into an array given by \(e_1\) with a numeric index given by \(e_2\). Let us make arrays 0-indexed. We assume there is an assignment expression and allow on the left-hand side of assignment to write to a given index of an array \(e_1\texttt{[}e_2\texttt{]} \mathrel{\texttt{=}}e_3\).
Exercise 35.3 Give the inference rule that extends the value judgment form \(e\;\mathsf{value}\) to specify that an address \(a\) is a value.
A Proficient (P) answer gives \[ \inferrule[AddrValue]{}{ a\;\mathsf{value} } \]
An Exceeding (E) answer may also discuss that addresses as values are pointers. This rule may already be given from dynamically-allocated mutable objects.
An Exceeding (E) answer may also note that we often abbreviate this judgment form using a grammar for the meta-variable for values \(v\) since it is a unary relation.
Exercise 35.4 Give the inference rule that extends the location judgment form \(e\;\mathsf{location}\) that specifies an array-index memory location (i.e., an array-index l-value).
A Proficient (P) answer gives \[ \inferrule[ArrayIndexLocation]{}{ a\texttt{[}n\texttt{]} \;\mathsf{location} } \] where \(n\) is a number.
An Exceeding (E) answer may discuss if we should somehow restrict indexes to be natural numbers.
Exercise 35.5 Give a definition for memory \(m\) to represent dynamically-allocated mutable arrays.
A Proficient (P) definition is something like: \[ \begin{array}{rrrl} \text{memories} & m& \mathrel{::=}& \cdot \mid m[a \mapsto \texttt{[}\, \overline{ v} \,\texttt{]} ] \end{array} \]
Exercise 35.6 Consider the small-step operational semantics judgment form with memory \( \langle e, m \rangle \longrightarrow \langle e', m' \rangle \). Give inference rules that define reducing the array-creation expression \(\texttt{[}\,\overline{e}\,\texttt{]}\), the array-indexing expression \(e_1\texttt{[}e_2\texttt{]}\), and the array-index assignment expression \( e_1\texttt{[}e_2\texttt{]} \mathrel{\texttt{=}} e_3\). Use left-to-right evaluation.
A Proficient (P) answer will give a \(\TirName{Do}\) rule for each construct (e.g., \(\TirName{DoArray}\), \(\TirName{DoArrayIndex}\), \(\TirName{DoAssignArrayIndex}\)), as well as \(\TirName{Search}\) rules that enforce a left-to-right evaluation. For example,
\(\inferrule[SearchArrayIndex1]{ \langle e_1, m \rangle \longrightarrow \langle e_1', m' \rangle }{ \langle e_1\texttt{[}e_2\texttt{]} , m \rangle \longrightarrow \langle e_1'\texttt{[}e_2\texttt{]} , m' \rangle }\)
\(\inferrule[SearchArrayIndex2]{ \langle e_2, m \rangle \longrightarrow \langle e_2', m' \rangle }{ \langle a_1\texttt{[}e_2\texttt{]} , m \rangle \longrightarrow \langle a_1\texttt{[}e_2'\texttt{]} , m' \rangle }\)
An Exceeding (E) answer may state the rules generically for the assignment expression \(e_1 \mathrel{\texttt{=}}e_2\) or explain how the generic search rules for assignment from before are already sufficient given the extended definition of \(e\;\mathsf{location}\) with rule \(\TirName{ArrayIndexLocation}\).
An Exceeding (E) answer may also ponder whether arrays should be dynamically-extensible or fixed-sized. If they are dynamically-extensible, such an answer might consider what should uninitialized indices contain. If they are fixed-sized, such an answer might consider what happens with out-of-bounds accesses. In case you are curious, JavaScript has dynamically-extensible arrays where uninitialized indices contain the \(\mathbf{undefined}\) value.
We represent the abstract syntax for arrays in Scala as follows:
trait Typ
case class TArray(t1: Typ) extends Typ // t ::= t1[ ]
trait Expr
case class Array(es: List[Expr]) extends Expr // e ::= [ es ]
case class Index(e1: Expr, e2: Expr) extends Expr // e ::= e1[e2]
case class Assign(e1: Expr, e2: Expr) extends Expr // e ::= e1 = e2
case class A(a: Int) extends Expr // e ::= adefined trait Typ defined class TArray defined trait Expr defined class Array defined class Index defined class Assign defined class A
Assume appropriate definitions of isValue, isLValue, DoWith, and Mem:
def isValue(e: Expr): Boolean = ???
def isLValue(e: Expr): Boolean = ???
sealed class DoWith[S, +A] private (doer: S => (S, A)) {
def map[B](f: A => B): DoWith[S, B] = new DoWith[S, B]({ (s: S) => { val (s_, a) = doer(s); (s_, f(a)) } })
def flatMap[B](f: A => DoWith[S, B]): DoWith[S, B] = new DoWith[S, B]({ (s: S) => { val (s_, a) = doer(s); f(a)(s_) } })
def apply(s: S): (S, A) = doer(s)
}
object DoWith {
def doget[S]: DoWith[S, S] = new DoWith[S, S]({ s => (s, s) })
def doput[S](s: S): DoWith[S, Unit] = new DoWith[S, Unit]({ _ => (s, ()) })
def doreturn[S, A](a: A): DoWith[S, A] = new DoWith[S, A]({ s => (s, a) })
def domodify[S](f: S => S): DoWith[S, Unit] = new DoWith[S, Unit]({ s => (f(s), ()) })
}
import DoWith._
sealed class Mem private (m: Map[A, Expr], nextAddr: Int) {
def apply(a: A): Expr = m(a)
def +(av: (A, Expr)): Mem = { val (a, _) = av; require(m.contains(a)); new Mem(m + av, nextAddr) }
def alloc(v: Expr): (A, Mem) = { val fresha = A(nextAddr); (fresha, new Mem(m + (fresha -> v), nextAddr + 1)) }
}
object Mem { val empty: Mem = new Mem(Map.empty, 1) }
def memalloc(v: Expr): DoWith[Mem, A] = doget flatMap { m => val (a, m_) = m.alloc(v); doput(m_) map { _ => a } }defined function isValue defined function isLValue defined class DoWith defined object DoWith import DoWith._ defined class Mem defined object Mem defined function memalloc
Exercise 35.7 Implement
def step(e: Expr): DoWith[Mem, Expr] = ???defined function step
for mutable arrays according the judgment form \( \langle e, m \rangle \longrightarrow \langle e', m' \rangle \) you defined in Exercise 35.6.
You may assume the existence of a helper function
mapFirstWith: List[A] => (A => Option[DoWith[S, A]]) => DoWith[S, List[A]]
that replaces the first element of given list List[A] where the callback returns Some(a) with a: DoWith[S, A].
A Proficient (P) answer implements
stepfollowing the \(\TirName{Do}\) and \(\TirName{Search}\) rules using appropriateDoWithconstructors for the \(\TirName{Do}\) rules and themapmethod onDoWithfor the \(\TirName{step}\) rules. For example,
def mapFirstWith[S, A](l: List[A])(f: A => Option[DoWith[S, A]]): DoWith[S, List[A]] = ???
def step(e: Expr): DoWith[Mem, Expr] = e match {
// DoArray
case Array(vs) if vs forall isValue => memalloc(e)
// SearchArray
case Array(es) =>
mapFirstWith(es) { ei =>
if (!isValue(ei)) Some(step(ei)) else None
} map { es => Array(es) }
}defined function mapFirstWith defined function step
In this section, let us assume that array indices must be numeric expressions of type \(\texttt{number}\).
Exercise 35.8 Give a rule for the location-typing judgment form \(\Gamma \vdash e \mathrel{\mathord{:}\mathord{\&}} \tau\) to enable array-indexing expressions to be assigned to.
A Proficient (P) answer give a rule for the array-indexing expression \(e_1\texttt{[}e_2\texttt{]}\) that infers the type of the array \(e_1\) and checks that \(e_2\) has type \(\texttt{number}\).
Exercise 35.9 Extend the typing judgment form \(\Gamma \vdash e : \tau\) to type check dynamically-allocated mutable arrays.
A Proficient (P) answer will give a \(\TirName{Type}\) rule for each construct (e.g., \(\TirName{TypeArray}\) for \(\texttt{[}\,\overline{e}\,\texttt{]}\), \(\TirName{TypeArrayIndex}\) for \(e_1\texttt{[}e_2\texttt{]}\)).
A Proficient (P) answer may give a \(\TirName{TypeAssignArrayIndex}\) rule for \( e_1\texttt{[}e_2\texttt{]} \mathrel{\texttt{=}}e_3\), while an Exceeding (E) answer may instead discuss why the generic \(\TirName{TypeAssign}\) rule is sufficient given the extended location-typing judgment form from Exercise 35.8.
Let us consider a new kind of parameter passing mode that we describe here. Suppose that we extend imperative JavaScripty with copy-out parameters where the function must be called with a location value (i.e., a mutable memory cell). On a call, a new mutable cell is allocated for the parameter initialized to \(\mathbf{undefined}\). Then, the body of the function is executed. Finally, the contents of the parameter cell are written back to the argument cell. We will write such functions with the \(\mathbf{out}\) mode annotation. For this question, assume that all functions have exactly one parameter and are anonymous (i.e., cannot be recursive), so a call-by-result function looks like the following:
\[ \texttt{(}x\texttt{:}\, \mathbf{out}\,\tau \texttt{)} \mathrel{\texttt{=}\!\texttt{>}} e_1 \]
For simplicity, assume the type checker rules out reading from \(x\) until it has been written to. The function should as usual return the value of \(e_1\). Hint: You will need to step to a new expression with a substitution but not just a substitution.
Exercise 35.10 Give the \(\TirName{Do}\) rule for calling call-by-result functions.
A Proficient (P) answer gives a rule that states a memory allocation \(a\notin \operatorname{dom}(m)\), that the argument \(e_2\) is a location \(e_2\;\mathsf{location}\), and writes the contents of the parameter cell back to the argument location after reducing the function body \(e_1\).
Exercise 35.11 Consider the following program in JavaScript with mutable objects.
a\(i\) based on the order of allocation (in our operational semantics). The first memory state is given as an example.console.log prints.const o = {x:0, y:0}
// [a1 -> {x:0, y:0}]
o.x = {f:1, g:{f:2, g:3}};
// ???
o.y = o.x.g;
// ???
o.y.g = o.x;
// ???
o.y = o.y.g;
// ???
o.x = o.x.g;
// ???
o.y.f = o.x.f;
// ???
console.log(o.x.f);
o.y.g.g.f = 7;
console.log(o.x.f);
console.log(o.y.f);A Proficient (P) answer will appropriately reduce object literals to their memory addresses (i.e., pointers). For example, the first
// ???in the above is as follows:
// [a1 -> {x:a3, y:0}, a2 -> {f:2, g:3}, a3 -> {f:1, g:a2}]The values that are printed at the end are evident given the memory states.
A Novice (N) to Approaching (A) answer will fail to recognize that object literals are not values, for example, writing incorrectly something like the following:
// [a1 -> {x: {f:1, g:{f:2, g:3}}, y:0]An Exceeding (E) answer may observe that the assignment
o.y.g.g.f = 7works because the assigments above it create a cycle in memory.