Could someone quickly summarize how a stateful game is best implemented in a purely functional language, like here?
Is there a main tail-recursive function which takes any inputs that have appeared since the last iteration and adds them to the arguments for the next recursive call? The global state would evolve as the arguments of that tail-recursive function over time?
Any state-evolution would need to be made by creating new data-structures out of existing ones, not by modifying the existing data-structures, to be "pure". So in essence the whole state of game-world would need to be copied for each iteration? What's the trick that makes it efficient enough to be usable?
It's a bunch of trees. You end up only copying the spine (from modified leaf to root). containers & unordered-containers are the popular packages.
It's also pretty common to still use mutability (the vector package in Haskell is hugely popular) but it tends to be principled and/or abstracted out because its use is explicitly tagged in type signatures. And those APIs can get even better once LinearTypes land.
In gamedev, both can be useful. Vector is useful for performance and GC relief (when Storable/Unboxed). Immutable structures are still useful when backtracking is needed since they make it trivial and performant in that setting. A useful property for debugging, "training mode", replays, netcode etc.
Recursion is used but not necessarily self tail recursion thanks to general TCE.
I believe they are just saying that tail calls can be used in a mutually recursive way without consuming unbounded memory. They said "self tail recursion" is not necessary but you interpreted it as "tail recursion is not necessary".
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.
Eventually you need to cheat (or more accurately in the case of Haskell you need an impure runtime system that can interpret all of your pure code) to interface with the outside world, but not in the scenario the parent comment has laid out so far.
Persistent data structures (structural sharing) is not cheating. Persistent data structures are immutable just as if updates to the data structure had been implemented by wholesale copying of a data structure rather than just updating the part that needs updating.
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.
> 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 :)
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"
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.
>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.
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.
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.
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.
While it is perhaps useful to think of tail-call elimination as changing a recursive function into a while loop is a useful first approximation (and is how it is implemented in e.g. Scala), this is not really an accurate picture of tail-call elimination in general. Indeed it breaks down when considering mutually recursive functions.
Tail-call elimination is simply the observation that in a tail position you do not keep a reference to the parent function around after you've called the child function.
If function calls happen on the heap instead of the stack for example, then tail-call elimination is done simply as a matter of course by the garbage collector.
>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.
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.
>Choosing a language for performance first when developing your game is silly.
It is absolutely not. Components of the game can be done with an interpreted language but if performance is key, which it is for triple A games, then the core language is important.
Scripting languages in games tend to deal with IO a lot. If your program contains too much IO it negates almost all the benefits of FP. Procedural programming is better for modeling temporal phenomena which is the core subject of what most of these "scripts" are attempting to model.
>But saying "oh computers are inherently mutable" is a pretty worthless and shallow statement.
I beg to differ. Saying otherwise is the 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)
There are many things that hinder it but not preclude it. By common sense in general, it is harder for FP to get more performance out of the system. The logic is simple, the functor from functional programs to assembly language programs cannot be written in a way where it is bijective meaning that functional primitives have to map to another category where the objects are ordered tuples of multiple assembly language commands.
In C you can very much write a program that is in spirit bijective with assembly. By that logic FP in general will be harder to control because every FP primitive means an almost unpredictable amount of assembly instructions. Performance improvements will tend to appear as leaky abstractions or hacks in FP. Especially with the call by need model in Haskell optimization is even harder.
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?
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.
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/...
The main loop is probably a tail recursive function.
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
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?
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
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.
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.
> 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.
A mutable tree requires the same logarithmic time factor to update a leaf, because it also requires logarithmic time to access the leaf. It seems like the real difference between the mutable and the immutable structure is that the mutable structure requires O(1) space to do the update, while the immutable one requires O(log n) space in addition to the common requirement of O(log n) time.
Sort of. Structural sharing generally actually results in amortized constant space operations if you don't need the copies. In this case, if you aren't actually using the other tree, the nodes could be GC-ed. In the most ideal case they could be GC-ed as you're constructing the new nodes, though I imagine this essentially never happens (hence amortized). But regardless you're right that the thing to focus on is space rather than time when looking at how it would be different in an immutable vs mutable context.
Also my comment was incomplete. What I should've added is that most immutable data structures are trees under the hood in some form or another, hence many operations have a logarithmic factor. Mutable data structures provide more options when you want constant time access.
case health <= 0 of
False => pure ()
True => Output $ Death target
This ought to just be:
when (health <= 0) Output $ Death target
It takes years to learn all the general-purpose helper functions in these languages (I'm still discovering new ones after 10 years of Scala), but they can help make code so much clearer. And since they're just plain functions rather than keywords or anything, a reader who doesn't know can just jump through to the definition, which is a one-liner: https://github.com/idris-lang/Idris-dev/blob/master/libs/pre...
> Sadly I didn’t manage to make as much use of this type-level programming as I had hoped I would at the beginning: Idris allows you to gradually refine your types, and I’ve often succumbed to just moving on to the next feature as my interest for the game itself grew.
This sounds quite promising. Large amounts of mandatory type level programming makes constructing useful programs hard. That it is opt-in is a good thing, and agrees with my own experiences with Idris, which are on a much smaller scale than the OP's.
I'm fascinated by Idris, dependent types and the promise of massively expanding compile-time guarantees. The compile times mentioned in the article raise a question that I've wondered about, and would love to hear from an expert: are compile times essentially unbounded in languages like Idris? Is it possible (likely?) in practice that wrong or misguided uses of the type system could cause quadratic or exponential scaling of compile times?
Not an expert, but I've played with these languages. The short answer is yes this is possible, but it is also possible already in non-dependently typed languages to do so.
Moreover in practice it's not very common to actually evaluate your functions on large literal inputs at compile time. Indeed it's not very common to evaluate the function on a single value as such at all. Instead it is better to think of your functions as abstract rewrite rules, that allow you to substitute one side with the other. Unlike at runtime, recursive functions do not always need to recurse until their base case.
Therefore it's not actually very common to e.g. have a recursive function recurse many times at compile time. However, when it does happen, yeah your compile times can shoot up, but it's usually fairly obvious what's causing it. Even then, in absolute terms the quantity of calculations involved generally isn't astronomical, it's rather the case that the compiler is far more inefficient at executing your code at compile time than your runtime system is at executing the compiled code.
That being said, dependently typed languages on the whole do tend to have abysmal compile times, but this seems like an implementation issue rather than a fundamental limitation. Efforts like https://github.com/AndrasKovacs/smalltt/blob/master/README.m... make me hopeful this is something that can be solved.
Virtually any compiled programming language has had an infinite-loop bug in the compiler at some point or other. E.g. Java has a notoriously simplistic type system, but still had a famous case.
Typing an ML-like language is technically exponential in the length of the program, but really the way to look at it is that it's exponential in the depth of the most deeply nested block (for certain kinds of block). There's a certain symmetry with how program runtime is naturally exponential in the depth of the most deeply nested loop - and, in the same way, while deeply nested blocks are possible, they're generally bad code.
I've hit troublesome compile times in Scala a couple of times. One of them was due to a naively implemented type-level intersection operation and lead me to abandon that project (I was trying to write a compile-time dependency injection framework, so you'd have a set of types representing what you had already instantiated and a set of types representing what each service needed to instantiate itself, so you could only add a service if you already had all of its dependencies available. But it was all using linear search, since types (in Scala) are not hashable as far as I know, and even if they were, I don't know that I'm up to implementing a hashtable using type-level programming).
Yes, you can make compile times _extremely long_. They're not unbounded, as code you use in types needs to pass the _totality checker_, which proves it terminates. (The totality checker requires code to follow certain formats the checker knows how to solve for, otherwise it would solve the halting problem and therefore it could not exist)
I'm not an expert, but yes compile times can get crazy if you're not careful. In theory, the situation is no different from (ab)use of C++ templates, the Rust macro discussed here, and so on. In practice, whereas C and Rust will choke on a 100kloc function, Idris might choke on a 100-liner, depending on what you're doing. Edwin Brady is currently making steady progress on a new compiler--this time written in Idris itself--that's much faster in practice:
https://github.com/edwinb/Idris2
Compile times are already exponential in Haskell. No need to go to Idris for that. The reason is that type checking is exponential even for the simpler type systems in Haskell or OCaml. The trick is to have deeply nested sequences of `let` expressions in the right hand sides, rather than in the bodies.
But in my experience, it's possible but not likely in practice.
Some functional languages have "id id id id id id id id id..." causing exponential compile times. I know F# does, and Haskell did at one point but doesn't any more.
Languages like Idris and Haskell have a big learning curve along with fixed costs around missing ecosystem. But once you pay those off, they allow for single developers or small teams to manage large amounts of complexity and get lots of things "for free" thanks to their composition- and data-oriented nature. A level editor and scripting engine are actually the exact sorts of things I'd expect Idris or Haskell or the like to make noticeably easier than other languages!
Eh, I'm not sure the level editor/scripting comes from the language so much as the nature of game dev. I've written a hobby 2d engine + game before, level design is a hell of a lot easier if you build an editor to do it in. Same with scripting for enemy behaviors. I wrote one in c++ and another in Java, both ended up with level editors and a limited scripting language designed for my own benefit. Once you have them, it speeds up actual game development immensely.
For language design, fp tends to make things a lot easier to represent. Any parser-type application is going to be a recursive structure with a lot of continuations which is the natural way of coding in a functional lang. If you ever look into language design or compilers, you'll see that things are generally written as sum types in bnf, cnf, etc [0]. Basically all fp langs implement sum types, so you can practically translate theory 1-1 into code. I guess you could think of a level editor as a type of language, it's just so minimal that I don't.
Grief, this is impressive. For the record, I really can’t recommend learning (typed, pure) functional programming on Idris. It’s a whole extra step beyond learning to do Haskell well.
On the contrary, I’d recommend to start with Idris instead.
The design of the language is globally better and way more coherent. It fixes a lot of Haskell “mistakes”.
Check out “Type-Driven Development with Idris” by Edwin Brady himself. The book is truly amazing.
Idris is great, its design is super impressive, and it expanded my mind tremendously in terms of what is possible in programming. We can and should ask much more of our type systems!
It is also way less mature than Haskell, and someone trying to learn it will run into many issues as a result. I mean, read the linked blog post! Needing to regularly restart one's editor, long compile times for even short programs, and difficulties with installation are all issues I also ran into.
(Also, strong agree about the book. It's really well written, and all around excellent)
I would second this. If you've never done pure functional programming before I would hesitate to recommend Idris as your first foray simply because of ergonomic issues with the tooling. Regardless of whether you think Idris the language is suitable for a beginner, it's not a fun experience to deal with the landscape of abandoned libraries, editor integration issues, compiler bugs, etc. if you are already struggling to understand some of the basic principles behind the language.
The only exception is if you use it purely as a companion to the Type-Driven Development book. As long as you don't stray too far from the book you generally won't run into any of these other issues and it's more plausible to think of it as a first foray into pure functional programming.
Idris 2 is supposed to be better in that regard. I could not see in the article if 1 or 2 was used but I think it was 1; 2 is a lot faster and fixed a lot of issues from 1.
I believe the plan is to release an Idris2 edition of the book. The Idris2 repository currently has all of the book code as part of its test suite and is making progress towards compiling all of it (currently 12 of the 15 chapters).
I wouldn't think so. As a beginner you can probably just treat Idris like a superset of Haskell and learn the parts that are common to both. For example you can use the `data T =` syntax and not worry about the more advanced `data T where` syntax for GADTs. You can turn off totality checking. You can use simple data types like lists rather than length-indexed vectors.
I quite like the book Type-Driven Development with Idris by Edwin Brady. It doesn't assume you already know Haskell. But it does teach you a nice mindset of thinking about types first and use that to drive the implementation.
Developer productivity outside, I'm curious if garbage collection (which almost every functional programming language all have) would become an issue. Especially if you're making a 2D platformer, you really don't want to have any sort of frame stuttering.
And yeah, compile times are really a big problem if you're making games, because you need to constantly tweak your game logic and playtest). To be fair C++ also has this issue, but fortunately there are ways to alleviate this problem (minimize template usage, do not use libraries which use template metaprogramming like the notorious Eigen, divide your files into source/header files frequently, etc.)
Unless you’re making a large or complex game, I doubt it will matter. Remember that Minecraft was written in a garbage collected language (although its possible they carefully do object pooling, I’m not sure they did in the early days).
On your second point, some people dynamically recompile C++ too! I guess that code maybe is designed for fast compiling. Many other people use an embedded language like Lua for fast iterations.
Yes. IIRC according to Edwin, he didn’t want to spend too much time on implementing an efficient RTS and decided to focus on his core competency instead to (correctly) bring in qtt.
The result is surprisingly good and fast. Way faster than v1 actually on both compile and run time.
Is there a main tail-recursive function which takes any inputs that have appeared since the last iteration and adds them to the arguments for the next recursive call? The global state would evolve as the arguments of that tail-recursive function over time?
Any state-evolution would need to be made by creating new data-structures out of existing ones, not by modifying the existing data-structures, to be "pure". So in essence the whole state of game-world would need to be copied for each iteration? What's the trick that makes it efficient enough to be usable?