6 ms·

The whole state of the game doesn't need to be copied per se - if you use efficient functional data structures then only the parts of the state you modify are c

The whole state of the game doesn't need to be copied per se - if you use efficient functional data structures then only the parts of the state you modify are copied, the rest of the unchanged data structure is referenced directly.

galaxyLogic 7y ago
Is that what happens by default, or do you need to take care to make it be so? I understand you can create a new car-cdr -list out of existing list and a new element, without having to modify anything. So would implementing the game-state functionally then mostly consist of creating new lists non-destructively? Also still wondering about the 'main loop". Is it a tail-recursive function?
- lalaithion 7y ago
  The common data structures in pure languages are slightly different than what you would find in a stateful language, so you do need to take care to make it so only via what data structures you choose to use. Additionally, the author does say they use Control.ST, which depending how you look at it is either a pure wrapper over stateful operations or stateful looking syntax implemented with technically pure semantics. https://www.microsoft.com/en-us/research/wp-content/uploads/1994/06/lazy-functional-state-threads.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... The main loop is probably a tail recursive function.
  - dwohnitmok 7y ago
    That's not the correct link. Idris' ST is not the same as Haskell's ST. Haskell's ST is a way of introducing locally scoped mutability, which is indistinguishable from immutability to an outside observer, but can offer better performance. Idris' ST is a way of implementing a state machine with statically checked state transitions. http://docs.idris-lang.org/en/latest/st/state.html http://docs.idris-lang.org/en/latest/st/state.html
- dwohnitmok 7y ago
  It happens by default in the sense that all standard library data structures in most functional programming languages implement data sharing so that new versions share any common data with the old version instead of being created by scratch. This is known as being a persistent data structure. Likewise custom types you make (the equivalent of say classes in an OO language) usually are implemented as referring to their subcomponents by reference rather than value (since everything is immutable the two are impossible to distinguish at the language level) and so your custom data structures also get this for free. The only common immutable data structure that does not have a persistent/data sharing implementation is an immutable array (as opposed to a linked list or a tree structure approximating an array), since arrays must be contiguous sequences of memory and therefore parts cannot be shared (unless you count array slicing, where the new array is always a subarray). However, unless you have strict performance requirements, you generally can get away with not using an array, since arrays generally only offer performance benefits if they are primitive arrays (rather than arrays of pointers to other objects). And if you do need a mutable array, there are ways of ensuring that its mutability doesn't spread out and "infect" other components of your system. Generally speaking, yes the main loop ultimately is a tail recursive function. This does not turn out to be much of a constraint. This is because main generally returns Unit (what is called void in e.g. C or Java), and so generally does not make sense to put anywhere except in a tail position since it does not return a useful value to be used elsewhere.
- thaumasiotes 7y ago
  https://www.amazon.com/Purely-Functional-Data-Structures-Okasaki/dp/0521663504 https://www.amazon.com/Purely-Functional-Data-Structures-Oka...
  - galaxyLogic 7y ago
    I see. So, let's say I have a tree with arbitrary number of nodes branching into further nodes and so on. (My 'state') Can I now make a single call to some API-function that gives me an almost identical (immutable) tree as a result except that some leaf somewhere has a modified value, or where some node has been deleted? And, would this internally happen without much copying?
    - dwohnitmok 7y ago
      The answer to all your questions is all "yes" technically, but the way you've worded them makes me think just saying "yes" will be a bit misleading to you. So let's take a real-world example. I'll use pseudo-Scala syntax since that's fairly similar to a lot of imperative languages. Let's construct a tree data structure from scratch and see how to update it. abstract class BinaryTreeOfInts final class Leaf(final value: Int) extends BinaryTreeOfInts final class Node(final value: Int, final left: BinaryTreeOfInts, final right: BinaryTreeOfInts) extends BinaryTreeOfInts All fields here are by reference. So because everything is final here, we've constructed an immutable tree. You cannot update any of these values once it's been constructed. Let's see how you might construct the following binary tree 5 / \ 6 1 / \ 2 3 myTree = Node( 5, Leaf(6) Node( 1, Leaf(2), Leaf(3) ) I want to modify 5 now to be 10 newTree = Node(10, myTree.left, myTree.right) Done. This is effectively one operation. newTree and myTree are both still immutable, but there's a ton of sharing going on. Now this is the best case scenario. Modifying a leaf is the worst case scenario, but even there only requires as many operations as there are levels in your tree, which, as long as you have a fairly balanced tree, only grows logarithmically in the number of elements you have. To illustrate let's make another change, this time changing 3 to 30. anotherTree = Node( newTree.value, newTree.left, Node( newTree.right.value, newTree.right.left, Leaf(30) ) ) Note I've had to instantiate a new Node for each level of the tree, and I've made a new Leaf, but otherwise everything else is shared. Now this is the low-level way of performing these changes. There are various APIs and tricks to make this look a lot cleaner in code so writing this out isn't as tedious, but I figured I'd present the low-level way to make things less magical. BTW, the logarithmic time factor to update a leaf is why you will often see logarithmic factors in time complexities of various operations on immutable data structures.
crimsonalucard 7y ago
You need to cheat. Basically like react, the part that does mutation needs to be a framework segregated from most of the actual logic.
- galaxyLogic 7y ago
  Cheating sounds bad. But if it makes it run faster, without any bad side-effects that would seem ok, and I'm not sure if it should even be called "cheating". Basically as I understand it functional languages must internally "cheat" all the time, because they must run on top of non-functional hardware abstractions. Tail-recursion-elimination happens by turning what looks like a recursive function into a while-loop internally, updating some mutable data.
  - crimsonalucard 7y ago
    >Basically as I understand it functional languages must internally "cheat" all the time, because they must run on top of non-functional hardware abstractions. By cheating I mean functions must eventually execute a side effect and that side effect is usually mutating state. The IO monad is a cheat depending on your perspective. The very pixels on your screen are entities with states: RGB which even a "pure" program like haskell will be modifying. What haskell does is call these pixels IO and it segregates the actual mutation from the rest of the program. This is just my opinion but the main benefits of functional programming lie not in performance but in organization of code or what most programmers refer to as "design." If you're looking for extreme performance FP is not the the way to go. Assembly language is the way to go, but even before that I would pick a procedural language like C long before I use an FP language.
    - whateveracct 7y ago
      Choosing a language for performance first when developing your game is silly. Many games (even AAA) have a lot of logic in some interpreted language. Haskell or Idris can be the equivalent of these (and they're way more performant) and you can easily writing custom asm or C or Rust or whatever via their (very good!) FFIs. But saying "oh computers are inherently mutable" is a pretty worthless and shallow statement. Nothing about that precludes FP, and FP works fine in those settings (Haskell can definitely approach C level performance if you know what you're doing) But you're right that nothing about FP is for performance. I don't think anyone would assume Haskell is inherently faster than C. It makes no sense. The closest you could say is some immutable data structures enable performance without much effort in certain use-cases.

galaxyLogic 7y ago

Is that what happens by default, or do you need to take care to make it be so? I understand you can create a new car-cdr -list out of existing list and a new element, without having to modify anything. So would implementing the game-state functionally then mostly consist of creating new lists non-destructively? Also still wondering about the 'main loop". Is it a tail-recursive function?

lalaithion 7y ago
The common data structures in pure languages are slightly different than what you would find in a stateful language, so you do need to take care to make it so only via what data structures you choose to use. Additionally, the author does say they use Control.ST, which depending how you look at it is either a pure wrapper over stateful operations or stateful looking syntax implemented with technically pure semantics. https://www.microsoft.com/en-us/research/wp-content/uploads/1994/06/lazy-functional-state-threads.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... The main loop is probably a tail recursive function.
- dwohnitmok 7y ago
  That's not the correct link. Idris' ST is not the same as Haskell's ST. Haskell's ST is a way of introducing locally scoped mutability, which is indistinguishable from immutability to an outside observer, but can offer better performance. Idris' ST is a way of implementing a state machine with statically checked state transitions. http://docs.idris-lang.org/en/latest/st/state.html http://docs.idris-lang.org/en/latest/st/state.html
dwohnitmok 7y ago
It happens by default in the sense that all standard library data structures in most functional programming languages implement data sharing so that new versions share any common data with the old version instead of being created by scratch. This is known as being a persistent data structure. Likewise custom types you make (the equivalent of say classes in an OO language) usually are implemented as referring to their subcomponents by reference rather than value (since everything is immutable the two are impossible to distinguish at the language level) and so your custom data structures also get this for free. The only common immutable data structure that does not have a persistent/data sharing implementation is an immutable array (as opposed to a linked list or a tree structure approximating an array), since arrays must be contiguous sequences of memory and therefore parts cannot be shared (unless you count array slicing, where the new array is always a subarray). However, unless you have strict performance requirements, you generally can get away with not using an array, since arrays generally only offer performance benefits if they are primitive arrays (rather than arrays of pointers to other objects). And if you do need a mutable array, there are ways of ensuring that its mutability doesn't spread out and "infect" other components of your system. Generally speaking, yes the main loop ultimately is a tail recursive function. This does not turn out to be much of a constraint. This is because main generally returns Unit (what is called void in e.g. C or Java), and so generally does not make sense to put anywhere except in a tail position since it does not return a useful value to be used elsewhere.
thaumasiotes 7y ago
https://www.amazon.com/Purely-Functional-Data-Structures-Okasaki/dp/0521663504 https://www.amazon.com/Purely-Functional-Data-Structures-Oka...
- galaxyLogic 7y ago
  I see. So, let's say I have a tree with arbitrary number of nodes branching into further nodes and so on. (My 'state') Can I now make a single call to some API-function that gives me an almost identical (immutable) tree as a result except that some leaf somewhere has a modified value, or where some node has been deleted? And, would this internally happen without much copying?
  - dwohnitmok 7y ago
    The answer to all your questions is all "yes" technically, but the way you've worded them makes me think just saying "yes" will be a bit misleading to you. So let's take a real-world example. I'll use pseudo-Scala syntax since that's fairly similar to a lot of imperative languages. Let's construct a tree data structure from scratch and see how to update it. abstract class BinaryTreeOfInts final class Leaf(final value: Int) extends BinaryTreeOfInts final class Node(final value: Int, final left: BinaryTreeOfInts, final right: BinaryTreeOfInts) extends BinaryTreeOfInts All fields here are by reference. So because everything is final here, we've constructed an immutable tree. You cannot update any of these values once it's been constructed. Let's see how you might construct the following binary tree 5 / \ 6 1 / \ 2 3 myTree = Node( 5, Leaf(6) Node( 1, Leaf(2), Leaf(3) ) I want to modify 5 now to be 10 newTree = Node(10, myTree.left, myTree.right) Done. This is effectively one operation. newTree and myTree are both still immutable, but there's a ton of sharing going on. Now this is the best case scenario. Modifying a leaf is the worst case scenario, but even there only requires as many operations as there are levels in your tree, which, as long as you have a fairly balanced tree, only grows logarithmically in the number of elements you have. To illustrate let's make another change, this time changing 3 to 30. anotherTree = Node( newTree.value, newTree.left, Node( newTree.right.value, newTree.right.left, Leaf(30) ) ) Note I've had to instantiate a new Node for each level of the tree, and I've made a new Leaf, but otherwise everything else is shared. Now this is the low-level way of performing these changes. There are various APIs and tricks to make this look a lot cleaner in code so writing this out isn't as tedious, but I figured I'd present the low-level way to make things less magical. BTW, the logarithmic time factor to update a leaf is why you will often see logarithmic factors in time complexities of various operations on immutable data structures.

crimsonalucard 7y ago

You need to cheat. Basically like react, the part that does mutation needs to be a framework segregated from most of the actual logic.

galaxyLogic 7y ago
Cheating sounds bad. But if it makes it run faster, without any bad side-effects that would seem ok, and I'm not sure if it should even be called "cheating". Basically as I understand it functional languages must internally "cheat" all the time, because they must run on top of non-functional hardware abstractions. Tail-recursion-elimination happens by turning what looks like a recursive function into a while-loop internally, updating some mutable data.
- crimsonalucard 7y ago
  >Basically as I understand it functional languages must internally "cheat" all the time, because they must run on top of non-functional hardware abstractions. By cheating I mean functions must eventually execute a side effect and that side effect is usually mutating state. The IO monad is a cheat depending on your perspective. The very pixels on your screen are entities with states: RGB which even a "pure" program like haskell will be modifying. What haskell does is call these pixels IO and it segregates the actual mutation from the rest of the program. This is just my opinion but the main benefits of functional programming lie not in performance but in organization of code or what most programmers refer to as "design." If you're looking for extreme performance FP is not the the way to go. Assembly language is the way to go, but even before that I would pick a procedural language like C long before I use an FP language.
  - whateveracct 7y ago
    Choosing a language for performance first when developing your game is silly. Many games (even AAA) have a lot of logic in some interpreted language. Haskell or Idris can be the equivalent of these (and they're way more performant) and you can easily writing custom asm or C or Rust or whatever via their (very good!) FFIs. But saying "oh computers are inherently mutable" is a pretty worthless and shallow statement. Nothing about that precludes FP, and FP works fine in those settings (Haskell can definitely approach C level performance if you know what you're doing) But you're right that nothing about FP is for performance. I don't think anyone would assume Haskell is inherently faster than C. It makes no sense. The closest you could say is some immutable data structures enable performance without much effort in certain use-cases.