PATTIS@WASHINGTON.ARPA (Richard Pattis) (05/30/86)
A New Modula-2 Book:
I recently received a copy of a new Modula-2 book. It was written by Arthur
Sale of the Univeristy of Tasmania in Australia, and it is titled "Modula-2:
Discipline & Design". It is published by Addison-Wesley and costs about $25.
I'll quote a section from the preface to show what I think is the flavor of
this book (all typos are my own):
"My purpose in writing this book is to bring together a precise
discussion of Modula-2 and its features and modern concepts of
professional large program writing. There are few books which are
accessible to learning students which use Modula-2 at the present
time, and this is an inhibiting factor in its use as a teaching
language. However, even more important in this book is the break
with the traditional approaches to first language texts. It is my
experience over ten years that learning students can cope with
concepts of considerable abstraction, such as predicate transformers
and invariants. Not all the implications are realized by students,
but the concepts can be planted and used. The best students progress
much faster, but even average students see the ideas which are presented
as a result of modern computer science research as converting the dark
art of programming into something which is understandable. The era of
learning programming by osmosis, which has persisted for far too long,
is ending, and programming has become a subject in which design and
discipline reign and can be taught"
A Modula-2 Problem:
In Sale's discussion of strings, he decides to store each string padded with
0Cs (not just one, but 0Cs all the way up thru the last element in the array).
Of course, if the string fills the array, there is no padding at all. Also,
note that the string terminator, 0C, compares less than any other character.
Given any two parameter strings that follow this convention, Sale writes the
following function to compare them (I've tried to transcribe the code directly
from this introductory text, using the same indentation and spacing):
TYPE Order = (Before,Same,After);
PROCEDURE CompareStrings (S1: ARRAY OF CHAR; S2 : ARRAY OF CHAR) : Order;
CONST
NUL = 00C; (* Terminating Marker *)
VAR
i : CARDINAL;
Shortest : CARDINAL;
Result : Order;
ResultKnown : BOOLEAN;
BEGIN
Shortest:= Min(HIGH(S1),HIGH(S2));
ResultKnown:= FALSE;
i:= 0;
WHILE NOT ResultKnown DO
IF S1[i] < S2[i] THEN
(* Found unmatched character *)
Result:= Before;
ResultKnown:= TRUE;
ELSIF S1[i] > S2[i] THEN
(* Found unmatched character *)
Result:= After;
ResultKnown:= TRUE;
ELSE (* S1[i] = S2[i] *)
IF S1[i] = NUL THEN
(* Both strings same up to two NULs. *)
Result:= Same;
ResultKnown:= TRUE;
ELSE
(* Task unresolved, must look at next component. *)
i:= i+1;
IF i > Shortest THEN
(* Run out of one string's components. *)
IF HIGH(S1) = HIGH(S2) THEN (* Both together. *)
Result:= Same;
ELSIF Shortest = HIGH(S1) THEN (* S1 shorter *)
Result:= Before;
ELSE (* S2 shorter *)
Result:= After;
END;
ResultKnown:= TRUE;
END;
END;
END (* of IF comparing S[i]'s *);
END (* of WHILE *);
RETURN Result;
END CompareStrings;
(1) I assert, that this function computes wrong answers. In what cases does
it do so? Be as general as possible and remember the assumptions above.
(2) Describe how we could rewrite this function to correct this deficiency.
(3) Given the same assumptions, completely rewrite this function to be as
simple as possible. It should also execute as quickly as possible.
(4) Now, remove the padding assumption; instead, assume that only one 0C is
placed at the end of each string that doesn't fill its array. Rewrite
this function to work correctly with strings following this convention.
(5) What interesting conclusions can you draw from this exercise?
For parts 3 & 4, use your best programming style. Write these function as
clearly as possible.
Please send your answers to me, PATTIS@WASHINGTON. After you send me your
analysis, I'll send you mine. I'll also keep a compendium of the analyses
that I receive, and send it out to the mailing list when responses stop. If
you don't want your analysis shown to anyone, or if you don't want your name
attached to it, please tell me when you mail in your analysis. If there is
enough interest in this exercise, I'll construct a similar one.
Rich
-------