Iteration versus enumeration

[shelby3]

We will need to decide which models we provide. This may not be purely a library decision and may reach into the features we offer in the language.

To kick off discussion, I refer to my post from May 8 in the Rust forum.

[keean]

I think we need both. Some algorithms are best expressed as recursion (mostly divide and conquer algorithms like quicksort). Some are best expressed as iteration. Iteration has the advantage that it does not introduce a new stack frame. Index variables and arrays make for very clear vector and matrix operations that become a mess with recursion, and unreadable using higher order combinators.

[shelby3]

Conceptually I agree. We will need to dig into the details though.

[shelby3]

Do we support for? Only for iterators, or also in traditional JavaScript form? Do we have a for for enumerables?

Your ideas for syntax?

I think we should retain the ability to construct a var within a for, but I would argue it should have the semantics of ES5's let so the reference doesn't escape the for's scope.

[SimonMeskens]

I think that you can solve the mess of recursion with generators. Can you provide an example where recursion gets messy? I'll try to rewrite it with generators to explain how I see it working.

[keean]

function mystery(x) {
    var a = [[]]
    for (var i = 0; i < x.length; ++i) {
        var b = []
        for (var j = 0; j < a.length; ++j) {
            for (var k = 0; k < x[i].length; ++k) {
                b.push(a[j].concat([x[i][k]]))
            }
        }
        a = b
    }
    return a
}

[keean]

Here's the same code written using higher order functions:

function mystery(x) {
    return x.reduce((a0, v0) => {
        return a0.reduce((a1, v1) => {
            return a1.concat(v0.map((v2) => {
                return v1.concat([v2])
            }))
        }, [])
    }, [[]])
}

I find it harder to understand what this version is doing. I put this down to there being type-transformations being done by the higher order functions which you have to work out. With the imperative version the types of x, a and b remain the same throughout which makes it easier to understand.

[SimonMeskens]

I just played around with it for a good long while and I agree that this example resists most methods of simplification and that as far as I can tell, the simple iteration method is probably preferable in this case.

There's simply no clear way to un-nest the loops, as the accumulator loop stops almost any form of un-nesting. Nested lambdas are very hard to understand and iteration is preferable in that case.

You can probably fix this by introducing some complex combinators, but that wouldn't increase simplicity of course.

[shelby3]

Here's the same code written using higher order functions:

Additionally in general the implementation in an eager language with functors is much less efficient, because temporary collections are created. In the OP, I linked to some of my ideas for perhaps improving that efficiency.

The obscurity of the algorithm in this pathological case is convincing towards preferring iterators. However the ability to compose meaningfully named functors can sometimes aid clarity.

[keean]

I agree there are some clear cases where higher order approaches are preferable. Mapping a function over a collection is straightforward. Anything with maths on the indexes loops are probably better. Another example where loops seem clearer is the Sieve of Eratosthenes (aside: someone recently made a breakthrough improving the memory usage of the sieve by a couple of orders of magnitude).

[keean]

List (and other collection) comprehensions offer a nice declarative solution to this (in Python):

def perm xss 
   var tot = [[]]
   for xs in xss
      tot = [x:ys | x <- xs, ys <- tot]
   return tot

or Haskell:

perm :: [[a]] -> [[a]]
perm [[]]   = [[]]
perm xs:xss = [x:ys | x <- xs, ys <- perm xss]

[shelby3]

@keean wrote:

List (and other collection) comprehensions offer a nice declarative solution to this (in Python):

I have agreed they are interesting to consider, but argued to delay these decisions here and here.

[shelby3]

A recent LtU post and the ensuing discussion, brings back some of the points I was making to @keean in the debate between us about iterators versus enumerables at Rust forum this past May.

[keean]

Forcing people into a functional Style is not going to make the language popular.

Also even people who advocate this programming style don't seem ro appreciate the real limitations. No optimiser can incorporate domain specific optimisations into representstiond, as this is effectively a huge search operation in an infinite search space. Even humans do this by referring to libraries of pervious results. I am not going to re-prove all the results of prime-number theory every time I need a new prime number for an encryption key, I have a library that incorporates this knowledge. Program transformation is mathematically equivalent to proof transformation, so optimisation is transforming one proof into a shorter, faster one. The solution is to give the programmer the ability to incorporate domain specific optimisations. We don't need a second language to transform the first, as that is just added complexity, we just need a first language that can represent the optimised operations. This means an imperative language with control over memory layout, evaluation order, the individual bits.