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 size

Question 69 (2010):

Submission reference: IN2030

Hiya, I have been going through the 2010 paper and have come stuck on question 3(a) where I have to write a function to count the TRUE elements in an array of bools, but the size of the bool array is not mentioned. How would I go about this?

Also, I noticed that in the answers page you have said that mobiles are not examinable, but there was a question on barriers. Are mobiles examinable this year??

Thanks :D

Answer 69:

The prefix SIZE operator returns the size of an array (of channels or any data-type). See slide 113 from the choice set of slides, 93 from replicators, 71 from shared-etc and Question 52 (2003) and Question 58 (2000) from the anonymous Q&As (which I found by searching for "SIZE" under the keyword-index page for "arrays" – I've now added a page for the keyword "size"). There's also an example in the very last code box of the occam reference/checklist (which is linked from the Practical Resources box on the Co538 Moodle page).

Note that this last example (from the reference/checklist) has very similar form to the answer required for the exam question part you raised. The answer to that part is trivial:

  INT FUNCTION count.true (VAL []BOOL array) 
    INT count: 
    VALOF 
      SEQ                  -- function body
        count := 0 
        SEQ i = 0 FOR SIZE array 
          IF 
            array[i] 
              count := count + 1 
            TRUE 
              SKIP
      RESULT count
  :

(where you only had to write the 8 lines starting from the line commented "function body").

I can't find anything in the answers page for this year that says there was a question on barriers? Please mail me (phw@kent.ac.uk) where you have seen this.

The concept of barrier synchronisation has been explained in previous exam questions (see Question 62 (2008)), with follow-on parts asking for bits of implementation and/or use. Such questions – introducing new concepts – are always possible. However, the formal occam-pi language mechanism for BARRIERs, along with that for MOBILEs, is presented in the slides titled mobiles. The material in the mobiles slides is for advanced study and is not examinable in Co538. The material in all the other slide sets (including shared-etc) is examinable.

Keywords: arrays , size

Question 52 (2003):

How do we know/check if an array is empty ?

Answer 52:

The `SIZE' operator in occam will return the number of elements in an array. If zero, then you know the array is `empty' (or more correctly, zero-sized).

Unlike Java, there is no concept of null-ness in occam, and you can't declare sizeless arrays. Parameters are slightly different, you can have:

    PROC n.elements (VAL []INT array, INT count)
      count := SIZE array
    :

But not:

    PROC blah ()
      []INT array:
      SEQ
        ...  stuff
    :

occam will not let you declare a zero-sized array either, for example:

    PROC blog ()
      [0]INT array:
      SEQ
        ...  stuff
    :

Keywords: arrays , size

Referrers: Question 69 (2010)

Question 58 (2000):

Please could you type up the example on abbreviations you showed us in the lecture? They were on hand-drawn slides and about adding up elements of a 2-D array. Thanks.

Answer 58:

OK. Here's some code for adding up the elements of a 1-D array:

  SEQ
    sum := 0
    SEQ i = 0 FOR SIZE a
      sum := sum + a[i]

where a is an array of REAL64s (say) and sum is a single REAL64 variable.

Now, suppose a is a 2-D array of REAL64s and we need to add up each of its rows into corresponding elements of sum (which is now a 1-D array of REAL64s). The naive code, based on the above, would be:

  SEQ row = 0 FOR SIZE a
    SEQ
      sum[row] := 0
      SEQ col = 0 FOR SIZE a[row]
        sum[row] := sum[row] + a[row][col]

This code is correct but somewhat inefficient. Firstly, occam 2-D arrays live in a contiguous block of memory with all its rows having the same lengths (which is not the case for Java 2-D arrays). Therefore, it's slightly wasteful to look up the size of each row each time the inner loop starts. Instead, look this up once before doing anything else, give it a VAL name and use that name:

  VAL INT n.cols IS SIZE a[0]:
  SEQ row = 0 FOR SIZE a
    SEQ
      sum[row] := 0
      SEQ col = 0 FOR n.cols
        sum[row] := sum[row] + a[row][col]  -- innermost loop code

But the real inefficiency lies in the code of the innermost loop. That code is executed n.rows * n.cols times and involves calculating the addrresses of elements sum[row] and a[row][col]. The latter requires a multiplication and an addition - the former just an addition. Three run-time checks that row and col lie within their respective array index ranges may also be required (although a really clever optimiser may be able to deduce that they will always be within bounds and, therefore, omit these checks).

Compare the above with:

  VAL INT n.cols IS SIZE a[0]:
  SEQ row = 0 FOR SIZE a
    REAL64 sum.row IS sum[row]:             -- this is where we will do the sum
    VAL []REAL64 a.row IS a[row]:           -- this is what we are going to sum
    SEQ
      sum.row := 0
      SEQ col = 0 FOR n.cols
        sum.row := sum.row + a.row[col]     -- innermost loop code

Now, the innermost loop contains just one array reference, requiring only one addition for the address calculation and one range check on col (for which an optimiser does not have to be that clever to optimise away). Two new array references have been introduced in the abbreviations themselves - but these are not part of the innermost loop and only happen once per row. This code will execute much faster than the previous version.

The other benefit from introducing those abbreviations is that the inner code:

    SEQ
      sum.row := 0
      SEQ col = 0 FOR n.cols
        sum.row := sum.row + a.row[col]     -- innermost loop code

is as simple as the 1-D array summing code with which we started:

Keywords: abbreviation , arrays , size

Referrers: Question 69 (2010)