Re: OCCAM, JOYCE, SUPERPASCAL AND JAVA

["P.H.Welch" <P.H.Welch@xxxxxxxxx>]

We (at Kent) shared Adrian/Denis's slight disappointment that Brinch Hansen's
"Efficient Parallel Article" did not come up with a complete solution, but
it's nevertheless a valuable contribution.

It is different from the old occam trick of getting bounded-depth recursion
(parallel or otherwise) by replicating code.  That's very effective ... but
is a compile-time activity and not a run-time one.  It also doesn't lead to
any sharing of parallel workspaces.

The KRoC system would require a modest modification to the compiler because
the parameter passing convention would have to change somewhat - but not a
massive job.

We wondered about relaxing the rule on exact-size workspaces (one free-list
for each PROC/FUNCTION) to one that built free-lists that were always powers
of 2 in size.  The compiler generates an index into a table of these free-
lists for each PROC/FUNCTION so that each is associated into the free-list
of the smallest sized partitions into which its workspace fits.  The penalty
is a waste of (on average) a quarter of your memory.  The gain is that each
free-list is shared between *all* PROCs associated with it - not just one
specific PROC.  That might considerably alleviate the never-gets-reclaimed
problem.

We also wondered about the compiler generating different call sequences
depending on whether the routine being called was recursive or not.
For non-recursive calls, the workspace is pre-allocated in the usual
way.  For recursive ones, it has to be allocated off the associated
free-list (or grabbed off free-memory if that free-list were empty).
That way, non-recursive PROCs would be as fast as ever ... mind you,
the recursive ones would be not much slower :-) ...

Either way, the occam language would need changing to allow recursion,
particularly for mutual recursion.  If we want to stick to the rule that
something must be declared before it is used (rather than just being
declared somewhere in the same block) -- and I would prefer to stick
to that rule -- we would need something like forward-declarations.

Here's a suggestion for dealing with the points in the last two paragraphs.

First of all, make recursive declarations explicit.  The compiler needs
to know (because different calling/return code sequences have to be
generated and different workspace allocations made -- zero in the case
of a recursive call).  The compiler could find out ... but that conflicts
with the declare-before-use rule when we have mutual recursion.  I also
feel more comfortable with making semantic details explicit and getting
the compiler to check them - rather than getting the compiler to deduce
what I had in mind.  So:

  REC PROC P (...)
    ...  body that calls P (possibly in parallel)
  :

and similarly for FUNCTIONs.  Without the REC, the existing semantic rules
apply -- namely that the routine name doesn't come into scope until after
the declaration body.  So, we have semantic compatibility with the current
language :-)

For mutual recusion, rather than introduce a notion of forward declarations,
let's pick up on something from occam3:

  EXPORT
    ...  declarations (e.g. types, PROC/FUNCTION headers, channels etc.)
  FROM
    ...  stuff (that must include the bodies of any of the above headers)
  :

This is a declaration from which only the items in the EXPORT list become
visible.  It's purpose was for occam3 LIBRARYs, where we wish to hide
various supporting items, but it stands on its own and can be used anywhere.

It provides a very convenient *structure* for making any forward declarations
needed for mutual recursion:

  EXPORT
    REC PROC P (...):
    REC PROC Q (...):
  FROM
    
    REC PROC P (...)
      ...  body that calls Q (possibly in parallel)
    :

    REC PROC Q (...)
      ...  body that calls P (possibly in parallel)
    :
  
  :

Everything is made explicit both to the human reader/writer and the compiler
(which pre-allocates zero space for each call of Q and P, but generates the
clever free-list-memory-grabbing calling sequence described by Brinch Hansen).

That's all ... back to the marking ;-( ....

Peter.

PS. BTW, PBH's SuperPascal is a neat combination of occam and Pascal (as he
    says in his `Concurrency, Practice and Experience' article.)  Pointers
    and the heap are gone from Pascal, occam's anti-aliasing rules are
    imposed for VAR parameters and he has channels, simple protocols,
    PAR and replicated PAR.  No ALTs though :-( ... but as a language
    for the description of parallel supercomputing applications, he's
    probably right to steer clear of non-determinacy.  That picks up from
    the occam (or, rather, CSP) property that PAR on its own gives us
    completely deterministic algorithms.

    Mind you, recursive occam2.x (which includes run-time computed replication
    sizes for PAR) is looking a pretty neat publication language too.  And,
    with a bit more work, not just a publication one ...

    Now does anyone have an algorithm for efficiently gererating workspace
    for run-time sized arrays in a parallel language?!!  Maybe the power-of-2
    free-lists are still the best we can do for this ...