RE: Depreciation of elm-lang/lazy library


#1

Synopsis: Although I partially agree with Evan that the Lazy library is often misused and unnecessary for many applications, I disagree that it should be completely removed from availability for those who truly need it. I will discuss why I think the reasons for this depreciation aren’t valid and also some applications (at least a few that I can think of quickly) that can’t be implemented efficiently without using this library, as follows:

Given Reasons for Depreciation

The reasons that Evan gives for this depreciation boil down to the following two concise statements:

  1. It is overkill for all the scenarios (he has) seen in Elm.
  2. It allows the creation of cyclic data, significantly complicating Garbage Collection (GC).

Consideration of Reasons for Depreciation

I choose to address point 2 first: Evan further says the following in the library ReadMe.md file:

With laziness you can create a list like ones = 1 :: ones that refers to itself. Without laziness, there is no way to create cyclic data in Elm. That means we can use a naive reference counting approach to collect garbage if we wanted.

I say to this “how does the removal of the Lazy library prevent that definition of cyclic data?”. It is true, with the lazy library we can write things like ones = lazy <| \() -> 1 :: Lazy.force ones which will cause a stack overflow if one actually tries to use it; it may also cause a memory leak if reference counted allocations were used in that every stack element refers to a “Lazy number” structure in the heap; However, not using the Lazy library we can still write the same definition just using deferred execution as ones = \() -> 1 :: ones() with the exact same problems, and in fact every invocation of the (single) ones function causes the creation of a function invocation object or closure if free variables were referenced in the definition; thus, I don’t see that this can possibly be a valid rationale for the removal of the Lazy library: Exactly the same problem persists whether the Lazy library exists or not - in fact it is a version of the “halting problem”.

Evan’s point 2 is thus out of the consideration.

On to address point 1 - whether Lazy is needed or not:

To summarize what Evan said in the ReadMe file, the difference between deferred execution such as \() -> expensiveCalculation a then using a() when one actually needs the value a, and laziness as in lazy <| \() -> expensiveCalculation a then using Lazy.force a when one needs the value, is that when using the first the calculation has to be run every time the value is needed, whereas for the second the calculation is run only the first time the value is needed and a saved result of the calculation is provided thereafter, which we call “memoization”.

It is true that sometimes the deferred results are needed only once, in which case lazy is not needed.

It is a further fact that one can sometimes find other ways of doing memoization as in storage of single values in a memoization type or such as storage of many calculated values in an Array or a Dict; however I will show applications where using Lazy for many values produces a O(n) performance where the use of (immutable) Array or Dict is O(n log n) or slower with a quite high constant execution overhead, so these alternatives aren’t really acceptable.

It is also a fact that the use of Lazy is slower than the simpler deferred execution (even slower because most JavaScript engines don’t handle creating a function from within a function very well, as is necessary for Elm in order for the necessary mutation not to be perceptible from the outside), but my point is that there are applications where one can’t easily implement them efficiently without laziness to the point that the constant execution cost of its use is very much less than the algorithmic cost of not using it.

I would not dispute the removal of the Lazy library if the only use was for single calculations at a time, as I agree that alternate means can be found; however, the class of problems that require a sequence often may require the memoization of the elements of the sequence provided by laziness.

Examples Requiring the Use of Lazy

First, lets define some list/sequence types to be used in the further examples:

For DeferredList executions:

type alias Deferred a = () -> a
type alias DeferredPairElement a = { head : a, tail : DeferredList a }
type DeferredList a = ConsDeferred (Deferred (DeferredPairElement a)) | EmptyDeferredList 

nthDeferredListValue : Int -> DeferredList a -> Just a
nthDeferredListValue n stream =
    case steam of
        EmptyDeferredList -> Nothing
        ConsDeferred thunk ->
            let pair = thunk() in
            if n <= 0 then Just pair.head
            else nthDeferredListValue (n - 1) pair.tail          

For LazyList executions:

-- defined by Lazy...
lazy : (() -> a) -> Lazy a
force : Lazy a -> a -- where the first "thunk" is only executed once..
type alias LazyPairElement a = { head : a, tail : LazyList a }
type LazyList a = ConsLazy (Lazy (LazyPairElement a)) | EmptyLazyList 

nthLazyListValue : Int -> LazyList a -> Just a
nthLazyListValue n stream =
    case steam of
        EmptyLazyList -> Nothing
        ConsLazy thunk ->
            let pair = Lazy.force thunk in
            if n <= 0 then Just pair.head
            else nthLazyListValue (n - 1) pair.tail          

Note how little difference there is between the two.

Now, I might use the following naive implementation of the Fibonacci sequence as a justification for using Lazy:

fibs() =
    let
        fib n =
            if n < 2 then n
            else fib (n - 1) + fib (n - 2)
        fbs n =
            ConsDeferred <| \() ->
                { head = fib n, tail = fbs (n + 1) ]
    in fbs 0

Note that this is a perfectly legitimate use of infinite recursion in that, due to deferral/laziness, the tail calculation is only done when the next value is requested.

The performance of the above absolutely stinks, with seconds required just to calculate the first 35 numbers in the sequence, with the reason obvious in that it is repeatedly back calculating all of the previous values in the sequence for each new value! Simply substituting ConsLazy <| lazy <| ... for ConsDeferred and using the alternate nthLazyListValue instead of nthDeferredListValue to find the nth value results in negligible time to find the 100th value at which point the size already exceeds the number range (but the timing is still valId).

However, that is hardly fair, as the function should really be written as follows:

fibs() =
    let
        fbs first second =
            ConsDeferred <| \() ->
                { head = first, tail = fbs second (first + second) }
    in fbs 0 1

In which case it doesn’t need laziness in order to calculate 100’s of fibonacci numbers in an instant. That was an example of justification of Lazy by an idiot :grinning:.

Following is an example that is not by an idiot, in the case of the sequence of Hamming or Smooth-5 numbers:
Translation of the following Haskell code:

hamming = 1 : foldr u [] [2,3,5] where
        u n s = -- fix (merge s . map (n*) . (1:))
                r where 
                r = merge s (map (n*) (1:r))
 
merge [] b = b
merge a@(x:xs) b@(y:ys) | x < y     = x : merge xs b
                        | otherwise = y : merge a ys

as the following Elm code using DeferredList instead of LazyList:

hammings() =
    let
        merge xs ys =
            case xs of
                EmptyDeferredList -> ys
                ConsDeferred thunkxs ->
                    let pairxs = thunkxs() in
                    case ys of
                        EmptyDeferredList -> xs
                        ConsDeferred thunkys ->
                            ConsDeferred <| \() ->
                                let pairys = thunkys() in
                                if pairxs.head < pairys.head then
                                    { head = pairxs.head, tail = merge pairxs.tail ys }
                                else
                                    { head = pairys.head, tail = merge xs pairys.tail }
    -- does as map ((*) scale) stream, but faster; more specialized
        smult scale stream =
            let
                smlt strm =
                    case strm of
                        Empty -> strm
                        ConsDeferred thunk ->
                            ConsDeferred <| \() ->
                                let pair = thunk() in
                                { head = scale * pair.head, tail = smlt pair.tail }
            in smlt stream
        u n stream =
            let
                dfrstrm() =
                    merge
                        stream
                        (smult n (Cons <| \() -> { head = 1, tail = dfrstrm() } ))
            in dfrstrm()
    in cons 1 (\() -> List.foldl u EmptyDeferredList [ 5, 3, 2 ])

Now, in this case it takes seconds to calculate just the first 1691 hamming numbers (to not overflow the 32-bit number range) using DeferredList, whereas only an instant using LazyList. Although one can do this in other ways not requiring Lazy if only the one value of the nth Hamming number is required, there aren’t better algorithms for Elm in O(n) time if one requires the complete sequence, such as one would use if counting the number of Hamming numbers up to a limit.

Another example requiring memoization in in using the Sieve of Eratosthenes to determine the sequence of prime numbers: the fastest way to do this is to use a page segmented sieve where one must scan across the base primes for each segment page; if one were not to memoize the sequence of base primes, they need to be re-determined for each segment page pass. The code to do this would make this post very long, and it just proves more of the same.

I’m sure we can find other sequences that need laziness if we put our minds to it.

Further Considerations

The old ReadMe file further stated that using laziness is dangerous in that one might create chains of laziness (as often happens accidentally in Haskell) such that the actual calculations don’t get unwrapped until the outer lazy is evaluated; My answer is that Haskell is different in that laziness (or rather non-strictness) is the default for everything unless the programmer manages to hint to the “strictness analyzer” that laziness isn’t necessary, in Elm, OCaml, F#, etc., strictness is the default and one must explicitly add laziness where it is deemed beneficial. Why would a programmer explicitly stack laziness if it were a detriment? Explicitly stacking laziness as in a LazyList (or DeferredList for that matter) is a choice made for a perceived benefit, and also isn’t what was being referenced as in stacked laziness for a single outcome result, which also is impossible without explicitly writing it that way.

Surely the Elm authors don’t want to treat its users as idiots and control what they are able and not able to do using legitimate Elm constructs? Every other functional language has the concept of memoized laziness used especially in the creation and use of LazyList’s, why not Elm when there ARE legitimate uses?

Summary: Due to the above, I propose that the Lazy library not be dropped, but just that the documentation be augmented to better explain, with examples, how not to misuse it and when just simple deferred execution would be a better choice.

If it is felt that the Lazy library is apt to be mishandled by less astute programmers, why not include a very good LazyList implementation in the official (not community) libraries, with that library wrapping the “dangerous” Lazy concept wrapped in such a way as to be less subject to abuse with the warning that DeferredList (which could also be an official library) is more appropriate in many cases for given reasons with good examples?


#2

I am wondering - if reference counting was implemented, could the issue of the overhead in maintaining the storage with DIY memoization be solved?

With reference counting, the runtime can detect when the reference count equals 1. In such a situation, as only 1 copy of a data structure exists, the previous copy can be directly mutated.


#3

If reference counting were implemented and the reference count equalled one, it would mean the (only) reference to the heap object could modify the object and return it as if it were copied on write and I suppose gain some performance thereby, but this couldn’t be used to implement a Lazy to contain either the unevaluated thunk or the calculated value, as then the same wrapped contents would appear to be mutated from a JavaScript function to whatever the contained type of the Lazy.

For single Lazy values, we don’t need to use reference counting, as one could just use the force function to convert a Union type from Unevaluated thunk to Evaluated value, assigning a different binding to the output than the input of the force.

My problem comes about in inability to implement a memoizing lazy list. (possibly infinite) when that is a requirement

However, your comment has given me an idea to check out, let me follow that up and post the results here…


#4

@rupert, my idea only partly worked out: one can apply a memoizing function to an already existing DeferredList so the new generated (lazy) list won’t have to repeat the calculations again, but it can’t be used while generating a DeferredList in the first place if it is recursive more than a simple iteration of a function over immediately preceeding values to get immediately succeeding ones (like in the good version of fibs()), as a race condition will result; therefore, there is no substitute for the Lazy library as the OP States for doing those types of things. I’m working on simpler examples to run on Ellie to demonstrate this.


#5

In this post, I present a short concise series of examples to show why a true memoizing LazyList is necessary for some functional algorithms:

I can’t seem to get the elm-explorations/benchmark library working on Ellie, so I’ve written my own simple benchmark framework to time the operations, as you’ll see in the example.

I ran the tests on my Windows 10 tablet using an Intel Atom i5-Z8350 at 1.92 Gigahertz (single threaded).

I’m going to use an infinite deferred list of numbers as an example since the applications that really need Lazy are quite complex and thus the examples will be a bit synthetic in that there is a way to implement this without requiring memoization so it compares that way to an alternate form which does require memoization. Also, since I’m only dealing with an infinite list, I’m going to not include a terminator EmptyDeferredList to the type in order to keep the examples shorter in not having to deal with nested case ... of in order to de-structure/pattern match on the type.

Thus, all examples use the following definitions for the DeferredList:

type alias Deferred a = () -> a
type alias ElementPair a =  { head : a, tail : DeferredList a }
type DeferredList a = Cons (Deferred (ElementPair a))

To set a baseline of the maximum speed possible with the above structure, I use the deferred sequence of numbers just using a recursive function (as in the fast version of fibs in the OP) to get about 270 CPU cycles per iteration when iterating to 10 million - Try it here:

fasterNumbers : () -> DeferredList Int
fasterNumbers () =
    let
        nmbrs n =
            Cons <| \() -> { head = n, tail = nmbrs (n + 1) }
    in
    nmbrs 1

Notice that if one varies the number of iterations, this is about linear with range (after a warm-up time of a few tests for each).

Now, for the sequence of numbers written to refer to itself, which is a frequently necessary paradigm in writing sequences (although not absolutely necessary here) by just changing the reference in answer() from fasterNumbers() to slowerNumbers() (DON’T FORGET TO SET THE NUMBER OF ITERATIONS DOWN TO 1000 OR SO OR YOU’LL BE WAITING A VERY LONG TIME!!!):

slowerNumbers : () -> DeferredList Int
slowerNumbers () =
    let
        plus1 (Cons thunk) =
            Cons <|
                \() ->
                    let
                        pair =
                            thunk ()
                    in
                    { head = pair.head + 1, tail = plus1 pair.tail }
    in
    Cons <| \() -> { head = 1, tail = plus1 (slowerNumbers ()) }

Note that this uses “safe” recursion in that it re-curses on the head of the previous list, which is known for every successive iteration, but without a memoizing Lazy library to preserve previous values, it has to recalculate all of the sequence back to the initial value (of 1) for every iteration. Thus, the time expended is multiplied by a log function of the current length of the iteration, making it very slow: it takes about 96,000 clock cycles per iteration to 100 and about 210,000 clock cycles per iteration to 1000, and of course will get successively worse with length. This make it impossible to use deferred lists for any significant problem that needs this form of expression (such as the hammings() function in the OP). Even if memoizing were available, this sequence will still be some slower than the other version due to the constant overhead of the memoize function implementation and that of calling it, but it would be worth using as at least the result would have a linear execution time with range.

Therefore, I believe that we do need an implementation of a true memoizing LazyList library available to us, even if it is only in elm-explorations; I have rethought this and realize that we don’t actually need the Lazy library available to “the public” to implement this, and the parts that are needed for LazyList can be wrapped and not exposed in the LazyList library.


#6

I want to share some technical details that it seems were not taken into account in your analysis of the GC reasoning.

Technical Details

As of 0.19 the checks for cyclic data structures are designed in a very specific way. Cyclic data is permitted at the top level, but not in let expressions. That means you can construct a Decoder, Parser, or Generator with a self-recursive definition, but because it is at the top level, the allocation is statically known. That means you can set a little bit of memory off to the side even at compile time. The object will live for the life of the program (because it is top-level) and GC does not need to be concerned about it.

If the same cyclic data could be constructed in let expressions, it would be allocated dynamically, thereby becoming the concern of the GC. (That is why they cannot be allocated in let expressions!)

Reevaluating Claims

I think you are claiming that ones = \() -> 1 :: ones () proves that cycles can still exist. It does not create cyclic data though. Another way to write it is ones () = 1 :: ones () so we are just looking at a function that calls itself. Functions allocate things separately, so you would resolve the recursive call and then allocate a new cons cell. No cycles.

This example is weird because if you ever call ones () in your program, it infinite loops until you run out of memory. So even if it did create cycles (which it does not) it would not be usable in practice.

Having a lazy library allows you to create code like this:

type Stream a = Cons a (Lazy (Stream a))

ones : Stream Int
ones =
  Cons 1 (lazy (\() -> ones))

When the lazy part is forced, the internals switch from an unevaluated function to a pointer back to the initial allocation. This is cyclic data!

If you can create a value like this in a let expression, you can dynamically create cyclic data that needs to get GC’d at some point. This means a naive ARC implementation is not viable anymore.

So given the actual details about cycles (only top-level and statically known) I think the GC considerations are still valid. If I am missing something, I’d like to understand it via a small example.

Prioritization

On one side we have an argument about GC and a potential performance profile that has not been possible before: naive ARC can be used without leaving garbage around. (Perhaps I made a mistake and somehow function closures can create cycles that are uncollectable, but I’m not seeing that example though.)

On the other hand we have the computation of Hamming Numbers and the Sieve of Eratosthenes. Are you using either of those in any of your Elm applications? Is that part of the code a noticeable performance bottleneck? Have you heard about it from the people who use your application?

Point is, given the information I have now, I think it would be a shame to close the door on a really interesting optimization that could improve the performance of Elm programs for the sake of the examples that have been provided here.


#7

@evancz, thank you very much for your detailed reply; I appreciate that you must be very busy.

First understand my objective: I don’t want to add or write JavaScript to a library if it isn’t absolutely necessary; I hate JavaScript, which is why I embrace Elm and am looking forward to the day that Elm emits Web Assembly. I have rethought this to agree with you that the Lazy library is likely not really necessary; I just want to examine whether a memoizing LazyList library can be provided that doesn’t break anything.

Technical Details:

I had accidentally discovered that cyclic data is only allowed at the top level, and now see your reasons for not allowing it in let .. in expressions: I wholeheartedly agree with this.

Reevaluating Claims:

I now see that a recursive function doesn’t constitute cyclic data, and we both know that if recursive functions aren’t constructed carefully, they will race until either stack overflow or forever unless there is a limiting condition placed in the loop, with the behavior depending on whether Tail Call Optimization can form a loop or not depending on the placement of the recursive call.

As to your provided example, let’s do the same thing just using deferred execution without using Lazy:

type Stream a = Cons a (() -> Stream a) 

ones : Stream Int
ones =
    Cons 1 (\() -> ones)

This doesn’t use Lazy/lazy but still produces cyclic data; however, as explained in Technical Details, since this is only allowed in the global scope and not in a let .. in , this recursive reference to a global object doesn’t cause any problems. The same would be true even if the lazy version were used, as the injection of the intervening extra function call(s) doesn’t change the new version 0.19 compiler’s ability to detect and reject the recursion when in a let .. in local declaration. Thus, the new compiler rejects all cases of cyclic data, including lazy cyclic data, other than at the global level where it doesn’t cause any problems.

My point was this: If in the same situations one can produce the same cyclic data in global scope (and cannot produce it in local scope) whether using the Lazy library or not, you can’t use that as a reason for not using the Lazy library.

If fact, I now support you in not allowing the Lazy library to be used directly as I, too, see that its use can almost always be accomplished in other ways; my request now is that you consider its effect to be used in implementing a true memoizing LazyList library with it well buried inside and not directly accessible to users of such a library.

Prioritization:

The above example proving that use of the Lazy library doesn’t have an impact on your GC considerations doesn’t make those considerations invalid: now that you have made cyclic data references no longer possible for local declarations, you have prepped the way to this alternate implementation of GC, if that is desired. Thus, whether you decide to go ahead or not with such optimization is no part of this discussion.

I use Elm to create web pages I use in teaching mathematics concepts, as well as for exercises in learning computer programming by creating such web pages as student activities, somewhat in co-operation with Professor Christopher Anand of McMaster University in Canada. While it is true that I can teach with constructs that are terribly inefficient, it doesn’t reflect well on Elm as a general purpose language when such code may run hundreds of times slower than when implemented in other functional languages. The language Fable, which also transpiles to Javascript, is an example of such a language, and although it offers mutability as an option, it is still faster for doing these kinds of algorithms even when not using mutability. The reason I want to choose Elm over Fable (or PureScript, etc., although PureScript is more complex than I want) is that Elm is a complete solution for generating web pages in that the Elm Architecture is built-in, where one has to go through hoops with Fable (or PureScript) to generate the same thing; I also like the idea of mutability not being an option at all, as it doesn’t let the students fall into bad habits.

So to answer your direct question, yes I do use exercises in the generation of Hamming numbers and use of the Sieve of Eratosthenes (and others) as exercises in my advanced teaching courses, and performance is a bottleneck for use in other than the most limited ranges when the students compare what they can do in other languages when they know them. I don’t want Elm to look limiting in what it can be used to do if such limitations aren’t necessary, and I don’t think this is a necessary limitation for the reasons given.

My point is: Allowing the addition of a true memoizing LazyList library that includes some minimal Native JavaScript that isn’t exposed to users as a library in elm-explorations does not close the door on your proposed GC optimizations. Thus, what reason can you give for rejecting it other than that so far it has found limited application?

Part of the reason that the LazyList library in elm-community/lazy-list wasn’t used very much is that, first, not many discovered it, and second, that it is flawed; I was in process of correcting those flaws in a PR, for which I deferred proceeding since it can’t work without either a Lazy library or permission to generate the equivalent Native code within it.

If a very good implementation were provided in mainstream elm-explorations with great documentation explaining how it can be effectively used (and the use cases where a lazy Stream without memoization would be more suitable for performance reasons), there will be applications using it:

“If you build it, they will come.”

If you allow it, I volunteer to be the author of such a library.


#8

Are you familiar with John Hughes’ Why Functional Programming Matters? It explains why both higher-order-functions (which is not the subject here) and laziness are very strong and useful tools in programmer’s toolbelt.

He shows a couple of examples where lazyness is extremely useful:

1: An algorithm approximating some interesting numerical quantity.

Because generating ever-improving approximations is done lazily, it is completely decoupled from how the result is consumed: Do we keep on improving the approximation until the result adheres to a certain metric? Do we improve the approximation a little bit, but always stop after half a second is passed because showing a rough result quickly is more important for our application than being very precise? (This also applies to e.g. pathfinding in real-time games, rendering fractals, as well as other types of computational geometry or genetic algorithms (example)).

  • Yet another example where this would be super useful, is to create recursive fuzzers that do not require to have a hard-coded depth limit!
    Instead, the limit can be decided based on hardware speed, or you could configure different depth limits in dev vs continuous integration. Or even something else: That’s the point! The fuzzer definition should not need to care.

2: Artificial Intelligence.

(In the paper, he talks about the Minimax algorithm with alpha-beta pruning.)

In these types of algorithms, the possible ways for the game to continue are represented as in a tree structure. Since in many games, certain board situations can re-occur, these trees are inherently infinite.

In languages that do not support lazy evaluation, you are forced to create these trees implicitly, which means that you will write code that interweaves multiple concerns. In fact, John Hughes writes in the paper:

[In the lazy implementation, with stark contrast to the naive eager implementation,] Only a small part of the tree is stored at a time. The lazy program is therefore efficient.
This efficiency depends on an interaction between maximize (the last function in the chain of compositions) and gametree (the first);
without lazy evaluation, therefore, it could be achieved only by folding all the functions in the chain together into one big one.
This would be a drastic reduction in modularity, but it is what is usually done. We can make improvements to this evaluation algorithm by tinkering with each part; this is relatively easy.
A conventional programmer must modify the entire program as a unit, which is much harder.


Conclusion

In summary, lazyness can greatly improve modularity, because you separate the generation of data from the way it is manipulated and from how it will eventually be consumed. Without lazyness you end up (even if you have deferred execution):

  1. Combining generation and consumption into the same function;
  2. Writing a producer that works optimally only for certain consumers;
  3. Implementing your own version of memoized laziness. (which will be very difficult in pure Elm and might very well end up passing intermediate results around the TEA such they can be ‘memoized’ by storing them in the model somewhere.)

Each of these points poses a problem; even more so for library developers than for application developers.

I hope to have provided a reasonable case why Lazy is an intrinsically important tool to people working in Elm.


#9

By the way, I do not completely understand why Automatic Reference Counting would be tremendously more difficult to implement if cycles are possible: Since Elm’s compiler is already smart enough to realize that something is a cycle, a weak reference could simply be used instead of a strong one whenever the step that completes the cycle is executed.

If I am missing something here, please do tell! :slight_smile:


#10

I still do not understand how it’s possible to create a circular data structure in Elm. Doing so requires maleability, which Elm strictly forbids. Does the old lazy library violate this somehow? Or maybe what some people call a circular data structure is not what I mean. I mean a data structure some part of which is the whole. This is easy to do in languages that allow you to change the components of a data structure, but impossible in a purely functional language.

Not having circular data structures means that reference counting is ALWAYS sufficient. It also makes generational mark-sweep-compact much more local, since there are NEVER pointers from old space to new space.


#11

Yes, lazy allows you to circumvent this using a procedure known as ‘tying the knot’.

In a purely functional language, evaluation can be seen as graph reduction, with the language runtime following the edges (the references to nested data structures) of this graph to find out what is contained. In the case the edges are connected in such a way that they form a cycle (which in Elm we can do using Lazy.lazy), we keep on following the edges around the cycle, which evaluates to an infinite structure. If we do this in an eager language, of course we will never end walking around the cycle so the program will not halt. But if we do only as much work as is necessary (in other words: if we do the work lazily), we can just return the result of all elements encountered as far as we’ve walked around the cycle. In other words: Some elements are returned multiple times. This is not a problem of course, since they are immutable anyway.

So there is no mutating going on here at all.

More information on Haskell’s wiki about Tying the Knot.

An Elm example of creating such a circular data structure can be seen in the LazyList library’s Lazy.List.cycle function.

And note that if we just use non-memoized lazy evaluation, walking around a circular data structure means each element in the cycle is re-computed every time we reach it, which is why just using \() -> a is not good enough to support it.


As far as I know, weak references are references that, as far as the garbage collector is concerned, do not exist, so they should not complicate any garbage-collection scheme you throw at it.
The single difficulty of using weak references is that you have to know when to use a normal reference and when to use a weak one, but the Elm compiler has already solved this problem, because it already detects cycles.


#12

Ah. So we’re talking about truly lazy computation, as implemented by Haskell, where nothing is actually done until it needs to be printed, or sent over the wire. Elm doesn’t do that. At least not now. Html.Lazy is a poor man’s simulation, but not the real thing.

I know very little of the benefits and pitfalls of Haskell’s lazy execution, except that it makes defining infinite data structures, which may or may not be circular, very easy.


#13

@Qqwy, In your discourse, can you distinquish whether most things that you consider being able to do in Elm truly need Lazy or would it be sufficient to provide a true memoizing LazyList?

It seems to me that the latter would be sufficient.

I think it unlikely that Evan will grant us the first, but I’m hoping for the second…


#14

@billstclair, regarding comparing the proposed memoizing laziness for Elm compared to the full time laziness of Haskell (actually non-strictness to be pedantic), we are not really proposing that we turn Elm into a mini Haskell.

If Elm still had the Lazy package it would still be a strictly evaluated language with memoized laziness as an option much as F#, OCaml, etc. support. We are unlikely to get that back unless someone (not me) convinces Evan that it would provide an essential benefit to the language; I have come to agree with Evan that laziness in the form of the Lazylibrary is not essential.

However, I feel that a memoizing LazyList library would be very useful and sufficient for most use cases, as well as being able to be made safer to use in avoiding some race conditions.


#15

It would seem that some clarification with examples is in order to define the impact of using a memoizing LazyList compared to a non-memoizing Stream on potential Garbage Collection (GC):

First, let’s define simple infinite (as in no ability to detect an end of sequence) versions of each, assuming that the LazyList has access the the old Lazy library which isn’t exposed to users (ie. the types are exposed but none of the constructors or the force evaluating function in the Lazy library):

type Stream a = ConsSteam a (() -> Stream a)
headStream : Stream a -> a
headStream (Stream head _) = head
tailStream : Stream a -> Stream a
tailStream (Stream _ tailfunc) = tailfunc() -- to appear the same as the LazyList version
consStream : a -> (() -> Stream a) -> Stream a
consStream hd tl = ConsStream hd tl

type LazyList a = ConsLazyList a (Lazy (LazyList a))
headLazyList : LazyList a -> a
headLazyList (LazyList head _) = head
tailLazyList : LazyList a -> LazyList a
tailLazyList (LazyList _ taillazy) = force taillazy
consLazyList : a -> (() -> LazyList a) -> LazyList a
consLazyList hd tl = ConsLazyList hd <| lazy <| \() -> tl() -- extra indirection used so lazy/Lazy needn't be exposed

So now we can work with only the types and the functions to construct and deconstruct the types.

This is a synthetic construction, as numbers() can be defined as just a recursive function with either:

numbersStream : () -> Stream Int
numbersStream() = let nmbrs n = consStream n <| \() -> nmbrs (n + 1) in nmbrs 1

numbersLazyList : () -> LazyList Int
numbersLazyList() = let nmbrs n = consLazyList n <| \() -> nmbrs (n + 1) in nmbrs 1

Now the sequence of all the natural numbers can be constructed as recursively referred sequences as following. Using recursion on the generated sequence, which does not run away as the recursion is broken with the deferred execution of either as long as the starting definition is initialized properly:

numbersStream : () -> Stream Int
numbersStream() =
    let plus1 strm = consStream ((headStream strm) + 1) <| \() -> plus1 <| (tailStream strm)()
    in plus1 <| consStream 1 <| \() -> numbers()

numbersLazyList : () -> LazyList Int
numbersLazyList () =
    let plus1 lazylst = consLazyList ((headLazyList lzylst) + 1) <| \() -> plus1 <| tailLazyList lzylst
    in plus1 <| consLazyList 1 <| \() -> numbers()

Note that these are functions and not constants (without the ()), else on use in the case of a memoized LazyList it will hold onto whatever part of the sequence is evaluated, with no way of freeing the memory until the program ends; as a Stream it won’t hold onto memory.

However, even as a LazyList and with reference counting, there is no memory leak, as if not constructed properly (not initializing the first element of the stream to one as required here), it will overflow the stack in which case the error recovery for the memory manager can recover the memory, or if if used correctly so as to release the head of the sequence as consumed, it will then also release the memory properly in sequence; in the case of not releasing the head, the memory manager will release the memory when the program terminates normally.

Further, this is the same case as for cyclic data defined this way as follows:

cycleLazyList : a -> LazyList a
cycleLazyList nythng = consLazyList a <| \() -> cycleLazyList nythng

This is a function, and if one sets a binding to the result of the function, that binding will hold onto the head of the LazyList not allowing any of the evaluated part of the sequence to be released until the program terminates, just as before; however, again just as before, if one arranges for the head of the sequence to be released as it is consumed, there will only be one element held in memory at a time, whether the memory manager works by garbage collection scans or by reference counting.

Finally, in the case that everyone seems to be concerned about, as follows:

ones = consLazyList 1 <| \() -> ones

There is only ever one element produced, as the Lazy on the tail just refers back to the beginning of the LazyList which is the binding of ones; where is the problem? There is no race and no memory consumed, but there are two references being produced, one for the ones binding and one inside the embedded Lazy or maybe three if the one inside the thunk is persisted, only two in the case of this same structure using Stream. However, this definition is now only allowed at the global level meaning that the ones binding can never go away until the program is ended, so it can’t cause any problems.

As well, additional references to this object such as:

otherones = ones
otherotherones = otherones

don’t cause any problems as they just add two references (permanent if at the global level; temporary if at the local level) bringing the total up to four while they are in scope (always in scope at the global level).

In short, lazy memoizing and memory management now have nothing to do with each other other than memoizing uses a fixed amount of memory as it memoizes just as it is meant to do!!! This is the trade-off one makes (as well as the slower speed) when there are advantages to be gained by the memoizing.

The “Weak Reference” discussion and extra complexity have no meaning, as there is no need to use such a thing.

This discussion considering reference counting for memory management makes me think that someone is considering Beyond JavaScript, as when Elm is transpiled to JavaScript, the JavaScript engine handles memory management and there wouldn’t be any point to adding extra levels on top as it would just slow it down even more; however, currently WebAssembly only uses an assigned block of memory so memory management is up to the application built on top of it: thus I hope this is a clear sign that we are getting closer to emitting WebAssembly from Elm!.

As described, the rules are simple: Add one to the reference count when a binding comes into scope, including on creation; subtract one when a binding goes out of scope; when the reference count goes to zero dispose of the created object.

The only problem with a naive reference counting memory manager is that memory gets fragmented, but observing that Elm only has a limited range of sizes of “things”, currently with sub Array's perhaps being the largest at 256 bytes, and the smallest non-primitive perhaps being the List element at say 24 bytes, it would be quite easy to assign memory from different memory pools as per the given element size; in this way no compaction would be necessary! String's (of Char's) would need to be re-implemented as List's of Char's or more likely for better memory efficiency, List's of small sub arrays of Char's, as one couldn’t just tie into JavaScript’s concept of String; essentially, every element becomes a small immutable array.

Hey, if Evan will build the conversion of his Elm AST into WebAssembly, I’ll provide you with a reference counting memory manager!


#16

Yes:

  • For the first example, having a LazyList that can work with an infinite stream of linear data is good enough, because the problem is naturally expressed as taking items from an infinite stream until we’ve arrived at one that is ‘good enough’.
  • However, the second example, the AI example, uses a multi-way tree. As far as I know, there is no possible way to map a (possibly infinite) multi-way tree to a linear stream (since it can be seen as the reduced, one-dimensional case of a multi-way tree).

#17

@GordonBGood Nice code examples!

:+1: Yes, my point exactly!

I am fairly certain that @evancz is indeed thinking about WebAssembly here.


#18
  • However, the second example, the AI example, uses a multi-way tree. As far as I know, there is no possible way to map a (possibly infinite) multi-way tree to a linear stream.

So, we would need yet another library to implement a multi-way tree, but it could still hide the memoization inside so that it isn’t exposed to users if Evan so desires.


#19

In practice, it can be done like this:

That is, using a buffer to order nodes in the tree for later (lazy) exploration.


#20

Interesting idea! It seems a tree is modeled by the Buffer type by being able to lazily move in two ‘directions’: Down to the ‘current’ child, and over to the next ‘sibling’.

Also interestingly, is that the given search algorithm is not lazy. I am fairly certain that the search algorithm will break on infinite trees, or graphs with cycles.

If implemented in a lazy fashion, it would be built on top of Lazy as well, rather than LazyList because the latter does not make any sense. If only the latter were exposed by the language, you’d be forced to create singleton lists.