Courses/CS 332L/Control structures
From CSWiki
We now have expression evaluation, variable storage and retrieval, and statement sequences. The next step is to add control structures: if and while.
Contents |
[edit] if statements
Our objective is to produce results similar to the following.
?- eval(if(x == 5) then y = 6 else z = 7, [y = 4, x = 3], Bindings_out, Result). Bindings_out = [z=7, y=4, x=3], Result = 7
and
?- eval(if (x == 3) then y = 6 else z = 7, [y = 4, x = 3], Bindings_out, Result). Bindings_out = [y=6, x=3], Result = 6
There are two issues to worry about.
- How are these structures parsed? What sort of parse tree is produced?
- How are the parse tree elements executed?
[edit] Prolog operators
We would like
if(x == 5) then y = 6 else z = 7
to produce a parse tree like this.
then
/ \
/ \
/ \
/ \
if else
| / \
| / \
= = =
/ \ / \ / \
/ \ / \ / \
x 5 y 6 z 7
Look at 4.24 Operators in the online manual for information about operators. The table on that page shows the pre-defined operators. To understand this table, let's take the line
400 yfx *, /, //, rdiv, <<, >>, mod, rem
as an example.
This line means that
*, /, //, rdiv, <<, >>, mod, rem
are all defined as binary operators. That means that you can write something like
?- X = 4 mod z. X = 4 mod z
In other words, mod is an operator. It causes a binary tree to be built
mod
/ \
4 z
As a result of the statement above, X refers to that tree. Note that you would get an error message if you wrote the following.
?- X is 4 mod z. ERROR: is/2: Arithmetic: `z/0' is not a function
is/2 asks for the tree 4 mod z to be evaluated. But it can't be evaluated because z isn't a number.
The number 400 at the start of the line is the precedence of these operators. The higher the precedence, the less tightly an operator binds. The reason x + y * z parses like x + (y * z) is because * has precedence 400 and + has precedence 500. You can test this as follows.
?- x + y * z = A + B. A = x B = y*z
This shows that the top-level operator in x + y * z is +.
?- x + y * z = A * B. No
This shows that the top level operator in x + y * z is not *. In other words, the tree that is built from x + y * z is the following.
+
/ \
x *
/ \
y z
It unifies with
+
/ \
A B
It doesn't unify with
*
/ \
A B
The notation yfx in our example line means (a) that * is a binary operator and (b) that it associates to the left.
Unary operators are shown with either an x or a y on either side of f but not both. Note that + and - are declared to be both binary and unary.
A y means that the operator associates to that side. An x means that it does not associate to that side. (Operators can't associate to both sides. So there is never more than one y. There may be no y's.) The fact that * associates to the left means that x * y * z parses as (x * y) * z. In other words, x * y * z results in this tree.
*
/ \
* z
/ \
x y
You can test this as follows.
?- x * y * z = A * B. A = x*y B = z
[edit] Defining if, then, and else as operators
The predicate op/3 allows users to define (or redefine) operators. Again, see Operators.
We are going to define if, then, and else as operators.
Since ; has precedence 1100, and we want if, then, and else to bind more loosely than ; we will define them with a higher precedence.
We want these declarations to be visible outside the file in which they are defined. SWI prolog has made a convention that operator declarations are only visible within the file in which they are defined unless they are explicitly exported using the module/2 predicate. So we will start our file as follows.
:- module(ifThenElse, [eval/4,
op(1150, fx, if),
op(1150, xfx, else),
op(1175, xfx, then)]).
After loading the file into Prolog, we might test it out as follows.
?- if (x == 2) = A. ERROR: toplevel: Undefined procedure: (if)/1 (DWIM could not correct goal)
Do you know why the error message was generated? (Hint: What is the precedence of if and what is the precedence of = ?)
The tree that was generated was the following, as if the input had been if ((x == 2) = A).
if
|
=
/ \
== A
/\
x 2
The error message said that the system didn't know how to execute if((x==2)=A). But that's not what we wanted anyway. We wanted the tree
=
/ \
if A
|
==
/\
x 2
To get that we write the following.
?- (if (x == 2)) = A. A = (if x==2)
We can test the parsing of the entire construct as follows.
?- (if (x == 2) then y else z) = (A then B). A = (if x==2), B = (y else z)
Note the extra parentheses in the input to ensure that = is the main operator.
?- (if(x == 5) then y = 6 else z = 7) = (if A then B else C). A = (x==5), B = (y=6), C = (z=7)
[edit] Evaluating an if statement
Now that we can write if statements, we have to think about evaluating them. Presumably we will want a pair of clauses something like this.
% If the condition holds, then the value of the if statement is the value of the then part. eval(if Condition then Then_Part else _Else_Part, Bindings_in, Bindings_out, Result) :- % We are assuming no side effects in evaluating the condition. eval(Condition, Bindings_in, _, true), !, eval(Then_Part, Bindings_in, Bindings_out, Result). % If the condition doesn't hold, then the value of the if statement is the value of the else part. eval(if Condition then _Then_Part else Else_Part, Bindings_in, Bindings_out, Result) :- % We don't really have to evaluate the Condition again. % We know it isn't true, or we wouldn't be here. % We are assuming no side effects in evaluating the condition. eval(Condition, Bindings_in, _, false), !, eval(Else_Part, Bindings_in, Bindings_out, Result).
[edit] Evaluating a while statement
Evaluating while statements is like evaluating if statements. First we have to declare the appropriate keywords as operators. Then we have to determine how to evaluate the statement.
The strategy for evaluating a while statement relies on recursion and on the fact that
while (Condition) do Body
is the same as
if (Condition) then Body; (while (Condition) do Body) else <null>
In other words, to evaluate
while (Condition) do Body
evaluate the Condition. If it's true, evaluate the Body and call
while (Condition) do Body
recursively.
So you might have an eval/4 clause like this.
eval(while (Condition) do Body, Bindings_in, Bindings_out, Result) :-
!,
eval(if (Condition) then Body; (while (Condition) do Body) else null,
Bindings_in, Bindings_out, Result).
You will have to define the null statement as a statement that does nothing. For example,
eval(null, Bindings, Bindings, null) :- !.
