In Memory of
Niklaus Wirth

Ryan R. Kelly

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

   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

The five lists are to be preceded by suitable titles.
{$mode ISO}
program PollReports(Output, Poll);

      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}

      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
      Score    = array [Category] of Integer;

      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
            result := AdultWomen
         if (R.s = Male) then
            result := YoungMen
            result := YoungWomen;
      ResponseCategory := result
   end   { ResponseCategory };

   procedure InitOrder();
   { Initialize ranking order }

         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 }

         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;
      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 { 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}

            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
            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. :) }

          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)
            Swap(Left, Last);
            Sort(Left, Last, C);
            Sort(Left+1, Right, C);
      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 }

         I: Integer;
         H: Hit;

   begin { ReportPopularity }
      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 { 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. }

            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
               Flag := False;
            I := I + 1
      end { WriteAlpha };

   begin { WriteResponseName }
      WriteAlpha(R.FirstName);  Write(' ');  WriteAlpha(R.Name);
   end { WriteResponseName };

   procedure ReportCategory(C: Category);
   { Report all respondants with first hit choice in the top choices
     in their category }

         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');
         Writeln(' ---');
      end { Report Heading };

      function IsTopMention(H: Hit): Boolean;
      { Determine if hit H is a top choice in the current ranking order }

            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 }
      while not Eof(Poll) do begin
         Read(Poll, R);
         Rc := ResponseCategory(R);
         if (Rc = C) and IsTopMention(R.Choice[1]) then
   end { ReportCategory };

begin { PollReports }
end { PollReports } .