CIT 594 Assignment 6 Part II: Funl Evaluator
Spring 2013, David Matuszek

Funl is a very simple functional language. Functional means that functions are values. Very simple means that it's a "toy" language, not really good for much.

I have referred to this part of the assignment as an "interpreter," but that's really not correct. In a conventional language we interpret statements (things that have side effects), but we evaluate expressions (things that return a value). In Funl, everything has a value, so this assignment is really about writing a Funl evaluator.

The syntax of Funl was specified here.

Class structure

Create a project named Funl, a package named evaluator, and in the package put a class named Funl. Move or copy your other Funl classes (Parser, Tree, Token, Tokenizer, maybe others) into this package.

Within the Funl class you will have a main method. Executing the main method runs the REPL.

The class should also include an eval method:
          public Tree<Token> eval(Tree<Token> expr)
that is, it takes a Funl expression, evaluates it, and returns another Funl expression. This method will be highly recursive. You will also need a number of helper functions.

The class should also include a define method:
          public void define(String functionDefinitions)
This method will take a "program" (one or more function definitions), parse it, and save the functions in a HashMap<String, Tree<Token>>. Probably, this method will do little more than call the program method in your parser, and make the results available to this evaluator. We will also need it available for our unit tests.

Funl semantics

A program is nothing more than a collection of one or more functions. All the program does is define functions; it does not execute them. We will write a separate REPL to do that.

A function definition defines a function. It has a name, zero or more formal parameters, and a body. The body consists of a sequence of one or more expressions.

A function call is made by giving the name of the function, followed by a parenthesized list of zero or more arguments (expressions). The parentheses must be present even if there are no arguments. The number of arguments (actual parameters) in the function call must be the same as the number of formal parameters in the function definition. Details of function call and evaluation are given below.

A value definition, val name = expression, associates a value with a name. Funl is single-assignment; any subsequent attempt to assign a value to the same name will result in a run-time error. The value of a value definition is the same value that is assigned to the name.

An expression is either a value, a value definition, or it is a fairly typical arithmetic expression. The latter may involve numbers, names whose value is numeric, the four arithmetic expressions, parentheses for grouping, and also "if expressions" and "read expressions."

A sequence of expressions (denoted in the grammar by <expressions>) is evaluated one after the other, in order. The value of the sequence is the value of the last expression in the sequence.

An if expression consists of a condition part, a then part, and an else part.

A read expression prints a string to the console, then accepts a number entered by the user. The purpose of the string is simply to act as a prompt, alerting the user that input is expected. The value of the read expression is the number entered by the user.

Function evaluation

When a function call is made,

The REPL

The REPL (Read-Eval-Print-Loop) repeatedly: Reads in an expression from the user (provide some kind of prompt), evaluates the expression, prints the result, and loops to get the next expression. It recognized two special instructions:

The REPL has its own scope, with slightly different behavior from function scopes. In the REPL, a val expression is permitted to replace the value associated with a name. (In other words, it behaves like a Java assignment statement.)

Implementation notes

Every "value" can be kept as a Tree<Token> value. This is not efficient. For example, to evaluate 1 + 2, you would have to extract the String "1" from one token, extract the String "2" from the other token, convert the two strings to doubles (Double.parseDouble(string)), add them, convert the result to a String, create a Token to hold it, put the Token as the single node in a Tree, and use the Tree as the result.

It isn't efficient, but it does make the programming simpler, so do it this way. Efficiency is not an issue in this assignment.

For the REPL, you should keep your values in a HashMap<String, Tree<Token>>. The String is a variable name, and you use this as the key. The value you get back is a Tree<Token> representing the value, which is usually a number. If the key is not in the HashMap, and is not the name of a function, this is an error; you should politely inform the user that the name has no value, and continue running (do not crash the REPL!).

To implement function scopes, you need a Stack<HashMap<String, Tree<Token>>>, that is, a stack of HashMaps. Creating a new scope simply involves creating a new HashMap and putting it on the stack. Discarding a scope merely means popping the stack. I strongly recommend writing helper methods fetch and store, to access values in the topmost HashMap and to put them there. You may also want minor variations on these helper methods, to deal with parameter transmission (which involves two different scopes), and the REPL (which allows reassignment to val variables).

Pay special attention to the fact that the value of a name may be either a number or a function. If a number, the name should be found in the stack of HashMaps. If a function, it should be in another HashMap of functions. Functions, like numbers, may be passed as parameters to a function, or returned from a function. However, trying to use functions where numbers are required (for example, adding two together), or trying to call a number as if it were a function, should result in a (friendly) error message. It should also be illegal to use the same name for both a function and a number.

The eval method may seem frightening, but it's really just a bunch of special cases, depending on what is in the root of the tree. If it's a "+", you evaluate the two subtrees, add them, and return the sum (after putting it in a Tree<Token>). If it's a "$seq", you evaluate each of its children in order, and return the result of the last one. And so on.

One special case should be pointed out. A <program>, which is simply a sequence of function definitions, is not evaluated. It does not form a Tree. Instead, each function definition is put into a separate HashMap<String, Tree<Token>> of function definitions. The eval method does not handle this case.

More to come...

This is almost the last word (barring corrections and clarifications). Most of what we need to unit test your program is your define and eval methods (along with the equals method in your Tree class, which had better work!). Finally, I will provide some Funl programs for you to try out, and you should write some of your own.