CS130 Pascal Templates

Disclaimer: This document was created by exporting a Microsoft Word document to HTML with some minimal manual cleanup. The process leaves a lot to be desired.

-- Byron Weber Becker

Background

This set of templates was developed to accompany CS130 -- an introduction to programming course taught in Pascal. Templates were used in class to summarize what was done. Students had paper copies (from which this document was derived); the code portions were available on-line.

Table of Contents

Binary Search

Counter-Controlled Loop

EOF-Controlled Loop

Finding a Max or Min

For Loop

Function

Insertion/Deletion in a Sorted Array

Iteration Over an Array

Linear Search (Sorted)

Linear Search (Unsorted)

List Deletion (Sorted)

List Insertion (at Head)

List Insertion (Sorted)

List Search (Sorted)

List Traversal

Procedure

Program

Reading from a File

Repeat-Until Loop

Sentinel-Controlled Loop

Validating Input

While Loop

Writing to a File

Yes

Templates are commonly used pieces of code that can be easily modified to suit a new environment. A good programmer will have a mental library of many templates that can be quickly inserted into a program.

The parts of a template are:

Some templates are missing one or more of these attributes. Perhaps because it’s not applicable or the right inspiration has not yet struck the author. Suggestions for improvement are welcomed by any of the instructors, but most especially by Byron Weber Becker, bwbecker@dragon.uwaterloo.ca, x4661.

Binary Search

Explanation

Search an sorted array by eliminating approximately half the remaining elements after each comparison.

Pseudocode

if subarray[left..right]is empty 
then search failed
else if subarray[middle] = key 
then found item
else if key < subarray[middle] 
then 
   search left subarray
else 
   search right subarray

Analogy

Most people instinctively use this method to guess a number in a number guessing game.

Illustration

Debugging and Testing

  • When debugging a new program, make sure the array passed to binary search really is sorted.
  • Search for elements smaller than the first element, larger then the last element, the first element, the last element, an element occurring in the middle of the array and an element that would occur in the middle — but isn’t present.

Pascal Code

function  BinSearch(A : ‹tArray›; left, right : ‹indextype›; 
Key : ‹KeyType›) : integer;
   var    middle : ‹indextype›;
      BStemp : integer;
begin 
   middle := (left + right) div  2;













   BinSearch := BStemp;
end ; {BinSearch}

Related Templates

  • Linear Search (Sorted)
  • Linear Search (Unsorted)
  • List Search (Sorted)

 

 

 

Counter-Controlled Loop

Explanation

Count the number of iterations of the loop to determine when to stop.

Pseudocode

initialize counter
initialize final value
while counter is less than final value
   do something
   update counter

Analogy

A kindergarten class with 20 students is going on a field trip. The bus driver counts until 20 kids are on board and then closes the door and leaves.

Illustration

Debugging and Testing

  • In the while version, failure to initialize the counter or to increment it can cause unpredictable results or an infinite loop, respectively. The for version avoids these problems.
  • An equivalent loop starts at 0 and continues while the counter is strictly less than the final value. Other loops may use other initial values, depending on the context.

Pascal Code

{While version}
counter := 1;
readln(num_items);
while   counter <= num_items do begin  
   ‹body›;
   counter := counter + 1;
   end  ;

{For version}
readln(num_items);
for   counter := 1 to   num_items do begin  
   ‹body›;
   end  ;

 

 

Related Templates

  • While Loop
  • For Loop
  • Sentinel-Controlled Loop
  • EOF-Controlled Loop

EOF-Controlled Loop

Explanation

Read data values until the operating system says there are no more to read.

Pseudocode

while values remain
   read an item
   process the item

Analogy

A kindergarten class is going on a field trip. When everyone has boarded the bus, a school official tells the driver that everyone is on and it is time to close the door and leave.

Illustration

Debugging and Testing

  • The order of reading and processing an item is reversed from the Sentinel-Based Loop. Also, no priming read (the read before the loop is entered) is required.

Pascal Code

{Sentinel is the EOF condition.}
var   
   InFile : Text;

OpenFile(InFile, 'myfile', OpenRead);

while    not    eof(InFile) do begin   
   readln(InFile, item);
   ‹process item›
   end ;

close(InFile);

Related Templates

  • While Loop
  • Reading from a File
  • Sentinel-Controlled Loop

Finding a Max or Min

Explanation

Identify one individual in a group according to a maximum or minimum attribute.

Pseudocode

Initialize MaxSoFar
while more items
   if current item is greater than MaxSoFar
      save current item as MaxSoFar
   read next item

Analogy

Go through a pile of pennies, always keeping the oldest penny in your hand.

Illustration

Debugging and Testing

  • In method 1, initializing MaxSoFar fails if there are no items in the group — hence the test for an empty file.
  • Method 2 uses an impossibly small value to ininitialize a maximum and an impossibly large value to intialize a minimum.

Pascal Code

if ‹file not empty› then begin   {Method 1}
   ReadLn(MaxSoFar);
   ReadLn(‹item›);
   while  ‹more items› do begin  
      if  ‹item›  > MaxSoFar then 
         MaxSoFar := ‹item›;
      ReadLn(‹item›);
      end  ;
   end;

MaxSoFar := ‹minimum value›;   {Method 2}
ReadLn(‹item›);
while  ‹more items› do begin  
   if  ‹item›  > MaxSoFar then 
      MaxSoFar := ‹item›;
   ReadLn(‹item›);
   end  ;

Related Templates

  • Sentinel-based loop

For Loop

Explanation

Repeat a group of statements a specific number of times.

Pseudocode

‘C’:

int   i;
for(i=1; i<10; i=i+1) {
   <something to do>
}

Turing:

for i: 1..10
   <something to do>
end for

 

 

 

Pascal:


			

The for loop is exactly equivilent to:

var   i : integer;
i := 1;
while i <= 10 do
   begin
   <something to do>
   i := i + 1;
   end;

Description

Consider the loop

for  i := first to  last do  begin  
   WriteLn(i);
end ;

This loop will print all the values between first and last, inclusive. If first is larger than last, the loop does not execute.

It is possible to substitute the keyword downto for to. In that case, first should be larger than last and the index variable counts backwards.

Illustration

Debugging and Testing

  • As with the while loop, test the boundary cases — 0 iterations, 1 iteration, maximum number of iterations — as well as the normal case of several iterations.
  • Changing the loop index may cause unpredictable results. Better compilers will not let you do it.
  • The loop index’s value is undefined after the loop ends.

Pascal Code

var  i:integer;
for  i := 1 to  10 do  begin  
   ‹something to do›
   end  ;

for  ‹var› := ‹initial value› to  ‹final value› do  begin  
   ‹body›
   end  ;

for  ‹var› := ‹initial value› downto  ‹final value› do  begin  
   ‹body›
   end  ;

Related Templates

  • While Loop
  • Counter-controlled Loop
  • Repeat-until Loop

Function

Explanation

Break a larger program into smaller pieces, each of which has a clearly identified purpose contributing to the solution of the overall problem. A function generally returns exactly one result which is used in an expression.

Pseudocode

function <name>(<parameters>):<type>;
   constant declarations
   type declarations
   procedures and function declarations
   variable declarations
   body
      <name> := <result>;

Analogy

The owner of a company cannot do all the work. She hires people to solve certain problems — manage production, collect bills, advertise, etc. — and delegates responsibility to them to accomplish their task. They may, in turn, hire additional people and do additional delegation to do their work.

Illustration

Debugging and Testing

  • Make sure that parameters passed in contain legitimate values.
  • It is often possible (and desirable!) to test a function with a simple program (called a driver). This can make it easier to test many different cases directly
  • Standard Pascal only allows scalar types (integers, reals, enumerated types, subrange types) to be returned from functions. Many implementations also allow most types.

Pascal Code

program  Doit;

   function  Average(a, b: integer):real;
   begin 
      Average := (a + b) / 2.0;
   end ;
var
   avg : real;
begin 
   avg := Average(10, 11);
   WriteLn(avg);
end .

 

 

Related Templates

  • Program
  • Procedure

 

Insertion/Deletion in a Sorted Array

Explanation

Insert into or delete from an Sorted array.

Pseudocode

Insertion:

Find position for new element
Move all elements after this position down 1
Insert new element

 

Deletion:

Find position for new element
Move all elements after this position up 1

Analogy

All students in a class are to sit alphabetically in desks with all the empty desks at the back of the room. When a new student enters the class, all students with names after the new student’s name must shift one desk over.

Illustration

Debugging and Testing

  • Make sure there’s room in the array for an inserted element.

Pascal Code

{To be inserted by the student.}

Related Templates

  • Linear Search (Sorted)
  • While Loop

Iteration Over an Array

Explanation

Iterate over an array when you need to do something to every element — initialize, output, etc.

Pseudocode

for each element
   do something

Analogy

Members of a kindergarten class are put in a line. The teacher goes down the line in order asking each student to answer a question.

Illustration

i points to each element of the array, in turn.

Debugging and Testing

  • Do not access memory outside of the array. Always use the range checking compiler options to make sure.

Pascal Code

type 
   ‹Range› = ‹First› .. ‹Last›;
   ‹ArrType› = array [‹Range›] of  ‹ElemType›;

var 
   ‹Arr› : ‹ArrType›;
   i : ‹Range›;

for  i := ‹First› to  ‹Last› do  begin 
   ‹do something›;
   end ;

 

Possibilities for ‹do something›:

{Initialize each element to 0.}
‹Arr›[i] := 0;

{Read elements from a file.}
ReadLn(‹Arr›[i]);

{Print contents:}
WriteLn(‹Arr›[i]);

Related Templates

  • For Loop
  • Insertion/Deletion in a Sorted Array

Linear Search (Sorted)

Explanation

Search a sorted array by examining each element in turn. Stop when an element larger than or equal to the key is examined.

Pseudocode

if array is empty or key goes after end of array then
   failed
else
   while element < key
      move to next element
   check if last element examined is the key
Analogy
Illustration

Debugging and Testing

Pascal Code

{Purpose:   Search for key in sorted array A.  If found, return Pos such    }
{         that A[Pos] = Key.  Set Success to true.  If no found, set   }
{         Success to false and Pos such that  A[1..Pos-1] < Key and   }
{         A[Pos..last] > Key.   }
procedure  LinSearch (A: ‹tArray›; key : ‹tKey›; 
         var  Pos : integer; var  Success : Boolean);
begin  

{Check if we'll stop before we get to the end of the list.}
if  (‹last› = 0) | (key > A[‹last›]) then  begin  
   {Belongs after the end of the list.}
   Pos := ‹last› + 1;
   Success := False;
   end  
else  begin  
   {The correct position is somewhere before the end of the list.}
   Pos := 1;
   while  A[Position] < Key do  
      Pos := Pos + 1;

   Success := A[Position] = Key;
   end  ;
end  ;   {Search}

Related Templates

  • Linear Search (Unsorted)
  • Binary Search
  • List Search (Sorted)

Linear Search (Unsorted)

Explanation

Search an array by examining each element in turn.

Pseudocode

while item not found and end not reached
   examine next element

return result of search
Analogy
Illustration

Debugging and Testing

Pascal Code

function  LinSearch (A ‹tArray›; key : ‹tKey›) : integer;
var 
   pos : integer;
begin 
   pos := ‹First›;
   while (pos < ‹Last›) and (Key <> A[pos]) do 
      pos := pos + 1;

   if  key = A[pos] then 
      LinSearch := pos   {Success}
   else 
      LinSearch := 0;   {Failure}
end ; {LinSearch}

 

 

Related Templates

  • Linear Search (Sorted)
  • Binary Search
  • List Search (Sorted)

 

 

 

List Deletion (Sorted)

Explanation

Delete a node from an sorted linked list, preserving the sort.

Pseudocode

 

 

 

 

 

 

 

Analogy
Illustration

Debugging and Testing

 

 

Pascal Code

procedure  Delete (
      var  Head: ‹NodePtr›;   {the linked list}
           key: ‹KeyType›;   {key to the node to delete}
      var  Success: boolean);   {true IFF node found and deleted}


















end ; {Insert}

Related Templates

  • List Traversal
  • List Insertion (at Head)
  • List Insertion (Sorted)

 

 

List Insertion (at Head)

Explanation

Insert a new node at the head of a linked list.

Pseudocode

Make the new node point to what the head
   points to
Make the head point to the new node

Analogy

A line of children is organized by a teacher who always chooses the next child, placing her at the front of the line.

Illustration

Before

After

Debugging and Testing

  • Head must be either nil (the empty list) or pointing to a valid list.

Pascal Code

procedure InsertAtHead(
   var  Head : ‹NodePtr›;    {Head of the list}
      NewNode : ‹NodePtr›);   {Pointer to node to insert}
begin 
   NewNode^.‹Link› := Head;
   Head := NewNode;
end ;

 

 

Related Templates

  • List Insertion (Sorted)
  • Insertion/Deletion in a Sorted Array

List Insertion (Sorted)

Explanation

Insert a new node in an sorted linked list, preserving the sort.

Pseudocode

 

 

 

 

 

 

 

Analogy

Illustration

Debugging and Testing

    1. There are four different cases: an empty list, at the beginning of the list, the end of the list, and in the middle. The first two and last two can be combined, resulting in two cases to handle.

Pascal Code

procedure Insert(var  Head : ‹NodePtr›; NewNode : ‹NodePtr›);
var 
   Before, After : ‹NodePtr›;
begin 



















end ; {Insert}

Related Templates

  • List Traversal
  • List Insertion (at Head)
  • List Deletion

 

 

List Search (Sorted)

Explanation

Search an sorted list for a specific key. If found, set item to point to the found element and return true. If not found, set Item to point to the element after where the item would have appeared (or nil if the end of the list), and return false.

Pseudocode

while (not end of list) and (not found) do
   p := next node
found := (not end of list) and (key = data)
Analogy
Illustration

Debugging and Testing

Pascal Code

procedure Search (Head: ‹NodePtr›; 
               Key: ‹KeyType›;
            var Item : ‹NodePtr›;
            var Found : Boolean);
   var  
      p: ‹NodePtr›;
begin  
   p := Head;
   while  (p <> nil  ) & (p^.‹Key› < Key) do  
      p := p^.‹Link›;

   
   Item := p;
   Found := (p <> nil  ) & (p^.‹Key› = Key);
end  ;

 

 

Related Templates

  • List Traversal
  • Binary Search

List Traversal

Explanation

Traverse a linked list, performing some operation on each element.

Pseudocode

p := head of list
while not done
process current node
p := next node
Analogy
Illustration

Debugging and Testing

  • If a second termination condition is used, a conditional and must be used to prevent dereferencing a nil pointer.

Pascal Code

procedure Traverse(Head : ‹NodePtrType›);
   var 
      p : ‹NodePtrType›;
begin 
   p := Head;
   ‹pre-processing›
   while  (p <> nil ) ‹& (second termination condition)› do  begin 
      ‹process node›;
      p := p^.‹Linkfieldname›;
      end ;

   ‹post-processing›;
end ;

 

Example for finding minimum:

•&#9;pre-processing = Min := Head;

•&#9;second termination condition is empty

•&#9;process node = if p^.‹Data› < Min^.‹Data› then Min := p;

Example for searching:

    •&#9;pre-processing is empty

    •&#9;second termination condition = p^.Data < Key

    •&#9;post-processing = success := (p <> nil) & (p^.Data = Key);

    FoundItem := p;

Related Templates

  • List Insertion (Sorted)

Procedure

Explanation

Break a larger program into smaller pieces, each of which has a clearly identified purpose contributing to the solution of the overall problem.

Pseudocode

procedure <name>(<parameters>);
   constant declarations
   type declarations
   procedures and function declarations
   variable declarations
   body

Analogy

The owner of a company cannot do all the work. She hires people to solve certain problems — manage production, collect bills, advertise, etc. — and delegates responsibility to them to accomplish their task. They may, in turn, hire additional people and do additional delegation to do their work.

Illustration

Debugging and Testing

  • Make sure that parameters passed in contain legitimate values.
  • It is often possible (and desirable!) to test a procedure with a simple program (called a driver). This can make it easier to test many different cases directly.

Pascal Example

program  Doit;
   const  
      ‹lo› = 1;
      ‹hi› = 100;
   type  
      tArray = array  [‹lo›..‹hi›] of  integer;

   {Initialize part of an array — from a to b — to 0.}
   procedure  InitArray (a, b: integer; var  A: tArray);
      var  
         i: integer;
   begin  
   for  i := a to  b do  
      A[i] := 0;
   end  ;
   var  
      myArray: tArray;
begin  
InitArray(3, 10, myArray);
end  .

Related Templates

  • Program
  • Function

Program

Explanation

Every program has a standard structure.

Pseudocode

declarations
   constants
   types
   variables
   functions and procedures
body

Analogy

This is the "outline" of the program.

Illustration

Not applicable.

Debugging and Testing

  • The last end in the program is followed by a period; other uses of end will be followed by a semi-colon or nothing at all.
  • Standard implementations of Pascal will require const, type and var keywords to appear in the order given and only appear once. Modern implementations allow them to appear multiple times in any order so long as identifiers are declared before use.

Pascal Code

program   ‹name›;
const   
   ‹constants›;
type  
   ‹user-defined types›;
var   
   ‹variable declarations›;

‹procedure and function declarations›;

begin   
   ‹statements›;
end   .

Related Templates

  • none
  • procedure
  • function
  • All others

Reading from a File

Explanation

Read data already entered into the computer and stored in a file.

Pseudocode

Get the filename and open the file
Read the data
Close the File
Analogy
Illustration

Debugging and Testing

  • Handling errors in opening the file is hardest — what happens if the user specifies an invalid file or it doesn’t exist or is already open by another program? Pascal doesn’t support handling these kinds of errors well.
  • Note that OpenFile is not standard Pascal (there is no real standard for opening files).

Pascal Code

uses  cs130Lib;
const 
   Sentinel = 999;

var  
   InFile : Text;

Write('Enter filename: ');
ReadLn(FileName);
OpenFile(InFile, FileName, OpenRead);

ReadLn(InFile, data);
While data <> Sentinel do  begin 
   ‹process data›;
   ReadLn(InFile, data);
   end ;

close(InFile);

Related Templates

  • Sentinal-Controlled Loop
  • other looping templates
  • EOF-Controlled Loop
  • Writing to a File

Repeat-Until Loop

Explanation

Repeat statements until some condition is true.

Pseudocode

‘C’:
do {
   <something to do>;
} while (<cond>);
Turing:
loop
   <something to do>
   exit when <cond>
end loop

Analogy

 

 

Illustration

Debugging and Testing

  • This loop always executes at least once. This sort of behaviour is not usually needed and should always be tested.
  • Off-by-one errors are common (see the While Loop template).

Pascal Code

{Writes out "0 1 2 3 4"}
i := 0;
repeat
   Write(i);
   i := i + 1;
until i = 5;


repeat
   ‹body›;
until  ‹condition›;

Related Templates

  • While Loop
  • For Loop

Sentinel-Controlled Loop

Explanation

Read data until sentinel (an end-marker) is found.

Pseudocode

read a data item
while the sentinel has not been read
   process the current item
   read the next item

Analogy

A kindergarten class is going on a field trip. The bus driver is told that when the teacher boards the bus, it is time to close the door and go.

Illustration

Debugging and Testing

  • If the sentinel is a valid data value, the program will fail if that data item is added to the middle of the file. It is far better to choose a sentinel value which cannot be a valid data item.
  • If the sentinel is a valid data value, it must be processed in the loop. If it is not a valid value, the loop must be structured so that the sentinel is not processed.
  • The priming read (just before the while statement) is often forgotten.

Pascal Code

{sentinel is a data value in the file}
const  
   sentinel = 'zzzzzzz';

var  
   item : string;

readln(item);
while   item <> sentinel do  
   begin  
   ‹process item›
   readln(item);
   end  ;

 

 

Related Templates

  • While Loop
  • Repeat-Until Loop
  • Read a List
  • Counter-Controlled Loop
  • EOF-Controlled Loop

Validating Input

Explanation

Loop until the user enters one of a predetermined set of characters.

Pseudocode

Ask user for input
Read answer
while not valid
   error message
   read again
repeat
   Ask user for input
   read answer
until valid

Analogy

An attorney asks a question of a witness and demands a ‘yes’ or ‘no’ answer, repeatedly asking the question until ‘yes’ or ‘no’ is given.

Illustration

Debugging and Testing

  • Make sure all variables are initialized before testing them.
  • All possible correct answers should be represented in the set.

Pascal Code

Write('Did you kill John?  Yes or no [YN]? ');
ReadLn(answer);
while   not   answer in   ['y', 'n', 'Y', 'N'] do   begin  
   Write('Please answer with "y" or "n".');
   ReadLn(answer);
   end  ;

repeat 
   Write('Did you kill John? Yes or no [YN]?');
   ReadLn(answer);
until  answer in  ['y', 'n', 'Y', 'N'];

Related Templates

  • Sentinel-controlled Loop
  • Repeat-Until Loop
  • Yes

While Loop

Explanation

Repeat the body of the loop while an expression is true.

Pseudocode

‘C’:
int   i;
i = 1;
while (i < 10 ) {
   <something to do>
   i = i + 1;
}
Turing:
var      i:int;
i := 1
loop
   exit when i = 10
   <something to do>
   i := i + 1
end loop
Analogy
Illustration

Debugging and Testing

  • Failure to initialize the condition variable can cause erratic behaviour.
  • Failure to update the condition variable inside the loop results in an infinte loop.
  • "Off-by-one" errors are commonly caused by substituting ‘<‘ for ‘<=‘ or vise versa. Similarly for ‘>‘ and ‘>=‘.
  • Create tests causing the loop to execute 0 times, 1 time, many times. If there is a maximum, test it too. Pay special attention to the loop’s results from the last iteration.

Pascal Code

var  i: integer;
i := 1;
while    i < 10 do begin   
   ‹something to do›
   i := i + 1;
   end  ;


‹initialization›
while    ‹condition› do begin   
   ‹body›;
   ‹update condition variable›;
   end  ;

 

 

Related Templates

  • Sentinel-controlled Loop
  • EOF-controlled Loop
  • Counter-controlled Loop
  • For Loop
  • Repeat-Until Loop

Writing to a File

Explanation

Save the output of a program by writing it to a file.

Pseudocode

Obtain the filename and open the file
Write the data
Close the file
Analogy
Illustration

Debugging and Testing

  • The file may already exist, in which case it will probably be overwritten.
  • The user may specify an invalid folder (directory) in which to put the new file.
  • Failing to close the file may result in lost data
  • Note that OpenFile is not standard Pascal (there is no real standard for opening files)..

Pascal Code

uses  cs130Lib;
var  
   OutFile : Text;

Write('Enter filename: ');
ReadLn(FileName);
OpenFile(OutFile, FileName, OpenWrite);

while  ‹more data› do  begin 
   ‹generate data›;
   WriteLn(OutFile, data);
   end ;

close(OutFile);

Related Templates

  • Looping templates
  • Reading from a File

Yes

Explanation

Ask the user a question. Return true if the user responds with ‘y’ or ‘Y’.

Pseudocode

Ask question
Loop until valid answer
   Read Answer
Return Answer = ‘y’

Usage

if  Yes('Do you want to see the menu? ') then 
   ShowMenu;

while  Yes('Is there more data?') do  
   ‹process data›;

Illustration Debugging and Testing

Pascal Code

function  Yes(prompt:string):boolean;
var 
   Answer : char;
begin  
Write(prompt);
WriteLn(' [YN]: ');
ReadLn(Answer);
while   not  (Answer in   ['y', 'Y', 'n', 'N']) do   begin  
   Write('Please answer with "Y" or "N".  ');
   ReadLn(Answer);
   end ;
Yes := Answer in   ['y', 'Y'];
end ;  {Yes}

Related Templates

  • Validating Input