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 "consts.inc"
    
    --
    -- sort.occ
    -- Matthew Woitaszek
    --
    PROC hello.world (CHAN OF BYTE keyboard, screen, error)                      
    
      [21]CHAN OF BYTE sortchar:
      VAL INT MAXLENGTH IS 20:
      
      PAR
    

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
        --
        PAR J = 0 FOR MAXLENGTH
          BYTE x, y:
          SEQ
            sortchar[J] ? x
            WHILE x <> 255
              SEQ
                sortchar[J] ? y
    
                -- Send the smaller characters down the pipeline
                IF
                  x < y
                    SEQ
                      sortchar[J+1] ! x
                      x := y
                  TRUE
                    sortchar[J+1] ! y
    
            -- After the WHILE loop has terminated, flush the pipeline.
            IF
              J < (MAXLENGTH - 1)
                sortchar[J+1] ! 255
              TRUE
                SKIP
    

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
    
        SEQ
    
          -- 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
            SEQ
              keyboard ? ch
    
              -- If the user hit Enter, finish. Otherwise, save the character.
              IF
                ch = '*n'
                  flag := FALSE
                ch <> '*n'
                  SEQ
                    screen ! ch
                    screen ! FLUSH
                    word[count] := ch
                    count := count + 1
    
              -- If the string is the maximum length, finish now.
              IF
                count = MAXLENGTH
                  flag := FALSE
                TRUE
                  SKIP
    

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
            SEQ
              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
    Done!                                                                        
    

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.

References
Return to Index