Thursday, July 03, 2008


Calculator Project
In VBA, make a form, and make a calculator, with a testbox and a series of buttons for addition, subtraction, multiplication, division, and equal.
>> View/Complete Assignment: Calculator Project

Item Prolog Homework 3
Trace through the conc procedure, appending a list of four elements to another list of four elements.

Write the following prolog procedures, on lists.

1. subst(A,B,C,D) where list D is list C with element A substituted for all occurrences of element B.
2. equal(X,Y) if X and Y are the same set.

Also, read thru the following:
http://www.ling.helsinki.fi/kit/2004k/ctl272/Bangor/clbook_30.html

and do copy and try out the examples.
>> View/Complete Assignment: Prolog Homework 3

Item Prolog Homework 2
  1. Try to write Prolog rules corresponding to each of the following.
    1. Every farmer owns a donkey.
    2. Every farmer who owns a donkey beats it.
    3. If Pedro owns a donkey, he beats it.
    4. If Pedro is a farmer, he owns a donkey.
    5. If Pedro is a donkey-owning farmer then he beats his donkey.
    6. If Pedro is a donkey-owning farmer then he probably beats his donkey.
    7. Donkeys have a hard time.
  2. The infix predicate =/2 takes two arguments and tries to unify them. We can use this to experiment with Prolog's pattern matching; for example:
    | ?- X = [a,b].
    X = [a,b] ?
    yes

    | ?- [X] = [a, b].
    no

    | ?- X = a, X = Y.
    X = a,
    Y = a ?
    yes
    So, Prolog will tell us whether the terms on either side of the = unify, and if they do, it will provide us with the bindings for any variables that appear.

    For each of the following:

    • specify whether the query submitted to Prolog succeeds or fails; and
    • if it succeeds, specify what is assigned to the variables by the unification;
    • if it fails, explain why.
      1. | ?- X = fred.
      2. | ?- jane = fred.
      3. | ?- X = fred, X = Y.
      4. | ?- X = happy(jim).
      5. | ?- X = Y.
      6. | ?- 2 + 1 = 3.
      7. | ?- f(X,a) = f(a,X).
      8. | ?- fred = fred.
      9. | ?- likes(jane, X) = likes(X, jim).
      10. | ?- f(X,Y)=f(P,P).
      1. | ?- A = b(c).
      2. | ?- a = b(c).
      3. | ?- a(b,C) = a(C,b).
      4. | ?- a(b,C) = a(C,d).
      5. | ?- A = B.
      6. | ?- A = b(C).
      7. | ?- 3 = 6/2.
      8. | ?- a(b,c) = a(b,c).
      9. | ?- a(B,C) = a(D,D).
      10. | ?- member(a,L) = member(E,[b,c,d]).
      11. | ?- A = b(A).
  3. Write the ancestor/2 predicate to a file, and add about ten facts along the lines of parent(anna,belinda), parent(belinda,celia) etc. Then call ancestor(anna,X). Use ; to see all solutions, viewing the execution of the goal with trace.
  4. We can use the successor notation for addition to show an example of the interaction between unification and recursion. This example may appear a bit complex first, if you are not used to mathematical theory, but in fact it just shows how simple the ideas really are.

    The numbers 0, 1, 2, 3, 4...are defined by a set of axioms called the Peano axioms. The definition of the numbers themselves are based on two concepts:

    • a STARTING POINT, which we call zero and write as 0; and
    • the concept of BEING THE NEXT NUMBER, which we will represent as s(K).
    In this notation, 0 is 0, 1 is s(0), 2 is s(s(0)), 3 is s(s(s(0))), and so on. Note that although s is a function, there is no notion of it being evaluated.

    Using this representation, we can write a procedure which formalises the definition of addition:

    % succ_plus/3
    % the definition of addition according to the Peano axioms
    % succ_plus(X,Y,Z) corresponds to X + Y = Z
    % X,Y,Z are all given in successor notation

    succ_plus(0,X,X).
    succ_plus(s(X),Y,s(Z)) :-
    succ_plus(X,Y,Z).

    Let's say that we want to add 3 and 2. 3 is the successor of the successor of the successor of 0 (s(s(s(0)))) and 2 is the successor of the successor of 0 (s(s(0))). To follow the execution of the goal, we use trace as usual:
    | ?- trace,succ_plus(s(s(s(0))),s(s(0)),X).
    {The debugger will first creep -- showing everything (trace)}
    1 1 Call: succ_plus(s(s(s(0))),s(s(0)),_128) ?
    2 2 Call: succ_plus(s(s(0)),s(s(0)),_325) ?
    3 3 Call: succ_plus(s(0),s(s(0)),_445) ?
    4 4 Call: succ_plus(0,s(s(0)),_561) ?
    4 4 Exit: succ_plus(0,s(s(0)),s(s(0))) ?
    3 3 Exit: succ_plus(s(0),s(s(0)),s(s(s(0)))) ?
    2 2 Exit: succ_plus(s(s(0)),s(s(0)),s(s(s(s(0))))) ?
    1 1 Exit: succ_plus(s(s(s(0))),s(s(0)),s(s(s(s(s(0)))))) ?

    X = s(s(s(s(s(0))))) ?

    yes
    ?-
    Whenever the second clause of addition/3 is used (i.e. every time the first term is not equal to 0) X matches the interior of a structure. For instance, in the first call, s(X) and s(s(s(0))) are unified, giving the substitution X = s(s(0)). The recursive clause is used until X is matched to 0--then we use the base case, and the third term is unified with the second term. As we step back through the recursive clause, s(...) is added on to the third term once for every s(...) we had to strip off to reach the base case.
    1. Try the program out with a few different numbers, until you understand how it works.
    2. Write a procedure for subtraction. This will only work when the first number is equal or greater to the second--why?
      >> View/Complete Assignment: Prolog Homework 2

Item Prolog Homework 1
Download and install SW-I Prolog.

Trace through the sam likes example.

Then:

  1. Create files with the facts and rules discussed in this chapter. Try out various queries.
  2. Represent the following sentences as Prolog facts.
    1. Bill is tall.
    2. Bill is a teacher.
    3. Bill sings.
    4. Bill likes ice-cream.
    5. Mary hates ice-cream.
    6. Today is Friday.
    7. Jane hit Bill.
    8. Jane hit Bill with a cricket bat.
    9. Belinda bought a sweater.
    10. Belinda bought Jim a sweater.
    11. Belinda bought Jim a sweater at Jenner's.
    12. Belinda bought Jim a sweater for fifty pounds at Jenner's.
    13. Belinda is married to John.
    14. John is Belinda's husband.
    15. John and Belinda are married.
  3. Construct a file called family.pl containing the following Prolog clauses.
    % parent(Parent,Offspring)
    parent(mary,thomas).
    parent(mary,jane).
    parent(william,thomas).
    parent(william,jane).
    parent(thomas,lee).
    parent(thomas,sandy).

    % female(Female).
    female(mary).
    female(jane).
    female(sandy).

    % male(Male).
    male(thomas).
    male(william).
    male(lee).
    Load the contents of the family file into the Prolog interpreter.
    • Display the contents of the database by using listing/0. Don't forget the full stop.
    • Display parts of the contents by using the predicate listing/1 whose argument should be the name of a predicate. For instance typing listing(male) will display all facts whose predicate is male regardless of arity.
    • Look at the following queries. Try to work out what the interpreter will reply first, then try them out. Check if there is more than one solution using ; if applicable.
      | ?- parent(mary,thomas).
      | ?- parent(thomas,lee).
      | ?- parent(thomas,mary).
      | ?- male(william).
      | ?- parent(thomas,Who).
      | ?- parent(Parent,sandy).
      | ?- parent(X,Y).
    • What queries would you use to find out the following?
      • Is Mary the parent of Thomas and Jane?
      • Do Jane and Thomas have the same parent?
      • Does Sandy have a sister?
      • Who is Thomas's mother?
  4. Establish a database with parent and gender facts for your own family. Write rules for commonly used family terms, such as sister, brother, mother, father, grandparent, grandfather, cousin, aunt, half-brother, etc. Try out the program, making sure that it gives the correct answers. Use trace to make sure you understand the different answers.
    >> View/Complete Assignment: Prolog Homework 1

Item Homework #11: Dynamic Variables
Read this article at Microsoft Research about "Dynamic Variables." Do not read the Appendix to the article just yet, only the main body of the article.

Answer the following questions:
1) List two purposes for which they envision using these dynamically scoped variables?
2) Choose one of those two, and motivate it. That is, show what the code would look like when not using dynamic variables, and then what it would look like with dynamic variables.
3) Briefly describe the "simple" and the "novel" implementations.
>> View/Complete Assignment: Homework #11: Dynamic Variables

Item Static Scoping
Read this article. Give four reasons why nesting in Ada programs is for the birds. What is the authors' suggestion? Also, read this article about regular expressions in Word, and try the find and replace example in the article. http://office.microsoft.com/en-us/help/HA010873051033.aspx
>> View/Complete Assignment: Static Scoping

Item HW #8
Using VBA for Excel, implement the first FSA from assignment #5. On the spreadsheet, include a formal description of the FSA. This includes the transition function delta. Rather than using Gotos, keep a variable which maintains the present state, and look up the appropriate transition to the next state, based on the present state and the input, from that lookup table on the Excel worksheet.


Item HW #7
Using VBA for Excel, implement the first FSA from assignment #5. Read the input string from cell B1. Print "accept" or "reject" in C1. Print the sequence of states in cell A4 and down (A5, A6, etc). Use gotos and goto labels to represent the states. Use the MID function to extract letters sequentially from the input string.


Item Assignment 6: FSAs
FSA.doc (38 Kb)
Answer the questions in the attached Microsoft Word document about two FSMs.

Due Feb 11, 2008

Item Assignment 5
Download G95 (sidebar) and install it on your computer. Name the files *.f90 to be able to use FORTRAN 90 syntax. If you name it *.f, you will have annoying restrictions, such as the first 6 characters on a line being reserved. Read through the beginning of the tutorial, here:

http://www.cisl.ucar.edu/tcg/consweb/Fortran90/F90Tutorial/tutorial.html

Specifically, start with "Exercises and Examples," and do Exercise 2.1

Due Feb 11, 2008

Item Assignment #3, 4
#3: Due this Wednesday, Feb 6
In Visual Basic for Applications for Excel, create a macro that puts the numbers 1 through 13 in cells A1 through A13. If possible, do so using the functionality in which you can drag to extend an existing pattern of numbers. Copy the text of the VBA macro which was created, and submit that.

#4: Due next Monday, Feb 11
Write two UDFs (User Defined Functions), with meaningful names of your own choosing. The first should take in X and Y and return X times Y. The second should take in X and return X factorial.

Item Assignment #1, #2
1. Give a short evaluation (a few sentences) of Stroustrup's paper on Generalized Operator Overloading for C++ 2000 in terms of readability and writability.

Due approximately Monday, Feb 4.

2. Take some programming language you know and discuss its positive and negative aspects in terms readability, writability, and reliability. (Two or three paragraphs.)

Due approximately Monday, Feb 6.