Learning Objectives
With this assignment you will demonstrate:
- The ability to write denotational semantic specifications for mid-size programming languages
- An understanding of the differences between operational and denotational semantics
- The ability to write an interpreter
Readings and Videos
Please:
- Review course notes and previously assigned readings as needed.
Instructions
Submit, to BrightSpace, a neatly typeset answer to Problems 1 and 2, and a link to a GitHub repo for Problem 3. Please make a best effort for typesetting. Handwritten answers are okay if you are short on time, but pay extra attention to neatness if you go that route.
Problems to Submit
Each of the problems are for an extension to the Bella language in the course notes. The new language is called Bella 2, and like Bella, is strongly-typed and dynamically typed. Here is the abstract syntax:
$ \begin{array}{l}
n\!: \mathsf{Numeral} \\
i\!: \mathsf{Identifier} \\
e\!: \mathsf{Expression}
= n
\;|\; i
\;|\; \mathtt{true}
\;|\; \mathtt{false}
\;|\; \mathit{uop} \; e
\;|\; e_1 \; \mathit{bop} \; e_2
\;|\; i \; e^*
\;|\; e \; \mathtt{?} \; e_1 \; \mathtt{:} \; e_2
\;|\; \mathtt{[} \; e^* \; \mathtt{]}
\;|\; e \mathtt{[} e \mathtt{]} \\
s\!: \mathsf{Statement}
= \mathtt{let}\;i = e
\;|\; \mathtt{func}\;i\;i^*=e
\;|\; i = e
\;|\; \mathtt{print}\;e
\;|\; \mathtt{while}\;e\;b \\
b\!: \mathsf{Block} = \mathtt{block}\; s^* \\
p\!: \mathsf{Program} = \mathtt{program}\; b
\end{array} $
The unary operators are
- and
!.
The binary operators are
+,
-,
*,
/,
%,
**,
<,
<=,
==,
!=,
>=,
>,
&&,
and ||.
The standard library is as we saw in class.
Here are the problems to submit. Please use Claude, Codex, Gemini or your favorite agent for assistance. You may let the agent do the entire assignment for you; however, you still need to read and understand everything. Use the assist as a learning opportunity.
This assignment is too large to do entirely by hand.
- Give a natural semantics for Bella 2. It is possible that this is already done in the course notes. There is benefit in packaging it all up neatly as part of an assignment packet, though. If you prefer to something new, you may instead write a structural operational semantics or a concrete operational semantics.For the latter, your abstract machine will need a way to bundle up un-evaluated functions. Make sure to document your approach. Feel free to work out the approach with Claude or any other thought partner.
- Give a denotational semantics for Bella 2.
- Write a complete interpreter for Bella 2. The language in which you implement the interpreter is not important. TypeScript, any ML dialect, Clojure, Rust, Swift, Kotlin, Python, Java, Go, or any other language is fine. What is important is that you include a test suite with 100% coverage. I will also ask that you use modern forms of the language you choose. For example, if you choose Java, please use records and sealed classes and any other modern Java feature, such as switch expressions, that make sense. The input to the interpret function can be a structured program representation (an abstract syntax “tree” object), or you may have have your agent write a full parser for you.