1. Immutability is non-intuitive. If I were to hand a regular person a book, and ask him how he would list all the page's numbers where the word cheese appears, he would probably say something like this: 'I would read through the book, keeping a scrap of paper at hand. Whenever I saw the word cheese, I would write down the page number' This is an imperative algorithm. I could give more examples, but I hope you get the point.
2. I just wrote the 'friends' example to make a point - common, complex programs often have huge graphs of interconnected objects, whether one would like it or not. Your solution is to build a journal of friendships and breakups - it's not a typical solution for object relations - seeing if 2 people are friends is a linear operation. Keeping the history around might not be necessary or useful.
3. Your FP code runs on a modern OoO CPU whether you like it or not - so it's safe to make that assumption. And multithreading might not be a silver bullet. FP does nothing to break long dependency chains. As for sharing values between CPU cores, considering the latencies involved, it might be cheaper to compute the value locally, but multithreaded optimization is a black art - it's not always obvious if sharing is better.
Another example is when I made a small toy Excel-like spreadsheet that supported formulas - while Excel itself is FP, I realized that the best way to update cell values, is to topologically sort all dependent expressions, and evaluate them one after the other - an imperative concept.
4. I was just making the point is it's easy to write a function in e.g. Java that is imperative on the inside, but is pure when called from the outside. Other languages will even allow the compiler to enforce this, while still being imperative. So both 'regular' and FP languages can avoid some side effects to some extent, but have to deal with others.
> 1. Immutability is non-intuitive. If I were to hand a regular person a book, and ask him how he would list all the page's numbers where the word cheese appears, he would probably say something like this: 'I would read through the book, keeping a scrap of paper at hand. Whenever I saw the word cheese, I would write down the page number' This is an imperative algorithm.
No, that's a purely functional algorithm. Note how he's just adding numbers to the end of a list and emphatically not mutating the existing items in any way. Tell me what you see as the functional real-world solution to this problem. Do you consider an accounting general ledger to also be imperative? Because it clearly isn't, it's an append-only log where all previous entries are immutable, which is exactly the same thing as the list noting the pages containing the word "cheese".
> 2. I just wrote the 'friends' example to make a point - common, complex programs often have huge graphs of interconnected objects, whether one would like it or not. Your solution is to build a journal of friendships and breakups - it's not a typical solution for object relations - seeing if 2 people are friends is a linear operation. Keeping the history around might not be necessary or useful.
The example doesn't make a point. In either imperative or functional programming, the operations you need and their time and space complexity will dictate the data structures and algorithms to use. Saying that programs have "huge graphs of interconnected objects" is not evidence of anything specific.
> 3. Your FP code runs on a modern OoO CPU whether you like it or not - so it's safe to make that assumption.
Make what assumption exactly? Microcontrollers are in-order. GPUs are in-order. You also made claims that FP programs are full of pointers and non-performant data structures. I have no idea what out of order execution has to do with this claim. Certainly early FP languages were pointer heavy, but early imperative programs were goto heavy, so I'm not sure what exactly you think this says about FP in general.
> And multithreading might not be a silver bullet. FP does nothing to break long dependency chains.
FP encourages and often forces immutability which does help significantly with parallelism and concurrency.
> Another example is when I made a small toy Excel-like spreadsheet that supported formulas - while Excel itself is FP, I realized that the best way to update cell values, is to topologically sort all dependent expressions, and evaluate them one after the other - an imperative concept.
Prove that that's the best way, and not merely the best way you know of, or the best way available to your programming language of choice.
> No, that's a purely functional algorithm. Note how he's just adding numbers to the end of a list and emphatically not mutating the existing items in any way.
They are clearly mutating the piece of paper to add new numbers to it. There is no linked list in sight. They are also flipping the pages of the book in order, another imperative paradigm.
The closest you could come to a pure FP algorithm expressed in physical terms would have been "Say there are still pages I haven't looked at, and say I have a stack of post-it notes on the current page; then, I would check if the word cheese appears on this page, and if it does, I would produce a post-it note with the page number on it, adding it over the stack of post-it notes; I would then flip one page; on the other hand, if I am looking at the last page of the book, I would add another post-it note to the stack if needed, and return the whole stack of post-it notes to you otherwise".
Imperative:
foreach page in book
if 'cheese' in page
write(paper, page.number)
Of course, we could write this easier with a map and filter, but I don't think there is any good way to express those in physical terms (not with a book - filters have nice physical interpretations in other domains though).
Later edit:
A version of the imperative algorithm closer to what was described in prose:
repeat:
word = read_word(book)
if word == 'cheese':
write(paper, current_page_number(book))
if no_more_words(book):
return paper
> They are clearly mutating the piece of paper to add new numbers to it.
No, they are simply adding a new record for the word occurrence. If the paper runs out, they grab another sheet and continue. This is clearly an append-only ledger, just like that used in accounting. These are both immutable abstractions.
The fact that this is happening on a single sheet of paper is merely an optimization, it's not a property of the underlying algorithm they're employing. The post-it equivalent you describe is simply a less space efficient version of exactly the same algorithm. You're basically saying that tail call elimination makes FP no longer FP.
> There is no linked list in sight.
What do linked lists have to do with anything? You don't think that FP or immutable programming have to use lists do you?
> They are also flipping the pages of the book in order, another imperative paradigm.
Traversing an immutable sequence in order is now an imperative algorithm? Since when?
What's really happening here is that you've already assumed that physical reality and people's intuitions are imperative, regardless of the contortions required.
This example of counting words and the general ledger are perfect examples: it's absolutely crystal clear that all of the recorded entries are immutable and that this log of entries is append-only, which is a characteristic property of FP and immutable abstractions, and yet you have to contort your thinking into looking at the paper itself as some mutable state that's essential to the process in order to call this an imperative process.
> The fact that this is happening on a single sheet of paper is merely an optimization, it's not a property of the underlying algorithm they're employing.
The person is describing the abstraction, not any optimization. If you were to translate their words directly into code, you would have to write code that modifies the piece of paper, because this is what they described.
In contrast, when using a persistent data structure, the abstraction says that I create a new structure that is the old one + some change, but, as an optimization, the computer actually modifies it in place. The implementation is imperative, but the abstraction is functional.
> You're basically saying that tail call elimination makes FP no longer FP.
No, I'm saying that there is a difference between writing an algorithm using tail-call recursion, and writing it using iteration; even if the compiler produces the same code. The tail-call recursive version is FP. The iterative version is imperative. How they actually get executed is irrelevant to whether the algorithm as described is FP or imperative.
In contrast, you're basically claiming that any algorithm that could be abstracted as FP is in fact FP. So, `for (int i = 0; i < n; i++) { sum += arr[i]; }` is an FP algorithm, as it is merely the optimized form of `sum x:xs total = sum xs x+current; sum [] current = total` after tail-call elimination.
> Traversing an immutable sequence in order is now an imperative algorithm? Since when?
Immutability and FP are orthogonal. Append-only ledgers are a data structure, not an algorithm; and it's algorithms that can be functional or imperative.
On the other hand, yes - traversing a data structure in order is an imperative idiom. In pure FP, the basic operation is recursive function application, not traversal. For loops and tail-call recursion obtain the same thing in different ways.
> This counting words and the general ledger are perfect examples: it's absolutely crystal clear that all of the recorded entries are immutable and that this log of entries is append-only, which is a characteristic property of FP and immutable abstractions, and yet you have to contort your thinking into looking at the paper itself as some mutable state in order to call this an imperative process.
By your definition, I understand this is an FP algorithm for producing a list of the first 100 natural numbers, since it's append-only:
xs := []int{}
for (i := 0; i < 100; i++) {
xs = append(xs, i)
}
You can certainly define FP = append-only, but that is emphatically not what others mean by the term. Instead, most people take FP to mean "expressing the problem in terms of function applications (and abstractions based on them), where function == pure function in the mathematical sense".
> What's really happening here is that you've already assumed that physical reality and people's intuitions are imperative
I've actually shown what I think is actually an FP algorithm represented in physical terms, and how that translates 1:1 to FP code (and the alternative imperative algorithm). I don't think it's fair to accuse me of assuming that physical reality is imperative - at least not without showing your 1:1 mapping of the description to FP pseudo-code.
Edit to ads:
Perhaps a fairer representation of the imperative algorithm should have been:
repeat:
word = read_word(book)
if word == 'cheese':
write(paper, current_page_number(book))
if no_more_words(book):
return paper
This is even closer to the prose version, and makes it clearer that it was describing an imperative traversal.
2. I just wrote the 'friends' example to make a point - common, complex programs often have huge graphs of interconnected objects, whether one would like it or not. Your solution is to build a journal of friendships and breakups - it's not a typical solution for object relations - seeing if 2 people are friends is a linear operation. Keeping the history around might not be necessary or useful.
3. Your FP code runs on a modern OoO CPU whether you like it or not - so it's safe to make that assumption. And multithreading might not be a silver bullet. FP does nothing to break long dependency chains. As for sharing values between CPU cores, considering the latencies involved, it might be cheaper to compute the value locally, but multithreaded optimization is a black art - it's not always obvious if sharing is better.
Another example is when I made a small toy Excel-like spreadsheet that supported formulas - while Excel itself is FP, I realized that the best way to update cell values, is to topologically sort all dependent expressions, and evaluate them one after the other - an imperative concept.
4. I was just making the point is it's easy to write a function in e.g. Java that is imperative on the inside, but is pure when called from the outside. Other languages will even allow the compiler to enforce this, while still being imperative. So both 'regular' and FP languages can avoid some side effects to some extent, but have to deal with others.