3 ms·

Brian's Functional Brain

24 points by edw519 17y ago

Tichy 17y ago
"But we're doing this functionally, so we need to walk over the entire board, apply the rules and return an entire board." This is why I am still wary of adopting these languages with "fixed memory". Ok for a cellular automaton there happened to be a workaround, but in general, isn't all data connected somehow? So how does one handle that in a big system with lot's of data? I can not change ALL data in every iteration. (Specific example: suppose I want to write a multiplayer game server - for every move a player makes, I would have to replace ALL game objects, player object, and so on???). I looked a bit into Erlang and it seems there could be a workaround by having lots of threads, so one only needs to change the dataset of one thread at a time. But how do Clojure or Haskell handle that kind of thing (I don't think they encourage thousands of threads as Erlang does?). I think erlang also had a special kind of data structure that would also allow for kind of mutable data per thread, but really, it all sounded a bit messy to work with. How does the paradigm hold up anyway? Isn't there one point eventually when the processes still interfere with each other? For example when accessing the database?
- davidw 17y ago
  What Erlang does is have each "thread" (they're really called processes and they're neither system processes nor system threads, but Erlang processes) have a loop that sends data back to itself with whatever modifications may have been requested by the user, thus simulating a variable with state, to some degree. It also does have per process ways to just plain store data, but they're severely frowned upon.
- runevault 17y ago
  Clojure's data structures handle this by sharing state across different copies of the structure. So say I have a hashmap with 15 k/v pairs in it, then I change one of the values in an existing key. Only the path to and that k/v pair are changed, the rest are just pointers to the same items that were already existing, minimizing the cost of "changing" it and allowing concurrency to still work without contention issues.
- jerf 17y ago
  The answer to your very good question is beyond the scope of what can be covered in an HN post, so I would suggest that you look at http://en.wikipedia.org/wiki/Purely_functional http://en.wikipedia.org/wiki/Purely_functional for a quick answer, or http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf for a more in-depth answer. After that, you'll know what to Google for. I particularly recommend the discussion of tree updates in the Wikipedia article to start with, since it has good diagrams. That said... multidimensional arrays continues to be a sore point with functional programs, as far as I know. A variety of purely functional structures exist that can replicate some parts of the performance guarantees of traditional arrays, but I am not aware of anything that can cover the full gamut of uses for a multidimensional array. Usually in this case there is a functional structure that does what you really need, but ISTM that when you find yourself needing a multidimensional array, it's because A: it's huge B: you need fast O(1) updating and C: you need fast O(1) access and that combo is just killer. (And nowadays, D: you need cache coherence control comes up too.) Oh, and if I'm reading your question correctly, Erlang process isolation is not really related to your question. However, I will point out that in Erlang, two processes will not access the database "at the same time". Two processes will send messages to the database Erlang-process, which will serve them in order and send back the replies. When processes and messaging are cheap you change how you do things; a lot more things get wrapped in processes (files, socket connections, foreign libraries, pipes to externally running programs ("ports" in Erlang speak, rather unfortunately), etc.) than you'd expect. It's the fundamental primitive for avoiding contention, it gets used a lot!
- jdminhbg 17y ago
  In Clojure, you can handle this with STM holding the state of the world, where changes are wrapped in transactions. Rich Hickey's talk on the subject is here: http://blip.tv/file/812787 http://blip.tv/file/812787 The first half is sort of a description of the Clojure philosophy, the second half is building an ant simulation very similar to this game of life but with STM instead.
MindTwister 17y ago
Just curious, isn't this usually called Conway's game of life?
- tel 17y ago
  Conway's Game of Life has a slightly different rule set. Cellular Automata is the blanket term for things like this and there are a pretty incredible variety of rulesets.
- jacquesm 17y ago
  At first reading the rules seem to be subtly different.

24 points by edw519 17y ago

Tichy 17y ago

"But we're doing this functionally, so we need to walk over the entire board, apply the rules and return an entire board." This is why I am still wary of adopting these languages with "fixed memory". Ok for a cellular automaton there happened to be a workaround, but in general, isn't all data connected somehow? So how does one handle that in a big system with lot's of data? I can not change ALL data in every iteration. (Specific example: suppose I want to write a multiplayer game server - for every move a player makes, I would have to replace ALL game objects, player object, and so on???). I looked a bit into Erlang and it seems there could be a workaround by having lots of threads, so one only needs to change the dataset of one thread at a time. But how do Clojure or Haskell handle that kind of thing (I don't think they encourage thousands of threads as Erlang does?). I think erlang also had a special kind of data structure that would also allow for kind of mutable data per thread, but really, it all sounded a bit messy to work with. How does the paradigm hold up anyway? Isn't there one point eventually when the processes still interfere with each other? For example when accessing the database?

davidw 17y ago
What Erlang does is have each "thread" (they're really called processes and they're neither system processes nor system threads, but Erlang processes) have a loop that sends data back to itself with whatever modifications may have been requested by the user, thus simulating a variable with state, to some degree. It also does have per process ways to just plain store data, but they're severely frowned upon.
runevault 17y ago
Clojure's data structures handle this by sharing state across different copies of the structure. So say I have a hashmap with 15 k/v pairs in it, then I change one of the values in an existing key. Only the path to and that k/v pair are changed, the rest are just pointers to the same items that were already existing, minimizing the cost of "changing" it and allowing concurrency to still work without contention issues.
jerf 17y ago
The answer to your very good question is beyond the scope of what can be covered in an HN post, so I would suggest that you look at http://en.wikipedia.org/wiki/Purely_functional http://en.wikipedia.org/wiki/Purely_functional for a quick answer, or http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf for a more in-depth answer. After that, you'll know what to Google for. I particularly recommend the discussion of tree updates in the Wikipedia article to start with, since it has good diagrams. That said... multidimensional arrays continues to be a sore point with functional programs, as far as I know. A variety of purely functional structures exist that can replicate some parts of the performance guarantees of traditional arrays, but I am not aware of anything that can cover the full gamut of uses for a multidimensional array. Usually in this case there is a functional structure that does what you really need, but ISTM that when you find yourself needing a multidimensional array, it's because A: it's huge B: you need fast O(1) updating and C: you need fast O(1) access and that combo is just killer. (And nowadays, D: you need cache coherence control comes up too.) Oh, and if I'm reading your question correctly, Erlang process isolation is not really related to your question. However, I will point out that in Erlang, two processes will not access the database "at the same time". Two processes will send messages to the database Erlang-process, which will serve them in order and send back the replies. When processes and messaging are cheap you change how you do things; a lot more things get wrapped in processes (files, socket connections, foreign libraries, pipes to externally running programs ("ports" in Erlang speak, rather unfortunately), etc.) than you'd expect. It's the fundamental primitive for avoiding contention, it gets used a lot!
jdminhbg 17y ago
In Clojure, you can handle this with STM holding the state of the world, where changes are wrapped in transactions. Rich Hickey's talk on the subject is here: http://blip.tv/file/812787 http://blip.tv/file/812787 The first half is sort of a description of the Clojure philosophy, the second half is building an ant simulation very similar to this game of life but with STM instead.

MindTwister 17y ago

Just curious, isn't this usually called Conway's game of life?

tel 17y ago
Conway's Game of Life has a slightly different rule set. Cellular Automata is the blanket term for things like this and there are a pretty incredible variety of rulesets.
jacquesm 17y ago
At first reading the rules seem to be subtly different.