Extending ParselTongue

In this assignment, you will extend your implementation of ParselTongue three times, with

  1. Exceptions
  2. Python-style variables
  3. JavaScript-style variables

You will perform each extension separately, resulting in three separate implementations (which will likely share code). You do not have to, for instance, consider the interactions of the two kinds of scope and exceptions. It wouldn't hurt you at all to start thinking about it now, however, since these features do interact in Python.

Everything you need to get started is in one assignment bundle.

The grading binaries are included inside the reference implementations

Exceptions:

The typed-lang.rkt file that we've distributed has two syntactic forms for exceptions:

[TryCatchP (body : ExprP) (param : symbol) (catch : ExprP)]
[RaiseP (exn : ExprP)]

The concrete syntax looks like:

try
  raise "hi mom!"
catch e in
  e
# yields "hi mom!"

A raise expression provides its value as a binding for the parameter of the last-entered try-catch expression. Any value can be thrown, and should be bound to the catch parameter unmodified for exceptions that come from raise.

The most recently entered try-catch expression may be in another function or part of the program; for example:

deffun foo()
  raise "in foo"
in
deffun bar(f)
  try
    f()
  catch e in
    e
in {
  bar(foo)
}
# yields "in foo"

Throwing an exception should not change the store; any effects that occurred before the value was thrown remain:

defvar x = 0 in
  try
    +(x++, raise 42)
  catch e in
    x
# yields 1, because x was incremented

Finally, all the built-in errors of ParselTongue are catchable. They are thrown as object values with two fields - a "type" field set to the string "PSL", and a "message" field set to the string of the error message from the specification.

try
  +(5, "not-a-num")
catch e in {
  print(e.type);
  print("\n");
  print(e.message);
}

# Yields output:

PSL
Bad arguments to +Bad arguments to +

The type field is intended to distinguish ParselTongue errors from other kinds of errors.

If an exception is not caught by any catch block, the program terminates, and the program prints either:

  1. The Pretty version of the value, if the exception value isn't an object with a message field
  2. The Pretty version of the value in the object's message field, if the exception is an object with a message field.

Use raise-user-error to do this error handling; it produces output suitable for our test cases.

You may find this type useful for implementing exceptions:

(define-type AnswerC
  [ValueA (value : ValueC) (store : Store)]
  [ExceptionA (exn : ValueC) (store : Store)])

Along with following this signature for your interpreter:

(define (interp [exprP : ExprP] [env : Env]) : AnswerC
  ...)

HINT: Exceptions are somewhat like store-passing style. The result of evaluating each sub-expression can be an exceptional value, and the interpreter needs to check for it. Unlike in store passing style, where the store is handed on to the next expression, an exceptional result means that the interpreter needs to stop and yield the exception now. This repeated yielding of exceptional values either finds a try block or stops the whole program in an error.

Pythonic Scope

In Python, variables are added to the local scope by assignment statements, rather than by explicit declaration:

def foo():
  x = 22
  print(x) # 22 is printed
foo()

But they are undefined beforehand:

def foo():
  print(x)
  x = 22
foo()
# throws NameError: name 'x' is not defined

Python allows access to these variables in inner functions: 

def foo():
  x = 22
  def bar():
    return x
  bar()
foo()

# yields 22

But, Python doesn't allow assignment to closed-over variables by default, instead creating a new binding:

def foo():
  x = 22
  def bar():
    x = 44
    return x
  return {'bar': bar(), 'x': x}
foo()
# yields {'bar': 44, 'x': 22}

You need to change your implementation of ParselTongue to have this kind of scoping. deffun should still introduce a recursive binding, and defvar should still introduce new bindings as before. However, all assignments to unbound variables should cause a variable to be created:

deffun foo()
  x = 4;
  x;
in { foo() }
# should yield 4

Assignments to already bound variables should update them as usual if the binding is in the same function:

deffun foo()
  x = 4;
  print(x);
  x = 5;
  x;
in { foo() }
# should print 4, then yield 5 as an answer

If the binding is from a closed-over function, a new binding should be created:

deffun foo()
  x = 4;
  bar = lambda() {x = 5; x;};
  bar();
  x;
in { foo() }
# should yield 4, with the assignment in bar() not being seen
# outside

However, bindings can be seen inside:

deffun foo()
  x = 4;
  bar = lambda() x;
  x = 5;
  bar();
in { foo() }
# Should yield 5, with the update to x seen inside bar()

Note that this holds for all assignments in a function, even if they occur inside loops or conditionals:

if (true) then { x = 10; } else { false };
x;
# should yield 10

An identifier that is accessed before ever being set yields an unbound identifier error as usual.

HINT: Object update has the property that the field assigned to is either added to the object or altered depending on if it was already present.

JavaScript Scope

We've added one syntactic form for implementing JavaScript-style variable scoping:

[VarP (id : symbol) (value : ExprP)]

In JavaScript, a var declaration is "hoisted" to the top of the function it appears in, and acquires the initial value undefined.

function foo() {
  console.log(x);
  var x = 4;
  console.log(x);
  return x; 
}
foo();
# yields 4

This shows that the declaration for x is lifted to the top of the function, and is undefined until the original var declaration is reached.

If we didn't have the var statement, x would throw an error for being unbound:

function foo() {
  console.log(x);
  return x; 
}
foo();
# yields "Unbound identifier: x"

This includes hoisting through conditionals and loops. Multiple var declarations in the same function are simply redundant; only one variable is created for each, and they have their effects on the same created variable.

If a var declaration would be visited more than once, it acts as an assignment (switching to ParselTongue here):

for(var x = 0; <(x,10); x++) {
  var y = x;
};
y;
# yields 9 (this program just had 10 assignments to y)

You should make sure that for a program like this:

print(x);
var x = 12;

Your implementation actually prints the string "undefined". Similarly, the program:

var y = x;
var x = 2;
y;

Results in the undefined value, which you should print as "undefined". We recommend adding an UndefinedV case to the value type to handle this, but you are free to choose another representation if you wish.

In ParselTongue, variables should be lifted to the top of:

  1. The top level of the program
  2. Function bodies (including functions defined with deffun)
  3. deffun bodies
  4. defvar bodies

So, there are two places where var x is lifted below, once inside the function bound to foo, and once inside the body of the deffun:

deffun foo()
  var x = "inside foo";
  x = "set inside deffun";
in {
  var x = "in body";
  foo();
  x;
}

Note that if a variable declaration with the same name as a function parameter or defvar variable appears, the variable (including its initial undefined state), is what is seen in the body of the expression.

HINT: In order to implement this, consider starting with the following function:

(define (get-vars [exprP : ExprP]) : (listof symbol)
  ...)

This function should traverse the expression and find all the variables in it, which you can then manipulate to set up the hoisted declarations correctly.

Implementation and Grading Interface

Everything you need to get started is in one assignment bundle. A grade reporting script will be released closer to the deadline; this package contains everything you need to get started.

The bundle for this assignment is split across lib, tests, parseltongue-lang, and evaluators. You will work in tests and evaluators, though you're welcome to poke around in any of the other directories. You may also find it useful to change typed-lang.rkt in the parseltongue-lang directory, as restricted below.

You are free to split your implementation of these features across any combination of desugaring and interpreting. You are free to modify the core language in typed-lang.rkt by adding new values or new expression forms. You cannot change the definition of ExprP, which is the type of the inputs to your program, and is the top-level specification of ParselTongue expressions. We provide a typed-lang.rkt with some suggestions (like TryCatchC as a core form for exceptions), but you do not have to use them.

Note that var, try-catch, and raise are always included in the type for ExprP, even when you're implementing a feature that doesn't care about them. You can simply leave these cases as errors from your evaluator in those cases. For example, your exceptional interpreter might say:

[VarP (id value) (error "This evaluator doesn't handle VarP")]

Our tests for your implementation of exceptions won't touch this case.

To interface with the grader, you no longer provide both a desugarer and interpreter. Instead, you are to define a single evaluator, whose only constraint is that it take values of type ExprP. You will define a function called evaluate, and a function called pretty-print, which we will import to run your solution. We need the pretty printer because our harness prints out the answers of your evaluation, and we need you to provide us with a correctly-typed function. We expect that you may want to split your implementation across several files; a sample evaluator might look like:

    #lang plai-typed

    (require "typed-lang.rkt" "typed-desugar-py.rkt" "typed-interp-py.rkt")

    (define (evaluate e)
      (interp (desugar e)))

    (define pretty-printer pretty-value)

We have provided stubbed-out, suggested templates for all the evaluators (composed of interpreters and desugarers) in the assignment bundle.

We have written reference implementations for you, but we are providing only a small set of initial tests. For this assignment, it is your job to build up the test suite for the features as you implement them.

Instead of an executable, you can run the Racket yourself this time. Paths will be set up correctly if you run from within the evaluators directory:

$ raco make ../parseltongue-lang/extensions-assignment-main.rkt
<You may get a warning about "shift-reduce conflicts" here.  It's OK.>
$ racket ../parseltongue-lang/extensions-assignment-main.rkt <options>

The options are:

--stdin --stdout --stderr

As in other assignments

--set-evaluator filename

Use the evaluate and pretty-print functions from filename.  Note that you
should use this option before --interp or --test; order matters.

--interp

Run standard input with the provided evaluator (errors if nothing
provided)

--test dirname

Run the provided evaluator against the provided directory

The grading facilities are included in the reference implementations. You can use the --help option to see the format you will need to submit in. The relevant option is:

--report exn-evaluator.rkt py-evaluator.rkt js-evaluator.rkt

Runs all three interpreters against a reference test suite and outputs the
results in a grade report on stdout.

Handin

Submit your results at the submission form.

You will submit:

  1. Your grade report.
  2. A zip file with all of the Racket files and tests you write.

So that we can reproduce your results if necessary, you must name your evaluators exn-evaluator.rkt, py-evaluator.rkt and js-evaluator.rkt, for the three different extensions. If you customized typed-lang.rkt, include that in your zip bundle as well (copy it from the parseltongue-lang directory).