18 Apr, 2009, Silenus wrote in the 1st comment:
Votes: 0
Hi,

I have been recently looking into functional programming languages and find them to be quite elegant in design(and simple to implement except for perhaps the runtime garbage collector). The question I have is whether or not it would be possible to use languages like these for mud development especially if they are pure.

I was curious if anyone here is versed in for example monads and Eugenio Moggi's work and whether it is possible to with a combination of abstract data types/modules construct relatively understandable code using this the fp approach. Unfortunately I have limited exposure to large programs constructed in languages like ML,OcaML, Haskell etc. and I was somewhat wondering how these would look like and whether you could easily map mud abstractions onto a language like this (I am still working on my own compiler + engine).
18 Apr, 2009, David Haley wrote in the 2nd comment:
Votes: 0
A MUD server is an inherently stateful beast, and things are supposed to have side effects (that's the whole point). Think about what it would entail to have a truly pure functional language – how would you do things like update command statistics with time spent on the command? (first example that comes to mind, but there are tons – pretty much every command has desired side effects) Just sounds like a nightmare to me.

There are lots of very good things to be taken from functional languages, but total lack of side effects is not something you want for a MUD.

Now that's not to say that you could make many of your routines purely functional, and arguably many should be.
18 Apr, 2009, Silenus wrote in the 3rd comment:
Votes: 0
That is the thing I still find difficult to understand about pure functional languages (or perhaps true functional languages)- how they cope with various things where it may be desirable to model state information. I guess that is why I was referring to monads which allow one to some extent control the order of function applications when doing I/O type stuff. Unfortunately I have only done a limited amount of programming in a pure functional language (Clean) and I found it quite difficult though I could get it to do what I wanted. Basically I spent alot of effort passing state variables in and out of functions to do what I needed.

I may have to try doing more programming in something like Haskell to get a feel of it. I heard that the use of monads (whatever they may be) allows one to encapsulate state while preserving the virtues of a pure language.
18 Apr, 2009, JohnnyStarr wrote in the 4th comment:
Votes: 0
Quote
the virtues of a pure language.


What virtues do you feel are best? And why would these be better suited for a MUD server?
18 Apr, 2009, Silenus wrote in the 5th comment:
Votes: 0
It is hard to say whether or not the chief advantages of pure fp- i.e. referential transparency and independence from execution order are of much interest practically when it comes to implementing muds or any better. The question for me is whether it is feasible to do so. I just happen to be working part time on a project where purity might be a desirable feature so rather than write two compilers (one for muds and one for this other project) I was wondering if I could recycle the same code for use with muds.
18 Apr, 2009, flumpy wrote in the 6th comment:
Votes: 0
you can do functional programming with groovy

http://groovy.codehaus.org/Functional+Pr...

just wavin' my little groovy flag again
18 Apr, 2009, elanthis wrote in the 7th comment:
Votes: 0
My feeling is that functional programming is just ill suited to MUDs, or games in general. Functional programming makes some tasks significantly easier while making others significantly harder, and the specific tasks a MUD needs tend not to favor a functional approach.

Quite simply, object-oriented programming best fits MUD (or most other game) development, because the core data and core logic of a MUD are very naturally expressed as a set of mostly self-contained objects, their responses to stimuli, and their interactions.
18 Apr, 2009, David Haley wrote in the 8th comment:
Votes: 0
You can always write purely functional functions (as it were) in any language, even in C. You could even conceivably take advantage of many of the benefits by having some kind of markup scheme so that you can mark certain functions as being free of side effects.

A big advantage of side-effect free functions is that you can parallelize up to wazoo without having to think about anything beyond the order in which results are needed. This is a huge step up from having to start worrying about synchronization across parallel invocations of functions of parts of functions.
19 Apr, 2009, quixadhal wrote in the 9th comment:
Votes: 0
David Haley said:
A MUD server is an inherently stateful beast, and things are supposed to have side effects (that's the whole point). Think about what it would entail to have a truly pure functional language – how would you do things like update command statistics with time spent on the command? (first example that comes to mind, but there are tons – pretty much every command has desired side effects) Just sounds like a nightmare to me.


You do the evil thing we've done in the dark ages…. you pass in a reference to your "world" data structure to every stinking function so it can stuff things in there. Naughty.
19 Apr, 2009, David Haley wrote in the 10th comment:
Votes: 0
Actually that doesn't work, as modifying the state of some object passed in as a parameter makes it a function with side effects…
19 Apr, 2009, quixadhal wrote in the 11th comment:
Votes: 0
Ah, so you're only allowed to work with return values? Yikes…. even more strict.
19 Apr, 2009, Silenus wrote in the 12th comment:
Votes: 0
Yeah my limited understanding of it is you basically you have to use a state transformer function which maps the operation and current state into a new state. I am just starting to read various proposals on how this kind of thing can be done in a pure functional language while having some form of encapsulation. In theory I guess purity may help with implicit parallelism but my (limited) understanding is that it's quite tricky to do this well or build sufficiently intelligent compilers which can optimize code written in the FP style onto arbitrary parallel architectures.
19 Apr, 2009, elanthis wrote in the 13th comment:
Votes: 0
You CAN'T make a MUD with implicit parallelism like that. It's conceptually impossible, because any two concurrent actions (e.g., two player inputs, AI input, etc.) may act upon the same object simultaneously. Pure functional languages are just wrong for this sort of application, entirely.

Pure functional languages (as their name imply) are fantastic for purely mathematical operations, including non-numeric math like set theory and the like. When you're trying to write software that is inherently a set of objects and methods, using a functional language is just plain out wrong. You can with a huge amount of difficulty probably pull it off, but you will get absolutely no advantages over using any imperative language, and it'll just end up being harder to understand than if you'd used an imperative language. There's no reason at all to use only one language, especially when that language limits you so heavily. Imperative programming is not ideal for all tasks, and neither is functional programming. Don't use a hacksaw to drive in a nail. (more tool metaphors, yay!)
19 Apr, 2009, David Haley wrote in the 14th comment:
Votes: 0
Besides, MUD servers aren't doing anything often enough that would actually benefit from implicit parallelization.

As several people have said, the main benefit of functional programming here should be to learn clean organization of algorithms, not to write the whole program in a purely functional language.

Here's a little something to think about. How would you go about writing the simplest data container – a plain old list – in a language that strictly disallows side effects?
Once you've figured that out, ask yourself if you want to write an inherently stateful application the same way.
20 Apr, 2009, Silenus wrote in the 15th comment:
Votes: 0
I think you might have misread my remark that was in reply to DH's comment concerning parallelism w.r.t pure functional languages. In theory it's possible but unfortunately doing this sort of thing without additional annotations so far (AFAIK) seems to pose tremendous problems for compilers. So in general it's a very hard problem.

W.r.t. Elanthis remark TBH I am no expert in this area so I cannot really comment. However I thought the whole point of the idea of implicit parallelism was to infer when or if you could parallelize in theory and when you cannot through a form of dependency analysis then restructure things (hard large search space problem) to maximize parallelism and determine whether and when it's productive to do so based on a cost model. Are you saying that these opportunities are limited(ignoring for the moment that this problem is unsolved in the general case anyhow) for MUDS or something different?

DH I am not sure I understand the problem w.r.t. to the list abstraction. Most LISP descendents have it as part of the basic semantics and you can employ it in a pure style and languages like Haskell have similar built in constructs. In the case of the latter if you wanted to construct a list you could do so using recursive data types. To me the semantics would be essentially the same but the computational aspects (since you dont have destructive updates) may be potentially different. Certain languages like pure lazy languages like Clean have something called a uniqueness types where if the system can infer (with additional annotations) that the old value is not used again it does a destructive update. I believe there is work in this area (not sure how advanced it is) which addresses this issue for functional languages using static analysis. Is that what you are getting at?
20 Apr, 2009, David Haley wrote in the 16th comment:
Votes: 0
Silenus said:
I think you might have misread my remark that was in reply to DH's comment concerning parallelism w.r.t pure functional languages. In theory it's possible but unfortunately doing this sort of thing without additional annotations so far (AFAIK) seems to pose tremendous problems for compilers. So in general it's a very hard problem.

Well, in a pure functional language, it's not hard at all to parallelize computation. The hard part is deciding what might be worth parallelizing (i.e. when the overhead is offset by the gain). Remember that in a pure functional language nothing has side effects, so any computations can be done in parallel as long as their inputs have been calculated; ordering the computations is pretty easy to do.

Silenus said:
Are you saying that these opportunities are limited(ignoring for the moment that this problem is unsolved in the general case anyhow) for MUDS or something different?

Yes. As I said, MUD's just don't really have this kind of large scale parallel operation, so there isn't much parallelism to detect. You might think that you could parallelize the update loop, for instance, the one that updates over all mobs and has them run through game logic. But as you process each mob, all kinds of things can happen to other mobs (e.g. they might die) so processing in parallel can be really tricky unless you design the entire function to return actions that then get processed.

Silenus said:
DH I am not sure I understand the problem w.r.t. to the list abstraction. Most LISP descendents have it as part of the basic semantics and you can employ it in a pure style and languages like Haskell have similar built in constructs. In the case of the latter if you wanted to construct a list you could do so using recursive data types. To me the semantics would be essentially the same but the computational aspects (since you dont have destructive updates) may be potentially different.

I didn't say that you can't write lists; of course you can. :wink: I'm just asking you to think about how you would go about dealing with lists. And then how you would go about dealing with larger data structures. You started getting to the problem with the lack of destructive updates. But the problem is not just a computational one – of course the computational cost will be high. What does it mean in practice for how you write code if you can't modify things in-place?
20 Apr, 2009, elanthis wrote in the 17th comment:
Votes: 0
Silenus said:
W.r.t. Elanthis remark TBH I am no expert in this area so I cannot really comment. However I thought the whole point of the idea of implicit parallelism was to infer when or if you could parallelize in theory and when you cannot through a form of dependency analysis then restructure things (hard large search space problem) to maximize parallelism and determine whether and when it's productive to do so based on a cost model. Are you saying that these opportunities are limited(ignoring for the moment that this problem is unsolved in the general case anyhow) for MUDS or something different?


Pretty much. Almost every single last piece of data is inter-related. You cannot cleanly separate the object space outside of breaking the game into multiple independent regions (and even then you have to deal with shared data, e.g. object definitions when items are carried between regions, players traveling between regions, players chatting with each other, etc.).

Every single bit of logic in the game world is generally capable of causing a side-effect on another object. AI updates require querying the world (to see what state it is in) and then effecting changes on the world (even if that change is just the mobile moving, or saying something). Item updates can cause items to remove themselves from the world (timed one-use items, or items sustaining damage from a long-term effect) which in turn alter the game world state. Player commands can obviously effect a large number of state changes.

The only real way functional languages make any of that even possible is with monads or similar concepts, and those impose a great deal of limitations on what you can do. A monad can be thought of as a delayed state change (similar to a database transaction) which means that parallel updates would be incapable of seeing each other, which in turn means that AI or the like may be operating on "stale" data and thus doing bogus things. E.g., if an AI and a player update both try to pick up an item, both routines will see the item, validate the request as valid, and then encode a state transition entailing the moving of the item to the respective character's inventory. When the state changes are processed, something will go wrong – either one or the other state transition will be invalidated (causing the entire update process to fail, which has its own set of consequences, such as causing AI to appear "stuck" momentarily) or the item will be moved into both characters' inventories, causing an item duplication bug.

Working around that problem essentially requires running all updates that could possibly conflict in a sequential manner, which takes you right back to where you are without implicit parallelization.

Whatever advantages you may gain from using functional languages for a game world like this, implicit parallelism isn't one of them.
20 Apr, 2009, Silenus wrote in the 18th comment:
Votes: 0
Quote
Well, in a pure functional language, it's not hard at all to parallelize computation. The hard part is deciding what might be worth parallelizing (i.e. when the overhead is offset by the gain). Remember that in a pure functional language nothing has side effects, so any computations can be done in parallel as long as their inputs have been calculated; ordering the computations is pretty easy to do.


Isnt this precisely the problem though? most functional computations are described in terms of recursions (for example in lisp this would be recursions in most cases over lists) so the call graph and thus inputs are severely constrained a priori- so unless you do some restructuring you cannot make progress in alot of cases. Even something like map/apply over a list is typically described as a simple list traversal recursion when in fact it can be data parallel.

Quote
Yes. As I said, MUD's just don't really have this kind of large scale parallel operation, so there isn't much parallelism to detect. You might think that you could parallelize the update loop, for instance, the one that updates over all mobs and has them run through game logic. But as you process each mob, all kinds of things can happen to other mobs (e.g. they might die) so processing in parallel can be really tricky unless you design the entire function to return actions that then get processed.


Well this question was directed at Elanthis since I was curious to hear his opinion- but anyhow(oops Elanthis posted while I was posting ;-) ). I guess this is one area I am rather unsure about. I do understand that in alot of cases for alot of tasks this probably is the case but I wonder if the question has been completely resolved. As I already indicated hard problem.

Quote
I didn't say that you can't write lists; of course you can. :wink: I'm just asking you to think about how you would go about dealing with lists. And then how you would go about dealing with larger data structures. You started getting to the problem with the lack of destructive updates. But the problem is not just a computational one – of course the computational cost will be high. What does it mean in practice for how you write code if you can't modify things in-place?


Well this is a sort of depends question I think. I.e. if you ignore the computational cost question I would say the only real loss from the programmers perspective is perhaps lack of encapsulation due to the addition of state variables being passed through the system. Otherwise there is semantic equivalence. The main issue from my perspective is a computational one- and the question, for me, is to what extent different transformations and analysis can be used to close the gap in performance at present.
20 Apr, 2009, David Haley wrote in the 19th comment:
Votes: 0
Silenus said:
I do understand that in alot of cases for alot of tasks this probably is the case but I wonder if the question has been completely resolved.

What does "completely resolved" mean? I think it's pretty clear that neither of us would seriously consider implementing a MUD in a purely functional language.

The "hard problem" is frankly not if you would do it: the hard problem is how you'd do it. :wink:

Silenus said:
Well this is a sort of depends question I think. I.e. if you ignore the computational cost question I would say the only real loss from the programmers perspective is perhaps lack of encapsulation due to the addition of state variables being passed through the system. Otherwise there is semantic equivalence. The main issue from my perspective is a computational one- and the question, for me, is to what extent different transformations and analysis can be used to close the gap in performance at present.

Have you ever actually written pure functional code? The reason I ask is that "semantic equivalence" is useless here. Assembler can be written to be "semantically equivalent" to any language … so what?

The reason I keep pushing on this is that the paradigm makes this kind of programming hard. Seriously, just try writing some code with simple data structures with state in a purely functional language, and then compare to a procedural/OO language.

I think you're approaching this whole issue from some very high theoretical level and aren't considering the practical aspects involved. Semantic equivalence is all well and good until you start actually writing code and see how hard it is to achieve that semantic equivalence.
20 Apr, 2009, Lobotomy wrote in the 20th comment:
Votes: 0
David Haley said:
I think you're approaching this whole issue from some very high theoretical level and aren't considering the practical aspects involved. Semantic equivalence is all well and good until you start actually writing code and see how hard it is to achieve that semantic equivalence.

That said, I think things have now reached the point on the matter where such a project should be attempted/done (not explicitly by the OP, but rather by anyone who just feels like it), simply as a proof of concept if nothing else. I think it'd be rather interesting, personally, and we could have some kind of idea of how difficult/easy the approach is as a matter of practice instead of conjecture.
0.0/51