## Functional programming and software engineering

When I encountered discussions about OO vs FP on LtU the first time my immediate response was that FP likely doesn't lack anything technology-wise but something essentially different: a discourse about modeling and design that is devoid of implementation or PL feature considerations but mostly strategic. A strategic approach is for instance object oriented analysis and design: start with a decomposition of a system into objects. Identify their responsibilities and relationships ( modularization / class diagrams ), their behaviour and interactions ( methods ) and their properties ( member variables ). The choice of a projects programming language is than influenced by its attitude to embrace the design/modeling strategy and not by other considerations that are secondary to this process: whether it favours recursion over iteration or enables the compiler to safely exploit cute little identities among combinators granted by referential transparency.

There has been a funny polemics by Steve Yegge some time ago about Java as the kingdom of nouns that caricatures the obsession of subordinating verbs ( functions ) under nouns ( objects ). The only immediate inversion of this subordination I'm aware of is that of category theory but I didn't notice yet a push of "general abstract nonsense" into a handy toolset that guides the programmer from customer requirements to program code. At the moment FP is advocated in terms of compensations or vagueries. It improves your quality as a programmer even when you write code in Java or C++ and it is "mind expanding" ( whatever this means ) or it is praised as the future of programming because once again it simplifies the life of compiler authors to deal with parallelism. It's always hard to distiguish hope from defiancy.

What do you think, are there approaches to transcend the current state by envisioning a new "big picture" or am I'm just wrong in my analysis and so deeply brainwashed by my education that I overlooked the obvious and eternal truth? In the latter case I would be grateful about a "mind expansion".

## Comment viewing options

### Call me Van Helsing

I hope to drive a stake into the heart of this undead monster that has terrorized our LtU countryside for too long, one of the dreaded X vs. Y vampires that drains the intelligence out of a thread when we least expect it.

This particular blood-sucker, OO vs. FP, having escaped from its natural habitat of TransylSlashdot, has been second only to that Other One That Shall Not Be Named (you know which one I mean...) in turning threads into the zombified living dead, and really there is no need for it.

OO and FP aren't diametrically opposed and their impact on satisfying customers or on high-level design of software is not that big.

In any programming, you need some way to group data together into meaningful units, and some way to group operations together into practical units, whether you call the mechanisms functions, methods, procedures, objects, modules, ADTs, or anything else.

Sure, there are a range of choices about the details that need to be made, but to call yourself a master programmer you need to understand ALL of them, with the design trade-offs they all imply.

As for making well-designed software that fulfills customer needs, the OO/FP discussion is ultimately utterly irrelevant. At the level customers care about, visible features that accomplish particular tasks, all the OO/FP blather is a mere question of implementation details, all sound and fury, signifying nothing.

Someone who understands how to elicit requirements and turn them into a coherent design can do so completely abstracted away from the choice of "paradigm", and someone who doesn't can't be saved no matter how religiously they follow their chosen paradigm.

So let's drive a stake into this one once and for all so we can all return to being happy LtU villagers who can discuss the ideas of real consequence to our field of interest without the fear of being bitten by an undead thread in the night.

### Is This the One...

...where some mysterious animal/monster terrorizes the villagers until we discover that it's really modern times, and the village was simply trying to escape violent crime by establishing the village in a wildlife preserve and pretending it was still the 19th century?

Certainly, hiding behind a given paradigm strikes me that way. :-)

### Hollywood, here I come...

Hey, Paul, you've given me an idea!

Maybe I should pitch my post as the basis for a movie script.

It could be educational and really scary at the same time. ;-)

### OK... "Van Helsing." Now what?

In any programming, you need some way to group data together into meaningful units, and some way to group operations together into practical units, whether you call the mechanisms functions, methods, procedures, objects, modules, ADTs, or anything else.

True, but you don't necessarily need a way to group operations and data together into meaningful units. And you definitely do not need grouping data and operations to be mandatory, as in Java.

At the level customers care about, visible features that accomplish particular tasks, all the OO/FP blather is a mere question of implementation details, all sound and fury, signifying nothing.

Utter nonsense. Homeowners care about details that aren't visible (e.g. I wouldn't want my roof to collapse in a rainstorm, even if I lived in a desert), and software is a far more malleable thing. Its foundations are important, as they are directly reflected in the final product (and its reliability). Different languages have a large effect on the way we think, and the way we think has a profound impact on how we approach projects.

Someone who understands how to elicit requirements and turn them into a coherent design can do so completely abstracted away from the choice of "paradigm"

Untrue. Design isn't necessarily so abstracted. Specification might be, but it has its own sets of abstractions that are important.

and someone who doesn't can't be saved no matter how religiously they follow their chosen paradigm.

True.

### Have a garlic pill

And you definitely do not need grouping data and operations to be mandatory, as in Java.

You have moved from the general (OO) to the specific (Java). Individual languages make different choices often independent of their putative paradigm; that doesn't really affect the argument. A poorly designed exemplar of a paradigm doesn't define the paradigm.

Utter nonsense. Homeowners care about details that aren't visible...

Are you seriously saying that customers care about whether you implement a particular feature with an ADT, say, or an object?

Customers care about reliability, performance, etc, but what does that necessarily have to do with a particular paradigm?

Different languages have a large effect on the way we think, and the way we think has a profound impact on how we approach projects.

Search for "Sapir-Whorf" on LtU if you want to know what I really think of this argument. ;-)

My own experience is that, the more you understand different paradigms, languages and design approaches, the less constraining the individual language is to your thinking.

One's native language is only a limitation on expressive possibilities until you a fluent in another one.

Untrue. Design isn't necessarily so abstracted.

Ah, you're right. Let me rephrase: good design is abstractable from implementation. If you don't understand your problem independent of implementation, how can you know if you have a good implementation or not?

### Straight outta Gilroy

Quite true - I misattributed some earlier statements about Java to you.

Are you seriously saying that customers care about whether you implement a particular feature with an ADT, say, or an object?

I'm saying that as professionals, we should care on their behalf. Craftsmen can bilk more hours and incur lower costs (for themselves) using inferior tools. That doesn't mean respectable professionals do that. Customers don't care immediately whether the code sucks or not, as long as it works now, for this project. But we still have a professional (and personal, for most of us) responsibility to care about factors that affect the longer-term view of systems as intellectual assets.

Customers care about reliability, performance, etc, but what does that necessarily have to do with a particular paradigm?

We may not be disagreeing here, but to imply that paradigms have nothing to do with the "-ilities" is to imply that they're roughly equivalent tools. I disagree with that. There are other more important success factors, but I think OO is strictly inferior to both FP and relational, for nearly every job.

Whether O-O is wholly subsumed by an FP or relational "sub-paradigm" is an argument for bigger brains than mine, but CLOS and Alloy (for example) both strongly suggest that. CLOS "does objects" better on an FP core than most O-O languages I know, and Alloy shows that common object concepts are a mere subset of relations.

So yes, customers care. They just don't know that they do. :-)

### Eat my brain

I agree with Marc about the irrelevance of OO "vs" FP — that's a red herring if I've ever seen one. However, I'll risk feeding an undead zombie and respond to some of these points, since they don't match my perspective on FP very well.

When I encountered discussions about OO vs FP on LtU the first time my immediate response was that FP likely doesn't lack anything technology-wise but something essentially different: a discourse about modeling and design that is devoid of implementation or PL feature considerations but mostly strategic. A strategic approach is for instance object oriented analysis and design: start with a decomposition of a system into objects. Identify their responsibilities and relationships ( modularization / class diagrams ), their behaviour and interactions ( methods ) and their properties ( member variables ).

I'm not sure if I've understood this correctly, but if you think FP lacks this strategic orientation, I'd say that's the exact opposite of the reality: it'd be more accurate to say that FP is primarily about such a strategic orientation to analyzing and decomposing problems, without resorting to the kind of low-level details that so often creep into programming in popular languages.

In theory, OO is also about such high-level analysis. However, in practice, in the current crop of OO languages, programmers often avoid abstractions and instead (ab)use basic data structures such as arrays, or whatever core data structure is offered by the language in question, so that many abstractions end up as latent rather than being explicitly encoded in the program. This representation-oriented approach is quite pervasive, and many languages, OO and otherwise, either encourage it or at least do nothing to discourage it.

If anything, FP seems unfamiliar to many OO programmers because it doesn't support these abstraction violations as easily. This seems to be the opposite of what is being claimed in the quote above. Programmers who are used to having their representation-fixation pandered to can get a bit lost when they encounter a language which doesn't pander as much.

To give a concrete example, the other day in comp.lang.functional, someone was struggling to implement tic-tac-toe in OCaml, and pointing out the comparative simplicity of the same program in Python. In both cases, the chosen board representation was a three-element array of three-element arrays of characters. Compare that representation to the one used in this paper:

data Mark = X | O deriving (Ord, Eq, Show)
type Loc = (Int, Int)
type Board = FiniteMap Loc Mark


Which approach is "mostly strategic"?

Note that a good OO analyst would certainly come up with something roughly similar to the latter, which underscores Marc's points. But the difference is that "strong FP" languages aren't always as forgiving if you don't use abstractions appropriately.

whether it favours recursion over iteration or enables the compiler to safely exploit cute little identities among combinators granted by referential transparency.

I'd agree that there is sometimes an overemphasis on such details, but as much as anything else this happens because programmers investigating FP (or any unfamiliar language) often do so in a bottom-up way, focusing first on specific technical details which seem different, and only later beginning to grapple with the bigger picture. Most of the topic post's discussion of FP seems to be roughly at this level; whether that is intended just for rhetorical purposes, I can't tell.

Besides, I don't think the real issue is "whether it favours recursion over iteration", but rather whether a language supports recursion well, in addition to iteration. Supporting only one or the other shouldn't be acceptable, and it's only an accident of history that languages which do so are blithely accepted as being perfectly normal, rather than irredeemably crippled. (Sorry for the dogmatism, a zombie just took a particularly large bite out of my brain.)

While support for recursion might seem like a low-level detail which isn't relevant at a higher strategic level, it feeds into a much larger question, which is the ability of a language to express abstractions. Full support for higher-order functions and recursion (which necessarily includes at least some optimization of tail recursion) supports the expression of abstractions that are tedious to express in languages that don't have such features. This is primarily a high-level strategic issue, and the implementation details should in theory only be of interest to language designers, except for the fact that we live in a world where one cannot take for granted the simple ability to e.g. nest one functional abstraction inside another.

So we tend to focus on language implementation details because they're a concrete manifestation of larger, more abstract concepts, in the same sort of way that political discourse sometimes focuses on subjects like abortion as an embodiment of a conflict between much more abstract principles.

At the moment FP is advocated in terms of compensations or vagueries. It improves your quality as a programmer even when you write code in Java or C++

I guess my comment here might be considered an example of this. However, the only reason vagueness comes into it is because it's difficult to boil down a rich body of knowledge into a few sentences for someone who is unfamiliar with it.

In any case, for me, "FP" is not really the point. The point is rather that if one wants to be a better programmer, or expand one's knowledge and understanding of programming or programming languages, it makes sense to study principled sources of knowledge on the subject. Learning about FP is a side effect of such study. It should hardly be necessary to "advocate" FP in the study of computing, any more than it's necessary to advocate mathematics in the study of, say, physics.

or it is praised as the future of programming because once again it simplifies the life of compiler authors to deal with parallelism. It's always hard to distiguish hope from defiancy [deficiency?]
It can simplify the life of anyone dealing with issues of concurrency — not just in the parallel processing context, but in ordinary multi-user systems. The benefits of functional purity are well-known even in e.g. the Java and C++ worlds, at least amongst those who work with systems that are impacted by such issues. Both Java and C++ have type systems which can statically enforce purity on specified variables and functions/methods. All the discussions that have appeared on LtU of the problems with shared-state concurrency are not just theoretical: take a look at the people who have raised such issues — most of them are not academics. So there's neither hope nor deficiency here; rather, real, proven solutions (see e.g. Erlang) to problems that have tripped up rocket scientists (probably literally) in less functional contexts.
What do you think, are there approaches to transcend the current state by envisioning a new "big picture" or am I'm just wrong in my analysis and so deeply brainwashed by my education that I overlooked the obvious and eternal truth? In the latter case I would be grateful about a "mind expansion".

I'm not sure what is being asked here, since it first requires agreeing on what is meant by "the current state" and what kind of obvious and eternal truth is being sought. However, I am sure that this is nothing that can't be fixed by working one's way through many of the papers which appear on LtU. ;)

If the question is some variation on "awwww, do I really need to get seriously into FP", then I've already answered that.

### Daywalker

From a PL perspective, I'd think the more interesting question would be how well the two paradigms can be blended together. The best examples of such are probably O'Caml (an FP language that supports OOP) and Scala (an OOP language that supports FP). Or to quote from the Scala Rationale:

Module systems of functional languages such as SML or Caml excel in abstraction; they allow very precise control over visibility of names and types, including the ability to partially abstract over types. By contrast, object-oriented languages excel in composition; they offer several composition mechanisms lacking in module systems, including inheritance and unlimited recursion between objects and classes. Scala unifies the notions of object and module, of module signature and interface, as well as of functor and class. This combines the abstraction facilities of functional module systems with the composition constructs of object-oriented languages.

Yes, but the "multiparadigm" approach to programming language design is still no modeling approach. We might ask: how does the decomposition of a system influence the way we distribute responsibilities? What shall be an unbound function and what shall be an object method? Do we really need both function closures and objects in our languages and how does the presence of both influence our design ... ? What are our architectures look like when we mainly focus on unbound functions ( "kingdom of verbs" )? The other side is well known since it was covered by UML and the discourse about OO and SE in the last 15 yrs.

### Doh! Hallowe'en is over!

Yes, but the "multiparadigm" approach to programming language design is still no modeling approach.

I still think you are confusing system design with system implementation approaches.

UML is simply a communication medium in which to express design ideas: there really isn't a single, substantive design methodology underlying it.

As others have said, you could use UML to model a system you plan to implement with FP: use class diagrams for modules, data members for data types and methods for functions.

As for this pernicious "verb vs. noun" meme that seems to have gained currency in certain design circles, I think it neither provides any significant insight into design, nor does it show any understanding of the grammatical categories it purports to base itself on. The concepts are dual in a deep sense and presenting them as an opposition obscures the interwoven, shared structure that they both belong to.

Sofware design is software design, independent of methodology or implementation style: you need to understand the end users requirements and decompose them into data and operations on data so that you can implement them.

Paradigm choice only comes into the equation when you take the next step and have to map those entities onto particular PL constructs.

the discourse about OO and SE in the last 15 yrs

Having spent WAY too much time reading that discourse over that time, I feel pretty confident saying that 90% of it was meaningless blather meant to sell software and consulting products.

If there are substantive lessons that you have gleaned from it, perhaps if you state them specifically we can discuss how the same lesson could be applied to a project with FP implementation.

### I feel pretty confident

I feel pretty confident saying that 90% of it was meaningless blather meant to sell software and consulting products.

I hear you, man... While I feel the same way, let me add that some people that I mildly trust try on occasion to convince me that modelling languages and tools are the way forward. If you ask me, I think the AI angle is slightly more promising ;-)

While I feel the same way, let me add that some people that I mildly trust try on occasion to convince me that modelling languages and tools are the way forward.

I think I understand what problem those people think they are solving:

• Design is hard.

• Many programmers lack good design skills.

• Therefore, we must encode good design into tool and languages so they don't need to develop these skills.

Unfortunately, they overestimate their ability to encode good design into tools and languages... (or programmers' ability to find ways to subvert and screw it up.)

If you ask me, I think the AI angle is slightly more promising ;-)

Yeah, I can imagine a future TV show where an AI teaches design principles to clueless programmers:

Digital Eye for the Analog Guy. ;-)

### Unfortunately, they

Unfortunately, they overestimate their ability to encode good design into tools and languages...

Put differently, to make some progress along these lines you'd need to create something radically different. Something like FP, say.

### Teaching to fish

I agree with your assessment in general, but to be fair I would say that the goal can be more noble, namely that of teaching design skills, rather than eliminating the need for them.

I did some OO A&D training in the early '90s, and it never occurred to me that a goal ought to be to eliminate the need to learn design skills.

If it ends up skewing towards that goal in practice, that may be as much a reflection of the audience as of the modeling language proponents.

### Hostility to design formalisations

I don't get this hostility to design formalisations at all. Surely anyone who has picked up a heavy tome on UML realises that it's not a quick and easy way.

Reading Daniel Jackson's "Software Abstractions", about his design language Alloy, has convinced me that design formalisations is the way forward, especially formal design formalisations :-)

### I don't think it's hostility

I don't think it's hostility to design formalizations in general, but rather a dislike for specific design approaches. In fact, I think Alloy has several LtU fans.

### Indeed!

The takeaway for me from UML + OCL, Alloy, JML, and now Coq is precisely that the gap between modeling and programming narrows as the expressiveness of the type system increases—witness the fact that some JML verifiers rely on a theorem prover, and that one such theorem prover being relied upon is Coq. Alloy, for me, lead to a real "aha!" moment in helping me actually understand, vs. merely to "know," the relationship between "object modeling" and "relational modeling" in the form of Set Theory. Databases, Types, and the Relational Model does something very similar in the database context. So far from being hostile to the formalization of modeling, I encourage it, precisely because I believe that the gap is artificial and will disappear with sufficient attention to programming language design and type systems—by which I don't mean that no one will do modeling; on the contrary, I believe everyone will. It's just that the resulting models will be directly executable and correct by construction.

### Against formal lies

Surely anyone who has picked up a heavy tome on UML realises that it's not a quick and easy way.

It may not be quick and easy, but it doesn't really formalize the right things, IMO, or rather the "language" itself doesn't help you formalize the right things. It can have some utility as a communication tool, but I think that is a different thing than a formalization, and confusing the two is not helpful.

A formalization should be a specification of expected behaviours with clear-cut pass/fail satisfiability conditions. In this light, TDD is a "light" formalization methodology, whereas full-on program validation with a theorem prover is maybe at the current heavy end of such approaches.

Though I'm interested in the latter (I'm working through the Coq'Art book right now), I suspect there will be a demand for the full range of options for the foreseeable future: heavy formalization is more work than its payoff in some contexts.

### Confusious

Paradigm choice only comes into the equation when you take the next step and have to map those entities onto particular PL constructs.

I think "paradigm" goes further than that. For example, UML is definitely based on an O-O "paradigm," while Alloy (a much stronger formalism and tool, since UML is a documentation standard dressed up as a semiformalism) is relational, and demonstrates the power of relations (albeit its particular take on them) by cleanly embracing-and-extending O-O.

So "paradigms" influence all notations, and notations are important in requirements, specifications, designs, and programming.

### Are you asking if there's a

Are you asking if there's a UML for FP?

### Yes. But it is not

Yes. But it is not necessarily a graphical language with boxes and arrows such as UML or FlowCharts - but why not? It can be any kind of high level software architecture view that is refined to concrete program code.

### Sure. But at least I

Sure. But at least I understood your question. Others seemed to think about other issues entirely.

### It's just a FAD ;-)

You might try Dan Russell's FAD: A Functional Analysis and Design Methodology. It includes graphical notation for various FP concepts, as well as a methodology for using the notation. I've never personally used it (and am not aware of anyone who has), but it sounds something like what you are looking for.

### I'm not sure if I've

I'm not sure if I've understood this correctly, but if you think FP lacks this strategic orientation, I'd say that's the exact opposite of the reality: it'd be more accurate to say that FP is primarily about such a strategic orientation to analyzing and decomposing problems, without resorting to the kind of low-level details that so often creep into programming in popular languages.

Forget the programming language theme for a moment and focus on modeling languages, requirement engineering or software architecture drafts. There is a very close fit between UML and Java for instance and it is materialized in a vast body of literature about this topic, also in conferences, university lectures, journals etc. That is what I call a "discourse" about OO and software engineering to reduce misunderstandings. It is unrelated to success stories of individual projects with virtually any kind of tool or slashdoted language wars. But maybe this embedding of languages into a broader context is just too far off the narrow technical discussions and problem puzzlings ( concurrency etc. ) LtU is mainly concerned with, so I better shut up.

### I think that the general

I think that the general questions you raise are appropriate for LtU (if they don't evolve into holy wars): Do FPLs need something like UML? Is there a real reason (i.e., not a market issue) why there isn't a UML for FP? etc.

### And how would it differ from

And how would it differ from eg Haskell with some sugar for binding identifiers to undefined? :-)

### None can turn Haskell into

None can turn Haskell into UML. UML's just plain too ugly...

### Translate the syntax into a

Translate the syntax into a C-style one and from there into a visual representation?

### There is a very close fit

There is a very close fit between UML and Java for instance and it is materialized in a vast body of literature about this topic, also in conferences, university lectures, journals etc.

maybe the lack of communication about the correspondence of model-driven development and functional languages as their implementation language is just mirroring the fact that functional languages are, economically, a minority in comparison to imperative, object oriented languages.

uml is perfectly applicable to functional programming as it is independent of the implementation language. uml and it's cousins operate at an abstraction beyond language paradigms.

for example, xslt is a purely functional language that happens to be quite widespread. in the industry it is regularily modeled with the help of uml, and you will find literature, etc.

### A size 500 suit fits everyone badly

uml is perfectly applicable to functional programming as it is independent of the implementation language. uml and it's cousins operate at an abstraction beyond language paradigms.

I agree that UML is about as useful for functional as for O-O programming. It's equally unfit for both.

Actually, UML is clearly geared toward O-O, though Alloy (for example) is a much better modeling and specification language for both paradigms. It does modeling well for all the domains I know. Perhaps real-time is outside its purview, but somehow I don't think so.

### Executable specifications are models

Forget the programming language theme for a moment and focus on modeling languages, requirement engineering or software architecture drafts.

The reason I focused on the programming language theme is because the original post, IMO, focused on all the wrong things about FP. It's meaningless to discuss high-level modeling using a paradigm if basic aspects of the paradigm are misrepresented or misunderstood.

As for modeling languages, my experience is that FP languages are modeling languages, precisely because of some the issues I raised in my earlier comment. A concise mathematical specification, not concerned with representation or other implementation details, can communicate a lot of information in a very short space. This is exactly where FP has a big advantage. If you want an executable specification, an FP language is one of the best ways to get it. See e.g. The use of Functional Programming in the Specification and Testing Process (that's just an extended abstract, but it summarizes some of these ideas).

In some domain-specific cases, it is possible for a system to take a model or specification and generate complete working programs from that. A good example of this is the SCADE system, which is being used to generate the control system software for Airbus aircraft, nuclear power plants, etc. In such cases, to a large extent, modeling is programming.

In the more general case, if you're looking for "a handy toolset that guides the programmer from customer requirements to program code", I agree with Peter Steiner that there's an economic issue here. The popular modeling systems all grew out of commercial system design efforts, growing organically out of actual practice, because they deal as much with the psychology of the design process as with anything technical.

If someone sat down now to develop such a toolset for FP, geared towards ordinary commercial programming environments, they would simply run into all of the other reasons that FP languages aren't currently used widely in industry. Those reasons aren't so much language features (although there's some of that, too), but rather all of the countless supporting bits and pieces that commercial development tends to depend on: development environments, GUI builders, libraries and frameworks for user interface, persistence, configuration, etc., as well as a suitably targeted knowledge base covering all these tools: books, articles, websites etc., very little of which currently exists. (Existing material is not focused on commercial development.) Focusing on this kind of modeling is focusing on the top of the development pyramid, which requires the pyramid to be filled in up to that level.

I also agree with Marc that modeling languages, requirements engineering, and software architecture are largely paradigm-independent. UML includes some OO-specific features, but they aren't very essential — the main area that can require some rethinking is inheritance, which is often overused and misunderstood anyway (due to confusion between interface and implementation inheritance).

In fact, I recall hearing similar arguments in the early OO days, when the dominant data modeling systems were all relational. Again, modulo inheritance, there really isn't all that big a difference between relational modeling and OO modeling, which is what makes it relatively straightforward to do O-R mapping.

Again, modulo inheritance, there really isn't all that big a difference between relational modeling and OO modeling, which is what makes it relatively straightforward to do O-R mapping.

I would also add "modulo model normalization" and ideally point to some old threads, but my Google-Fu seems to have failed me...

### normalization vs. DRY

I'd be interested in a hint as to the issues in question. IME, normalization corresponds quite closely to what has been popularized as Don't Repeat Yourself in the OO context (of course, normalization has a stronger theory behind it). OO models often tend to be somewhere around 3rd normal form.

### Friendly relations

I'd be interested in a hint as to the issues in question

The main thing I'm thinking about is the Law of Demeter as an OO "normalization principle".

Relational models assume all relations are symmetric and global, whereas OO relations are often asymmetric and localized.

IME, this often pushes you to make bad design choices for BOTH models when working with particular O/R tools.

### Local relations get old fast

Relational models assume all relations are symmetric and global

Symmetric yes, global no.

whereas OO relations are often asymmetric and localized.

I've never seen the need for "asymmetric relations"; it's hardly an advantage of O-O that all relations needs to be implemented as pointers in both directions. As for "localized," certainly a routine in a properly relationalized language could create a relation to do its work - with a very restricted scope (e.g. a single function).

### Interfaces and OO

"the main area that can require some rethinking is inheritance, which is often overused and misunderstood anyway (due to confusion between interface and implementation inheritance)."

I'd often thought that, too. It seemed to me that Java and other OO languages mixed up classes as a means for code reuse and interface definition, and I wondered if Java wouldn't have been a better language if it got rid of inheritance entirely and just used its great interfaces, and found some other means to reuse implementation code. Now from my glances at Haskell, it seems that the system of "type classes" is something very close to that, at least if we think of Haskell types as immutable classes. How well it works for the imperative pieces in practice is something I have yet to explore - I'm learning Haskell.

But to me it seems that Haskell in this area offers better OO than traditional OO languages. The real adoption issues shouldn't be OO vs not OO, because functional progamming can incorporate the very important lessons learned from there (and shame on those who reject them).

The real barrier to adoption, IMO, is that functional languages still make you jump through hoops to deal with inherently stateful problems, which there are a lot of. But that is for another thread.

### Nominal vs. Structural

I think a lot of the implementation and interface inheritance problems are due to nominal subtyping and class-as-vtable notions. Haskell's type classes are definitely a step in the right direction although deriving is a bit of a hack for some form of polytypic/meta programming.

This doesn't seem to be as much of an issue in dynamic languages though. I suspect the problem will lessen to a great extent given a popular structural subtyping language. Implementation inheritance is really just special case of encapsulation and message forwarding in a such a language which is related to the Law of Demeter you mentioned.

### What about the transition system?

An interesting paper was posted recently in another thread by John Backus called "Can Programming be Liberated from the Von Neumann Style", August 1978. This paper doesn't invent functional programming but seems to eloquently make the case for functional languages at an early date. However Backus doesn't present a case for "pure" functional programming but suggests that it should be combined with a "transition system".

A transition system is a way to represent state in a concise way with the same virtues of functional analysis but applied to the systematic part of a program. I use this approach all the time in my own programming and often wonder why there are no languages that support transition systems "explicitly", one is forced to adapt a "case" statement or use labels and goto's. Odely enough transition systems are the cure to spaghetti code (along with functions) even though they are the origin of labels and goto's.

In my opinion the transition system approach eliminates the so called problems of state by making the system explicit. When this is done the system can be analyzed and checked to confirm its performance and properties. Also specifications are likely to be already in the transition system form. Automata theory implies a transition system.

Maybe we should go back to 1978 and try again?

### In Transition

often wonder why there are no languages that support transition systems "explicitly", one is forced to adapt a "case" statement or use labels and goto's.

Perhaps I'm not understanding what you mean, but I can think of many ways of representing this kind of thing both implicitly and explicitly without resorting to gotos.

You could argue that monads are one such mechanism, or you can model individual states with an object or ADT, or you can explicitly pass and return states from functions along with other inputs and outputs.

What kind of mechanism are you proposing that would look different from one of these?

### The point of a "transition system"

The point of a "transition system" is to control when changes to the states are allowed. We usually think of this as a cycle. Given the states and any inputs we calculate everything possible until the system is stable, only then do we allow the state to be updated. This is just a software version of a Mealy or Moore automata. Obviously you can do this with any language that you have at your disposal. My point about a language was that many things can be done to help the programmer in constructing transitions systems that aren't being done.

Timing state transitions is an important part of hardware logic design that is usually controlled by a clock. States are updated on a clock edge. Logic design without clocks is very complex and must take "ripple through" delays into account to avoid races, cycles, and deadlocks. Software logic often resembles ripple through or ripple along logic the way it was once done with relays. It normally works but if you ignore it long enough it can turn into a problem. A transition system simplifies things a lot.

Another advantage of transition system approach is that one can apply the principles of system theory to better understand what is going on.

### Example

A very simple example of a transition system and why it matters. Suppose we are parsing a line and we want to disable parsing for characters inside Of quotes: ". We need a state telling us that we are inside quotes. It is easy to make the following mistake:
bool paren=FALSE;
----------
if(ch=='"') paren=TRUE;
if((ch=='"')&&(paren)) paren=FALSE;

If it is late at night and you have been working too long you might not see what is wrong with this. Basically the first line will set paren to TRUE and the next line will set it back to FALSE. The problem is that paren is a state and must be changed with a single statement.
bool paren=FALSE;
---------
if(ch=='"'){
switch(paren){
case TRUE : paren=FALSE; break;
case FALSE : paren=TRUE; break; } }

### Distinguish from FP?

The buggy version of your program consists of two separate, sequential, imperative, variable-mutating statements — the antithesis of a functional program. Rewriting this in functional form is almost guaranteed to solve the problem (the corrected version is more functional, for example). So, either functional programs take care of this issue automatically, or you need a better example.

### See above

The example is about transition and the need to transition in a single statement or place. The argument starts with the Backus paper and his combination of functional languages and transition systems. Yes, the point is that the imperative approach doesn't work. That is the point of the paper. So the question is what is the one statement approach without side effects using functions? Probably something with monads? I am inclined to wonder what a functional language combined with some transition system would look like. Do you know of such a thing? Whatever happened to the Backus proposal?

### Liberation from the state transition style

The approach without side effects using functions is simply to have a set of mutually recursive functions, with function calls representing state transitions — in other words, a functional program. You don't need any complex magic. For the specified example, you might have a parse_token function, and when a quote is detected, you'd call a skip_quotation function, which would loop through the input until it sees the closing quote, and then return. The boolean is no longer explicit, it's implied by which function is currently being evaluated.

Expressing such transition systems in a high level way is, in a sense, what functional programming is all about. For an example, see Shriram Krishnamurthi's talk The Swine Before Perl. Although it focuses on the benefits of Scheme macros, the relevant point here is that it demonstrates and explains a simple & small purely functional finite state machine. There's a diagram of the machine on slide 22, a macro-free version of the code for it on slide 32 (with arrows showing the transitions), and a high-level macro version of the program on slide 38 (but see the rest of the slides for more info).

More generally, Plotkin showed in A Structural Approach to Operational Semantics how the semantics of a programming language could be defined in terms of a state transition system. Implementing such systems has been a major application of functional languages, so one might imagine they'd be pretty good at it by now. Here's an example of the semantics for a small imperative language, implemented as a transition system in Haskell — see the 'transition' function for the guts of it.

I am inclined to wonder what a functional language combined with some transition system would look like. Do you know of such a thing?

There are quite a few systems that generate table-driven automata — that's what most lex & yacc tools, and other kinds of parsers, do, for example. Again, the goal is to avoid having to deal with the transition system at the lowest level, though. After all, according to Backus (2.2.1), even for "state transition systems with very simple states", the clarity of programs is "unclear and conceptually not helpful". [Edit: Fans of operational semantics might not agree?]

Whatever happened to the Backus proposal?

I'd have to re-read the paper, but the answer might be that FP exceeded Backus' expectations, overcoming some of the limitations he perceived.

### fp?

Backus' FP is a sort of proto-APL, as far as I can tell, so the Inscrutable Goop Factor is pretty high. One of its core dogmas is that named variables are bad, so a lot of your programming is spent shuffling, zipping, and cloning variables to pass parameters. But give Language::FP on CPAN a whirl if you're curious!

### Eschew lambda expressions

That rings a bell. I found a nice quote in that paper:

If one constantly invents new combining forms to suit the occasion, as one can in the lambda calculus, one will not become familiar with the style or useful properties of just the few combining forms that are adequate for all purposes. [...] so functional programming eschews the lambda expression[*], substitution, and multiple function types.

So rather than "FP" exceeding his expectations, lambda calculus did. I guess he might appreciate Joy, hate macros, and dislike ML & Haskell.

--
[*] Foreshadowing work by Krishnamurthi et al.

### "Liberation from the state transition style"

The approach without side effects using functions is simply to have a set of mutually recursive functions, with function calls representing state transitions

Yes, this certainly works and often makes sense, but has the effect of hiding the state and the model. Why? Certainly state can be represented badly but there is nothing bad about state. Neither imperative nor functional schools seem willing to address state directly and cleanly. I think this is what Backus was trying to do back in 1978, and it still seems to be a worthwhile objective today.

The opinion of a frustrated programmer.

### The answers are out there (or in here)

Yes, this certainly works and often makes sense, but has the effect of hiding the state and the model. Why?

Because the result is usually much more comprehensible. The functions are chosen to correspond more directly to features of the problem domain.

However, nothing stops you from making the function calls correspond directly to the labels in a labelled state transition machine. IIRC, that's what Shriram's example does. Have you looked at that yet? Perhaps you could say something about why that program (the macro free version) is not the kind of thing you're looking for.

The literature which deals with state machines — including operational semantics, parsing, regular expressions etc. — is full of programs which manipulate them in all kinds of ways, ranging from abstract higher-order representations (with and without monads) to direct encodings of the transitions between states based on the typical mathematical models of machines as n-tuples.

The opinion of a frustrated programmer.

It's highly likely that something similar to what you have in mind already exists. I'd make some suggestions, but I'm not yet sure what you're thinking of. If the idea is to have a language which is designed to deal explicitly with states and transitions between them, but without the pitfalls of imperative programs, I think you might find that the design of such a language would be quite similar to that of a functional language.

This all goes back to some very basic stuff: functions are just labels with parameters (corresponding to the labels in a labelled state transition machine); function parameter lists are tuples, and machines are modeled by tuples. Fancy stuff like pattern matching is just sugar — you can write it all with good old-fashioned ifs and case expressions if you want to.

### However, nothing stops you

However, nothing stops you from making the function calls correspond directly to the labels in a labelled state transition machine. IIRC, that's what Shriram's example does. Have you looked at that yet? Perhaps you could say something about why that program (the macro free version) is not the kind of thing you're looking for.

Actually I like this approach because it leaves the state transition representation in tact and integrates with a functional style. If you have models, systems, and states to work with it helps to keep them in the program, and it is easier to use them later for analysis sake. Also what Shriram is doing can simply be taken as a strategy and used in other languages. Often we are stuck with one language or another. And of course there are other strategies some of which you also have mentioned; some less functional but still concise. I will have to think about it a lot more. Thank for the links.

I wonder what John Backus would say?

### Tail call optimization considered essential

Also what Shriram is doing can simply be taken as a strategy and used in other languages.

True to an extent. Note that the implementation of a machine which needs to recurse between states for long enough will require some support for tail call optimization.

This is why languages (or language implementations) without decent tail call optimization may be considered broken. On the spectrum I mentioned between abstract higher-order representations and direct encoding of state machine transitions as function calls, languages without TCO cannot in general implement solutions at either end of the spectrum.

This is strange, because as I mentioned, state transition systems can provide a model for programming language semantics, and in particular, they provide a fairly natural and compatible model for the semantics of typical imperative languages. Yet most imperative languages are not capable of conveniently and safely expressing the semantics of such machines — they have to resort to loops with breaks, big case statements, and even to pre-structured-programming techniques such as jumps and labels, of course all combined with variable mutation which is harder to reason about. It would be as if functional languages were not capable of conveniently expressing the semantics of the lambda calculus. Yet functional languages can conveniently express both, while non-TCO imperative languages have problems with both.

It is ironic that it's the traditional imperative languages that don't provide the right abstractions for dealing with state.

### OK.. This is getting deep,

OK.. This is getting deep, but also interesting. I was thinking mutually recursive functions, I guess I overlooked the possibility of stack overflow? One can of course write functions in; dare we say C; and I use such functions recursively all the time, but the system never gets very deep. I have the vague idea that even tail recursion is not that hard but I will have to look into that and study Shriram a little more, and bone up on Scheme.

All the basic Lisp features can be written in a dozen pages of C style code compiled with C++ for the sake of some added helpful features. I guess you are saying that isn't enough without tail recursion and TCO?

### OK.. This is getting deep,

OK.. This is getting deep, but also interesting.

It might be deep, but the water's warm. ;)

I was thinking mutually recursive functions, I guess I overlooked the possibility of stack overflow? One can of course write functions in; dare we say C; and I use such functions recursively all the time, but the system never gets very deep.

Actually, these days C isn't so bad — at least gcc can do some tail optimization. I don't make much serious use of C any more, so I don't know its exact limits, or which other compilers do this. So it may not be portable, but it can be done.

Regarding recursion getting deep, most imperative programmers instinctively avoid recursion and use things like loops instead, where necessary. As a simple example, for the main loop of a long-running server program in C, most people probably wouldn't code the main server function so that after having handled a request, it calls itself recursively (even if you can get away with that in some compilers). But using loops leads to the need to break out of them (as opposed to just calling another function), and next thing you know you're using labels and goto, if you're really coding a non-trivial state transition system directly.

I have the vague idea that even tail recursion is not that hard but I will have to look into that and study Shriram a little more, and bone up on Scheme.

Tail recursion is not that hard, if it's built into the language. Of course, it's harder if you're implementing an interpreter, and the host language doesn't do it, in which case you have to resort to things like trampolines, which also slow down the code.

All the basic Lisp features can be written in a dozen pages of C style code compiled with C++ for the sake of some added helpful features. I guess you are saying that isn't enough without tail recursion and TCO?

That's right. gcc's tail recursion support might be good enough to do it now, though. It wasn't when I wrote a Scheme interpreter in C++, around 2000. But the Stalin Scheme compiler generates C, and it is now "properly tail recursive, by default, in all but the rarest of circumstances."

### C/C++ and TCO

Actually, these days C isn't so bad — at least gcc can do some tail optimization.

As far as I know, it only supports tail recursion, which is much too weak for most purposes (including the one under discussion).

But worse, note that many features in C and C++ prohibit TCO for most interesting functions: for instance, the ability to take the address of, or form a reference to, a local variable (which you often cannot avoid as a programmer, because libraries require it), or the destructor machinery in C++ (which has to be invoked last). In practice it is virtually impossible for a compiler to find out that TCO would not invalidly change semantics in the presence of any of this.

These are principal problems with those languages - yet another example of their low-level nature prohibiting interesting optimizations.

### Oleg once wrote for us a

Oleg once wrote for us a nice summary about the issues involved.

### gcc kicks tail

As far as I know, it only supports tail recursion, which is much too weak for most purposes (including the one under discussion).

If by tail recursion you mean only self-recursion for tail calls, it's better than that. E.g. under gcc, compiled with -O3, the following won't run out of stack:

int odd(int n) { return n == 0 ? 0 : even(n-1); }
int even(int n) { return n == 0 ? 1 : odd(n-1); }


With -O3, this will work with maxint as input (even if each function is compiled separately); without -O3, it runs out of stack on my machine at around 260,000.

But worse, note that many features in C and C++ prohibit TCO for most interesting functions: for instance, the ability to take the address of, or form a reference to, a local variable (which you often cannot avoid as a programmer, because libraries require it), or the destructor machinery in C++ (which has to be invoked last).

I should have mentioned that. However, I was thinking mostly of what's needed when developing an interpreter in C or a compiler to C, in which case it may be possible to avoid these issues, as Stalin does. (Details of Stalin's reliance on gcc's tail recursion can be found in its manpage. A copy of the relevant section can be found at the bottom of this page.)

Similarly, it ought to be possible to implement many state machines which exploit mutual recursion under gcc. But I agree that it shouldn't be assumed that tail recursion under gcc is completely general and problem-free, let alone in C in general.

### Computed goto

As long as we're talking gcc, don't forget computed goto.

### Hidden Loops

In response to everyone above I have taken the liberty to move this over.

Whenever I read about tail recursion I get the feeling that it is a way to hide a loop and keep a pure functional semantics. Stack overflow is usually due to a function that could also be written as a loop. As long as we are talking C why not just loop on the function or block causing the problem. To me the real virtue of functions (and also procedures) is blocking and scoping and making that visible. Getting back to my earlier comments the real problems in imperative code occur when there is a lack of clear blocking and scoping. This can happen because the method allows it, whereas functions don't allow it. C is not a "safe" environment but an extension of assembly language (my opinion of course). The challenge seems to be using it in a way that has a clear semantics perhaps in terms of a model with a one to one correspondence to the code. This is ultimately what makes me feel good about a program.

### Hidden loops? Obscured functions!

Whenever I read about tail recursion I get the feeling that it is a way to hide a loop and keep a pure functional semantics.

That's only valid for simple cases of self-recursion. But if you're talking about general tail call optimization, so that mutual recursion can rely on it, then it can "hide" multiple, interdependent loops, each of which may need to contain break statements and even jumps to labels. Thinking about this as "hiding a loop" is going to give you a skewed perspective: you're thinking in terms of a model that contains an arbitrary restriction (watch out for Sapir Whorf!)

As I've pointed out, the function call model with unoptimized tail calls is unable to express many state machines using only function calls for control flow, so it is not as general as the functional equivalent. Rather think of loops and jumps as workarounds used to compensate for lack of fully general function calls.

As long as we are talking C why not just loop on the function or block causing the problem.

In general, there are many cases where this can be comparatively difficult to reason about, when recursion isn't trivial. You start seeing the effects of this even in something as apparently trivial as the iterative version of the fibonacci function. Have you ever worked through SICP? It has a good treatment of some of these issues.

To me the real virtue of functions (and also procedures) is blocking and scoping and making that visible. Getting back to my earlier comments the real problems in imperative code occur when there is a lack of clear blocking and scoping.

Right. And in a state machine with a mutually recursive implementation, every state is "blocked and scoped", and every transition is a function call. This is exactly why the functional version is easier to reason about, and why the equivalent with loops and jumps can be problematic.

### OK, this raises one last

OK, this raises one last question. Since I like to think of C as an extended assembly language is there some subset of C or some other language. O'camel comes to mind. I think you said that Scheme itself can be written in C. If so, where is the tail recursion problem? Scheme has to translate into something; either C or Assembly and Scheme has tail recursion?

### Just guessing

But the generated code probably uses GOTO type flow control to attain TCO (something which would be frowned on if coded by hand, but usually tolerated when it is a compiled intermediate form).

### C in context

Schemes that are implemented in C, or that compile to C, have to jump through hoops (almost literally) in order to support tail recursion. It has gotten better with recent versions of gcc, but see the Stalin docs I linked to for details of one of the approaches to making it work. As those docs point out, even with the current gcc support, there are still limitations, which can have an effect on the performance that implementations can achieve when supporting tail recursion. Most such implementations have options to allow you to turn off tail recursion for performance reasons. This is only needed because of the use of C as the implementation language.

This issue isn't just limited to Scheme — all functional languages are affected. See e.g. Compilation of Functional Programming Languages using GCC.

On the subject of using C for implementing advanced languages, the issues go beyond tail recursion. I mentioned some of them, with relevant links, in this message. That message gets into some of the reasons that C can seem like an extended assembly language, which is that it's usually being used within a context in which the things it depends on are also implemented in C, so you don't usually experience an impedance mismatch, either with the issues raised so far, or with other things like argument passing conventions. However, that comfortable illusion breaks down, badly, when you're not operating in a C hegemony. You could just as easily say that Lisp is an extended assembly language, as long as you're working on a Lisp Machine.

IOW, the idea that C is an extended assembly language is a myth. It's a low-level language, sure, and you can pretend it's an extended assembly language in a certain context. Unfortunately, that context is quite pervasive. I prefer to think of C as a millstone around the world's neck. ;)

Since I like to think of C as an extended assembly language is there some subset of C or some other language. O'camel comes to mind.

Not sure exactly what you're asking for here, but in general, if you want something truly assember-like, with the same degree of generality, you need something that's a lot like assembler. Some systems in that general space include TAL, C--, BitC, and LLVM, but even most of those include some higher-level features that limit what can be expressed, and how. Something as high-level as OCaml imposes its type system and doesn't give any control over machine-level representation, so probably doesn't qualify (depending on what the goal is).

### Guess

Is this a good guess? It sounds like the problem is the call and stack control system since that is what TCO is working with. A language would needs to have a Scheme compatible call system. That could be: ->Scheme.

### Wrapup?

If I've correctly divined the question that the guess is answering, then to implement tail calls efficiently and without problems, the underlying language needs to already support them, one way or another. That could be by providing sufficient control of the call stack etc. Also, as I said, this isn't just about Scheme, but rather affects any functional language. C-- is one explicit attempt to provide a low-level language, which could serve as a good portable assembly language for functional (and other) languages.

### After looking over Shriram

After looking over Shriram talk I had the following observations.

First by making a state representation in a functional language like Scheme one indeed does get a concise transition system. But there are several problems. First of all the state itself is the stack. There is no way to "single step" through the system. Although one might think of saving and restoring the stack (perhaps with a call/cc?) I don't know how practical that is but it might result in a useful transition system. But normally this wouldn't be necessary because all the "inputs" (ie the c d a r strings) are already available in a list. If the letters were arriving intermittently from outer space we might need a transition system.

A second point about Shriram is that the method of transforming a scheme program into its state equivalent in scheme forces one to think in terms of state and generally this would seem to reduce the need for TCO. If one has the state transition diagram one can find the deepest path (or recursion) by inspecting the graph. The examples that shriram gives don't seem to benefit from TCO? But I am not a schemer. Recursion depth when processing a list is just the depth of the list.

One more observation about Shriram is that introducing explicit state machines in scheme invites the introduction of a variable with dynamic scope, (an accumulator) and a further reduction in the need for TCO. Don't know if that is allowed in Scheme? Just an observation.
Edit: This is not to imply any sort of attitude on my part about TCO, If I had it, I would probable use it.

### 1, 2, 3...

1. Single stepping is easy. Remember what the "state" is: it is the name of the current function and its tuple of arguments (which don't change, because we have a functional langauge!). Simply replace each of those transition functions with a constructor for a record of its arguments, and then implement a dead simple top-level driver that interprets a state using the old functions.

Though really, what you would do in Scheme is redefine the automaton macro to get the single-step version from exactly the same code as the original.

That's much easier than single-stepping the imperative version where the state is hidden away in mutable variables. ;)

2. How deep is the deepest path in a graph with a cycle? Who cares, if you have proper handling of tail calls.

3. Huh?

### What?

OK: We did it! Hope I am not jumping to conclusions, but we seem to have implemented John Backus's Applicative State Transition System (also called AST) in his FFP (for formal functional program). What? Comments welcome.

### REFAL

I think the most basic approach to connect systems theory to programming languages works with term rewriting engines: having a multiset of expressions and rewriting rules operating upon those recursively. If you want to time travel back right now you might also consider making a stop in 1968 where REFAL was invented by the russian fundamental cybernetican Valentin Turchin.

### GemCutter? - or Java meets Haskell

Since UML for functional languages was brought up, I thought I'd link to
CAL which is a Haskell for the JVM. The relevant demonstration though would be GemCutter, which is the graphical tool. If you scroll down or search on that page you'll see demonstration video of the GemCutter tool.

### OO design can be used with FP.

Object-oriented design is about designing who's responsible for what. The result program can easily (or not so easily) be written in an FP language.

My only question is how to handle state in-the-large: most of the designs I have encountered have been around object models that hold the state of the application, and the model-view pattern attached to it. I've been told to look into the zipper pattern, and some game implementations, but the examples I have seen use an almost flat model, and it seems really difficult to extend that logic in a huge state model.

### Buffy

Without trying to invoke the not-to-be-named unholy war, here's my couple of cents:

1. I always felt that typeful programming works best with FP. When I program in Haskell or Scheme or Erlang I first think of the types. IME it's a great way to place the responsabilities of a piece of software. I also use this in my day job (i.e. Java programming) but I think it loses part of it's effectiveness because OOP languages usually just provide coalgebraic types and most of the times (in "enterprise" apps) algebraic types are better suited.
2. Also FPs are usually great (executable) specification languages. Without side-effects code is simpler to reason and pure functions rarely become thirty pages of code. Some formal specification languages (e.g. VDM-SL and Z, to name two that I actually know) are FPLs in disguise.
3. 3. Higher-order code is great to capture idioms and patterns. Going there to DSls is just a matter of time and before you know your code is as simple as its specifications (modulo pesky UI details).

Whenever I have to design a program in a FPL I start from the specifications and go top down, defining the required types and their invariants. After specifying a couple of high-level operations I start to develop a small library of functions that capture the essential dynamic behavior of the system. I keep going through this cycle until I have running code and all the requirements nailed. At this point the solution usually is a half-baked DSL that could be improved if I was smarter.

Theses techniques aren't tied to FP but almost every succesful FP project uses it and most OOP projects don't, relying on some vague guidelines or just waiting for the design to emerge* instead.

*I agree with the emergent design theory, but you asked about design and modelling strategies, so I couldn't just say wait for it to emerge into a beautiful HOT DSL full of lazyness and HOFs

### Emergent "design"

I have recently noticed how this seems to be the most effective style of design that I've found.. for the large-scale (imperative) projects I've worked on.
It hadn't occurred to me that it might be tied to the low-level (vs. HOF) style, though. Of course, I haven't worked on large-scale FP/HO projects!

I used LtU search, but didn't (immediately) see any related discussions or papers.. do you have pointers to such? I suppose this pops up in the holy-war threads, but I was looking for something more specifically about pre-implementation _design_. (maybe these are the wars "designers" fight)

Also, when you say "I agree with the emergent design theory", how does this tie in with the rest of your comment? Multiple iterations through the top-down strategy you're endorsing (?) for FP?

### Submergent design

I was looking for something more specifically about pre-implementation _design_. (maybe these are the wars "designers" fight)

In the agile world the emergent design idea comes from the XP folks as an alternative for BDUF so it usually implies in minimal pre-implementation _design_.

Also, when you say "I agree with the emergent design theory", how does this tie in with the rest of your comment? Multiple iterations through the top-down strategy you're endorsing (?) for FP?

I use TDD most of the time now, so I start with a general design/architecture definition (e.g. one module per layer, a regular three-layered architecture), coding guidelines (e.g. small functions only, few parameters, factor duplication using HOFs, total functions mainly) and write tests for specific parts of the system. In Haskell, my language of choice, using QuickCheck and HUnit make it very easy. As I write down the tests and the code to implement it I go in iterations of testing, coding, refactoring, cursing the gods and re-reading the works of Simon-Peyton Jones and Paul Hudak looking for osmotic learning. In the end there's lot of nice thingies in the program, like: embedded DSLs, many useful HOFs, few Ifs and guards because folds and unfolds do the job. It's quite pleasant to look at the source and easy to understand what it does, even a year later while you're drunk ;).

I think you can TDD either bottom up or top down, in the latter you have to stub your dependencies. As my mood varies through the day I don one or the other and notice no significant difference in my work flow. YMMV and all that of course.

I usually have an pretty well defined idea on how the design shall look, but IME it's usually wrong in technical domains I don't know (i.e. games vs. "enterprise" apps) and it's usually right where I'm very experienced. In the former BDUF hurts because I'm forcing my erroneus ideas and making the system harder to understand and evolve while in the form it hurts because it's so damned obvious that my time is wasted even if I only think about it. As there's no middle ground (either you're a grasshopper or a master ;) BDUF has no place in my software developing world.

### Emerge from where?

relying on some vague guidelines or just waiting for the design to emerge instead.

I think the distinction between the two approaches as undertaken by people with solid design skills is not really that different.

Any design can only be arrived at and evaluated by understanding its goals and constraints. The only real difference between the two approaches being described is different assumptions about how completely one understands the goals and constraints of one's problem at the outset.

In either case, whether you work in small design steps from bottom-up or large steps top-down, the quality of the resulting design emerges not from the ether, but from the design skill and judgement of the designer.

### From /dev/null, of course.

I should go back and ad a ;) to the end of that sentence. The emergent design definitions usually given are vague guidelines so I was trading six of one for half a dozen of the other.

Let's just agree to agree on your post, as there's nothing on it that I think is wrong. As you say it depends on ...the design skill and judgement of the designer which is ultimately a people problem.

### Perhaps then you can enlighten me on some issues.

I am a Java programmer too, but I have a very hard time translating imperative patterns to functional ones. Since Java programs heavily relate in patterns like the model-view-controller one, can you give me an example of how you can easily convert a Java application to a functional one? You can use a very simple example, like the J2EE web shop tutorial...

EDIT:

links to previous discussion on the topic:

http://lambda-the-ultimate.org/node/1578#comment-18893

I've read all about Zipper, simple arcade games etc but I still can not convert a simple MVC-driven Java app to the Haskell equivalent. Perhaps it's me... :-).

It is an LtU community tradition that whenever a subject has been discussed before, a link to the previous discussion is given. Having been around for a while, I know that you have asked this question about MVC and FP a number of times. I have no qualms with the question but you should provide links to the previous discussions.

### Keisaku

I still can not convert a simple MVC-driven Java app to the Haskell equivalent. Perhaps it's me... :-).

Don't mistake a failure of imagination for impossibility.

Consider an MVC pattern where, instead of one global version of each, you had indexed immutable versions of each.

So my current view has a reference to a particular version of the model and controller. I initiate an operation on my controller, which causes an updated instance of my model to be created, and then an updated view to be created and returned to the UI, including references to an updated version of the controller for the view.

There is no desctructive update in this example, so it has referential transparency.

Still don't think you could build that?