►CMSC 430:   Design and Implementation of Programming Languages
▼Assignments
►Assignment 3:   Primitives, Conditionals, and Dispatch
On this page:
What to Do
Primitives
Conditional expressions
Case expressions
Implementing primitives
Implementing cond
Implementing case
A Leg Up on Parsing
Testing
Submitting
8.13
    contents    up   

Assignment 3: Primitives, Conditionals, and Dispatch🔗

Due: Monday, June 17, 11:59PM

The goal of this assignment is to extend the language developed in Dupe: a duplicity of types with some simple unary numeric and boolean operations and two forms of control flow expressions: cond-expressions and case-expressions. The new language is called Dupe+.

The Dupe+ language extends Dupe in the following ways:

What to Do🔗

You must extend the parser, interpreter, and compiler to implement Dupe+. You are given a file dupe-plus.zip on ELMS with a starter compiler based on the Dupe: a duplicity of types language we studied in class.

You may use any a86 instructions you’d like, however it is possible to complete the assignment using Cmp, Je, Jg, Jmp, Label, Mov, and Sub.

Primitives🔗

The following new primitves are included in Dupe+:

Conditional expressions🔗

The following new conditional form is included in Dupe+:

(cond [e-p1 e-a1]
      ...
      [else e-an])

A cond expression has any number of clauses [e-pi e-ai] ..., followed by an “else” clause [else en]. For the purposes of this assignment, we will assume every cond expression ends in an else clause, even though this is not true in general for Racket. The parser should reject any cond-expression that does not end in else.

The meaning of a cond expression is computed by evaluating each expression e-pi in order until the first one that does not evaluate to #f is found, in which case, the corresponding expression e-ai is evaluated and its value is the value of the cond expression. If no such e-pi exists, the expression e-an’s value is the value of the cond.

Case expressions🔗

The following new case form is included in Dupe+:

(case ev
      [(d1 ...) e1]
      ...
      [else en])

The case expression form is a mechanism for dispatching between a number of possible expressions based on a value, much like C’s notion of a switch-statement.

The meaning of a case expression is computed by evaluating the expression ev and then proceeding in order through each clause until one is found that has a datum di equal to ev’s value. Once such a clause is found, the corresponding expression ei is evaluated and its value is the value of the case expression. If no such clause exists, expression en is evaluated and its value is the value of the case expression.

Note that each clause consists of a parenthesized list of datums, which in the setting of Dupe means either integer or boolean literals.

Implementing primitives🔗

Implement the primitives as described earlier.

There are many ways to implement these at the assembly level. You should try implementing these using the limited a86 instruction set.

To do this, you should:

  • Study ast.rkt and the new forms of expression (i.e. new AST nodes) then update the comment at the top describing what the grammmar should look like.

  • Study parse.rkt and add support for parsing these expressions. (See A Leg Up on Parsing for guidance.)

  • Update interp-prim.rkt and interp.rkt to correctly interpret these expressions.

  • Make examples of these primitives and potential translations of them to assembly.

  • Update compile.rkt to correctly compile these expressions.

  • Check your implementation by running the tests in test/all.rkt.

Implementing cond🔗

Implement the cond expression form as described earlier. To do this, you should:

Implementing case🔗

Implement the case expression form as described earlier. To do this, you should:

A Leg Up on Parsing🔗

In the past, designing the AST type and structure definitions has given students some grief. Getting stuck at this point means you can’t make any progress on the assignment and making a mistake at this level can cause real trouble down the line for your compiler.

For that reason, let us give you a strong hint for a potential design of the ASTs and examples of how parsing could work. You are not required to follow this design, but you certainly may.

Here’s a potential AST definition for the added primitives, cond, and case:

; type Expr =
; ...
; | (Cond [Listof CondClause] Expr)
; | (Case Expr [Listof CaseClause] Expr)
 
; type CondClause = (Clause Expr Expr)
; type CaseClause = (Clause [Listof Datum] Expr)
 
; type Datum = Integer | Boolean
 
; type Op =
; ...
; | 'abs | '- | 'not
 
(struct Cond (cs e)    #:prefab)
(struct Case (e cs el) #:prefab)
(struct Clause (p b)   #:prefab)

There are two new kinds of expression constructors: Cond and Case. A Cond AST node contains a list of cond-clauses and expression, which the expression of the else clause. Each cond-clause is represented by a Clause structure containing two expressions: the left-hand-side of the clause which is used to determine whether the right-hand-side is evaluated, and the right-hand-side expression.

The Case AST node contains three things: an expression that is the subject of the dispatch (i.e. the expression that is evaluated to determine which clause should be taken), a list of case-clauses (not to be confused with cond-clauses), and an else-clause expression. Each case-clause, like a cond-clause, consists of two things. Hence we re-use the Clause structure, but with different types of elements. The first element is a list of datums, each being either an integer or a boolean.

Now, we won’t go so far as to give you the code for parse, but we can give you some examples:

Testing🔗

You can test your code in several ways:

Note that only a small number of tests are given to you, so you should write additional test cases.

Submitting🔗

Use make from within the dupe-plus directory to create a zip file containing your work and submit it to Gradescope.

    contents    up