Tail call optimization?

[tor]

Reading http://gdm9000.wordpress.com/2012/05/05/julia/ I get the impression that Julia supports tail call optimization. Does it? (tests suggests otherwise. f(n) = f(n+1) smashes the stack). Can it be made to? Is this a planned feature?

BTW, after a couple of weeks fooling around with Julia, I'm starting to think this language is the overall best language I've ever tried. Honestly!

[Jeffrey Sarnoff]

+1

[Jeff Bezanson]

Thank you for the very nice compliment!

Currently we do not do tail call optimization. We could with some
work, but I find it to be a mixed bag. Some tail calls can be
converted to jumps as a performance optimization, and I would like to
do some of that eventually. But in general, a constant-space tail call
can actually be slower since an extra stack adjustment might be
necessary.

The single biggest reason for TCO is space complexity. In order to
rely on constant-space tail calls, you have to do the optimization
everywhere. In Julia, explicit iteration is idiomatic, so this is not
terribly necessary. So we will probably not go all the way to
scheme-style tail call semantics.

[John Cowan]

On Tue, Jul 3, 2012 at 9:05 PM, Jeff Bezanson <jeff.b...@gmail.com> wrote:

> The single biggest reason for TCO is space complexity. In order to
> rely on constant-space tail calls, you have to do the optimization
> everywhere.

I think that when you rewrite the Julia parser in Julia, you'll find
that you want TCO to for writing the necessary state machines.
However, it's true that TCO in LLVM-based systems is dependent on
which CPU you are using; historically, at least, it worked only on x86
and x86_64. So it is an optimization rather than Scheme-style "proper
tail recursion" (which is a guarantee that programs and programmers
can depend on).

--
GMail doesn't have rotating .sigs, but you can see mine at
http://www.ccil.org/~cowan/signatures

[Tor Gausen]

Jeff Bezanson

> Thank you for the very nice compliment!

No, thanks to YOU guys for this awesome language!

John Cowan

> So it is an optimization rather than Scheme-style "proper
> tail recursion" (which is a guarantee that programs and programmers
> can depend on).

What I like about TCO is that it expands one's expressive power. A lot of Haskell code looks so neat simply beacause it handles linear time problems recursively. I still have a faint hope this will come to Julia some day (maybe together with that sweet Haskell style pattern matching!), but after reading a bit here and there, I realize It can be quite tricky to implement. It has no haste of course.

[Toivo Henningsson]

On Thursday, July 5, 2012 10:41:36 PM UTC+2, tor wrote:

What I like about TCO is that it expands one's expressive power. A lot of Haskell code looks so neat simply beacause it handles linear time problems recursively. I still have a faint hope this will come to Julia some day (maybe together with that sweet Haskell style pattern matching!), but after reading a bit here and there, I realize It can be quite tricky to implement. It has no haste of course.

I'm currently working on method dispatch using pattern matching for julia, as a generalization of julia's multiple dispatch.
Here's the project page and the discussion we had here on the list.

Since the first release, I've been working on a major overhaul of the basic pattern matching machinery, not through it yet :)
It should hopefully be more consistent, give more expressive power, and allow to generate better code.

My vision right now is:
 * An underlying pattern matching framework that can
   - parse and print patterns
   - generate matching code from a pattern/a collection of patterns (to find the most specific match)
   - unify patterns (form the pattern p that matches those values that match both p1 and p2)
   - compare patterns to see whether one is more general than another
 * A few useful macros to make the machinery available
   - @pattern function
   - @ifmatch let?
   - @case (a la Haskell)?
   - others?

A few planned features that are not on the project page yet:
 * Unification in pattern expressions: the pattern p~q matches x if both patterns p and q do
 * Matching on circularly linked data structures:
   {1,x} matches any 2-length vector with first element 1,
   x~{1,x} matches only such vectors where the second element refers to the vector itself.
 * Compatibility with EGAL (see also this discussion) which will hopefully make its way into julia eventually.
 * Guard conditions in the form of e g boolean expressions.

Please note one major difference from Haskell: dispatch will not choose the first matching pattern, but the most specific one (just as with multiple dispatch)

I don't have any experience with Haskell (just read up a bit on its pattern matching) or much experience with functional programming in general. Any feedback on my ideas is appreciated. (I also want to thank everyone who gave feedback the last round!)

 / Toivo

 

[Jeffrey Sarnoff]

alright!

[tor]

>> * Compatibility with EGAL...

Interesting read!  (I wrote more on the patterns thread).

[Jeff Bezanson]

Our is() function now implements EGAL (and uid() is a corresponding
hash function).

Henry Baker's papers are great. IMO stuff anybody implementing dynamic
languages should be reading.

[Toivo Henningsson]

On Monday, July 9, 2012 10:02:43 PM UTC+2, Jeff Bezanson wrote:

Our is() function now implements EGAL (and uid() is a corresponding
hash function).

Great! But I guess immutable composite types are still some way away?

Right now I've defined my own egal function so that types that are intended as immutable can supply the expected behavior. (For my own internal use.) I know this is not so clean, but it will have to do until immutable composites arrive.

[Pierre-Yves Gérardy]

Doing some grave digging here, I'd like to chime in on this topic. 

Lua does TCO, and tail calls in LuaJIT are exactly as fast as low level loops (see below for the sample code). This may be related to the tracing nature of LuaJIT, and may not be applicable to Julia.

This:

    local function _while (c,f)

        if c() and not f() then -- return true in the function body means break.

            return _while(c,f)

        end

    end

    local a=1

    _while (function()return  a < 10000000  end, function()

        a = a + 1

    end)

is as fast as this:

    local a=1 

    while a < 10000000 do a = a + 1 end

In Lua TCO is only triggered if the return keyword is used (note that Lua doesn't have implicit returns). You could use a similar approach to determine what to optimize away.

-- Pierre-Yves

[Piotr X]

Hi,

sorry for bringing up this old thread.

Is there any update on a possible TCO implementation in Julia-lang?

Regards,

  Piotr

[Jeff Bezanson]

No, no update. It's not a high priority, but eventually we will
probably do some of the optimizations, but not the semantic guarantee.