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.

[SimonMeskens]

I've been working on a language that allows you to hand-optimize blocks of code, with a theorem solver to guarantee correctness of the optimization, for years. It's a really complex problem and rabbit hole to go down into. I assume in a best-case scenario, it will make the feature (or even language) complex to work with.

[shelby3]

@keean wrote:

The solution is to give the programmer the ability to incorporate domain specific optimisations.

The tradeoff is a loss of genericity or generality. It is I guess of another one of those triplet rules where you can't have all three so pick 2: genericity performance extension.

[keean]

The tradeoff is a loss of genericity or generality. It is I guess of another one of those triplet rules where you can't have all three: genericity performance extension.

You can do this with typeclass specialisation, provide a generic implementations for something, and then specialise for different types. The library author declares a new type, say a matrix, and then overloads the genetic operators like '+' with highly optimised code for high performance matrix maths.

[shelby3]

@keean wrote:

You can do this with typeclass specialisation

Example.

[shelby3]

@keean wrote in 2016:

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.

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
}

The proposed for for Zer0 makes the algorithm even more readable:

mystery :: (x) =>                  [[T]] -> [[T]]
   a := [[]]                       // [[T]]; Dunno if will need to annotate this type or can be inferred
   for v in x
      b := Array<[T]>(a.length * v.length)
      for j, v1 in a
         for k, v2 in v
            b[j * v.length + k] = v1.concat(v2)
      a = b
   a

But for fair comparison, let’s rewrite the recursion example in Zer0 and not try to make it more sloppy than it needs to be:

mystery :: (x) =>                  [[T]] -> [[T]]
   x.fold([[]], (a, v) =>
       a.fold([], (b, v1) =>
           b.concat(v.map((v2) => v1.concat([v2])))))

Frankly I think the recursion example is now more declarative, easier to read and understand than the one employing imperative loops.

Which can be even more concise:

mystery :: (x) =>                  [[T]] -> [[T]]
   x.fold([[]], (a, v) =>
       a.fold([], (b, v1) =>
           b.concat(v.map(v1.concat([_])))))

[keean]

@shelby3 I disagree, when I surveyed people about this, it was the fact that the types changed between functions that causes the problems, and neater syntax does not address this. Concat and reduce both do non-obvious things with types. What makes the imperative verison easier for people to understand is that we have objects (a and b) whose types remain the same throughout the algorithm.

This is because in real life we don't have machines that a car goes into and and aeroplane comes out of. Instead we are happier removing passengers from the car and adding them to the aeroplane.

[shelby3]

@keean I don’t comprehend your complaint. The type of a and b in both are [[T]] and [T] (i.e. Array<Array<T>> and Array<T>) respectively. Ditto the input and result type of concat being [T].

The higher-order functions (aka HOF) variant is much more declarative about the semantics of what the algorithm is doing. The imperative version uses instead generic loops which have no declarative meaning and must instead analyze the algorithm in imperative detail to figure out what it does.

---

In short, imperative coding with mutability = spaghetti. We can't unravel any part of our program from any other part. It becomes one amorphous blob.

^{EDIT: https://codeburst.io/a-beginner-friendly-intro-to-functional-programming-4f69aa109569}

sup>https://medium.com/@riteshkeswani/a-practical-introduction-to-functional-programming-javascript-ba5bee2369c2</sup

^{https://flaviocopes.com/javascript-functional-programming/}

^{https://thenewstack.io/dont-object-ify-me-an-introduction-to-functional-programming-in-javascript/}

Note to readers: The point of PFP (pure FP) is not to eliminate all mutability. We want to separate the declarative logic from the mutable side "effects", so that we can refactor the declarative part without creating spaghetti cascade of unintended (i.e. opaque) side effects to our intended semantics. That's why the transparent in referential transparency.

I wrote in the OP of this thread:

^{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.}

In that linked Rust forum post from May 8, 2016 I wrote:

1. Efficiency of lazy versus eager evaluation in functional programming composition over collections (more generally enumerables).
2. _Advantages of encapsulation and a more informational structure of enumerables versus [unstructured] iterators_, ^{yet need [unstructured] iterators for some algorithms.}
3. ^{GC memory performance cost versus imperative boilerplate and/or manual memory management cost of temporary objects.}
4. ^{The imperative boilerplate and/or manual memory management cost of longer lived generational objects when abandoning GC due to performance issues related to the above 3 issues.}

^[…]

^{There is some work on ways to iterate collections that might be relevant to the discussion: http://okmij.org/ftp/papers/LL3-collections-enumerators.txt}

The goal is attaining the “Reuse” Augustss prefers about lazy evaluation, while not incurring the negative side-effects (i.e. resource and timing indeterminism) of lazy evaluation ^{and also not forsaking encapsulation of resource lifetime management that imperative spaghetti such as unstructured use of iterators ostensibly might entail.}

For another example of the bolded, italicized quoted compositional, declarative advantages of Haskell’s lazy evalution and memoization, c.f. the Fibonacci numbers example:

fib n = fibs !! n
  where fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs)

EDIT#2: I don’t know why readers fail to pay attention to the link I provided above that explains that imperative programming can’t be composed and FP can be composed. That is the entire fundamental point. If the reader misses that point, they might as well have not read anything else above:

http://augustss.blogspot.com/2011/05/more-points-for-lazy-evaluation-in.html

I’m also recommending that readers who are new functional programming (FP) also read the book Programming in Scala which appears to be available for free as a downloadable PDF online.

EDIT#3: I had also discussed this issue on Feb 4, 2018.

[keean]

@shelby3 I surveyed people including seasoned functional programmers, and by far the majority found the imperative version easier to understand. You cannot argue against that, it is an empirative fact. You could conduct a larger survery to over turn the results, by showing you have a better sampling of the target audience of the language, but this is a measurement not an opinion.

[shelby3]

@keean I wasn’t disputing your survey results. Nor am I claiming that the results would be different with a larger sample. I think the results would only be different for a sampling of those who like functional programming.

The point is that Zer0 should have both paradigms available. So for example one benefit is the functional programmers have an optional choice other than Haskell.

Personally I much prefer the declarative variant and will try to teach that in the documentation and how-to guides for Zer0, discouraging the use of for.

Do you have a problem with offering both paradigms?

(I am preparing to show how the HOF can be done lazily employing iterators and generators to they are just as efficient as the imperative and also have the benefits of Haskell’s non-strict evaluation strategy.)

[shelby3]

Tikhon Jelvis explained why lazy evaluation is important for functional programming (and I explained up-thread that functional composition requires laziness):

You see, the real advance is that non-strictness moves the program’s evaluation order below our level of abstraction. It has a powerful analogy to garbage collection which similarly abstracted over memory management. Before garbage collection came along, programmers constantly thought about memory allocation and deallocation; now it’s something you don’t have to worry about 99% of the time. The less you need to think about incidental details like this, the more you can focus on what matters—your domain.

I feel the same going back to strict languages. When I write in JavaScript or Python or even OCaml, I constantly think about what order my code will run in. It’s so constant you probably don’t notice, just like a fish doesn’t notice water. But when I’m back in Haskell, all of a sudden I don’t have to worry about it any more. I can write code in an order that makes sense to me and that guides the reader properly. It’s a step away from assembly and closer to prose.

[…]

There’s a reason literate programming lives on in the Haskell world—it fits with the Haskell model in a way that is foreign to fundamentally imperative languages.

At this point, I simply take laziness for granted. If you take a random module I’ve written and make it strict, it probably won’t work. Sometimes this comes from “flashy” tricks that rely on non-strictness: infinite quadtrees, automatic differentiation or self-referential data structures. Far more often, though, it’s the little things: variables extracted from conditionals into shared where-clauses; functions written separately but executed fused; creating and consuming a large structure without putting it in memory; expensive logs and asserts that won’t cost anything when turned off. Little advantages that make my code clear and easier to write—that I use without thinking.

It’s just that convenient.

I wrote:

(I am preparing to show how the HOF can be done lazily employing iterators and generators to they are just as efficient as the imperative and also have the benefits of Haskell’s non-strict evaluation strategy.)

I wrote in the OP of this thread:

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.

In that linked Rust forum post from May 8, 2016 I wrote:

1. Efficiency of lazy versus eager evaluation in functional programming composition over collections (more generally enumerables).
2. Advantages of encapsulation and a more informational structure of enumerables versus iterators, yet need iterators for some algorithms.
3. GC memory performance cost versus imperative boilerplate and/or manual memory management cost of temporary objects.
4. The imperative boilerplate and/or manual memory management cost of longer lived generational objects when abandoning GC due to performance issues related to the above 3 issues.

In the aforementioned threads, I have alluded to some ideas I have about perhaps how to paradigm shift the issues with inversion-of-control.

I think it is helpful to first understand how C++11 encapsulated the problem of temporary objects of rvalues, and thus was able to optimize their memory allocation orthogonal to any semantics in the programmer’s code, i.e. afaics rvalue is an inherently encapsulated semantic for this optimization case.

But rvalue encapsulation is useless in the more general case of temporary objects created under functional composition:

I wrote:

kirillkh wrote

There is some work on ways to iterate collections that might be relevant to the discussion: http://okmij.org/ftp/papers/LL3-collections-enumerators.txt

The goal is attaining the “Reuse” Augustss prefers about lazy evaluation, while not incurring the negative side-effects (i.e. resource and timing indeterminism) of lazy evaluation and also not forsaking encapsulation of resource lifetime management that imperative spaghetti such as unstructured use of iterators ostensibly might entail.

In Haskell we can write:

map :: (a -> b) -> [a] -> [b]

some :: (Maybe m) => (a -> m b) -> [a] -> [b]

f :: a -> b

g :: (Maybe m) => a -> m b

let x = some g (map f 0::1)

We can I suppose write that in Rust roughly as follows:

fn map<A,B,C:Collection>(fn(A) -> B, C<A>) -> C<B>;
fn some<A,B,C:Collection>(fn(A) -> Option<B>, C<A>) -> C<B>;
fn f<A, B>(A) -> B;
fn g<A,B>(A) -> Option<B>;
let x = some(g, map(f, {0, 1}));

Since Rust employs eager evaluation strategy, map calls f for every element before some is called; thus if some terminates (when g returns false) before all the elements have been enumerated, Rust has wasted some computation. Whereas, since Haskell employs lazy evaluation strategy, f is only called for those elements which some enumerates.

We need to employ inversion-of-control in an eager language so that the called functions can call and enumerate their callers. But this isn’t straightforward because the generalized structure and composability of Collection semantics must be respected.

The most general forward enumeration function is a fold where B is the current value of the result of the fold and the Option can terminate the enumeration early:

fn fold<A,B>(Enumerable<A>, B, fn(B, A) -> Option<B>) -> B;

The functions map and some can be built employing fold. [Note I meant that to for example map a list then fold over the list accumulating a new list as the output.]

Afaics, it would be impossible to build our design on the general fold without coroutines or generators, because there is no guarantee that the incremental partial orders of its interim result type can be enumerated incrementally, i.e. there are no assumptions that can be made about the semantics of the unbounded generic result type B. [Note I meant that B might not isomorphic to an iterable or enumerable data structure.]

Afaics, if we were to instead build our design for inversion-of-control on fn map<A,B,M:Monoid+Enumerable>(M<A>, fn(A) -> Option<B>) -> M<B> where the incremental consistency is honored and M is consistent across the functional composition, then the optimization arises of ignoring the structure of the result type, compose the callers’ chain of fn(A) -> Option<B> operations, enumerate the input Enumerable (aka Iterable) on those composed functions, and employ Monoid::append to construct the result. In other words, simply call map with the composed function.

For more general case where M is not consistent but the enumeration can be modeled as an incremental cursor (see the aforementioned quoted reference), we only need a control function with that has a variadic input taking an Enumerable+Monoid paired with each fn(A) -> Option<B> operation in the composition. This control function can encapsulate all the resource lifetime management orthogonal to instance and compositions. I don’t see any reason we need coroutines or generators in this case. The instance of the Enumerator (aka Iterator) maintains the necessary state.

For more general case where the enumeration can’t be modeled as an incremental cursor (see the aforementioned quoted reference), we need to allow the Enumerable:fold method decide when and how many times it will invoke the fn(B, A) -> Option<B> operation so it can then yield to its caller, who can continue its Enumerable:fold. So the input to fold requires a Yieldable interface:

fn fold<A,B:Yieldable>(Enumerable<A>, B, fn(B, A) -> Option<B>) -> B;

This Yieldable interface should be implemented with stackless coroutines, which in this special case can be implemented with a function call that inputs and outputs its internal state so each yield (return from the function) can be restarted (by calling the function inputting the last output state). Otherwise known as generators.

The fn(B, A) -> Option<B> operation must be a pure function so that it can’t leak resources to subvert the encapsulation of the resource lifetimes.

I believe this is more and less the rough outline at least to my current understanding of this issue.

Edit: the fn(B, A) -> Option<B> operation does not have complete control over its efficiency w.r.t. to how many successive times it will be invoked relative to the yield. It can’t cache and queue expensive operations in B because it can’t be sure it will be invoked again. Some improvement in this design may be needed.

Edit#2: I don’t think higher-kinded types are required by any of the functions mentioned above. They could possibly required for iterators.

Quoted above the problem from issue #1 is that in an eager language a copy of the entire collection is created by map even though some may exit before processing the entire collection. So temporary objects are created and CPU is wasted unnecessarily, which is the price to pay for generalized functional composition over collections. Even in a lazy language like Haskell, all those temporary objects for the thunks will be created unnecessary (in addition to other disadvantages of lazy evaluation such as non-deterministic resources and timing).

Afaics, Rust’s memory management paradigms can’t help us solve that waste with maximum degrees-of-freedom. I anticipate @keean will probably offer some more complex boilerplate way to accomplish what I lay out below, and I will aim to show him as I did in my other thread, that boilerplate reduces degrees-of-freedom.

But I showed a conceptual way to invert the control in an eager language (like Rust), so that none of the above waste is incurred:

For more general case where the enumeration can’t be modeled as an incremental cursor (see the aforementioned quoted reference), we need to allow the Enumerable:foldmethod decide when and how many times it will invoke the fn(B, A) -> Option<B> operation so it can then yield to its caller, who can continue its Enumerable:fold. So the input to fold requires a Yieldable interface:

fn fold<A,B:Yieldable>(Enumerable<A>, B, fn(B, A) -> Option<B>) -> B;

This Yieldable interface should be implemented with stackless coroutines, which in this special case can be implemented with a function call that inputs and outputs its internal state so each yield (return from the function) can be restarted (by calling the function inputting the last output state). Otherwise known as generators.

The fn(B, A) -> Option<B> operation must be a pure function so that it can’t leak resources to subvert the encapsulation of the resource lifetimes.

Additionally, if the callback functions of the enumerables are pure functions (and given they are pure they can’t mutate—such as via closure—the collection they are enumerated over), and if using an appropriate method such as map (and not a generalized fold) then the intermediate collections can be freed without any need for GC, refcounting, nor lifetime checking, because they are encapsulated such that they can’t be referenced by the callback function. The solution is pure semantic encapsulation.

However the temporary objects created by the callback function can’t be assumed to have not ended up referenced in the final output of the composition, so these can’t be freed without some optimized form of GC, refcounting, or lifetime checking:

I wrote:

Edit: could it be that the generational GC was not able to be sure that you hadn’t referenced the temporary objects from the mutable objects in the older region? See the a key advantage of immutability for Haskell.

I wrote: In a mutable language such as C#, how would it know that these temporary objects haven’t been referenced by some mutable objects in the older area of the generational GC? If it can’t know, then it can’t free these objects efficiently at the end of the generation, because it would require tracing all the possible paths to these temporary objects in the older area as well.

When I post about inversion-of-control and temporary objects, I think we will see that immutability is crucial. Otherwise the only choice we appear to have is to unwrap all the elegance of higher-level composition and force the programmer to do boilerplate.

[…]

In the above quoted post I was trying to simulate the advantages of Haskell’s lazy evaluation and memoization in a non-lazy (i.e. eager evaluation) programming language. One of the reasons the above post (and actually the entire linked Rust thread) was so convoluted is that I was trying to figure out how to have GC nearly as efficiently as for C++ while achieving those desirable Haskell composition and declarative capabilities. Also the immutability issue is problematic in Rust because its lifetimes require exclusive mutability.

Given the epiphany (c.f. near bottom of the linked post) about how to achieve near zero-cost resource allocation and deallocation in an Actor model without Rust’s lifetime woes, I think the above goal can be achieved much more elegantly because we simply don’t need to be concerned with encapsulating the stack frame and young generational heap from the top-down, because the deallocation (of everything not persisting) is performed at the Actor’s stack head instead (independent of the functional compositions inside the call hierarchy of the Actor’s function and stack).

Simply have fold, map, etc (which are typeclasses) return a variant of the collection (or other) data type input, wherein that variant has a closure on the lazy, incrementalized operation. No generators needed. When that variant data structure is passed as input to another function in the compositional chain (e.g. some, drop n, take n, zipWith, etc) then it can supply an Iterator typeclass instance which of course evokes the closure to lazily and incrementally compute it. Even random access iterators could be supported for arrays.

The closure makes these functions not pure (i.e. non-referentially transparent mutation) but remember a non-pure computation can be contained within a pure function.

Note these lazy variants of those functions are less efficient when it’s known that the entire for example map must run to completion, so we should have fast versions of these typeclasses as well. The programmer will choose.

Obviously there are still all sorts of performance decisions to be made such as for example whether the model an array as a list or list as an array. The array has O(1) random access but needs to know its maximum size when allocated else copying is needed when the array size must be reallocated larger. But for a lazy computation, the array could potentially be unbounded in size (even though it will not all be computed). Whereas, lists have slower access performance and slow random access, but have O(1) when adding new elements because never have to reallocate.

EDIT: I was contemplating whether this proposal might conflict with the value restriction, given the type parametrised ValueType for the collections. But the value restriction isn’t required if values can’t be polymorphic after instantiation.

[shelby3]

So @keean what is your reaction to the prior post as now edited? Especially Tikhon Jelvis’s point.

Do we need to adopt strategies for our libraries to provide lazy versions as well as eager versions?

[keean]

@shelby3 I think that generators using 'yield' are a better solution than lazyness by default. Lazyness leads to unpredictable performance in both time and space. Simple loops fill memory with thunks before doing a single thing.

I thought about data-flow for a while, but I think that it is a culturally harder for people to think about.

Algorithms are described by mathematicians as a step by step imperative process, going back 1000s of years to the ancient Egyptians. This tells us that imperative strict ordering is the way people naturally think of algorithms.

So in the end, I think default strict with genrators to provide lazyness where you need are the right solutions, and offer all the possibilities of lazyness with none of the uncertainty (or maybe strict co-routines).

Oleg goes through the whole reasoning in much more depth here:

http://okmij.org/ftp/continuations/PPYield/yield-pp.pdf&ved=2ahUKEwjz1cCU5YzdAhVHPsAKHZvAA7c4ChAWMAB6BAgFEAE&usg=AOvVaw3WvH-lqwF8AzR52I87sdKm

[shelby3]

@keean wrote:

I think that generators using 'yield' are a better solution than lazyness by default.

My longish post that I asked for your reaction to, actually proposes the use of iterators as the lazy glue to make function composition lazy and thus efficient. And iterator is sort of analogous to a generator, because it captures the necessary state to return to caller and restart the next time the caller calls it again.

So I think we are actually in agreement on that point. I want to make sure you actually understand what my longish post is about.

I thought about data-flow for a while, but I think that it is a culturally harder for people to think about.

Algorithms are described by mathematicians as a step by step imperative process, going back 1000s of years to the ancient Egyptians. This tells us that imperative strict ordering is the way people naturally think of algorithms.

Now you are reacting to a different facet of my longish post. That is the issue of whether functional composition (e.g. fold) is superior to imperative spaghetti. In this case, where functional composition is not too convoluted, it is actually much more comprehensible than imperative spaghetti. I experienced this benefit in Scala and really liked it. Imagine map take 1 instead of some convoluted special imperative spaghetti that has to be rewritten for every permutation of function composition. It’s just we need laziness (even simulated with iterators as I proposed) otherwise it is wasteful as Augustss explained up-thread.

Sorry but I think you are just wrong on this issue.

Yet some algorithms are too convoluted to express with functional composition, so in that case I still want to offer the ability to code imperative loops.

[keean]

@shelby3 simple functions work well with functional composition, like turn every int into a string. The problems with understanding happen when things go through several intermediate types.

Python agrees with me :-) http://lambda-the-ultimate.org/node/587

Of course I favour declarative programming wherever possible, so list/array/map comprehensions like in python make sense to me.

[shelby3]

@keean Eric S. Raymond (the “LISP hacker”) threatened mutiny if Guido removed his lambdas from Python. Guido backed down and did not remove them. My guess is that Guido is not that senior of a programmer. I’m guessing he is more like mid-tier, not senior level like us (based only on a few blog posts of his I read, but I could be mistaken). And he ostensibly wants to dumb Python down to his level. Well maybe I shouldn’t characterize myself as senior, as that should be proven I guess (hopefully over next couple of years).

Anyway, the point is that Python doesn’t want to be a functional programming language.

This comment was particular poignant:

My problem with GvR's reasoning is his desire to drag everyone down to his level of ability.

I think the problem, if it is a problem, is that Python is intended as a single-paradigm language, and that paradigm isn't functional.

I refer to this quote:

almost every time I see a reduce() call with a non-trivial function argument, I need to grab pen and paper to diagram what's actually being fed into that function before I understand what the reduce() is supposed to do

It's not a problem I've ever had... It just takes some time to learn the pattern of using fold, just like you have to learn the patterns of using generators, or objects, or anything else.

You can kiss my ass goodbye if we’re not creating a functional programming language here.

Also @keean you seem to be forgetting that functional composition can be parallelised and optimised better by the compiler than some imperative spaghetti.

The sort of people who might agree with you (actually he prefers Python’s list or generator comprehensions) and Guido also think that redundant semicolons are a good thing.

Btw, for comments posted by JustSaying, that was me.

[keean]

@shelby3

Also @keean you seem to be forgetting that functional composition can be parallelised and optimised better by the compiler than some imperative spaghetti

In theory, but due to side effects in most languages like Lisp, you cannot actually parallelize, and the kind of optimisations needed for performance are not easy, and have not been successfully implemented in any language, so if you don't trust the optimiser with references (which do work well in Ada) then you should not be expecting the optimiser to help significantly here.

Anyway my point was not that we should not allow higher order functions, but more that their use should be discouraged from creating unitelligably terse points-free compositions.

I am considering disallowing closures though, which are un-functional anyway because they create side-effects when combined with mutation.

[shelby3]

@keean wrote:

Anyway my point was not that we should not allow higher order functions, but more that their use should be discouraged from creating unitelligably terse points-free compositions.

I agree except the question is how you define the what is to be discouraged. Up-thread we disagreed on an example that I thought was better expressed in functional composition.

So that is why I say I want both paradigms in Zer0 and then let the programmers decide. We can’t make that choice for them, unless we want to be like Python and not have pithy functional composition.

Imperative coding does not compose. Monads do not compose. Side-effects do not compose. That is the point of functional programming.

I am considering disallowing closures though, which are un-functional anyway because they create side-effects when combined with mutation.

As I recently stated in the Closures are bad? issues thread #33, I want them implicitly when they don’t escape the function where they were instantiated. Remember even you had noted in the past that a pure function can contain impure procedural code as long as the side-effects don’t leak outside (aka escape) the said containing pure function. I want closures only explicitly otherwise.

[sighoya]

@shelby3

I find the standard definition of "pure" too restrictive.

The idea of pure functions is to provide deterministic functions, i.e. there is exactly one value for each pair of parameter values.

I would also considering functions pure which cause mutations (effects) which escape the current context as long as the mutated value is not involved into the return value. If it is otherwise, then the function is only impure because of drawing non deterministically a value from a container (receiving effect) and not of subsequent mutation (sending effect).

So receiving effects and include them into the return value should only create impure functions and not sending effects.

Of course it doesn't suffice to compare functions for equality if they can be compared, for this you need an effect system.

[keean]

@sighoya algebraic effects allow more fine grained control than monads, and are my currently preferred solution.

I also think actors with pure methods, somewhat like state-machines are an interesting point in the design space. We consider the method takes the arguments of the method plus the current state of the actor, and returns the new state would be pure, and yet sending a message to an actor is already impure, so nothing is lost by having impure state.

@shelby3 as we discussed before algebraic effects compose, and can be modelled as an "EffectMonad".

[shelby3]

Guys I still have no understanding of the benefits of algebraic effects. After studying them it just looked like more abstraction thicket masturbation to me. In a few sentences, what is the point and compelling advantage?

I would also considering functions pure which cause mutations (effects) which escape the current context as long as the mutated value is not involved into the return value. If it is otherwise, then the function is only impure because of drawing non deterministically a value from a container (receiving effect) and not of subsequent mutation (sending effect).

So receiving effects and include them into the return value should only create impure functions and not sending effects.

Of course it doesn't suffice to compare functions for equality if they can be compared, for this you need an effect system.

I have no idea what any of this means.

A pure function has a clear definition. Anything else is not a pure function.

I wrote in the Why typeclasses? issues thread #30:

I do agree though that when the abstractions become a layered thicket of opaque mechanisms a la monad transformers in Haskell, that sort of abstraction is too abstruse and I would not like to promote that style of programming. That is abstraction complexity that is required just to shoehorn a separation of effects such as IO into a limited, low-level paradigm of monolithic purity. As I stated in my comments about Haskell, that imperative effects are inherently highly granular; and thus trying to get all those ducks into a row is (borrowing from Robert Harper’s comments about modules versus typeclasses) like trying to turn the Titanic. I have instead agreed with @keean that maybe we should look at Actors instead and designing our abstractions to be indifferent to message arrival order (i.e. inherently design for disorder) rather than having that abstraction enforced at such a low-level as purity. Purity seems to be a useful concept for expressing an invariant but it appears to be too low-level for dealing with effects in general.

[keean]

@shelby3 why effects?

Effects allow control over side effects, but unlike monads the compose.

[shelby3]

@keean, I wrote:

I wrote:

and we want to control effects with an effects system. With actors only the actors implement interfaces, and side effects are implicit in the actors.

I don’t want to control effects with your idea of typeclasses. I want to eliminate effects by making actors function independent of ordering of messages. For other types of effects, we need some model that works at the actor level.

By effects we mean management of a state machine.

What I am saying is that the state machines of Actors should be independent from each other. They should function correctly regardless of the state machines outside.

So this means abandoning determinism and accepting statistical progress.

Determinism is the wrong assumption. We can’t move forward with computing until we abandon it.

In fact, my decentralization solution to the centralization problem of blockchains which nobody else has solved, is basically at the generative essence about abandoning determinism.

So I think the entire concept of algebraic effects, purity, and monads is far too low-level to deal with the problem they are actually purporting to deal with.

[shelby3]

Reminder that Go doesn’t offer tail call optimization (TCO), although note that may not matter as I wasn’t proposing to employ recursion for FP. Rather I proposed employing iterators to implement for example fold.