home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power-Programmierung
/
CD1.mdf
/
magazine
/
pas_nl
/
06
/
pnl006.txt
< prev
next >
Wrap
Text File
|
1991-03-17
|
64KB
|
1,692 lines
//////// // // //
// // /// // //
// // //// // //
//////// // // // //
// // //// //
// // /// //
// // // ///////
Pascal NewsLetter
Issue #6
March, 1991
Editor: Pete Davis
The Programmer's Forum BBS is the home of
PNL. It can be reached in Washington, DC at
(202)966-3647. Information is available
through the following locations:
FidoNet: Pete Davis@1:109/138
GEnie: P.DAVIS5
BitNet: HJ647C@GWUVM & UE356C@GWUVM
InterNet: HJ647C@GWUVM.GWU.EDU
or UE356C@GWUVM.GWU.EDU
Uucp: Pete.Davis@f138.n109.z1.fidonet.org
Table of Contents
Introduction ................................ 3 (P.D.)
Returning Structured Data Using TP Functions. 5 (B.M.)
Displaying an Integer with Commas, Revisited. 10 (N.P.)
Chess-Ter ................................... 13 (P.D.)
Searching ................................... 19 (K.S.)
For Beginners ............................... 21 (B.G.)
Conclusion .................................. 26 (P.D.)
Key:
----
P.D. - Pete Davis : Editor-in-Chief
R.M. - Richard Morris : Editor-Over-The-Pond
B.G. - Bob Gowans : Columnist
B.M. - Bill Madison : Contributing Writer
N.P. - Nathan Phillips : Contributing Writer
K.S. - Kelly Schwarzhoff : Contributing Writer
Introduction
Well, it's been quite a while since PNL005 and I apologize for
the delay. Many of you know why it took so long, and for those of you
who don't, I will give you my excuse. First of all, since this is
going to remain a free newsletter in the foreseeable future, I have to
put my priorities in order. Since money isn't going to be my priority,
school is. I have decided to add to my course load so that I can
graduate a semester earlier than planned. This has resulted in the
addition of two credits bringing my total to 17. Also, I decided (not
wisely) to take a graduate course. The additional two credits and the
graduate course have taken up an enormous amount of extra time. On top
of this I also work 20-30 hours a week. These, combined with an
attempt to maintain my social life (very hard with school and work)
has left little time for keeping the newsletter coming out at a
regular interval. Right now I am in my spring break which will allow
me a little time to get this issue out. I hope to get started on
PNL007 before summer, but I just can't be sure. If the first half of
this semester is any indication, PNL007 won't come out until about a
week after summer vacation begins. Also, getting the issues out over
summer won't be as easy as last summer as I am going to be taking some
classes over the summer and working almost full time.
Well, that's my excuse. Don't get me wrong, I love doing the
newsletter, and if I didn't have to worry about school and work I
would certainly be working much harder on it.
I would like to bring up some very good news, though. One of my
professors, Ray Thomas, who was my professor for some of my first
classes in programming, will be retiring soon. Professor Thomas taught
me a lot of what I know and is directly or indirectly responsible for
several articles that I have written. He has also been very supportive
of the newsletter. He has told me that after his retirement (the end
of this semester) he will be writing articles now and then for the
newsletter. This is very good news to me and I think many of you will
be pleased.
The introduction and conclusion areas are sort of my areas to
ramble on about things related to the newsletter as opposed to Pascal
specific things. So, to that end, here are some things I want to talk
about. First of all: I love getting comments and suggestions about the
newsletter. (Not quite as much as getting articles, but the comments
help a lot.) So, keep them coming. Also, I've been thinking about
dividing the newsletter into sections. Maybe having a beginners,
moderate and advanced level areas. I'd like to hear comments on this
idea. Would it help you find the stuff you want a little quicker?
I feel like I have a million things to talk about. It has been so
long since my last issue, but I would probably bore many of you. I
will just add a little about what you can expect from this issue and
then let you go on to the good stuff.
- 3 -
This issue I will start my series on Chess-Ter, a chess game
written by me and 5 others. It's not an artificial intelligence chess
program, but one that two people can play. I present it for it's
application to Pascal, not AI. The first two or three installments of
this article aren't going to go very in-depth and will only get the
surface of certain parts of the program. The idea being that you, the
reader, will tell me what parts interest you and confuse you, then in
later issues I will go back and cover things in a more in-depth
fashion. Just because of the size of the program, it is going to take
a long time cover the whole thing and I want to get the whole program
out to you, the readers, as quickly as possible. Anyway, read the
article for more information.
Bill Madison presents a method of Returning Structured Data Using
Pascal Functions. Also, we have Displaying an Integer with Commas,
Revisited. This piece, by Nathan S. Phillips is a return to a
procedure that appeared in issue #2 of the PNL. He goes into new ways
of doing the same thing and showing the good and bad aspects of each
method. This is a great lesson in program optimization. Kelly
Schwarzhoff, a high school sophmore, shows some methods of searching.
a list. And Bob Gowans, my faithful companion comes through again with
another column in the For Beginners section.
Richard Morris' article has been dis-continued temporarily. We
hope to have it continued as soon as possible.
Well, that's about it, hope you enjoy this issue.
- 4 -
Returning Structured Data Using Turbo Pascal Functions
by Bill Madison
W. G. Madison & Associates, Ltd.
8425 Greenbelt Road, #101
P. O. Box 898
Greenbelt, MD 20770
(301)552-7234
CIS 73240,342
ABSTRACT
Turbo Pascal is, without question, the development language of
choice for microcomputer applications in which portability is not an
overriding issue (C addicts to the contrary notwithstanding).
Turbo Pascal, or any dialect of Pascal for that matter, has
several serious shortcomings. One of the more important among these is
Pascal's inability to establish structured data types (with the sole
exception of strings) as a function return. This effectively precludes
the writing of many types of packages in a programmer-friendly manner.
This article explores a technique for circumventing the problem
by using the mechanism of functions having returns of type POINTER or
a variant thereof. Examples are shown, drawn from a COMPLEX unit which
has been designed, written, and used by myself.
INTRODUCTION AND MOTIVATION
I was recently given an assignment by a client which involved
extensive manipulation of complex numbers. This was not the first time
this had occurred.
Tired of re-inventing the wheel every time it occurred, and
equally tired of making interminable procedure calls to evaluate a
simple expression, he decided that there had to be a better way. IF
ONLY TURBO PASCAL WOULD PERMIT FUNCTIONS TO RETURN STRUCTURED DATA
TYPES!!! The result turned out even better than expected; a design
methodology emerged which, when implemented, would work equally well
for ANY structured data type. With minor modification, it would even
work well with data types in which,ideally, the size of the actual
data to be manipulated could not be determined until execution time;
e.g., matrices, long strings (i.e., strings whose length exceeds 255
characters).
To refresh your memory, complex numbers, which will be used to
develop this discussion, are numbers of the form R + (i*I), where i =
sqrt(-1)). In a Pascal environment, this inherently represents a
RECORD structure:
type
ComplexBaseType = record
Re,
- 5 -
Im : real;
end; {ComplexBaseType}
Mathematical rules exist which define the four basic arithmetic
operations with respect to the complex numbers. Given these rules,
other rules have been derived such that, if an operation exists for
conventional REAL numbers an analogous rule exists for the COMPLEX
numbers. Thus, one may speak of powers and roots of complex numbers,
their trigonometric functions, etc.
In order to define these operations to Pascal, they would either
need to be defined in the native compiler or the compiler would need
to be syntax extensible. Then one would be able to write, for example,
C := A + B;
where A, B, C have been declared to be type ComplexBaseType.
Yet it is impossible to expect that the plethora of unusual data
types which one might devise could be compiled in native mode.
Further, syntax extensibility is a compiler attribute not found
(unfortunately) in commercially available compilers. (The most recent
commercially available compiler having any form of syntactic
extensibility which I have seen was the FORTRAN for the CDC 1604,
built during the mid-1960's.)
An alternative, therefore, would be to permit the user to write
functions implementing desired operations, which would return
arbitrary data types as function results. Were this language feature
available, and assuming that functions to combine two complex numbers
were declared
function CAdd(A, B : ComplexBaseType) : ComplexBaseType;
function CSub(A, B : ComplexBaseType) : ComplexBaseType;
function CMul(A, B : ComplexBaseType) : ComplexBaseType;
function CDiv(A, B : ComplexBaseType) : ComplexBaseType;
one could write the equivalent of
E := (A + B * C) / D
as
E := CDiv(CAdd(A, CMul(B, C)), D);
Clumsy as this might appear at first, it is infinitely more
readable (in my opinion) than declarations of
procedure CAdd(A, B : ComplexBaseType;
var C : ComplexBaseType);
procedure CSub(A, B : ComplexBaseType;
var C : ComplexBaseType);
- 6 -
procedure CMul(A, B : ComplexBaseType;
var C : ComplexBaseType);
procedure CDiv(A, B : ComplexBaseType;
var C : ComplexBaseType);
and an evaluation of the expression as
CMul(B, C, Temp);
CAdd(A, Temp, Temp);
CDiv(Temp, D, E);
especially as one attempts to evaluate more complex expressions.
Of course, we are still not out of the woods, because Turbo
Pascal can't return structured values from functions!
ONE POSSIBLE SOLUTION
Suppose, instead of working with ComplexBaseType as defined
above, we work with
type
Complex = ^ComplexBaseType;
and then in addition to declaring our variables
var
A, B, C, D, E : Complex;
we declare the functions as
function CAdd(A, B : Complex) : Complex;
function CSub(A, B : Complex) : Complex;
function CMul(A, B : Complex) : Complex;
function CDiv(A, B : Complex) : Complex;
then we can write the above expression evaluation as
E^ := CDiv(CAdd(A, CMul(B, C)), D)^;
which, as we can see, is just as readable and convenient as the
original (with the minor inconvenience of requiring the "^" symbol on
each side of the replacement operator.
Note, however, that since all operations are being performed by
nested function calls, the normal rules of operator precedence are not
applicable. All "operators" are of equal precedence. It is therefore
incumbent on the programmer to assure that any required operator
dependency is properly managed.
If this approach of using pointer-type functions is taken, an
additional step must be included. Note that a variable of type Complex
- 7 -
is actually a pointer. Unless a pointer is initialized with something
to point to, strange things will occur very quickly when the program
is executed. Therefore, each variable, in addition to being declared
must be initialized.
Pointer variables suggest (but do not require) that the things
pointed to must be on the heap. Assume that we accept the suggestion,
and agree to store all Complex data on the heap. Further, assume a
function CInit, declared as
function CInit(A : Complex) : boolean;
which will return FALSE if and only if there is insufficient
contiguous space left on the heap. Then, prior to the first reference
to any of the variables, we would have a sequence of instructions like
if not CInit(A) then {Do error recovery};
if not CInit(B) then {Do error recovery};
if not CInit(C) then {Do error recovery};
if not CInit(D) then {Do error recovery};
if not CInit(E) then {Do error recovery};
One additional requirement must be met to use this approach
effectively; specifically, the storage of intermediate results. When a
value is returned from a function in Turbo Pascal, that value is
stored on a stack and is popped off as required. The stack maintenance
code is generated by the compiler, as part of the compilation process.
However, when we take over a part of the compiler's functionality, as
we are doing here, we must also assume responsibility for keeping
track of the structured values being returned. This is necessitated by
the fact that the function returns are pointers to the returned
values, and not the values themselves!
This is most conveniently done by establishing one or more ring
buffers, again probably (but not necessarily) on the heap. The actual
structured value is then stored in the ring buffer, and the return
from the Pascal function becomes the pointer value pointing into the
ring. The size (i.e., the number of elements) of the ring buffer
determines the maximum complexity of the expression to be evaluated.
Theoretically it would be possible to write expressions whose
evaluation would require storage of any desired number of temporary
results. A more serious threat, however, lies in the evaluation of
recursive procedure or function calls, in which a stack (or ring) of
any size could be quickly exhausted.
CONCLUSION
While no perfect solution exists for the easy manipulation of
structured data types within the confines of any dialect of the PASCAL
programming language, a methodology has been suggested which, when
properly applied, can approach this ideal.
- 8 -
The use of Pascal functions which accept and return pointer
values and allocate data storage on the heap provides a mechanism for
effectively and relatively easily and readably manipulating data
structures of any degree of complexity.
A WORKING EXAMPLE
Following is the code for a unit I wrote to implement COMPLEX
arithmetic using Turbo Pascal, along with the code for a program used
to test the unit. The code for both the unit and the test program is
available on many BBSs under the name SHCMPLX1.ZIP.
I have also used this basic technique to implement a unit for the
manipulation of long strings (up to 65517 characters), without having
to allocate the full maximum allowable length for each long string
declared. The code for both the LongString unit and its test program
is available on many BBSs under the name SHLNGST1.ZIP.
{Editor's note: The file SHCMPLX1.ZIP is included with this PNL006.ZIP
file and the code mentioned in the article is found there.}
- 9 -
Displaying an Integer with Commas, Revisited
by Nathan S. Phillips
In the second issue of the PNL, I discussed a recursive method of
displaying an integer with commas (12345 -> 12,345). The recursive
procedure provided as an example at that time has several problems.
First, being recursive, stack space is used for storage of
parameter values and calls. The program has to keep track of all
local variable values used in the procedure so that they can be
restored when the next call returns. It takes time to perform these
housekeeping tasks. Although in this particular example these are not
major concerns, you should bear them in mind when contemplating more
complex recursive routines.
The second problem with the procedure is that it is fairly
cryptic; anyone attempting to revise or debug the code would probably
spend several minutes figuring out how the blasted thing works in the
first place. More than likely, the person would then choose to
rewrite the entire procedure, resulting in more lost time. As with
the first point, this is not a major problem with the particular
routine being considered, but with a larger piece of code the amount
of wasted time could add up very quickly.
Finally, since the procedure does the output internally, you must
position the cursor before calling the procedure; the number with
commas is then simply 'spit out' at that location. This makes it very
difficult to do formatting such as right justification, because you
don't know in advance (without doing additional calculations) how long
the number will be once the commas are included. Also, to get the
output to go somewhere besides the display, you have to modify the
procedure! Not good programming practice at all. If it returned a
string, we could then put the string wherever we want to, and with a
simple Length() call, we would know how long it is.
Wouldn't it be nice if this were a non-recursive, easily modified
function which took the number as a parameter and returned a string
which was the number with commas included? Well, let's make it so:
function NumWithCommas(theNum : longint) : string;
var nwcStr, { the working string }
tempStr { a temporary string }
: string;
begin { function NumWithCommas }
nwcStr := ''; { initialize working string }
while theNum >= 1000 do { as long as we need more commas }
begin { while theNum }
- 10 -
Str(theNum mod 1000, tempStr); { put the last 3 digits }
{ of theNum in tempStr }
while Length(tempStr) < 3 do { pad tempStr with }
tempStr := '0' + tempStr; { '0's on the left }
nwcStr := ',' + tempStr + nwcStr; { add comma & digits }
{ to working string }
theNum := theNum div 1000; { discard the 3 digits }
{ we just took care of }
end; { while theNum }
Str(theNum,tempStr); { now theNum is less than 1,000 }
NumWithCommas := tempStr + nwcStr; { put first digits }
{ at the beginning }
end; { function NumWithCommas }
This function has very little overhead, is easier to revise and
debug, and is generally more useful.
(Sidebar to technically inclined: I tested both forms of this
routine using Turbo Profiler and found, to my surprise, that the
non-recursive function version shown here is faster by a small amount.
I was sure that the string operations it uses would make it
considerably slower - any ideas what this isn't so? I forced this
function to write the result before returning, so the 'output
slowdown' should have been the same for both routines.)
Now, how does one go about using this new function? Suppose you
wish to inform the user of the number of bytes that the current
directory is taking up on the hard disk. A typical method is:
writeln(bytesUsed:1, ' bytes used for directory ',dirName);
which produces:
1348857 bytes used for directory FOO
With NumWithCommas, you can dress up the output very easily:
writeln(NumWithCommas(bytesUsed),' bytes used for directory',
dirName);
which produces:
1,348,857 bytes used for directory FOO
- 11 -
But the old recursive procedure could do that! Why did we go to
the trouble of rewriting it? Suppose there are several directories
for which you want to display size information in column format. With
the old DisplayWithCommas, you had to settle for:
for i := 1 to numDirs do
begin
for j := 1 to 8-Length(dirName[i]) do
write(' ');
write(dirName[i],' - ');
DisplayWithCommas(bytesUsed[i]);
writeln(' bytes');
end;
which produces:
FOO - 1,348,857 bytes
LABELS - 243,567 bytes
UTIL - 16,344,059 bytes
FAKEDIR - 1,024 bytes
Now with NumWithCommas as a function, you can do this:
for i := 1 to numDirs do
begin
for j := 1 to 8-Length(dirName[i]) do
write(' ');
write(dirName[i],' - ');
wcStr := NumWithCommas(bytesUsed[i]);
for j := 1 to 10-Length(wcStr) do
write(' ');
writeln(wcStr,' bytes');
end;
producing:
FOO - 1,348,857 bytes
LABELS - 243,567 bytes
UTIL - 16,344,059 bytes
FAKEDIR - 1,024 bytes
The combination of commas and formatting makes it very easy for
the user to determine at a glance the relative magnitude of each
value. And the easier your program is for the user, the more likely
it is to be used (and, hopefully, paid for).
- 12 -
Chess-Ter
By Pete Davis
Well, I mentioned in a previous issue that I would do this
article and, after a good deal of procrastination, I finally got
started on it. Part of the delay is just due to the volume of the
program itself. The code is broken into 8 units and comes to over 4800
lines of code. This sheer volume makes it a little difficult to handle
in the newsletter. I have decided to break up the article into either
two or three parts, initially. The two or three parts would be sort of
a quick overview and between those two or three, the entire source
code would be released.
For example, in this issue, I plan on talking about the
CHESSTER.PAS, GLOBALS.PAS, KB1.PAS and DRAW_PCS.PAS. I will only
release the source code for those parts of the program with this
issue. Then, in the next issue, I will release the source code to the
other parts of the program I discuss and, if necessary, I will release
anything remaining in the third part.
I am doing a rather brief overview at first so that I can get out
the different parts of the program quickly. After the entire program
has been released, I will back-track and talk about some of the more
technical aspects of the program and discuss ways of improving the
code and so-forth.
First, I suppose I should provide some sort of background on
Chess-Ter. Last semester I took a class called Software Engineering.
The main thrust of the class was putting together large projects. I've
thought about concentrating on that issue in a series in the
newsletter, but unless I get some requests, I'm going to hold off on
that. Anyway, about two weeks into the semester we got our assignment,
which was due at the end of the semester. The project was a Chess
program that two people could play. This is not an AI chess program,
it only lets two people play. The AI part is left for you, if you
dare.
Anyway, I got into a group of 5 other programmers who turned out
to be very hard working. Good thing, because I'm not and without the
push from the rest of the group, a project like this would not have
been done by me. So, I would first like to name all the authors and
point out their contributions:
Mark Friedman - Did most of the chess pieces and the board. He also
did the Handle Moves Request and Handle Take-Back Request.
Jessica Chestnut - Did most of the checks for legal moves. (A very
impressive feat for someone who had never played chess until a couple
days before the project was completed.)
Akiko Okamoto - Did the Load and Save games file handling.
- 13 -
John Loux - Wrote the main keyboard interface and the central
procedure of the program.
Paul Sternal - Wrote the Replay procedures that allow for game
replays.
and Me - I did the Check for Check and Check for Check-Mate
procedures. I also did the intro screen and the screen interface.
(With the exception of the board and pieces.)
That about covers the intro to the project. There are a few
things I'd like to bring up, though. First of all, the program is
copyrighted and the source code is released not just from me, but from
the entire group (collectively known as The Pascal Team). Also, I had
considered cleaning the program up before writing this, but then it
occurred to me that leaving in some of the problems might be useful in
discussion of improvements for the program. I hope to bring some
improvements into the program through future issues.
Well, let's get started. First of all, I guess I should discuss
the main program file, CHESSTER.PAS. Not a whole lot to discuss. It
includes all the necessary units: Globals (discussed later), CRT, KB1
(discussed later), DOS, and Draw_Pcs. The screen is initialized, the
game is initialized, the board is drawn, text displayed and finally
Get_Keyboard is called, which is an iterative procedure that keeps
going until the game is quit. Then the endprompt is shown. Not a whole
lot in the main program.
For large projects it's a good idea to keep the main program
itself rather small. This helps to enforce the idea of modularity, or
breaking your programs into smaller pieces.
The first unit I want to discuss is GLOBALS. GLOBALS contained
all the type definitions and procedures which were common throughout
the program. I want to point out that this wasn't always the case.
This was the desired result, but sometimes it turned out that a
procedure we thought would be used globally, turned out only to be
used one place, or vica-versa. The representation of our board was, of
course, a key concern, but even more important was the current state
of the game. We felt the best way for all the different procedures to
share information was to create a variable type of Game_State. The
Game_State had everything from a 2 dimensional array of all the pieces
on the board to the current move number, whose move it was and what
mode the game was playing in. (A short note about the modes. The game
has a novice and expert mode. The novice mode allows the ability to
take back moves and find out what all the legal moves for a given
piece are.) The game state also kept various flags about current
moves.
Along with the game_state there is also a move history which
keeps track of all the moves made. This is basically an array of the
Move_Type. The Move_Type contains the pieces from and to locations,
- 14 -
the piece color, the piece_type, what kind of piece was taken, if any,
and what the move type was (i.e. castle, check, mate, and other
exceptional conditions).
Although it is usually considered bad practice to keep global
variables, in this case we found it necessary and sometimes it is. We
kept several things global: The current game state, the current move,
the move_history and the list of legal moves for the current moving
piece.
Now I'd like to get into the graphics a bit. Here is something
that is mentioned in the Turbo manual and has turned out to be a very
useful feature. Instead of having the BGI files we needed loaded at
run-time, we decided to have them linked in at compile-time. This has
several advantages: First of all, it keeps you from having to keep
track of more than one file in the run-time program. It also saves a
bit of trouble, I feel.
In this program we used EGA mode. This was done mainly because
that was the only graphics I had and since I did a lot of the
graphics, I had to have it compatible with my system. So, here's how
we handle the compile-time linking of BGI files. (I also did this with
the Gothic character set included with TP.) Since we are working with
EGA, used the EGAVGA.BGI file. I changed this to an object file using
BINOBJ.EXE. I then typed, from the DOS prompt, with EGAVGA.BGI and
BINOBJ.EXE in the current directory:
BINOBJ EGAVGA.BGI EGAVGA.OBJ EGAVGA
This turns the .BGI into a .OBJ and gives it a public name of
EGAVGA (Don't worry about that last part, just stick to using the part
of the filename before the period and you should be fine.) I followed
this by doing the same thing to the gothic character set:
BINOBJ GOTH.CHR GOTH.OBJ GOTH
This turns the .CHR file into a .OBJ file also. Then in the
GLOBALS procedure I link both of these .OBJ files into the main
program as follows:
procedure EGAVGA; external;
{ The procedure name must match the Public name given above. }
{$L EGAVGA.OBJ}
{ the $L, above actually links it in. }
procedure GOTH; external;
{ Just like above: }
{$L GOTH.OBJ}
- 15 -
That's all there is to it. You now have the .BGI files linked in.
Now, to actually use those .BGI routines you need to register them
with TP. This is all done in the InitScrn procedure in the GLOBALS.PAS
file.
Some of the other important procedures included the Prompt
procedure which put a line of text on the 23rd line of the screen.
This was basically used to send some sort of message to the user.
There was also a beep procedure that went well with the prompt
procedure.
Then a Query procedure was added, which worked just like the
prompt procedure, but then read in a line of text from the user so
that a response could be returned. Then there is the Error_Display
procedure which is like Prompt, but in a different color to help grab
the user's attention.
The next thing on our list is the InitGame procedure. Basically
this is called everytime you start a new game. This initializes all
the conditions in the game and finds out whether the user want's
expert or novice mode. Also initial positions for all the pieces are
set. This should all be very straight forward.
One thing you might notice in the InitGame procedure is the very
beginning. The code starting with SetFillStyle(8, Blue) through
OutTextXY(370,220,'(C) ... this is the opening screen. Using the
simple Gothic font and some easy to use graphic procedures, Turbo
Pascal let's you do some very nice opening screens.
The Convert_Rank and Convert_File procedures were used to convert
the board positions (A1-H8) to screen pixel positions. This was
necessary since we were using a board that was 8x8 in concept, but
actually several hundred pixels in length and height.
The Display_Move_History updates the Move_History that is shown
on the screen. Basically it's a list of all move made since the game
began. This, again, is done in a fairly straight-forward way, except
for one thing. I used the assignment: directvideo:= false; before
doing any screen writes. This allows you to write text into a graphics
screen.
The show_text procedure, like the Display_Move_History turns
directvideo off. All it really does is displays the text on the
screen, other than the move_history. It is straight-forward and easy
to follow.
The next unit I want to cover is the Draw_Pcs unit. This one is
very simple to follow. It was more of a tedious routine to put
together than a complicated routine. Basically you sit and draw your
pieces one line at a time and keep looking at them on the screen until
they look good. In this case, the pieces were drawn by Mark Friedman,
- 16 -
who spent a lot of time drawing the pieces out.
I would like to point out one improvement we encountered when
writing this. Originally Mark wrote the procedure using for-do loops
and the putpixel procedure to draw the pieces. This turned out to be
very slow, so we ended up replacing all the putpixels and for-do loops
with lineto procedures. This resulted in a huge time savings. You'll
notice that the squares are still drawn using the putpixel routine. We
left this that way for the visual effects it provides. That's really
all there is to the Draw_Pcs.
The last unit we will be discussing in this issue is the KB1
unit. This Get_Keyboard procedure at the end of the unit is the
center-piece for the entire program. It is where the user's input is
handled. It checks to make sure certain keystrokes are valid for the
current mode. (Expert or Novice). It takes care of check-mate.
Basically the routine is centered around a repeat-until loop that
reads the keyboard input and then uses a case statement to process
different requests from the user.
Going back to the beginning of the unit we have the Arrow_Moves
procedure. This reads in the keypad arrows and uses them for cursor
movement in the game. It also checks to make sure the user stays on
the board and doesn't try to roam off.
Following that are two Beep routines (Beep2 & Beep4) These,
looking back, probably belong in the Globals unit with Beep, but we
will discuss that later when we talk about ways to improve the
program.
The Select_A_Piece procedure changes the color of a piece on the
board after the user has selected that piece to be moved. Following
that is DeSelect which then turns the piece back to it's previous
color.
The Check_Move_Piece procedure takes care of picking up and
moving pieces on the board. IT calls the logic procedures(Legal_Move)
to see if the moves are legal. We'll get involved in the logic part in
a later issue.
The Check_Legal_Piece checks to see if the piece the user has
selected is a piece on his side.
And the final procedure is the Handle_New_Game_Request which
basically re-initializes the game state and board.
Now, I know what you're thinking. You think I've shot through
this program without a whole lot of explanation and you're right. I
want to give you a quick overview of everything first and when we've
covered the entire program I will back-track and go in-depth into
parts we've only touched on now.
- 17 -
The entire program is very large and represents a lot of work
done by six people. There are errors and the code is not perfect, but
I believe that showing some of the mistakes we made can help prevent
you from making the same ones.
- 18 -
Searching
By Kelly Schwarzhoff
Internet schwarzhoff@f103.n914.z8.rbbs-net.org
Rbbs-Net 8:914/103
Fidonet 1:125/41
For anyone who is planning on taking a Pascal class there comes a
time when he/she must make a search program. For me that happened two
weeks ago in my high school AP Computer Science class. I had to make
a program that would search for a certain inventory part and print out
the inventory or "not found" if there are none. In the following
examples I assume you're using the following type definitions:
list=record
id:integer;
inv:integer;
end;
parts=array[1..5000] of list;
I also assume you have defined variable a to be a variable of
type parts (this is the raw data) and a variable count to be of type
integer (this is how many different parts there actually are).
Finally, I expect the id #'s to be pre-sorted from smallest to biggest
(see PNL #3 for an excellent article on sorting).
There are two main type of searches. The easiest way is a
sequential sort that simply goes through the list and will search for
a particular number.
Although the sequential sort is nice and easy, it is extremely
slow. Luckily for us there is a faster (and harder) way called a
binary search. Binary search requires the data to be sorted in order
of the item-type you are searching for. The procedure will set two
variables (called b and z in the program) to be at each end of the
parts array. It will then create a variable mid that will equal the
middle of b and z ( (b+z) div 2). It will then check to see what the
value of the id number of mid is (a[mid].id) and make an if then else
if check. If the number is equal to the number you're looking for
(a[mid].id=look) then you found it and it will return that number. If
the mid is greater than the number then it is in the lower side of
your list in which case you set the right hand side variable to right
below mid. If the mid is less than the number then the number you're
looking for is in the lower side of your list in which case you set
the left-hand variable to right above mid. This continues until the
two variables either collide or you find the variable. If the id #
you're looking for is never found the function will return -1.
For those of you who want the technical speeds of the searches,
sequential is on average an O(N/2) search and binary is an O(log2 N)
search.
- 19 -
If you have any questions feel free to contact me at the listed
network addresses.
{Editor's Note: Two files included with PNL006.ZIP are SEQUENT.PAS and
BINARY.PAS. These are related to this article.
A note about the author. Kelly Schwarzhoff is a sophmore in high
school. I bring this up, mostly to point out that the articles in this
newsletter are not written by PhDs in Computer Science. One of the
most common compliments about the newsletter is that it's written by
regular people like you and me, so go ahead and send in an article!}
- 20 -
For Beginners
by Bob Gowans
In this issue of PNL I thought we could develop a programming
project based on the knowledge we have obtained from previous issues
of PNL. As wordprocessors are familiar to us all I have decided to
build our project around text manipulation. First, it will involve
counting the number of words in a line of text. Second, calculating
the length of a line of text. Both procedures are obviously simplified
versions of those a commercial wordprocessor would make use of to
invoke word wrap and set text between left and right margins, however
the principle of problem solving, program design and program coding is
the same whether the project is large or small.
Before running to the nearest PC and hastily churning out the
code for our project lets stop and think a while about program design
and any constraints we may have to impose on the program. Program
constraints will be given, bearing in mind the knowledge that has been
obtained from the last five articles in the beginners column.
Obviously there may be better ways to implement the program than the
way suggested, but we must write the program within the confines of
what we know. It is not unusual for programmers to have constraints
placed upon them - for example financial constraints could influence
the implementation of one design over another.
Wordcount/Line length -
A line of text is to be processed, each word is followed by a
single space including the last word in the line. The line is
processed to determine the total number of words. We can assume that
the line of text is entered by the user from the keyboard and at least
one word will be entered. The result, the total number of words in a
line is printed to the screen. In addition a count of the total number
of characters in the line, including spaces, is calculated. A line
length is then calculated in inches based on an assumption that 10
characters will be one inch in length.
The design for this process must involve a loop that scans the
text, looking for the single space between the words, it must also
involve a counter to keep track of the number of spaces. How will the
loop be terminated? ie. as the line of text is scanned how will the
program know it has reached the end of the line. We can make the
decision that the end of the line will include a space then a special
character, % (percent). Also,the loop must make a count of all the
characters in the line, excluding the final space and the special end
of line character (%).
Pseudo-code
1. read in first character
2. initialize variables updated in loop
- 21 -
3. loop while there are characters in the line of text
4. process characters
5. read in next character
6. loopend
7. calculate total number of words
8. calculate length of line of text
9. write out total number of words
10. write out length of text
Assuming that the character to be processed is held in the
variable called character, step 3 can be refined as follows :
3.1 loop while character <> percent sign
The end of each word is marked by a space so if the character
being processed is a space we can update a variable spacecount by 1,
if the character being processed is anything else we update the
variable lettercount by one.
4.1 if character = space
4.2 then
4.3 update spacecount by one
4.4 else
4.5 update lettercount by one
4.6 ifend
The variables spacecount and lettercount are initialized in step 2 and
are further refined below:
2.1 set spacecount to zero
2.2 set lettercount to zero
Step 7 does not really need refining as the total number of spaces is
equivalent to the total number of words in the line of text. When the
loop is terminated spacecount will contain the value for the total
number of words.
For the sake of clarity we will write step 7 as follows:
7.1 set totalwords to spacecount
Step 8 however, requires a bit more thought. The length of a line of
text in inches is given by the total number of characters divided by
10. The total number of characters would be calculated by adding
lettercount and spacecount minus one (the last space on the line is
not counted). This would give the total number of characters including
spaces. To complete the calculation the total number of characters is
divided by 10 and the result printed out, in inches, to 2 decimal
places.
8.1 set totalcharacters to lettercount + spacecount - 1
8.2 set linelength to totalcharacters/10
- 22 -
The final design is as follows:
1. read in first character
2.1 set spacecount to 0
2.2 set lettercount to 0
3.1 loop while character <> percent sign
4.1 if character = space
4.2 then
4.3 update spacecount by one
4.4 else
4.5 update lettercount by one
4.6 ifend
5. read in next character
6. loopend
7.1 set wordcount to spacecount
8.1 set totalcharacters to lettercount + spacecount - 1
8.2 set linelength to totalcharacters/10
9.1 writeout 'Total words in text line = ',totalwords
10. writeout 'Length of line of text = ',linelength,' inches'
Implementation of the design
The Pascal coding of the design should not present any problems
as we have covered most of the issues before. However I would like to
introduce constants into this particular code. Constants are used to
give a fixed value to an identifier. The system uses constants such as
Boolean values or the set of integer values, these are internal
constants set by the system. Constants can also be named by the user
as illustrated:
const
interest_rate = 0.15;
The Pascal reserved word CONST must come before the constant
definition. Constant definitions are placed, in order of program
sequence, before variable declarations as you will notice in the code
below. Notice also that the assignment symbol for a constant is simply
an equals (=) sign and not the Pascal assignment symbol (:=). The
advantages of using named constants are that you can make your code a
lot more readable if you use them wisely. When using constants it is
useful to bear in mind the possibility of your program being updated.
In the example above, the constant definition of interest_rate could
be used in a program that calculates loan repayments. We all know too
well how interest rates fluctuate so it is advantageous to declare
interest rate as a constant. When it comes to updating the program, as
a new interest rate is given, we simply have to change the constant
definition line. All references to interest_rate in the program are
then automatically updated, saving you a lot of work!
- 23 -
Constructing a data table for the design:
IDENTIFIER DESCRIPTION TYPE
space the space character ' ' constant
line_end the percent character '%' constant
cpi characters per inch constant
character characters input by user char
spacecount counter of space characters integer
lettercount counter of letter characters integer
total_chrs holds total number of
letters and spaces integer
total_words holds total number of words integer
line_length length in inches of 10
characters real
Here's the code to our design:
program process_line;
{By R.Gowans 7/2/91 - Manchester Polytechnic Didsbury}
{Calculates number of words in a line of text as input by the user and
outputs the result to the screen. Calculates line length given there
are 10 characters per inch and outputs results to screen.}
const
space = ' ';
line_end = '%';
cpi = 10;
var
character : char;
spacecount,lettercount,total_chrs,total_words : integer;
line_length : real;
begin
writeln('Input a line of text, each word must be followed by a');
writeln('space,the line must be terminated by a pct sign (%)');
writeln;
write('Enter line > ');
read(character);
spacecount := 0;
lettercount := 0;
while character <> line_end do
begin
if character = space
then
spacecount := spacecount + 1
else
lettercount := lettercount + 1;
- 24 -
read(character)
end;
total_words := spacecount;
total_chrs := lettercount + spacecount - 1;
line_length := total_chrs/cpi;
writeln;
writeln('Total words in text line = ',total_words);
writeln;
writeln('Length of line = ',line_length:4:2,' inches')
end.
You will have probably noticed that there are a lot of 'What
if's???' about this program and if it has raised some questions in
your mind, well that is the intention. Some of the questions I hope
you may be asking yourself are:
1. What if the character read in is not a space, letter or a
percent sign?
2. What if the first character is a percent symbol?
3. What if there is more than one space between the words?
You can probably think of more questions which will reveal the
weaknesses of this program and it is fitting to be critical in order
to make the best possible,positive modifications to a program. I will
leave you to think about the question of data checking, it is an
essential part of any non-trivial program. Try predicting what the
program will do when you enter unusual data then try it out! A word of
warning - be sure you know how to break out of a program if you are
attempting the unpredictable, the usual sequence on a PC is to hold
down the CTRL key and press c or break.
- 25 -
Conclusion
Well, that about wraps up this rather hastily assembled issue of
the newsletter. I'm sorry for taking so long and I hope to be able to
do another issue before summer, but I can't promise anything. Either
way, I plan on trying to make up for it this summer by putting out 4
or 5 issues over the summer.
I really need your help. The readers who contribute really make
this happen and unless I receive articles from the user, it's going to
take longer and longer between issues. Eventually, if I have to carry
the load of writing the entire newsletter, it will fade away. I don't
want to see that happen, so please try to help out. Try to set aside a
few hours on a weekend and put something together for us here.
I'm still not too sure about what's in-store for the next issue.
I haven't really thought about it too much. I will do more on Chess-
Ter and surely Bob will be back with For Beginners. I hope to have
Richard back writing his articles on Graphics in TP. I haven't
published anything about TP6.0 because frankly, I haven't had a chance
to use it myself, yet, and I haven't received anything from my readers
on it, so if there are those of you that have gotten familiar with
TP6.0, I'd sure like to see some reviews.
Oh well, enough begging on my part. I'll leave the rest up to you
guys. I'm off to complete what is left of my vacation. Hope you
enjoyed the issue and I'll write to you in the next issue.
_Pete Davis
- 26 -
The Pascal NewsLetter is Copyrighted by Pete Davis. Articles
submitted by others are the property of the authors and are used
with permission. They may not be treated seperately from this
newsletter without the author's permission and thus maintain all
distribution rules of the newsletter as a whole. It may be freely
distributed in un-modified form, but no charge whatsoever may
be incurred on the recipient. All code is provided 'as-is' with no
guarantees whatsoever.
The Pascal NewsLetter can be obtained from the following
locations:
GEnie : General Electric Network for Information
Exchange. It is located in the IBMPC
filelist.
Simtel : Internet address: 26.2.0.74 or
Simtel20.ARPA It is located in the
<MSDOS.PASCAL> directory.
Programmer's Forum : This is the home of the PNL.
Each issue can be found in
the PNL directory from the main area.
The number is on the title page.
If you would like to receive back issues of PNL directly
from me, send a diskette and $2.00 for shipping. Don't forget
to include your address.
Send your order to:
Peter Davis
4851 Brandywine St. NW
Washington, DC 20016
If you are a SysOp that will regularly carry PNL and would
like to have your bulletin board listed as such, here, send me a
message either by postal mail or at one of the electronic addresses
given on the title page, with your bulletin board's name, phone
number, and your name.
- 27 -
The Pascal NewsLetter Distribution List
BBS | Fidonet Address | Phone #
--------------------------+----------------------+---------------
The Bored | 1:397/3 | (512) 303-0471
Classic City BBS | 1:370/10 | (404) 548-0726
Thieve's World BBS | 1:106/805 | (713) 463-8053
Hippocampus BBS | 1:141/205 | (203) 484-4621
Rogers State College | 1:170/711 | (918) 341-8982
The Foxtrot BBS | 1:272/26 | (914) 567-1814
Turbo City BBS | 1:208/2 | (209) 599-7435
Austin IEMUG/MIDI BBS | 1:382/14 | (512) 258-0626
Laser Publishers | 1:170/403 | (918) 438-2749
Fargo RBBS-PC | 1:10/8 | (701) 293-5973
Momentary Lapse of Reason | | (704) 327-6361
The Demon's Den | | (508) 433-2702
The Cannibal Cafe | | (508) 840-6589
IBM Tech FIDO | | (508) 433-6491
The User Friendly BBS | | (704) 323-8223
KHIRON Software-Mail Only | 3:640/378 | 61-7-878-1194
Beyound Frontiers BBS | 2:230/101 | (+45)8694-1609
Collision Theory | | (703) 503-9441
Merlin's Mailbox | 2:245/39 |
Ed-Net 9600 | 1:153/734 | (604) 732-8877
EILC BBS | 1:3610/60 | (407) 676-2998
Polysyncronism BBS | | (708) 358-5104
(Name Unknown) | | (315) 592-7300
- 28 -
