Comment by qazxcvbnm

Of course! Let me write a complete overview on the subject. Consider the following program:

    (Foo a b) = (If a (F b) (G b))

It is easy to note that Foo makes an unnecessary clone of the 'b' variable, since it is used in different branches. This could be avoided by adding a lambda, as follows:

    (Foo a b) = ((If a λb(F b) λb(G b)) b)

That is what I mean when I said that, in most instances, cloning can be avoided by adding strategic lambdas. Now, in some cases, such as issue #60, this won't be possible. Issue #60 isolates a situation where lazy cloning is necessarily quadratic. Here it is:

    (Gen 0)             = Nil
    (Gen n)             = (Cons n (Gen (- n 1)))
    (Sum Nil)           = 0
    (Sum (Cons x xs))   = (+ x (Sum xs))
    (Tails Nil)         = (Cons Nil Nil)
    (Tails (Cons x xs)) = (Cons xs (Tails xs))
    (Heads Nil)         = Nil
    (Heads (Cons x xs)) = (Cons (Head x) (Heads xs))
    (Head Nil)          = 0
    (Head (Cons x xs))  = x
    Main                = (Sum (Heads (Tails (Gen 1000))))

What this program does: first, it converts a list like [1,2,3,4,5] into a list of where each element stores its tail: [[2,3,4,5],[3,4,5],[4,5],[5]]. Then, it takes the head of each element, resulting in [2,3,4,5]. Notice it is a very inefficient, roundabout implementation of 'tail', which happens to be quadratic on HVM, and linear on GHC. In this specific case, this could be fixed by just writing Tail as usual:

    (Tail (Cons x xs)) = xs

It is worth pointing out that this is the case in all examples where HVM is sub-optimal! That is, there is always an alternative algorithm that avoids unnecessary cloning. That said, of course, in more complex programs, it will be impossible to identify sub-optimal situations and fix automatically (unless supercompilers become practical). As such, it is important for HVM to be able to handle these programs without quadratic slowdowns. To understand how that could be accomplished, let's first note that the culprit of the quadratic slowdown is the way HVM handles a non-linear variable. On the line below:

    (Tails (Cons x xs)) = (Cons xs (Tails xs))

HVM's default behavior is to assume that, by writing `xs` twice, you meant to do a lazy clone. In other words, the program above is compiled as:

    (Tails (Cons x xs)) =
      let [xs_a, xs_b] = xs.lazy_clone()
      (Cons xs_a (Tails xs_b))

In order to work, lazy cloning adds a "fan node" to the program's graph, which uses space. That means that, if you perform a lazy clone and immediately discard it, you'll be left with a "useless clone node" that still occupies memory. On the program shown on issue #60, we're essentially constructing an entire Tail and immediately dropping it with a call to Head, and we do that recursively, so, after enough calls, we have, in memory, the equivalent of:

    let [_, xs0] = xs.lazy_clone()
        [_, xs1] = xs0.lazy_clone()
        [_, xs2] = xs1.lazy_clone()
        [_, xs3] = xs2.lazy_clone()
        ...
        [_, xs{N}] = xs{N-1}.lazy_clone()
    in xsN

Notice how this expression takes a list, clones it several times, discards all the clones, and then immediately returns the original list. These accumulating useless let-expressions (i.e., cloning nodes) are the source of the quadratic slowdown. So, how do we fix it? The solution proposed on TOIFPL book is to add safe pointers, which would allow us to remove redundant clone nodes when safe. But there is a simpler approach: just do NOT make a lazy clone there, to begin with! While lazy cloning is great for things like higher order lambda compositions, in some cases, a good-old pass-by-reference would do a better job. In a future version of the HVM, we could have something like:

    (Tails (Cons x &xs)) = (Cons xs (Tails xs))

Where `&` would mean "pass by immutable reference", skipping lazy cloning entirely, and making this program linear, as it should.

In short, the culprit for the quadratic slowdown is merely the fact that HVM automatically inserts a ".lazy_clone()" whenever you use a variable more than once, but there is no inherent incompatibility between interaction nets and good-old pass-by-reference, so HVM will have different pointer types that allow a programmer to implement functions like Tails that behave like they would on GHC, without any associated slowdown.