> 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.
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:
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:
This is even closer to the prose version, and makes it clearer that it was describing an imperative traversal.