Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!wuarchive!hsdndev!husc6!carlton
From: carlton@husc10.harvard.edu (david carlton)
Newsgroups: comp.lang.scheme
Subject: Re: Notions of program correctness (was Re: Tail-calling ...)
Message-ID: <CARLTON.91Feb18160459@husc10.harvard.edu>
Date: 18 Feb 91 21:04:59 GMT
References: <9102112032.AA03542@cymbal.reasoning.com.>
	<harlan.666514120@copper> <CARLTON.91Feb15122042@husc10.harvard.edu>
	<HANCHE.91Feb17002434@hufsa.imf.unit.no> <908@anaxagoras.ils.nwu.edu>
Sender: news@husc6.harvard.edu
Organization: Citizens for Boysenberry Jam
Lines: 75
In-reply-to: krulwich@ils.nwu.edu's message of 18 Feb 91 18:14:34 GMT

In article <908@anaxagoras.ils.nwu.edu> krulwich@ils.nwu.edu (Bruce Krulwich) writes:
   [A discussion was started about tail call optimization effecting the
   "correctness" of a program.  It was pointed out that tail call optimization 
   doesn't effect what programs will run, only how efficient they will be.  In
   response to this...]

   hanche@imf (Harald Hanche-Olsen) writes:
   >On a machine with infinite memory, optimizing tail recursion does not
   >change the meaning of programs.  However, in Scheme you can write a
   >loop using a tail call and the loop can execute millions of times
   >without running out of memory if it can do it once.  I'd say that
   >whether or not the program runs out of memory changes its meaning,
   >whether the semantics say so or not ...

   In Scheme you can write a program that uses CONS that will run out of memory
   on a machine with a 5-byte heap.  Does that mean that no program that uses
   CONS can be assumed to work across Scheme implementations?  Also, in Scheme
   it is possible to write a recursive (non-tail) function that will run out of
   memory on some implementations.  Does that mean that any recursive
   (non-tail) function in Scheme doesn't have the same meaning across
   implementations?

[ he then goes on to talk more about how tail recursion isn't a
semantic difference. ]

Hmmm.  I'm not sure that i agree with this, even though i made a post
a few days ago saying something like it.  After some discussion in
e-mail, i think that there is a semantic difference that it is
profitable to make: there exist programs that will run on Scheme
implementations with sufficiently large amounts of memory that will
not run on an implementation that does not optimize tail calls into
jumps.  While i agree with bruce that merely lowering the amount of
necessary for a program to run correctly isn't semantically important,
i do think that changing a program from something that will always run
out of memory to something that may not run out of memory is
important.  The simplest example of such a program is:

(define forever
  (lambda ()
    (forever)))

Of course, this isn't very interesting.  Another example might be

(define wait-until-eof
  (lambda ()
    (if (eof-object? (read-char)) #t
        (wait-until-eof))))

And while this function itself doesn't do anything useful, with only
slight modification you can turn it into a read-eval-print loop, say.
Note that under any given (finite) input, this program will run
correctly under either under a tail-recursive or non-tail-recursive
implementation; the difference is that under a tail-recursive input
there exists an amount of memory which will be enough for any input,
whereas under a non-tail-recursive implementation for any input there
exists an amount of memory which will be enough, but that amount can
be different for different inputs.  Another example might be

(define even?
   (lambda (num?)
     (cond
       ((zero? num) #t)
       ((= num 1) #f)
       (else (even? (- num 2))))))

(and no, i wouldn't write even? that way myself, but again there are
useful programs which look like that.)

david carlton
carlton@husc9.harvard.edu

	"Parentheses in Scheme are like the petals of a cherry blossom;
	 they come for a time, evaluate themselves, and are gone."

			-- Greg "Moonbeam Thru Prune" Travis