CMPUT 325 - Assignment #3

Due Date:    11:59pm, Tuesday  16 Nov 04   via the try program.

You should submit one file containing all your programs along with documentation. (Include answers to dry-lab questions as comments.) Your programs will be run against our solutions to provide feedback to your work. You may submit many versions; the last one before the deadline will be retained as your submission. (If you submit prior to the deadline, but plan to use one or two of your excused late days, you must tell the TAs to disregard your pre-deadline submission... or risk their wrath.) Questions about the try command can be directed to

Assignment Marks: There are a total of 75 points possible on this assignment.  It is worth 8% of the total course grade. Your programs must be readable and understandable as well as correct. You could lose up to 1/2 of the marks for bad style even if your programs are correct. See DocumentationGuidelines, TA'sGuidelines and programming style and marking guideline for an overview of the documentation, testing examples, etc. that we expect.

In general, your Prolog function may involve more than one clause, and may also involve new predicates.
You should also make sure you code is reasonably efficient -- or at least not incredibly inefficient.
As always, no line should be longer than 80 characters.

 #1 (10 marks)   Logic Programming: List Structure I

Define the   double_me( X, Y )  relation that  holds when Y is a list structure that contains the same basic structure, and elements, that appeared in X, but each entry in Y is a list containing two copies of the entry in X. Hence,

In general, your program should work even even if there are variables in either argument -- as suggested by the above examples. Be sure to specify if that is not true.

You should also discuss what the program will do if the inputs are not standard lists, etc.

 #2 (15 marks)   Logic Programming: List Structure II

Define the   flatten( X, Y )  relation that  holds when Y is a list structure that contains the same elements as X, in the same order, but as a list.

You may use the code
 non_nil_atom(X) :- X \== [ ],  atom(X).
to test if a component is an atom that is not [ ].  You may assume that this will "catch" the base case.
(Your code does not have to worry about numbers, etc.)

(The comments written for #1, about variables and error conditions, apply here as well.)

#3 (20 marks) Breadth-First Traversal

We can represent a hierarchical multiple inheritance structure as a collection of objects in Prolog, connected with "isa" relations. For instance:


Given such a Prolog representation of a structure, we would like to determine all the objects from which a given object can inherit properties. For the purposes of this question, we assume that this inheritance relationship is reflexive --- ie, an object can inherits properties from itself.

We assume that the inheritance structure is a directed acyclic graph (DAG). While it will not have cycles, there may still be multiple paths connecting a pair of nodes. In the example above, we can get from a to b via either  a->b  or  a->c->c->d->b.

Write a relation bft(X,Y) that holds when Y is an ancestor of X in the isa-based inheritance structure. If Y is not instantiated, then successive values for Y should be produced in a breadth-first order. You should produce each ancestor exactly once; no duplicates.

Using the structure shown above, bft(a,X) should return:

The results should be in exactly this order. For instance, even though we can reach both c and b directly from a, we choose to start with c, because the statement isa(a,c) comes before the rule isa(a,b) in the Prolog database.

bft(a,b) should return yes, as should bft(a,h).

bft(b,a) and bft(f,c) should return no.

For the purposes of this question, the predicate findall/3 may be useful. It is used as follows:

In this case findall/3 generates a list of all A that satisfy the relation bft(a,A), in the order they would be produced by standard Prolog backtracking.

Warning: While you may want to (and, in fact, should!) use your own objects and isa statements when testing your code, make sure to comment them out of your code before you submit. Otherwise, these statements may add structure to the hierarchy, which may cause your system to fail try's tests. If this happens, you will be penalized.

#4 (30 marks)   Logic Programming: Circuit Simulation

The following set of rules specify the components of a boolean circuit:

and_gate(X)  holds when X is an and-gate
or_gate(X)  holds when X is an or-gate
xor_gate(X)  holds when X is an xor-gate
not_gate(X)  holds when X is an not-gate

connected( P1, P2)   holds when the port P1 is connected to the port P2
value( Port,  V)   holds when the value of the port  Port is  V

input(X, Pj)   designates the j-th input port of the gate, X
output(X, Pj)   designates the j-th output port of the gate, X

(Note the latter 2 are terms, and not predicates. Hence, the proposition connected( output(a9, 1), input(x10, 2) ) means the first output of the device a9 is connected to the 2nd input of device x10. Also, value( output(a9, 1), 1) means the value of the the first output of the device a9 is 1.)
You may assume, throughout, that this is a "feedforward" (combinatorial) system; in particular, you will not have the output of one component feeding back to become its own input, etc.

PartA (10marks)  Write down the rules that state

PartB (10marks)
A Full-Adder is composed of a set of  2 AND-gates,  2 XOR gates, and 1 OR gate; see

For details, see website
(13/Nov: RG added figure.)

Write down the axioms that specify this device, called full_adder.
You should use the names on the figure: a1, a2, x1, x2, o1.
Note that full_adder has 3 input ports (the two bits to add, and a carry bit in) and 2 output ports (for the resulting value, and the carry bit out).

Use this description to compute what the output will be, for various different sets of input triples
--- eg, when the input is <1, 0, 1>,  as represented by the facts  
      value(input(full_adder, 1), 1) .
      value(input(full_adder, 2), 0) .
      value(input(full_adder, 3), 1) .

Note: you may want to use a single rule for each type of gate (eg, one rule for and-gates, another for or-gates, ...) and have a set of facts that succinctly describe the i/o behavior of correctly working and-gates, another set of facts describing the i/o behavior of correctly working or-gates, etc.

PartC (10marks)
Of course, this description assumed that the gates were all working correctly --
eg, an "ok" and-gate maps <1,1> to 1.
Add the new relation

state(X, S)  which holds when gate X is in state S, where S can be
Rewrite the program to incorporate the appropriate behaviour (be sure to remove the ones defined for PartA).
Now add  the axiom   state(X, ok).  and report the behaviour.
Use a set of test cases to demonstrate that your new system acts appropriately for the other assignment of states to components.