5 ms·

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,

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.

naasking 4y ago
> 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.
- tsimionescu 4y ago
  > 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) Functional: search page:rest_of_book post-it-stack = search rest_of_book (if ('cheese' `on page) then number(page):post-it-stack else post-it-stack) search [] post-it-stack = post-it-stack 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
  - naasking 4y ago
    > 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.

naasking 4y ago

> 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.

tsimionescu 4y ago
> 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) Functional: search page:rest_of_book post-it-stack = search rest_of_book (if ('cheese' `on page) then number(page):post-it-stack else post-it-stack) search [] post-it-stack = post-it-stack 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
- naasking 4y ago
  > 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.