[erlang-questions] Erlang for youngsters

Lloyd R. Prentice lloyd@REDACTED
Tue Jun 24 03:33:48 CEST 2014


Logo, based on Lisp, developed at MIT, has been widely taught to kids, er, rather, given to kids to teach themselves. They develop recursive programs to draw beautiful turtle graphics.


Children's Mental Models of Recursive Computer Programs



Sent from my iPad

> On Jun 23, 2014, at 8:53 PM, "Richard A. O'Keefe" <ok@REDACTED> wrote:
> 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.
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions

More information about the erlang-questions mailing list