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.
Learning-Levels Rubric
4 - Exceeding (E)
Student demonstrates synthesis of the underlying concepts. Student can go beyond merely describing the solution to explaining the underlying reasoning and discussing generalizations.
3 - Proficient (P)
Student is able to explain the overall solution and can answer specific questions. While the student is capable of explaining their solution, they may not be able to confidently extend their explanation beyond the immediate context.
2 - Approaching (A)
Student may able to describe the solution but has difficulty answering specific questions about it. Student has difficulty explaining the reasoning behind their solution.
1 - Novice (N)
Student has trouble describing their solution or responding to guidance. Student is unable to offer much explanation of their solution.
17.1 Abstract Syntax Trees
Exercise 17.1 Consider the following buggy implementation of nnf that attempts to convert a boolean expression represented as a BExpr into negation normal form (Exercise 13.2). What’s correct and what’s buggy about this implementation?
sealedtrait BExprcaseclassVar(x:String)extends BExprcaseclassNot(e: BExpr)extends BExprcaseclassAnd(e1: BExpr, e2: BExpr)extends BExprcaseclassOr(e1: BExpr, e2: BExpr)extends BExpr defnnf(e: BExpr): BExpr = e match{caseNot(Not(e1))=> e1 // Remove double negationcaseNot(And(e1, e2))=>Or(Not(e1),Not(e2))// De Morgan's Law for conjunctioncaseNot(Or(e1, e2))=>And(Not(e1),Not(e2))// De Morgan's Law for disjunctioncase _ => e}
defined traitBExpr
defined classVar
defined classNot
defined classAnd
defined classOr
defined functionnnf
A Proficient (P) answer recognizes that the pattern matching implementing the rules to convert to negation normal form is correct, but the following are missing: base cases, pass-through recursive cases for And and Or, and the recursive calls to normalize the appropriate sub-expressions in the Not cases. A Proficient (P) answer should be able articulate which test cases will work and which will not.
Exercise 17.2 Fix this buggy implementation of nnf and argue that it correctly converts any BExpr into negation normal form. It is sufficient to do this by writing on a sheet of paper or a whiteboard.
A Proficient (P) answer will be able add the missing base cases, the cases for And and Or, and fix the Not cases. The correctness argument should state something about normalizing recursively or by induction.
An Exceeding (E) answer should recognize that the induction hypothesis needs to be general enough for both expressions \(e\) and their negation Not(\(e\)).
17.2 Ambiguity Detective
Exercise 17.3 Consider a programming language with some binary infix-operator expressions. When is it possible to test the relative precedence of those operators by evaluating example expressions? How would you do it? Can you give an example? Explain.
A Proficient (P) answer should recognize this is what was asked in the Precedence Detective exercise (Exercise 13.4) with << and -. It should state that if running different versions of an expression using << and - corresponding to different precedence orders yields different values, then it is possible to test relative precedence.
Exercise 17.4 How about for associativity? Can you give a positive example an operator that you can test its parsing-associativity by evaluating expressions and a negative example where you cannot in Scala?
A Proficient (P) answer should recognize that different versions of an expression corresponding to different associativities may yield the same answer. In this case, one cannot test. In math, an operation is called an associative operation where parsing expressions with the operator as left or right associative does not change its semantics. Note the difference in using two uses of “associative” in the last sentence. A standard example for an associative operation (in math) is \(+\), while \(-\) is not.
Describe the sentences of the language defined by this grammar.
Give two positive example sentences in the language described by this grammar and two negative example strings not in the language described by this grammar.
For each positive example sentence, give a leftmost derivation and a parse tree.
For each negative example string, argue why they are not by described the grammar (e.g., show getting stuck trying to construct parse trees).
A Proficient (P) answer sees that \(\mathit{A}\) describes the language of one-or-more \(\mathtt{a}\)’s and \(\mathit{B}\) as the language of matching \(\mathtt{b}\)’s and \(\mathtt{c}\)’s. Thus, \(\mathit{S}\) must have one-or-more \(\mathtt{a}\)’s followed by matching \(\mathtt{b}\)’s and \(\mathtt{c}\)’s followed by one-or-more \(\mathtt{a}\)’s. A Proficient (A) answer will be able to give derivations, parse trees, etc. for 2–4.
Exercise 17.6 Consider the following two grammars for expressions \(\mathit{e}\): \[
\begin{array}{rrl}
\mathit{e} & \mathrel{::=}& \mathit{operand} \mid\mathit{e}\;\mathit{operator}\;\mathit{operand}
\end{array}
\tag{17.1}\]
In both grammars, \(\mathit{operator}\) and \(\mathit{operand}\) are the same; you do not need to know their productions for this question.
Describe the expressions generated by the two grammars.
Do these grammars generate the same or different expressions? Explain.
Hint: Think about both the concrete syntax (sentences or strings) and the abstract syntax (terms or trees).
A Proficient (P) answer will recognize that in both grammars, the language described by \(\mathit{e}\) is one-or-more \(\mathit{operand}\)’s separated by \(\mathit{operator}\)s. It should state they describe the same language, that is, they are the same in terms of strings and concrete syntax. They are both refactorings of a common binary \(\mathit{operator}\) grammar.
A Proficient (P) answer will recognize that neither grammar is ambiguous and in terms of parsing, produce different parse trees. The first grammar has left recursion in \(\mathit{e}\), while the second grammar has right recursion in \(\mathit{esuffix}\).
17.4 Concrete Syntax, Abstract Syntax, and Semantics
Exercise 17.7 Is the above grammar ambiguous? If so, prove that it is ambiguous. If not, argue informally why it isn’t.
A Proficient (P) answer will recognize that the grammar is ambiguous involving the second and third productions. An example sentence that shows the ambiguity is \(\otimes \mathtt{a} \oslash \mathtt{a} \oplus \mathtt{a}\). It will state a sentence like this one and give two different (valid) parse trees for it.
Exercise 17.8 Let us ascribe a semantics to the syntactic objects \(\mathit{A}\) specified in the above grammar. In particular, let us write \[
\mathit{A} \Downarrow n
\] for the judgment form that should mean \(\mathit{A}\) has a total number \(n\) of \(\mathtt{a}\) symbols where \(n\) is the meta-variable for numbers. Define this judgment form via a set of inference rules. You may rely upon arithmetic operators over numbers.
Hint: There should be one inference rule for each production of the non-terminal \(A\) (called a syntax-directed judgment form).
A Proficient (P) answer will define this judgment using three inference rules—one for each production of \(\mathit{A}\). It is also a good answer to define a judgment form \(\mathit{B} \Downarrow n\) with one inference rule.
A Exceeding (E) answer will realize that one could give these two possible answers.
17.5 Interpreter Implementation
Exercise 17.9 Some binary operators \(\mathit{bop}\) are overloaded for numbers and strings in JavaScript(y), that is, they apply a different number or string operation depending on the type of the operands.
To implement your eval function, how did you discover which ones? Which ones did you discover are overloaded?
Give an example JavaScript(y) expression that performs a string operation after coercing a number to a string.
On paper or a whiteboard, trace through your eval implementation using your test case from 2. It is fine if you discover a bug in your eval implementation doing this exercise.
Use this following notation to show the key steps in running your Scala implementation:
eval(\(\mathit{env}\),\(e\)) =\(v\)
if eval(\(\mathit{env}_1\),\(e_1\)) =\(v_1\)
if eval(\(\mathit{env}_1'\),\(e_1'\)) =\(v_1'\)
\(\ldots\)
if eval(\(\mathit{env}_2\),\(e_2\)) =\(v_2\)
\(\ldots\)
\(\ldots\)
where each “node” in the tree above is a recursive call to eval. You may write \(\mathit{env}\), \(e\), \(v\) as Scala values (i.e., the Scala representation of JavaScripty) or JavaScripty concrete syntax as you prefer.
A Proficient (P) answer will say that number addition and string concatenation use the same operator + and that number comparison and lexicographic-string comparison is also overloaded with <, <=, >, and >=. The answer should include that they wrote and ran JavaScript expressions that should performing number addition versus string concatenation (and similarly for comparisons) to discover that + is considered string concatenation if either argument is a string, while <, <=, >, and >= are considered lexicographic-string comparison only if both arguments are strings. It should then use + to give a test case that coerces a number to a string.
A Proficient (P) answer for the tracing should have the right number of eval calls on sub-expressions to reach the bases cases with the appropriate indentions showing recursive calls.
Exercise 17.10 Trace through your eval implementation for the JavaScripty test case \[
\mathbf{const}\; \texttt{abc} \;\texttt{=}\; \texttt{1} \mathbin{\texttt{+}} \texttt{2} \texttt{;}\; \texttt{abc}
\] or equivalently, for
A Proficient (P) answer will have exactly 5 calls to eval.
As noted above, it is fine to answer with concrete JavaScripty syntax in place of the Scala abstract syntax tree representation as long as it is understood that this is just for ease of writing it on the board and is not what “Scala sees”. It is a below Proficient (P) indicator if there’s confusion about what is concrete syntax for the board and what are abstract syntax trees.