[plt-scheme] guido on tail recursion

Please correct my interpretation of historical developments since I'm
not old enough to have experienced them firsthand:

My understanding is that the adoption of iterative constructs of
"structured programming" languages ala C, Pascal, Python, Java, etc.
were a response to the "spaghetti code" problems of goto statements.
So apparently the aversion to having totally uncontrolled flow of
control due to arbitrary goto's spurred the invention/adoption of
constrained syntactic loop structures (for, while, etc.) -- perhaps
too constrained, but that was a result of the fear of falling back
into the spaghetti code mess. So I view the sort of features and
supported optimizations available in Scheme as a process of easing the
syntactic constraints on sensible control flow while still producing
the efficiency of pure 'goto's, at least to some degree.

Does that make sense?

--- nadeem


On Sat, Apr 25, 2009 at 5:54 PM, Joe Marshall <jmarshall at alum.mit.edu> wrote:
> I suppose you'll get several answers to your questions, but I want to
> try answering.
>
> On Sat, Apr 25, 2009 at 12:32 PM, emre berat nebioğlu <beratn at gmail.com> wrote:
>> this will be a newbie question.I read all mail but i wonder something.
>> can we say iteration instead of tail recursion.
>
> Shriram doesn't like the term `tail recursion' either, but `iteration' seems to
> imply a sequential, one-at-a-time approach.  When I say `tail recursion', I
> mean something more than just iteration.
>
> I like the `subproblem' and `reduction' terminology.  There are two ways to
> solve a complex problem:
>
> 1) break it into simpler `subproblems', solve each
> subproblem, then combine the results into a solution,
>
> 2) reduce the problem to a simpler problem that has the
> same answer and solve the simpler one instead.
>
>> I dont know how to write a
>> program with iteration in scheme
>> in java there are for,do while but someone said you can make loop in scheme.
>
> One important point is that you don't need to do anything special in Scheme
> to get iteration.  A process in Scheme will execute iteratively if it consists
> of a chain of reductions.  In languages like Java, the programmer has to
> specifically instruct the computer to behave iteratively through use of special
> iteration constructs like `for', `do', and `while'.  In Scheme, the computer
> figures this out all by itself.
>
>> In tail recursive, program can be written by adding one extra parameter in
>> scheme,in java.But logic is same in both tail recursion and iteration "not
>> using stack (memory)". I mean using temprary value instead of using
>> memory.If i make a mistake i am sorry.I am beginner on programming.
>
> I think I understand what you mean here.  It is often the case that by
> adding an additional parameter you can transform a program from a
> recursive one into an iterative one.  (But not always.  I think you can
> only transform `primitive recursive' programs this way.)
>
>> And why are we writing recursive program.There are some advantages on that ?
>
> Yes.  There are recursive programs that cannot be expressed as iteration.
> In fact, the set of programs that can be expressed with iteration is
> much smaller than the set of programs that can be expressed with
> recursion.  And it appears to be the case that if you can't express a program
> recursively, then you can't compute it at all (through any means!).
>
> So recursion is the most powerful tool we have.
>
>> Let say we wrote factorial function with recursion and call it like
>> factroail(50).Program stuck.If you use laptop,your machine warm up,may be
>> other process on machine cannot be proceed for sometime.
>>
>> But you wrote this program with tail recursive.Your calculation ends with
>> two or three second.
>>
>> So may be we prefer CPS.But both CPS and tail recursion is faster and
>> freeofcost and not diffucult for machine.But recursive is opposite.Why do we
>> still write program with recursive.
>
> Not every problem can be transformed like this.  And even if you *can* rewrite
> a program to be iterative, it may not be the clearest way of expressing what
> you want.
>
>>
>> (your discussion is very advanced to me and i ask few question i try to
>> improve myself i hope you are welcommed me)
>>
>>
>> On Sat, Apr 25, 2009 at 9:49 PM, Joe Marshall <jmarshall at alum.mit.edu>
>> wrote:
>>>
>>> The word `call' itself is problematic because it implies a return.
>>>
>>>
>>> On Sat, Apr 25, 2009 at 11:42 AM, Shriram Krishnamurthi <sk at cs.brown.edu>
>>> wrote:
>>> > It is dangerous to use the term "tail recursion" ever, unless you
>>> > really, really mean recursion in the very narrow sense by which the
>>> > doofus-in-the-street understands it, namely "a function that
>>> > *directly* calls itself".
>>> >
>>> > I have seen an especially strong trend amongst MIT folks to use "tail
>>> > recursion" to refer to the general case of "a sequence of calls that
>>> > eventually result back in the same function, even if indirectly".
>>> > This is technically correct, and the meaning of this general phrase
>>> > may be obvious to all members of the very highly intelligent species
>>> > that populates MIT.  But it confuses the doofus, and that's a problem,
>>> > because it leads to the sort of confusion in Guido's message and
>>> > ensuing discussion -- on a topic that needs less, not more, confusion.
>>> >
>>> > [Tail calls that do not lead to recursion are still worth optimizing,
>>> > but they cannot lead to order-of-complexity increases in size except
>>> > in pathological cases, so they are not as interesting to focus on
>>> > because that, too, distracts the conversation.]
>>> >
>>> > Shriram
>>> >
>>>
>>>
>>>
>>> --
>>> ~jrm
>>> _________________________________________________
>>>  For list-related administrative tasks:
>>>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>>
>>
>
>
>
> --
> ~jrm
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>



-- 
Nadeem Abdul Hamid
Assistant Professor, Computer Science
Berry College
PO Box 5014
2277 Martha Berry Hwy NW
Mount Berry, GA 30149-5014
(706) 368-5632
http://cs.berry.edu/~nhamid/