🚀 go-pugleaf

In article <MICHAEL.92Nov16185558@lucrece.uk.ac.oxford>, 
michael@uk.ac.oxford.robots (& Stevens) writes:
|> Now the arguments about recursion and OCCAM have been going a while I
|> though I would make a quick summary.
|> 
|> FOR recursion:
|> 	1. Recursion is mathematically elegent. Serious software
|> engineering requires it.

This depends on what you mean by "serious software enginerring". Certainly,
there are a large class of problems which are best handled via a language
which supports recursion. There are also very many problems which do not.

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

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

|> 	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!"+

|> Ok enough humour, how about the even tricker issue of dynamic memory
|> allocation. Does OCCAM 3 need it as part of the language? Should OCCAM
|> 3 have type safe pointers? Or should we be content with INT32 and
|> library procedures to allocate memory?

Again, there is more to this than the issue of type safe pointers. Remember,
occam is supposed to be a language for programming distributed systems -
this means that pointers may become meaningless when passed from one process
to another.

Actually, a recurive occam-like language is a good idea, and very good fun
to use. However, it creates a language which is substantialy different
(in terms of relative costs of operations (+, call, PAR) from occam. In the
past we have built an occam (1?) system which had recursion. It let you
write wonderful (apart from the non-termination of the code) things like:

    PROC sieve(CHAN source, sink)
      INT my.prime :
      SEQ
        source ? my.prime
        sink ! my.prime
         
        CHAN to.next.sieve :
        PAR
          sieve(to.next.sieve, sink)

          WHILE TRUE
            INT candidate :
            SEQ
              source ? candidate
              IF
                candidate \ my.prime = 0
                  to.next.sieve ! candidate
                TRUE
                  SKIP
   :                                          

   CHAN to.sieve, from.sieve :
   PAR 
    sieve(to.sieve, from.sieve)

    INT candidate :
    SEQ
      n := 2
      WHILE TRUE
        SEQ
          to.sieve ! n
          n := n + 1
        
    
     WHILE TRUE
       INT prime :
       SEQ        
         from.seive ? prime
         print(prime)
    
-- 
Roger Shepherd, INMOS Ltd   JANET:    roger@uk.co.inmos 
1000 Aztec West             UUCP:     ukc!inmos!roger or uunet!inmos-c!roger
Almondsbury                 INTERNET: roger@inmos.com
+44 454 616616              ROW:      roger@inmos.com OR roger@inmos.co.uk

In article <MICHAEL.92Nov16185558@lucrece.uk.ac.oxford> michael@uk.ac.oxford.robots (& Stevens) writes:
>Now the arguments about recursion and OCCAM have been going a while I
>though I would make a quick summary.
>
>FOR recursion:
>	1. Recursion is mathematically elegent. Serious software
>engineering requires it.
>	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.
>	3. You don't need to use it. If you want to be able to
>predetermine memory usage at compile time don't recurese.
>	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.
>
>AGAINST recursion:
>	1. OCCAM 2 doesn't do it.
>	2. Its not implemented in OCCAM 2.
>	3. Thats all I can think of, but I am sure it has something to
>do with OCCAM 2.
>
>Personally I think the arguments against have it :-)
>
>Ok enough humour, how about the even tricker issue of dynamic memory
>allocation. Does OCCAM 3 need it as part of the language? Should OCCAM
>3 have type safe pointers? Or should we be content with INT32 and
>library procedures to allocate memory?
>
>Would all this overburned OCCAM and turn it into yet another hacked up
>language like C?
>

Three years ago I wrote a large program in Occam2.

After writing some stack based utilities using arrays in Occam to
allow simulated recursion. This took time to develop.

Nowadays I use Inmos Parallel C which is a far more usable language.



-- 
Email: N.H.Thomas@cs.bham.ac.uk     G7ABW
Work:   Fax: +44 (0)21 414 4281     Tel: +44 (0)21 414 3736
Home:   Fax: +44 (0)21 454          Tel: +44 (0)21 454 5729
Mobile: +44 (0)891 

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

In article <rob.721665532@dutncp8> rob@pact.nl (Rob Kurver) writes:
>What's so special about a program running out of memory at runtime?

It stops.  Unfortunately, embedded systems can't prompt the user to add some
more RAM when coming into land.

>How about disk space? How about time?

With disk space the same.  With real time systems one normally thinks
of something sensible to do if you miss a deadline, this could be stopping.

>Having to deal with building your own stack distracts you from the
>real problem at hand, i.e. solving your problem.  Further, the
>extra code required makes your program harder to read and understand,
>especially when you come back in a couple months time.

Yes, I had to build it by hand.  No, I don't find it much harder to
understand today.

>Similarly, having to deal with creating processes, starting processes,
>waiting for processes etc. yourself is distracting and prone to errors.
>It is a job much better done by the compiler.

True, I don't know if the possibilities of constant-at-compile-time
recursion have been looked at.  I suspect they have and that it is 
too expensive in performance terms.

>These language constructs make your program easier to read,  the
>algorithm easier to understand, and thus, ultimately, they help you
>solve your problem quicker.

I hope you mean "express your problem with more brevity".

As we have seen with occam, constructs on their own, are not the most
powerful way to build up a language.  Replication gives occam more
than a for loop could.

In article <MICHAEL.92Nov16185558@lucrece.uk.ac.oxford> michael@uk.ac.oxford.robots (& Stevens) writes:
>FOR recursion:
>	1. Recursion is mathematically elegent. Serious software
>engineering requires it.

I work with a formal method called UNITY (Parallel Program Design, Chandy
and Misra) which comes with a parallel programming notation.  I was
surprised how powerful it is without having recursion in it.

>Ok enough humour, how about the even tricker issue of dynamic memory
>allocation. Does OCCAM 3 need it as part of the language? Should OCCAM
>3 have type safe pointers? Or should we be content with INT32 and
>library procedures to allocate memory?
>
>Would all this overburned OCCAM and turn it into yet another hacked up
>language like C?

Fraid so.

In article <1992Nov17.093335.11067@inmos.co.uk> roger@gimli.inmos.co.uk (Roger Shepherd) writes:
>Actually, a recurive occam-like language is a good idea, and very good fun
>to use.

I would very much like such a language that has all the things that
parallelism prevents: recursion, pointers, dynamic memory and data
structures.  I like having the rigorous semantics and the transformation laws.
Though having said all of that, I also like having PAR without using
PLACED PAR.  It would be interesting to see if occam - PAR + OO is not
as expressive as occam.

The programming language Turing has a formal semantics too, but no structuring
through indenting, replication or the other design decisions I prefer the
direction of in occam.  I think this liking will extend to occam 3 from having
seen Jon Kerridge use of it.

As, no one language can be ideally suited for all applications,
>
>there are a large class of problems which are best handled via a language
>which supports recursion. There are also very many problems which do not.
>
and there appears to be quite an argument along the lines of Michael's "why
don't you have it and just not use it when you don't need it", which as
Roger Shepherd said, means having two compilations approachs (if I understand
correctly).  Perhaps Inmos have a market for a family of occam languages,
occam.par and occam.seq.

Things should not be multiplied beyond need---however, if there's a need.

Warren

If it is considered reasonable to force the programmer to declare the
size of all arrays at compile time why isn't it reasonable to force
the programmer to declare the depth of recursion at compile time?

It seems to me that it would be better to take this approach than to
have all the programmers writing their own code to implement recursion
with all the wasted time and errors that involves.
-- 
Lindsay Patten
Pattern Analysis & Machine Intelligence Group         lindsay@pami.uwaterloo.ca
Dept. of Systems Design Engineering  {utai|decvax|uunet}!watmath!watnow!lindsay
University of Waterloo                   Neither I nor PAMI speak for the other

In <2292@eagle.ukc.ac.uk> wgd@ukc.ac.uk (Warren Day) writes:

>I would very much like such a language that has all the things that
>parallelism prevents: recursion, pointers, dynamic memory and data
>structures.

I'm afraid you've lost me:  why do you think parallelism prevents
recursion, pointers, dynamic memory and (especially) data structures?
Parallelism may complicate matters, but it doesn't actually prevent any
of these things.

>and there appears to be quite an argument along the lines of Michael's "why
>don't you have it and just not use it when you don't need it", which as
>Roger Shepherd said, means having two compilations approachs (if I understand
>correctly).

Not necessarily.  A smart enough compiler system may well be able to
support recursion at a small price if used, but without any overhead if
not used.  This can be implemented by a smart linker, which uses a call
graph to locate recursion and inserts stack allocation and expansion
code where necessary.  If no recursion is used, no stack expansion code
is introduced.

>             Perhaps Inmos have a market for a family of occam languages,
>occam.par and occam.seq.

I don't believe it would be wise for Inmos or any other transputer
compiler vendor to have parallel and sequential versions of their tools.
It may make sense to provide compiler options to allow stack stacking
and expansion to be tuned, in the absence of aforementioned smart
linker.

The CSP paradigm as supported by Occam and PACT Parallel C is a very
powerful one, and is especially interesting with the support provided
by the transputer.  It is up to the implementation to avoid unnecessary
overhead.

Cheers. - 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.722034771@dutncp8> rob@pact.nl (Rob Kurver) writes:

>
>The CSP paradigm as supported by Occam and PACT Parallel C is a very
>powerful one, and is especially interesting with the support provided
>by the transputer.  
>
>Cheers. - Rob
>

Rob, you seem to have forgotten about INMOS ANSI C providing the same sort of
CSP paradigm as your own, this obviously slipped your mind :-). I guess the 
difference boils down to whether you want an ANSI C validated compiler with 
functional additions for parallelism and communications or an ANSI C compiler 
with non-ANSI language additions for the same. I would argue (from customer 
feedback) that OCCAM tends to be used along with INMOS ANSI C as this 
provides you with a flexible environment for parallel/comms/sequential 
programming with excellent diagnostics at compile and run time.

Just to cloud the issue once more INMOS' soon to be shipping new optimising C 
compiler has a specific optimisation for tail call recursion i.e.

void p (int q)
{
  ...
  return(p(...));
}

in this case the workspace of p is reused as the function recurses, also, 
nested returns are omitted so that only one return is needed no matter how many 
levels of recursion take place.

Steve

Steve Doyle, Software Marketing, INMOS Ltd   | Tel +44 454 616616
1000 Aztec West                              | 
Almondsbury                                  | UK: steved@inmos.co.uk
Bristol BS12 4SQ, UK                         | US: steved@inmos.com

In <1992Nov18.130407.12799@titan.inmos.co.uk> steved@lion.inmos.co.uk (Stephen Doyle) writes:

>In article <rob.722034771@dutncp8> rob@pact.nl (Rob Kurver) writes:

>>
>>The CSP paradigm as supported by Occam and PACT Parallel C is a very
>>powerful one, and is especially interesting with the support provided
>>by the transputer.  
>>
>>Cheers. - Rob
>>

>Rob, you seem to have forgotten about INMOS ANSI C providing the same sort of
>CSP paradigm as your own, this obviously slipped your mind :-). I guess the 
>difference boils down to whether you want an ANSI C validated compiler with 
>functional additions for parallelism and communications or an ANSI C compiler 
>with non-ANSI language additions for the same.

Steve, you seem to have forgotten about PACT Parallel C providing the same
sort of functional additions as your own, this obviously slipped your
mind :-).  It is my humble opinion that the CSP paradigm really should be
supported by language constructs.  Yes, use of the C language constructs
makes for a not strictly conforming program, so you'd better not use them
if you intend to port your code to a non-transputer.  Better not use
Occam in this case, either... :-)  The language constructs were added to
PACT Parallel C in an ANSI conforming manner - if you don't use them, you
have a fully validated ANSI C compiler.  (Please reply by email if you're
interested in the details of this.)

I guess the difference boils down to whether you want an ANSI C validated
compiler with functional additions for parallelism and communications or
an ANSI C validated compiler with the same functional additions for
parallelism and communications, with language constructs thrown in as
well.

>                                               I would argue (from customer 
>feedback) that OCCAM tends to be used along with INMOS ANSI C as this 
>provides you with a flexible environment for parallel/comms/sequential 
>programming with excellent diagnostics at compile and run time.

We support mixing of Occam and PACT Parallel C object modules, for the
exact same reasons Inmos do.  No argument there.  Although customer
feedback indicates people eventually forget about Occam as they find
they can do everything they want in PACT Parallel C.

>Just to cloud the issue once more INMOS' soon to be shipping new optimising C 
>compiler has a specific optimisation for tail call recursion i.e.

We decided against tail recursion optimization as it really doesn't improve
performance very much.  Of course, we continue to add optimizations and
improve our product as well, to make sure PACT Parallel C stays faster.
I've seen benchmark results of the beta version of your new optimizing C
compiler, and was relieved (although not surprised) to see PACT Parallel
C is still faster.

>Steve

Rob

P.S.: How come we don't here from Kirk Bailey about this recurring
      subject?  Are you still with us, Kirk?

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

In article <rob.722034771@dutncp8> rob@pact.nl (Rob Kurver) writes:
>I'm afraid you've lost me:  why do you think parallelism prevents
>recursion, pointers, dynamic memory and (especially) data structures?
>Parallelism may complicate matters, but it doesn't actually prevent any
>of these things.

As Roger Shepherd said, the mixture of the two, colours performance issues.

>Not necessarily.  A smart enough compiler system may well be able to
>support recursion at a small price if used, but without any overhead if

Why should there have to be a price.

>not used.  This can be implemented by a smart linker, which uses a call
                                         slow

>I don't believe it would be wise for Inmos or any other transputer
>compiler vendor to have parallel and sequential versions of their tools.

What I was suggesting was a sequential language (not that I want to wait
longer for occam 3, but).  This language looks like occam 3 and has a similar
foundation, but has no parallelism, instead it has recursion and pointers and
things.  However, I suspect that "recursion & pointers" and "similar
foundation" are logically incompatible.

>Cheers. - Rob

Warren

In article <rob.722124411@dutncp8> rob@pact.nl (Rob Kurver) writes:
>In <1992Nov18.130407.12799@titan.inmos.co.uk> steved@lion.inmos.co.uk (Stephen Doyle) writes:
>
>...  Although customer
>feedback indicates people eventually forget about Occam as they find
>they can do everything they want in PACT Parallel C.
>
You are rather trivialising OCCAM to syntax for creating/using processes and
channels, there is much more than this to the language, a C environment 
simply does not provide the semantics, compile and run-time checking, 
formal proving or transformation methods that you get with OCCAM. OCCAM is
a popular language and is not losing popularity, you can rewrite an 
application in obfuscated C but it bears only a passing resemblance to 
OCCAM. I still echo the sentiment of many customers who like to use the
benefits of both.

>I've seen benchmark results of the beta version of your new optimizing C
>compiler, ...

Aren't benchmarks wonderful, so subjective! 

Just as well there are so many other goodies in the package then!

> ... email me for details

Likewise

Steve


Steve Doyle, Software Marketing, INMOS Ltd   | Tel +44 454 616616
1000 Aztec West                              | 
Almondsbury                                  | UK: steved@inmos.co.uk
Bristol BS12 4SQ, UK                         | US: steved@inmos.com

In article 92Nov16185558@lucrece.uk.ac.oxford, michael@uk.ac.oxford.robots (& Stevens)
 writes:
>Now the arguments about recursion and OCCAM have been going a while I
>though I would make a quick summary.
>
>FOR recursion:
>	1. Recursion is mathematically elegent. Serious software
>engineering requires it.
Rubbish.  It is true that mathematical elegance is `nice', but 
serious engineering is not about producing nice programs for display
at the Tate, but robust programs which do what they are designed to do
when they are asked to do it.  Every time.  Even when operated by
morons.  

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

Rubbish.  C has one stack, when it fills you are stuck with no way out
anyway.  OCCAM would need p stacks - where p is the number of processes
(which changes dynamically).  When one runs out, you might have been 
better off making that one bigger and the others smaller - but it is
too late.

>	3. You don't need to use it. If you want to be able to
>predetermine memory usage at compile time don't recurese.
This seems OK, but there is probably something wrong with it.

>	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.
>
Because memory CAN be predetermined, the others cannot.  Computing 
time is data dependent and would probably involve solving the halting
problem.  Disk space ditto.


>AGAINST recursion:
>	1. OCCAM 2 doesn't do it.
Neither does FORTRAN.

>	2. Its not implemented in OCCAM 2.
See Geoff Barrett for the dirty trick which makes it look as though
it is.

>	3. Thats all I can think of, but I am sure it has something to
>do with OCCAM 2.
OCCAM 1 is all that is NEEDED.

--
Dr David J. Pritchard		
Electronics and Computer Science	tel	(+44 703) 592722
University of Southampton		fax	(+44 703) 593045
Southampton SO9 5NH			email	djp@uk.ac.soton.ecs (UK)
United Kingdom					djp@ecs.soton.ac.uk (World)

In <2306@eagle.ukc.ac.uk> wgd@ukc.ac.uk (W.G.Day) writes:

>>Not necessarily.  A smart enough compiler system may well be able to
>>support recursion at a small price if used, but without any overhead if

>Why should there have to be a price.

Few things in life are free.

>>not used.  This can be implemented by a smart linker, which uses a call
>                                         slow

I don't think building a call-graph during linking gives a noticeable
performance difference.  The time required is certainly negligible
compared to the time needed for file I/O.  If you have data that shows
otherwise, please post it.

Rob

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

It seems that this argument has degenerated into two camps: those who
think Occam is more "reliable" than C because it doesn't have recursion,
and those who need to use recursion and therefore program in C (does
anyone use Pascal on the Transputer?)

The reason lack of recursion makes Occam more "reliable" seems to be
that the proponents of this argument can't think of a decent way to
allocate memory on a fixed-memory machine.  Given that many of these
proponents come from Inmos perhaps that explains why Inmos C handles
memory resources so badly...

For my own experience, I ported a largeish application from Occam to C,
still on the Transputer.  The result ran about the same speed, even
though the C compiler seems to generate code which runs much slower than
the Occam compiler.  The compensating factor was in algorithm
improvements made possible by the improved expressability of C.  The
result as also *much* more reliable than its Occam predecessor as I had
been able to remove large chunks of code which were only necessary in
the older system to get around the limitations of Occam, and could thus
devote my effort to improving the system instead of working around the
compiler.

	-jeremy

--
--
Jeremy Webber			   Internet: jeremy@cs.adelaide.edu.au
Digital Arts Film and Television,	     jeremy@chook.ua.oz.au
1 Ledger St, Beverley, SA 5009,       Phone: +61 8 347 4691
Australia			        FAX: +61 8 347 4692