XML CO538 Anonymous Questions and Answers Keyword Index

This page provides a keyword index to questions and answers. Clicking on a keyword will take you to a page containing all questions and answers for that keyword, grouped by year.

To submit a question, use the anonymous questions page. You may find the keyword index and/or top-level index useful for locating past questions and answers.

Keyword reference for sort-pump

Question 63 (2004):

I am a little confused to as what happens in the cell process of sort pump:

    BYTE x, n:
    WHILE TRUE
      SEQ
        in ? x
        out ! end.marker
        WHILE x <> end.marker
	  ...  body of inner loop

Why do you send the end.marker down the out channel?

Answer 63:

This was explained in the lecture covering this topic.

Groups of numbers, separated by end markers, are fed into the sort pump. This means they are fed into the pipeline of cells by which it is implemented. So, groups of numbers, separated by end markers, are fed into the first cell in the pipeline. Each cell looks out for that end marker (which, to save one test in the inner loop, we know is greater than any of the numbers in any group). When it finds that end marker, the inner loop ends and the cell gets ready for the next group (by looping back in the outer loop).

But that first cell must pass on the end marker ... otherwise the next cell (and the next cell (and the next cell ... )) will not get that end marker between the groups -- and they need them!

But I agree that outputting the end marker before processing the group is a little odd! It makes no difference since the next outer loop does the same (and provides the end marker following the first group). However, it does mean that there is a funny start-up effect in that a stream of end markers (as many as there aare cells in the pipeline) are the first things out of the pump. That just indicates a bunch of zero-length groups, which are harmless and ignored by whatever is consuming them. Following this, the pump behaves as expected (i.e. it produces sorted groups of numbers separated by a single end marker).

I changed this code in the Powerpoint Chapter 5 slide 19, so that it outputs the end marker after processing each group. This is more logical and does not give rise to the start-up flow of end markers. Here is that revised structure. Note: I've changed the name 'x' to 'max' and moved its declaration inside the outer loop. I've also moved the declaration of 'n' inside the inner loop (which is not shown below). Variables should not be declared where they are not needed -- 'max' does not need to be known outside the outer loop and 'n' is only needed in the body of that inner loop:

    WHILE TRUE
      BYTE max:
      SEQ
        in ? max
        WHILE max <> end.marker
          ...  body of inner loop
        out ! end.marker

Keywords: sort-pump

Question 60 (2004):

Hi, could you just give an explanation of how the following code works (taken from "sort_pump.occ"):

    PROC sort (CHAN OF BYTE in, out)
      [total - 2]CHAN OF BYTE c:
      PAR
        cell (in, c[0])
        PAR p = 1 FOR total - 3
          cell (c[p - 1], c[p])
        cell (c[total - 3], out)
    :

Thanks.

Answer 60:

This code creates a pipeline of processes (of `total - 1' cells) -- see slides 5-17 and 5-18. The two end cells are catered for specially (since these plug into the external environment -- via `in' and `out'). The cells between these are created using a replicated PAR. If you substitute a constant value for `total' (say 10), then expand and flatten the PAR replicator, it becomes a bit clearer:

    [8]CHAN OF BYTE c:
    PAR
      cell (in, c[0])

      cell (c[0], c[1])        -- PAR p = 1 FOR 7
      cell (c[1], c[2])        --   cell (c[p - 1], c[p])
      cell (c[2], c[3])
      cell (c[3], c[4])
      cell (c[4], c[5])
      cell (c[5], c[6])
      cell (c[6], c[7])

      cell (c[7], out)

Keywords: sort-pump , par , replicator

Question 29 (2004):

Just a quick question regarding sort_pump.occ. In the window process, does the following fill the buffer array with end markers?

  SEQ
    SEQ i = 0 FOR buff.max
      buffer[i] := end.marker
    ptr := 0

If so, what is the point of doing so?

Also, what does ptr mean? Is it some kind of field to keep track of the index of the array? Thanks.

Answer 29:

Yes. The statement "buffer[i] := end.marker" is replicated buff.max times in SEQuence, each with a different value for the control variable i (starting with zero, in this case, and incrementing by one each time).

We have to put something in the buffer since what is there initially gets pumped into the sorter as we type characters. We need something visible for display -- so zeroes (ASCII nulls) would not work. End markers work (they are mapped to visible dots for display) and they are harmless -- just ignore them (as does the lay.out process does if it sees consecutive markers!).

Note that in occam, there is no auto-initialisation of variables to default values (such as zero).

The answer to your last question is yes -- see the code labelled display buffer and update buffer, further down in the window process.

Keywords: replicator , sort-pump