Explorations in Scopes and Evaluation

We have now (hopefully) learned enough that we can do interesting and fun things with languages. This exercise will explore some of the possibilities.

This exercise is compulsory, meaning that you should hand it in for correction. The deadline is September 30th. You will not get a grade, only pass/fail. It's compulsory because

• We want to make sure that you actually get started on your programming assignments
• We want to check how much you've learned, so that we can adapt the course if necessary

If you get stuck, please ask Anya, Naim or one of your fellow students for help. The assignment should be completed individually, but you can certainly discuss problems with each other. You should understand and be able to explain all parts of your own solution.

Submitting Your Solution

1. Ideally, follow the recipe at Using the SLE@UiB Team, and just send us an email with your repository name/url when you're finished. Remember to browse the Source and/or Commits tab of the Bitbucket page for your repository to make sure that all your code has been delivered.

2. If all else fails, just send us a Zip file with your code.

3. Show up at the lab, either Sep 27th or Oct 4th, and show and explain your code to Naim or Anya. Or, you can do this at one of the lectures or by appointment. You are responsible for making sure that we look at and approve your code.

1. Get Software

First, Upgrade Rascal

• You need to uninstall the old Rascal first, due to changes in the package names

  • Help → About Eclipse → Installation Details
  • Find The Rascal Meta-Programming Language in the list of installed software
  • Click Uninstall
  • Click Finish
  • You can say No to restarting

• Then go to Help → Install New Software, and select the http://update.rascal-mpl.org/stable/ update site

• Select Rascal, and follow the installation procedure to the end

• Restart Eclipse

Bugfix for old projects

If you have old projects that give a null pointer after updating to a new version:

• close the project in Eclipse (or just shut down Eclipse)
• open the .project file and remove the linkedResources section.
• open the project again in Eclipse (or start Eclipse again)

The .project file is in the project directory, which is wherever you checked things out from Git, or in your Eclipse workspace (if you made your own project).

Download Code

• First, pull (update) any code you've already checked out from the inf225public repository. Click on each project and run Team → Pull.

• Some of the Eclipse .project files have changed, in order to get rid of annoying popups with the new Rascal version. After you've updated your old project, restart Eclipse to make it reload the project files.

• Follow the Git import instructions from Installing Rascal step 5 and onwards. The repository URI is probably already available in the wizard. Get inf225ex3 (and possibly all the other projects that are available).

2. Updatable variables

The inf225ex3 project contains a EvaluatorDynamic version of the evaluator, with dynamic scoping. We'll use this one first.

Your task is to change the semantics of the language to allow variable values to be assigned to (changed). In the old design, a variable is bound to a value, and it then has that value for the entire lifetime of the variable (i.e., the scope of the let-expression). A nested let-expression may be able to rebind the variable name (i.e., create an inner variable definition that shadows the outer one), but it could never affect the value of the variable outside its scope.

2.1 Add new language constructs

Assignment

The syntax for assignment should be something like (assignment is normally right-associative, if it is associative at all):

  syntax Expr
      = right VAR var "=" Expr e
      ;

• Add the assignment syntax to your grammar. Make sure that you deal with operator priorities properly.

For simplicity, you might want to forbid function names from being assigned to.

Sequencing

In order for assignment to have any useful effect, you also need a sequencing operation – an idea of one thing being executed before another thing.

You can support this with a sequence operator:

  syntax Expr
      = left Expr e1 ";" Expr e2
      ;

This will have the meaning: “Evaluate e1 first, then evaluate e2. The value of ‘e1;e2’ should be the value of e2.” The sequence operator should be left-associative.

C-like language has a comma operator with similar semantics.

• Add the sequence operator to your grammar. Again, you need to thing about operator priorities, or your programmers are going to get confused.

The syntax of ‘let’ and ‘if’ have an ‘end’ keyword at the end. This is very helpful in avoiding confusion and ambiguities once we add the above constructs.

Iteration

• You may also want to add a ‘while’ loop to your syntax. This is entirely optional.

Semantics of Updatable Variables

Assignment is a type of expression that can affect its environment. In order to allow this, we must update our evaluator so that evaluation of expressions return both a return value and a new, updated environment.

• You must change all the eval functions that deal with expressions to return the type tuple[Value, Env]. You construct a tuple value using angle brackets: <val, env>.

• When you recursively call the evaluator, you must decompose the return value into the value and the updated environment. The updated environment is then passed to the next evaluation step, or returned:

public Value eval((Expr)`<Expr e1>+<Expr e2>`, Env env) {
    <e1Val, env1> = eval(e1, env);
    <e2Val, env2> = eval(e2, env1);

    return <Int(e1Val.intValue + e2Val.intValue), env2>;
}

• Do this for all expression constructs.

• The function that evaluates programs should probably just return the value, so that the user doesn't have to deal with environments at all. E.g., like this:

public Value eval((Program)`...`) { ... }

• Check that the evaluator still works, by writing and evaluating a few small programs (see below for more about testing).

• Add the assignment operator. It will return an updated environment. If you want to check that the variable is already defined (in a dynamic language, it typically won't have to be), you can do varName in env (read more about the Rascal in operator). You can throw an exception by doing throw "Undefined variable <varName>" (any value is a valid exception object for throwing exceptions in Rascal).

• Implement let. This is the tricky bit... Let will add a new variable, and any changes to that variable shouldn't be visible outside the let. However, changes to other variables should be visible outside the let. For example:

let x = 5 in
  let x = 7 in
    x = 9
  end;
  x
end

should give the result 5 (the binding of x to 7, and subsequent assignment is undone when the inner let ends), whereas

let x = 5 in
  let y = 7 in
    x = 9
  end;
  x
end

(We solved parts of this problem in the code for Lecture 10)

• If you added a while loop to the syntax, you also need to add it to the evaluator. Traditionally (e.g., in Lisp), the value of a while expression is the value of its body at the last iteration. You also need a sensible value for when the while loop is not executed at all (zero, perhaps?).

Hints & Tips

• The new note on evaluators is probably (hopefully?) helpful.

• It may be a good idea to read the documentation on central Rascal concepts

• We fixed a bug on Sunday, so make sure you have the latest changes if you find errors.

• Make sure that eval((Program)`let x = 0 in var x = 4; 9 end`) == eval((Program)`let x = 0 in (var x = 4); 9 end`), otherwise you have a priority problem in your grammar. (The semicolon should have lowest priority.)

• If you change your grammar in Eclipse, the editor is not always updated with the latest grammar, so you might still get syntax errors there. Possible fixes include closing and opening the editors, and maybe importing things in the console again.

• You also need an evaluation rule for parenthesis expressions.

Testing

You can add tests to your program using the Rascal test feature. Just add the test modifier to any boolean function, and it'll get run when you type :test in the console (provided you've imported the module in the console).

For example (these should work even without assignment):

test bool Numbers() { return eval((Program)`5`) == Int(5); }

test bool Arith1() { return eval((Program)`5+5`) == Int(10); }
test bool Arith2() { return eval((Program)`1+2*3`) == Int(7); }
test bool Arith3() { return eval((Program)`10-2`) == Int(8); }
test bool Arith4() { return eval((Program)`10/2`) == Int(5); }
test bool Arith5() { return eval((Program)`(1+2)*3`) == Int(9); }
test bool Arith6() { return eval((Program)`((10)/(2))`) == Int(5); }

test bool If1() { return eval((Program)`if 2*3 == 6 then 42 else 69 end`) == Int(42); }
test bool If2() { return eval((Program)`if 6 == 5 then 42 else 69 end`) == Int(69); }
test bool If3() { return eval((Program)`if 10 \< 5 then 1 else 0 end`) == Int(0); }

For ad-hoc testing, open the console and import both your evaluator and the syntax (needed so you can use concrete syntax in the console). Then you can call the evaluator directly from the console:

eval((Program)`let x = 5 in x = 6; x end`)

Official Tests

I've prepared a few tests you can use on your own evaluator. They've all been pushed to Git:

• TestBasic should work with or without adding assignment and sequencing
• TestRandom will test the arithmetic operators with random numbers. Requires that you add negative numbers to your grammar.
• TestAssign will test your finished project.

I'm assuming that your eval((Program)`...`) takes care of constructing the environment and discarding it when evaluation is done, so it returns just a value. You may need to make minor adjustments to the test files.

Run the tests by importing the test modules in the console, and entering :test. The random tests may take some time to run.

2.2 Scoping variants

Let's do this as a non-compulsory exercise. ;)