Just trying to get a handle on the idea of functional programming, especially in how it can be used in games. As I understand it, functional programming doesn't allow any kind of state. So, I can't pass a structure into a function and be able to modify the structure's data there. This makes designing for games tricky, since games are pretty much nothing but state. The only place where state can exist in a functional program is in function parameters (and, I guess, return values). This makes me wonder: for a game, would state be maintained by passing the old state to a function that returns a whole new state that represents the next frame? Lets use an example. Say I have a structure representing a ball with an X and a Y position. Each frame I want to update the ball's position. Say I do this by passing this ball to a moveBall function. In an imperative language, moveBall would modify the ball's X and Y values directly and could be declared void. If I understand functional programming correctly, moveBall would instead return an entirely new ball to "replace" the ball passed as a parameter, where the old ball was used to come up with the X and Y values the new ball needed. If I have a list of balls, I'd pass the list to a function that will generate a whole new list with wholly new balls that conceptually replace the old balls, instead of the function modifying the balls in-place. Am I understanding functional programming right?

Yes, you have the right basic idea. Sequenced execution in purely functional languages has, as its central tool, the natural constraints on order of evaluation. If you evaluate the tuple (f1(), f2(), f3()) then those three functions can be executed in any order, and none of them knows the results of the other (let alone that they've been called at all). If, on the other hand, you execute f3(f2(f1())), the order of evaluation (lazy evaluation notwithstanding) is fixed, and state is propagated from function to function.

For more information, get to know monads in haskell, particularly the State monad.

Quote:Original post by Guy Meh
This makes me wonder: for a game, would state be maintained by passing the old state to a function that returns a whole new state that represents the next frame?

Yes. This can often be optimized behind the scenes so that it actually works the way it would in an imperative language (making a change to the existing data, instead of making a modified copy, rebinding to the copy and allowing the original to be GCd).

Quote:Lets use an example. Say I have a structure representing a ball with an X and a Y position. Each frame I want to update the ball's position. Say I do this by passing this ball to a moveBall function. In an imperative language, moveBall would modify the ball's X and Y values directly and could be declared void. If I understand functional programming correctly, moveBall would instead return an entirely new ball to "replace" the ball passed as a parameter, where the old ball was used to come up with the X and Y values the new ball needed. If I have a list of balls, I'd pass the list to a function that will generate a whole new list with wholly new balls that conceptually replace the old balls, instead of the function modifying the balls in-place.

If the class is called Ball, I wouldn't call the function moveBall in either an imperative or functional context. In an imperative context, I'd call it "move". In a functional context, I'd call it "movedBy" - that is, it returns a new Ball representing the old Ball, "moved by" the specified displacement.

But yes, the list example would look just like that. It may seem like a lot of extra work to you, but it's not work that the programmer does, and it often makes it much easier to write certain algorithms - especially if you have to remove or insert Balls as a part of the update. Basically, you think of the input list as an input stream, and the return value list as an output stream. :)

Note that you can write code honouring the functional paradigm in, well, any language with functions. :) You just won't necessarily reap the benefits, or get to play with the fun abstractions usually associated with functional programming languages (i.e. higher-order functions).

Quote:Original post by Guy Meh
As I understand it, functional programming doesn't allow any kind of state.

It doesn't allow mutable state you may have state a plenty. That isn't true either since most functional programming languages allow mutable state in some fashion. Scheme has set! functions, Ocaml has references, Haskell has the state monad. For the most part yes you don't use mutable state you return a new item instead of update. Another idea you will see is Functional Reactive Programming.

Quote:Original post by Zahlman

Quote:Original post by Guy Meh
This makes me wonder: for a game, would state be maintained by passing the old state to a function that returns a whole new state that represents the next frame?

Yes. This can often be optimized behind the scenes so that it actually works the way it would in an imperative language (making a change to the existing data, instead of making a modified copy, rebinding to the copy and allowing the original to be GCd).

That's certainly a relief. I suppose anyone may be initially scared off by the game state been apparently duplicated each frame.

I imagine the state "duplication" could have other uses too. I'd expect recording replays would be easier, and the functional environment might even allow some kind of time travel worked in. :)

Quote:Original post by Sneftel
For more information, get to know monads in haskell, particularly the State monad.

Ah geez, do I have to? :P It seems all the stuff I've read on monads either go right over my head or look like hacks to get imperative programming back into a functional program.

I know monads are used for I/O, but surely swinging the state structures around inside a recursive function representing the main loop is enough.

P.S. I suppose I'll insert a "choose a language for me" plead here. It has to at the very least work on Mac OS X since that's what I'm using. I'm leery of Haskell since it seems to use monads for everything but the most basic tasks. Erlang seems to be a good choice since it seems to be one of the few functional languages with extensive use outside academia (it's even used for Wings 3D) but I'm not sure how "purely" functional it is. Clean looks like another good choice since it's like Haskell but doesn't use monads. Obviously, since I'm thinking of games here, I want a language that has a library for graphics and other things games need (though I have to wonder what rendering graphics in a functional environment would be like).

Monads aren't just for procedural code. Take a look at some short examples of the List and Maybe monads. They're like programmable semicolons (a frequent slogan in monad articles), which is seriously nifty.

State does take some thinking in functional land, though. I find it easiest to move any state (including IO) into the tiniest, outermost chunk of the program and leave the functional heart of the thing as pure as possible.

Quote:Original post by Guy Meh

Quote:Original post by Sneftel
For more information, get to know monads in haskell, particularly the State monad.

Ah geez, do I have to? :P It seems all the stuff I've read on monads either go right over my head or look like hacks to get imperative programming back into a functional program.

"Hack" is more a value judgment than a useful descriptor. Monads are the mathematically-formalized abstraction of sequenced computation.

Quote:I'm leery of Haskell since it seems to use monads for everything but the most basic tasks.

You're leery of Haskell because it uses monads, and you're leery of monads because you don't understand them. Lack of understanding is an iffy basis for choosing a language. BTW, I wouldn't suggest Haskell as an everyday programming language. It's just one that's useful to know really well.

Quote:Erlang seems to be a good choice since it seems to be one of the few functional languages with extensive use outside academia (it's even used for Wings 3D) but I'm not sure how "purely" functional it is.

It's not.

Quote:Clean looks like another good choice since it's like Haskell but doesn't use monads.

Clean uses uniqueness typing as a substitute for monads. The concepts are not quite the same, but if you don't understand monads, you're totally not going to understand uniqueness typing. Additionally, uniqueness typing is not as useful or illuminating a concept, because it pretty much only does one thing.

Quote:Obviously, since I'm thinking of games here, I want a language that has a library for graphics and other things games need (though I have to wonder what rendering graphics in a functional environment would be like).

Haskell and OCaml both have GL bindings. I'm not sure about Clean.