ALGOL W - Priority queue

For our sample ALGOL W program we’ll implement a simple priority queue.

The problem

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

See Rosetta Code for full details.

Implementation

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.

Interface

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;

Test driver

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 and 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;

Private functions

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 PQ_Swim and PQ_Sink:

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

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.

Further information

Full source code for this program is on github.

Comments

comments powered by Disqus