CMPUT 325 - Assignment #3

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 tommy@cs.ualberta.ca

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.

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,

|?-  double_me( [a, b, [c,d]], Y).
Y = [ [a,a], [b,b], [[c,d], [c,d]] ] ? ;
no

|?- double_me( [1, X], [Y, [2, Q]]).
Q = 2,
X = 2,
Y = [1,1] ? ;
no

|?- double_me( [1, X], [Y, [2, 3]]).
no

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

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.
Hence,

|?-  flatten( [a, b, [c,d]], Y).
Y = [ a, b, c, d] ? ;
no

|?- flatten( [a,[b],[[[c]]], [d,e]], X).
X = [a,b,c,d,e] ? ;
no

 non_nil_atom(X) :- X \== [ ],  atom(X).

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

Structure	Representation
	object(a). object(b). object(c). object(d). object(e). object(f). object(g). object(h). isa(a,c). isa(c,d). isa(d,b). isa(a,b). isa(b,e). isa(e,f). isa(f,g). isa(f,h).

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:

| ?- bft(a,X).

X = a ? ;

X = c ? ;

X = b ? ;

X = d ? ;

X = e ? ;

X = f ? ;

X = g ? ;

X = h ? ;

no

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:

| ?- findall(A, bft(a,A), X).

X = [a,c,b,d,e,f,g,h] ?

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.

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
 

PartA (10marks)  Write down the rules that state

• connected ports have the same value
• the output of an and-gate is 1 iff both of the inputs are 1; otherwise, the output is 0
• the output of an xor-gate is 1 iff exactly one of its two inputs is 1; otherwise, the output is 0
• the output of a not-gate (aka "inverter") is 1 iff its sole input is 0; otherwise, the output is 0
  (12/Nov: RG fixed.)

.

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

• ok    meaning the gate X is working correctly.
• flipped   meaning the gate X is working exactly wrong -- so a flipped or-gate behaves like an nor-gate, a flipped not-gate behaves like a wire, etc.
• stuck_high   meaning the gate X always outputs 1, independent of its input.