[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: OCCAM, JOYCE, SUPERPASCAL AND JAVA
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:
> (n = 1)
> result := 1
> result := n * factorial (n-1)
> RESULT result
> and an unbounded PAR statement:
> INT n:
> ... 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)
VAL top IS [list FROM 0 FOR pivot] :
VAL bottom IS [list FROM pivot + 1] :
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