CIT 594 Assignment 7: User-Defined Functions in LOL
Spring 2011, David Matuszek

Purposes of this assignment

General idea of the assignment

Our Little Ol' Language has a number of built-in functions, but it doesn't yet have a way for the user to define new functions. Your assignment is to extend the language with user-defined functions.

This extension will not require much additional code, but the code that it does require is fairly complicated. Changes must be made to both the parser and the interpreter. I'll tell you most of what you need to know, so please read this assignment extra carefully.

Constraints

The parser

  1. We want to be able to define functions with parameters (they would not be very useful otherwise).
  2. The parser needs to know how many parameters (the arity) each function takes.

Consequently:

  1. The parser must see the definition of a function before it sees any calls to the function. (That is, function definitions should be placed earlier in the program than calls to those functions.)
  2. To allow a function to be recursive, the parser must make note of the arity of the function before it processes the function body.

The interpreter

  1. We want functions to behave in a conventional way. They should take parameters (whose values are supplied in a call to the function), treat parameters as local variables, allow additional local variables, support recursion, and return a value.
  2. We want to call user-defined functions just like built-in functions: by giving the function name followed by values for its arguments.
  3. By the rules of LOL, every word is treated as a function, and has a value. Therefore, function definitions (not just function calls) should have a value.

Implementation

The parser

Function Arity Examples Semantics Value
define 3

def average [x y]
  divide plus x y 2

def factorial [x] [
 if equals? x 1
   1
   times x factorial minus x 1

Defines a new function whose name is the first argument, whose arity is the size of the second argument (which must be a block containing only words), and whose body is the third argument. None of the arguments are evaluated. Zero.
local 2 local count 0 The second argument is evaluated, and the result assigned to the first argument, which is treated as a local variable. The value assigned to the variable.
Calls to user-defined functions Depends. tell average 3 7
set f factorial 10
See below. Depends.

How to implement the parser

Your parse method, which already handles words (functions), numbers, and blocks, must be extended to handle the define statement. Here's what to do:

  1. Define a new HashMap to hold your user-defined functions (details given below).
  2. Recognize the word "define".
  3. Get the name of the function (first argument).
  4. Parse the parameter list (second argument), giving a tree with "[]" at the root, and one child for each parameter.
  5. Count how many parameters there are, and add the function name and arity to your map of function arities (you already have this table somewhere.) Do this step before doing the next step!
  6. Parse the function body.
  7. In your map of user-defined functions, add the name of the function, and a reference to the root of the function tree (the node containing the word "define").

Discussion

A function may be recursive; that is, it may call itself. This means that the body of the function may contain calls to the function. The way our parser works, we must know how many arguments a function takes before we can call it. To allow functions to be recursive, therefore, we must do step 4 (record the arity) before step 5 (parse the body of the function, which may contain a recursive call).

As I've described things, function definitions must occur before calls to that function. This means that we must be careful about the order in which we define our functions. It also means that we can't have mutually recursive functions: Function A calls function B, and function B calls function A. One solution which I considered (and which you can implement if you like), is to predeclare the arity of functions, with a statment something like arity sum 2.

Later on, when you interpret the program, you need to be able to find a function when there is a call to it. For this, you can set up a map of function names to function definitions. This is a little complicated; it's a HashMap<String, Tree<String>>.

Once you have done the above, you don't need to do anything more to parse calls to user-defined functions. They act just like built-in functions (at least, as far as the parser is concerned).

One question remains: What is the value of the definition of a function? We would really like to avoid nonsense statements like
     if greater-than? x y define big [] x define small [] y
In some languages this would be legal (the interpreter would define the new function), but in our language, the parser will define the functions, regardless of where they happen to be. There are two obvious solutions:

  1. Remove the define tree completely from the program tree. It doesn't need to be there. You could keep it as a separate tree; you have a reference to it in your map of user-defined functions. The parser could continue on as if the define had never happened (except for the new entry in the table of arities).

    This is really the better solution. However, if you do this, then when you look at the parse tree in your GUI, the user-defined functions won't be there--unless you want to make the GUI a lot more complicated. That can make your LOL programs much harder to debug.

  2. Leave the define tree as part of the program tree, but give it some value (I've said to use zero). This means that the "nonsense" statement above would be legal, and would result in a value of zero. But let's face it: You can write nonsense in any language. Why should LOL be any different?

How to implement the interpreter

I hope you remember that, a few weeks back, I talked about implementing functions using stacks and stack frames (see 11-stacks.ppt). This is what you need to do.

You already have a HashMap<String, Double> in which you keep the values of variables. The difference is that now we will use that HashMap to keep track of global variables. Now we need to also keep track of local variables, and for that we need a Stack of HashMaps, that is, a Stack<HashMap<String, Double>>.

In your interpreter, after you have checked for built-in functions and before you decide it's a variable, you should check whether the word is the name of a user-defined function. If it is:

  1. Create a new HashMap for the local variables, but don't yet add it to the stack of local variables.
  2. Evaluate each argument to the function (you know it's arity), get the name of the corresponding formal parameter, and add the name and value to the topmost new HashMap in the stack of local variable HashMaps.
  3. Now add the new HashMap to the stack of local variables.
  4. Evaluate the function body, and hold on to the result.
  5. Discard ("pop") the topmost HashMap from the stack.
  6. Return the value of the function

Your fetch and store methods need to be updated.

You also have a new function, local, to interpret. This function computes a value and stores its result as a local variable (in the topmost HashMap of your stack). This is intended for use only inside functions; but if it occurs in the "main" program, store the variable and its value in the global table.

Testing

In addition to the usual unit tests, write LOL programs to test out every aspect of your interpreter. Submit these in the same zip file as the rest of your program.

Due date

Turn your assignment in to Blackboard before 6AM Monday, March 14.