From: rob@pact.nl (Rob Kurver)
Subject: Re: IS Occam3 recursive?
Organization: PACT, Delft, The Netherlands
Date: Fri, 13 Nov 1992 14:01:57 GMT

In <BxnGAH.3t9@sci.kun.nl> Marco Kesseler <marcok@cs.kun.nl> writes:


>In article <1992Nov12.094835.8563@wraxall.inmos.co.uk> Geoff Barrett,
>geoffb@inmos.co.uk writes:

>>More seriously, it does illustrate an important property of occam
>>processes, namely that their workspace requirements can be determined
>>statically.  If you can't do this, then the implementation of parallel
>>processes becomes much more difficult. In current implementations of
>>occam, it is possible to allocate a fixed amount of workspace for each
>>parallel process.  If you allow recursive processes you cannot
>>determine statically how much workspace each process will need.  This
>>means that you have to know what to do with stack overflow when the
>>obvious place to extend it has been allocated to something else
>>already.

>Sofar, I agree.

Me too.  The obvious thing to do is to allocate a new chunk of memory
to use for the stack.  There's nothing very hard about this - many
compiler systems have done it for years, even before transputers
existed, and many transputer compiler systems support this as well.

>>If you think you have a solution to this, and it does not
>>have an adverse affect on the context switch time, then I will be
>>interested to hear it.

>I am confused. What do you mean when you talk about a 'context
>switch'? It is clear that recursion implies additional overheads
>at runtime during function calls. That it affects the time to
>timeslice processes is totally new to me. Perhaps I am missing
>a point here.

Stack checking and extension in the function prologue introduces
a certain overhead (typically some 5 to 10 percent with a straight-
forward implementation).  It does not introduce any context switch
overhead.  In time-critical code it makes sense to optimize the
stack use to ensure no stack extension is done (or even checked
for) in the 10% of your code that uses 90% of your cycles.  In this
way it is really quite easy to have arbitrary recursion where you
need it, at a negligible overhead.

Again, this is not very exciting or new, and is, IMHO, a rather
basic requirement for ANY professional transputer compiler
(especially C compilers, of course).  The existance of multiple
threads does not make this problem any harder, and does not
excuse the compiler system from supporting this.

Recursion is a very powerful programming tool, and is very clean
and `mathematically correct'.  The fact that it introduces variable-
size stacks is a tad inconvenient, but no excuse to remove the
feature from a modern programming language.  IMHO, of course.

>>In general, it is more important for an
>>embedded application to be sure of enough space in which to run.  After
>>all, you don't want to run out of memory just as you reach a critical
>>section of control code.

>Yes, but knowing how much stack space the embedded application needs
>is no reason to rule out the possibility to use recursion in some
>language:
>If you don't need it, don't use it.

Exactly!

>Marco Kesseler
>Faculty of Mathematics and Computer Science
>University of Nijmegen

Rob Kurver
PACT Parallel Architecture and Compiler Technology
--
     PACT                   Rob Kurver
    Foulkeslaan 87         rob@pact.nl
   2625 RB Delft     ph: +31 15 616864 
  The Netherlands   fax: +31 15 610032
Xref: sparky comp.sys.transputer:1172 comp.os.ms-windows.apps:4662 comp.os.ms-windows.misc:4465 comp.os.ms-windows.programmer.misc:3334