recursion elimination?
Paul Rubin
recursion? I don't mean tail recursion elimination, I mean converting
non-tail calls into tail recursion or iteration:
fac 0 = 1
fac n = n * fac (n-1)
is not tail recursive but translates traditionally:
fac' 0 acc = acc
fac' n acc = fac' (n-1) (n*acc)
fac n = fac' n 1
The recursive version is a lot easier to write and so I wonder why
compilers don't attempt this optimization.
Chung-chieh Shan
Well, your fac' actually performs the multiplications in a different
order as your fac, so the optimization would assume the associativity of
multiplication, for one thing (Wand JACM 27(1):164-180). But it's not
hard to write a fac'' that's both tail-recursive and that performs the
multiplications in the same order as fac does. To convert fac to fac'',
the compiler would need to notice that defunctionalizing the implicit
continuation in fac yields a Peano-unary natural number, which can be
represented in binary instead (Danvy DSc dissertation).
--
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
No arms? - no cookies!
Jon Harrop
Because it isn't an optimization for one thing. One of the reasons the OCaml
stdlib has lots of non-tail recursive functions is that they are faster for
shallow recursions.
So this is a trade-off rather than an optimization and compilers currently
choose the simpler solution.
From a practical point of view, a compiler could only spot a limited number
of cases where that transformation can be made and you must often guarantee
that it has been done. So you would still write in explicitly tail
recursive style most of the time anyway and the only functions that got
transformed automatically would be, by definition, the unimportant ones.
--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?usenet
dbe...@eecs.wsu.edu
> ...
> compilers don't attempt this optimization.
I am under the impression that several compilers do. In particular, a
continuation-passing style semantic analysis will (I am led to
understand) auto-convert to tail recursion at least frequently. Then
the newer FLINT based analysis produces fairly decent code.
I am not familiar with what MLton does, but the authors claim it
produces the fastest code of any of the compilers for Standard ML.
(Still my favorite language for most purposes...)
Christopher Diggins
> Paul Rubin <http://phr...@nospam.invalid> wrote in article <7x6427x56g.fsf...@ruckus.brouhaha.com> in comp.lang.functional:
>
> > Is there a reason compilers don't make greater efforts to eliminate
> > recursion? I don't mean tail recursion elimination, I mean converting
> > non-tail calls into tail recursion or iteration:
>
> > fac 0 = 1
> > fac n = n * fac (n-1)
>
> > is not tail recursive but translates traditionally:
>
> > fac' 0 acc = acc
> > fac' n acc = fac' (n-1) (n*acc)
> > fac n = fac' n 1
>
> > The recursive version is a lot easier to write and so I wonder why
> > compilers don't attempt this optimization.
>
> Well, your fac' actually performs the multiplications in a different
> order as your fac, so the optimization would assume the associativity of
> multiplication, for one thing (Wand JACM 27(1):164-180).
Are you aware of any languages (or implementations) that allow us to
state which operations are associative? If we were to provide
optimization hints that say whether a function is associative, I would
expect that to be quite helpful for compiler optimization. Do you
agree?
> But it's not
> hard to write a fac'' that's both tail-recursive and that performs the
> multiplications in the same order as fac does.
If I am not mistaken, a tail-call version that maintains the order of
multiplications would require the use of the sucessor function (+ 1)
instead of the predecessor function (- 1), correct?
> To convert fac to fac'',
> the compiler would need to notice that defunctionalizing the implicit
> continuation in fac yields a Peano-unary natural number, which can be
> represented in binary instead (Danvy DSc dissertation)
Is this recognition generally considered an easy or hard problem for a
compiler?
For those interested a url to Danvy's dissertation is:
http://www.daimi.au.dk/~danvy/DSc/00_dissertation.pdf
Unfortunately I couldn't find the Wand paper outside of the ACM
archives:
http://doi.acm.org/10.1145/322169.322183
>
> --
> Edit this signature athttp://www.digitas.harvard.edu/cgi-bin/ken/sig
> No arms? - no cookies!
Christopher Diggins
http://www.cdiggins.com
Chung-chieh Shan
> Are you aware of any languages (or implementations) that allow us to
> state which operations are associative? If we were to provide
> optimization hints that say whether a function is associative, I would
> expect that to be quite helpful for compiler optimization. Do you
> agree?
Well, I'm not aware of any languages that let the programmer say which
operations are associative *for the purpose of optimization*. It is
my impression that it is still the domain of manual creativity, to
optimize a representation in a way that requires induction to prove
correctness...
> If I am not mistaken, a tail-call version that maintains the order of
> multiplications would require the use of the sucessor function (+ 1)
> instead of the predecessor function (- 1), correct?
Yeah.
> > To convert fac to fac'',
> > the compiler would need to notice that defunctionalizing the implicit
> > continuation in fac yields a Peano-unary natural number, which can be
> > represented in binary instead (Danvy DSc dissertation)
>
> Is this recognition generally considered an easy or hard problem for a
> compiler?
It can't be hard to notice that an algebraic data type is essentially
the same as "data Nat = Zero | Succ Nat", but I'm not aware of
any compiler (MLton?) that uses this information to improve the
representation--- perhaps the idea needs to be generalized to be worth
the implementation effort?
--
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
This is completely pointless (in fact, there's only one comma)
Jon Harrop
> Are you aware of any languages (or implementations) that allow us to
> state which operations are associative?
Mathematica.
Jon Harrop
> On Sep 18, 10:19 am, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
>> ...
>> compilers don't attempt this optimization.
>
> I am under the impression that several compilers do. In particular, a
> continuation-passing style semantic analysis will (I am led to
> understand) auto-convert to tail recursion at least frequently. Then
> the newer FLINT based analysis produces fairly decent code.
I think that is likely to just grow a stack of closures on the heap. So it
will reduce system stack consumption to O(1) but total space consumption is
still O(n) rather than O(1).
> I am not familiar with what MLton does, but the authors claim it
> produces the fastest code of any of the compilers for Standard ML.
> (Still my favorite language for most purposes...)
In general, I think that is a fair assertion. SML/NJ can produce
competitively performant numerical code for flat arrays on certain
architectures though.
ross...@ps.uni-sb.de
>
> > I am not familiar with what MLton does, but the authors claim it
> > produces the fastest code of any of the compilers for Standard ML.
> > (Still my favorite language for most purposes...)
>
> In general, I think that is a fair assertion. SML/NJ can produce
> competitively performant numerical code for flat arrays on certain
> architectures though.
I have been quite impressed by the performance of the latest Poly/ML
recently. At least for symbolic computations it seems to be almost on
par with MLton, while compile times are lightning fast. I would be
interested in knowing how it fares for numeric code.
- Andreas
Jon Harrop
Wow, that's impressive. Looks like it also support 64-bit. I'll take a
look...
dbe...@eecs.wsu.edu
> I think that is likely to just grow a stack of closures on the heap. So it
> will reduce system stack consumption to O(1) but total space consumption is
> still O(n) rather than O(1).
> Dr Jon D Harrop, Flying Frog Consultancy
> OCaml for Scientistshttp://www.ffconsultancy.com/products/ocaml_for_scientists/?usenet
SML/NJ has no stack. By direct experimentation, space consumption for
recursive functions which are morally tail-recursive, like
'factorial', is O(1) provided there is no explicit exception handler.