From: rob@pact.nl (Rob Kurver)
Subject: Re: IS Occam3 recursive?
Organization: PACT, Delft, The Netherlands
Date: Tue, 17 Nov 1992 12:59:03 GMT

In <1992Nov17.093335.11067@inmos.co.uk> roger@gimli.inmos.co.uk (Roger Shepherd) writes:

>In article <MICHAEL.92Nov16185558@lucrece.uk.ac.oxford>, 
>michael@uk.ac.oxford.robots (& Stevens) writes:

[BTW, Michael, your original article never made it to this site - did you
 restrict the distribution or did a local system goof up?]

>|> Now the arguments about recursion and OCCAM have been going a while I
>|> though I would make a quick summary.

>|> 	2. Code generation isn't hard. Handle the stack extension is possible.
>|> If it can be done for C, you can do it for OCCAM.

>Errr. C doesn't has concurrency. It is the COMBINATION of concurrency and
>recursion which leads to problems. Code generation is possible certainly,
>but the resulting code is likely either to waste memory (if you allocate
>vast amounts of memory to each process) or will run slowly (dynamic allocation
>on every procedure call).

Why do you think C has no concurrency?  Just because many C compilers
provide no elegant language constructs to specify concurrency, doesn't
mean C has no concurrency.

There exists a parallel dialect of C [guess who makes it? :-] that
is just as concurrent as Occam.  It is certainly possible to have
recursion and concurrency:  by allocating stack space in chunks it
is even possible to have recursion and concurrency at a very low
cost.  The cost of stack checking and expansion in our PACT Parallel
C compiler is more than compensated for by the code optimizations
and generation!

>|> 	3. You don't need to use it. If you want to be able to
>|> predetermine memory usage at compile time don't recurese.

>Unless you provide a system which implements both recursive and non-recursive
>occam you will pay the price of supporting recursion even when it is not used.

It is very well possible to introduce stack checking code during linking,
when a call-graph of the program can be used to determine if and when
it is possible.  This would result in ZERO overhead for a program written
without recursion, and minimum overhead for recursive programs.  We
are currently working on this feature in PACT Parallel C.

>|> 	4. Why single out memory as the single resource that should be
>|> predetermined at compile time. Time is another resource that runs out,
>|> and so does disk space.

>Running out of memory is just one issue - performance is another. Also, this 
>argument strikes me as somewhat specious - "because you can't do everything
>correctly, you shouldn't bother doing anything!"+

As indicated above (which is confirmed by our actual measurements, BTW),
performance is not a reason to disallow recursion.  Yes, recursion does
complicate the design of your compiler system and runtime environment
somewhat, but it is very well possible to support stack checking and
expansion that can be tuned by the programmer for speed if and when he
feels like it, thus resulting in negligible overhead.

Because you _can_ do recursion correctly, and it is so valuable for so
many problems, you _should_ bother to do it.  If the compiler doesn't
support it, and users need it anyway, they will just build their own
stacks, at a much higher cost.

>Actually, a recurive occam-like language is a good idea, and very good fun
>to use.  [...]

Yes, we think so, indeed.

Cheers. - Rob
--
     PACT                   Rob Kurver
    Foulkeslaan 87         rob@pact.nl
   2625 RB Delft     ph: +31 15 616864 
  The Netherlands   fax: +31 15 610032
Newsgroups: comp.sys.transputer