7 Course Assignments

The following is a series of assignments complementing the exercises found in [Madsen93]. Please do not expect these assignments to be complete in any sense. You should see them as proposals, that should be supplemented, depending on the style of the course and the background of the students.

Currently, the order of the assignments is somewhat random, not expressing any levels in difficulty, etc.

7.1 Assignment

Write a BETA program, that converts UNIX file names to Macintosh file names. I.e. converts the string:

"/home/saturn/kurt/hello.bet"

to:

"home:saturn:kurt:hello.bet"

Note, that this assignment is based on knowledge about the text patterns in betaenv.

7.2 Assignment

The idea here is to build a search program which, given a line of text, can find occurrences of characters and of other (smaller) strings of text. Here are the relevant commands:

T       (* Text: input new "base" text string *)
<text>
C       (* Char: count occurrences of a char *)
<char>
O       (* Occurs: check if some text occurs as a substring (Yes/No) *)
<text>
N       (* Number of occurrences: count occurrences of a substring *)
<text>
F       (* First: first location of a substring *)
<text>
L       (* Last: last location of a substring *)
<text>
Q       (* Quit *)

7.2.1 Question A:

Sketch the search algorithms you want to use.

7.2.2 Question B:

Implement a search program (search) in BETA that supports the above commands. You may test your program using the given sample interaction. User typing is printed in underlined. This is only an example - feel free to choose your own style for the interface.

7.2.3 Question C:

How well does your code separate the search functionality from the handling of the user interface? For example, do you think it would be easy to reuse your search patterns in a different environment (say, where the text appears in a window and commands come via menus and dialogues)? Do you have any general reactions to line-oriented interfaces like these?

search
Commands:
T. input new "base" text string
C. count occurrences of a char
O. check if some text occurs as a substring
N. count occurrences of a substring
F. first location of a substring
L. last location of a substring
Q. quit

Be sure to end each line of input with <enter>

T
New "base" text string:
abcdefg
Next command:
C
Char to search for:
g
  1 occurrences of "g" in "abcdefg":
Next command:
T
New "base" text string:
abc def ghi def de
Next command:
O
Substring to search for:
f g
Yes - there are some occurrences of "f g" in "abc def ghi def de" 
Next command:
O
Substring to search for:
fg
No occurrences of "fg" in "abc def ghi def de" 
Next command:
N
Substring to search for:
def
  2 occurrences of "def" in "abc def ghi def de" 
Next command:
F
Substring to search for:
de
  5 is the first location of "de" in "abc def ghi def de" 
Next command:
L
Substring to search for:
de
 17 is the last location of "de" in "abc def ghi def de" 
Next command:
L
Substring to search for:
cd
No location of "cd" in "abc def ghi def de" 
Next command:
N
Substring to search for:
 d
  3 occurrences of " d" in "abc def ghi def de" 
Next command:
Q
So long!

7.3 Assignment

This assignment is a review of concepts like dynamic references and repetitions. Consider the bank example in [Madsen93].

7.3.1 Question A Modelling the customer's address

Change the address attribute of Customer from a simple text attribute to be a structured object consisting of three text attributes: streetAndNumber, postalCode, city. That is, in the object descriptor of Customer, instead of "Address: @text", you'll have "Address: @(# ... #)". Also, give Address its own Print attribute which can print the three parts of an address. The Print attribute for Customer should (among other things) now invoke the print for Address. You'll probably want to change the Initialize pattern of Customer to set the new Address fields.

The Account pattern shouldn't need to be modified. Again, test your code by creating an account and a customer and printing the balance. Do you agree that Address should be declared this way instead of as a dynamic reference to a separate object?

7.3.2 Question B: Modelling bank accounts having several owners

An account might have several owners (e.g. husband and wife). Change the owner attribute to "owners" and make it be a repetition of dynamic references to Customer. PrintBalance should print the information of all customers before printing the account balance. You'll need a way to add new owners, say, an AddOwner procedure attribute.

Test your code by creating several customers for the same account and printing the balance.

7.3.3 Question C:

Modify the bank system such that it includes a procedure pattern that deletes the account of a specific costumer.

7.4 Assignment

You must design and implement a very simple soda machine which "dispenses" just two kinds of drinks, cola and juice.

Your soda machine should include a current total of money. (You can assume you'll only get 1 dollar coins or larger so it can be an integer.) You must manage two other totals: the current number of colas and the current number of juices. Your soda machine should support transactions where the user puts in money and gets back a cola or a juice plus change. But you'll also need to support the soda machine maintainer who refills the machine and checks the current totals.

Here's a sample user interaction which your program should be able to support. ("R" stands for refill, "C" for buy a cola, "J" for buy a juice, "T" for print totals, "Q" for quit.) What the user types are underlined. Colas cost 8 dollars and juices 7 dollars each.

T
Current totals: 0 colas, 0 juices, 0 dollar.

R
How many colas to add?
15
How many juices to add?
20
How many dollars should we start with?
100

T
Current totals: 15 colas, 20 juices, 100 dollars.

C
A cola costs 8 dollars.  How much money are you inserting?
10
Thanks.  Your change is 2 dollars.

J
A juice costs 7 dollars.  How much money are you inserting?
20
Thanks.  Your change is 13 dollars.

T
Current totals: 14 colas, 19 juices, 115 dollars.

Q
Goodbye.

7.4.1 Question A:

Identify the objects in the example. What patterns will you need to define? What attributes will they have?

7.4.2 Question B:

Implement the soda machine in BETA and test it.

7.4.3 Question C:

What happens in your program if the number of colas goes down to zero before a refill? What happens if the user puts in less money than the drink costs? Suppose you needed to change the costs of colas and juices? Are those numbers easily adjustable or are they "hard-wired"?

7.5 Assignment

Make a BETA program, which reads a number of numbers (terminated by 0), and outputs the largest and smallest number.

Then modify the program such that it outputs all numbers sorted (use whatever sorting method you want).

7.6 Assignment

Consider the following BETA program:

(# Ptn: (# i: @integer;
           t: @text
        enter (i, t)
        do ' ' -> t.put;
           i -> t.putInt
        exit t[]
        #);
   j: @integer;
   s: @text;
   p: @Ptn
do (* first sequence *)
   17 -> j;
   's:' -> s;
   (j,s) -> p;
   p -> putline;

   (* second sequence *)
   17 -> j;
   's:' -> s;
   (j,s) -> &amp;Ptn;
   p -> putline
#)

The program consists of a declaration of a pattern: Ptn, and some static items: j, s, and p. The action-part contains two nearly identical sequences of imperatives.

7.6.1 Question A:

Explain the object-structure of this program (i.e. which objects are allocated, and when).

7.6.2 Question B:

Explain the results of executing the first sequences of imperatives.

7.6.3 Question C:

Explain the results of executing the second sequences of imperatives.

7.6.4 Question D:

Explain the difference between the results of the two sequences.

7.7 Assignment

This assignment is a chance to play with the notions of inheritance, specialisation and generalisation. Recall that specialisation involves creating a new subpattern that specialises an existing pattern, that is, it inherits attributes from the existing pattern and (usually) adds new ones of its own. (The subpattern can also extend the superpattern's action part.) Generalisation is when you create a new superpattern by gathering common attributes from several existing patterns.

Starting from the bank example in [Madsen93], write two new subpatterns, CheckingAccount and SavingsAccount, which specialise the Account pattern. Your SavingsAccount pattern should include a new part attribute, interestRate, and a procedure attribute CalculateInterest which can be called at the end of every working day to increment the balance according to the current interest rate.

Your CheckingAccount pattern should model the US system where customers are charged a fixed (small) price for every check they write unless the balance exceeds a certain threshold, in which case writing checks is free. What new part attributes do you need? Add a new procedure attribute ProcessCheck which reduces the current balance by the amount of the check plus the check-writing charge if applicable.

7.8 Assignment

Construct a BETA program that calculates the natural number square root of a number: n >0.

The natural number square root is the number r, such that:

r^2 <= n < (r+1)^2

Implement this program and test it.

7.9 Assignment

Starting from your own soda-machine code, generalise your SodaMachine pattern by implementing a superpattern called VendingMachine. Also, make another subpattern of VendingMachine called CandyMachine. (A CandyMachine is like a SodaMachine except that instead of juices and colas, you can get chewing gum, chocolate bars, and M&Ms.) Think about which attributes are common to both SodaMachine and CandyMachine; these are candidates for moving up into VendingMachine.

In your original SodaMachine pattern was a procedure attribute that printed the totals, let's call it PrintTotals. Move this procedure attribute up to VendingMachine and specialise it for SodaMachine and CandyMachine. (Don't forget that your definition of PrintTotals in VendingMachine should include an inner imperative.) So SodaMachine and CandyMachine will have new attributes called SMPrintTotals and CMPrintTotals, respectively, which specialise VendingMachine's PrintTotals pattern.

You probably also had a procedure attribute that refilled the machine, let's call it Refill. Make a new Refill attribute in VendingMachine which takes one enter parameter, a number of dollars, and adds this money to the current total. Then specialise Refill in each of SodaMachine and CandyMachine to take extra enter parameters corresponding to the number of items to add (either juices and colas, or chewing gum, chocolate bars, and M&M bags). So SodaMachine and CandyMachine will have new attributes called SMRefill and CMRefill, respectively, which specialise VendingMachine's Refill pattern.

Modify the do-part of your soda-machine code to test your new patterns and attributes.

7.10 Assignment

This assignment is a chance to play with virtuals.

In Assignment 9, you modified your soda machine code to include two new patterns, VendingMachine and CandyMachine. Among the procedure attributes of VendingMachine, were two called Refill and PrintTotals. You also made specialisations of these in SodaMachine and CandyMachine called SMRefill, CMRefill, SMPrintTotals, and CMPrintTotals.

Change these specialised attributes to be virtuals. That is, Refill and PrintTotals should be declared as virtuals in VendingMachine and (the same names) further bound in SodaMachine and CandyMachine. Note that this should be easy! Very little of your other code should need to be changed.

Add a new virtual called Empty which simply resets to zero the money in the machine and the amounts of all items. (A handy procedure for thieves!) Again, you'll be declaring Empty to be a virtual in VendingMachine and specialising it in SodaMachine and CandyMachine. What part of the work should be done in each pattern?

As usual, be sure to test all your changes using the do-part of the program.

7.11 Assignment

Design a Dictionary pattern with the operations: associate, disassociate, lookup and scan:

Discuss the consequences of allowing more than one element for each entry.

Make the dictionary as general as possible, using inheritance and virtual attributes as much as possible.

7.12 Assignment

Modulize the Dictionary pattern from exercise 11 such that the users of the dictionary cannot gain access to the implementation of it.

7.13 Assignment

Extend the Dictionary pattern from exercise 12 such that exceptions are defined taking care of the many different exceptional cases which may occur during the lifetime of a dictionary object.

7.14 Assignment

Make use of the Dictionary from exercise 13 to implement a phone book.

Use the Persistent Store to make it possible to save the phone book between program executions.

Make two distinct programs (e.g. an update and a query program), both using the same phone book saved in the Persistent Store. Its OK to assume that these programs never are running at the same time.

Use the exceptions defined e.g. for dictionary in the phone book and phone book programs to make the programs more fault-tolerant.

7.15 Assignment

Dining philosophers. Five philosophers spend their lives thinking and eating. The philosophers share a common dining room where there is a circular table surrounded by five chairs, each belonging to one philosopher. In the center of the table there is a large bowl of spaghetti, and the table is laid with five forks. On feeling hungry, a philosopher enters the dining room, sits in his own chair, and picks up the fork on the left of his place. Unfortunately, the spaghetti is so tangled that he needs to pick up and use the fork on his right as well. When he has finished, he puts down both forks, and leaves the room. The room should keep a count of the number of philosophers in it.

The problem is to prevent any philosopher from dying from starvation due to the philosopher on his right always using the right fork. It is assumed, that the philosophers only are eating in a limited period of time.

7.16 Assignment

The following questions require writing a few small programs which draw various geometric figures. The programs should be written in a programming language with the following syntax:

command -> drawN | drawW | drawS | drawE |

moveN | moveW | moveS | moveE |

command newline command |

thickness thickness |

color color

repeat number newline command newline end repeat

thickness -> "thick" | "thin"

color -> "black" | "red"| "blue"

number -> #an integer greater than 0#

newline -> #a line-feed/carriage-return#

These programs can be realised by implementing a drawing environment using either GuiEnv or Bifrost.

7.16.1 Question A:

Write and test a program that draws the above figure.

7.16.2 Question B:

Write and test a program that draws the above figures. Write one or more algorithms that draw the same figures. Are there any essential differences between the algorithms?

7.16.3 Question C:

Write and test a program that draws the above figure. Write one or more algorithms that draw the same figure. Are there any essential differences between the algorithms?

7.16.4 Question D:

Write and test a program that draws the above figure. Write one or more algorithms that draw the same figure. Are there any essential differences between the algorithms?

7.16.5 Question E:

In this assignment, you've used draw-primitives like drawN and moveE. Based on your experience with questions A) through D), suggest other draw primitives. Try writing algorithms with your new primitives. Are yours an improvement? Why?

7.16.6 Tips on using DrawEnv.bet

The BETA implementation of this application can be constructed along the following guidelines. You should have two windows called Drawings and Commands. (There's also a partially hidden Console window which you can ignore.) Choosing an item off the Commands menu adds a line of text with that command (followed by a newline) at the current cursor position in the Commands window. You can also type commands into the window manually. The repeat command menu item works in a slightly special way. If some number of lines in the Commands window are currently selected (i.e. highlighted), then the repeat command will "bracket" those lines. The repeat n part of the repeat statement will be inserted before the selection and the endrepeat after the selection. Be sure to change the number n to be the desired number of iterations. Using the Actions menu, you can reset the current position in the Drawings window back to the upper left corner of the window (for the next draw or move command), clear the contents of both windows, and "run" or "execute" the current selection in the Commands window. Note: you can copy/paste a saved set of commands into the Commands window from another file (say, a Microsoft word file).

7.17 Assignment

Make a text editor with a menu using MacEnv/AwEnv/MotifEnv. Each time the menu is selected, a beep sound should be made. Compile and run the program.

7.18 Assignment

Write an application with one graphical window, one menu and one dialog box. The menu contains the following entries: Rect, Oval, RoundRect. When one of these are selected, a corresponding shape is drawn in the window. The menu also contains a shape entry. When that entry is selected, a dialog box appears with three radio buttons (Rect, Oval, RoundRect), and four text fields (height, width, X, Y) and two buttons (OK, CANCEL). The radio buttons selects the shape type, height and width defines the size of the shape, and X and Y defines the position of the shape in the window.

Implement the system in MacEnv, AwEnv or MotifEnv and test it.

7.19 Assignment

This assignment is an introduction to MacEnv. Each question asks you to modify one of the small MacEnv demo programs. This require understanding part of the source code for the particular demo program and that in turn means that you'll be referring to the MacEnv documentation . Don't forget to use the index as well as the table of contents when looking up the various MacEnv patterns and attributes.

Notice that for each of the applications, the Close and Quit items on the file menu are automatically enabled. (Close is only enabled if there's a window belonging to the application currently open on the screen.)

7.19.1 Question A: Hammer windows

The Hammer program puts up a window containing a picture of Thor's famous hammer "Mjølner." The window "handles refresh", that is, if the window is activated (clicked in) after having been covered up by another window, it redraws its contents. (Find the part of the code that does this!) The program also allows you to create new hammer windows using the New item on the File menu. Trouble is, these new windows come up in the same place on the screen. Change the code so that the new windows are positioned at different places on the screen, but still have the same dimensions.

7.19.2 Question B: Multiple text editor windows

The program TextEditors lets you create multiple text editor windows using the New item on the File menu. The new windows are positioned successively down and to the right, each one overlapping the previous. Change the program so that new windows are opened next to each other. That is, so they are positioned side-by-side, that is, their edges just touch. (How many new windows can you make before running out of screen space?)

7.19.3 Question C: Catching an event in a text editor window

The EventDemo program creates a text editor window and beeps whenever the mouse is clicked inside the window. Change the program so that it also inserts the text string 'beep' at the current position. If the user double-clicks in the window, insert the string 'double-beep'. (This gives you a way to experiment with the difference between two successive clicks and a single double-click.)

7.20 Assignment

Make a Matrix data structure with hidden implementation. Make a Vector data structure, such that Vector is able to utilise the implementation of Matrix, without revealing the Matrix implementation to the rest of the program (e.g. to the users of the Vector data structure.

7.21 Assignment

Implement the so-called futures in BETA using the concurrency facilities. A future is a value, returned as the result of an operation, but where the results of the operation may not have been completely calculated yet (e.g. a concurrent computation has not yet completed). References to futures may be passed around like any other object even though the result still isn't available. If some system object evaluates the future, it should be blocked until the result of the computation becomes available, in which case the result(s) are exited from the future object.


Teaching Package
© 1991-2004 Mjølner Informatics
[Modified: Monday March 11th 2002 at 16:16]