Lambda the Ultimate

You seem to think that C function pointers gives you closures.

I didn't get this from the OP at all. He mentioned Python as a counterpoint, which does in fact have real closures. Some other non-pure-FP languages with real closures are Ruby, Smalltalk, Javascript, and Perl. So I think the OP's point that closures can't be cited as an advantage of FP over other programming paradigms is valid.

Adam Jenkins: Some other non-pure-FP languages with real closures...

I think this is the key observation: closures are a benefit of pretty much every lexically-scoped language in which functions are first-class. It just happens that that covers a pretty decently-sized set of languages these days. I mean, really, the moment you say "pure functional language," what does that mean? Haskell, around here, but there's also Concurrent Clean, and... um... :-)

So I think the OP's point that closures can't be cited as an advantage of FP over other programming paradigms is valid.

Um...I'm not sure I completely agree with this. Functional programming isn't a well defined set of properties (and neither is OOP). There are many "non-functional" languages that share these features, and allow a functional style (same with OOP). Just because a language isn't a pure-functional language doesn't mean it isn't functional at all (also true of OOP).

Functional programming is a style that combines several features and ideologies together (just like OOP). You can write a program in a functional style in a non-functional language (this is also true of OOP), however "functional" languages have better support for the functional style and allow certain things (because of guarantees properties like immutability give you) that are not allowed in non-functional languages (as OO languages have better support for the OO style and allow things that are not necessarily allowed in non-OO languages). In other words, functional languages have the support for programming in the functional style (just like OO languages have support for the OO style). It’s the features, when combined together along with the functional style that give functional languages the advantages they have.

You can, after all, write object oriented code in C, but it gets to be a pain. Is C an object oriented language? Same with Python/functional programming. You can write functional code in Python, but it will get to be a pain.

You can write a program in a functional style in a non-functional language...

I agree completely that the paradigms you use and the PL you use are orthogonal. OO and FP are paradigms, which can be used from any language to some extent. Some languages are designed to facilitate one paradigm specifically, but you can for instance write non-OO code in a language designed to support OO and vice versa, and most languages are designed to facilitate multiple paradigms really.

Having acknowledged that, I still think the OP's observations/questions are mostly valid. Many features which are often cited as advantages of FP as a paradigm are really just language features, which can in principle be just as useful, and exist just as naturally, in a language designed to support other paradigms than FP. Some such features would be first class functions, closures, anonymous closures, type inferencing, tail call elimination, pattern matching, currying. In fact the only major FP language feature I can think of which really would be more difficult in a non-referentially transparent language would be default laziness as in Haskell, though I'm sure there are some others.

I agree with another poster who said the main distinguishing feature of FP is referential transparency, which allows programs to be expressed as if they were just one big nested function call, with order of execution just being implicit rather than explicit. Many of the features in FP languages are there to facilitate being able to structure your programs this way, though they're also useful even if you're not trying to program in the functional paradigm.

I'd probably approach that sort of simulation with Yampa, but YMMV.
Check out the code for the Yampa Arcade.

Thanks for the link. Although the yampa approach is interesting, it does not address the problem I presented above (i.e. how to do the model-view-controller pattern on a big object model). The arcade game they present has a very limited object model.

I would also like to note that the game they present is not like Space Invaders, but more like Galaga.

I would sincerely appreciate any other tips.

A simple and clean way to do something like this is by chaining the state thru a (tail-)recursive function:

  eventLoop updater state = 
     if is_finished state then state
     else eventLoop updater state

So the core of the whole update process is a loop like

   state' = updater state

where 'updater' has to interate over the state to create a new one and mark it as 'finished' if a end-state has reached. The problem is that in each 'round' you have to create a new state from an old state. This could be a bit costly because lots of data have to copied in each round.

But because the old state is thrown away after each round so a clever compiler should be able to use this for optimisation. It would be interesting to know how common compilers optimize the above pattern and if they are able to optimize it by replacing it with in-place updates where possible.

It seems like nobody noticed the size of the object model :-).

What you propose was my first approach, but I had to write all sorts of functions that traverse the old state and create a new state from the previous one, for almost each branch of the tree.

Look at section 4.1 of the Yampa Arcade paper. A gun is defined as a chunk of state and a state transformer.
Then in section 5 the game itself is described as a collection of game objects, and their state transformers.

So rather than using Yampa with a big single chunk of state and one state transformer for your simulation, try writing a single chunk of state and a single state transformer for each interacting entity in your system and putting those into a dynamic collection.

If you want a larger Yampa example, try the Quake clone Frag.

But my problem is not the simulation. That is trivial: a list of objects is processed and creates another list of objects.

What I am interested in is the model-view-controller pattern: when state changes, signals are emitted and registered listeners' responses are executed. Listeners connect to the model arbitrarily and disconnect automatically.

In the imperative languages like C# or Java, such a task is trivial to do. Is there a way in FP to do the MVC pattern equally trivially?

Achilleas, with all due respect, how many times are you going to ask this question, have it answered in ways that you don't understand and apparently aren't willing to learn about, and come back with the same question over and over and over again?

For the last time: MVC isn't appropriate in the functional paradigm, and arguably isn't appropriate in the object-oriented paradigm. Functional Reactive Programming is a big win in the functional world, and now you have links to papers, running software, everything you could want in order to learn more about it. If that's too big a bite to chew, go back to my post about the subject/observer pattern in O'Caml. In fact, nevermind; here it is again, from memory:

class ['O] subject =
object (self : 'selftype)
  val mutable observers : 'O list = []
  method add_observer obs = observers <- obs::observers
  method notify (message : 'O -> 'selftype -> unit) = List.iter (fun obs -> message obs self) observers
end

class ['S] observer = object end

Here's a very brief example use:

class ['O] window =
object (self)
inherit ['O] subject
  val mutable position = 0
  method draw = Printf.printf "[Position = %d]\n" position
  method move d = position <- position + d; self#notify (fun x -> x#moved)
end

class ['S] manager =
object
inherit ['S] observer
  method moved (s : 'S) = s#draw
end

let w = new window in w#add_observer (new manager); w#move 5

There you go. Again. Revision not to use objects and use, e.g. polymorphic variants is left as an exercise for the reader.

Thanks, but that is not a functional example, that's an imperative example. It can be translated, line to line, to this (I have no knowledge of O'Caml, but it seems pretty obvious):

template <class T> class subject {
public:
    void add_observer(observer<T> *l) { observers.push_back(l); } 
    void notify(T val) {for(list<observer<T> *>::iterator it = observers.begin(); it != observers.end(); ++it) (*it)->moved(val));}
private:
    list<observer<T> *> observers;
};

class window : public subject<window *> {
public:
    int position;
    window() : position(0) {}
    void draw() { printf("position = %i", position); }
    void move() { position++; notify(this); }
};

class manager : public observer<window *> {
    void moved(window *w) { w->draw(); }
};

int main() {
    window *w = new window;
    w->add_observer(new manager);
    w->move();
}

I would like a functional example, i.e. an example in Haskell or ML. I would like to see an example of MVC in pure functional languages.

For the last time: MVC isn't appropriate in the functional paradigm

I have never written an app where I did not have to use the MVC pattern in some form, from real-time apps to business apps. By saying the above, it seems that you are implying FP is appropriate for a every limited range of types of applications, which is exactly the point I am trying to make, in the context of the real benefits of FP.

and arguably isn't appropriate in the object-oriented paradigm.

What? you are largerly mistaken. The MVC pattern goes hand-in-hand with OO. The roots of MVC are propably in Smalltalk, and used wildly in Qt, Java etc.

Functional Reactive Programming is a big win in the functional world, and now you have links to papers, running software, everything you could want in order to learn more about it.

The problem is that functional reactive programming is not what I asked for. Where is the "arbitrary attachement of listeners to models" in the Yampa example?

How would I approach management of big states like the object model I shown above with cyclic references (parent to child, child to parent etc)?

Achilleas Margaritis: I would like to see an example of MVC in pure functional languages.

I'm not a Haskell programmer, so I can't go into too many specifics, but I do know that you've been shown at least two: Yampa Arcade and Frag.

Achilleas Margaritas: I have never written an app where I did not have to use the MVC pattern in some form, from real-time apps to business apps.

When the only tool you have is a hammer...

Achilleas Margaritas: By saying the above, it seems that you are implying FP is appropriate for a every limited range of types of applications, which is exactly the point I am trying to make, in the context of the real benefits of FP.

Categorically false, because you get the cause-effect relationship backwards. The correct logical conclusion is that pure functional programming has other approaches—such as FRP—to solving the same class of problem. Similarly, a concurrent-constraint language such as Oz also has a different approach to things done with MVC in most object-oriented systems, such as GUI programming. This is a reasonable working definition of "different paradigm," and seems to be the thing that you have what I can only interpret as a willful refusal to learn about.

Achilleas Margaritas: What? you are largerly mistaken. The MVC pattern goes hand-in-hand with OO. The roots of MVC are propably in Smalltalk, and used wildly in Qt, Java etc.

Self, a dialect of Smalltalk, moved away from MVC to Morphic. Morphic eventually made its way into the best-known surviving Smalltalk, Squeak. Swing in Java gave up and collapsed the "M" and "C" because it's just too hard to keep them abstract from each other. There's a huge body of literature on the problems with MVC just within the OO community, nevermind outside it.

Achilleas Margaritas: The problem is that functional reactive programming is not what I asked for.

The problem is that you keep asking the wrong question: "How do I do MVC in a purely functional language?"

Achilleas Margaritas: Where is the "arbitrary attachement of listeners to models" in the Yampa example?

The point is precisely that "arbitrary attachment of listeners to models" isn't necessarily the appropriate implementation strategy in a purely functional language.

Achilleas Margaritas: How would I approach management of big states like the object model I shown above with cyclic references (parent to child, child to parent etc)?

I recommend seeing how Frag handles its scene graph. Also, consider looking more closely at something like Oleg's ZipperFS to see how "state changes in a tree" can be modeled in Haskell.

First of all it is 'Margaritis', not 'Margaritas'.

I'm not a Haskell programmer, so I can't go into too many specifics, but I do know that you've been shown at least two: Yampa Arcade and Frag.

Let me tell you again: Yampa, from my understanding, does not seem to solve the problem I am describing. In the model-view-controller paradigm, listeners can be arbitrarilly connected to events. I did not see that in Yampa. What I saw was a nice way to model reactions to events.

When the only tool you have is a hammer...

No, it is not that. It is that every application has a part where reactive programming is the solution.

Categorically false, because you get the cause-effect relationship backwards. The correct logical conclusion is that pure functional programming has other approaches—such as FRP—to solving the same class of problem. Similarly, a concurrent-constraint language such as Oz also has a different approach to things done with MVC in most object-oriented systems, such as GUI programming. This is a reasonable working definition of "different paradigm," and seems to be the thing that you have what I can only interpret as a willful refusal to learn about.

Until you show me that OOP MVC == FRP and that FRP solves the problem with equal or better elegance, I will not accept the fact that the solution is equal for all the cases that OOP MVC applies.

Self, a dialect of Smalltalk, moved away from MVC to Morphic. Morphic eventually made its way into the best-known surviving Smalltalk, Squeak. Swing in Java gave up and collapsed the "M" and "C" because it's just too hard to keep them abstract from each other. There's a huge body of literature on the problems with MVC just within the OO community, nevermind outside it.

Nope. Java is full of model classes, in case you haven't noticed. And Qt moved from no MVC architecture from version 3 to MVC to version 4.

And any architecture that contains the world 'model' in is IS a Model-View-Controller architecture, even if the controller and the view are unified.

The problem is that you keep asking the wrong question: "How do I do MVC in a purely functional language?"

Why is it the wrong question? it is the exact appropriate question. Isn't FP the holy grail of programming? at least this site supports so. So my question is pretty easy: how to do the MVC pattern (something I use daily in imperative programming) in FP.

The point is precisely that "arbitrary attachment of listeners to models" isn't necessarily the appropriate implementation strategy in a purely functional language.

By changing the definition of the problem, then our discussion is blown away. If you do not know how to answer it, then don't.

I am not asking for a similar implementation, but for a similar outcome, one that is functionally equivalent and similarly easy to use.

I recommend seeing how Frag handles its scene graph. Also, consider looking more closely at something like Oleg's ZipperFS to see how "state changes in a tree" can be modeled in Haskell.

Ok, I will take a look at Frag. But when it comes to Zipper, it is nice, but it still says nothing about 'arbitrary connection of listeners'.

It is that every application has a part where reactive programming is the solution.

So my question is pretty easy: how to do the MVC pattern (something I use daily in imperative programming) in FP.

Even if that was true (which it patently isn't), OO and MVC isn't necessarily the best solution either. Building a reactive system out of concurrent processes interacting via message-passing, like those used in Erlang and occam, can directly yield the kind of behavior that the MVC pattern attempts to emulate.

First of all, why do you consider message passing not being reactive programming? reactive programming does not mean that a callback must be invoked right after the event, but rather that something happens due to something else having happened before that. Reactive programming links cause and effect, and message passing fits directly into that.

In the context of the app I initially mentioned, the simulator sends messages to the other threads of the system when an event happens...then the main thread that deals with the UI processes those events to alter the UI. That's MVC done through message passing.

Secondly, why should I use processes when I don't need them?

Part of any pattern is a context in which the pattern should be used. MVC makes sense in the context of an OO design. It makes less sense in the context of an FP-based design (where other patterns are more appropriate).

No. MVC is not coupled to OO by any means. I have done procedural apps that where mostly about reactive programming: a part of a program did some computation and modified some state, and then informed the other parts of the program through messages or callbacks.

OO is not a programming paradigm, by the way, it is a code organization technique. OO is procedural at heart: a method is a procedure after all.

There are only two programming paradigms: the imperative one which directly alters state and the non-imperative one which does not alter state directly.

First of all, why do you consider message passing not being reactive programming?

Reactive programming links cause and effect, and message passing fits directly into that.

Secondly, why should I use processes when I don't need them?

No. MVC is not coupled to OO by any means. I have done procedural apps that where mostly about reactive programming: a part of a program did some computation and modified some state, and then informed the other parts of the program through messages or callbacks.

There are only two programming paradigms: the imperative one which directly alters state and the non-imperative one which does not alter state directly.

I think that you're allowing the FP bogeyman to fill your vision a bit too much. That's just one dimension by which you can classify programming languages. Take some deep breaths, and try looking in a different direction. How about concatenative/stack-based programming (Forth/Joy/Factor), logic programming (Prolog/Mercury/Kanren), or goal-directed evaluation (Icon), to name a few candidates? Many of these things are covered in books like SICP and CTM. Give them a try!

Achilleas Margaritis: Until you show me that OOP MVC == FRP and that FRP solves the problem with equal or better elegance, I will not accept the fact that the solution is equal for all the cases that OOP MVC applies.

And here we have the crux of the problem: I can't force that understanding on you; you have to arrive at it yourself. The systems and papers are out there; you're either committed enough to learning or you aren't.

Achilleas Margaritis: By changing the definition of the problem, then our discussion is blown away. If you do not know how to answer it, then don't.

I'm not changing the definition of the problem; I'm pointing out that you aren't framing a problem, but insisting upon a specific implementation. If your question includes, as a subquestion, "How do I mutate a list in a purely functional language," then you are asking if God can create a rock so big that even He can't move it, and I feel quite comforable in pointing out that you're asking for an oxymoron. The fact that I can't answer the question because the question is unanswerable is irrelevant.

Achilleas Margaritis: I am not asking for a similar implementation, but for a similar outcome, one that is functionally equivalent and similarly easy to use.

A transparently obvious lie, since you keep asking how to attach arbitrary listeners in purely functional languages, you've been told multiple times what the functionally equivalent approach in Haskell and other languages are, and yet you keep coming back. I won't even get into the "similarly easy to use" rathole. We'll take that up, if I still have the energy, when you've actually bothered to study a purely functional language and FRP for a year or two.

Achilleas Margaritis: Ok, I will take a look at Frag. But when it comes to Zipper, it is nice, but it still says nothing about 'arbitrary connection of listeners'.

Yes, you'll actually have to infer that part. But (Oleg's, vs. Huet's) Zipper is precisely what gives you a "write cursor" into an immutable structure given some consistent iteration interface over that structure. The result of the modification is a new copy of the structure, but one that maximally shares anything that wasn't modified with the original structure, so you don't have the cost of copying the entire structure to face. And it doesn't matter what kind of structure we're talking about as long as it supports the iteration interface. So it's very easy to envision a Zipper over a list of functions to call whenever a certain action is taken, as a degenerate example. Better yet, you could easily provide a Zipper over your entire term graph and do whatever you need in that context. But it's almost certainly not necessary to work at such a low level when tools like Yampa exist. But it remains to be seen whether you'll ever realize that or not.

And here we have the crux of the problem: I can't force that understanding on you; you have to arrive at it yourself. The systems and papers are out there; you're either committed enough to learning or you aren't.

No, that's not acceptable. If you can not explain it with a few lines, then you haven't understood it either. I have never found anything 'complex' in CS that I couldn't explain with a few lines (few = enough so that a mind can easily hold, with the proper abstractions).

I'm not changing the definition of the problem; I'm pointing out that you aren't framing a problem, but insisting upon a specific implementation. If your question includes, as a subquestion, "How do I mutate a list in a purely functional language," then you are asking if God can create a rock so big that even He can't move it, and I feel quite comforable in pointing out that you're asking for an oxymoron. The fact that I can't answer the question because the question is unanswerable is irrelevant.

Thank you very much for pointing out what my request is (/sarcasm), but it is not what you have understood. Let me rephrase the problem:

In imperative languages, it is very easy to do the MVC pattern (or any other model-oriented pattern), and the main characteristic of this pattern is the arbitrary connection of views and controllers to models and the highly increased decoupling between them.

I would like to see a functional programming pattern that is as easy to use as in an imperative language and with the same degree of decoupling. Not necessarily the same implementation. I am not asking for how to mutate a list.

A transparently obvious lie, since you keep asking how to attach arbitrary listeners in purely functional languages, you've been told multiple times what the functionally equivalent approach in Haskell and other languages are, and yet you keep coming back. I won't even get into the "similarly easy to use" rathole. We'll take that up, if I still have the energy, when you've actually bothered to study a purely functional language and FRP for a year or two.

Oh man, you get on my nerves! not only you are personally attacking me, but you are also lying (and I am requesting LtU to fix this situation). I am asking again because I never got a satisfactory reply.

Guess what: if I need to study FRP for a year or two then it is not easy to use! I can explain the MVC model to a 5-year old in a few lines of code...I should be able to do so with any kind of functional pattern which simulates FRP.

You could easily have said that "it is very easy to do MVC in an FP like this: any changes are recorded in a collection, passed to the top level loop where the application's context is manipulated according to the changes in that collection".

Yes, you'll actually have to infer that part. But (Oleg's, vs. Huet's) Zipper is precisely what gives you a "write cursor" into an immutable structure given some consistent iteration interface over that structure. The result of the modification is a new copy of the structure, but one that maximally shares anything that wasn't modified with the original structure, so you don't have the cost of copying the entire structure to face. And it doesn't matter what kind of structure we're talking about as long as it supports the iteration interface. So it's very easy to envision a Zipper over a list of functions to call whenever a certain action is taken, as a degenerate example. Better yet, you could easily provide a Zipper over your entire term graph and do whatever you need in that context. But it's almost certainly not necessary to work at such a low level when tools like Yampa exist. But it remains to be seen whether you'll ever realize that or not.

I have already realized that, as I have posted elsewhere. What you do not realize is that the Yampa example is trivial: it uses a very small model, and one static view (the game view) to show its goodies. I want an example where views are created and destroyed over time.

Of course I understand how to use Zipper, even for views. Because the views are also an application model. But putting it all together (zipper + yampa + monads) makes it rather difficult for me or for anybody else to use FP...and that's my point.

And if you see that benefits of FP can be realized with only ...two years of studying FP, then I have news for you: no one will care about FP; actually reality is that already FP has got a very small percentage of the market - the reason is because FP is mind-twisting, and not because we are accustomed to thinking in a non-FP way.

Please end this thread or take it offline.

[Edit Note]. Ended at admin request.

... is that the "year or two" was only to point out that folks who are familiar with imperative languages as opposed to purely functional ones have spent at least that long mastering them, and that a "different paradigm" that is instantaneously understandable isn't a different paradigm at all. The difference between having mutation and not having mutation is radical; it's one of the few things that the CTM sees as justified in adding primitively to their evolving kernel language that they build throughout the book.

Beyond that, I agree with Ehud: we've put far too much into this, and that unconstructively. I will henceforth hold my (virtual) tongue, but let me part with the observation that I sincerely hope that you find what you seek.

Aka, Teach Yourself Programming in Ten Years (on LtU). By that measure, I'm a slow learner, having been at it for some 2.5 decades (and still counting).

It might only have taken Peter Norvig ten years!

Isn't FP the holy grail of programming? at least this site supports so.

As Ehud has mentioned in the past, this is a site on language design and research, not a site dedicated to functional programming. Furthermore, there are many people here who have expressed the opinion that functional programming is good to know, but not always the right tool for the job. Somebody even wrote a thesis/book on it, and his main conclusion was that functional techiniques should be applied to an object oriented language, and not the other way around.

I can understand your frustration, because when you read papers/articles that advocate functional programming, they only focus on the positives and don't prepare you for the disadvantages.

As Ehud has mentioned in the past, this is a site on language design and research, not a site dedicated to functional programming.

Right! Thanks, Jeff.

The emphasis at LtU is intended to be on the study of programming languages. Studying programming languages necessarily involves developing and using formal descriptions of languages. Functional languages are some of the most formally well-grounded languages — they arose out of formal reasoning, and lend themselves to such reasoning, so there's a natural emphasis on them here for that reason. However, that has nothing to do with advocating FP for arbitrary real-world programming tasks.

The answer to the original topic of this thread should really be mu, i.e. it's the wrong question. Asking a question like "What are the real benefits of FP" is unlikely to yield answers that are useful to the questioner. It's a little like asking the price of something that's very expensive: if you have to ask, you can't afford it. If you have to ask what the benefits of FP are, you haven't studied enough about programming languages in general to understand the answers yet. Start with some of the books in the Getting Started thread, particularly CTM, SICP, PLAI, EOPL, or HtDP, and proceed from there. Hopefully, it shouldn't be necessary to ask "What are the benefits of studying programming languages", but at least that's a more appropriate question.

As for MVC in FP, that's another one for which the answer is mu. What's FP? You can certainly do MVC in Scheme [or OCaml, etc.], for example, and Scheme supports FP. Sure, you'd probably make use of mutation in order to make MVC work naturally. So what? If you're a programmer, as opposed to a language designer, a major point of studying programming languages is so that you will be able to intelligently choose sensible approaches and tools to solve a given problem. Fixating on a single paradigm (particularly in its most restrictive form) and then getting hung up on asking "how do I do X in Y paradigm" misses any possible point. What's the real question? What's the goal? Again, what seems to be lacking here is any real study of the underlying subject, and that study is what we're really about here.

The answer to the original topic of this thread should really be mu, i.e. it's the wrong question. Asking a question like "What are the real benefits of FP" is unlikely to yield answers that are useful to the questioner. It's a little like asking the price of something that's very expensive: if you have to ask, you can't afford it. If you have to ask what the benefits of FP are, you haven't studied enough about programming languages in general to understand the answers yet.

That strikes as a very elitarian position. With that kind of argument, we never were supposed to ask questions about the purpose of something we have not studied yet. How do you know what's worth studying then?

I think the OP's question is perfectly valid, despite the fact that it turns out to be problematic in practice. We should be able to give understandable high-level answers. What the questioner cannot expect, though, is to readily see why these answers or any claims made in them are justified. Understanding that requires studying on his side.

What the questioner cannot expect, though, is to readily see why these answers or any claims made in them are justified. Understanding that requires studying on his side.

This is really the point I was trying to make.

I've replied to the elitism question and some of other points here (just to keep policy-related discussion in one place).

A datatype can easily represent a model. You could be even more explicit about the model with GADTs.
A view can be any typeclass that outputs text, graphics, or whatever. You just make your datatype an instance of that.
A controller could be a separate typeclass that sends input to the datatype.

A collection of listeners could be a list of functions, whether partially applied or built in some other way.

You would register new listeners by adding functions to the list, and disconnect them by removing them from the list.

This is a trivial implementation of MVC in Haskell.

Look at the Zipper datatype as a useful and simple model for an editor buffer. The Zipper has been used in an MVC-like manner to implement text editors in Haskell.
You could have different typeclasses representing mouse, keyboard, or touchscreen input for controllers.
The view could show the buffer on screen in the console, in X, and/or via OpenGL.

Does that sound like MVC to you?

If your data type for your domain model gets big, you can avoid writing boring traversal code using Scrap Your Boilerplate combinators or generic functions.

This is a question I also have. Here is a hopefully a partial answer. Since your system is a simulation there certainly is state. You can't get rid of it, but there is a way to hide it. One can do a serial/parallel decomposition of the system. This results in a flow graph. (ie boxes with inputs and outputs). Now we can visualize the system with the state hidden in the boxes, and treat the boxes as "functions" (is this a correct use of monad?) These input/output functions can only be executed in order like pure functions (ie a nested string). I wonder if this is consistent with the use of monads?

If it's really necessary, you can have mutable state in Haskell, too. Since driving a gui involves IO anyway, it isn't all that painful, but still excessively ugly.

Traversal of large data models can be a huge pain. If that's really the case, the Scrap Your Boilerplate approach to generic programming might relieve you of the tedium. It's sort of a reflection api for Haskell, see http://www.cs.vu.nl/boilerplate/

Don't forget that you can compose functions. If you have functions to update a record and functions to update a list, you automatically get a function to update a list of records by composing them. Doing so cuts back on the number of trivial functions needed. Think of it as the functional equivalent of the Adaptor Pattern.

For me, the single feature that makes a language functional is that of referential integrity i.e. no destructive updates. All other features can happily exist in imperative languages.

I agree completely. I think the so-called FP community gets hung up on too many specific features: currying, static typing, etc. In reality, referential transparency is the biggie, and that's the one that's the fundamental stumbling block. You can talk about all the advantages you want, but they don't address how to write non-toy programs without destructive updates.

I think to support a functional style of programming, a programming language should support at least higher order functions, recursion (with tca), and referential transparency. Closures, algebraic datatypes, pattern matching, and lazy evaluation also help.

Higher-order functions imply closures. On the other hand, I don't see why referential transparency is a prerequisite for supporting functional style (that requirement would imply that you can only program functionally in Haskell, Clean, or some experimental languages).

But if you're debugging a function in Java, C, or whatever, you don't necessarily know the names of the variables that are currently active or what their states are.

I have worked in many IDEs (VS, DevC++, Emacs, Eclipse, Netbeans) but I never had a problem like the one you describe. The debugger view always shows the names of the variables I want to debug, as well as the name of the global symbol (if we are talking about global variables).

If there is a bug, sometimes you must print or log the status of every single active variable after each line of code, to see where and how things change.

If there is a bug, sometimes you must print or log the status of every single active variable after each line of code, to see where and how things change.

You don't have to do that. You can step through the code.

In functional programming, you're guaranteed that the inputs you get are the only pieces that affect function output. You never have to hunt for global variables, and they can never accidentally affect function output. If you're unsure of the state of an input value, look no further than your input list in the function declaration.

I can say that global variables are almost never the problem. A well-written piece of code will have a very limited amount of global variables.

All is well with FP, but, as I wrote above, I have no idea how to code an app with a big object model, and I would appreciate any help.

Java, Perl, Python, and a host of other languages are interpreted languages

Java is not an interpreted language. It is a JIT-compiled language.

But I keep reading that applications written in functional languages tend to have 10%-25% the lines of code compared to their procedural language equivalents.

I will believe that when I see a solution to the problem I described above. One can easily do the stuff Haskell does in a similar amount of lines of code, provided that the language provides some needed tricks (anonymous functions, generic programming, etc)...which leads me to believe that Haskell raises productivity not because it is functional but because it has the right features. To put it in other terms, if Haskell allowed for update of variables, it would no longer be called 'functional', but it would still increase productivity.

Which leads me to believe that Haskell raises productivity not because it is functional but because it has the right features.

Having features x, y, and z are what make it functional. An FP language is merely one that almost exclusively supports functional programming style. C++ could be called object-oriented, but it supports other styles of programming. If you have a language with all these features, guess what, if it's not necessarily an FP language, it still supports functional programming. You're absolutely right, it is the features that (allegedly) make Haskell programmers more productive. But a functional programming language is defined as a language having this collection of features.

Not really. The only thing that separates languages is the referential transparency feature. Take Haskell and remove referential transparency...what would you call the result language? of course, an imperative one.

I have worked in many IDEs (VS, DevC++, Emacs, Eclipse, Netbeans) but I never had a problem like the one you describe. The debugger view always shows the names of the variables I want to debug, as well as the name of the global symbol (if we are talking about global variables).
[...]
You don't have to do that. You can step through the code.

Just my two cents: quite often, I can't. Perhaps my tools are not up to the task, but when working on dynamically loaded C++ XPCom/Mozilla components, too often, it's just not possible to use a debugger.

I was under the impression that the real advantage of functional programming was software engineer productivity

But I keep reading that applications written in functional languages tend to have 10%-25% the lines of code compared to their procedural language equivalents.

Are these intended to be related statements? I have occasionally seen comments that suggests programmers can be more productive in Haskell, say, than C++, because Haskell programs are much shorter. But much of the wasteful verbiage in C++ takes the form of common idioms (eg. writing an explicit loop instead of using a HOF) and the time taken to write such code is typically insignificant compared with total development time. (In a sense you don't have common idioms in a functional programming language, because if you did, you could factor them out.)

I have occasionally seen comments that suggests programmers can be more productive in Haskell, say, than C++, because Haskell programs are much shorter. But much of the wasteful verbiage in C++ takes the form of common idioms (eg. writing an explicit loop instead of using a HOF) and the time taken to write such code is typically insignificant compared with total development time.

A snippet of code is usually read many many more times than it is written. The main problem with explicit loops (or recursion) isn't that it would take more time to write (it does), but that you need to carefully analyze it to reveal the intent of the loop (or recursion). With higher-order functions you just take one look at the name of the function (map, find, filter, ...) and you're done with that part of the analysis.

(In a sense you don't have common idioms in a functional programming language, because if you did, you could factor them out.)

There are recurring idioms in FP-languages and recurring problems that can not be easily factored into a library (in existing languages). This isn't really a characteristic specific to FP- or OO-languages. Rather, this has to do with things like expressiviness, verbosity and programming convenience. For example, it is quite easy to replace explicit loops using the Template Method pattern in most mainstream OO languages (and with HOFs in the OO languages that support them), but it tends to be verbose and not so convenient to use for the "simpler" cases.

I agree that HOFs are often much easier to read than explicit loops. But this is a slightly different issue from that of code development time - though not unrelated, of course.

I think one could make a reasonable argument that fewer lines of code will, in general, mean shorter development time, but you're correct in your observation that nobody has actually (to my own knowledge) performed a study to demonstrate this idea. However, the error here is the assumption that software engineer productivity simply means faster development time. Certainly development time is a factor in productivity measurements, but it isn't the only factor. Ability to reason about the code (either mathematically with pencil and paper or automatically with the compiler/static analysis tools), deduce facts and relationships, and understand code more quickly also play a factor in productivity. If you can guarantee properties of your program, because your using a language that is mathematically rigorous (is well defined mathematically), this gives you a lot of power.

Why do you suppose so many of the “hard” scientists and engineers use so much mathematics? Could it be because it gives them the power to reason and deduce properties of the systems they are studying/building that they would otherwise be unable to deduce and reason about?

You've talked about the benefits of reasoning (you won't get any complaints from me about that, I'm a mathematician) but you haven't related this back to functional programming.

Are you claiming that functional programs are the only ones you can reason about? That's plainly false, I've been reasoning all my life about programs written in a wide variety of languages, both functional and not. As a mathematician I've often had to prove the correctness of algorithms expressed in imperative style. Just about every computer language I've ever used, going back to Fortran, has been 'well defined mathematically' (except with respect to concurrency and asynchronous events, or arguably with the minutiae of floating point evaluation, though even in these cases there are domains you can carve out that are well defined).

Maybe you're claiming functional programs are easier to reason about. This is an interesting claim but it certainly requires some justification. In my own experience I've seem some tradeoffs between different forms of reasoning when moving between C++ and Haskell. So I don't think it's clear cut.

You've talked about the benefits of reasoning (you won't get any complaints from me about that, I'm a mathematician) but you haven't related this back to functional programming.

Yes, I'm sorry; I never did make my final point, did I? Perhaps I jumped on the “submit” button a little too fast. :-)

Are you claiming that functional programs are the only ones you can reason about?

No.

Maybe you're claiming functional programs are easier to reason about.

Yes, this is my claim. Concepts in functional programming (especially immutability) make reasoning about code much easier. You can manipulate and change code according to a set of rules without having to worry about the code changing meaning.

Now, functional programming isn’t a panacea. Functional languages don’t have better mathematical (formal) definitions than other languages just because they are functional (whatever “functional” means). It just happens to be the case that most (all?) modern functional languages have a history of mathematical formalism, thus they tend to lend themselves to mathematical reasoning easier than other languages (which typically have a different history).

I can´t find the source, but I remember reading that Ericson made a study showing that the number of lines made by a programmer is kind of constant independent of the language (the same programmer will do a similar number of LOC a day in assembler, C, Lisp, etc.) before creating Erlang.

Brooks makes this point in TMMM (ch 8):

Productivity seems constant in terms of elementary statements, a conclusion that is reasonable in terms of the thought a statement requires and the errors it may include.

globals are NOT semantically equivalent to implicit function arguments.

They are equivalent to implicit function arguments if you also consider them also to be implicitly returned, like the way "return x" in Haskell might implicitly return state information in the appropriate monad.

Or for the C++ programmers in the room, if they're implicitly passed by reference. Or for the C programmers, if they're implicitly passed by address.

I mean yes, you are right, but the problem with globals isn't how they are implemented (state accessible to the whole program or magical implicit function args) but how they are used.

Yes. In C++ you have a degree of transparency because you typically refer to globals by name. In Haskell, say, you emulate globals by passing variables in and out of functions but hide this passing by using implicitly generated binds coming from monadic syntactic sugar. The precise form of these bind functions depend on the choice of monad and the selection of monad is deduced by the compiler by using type inference from information scattered throughout your code.

I find this "it changes your mind" and "you will become a better programmer" assertions a bit of sectarian. If it fails to change ones mind one has done it wrong. In order to prevent or dissimulate failue one performs autosuggestion to convince onself in doing it right and adopts some kind of group-thinking [1].

In all fairness. What about refactoring some idiomatic code that is considered well done in typical statefull OO languages ( typed and untyped ) into FP solutions and finally compare them?

[1] Yesterday I suggested a beautifully structured factoring algorithm for natural numbers on a newsgroup. A numerics oldtimer, whose knowledge dwarfs my one a few orders of magnitude, explained to me that his algorithm though more ugly and crowded with plenty of special case handlings is not only faster although one would expect a higher computational complexity at first but also won't run into trouble in corner cases. He concluded : "the OP said he was looking for speed more than elegance, and they're not good buddies here". Some things are going to influence my mind as well, of course. BTW the OP asked for a recursive factoring algorithm and suggested one. The solution seemed to be "bizarre" to the numerics expert.

What about refactoring some idiomatic code that is considered well done in typical stateful OO languages ( typed and untyped ) into FP solutions and finally compare them?

This is a good question. CTM has two examples: (1) functional decomposition versus type decomposition (section 7.5.3, page 542), and (2) Flavius Josephus problem: active objects versus declarative concurrency (section 7.8.3, page 558). The main conclusion is that there is no one best way, but that each approach has its uses.

...it's been proven that in the general case, they can't. I think there's something in Okasaki's Purely Functional Data Structures about this. But O'Caml certainly gets close enough for government work. Let's put it this way: Tim Sweeney says that current UnrealScript runs at approximately 10-20x slower than C++, and I don't hear anyone complaining about the Unreal technology's performance, so I'd be perfectly willing to write a game in O'Caml, even if the difference in performance from C++ meant that I'd have to write a JIT for my game scripting interpreter. But I'd be willing to bet good money that I wouldn't need to.

Actually, embedded scripting languages in games generally don't need to be that efficient. The actual engine of the game, though, does, although I agree with your statements (O'Caml is about as fast as C++, anyway).

That was precisely my point. :-) Games are famously performance-sensitive... but it turns out that there's a kernel that has to be super-finely tuned that deals with rendering, physics, and the like, but the code that deals with gameplay, AI, and so on is typically much less so—see Tim Sweeney's presentation on The Next Mainstream Programming Language for details. So given a language that gets me within epsilon of C++ on performance, a bit of tweaking of the scripting language "interpreter" should result in a competitive game, performance-wise.

I already have enough unfinished projects, but the existence of OCamlSDL, LablGL, OCamlODE, and Lua-ML make the thought a very tempting one. LablGL really needs to evolve to support OpenGL 2.0, and I'd need to write a good scene-graph API on top of that. But O'Caml would be an excellent language in which to write a scene graph API!

Ocaml is not as fast as C++ -- I've read an Ocaml developer state that compiled Ocaml code runs roughly 50% of the speed of C code. I'm sure it matches C/C++ for specific operations, but not for a complex app.

Seeing as compiler optimizations are supposed to be much less effective than picking better algorithms, it still looks like other languages are dog slow. I remember reading the main Haskell tutorial, and it had an example of quicksort implemented in Haskell, and basically glowed about how concise it was. Then it made the small mention that it wasn't in place -- thus not being a real quicksort. Are current implementations simply not performant because of this sort of its-close-enough attitude?

dataangel: Ocaml is not as fast as C++ -- I've read an Ocaml developer state that compiled Ocaml code runs roughly 50% of the speed of C code. I'm sure it matches C/C++ for specific operations, but not for a complex app.

That would be Xavier Leroy himself, but note that he's referring to a specific microbenchmark of floating-point performance on 32-bit Intel hardware. A somewhat more interesting comparison can be found here, where we see that O'Caml fares relatively well against g++ and even whole-program optimizing compilers such as Stalin and MLton in 32 bits, and handily beats everything but heavily hand-optimized g++ in 64-bits. Unsurprisingly, there's a great deal of variability in the g++ scatter: that is, you have a lot of control over the code's performance depending upon how much of it you're willing to write. That's less true of O'Caml, although there's an interesting leap in the most heavily-optimized code on the 64-bit AMD platform.

It's actually in more complex, real-world code with non-trivial data structures and algorithms, vs. highly vertical, domain-specific code, that O'Caml really competes nicely with C++, both in terms of concise expressive power and in terms of performance. What's especially nice is that it does so without requiring extensive tuning or even sacrificing things like separate compilation, unlike Stalin or MLton. It also does so without taking forever and a day to compile, again unlike MLton to an extent, but especially Stalin.

But the proof of the pudding is in the eating. You can certainly write slow code in O'Caml, as surely as you can in C++. But give it a whirl, and if the results seem unacceptably slow, ask questions on the mailing list. Chances are that someone will point out some simple, localized changes that can have a definite effect on the results and keep you well within epsilon of the equivalent C++.

Yes. OCaml is about 50-100% the speed of C++ for numerical microbenchmarks but is much faster for most non-trivial (real) programs.

I ported a 25kLOC vector graphics library from C++ to OCaml and the OCaml was about half the speed on average but 5x faster in the worst case.

The main benefit of OCaml is development speed. Despite being relatively new to OCaml, I can develop programs much faster in OCaml than in any other language.

Cheers,
Jon.

They wouldn't complain about Unreal they'd just use another engine or write their own.

Some of the game work being done in Java (which is a lot slower than C/C++ and O'Caml) does prove that high graphics throughput can be achieved though.

But physics and base AI routines are a different story. Matching GCC C/C++ seems out of the question never mind a good compiler like CodePlay.

The old mantra of having performance critical code is C/C++ does apply though. O'Caml for scripting would probably rock (as well as scare the average mod' coder away |:^)

You'll notice that I cheated a bit in my suggestion of game dev tools in O'Caml! For example, OCamlODE is a set of O'Caml wrappers to the Open Dynamics Engine for rigid-body dynamics, which is written in C. I'm not suggesting writing a physics engine in O'Caml, although someone should, just for comparison's sake.

But I don't know that matching GCC C/C+ is out of the question; O'Caml is very frequently within epsilon of C++ anyway. For AI work I'm quite sure I could easily meet or beat C++, not only in performance, but especially in concision and correctness. For physics, it's more likely we'd run into Xavier Leroy's observation about floating-point performance, but it would be interesting to find out concretely.

O'Caml has several good FFIs—I especially like Forklift, since I can annotate a header I can't directly modify and still make use of it—and thanks to Saffire we also can do some very good analysis to ensure that our use of the FFI is, in fact, type-safe.

O'Caml as a scripting language itself is an interesting idea! I guess I'd have to use Asmdynlink in that case, to allow my native engine to dynamically load O'Caml bytecode. What I was proposing was something a bit less weird to most programmers: to take advantage of Norman Ramsey's work in embedding Lua in O'Caml. Lua is quite popular as a game scripting language, having been used extensively by Lucas Arts in some dozen or more titles.

You may well have point about AI, although what I had in mind is the AI core routines like path finding. On deeper thought however most AI is really decision and dispath so O'Caml would probably be pretty well suited. I totally agree with your concision and correctness arguments.

ODE bindings seem to be popular in most non-C/C++ game efforts.

GCC has widened the gap slightly with version 4.x, SSA (which ironically has functional connections) is doing pretty well for them.

O'Caml as script from a purely semantic perspective would be great but I would be overcome by 'the fear' that mod writers wouldn't like it, even with the promise of less bugs. Syntax wise ML derivatives can be a acquired taste. I must check out this LuaML work though, sounds very interesting.

For AI work I'm quite sure I could easily meet or beat C++, not only in performance, but especially in concision and correctness.

A few years ago, as a student, I wrote graph and pathfinding algorithms both in macroized C, templated C++ and polymorphic OCaml. I don't remember the statistics, and they wouldn't prove much, but basically, it boiled down to this:

• the OCaml code was about 5 times shorter than the C code, itself about 5 times shorter than the C++ code
• the OCaml and the C code compiled instantaneously, while the C++ code took several minutes
• on my testbench, they all performed similarly (i.e. they all returned the proper result too fast for me to measure with time)
• the OCaml code was developped about 3 times faster than the C code, itself about 10 times faster than the C++ code (dangling pointers are nasty, especially when they are due to unclear bits of the C++ "specifications").

Note that I didn't use the exact same algorithms in each language (the C version could modify the graph during traversal, while the C++ and OCaml versions couldn't).

Why would you expect them to? C is basically a macro assembler for the PDP 11. It's hard to beat assembly language on a given processor...

Now look at what came after that: general purpose CPUs jump through hoops so the assumptions C makes aren't grossly violated (think out-of-order-execution with complicated retirement, think cache coherency protocols). So they are built to emulate a PDP 11, and again, how would you beat the native assembly language?

All other processors fell into oblivion. Data parallelism didn't work out (not even MMX and SSE are really supported by compilers, IA64 was a dud, no vector processor has survived, no data flow processor is in common use (think PACT SPP). The common reason is: because you can't get performance out of them if you want to program in C. (And I really think the guys behind PACT are stupid for never porting a Haskell compiler.)

Now what was there first, the hen or the egg? I'd say nothing beat C because of a terrible accident. But parallelism is gaining importance, and C loses there. Watch out what happens on the Cell processor, then watch for its successor.

One good reason would be because most of them are still having to compile via C.

I already posted my reply about the Yampa game.

The Yampa approach does not cover my request (or if it does and I don't understand it, please someone explain it).

(I'm not a Haskell guy. Most of my work is in C++. But I did a fair amount of what resembles functional programming in C++ for a couple years, in an attempt to control some problems in a scaleable HTTP caching server. It often would have been simpler to do in an actual FP language, or partially FP. I often think about how to do that sort of thing better than I did last time. Erlang would have made it simple.)

Achilleas Margaritis: No one has replied to my request yet. What's up? is it is problem that Haskell can not handle?

It was a good request, in the sense thinking about an answer is fun and interesting. :-) But my ideas so far have too much length when verbalized. I wish we could chop it into pieces; I'm sorta waiting for that to happen, to avoid a need to write more than a few hundred words at a time. I'll just start here, and resume later after letting other folks jump in and say something.

There's a useful model to hold in mind while considering these questions of refactoring imperative code into a more functional style. Right now I'll just mention it without much explanation of why the model is relevant: source code control systems. A typical SCC model keeps around the history of past values of things -- source code entities -- until you discard it. You can branch code wherever you want, and different users can work with different versions of code at the same time, on different branches.

(This model is closely related to the idea of long term transactions in databases, which might or might not spark different ideas.)

When you simulate imperative code in functional style, you can simulate update by branching old content while replacing changed parts with new content, and just keeping old content that hasn't changed. (Note when data is immutable, it's especially easy to share common parts, then simulate copy-on-write by patching out changed parts with newly generated replacements.) You need only allocate new space proportional to what's changed. Old content that no one is using (no other thread for example) can be gargage collected once no longer referenced.

(Some server models are simplified by letting current outstanding serviced requests continue un-interrupted, even when using data to build a response that has gone out of date since a request started. You can have multiple copies of data in a system -- different versions of the same object -- with older versions going into oblivion when no longer in use. This approach avoids complexity in trying to make everyone see the same version at the same time.)

To simulate an imperative MVC system, you can generate new versions of your model sharing all old unchanged state with only new space used for the updates. Asynchronous message passing can be used to notify views they should attempt to re-render the presentation, which presumably will use the new model, perhaps because a reference to the new model is passed in the message. (That would let you avoid the issue of whether you need to update a directory of "current" model information.)

Okay, it's 2am in the morning and I'm turning into a pumpkin. Is any of this sounding useful yet?

Oops, forgot to say you want your model to avoid being a strongly connected graph, since that will make copy-on-write patching hard to do. If children nodes know about parents, you can't replace a parent without also needing to replace a child. If your data is tree structured, and children don't know about parents, then you can share tree substructure easily by using new parent nodes with only as many new children as necessary.

Thanks for your reply, it sounds good.

Unfortunately, my model is a strongly connected graph, because each child has to have a link to its parent.

What do I do in this case? perhaps I should place all my objects in maps, and keep an id in children objects instead of a reference to the parent. I do not know if it will work, but it will further slow down the application due to map lookup.

Does it really need to save the link to the parent, or can you pass in the parent object to the methods that need access to said parent? This would break the loop, which would allow for copy-on-write.

I think it is really needed. Let's say there is an open editor of a child component (target, for example). As the user edits the data, the target object notifies its parent to set the modified status to true. The target's parent sends the message to its parent etc until the message is bubbled up to the scenario object. Then the scenario sets its 'modified' flag to true. The persistent document, in this case, is the scenario.

Let me assure you that Achilleas has been told about the zipper before. Let me assure you that there are very few things that Achilleas hasn't been told about before. Please don't feed the troll.

Let me assure you that Achilleas has been told about the zipper before. Let me assure you that there are very few things that Achilleas hasn't been told about before. Please don't feed the troll.

I dot not recall seeing the zipper anywhere, and certainly I am not a troll.

After studying the idiom, it seems like a set of functions that reassembles a structure (a tree, in this case) after some algorithm is applied to the structure. It is no different than what I have thought of so far, but it is one part of the problem, namely how to update the data.

I guess a list of functions can be attached at each node (i.e. the listeners) that compute a new UI state...but then this state will have to be "reassembled" too and returned to the outter context, just like the data model (the UI is also a model, let's not forget that).

Assuming the approach works, there is still a problem: the data model and UI model are highly coupled...where as in the MVC paradigm they are uncoupled.

Ok, let's go over it again:

1) The program reads events from the window manager; the user enters a value.
2) the event is caught by some widget.
3) the widget's callback is invoked which alters the data model of the application. A new data model is returned to the main loop along with the event of changed model.
4) The changed model has signals attached to it which are executed. The signals return a new UI model.
5) the new UI model is fed to the event loop, so back to 1)

Within the course of action, some callback will modify the UI model to include a new dialog, for example, and the new dialog would contain some view of a model. The view will be attached to the list of views the model notifies.

The creation of a new view implies that the whole data model is passed to the new view function, so as that the zipper idiom is used to reconstruct the data model with one more view.

The modification of the model implies that the whole UI model is passed to the new state function, so as that the zipper idiom is used to reconstruct the UI model with one the modified view.

But how is that the MVC pattern? all the above is not the MVC pattern, but a set of functions which modify the application's model (data model + UI model) when something happens. I could have done it without thinking about MVC at all, as a set of functions that alter one or more values...so, for example, when the user enters a new value, a function simply computes a new data model and UI model.

But if I do it in the above way, one of the principles of MVC is lost: my functions have to know everything about the data model and view model of the application...whereas in the imperative MVC I modify the data and the rest of the program behaves accordingly, with the functional MVC approach I have to pass the whole app's state around.

Not to be rude, but first let's establish some no-Lucy rules. In the Peanuts cartoon strip, Lucy was famous for tricking Charlie Brown by holding a football so he could place kick it, only to snatch it away at the last second, so Charlie does a hilarious pratfall. How does that apply to this conversation?

I assume you actually need functional programming (FP) or that you want to do it as an exercise, and you'll accept complexity costs yielding benefits in situations where FP actually helps -- we can spell that out later. (I don't want to sell FP, only to be told each technique seems ridiculous because "unnecessary". That would be Lucy yanking away the football at the last second. Necessity is a given only as your choice, okay? :-) I understand the original OP questioned benefits of FP, but I'm not addressing that. I just care about the how-to subtopic. What I quote is always a strong focus for my context.)

Achilleas Margaritis: Unfortunately, my model is a strongly connected graph, because each child has to have a link to its parent.

For copy-on-write, you want to remove instrinsic cycles from your model's graph. You can refactor your model so this works; the most clear and least painful way probably depends a lot on how your code uses the data, so it's pretty context dependent. You suggested one way of making a separate map representing the relation of child to parent. There are more ways, but some are hard for me to describe (since I just made them up as I went along, and I surely use non-standard jargon to describe them).

When I worked on btrees in the past, I almost always navigated from tree root to leaf every time I performed an operation, and the child-to-parent relation was maintained on the stack (ie in the thread continuation), and this was always sufficient. In a FP style language, you might chain this relation incrementally backwards. In C++ I tended to allocate all state at once, up front in a top level method, because each tree had a small maximum depth given an address space of only 32 bits.

To generalize this technique, I might say your continuation (thread of control) can maintain missing state you wanted in your model, but was factored out to allow sharing. The combination of shared model and execution thread together have enough knowledge to work, even if the shared model alone is not enough. Making this really cheap and high performance might depend on clever observations about how your threads actually use the model.

So, partition your model into 1) a shared acylic part with nice copy-on-write properties, and 2) an unshared part supplying the rest of your model's graph. Where to put the unshared part depends a lot on your language and design whims. When folks tell you how to use langauges like Haskell, they are often telling you where to put this second unshared part in the flow of control. (I expect they assume this model partitioning tactic is obvious from long past experience.)

Copy-on-write is an optimization aiming to be equivalent (under referential transparency) to a simpler but more expensive approach of just copying everything. Sharing is a form of compression saving both time and space, but increasing complexity. As noted elsewhere, constraining resources does increase development time. But copy-on-write is a very well-behaved optimization that doesn't get nastier as you approach 100% correctness; once you buy the problem, it's easy and accelerates as you finish because it gets more obvious.

FP and copy-on-write might sound too complex for a simple, small model managed by one developer with only one reader and one writer thread, developed only one time without revision. But managing state models gets more difficult, though, as you add more developers, threads, scale, distribution, model versions, and code versions. The more chaos you introduce -- and the harder it is to fit all models at once in your address space -- the better it is to simplify things with shared immutable data, at which point FP style begins to shine.

As growing complexity causes you to lose knowledge of exactly what to do, it becomes dangerous (to your plans and features) to share mutable state and update in place, especially with multiple threads. It becomes safer to version content to avoid conflicts. Then to keep costs under control, optimization begs for sharing and copy-on-write, which increases complexity again. But this additional complexity is fixed point and not chaotic.

Hello again. I was referred to your article by a few people who found it useful and interesting, so you could consider it successful.

I haven't ever really thought of attempting to write a game in Haskell or Concurrent Clean. Hmmm. This sounds like it might be a job for delimited dynamic binding, assuming that there were reasons why FRP wouldn't work for you.

There are "non-trivial" games written in Haskell with source code available, (both of) you could look at them to see how they handled this issue. Some are listed here.

One point though*, even Haskell programmer's aren't rabidly zealous about using mutable state especially in it's more controlled form in Haskell. I think one impression some people may get about practical pure functional programming if they only read discussions and articles like this is that Haskell programmer's will jump through all kinds of hoops to avoid an IO/STRef or any kind of side effect. Sometimes a mutable reference cell (and mutable data structures etc.) is the simplest most straightforward technique you come up with, perhaps there may be a different, more functional, approach to your problem, but implementing the program is the goal not "being functional".

* This isn't really directed at Paul. It is certainly valid to want to see what more functional approaches are available.

I'm not a Haskell programmer mainly because, like Peter Van Roy and Seif Haridi, I find it a bit much to have to use monads all of the time. But that doesn't mean that I don't appreciate the purity conceptually and enjoy having the option of using it. In fact, I just posted in another thread that I asked Oleg Kiselyov to bring his monadic delimited continuation implementation in O'Caml into his, Lydia E. van Dijk, and Jacques Carette's pa_monad syntax extension for O'Caml, and he did. So now I have delimited continuations in ocamlopt-compilable O'Caml, at the cost of having to code in the monadic style, but at least I have the Haskell do-like "perform" syntax to keep it from being too ugly.

Still, your point is well-taken. I'm painfully aware that I take on the role of FP zealot here, despite having said many times that I greatly appreciate dynamic tools like Common Lisp, Scheme, Oz, and E, and the most educational interactions I have here are with the brilliant and articulate supporters of the dynamic tradition: Anton van Straaten, Peter Van Roy, and Mark Miller particularly come to mind. I just got my CTM back from someone at work I'd loaned it to, and I think it may be time to commit to working through it, to regain some balance I feel I've lost. In any case, I think it's time for another breather from LtU; I don't feel like I'm adding value these past few months, I have a crushing deadline at work in July, and I should spend more time with family, especially with a stepson who's just graduated from high school and will be off to college soon. Thanks for the feedback, and I'll be back soon!

The footnote was intended to imply that the second paragraph was not directed at you. In the second paragraph, I wasn't referring to you or anyone in particular, nor was I pointing out any deliberate bias; rather most of the discussion that comes up on LtU and the kinds of articles it links about FP and FP techniques tend to explicitly be trying to achieve a strong functional style or are assuming a strong functional style. This is perfectly fine; the goal is how to do something in that style, but real Haskell code, while still much more strongly functional than any other language, is still more multiparadigm (and unfortunately "dirtier") than the impression many academic papers and Haskell intros would give.

I'm painfully aware that I take on the role of FP zealot here, despite having said many times that I greatly appreciate dynamic tools like Common Lisp, Scheme, Oz, and E, and the most educational interactions I have here are with the brilliant and articulate supporters of the dynamic tradition: Anton van Straaten, Peter Van Roy, and Mark Miller particularly come to mind.

I'm pretty sure that many readers probably consider me to be a Haskell and/or static typing "fanatic" perhaps even "zealot" too, despite, like you having pushed pretty much the same set of languages (though I'd also stick in Self).

I don't feel like I'm adding value these past few months

I disagree (though you still owe us that POJO presentation...).

You can always rebuild identity by tagging your objects with a number and going from there.

Let the anti-Greenspunning commence!

Um, what? All the politically charged words and phrases have overwhelmed the programming language content of the message, at least for me. I see programming languages mentioned in the post, but I don't understand how the politics and PL's fit together. I don't follow politics closely, so I probably don't understand the nuances of the terms.

When I read LtU, I'm expecting messages that follow the etiquette and have the tone that Mitchell N Charity suggests here. As it stands, this message confuses me.

Befor there were OO or FP, or even software there was the so called Cybernetic age. Cybernetics was the paradigm of the 1940's and 50's, popularized and formalized by Nobert Wiener's book "Cybernetics" in 1949, and the information theory of Shannon and Weaver. Cybernetics was a theory of everything, and the cybernetic age was an age of human and mechanical/electrical parts communicating by teletype and paper tape. It was goal oriented and "feedback" was a central concept. After 1960 with the first transistorized general purpose computers it was clear that the age of cybernetics was over and the new age of software and digital processing had dawned. In the rush to be "with it" old ideas like systems theory were no longer popular, and attention shifted to the new paradigm of software.

In the last 45 years systems theory has come a long way without being popular and software while popular seems to be stuck in the mud. This I think is because the software disciplines define their problems too narrowly. Software is all about implementing systems: even when all the parts are software, systems theory still applies. I often think that the so called "software problem" is really not a problem with software but a systems theory problem. Or put another way you can't do software without systems theory.

I strongly disagree with Anton van Straatens position that we shall ignore the "paradigms" and study languages instead.

Perhaps I expressed myself poorly, so let me take another stab at it. All I'm really saying is the following, which I'll highlight on its own line because it's a short and simple thesis which might be easily missed:

Learning about the theory of programming languages will give you the tools to understand programming paradigms more easily.

Because of this, in the context of LtU, it doesn't make sense to try to learn about new programming paradigms if you haven't at least studied some basic PL theory of the sort found in CTM/SICP/EOPL/PLAI, etc. (And by study, I mean including experimentation, doing exercises, writing interpreters, etc.) Once you do learn some PL theory, it becomes possible to evaluate and understand programming languages and paradigms in a way that isn't possible otherwise.

I'm not saying that anyone should ignore paradigms, but if you're reading LtU, studying a specific paradigm before you study the general theories is putting the cart before the horse.

As far as the political perspective on it all goes, studying theory is a good way to get beyond that, to a place where you can be somewhat objective (within human limits!) about the advantages and disadvantages of different languages and paradigms, and be in a position to assess things for yourself, rather than relying on the madness of crowds to lead in you in a direction that's guaranteed to be temporary.

In fact, I believe that what I'm saying at least partly addresses a comment which you made earlier, in response to Derek Elkins:

I find this "it changes your mind" and "you will become a better programmer" assertions a bit of sectarian. If it fails to change ones mind one has done it wrong. In order to prevent or dissimulate failue one performs autosuggestion to convince onself in doing it right and adopts some kind of group-thinking.

I agree with you on this. If all you're doing is learning to program in OCaml, Haskell etc. then you're relying on luck and intuition to figure out what their real benefits are. It's easy to be misled by hype about particular features when you don't have the grounding to see through that hype.

The way around this is to learn theory. Theory gives you general frameworks with which to evaluate languages. Theory will "change your mind" and "make you a better programmer" because you will learn about models which encompass all programming languages, you will learn how things can be expressed in their most general form, you will learn how to approach problems with greater formal rigor.

Having learned the theory, you will not necessarily come to the conclusion that FP is the greatest thing since sliced bread — but you will be able to more clearly see its advantages and disadvantages, and contrast it to other systems using the general models you've learned. You will more easily be able to apply the important underlying theoretical principles that you've learned in any language, FP or not.

I seem to have lost my memory why I disagreed with you :)
Personally I consider language theory ever more as a kind of joy which goes beyond just mastering PLs - but is for obvious reasons not decoupled from it.

I don't mean to imply that software engineers know nothing about systems theory. Recent work such as coalgebra of systems is done as theoretical computer science. Also there is a rather philosophical side to modern systems theory that may not be very practical.

To say that software is in part systems theory or cybernetics is to recognize the basic idea of cybernetics. A system description is independent of its embodiment: software, hardware, or organic. For a hardware engineer seeing the "system" is easy because it must be made from a collection of real things. For a software engineer the system may be more difficult to visualize. This is why I brought up old fashioned cybernetics. Try to imagine your system in terms of these old parts (ie people, discrete devices, simple communication, etc.) I often think of software as hardware, and then apply whatever analysis I need. Historically this transition of hardware to software actually took place. Of course this is much of what design patterns are about but with a different spin. However I probably am oversimplifying a complex situation.

To clarify: Do you mean that software engineers should think of the people (e.g., users) as part of the software system, or was that bit merely an example of the the cybernetics approach?

Ehud Lamm: Do you mean that software engineers should think of the people (e.g., users) as part of the software system...

I think it depends on the questions you ask. So it's 'no' when you ask a question about (formal) structure and behavior in code with respect to compiler or vm. But it's often 'yes' for questions at a scope including people (users and/or developers) as significant forces. It's usually 'yes' for me when I ask questions about what's going to happen in the future of a project or technology.

For the last several years, the biggest problem I've seen in software development has usually been communication (typically the lack of it) between team members. Lack of communication can easily pass without notice when folks assume others share the same assumptions, goals, agendas, etc. It's hard to gather evidence about what others think if the issue doesn't appear in the code immediately.

(Some unknown percentage of developers seem to play a game based on this difference, since obfuscation pays a reward in strategies that payoff when coworkers seen as competitors do less well. Yes, this is perfectly creepy, and hard to imagine -- and therefore notice -- when you're a straight shooter, like me. It can help to simulate contrarian tactics in your mind, so you can recognize risk when coworker behavior matches the simulation too closely. It's a sad part of life.)

When politics, marketing, cognitive psychology, and philosophy affect the outcome, you need to include people as part of the software system, especially if the effects might be large compared to the purely technical end of things. Cognitive psychology is perhaps the cleanest of them; a software engineer should worry about whether designs will work well with how people think.

The cybernetic approach certainly may include the users of a system, but what I was actually thinking of was people moving objects on a situation board or running a teletype machine. The command and control system used by the British during the battle of Britain was designed as a system in the cybernetic sense. Today the same functionality would take place as a system of computer programs.

Back to the first part of your question:
Do you mean that software engineers should think of the people (e.g., users) as part of the software system,
The user isn't part of the software part of the system but part of the system. The answer is yes. There are methods for doing this but I am no expert. More generally the environment of the software (ie human user, or other software or hardware should be considered as part of the system. Edit: Somebody better do it!

An article with relevant ideas, although focused on software developers as part of the development process rather than on users as part of the system, is Characterizing People as Non-Linear, First-Order Components in Software Development (previously mentioned on LtU here).

IMO, the system-theory approach is extremely helpful when you're designing a computer system. Designing independent components that react smoothly to their inputs, and then building negative feedback loops to maintain dynamic stability works really nicely. But this approach just crashes, burns and dies if you try to apply it to a larger system containing humans in it.

The reason is that people don't respond incrementally to the local feedback they get -- they look at the system as a whole and then game the system to get the best result they can for themselves. Economists ran headfirst into this in the early 1970s, when the economist Robert Lucas pointed that the macro-economic models the government was using to manage the economy weren't working because the people in the markets ran those models themselves, and then pre-emptively based their decisions on predicted government policy. Economists call this the Lucasian critique, and what it means is that you have to build up the behavior of a large system from the microfoundations of how a people-containing system will behave based on the real incentives that the actual participants in the system face.

The upshot is that you can't design a system with people in it and expect to specify the behavior of people in the same way you can specify the behavior of a thermostat or stack ADT. That just doesn't work. A successful computer system must work so that it aligns with the grain of human interest, rather than trying to override it.

But this approach just crashes, burns and dies if you try to apply it to a larger system containing humans in it.
There are all sorts of human factors. One might be interested in only typing speed or eye movement or other psychological factors. At the other end of the spectrum one might be interested in something like stock prices. In this case you wouldn't model the trader but simply analyize charts as if a system were present, and try to predict that system. People do it all the time but it isn't clear how well it works.
A successful computer system must work so that it aligns with the grain of human interest, rather than trying to override it.
I agree with that!

Overriding means initially non-acceptance. But the designer also has to care for reducing volatility and contradictions. In some cases a rational approach that lets the designer divide the system and adapt it to particular user sub-groups may also fail because a group might want to see itself as a collaborative whole which embodies standardized routines and works efficiently. But the group isn't and therefore it is always in trouble with itself. Systems development will become an inevitable part of "group therapy". This is metaphorical but I know what I'm talking about. I will meet such a group an hour or two from now :)

After reading the responses, I feel I should again turn your attention to this paper.

After rereading your question you may be interested in the idea of hybrid systems . Often important things happen in the transition from one medium to another. Such as analog to digital conversion. A human user of a software system seems like another kind of hybrid.

For all you history buffs W Ross Ashby's Introduction to Cybernetics is now free on line. In its day a basic introductory text. It is interesting to compair this book to the modern coalgebra of systems. Coalgebra proves and expainds on these ideas but the original cybernetics has a very practical point of view that is still usefull.