Hi Leo,

sorry for the delayed answer. I was looking to something smart to say over this topic, but nothing came :) Indeed, I don't have tested yet patterns like expression template to make any pertinent remark there.

 you should probably also set `TAILCALLS` to -1
Thx for pointing this out.

>This also means that unconditionally inlining recursive functions can send the compiler into an infinite loop.

For C++ (the only interpreter I know a little), this is left under the user responsibility. When such infinite loop occurs, then the user payback its freedom spending a lot of time to blindly understand why its interpreter rose an exception. I don't know whether it is a good idea or not. 

This is conceptually simpler, but would bloat the syntax tree and mostly (?) not help much. 
See remark above.

In a first phase, having inlined version of fn:fold-left (maybe naming it as hof:fold-left would be safer ?) should be enough, and safer, since you should know in advance the call depth. Shall (INLINE = ?) control the depth call ?

I did not have a look to the code yet, but I was wondering how can you detect recursive calls ? The self recursive case seems easy to detect, but if I glue two functions together, it seems trickier.

Cheers

Jean-Marc


2013/11/24 Leo Wörteler <lw@basex.org>
Jean-Marc,

Am 23.11.2013 17:52, schrieb jean-marc Mercier:

A drawback is  that the stack trace is inefficient, hardening the debugging. Thus it is better to set INLINE = 0 in dev phase.

yes; you should probably also set `TAILCALLS` to -1 if you want the stack trace to always be accurate. As BaseX performs tail-call optimization [1], the stack will otherwise never contain more than a fixed number (currently 256) of tail-call frames.


Could you be kind enough to point me out the link to your code at Basex repository ?

Sure, function inlining is triggered in StaticFuncCall [2] and DynFuncCall [3].


Motivation : I would like to try evaluating whether inlining recursive
functions is possible or not. You are welcome to suggestions !

The hard part about inlining recursive functions is figuring out when to stop. As they have a call to themselves in the function body, each time you inline them at least one new call is inserted. This also means that unconditionally inlining recursive functions can send the compiler into an infinite loop.

Inlining is indeed possible for all functions for which we can guarantee that the number of replacements will be finite. I'm currently implementing this for `fn:fold-left`, `fn:fold-right` and `fn:for-each` (basically loop unrolling) when the sequence is short and known at compile time. It would definitely be possible to implement this for user-defined functions, too, but we'd need to identify (a subset of) the correct ones.

Another option would be to always inline recursive functions up to a fixed depth. This is conceptually simpler, but would bloat the syntax tree and mostly (?) not help much.

What are your ideas?
  Leo

[1] http://en.wikipedia.org/wiki/Tail_call
[2] https://github.com/BaseXdb/basex/blob/next/basex-core/src/main/java/org/basex/query/func/StaticFuncCall.java#L71
[3] https://github.com/BaseXdb/basex/blob/next/basex-core/src/main/java/org/basex/query/func/DynFuncCall.java#L57