5 ms·

I just don't get the idea that "sequential" is somehow a bad thing? The whole concept of an algorithm/procedure to perform a computation is about performing a s

I just don't get the idea that "sequential" is somehow a bad thing? The whole concept of an algorithm/procedure to perform a computation is about performing a series of operations in a specific order. You have to think about the operations and their order as well to come up with an algorithm.

greydius 8y ago
Order is not always necessary. For an example, just consider why SIMD instructions and GPUs are so powerful: they can do the same operation on a lot of data at the same time. A different example would be the async/await patten. Independent calculations can proceed concurrently. So no, a specific order of every operation is not part of the definition of algorithm. Indeed, if that was the case CPUs could not do out-of-order execution optimizations.
- ankurdhama 8y ago
  What you are describing is that you can design an algorithm where "some part of the algorithm" can be executed in any order, so that you can execute them in parallel to gain performance using multiple cores but overall when thinking about coming up with the algorithm you will have to figure out the correct sequence. Async/await is sequential where the operations are asynchronous (you don't move to next async operation until the previous async operation is done, given that the second async operation have dependency on the first operation's result).
CuriousSkeptic 8y ago
If the sequenece is non-essential to the problem, it adds the accidental complexity of all sequence related bugs to the system. See the out of the tar pit paper https://blog.acolyer.org/2015/03/20/out-of-the-tar-pit/ https://blog.acolyer.org/2015/03/20/out-of-the-tar-pit/
- ankurdhama 8y ago
  AFAIK, tar pit paper is about how "shared mutable state" is problematic. Not sure what that has to do with sequentiality.
  - dragonwriter 8y ago
    It is about complexity; state, not necessarily shared, is the main source of complexity addressed but the fundamental point isn't specific to state. Sequentiality, often, especially, for example, for things which can be conceived of as set operations, adds unnecessary complexity which complicates reasoning.
  - vendiddy 8y ago
    Shared mutable state is just one cause of accidental complexity. In section 4.2 of the paper, they also talk about "Complexity caused by Control". Quoted: > The problem with control is that very often we do not want to have to be concerned with this. Obviously — given that we want to construct a real system in which things will actually happen — at some point order is going to be relevant to someone, but there are significant risks in concerning ourselves with this issue unnecessarily.
  - typon 8y ago
    The paper argues specifically against Prolog because it is not a "pure" control-agnostic language. a = 1; b = 2; The programmer does not need to concern themselves with the order of these two assignment statements and when languages impose the order, it adds unnecessary complexity to the system. (especially when thinking about concurrency)
ghusbands 8y ago
Things are only sequential when you're programming in imperative style. Haskell, for example, supports plenty of algorithms that don't have a specific order in which things happen. Prolog, too. And Halide. Also, Oz. There are plenty around, and they are both useful and fascinating.
- ankurdhama 8y ago
  Haskell is lazy, you can write a bunch of expressions and use the results of those expressions in other expressions and so on. For example: foo :: Int -> Int foo a = let z = a * c b = 10 c = 20 in b + c + z I used c is z but c is defined later. The language allows you to defined the expressions in any order but internally it will have to figure out the dependencies between the expressions and execute them in specific order and also while writing code and coming up with the logic of the algorithm you will have to think about what you want to compute first and what to compute next.
- wwweston 8y ago
  Not sure Prolog is a good example here; my experience with it involved having to spend essentially as much time reasoning about how the unification/backtracking algorithm was going to visit different clauses and facts (and how I might want to cut/control that) as an imperative programmer might think about the order in which statements are executed. Maybe more, considering the process was less linear and obvious. (Not that I didn't like Prolog -- I did -- I just felt far from freed of mundane concerns of execution order.)
ordu 8y ago
I believe that this: > I just don't get the idea that "sequential" is somehow a bad thing? and this: > The whole concept of an algorithm/procedure to perform a computation is about performing a series of operations in a specific order. are different manifestations of the one thing: you are thinking about programming in a sequential terms only. When you think about programming problem you are trying to solve it by a sequence of operations. You should try something like Haskell, something that force your mind to think differently, it would help you to teach your mind to see programming other way. Such a "sequential thinking" is acceptable, but you probably not as good as you might be at thinking about programming problems. Functional programming helps to think about code one level higher, without distractions and compications caused by "linearization" of your thoughts to fit them into imperative paradigm. The main reason behind functional paradigm is an ability to prove statements about code, to be able to reason about code. To throw out idea of sequence from reasoning of code is a futher abstraction from underlying machinery like transistors or machine instruction set. As any abstraction it gives you both benefits (you can think about more complex problems using the same amount of computational power of your brains) and downsides -- you become more restricted by paradigm itself, though I cannot explain what these restrictions are, because I can feel them sometimes, but do not know how to verbalize that feelings. You can reason about code even if you think that any program is a sequence of operations, but you can do it better, if your idea of program is wider than a "series of operations in a specific order". Moreover some of that reasoning you can do by special program, like compiler or static analyzer.
- ankurdhama 8y ago
  > You can reason about code even if you think that any program is a sequence of operations, but you can do it better, if your idea of program is wider than a "series of operations in a specific order". Can you provide a concrete example of this? Otherwise it is just a hand wavy thing to say (which are way too many in programming world).
  - ordu 8y ago
    I'm not sure that example can possible work here. The best example would be something that is impossible to reason about in imperative terms but possible in functional terms. So... we need sufficiently difficult task, that will cause problems with understanding. And this task should be easy enough to be an example to write in HN comment. A contraversial setup, isnt it? I should use an artifical task as an example, but the trouble is if someone thinks in imperative terms only, then when he tried to think about a task he would frame the task in imperative terms and he would see it as an imperative problem and would fail to see it as a functional one. It is not because he is stupid or he posess some other disabilities, it is just the way human mind works. It is like people saying "what is so good about language X, if you can do all in Y"? "Why one needs OOP languages, if you can do OOP in C?" The way we think about problems defines how we see problems, and what we see as a problems. But let us try. qsort [] = [] qsort (x:xs) = qsort [ y | y <- xs, y < x ] ++ [x] ++ qsort [ y | y <- xs, y > x ] This is functional definition of a quicksort. It is possible the worst definition from performance standpoint, but I like it for clarity of algorithm expression, and it demonstrates the point. I remember the very first time I saw quicksort in C I have spent maybe half an hour trying to figure out how that code was supposed to work. Here you can see compressed version which have nothing but the very idea of quicksort: quicksort of empty sequence is an empty sequence. quicksort of sequence starting with x is a concatenation (operator ++) of three lists: quicksorted list of items from the rest of sequence (sequence without the first element which is designated as x) that are lesser then x, list of one element x, and quicksorted list of elements that are greater than x. Of course, if you want quicksort to be sorting in place, you would need to think about small details like traversing two pointers, one from the front of the sequence, second from the back, swapping elements, and not forgetting about the choosen one... Yeah, reality is more complicated than that, sometimes you cannot get rid of complexity. Functional compilers are constantly searching for optimizing techniques to get rid of all these small details, and in some ways they are succeeding. Though no one is good enough to generate machine code for sorting in place by compiling high level code above. But I tried to demonstrate the idea of abstraction of details and how it helps to understand code and to reason about it, and I believe the example is showing it.
dpratt71 8y ago
Various parts of an algorithm/procedure are related to each other in various ways. Sometimes those relationships describe a sequence. Other times they do not. For me, this is the essence of functional programming: a means to describe how the many small parts of an algorithm are related to each other in the whole (in a natural way). If the computation truly is one that is most practically described as a sequence of steps, that is easy to do. In fact, in some sense this is what the infamous "Monad" concept is all about.
SatvikBeri 8y ago
Some difficult problems are easier to solve if you don't have to think about them sequentially. One problem in my current work involves getting records from events one at a time, building predictive algorithms from those, and building another set of algorithms based on those. If you model it sequentially, it takes a lot of work to make sure the right data is calculated in the right order. But you can also model it as a set of lazily evaluated streams, and that makes life a lot easier – because order of evaluation isn't part of the domain, it's essentially an implementation detail. ETA: another way to think about it is that this lets the compiler manage evaluation order by default, while you're free to focus on other stuff (with the option to manage manually if you need to.) This is a similar type of benefit to garbage collection.
dorfsmay 8y ago
Not sequential: you can treat it as a set (in the mathematical sense) and solve your problems as a set operation, eg: "I want all the numbers greater than one". It makes it easy to read but also allows 1)not to deal with it until really needed (lazy eval) 2)partalellize the solution to n threads on m cores. Think list comprehension/generator in Python. Cons: you need more memory than you have data Sequential: you deal with one item at a time, you can deal with an infinite amount of data with a finite amount of memory. Cons: can't parralellize, early eval of things you don't need, you might need to go through the loop more than once.
crimsonalucard 8y ago
Having the power to order instructions introduces the possibility of having bugs that have to do with the order of operations. Getting rid of order gets rid of the bugs. Like how restricting types with type checking gets rid of all type errors.

greydius 8y ago

Order is not always necessary. For an example, just consider why SIMD instructions and GPUs are so powerful: they can do the same operation on a lot of data at the same time. A different example would be the async/await patten. Independent calculations can proceed concurrently. So no, a specific order of every operation is not part of the definition of algorithm. Indeed, if that was the case CPUs could not do out-of-order execution optimizations.

ankurdhama 8y ago
What you are describing is that you can design an algorithm where "some part of the algorithm" can be executed in any order, so that you can execute them in parallel to gain performance using multiple cores but overall when thinking about coming up with the algorithm you will have to figure out the correct sequence. Async/await is sequential where the operations are asynchronous (you don't move to next async operation until the previous async operation is done, given that the second async operation have dependency on the first operation's result).

CuriousSkeptic 8y ago

If the sequenece is non-essential to the problem, it adds the accidental complexity of all sequence related bugs to the system. See the out of the tar pit paper https://blog.acolyer.org/2015/03/20/out-of-the-tar-pit/ https://blog.acolyer.org/2015/03/20/out-of-the-tar-pit/

ankurdhama 8y ago
AFAIK, tar pit paper is about how "shared mutable state" is problematic. Not sure what that has to do with sequentiality.
- dragonwriter 8y ago
  It is about complexity; state, not necessarily shared, is the main source of complexity addressed but the fundamental point isn't specific to state. Sequentiality, often, especially, for example, for things which can be conceived of as set operations, adds unnecessary complexity which complicates reasoning.
- vendiddy 8y ago
  Shared mutable state is just one cause of accidental complexity. In section 4.2 of the paper, they also talk about "Complexity caused by Control". Quoted: > The problem with control is that very often we do not want to have to be concerned with this. Obviously — given that we want to construct a real system in which things will actually happen — at some point order is going to be relevant to someone, but there are significant risks in concerning ourselves with this issue unnecessarily.
- typon 8y ago
  The paper argues specifically against Prolog because it is not a "pure" control-agnostic language. a = 1; b = 2; The programmer does not need to concern themselves with the order of these two assignment statements and when languages impose the order, it adds unnecessary complexity to the system. (especially when thinking about concurrency)

ghusbands 8y ago

Things are only sequential when you're programming in imperative style. Haskell, for example, supports plenty of algorithms that don't have a specific order in which things happen. Prolog, too. And Halide. Also, Oz. There are plenty around, and they are both useful and fascinating.

ankurdhama 8y ago
Haskell is lazy, you can write a bunch of expressions and use the results of those expressions in other expressions and so on. For example: foo :: Int -> Int foo a = let z = a * c b = 10 c = 20 in b + c + z I used c is z but c is defined later. The language allows you to defined the expressions in any order but internally it will have to figure out the dependencies between the expressions and execute them in specific order and also while writing code and coming up with the logic of the algorithm you will have to think about what you want to compute first and what to compute next.
wwweston 8y ago
Not sure Prolog is a good example here; my experience with it involved having to spend essentially as much time reasoning about how the unification/backtracking algorithm was going to visit different clauses and facts (and how I might want to cut/control that) as an imperative programmer might think about the order in which statements are executed. Maybe more, considering the process was less linear and obvious. (Not that I didn't like Prolog -- I did -- I just felt far from freed of mundane concerns of execution order.)

ordu 8y ago

I believe that this: > I just don't get the idea that "sequential" is somehow a bad thing? and this: > The whole concept of an algorithm/procedure to perform a computation is about performing a series of operations in a specific order. are different manifestations of the one thing: you are thinking about programming in a sequential terms only. When you think about programming problem you are trying to solve it by a sequence of operations. You should try something like Haskell, something that force your mind to think differently, it would help you to teach your mind to see programming other way. Such a "sequential thinking" is acceptable, but you probably not as good as you might be at thinking about programming problems. Functional programming helps to think about code one level higher, without distractions and compications caused by "linearization" of your thoughts to fit them into imperative paradigm. The main reason behind functional paradigm is an ability to prove statements about code, to be able to reason about code. To throw out idea of sequence from reasoning of code is a futher abstraction from underlying machinery like transistors or machine instruction set. As any abstraction it gives you both benefits (you can think about more complex problems using the same amount of computational power of your brains) and downsides -- you become more restricted by paradigm itself, though I cannot explain what these restrictions are, because I can feel them sometimes, but do not know how to verbalize that feelings. You can reason about code even if you think that any program is a sequence of operations, but you can do it better, if your idea of program is wider than a "series of operations in a specific order". Moreover some of that reasoning you can do by special program, like compiler or static analyzer.

ankurdhama 8y ago
> You can reason about code even if you think that any program is a sequence of operations, but you can do it better, if your idea of program is wider than a "series of operations in a specific order". Can you provide a concrete example of this? Otherwise it is just a hand wavy thing to say (which are way too many in programming world).
- ordu 8y ago
  I'm not sure that example can possible work here. The best example would be something that is impossible to reason about in imperative terms but possible in functional terms. So... we need sufficiently difficult task, that will cause problems with understanding. And this task should be easy enough to be an example to write in HN comment. A contraversial setup, isnt it? I should use an artifical task as an example, but the trouble is if someone thinks in imperative terms only, then when he tried to think about a task he would frame the task in imperative terms and he would see it as an imperative problem and would fail to see it as a functional one. It is not because he is stupid or he posess some other disabilities, it is just the way human mind works. It is like people saying "what is so good about language X, if you can do all in Y"? "Why one needs OOP languages, if you can do OOP in C?" The way we think about problems defines how we see problems, and what we see as a problems. But let us try. qsort [] = [] qsort (x:xs) = qsort [ y | y <- xs, y < x ] ++ [x] ++ qsort [ y | y <- xs, y > x ] This is functional definition of a quicksort. It is possible the worst definition from performance standpoint, but I like it for clarity of algorithm expression, and it demonstrates the point. I remember the very first time I saw quicksort in C I have spent maybe half an hour trying to figure out how that code was supposed to work. Here you can see compressed version which have nothing but the very idea of quicksort: quicksort of empty sequence is an empty sequence. quicksort of sequence starting with x is a concatenation (operator ++) of three lists: quicksorted list of items from the rest of sequence (sequence without the first element which is designated as x) that are lesser then x, list of one element x, and quicksorted list of elements that are greater than x. Of course, if you want quicksort to be sorting in place, you would need to think about small details like traversing two pointers, one from the front of the sequence, second from the back, swapping elements, and not forgetting about the choosen one... Yeah, reality is more complicated than that, sometimes you cannot get rid of complexity. Functional compilers are constantly searching for optimizing techniques to get rid of all these small details, and in some ways they are succeeding. Though no one is good enough to generate machine code for sorting in place by compiling high level code above. But I tried to demonstrate the idea of abstraction of details and how it helps to understand code and to reason about it, and I believe the example is showing it.

dpratt71 8y ago

Various parts of an algorithm/procedure are related to each other in various ways. Sometimes those relationships describe a sequence. Other times they do not. For me, this is the essence of functional programming: a means to describe how the many small parts of an algorithm are related to each other in the whole (in a natural way). If the computation truly is one that is most practically described as a sequence of steps, that is easy to do. In fact, in some sense this is what the infamous "Monad" concept is all about.

SatvikBeri 8y ago

Some difficult problems are easier to solve if you don't have to think about them sequentially. One problem in my current work involves getting records from events one at a time, building predictive algorithms from those, and building another set of algorithms based on those. If you model it sequentially, it takes a lot of work to make sure the right data is calculated in the right order. But you can also model it as a set of lazily evaluated streams, and that makes life a lot easier – because order of evaluation isn't part of the domain, it's essentially an implementation detail. ETA: another way to think about it is that this lets the compiler manage evaluation order by default, while you're free to focus on other stuff (with the option to manage manually if you need to.) This is a similar type of benefit to garbage collection.

dorfsmay 8y ago

Not sequential: you can treat it as a set (in the mathematical sense) and solve your problems as a set operation, eg: "I want all the numbers greater than one". It makes it easy to read but also allows 1)not to deal with it until really needed (lazy eval) 2)partalellize the solution to n threads on m cores. Think list comprehension/generator in Python. Cons: you need more memory than you have data Sequential: you deal with one item at a time, you can deal with an infinite amount of data with a finite amount of memory. Cons: can't parralellize, early eval of things you don't need, you might need to go through the loop more than once.

crimsonalucard 8y ago

Having the power to order instructions introduces the possibility of having bugs that have to do with the order of operations. Getting rid of order gets rid of the bugs. Like how restricting types with type checking gets rid of all type errors.