4 ms·

Even with structural sharing you need to cheat. The program needs to feed that data structure into a black box that is mutating the actual hidden game-state. S

Even with structural sharing you need to cheat. The program needs to feed that data structure into a black box that is mutating the actual hidden game-state. Somewhere in the entire game pipeline there are mutations happening at 60 FPS, and pure FP languages hide this from you by "cheating" while other languages make this fact explicit.

dwohnitmok 7y ago
Other imperative languages do not necessarily make this fact explicit. For example, elsewhere in this thread I present an example of structural sharing with a tree structure. That code could easily be adapted into, say, Java. There is no mutation going on at the language level. And that tree could be the entire game-state. The closest thing to cheating that's going on in that example is that GC is happening and hence memory will be recycled. Note however, that this is a fact not directly accessible to Java, whether you're writing imperative code or functional code. Imperative code is also "cheating" here, where it assumes that each new object instantiation is "new" memory, when in fact it may be old memory that's been reused. If you're writing FP code in Java, eventually you will need to cheat when it comes time to write out your data to the screen and when accepting user input (if you're writing it in Haskell eventually the runtime cheats on your behalf). But if your game-state is an immutable data structure, the update of game-state itself does not require mutability at the language level, even if you're writing in a traditionally imperative language.
- crimsonalucard 7y ago
  >the update of game-state itself does not require mutability at the language level, This is more inline with what I mean. The muteability must happen somewhere whether it's a framework or a language it is being hidden from you via a black box. It doesn't matter whether or not the language is FP or not, it is the paradigm I am talking about as you can do FP in any language. The way you describe it via the GC, is a leaky abstraction. At the language level the immuteable data strucure must exist forever, but underneath this, what is occuring is mutation behind a black box. If at the language level where all things are immuteable you treat everything as the abstraction says you should and reference past state your program will overflow. Therefore in order to do your technique properly you must know what's going on underneath in order to properly use the functional abstraction in this way as the leak from the blackbox limits you in what can be done in the FP paradigm.
  - dwohnitmok 7y ago
    The situation is not any different for an imperative GC language. They don't offer any way of destroying an object, so the abstraction says an object once instantiated should stay around forever. And e.g. the JVM has a setting for this (see the Epsilon GC). Of course you eventually run out of memory and blow up, even in imperative code. Indeed, even the choice to say have an operation like x++ not allocate additional memory is implementation defined. In Python (and in Java if this is an Integer), sometimes this is an object that is not mutated in place, but rather a new copy is created. This is very implementation dependent. For most varieties of the JVM this behavior kicks in only once your integer is greater than 127. Below it they all share a pool of the same integers. In those cases x++ is only a constant space operation because of GC, not because of imperative semantics. It's all black boxes everywhere. The distinction here is between GC and non-GC not functional and imperative. In a deeper sense our conversation is a sort of category error. Immutability and mutability are both examples of language-level semantics that are implemented in many different ways. Mutability can be implemented by an immutable underlying system (the prime example of this is Copy-on-Write file systems) and immutability can be implemented by a mutable underlying system. The implementation layer has its own set of semantics distinct from the semantics of the language itself. The whole spark that drove all this, is that at the moment of update immutable structural sharing is generally not implemented with mutability, which while never explicitly stated, was what I guessed galaxyLogic was getting at (their questions all seemed to stem from this assumption). Mutability may come into play later, but at the time of update, there is no mutability. I emphasize this, because this is not how React works. With React you're correct that each update to the virtual DOM results in ultimately a mutable update to the real DOM. This is not how structural sharing with immutable data structures works. There is no such one-to-one correspondence. It is generally not the case that, e.g. there is a single mutable array backing a family of immutable data structures with complex book-keeping to maintain a facade of immutability (although of course if you wanted to you could implement it this way). The virtual DOM by itself is often implemented with structural sharing but that's a different story.
    - crimsonalucard 7y ago
      I am 100% aware of what you're talking about and the differences between what you're talking about and react. You are largely correct on the GC and non-GC distinction. However, even accounting for this a cheat must still occur somewhere else in the pipeline. That immutable data structure you're talking about must be fed to IO which updates the screen. This is equivalent to updating the virtual DOM. This is where the one to one correspondence forms with FRP. The "cheat" so to speak... whether a framework or an outside runtime implements it no computer system can truly implement FP and they all must cheat. You could argue that we're not talking about things at that level of abstraction but I would argue that for gaming and systems level programming, this level of abstraction is critical to the topic at hand.
whateveracct 7y ago
> Somewhere in the entire game pipeline there are mutations happening at 60 FPS, and pure FP languages hide this from you by "cheating" while other languages make this fact explicit. This is incorrect on multiple levels. 1. You don't need to perform mutations at all. You can have a recursive loop w/only immutable state. I suppose the compiler ends up mutating some memory due to TCE, but that's a principled transformation and not "cheating" or bad in any way compared to writing the code mutably up front. 2. When you do use it, mutation is _always_ very explicit in Haskell and Idris. It is _more_ explicit than other languages! You can' tell if a Go function modifies its inputs or some global state without reading its definition. You can with Haskell :)
- crimsonalucard 7y ago
  > This is incorrect on multiple levels. I'm very sorry but you are actually incorrect on every level. >1. You don't need to perform mutations at all. You can have a recursive loop w/only immutable state. I suppose the compiler ends up mutating some memory due to TCE, but that's a principled transformation and not "cheating" or bad in any way compared to writing the code mutably up front. Suppose? The GC must delete unused values or there will be a memory overflow. This is cheating behind a blackbox. The minute you start using those "immuteable values" the cheat is revealed via leaky abstraction. >2. When you do use it, mutation is _always_ very explicit in Haskell and Idris. It is _more_ explicit than other languages! You can' tell if a Go function modifies its inputs or some global state without reading its definition. You can with Haskell :) In haskell and Idris, you cannot do mutation period. So your statement is categorically wrong. When haskell or Idris "does mutation" it must feed it into an abstraction outside of the core language, aka cheating. This is what you mean by "very explicit"

dwohnitmok 7y ago

Other imperative languages do not necessarily make this fact explicit. For example, elsewhere in this thread I present an example of structural sharing with a tree structure. That code could easily be adapted into, say, Java. There is no mutation going on at the language level. And that tree could be the entire game-state. The closest thing to cheating that's going on in that example is that GC is happening and hence memory will be recycled. Note however, that this is a fact not directly accessible to Java, whether you're writing imperative code or functional code. Imperative code is also "cheating" here, where it assumes that each new object instantiation is "new" memory, when in fact it may be old memory that's been reused. If you're writing FP code in Java, eventually you will need to cheat when it comes time to write out your data to the screen and when accepting user input (if you're writing it in Haskell eventually the runtime cheats on your behalf). But if your game-state is an immutable data structure, the update of game-state itself does not require mutability at the language level, even if you're writing in a traditionally imperative language.

crimsonalucard 7y ago
>the update of game-state itself does not require mutability at the language level, This is more inline with what I mean. The muteability must happen somewhere whether it's a framework or a language it is being hidden from you via a black box. It doesn't matter whether or not the language is FP or not, it is the paradigm I am talking about as you can do FP in any language. The way you describe it via the GC, is a leaky abstraction. At the language level the immuteable data strucure must exist forever, but underneath this, what is occuring is mutation behind a black box. If at the language level where all things are immuteable you treat everything as the abstraction says you should and reference past state your program will overflow. Therefore in order to do your technique properly you must know what's going on underneath in order to properly use the functional abstraction in this way as the leak from the blackbox limits you in what can be done in the FP paradigm.
- dwohnitmok 7y ago
  The situation is not any different for an imperative GC language. They don't offer any way of destroying an object, so the abstraction says an object once instantiated should stay around forever. And e.g. the JVM has a setting for this (see the Epsilon GC). Of course you eventually run out of memory and blow up, even in imperative code. Indeed, even the choice to say have an operation like x++ not allocate additional memory is implementation defined. In Python (and in Java if this is an Integer), sometimes this is an object that is not mutated in place, but rather a new copy is created. This is very implementation dependent. For most varieties of the JVM this behavior kicks in only once your integer is greater than 127. Below it they all share a pool of the same integers. In those cases x++ is only a constant space operation because of GC, not because of imperative semantics. It's all black boxes everywhere. The distinction here is between GC and non-GC not functional and imperative. In a deeper sense our conversation is a sort of category error. Immutability and mutability are both examples of language-level semantics that are implemented in many different ways. Mutability can be implemented by an immutable underlying system (the prime example of this is Copy-on-Write file systems) and immutability can be implemented by a mutable underlying system. The implementation layer has its own set of semantics distinct from the semantics of the language itself. The whole spark that drove all this, is that at the moment of update immutable structural sharing is generally not implemented with mutability, which while never explicitly stated, was what I guessed galaxyLogic was getting at (their questions all seemed to stem from this assumption). Mutability may come into play later, but at the time of update, there is no mutability. I emphasize this, because this is not how React works. With React you're correct that each update to the virtual DOM results in ultimately a mutable update to the real DOM. This is not how structural sharing with immutable data structures works. There is no such one-to-one correspondence. It is generally not the case that, e.g. there is a single mutable array backing a family of immutable data structures with complex book-keeping to maintain a facade of immutability (although of course if you wanted to you could implement it this way). The virtual DOM by itself is often implemented with structural sharing but that's a different story.
  - crimsonalucard 7y ago
    I am 100% aware of what you're talking about and the differences between what you're talking about and react. You are largely correct on the GC and non-GC distinction. However, even accounting for this a cheat must still occur somewhere else in the pipeline. That immutable data structure you're talking about must be fed to IO which updates the screen. This is equivalent to updating the virtual DOM. This is where the one to one correspondence forms with FRP. The "cheat" so to speak... whether a framework or an outside runtime implements it no computer system can truly implement FP and they all must cheat. You could argue that we're not talking about things at that level of abstraction but I would argue that for gaming and systems level programming, this level of abstraction is critical to the topic at hand.

whateveracct 7y ago

> Somewhere in the entire game pipeline there are mutations happening at 60 FPS, and pure FP languages hide this from you by "cheating" while other languages make this fact explicit. This is incorrect on multiple levels. 1. You don't need to perform mutations at all. You can have a recursive loop w/only immutable state. I suppose the compiler ends up mutating some memory due to TCE, but that's a principled transformation and not "cheating" or bad in any way compared to writing the code mutably up front. 2. When you do use it, mutation is _always_ very explicit in Haskell and Idris. It is _more_ explicit than other languages! You can' tell if a Go function modifies its inputs or some global state without reading its definition. You can with Haskell :)

crimsonalucard 7y ago
> This is incorrect on multiple levels. I'm very sorry but you are actually incorrect on every level. >1. You don't need to perform mutations at all. You can have a recursive loop w/only immutable state. I suppose the compiler ends up mutating some memory due to TCE, but that's a principled transformation and not "cheating" or bad in any way compared to writing the code mutably up front. Suppose? The GC must delete unused values or there will be a memory overflow. This is cheating behind a blackbox. The minute you start using those "immuteable values" the cheat is revealed via leaky abstraction. >2. When you do use it, mutation is _always_ very explicit in Haskell and Idris. It is _more_ explicit than other languages! You can' tell if a Go function modifies its inputs or some global state without reading its definition. You can with Haskell :) In haskell and Idris, you cannot do mutation period. So your statement is categorically wrong. When haskell or Idris "does mutation" it must feed it into an abstraction outside of the core language, aka cheating. This is what you mean by "very explicit"