5 ms·

I think a lot of people gloss over a bit too quickly on the actual implications at a hardware level on what it means to have immutable state. If you have 10mb o

by RyanZAG 13y ago

I think a lot of people gloss over a bit too quickly on the actual implications at a hardware level on what it means to have immutable state. If you have 10mb of numbers that you need to add 1 to, immutable state means you now have 20mb of numbers guaranteed. Allowing for mutable state means you can stick to the 10mb and mutate it. So in general, forced immutable state means that any class of problems which require both high performance and a lot of mutation are going to be very poor candidates for functional programming. This is actually a large share of embedded programming and why the OP probably hasn't found that much use for it - embedded programming often comes down to accepting large amounts of data from sensors and manipulating it. The problems where functional programming shine are where you have a chunk of data and need to create an answer from it. Given 10mb of data, should I do X or Y? Functional programming is a very good tool here because of aspects such as composability allowing for extra steps to be chained into a calculation, and immutable data ensuring that multiple steps can be run on the same data at the same time. Hopefully that helps a bit in deciding when functional would be useful or less useful.

yetanotherphd 13y ago
Totally agree on the hardware implementation. Mutable state has two uses. First, when what you are modelling really has state the varies with time (e.g. real world stuff, UI stuff). Second, as a kind of optimization. One good reason for learning FP is that you think more clearly about what mutable state you are using and why. For example, OOP programmers tend to instinctively write obj.setX(x) obj.doG() y = obj.doF() when it could be done as y = F(G(x)) They instinctively cache G(x) in case they need it later, even though this never actually happens.
- fleitz 13y ago
  State rarely varies with time other than the wall clock, mostly in between time X and Y some events happened. With FP systems you generally have to model these things explicitly and attach a particular time to a particular state which makes the entire system much easier to reason about. Cached state really bothers me because invariably even after caching it, the state can't be reused because of the difficulty of reasoning about the whole system. I think in reality the appeal of FP is that the people who use it are generally more experienced programmers who tend not to make too much mess in non-FP languages anyway. The benefits are more the peer group than anything else.
  - RyanZAG 13y ago
    > I think in reality the appeal of FP is that the people who use it are generally more experienced programmers who tend not to make too much mess in non-FP languages anyway. The benefits are more the peer group than anything else. Careful, you're arguing here that FP is better because the person using it is a better person. There is nothing wrong with that statement if it is actually an unbiased fact, but simply choosing to use or not use FP would automatically bias you towards declaring that true or false. Avoiding that line of reasoning is a good idea because it's not useful. Stick to the merits of FP itself.
    - yetanotherphd 13y ago
      Actually I think the poster is right, and I don't think we should avoid all lines of argument that might be subject to personal bias. The poster was saying that FP has a certain cachet (no pun intended) that is probably due to the quality of the average programmer. It's a bit like if someone was asked to explain higher salaries in Silicon Valley. Are we allowed to refer to the quality of programmers? Of course there is a risk of personal bias, but how could one have this discussion without referring to this factor?
      - RyanZAG 13y ago
        You'd have to bring in actual results: programmers in SV create great products that are widely used around the world. This could be used as evidence to imply they are better. FP is a bit tougher here - the vast majority of programs used by the general public are not FP. You could argue that FP is 'newer' and not had time to create these widely used programs yet - but FP is far from new. Basically there is no real world evidence to back up that FP programmers are higher skilled and only personal biases and assumptions.
        yetanotherphd 13y ago
        I find that a bit limiting, I would rather hear people's opinions even if they might be subject to bias. And I don't think that an opinion based on personal experience is "only personal biases and assumptions". It is also important that your approach be uniformly enforced: you would have to encourage people to refrain from saying that FP programmers have the same skill level as non-FP programmers, since that opinion is also not based on any evidence.
jetru 13y ago
Don't the compilers optimize this? I always believed functional programming to be popular among compiler experts because it's easier to write certain optimizations on a program because of it's many properties like state not changing etc. I don't know if this leads to realistically faster programs in real life.
- yetanotherphd 13y ago
  That is just theory. In practice, it is going to be very hard for the compiler to know, at the time that you change a single value in a huge array, that you are never going to refer to the old array, and so it can just mutate the array.
MichaelGG 13y ago
Something like "map myints (+ 1)" can be performed in a mutable way, without compromising on functional purity. (So long you're not using the old values afterwards, of course.) Not all compilers perform such optimizations, but there's no fundamental conflict. I believe Haskell's GHC compiler has "fusion" which allows it to wrap chains of maps/filters/folds into a single tight loop. That way you keep functional style, but get performance of writing it imperatively.
- RyanZAG 13y ago
  You're getting a bit bogged down in details, I meant it more as a general case. There are numerous cases where it is simply more efficient to be operating directly on data - the most used example I can think of are fragment and vertex shaders. It's irrelevant to the issue anyway though: simply having the ability to do something does not make it the best way to do something. You could code in a composable and immutable way using FORTRAN or COBOL if you tried hard enough. The OP was asking for cases where you'd prefer to be using FP over the type of code he is used to. Manipulating blobs of sensor data are simply unlikely to be a productive use of FP - although it could certainly be done. However, calculating statistics from that data is going to be a place where FP would shine and would be a good choice for it. Not everything is a nail simply because you can spend hours hitting it with enough transformations to make it look like one. EDIT: Thinking about it, fragment and vertex shaders actually seem like a very good place to use FP.
  - MichaelGG 13y ago
    Even when doing direct mutation of a byte array, FP can come in handy. The key part is being able to pass around and return functions. While I don't have experience "manipulating blobs of sensor data", most code can benefit from passing functions around and using closures. Even in otherwise imperative code, using folds and maps may make things clearer. Although, it might not be practical due to performance reasons.
marcosdumay 13y ago
> If you have 10mb of numbers that you need to add 1 to, immutable state means you now have 20mb of numbers guaranteed. Immutable state also means that you don't need to add 1 to the numbers you won't use, and that you can discard the old numbers if you only wanted the incremented ones. Garbage colletors and run-time optimizers are added complexity, and may be too much for an embbebed system (or maybe not, controlers are getting bigger each day). But that's a context dependent conclusion, not a certainty.
wesnerm2 13y ago
Immutable state does not necessarily imply 20mb of numbers guaranteed. It depends on the compiler and on the implementation of data structures. Functional data structures can use mutation behind the scenes to produce a facade of immutability. Clojure has an efficient "immutable" array data structure offering constant-time (~log32 n) performance and better space usage. Shallow binding is another general technique that produces space and time performance nearly identical to corresponding mutable data structures by wrapping the mutable data structure with older versions storing a pointer to the incrementally newer version plus the incremental change. Both of these use mutation behind the scenes. It's not necessary to sacrifice performance to program in a functional way.
runT1ME 13y ago
> If you have 10mb of numbers that you need to add 1 to immutable state means you now have 20mb of numbers guaranteed You'd only have 20mb of 'numbers' if you needed to keep a reference to the original data structure. Otherwise its' garbage. >So in general, forced immutable state means that any class of problems which require both high performance and a lot of mutation are going to be very poor candidates for functional programming FP does not necessitate 'immutable state', even in pure languages like Haskell. What it enforces is purity, or more concrete, referential transparency. Often the easiest way to obtain referential transparency is immutable data (non destructive data structures, etc), but you can have mutable data and maintain referential transparency for high performance (see ST Monad).
wonderzombie 13y ago
That's a somewhat naive view of immutability. Garbage collection should take care of the 10mb of numbers you aren't using anymore. True, there are issues for more complex data structures, but that's why persistent data structures were invented. The goal is only to retain what you use. This isn't that different from an imperative world. If someone somewhere has a reference to some part of that data (or may have a reference), what are you going to do? Presumably you'll make a copy. In an immutable world, adding references to an existing of data is trivial. So either you accrete more data, in which case you're in the same place as the imperative world, or it's not new data, no one is using it, and you can throw it out. In practice it's probably more complex than that, and depends on the language implementation. There's also something to be said for something which, implementation-wise, mutates in place when possible but semantically acts as if it is immutable. I'm not advocating for FP in embedded systems, just trying to flesh out more detail about the trade-off here. I think even if you don't program with a language with immutability, it may be worth asking questions (which may have a simple answer in the affirmative!) about the extent to which you need mutability in a given situation vs not. "Don't optimize yet" and all that.

by RyanZAG 13y ago

yetanotherphd 13y ago

Totally agree on the hardware implementation. Mutable state has two uses. First, when what you are modelling really has state the varies with time (e.g. real world stuff, UI stuff). Second, as a kind of optimization. One good reason for learning FP is that you think more clearly about what mutable state you are using and why. For example, OOP programmers tend to instinctively write obj.setX(x) obj.doG() y = obj.doF() when it could be done as y = F(G(x)) They instinctively cache G(x) in case they need it later, even though this never actually happens.

fleitz 13y ago
State rarely varies with time other than the wall clock, mostly in between time X and Y some events happened. With FP systems you generally have to model these things explicitly and attach a particular time to a particular state which makes the entire system much easier to reason about. Cached state really bothers me because invariably even after caching it, the state can't be reused because of the difficulty of reasoning about the whole system. I think in reality the appeal of FP is that the people who use it are generally more experienced programmers who tend not to make too much mess in non-FP languages anyway. The benefits are more the peer group than anything else.
- RyanZAG 13y ago
  > I think in reality the appeal of FP is that the people who use it are generally more experienced programmers who tend not to make too much mess in non-FP languages anyway. The benefits are more the peer group than anything else. Careful, you're arguing here that FP is better because the person using it is a better person. There is nothing wrong with that statement if it is actually an unbiased fact, but simply choosing to use or not use FP would automatically bias you towards declaring that true or false. Avoiding that line of reasoning is a good idea because it's not useful. Stick to the merits of FP itself.
  - yetanotherphd 13y ago
    Actually I think the poster is right, and I don't think we should avoid all lines of argument that might be subject to personal bias. The poster was saying that FP has a certain cachet (no pun intended) that is probably due to the quality of the average programmer. It's a bit like if someone was asked to explain higher salaries in Silicon Valley. Are we allowed to refer to the quality of programmers? Of course there is a risk of personal bias, but how could one have this discussion without referring to this factor?
    - RyanZAG 13y ago
      You'd have to bring in actual results: programmers in SV create great products that are widely used around the world. This could be used as evidence to imply they are better. FP is a bit tougher here - the vast majority of programs used by the general public are not FP. You could argue that FP is 'newer' and not had time to create these widely used programs yet - but FP is far from new. Basically there is no real world evidence to back up that FP programmers are higher skilled and only personal biases and assumptions.
      - yetanotherphd 13y ago
        I find that a bit limiting, I would rather hear people's opinions even if they might be subject to bias. And I don't think that an opinion based on personal experience is "only personal biases and assumptions". It is also important that your approach be uniformly enforced: you would have to encourage people to refrain from saying that FP programmers have the same skill level as non-FP programmers, since that opinion is also not based on any evidence.

jetru 13y ago

Don't the compilers optimize this? I always believed functional programming to be popular among compiler experts because it's easier to write certain optimizations on a program because of it's many properties like state not changing etc. I don't know if this leads to realistically faster programs in real life.

yetanotherphd 13y ago
That is just theory. In practice, it is going to be very hard for the compiler to know, at the time that you change a single value in a huge array, that you are never going to refer to the old array, and so it can just mutate the array.

MichaelGG 13y ago

Something like "map myints (+ 1)" can be performed in a mutable way, without compromising on functional purity. (So long you're not using the old values afterwards, of course.) Not all compilers perform such optimizations, but there's no fundamental conflict. I believe Haskell's GHC compiler has "fusion" which allows it to wrap chains of maps/filters/folds into a single tight loop. That way you keep functional style, but get performance of writing it imperatively.

RyanZAG 13y ago
You're getting a bit bogged down in details, I meant it more as a general case. There are numerous cases where it is simply more efficient to be operating directly on data - the most used example I can think of are fragment and vertex shaders. It's irrelevant to the issue anyway though: simply having the ability to do something does not make it the best way to do something. You could code in a composable and immutable way using FORTRAN or COBOL if you tried hard enough. The OP was asking for cases where you'd prefer to be using FP over the type of code he is used to. Manipulating blobs of sensor data are simply unlikely to be a productive use of FP - although it could certainly be done. However, calculating statistics from that data is going to be a place where FP would shine and would be a good choice for it. Not everything is a nail simply because you can spend hours hitting it with enough transformations to make it look like one. EDIT: Thinking about it, fragment and vertex shaders actually seem like a very good place to use FP.
- MichaelGG 13y ago
  Even when doing direct mutation of a byte array, FP can come in handy. The key part is being able to pass around and return functions. While I don't have experience "manipulating blobs of sensor data", most code can benefit from passing functions around and using closures. Even in otherwise imperative code, using folds and maps may make things clearer. Although, it might not be practical due to performance reasons.

marcosdumay 13y ago

> If you have 10mb of numbers that you need to add 1 to, immutable state means you now have 20mb of numbers guaranteed. Immutable state also means that you don't need to add 1 to the numbers you won't use, and that you can discard the old numbers if you only wanted the incremented ones. Garbage colletors and run-time optimizers are added complexity, and may be too much for an embbebed system (or maybe not, controlers are getting bigger each day). But that's a context dependent conclusion, not a certainty.

wesnerm2 13y ago

Immutable state does not necessarily imply 20mb of numbers guaranteed. It depends on the compiler and on the implementation of data structures. Functional data structures can use mutation behind the scenes to produce a facade of immutability. Clojure has an efficient "immutable" array data structure offering constant-time (~log32 n) performance and better space usage. Shallow binding is another general technique that produces space and time performance nearly identical to corresponding mutable data structures by wrapping the mutable data structure with older versions storing a pointer to the incrementally newer version plus the incremental change. Both of these use mutation behind the scenes. It's not necessary to sacrifice performance to program in a functional way.

runT1ME 13y ago

> If you have 10mb of numbers that you need to add 1 to immutable state means you now have 20mb of numbers guaranteed You'd only have 20mb of 'numbers' if you needed to keep a reference to the original data structure. Otherwise its' garbage. >So in general, forced immutable state means that any class of problems which require both high performance and a lot of mutation are going to be very poor candidates for functional programming FP does not necessitate 'immutable state', even in pure languages like Haskell. What it enforces is purity, or more concrete, referential transparency. Often the easiest way to obtain referential transparency is immutable data (non destructive data structures, etc), but you can have mutable data and maintain referential transparency for high performance (see ST Monad).

wonderzombie 13y ago

That's a somewhat naive view of immutability. Garbage collection should take care of the 10mb of numbers you aren't using anymore. True, there are issues for more complex data structures, but that's why persistent data structures were invented. The goal is only to retain what you use. This isn't that different from an imperative world. If someone somewhere has a reference to some part of that data (or may have a reference), what are you going to do? Presumably you'll make a copy. In an immutable world, adding references to an existing of data is trivial. So either you accrete more data, in which case you're in the same place as the imperative world, or it's not new data, no one is using it, and you can throw it out. In practice it's probably more complex than that, and depends on the language implementation. There's also something to be said for something which, implementation-wise, mutates in place when possible but semantically acts as if it is immutable. I'm not advocating for FP in embedded systems, just trying to flesh out more detail about the trade-off here. I think even if you don't program with a language with immutability, it may be worth asking questions (which may have a simple answer in the affirmative!) about the extent to which you need mutability in a given situation vs not. "Don't optimize yet" and all that.