Courses/CS 332L/Fall 2006

From CSWiki

Jump to: navigation, search

Contents

[edit] Grading and Final Exam Schedule

[edit] Resources

[edit] Prolog Interpreter

[edit] Primary Prolog Tutorial

also wikipedia's Prolog page

[edit] Other Prolog Tutorials listed alphabetically by author

[edit] User Pages

Ron Redden

SmboInc

Juan Gallaga

Chao Lin Chu

Carlo Marini

Steven Martin

Daniel Germann

Chia-Yao Chien

Yuet-Chi Lee

Guillermo

Edmond Kong

Lalantha Sath

Rubic

Lymon S.

Mads Moeller

Eugene Flock

[edit] Sept 22 (Week 1)

Fisher's tutorial, sections 1, 2.1, 2.2, and 2.7.

[edit] Homework

  • Lab
    • Exercises: 2.2.1, 2.2.2.
  • Tuesday
    • Create a user page, including your email address.
    • Introduce yourself on the discussion page.
    • Exercises: 2.7.1, 2.7.2, 2.7.3.
  • Thursday
    • Exercises: 2.7.4, 2.7.5, 2.7.6, 2.7.7, 2.7.8, 2.7.10. (2.7.9 is optional.)

[edit] Sept 29 (Week 2)

Fisher's tutorial, continue with section 2.7.

Look at the following definition of the append predicate. 

append([],X,X).
append([X|Y],Z,[X|W]) :- append(Y,Z,W).

In this version I reversed the order of the clauses from that in the tutorial.

It is the closest thing to magic you will see in software—at least in anything this small.

  • Does this change make any differenc in which inputs produce which outputs?
    • No, any input -> output that occurs in one version will occur in the other. The two clauses are mutually exclusive since one requires the first argument to be the empty list; the other requires that it not be the empty list. That is append(L1, L2, L3) will produce the same result with the clauses in either order as long as L1 is not a variable.

BUT consider the append/3 magic. This is executed with the clauses in the order shown above. 

?- append(X, Y, [a, b, c]).

X = []
Y = [a, b, c] ;

X = [a]
Y = [b, c] ;

X = [a, b]
Y = [c] ;

X = [a, b, c]
Y = [] ;

How does this happen? Since X and Y are variables, the first clause applies initially. But if we backtrack (;) the first call will use the second clause. If you trace it through, it will lead to the second result. If you backtrack again, you will get the third resul.

But what happens if you reverse the order of the clauses? 

append([X|Y],Z,[X|W]) :- append(Y,Z,W).
append([],X,X).

?- append(X, Y, [a, b, c]).

X = [a, b, c]
Y = [] ;

X = [a, b]
Y = [c] ;

X = [a]
Y = [b, c] ;

X = []
Y = [a, b, c] ;

In this case, the first call uses the new first clause. This binds X to a and leads to the recursive call append(Y, Z, [b, c]). This will eventually produce the first output. On backtracking, we will get the second output and then the third. So the only difference is that the results are generated in a different order. As far as we are concerned, this doesn't matter.

For the most part, we won't be using this prolog magic. But it's worth knowing that it's possible. The way to think of append/3 is as follows.

append(L1, L2, L3) is true if it is possible to find values for L1, L2, and L3, such that when you append L2 to L1, you get L3. It doesn't matter which of the three variables are instantiated initially as long as the complete list is specified in one way or another. (They it with three variables and see what happpens.)

[edit] Homework 2

We are trying to define and manipulate a set of objects using a list. Let us consider the following list. 

[ [car1, [color, red], [make,  toyota], [model, camry], [year, 2000]],
  [car2 ,[color, white], [make,  dodge], [model, neon]],
  [book1, [title, prolog], [author, mellish], [price, regular]]
]

An object has an object name, attributes and values associated with the attributes. The list above includes three objects named car1, car2, and book1. car1 object has four attributes that are color, make, model, and year, and associated values that are red, toyota, camry, and 2000. car2 object has three attributes (color, make, model) and associated values (white, dodge, neon). book1 has three attributes(title, author, and price) and associated values (prolog, mellish, regular).

Assume that a list L can contain an arbitrary number of objects and each object can contain an arbitrary number of attributes.

[edit] Lab 2

1. Define an objs/2 predicate that takes a list and returns how many objects are defined in the list in the second argument. Assume that L is the list specified above. For test purposes, replace L with the actual list. Look back at factorial to see how to do arithmetic. You have to use is/2. (You may not use a length/2 predicate unless you write your own.) 

?- objs(L, N).
N=3.

2. (unrelated) Write a combine1/3 predicate that takes three lists as arguments and combines the elements of the first two lists into the third as follows: 

?- combine1([a,b,c],[1,2,3],X).
X = [a,1,b,2,c,3]

?- combine1([foo,bar,yip,yup],[glub,glab,glib,glob],Result).
Result = [foo,glub,bar,glab,yip,glib,yup,glob]

[edit] Tuesday 2

1. Define an attrs/3 predicate that takes a list and an object name and returns how many attributes are defined for the object in the list. Assume that L is the list specified above. For test purposes, replace L with the actual list. (You may not use a length/2 predicate unless you write your own.) 

?- attrs(L, car1, N).
N=4. 

?-  attrs(L, car3, N).
no

2. (unrelated) Write a zip/3 predicate that takes three lists as arguments and combines the elements of the first two lists into the third as follows: 

?- zip([a,b,c],[1,2,3],X).
X = [[a,1],[b,2],[c,3]]

?- zip([foo,bar,yip,yup],[glub,glab,glib,glob],Result).
Result = [[foo,glub],[bar,glab],[yip,glib],[yup,glob]]

It should also work to unzip a list. 

?- zip(A, B, [[foo,glub],[bar,glab],[yip,glib],[yup,glob]]
A = [foo,bar,yip,yup]
B = [glub,glab,glib,glob]

3. Write a smallest/2 predicate that takes a list of integers and returns the smallest. 

?- smallest([3, 2, 7, 1, 4], X).

X = 1
?- smallest([3, 2, 7, 1, 4], 3).
No.

[edit] Thursday 2

1. Define a search/4 predicate that takes a list, an object name and an attribute name and returns the value of attribute of the object in the list L. Assume that L is the list specified above. For test purposes, replace L with the actual list. 

?- search (L, car1, year, X).
X=2000.

2. (unrelated) Write a combine3/3 predicate that takes three lists as arguments and combines the elements of the first two lists into the third as follows: 

?- combine3([a,b,c],[1,2,3],X).
X = [join(a,1),join(b,2),join(c,3)]

?- combine3([foo,bar,yip,yup],[glub,glab,glib,glob],R).
R = [join(foo,glub),join(bar,glab),join(yip,glib),join(yup,glob)]

3. Write a predicate nth/3 that finds the n'th element of a list. The first element in the list is number 1. 

   ?- nth([a,b,c,d,e], 3, X).
   X = c
   ?- nth([a,b,c,d,e], 9, X).
   No

[edit] Oct 6 (Week 3)

[edit] Notes 3

[edit] Homework 3

In all these assignments use the cut in each clause to indicate where the end of the guard is. Even if the guard is only in the head, put the cut at the start of the body. Do so even if the rest of the body is null. That is, it is ok to write a clause that looks like this. 

p( … ) :- !.

[edit] Lab 3

Write a fibonacci/2 predicate.

  • fib1(N, Fib). This version uses naive recursion (twice) to compute Fib as the Nth fibonacci number. 
fib(N) = fib(n-1) + fib(n-2)

[edit] Tues 3

  • Write a second version of fibonacce: 
fib2(N, Fib) :- fib(1, O, 1, N, Fib).
It's your job to define fib/5, which computes fib from the bottom up rather than from the top down. In fib/5 the first argument is a counter. The second and third arguments are the n-1 and nth fibonacci number. The fourth argument is the initial input, i.e., which fibonacci number you want. The last argument is the answer when you get to it. Assume you are looking for the 6th fibonacci number. The sequence of calls would look like this. 
?- fib2(6, F)
~> fib(1, 0, 1, 6, F)
~> fib(2, 1, 1, 6, F)
~> fib(3, 1, 2, 6, F)
~> fib(4, 2, 3, 6, F)
~> fib(5, 3, 5, 6, F)
~> fib(6, 5, 8, 6, 8)
  • Write a predicate that returns the sum of a list of numbers: 
sum(List, Sum).

Can you do it two ways, both top-down and bottom-up? (Added Oct 13.)

  • Extend Bartak's date data structure and predicates to deal with time (just hours and minutes). Include a predicate like tomorrow that finds the nextMinute. 
:- nextMinute(DateTime, NewDateTime).
nextMinute/2 should make sure the hour position is no more than 23 and the minute position is no more than 59. (Use military time: hours range from 0 .. 23.)

[edit] Thurs 3

  • Write max/3, which returns in its third argument the greater of the first two. 
?- max(3, 4, X).
x = 4

?- max(4, 3, X).
X = 4

?- max(3, 4, 3).
No
Be careful about the last example.
  • Rewrite the search/4 predicate from last week using a more sophisticated data structure. Instead of 
Objects = 
[ [car1,  [color, red], [make,  toyota], [model, camry], [year, 2000]],
  [car2,  [color, white], [make,  dodge], [model, neon]],
  [book1, [title, prolog], [author, mellish], [price, regular]]
]

assume that the data structure looks like this. 

Objects = 
[ object(car1,  [attr(color, red), attr(make,  toyota), attr(model, camry), attr(year, 2000)]),
  object(car2,  [attr(color, white), attr(make,  dodge), attr(model, neon)]),
  object(book1, [attr(title, prolog), attr(author, mellish), attr(price, regular)])
]

That is, Objects is a list. Each element of the list is a data structure of the form 

object(Name, Attr_List)

where Attr_List is a list of attributes, each of which looks like 

attr(attr_name, value)
  • Write a predicate that adds or modifies such a data structure. 
modify(Objects, Name, Attr, Value, New_Objects).
    • If the Name object already has an attribute Attr, replace its current value with Value.
    • If Name does not have an atrribute Attr, add a new attr(Attr, Value) element to its Attributes list.
    • If there is no Name object, create one with an Attributes list containing a single value attr(Attr, Value).
    • New_Objects is returned as the modified data structure. There is no requirement that the order of elements in either the top-level of the Attribues list be preserved.

Here is a solution to the modify/5 problem. 

database([object(car1, [attr(color,red),
                        attr(make,toyota),
                        attr(model,camry),
                        attr(year,2000)]),
          object(car2, [attr(color,white),
                        attr(make,dodge),
                        attr(model,neon)]),
          object(book1,[attr(title,prolog),
                        attr(author,mellish),
                        attr(price,regular)])]).
 
modify(Objects, Name, Attr, Value, New_Objects) :- 
	s3(Objects, Name, Attr,Value,New_Objects).

s3([object(O, Attrs )| Rs],O,Y,Z,[object(O,Q)| Rs]) :- 
	!,
	f3(Attrs,Y,Z,Q).
s3([object(O, Attrs)| Rs],X,Y,Z, [object(O,Attrs)| Q]) :- 
	O \= X,
	!,
	s3(Rs,X,Y,Z,Q).
s3([],X,Y,Z,[object(X, [attr(Y,Z)])]) :- !.

f3([attr(N, _)| R],N,Z,[attr(N,Z)| R]) :- !.
f3([attr(N, V)| R],Y,Z,[attr(N,V) | Q) :- 
	N \= Y, 
	!, 
	f3(R,Y,Z,Q).
f3([],Y,Z,[attr(Y, Z)]) :- !.

?- database(DB), modify(DB, car1, color, blue, DB1).

DB = [object(car1,  [attr(color, red), 
                     attr(make, toyota), 
                     attr(model, camry), 
                     attr(year, 2000)]), 
      object(car2,  [attr(color, white), 
                     attr(make, dodge),
                     attr(model, neon)]), 
      object(book1, [attr(title, prolog), 
                     attr(author, mellish),
                     attr(price, regular)])]

DB1 = [object(car1,  [attr(color, blue), 
                      attr(make, toyota), 
                      attr(model, camry), 
                      attr(year, 2000)]), 
       object(car2,  [attr(color, white), 
                      attr(make, dodge), 
                      attr(model, neon)]), 
       object(book1, [attr(title, prolog), 
                      attr(author, mellish), 
                      attr(price, regular)])]

[edit] Oct 13 (Week 4)

[edit] Quiz next week.

[edit] Problems from Werner Hett's problem repository

[edit] Lists

  • Flatten a nested list structure.

Transform a list, folding lists as elements into a `flat' list by replacing each list with its elements (recursively). 

   Example:
   ?- my_flatten([a, [b, [c, d], e]], X).
   X = [a, b, c, d, e]

Hint: Use the predefined predicates is_list/1 and append/3

  • Eliminate consecutive duplicates of list elements.

If a list contains repeated elements they should be replaced with a single copy of the element. The order of the elements should not be changed. 

   Example:
   ?- compress([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).
   X = [a,b,c,a,d,e]
  • Pack consecutive duplicates of list elements into sublists.

If a list contains repeated elements they should be placed in separate sublists. 

   Example:
   ?- pack([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).
   X = [[a,a,a,a],[b],[c,c],[a,a],[d],[e,e,e,e]]
  • Run-length encoding of a list.

Use the result of the previous problem to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as terms [N,E] where N is the number of duplicates of the element E. 

   Example:
   ?- encode([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).
   X = [[4,a],[1,b],[2,c],[2,a],[1,d][4,e]]
  • Decode a run-length encoded list.

Given a run-length code list generated as specified in problem P11. Construct its uncompressed version.

  • Run-length encoding of a list (direct solution).

Implement the so-called run-length encoding data compression method directly. I.e. don't explicitly create the sublists containing the duplicates as above but only count them. 

   Example:
   ?- encode_direct([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).
   X = [[4,a],[b],[2,c],[2,a],[d],[4,e]]

[edit] Binary trees

http://www.hta-bi.bfh.ch/~hew/informatik3/prolog/p-99/p67.gif

A binary tree is either empty or it is composed of a root element and two successors, which are binary trees themselves.

In Prolog we represent the empty tree by the atom 'nil' and the non-empty tree by the term t(L, X, R), where X denotes the root node and L and R denote the left and right subtree, respectively. The example tree to the right is represented by the following Prolog term.

T1 = t( t( t(nil, d, nil), b, t(nil, e, nil) ), a, t( nil, c, t( t(nil, g, nil), f, nil ) ) ) 

T1 = t(
       t(
         t(nil, d, nil), 
         b, 
         t(nil, e, nil)
        ), 
       a, 
       t(
         nil, 
         c, 
         t(
           t(nil, g, nil), 
           f, 
           nil
          )
         )
        )


Other examples are a binary tree that consists of a root node only:

T2 = t(nil, a, nil) or an empty binary tree: T3 = nil

  • Check whether a given term represents a binary tree

Write a predicate istree/1 which succeeds if and only if its argument is a Prolog term representing a binary tree. 

   Example:
   ?- istree(t(t(b, nil, nil), a, nil)).
   Yes
   ?- istree(t(t(nil, b, nil), a)).
   No
  • Symmetric binary trees

Let us call a binary tree symmetric if you can draw a vertical line through the root node and then the right subtree is the mirror image of the left subtree. Write a predicate symmetric/1 to check whether a given binary tree is symmetric. Hint: Write a predicate mirror/2 first to check whether one tree is the mirror image of another.

  • Binary search trees (dictionaries)

Write a predicate to construct a binary search tree from a list of integer numbers. 

   Example:
   ?- construct([3,2,5,7,1], T).
   T = t(t(t(nil, 1, nil), 2, nil), 3, t(nil, 5, t(nil, 7, nil)))
  • Count the leaves of a binary tree

A leaf is a node with no successors. Write a predicate count_leaves/2 to count them. 

   count_leaves(T, N) :-  
   % the binary tree T has N leaves
  • Collect the leaves of a binary tree in a list

A leaf is a node with no successors. Write a predicate leaves/2 to collect them in a list. 

   leaves(T, S) 
   % S is the list of all leaves of the binary tree T
  • Collect the internal nodes of a binary tree in a list

An internal node of a binary tree has at least one non-empty successors. Write a predicate internals/2 to collect them in a list. 

   internals(T, S) :-   
   % S is the list of internal nodes of the binary tree T.
  • Collect the nodes at a given level in a list

A node of a binary tree is at level N if the path from the root to the node has length N-1. The root node is at level 1. Write a predicate atlevel/3 to collect all nodes at a given level in a list. 

   atlevel(T, L, S) :- 
   % S is the list of nodes of the binary tree T at level L

[edit] Homework 4

[edit] Lab

Drop every N'th element from a list. 

   Example:
   ?- drop([a,b,c,d,e,f,g,h,i,k],3,X).
   X = [a,b,d,e,g,h,k]

Hint. Write code that copies a list but skips every Nth element. The calls will look something like this. 

?- drop(Input, 3, Output)
~> drop([A | As], 1, 3, Output)
~> drop([B | Bs], 2, 3, Output1), where Output = [A | Output1] (Copy the A.)
~> drop([C | Cs], 3, 3, Output2), where Output1 = [B | Output2] (Copy the B.)
~> drop([D | Ds], 1, 3, Output3), where Output2 = Output3  (Drop the C.)
~> drop([E | Es], 2, 3, Output4), where Output3 = [D | Output4]. (Copy the D.)

Write a pre_order tree traversal. 

   Example:
   ?- pre_order(t(t(nil, b, t(nil, c, nil)), a, t(t(nil, d, nil), e, nil)), P).
   P = [a, b, c, e, d]

[edit] Tues

Split a list into two parts; the length of the first part is given. Do not use any predefined predicates. 

   Example:
   ?- split([a,b,c,d,e,f,g,h,i,k],3,L1,L2).
   L1 = [a,b,c]
   L2 = [d,e,f,g,h,i,k]

Write in_order and post_order tree traversals. 

   Example:
   ?- in_order(t(t(nil, b, t(nil, c, nil)), a, t(t(nil, d, nil), e, nil)), P).
   P = [b, c, a, d, e]

   ?- post_order(t(t(nil, b, t(nil, c, nil)), a, t(t(nil, d, nil), e, nil)), P).
   P = [c, b, d, e, a]

[edit] Thurs

Extract a slice from a list. Given two indices, I and K, the slice is the list containing the elements between the I'th and K'th element of the original list (both limits included). Start counting the elements with 1. 

   Example:
   ?- slice([a,b,c,d,e,f,g,h,i,k], 3, 7, L).
   X = [c,d,e,f,g]

Write an arithmetic expression evaluator for arithmetic expressions represented as binary trees. 

   Example
   ?- eval(t(t(3, +, 4), *, t(t(7, *, 3), -, 1)), Val).
   Val = 140

Hint 1. 

?- T1 = t(3, +, 4), T2 = t(A, B, C), T1 = T2, Z is A + C.
T1 = t(3, +, 4)
T2 = t(3, +, 4)
A = 3
B = +
C = 4
Z = 7

Hint 2. To evaluate t(Left, Operator, Right), evaluate Left getting a value of LeftVal, evaluate Right, getting a value of RightVal, perform the operation indicated by Operator on the two values: LeftVal Operator RightVal.

[edit] Oct 20 (Week 5)

[edit] Homework 5

Here is an answer that uses =.. (univ). 

eval(X, X) :- number(X), !.
eval(Expr, Result) :-
  Expr =.. [Op, Left, Right],
  eval(Left, L),
  eval(Right, R),
  Expr1 =.. [Op, L, R],
  perform(Expr1, Result).

perform(Expr, Result) :- Result is Expr.
  • Thursday. Create a course page for yourself and list all the homework problems that you presented in class. To create your course page enter [[/your name/]] in the list of course pages. Entering [[/your name/]] will create a page "your name" as a subpage of this page.

[edit] Oct 27 (Week 6)

[edit] Operators

Open the SWI-Prolog online help manual. Look for op/3. You will find this description.

op(+Precedence, +Type, :Name).
Declare Name to be an operator of type Type with precedence Precedence. Name can also be a list of names, in which case all elements of the list are declared to be identical operators. Precedence is an integer between 0 and 1200. Precedence 0 removes the declaration. Type is one of: xf, yf, xfx, xfy, yfx, yfy, fy or fx. The `f' indicates the position of the functor, while x and y indicate the position of the arguments. `y' should be interpreted as ``on this position a term with precedence lower or equal to the precedence of the functor should occur. For `x' the precedence of the argument must be strictly lower. The precedence of a term is 0, unless its principal functor is an operator, in which case the precedence is the precedence of this operator. A term enclosed in brackets (...) has precedence 0.

The predefined operators are shown in table 4.1. Note that all operators can be redefined by the user. 

    -------------------------------------------------------------- 
    | 1200 | xfx | -->, :-                                        |
    | 1200 |  fx | :-, ?-                                         |
    | 1150 |  fx | dynamic,  discontiguous, initialization,  mod- |
    |      |     | ule_transparent,    multifile,    thread_local,|
    |      |     | volatile                                       |
    | 1100 | xfy | ;, |                                           |
    | 1050 | xfy | ->, op*->                                      |
    | 1000 | xfy | ,                                              |
    |  954 | xfy | \                                              |
    |  900 |  fy | \+                                             |
    |  900 |  fx | ~                                              |
    |  700 | xfx | <, =, =.., =@=,  =:=, =<, ==, =\=,  >, >=, @<, |
    |      |     | @=<, @>, @>=, \=, \==, is                      |
    |  600 | xfy | :                                              |
    |  500 | yfx | +, -, /\, \/, xor                              |
    |  500 |  fx | +, -, ?, \                                     |
    |  400 | yfx | *, /, //, rdiv, <<, >>, mod, rem               |
    |  200 | xfx | **                                             |
    |  200 | xfy | ^                                              |
    -------------------------------------------------------------- 
                     Table 4.1:  System operators

[edit] Symbolic differentiation

[edit] Homework 6

Lab. Let's represent numbers as follows. 

0 - 0
s(0) - 1
s(s(0)) - 2
s(s(s(0))) - 3
…

Write two prolog program to convert back and forth between these notations. 

Example
?- successorToNumber(s(s(s(0))), X).
X = 3.

?- numberToSuccessor(3, X).
X = s(s(s(0)))

Tuesday. Write a prolog program to do arithmetic in the successor notation. 

Example
?- evalSuccessor(s(s(0)) + s(s(s(0))), X).
X = s(s(s(s(s(0)))))
?- evalSuccessor(s(s(0)) * s(s(s(0))), X).
X = s(s(s(s(s(s(0))))))

Note: Don't convert from successor notation to integers. Do the arithmetic using the successor notation directly. But your program should be able to do the following. 

?- numberToSuccessor(3, S3), 
   numberToSuccessor(2, S2), 
   evalSuccessor(S3 * S2, S6), 
   successorToNumber(S6, X).
S3 = s(s(s(0)))
S2 = s(s(0))
S6 = s(s(s(s(s(s(0))))))
X = 6

Thursday.

1. Write a program to evaluate logical expressions. Let 

"+" mean "or" 
"*" mean "and" 
"->" mean "conditional"
"-" mean "not."

Note that "->" is defined as an operator. (See table above.) Its precedence is such that it parses correctly for our purposes.

[Note: See Negation about the negation operator (-).]

So 

x -> (y + z) * -(w + u)

means 

if x then (y or z) and not (w or u)

If x = true, y = true, z = false, w = true, u = false, this would evaluate as follows. 

true -> (true + false) * -(true + false)
~> true -> true * -(true)
~> true -> true * false
~> true -> false
~> false

Your program should be able to take a logical expression and returns its truth value. 

Example
?- evalLogic(true -> (true + false) * -(true + false), X).
X = false

2. Modify this program so that the logical expression contains variables whose values are given in a second argument. Note that the variables are atoms; they are not Prolog variables. 

Example
?- evalLogic(x -> (y + z) * -(y + z), [x: true, y: true, z: false], X).
X = false

?- evalLogic(x -> (y + z) * -(y + -z), [x: true, y: false, z: true], X).
X = true

Note that ":" is defined as an operator. (See table above.)

[edit] Nov 3 (Week 7)

[edit] Homework 7

[edit] Lab.

Extend the interpreter in Notes 7 to include an if-then (i.e., no else part) construct.

[edit] Tuesday.

A. Extend the previous result to include a repeat-until construct. It should work as follows. 

repeat(Body, Condition)

Repeatedly execute the Body until the Condition is true. 
Execute the Body at least once. That is, don't test
the Condition until after executing the Body.
This is different from while(Condition, Body),
which tests the Condition before executing the Body.
It's also different from while(Condition, Body) in
that the loop continues until the Condition becomes
true rather than until the Condition becomes false.

B. extend the previous result to include += and -= versions of assignment. 

Example
?- program(x := 5; x += 3+4, Storage)
Storage = [x = 12]

Note that := is not in the table of operators above. Use 

?- current_op(P, A, :=)

to determine its precedence and associativity. Define += and -= to have the same precedence and associativity.

[edit] Thursday.

Extend the previous result to include a simple for statement. 

for(Variable, start, end, Body)

Execute the Body with the Variable having
the values: start, start+1, …, end.
Be sure that start and end are integers. 
If not, issue an error message and fail.

If start < end, increment the Variable each
time through the loop. If start > end decrement
the Variable each time through the loop.

If Variable has a value in the storage before
the for statement, save that value and restore
it after the for statement. If Variable 
has no value in storage before the for statement
it shouldn't have a value afterwards.

Example
?- program(total = 0;
           for(i, 3, 7, total += i),
           Storage).
Storage = [total = 25]

[edit] Nov 10 (Week 8)

Veteran's Day holiday observed. No class.

[edit] Homework 8

  • Tuesday. Add function declarations to the language. That is, extend the language so that you can read and store function definitions. This will require that you add an additional parameter (or in some cases two additional parameters to many of your predicates. Since how you store functions is not visible at the top level, to see if you have stored them correctly, you will have to execute statement/5 at the top level. I'm assuming that you have redefined statement/3 to be statement/5 as follows. 
statement(Statement, Functions_In, Functions_Out, Storage_In, Storage_Out)

You should start with no functions defined, and then define a couple of them. (Note that the Storage (of variable values) does not change.) 

Example
?- statement(function(f1(x, y), body1 ); function(f2(x, y, z), body2 )), [], Functions_Out, Storeage_In, Storage_Out).
Functions_out = [f2 = ([x, y, z], body2), f1 = ([x, y], body1)]
Storage_In = Storage_Out
  • Thursday. Add function calls (function evaluation) to the language. See Adding functions for an example.

[edit] Nov 17 (Week 9)

[edit] A better way to return values from a function invocation.

In Adding functions. I suggested that you write 

expr_value(FunctionCall, FunctionStorage, Storage, Result) :-
  ...
  %% Retrieve the function definition, evaluate the arguments, 
  %% and bind those values to the function's formal 
  %% parametera in a StorageWithBoundParameters.
  ...
 
  %% Execute the function body with respect to that 
  %% newly created storage.
  statement(Body, _, _, 
            StorageWithBoundParameters, 
            ResultStorage),

  %% Retrieve the value of an identifier named 
  %% result and return that value
  %% as the value of the function.
  fetch(result, ResultStorage, Result).

This assumed that you defined a return statement to store a value in storage associated with a reserved identifier named result. In fact, if you always store a new value for a variable as the first element of storage (which is the default thing to do), it doesn't matter which variable name you use. (Ramon Hernandez used this idea.)

So your expr_value/5 clause could look like this. 

expr_value(FunctionCall, FunctionStorage, Storage, Result) :-
  ...   %% Retrieve and bind parameters.
  statement(Body, _, _, 
            StorageWithBoundParameters, 
            [_ = Result]).

Caution, executing a return statement doesn't stop the interpreter from executing other statements that may follow a return statement. For example, if you have a program that looks like this, you will get into trouble. 

function(f(x), if(Condition_1, return something);
               if(Condition_2, return somethingElse))

If Condition_1 holds, the return statement will be executed, which will throw out all of storage except [_ = something]. But the interpreter will go on to execute the second if statement anyway. Condition_2 may refer to some program variable, which will no longer be defined. Considering this problem it might be better simply to use the original method and store the value of the function under the identifier result and then fetch it at the end.

[edit] Homework 9

Lab. Modify your code (if necessary) so that it returns values from function calls as described above.

Tues. (Nov 28) The decisions about how to represent tuples has changed a bit. Be sure to re-read Defining class-like data structures. Also, look at the discussion on the Discussion page. Add the ability to read, store, and use tuples. That is, implement a tuple-definition statement and a new expression keyword that allows the user to construct tuples. 

?- program(tuple(t1(a, b)); x := new t1(3, 4), Storage_Out).

Storage_Out = [x = t1([a = 3, b = 4])]


Thurs. (Nov 30) Add the ability to access list components. Demonstrate by showing that your program can execute at least the two list sum functions on the Defining class-like data structures page.

[edit] Nov 24 (Thanksgiving Holiday)

No Class.

[edit] Dec 1 (Week 10)

  • Consolidate and review.

[edit] Dec 8 (Final)

The Final (2 1/2 hours) will start at the regular class time: 10:00 AM.

Retrieved from "http://cs.calstatela.edu/wiki/index.php/Courses/CS_332L/Fall_2006"
Personal tools