Can lazy-list (and/or Elm) support tail call recursion?

[naddeoa]

Hey!

I've been using lazy-list a bunch and it's been great so far, thanks for the hard work!

I'm running into some stack overflow issues:

overflow : Int -> List Int
overflow n =
    Lazy.List.numbers
        |> Lazy.List.takeWhile (\number -> number < n)
        |> Lazy.List.toList

Calling it in a view for example:

((overflow 100000)
    |> toString
    |> Html.text
)

I've read online that Elm actually does tail call optimizations. I can see from my stack traces that my program dies in the LazyList code. Is it possible for the LazyList library to take advantage of tail call optimizations if Elm does in fact support it?

[mgold]

Honestly... I have no idea.

[naddeoa]

Lol OK, well, if I dig into it and discover that it's possible would you be open to accepting a pull request?

…

On Fri, Dec 16, 2016, 8:15 PM Max Goldstein ***@***.***> wrote: Honestly... I have no idea. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#5 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABLTLQVE-IiCEivjoK188Ud5WNOylFqwks5rI2HRgaJpZM4LPR9h> .

[mgold]

In theory, yes, absolutely!

In practice, please be careful not to degrade correctness, the stable API, or performance.

[naddeoa]

Who would do such a thing?? Cool I'll see what I can do. I would probably do a POC first on one function to get some feedback from you before going all in.

…

On Fri, Dec 16, 2016, 8:36 PM Max Goldstein ***@***.***> wrote: In theory, yes, absolutely! In practice, please be careful not to degrade correctness, the stable API, or performance. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#5 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABLTLckdjxNy1fnVudY4PlpkyM7PA9yJks5rI2bZgaJpZM4LPR9h> .

[naddeoa]

Well, I can confirm that the compiler does support tail call recursion optimization. Given this elm code

rec : Int -> Int
rec n =
    case n of
        0 ->
            0

        _ ->
            rec <| n - 1

It generates this Javascript

var _user$project$Main$rec = function (n) {
	rec:
	while (true) {
		var _p0 = n;
		if (_p0 === 0) {
			return 0;
		} else {
			var _v1 = n - 1;
			n = _v1;
			continue rec;
		}
	}
};

Now, onto whatever is stopping lazy-list from being optimized. From my first look, it seems like each recursive call was wrapped in a lazy, which could explain the forced recursion.

[naddeoa]

#6

First attempt here. It isn't ready to be merged yet though, I wanted to get your feedback before I went any further. I describe everything in the commit message, but here is the TLDR

• Should I explicitly list all exported modules to stop the helper function I wrote from being exported?
• Is there a better way of handling the accumulation? toList is still O(n), but that List.reverse call seems avoidable.

[naddeoa]

As I mentioned in the pull request, the changes needed are more substantial than I thought. I ended up writing something else instead: https://github.com/naddeoa/stream

[GordonBGood]

@naddeoa, of course your opening example overflows the stack and it has nothing to do with TCO: when it evaluates toList it forces the evaluation of the whole lazy list plus creates a conventional non-lazy list 100,000 elements long.

Come now, you won't really want to put 100,000 numbers up on a web page would you (millions of characters)? And even if you did, there must be dozens of ways to generate them directly rather than the convolution of first lazy list, then conventional list.

The whole point of a lazy list is that you don't need to have the whole list in memory at one time; once you have converted it to a huge non-lazy structure, that is no longer true.

If you really did want to view 100,000 numbers in a web page, the way one would do it using a lazy list is to display (say) a hundred numbers at a time, and provide some controls to advance through the list and reset to the beginning (a lazy list - like a conventional list - does not have reversing capability unless you memorize it and that would defeat the purpose).

[naddeoa]

@GordonBGood I was able to overflow the library with 700 elements as well, and I'm sure I could have overflowed with less. The example I gave was contrived, sure. If you don't have any need for lazy lists with hundreds of items then feel free to not look for one. Also, feel free to contact me in slack or somewhere else if you'd like to talk about lazy list designs. This issue isn't for that.

[GordonBGood]

@naddeoa, ah, I see it: the problem comes about right from cons on which building an infinite lazy list depends; the tail list is not in tail call position because it is wrapped in the thunk function that is passed to the lazy function to form the outer Lazy wrapper; This formulation builds stack when called recursively as you noted in your since-closed PR.

To answer your question, this has nothing to do with Tail Call Optimization (TCO), as the above cannot use it, and if fixed TCO is not needed because stack will not be build due to injection of deferred execution.

Because of this current problem, repeat doesn't really work (as noted in the source comments/docs) as it can't build a lazy infinite list and that problem is the clue as to what is happening with any recursive building of lazy lists.

It's a pity, as the module has a great API.

It seems you should have left this issue open.

The problem is fixable, but one will have to inject deferred execution for the tail is in creating an extra level of force/lazy calls for every function such as cons that can create infinite lists, something like using Lazy.andThen, but that function has an even higher overhead. Using this technique, cons would be re-defined as follows:

cons : a -> LazyList a -> LazyList a -- same type signature
cons v list =
  lazy <|
    \() ->
      Cons v <| lazy <| \() -> force list

Notice that the last line breaks the recursive loop by injecting the creation of a new Lazy and thus does not build stack.

I am replying here rather than elsewhere because it does apply to this current repo and what it's problem is. Can you re-open issues you've closed yourself?
The advantage of this method is that the API is not broken (although external use of the LazyListView(..) will have to take these same measures for long lists).

However, the disadvantage is that performance will suffer due to the extra embedded function calls.

To fix the problem without a performance cost, one has to start from the basics of the definition of the LazyList type without the use of LazyListView as follows:

type LazyList a
  = Empty
  | Cons a (Lazy (LazyList a))

Now the infinite loop is broken by definition rather than by convention by defining the formation of the Lazy internal to the LazyList rather than wrapping it.

The performance won't be affected for the second method because there is still just one Lazy used per LazyList node.

However, the API will be different as to the internals of LazyList now having a LazyList(..) exposed and there being no LazyListView(..) and that now one will have to pass thunk functions as tail forming arguments rather than passing the tail LazyList itself directly.

Now cons and other functions that can be called recursively would be written as follows with a thunk function as an argument:

cons : a -> (() -> LazyList a) -> LazyList a -- changed type signature
cons v listfunc =
  Cons v <|
    lazy <| \() -> listfunc

Note that now the single Lazy injection is all there is so this both can not form an infinite loop when used recursively, nor does it require the double levels of lazy/force plus the outer Lazy wrapper. Thus, the performance will be much better than fix number one.

This is about as good as it gets implementing LazyList in a strict language. We can also retain almost all of the API changed only as noted with the passing of tail thunk functions rather than LazyList tail types themselves.

As a side issue, exposing numbers as a constant wasn't a very good idea anyway as being a constant it will prevent the head of the numbers list from ever being garbage collected: using 100,000 values from it (even if the other stack building problem is fixed) as you attempt to do here will consume millions of bytes worth of memory at least as bad as if one used a non-lazy list to do this directly. numbers should be written as a function as follows (using option number 2 above):

With iterate written as follows (with an inner "worker" function so that the invariant function doesn't have to be passed):

iterate : (a -> LazyList a) -> a -> LazyList a
iterate f v =
  let iteri v =
    Cons v <| lazy <| \() -> iteri f v
  in iteri v

then

numbers : () -> LasyList Int
numbers() = iterate (+) 0

As a function numbers() doesn't hold onto the head of the list and thus the resulting list can be garbage collected from its head if used correctly just as an argument to other functions or at most as a local let constant.

Fixing this would have changed the API anyway.

Good catch, and its a shame it isn't fixed yet; may have to do a PR myself, but as you say it is going to be extensive and the maintainer might need to be convinced it is necessary.

I note that your PR wasn't the right approach as it was much too complex and you closed it yourself; I believe that method number two is the right approach as it is relatively simple although it will still change many of the API functions.

[naddeoa]

@GordonBGood Thanks for digging into the issue. I could re-open the issue though it doesn't feel quite right to me. It's basically going to be a new library (even if the API is the same) when its done. That will be quite the PR.

Well, @mgold, I'll leave this open again since the issue really does exist and I only closed it because I worked around the issue. I'm not sure how you feel about having issues linger, but at the very least it could be an opportunity for someone to contribute to the library. If you decide to re-close it then no hard feelings.

[GordonBGood]

@naddeoa, I didn't want to open a new issue as what you've found applies. Yes, this will be a major departure from the current library and will necessitate a major version bump, but the great thing about github managed versions is that both versions can exist so nothing old is broken and the old version can still have updates and fixes if desired. As to the complexity of the PR, yes, many functions will change but in a relatively minor way, and the whole library isn't that big.

It turns out that similar libraries in other languages have the same problem; for instance the PureScript List.Lazy library has these same stack overflows when used for self-created-by-recursion infinite lazy lists. The problem is that the authors try to do in a strict language what is done in a non-strict language (usually Haskell), and that isn't possible in this way without making absolutely every element non-strict, but without Haskell's strictness analyzer and optimizations that smooth away the resulting overheads, the resulting code would not be performant (method 1). Elm isn't going to get that level of optimization anytime soon, likely never.

@mgold, I could immediately open a PR with everything implemented as per method two, but wanted to get your thoughts in the issue first before doing that. I am loathe to start another competing repository as this one says it all - lazy-list is exactly what it is, as well as what it will be when changed to method two but the new implementation will support lazy infinite lists of all sorts of types. For instance, repeat will create a true infinite lazy list and not need to immediately be throttled with a take or some such to prevent it from immediately overflowing the stack.

Note that my pending PR elm-lang/lazy#2, which is a dependency of this repository, will make lazy lists work up to about six times faster on browsers such as current Chrome, if accepted. It has the added advantage of detecting recursive loops such as these that are wrapped in Lazy, and throwing an early exception rather than blowing the stack.

[mgold]

@GordonBGood As I commented on the Lazy PR, your approach is flawed and you're unlikely to gain a speedup that way. That said, I'm fairly comfortable turning you loose within the safety of Elm. You're going to need to bring good evidence, but I'm willing to do a major version bump for even a modest speedup or raised stack ceiling. Whether that's tail calls, garbage collectable values, smaller types (I never liked LazyListView anyway), it doesn't matter to me as long as you don't write JavaScript.

There's the slight problem that good evidence will be tricky to create. This library is a dependency of elm-test so you can't use it to do testing. Therefore if you see the need for unit tests, you'll probably have to hack together an HTML page that reports them. There's not a good story for benchmarking in Elm yet, but you can see a working example here. Demonstrating the largest list without blowing the stack should be relatively easy.

@naddeoa I looked briefly at your stream library. It's a neat idea and definitely different enough from this one to coexist. If you can help Gordon with the performance, please do so.