[erlang-questions] Erlang for youngsters

[Richard A. O'Keefe]

I like the way Friedman and Wise put it in 1974:
   Although there are those who argue that recursion
   is an unnatural programming construct, it has been
   demonstrated to be rather an intuitive and entirely
   convenient way to program IF LEARNED FIRST.  Moreover,
   this control for repetitive processes better
   approximates the standards of readability, provability,
   and changeability required in schemes of structured
   programming.
(Emphasis mine.  The body of that classic paper cites a
source for the claim of "intuitive ... if learned first.")

On 24/06/2014, at 10:34 AM, Steve Davis wrote:

> Hi Richard,
> 
> I'm confused by your response... is it possible to do tail-recursion in Java (and thus make iteration and recursion similar)?

(a) I was not talking about Java at all.  I took "e.g. Java"
    to be an aside, not the meat of your claim.
(b) Whether Java *does* do TRO is one question,
    whether Java *could* is another.  And in fact
    the question is not one about Java the language
    but javac the compiler (or other Java compilers).
    It so happens that the C compilers I use have been
    doing this for a long time, so I don't see any reason
    why a native code compiler for Java couldn't.
(c) As evidence, apparently the .NET JIT *does* do tail
    call optimisation (not just direct TRO).  See
    http://blogs.msdn.com/b/davbr/archive/2007/06/20/tail-call-jit-conditions.aspx
    The CLR has explicit support for tail calls, and the
    JIT may sometimes turn call...;ret; into a tail call
    even without that explicit marker.
(d) According to the Wikipedia article on tail calls,
    "functional languages such as Scala that target the
    JVM can efficiently implement direct tail recursion,
    but not mutual tail recursion."
(e) Eric Bruno wrote in April that
    "Brian Goetz at Oracle [...] said that [TRO is]
    on a list of things to be added to the JVM, but it's
    just not a high-priority item."

Direct tail recursion is the one you need to replace
iteration.
> 
> I had imagined that each recursive function call in a JVM would add a frame to the stack and eventually cause an overflow.

It *may* be done that way, but it doesn't *have* to be.
There is nothing stopping a Java compiler turning
direct tail recursion into JVM-level gotos.

If a Java compiler *doesn't* do that, that's a
quality-of-implementation issue in that particular
compiler, not a fundamental property of the language
or of recursion as such.

> Maybe I missed making my point. :(

Indeed you did.  You missed MY point, which is
"expensive COMPARED TO WHAT?"

If you have a naturally recursive algorithm, and
you code it somehow without (formally) using recursion,
chances are you have *emulated* recursion by manipulating
stacks of things, and the odds are that this will be
*more* expensive than letting the compiler into the secret
and having it get on with the job.  It is virtually
certain that the code will be buggy and hard to maintain.

As it happens, I've rewritten a number of algorithms in
non-recursive form.  There was one machine I used with a
4MB address space but a 128kB stack.  There was one
system where there are a number of key operations that
had to be coded in assembler...  It's *painful*.

Getting back to the point of this thread, just a month or
two ago I was making a bunch of student programs for a
fairly simple task.  The recursive programs were short,
simple, and correct.  (They weren't always *efficient*
because Java had seduced some of them into first creating a
tree of objects and then traversing it in a second pass,
instead of doing it directly.)  The non-recursive programs
were much longer, nightmarish to try to understand, and
took much longer to debug.