Courses/CS 332L/Functions
From CSWiki
[edit] Defining functions
A function consists of a list of parameters and a body that is executed with respect to those parameters, and possibly some local variables. In Haskell (which you learn in CS 332f), the following notation (or something close to it) is used to represent functions.
\(x, y) -> x+y
This is an (unnamed) function of two variables x and y, whose body consists of the expression x+y. Since this parses in Prolog, we might as well use the same notation. Let's consider an example using factorial. We can write the following.
factorial = (\x -> (if (x < 2) then 1 else x * factorial(x-1))).
Since (->) has lower precedence than (else), and since (=) has lower precedence than (->), all the parentheses are needed. We could redefine the precedence of these operators, but it's probably easier simply to include the parentheses. This parses as follows.
=
/ \
/ \
/ \
/ \
factorial ->
/ \
(\) else
/ / \
x then *
/ \ / \
if 1 x \
| factorial
< |
/ \ -
x 2 / \
x 1
This is to be understood as saying that factorial is the name of the (recursive) function of one variable (x) whose body is
if (x < 2) then 1 else x * factorial(x-1)
Function definitions can be stored in the Bindings like other variable values. When we define functions as methods we can store those functions as values of instance variables.
[edit] Evaluating functions
When a function call (such as factorial(y)) is encountered, the job is to do the following.
- Evaluate the arguments in the argument list, yielding a list of values.
- Retrieve the function declaration.
- Create a new empty Bindings list.
- Bind the evaluated arguments to the function parameters by storing them in the new arguments using standard assignment.
- Execute the body of the function using the new arguments.
- Return the result.
- Discard the Bindings used for this function and restore the previous Bindings.
We want to get a result like the following.
?- eval( y = 5;
factorial = (\x -> (if (x < 2) then 1 else x * factorial(x - 1)));
z = factorial(y),
[],
Classes_out,
[],
Bindings_out,
Result)
Classes_out = []
Bindings_out = [z=120, factorial = (\x -> (if (x < 2) then 1 else x * factorial(x - 1))), y = 5]
Result = 120
You will want to write an eval/6 clause to handle function evaluation. As a first approximation, it will look something like the following.
From now on, we will assume that we are always working within some object. So instead of Bindings_in and Bindings_out, we will write Inst_vars_in and Inst_vars_out. (Does that feel like slight-of-hand?)
eval(Function_call, Classes, Classes, Inst_vars_in, Inst_vars_out, Result) :- % Classes_in = Classes_out since function evaluation shouldn't include class definitions. % But Inst_vars_in may change to Inst_vars_out if we are executing a function (method) inside an % object and that method assigns a value to an instance variable. Function_call =.. [Function_name | Args], member(Function_name = (\Parameters -> Body), Inst_vars_in), !, % Evaluate Args to get Arg_vals. % Bind Arg_vals to Parameters to get Function_bindings. % Evaluate the function Body with respect to these Function_bindings. eval(Body, Classes, _, Function_bindings, _, Result).
The problem with the preceding is that we have lost the function definitions in Inst_vars_in. So our example won't work because the recursive call won't find a definition for factorial. So we will have to expand eval/6 once again to become eval/8.
eval(Expression, Classes_in, Classes_out, Inst_vars_in, Inst_vars_out, Function_vars_in, Function_vars_out, Result)
- Classes_in and Classes_out keep track of our class definitions.
- Inst_vars_in and Inst_vars_out, keep track of the instance variables of our current object. When we are at the top level, we are assuming we are working inside a default current object.
- Function_vars_in, and Function_vars_out keep track of parameters and local variables in the function we are evaluating, if any. If we are not evaluating a function, these will be [].
This means that when we evaluate a variable, e.g.,
eval(x, Classes, Classes, Inst_vars, Inst_vars, Function_vars, Function_vars, Result) :- ...
we have to look for x first in Function_vars (since function variables are more local than instance variables) and then in Inst_vars. The same consideration applies to assignment statements.
So here is the next draft of our function evaluation clause.
% In this version Function_vars are the local variables for the function we are currently executing, if any. % If we are not currently evaluating a function Function_vars will be []. eval(Function_call, Classes, Classes, Inst_vars_in, Inst_vars_out, Function_vars, Function_vars, Result) :- Function_call =.. [Function_name | Args], member(Function_name = (\Parameters -> Body), Inst_vars_in), !, % Evaluate Args to get Arg_vals % Bind Arg_vals to Parameters to get New_function_vars eval(Body, Classes, _, Inst_vars_in, Inst_vars_out, New_function_vars, _, Result).
[edit] Top level variable creation
Prior to this we have been assuming that new variables in our top level programs are created in the Bindings list. How should we understand those variables now that we have both an Instance_vars list and a Function_vars list? I suggest that the most convenient way to think about top level variables is to suppose that we are starting programs by executing what in Java would be a main() method. So variables at the top level should be added to the Function_vars list of the main() function, whose body we are executing. Since this is what will happen if we don't make any changes to our processing assumptions this turns out to be a convenient way of conceptualizing the top level, i.e., initial call to eval/8.
?- eval(Main_body, [], Classes_out, [], [], [], Function_vars_out, Result).
Notice that parameters 5 and 6 (Instance_vars_in and Instance_vars_out) are both []. That's because at the top level, we are executing in the default object, which has no instance variables.
