MCS-287 Lab 4 (Spring 2007)

Due May 14, 2007

In this lab assignment, you will gain some experience using Prolog. Specifically, you will use the SWI-Prolog interpreter, which is available on the Linux systems in the MCS lab by executing the pl command in a terminal window. You can also download SWI-Prolog for your own computer.

Part 1: Defining Arithmetic from Scratch

If Prolog didn't already know how to do arithmetic operations, we could teach it about arithmetic starting from logical fundamentals. In this part of the lab, you will do exactly that. Because you are starting from scratch, you won't even use the built-in representation of numbers such as 0, 1, 2, and 3. Instead, you will use the atomic term z to represent zero and compound terms such as s(z), s(s(z)), and s(s(s(z))) to represent positive integers such as 1, 2, and 3. (The letter s is supposed to remind you of "successor." For example, s(z) represents the successor of zero.) In the remainder of this lab, the word "numeral" will be used to mean one of these terms. Be careful to keep this in mind; don't slip into using the conventional decimal representation. You are not to make any use of Prolog's built in arithmetic. For this part of the lab, you are to turn in Prolog definitions for the following predicates:

  1. First, now that you know what a numeral is, you should teach Prolog. Write a recursive definition of the predicate numeral such that numeral(X) is true if X is a numeral. You should test that it can correctly differentiate numerals from non-numerals. You should also test that it can be used to generate examples of numerals.

  2. Next, use the numeral predicate and recursion to define a three-place predicate addTo such that addTo(X,Y,Z) is true if X, Y, and Z are numerals such that the numbers represented by X and Y add up to the number represented by Z. For example, you could use your predicate to test that s(z) and s(s(z)) add up to s(s(s(z))), that is, that one and two add up to three. Test how flexible your predicate is. For example, it may be possible to use not only for yes-or-no queries, but also to do addition (find Z given specific values for X and Y), subtraction (find X, given specific values for Y and Z, or alternatively find Y, given specific values of X and Z), and even more exotic tasks such as finding all the different combinations of X and Y that add up to a particular value for Z.

  3. Use your addTo predicate to write a single rule defining the two-place le predicate, such that le(X,Y) is true if X and Y are numerals such that the number represented by X is less than or equal to the number represented by Y. With any luck, your predicate should be usable not only to test particular numerals, but also to find all the numerals less than or equal to a given numeral. You may even be able to use it to enumerate examples of numerals greater than or equal to a given numeral.

  4. Use your numeral and addTo predicates to write a recursive definition of a three-place mulTo predicate such that mulTo(X,Y,Z) is true if X, Y, and Z are numerals such that the numbers represented by X and Y multiply to form the number represented by Z. Test to see whether this predicate can be used as flexibly as your addTo predicate.

Part 2: Parsing and Checking Declarations

In this part of the lab, you will be working with the same grammar as in Lab 3:

<blck> ::= begin <stmts> end

<stmts> ::= <empty>
          | <stmt> <stmts>

<stmt> ::= declare <name>
         | use <name>
         | <blck>

You might notice that I am now using <blck> for the nonterminal that was <block> in Lab 3. This is because you will be defining a Prolog predicate to correspond with each of the grammar's nonterminals and SWI Prolog already has a predefined predicate named block.

Also, to make your life easier, let's change the specification of <name> so that any Prolog atom is a <name>.

This part of the lab is subdivided into four stages so that you will have less to work on at any one time and have a greater chance of success. When you have succeeded at a particular stage, be sure to save your program out under a different filename before starting work on the next stage. That way, if you aren't successful at the new stage, you will still have your working program from the previous stage. If you get the final stage to work, just turn in your code from that stage. If not, turn in the code from the most advanced stage that you got to work and, if you have an interesting but non-working attempt at the next stage, you can turn that in as well. Be sure to label what you turn in so that I know how to interpret it.

Stage 1: Checking whether the input can be parsed

Define a two-argument predicate blck such that blck(List1, List2) is provable if List1 starts with atoms that match the <blck> nonterminal and then continues with the atoms in List2. For example, the following query should produce "Yes":

blck([begin,declare,x,begin,use,x,end,end,something,else],[something,else]).

In this stage, you are not to worry about issues such as undeclared names and illegal redeclarations. The string of atoms should just be checked for conformity with the grammar. To help define the blck predicate, you should make use of two other analogous predicates, one for each of the other nonterminals in the grammar. The definitions should be mutually recursive in the same way that the grammar productions are.

Using the blck predicate, it is easy to write a predicate that can test whether a list of atoms is legal, that is, whether it is in the language described by the grammar. Namely, a legal list of atoms consists of a <blck> followed by nothing else:

legal(L) :- blck(L,[]).

Stage 2: Parsing the input into a syntax tree

One of the goals of parsing a language is to tell legal input strings from illegal ones, as in stage 1. However, there is another goal as well, which is to uncover the hierarchical structure that is implicit in the input. For that reason, modify all your predicates to take one more argument, which is to be used as in the following example:

?- legal([begin,declare,x,begin,use,x,declare,y,end,use,y,end],P).

P = [declare(x), [use(x), declare(y)], use(y)] 

Note that the string of atoms used in this example is treated as legal even though the use of the name y appears outside the scope of that name's declaration; just as in stage 1, we are ignoring this issue for the moment. That is about to change in stage 3.

Stage 3: Checking for undeclared names

Your goal for this stage is to make the preceding example produce "No" because the given list of atoms contains a use of an undeclared name. For lists without any uses of undeclared names, you should produce the same result as in the previous stage.

To do this, you should add two more arguments to each of the predicates that correspond to a nonterminal (that is, blck, stmts, and stmt). Each of these new arguments is a list of names. The first one is a list of the names that can legally be used in this portion of the input and the second one is a list of the names that can legally be used after it. For example, consider the following query:

?- stmt([use,y,moreinput],Tail,P,[x,y,z],Vars).

Tail = [moreinput],
P = use(y),
Vars = [x, y, z] 

This query is parsing a statement, which from the P variable's binding we can see is a use of the name y. This is legal because y is one of the three names that the query specified could legally be used. (The other two were x and z.) The fact that Vars is bound to the exact same list of three names reflects the fact that the same names are legal for use after this statement as were legal for use before it. Here are two further examples:

?- stmt([use,w,moreinput],Tail,P,[x,y,z],Vars).

No
?- stmt([declare,w,moreinput],Tail,P,[x,y,z],Vars).

Tail = [moreinput],
P = declare(w),
Vars = [w, x, y, z] 

The first of these two queries returns "No" because the list of atoms now does not start with a legal <stmt>. Although the first two atoms are legal so far as the grammar goes, the use of w is now recognized as illegal because this name is not in the list of names that may legally be used. In the second example, you can see how the list of legal names is built up; one more name is legal after the declaration of w.

After modifying the three predicates for the three nonterminals, you will also have to make a minor modification to the legal predicate:

legal(L,P) :- blck(L,[],P,[],_).

With this definition, you should now be able to execute queries such as these:

?- legal([begin,declare,x,begin,use,x,declare,y,end,use,y,end],P).

No
?- legal([begin,declare,x,begin,use,x,declare,y,end,use,x,end],P).

P = [declare(x), [use(x), declare(y)], use(x)] 

Stage 4: Checking for illegal redeclarations

Finally, you should also reject any input that contains a redeclaration of a name that has already been declared at the same nesting level, while allowing redeclaration of names defined in outer levels.

You can do this by adding two more arguments to each of the nonterminal predicates. As in the previous stage, each is a list of names, one for the situation before the current portion of the input and one for the situation afterward. However, this time the lists should contain those names that would be illegal to declare at the current nesting level because they are already declared at this level.