Hacker News Reader

Comment by svachalek | Hacker News Reader

I think if the second one is easier, you've more or less been taught to think like a microprocessor. That happens to most of us after a few years of writing imperative code. The more abstract functional approach is, however, conceptually simpler and more powerful at the same time. (For example, the first one is completely open to being performed in parallel.)

With a little experience, functional programming is quite straightforward. Practically everything comes down to map, filter, and fold, or whatever they're called in a given language.

View on HN

I can't help thinking like a microprocessor. Even when mixing functional style into my code, my brain tries to get a grasp on how it's going to be processed.

So the first example looks to me like two loops (hopefully the compiler does a better job on that), while the second one is obviously one loop.

I am already trying to guess how a compiler would parallelize that...

The second one might be obviously a single loop, but it is not obvious that it is O(n) and depends on the implementation of "append". It also tells you nothing about how the memory gets accessed and I'm assuming here that the for loop works just as well over linked lists and over arrays. In other words your knowledge that this is a single loop can be very misleading when thinking of expected performance. Which is fine because we work with abstractions such that we don't have to think about such details all the time, because that's not doable.

The first example is simply more abstract. It might be a single loop in case the implementation is lazy, it might be two loops in case it is strict. However, look closer. Those filter and map operations can be applied to basically anything you want, including asynchronous / infinite streams.

Your second loop on the other hand would have a hard time being translated to anything else than something that works on finite lists and that builds a finite buffer and not doing anything else while doing this.

Or in other words, your knowledge about this manual loop is not transferable ;-)

Excuse my ignorance but why is the first one parallelizable but not the second?

They're both parallelizable, but the second one is harder to automatically parallelize.

There are guarantees about the way a map function works. It doesn't mutate its input, it only has access to one element at a time, you can't access the data structure you're building, etc.

All of these traits are true of the imperative version as well, but it's a lot harder to write a program which understands that. Meanwhile, you know that's how map and filter work, so it's trivially easy to know that those guarantees hold.

As a matter of fact loops that mutate state are not parallelizable because you can't analyze what they do in order to infer intent and thus some imposed ordering with which you could efficiently distribute the required work while at the same time guaranteeing correctness - solve that and you'd solve the Halting problem ;-)

Can't be done.

Well, you can't solve it in the general case. But parallelizing compilers can and have been written that perform a conservative analysis -- they can prove some subset of all parallelizable loops as parallelizable, and for the ones they can't prove as such, they err toward 'remain serialized'.

For a simple example, code that performs regular array-based accesses, where index computations are simple affine functions (a*i + b) of a single iteration variable 'i', is a case that's received a lot of attention. See e.g. Polly for LLVM.

In the first one, you are simply telling it to map and filter every element. Since you can do that to each element in an independent way and the code is more abstract, the map and filter can be done in parallel without you knowing (I'm not sure if would execute in parallel in Swift, I know that in java you can change the way it does it by using parallel streams).

But in the second example, you are telling it to iterate over each element, sequentially. Since you are telling step by step what needs to be done, it's not parallelizable unless you implement it to be so.

Put another way, the first example is about data flow. The required value is specified declaratively, in the form of an expression.

The second example is about control flow. The required behaviour is specified imperatively, in the form of a statements to be executed in a defined order, and the combined effect of those statements is to update the list until it has the required value.

In the second case, the programmer specifies more details explicitly. In this case, those extra details probably aren’t helping, but the optimiser still has to prove that transforming the control flow (for example, into a parallelised form) really will give the same observable behaviour. In the first case, the optimiser doesn’t have to prove the things the programmer never specified anyway, so it has more latitude in how it implements the underlying computation.

As a matter of fact, any implementation of the same algorithm has the same parallelizing possibilities. You just need a smart enough compiler.

But a "smart enough compiler" is what compiler people say when they are talking about their version of the abstract anthropogenic equivalent AI. The fact is that the first one is much easier to parallelize, so that real implementations actually do it, while the second one is not done on practice. And it's easier to parallelize because there are some extra guarantees on the signature of those functions that a for loop does not give.

Maybe we aren't speaking the same language, but I never mentioned parallelism in my text.

We could talk about why the first example could be parallelized of course, but that's not what I wanted to talk about and you missed the point ;-)

Actually, I responded to the wrong post. I meant to post my reply to svachalek.

> For example, the first one is completely open to being performed in parallel

So what do you actually have to do to make this actually run in parallel? Or do you truly get it automatically?

I don't think that will happen in Swift, but conceptually there's nothing that stops the compiler from doing it since you're not specifying the order that anything happens. Some Haskell compilers can automate parallelization of the equivalent code. But pragmatically speaking, you can convert code in this style to parallel code without changing the algorithm; for example various "map-reduce" servers are built around the idea of mapping and reducing, which are fundamental concepts of functional programming.

In contrast, in the imperative form, you are specifying how items are appended to a list, which means that any attempt to do it in parallel could change the order of the operations and therefore the order of the result. Sure, a sufficiently smart compiler could in theory figure out what "should" happen and see how to optimize it, but in practice today's smartest compilers can barely handle the functional case.

Don't know about Swift, but in Haskell you substitute parallel versions of map and filter that are guaranteed to mean the same thing.

Hence why "structure and interpretation of computer programs" is a very important read.

Reply on news.ycombinator.com