Sorting Example

This example demonstrates more of occam's language features, including multiple nested sequential processes executed in parallel, an array of channels, and interactive input and output with the user. The program creates a 20-node systolic array to perform a bubble sort. After asking the user for a string, the characters are passed to the array, sorted automatically, and returned to the user for inspection.

The program starts with references to the library used for string output and the declaration of top-level variables. Note that the top-level constructor PAR is used, which designates that the subsequent processes are executed in parallel.

    #USE "course.lib"
    #INCLUDE ""
    -- sort.occ
    -- Matthew Woitaszek
    PROC (CHAN OF BYTE keyboard, screen, error)                      
      [21]CHAN OF BYTE sortchar:

Next, the sorting systolic array is defined. The PAR constructor uses a replicator to create MAXLENGTH parallel segments. In the case of this program, 20 instances of this process are created. Each process waits for its first character, named x. When another character has been received, the lesser value is passed to the next process in the systolic array. When the termiation value 255 is received, the process terminates. The effect is that the sorted string emerges from the last parallel process.

        -- Sorting Systolic Array
          BYTE x, y:
            sortchar[J] ? x
            WHILE x <> 255
                sortchar[J] ? y
                -- Send the smaller characters down the pipeline
                  x < y
                      sortchar[J+1] ! x
                      x := y
                    sortchar[J+1] ! y
            -- After the WHILE loop has terminated, flush the pipeline.
              J < (MAXLENGTH - 1)
                sortchar[J+1] ! 255

The next segment of the program is executed sequentially. After declaring several local variables, the software prompts the user for a string. The user may enter up to MAXLENGTH characters, or stop at any time by pressing Enter. Characters are accumulated in the byte character array "word".

        -- Interactive Process
        BYTE ch:                        -- Input character
        [MAXLENGTH + 1]BYTE word:       -- Entire string
        INT count:                      -- Character count
        BOOL flag:                      -- Done flag
          -- Input section. Read a string of up to MAXLENGTH characters from the 
          -- keyboard channel.
          out.string( "Enter a string:*c*n", 0, screen )
          ch := ' '
          count := 0
          flag := TRUE
          WHILE flag
              keyboard ? ch
              -- If the user hit Enter, finish. Otherwise, save the character.
                ch = '*n'
                  flag := FALSE
                ch <> '*n'
                    screen ! ch
                    screen ! FLUSH
                    word[count] := ch
                    count := count + 1
              -- If the string is the maximum length, finish now.
                count = MAXLENGTH
                  flag := FALSE

After the user input has been retrieved, the string is displayed to the user. Another display loop prints the string in reverse. Finally, the string is fed to the systolic array one character at a time, followed by 255, the program's sequence termination flag. The sorted characters are retrieved from the other end of the systolic array and displayed, and the program terminates.

          -- Print the string back to the display
          out.string( "*c*nYou entered the string:  ", 0, screen )
          SEQ I = 0 FOR count
            screen ! word[I]
          out.string( "*c*nPrinted in reverse:      ", 0, screen )
          SEQ I = 0 FOR count
            screen ! word[ (count - I) - 1]
          out.string( "*c*nSorted numerically:      ", 0, screen )
          -- Send the characters to the sorting systolic array
          SEQ I = 0 FOR count
            sortchar[0] ! word[I]
          sortchar[0] ! 255
          -- Retrieve the characters from the sorting array
          SEQ I = 0 FOR count
              sortchar[MAXLENGTH] ? ch
              screen ! ch
              screen ! FLUSH
          out.string( "*c*nDone!*c*n*c*n", 0, screen )

For an example run, the name "Matthew Woitaszek" has been sorted by the system:

    [matthew@cluster examples]$ kroc _mysort.occ -lcourse -d
    kroc: Selecting post-mortem debugging
    Warning-oc-_mysort.occ(8)- Parameter error is not used
    [matthew@cluster examples]$ ./_mysort
    Enter a string:
    Matthew Woitaszek
    You entered the string:  Matthew Woitaszek
    Printed in reverse:      kezsatioW wehttaM
    Sorted numerically:       MWaaeehikostttwz

Overall, occam is a powerful language directly supporting concurrent and parallel programming. While some of its language structures seem particularly low-level and esoteric, it provides the features of a high level language while maintaining close ties to microcontroller hardware.

Return to Index