8 ms·
Reconsidering Functional Programming
- hhandoko 11y agoInteresting premise. However, isn't what the author described is similar to event-sourcing?
- loganmhb 11y agoAlong these lines, for me one of the things that makes Clojure stand out is the careful thought that went into state, time and identity in the design of the language. It removes mutability as a default without forcing you to be purely functional all the way down, and gives you tools to manage state changes in ways that are easier to reason about (though still not necessarily easy of course).
- deleted 11y ago[deleted]
- hartror 11y agoThis is how the time travel mechanics of Braid were implemented. Record the events, apply those events in a deterministic manner, and then reverse the events to go backwards in time. More generally this is pretty much the event sourcing pattern: http://martinfowler.com/eaaDev/EventSourcing.html http://martinfowler.com/eaaDev/EventSourcing.html
- jblow 11y agoNot true, mostly. I recorded world state, not events. The one exception is world 5 where I record events so that your shadow-universe guy can do things. Event recording has a fair bit of history in games, especially as a debugging technique, but I did not want to use it for rewind, considering it too fragile and annoying, and probably too expensive and complicated (you would have had to store world state anyway, to have something nearby to delta from so that you don't start from the beginning of time every frame, so now you have TWO systems: world state recording and event recording. Better to stick with one.)
- Negative1 11y agoCan you elaborate on the distinction between world state and events? As in, you don't capture user inputs but rather track all object positions and states at all times? seems very inefficient that way. Also, big fan! Great work on the new language/compiler livecasts and can't wait for The Witness.
- jblow 11y agoExactly: I record the positions of all objects every frame (and other state variables), not the inputs that generated them. It is more expensive in terms of the amount of memory required, but it is much less expensive in terms of the amount of CPU required, and CPU was ultimately the biggest problem, so it seems I made the right decisions. Even on a limited-memory console like the Xbox 360 you can rewind most levels for 30-45 minutes before running out of buffer. That is more than anyone ever wants to do as a practical gameplay interaction. Working on The Witness... it will be done ... someday not too long from now.
- baddox 11y agoOut curiosity, what happens if you run out of buffer?
- nightpool 11y agoTheoretically, you probably just want to kick the stuff at the end out. (i.e. you lose the earliest state you can)
- seanmcdirmid 11y agoThat would be a cool game mechanic: you can freeze time and fine tune your behavior over a small window of the immediate past(e.g. the last two seconds), with the ability to see how the game changes over that window "strobe style." Sort of like Sherlock Holmes (in the movie where he thinks everything through "what if" style).
- Kiro 11y agoAre you just speculating or did you read this somewhere? You make it sound like fact until the creator of Braid comes in and says it ain't so.
- hartror 11y agoI thought I had read it somewhere, but obviously not.
- tuukkah 11y agoThe writer monad gives you purely functional "printing".
- mhluongo 11y agoI thought monads were going to be the answer at the end of the post... -_-
- wereHamster 11y agoThe IO monad gives you purely functional "printing". The Monad gives you purely functional sideeffects.
- ufo 11y agoI don't think the article really is about printing. He just uses printing as an analogy to point out that you can calculate changes without altering the simulation data during the calculations. And changing topic, I am not a huge fan of how the Writer forces your code into a monadic style. One of the things I enjoy the most when I program in Ocaml instead of Haskell is being able to put printfs or mutable buffers wherever I want.
- dllthomas 11y agoWriter isn't really about printing. It's about emitting values, to be later collected. That could very easily be state changes.
- ufo 11y agoI know. But even then, I kind of like being able to append values to a mutable buffer that is in scope without having to rewrite everything to use monads.
- dllthomas 11y ago"I know." Then I don't understand your earlier comment. "But even then, I kind of like being able to append values to a mutable buffer that is in scope without having to rewrite everything to use monads." We can agree to disagree, there.
- Animats 11y agoThat's an argument for single-assignment programming, of which functional programming is a subset. There's nothing wrong with named values; it's mutable variables that are the problem. Both Go and Rust encourage single-assignment programming, with ":=", "let", and automatic type inference for assignments. C++ has had "auto" for years. The trend is towards single-assignment as a programming style. Declaring named values without initializing them is so last-cen. Single-assignment programming is a bit more powerful than a pure functional style; you can use a value more than once. It's the difference between a tree and a directed acyclic graph. If you have code that does something imperative, talking to the world outside the program, trying to hammer that into a pure functional form is like pounding a screw. It's also nice to have named variables when reading a program. f(g.h(f2(g2(x)))) provides little information about why someone was doing that. When those intermediate results have names, it's somewhat more clear.
- the_af 11y agoI assume you've never read anything written by Tony Morris on this matter :) He argues that identifier names are one of the least useful tools in understanding programs: http://tonymorris.github.io/blog/posts/identifier-names/ http://tonymorris.github.io/blog/posts/identifier-names/ (his tone might be a bit grating, but he knows his subject). In any case, I'm puzzled... why do you think writing in a pure FP language has anything to do with not naming your variables? BTW, I'd say the opposite of your initial claim is true: single-assignment is the subset of FP, not viceversa. There's way more to FP than immutability, and in fact there are FP languages which allow (controlled) mutation.
- fsloth 11y agoThe claim that variable names are worthless is quite exotic in the general context. I value algebraically explicit operations as much as the next guy but I also write much better code when it's obvious to me what my code does, and good variable names are an important tool cognitively in that respect.
- holri 11y ago
- deleted 11y ago[deleted]
- zak_mc_kracken 11y ago> "At what point in the frame was this change made?" Some parts of the game may have looked at the original version, while others looked at it after the change. Now magnify the potential for crossed-wires by all of the destructive rewriting going on during a typical frame, and it's a difficult problem. Not really, it's a pretty trivial problem and one of the least concerns of game programming these days.
- subb 11y agoExactly, and in fact it's usually not as simple as "you just work on the previous frame's data". There's a bunch of data dependencies that needs to be respected during a frame update. For example, if you update the player position wrt user input, you will want to update its animation in the same update, and also check if its not coliding with anything. Otherwise you're just lagging behind.
- jacquesm 11y agoThat's a problem only if your engine runs so slow that the changes between frames are relatively large. They shouldn't be, otherwise you'll end up with inconsistencies no matter how many sources of data you use during the calculation of the new frame. It's entirely legal to run your 'world' locally at a higher rate to resolve such issues than the display rate.
- bsurmanski 11y agoThat was my initial thought too, but I think it's still a useful realization. at least one place in which this would make sense is physics response. If your actors has a single 'update' method, the first actor would check for collisions and move before any other actors had a chance to do anything. This gives certain actors preferential treatment in movement. Of course, you could instead plan out the dependencies better; do all collision detection before all physics response. But this is just a different way to look at 'immutability'
- jblow 11y agoIn most real physics systems, you have to solve systems of simultaneous constraints in order to get the right answer, i.e. all the guys involved in an interaction are sort of going at the same time. (Though also these systems do tend to have ways to break constraints and subdivide the problem when it gets too big, which then does give preferential movement, but not in a way that any kind of functional programming would solve, because it is inherent in reducing the complexity of the math problem.) There may be exceptions to this; it is not a subject I keep current with.
- dgreensp 11y agoI think there's a good insight here, related to Clojure's atoms and Facebook's Flux. If you start by making everything in your program 100% immutable and timeless, how do you introduce any kind of time-dependence? A nice clean answer is that there is a global clock, and when it ticks, everything changes.
- javajosh 11y agoTime dependence is just like an async dependence (like waiting for a mouse click) in that, in a profound sense, a program doesn't "know when it will happen". The only time a program's state changes is with new information, and the clock is just another source of information. (There's no reason why you couldn't specify timeouts in "ticks" and give the user a button that represented a "tick" such that they could advance the program.)
- RootDynasty 11y agoIn my opinion the most important part of functional programming is the purity of functions. There is a great quote about this on one of the Clojure doc pages "If a tree falls in the woods, does it make a sound? If a pure function mutates some local data in order to produce an immutable return value, is that ok?" Function purity enforces that mutations are localized to small areas of the code, while maintaining composition.
- ufo 11y agoFor me, having first class functions with proper lexical scoping is enough to start feeling functional. That might sound like nothing but its surprising how few of the most popular languages get both of those right.
- Kiro 11y agoWhat is proper lexical scoping? Does JavaScript get it right?
- coldtea 11y agoNo. Javascript gets it horribly wrong without "var", still terribly wrong with "var", and somewhat better with "let".
- Kiro 11y agoI don't understand what let has to do with functional programming though (enclosing a variable within if () {} instead of function block etc). Do you mind elaborating?
- coldtea 11y agoThe question wasn't about functional programming per se, but about lexical scope. "let" keyword in ES6 allows Javascript to have "lexical" style scoping (with some caveats due to JS legacy). That said, several ways of scoping a variable can be had in functional programming. Have a look here for some more explanation with regards to Common Lisp: http://stackoverflow.com/questions/463463/dynamic-and-lexical-variables-in-common-lisp http://stackoverflow.com/questions/463463/dynamic-and-lexica...
- yzzxy 11y agoI think this is roughly how demos (in Quake, et al) are recorded. I think most demos also include the state introduced by RNG if the game involves that. It's interesting to think about that idea with relation to functional programming.
- jarcane 11y agoI am a great lover of functional programming, so much so as to seek out and find a summer job in Clojure this year, and to have written my own functional Lisp dialect. Lately though, as I've been weighing engine options for a CRPG project, I have become increasingly skeptical of its applicability or utility to games. The simple point of the matter is that games are humongous state machines, but even more importantly, humongous state machines that are performance sensitive. The standard approach so far has been to simply deal with this either monadically or atomically, having some big state object that gets passed through each cycle, copied again and again with every frame. This is all well and good when the full extent of your game state is a handful of blocks and a paddle, but stop and think how many, say, console-style RPGs you've seen done in functional languages to completion. In the Pokemon games, there is a move called Defense Curl, that increases the users defense. Simple enough. Then in the second gen games, it was very silently given another effect: there is a particular attack move whose damage is doubled if the user has previously used Defense Curl in that fight. In the third gen, this was done again for an additional move that, at the time and for three more iterations of the series, was only available to a single character. That is an incredibly specific state detail. And that's just one. The entire game is filled with little quirks and mechanical details like that. There are over 600 moves in the game, many with other unique effects, not to mention the 700+ creatures, almost 200 abilities, plus an entire hidden second stat system with the IVs. Try passing a state object containing all the flags you need to keep track of that 30 or 60 frames a second. Is it any wonder then that you see so little done with FP languages that isn't just clones of old arcade games? I know of one company working on an A-level game in Haskell. Beyond that, I've seen a couple Quake 3 ports and a whoooole lot of unfinished projects. I'm just not convinced it's up to the task yet, and the research and theoretical end still seems to focus on trivial toy examples instead of full-scale projects that are on a whole other order of magnitude from Pac-Man. I seriously start to wonder how much of the learning so far and the 'obvious' patterns and solutions that seem to already just be accepted dogma, really have anything to do with real-world games programming in the large. Maybe Wayward Tide will finally release source and prove me horribly wrong here, or Elm will indeed prove as promising as it looks when extended beyond simple browser toy experiments, but in the meantime I'm veering hard back to commercial, traditional engines instead.
- 11y ago
- kibwen 11y ago> single-assignment "variables," It's a pet peeve of mine to see people disparage the phrase "immutable variable" as a contradiction. A given variable's value can vary each time its function is called, or each time its program is run, without ever needing to be mutated. In fact, in practice most variables don't end up requiring mutation, which was a surprise for me coming from traditional imperative languages (not to say that mutation isn't valuable, but it makes more sense for your language to make variables immutable by default rather than mutable by default). </rant>
- dukerutledge 11y agoThis is why we call these things "values" not "variables"
- mbrock 11y agoThose are different concepts. Variables have names, values typically don't. 500 is a value; foo is a variable.
- seanmcdirmid 11y agoValues that have names are typically called objects (their identity isn't structural). Named values are necessary for having mutable fields (I.e. variables).
- mbrock 11y agoHmm, that doesn't sound right to me, at least not if "name" means "identifier" in the conventional sense (like foo). For example, stack-based languages can do field mutation without names.
- seanmcdirmid 11y agoDepends if we are talking about local stack or global heap state. If you just want to modify a register, then a locally bound name/index/stack pointer is sufficient. If you want heap allocated aliased (shared) state, you need globally unique names or addresses. The challenge is always with global state, hardly ever with locally scoped state.
- Ingon 11y agoI wonder if somebody have tried using a STM style approach to making games? For a couple of LudumDares I did try (in java) and for the games I was able to do it worked fairly well. Basically the drawing thread is seeing a frozen readonly version of the world (and keeps 60 fps) while the update thread will try to run simlation over readwrite version of the world. When the update thread finishes it will "publish" the new state and start over. I have ever wondered how it will perform at scale, maybe it will start braking apart if it grows too much?
- m_mueller 11y agoIANAGameEngineProgrammer, but I'd say it all depends on how you do the 'publishing' part. To do this in a performant way you need a language that supports pointers, so all you need to do in the thread safe part of your code is to swap two pointers (current and new). I'd assume the thread sync overhead once a frame becomes negligable (is there a good analysis for thread sync overheads on current x86?).
- orbifold 11y agoIt breaks down when you approach the hardware limits, i.e. for rts games with thousands of units on the screen, particle effects and so on, or if you have complex cad models in automotive applications. Essentially you then need to minimize driver overhead and avoid data copying at all costs. In particular you need to do memory mapped IO (using glMapBufferRange) between the GPU and main memory as fast as possible. That is only possible if you do tripple buffering with a ring buffer, at any given time one part of the buffer will be in flight to the GPU, one will be processed by it and the third will be modified by the CPU. You "publish" with synchronization (glFenceSync() and glClientWaitSync()), see for example http://gdcvault.com/play/1020791/ http://gdcvault.com/play/1020791/. In particular you have to organize all your world data in flat mutable arrays because even on the CPU your data has to be presented in a way that avoids cache misses as much as possible, this philosophy goes by "data-oriented design", see for example https://www.youtube.com/watch?v=rX0ItVEVjHc https://www.youtube.com/watch?v=rX0ItVEVjHc.
- davexunit 11y ago
- dfbrown 11y agoI think the simplest way to do stuff like this is to build up an iterated copy of the previous state and once done replace the old state with the new one. Iterating isn't modifying the current state, it's generating the next state from the current one.
- ajuc 11y agoImmutability gives you elegant command-query separation, and it's sometimes useful (for example you can use the same function in physics, and in AI to predict where player will be in 5 frames). Of course you pay with performance. I wonder if keeping a tree of game states in persistent variable (like Clojure datastructures) could help with that. We could keep the current state as a root of game states tree, AI code will calculate possible future states a few steps ahead (these future states would mostly share memory with parent and sibling states, and if we predict n frames forward AI can start in each frame from states in step t+n-1 and calculate their immediate kids only). This is trivialy parallelizable BTW. And in each frame game engine would move the tree root to one of the kids depending on player action, culling the previous root and the branches not taken from the tree.
- journeeman 11y agoIsn't the author basically saying, an iterative process (process as in procedure-semantics; like the word is used in SICP) is better than a recursive process?
- marssaxman 11y agoI took a stab at solving this problem with a programming language called Radian: [http://www.radian-lang.org/ http://www.radian-lang.org/] It is based on the observation that SSA is functional programming, and there is a well-defined process for transforming imperative code into SSA, so why not reverse the process and develop a functional language with imperative-looking, Python-like syntax? The goal was to automatically extract parallelism from for-loops, internally converting them into map-reduce processes which could be spread across multiple cores, and that worked out pretty well. In absence of a marketing effort, however, a userbase never developed, and I haven't done any work on the project in a couple of years.