Explicit TCE

[Dmitry Olshansky]

On 12-Oct-12 22:17, Tyler Jameson Little wrote:
>> No idea what you are talking about.
>
> I'm not sure which part wasn't clear, so I'll try to explain myself.
> Please don't feel offended if I clarify things you already understand.
>


> An optimizable tail call must simply be a function call. The current
> stack frame would be replaced with the new function, so anything more
> complex than a simple function call would require some stack from the
> preceding function to stick around in the new function, thus requiring
> the old stack to stick around.
>
Yup.

> For example, te following is not optimizable the old stack (the one with
> 3) needs to be maintained until foo() returns, which is not TCE.
>
> return foo() * 3
>
>
> Since the old stack won't be around anymore, that leaves us with in a
> sticky situation with regard to scope():
>
> http://dlang.org/statement.html#ScopeGuardStatement
>
> If the current stack is going to be replaced with data from another
> function call, the behavior of scope() is undefined. The scope that
> scope() was in has now been repurpose, but the scope is still kind of
> there. If scope() is allowed, they must be executed just before the tail
> call, otherwise it will be overwritten (or it has to stick around until
> the actual stack frame is cleared.

  Consider:
>
> void a() {
>    become b();
> }
>
> void b() {
>    // when does this get called?
>    scope(exit) writeln("exited");
>    become a();
> }
>
> If we allow scope(), then the line should be written before the call to
> a(). If we don't, then this is a compile time error. I like disallowing
> it personally, because if the scope(exit) call frees some memory that is
> passed to a, the programmer may think that it will be called after a
> exits, which may not be the case.
>
I think it should be disallowed. That along with destructors.

> void a(void* arr) {
>    // do something with arr
>    become b();
> }
>
> void b() {
>    void* arr = malloc(sizeof(float) * 16);
>    scope(exit) free(arr);
>    become a(arr);
> }
>
> I just see this as being a problem for those who don't fully understand
> scoping and TCE.


>
> My mention of overhead was just how complicated it would be to
> implement. The general algorithm is (for each become keyword):
>
> * determine max stack size (consider all branches in all recursive
> contexts)
> * allocate stack size for top-level function
> * do normal TCE stuff (use existing stack for new call)

What's wrong with just allocating a new stack _in-place_  of the old?
In other words make 'become' synonym for 'reuse the current stack frame'.
Effectively you still stay in constant space that is maximum of all 
functions being called.

> The stack size should be known at compile time for cases like the one
> above (a calls b, b calls a, infinitely) to avoid infinitely expanding
> stack. A situation like this is a memory optimization, so forcing
> guaranteed stack size puts an upper-bound on memory usage, which is the
> whole point of TCE. If the stack is allowed to grow, there is
> opportunity for stack overflow.

Right.

> My use case for this is a simple compiler, but I'm sure this could be
> applied to other use cases as well.  I'd like to produce code for some
> BNF-style grammar where each LHS is a function. Thus, my state machine
> wouldn't be a huge, unnatural switch statement that reads in the current
> state, but a series of code branches that 'become' other states, like an
> actual state machine.

I see nice staff. My use case is optimizing virtual machine, the one 
inside std.regex primarily.

-- 
Dmitry Olshansky