🚀 go-pugleaf

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.

>Rob Kurver writes:
>> 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.

>Ok, but you still have not removed the 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 linker can build a call-graph for the
entire program, so it knows which functions call which other functions.
This allows it to detect recursion.  All non-recursive branches need
only have enough stack allocated once, at the start of the branch (i.e.
at process or program creation).  The recursive branches, if any, need
to have stack checking (+ expansion) code introduced in the loop
(unless you just want to restrict the depth at linktime, of course).

This way, there's no overhead if you don't use recursion, and there is
a small overhead if you do use recursion.  You don't have stack
overflows in any case.

>This comes close to the discussion of exception-handling: how do
>you solve that in Pact-C, and what would you recommend when stack overflow
>is encountered?

Upon stack overflow, the stack is extended by allocating a new block of
memory from the heap.  If this is not possible (out of memory), you get
a fatal error message and your program aborts.

>If occam had been written from the philosophy that "if you don't need it,
>don't use it", it definitively would have not been occam.

I guess it would not have been Occam-2, no.  It might have had data
structures :-).

>Is it possible to do multi-language design with the Inmos D7205 occam
>toolset and your Pact C-compiler, like it is with the Inmos C-toolset?

Yes.  You can link Occam (TCOFF) modules with PACT Parallel C modules.

>For me as an occam-user, your parallel C (:-) is of little interest because
>C is not interesting, if it were, I would not have used occam (recursive
>definition: interesting but little useful(%-|)

I C :-).  A lot of people do find C interesting, though.

>0yvind Teig
>Autronica, Trondheim, Norway

Rob

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

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.

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)"

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.

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. 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).


--
   Rob.

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

Occam was designed as a parallel programming language, with concurrency
implemented inter- and intra-processor.

For a transputer way out on a limb somewhere, running out of memory
resource is fatal.

In most C environments, with a disk nearby, this is not a fatal
condition. Indeed, on a virtual memory machine, the application may not
even notice unless it was watching the clock.

If recursion can be guaranteed not to exceed a fixed memory resource,
there seems to be no reason why it could not be added to the language.

Guarantees up until now have not been forthcoming.

A simple system like tail-recursion can be implemented in a loop. To
put restrictions like "only use recursion when tail-recursing" or
"ping-disk < 10msec" would be a sad day for the occam-as-a-language
aficandos.

Hmm .. let me see - you seem to have enough memory THIS time - still
muddies the language waters but may be a compromise.

Cheers,     Andy.
-- 
andyr@wizzy.com  Andy Rabagliati, RR1 Box 33, Wyalusing, PA 18853 (717)746-7780

In <By1FGL.CKF@wizzy.com> andyr@wizzy.com (Andy Rabagliati) writes
about Occam and dynamic memory:

>Occam was designed as a parallel programming language, with concurrency
>implemented inter- and intra-processor.

>For a transputer way out on a limb somewhere, running out of memory
>resource is fatal.

Indeed.  So _programs_ should make sure they don't run out of memory.

Is this best accomplished by removing support for heap-based dynamic
memory from the language?  Or should you provide both static and
dynamic memory allocation, and tell people about the pros and cons
of each?

Why do you think it is impossible to run out of memory with static
memory allocation?  Don't fixed-size arrays fill up?  Don't you
actually fill up one of the fixed-size arrays quicker than one of
the dynamic-size arrays?

Statically allocating the available memory does not solve the
out-of-memory problem, but actually makes it worse!

Rob

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