Homework answers / question archive / Assignment 3: Primitives, Conditionals, and Dispatch The goal of this assignment is to extend the parser, interpreter, and compiler with some simple unary numeric and boolean operations and two forms of control flow expressions: cond-expressions and case-expressions

Assignment 3: Primitives, Conditionals, and Dispatch The goal of this assignment is to extend the parser, interpreter, and compiler with some simple unary numeric and boolean operations and two forms of control flow expressions: cond-expressions and case-expressions

Computer Science

Share With

---

Assignment 3: Primitives, Conditionals, and Dispatch

The goal of this assignment is to extend the parser, interpreter, and compiler with some simple unary numeric and boolean operations and two forms of control flow expressions:

cond-expressions and case-expressions.

You are given a starter compiler based on the Dupe language we studied in class. The source code is available for download the dupe-plus.zip file can be found

You are tasked with extending the language in a number of ways:

adding new primitive operations,

adding cond, and

adding case.

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.

More primitives

Add the following forms of expression to the language:

(abs ): compute the absolute value of ,

(- ): flips the sign of , i.e. compute 0- , and

(not ): compute the logical negation of ; note that the negation of any value other than

#f is #f and the negation of #f is #t.

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.

e e

e e e

e e9/25/22, 8:54 AM

2/5

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.

Conditional Evaluation with Cond

The Dupe language we studied included a simple form of performing conditional evaluation

of sub-expressions:

(if )

However, in the original paper on Lisp, Recursive Functions of Symbolic Expressions and Their

Computation by Machine, Part I, John McCarthy introduced a generalization of if called

“conditional expressions,” which we could add to our language with the following syntax:

(cond [ ]

...

[else ])

A cond expression has any number of clauses [ ] ..., followed by an “else” clause

[else ]. 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 in order

until the first one that does not evaluate to #f is found, in which case, the corresponding

expression is evaluated and its value is the value of the cond expression. If no such

exists, the expression ’s value is the value of the cond.

Your task is to extend Dupe with this (restricted) form of cond.

To do this, you should:

Study ast.rkt to add appropriate AST nodes.

Extend parse.rkt to parse such expressions. (See A Leg Up on Parsing for guidance.)

Update interp-prim.rkt and interp.rkt to correctly interpret cond expressions.

Make examples of cond-expressions and potential translations of them to assembly.

Update compile.rkt to correctly compile cond expressions based on your examples.

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

Dispatching Evaluation with Case

Racket has a mechanism for dispatching between a number of possible expressions based on a

value, much like C’s notion of a switch-statement. This is the case-expression, which we

e0 e1 e2

e-p1 e-a1

e-an

e-pi e-ai

en

e-pi

e-ai e-pi

e-an9/25/22, 8:54 AM

3/5

could add to our language with the following syntax:

(case

[( ...) ]

...

[else ])

The meaning of a case expression is computed by evaluating the expression and then

proceeding in order through each clause until one is found that has a datum equal to ’s

value. Once such a clause is found, the corresponding expression is evaluated and its value

is the value of the case expression. If no such clause exists, expression 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.

Your task is to extend Dupe with this (restricted) form of case.

To do this, you should:

Study ast.rkt to add appropriate AST nodes.

Extend parse.rkt to parse such expressions. (See A Leg Up on Parsing for guidance.)

Update interp-prim.rkt and interp.rkt to correctly interpret case expressions.

Make examples of case-expressions and potential translations of them to assembly.

Update compile.rkt to correctly compile case expressions based on your examples.

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

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

ev

d1 e1

en

ev

di ev

ei

en9/25/22, 8:54 AM

l 4/5

; 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 right-handside of the clause which is used to determine whether the left-hand-side is evaluated, and the

left-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 caseclauses (not to be confused with cond-clauses), and an else-clause expression. Each caseclause, 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:

(abs 1) parses as (Prim1 'abs (Int 1)),

(not #t) parses as (Prim1 'not (Bool #t)),

(cond [else 5]) parses as (Cond '() (Int 5)),

(cond [(not #t) 3] [else 5]) parses as (Cond (list (Clause (Prim1 'not (Bool

#t)) (Int 3))) (Int 5)),

(cond [(not #t) 3] [7 4] [else 5]) parses as (Cond (list (Clause (Prim1 'not

(Bool #t)) (Int 3)) (Clause (Int 7) (Int 4))) (Int 5)),

(case (add1 3) [else 2]) parses as (Case (Prim1 'add1 (Int 3)) '() (Int 2)).

(case 4 [(4) 1] [else 2]) parses as (Case (Int 4) (list (Clause (list 4) (Int

1))) (Int 2)),

(case 4 [(4 5 6) 1] [else 2]) parses as (Case (Int 4) (list (Clause (list 4 5 6)

(Int 1))) (Int 2)), and

(case 4 [(4 5 6) 1] [(#t #f) 7] [else 2]) parses as (Case (Int 4) (list (Clause

(list 4 5 6) (Int 1)) (Clause (list #t #f) (Int 7))) (Int 2)).

Testing

You can test your code in several ways:9/25/22, 8:54 AM

5/5

Web Accessibility

Using the command line raco test . from the directory containing the repository to test

everything.

Using the command line raco test <file> to test only <file>.

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

cases.

Rubric

The autograder will grade based on these eight components:

Handwritten Tests (proportionally graded)

(50%) Public and non-public handwritten tests: Gradescope’s all.rkt will contain

additional private tests that does not match the ones in the publicly given file

Randomized Property Testing (must pass all the associated tests for each property)

(6.25%) Correct intepreter for primitives

(6.25%) Correct compiler for primitives

(6.25%) Correct intepreter for cond

(6.25%) Correct compiler for cond

(6.25%) Correct intepreter for case

(6.25%) Correct compiler for case

(6.25%) Correct intepreter

(6.25%) Correct compiler

Submitting

You should submit on Gradescope. You should submit a zip file with exactly the same

structure that the stub contains (a dupe-plus folder). We will only use the parse.rkt,

ast.rkt, compile.rkt, interp.rkt, and interp-prim.rkt files for grading, so make sure all

your work is contained there! The autograder will fail if it does not contain a dupe-plus folder

with these files or there is a syntax error