-Fred
--
Science answers questions; philosophy questions answers.
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient with your first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient with your first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
--
And what is good, Phaedrus,
And what is not good—
Need we ask anyone to tell us these things?
question: Is it fundamentally impossible to do TCO on JVM due to
current JVM lack of primitives to do so? Would TCO ever be possible on
the JVM without a new JVM design?
rhickey: TCO is easy if you are an interpreter - see SISC Scheme.
Using Java's call stack, the JVM would have to provide it. There are
no fundamental technical difficulties, but potential issues for the
security model, which uses the call stack to ensure privileges.
--
Omnem crede diem tibi diluxisse supremum.
Because bytecode attempting to manipulate the stack and jump around
(unrestricted goto-like) in other ways than through the usual JVM
method call mechanisms would not pass verification (the first step of
the bytecode loading process on the JVM).
> Is it to keep
> the clojure compiler fast (for dynamic runtime compilation), since
> performing tail call optimisation presumably requires a bunch of extra
> checks and more complex code generation? Perhaps this could be done on
> AOT compilation?
TCO adds no complexity at all when the generated object code handles
its own stack, subroutine calling conventions etc. A compiler
targeting native code has the option of simply not storing a new
return address on the stack when compiling a tail call (if the
arguments to the current subrouting where passed in registers; if they
were passed in a stack frame, it can simply be popped, with the return
address saved and reused for the tail call). On the JVM it is
impossible, because the generated object code (JVM bytecode) is not
permitted to do this sort of thing.
Interestingly, [Erjang][1] (a port of Erlang to the JVM) apparently
performs TCO while claiming to stay "reasonably fast". The gimmick
involved is apparently a particularly smart implementation of
trampolining. Read more about it [here][2]. I have a hunch that this
is a no-go for Clojure (partly because Clojure tends to insist on
staying close to the platform -- which has significant benefits -- and
partly because I'm not sure if this kind of thing wouldn't disagree
with Clojure's extremely dynamic nature... I haven't thought this
through that well, though, so maybe this is nonsense). At any rate, it
is interesting.
Sincerely,
Michał
[1] git://github.com/krestenkrab/erjang
[2] http://wiki.github.com/krestenkrab/erjang/how-erjang-compiles-tail-recursion
I have never done extensive benchmarking of clojure, but given the
frequent mentions of use of '-server' in order to achieve specific
performance goals, I get the impression clojure (i.e. Rich) definitely
wants to take advantage of all the optimizations the JIT can offer now
and in the future. Trampoline-based TCO would, as far as I can tell,
always defeat the JIT's notion of a call site - unless the JIT is made
to understand the trampoline (but then are we getting close to full
TCO support anyway? I dunno, I'm definitely not an expert on this
topic...). So, I would expect that those cases which are aggressively
optimized by JIT:ing, such as eliminating method lookups by inline
caching in light loops, would suffer potentially very extreme
performance impacts which aren't fixed by just avoiding allocation as
is mentioned in the erjang wiki page. Or is this over-stating the
problem?
--
/ Peter Schuller
When speaking about general TCO, we are not just talking about
On Aug 3, 2:19 am, Daniel Kersten <dkers...@gmail.com> wrote:
> Can one not detect that a recursive call is a tail call and then transform
> the AST so that its iterative instead - ie, not use the stack besides for
> initial setup of local variables (which then get reused in each recursive
> tail-call). Isn't this how its done in native compiled languages with TCO?
> How is this different from generating bytecode for iterative loops in
> imperative languages, or from what recur does? Alternatively, why can't the
> tail call be detected and converted into recur? I'm guessing that the
> problem is detecting tal calls - but why; speed of dynamic compilation?
> Something else?
>
> Obviously I'm missing something fundamental here - can somebody explain to
> me what it is?
>
recursive self-calls, but also tail calls to other functions. Full TCO
in the latter case is not possible on the JVM at present whilst
preserving Java calling conventions (i.e without interpreting or
inserting a trampoline etc).
While making self tail-calls into jumps would be easy (after all,
that's what recur does), doing so implicitly would create the wrong
expectations for those coming from, e.g. Scheme, which has full TCO.
So, instead we have an explicit recur construct.
Essentially it boils down to the difference between a mere
optimization and a semantic promise. Until I can make it a promise, I'd rather not have partial TCO.
Some people even prefer 'recur' to the redundant restatement of the
function name. In addition, recur can enforce tail-call position.
Rich
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
Some people even prefer 'recur' to the redundant restatement of the
function name. In addition, recur can enforce tail-call position.
Rich