FINAL CODE PROJECT: CS 4450

 

DUE: 3:00PM, 12/16/17

 

Directions

 

 

* The same general directions from Homeworks 1{3 for naming your submissions.

 

* When you submit, you must indicate which problems you attempted. Note that solutions to later problems depend on earlier problems. See the speci cations for details.

 

* You must make a good faith attempt to answer at least the  rst problem.

 

* Your base grade for this assignment starts at 75% and increases based on the following factors:

 

(a) Quality of submitted code (style will help, but not hurt your grade),

 

(b) Complete coverage of randomly generated test cases (automatic full credit),

 

(c) The total number of problems attempted and completed.

 

* This project uses the following le (available for download on the course canvas site):Base.hs, Lexer.hs, Operators.hs, RecursiveFunctions.hs, RecursiveFunctionsAST.hs, RecursiveFunctionsParse.hs.

 

* Every purported solution should be accompanied by tests written in HSpec.

 

Problems

 

 

1. Extend the de nition of the eval function to handle multiple declarations. Notice rst that the syntax of local declarations has changed (in RecursiveFunctionsAST.hs):

 

data  Exp  =	Literal	Value
|	Unary	UnaryOp	Exp
|	Binary	BinaryOp  Exp  Exp
|	If	Exp  Exp	Exp
|	Variable	String
|	Declare	[( String , Exp )]  Exp  —  This  has  c h a n g e d .
|  R e c D e c l a r e		String	Exp  Exp
|	Function	String	Exp
|	Call	Exp  Exp
deriving  ( Eq ,		Show )

 

Now, a declaration can take multiple bindings, so it will generally have the form:

 

Declare [(string₁; exp₁); : : : ; (string_n; exp_n)] body

 

A call to the evaluation function, eval Declare [(string₁; exp₁); : : : ; (string_n; exp_n)] body env, should process these declarations in the following way:

1. Apply eval to each of exp₁; : : : ; exp_n in the environment env, producing values value₁; : : : ; value_n,

2. Make a new environment adding bindings (string₁; value₁); : : : ; (string_n; value_n) to env;

 

3. Apply eval to body in this new environment.

 

You can then test your answer on the expressions, exp1,…,exp4, de ned in the project template. Note that exp4 contains a free occurrence of the variable m (because eval uses Scope Rule 2, see below); and as such, it should crash. You can also come up with your own test cases.

 

2. This problem concerns free variables. Recall from lecture that an occurrence of a variable in an expression is free if it does not occur within the scope of a declaration of that variable. Consider the following example written in concrete syntax:

 

var m = 42; n = m; n + m;

1 2 3

 

Three variables occur in this expression; labeled 1, 2, and 3. Occurrences 2 and 3 are bound by the declarations n = m and m = 5, respectively. But what of the rst occurrence? Well, that depends on the scope rules we pick; and thus, occurrence 1 could be either free or bound.

 

Let's de ne two scope rules. To do so, consider a declaration expression of the form: var x₁ = e₁; : : : ; x_n = e_n; body.

Rule 1. The scope of declaration x_i = e_i includes e_i+1; : : : ; e_n and body. As such, given the declaration x₁ = e₁

, x₁ does not occur free in e₂; : : : ; e_n or body. With this rule, occurrence 1 is bound by the declaration m = 5.

Rule 2. The scope of each declaration, x₁ = e₁; : : : ; x_n = e_n, consists only of body. In particular, the scope of the declarations of x_i = e_i do not include the e₁; : : : ; e_n. By this rule, occurrence 1 above is free, because it does not occur within the scope of m = 5 { since occurrence 1 does not occur in body.

 

Write two functions, freeByRule1 :: [String] -> Exp -> [String], that nds the free occurrences of an expression according to scope de ned by Rule 1 and freeByRule2 :: [String] -> Exp -> [String], that nds the free occurrences of an expression according to scope de ned by Rule 2. The cases that are most important to think through are the cases where variable declarations occur: Declare, RecDeclare, and Function. These functions must be written in accumulator passing style. In the speci ed type signatures, the rst argument { namely, [String] { is a list of variables that have already been declared.

 

1

3. This problem implements a command-line REPL (Read-Eval-Print Loop). The template contains code for a simple REPL. Go ahead and try it out. You can type in expressions, they are evaluated, the value is printed, and the loop starts over. you can quit by typing "quit" at the prompt.

 

Implement a REPL using the Haskeline library. Your interface should have history features, and it should be able to process expressions typed directly into the prompt, as well as, expressions written in les. Unlike the simple REPL, your interface should test expressions for free variables using Scope Rule 2; and, instead of crashing, it should handle free variables by notifying the user with a well-formated message. If anyone decides to do this, I will give you some utility functions to access le contents.

 

Grading

 

 

Function Points

 

eval: +4%

 

freeByRule1: +4%

 

freeByRule2: +4%

 

REPL: +9%

 

Hspec Tests: max +4%

 

Total +25%