Lambda the Ultimate

...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. :-)

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. ;-)

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.

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?

A poorly designed exemplar of a paradigm doesn't define the paradigm.

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. :-)

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.

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 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 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.

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.

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 to design formalizations in general, but rather a dislike for specific design approaches. In fact, I think Alloy has several LtU fans.

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.

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.

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.

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 understood your question. Others seemed to think about other issues entirely.

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 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 eg Haskell with some sugar for binding identifiers to undefined? :-)

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

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

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.

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.

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...

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.

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.

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).

"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.

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.

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" 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.

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; } }

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.

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?

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.

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!

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.

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.

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 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?

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, 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, 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."

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 nice summary about the issues involved.

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.

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

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.

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 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?

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).

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).

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.

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 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. 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?

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.

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.

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?

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.

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.

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.

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.

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?

Achilleas' standard response to this is to observe that it involves "copying everything." The standard response to that is to point out maximal-sharing options such as the Zipper (preferably Oleg's version). Achilleas' standard response to this is to observe that he's only seen "simple, flat" versions of the Zipper. How Oleg's Zipper-FS is "flat" or "simple," given that the filesystem is hierarchical and that its values can be any Haskell term at all, I fail to understand, so I've given up attempting to engage him on this subject anymore.

And approaches such as compartmentalising the relevant state are apparently only allowed if you never use an implementation with destructive update...