hubFS: THE place for F#

So I must admit I have been completely smitten with F# since I decided to stop trying to get C# 2.0 to do my functional bidding and move over to a language that was built to do this type of stuff from the get go. That said I am also inlove with lazy evaluation in haskell and understand why the creators of F# -- in doing such a great job with the language -- decided to make laziness optional, via the lazy keyword. So I decided to see how far I could get with the lazy keyword before F# screams uncle. My first project in this endeavor is to build a lazy Binary Search Tree.


type BSTree =
 |Empty
 |Leaf of int
 |Node of BSTree Lazy * int * BSTree Lazy
 
let rec bstree_add tree n =
 match tree with
 |Empty -> Leaf(n)
 |Leaf(x) -> if n < x then
                   Node(lazy(Leaf(x)),x,lazy(Empty))
                  else
                   Node(lazy(Empty),x,lazy(Leaf(x)))
 |Node(L,x,R) -> if n < x then
                          Node(lazy(bstree_add (L.Force()) n), x, R)
                         else
                          Node(L, x, lazy(bstree_add (R.Force()) n))



I have the basics of what would be needed worked out and after stairing at my white board for a few minutes I wondered what would happen to the function stack with the above definition if I looped through and built up a lazy BSTree from the numbers 1 ... 1000.

Technically the bstree_add function is not tail recursive but the recursive call is set to be lazily evaluated. Would I still get a stack overflow if I tried to build a BSTree from the stated definition with 100000 sorted numbers? If not, why?

I am rather conflicted over this question because I beleive the compiler creates a closure around the lazy (expr) which to my limited understanding means the stack frame is still left in place, even though a value is returned immediately.

Hi,
First off, I believe your bstree_add is NOT tail recursive, regardless of laziness. Consider your bstree_add with laziness removed:

let rec bstree_add tree n = match tree with
 ...
| Node(L,x,R) -> ... Node(L, x, (bstree_add ...)) // HERE

In the HERE line you do not immediately return a result of a recursive call from bstree_add, but use it to create a new Node object. This means that the stack frame should still be around after the return from the recursive call (bstree_add (R.Force()) n).

>compiler creates a closure around the lazy (expr) which to my limited understanding means the stack frame
> is still left in place, even though a value is returned immediately.

I think you are rather confused here. Compare the following two functions (I distill lazy to closures here):

let f x = g x + x
let f' x = (fun () -> g x + x)

To evaluate f <something>, you need to call actually call g, get its value and then add x to it. To do that, you need to keep stack frame from f on stack while you call g to be able to do the addition.
OTOH, when f' <something> is evaluated, no actual call to g is taking place. All that happens is that a closure is created in heap that contains a value of x (and an entry point for code evaluating g x + x).

One way to see this is f' is a version of f that allocates its stack on heap.

Now, lazy expr is essentially Lazy.create (fun () -> expr). So returning to your lazy bstree_add: it is NOT tail recursive, but it essentially evaluates in O(1) stack space. When you wrap up your recursive calls in 'lazy ...' you create a closure, and in doing so, allocate bstree_add's stack on heap.

Hope this helps,
Friendly,
Dmitry

    Yes it does. I appologize for seeming confused I was juggling a few things at the time I authored that post. However, when I said the bstree_Add was technically tail recursive I was using the term VERY loosely. What I meat was the resulting closure created by lazy(expr) would lead to the function operating in O(1) space(like you had said).

Your answer does force me to ask the following question. Does the compiled/jitted code reuse the space on the heap created by the closure a function like my bstree_add creates? Or does the next recursive call create a new closure on the heap ad leave the old one to be garbage collected?

> Does the compiled/jitted code reuse the space on the heap created by the closure a function like my bstree_add creates? Or does the next recursive call create a new closure on the heap ad leave the old one to be garbage collected?

It creates a new closure, leaving the old one to be garbage collected (closures in F# are essentialy immutable instances of inheritors of FastFunc base class)
Actually creating a closure (= allocating a block in Gen0) is fairly cheap (on par with stack allocation actually).
As a matter of fact, in generational GC, allocating a new object may even be cheaper that modifying an old object - if the modification adds a "wrong way" inter-generational  reference.

Hope this helps,
Friendly,
Dmitry

The original code is interesting - I think it's a very good piece of code for a first venture into F# functional coding.

The question you ask is also very interesting. Avoiding stack overflows when you consume the tree looks like it might require the use of continuations. Some of this is covered in Expert F# chapter 8.

However, it won't be so common for trees to get enomously deep if you keep them balanced.

One fun and helpful reference point in this domain is Wadler's classic on adding laziness to a strict language: http://citeseer.ist.psu.edu/102172.html

Kind regards

don