Lambda the Ultimate

Could be that the reason that higher-level languages are not more commonly adopted is that the people who understand and love them don't have the motivation to work on all the systems-level infrastructure that's required for them to be usable.

Maybe a language needs to be able to "boot" itself by having a group of enthusiastic early adopters sufficiently embedded in systems programming to do the things like compilers / virtual machines / editors and libraries that are necessary for them to become interesting to a wider audience.

Either that or the language needs to be good for creating that infrastructure.

Rather uncalled for.

Those who need FP already use it, don't they?

But most of the computing problems in IT is about input, processing and management of a company's data,

which mainstream imperative programming languages already can do in great success.

Why bother with FP is the project is trivial?

The overuse of state seems to be at epidemic levels in our industry.

Indeed. Many fellow programmers are unable to think of a solution to a problem as a computation.

But does it really matter? most problems are so trivial, that using state or not does not really make any difference.

Generally speaking, all problem solving is about input, processing, and output.

I meant that most projects are about forms and databases: input data in a form, store it in a database, retrieve data later, do some form of trivial processing.

Depends upon what criteria one uses for evaluating success.

I don't disagree that using FP languages would have some benefits in the end result.

But look the overall process of software: I have a contract, and my clients demand certain functionalities from me. The problem is trivial: lots of different input forms, a database back end, a client server architecture, and a minimal set of web pages.

Under this light, why should I choose (for example) Haskell? I'll go with Visual Basic, which can help me deliver the forms very quickly, has tones of tools, documentation and examples, and I can find plenty of programmers to help me deliver the product.

Well, if the problem is trivial, the solution should be trivial as well.

Indeed. Perhaps a client-server DB application would be very easy to write with Haskell, perhaps as easy as Visual Basic. But since I know Visual Basic, why should I waste time migrating to Haskell?

On the other hand, If I was writing an air-traffic control system, or a power-plant control system, or a multi-million dollar bank system, I may consider Haskell or Erlang or another functional language. But most of the projects around me certainly are not as big as that, and they don't justify migration to a functional language.

EDIT:

The last few years I have been working on the training system for the simulator for Crotale NG. The main system is in ADA and the training part is in C++. How would I benefit from using Haskell, for example? most of the bugs in the system are logical bugs, none of which Haskell is able to catch. The term 'logical bugs' refers to requirements not being complete, not fully understood, not being consistent or concise. I really doubt there would be any benefit from using Haskell or any other functional language.

I've had plenty of logical bugs per your definition effectively caught by the fact there wasn't a well-typed way to translate the specification. If you start needing to pile up hundreds of lines of kludge just to outline what the system looks like this tends to be a strong hint.

Can you please show me some examples of the kind of logical bugs you are talking about (and perhaps the solution)? just to get an idea of how FP can help in this way.

The best way to get such an idea is to actually write some non-trivial programs in a typed functional language.

I haven't been a part of this conversation yet, but I've been following it for a while. It's migrated well afield from the OP, but to my eye it currently appears thus:

First person: "I'm not well-versed in functional programming style, and I'm considering whether it would be a good investment of my time to learn it more thoroughly. Can someone point me at some examples of non-trivial functional programs within one of these several problem domains (with which I'm familiar) so that I can read them? I'd like to see how functional programming addresses the kinds of issues I usually face."

Second person: "In order to see how FP relates to these particular areas, you'll have to write the solutions yourself in FP style."

While I don't doubt that writing the code would provide many valuable insights, I believe some people in this thread are actually asking for code to read. If they (or I) could indeed already write non-trivial functional programs within these problem domains, I suspect they (I) wouldn't be asking for pointers to examples.

Are there any open projects using FP languages within the domains mentioned (I believe that so far they are interactive database access and interactive games), or other similar domains? Reading code is a great way to learn, in my opinion, and I'd love to be able to do that in this situation.

(My partner, on seeing this, offered me a link to "Space Invaders in PowerShell". PowerShell isn't a functional language, and the program is entirely in imperative style, but it's the kind of thing I'd love to see in, say, Haskell.)

I don't agree with your summary of the conversation. Achilleas' main theme seems to be "Why bother with FP is the project is trivial?" I'd agree that this perception is certainly a reason why most people don't start looking for better solutions the first time they have to write, say, a simple web app using PHP, but up until now I haven't responded on that aspect of the discussion.

However, a pretty much unrelated subthread arose, in which it was asked how Haskell might help catch "logical bugs" in the development of software for the Crotale NG Multi-Mission Air Defense Missile System training system simulator. This is a rather different question than "Why bother with FP is the project is trivial?"

Philippa's response referred to a phenomenon which occurs when translating a specification into a typed functional language: many cases of "requirements not being complete, not fully understood, not being consistent or concise" are exposed quite relentlessly. Merely reading code, in an unfamiliar language, is not going to help anyone understand why this is the case: you need to try to express your own problems, so that you experience what happens in the case of such a logical bug. There's a phrase in the LtU policies, taken from a comment of Ehud's, "You cannot learn swimming by debating the color or shape of pools". In this case, staring at the pool won't help either. You have to get wet. That was, in part, where my response was coming from.

A paper that analyzed this logical-bug-catching phenomenon and examined examples might be interesting; I'm not aware of such a paper. I think it's a bit much to expect that someone is going to give such an analysis in a comment on LtU, although it would be welcome.

Another factor is that this site is dedicated to the study of programming languages. You can't get very far in even the most basic introductions to that topic, such the books and papers mentioned in the Getting Started thread, without learning quite a bit about functional programming, because functional programming is the metalanguage of programming language theory[*]. Someone who's wondering whether there's anything in FP for them is not thinking in terms of studying programming languages, and might find better answers to such questions in some other forum.

[*] Being metalanguages is a big part of what makes them good at expressing specifications, and catching bugs in specifications.

Actually, your point about studying programming languages returns, I think, to the beginning of this thread: "Why people don't use functional programming?".

There's a subtle distinction there: the question isn't "why don't people learn about functional programming?", but more along the lines of "why don't they use it, directly and obviously, in more everyday projects?" I don't question the utility (even the importance) of studying functional programming. But the academic subject must become the practical technology at some point. I interpreted the theme of the original post as an inquiry into whether that has happened with functional programming, and if not, why.

Again, I'm entirely with you on the idea that learning about functional programming is valuable. But it's almost a cliché to hear, in almost any discussion of the practicality of {PLT concept}, someone say "learning about {PLT concept} makes you a better programmer, even if you never actually use {PLT concept} directly in your work." That may be true, certainly, but it doesn't answer the question "why don't people use {PLT concept} directly in their work?"

It ends up looking rather like Latin. Learning Latin might be A Good Thing in academics (at least, it used to be), but it's not really a technology you can apply much in your daily life (except in certain rarefied fields). Were someone to ask, "why don't people use Latin?", a reasonable response might be "Latin is not intended for practical daily use, but instead as a piece of your general academic foundation. It can make other study easier or more obvious, but it's not likely to be a primary skill."

I don't doubt that this analogy doesn't hold for functional programming. But it certainly seems sometimes that it does, and in no small part due to the dearth of examples of its concrete utility.

"why don't they use it, directly and obviously, in more everyday projects?"

That's been discussed quite a bit on LtU in the past. There are a lot of reasons for it, and I believe that the (relative) lack of examples are a consequence of those reasons, not a primary cause. One could go on for pages, if not chapters, about the various network effects at play. I described one class of such reasons in a comment about some of the ramifications of the C hegemony.

While I do not disagree with the basic promise of your argument, I asked for a demonstration of 'logical bugs' because I suspect the term has (slightly) different meanings for each one of us.

Someone who's wondering whether there's anything in FP for them is not thinking in terms of studying programming languages

But the issue at hand is not about studying programming languages but about using programming languages, i.e. applying the knowledge into everyday practical problems. The thread's title is 'why people don't use functional programming'.

But the issue at hand is not about studying programming languages but about using programming languages, i.e. applying the knowledge into everyday practical problems. The thread's title is 'why people don't use functional programming'.

The topic post requested pointers to papers on the subject, it wasn't a call for personal testaments of FP skepticism. If a new member had posted the same question, I would have posted a less terse response, along the lines of my explanation to Wolf, with a link to the Getting Started thread.

As to whether our definitions of logical bugs are different, I agree with Philippa that by the definition you gave ("requirements not being complete, not fully understood, not being consistent or concise"), that expressing a problem in a typed functional language like Haskell or ML will indeed catch many such bugs, and help improve your specification. The only practical way I can think of for you to verify that for yourself is to actually try it, as I said, unless the Koenig article that was linked to answers your question.

The topic post requested pointers to papers on the subject, it wasn't a call for personal testaments of FP skepticism.

Papers can offer information, but sometimes it might be equally interesting to hear what people say. I don't see why we should not discuss about it.

that expressing a problem in a typed functional language like Haskell or ML will indeed catch many such bugs

But there is always a class of bugs that Haskell can't catch...

Anyway, if you don't want people to talk about this subject, that's ok by me...

As to whether our definitions of logical bugs are different, I agree with Philippa that by the definition you gave ("requirements not being complete, not fully understood, not being consistent or concise"), that expressing a problem in a typed functional language like Haskell or ML will indeed catch many such bugs, and help improve your specification.

To a certain point this may be true. Prototyping a solution in a FP language may give great insight into the inconsistancies and incompleteness of the specification. I know that there are advantages to getting a prototype up. However, in my day job of solving my clients business problems, many more of these incomplete specifications are determined not in the practice of programming in a language but the practice of providing a business design (review and redesign in many cases).

It is more about recognizing the simple fact that people do things for reasons (good or bad) and that much of this doing (and why) is actually held in the heads of those who do it. I would expect that someone who is intending to provide a solution (using computers and programming languages - irrespective of the type) to be capable enough to help the client develop a functional design in the first place.

[An Aside to This is that many projects try to do everything all at once instead of actually seeking to fill the actual needs of the various sections of the business. These needs may not be able to be put into the same basket in the short term.]

The programming language ultimately used and the systems associated will be a result of the business imperatives and the whatever freedom of choice is given to the developers (which may be none).

When I have the choice and oppurtunity, I'll use what I feel is appropriate for the business that is using my services. If I have the freedom to use whatever I need, I'll use whatever I feel is appropriate to the problem at hand.

After watching many discussions and reading the various papers the members of LtU point to, I have come to feel that there are many in the IT industry as a whole who seem to be looking at the tool first instead of looking at the problem first (I see this as the case very much so in the commercial [non-IT] market). I myself have fallen into this trap many times over the years. These days, it is a matter of trying to understand the business imperative and needs of the clients first before developing a solution.

In having raised a couple of questions here myself, there have been a couple of very helpful people who have given examples of solutions in their "favourite" language that have given me a very good insight into the uses of the various FP languages and how they may be usable in a business context.

Ralf Lämmel has written a paper which exposes a number of type errors in the Mapreduce paper from Google. Those type errors are logical bugs, and definitely included in what this thread has been talking about.

Discused here.

To be fair, a lot of the advantages can also be apparent in strongly-typed languages of declarative inclination that isn't functional as such. Either way, inconsistencies in the spec rapidly become inconsistencies in the code - ones which can be exposed to and caught by the type system. In particular, inconsistencies in data flow will be exposed where a language like C++ would all but encourage you to brush them under the carpet - this being the advantage of maintaining a pure-by-default approach. Similarly, if the requirements are incomplete or incompletely understood, sooner or later you'll end up with a piece of code approximately like so:

foo = ... bar ...
bar = undefined -- WTF am I supposed to do here, anyway?

because there isn't a natural "just gets it done" translation, however badly-performing it might otherwise be, whereas if the spec is complete and understood then you'll instead stop expanding things out when you're down to library structures, types and operations you've already defined and perhaps a range of tasks that're known to be understood sufficiently ("insert CRUD form here").

In fact, if you allow a little bit of metapseudoprogramming along the lines of "map makeCRUD descriptions" in the first pass then even conciseness can be attacked. There was an incident on IRC a while back when someone commented you'd have to be insane to write more than 1000 lines of Haskell, to which the reply came that this was true because you shouldn't need 1000 lines for anything - while not literally true (GHC being a perfect example), if you can't on some level translate the spec into a comparatively small piece of code in the kind of style I'm referring to plus a pile of data then there are fairly good odds you've got a rather heavy spec to work with. You might even use this code sketch as a first pass at refactoring the spec!

An anecdote about ML type inference

Indeed. Many fellow programmers are unable to think of a solution to a problem as a computation.

But does it really matter? most problems are so trivial, that using state or not does not really make any difference.

I meant that most projects are about forms and databases: input data in a form, store it in a database, retrieve data later, do some form of trivial processing.

Anyhow, I think you trivialize the amount of complexity involved in database-to-user-form apps. Designing a good database schema is very hard. Designing a good UI is even harder. Perhaps the apps you work on can get by with Client-Server. Most apps I work on these days demand the web interface be either the sole means of access, or at the same level of capabilities as a sister desktop application. Users want access to their data at all times and all places. Many of the client-server apps I've been involved with lately also involve cache clients, where the user can go off-LAN and have the full power of the app built into the client - synchronizing when the user gets back on-LAN.

I don't disagree that using FP languages would have some benefits in the end result.

Or put another way. Perhaps most programmers will need to fall back on state, but that doesn't mean that it should pervade every line of code that we write. Personally, I think that even more important than functional programming is the declarative paradigm (though the two tend to overlap). Those databases that you refer to are quite declarative in nature - everything from the schema on down to the retrieval and updates. The question is why is it we don't use the same techniques to build our forms. Forms are mostly declarative in nature. Yet the tools and languages we use fight the separation of the declarative portions from the procedural portions.

Under this light, why should I choose (for example) Haskell? I'll go with Visual Basic, which can help me deliver the forms very quickly, has tones of tools, documentation and examples, and I can find plenty of programmers to help me deliver the product.

Indeed. Perhaps a client-server DB application would be very easy to write with Haskell, perhaps as easy as Visual Basic. But since I know Visual Basic, why should I waste time migrating to Haskell?

How would I benefit from using Haskell, for example?

I'm probably in the minority but I tend to think of most programmers as smarter than many give them credit.

I do not know, but from where I stand, it would be easy to counter your argument. And sites like thedailywtf show many examples of bad programming.

A common assumption is that this domain represents the bulk of manpower requirements for programmers.

Well, most projects I have worked on, seen, discussed about in this and other companies in all the 10 years of my professional career are about forms and databases.

Anyhow, I think you trivialize the amount of complexity involved in database-to-user-form apps. Designing a good database schema is very hard. Designing a good UI is even harder.

I was talking about the complexity of code. DB and UI design are certainly hard, but not really that complex.

Perhaps the apps you work on can get by with Client-Server. Most apps I work on these days demand the web interface be either the sole means of access, or at the same level of capabilities as a sister desktop application. Users want access to their data at all times and all places. Many of the client-server apps I've been involved with lately also involve cache clients, where the user can go off-LAN and have the full power of the app built into the client - synchronizing when the user gets back on-LAN.

Web apps are still client-server, be it 2-tier or 3-tier.

The complexity of web apps comes from the erroneous concept of browser and hypertext documents used for interactive applications, not from the complexity of computations or the number of states of the system.

Well, as near as I can tell you equate functional programming with Haskell (and perhaps Clean). I think ML, Oz, Scheme, Erlang and just using FP with current languages (like Boost) also deserves attention. Is it really necessary to chuck the concept of FP simply because one can't see programming in a pure language like Haskell?

I usually write about Haskell because it is the favorite around here :-). But I agree with you, and I already have written elsewhere that I would like to see more FP in mainstream languages.

Perhaps most programmers will need to fall back on state, but that doesn't mean that it should pervade every line of code that we write.

I couldn't agree more.

I think that even more important than functional programming is the declarative paradigm (though the two tend to overlap). Those databases that you refer to are quite declarative in nature - everything from the schema on down to the retrieval and updates. The question is why is it we don't use the same techniques to build our forms. Forms are mostly declarative in nature. Yet the tools and languages we use fight the separation of the declarative portions from the procedural portions.

You've described the problem correctly! here is my comment on Java's Swing app framework.

Here is another comment I made on allegro.cc about Ajax and ASP...guess what answer I got: "stupid LISP is not ASP", although a simple declarative language could reduce an 1-hour effort to 5 minutes.

But that's different from saying that Haskell doesn't have a place for a significant number of projects that do require a bit more programming discipline. Personally, I think the number of PLs in active use will continue multiplying. The days of a single language (which probably never existed) are numbered.

Ooops! unfair comment :-). I've stated that in my opinion Haskell and other languages are better for other types of projects, even necessary.

But the topic is that 'why people don't use FP' and my reply is 'people that need FP already use it'.

As people are probably getting tired of hearing by now, multi-core architectures mean that new programming models are desperately needed. There is an enormous economic imperative to find some way, any way, to allow average and below-average programmers to cleanly and safely utilize multi-core machines at reasonable efficiency. The industry absolutely will be spending tens of billions of dollars on this problem one way or another, and it would be nice if the end result was something decent. Many of the ideas from current functional programming languages will be necessary to this effort, even if the actual languages themselves probably won't.

Suppose that we have a fully pure FP program of many lines of code. Ideally, every little expression of the program could be executed in parallel. But almost in every expression the result must be passed to another expression! How is this program going to be automatically parallelized?

Obviously the parallelization can not take place in compile-time, because neither the size of data nor the availability of threads/CPU slots can be determined at compile-time. The scheduler needs to exist at run-time. How is the run-time scheduler supposed to work? how is the scheduler going to be able to understand how to best allocate resources to threads?

Furthermore, access to the memory manager should be synchronized. Since FP programs do lots of heap memory allocations, the number of synchronization attempts would have a big impact on performance.

Your failure to imagine it doesn't mean that it cannot be done.
LLNL's Sisal language was competitive with Fortran over 15 years ago.
Robert Bernacky also wrote an APL compiler that did exactly the optimizations you mention.
None of the other problems you mention are unique to functional languages. OpenMP, for example, has runtime scheduling.
(edited to mention APL)

SISAL looks fairly neat. Anybody know how popular it is, or how it feels to use vs. say Erlang?

I wonder if there can be a compiler which automatically parallelizes FP code, without special semantics.

I actually wasn't thinking about automatic parallelization, but rather manual parallelization. Programs written without mutable state (or with localizable state) are much easier and safer to manually parallelize than programs with global state. Google's map-reduce works on this principle, with junior developers able to slot their more-or-less functional programs into a massive parallel/distributed backplane.

Furthermore, access to the memory manager should be synchronized. Since FP programs do lots of heap memory allocations, the number of synchronization attempts would have a big impact on performance.

This is a long-solved problem (>30 years solved, IIRC). Modern memory managers for GC'ed languages allocate thread-local memory pools. Accessing those pools for allocation requires no synchronization, unless the pool needs refilled.

Data Parallel Haskell and Haskell on a Shared-Memory Multiprocessor might be of interest to you.

For your scheduling problem - how does your scheduler work today? How does your OS understand how to best allocate resources to the programs you run?

The problems you highlight with concurrent memory allocation and garbage collection have had a fair amount of research on them, people are very much aware of the problems.

Just a quick word: functional programming in functional languages is based on lambda-calculus and lambda-calculus translates quite naturally to pi-calculus. In turn, behavioural theory of pi-calculus defines quite well how to perform transformations (read "increasing parallelism") without altering the semantics of a term.

While this is not a decisive argument, it does suggest that functional programs may be easily translated to quite optimised parallel code.

This is definitely not my cup of tea, but a different approach is The semantic layers of Timber that describes a stratified semantics of a language with one layer closely resembling process calculus.

In general the need to exchange data over the internet strongly suggests list structure, as does all communication.

I think that the more general structure you're getting at is the algebraic data type and more specifically recursive types, of which lists are merely the simplest example. Functional programming languages are designed to handle such types, and do so very well.

The FP with Bananas & Lenses paper shows how the definition of lists can be generalized to recursive types, and how fold, unfold and related operations can be used to relate and translate between different recursive types. The paper is quite mathematical, but its basic message can be gleaned without following all the math. (For some advice on one way to work up to this paper, see the last paragraph of this comment by Dominic Fox in the Getting Started thread.)

The Universality of fold tutorial, while it focuses on lists, covers the important, general properties of fold, which can be generalized to recursive types as described in the Bananas paper. Both of these papers are mentioned on the LtU papers page, for good reason. There's more to it than lists!

For me, writing such a program in a purely functional manner would be a lot more of a puzzle.

But most functional programming languages are not pure! I do think, though, that the very existences of pure functional programming languages acts as a kind of bogeyman for many people. Perhaps they suspect that the impure functional languages are just there to lure them into doing the hard stuff -- a gateway drug. You start out using fold, and end up mainlining monads...

I think it's much more productive to think of purity as a way of understanding why we use impurity (at least when starting out, i.e. while you're just doing pot). Purity is also, of course, useful when dealing with programs mathematically, so my comments about FP in PL Theory apply here.

Agreed, but then what's the point, really? If purity doesn't really matter, there's a lot to be said for the "people have taken what they want from functional programming languages and rolled it into other languages" point of view.

I didn't say purity doesn't really matter. Even experienced imperative programmers know that it matters a lot, but that doesn't mean that achieving complete purity in e.g. the Haskell sense should be an overriding goal for every system. However, the kinds of systems you mention can still benefit from a more disciplined approach to mutation.

If doesn't really matter, there's a lot to be said for the "people have taken what they want from functional programming languages and rolled it into other languages" point of view.

There's a lot to be said, but I'm not sure that very much of it is good. Very few languages other than the ones usually identified as functional are able to exploit functional style to any significant degree. Purity is far from being the only feature of functional languages that hasn't yet been rolled into other languages. Even something as fundamental as dealing with recursive types hasn't yet been credibly dealt with in any non-functional language that I can think of, which is a pretty serious limitation on exploiting functional style. One might propose that OO is the mainstream answer to that, but there are plenty of problems with that idea.

Now I'm seeing my previous posts weren't worded all that well, but anyway...

Programming in Python (for example) is a lot more value-oriented than programming in C. Strings are immutable. It's common to create complex structures on the fly. There are list comprehensions, map, filter, and a limited form of lambda expressions. There's garbage collection. From my personal experience, these are things I associated with early functional languages like Hope, and now they're standard in various scripting languages. Yay!

Other things from functional programming are not standard: absolute purity, recursive types, monads. I think those are generally viewed as less useful. (Note: I'm not knocking functional programming at all. I use Erlang quite a bit, and have gone further than I suspect most people have in terms of purity.)

There's certainly been feature migration, but it's piecemeal, and misses some of the main benefits of FP. That's to be expected, and isn't too much of a problem as long as the migration is an ongoing process. But it's a mistake to think that the important migration has essentially all already happened.

(Individual feature migration between languages/paradigms can be a sort of "ducks swim well, so let's glue their feathers on our swim trunks" approach. While it might give some useful capabilities, it doesn't capture the full benefits by any means, and in fact it can be counterproductive — "well, those duck feathers didn't work out so well, guess those ducks aren't such good swimmers after all.")

Recursive types may very well be "generally viewed as less useful", but that view is wrong: they're critical, and the links in my comment Lists generalize to recursive types help to explain why. Without good support for such foundational features, it's not really possible for the non-functional languages to exploit functional style properly.

You also mentioned absolute purity again, but it's really providing disciplined ways of managing impurity that's important, even in Haskell. I don't agree that such capabilities belong in the "generally viewed as less useful" category: most mainstream programmers regularly deal with the issues created by impurity, and many techniques, ranging from ad-hoc to language-embedded (e.g. 'const' declarations) are used to help deal with it. The problems created by impurity are recognized by many, but mainstream approaches like OO are heavily skewed towards a dependency on mutation. Functional programming and languages still have a lot to teach in this area.

Games are getting more complex, though, and in the past ten years or so there have been many "Engines" developed. I suspect this has to do with the increasing complexity of the physics, AI, rendering, etc.

As discussed previously, there is a perception that FP could make this a lot less tedious.

There are still no examples of a large commercial game written in a functional manner, whereas there are thousands and thousands of games written with the most primitive of tools (including Apple II games developed entirely with the built-in ML monitor and no true source code).

I vaguely remember reading ages ago that the Crash Bandicoot games were written primarily in a Lisp dialect (I think - it might have been Scheme), with only a few core routines written in C for speed. I suspect there are more examples out there too, it's just that you don't get to hear about that aspect of them.

Actually, a quick bit of googling turned up this...

Naughty Dog wrote custom Lisp-like languages (GOOL, then GOAL), but they're not FP-oriented. There's a pretty good description in Wikipedia. It's still a very cool and very successful project, in any case.

Typically, functional languages focus on a higher level of abstraction so the ability to declare data of a certain length or do bit level operations is not as omnipresent. However, I see no reason that a functional language couldn't implement those features and I'd be a tad surprised if no such language exists. The GC may be a bit more of a valid concern for apps such as games but GCs are getting better all the time and some languages allow for you to shut them down and do explicit GC cycles at specific times.

There's a separate thread on the definition of a closure so I don't want to stray too far on that here but closures usually exceed the definition of a C struct in that they have visibility to parent scopes (lexical scoping). Granted, you can build data structures out of closures that you may use structs for in C. However, there are constructs you can build out of closures that you can't build out of C structs alone.

For applications that are very performance intensive, like games, you can always use a traditional language for the engine and a functional language, if appropriate, for other modules such as scripting. For instance, WoW uses (at least I'm pretty sure) C++/C for the main engine and Lua for scripting. Although Lua is certainly not a purely functional language, it does support first class functions and closures so you can use functional style if you want.

I just saw mention of Embedded ML in another forum thread.

Seems like all links are broken. Is this project dead?

It uses pattern matching syntax against binary data. In the little bit of time I spent with erlang, that was one of my favorite features. It worked a lot better than manually applying a bunch of bitwise ands and shifts to extract data, which is the way most 'system-level' languages let you deal with the data.

I certainly don't mean my comments in an insulting manner but it seems that the cons you are pointing out are not actually cons but simply questions you had about FP and never investigated.

Bit manipulation is possible in the limited FP's i have taken the time to really look at. Being efficient with memory is hard to say, it depends on what you are doing and if that is just something you feel is necessary or is an actual bottleneck. Some languages offer this fine grained control, others don't. so I'm not sure if that can be considered a con against FP.

Your issue in terms of GC suggests a lack of really questioning ones self when it comes to this. Can you give a reason why you want to manage your own memory? What is the benefit? Is managing your own memory just one of those things you 'feel' is right and has been so deeply en grained in your idea of programming that you feel something is wrong if you aren't managing your own memory? In situations like this it may be valuable to really investigate why you feel manual memory management is necessary and challenge your belief. Now that is not to say that GC is *always* superior, but the number of situations where a GC is lacking is rather small comparatively.

No insults taken. :)

it seems that the cons you are pointing out are not actually cons but simply questions you had about FP and never investigated.

I have attempted to delve into FP and learn what all the fuss is about, and so far I'm not excited. It could be because I just don't "get it" yet. I'm willing to admit that. Perhaps more people don't program in "functional languages" because (as far as I've looked) there's not a lot of places that convincingly explain what we're missing.

I've seen examples about infinite lists, lazy evaluation, closures, etc. And none of them have struck me as extraordinary. Because of speed and efficiency and the type of programs I enjoy creating, none of those things would be a benefit.

Your issue in terms of GC suggests a lack of really questioning ones self when it comes to this. Can you give a reason why you want to manage your own memory? What is the benefit? Is managing your own memory just one of those things you 'feel' is right and has been so deeply en grained in your idea of programming that you feel something is wrong if you aren't managing your own memory? In situations like this it may be valuable to really investigate why you feel manual memory management is necessary and challenge your belief. Now that is not to say that GC is *always* superior, but the number of situations where a GC is lacking is rather small comparatively.

I program heavily in C and so a GC to me seems lazy. Why not just not leak memory yourself? If you're organized and have a good coding style it's not that difficult to manage your own memory. I don't use GC in production work because I can easily write code that doesn't leak memory. (valgrind backs me up). So my benefit of no GC is smaller faster code.

I don't question the benefit of GC for other types of programs, nor their efficiency of doing what they do. I sometimes venture away from C and enjoy programming in "higher" languages. They allow you to program with less worry (like in our discussion, not worrying about memory usage), which is really nice.

However, I enjoy producing programs that are really small and really fast. If my program is more for fun and experimentation, I would have no problem using a GC, but in most my cases size and speed do matter, so I don't use GCs.

Of course, "small", "fast", "easily" are all subjective terms. YMMV. :-)

Actually, the allocation using a decent GC is often way faster than using "traditional" and "fast" manual memory management, i.e. malloc.

The reason for this is that in order to allocate space, malloc searches a list of free memory until it finds an unused block of memory big enough to fit the allocation. Instead GC (for example generational GC) simply increase the "current memory pointer" and check if there is still any memory left. If there's enough, that's all the work that is done, but if there isn't, a garbage collection cycle is triggered. Nevertheless, in general GC allocation is way faster than malloc.

I would say "in some cases, for some malloc implementations," not "in general." Can you point to any papers that support your claims "in general," i.e. using a respected malloc over a variety of significantly-sized programs?

A recent paper or presentation I read summarized it nicely:

If your program does:

* lots of small allocations, GC is often faster
* fewer, but larger allocations, than manual allocation is faster

Most research places GC runtime overhead at 5-20%. The best analysis I've seen places generational GC on par with manual allocation only when the heap is 5 times the size of the live data; smaller heaps mean higher overheads due to more frequent collections. A heap of only twice the live set resulted in 40% overheads IIRC.

Of course, GC is also much safer than malloc/free, which is often more important for us lowly developers. :-)

The fast allocation by pointer bump you mention is only for copying GCs, which aren't widely used nowadays. I don't see how mark and sweep allocation could be much faster than malloc.

Further, manual allocation can be customized to the particular application, so it will *always* be faster in one particular incarnation or other. Question is: how much effort are you going to spend implementing and debugging this manual memory allocator? It takes significant effort to implement non-trivial memory management allocation strategies.

So GC tends to be an overall engineering win, but it's by no means a winner in every category (yet).

A recent paper or presentation I read summarized it nicely:

Saying this without providing a title or a link is grounds for an LtU demerit. ;-)

The best analysis I've seen places generational GC on par with manual allocation only when the heap is 5 times the size of the live data; smaller heaps mean higher overheads due to more frequent collections.

That sounds like Quantifying the Performance of Garbage Collection vs. Explicit Memory Management. Someone summarized it here.

Sweet paper -- thanks for the pointer. That, or something like it, should be required reading for anyone who wants to claim that GC is either "too slow" or "as fast as manual allocation."

Saying this without providing a title or a link is grounds for an LtU demerit. ;-)

I know, but it was late! :-P

I think this was it.

That sounds like Quantifying the Performance of Garbage Collection vs. Explicit Memory Management.

Yup, that looks like the right one. I don't have the earlier papers I've read up on my Interesting Research page (mostly GC stuff). Thanks for the link. :-)

I'm not disagreeing with any part of naasking's remarks. I'm just suggesting a strong either-or opposition of gc or manual allocation is not necessary in a mixel model environment. Not that I can easily point you at one; but it's the model I've been planning around for a while.

Hybrid solutions (both gc and manual allocation together in some mix) can target different approaches for different parts of an application. Getting a nice mix, though, would require a mixed language model, with gc at some higher level and manual allocation at a lower one.

But with a mixed approach you can segregate your data according to purpose. The really large data sets with predictable lifetimes can use manual allocation. And the painfully hard-to-predict, ambiguous flow of control parts can use gc. A division like this would allow you to make gc memory a minority of total application footprint involved, so having five times (or more) available gc space than live data would be easy to arrange for the smaller gc minority.

Presumably the interface between the two would occur at the level of "primitive" definitions, from the point of view of a high level language. You'd be free to push some parts of an application down a lower level to manually control exactly how memory works. For example, you wouldn't really want to do network i/o in memory with non-C semantics anyway.

The ideal I'd prefer is a copying gc model in the high level language using full continuations, and a mixed reference counting and vanilla C model at the bottom for primitives, when I really have to control where things go and when. A copying gc can easily have a nice interface to "externally" allocated memory, because a copying gc can easily tell an address lies outside the space of memory managed by copying, and thus should not be copied or changed in any way.

Anyway, the gc parts can use the fast pointer bumping style of allocation, and get efficiencies from lower block fragmentation (less bookkeeping is needed) and low enough overheads by having a big enough ratio of free space to live gc data in the part of the address space that's collected.

Time pressure in development is big enough that faster development with gc first would be a win, especially when incremental shifts to manual allocation later can optimize exactly those parts most crucial to performance, without introducing a big upfront design requirement before getting a first version done.

We shouldn't forget about region-based memory management[*], as in MLKit and Cyclone. That ought to change the performance equation, but I don't have any numbers. It can be used on its own, without a garbage collector, or in conjunction with GC. There are some related links here.

[*] Old enough to have a retrospective.

You might be interested in Dylan's "Memory Pool System" then:

The Memory Pool System (MPS) is a very general, adaptable, flexible, reliable, and efficient memory management system. It permits the flexible combination of memory management techniques, supporting manual and automatic memory management, in-line allocation, finalization, weakness, and multiple simultaneous co-operating incremental generational garbage collections. It also includes a library of memory pool classes implementing specialized memory management policies.

The Real-Time Java specification includes support for defining memory regions, including different gc semantics for different regions. Arguablye this isn't quite what you are looking for (you can't explicitly free an object, just a region), but it covers the use cases you describe quite well.

naasking: The fast allocation by pointer bump you mention is only for copying GCs, which aren't widely used nowadays.

It's also applicable to generational GC, which seems to be the predominant form of GC these days.

It's also applicable to generational GC, which seems to be the predominant form of GC these days.

Generations are a heuristic optimization, not a collection technique in their own right. As far as I know, pointer bump is only possible with copying collectors, generational or not.

Just came across mark-copy GC which looks promising: reduces generational mark-sweep space overheads by ~80%.

Well, technically you are right. However, in practice most GGCs are copying, at least with respect to promoting from the youngest generation.

When you look at RT apps, GCs don't seem so appealing, same with embedded usage with little memory available.

The problem with GCs is that there are some brilliant GCs such like the new one from IBM, but you don't necessarily have access to them..

When people say "functional programming" or "functional programming language" these days, I think the definition is fairly narrow. Usually it means Haskell-like or ML-like. Almost always it means "languages based on the lambda calculus."

But Iverson and Hui's J actually gets a significant amount of use in industry (financial and actuarial work), and yet it is rarely mentioned in discussion about commercial uses of fp. Some would argue that J is "function level" instead of "functional," but that's a nit.

A reasonable question is "has the fp language community painted itself into a corner"?

In Haskell, again, the compiler has the equivalent of a Prolog system in it to do type inference/checking -- but you can't use its power as a programmer.

I wonder what this statement means?

The obvious interpretation is just as obviously wrong (after all, type inference, etc. does work) and, as has been demonstrated several times (Oleg Kiselyov's Number-parameterized types is the example that springs to mind), the Haskell type system can do all sorts of things that Prolog can do including arithmetic and various data-structures (I seem to recall reading about lists and trees, though I can't recall where, pointers welcome).

You don't mean "obvious", you mean "vacuous". If I had meant to say that the type system doesn't work as a type system, I would have said that.

The really obvious interpretation of what I said is that you can't do Prolog-like things (implicit search, backtracking, logical variables) in a Haskell program -- even though the Haskell compiler contains the better part of a Prolog interpreter to operate on the types.

Josh

This isn't really true. Yes, you can't program in Haskell *exactly* the same way you would program in Prolog, but you can emulate these features you speak of fairly easily with monads (like [] and others). You might also want to take a look at:

http://okmij.org/ftp/Computation/monads.html#LogicT

In fact, I recently was programming part of a theorem prover for intuitionistic logic in Curry (like Haskell, but with Prolog features -- it's a functional logic language), and was taken aback by how much shorter some of my solutions in Curry were versus the same in Haskell. However, after a little encouragement from one of my professors who is a big Haskell guy, I decided to try again in Haskell, and in the end, all it took was a little extra bit of ingenuity (not very much) to get almost exactly the same kind of solutions in Haskell using monads.

For what it's worth, if you really do need "Prolog-like things" in Haskell, you should probably just use Curry, and that way you get the best of both worlds.

So not only is it misleading that you can't do "Prolog-like things" in Haskell at the program level, but even if you have to do it at the language level, there are in fact solutions (Curry).

By the 'googling on language name + programming' metric, Links is more popular than any of the other languages Josh listed, with a grand total of 229 million hits :-)

Indeed, a little further research shows that the most popular programming languages are "a" and "i".

:^)

Josh

That is an interesting comment but your view is that Scheme is more popular than Haskell because ...?

...You can write a program in Scheme without making the types explicit? Will it compile the first time if you made typing errors? Or do you mean that naming types is too demanding?

Would Haskell meet your criteria of a "programmer's language" if type declaration was optional?

... of a "programmer's language" if type declaration was optional?

Good question; I don't know. My impression is that there are several other aspects of the language (and all the mainline ML-like languages) that are awkward.

The bottom line is there are two vastly different basic philosophical approaches to programming language design. The key difference is whether the language designer / compiler writer thinks he understands what the programmer is trying to do, better than the programmer himself does.

Now for programmers in the bulk of day-to-day applications work, this is probably true. But the cutting edge, it's not, and the assumption means that the more sophisticated the programmer, the more time he spends fighting the system.

Scheme otoh has the philosophy that the programmer is in charge, and we'll give him all the rope he wants, and if he hangs himself that's just tough. People on the frontier, programming new kinds of things, inventing new algorithms, find this a more congenial mindset.

Josh

Scheme otoh has the philosophy that the programmer is in charge, and we'll give him all the rope he wants, and if he hangs himself that's just tough. People on the frontier, programming new kinds of things, inventing new algorithms, find this a more congenial mindset.

Around LtU, people won't give much credence to unsubstantiated (and semi-insulting) claims like this. There are a lot of innovative people who do prefer staticly typed languages. I could list several, but I won't, because I Don't Feed the Trolls. If you want to paint with broad strokes, you need to bring your evidence to the table. And I'm not talking about giving us a list of people who are on the cutting edge and also use Scheme, I'm talking about some evidence that the well-respected people who do prefer staticly typed languages are not quite as brilliant as we think they are.

No insults intended. My point was that obligatory declarations, useful in some contexts (e.g. production programming environments) are an impediment in others (research programming).

Here's an anecdote: A few years back, I was responsible for (and wrote version 1 of) two programs for a CAD startup. One was in Python and the other in C. The Python one was larger and did real-time interaction, and was the first substantial Python program I'd written. Not a declaration in sight, of course. The C program was festooned with them, as required, and I've been programming in C for decades. Guess which one had more bugs? Same programmer, remember.

Josh

Comparing Python to C isn't exactly a fair comparison. You should just as soon compare Forth to Haskell to make general conclusions about type systems.

... namely that it is the ontological level of the language, rather than something like static-vs-dynamic typing, that is the biggest factor in its ease of use.

So to pull the threads back together, I claimed that the preoccupation of the FP community with type systems has had a chilling effect on (and diverted effort from) the development of more powerful data ontologies.

Josh

Have you ever used any of: Haskell, Clean, SML, Objective CAML, or Mercury?

I've tried all of them except Clean, and I've tried Oz/Mozart as well. Most my current experimental programming is in Prolog, with a little in Scheme. I've written an APL interpreter in Lisp, and a Lisp interpreter in APL. I've written an APL compiler in APL, and I wrote the first DECSystem-20 Common Lisp compiler (in CL of course). I've written a CAD system in J, and another one in Python. I contributed code in MIDAS to MIT Teco that the original Emacs was implemented in. (writing in J and Teco are similar experiences.) I would guess that overall, I've written programs in 50 languages (for real, not just exercises), ranging from PIC assembly code to Javascript. Trying new languages doesn't bother me. It needs to get a lot of things right for me to stick with it, however.

Josh

...but "try", "play" and "dink with" would be synonyms in my case. :-)

That said, I don't understand what you're trying to say in terms of the study and implementation of type languages interfering with the discovery of more meaningful research avenues for PLs (ontologies). Before beginning that discussion, it might help to agree on what the problem with current programming languages happen to be. I think we can agree that the problem is not that we have too few programming languages.

One problem would be that we have no way to rigorously examine the properties of the programs we write, a kind of guiding principle for type theory. Another problem would be that we are limited in the ways that we can express solutions - i.e. there are problems that currently rank as hard-to-intractable. Or perhaps the problem is that programming languages are error prone and hard to use as a means of communication - i.e. there has to be a way to make us more productive and less prone to mistakes. Or perhaps just a combination of these and many other problems that we currently have to put up with.

Anyhow, what fundamental nature of PL's do you think is currently getting short shrift on the R&D end of the scale?

An excellent question, and one that deserves more thought than I'm going to give it here :-)

I'd say one big lack is seamless integration of the many powerful paradigms that have been discovered. This is a well-understood moral hazard of academia, since you don't get tenure for doing integration work on other people's ideas. There is Leda, but multi-paradigm stuff is few and far between.

A related lack is IDE's and debuggers. Not too much hay to make as a theoretician, but there's a great need for the best and brightest of language mavens to contribute ideas here.

But the biggest lack is ontologies, in datastructures and the operations provided to manipulate them. I think that language designers today are way too ready to provide OO capabilities and punt the issue to the programmer, but that's just a way of ducking the problem. Coming up with a set of datastructures and an integrated set of well-matched operations that combine flexibly to allow the elegant specification of a wide range of representations and methods is very hard work, and the languages community has virtually ignored it for decades.

Because of this, languages have been stuck at a ground level of semantics for the same period. Here's an example: it was easy to write a sort in APL with a matrix expression that compared each element with every other one. Nobody would use that because it's N^2 -- and yet it was simpler and easier to understand than any N log N sort. Suppose instead language research had decided to concentrate on (a) finding ways for the programmer to specify, completely formally, but always more concisely and elegantly, what needed to be done, and (b) finding a way to compile it as efficiently as the state of the art knew how to do?

Josh

ps -- BTW, I do know that there has been some research along these lines, in areas like CLP and as someone above mentioned, Curry, which is a very neat system. But I still opine that we'd be better off if say 75% of the effort that has gone into types had gone along those directions instead.

but multi-paradigm stuff is few and far between.

Have you not read CTM or any of the voluminous discussion it has generated here on LtU?

All the work being done with OCaml also seems to contradict this notion that multi-paradigm issues have been ignored by academics and PL designers.

But the biggest lack is ontologies, in datastructures and the operations provided to manipulate them

Again it seems to me that there is all kinds of work done on data-structures and their signatures (some of it under the umbrella of the type-system investigations you seem to be impugning). Do you have some specific problem in mind that you think needs to be solved via PL research?

punt the issue to the programmer, but that's just a way of ducking the problem

PLT already gives the programmer who takes the time to study it plenty of tools to help him solve his problems (which are too varied for all of them to be anticipated by the PL designer). Very often not finding the "right" solutions is a sign that one is not asking the right questions.

The responsibility of academia is to advance human knowledge in all available directions. The reponsibility to understand the new knowledge so generated, and to use it to solve more immediate problems, lies with the practitioner.

PLT already gives the programmer who takes the time to study it plenty of tools to help him solve his problems (which are too varied for all of them to be anticipated by the PL designer). Very often not finding the "right" solutions is a sign that one is not asking the right questions.

What does PLT have to say about ease of debugging? Ease of maintenance? Requirements traceability? The sad answer is "a lot less then it probably could". There appears to be a decided lack of interest in the PLT community in the sort of software engineering issues where programming language improvements could do the most good.

The responsibility of academia is to advance human knowledge in all available directions. The reponsibility to understand the new knowledge so generated, and to use it to solve more immediate problems, lies with the practitioner.

This would work if academia actually had the resources to explore "all available direction". They don't. Tradeoffs get made, and unsurprisingly those tradeoffs don't always have the best interests of non-academic programmers at heart.

Dave, you're exactly right.

Business isn't interested in PLT. Most of it isn't even interested in software. It's just a means to an ends. And that means is represented by software engineering and not PLT. That's why it takes something like Sun or Microsoft to bridge that academic, real-world-business-interests divide.

A first step is to develop IDEs or plugins that have the same level of support that C# and Java get with VS, Eclipse, IDEA, Netbeans, etc...

What does PLT have to say about ease of debugging? Ease of maintenance? Requirements traceability?

What do you think PLT should say about these?

Debugging is mostly an implementational issue, though various kinds of semantic modelling can help work out a good system.

Ease of maintenance is enabled by all the abstraction mechanisms that are already provided. Very often programmer skill is the limit there.

Requirements traceability is probably a lost cause in general or else perfectly adequately handled by existing documentation methodologies, depending on your inclination. What makes you think PLT should and can make a difference there?

Tradeoffs get made, and unsurprisingly those tradeoffs don't always have the best interests of non-academic programmers at heart.

I would wager that more work gets funded specifically for industry-oriented work than gets neglected by "effete theoretical concerns".

Nonetheless, why do you think that academic investigators have a moral responsibility to investigate the problems that happen to seem reasonable to industry programmers? There is plenty of applicable work that already exists that industry continues to ignore for years to come, due to its own predilictions and blind-spots.

Please keep in mind, I'm speaking as an industrial programmer here, independent of my theory-wonk hat. The latter interest merely allows me to know that there is a lot of work that is done that speaks directly or indirectly to software engineering issues, but because it isn't all framed as pithy solutions to pre-conceived problems, it gets perceived as "irrelevant".

Ultimately, this whole critique of academia as out of touch with "real" concerncs is baseless until one has done one's homework and knows what knowledge has already been investigated, and has applied this knowledge in practice.

Surely, the academic/industry exchange has to be a two-way street?

Debugging is mostly an implementational issue, though various kinds of semantic modelling can help work out a good system.

So programming language theory has nothing to say about observability of program state, validity of state transitions, and abstraction of observational patterns? Have we reduced the subject to literally nothing but types?

Ease of maintenance is enabled by all the abstraction mechanisms that are already provided. Very often programmer skill is the limit there.

There's very little difference from this statement and "our current abstraction methods aren't very useful at easing program maintenance".

Requirements traceability is probably a lost cause in general or else perfectly adequately handled by existing documentation methodologies, depending on your inclination. What makes you think PLT should and can make a difference there?

I would have thought that matching specification to implementation (and understanding the transformations involved) would be well within the scope of programming language theory.

Nonetheless, why do you think that academic investigators have a moral responsibility to investigate the problems that happen to seem reasonable to industry programmers?

I certainly never indicated any such thing. There probably is a good moral argument to be made that, in the face of an enormous social problem ("The Software Crisis", broadly defined) that uniquely-skilled academics have some responsibility to target at least some of their researches toward understanding and alleviating it, but I am explicitly not making that argument.

So programming language theory has nothing to say about observability of program state,

The basic PLT constructs of environments, continuations and stores seem pretty relevant here. Provide inspection of those structures, along with single-stepping and you've got a debugger. Here's just one randomly googled link to some work by the PLT Scheme group on object debuggers. They also have MzTake. Is there some particular aspect of debugging theory that you've looked for information on, and haven't found anything? Perhaps a query on LtU could help.

I must admit I feel sorely tempted to weigh into the overall argument with a long screed, but I doubt it'd do any good. I