From: roger@gimli.inmos.co.uk (Roger Shepherd)
Subject: Re: IS Occam3 recursive?
Organization: INMOS Limited, Bristol, UK
Date: Tue, 17 Nov 1992 09:33:35 GMT

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
Newsgroups: comp.sys.transputer