A few years ago, I bought a used copy of the programming text book, Algorithms + Data Structures = Programs by Niklaus Wirth, published in 1976. I read through it quickly, and then I decided to implement the examples and work through the exercises.
The programming language presented in the text is Pascal, and because I had not written anything in Pascal since the 1990s, I chose to take a step back and picked up the Pascal User Manual and Report, 4th Edition. Over the last few months of 2023, I casually studied the example programs in the manual and ran them using the Free Pascal compiler.
As the new year began, I turned my attention back to Algorithms + Data Structures = Programs. Although one could use any programming language to grasp the ideas in the book, I've been enjoying working through the exercises in Pascal in an attempt to dwell in the style of that era.
Wirth seems to have viewed a computer program as the expression of a purely abstract idea which should not be bound to the physical device that may be executing it. He designed Pascal to hide the details of the computer's low level architecture as much as possible. In his exposition of fundamental data types and algorithms, you'll find no mention of bytes or twos complement integer encodings, though some of the examples and exercises leave no doubt that he is fully aware of the importance of word sizes, floating point representations, and address alignment. Even as he prompts the reader to consider how one might implement an array or a record at the machine level, he gives the stronger impression that programs can and should be written at a higher level, independent of the machine details.
The design of the Pascal language also reveals Wirth's affinity for simplicity and efficiency. Although I find Pascal's syntax to be verbose and error-prone, I do appreciate that it is consistent and regular. It is a language purposely formulated to be easy to parse and compile.
Niklaus Wirth died on New Year's Day 2024, at the age of 89. Today would have been his 90th birthday. In his memory, here is my solution to the final exercise in the first chapter of the 1976 edition of his book.
This is not the most exciting exercise in the chapter. The prompts to implement versions of Pascal's file I/O routines using arrays were more fun, and the exercise on formatting floating point numbers was difficult. Some of the exercises involving character input, in particular the implementation of a prototype ed style text editor, expose the frustrating mismatch between a Linux console's line discipline and the text file model Pascal implements.
Exercise 14, however, is the most precisely specified programming task in the first chapter, and it also stands out for requiring its output to be sorted. Algorithms for sorting are the subject of the second chapter.
{ Algorithms + Data Structures = Programs
Niklaus Wirth
ISBN 0-13-022418-9
Chapter 1. Page 54.
Exercise 1.14.
Implemented by Ryan Kelly on February 4, 2024.
A company organizes a poll to determine the success of its products. Its
products are records and tapes of hits, and the most popular hits are to be
broadcast in a hit parade. The polled population is to be devided into four
categories according to sex and age (say, less or equal to 20, and older than
20). Every person is asked to name five hits. Hits are identified by the
numbers 1 to N (say, N = 30). The results of the poll are represented by a
file.
type hit = 1..N;
sex = (male,female);
response =
record name, firstname: alfa;
s: sex;
age: integer;
choice: array [1..5] of hit
end ;
var poll: file of response
Hence, each file element represents a respondent and lists his name, first
name, sex, age, and his five preferred hits according to priority. This file
is the input to a program which is supposed to compute the following results:
1. A list of hits in the order of their popularity. Each entry consists of the
hit number and the number of times it was mentioned in the poll. Hits that
were never mentioned are omitted from the list.
2. Four seperate lists with the names and first names of all respondents who
had mentioned in first place one of the three hits most popular in their
category.
The five lists are to be preceded by suitable titles.
}
{$mode ISO}
program PollReports(Output, Poll);
const
N = 30; {Number of hits tracked by the poll}
MaxChoice = 5; {Number of hit choices per respondant}
MaxAlpha = 10; {Length of name strings, defined earlier in the text }
AdultAge = 21; {Least adult age, for categorization of respondants}
OrderLimit = 3; {Ranking limit for inclusion in Category reports}
type
Hit = 1..N;
Sex = (Male, Female);
Category = (AllListeners, AdultMen, AdultWomen, YoungMen, YoungWomen);
Alpha = array [1..MaxAlpha] of Char; { defined earlier in chapter 1 }
Response = record
Name : Alpha;
FirstName: Alpha;
S : Sex;
Age : Integer;
Choice : Array [1..MaxChoice] of Hit
end;
Score = array [Category] of Integer;
var
Poll: file of Response;
Scores: array [Hit] of Score;
Order: array [1..N] of Hit;
function ResponseCategory(var R: Response): Category;
{ Determine category of respondant by age and sex. }
var result: Category;
begin { ResponseCategory }
if (R.Age >= AdultAge ) then
if (R.S = Male) then
result := AdultMen
else
result := AdultWomen
else
if (R.s = Male) then
result := YoungMen
else
result := YoungWomen;
ResponseCategory := result
end { ResponseCategory };
procedure InitOrder();
{ Initialize ranking order }
var
I: Integer;
begin { InitOrder }
for I := 1 to N do
Order[I] := I
end { InitOrder };
procedure ScoreHits();
{ Count mentions of each hit for all categories }
var
R: Response;
H: Hit;
I: Integer;
C: Category;
begin { ScoreHits }
for I := 1 to N do
for C := AllListeners to YoungWomen do
Scores[I][C] := 0;
Reset(Poll);
while not Eof(Poll) do begin
Read(Poll, R);
for I := 1 to MaxChoice do begin
H := R.Choice[I];
Scores[H][AllListeners] := Scores[H][AllListeners] + 1;
C := ResponseCategory(R);
Scores[H][C] := Scores[H][C] + 1;
end
end
end { ScoreHits };
procedure SortOrder(C: Category);
{ Sort the ranking by descending number of mentions in category }
function Compare(I, J: Hit; C: Category): Integer;
{ Compare score for category C of hit I and J. Used by Sort below}
var
Result: Integer;
S1, S2: Integer;
begin { Compare }
S1 := Scores[I][C]; S2 := Scores[J][C];
if S1 < S2 then
Result := -1
else if S1 = S2 then
Result := 0
else
Result := 1;
Compare := Result
end { Compare };
procedure Swap(I, J: Integer);
{ Swap hit in ranking order array. Used by Sort below}
var T: Hit;
begin { Swap }
T := Order[I];
Order[I] := Order[J];
Order[J] := T
end { Swap };
procedure Sort(Left, Right: Integer; C: Category);
{ Recursive QuickSort - based on examples from
The C Programming Language - Second Edition
Brian W. Kernighan and Dennis M. Ritchie
ISBN 0-13-110362-8
... because I haven't gotten to chapter two of Wirth's
text. :) }
var
I, Last : Integer;
begin { Sort }
if Left < Right then begin
Swap(Left, (Left + Right) div 2);
Last := Left;
for I := Left+1 to Right do
if 0 < Compare(Order[I], Order[Left], C) then begin
Last := Last + 1;
Swap(Last, I)
end;
Swap(Left, Last);
Sort(Left, Last, C);
Sort(Left+1, Right, C);
end
end { Sort };
begin { SortOrder }
Sort(1, N, C)
end { SortOrder };
procedure ReportPopularity();
{ Write report of hits sorted by all mentions, excluding hits
with no mentions }
var
I: Integer;
H: Hit;
begin { ReportPopularity }
SortOrder(AllListeners);
Writeln('--- Hit Popularity ---');
Writeln('Hit':11, 'Mentions':11);
for I := 1 to N do begin
H := Order[I];
if 0 < Scores[H][AllListeners] then
Writeln(H:11, Scores[H][AllListeners]:11);
end
end { ReportPopularity };
procedure WriteResponseName(var R: Response);
{ Write respondant R's name with new line. Used by ReportCategory below}
procedure WriteAlpha(var A: Alpha);
{ Write an Alpha's contents, ending at the first non-alphabetical
charater. }
var
I: Integer;
Flag : Boolean;
AlphaChars : set of Char;
begin { WriteAlpha }
I := 1; Flag := True;
AlphaChars := ['A'..'Z'] + ['a'..'z'];
while (I <= MaxAlpha) and Flag do begin
if A[I] in AlphaChars then
Write(A[I])
else
Flag := False;
I := I + 1
end
end { WriteAlpha };
begin { WriteResponseName }
WriteAlpha(R.FirstName); Write(' '); WriteAlpha(R.Name);
Writeln()
end { WriteResponseName };
procedure ReportCategory(C: Category);
{ Report all respondants with first hit choice in the top choices
in their category }
var
R: Response;
Rc: Category;
procedure ReportHeading();
{ Write the report heading base on category C}
begin { Report Heading }
Write('--- ');
case C of
AllListeners: Write('All Listeners');
AdultMen : Write('Adult Men');
AdultWomen : Write('Adult Women');
YoungMen : Write('Young Men');
YoungWomen : Write('Young Women');
end;
Writeln(' ---');
end { Report Heading };
function IsTopMention(H: Hit): Boolean;
{ Determine if hit H is a top choice in the current ranking order }
var
I: Integer;
Flag: Boolean;
begin { IsTopMention }
Flag := False;
for I := 1 to OrderLimit do
if Order[I] = H then
Flag := True;
IsTopMention := Flag
end { IsTopMention };
begin { ReportCategory }
SortOrder(C);
Reset(Poll);
ReportHeading();
while not Eof(Poll) do begin
Read(Poll, R);
Rc := ResponseCategory(R);
if (Rc = C) and IsTopMention(R.Choice[1]) then
WriteResponseName(R)
end
end { ReportCategory };
begin { PollReports }
InitOrder();
ScoreHits();
ReportPopularity();
ReportCategory(AdultMen);
ReportCategory(AdultWomen);
ReportCategory(YoungMen);
ReportCategory(YoungWomen);
end { PollReports } .