Description
Building off the previous assignment, this defines additional derived classes to expand the expressions accepted by the program.
Problem Description
The previous assignment was able to support a wide variety of expressions, including all the defined operations for arithmetic and also the conditional expression for making decisions. No expression grammar would really be complete without being able to call functions.
To define a function using the actual syntax of the C language would require a significant extension to the grammar, including semicolons, braces, and variable declarations. Even taking the shorter Python approach would expect multiple-line input.
So instead, this assignment will take a shortcut and define functions in this way:
deffn sqr(x) = x*x
deffn abs(x) = x > 0 ? x : 0-x
deffn gcf(a,b) = (rem = a%b) == 0 ? b : gcf(b,rem)
The first token in the declaration will always be the string ‘deffn’ (which will look like an token for an undeclared variable), followed by a function declaration, and ‘=’, and an expression. You may assume the entire definition will appear on one input line. Of course, the input may also include all the expressions from the previous assignments.
You may assume for this assignment that all functions will be defined before any expressions try to use them, and that there will be no calls to non-existent functions.
Function Definitions
There are actually two aspects to handling functions — there is the definition of the function and its code, which would appear only once in a program. And then there are the function calls, which may occur many times, with different actual parameters.
A function definition would have these features:
a parameter list, naming the arguments to the function
a function body, which in this case would be an expression tree
For example, deffn square(x) = x*x would have a parameter list [“x”] and a function body Oper(Var(“x”),’*’,Var(“x”).
Of course, since a program can consist of multiple functions, there would need to be a container to hold these definitions. Since Python supports dynamic typing, the VarTree would work quite well — the ‘value’ of the ‘variable’ square would be a tuple holding the parameter list and the function body.
All that is required is for your program to use this new definition. There will be a new type of element for the expression tree representing the function call. This consists simply of the name of the function and a list of actual arguments. For example, square(a+2) would record the name square and the argument list [Oper(Var(“x”),’+’,Value(2))] There is no need for any information from the function definition to represent function call.
All of this information will come together at evaluation time. Evaluating a function will involve these steps:
Create a new empty VarTree representing the local function memory
Traverse the list of parameter names and actual arguments, assigning the values to each parameter within this new VarTree
Evaluate the function body, using the new VarTree
Since in C all function names are essentially global, visible within any other function, it is simplest to keep the function definitions in a separate variable. This would mean an extra parameter passed to all of your evaluate methods, just in case an expression includes a function call. Most operations (such as +) really do not need this function list, but they may need to pass it to anything that does.
A convenient front end
To minimize the number of changes between this assignment and the next, a short program file has been provided on the Canvas page. It will peek at the first word in the input line to identify whether it is defining a new function, or contains an expression to be evaluated.
Assignment Specifications
The list of files is essentially the same as for the previous assignment, with some additions to several of them.
evaluate.py
Front end distinguishing function definitions from expressions (no changes required)
exprtree.py
Defines the expression tree, with added support for function calls
infixtotree.py
Builds the expression tree, with added support for parsing function calls
newsplit.py
divides into tokens, generating an iterator (no new code required)
vartree.py
Implements a binary tree for variables (no new code required)
>No Extra Credit Option
The final assignment will have several extensions for Extra Credit, so if you want to or need to get credit, take an early look at that!