For our sample ALGOL W program we'll implement a simple priority queue.
A priority queue can be used to store items tagged with a priority value and then retrieve them in order of priority. Several operations need to be implemented
- Check if the queue is empty
- Insert an item
- Peek at what the highest priority item is
- Remove the highest priority item from the queue and return it
See Rosetta Code for full details.
We will use a binary heap to implement the queue: this allows O(log n) inserts and removals, and O(1) for peeking at the highest priority item, as the queue is kept in priority order after each operation.
Rather than doing this from scratch I'm going to base the solution on Robert Sedgewick and Kevin Wayne's Java implementation.
First let's define the data structures and interfaces available for users of the priority queue.
Each item can be modeled as a record with an integer priority; the data associated with it is a string here but could be anything else
record Item(integer Priority; string Task);
The public interface can then be described using the following procedure prototypes:
logical procedure PQ_Is_Empty; procedure PQ_Insert(reference(Item) value New_Item); reference(Item) procedure PQ_First; reference(Item) procedure PQ_Delete_First;
To test our program, we need to insert some items in random order and then see if they dequeue in priority order:
% Insert some tasks in random order % PQ_Insert(Item(3, "Clean drains")); PQ_Insert(Item(4, "Feed cat")); PQ_Insert(Item(5, "Make tea")); PQ_Insert(Item(1, "Solve RC tasks")); PQ_Insert(Item(2, "Tax return")); % Remove top priority item from queue and print % while not PQ_Is_Empty() do begin reference(Item) First; First := PQ_Delete_First; write(Priority(First), Task(First)); end
Data structure and constraints
To store the queue, the binary heap implementation needs an array of items and an indication of its current size, which we can define as:
reference(Item) array PQ(1::PQ_Capacity); integer PQ_Size;
PQ_Capacity is the maximum size of the queue, which we'll define as a constant; it does not seem possible to resize an array in ALGOL W. We'll make the array and size global variables for simplicity: a better, if more verbose solution, would be to pass the data structure to each interface function, eg
reference(Item) procedure PQ_Delete_First(reference(Item) array PQ(1::PQ_Capacity), integer PQ_Size;
It would also have been nice to encapsulate both
PQ_Size into a record, but ALGOL W records do not allow arrays as members. One way we could combine this into one variable is to make the array have bounds 0::PQ_Capacity and store the current size at location 0.
Public function implementation
It's then fairly simple to define the public functions:
% Initialise a queue % procedure PQ_Init(); begin PQ_Size := 0; end; % Return true if the queue is empty % logical procedure PQ_Is_Empty(); begin PQ_Size = 0 end; % Add a new item to the queue % procedure PQ_Insert(reference(Item) value New_Item); begin % Add to end of array and swim down to maintain % % priority order % PQ_Size := PQ_Size + 1; PQ(PQ_Size) := New_Item; PQ_Swim(PQ_Size); end; % Return the first item in the queue by priority % reference(Item) procedure PQ_First; begin PQ(1) end; % Return the first item and delete from queue % reference(Item) procedure PQ_Delete_First; begin reference(Item) First; PQ_Exchange(1, PQ_Size); First := PQ(PQ_Size); PQ_Size := PQ_Size - 1; PQ_Sink(1); % Just to be safe, null out reference at end % PQ(PQ_Size+1) := null; First end;
These call a number of private functions - note that privacy is not enforced in ALGOL W however. First, to keep the heap organised, we need
procedure PQ_Swim(integer value K); begin while K > 1 and PQ_Greater(K div 2, K) do begin PQ_Exchange(K, K div 2); K := K div 2; end; end; procedure PQ_Sink(integer value k); begin logical Done; Done := false; while 2*K <= PQ_Size and not Done do begin integer J; J := 2 * K; if J < PQ_Size and PQ_Greater(J, J+1) then J := J + 1; if PQ_Greater(K, J) then begin PQ_Exchange(K, J); K := J; end else begin Done := true; end; end end;
These need to call primitive functions to exchange and compare:
logical procedure PQ_Greater(integer value I; integer value J); begin Priority(PQ(I)) > Priority(PQ(J)) end; procedure PQ_Exchange(integer value I; integer value J); begin reference(Item) Temp; Temp := PQ(I); PQ(I) := PQ(J); PQ(J) := Temp; end;
A diversion - procedures without parameters
While writing this I got confused about the prototype for procedures without parameters; instead of
reference(Item) procedure PQ_First; ... result := PQ_First;
I was writing
reference(Item) procedure PQ_First(); ... result := PQ_First();
and got what looked like garbage as the Item reference returned.
Trying to reproduce this with a simple example yielded the same problem:
# $run *algolw = begin : integer procedure three; : begin : 3 : end; : : write(three); : end. : $endfile Options (UN022) :- main, debug (MAIN) 0.016 seconds to compile, size 448 bytes Execution begins ... 3 0.001 seconds in execution # $run *algolw = begin : integer procedure three(); : begin : 3 : end; : : write(three()); : end. : $endfile Options (UN022) :- main, debug (MAIN) 0.016 seconds to compile, size 504 bytes Execution begins ... 8632304 0.001 seconds in execution
Is the second example legal ALGOL W? I don't think it is, based on the Stanford specification you need something in the parameter list - but there was no error from the compiler.
Running the program
Once that was fixed, compiling and running the program was simple.
# $run *algolw scards=pqueue.alw par=deck Options (UN022) :- main, debug Object program: "-AWLOAD" (MAIN) 0.041 seconds to compile, size 4280 bytes # $run -awload 1 Solve RC tasks 2 Tax return 3 Clean drains 4 Feed cat 5 Make tea 0.001 seconds in execution
Final thoughts on ALGOL W
ALGOL W definitely feels more polished and easy to use compared with ALGOL 60: the lack of stropping is a relief. It's not the most powerful language - the restrictions on references stop it being much use for system programming - but I can see it would make a good choice as a teaching language. Apart from the issue I had above, the MTS compiler is much easier to use than the IBM ALGOL 60 one - I liked that it warns you if you use
goto or pass by name.
Why didn't ALGOL W become more popular? I think there were several factors
- Only initially available on S/360 machines
- Not as good performance as FORTRAN
- Did not become the official replacement for ALGOL 60
- Wirth did not work further on ALGOL W, moving on to Pascal, which does feel similar.
Next up, I will attempt to look at ALGOL 68 - if I can get it restored from the D4 tapes and running on D6.0.
Full source code for this program is on github.