[LLVMdev] [Segmented Stacks] Week 1

[Brian Hurt]

Sorry for the delay in responding.

On Mon, 13 Jun 2011, Rafael Avila de Espindola wrote:

> On 11-06-02 07:47 PM, Peter Lawrence wrote:
>> Guys,
>> regarding alloca.
>>
>> not only are exceptions a problem here, but just plain old "longjmp".
>
> Yes,
> On IRC Sanjoy pointed out that it should be possible to handle this by
> changing longjmp. I am not sure it can be done in general. The alloca
> might have been called a dynamic number of times for example.
>
> In fact, now that I think of it, the presence of longjmp pretty much
> forces a model where stacklets are not deallocated on return, just
> reused if stack grows again.

Perhaps only longjmp/exception throws need to not free stacklets- returns 
still do.

Segmented stacks are exciting to me, but only if the stacklets can be 
freed.  Here's why: if segmented stacks allow for "infinite" stacks, tail 
call optimization becomes a lot less important in functional languages- 
still useful, but not live or die.

For example, the natural way to implement the map function over lists is:
let rec map f lst =
     match lst with
     | x :: xs -> (f x) :: (map f xs)
     | [] -> []
;;

Interestingly enough, this is also the fastest implementation of map.  But 
it's not tail recursive- which means if you pass in a list long enough, 
you run out stack space and your program blows up.  So you end up writing 
a much more complicated version which is also slower, but which is tail 
recursive.

I'd love to have virtual infinite stacks- stacks which expanded as needed, 
but got freed when no longer needed.  That means being tail recursive goes 
back to being nice, not necessary.

Just my $0.02.

Brian