Assignment 3

3 minute read

Type: Individual Assignment
Due: before class on Tuesday, May 4, 2021

Introduction

On the previous assignment, we implemented a simple programming language akin to Lisp. In this assignment, we will extend this language to include functions and “let” expressions, which allow us to give names to values.

New Features

Environment

You will use an environment for your interpreter to keep track of the values of identifiers in scope. From the data definitions you can see that an Env is a list of (String,Value) pairs. This means you can use Haskell’s built in list functions on your Env.

Your interpreter should allow identifier shadowing, meaning that if you bind an identifier that is already bound, the new binding takes precedence.

Functions with Any Number of Parameters

Extend the language to include functions. Your functions should be able to take zero or more arguments. All arguments to the function must evaluate with the same deferred substitutions. Here’s an example of a function and its application:

((lambda (x y) (+ x y)) 2 3)

The above expression should evaluate to 5.

Let Expressions

You should also add let to the language as syntactic sugar. let should accept a list of one or more bindings of names to values. Each binding should be surrounded by parentheses:

(let ((x 1) (y 2)) (+ x y))

The above expression should evaluate to 3.

The let expression should behave as described in the book, and should disallow recursive definitions. That is, in (let ((<id> <expr>)) <body>), <id> should be bound in <body> but not in <expr>. The desugaring of let may not be obvious, but here’s a hint: it involves FnDef and FnApp.

The New Grammar

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

<expr> ::= ( <operator> <expr> <expr> )
        |  ( if <expr> <expr> <expr> )
        |  ( cond {<case>}* <else-case> )
        | <literal>
        | <id>                           // identifier
        | ( lambda ( {<id>}* ) <expr> )  // anonymous func
        | ( <expr> {<expr>}* )           // func application
        | ( let ({binding}*) <expr>)

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

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

<binding>   ::= ( <id> <expr> )

New Datatypes

Below are the main datatypes you will be working with. These types are an extension of those in Assignment 2.

type Identifier = String

data Value = NumV Int
           | BoolV Bool
             --  Parameters   Body Closure
           | FnV [Identifier] Expr Env 
           deriving (Show,Eq)

type Env = [(Identifier,Value)]

data Expr = NumE Int
          | TrueE
          | FalseE
          | Op Operator Expr Expr
          | If Expr Expr Expr
          | FnDef [Identifier] Expr -- Parameters, Body
          | FnApp Expr [Expr]       -- Function, arguments
          | Id Identifier
          deriving (Show, Eq)

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

Starter Files

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

Part 1: Implementing `interp`

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

Note that the parser already parses anonymous function definitions for you such as:

((lambda (x y) (+ x y)) 5 4)

You should thoroughly test the interp function before continuing.

Part 2: `let` Desugaring

let is a syntactical sugar akin to Haskell’s let x in ... syntax that makes code much easier to read.

A let statement in Lisp has the following form:

(let ((var1 exp1)
      (var2 exp2)
      ...
      (varn expn))
  body)

In this part, your task is to add let to the parser as a syntactic sugar. It may be easiest to add a line to the pBuiltIn parser with:

"let" -> ...

You can use the solution to cond as an example.

How to Turn in Your Code

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

Important Grading Criteria

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

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