Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!usenet.ins.cwru.edu!cwphysbb.PHYS.CWRU.Edu!eric
From: eric@cwphysbb.PHYS.CWRU.Edu (Eric M. Rains)
Newsgroups: comp.lang.misc
Subject: Re: The Universal Language
Summary: Proof of no recursion impossible
Message-ID: <1990Aug13.224738.5469@usenet.ins.cwru.edu>
Date: 13 Aug 90 22:47:38 GMT
References: <1990Aug13.213113.3743@craycos.com>
Sender: news@usenet.ins.cwru.edu
Reply-To: eric@cwphysbb.CWRU.EDU (Eric M. Rains)
Organization: CWRU Physics Department
Lines: 58

In article <1990Aug13.213113.3743@craycos.com> pmk@craycos.com (Peter Klausler)
says:

>Matthew Austern:
>> Can you really imagine a C compiler/linker that can prove that a
>> program has no recursive calls, and use a simpler calling convention
>> for such programs?)
>
>Uh, yes, I can. I use one daily. Why is this so unimaginable?

     Because it's completely impossible, that's why.  Imagine the following
piece of C code:

unsigned long possibly_recurse(void fun(),unsigned l)
{
if (l<=0)
  return(1);
else
  return(l*fun(fun,l-1));
}

void main(void)
{
if (some_other_function()) {
  printf("%lu!=%lu\n",5,possibly_recurse(possibly_recurse,5);}
else {
  printf("I am not undergoing recursion.\n");}
}

Now, consider the possibilities.  If "some_other_function()" is really a macro
that returns 0, then the program will not do any recursion.  However, if it
returns something else, the program will perform recursion.  How is your C
compiler going to be able to tell what to do in this case? 

     Suppose it decides that there is recursion going on here.  What if another
module contains only functions that do not recurse?  Suppose I want to call the
function possibly_recurse with arguments (non_recursive_func,3), where the
definition of non_recursive_func is

unsigned long non_recursive_func(void *junk,unsigned l)
{
return(l);
}

How can I link to this other module?  The calling conventions will be different
(assuming the module with non_recursive_func has no recursion)...

                                        Eric

P.S.  Besides; in a language like C, the problem of determining whether a
program performs recursion is equivalent to the halting problem...
-----
"...and the moral of that is--'Be what you would seem to be'--or, if you'd like
it put more simply--'Never imagine yourself not to be otherwise than what it
might appear to others that what you were or might have been was not otherwise
than what you had been would have appeared to them to be otherwise."
                          --Lewis Carroll, Alice's Adventures in Wonderland