Lambda the Ultimate

That said, you might want to check out Ocaml... You won't get a fancy IDE...

Interesting. It apparently supports Haskell too.

I wonder how alpha is "alpha". I've given up using Eclipse for anything other than Java, because the feature set with other plugins wasn't really superior to other alternatives. This includes the PHP and C++ plugins, which I suspect are more mature than Ocaml/Haskell.

I've been using the Haskell plugin for Eclipse for at least 3 releases. It's not perfect, but if you already know Eclipse it is well worth trying out.

It works well with GHC - providing problem feedback each time you save a file.

Lisp in a Box made it really easy for me to try Common Lisp on Windows. I highly recommend it to those interested. Common Lisp itself, though, is a bit clunky as a functional language.

While thinking Lisp, Scheme might be worth a look. There are a few Scheme implementations that run on top of the JVM, so any Java library is available to them. (I haven't tried using a Java library from Scheme, so I can't say how easy it is.) I find myself using PLT Scheme (which is not on the JVM) because of its many extensions, and it has a GUI toolkit built on wxWindows, although I haven't tried it.

Both Lisps lack the pattern matching and interesting type systems of modern functional languages, unfortunately. Macros are the real draw.

Pattern matching is available as a portable extension: http://www.cliki.net/fare-matcher.

Usually, when people mean "pattern matching", they mean pattern matching as a computation model.

Really? Functional languages mainly use pattern matching as a method of function dispatch.

not (A xor B) <=> (not A) and (not B)

My dear distinguished and learned poster: "Ignorance is no argument" [Baruch Spinoza], but, well, please, please, please, "Be obscure clearly" [Elwyn Brooks White].

;-P

FPLs usually employ pattern matching in context of data types built from base types (integers/strings), untagged product types (tuples), and tagged sum types (tags being names of constructors).

So one frequently uses pattern matching to transform (adapt) a context (continuation) of some sum type (lets say C = A x y | B z C) to a number (product) of contexts (continuations) dealing with alternatives (A x y, B z C) separately. Using "xor" for sum, "and" for product, "not" for continuation, one can arrive to quite logical formula demonstrating simple use of pattern matching.

Arguably, this is but a part of pattern matching, the other being syntactic sugar. Which of these parts has more rights to be called "pattern matching" is a cultural question. Should we vote? :-)

Well, thanks for clearing that up.

Vote? Democracy? No way, I prefer LtU's anarchy. [Oops, *ducks*, way OT now ;o)]

Well, thanks for clearing that up.

OTOH, I would be glad to see any comments from FP practitioners on whether pattern matching is indeed useful only/mostly in presence of tagged sums.

A programming language isn't useful without the presence of sums (perhaps as a derivable concept). Sums are how you make choices. Anyways, if we had "algebraic" data types without alternation all pattern matching could do is essentially project components. It would still have some convenience as deeply nested patterns would be less fun to write out, but this would be rather minor.

Also, I want to point out (and add to your clarification), that pattern matching, or more precisely the simplest form of case are "part" of the sums. (In CT-speak it is the unique mediating (iso)morphism in the definition(s) of coproducts.) Essentially, in "case x of Left a -> M | Right b -> N", the "a -> M" and "b -> N" are the two continuations and case turns them into a single "A+B -> C" expression.

pattern matching, or more precisely the simplest form of case are "part" of the sums

I remember getting this idea from Epigram docs. Well, I just could not explain it right :-)

OTOH, I would be glad to see any comments from FP practitioners on whether pattern matching is indeed useful only/mostly in presence of tagged sums.

I would agree with that statement. With the remark that OO class (inheritance) hierarchies often can be treated as tagged sum definitions too, there are some examples where pattern matching is used as a nice way to distinguish and decompose objects.

The important quality of pattern matching, like implemented in ML (and even better in Haskell), for me, is that it allows me to define a term rewriting rule in a very concise and natural manner. I seem to think of programming as term transformations.

A bit OT: But that's my way of doing things. I once read a somewhat different opinion on Slashdot that, I have a lousy memory, functional programs are impossible to debug since they are so abstract (build around 3 primitives) that noone knows what's happening ;-).

Well, I don't agree with the last statement but I do have the feeling that a lot of programmers are, and will be, better served with Python (let's not forget Guido! a rare programmers/people's language designer) than with ML or Haskell.

Btw, did you check the boolean logic truth table of your expression?

Btw, did you check the boolean logic truth table of your expression?

If seriously, I was once confused by slight discrepancies between classical logic and computational interpretations, but quite often it's possible to find some excuse for them.

Given that a) programming languages are implementations of computational models and b) computational models are not reducible to each other due to different properties of time/space complexity, safety, etc. we see that there is a real point in figuring out what computational model is meant where exactly.

Term rewriting (which is just "pattern matching" by another name) is a perfectly valid and effective computational model.

Which leads to the conclusion: implementing pattern-matching syntactic sugar on top of e.g. Lisp or C++ is not "good enough".

(Granted, this distinction loses much of the acuteness when we live in a world dominated by Intel.)

Given that a) programming languages are implementations of computational models and b) computational models are not reducible to each other due to different properties of time/space complexity, safety, etc. we see that there is a real point in figuring out what computational model is meant where exactly.

A programming language is not an implementation of a computational model though its operational semantics may depend on it.
Some computational models are reducible to each other, some are not.
Sometimes it is interesting what computational model is meant where exactly, abstractly, informally, most usually reduce to computational models of von-Neuman like "random memory access machine" kind-of-thingies.

Term rewriting (which is just "pattern matching" by another name) is a perfectly valid and effective computational model.

Term rewriting doesn't equal pattern matching although they are a natural fit.

Which leads to the conclusion: implementing pattern-matching syntactic sugar on top of e.g. Lisp or C++ is not "good enough".

You might try and explain this.

(Granted, this distinction loses much of the acuteness when we live in a world dominated by Intel.)

I am sure of it. There is no Ivan Tkatchev. You, sir, are an academic article generator.

Forget it. A bit more clarity Ivan, please.

A programming language is not an implementation of a computational model though its operational semantics may depend on it.

This is simply not true. Were it true, then PL design could be reduced to "syntactic sugar", and the problem of syntactic sugar has been resoundingly and absolutely solved back in the 1960's, and there is no point in this blog's existence. In other words, the only academically and theoretically interesting PLs are those that implement some sort of interesting computational model.

Some computational models are reducible to each other, some are not.

Right, and this is exactly why implementing pattern matching on top of Lisp is different from a language that implements pattern matching "natively" -- there are two computational models implied behind both solutions that are not necessarily reducible in an equivalent way.

Secondly, we say "pattern matching" but we really mean "term rewriting". Usually, "pattern matching" is a more lazy and informal way of saying "term rewriting" for people that are afraid of complicated words; but the implied computational model is usually the same in both cases!

Which brings me to the main point:

There are actually three levels of abstraction at play here:

• The computational model implied by the PL.
• The computational model of whatever hardware is running your program.
• The PL (read: compiler) that bridges the above two in some fashion.

Which is why Intel dominance is hurting CS theory badly: people tend to assume that the second level of abstraction is a primitive model of the simplistic random-memory-access 486 chip. This is simply not true for the general case, nor even in real-world practice. (For example, we get lots of interesting and hoary computational models when we introduce parallelism.)

[famous last note by A. Huxley]

This is simply not true. Were it true, then PL design could be reduced to "syntactic sugar", and the problem of syntactic sugar has been resoundingly and absolutely solved back in the 1960's, and there is no point in this blog's existence. In other words, the only academically and theoretically interesting PLs are those that implement some sort of interesting computational model.

Is true. Most language discussed here have the same mathematical expressiveness.
I have no clue whether there is any point to this blogs existence nor will I ever claim that there is. Whatever, it seems to amuse people
There is some truth to the last claim in the sense that I think that a lot of PL research could be rightly thrown out of the window and be replaced by other research ;-).

Right, and this is exactly why implementing pattern matching on top of Lisp is different from a language that implements pattern matching "natively" -- there are two computational models implied behind both solutions that are not necessarily reducible in an equivalent way.

All standard theory disagrees with you, though.

Secondly, we say "pattern matching" but we really mean "term rewriting". Usually, "pattern matching" is a more lazy and informal way of saying "term rewriting" for people that are afraid of complicated words; but the implied computational model is usually the same in both cases!

I don't mean term rewriting when I say pattern matching, at least I hope so ;-)

There are actually three levels of abstraction at play here:

• The computational model implied by the PL.
• The computational model of whatever hardware is running your program.
• The PL (read: compiler) that bridges the above two in some fashion.

They don't. The first must reduce to the second.

Which is why Intel dominance is hurting CS theory badly: people tend to assume that the second level of abstraction is a primitive model of the simplistic random-memory-access 486 chip. This is simply not true for the general case, nor even in real-world practice. (For example, we get lots of interesting and hoary computational models when we introduce parallelism.)

All those computational models reduce to each other normally. I am flabbergasted. I give up. You win.

In general, "Turing equivalence" is a harmful notion because it completely obscures the important bits of theory. (Which are, like I said, the bits that deal with complexity and safety.)

"Computability" in the larger sense you mentioned gives us no useful academic results -- the field stopped developing after Turing and Church. Meanwhile, I want practical theoretical results that guarantee that my programs run correctly and finish in certain time limits without exhausting memory.

Second point: one cannot conflate the three abstractions levels I mentioned; at least, if you do so you completely obliterate all point in PL theory, since all PLs are now glorified macro-assemblers.

I'm assuming that there is some important value in expressing algorithms with computation models different from those computation models which are used for building hardware. Not only because math and logic needs its own language, but also because of practical notions of portability and safety.

Prolog does "macros" is a cleaner and easier to understand fashion anyways. So does O'Caml, for that matter. (Though poorly documented, sadly.)

Generally, I find that Lisp-like "macros" are useful only if you really need a way to fight the cruel language design of Lisp-like languages; for actually building DSLs there are usually more convenient tools.

If you want to see what can be done with Erlang and OpenGL: Wings.

Your other choice might be to just use Python and do things in a functional style, using lots of first-class functions and list comprehensions. But it's dangerous to buck a language's culture when you use it: Guido has suggested removing map/filter/fold/lambda from Python in future versions, the language lacks support for tail-recursion, the syntax is not that conducive to FP, and the "accepted" way to do things in Python is really to use OOP.

I'd say avoid this anyway: Python doesn't have proper (ie. lexically scoped) closures, so the FP has weird semantics. I'd rather Python did remove these operators from the language, to avoid instilling false expectations in the programmer.

...or do one or more parts of your solution blatantly violate requirement 1 of my original post? I'm sure Microsoft deserves to get compensated for its work in developing .Net and Visual Studio, but as a contributor to OSS, I won't be one of the people so compensating them. Frankly, I'd rather donate money to one of the free projects than buy a VS license.

No, it is available for free: http://research.microsoft.com/projects/ilx/fsharp-release.aspx.

...but I'm pretty sure VS and C# are not.

Which includes language support for C#, VB.NET, J#, C++. Yes the whole compiler and .NET libraries are free.

Visual Studio is not free, but it is not required to build .NET apps. There are:

emacs mode
Eclipse plugins,
Sharp Develop

F# is a language add-in with a fantastic future. It's pretty much OCaml with access to the .NET Framework libraries. Anyone with experience building GUIs will attest that building GUIs with WinForms is unparalleled in ease and speed.

Don't get a knee jerk reaction against.NET because it's Microsoft. They have some nice research projects going on. Not only that but they have enough power to put FP into the forefront. I'm waiting a few years to see how F# works out. C# and VB.NET are getting more functional in future versions too.
C# future
VB.NET future

'free'

By having Windows as a requirement?

David B. Held: ...I'm sure Microsoft deserves to get compensated for its work in developing .Net and Visual Studio, but as a contributor to OSS, I won't be one of the people so compensating them...

But this is one of the few cases where the alternatives really aren't as good. I use VS at work, and I don't find anything particularly impressive about it. I prefer C++Builder. On the other hand, the Win32 GUI is about the only worthwhile thing Microsoft has written (note I didn't say the whole OS...just the GUI; nor did I say its GUI API is superior). I don't think any of the *nix GUIs or even the MacOS/OS X GUIs compare (the Mac GUIs look nice, but do not have nearly as rich native controls).

As a startling consequence of Erik Meijer's last post, if I understood it correctly, the next generation of VB might start to fit all criteria any time soon.

In particular, is Microsoft meeting the 'free beer' criteria?

I believe the VB compiler and the SDK is free. Now whether people find it useful without VS is another story. Is there an Emacs mode for VB?:)

It's in the best interests of M$ to have a huge army of developers diggin deep into their platform. In the memorable words of the chief: "developers, developers, developers...".

So, the whole infrastructure needed to develop .Net apps is certainly free as in beer. It's good marketing.

Of course, for most practical uses, you need VS. You can't simly open vi, type your program away and have a look at the docs when in doubt about a very deeply nested class... it's nonsense and improductive.

It's annoying when people joke of the open-source development tools, but think it's fine that the whole .Net is free. Yeah, it's free, but not as productive as C++ with KDevelop or Java + Eclipse. Even C + Emacs...

That's what you get when you give up freedom and go for some cheap free lunch...

It's in the best interests of any platform to have an army of developers

There is a free IDE for VB, C# called SharpDevelop. It's no VS.NET, but it has "intellisense" and other stuff. Most windows developers don't have a problem paying for VS though when they're going to be spending 40+ hours week in front of it.

Most people don't feel more "free" because they have the specs/code to their microwave.

Shameless plug: the SchemeScript plugin is located here.

Looks really promising.

Scala isn't Nice

David B. Heid: O'Caml... Don't like different names for integer and floating point intrinsic operations. I understand the point of strong typing, but it seems to me that overloading or parametric polymorphism or something should be able to come to the rescue.

While we're waiting for G'Caml, you may wish to read about polymorphic variants and code reuse in O'Caml and see if they can help address some of the issues you'll encounter.

"Ruby - Isn't this a lot like Python? As in, not-very-pure-FP?"

Actually, it's not a FP language at all: it's full of side-effects. Just like C++ or Scheme.

However, FP is a style or technique, not an implementation. Though some of its features are required to be supported by implementation, many programming languages are fully apt to do FP. Scheme, C++ and Ruby all fit the criteria.

Of course, Ruby is dynamically typed, just like Scheme, Smalltalk or Erlang. So, i guess you'll be overlooking a large amount of good languages and their dynamic strengths...

Forget the alpha plugin for Eclipse.

Get Emacs for windows and download tuareg-mode
http://www-rocq.inria.fr/~acohen/tuareg/

Which of course runs on windows.

You didn't mention static typing in your original requirements, but it seems to be one. Without wanting to start up the tiresome typing arguments again, I see this more as a personal quirk and not something that should obscure your vision. More than anything you want reliability, support, good tools, good libraries.

If someone gave you the task of munging together a bunch of data into a web site, then you'd be silly to ignore Python, for example. You wouldn't say "I refuse to work in a dynamically typed language."

There are enough smart and successful people in both camps to make this one of those meaningless issues. People who make money with OCaml are getting along fine with static typing. People who make money with Python, Erlang, and Lisp are getting along fine with dynamic typing.

The preference for static vs. dynamic typing has something to do with the application domain/execution environment. It seems that languages I prefer to use which have dynamic typing are often scripting languages which glue together components in a heterogenous environment. Whereas, for applications in which all of the components will be implemented in the same language, I prefer to use a statically typed language.

Now, I'm all about code reuse and library building. And one of the most important aspects of library building is making your components as idiot-proof as possible. Just off the top of my head, I remember writing a Lisp program that did some simple stuff with matrices. I implemented a matrix as a list of lists. However, I don't recall having a simple way of ensuring that my matrix-operating functions were always passed a well-formed matrix. The best I could do was to write a function which inspected the structure of the matrix parameter to make sure it conformed to the interface.

Of course, the disadvantages of this approach include the need to call the validation function in each operation as well as the overhead of the validator itself. Since there was no need for runtime polymorphism of the matrix arguments, I would have much preferred static type checking, which would have eliminated the runtime overhead as well as avoided problems like forgetting to call the argument validator.

If there's some better way to deal with type checking in dynamically typed languages, I'd be more than happy to learn about it. But for large-scale software development, and library development as well, I really don't see how you can get around the benefits that static checking brings.

I wrote:

There are enough smart and successful people in both camps to make this one of those meaningless issues. People who make money with OCaml are getting along fine with static typing. People who make money with Python, Erlang, and Lisp are getting along fine with dynamic typing.

Obviously the people writing large scale, production code in Erlang have dealt with this. They key is to write test cases and have a regression test suite that you can run at the drop of a hat.

According to James Hague, the "key [to dealing with dynamic typing] is to write test cases and have a regression test suite that you can run at the drop of a hat."

That's certainly a work-around. But it's not as good for two reasons:

1. Tests, in theory at any rate, don't do as good a job, because an invariant is stronger than a test. An invariant can guarantee that a certain condition never happens, a test cannot.

2. I have rarely seen cases where providing more-or-less equivalant checks through tests was not more verbose and more work to write than doing it with a good typing system.

"Dynamically-typed" languages do not provide an advantage over "statically-typed" languages because they lack early checking of typing; they provide an advantage because they remove the bad parts of many implementations of "static typing." Unfortunately, they remove the good parts as well.

I've been doing a lot of coding in ruby in the last year or two, and I have to say, I really do miss the convenience of being able to say, "never let this function be called with an object that doesn't satisfy these properties" and forgetting about it from that point on.

"I've been doing a lot of coding in ruby in the last year or two, and I have to say, I really do miss the convenience of being able to say, "never let this function be called with an object that doesn't satisfy these properties" and forgetting about it from that point on."

That realy isn't a property of dynamic typing in general. You could do that with dynamic checks as well.(With all the pros and cons of dynamic typing in general.) It's true though that nearly no dynamic languages does this.

Just off the top of my head, I remember writing a Lisp program that did some simple stuff with matrices. I implemented a matrix as a list of lists. However, I don't recall having a simple way of ensuring that my matrix-operating functions were always passed a well-formed matrix.

There's a whole spectrum of ways to deal with this, from tagging your matrix values, to implementing a completely encapsulated abstract data type. The latter can guarantee that matrix values are always well-formed. In either case, checking that you've received the right type of value is a simple tag comparison or the equivalent. This check can be automated by the use of assertions, or something more sophisticated, like PLT's contracts, which go well beyond what can be done with static checks alone.

If there's some better way to deal with type checking in dynamically typed languages, I'd be more than happy to learn about it. But for large-scale software development, and library development as well, I really don't see how you can get around the benefits that static checking brings.

To make that judgement fairly, I think you'd need to delve further into the possibilities on the dynamic side. The idea that "large-scale" software development requires static type checking is easily refuted by the various large-scale systems implemented in languages like Erlang and Lisp. There are probably such systems in e.g. Python too, although I'm not personally familiar with them.

...I guess I don't like tagging because it introduces yet more runtime overhead (in both space and time). Obviously, you need to do tagging to support runtime polymorphism, but I would like to avoid this overhead for non-polymorphic types.

The problem with relying on ADTs is that while the ADT can ensure that values are generated correctly, they cannot ensure that a function receives a parameter that has been created by the appropriate ADT. I can always try to circumvent the ADT by creating my own fake object (perhaps in an attempt to extend a component written by someone else) and passing it to a function expecting the ADT.

Also, I don't understand how assertions count as "automation". You, the programmer, have to write the assertions, correct? While contracts may be nice, there is nothing preventing you from implementing them in a statically typed language, is there? The point of static checking is to do as much at compile time as possible, as well as make the compiler do as much of the grunt work for you as possible. It seems to me that dynamic typing involves throwing away a lot of really useful information. In the days before polymorphic types and type inference, I can see good arguments for dynamic typing. But these days, arguments for dynamic typing sound suspiciously like arguments for error return codes vs. exception handling.

The idea that "large-scale" software development requires static type checking is easily refuted by the various large-scale systems implemented in languages like Erlang and Lisp

Well, I'd like you to quote where I said it's "required". However, this argument is like saying that COBOL is an excellent language because multi-million line COBOL programs exist (and quite a few more than Erlang and Lisp, I dare say, despite the fact that Lisp is as old as if not older than COBOL). The quality of software ought not to be measured by mere existence of large instances, but rather by how robust, reliable, and maintainable those instances are.

But Ada satisfies most of your requirements.

Was to learn a more or less "modern" FPL by implementing a non-trivial project in one. Were it not for that point, I'd just do it in C++ or Java. ;>

Without static "structural" typing for matrices, you are now forced to evaluate the whole matrix for accessing any sequence of elements of the matrix. This could totally kill your time complexity in some cases.

Without static "structural" typing for matrices, you are now forced to evaluate the whole matrix for accessing any sequence of elements of the matrix.

BS. Give an example.

Look, you realise the difference between strings and parse trees and why it exists?

Same idea here.

Explain.

The reason why we build parse trees instead of just parsing a token stream each damn time is so that element accesses become O(log(N)) instead of O(n) or O(n^2).

(Conceivably, you could do away with the concept of a "parse tree" and just do recursive-descent over a list of tokens that you've read into memory. The reason why nobody writes programs in this fashion is because of the aforementioned complexity problems.)

The same sort of logic applies to datatypes as well as to compiler design. (Datatypes being just small fragments of a parse tree you use for pattern matching.)

You don't need static typing for that though...

Lisp gives you a "parse tree" of lists of lists, also providing O(log N) access to elements. (Assuming the program structure is roughly balanced, and not one long composed function or one function with many args. Your example makes the same assumption).

Goo replaces the list-based program representation with an abstract data type, and provides generic functions for working with it.

Both are dynamically typed.

In a production Common Lisp matrix library, you'd probably use a multidimensional array rather than lists-of-lists. This gives the same time complexity as any other language. Tags are not necessary, beyond what the compiler inserts for strong typing.

I misspoke; of course, the word "static" is not needed.

I'm not impressed with the plugin, as the language-specific preferences page seems to be broken, but the language itself seems impressive enough to warrant a deeper look. The thing I'm wondering about Scala is this: one of the primary benefits of FP is function purity. Knowing that a piece of code has no side effects gives a tremendous advantage when it comes to optimization. However, Scala's free intermixing of FP and OOP pretty much eliminates any purity guarantees, so does that mean that Scala gets the worst of both worlds when it comes to optimization? I've been thinking for quite some time that a "pure" qualifier would be very nice (having first encountered its usefulness in the analysis of exception safety).

I'm not impressed with the plugin, as the language-specific preferences page seems to be broken

It does not work with the latest Eclipse (3.1). On 3.0.2 preferences show ok. But I agree that plugin is far from being worth the hassle (even being hardcore Eclipse user, I ended up using interactive interpreter - REPL).

I assume pure functions are good for optimization because they never need to be reevaluated (in an impure setting a programmer might assume some side effects). I guess that determining the purity of functions/methods can actually easily be done compile time (when designed into a language). But then, again, I guess that one even would like fine-grained control over that, it would make sense to add a pure keyword (even to abuse in settings like: "hey I know it's an impure function, but I don't care when it is evaluated once:).

Yes, exactly. Not only are we talking about things like idempotency optimizations, but also order-of-evaluation optimizations. The reason you want a keyword is because I think that full purity analysis is probably undecidable (but that's just a hunch, I haven't done any formal analysis). Where I know that you absolutely need a keyword is when you cross a library or language boundary. For instance, calling into a DLL/so or something like that. In that case, the compiler must assume the called function is impure, in the absence of knowledge to the contrary. So in a language with purity annotations, either the import declarations could declare purity, or the programmer could call the library functions with a wrapper function that declares purity explicitly.

Of course, merely declaring purity could break the optimizer if it turns out to be a lie. Perhaps compiler writers would decide that the subtle bugs that could result would be too pernicious to allow this level of control. But I think the future of languages is increasing compiler customization, and purity information for functions would aid automated exception safety analysis engines. Also, I think it would be a great way to gain some of the benefits of FP within an imperative setting, which would further enhance the interoperation of the paradigms.

It might not be that hard ;-).

Assuming purity attributes where a function might be assumed to be pure when not calling impure functions I think one could get away with tracing implication graphs. (Which reduces to a 2sat instance and is in P. A linear algorithm exists by Tarjan, I think.)

I think the problem with purity inference is higher order functions. The purity of those depend on whatever its function arguments is pure or not. What you could do is alow you to declare that the argument must be a pure function and that way make the function pure. Or yo could do a whole program analysis. You could probably do something like that for local functions if they isn't returned from there mother functions.

Bad news for you: the idea that purity is going to buy you an optimization advantage is completely theoretical. Look at the actual pure implementations and tell me what the benchmarks are. Haskell is clearly a lot slower than OCaml. Clean is pure and no slouch (actually, it's the only Windows-centric FPL I'm aware of, you should look into it, http://www.cs.ru.nl/~clean/) so we know that purity doesn't *exclude* performance, but the reality is that most of the purist languages are slow.

Why? Because the academics making them don't care about performance. They are concerned with abstraction, type safety, and the ability to reason about programs. Performance is last on their list of priorities, and given that everyone has limited time and energy, they just don't get around to the performance stuff if they really don't care about it that much.

Language front-ends and back-ends are not the same thing. If you dig into the books about compiler construction, you will find that most compilers are roughly the same on the back-end. They all have to output machine code sometime, and they all try to perform the same tricks on the code. So you've got compiler writers who get really jazzed about performance, and ones who don't. It has little to do with the niceties of what purity could buy you in theory.

Also, if you dig deeply into purity, you will find there's a lot of things it *can't* buy you. If you want maximum performance, you need to order your operations sometime, somehow. Try to wrap your head around monads and tell me if you see any opportunities for increased performance going on. I see none. I see a serialization technique.

This stuff about purity letting you do things in parallel is a bunch of hand waving that completely sidesteps the realities of complex software implementations. Yeah, suuuuure you're code's gonna get processed in parallel. I've got 2 bridges to sell ya, ta get ya over the Hudson River faster...

Cheers,
Brandon J. Van Every
(cruise (director (of SeaFunc)
'(Seattle Functional Programmers)))
http://groups.yahoo.com/group/SeaFunc

I think we all know that gcc shares a common back end with all of its front ends, but that does not at all imply that all languages are created equal when it comes to optimizations. Obviously, the back end can only optimize whatever information it has from the code's intermediate form. That includes all the low level optimizations like dead code elimination, forward substitution, expression factoring, const propagation, etc. However, there are still plenty of high-level optimizations that are only available *above* the level of the intermediate code.

I'm not saying that purity is exploited to its fullest. However, I can guarantee you that someone will exploit those optimizations eventually, so we might as well start thinking about them now. I doubt that any compiler on the market will do something as crazy as create lightweight threads to process some pure functions in parallel, but I *would* be surprised if none of them were able to do simple instruction reordering on the basis of purity information. Of course, most compilers infer that information directly from the intermediate code. But perhaps if the back end had more hints, it could be more aggressive about instruction reordering, which is particularly apropos in this age of superscalar architectures and speculative execution. And with chips like the Cell in production, I really don't see why some functions could not literally be called in parallel and scheduled on different physical pipelines. We may not have that today, but I don't see how whining about it is going to prevent it from happening in the future.

If we wait for back ends to catch up to front ends, we will miss an opportunity for free optimizations. But if we take paradigm mixing seriously, we should consider how to make imperative code look more like functional code w.r.t. effects in order to prepare the intermediate representation with more optimization hints.

But optimization is only half of the story. Another skeleton in the closet is exception safety. Everyone wants it, few people have it, and many don't really know how to achieve it. The fact is, the vast majority of code is written as if nothing fails, which becomes quite apparent by what happens when something does. It turns out that purity is a key concept in analyzing exception safety in imperative languages, although I'm not really sure how it interacts with monads. Right now it's essentially impossible to create an exception safety analysis tool for C++ because the language does not preserve information about purity, nor does it allow the programmer to annotate it (except perhaps in the crudest form - const). If a mixed paradigm language like Scala were to support explicit purity annotations, it might actually be feasible to write a tool that automates exception safety analysis.

For those thinking that the exception specifications in Java are enough, you need to try using a few large Java libraries to quickly disabuse yourself of that notion. Not only do exception specifications not really tell you anything about exception safety, they are more of a nuisance than a feature. The best exception idiom I use in Java is to convert caught exceptions into RuntimeException so they propagate C++ style to the most appropriate catch location. Then my methods all have clean exception specifications.

So overall, I think purity (or effect systems, if you prefer) is a fairly worthwhile topic of consideration, regardless of the current state of optimization technology.

We've been thinking about FP for 30 years now. Static Single Assignment form is popular on compiler back-ends nowadays, and SSA is Functional Programming. These things aren't theory problems. They're "who cares" and "who's it worth money to" problems. There's no such thing as "free optimizations," we're not missing anything.

Cheers, Brandon J. Van Every
(cruise (director (of SeaFunc) '(Seattle Functional Programmers)))

Well, optimization definitely depends on economics to get development effort, but there's still a gap between what is theoretically possible and what can be reasonbly implemented. I mean, there's a whole host of whole-program optimizations available to many imperative languages that don't get implemented partly because it would be very expensive and partly because nobody knows exactly how hard it is. And part of the reason nobody knows how hard it is is because nobody sits down and takes a good look at it.

I mean, if you care about optimizations, then why don't you get the source to your favorite FP compiler and do something about it? If you put half the effort into improving something as you do into being pessimistic and cynical, you should have a pretty fast compiler in no time. ;)

I mean, if you care about optimizations, then why don't you get the source to your favorite FP compiler and do something about it?

I am, with Chicken Scheme as base code. And I'm way farther along that road than you are, just asking "what's productive," not really knowing what's out there, and what the implementation problems are.

Cheers, Brandon J. Van Every
(cruise (director (of SeaFunc) '(Seattle Functional Programmers)))

I'm not whining about performance. ;) But if this is some sort of contest, which seems to be the case by your combative attitude in general, then you win. I'm just here to learn a thing or two.

You never asked me what I was working on, you just started telling me what I should be doing, as though I wasn't doing it already. You may pride yourself on not "whining" about performance, but your comments don't indicate much familiarity with either the implementations available or low-level backend issues. Is performance among your pedagogical goals?

Cheers, Brandon J. Van Every
(cruise (director (of SeaFunc) '(Seattle Functional Programmers)))

Ad hominem attacks and pissing contests aren't welcome here.

SSA is still insufficiently pure - no mutable variables, but since when's that the only side-effect? We're also still learning new things about functional programming, something I'm not sure can really be said about imperative programming per se.

And if you dig into it, you'll realize that pure FP is not what computation is really about. State is useful, and all around us in the real world.

Cheers, Brandon J. Van Every
(cruise (director (of SeaFunc) '(Seattle Functional Programmers)))

Sure. Unnecessary state merely gets in the way though. Absent-unless-stated is always easier to deal with than having to assume extra constraints unless you can prove otherwise.

Abnegating state causes some problem domains to contract, and others to expand. It's not "always easier to deal with." in fact, it's not even usually easier to deal with, because so many industrial programming problems have state. "Unless you can prove otherwise" betrays a preference for things that can be formally proven. Others would go with "unless you can easily implement it with state" and skip the proofs.

Cheers, Brandon J. Van Every
(cruise (director (of SeaFunc) '(Seattle Functional Programmers)))

No, others would not. We're talking about optimisations here, code transformations. You don't do them unless they're provably safe, or you run a risk of producing incorrect code. Given that, it is *always* easier if you are told when state is being used, as a number of transformations exist that're only safe in its absence.

I thought we were talking about pure vs. impure application code and compiler optimization architectures. I think we're talking past each other. I agree that people want their code to actually work.

Cheers, Brandon J. Van Every
(cruise (director (of SeaFunc) '(Seattle Functional Programmers)))

Philippa is talking about how all optimizations the compiler performs must be provably correct, i.e. not change the behavior of any legal code. Any difference between observed behavior in the unoptimized code and optimized code is a compiler bug, and compiler bugs are notoriously difficult to track down.

If the compiler knows that the code it's working with is pure, it can prove the correctness of more possible transformations, and hence more optimizations become possible. Alias analysis is one of trickiest problems in compilers for imperative languages; if the code is pure, you know that it's not aliased. Also, pure code can be memoized or lazyfied safely, and you know it won't adversely affect any other code areas. This opens up a lot of large-scale optimizations that can't be done with impure code, because you can't prove whether not evaluating that particular function will result in a difference in observed output.

if the code is pure, you know that it's not aliased.

Is it that you know it's not aliased or that aliasing doesn't matter?

Point taken; it's more correct to say that aliasing doesn't matter. The compiler, of course, is free to share memory locations behind the scenes as long as it doesn't mutate the value, which is the whole point of pureness in this discussion anyway.

Because the academics making them don't care about performance. They are concerned with abstraction, type safety, and the ability to reason about programs. Performance is last on their list of priorities, and given that everyone has limited time and energy, they just don't get around to the performance stuff if they really don't care about it that much.

I don't know if this supports or disputes your claim, but here it is anyway: Results from GHC performance week

Look at the actual pure implementations and tell me what the benchmarks are. Haskell is clearly a lot slower than OCaml.

We've had this discussion before. Part of the performance-problem is the laziness of Haskell as described in the papers cited in that discussion. What is a purely Functional Language proposes the following definition of purity:

A language is purely functional if (i) it includes every simply typed lambda-calclus term and (ii) its call-by-name, call-by-need, and call-by-value implementations are equivalent (modulo divergence a errors)

so laziness is not a requirement for a pure functional language.

Also, if you dig deeply into purity, you will find there's a lot of things it *can't* buy you. If you want maximum performance, you need to order your operations sometime, somehow.

I did not understand this comment. A pure language is most certiainly easier to partially evaluate than say for example C. Partial Evaluation is not a theoretical optimisation.

and everything to do with what gets implemented and optimized on the compiler back-end. Most of the purist crowd simply doesn't care about performance. There are exceptions, and none of them have widespread notoriety.

Cheers, Brandon J. Van Every
(cruise (director (of SeaFunc) '(Seattle Functional Programmers)))

Talking of things getting implemented and optimised, GHC does a pile of neat algebraic optimisations and exposes the mechanism so that coders can add their own for their own datatypes.

Laziness damn well is a big issue for back-end optimisations, and if you did a little reading on the execution models involved you'd realise that (thinking about thunks is rather illuminating). Throw in the fact all the big compilers are targetting C because there's too much need for portability and you've got a big issue whether people care or not.

If you dig into the compiler books you'll rapidly realise *none* of them are taking laziness seriously. That has major ramifications for the back end - although you might find Boquist's PhD thesis illuminating in that regard.

Monads offer possibilities for increased optimisation because they restrict the range of possible side-effects - you get all the purity-related advantages /and/ you can keep the one or two useful effects a given piece of code's using to go fast. Sequencing's a bonus - especially as it can be used to represent hard "do things in this order" sequencing and softer dependencies.

The parallelism stuff I'll give you, the research projects fall through often enough - purity is very much your friend when you play with explicit concurrency though, all the shared mutable data has to be very clearly marked as such and so you can safely stop worrying about synchronisation on it all.

Show me who's actually doing it. Then I might care.

Cheers, Brandon J. Van Every
(cruise (director (of SeaFunc) '(Seattle Functional Programmers)))

You commented on possibilities, not existing implementations. It's a little early to expect them - the first specified language to use monads seriously for anything at all was only seven years ago, and plain monadic IO is considerably less sophisticated than what I just described. In the meantime, monads are still far more than a serialisation technique as a poke around the source of Pugs will quickly demonstrate.

and I agree with you that we won't see any performance out of monads for a long time.

Cheers, Brandon J. Van Every
(cruise (director (of SeaFunc) '(Seattle Functional Programmers)))

I can see some straightforward holes in you assertion. Before I begin, I'd like to point out that there is a formal way of relating an effect type system and a monad type system for the same effect. A relevant example is that it is possible to encode regions using monads. Philip Wadler has a paper on this, and there is also a paper by Greg Morrisett and Matthew Fluet that is on that topic. So monads provide a general framework for reasoning about effects. I can't see how being able to reason about effects will do anything BUT enable more sophisticated analyses and hence optimizations to improve program performance. (ML code can be translated into an internal representation where everything is in an effects monad). So I'd argue that monads improve performance both because of the ease of introducing new primitive effects into a language (I think Oleg has an implementation of the region monad available on his webpage) and also because it provides a wonderful way of constructing incredibly useful combinator libraries such as ParSec that improve ones productive in software construction by a significant amount.

He's talking about having the optimisations in production-usable compilers now, we're not there yet.

I bet you can't find me *1* paper on the use of monads to achieve performance optimizations. I'd definitely like to take a look at such a paper if you've got one. And please, will all posters spare us the indirected chain of reasoning that because you like pure FP, it must by rights provide performance somehow. Stick to what can be demonstrated.

Cheers, Brandon J. Van Every
(cruise (director (of SeaFunc) '(Seattle Functional Programmers)))

I'm way farther along that road than you are

&

And please, will all posters spare us the indirected chain of reasoning that because you like pure FP, it must by rights provide performance somehow.

There's no reason to be as standoffish as you're being; it won't get you any traction here.

I don't know what your own remark was desgined to accomplish. It strikes me as misfeatured. Anyways, SeaFunc was created to avoid this kind of schism. I've yet to see anyone get in a huff over beer.

Cheers, Brandon J. Van Every
(cruise (director (of SeaFunc) '(Seattle Functional Programmers)))

He's a troll and this is what he does - complain or comment on something, argue, be rude, back pedal and when people suss him out complain about FP or language X or whatever not being serious and then leave.

BVE trolled on the OCaml list, in clf, in cls, various other newsgroups and now he's found ltu. I've wasted enough time entertaining this troll in the past so I'm ignoring him. My advice to you do the same.

And as the fellow SeaFunc member who mentioned this site to him, in the context of mentioning how dissappointed I was to see a K5 troll tolerated here, I am (ironically) deeply dissappointed by him taking his stances here. I do not find this welcome at all, Brandon. We may be polite over beers, but I think that's more about the beer than the content of what you're saying...

Or do you think smearing people is acceptable forum behavior? Contrary to popular belief, a troll is not "anything you don't like." It appears you have some issues with my opinions that you have not made me aware of at SeaFunc meetings. I suggest you take them up with me in person... and also consider the appropriateness of your own comments as a co-founder of SeaFunc. It's your group too, you're supposed to be 1/3 of the leadership, so make known whatever you think needs changing.

Cheers, Brandon J. Van Every
(cruise (director (of SeaFunc) '(Seattle Functional Programmers)))

Perhaps what he thinks is unacceptable is the way you come across as an insecure teenager with something to prove to everyone. I certainly don't expect you to agree with everything everyone says, but would it kill you to be a little polite? Also, it seems that most of what you say is negative, which puts you in a tricky position. First of all, proving a negative is a logically difficult task. Second, as anyone who has solved logic puzzles can attest, negative facts are only marginally useful compared to positive ones. So I am (and I suspect many people are) far more interested in the introduction of positive facts than the assertion of negative ones, especially when the negative "facts" turn out to be not so well supported.

Perhaps the reason your cofounder hasn't been open to you in person is because you have a rather combative personality that does not make the possibility of confrontation or disagreement a remotely pleasant one. Need I mention that one can catch more flies with honey than vinegar? I like a good debate as much as the next guy, but I like to think I've grown past the stage of making it mean-spirited. I think everyone would benefit more from your insights if they weren't delivered on the tip of a lance. Just something to consider.

P.S. I find the "Cheers" in your signature rather incongruous with the content of most of your posts. It seems rather disingenuous to me, assuming that you realize how abrasive you come across many times.

but I lost interest in debating my persona a long time ago. Brian's issues with my role in SeaFunc run deep and we've taken them up privately. As for "Cheers," it's my one remaining Anglicanization, nothing to apologise for. Translate it as "Ciao," "Cheerio," "Pip-Pip," "Toodles," or whatever you like.

Cheers, Brandon J. Van Every
(cruise (director (of SeaFunc) '(Seattle Functional Programmers)))

He does this in person, as well, and I don't mind that. I also don't mind him doing it here, if Ehud and associates let it be. But I do object to the SeaFunc tagline being used here in passive support of his stance. As to the "Cheers" observation, a co-worker has commented that this is an often telltale sign of personality issues, which had not explicitly occurred to me, but I am in no position to evaluate this. In any case, that type of behavior seems disengenuous to me as well.

You can use email, etc. Here, if a comment deserves to be ignored, simply ignore it, and let us continue with our lives.

Boquist's PhD thesis uses a monadic language as an intermediate form. Generational GC already interacts nicely with the use of return in monadic code too - if you know a piece of code is pure, you know old data never refers to new.

I've skimmed the Boquist PhD thesis. GRIN, the intermediate language, is untyped. This suggests it'll be in the lab awhile longer. The benchmarks do show signficant performance gains over old Haskell compilers, but they were measured on 140MHz and 300MHz SPARCS. The results can't be assumed to scale to the present day. Boquist doesn't appear to have published additional work. Boquist's old website hasn't been updated since 1999, and Boquist's current website only has a frog.

Cheers, Brandon J. Van Every
(cruise (director (of SeaFunc) '(Seattle Functional Programmers)))

It would be nice if you explained why the results obtained by him are wrong with the computers of today. Are cache misses cheaper? Have the branch prediction gotten so much better that it never misses? Did modern CPU's turn into mind readers?

John Meacham's been doing further work using Boquist's ideas targetting C - I don't believe jhc's up to production quality yet though. His version of Grin is typed.

If you've read what half the optimisations are you'll realise many of them are pretty much guaranteed to still apply today or indeed tomorrow - case hoisting is a perfect example, if you apply it after firstification and inline aggressively enough then with a few iterations a combinator-based parser could turn into something resembling a table-driven parser.

I'll look at Meacham's stuff.

As to future-proofing of optimizations: the performance differences cited in Boquist's paper are pretty startling in some instances. This leads one to suspect that he was competing against