Re: OCCAM, JOYCE, SUPERPASCAL AND JAVA

[Adrian Lawrence <adrian.lawrence@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx>]

Richard Beton writes:
> Denis A Nicole wrote:
> 
> > <snip>
> > The memory management story is also simple.  You calculate at compile time
> > the size of an activation record for each different recursively used
> > process.  The compiled code then manages a separate list of exact-size
> > buffers for each recursively used process. In-line code picks a buffer
> > from the list on process activation (or sbrk()'s a new one if the list is
> > empty) and returns the buffer to the list on process termination.  No
> > buffers are ever returned back from these exact-fit lists. The buffer
> > lists just grow out of contiguous free store.
> >
> > The total memory required is bounded, and is optimal if there is only one
> > recursive process---the typical teaching scenario. It all gets returned at
> > program termination.
> 
> Can I ask a [dumb] question?
> What is the difference in what Denis' solution achieves between recursive functions
> and unbounded PAR statements?

Well, first, what both Denis and I did was post a brief outline of Professor
Brinch Hansen's algorithm described in his paper. Both of us are describing
the same thing. I just called an activation record a "workspace" which is
pretty much the same thing in a transputer-like implementation. And outlined
the algorithm in occam-like syntax.

The solution belongs to Per Brinch Hansen. 

> To illustrate my question by example, what I mean is
> 
> INT FUNCTION factorial (VAL INT n)
>   INT result:
>   VALOF
>     IF
>       (n = 1)
>         result := 1
>       (TRUE)
>         result := n * factorial (n-1)
>     RESULT result
> :
> 
> and an unbounded PAR statement:
> 
> INT n:
> SEQ
>   ...  compute value for n
>   PAR i = 0 FOR n
>     ...  do lots of things concurrently

You would use the same algorithm to allocate memory for any and all
process instances. The whole point is that allocation is dynamic, so indeed
a PAR replicator need no longer be a constant.


More interesting is the case where you have parallel recursion like a quicksort
along the lines

PROC quicksort([]INT list)
    SEQ
      select pivot
      partition_about_pivot
      VAL top    IS [list FROM 0 FOR pivot] :
      VAL bottom IS [list FROM pivot + 1]   :
      PAR
        quicksort(High)
        quicksort(Low)
:


Adrian
-- 
A E Lawrence, MA., DPhil.  	adrian.lawrence@xxxxxxxxxxxxxx
MicroProcessor Unit, 13, Banbury Road, Oxford. OX2 6NN. UK.                
Voice: (+44)-1865-273274,  Fax: (+44)-1865-273275