Re: OCCAM, JOYCE, SUPERPASCAL AND JAVA

[Denis A Nicole <dan@xxxxxxxxxxxxxxx>]

On Tue, 8 Jun 1999, P.H.Welch wrote:

> 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.

Yes.  There is a real technical point here, that the SuperPascal version
guarantees that any bounded recursion will run given enough linear memory.

> 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.

Sane for SPoC.  I just don;t know when it would get done...

> 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.

Yes.  And it still lets you compute a sensible boun d on memory
requirements if you know the recursion depth.  Note that you know how many
such lists you require at compile time.  Note also that you do not need to
merge pairs of adjavent workspaces in the manner of the old dynamic PAR
occam for Transputers.

> 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 :-) ...

Yes, that seems sensible to me, although a fully dynamic strategy may use
less memory as you wouldn't need workspace for PROC calls that don't
actually get executed.

> 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)
>   :

We thought about this a long time ago and our (simple) solution was a REC
operator that took any number of PROCs or FUNCTIONs as arguments and put
all their names in all their scopes.  eg

REC
  INT FUNCTION ack(VAL INT m, n)
    INT value:
    VALOF
      IF
        m=0
          value := n + 1
        n=0
          value := ack(m-1,1)
        (m>0) AND (n>0) 
          value = ack(m-1,ack(m,n-1)
      RESULT value
  :

or, for mutual recursion

BYTE inch:
PROC next()
  inch = getchar()
:
REC
  PROC S()
    SEQ
      T()
      Sprime()
  :
  PROC Sprime()
    IF
      inch = '+'
        SEQ
          next()
          T()
          Sprime()
      TRUE
        SKIP
  :
  PROC T()
    SEQ
      F()
      Tprime()
  :
  PROC Tprime()
    IF
      inch = '*'
        SEQ
          next()
          F()
          Tprime()
    TRUE
      SKIP
  :
  PROC F()
    IF
      inch = 'a'
        next()
      inch = '('
        SEQ
          next()
          S()
          IF
            inch = ')'
              next()
  :
PROC main()
  SEQ
    next()
    S()
    IF
      inch = '.'
        SKIP
:


Denis A Nicole                      WWW:   http://www.hpcc.ecs.soton.ac.uk/~dan 
High Performance Computing Centre   Email: dan@xxxxxxxxxxxxxxx                  
University of Southampton           Phone: +44 1703 592703                      
UK.                                 Fax:   +44 1703 593903