Assignment 2

Type: Individual Assignment
Due: before class on Thursday, April 22, 2021

Introduction

During class, we implemented a minimalistic, Lisp-inspired language that supports numbers, Booleans, basic arithmetic operators, and conditionals. In this assignment, you will extend this language to support additional operators and refactor the code to be more easily extensible. In particular, you will be adding operations for equality, numeric comparison, and multi-way conditionals.

Below is the BNF grammar for the language you will be implementing:

<expr> ::= ( <operator> <expr> <expr> )
        |  ( if <expr> <expr> <expr> )
        |  ( cond {<case>}* <else-case> )
        | <literal>

<operator> ::= + | * | - | = | < | <= | > | >=
                 | and | or | not

<case>      ::= ( <expr> <expr> )
<else-case> ::= ( else <expr> )

<literal> ::= #t | #f | <natural>
<natural> ::= <digit><natural> | <digit>
<digit>   ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Below are the main datatypes you will be working with. You should immediately notice that operations are grouped using the Operator algebraic datatype instead of cluttering the Expr datatype. Moreover, many of the operations such as -, <=, >, >=, and others do not have an associated Operator constructor. These operations are “syntactic sugars” and they will be implemented in terms of the core operations.

data Value = NumV Int
           | BoolV Bool
           deriving (Show,Eq)

data Expr = NumE Int
          | TrueE
          | FalseE
          | Op Operator Expr Expr
          | If Expr Expr Expr
          deriving (Show, Eq)

data Operator = Plus
              | Mult
              | Equal
              | LessThan
              deriving (Show, Eq)

Before continuing, be sure to download the following starter files.

• Parsing.hs
• Lang.hs

Part 1: Implementing interp

In the starter file, the parser is already partially constructed for you using the code we wrote together in class. However, you’ll notice that the interp function is undefined. You should begin by implementing interp.

Since the core binary operations are built-in using a table, I strongly suggest you write a helper function such as

opTable :: Operator -> (Value -> Value -> Value)

that takes in an Operator and returns the binary function that it is associated with. If your interpreter is implemented in this fashion, it will be trivial to add new core operators to the language.

You should thoroughly test the interp function before continuing.

Part 2: Comparison Operators

Although the parser already parses most of the core statements correctly, there are two new core operations that you need to add to the parser: = and <. Statements like (= 5 4) should be parsed into their corresponding AST Equal (NumE 5) (NumE 4). You can use the way + and * are implemented as a guide to parsing these.

Once you are done implementing = and < and thoroughly tested them, you should add the operators <=, >, and >= as syntactic sugar to the parser. You can use the way - is implemented as a guide.

Part 3: Mult-Way Conditionals

cond is a syntactical sugar for a mult-way conditional. In Python, a multi-way conditional has the following form:

if <cond1>:
    return <body1>
elif <cond2>:
    return <body2>
else:
    return <body3>

This conditional structure can be written using cond in the following way:

(cond (<cond1> <body1>)
      (<cond2> <body2>)
      (else    <body3>))

In this part, your task is to add cond to the parser as a syntactic sugar using nested if conditionals. If you do not immediately see how cond is a syntactic sugar, consider how the Python expression above can be written as:

if <cond1>:
    return <body1>
else:
    if <cond2>:
        return <body2>
    else:
        return <body3>

How to Turn in Your Code

1. Once you are finished with the assignment, you should go to https://codepost.io and log into your account.
2. Go to the CS 135 course.
3. Go to Assignment 2 and upload all of your files.
4. That’s it! You’ve just submitted your assignment.

Important Grading Criteria

I will evaluate your work with the following criteria in mind.

1. Correctness. Does your code do what is asked? (e.g. named correctly, input and outputs correct values, etc.)
2. Formatting. Is your code formatted so that it is easy to understand?
3. Elegance. Is your code concise and elegant?