Courses/CS 332L/Fall 2007
From CSWiki
Contents |
[edit] Grading
- See Abbott
[edit] Resources
I didn't order a book for this class, but see Resources. There are lots of online Prolog tutorials.
Please download and install SWI-Prolog for use at home.
There will be a video each week.
[edit] 9/21. Week 1
[edit] Week 1. Homework
Due Sunday 9/23. The SWI-Prolog Online manual lists a number of predicates in its built-in library. Look at the lists module. Write your own versions of nextto/3, select/3, last/2. You may be able to find these online. The point is for you to understand them, not just to hand them in. Understanding means that if I ask you to do the same thing on a test, you will be able to do it.
Due Friday 9/28 before class. Write your own versions of append/3, delete/3, reverse/2. For append/3 write it only so that it "goes forward". That is, append/3 is defined:
append(?List1, ?List2, ?Result).
Just worry about this case.
append(+List1, +List2, ?Result).
[edit] 9/28. Week 2
See Data structures and unification.
[edit] Week 2. Homework
Recall that
?- differentiate(4*x^2 + 3*x + 5, x, R). R = 4* (2*x)+3
Let's add some rules to simplify this result.
Notice that 4 * (2 * x) is represented by the tree
*
/ \
4 *
/ \
2 x
To simplify a structure like this you will need a simplification rule that recognizes a structure something like this:
*
/ \
A *
/ \
B Y
In Prolog that would be represented by A * (B * Y), where A and B are both numbers. If you find a structure like that you want to do the following.
- Multiply A by B to get C
- Simplify Y to get Z
- Return as the result: C * Z.
In this case, that would convert 4 * (2 * x) into 8 * x, which is what we want.
Also, note that there are no rules for taking the derivative of sin and cos. Let's add some rules for these functions also.
Due Sunday 9/30. Add some deriv/3 and simplify/2 rules.
Due Friday 10/5. Add some more deriv/3 and simplify/2 rules.
[edit] 10/5. Week 3
See Peano arithmetic
[edit] Week 3. Homework
Due Sunday 10/7.
- Define number_to_peano/2.
- Define sum/3.
- Define difference/3. Explain how it works.
Due Friday 10/12 before class.
- Define eq/2, lt/2, and gt/2. These predicates should succeed if the relation hold. They should fail otherwise.
- Define product/3.
- Define divides/3.
- Optional. Define is_prime/1. is_prime(X) will succeed if X is prime. It will fail if X is not prime. The predicate is_prime/1 expects a Peano number as its argument.
?- is_prime(s(s(0))). Yes ?- is_prime(s(s(s(0)))). Yes ?- is_prime(s(s(s(s(0))))). No
Recall that not in prolog is \+. So you might define is_prime/1 as follows.
is_prime(X) :- \+ find_divisor(X, _).
The predicate find_divisor(X, Y) returns as Y some divisor of X (between 2 and X-1) if there is one. It fails if it can't find one. When called from is_prime/1, we don't care what the divisor is, only whether there is one — hence the underscore (don't care) as the second argument. If there is one, X is not prime.
find_divisor(X, Y) can use divides/3 to look for divisors.
An alternative way to accomplish the same thing without using negation is as follows.
is_prime(X) :- find_divisor(X, _), !, fail. is_prime(_).
Since the cut in the first clause comes after find_divisor(X, _), it says that if there is a divisor of X, then that clause applies. But then it says to fail. So if find_divisor(X, _) succeeds, is_prime(X) fails.
The second clause applies only if the first one doesn't. In that case, it simply succeeds since we already know that there aren't any divisors of X. In that case is_prime(_) succeeds.
[edit] 10/12. Week 4
[edit] Week 4. Homework
Note. The homework for this week may be included on the midterm. If you have questions about it, please use the discussion page to ask your questions.
[edit] Due Sunday 10/14.
- Modify the arithmetic function evaluator so that it can handle the built-in unary functions (like sqrt/1) and nullary functions (like pi/0) as well as binary functions.
- Hint. Define a predicate eval_exprs/3 that takes a list of arguments and returns a list of their values. It must also take Bindings as an argument. Use eval_exprs/3 to evaluate all the arguments to an expression at once.
?- eval_exprs([x, y, x+y], [x = 5, y = 3], Vals). Vals = [5, 3, 8]
- Why would this help? The line
Expr =.. [Op, E1, E2],from the following clause from the expression evaluator assumes that Expr has exactly two arguments
eval(Expr, Bindings, Result) :- % current_arithmetic_function/1 succeeds if Expr % unifies with a defined arithmetic function. current_arithmetic_function(Expr), Expr =.. [Op, E1, E2], !, eval(E1, Bindings, V1), eval(E2, Bindings, V2), perform_op(Op, V1, V2, Result).
- The homework problem asks you to allow any number of arguments. If you had eval_exprs/3, you could do that. You could replace
... Expr =.. [Op, E1, E2], eval(E1, Bindings, V1), eval(E2, Bindings, V2), ...
with something like this.
... Expr =.. [Op | Args], eval_exprs(Args, Bindings, Values) ...
- Make up and add your own arithmetic function(s). For example, you might make up a ternary function that returns the middle of three numbers. Or you might make up a unary function that returns the number if it is prime and the next higher prime if it isn't. Or you might simply make up some function of two arguments such as f(x, y) = x^2 + y + 5.
- To add an arithmetic function follow this example. To add the arithmetic function mean/2, include the following in your program file.
:- arithmetic_function(mean/2).
mean(A, B, C) :-
C is (A+B)/2.
- Don't forget the :- in front of arithmetic_function(mean/2).
- The predicate you define has 3 arguments. When called as an arithmetic function, it will be passed the first two arguments. Its job is to return the result in its third argument.
- You will then be able to call mean(x, y).
?- eval(mean(x, y), [y = 4, x = 3], X). X = 3.5
[edit] Due Friday 10/19 before class.
- Extend the expression evaluator so that it is able to evaluate relational functions (>, <, ==, etc.) and logical functions (and, or, exclusiveOr, negation, and conditional). Use the atoms true and false for logical values.
?- eval(x > 5, [x = 7], Result). Result = true ?- eval(x < 5, [x = 7], Result). Result = false
Note that Prolog evaluates relational expressions and either succeeds or fails.
?- 7 > 5. Yes ?- 5 > 7. No
- Part of your job is to convert success or failure into true and false.
- Extend the expression evaluator to allow assignments so that the list of bindings can be extended. This will require that eval/3 become eval/4 so that the list of Bindings can be both input and output.
% eval(+Expr, +Bindings_in, -Bindings_out, ?Result)
?- eval(x = 5, [], Bindings_out, Result). Bindings_out = [x = 5] Result = 5
If an assignment assigns a value to a variable that already has a value, delete the old value.
?- eval(x = 5, [y = 7, x = 4, z = 3], Bindings_out, Result). Bindings_out = [x = 5, y = 7, z = 3] Result = 5
- Recall that delete/3 deletes all instances of its second argument from the list which is its first argument, returning the result as its third argument. delete/3 succeeds whether or not its second argument belongs to the original list.
?- delete([a, b, a, c, d], a, X). X = [b, c, d] ?- delete([b, c, d], a, X). X = [b, c, d]
- Extend the expression evaluator to allow sequences of operations. Use the semi-colon (;) to separate statements. The Result should be the value of the final statement.
?- eval(z = 7; mean(y, z), [y = 4, x = 3], Bindings_out, Result). Bindings_out = [z=7, y=4, x=3], Result = 5.5
- Hint. When eval/4 is passed a sequence of expressions, it gets a tree as usual. In the previous example, the tree is as follows.
;
/ \
/ \
/ \
= mean
/ \ / \
z 7 y z
- As far as eval/4 is concerned, the relevant clause will look something like this.
eval(Stmt; Stmts, Bindings_in, Bindings_out, Result) :- !, eval(Stmt, ... ), eval(Stmts, ...).
- In class I said that (stmt1; stmt2; stmt3) parses like this: ((stmt1; stmt2); stmt3). In fact semi-colon associates to the right. So (stmt1; stmt2; stmt3) parses like this: (stmt1; (stmt2; stmt3)).
- As far as your program is concerned, it doesn't matter which way it parses. You will still process the statements from left to right.
[edit] 10/19. Week 5
"CS 332L. Midterm. Fall 2007" (doc) (upload page).
[edit] Week 5. Homework
The homework for the week is to do the midterm problems as homework problems. If you think you already did them correctly, there is nothing to do. If you're not sure about your answers, this is a chance to think about the problems without the stress of a doing them during a test.
Due Sunday 10/21. Problems 1, 2, and 3 from the midterm.
Due Friday 10/26 before class. Problems 4 and 5 from the midterm.
[edit] 10/26. Week 6
See Control structures.
[edit] Week 6. Homework
Due Sunday 10/28. Complete the code for if statements.
Due Friday 11/2 before class.
- Implement while statements.
- We currently use ; as a statement separator. Add a declaration of ; as a unary postfix operator so that it can also be used as a statement terminator as in the following.
?- eval(x = 5; y = 6;, [], Bindings_out, Result). Bindings_out = [y=6, x=5], Result = 6
[edit] 11/2. Week 7
"Spencer_s_Code" (txt) (upload page)
See Classes
[edit] Week 7. Homework
Due Sunday 11/4. Write/complete the code for Classes.
Due Friday 11/9 before class. Write code so that one can assign values to instance variables.
?- eval(y = 5; class c1(a, b); x = new c1(3+y, 4*y); x@a = 2*x@b, [], Classes_out, [], Bindings_out, Result). Classes_out = [c1 = class[a, b]] Bindings_out = [x = c1 [a = 40, b = 20], y = 5] Result = 40
Note that you will have to write yet another clause for eval/6 that recognizes when an assignment statement is assigning to an instance variable of a class instance.
eval(X@A = Expr, Classes_in, Classes_out, Bindings_in, Bindings_out, Result) :- ...
When we are doing assignment to an instance variable (i.e., assigning a value to the a instance variable of the object x) we don't want to find the current value of x@a. We want to find the value of Expr with respect to Bindings_in and assign that value to x@a. In this case, the values when the relevant call is made will look like this.
eval(x@a = 2*x@b, [c1 = class[a, b]], Classes_out, [x = c1 [a = 8, b = 20], y = 5], Bindings_out, Result)
You will want to evaluate x@b in the usual way, multiply it by 2 as part of the evaluation of the expression on the right hand side of an assignment statement, and then do an assignment to the instance variable a in the value of x, which is c1 [a = 8, b = 20]. This should produce c1 [a = 40, b = 20] as the new value for x. Don't forget to store that new x back into Bindings_out.
Be sure your code will work if the statement had been something like this.
x@y@z = 5.
You are storing a value for the z instance variable of the object which is the value of the y instance variable of x. In particular, what will your program do with the following?
?- eval(class c1(a); class c2(b); x = new c1(new c2(3)); x@a@b = 7, [], Classes_out, [], Bindings_out, Result).
The best strategy is to create an object with a generated name when you create a nested object. That would produce a result like this.
?- eval(class c1(a); class c2(b); x = new c1(new c2(3)); x@a@b = 7, [], Classes_out, [], Bindings_out, Result). Classes_out = [] Bindings_out = [anon1 = c2[b = 7], x = c1[a = anon1]] Result = 7
The alternative would be to create the nested object in place. This would yield this result.
?- eval(class c1(a); class c2(b); x = new c1(new c2(3)); x@a@b = 7, [], Classes_out, [], Bindings_out, Result). Classes_out = [] Bindings_out = [x = c1[a = c2[b = 7]]] Result = 7
There are two difficulties with this approach. First of all it is harder. More significantly, though, it doesn't deal properly with this situation.
?- eval(class c1(a); class c2(b); x = new c1(new c2(3)); y = x@a; y@b = 7, [], Classes_out, [], Bindings_out, Result). Classes_out = [] Bindings_out = [y = c2[b = 7], x = c1[a = c2[b = 3]]] Result = 7
Normally in object-oriented programming, an object is pointed to from a number of places. When you change an object, the actual object is changed and not just a copy of it as in this result. In this example, the copy of x@a that is assigned to y was changed but not the copy in x@a.
[edit] 11/9. Week 8
See Functions
[edit] Week 8. Homework
Due Sunday 11/11. Complete the code for functions and execute the factorial example.
Due Friday 11/16 before class. Ensure that your code works when a function is defined as a method within an instance of a class. Try it out by assigning a value to an instance variable from within a function/method. You might try something like this.
eval(class c1(a, b, getA, setA, getB, setB, sumAB);
x = new c1(0,
0,
\ -> a, % Defines getA(), which has no parameters.
\(newA) -> a=newA, % Defines setA(newA).
\ -> b, % Defines getB(), which has no parameters.
\(newB) -> b=newB, % Defines setB(newB).
\(z) -> getA() + getB() + z); % Defines sumAB(z). The final ')' closes the new c1( ).
x@setA(3);
x@setB(4);
y = x@sumAB(5),
[], Classes_out,
[], Inst_vars_out,
[], Function_vars_out,
Result).
To make it easy to run this, you might want your file to contain the program separately. For example:
test_program(
class c1(a, b, getA, setA, getB, setB, sumAB);
x = new c1(0,
0,
\ -> a, % Defines getA(), which has no parameters.
\(newA) -> a=newA, % Defines setA(newA).
\ -> b, % Defines getB(), which has no parameters.
\(newB) -> b=newB, % Defines setB(newB).
\(z) -> getA() + getB() + z); % Defines sumAB(z). The final ')' closes the new c1( ).
x@setA(3);
x@setB(4);
y = x@sumAB(5)).
Then on the command line write the following.
?- test_program(P), eval(P, [], Classes_out, [], Inst_vars_out, [], Function_vars_out, Result).
[edit] 11/16. Week 9
[edit] Persistent functions
Since one doesn't want to have to define the methods for a class every time the class is instantiated, let's create the convention that when a class is declared, initial values for its instance variables may be specified at the same time. Let's put that to work on a list class.
class list(head, tail, length = (\ -> 1 + (if (tail == null) then 0 else tail@length()))
In writing the preceding we are adopting a number of conventions.
- If an instance variable name is followed by
= <something>the<something>is the initial value of the instance variable. This implies that the number of arguments to a new statement needn't match the number of instance variables. So with this convention, it is ok to write the following.
list1 = new list(a, new list(b, null));
This should create the following lists.
list1 = list[head = a, tail = anon1, length = (\ -> .. )], anon1 = list[head = b, tail = null, length = (\ -> .. )]
- null is a reserved identifier(like true and false), which we are using for the null object. It also stands for the empty list.
- Every (actual) list object has at least one element. There are no explicit empty list objects other than null.
[edit] Other issues
- How to store objects (instances). is the convention className[list] ok or should it be className(tuple)?
- Anonymous identifiers. Use anon(X) and anon_counter(Y) in Inst_vars? A reasonable trick since can't get confused with user variable name.
- Persistent functions again. Store class declarations as having two components: instance variables and function declarations. Requires that one look up functions when called. Need to keep track of class of current object. Use same trick as above, e.g., store class(C) in Inst_vars? So instead of declaring:
class c1(a, b, getA, setA, getB, setB, sumAB)
one might declare
class c1((a, b), (getA= (\x -> body_a), setA=..., getB=..., setB=..., sumAB=...))
where a and b are the instance variables and getA, setA, getB, setB, and sumAB are the methods.
- Static/class-level methods and variables.
- Subclassing.
[edit] Week 9. Homework
Due Friday 11/30 before class.The homework for this week is to decide how you would modify extend our language framework. It is all due next Friday.
