From: rob@pact.nl (Rob Kurver)
Subject: Re: Recursion in occam
Organization: PACT, Delft, The Netherlands
Date: Fri, 20 Nov 1992 13:22:04 GMT

In <1992Nov20.102603.2898@titan.inmos.co.uk> rob@icarus.inmos.co.uk (Robin Pickering) writes:

>In article <rob.722177288@dutncp8> rob@pact.nl (Rob Kurver) writes:
>>In <142@autro1.UUCP> teig@autro1.UUCP (Oyvind Teig) writes:
>>
>>>Recursion of occam-2 or -3
>>
>>>I have seen enough of stack overflow errors to appreciate the lack
>>>of recursion in occam.
>>
>>Recursion + stack-checking -> no stack overflow.
>>
>...
>>
>>When I say "stack checking" I mean "stack checking plus expansion if
>>necessary".  By checking the stack and expanding it if necessary, you
>>remove the stack overflow.

>The system you describe does not "remove stack overflow", it simply makes
>it impossible for the programmer to deduce the circumstances under which
>a stack overflow will occur.

In my book, stack overflow means using memory past the end of the stack,
which typically results in rather fatal problems.  By extending the stack
when needed it no longer overflows.

Yes, to extend the stack you do require dynamic memory allocation.
Now, if you run out of memory at this point you're in trouble.  I would
call this a memory problem, not a stack overflow problem.  Memory can be
exhausted on any system with limited amounts of physical and/or logical
memory, not just on a system that extends the stack when necessary.

>I can just see it now, an airliner on final approach, pilot hits the
>undercarriage lever:

>"Please wait, stack extension in progress"
>....
>"Stack extension failed (memory fragmented)"
>"Error flag set (please re-boot)"

Yes, that would be inconvenient, wouldn't it?  But then, it would also
be inconvenient if the machine got stuck in an infinite loop, or
misbehaved due to one of a zillion other reasons.

>Get real, OCCAM was designed for programs where it was fairly important
>to the programmer to be able to predict how the end system would behave.
>Don't ask for OCCAM to have features introduced which break this critical
>functionality.

Do you really think recursion is the only thing inhibiting a prediction
about end system behavior?  Everything else can be checked by compilers?
It is never possible for an Occam program to be waiting for a value that
never arrives, or not in time?  An Occam compiler can tell you all this
at compile-time, because there's no recursion?

>If you want want quicker development cycles and don't mind indeterminate 
>behaviour of your system at run-time, fine use C with these kinds of
>extensions.

I would hardly call recursion an extension to C.  Or to most other
programming languages, for that matter.  Neither is stack extension
an extension to C, as C does not define stacks, nor what should happen
with them when they run out of space.

>            Nothing wrong with that, for a certain class of applications
>this is a perfectly acceptable programming environment (I use it a lot).
>However please don't use such a system to develop software for any 
>airliner that I might travel on! (or any other kind of system where failure
>is anything other than a moderate inconvenience).

I fail to see how a program (written in Occam or any other language) is
safe if and only if it does not use recursion.  This would have major
implications for the design of critical systems!

Recursion with stack extension is just a special form of dynamic
memory.  The problem with dynamic memory is that it is a scarce
resource: you don't know when it will run out, and you don't want it
to run out at the wrong moment.  Now you can do one of two things:
not support dynamic memory in the hope it will not be needed, or
support it the best you can so it can be controlled.

When dynamic memory is not supported people will have to jump through
hoops when they need it anyways (there's been plenty of testimony to
that in recent days), and they are bound to make a mistake sooner or
later.

By supporting it and educating users about the potential problems
with it, you give programmers the choice to use it or not.  If they
don't need it, fine, you don't run into problems with it.  If they
do need it, they at least have working support for it.

Back to recursion:  if recursion is supported programmers can either
use it or not.  If they decide not to use it, fine, they don't run
into any problems with it (as the compiler system will be able to
determine so at link-time and allocate all stacks statically).  If
they do need it, at least they have working support for it, and they
know what the consequences may be.

Similar arguments can be applied to iteration, replication, etc.

Anyways, I'd be very interested in an explanation of the special
position of memory as a scarce resource.  What about time?  What
about disk storage?  Perhaps files should be disallowed as well,
since they may fill up your disk and your plane may crash?

>--
>   Rob.

Cheers. - Rob

P.S.: I've been told that the original pre-transputer Occam language
      (I think it was implemented on a VAX back then) did support
      recursion.  Can anybody confirm or deny this?
--
     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