## Most Productive FP Lang?

I realize this isn't really a theory question, and I humbly hope the moderators tolerate the thread anyway. However, this crowd probably knows more about FPLs than most, and hopefully this thread will be a useful resource to other people looking to get into an FPL. For my purposes, "productive" includes the following requirements, roughly in order of importance:

• Free - I realize that many FPLs have free implementations, but it would be ideal if the entire toolchain was free, or at least a reasonably significant portion of it; in this case I'm more interested in "free beer" than "free speech"
• Windows implementation - yes, I know Windows is evil, but alternative x86 GUIs just aren't as mature, which leads to the next requirement:
• GUI support - the application I have in mind is a client/server app, and I want the client to have a nice interface; a GUI builder would be best, but a decent GUI API is good enough
• Library support - I don't want a stripped-down language that is mostly useful for solving academic mathematical curiosities; I don't expect a library set as rich as Java or C++, but I want something reasonably rich; if the language supports linking to C/C++ libs, it should do so fairly painlessly
• IDE - the nicer the IDE, the better; an Eclipse plugin would be ideal, but I don't expect anything more fancy than an emacs mode
• OOP - my application will do a lot of modelling, so I suspect that OOP support will be very helpful (though I will make a best attempt to use the language idiomatically)

A rationale along with a given suggestion would be most welcome. Thanks.

## Comment viewing options

### Erlang and J

I've been through the whole cycle of looking at FP languages for everyday work, with the requirement that an implementation must have more than just tacked-on support for Windows. This is my own personal experience, so commenters please take it easy :)

I ended up getting along the best with Erlang and J. Erlang fails in a couple of your categories (OOP, GUI, IDE), but I've found it to be pleasant and useful. J is a descendant of APL that gets surprisingly little discussion in the FP community, even though it's the closest programming language to what Backus proposed in his famous Turing Award lecture. It has a beautiful little IDE, includes a GUI builder, and even has built-in OpenGL support. Very nice. The downside is that it's free to use, but not free software. It hits all your requirements otherwise.

I should mention that I used to be very concerned about performance and benchmarks and having a compiler that generates the fastest possible code. Obviously I gave that up, as both languages I'm recommending are interpreted.

### Pretty tall order

You're asking for quite a lot. IDEs, GUIs, and large libraries all take significant programming investment, and you want that to be free. Because the FP community is relatively small, that's an awful strain on resources.

That said, you might want to check out Ocaml. The compiler is certainly free, as is almost all of the toolchain. I can't speak to the Windows implementation - I've only used it on Linux - but I know that one exists, including a native-code compiler. There are GUI bindings, along with other libraries. And you can use Python extensions and CPAN with it, plus the obvious C FFI. You won't get a fancy IDE, but it does have a good Emacs mode. And there's a very extensive object system, though it's likely unlike anything you've ever seen before.

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.

Most of the other major FPLs don't really seem to be what you want. Haskell has a Windows version that works fairly well, but you can forget about OOP, and I'm not sure how well the GUI libraries work on Windows. Lisp is either "free" or "on Windows", but not both (okay, okay, there's CLisp, but as I understand it that's much easier to use on *nix). And while Lisp GUIs are very advanced programatically, they don't use standard widgets and so often look clunky to users. Erlang is made for massively concurrent systems; I'm not sure whether it has a GUI system or not, but if it does it's probably not what you want. Dylan might be an interesting choice, and the Windows IDE is quite nice, but it was a little buggy last time I tried it. And the Dylan community is almost moribund, so you'd have a time finding libraries for it.

### OCaml and Eclipse

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

There is apparently an alpha-level OCaml plugin for Eclipse.

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.

### EclipseFP

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

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

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

### Not fair.

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

### Really? Functional languages

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

### Yep

...being in disguise an adaptor between a continuation of sum type and a product of continuations.

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

### Whoops!

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

;-P

### Heh

I really didn't mean to be obscure, either clearly or not. Let's see if I can decypher what I meant.

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

### Meritocracy, Gerontocracy, Technocracy or Kleptocracy?

Well, thanks for clearing that up.

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

### It's a forum, after all

Well, thanks for clearing that up.
No problem, just be advised that I do not program in any FPL, so you should take my comment with a huge grain of salt.

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.

### Pattern Matching

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.

### Exactly

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

### Atriplex

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?

### It depends

Btw, did you check the boolean logic truth table of your expression?
In which logic? ;-)

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.

### That depends.

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

### Rooter: Methodology for the Typical Unification of Access Points

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.

### OK.

You say:

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.
All three co-exist in a fairly orthogonal fashion w.r.t each other.

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

### "***, 100 Âµg, i.m."

[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.
All three co-exist in a fairly orthogonal fashion w.r.t each other.

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.

### This is a fallacy.

Being computable does not mean being equivalently reducible; while we can mathematically determine limits on which classes of functions are computable, this tells us nothing about time/space complexity, safety, etc.

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.

### Scheme macros.

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.

### Erlang UI

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

### FP without closures

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.

### F#

F# is a functional language largely based on OCaml and implemented on the .NET framework. It has its own libraries which give a degree of compatibility with OCaml but you also get access to the .NET framework libraries which are huge and pretty easy to use. It also a plug in for Visual Studio 2003 and 2005 this gives automatic syntax checking and will show tool tips of the inferred types.

Thereâ€™s even scope for doing youâ€™re GUI in C# and using the graphical designer then calling your functions to populate this GUI.

### Am I mistaken...

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

### F# may be free...

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

### The whole .NET Framework SDK is free

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'

### Haven' t you already compensated them

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

### Maybe so...

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

### The Usual Suspects

Let's just trot out the usual suspects:

• PLT Scheme supports everything you desire. And, yes, it does have pattern matching (I find it a bit strange to suggest that a language with macros wouldn't support pattern matching). There is a Scheme plugin for Eclipse (SchemeScript?), though I haven't used it.
• O'Caml, already mentioned, meets the bill. Getting it to work on Windows was a bit of an arse last time I tried (had to download nasm IIRC) but it works.
• Haven't tried Haskell on Windows, so can't comment.
• The almost-functional languages like Python and Ruby might meet your needs.

### VB! Huh?

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.

### Who's Shout Is It?

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

### Is there VB without VS?

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... ### free as in choice 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. ### Scheme Eclipse plugin Shameless plug: the SchemeScript plugin is located here. ### The Q equational term rewriting language (There are several languages called Q; this one is at http://q-lang.sourceforge.net.) Q provides general term rewriting rather than specifically lambda-calculus-based rewriting. It has no a priori distinction between constructors and defined function symbols, and argument patterns are not restricted to constructor terms. It is bottom-up and eager by default, but one can declare particular functions/constructors as lazy. It is dynamically typed. Q is free as in speech; it runs on Windows; it provides GUI support via Tk (GTK+ implementation in progress); there is an Emacs mode; Q provides object types with single inheritance, including enumerations. The core supports the following libraries: Posix (including threads), curl, OpenDX, ggi, ImageMagick, Octave, ODBC, Swig, Tk, libxml2, libxslt. Available add-ons include a combinatorial graph package. There is also an extensive collection of multimedia modules: PortAudio, Faust, MidiShare, OpenAL, OpenGL, OSC, SuperCollider3, and Xine. The implementation is mature at Q 6.2 presently. Performance is comparable to Clisp or Hugs. ### Scala Scala might be what you are looking for. It is freely available under BSD licence. It targets both the Java and .NET (via J#) virtual machine so running it on windows with extensive GUI and library support is possible. There is an eclipse plug-in. It is a multi-paradigm language with both fp and oop features. ### Nice language! Looks really promising. ### Scala isn't Nice Scala isn't Nice ### Summary Thanks for all the input. Here is my understanding and comments on the various suggestions: Erlang - May be a nice language, but probably fails too many of my requirements for this project J - Interesting looking language, but tutorials seemed to be very numerics-heavy. Intrinsic plotting functionality very cool, but not really relevant to my project. The fact that arrays are the fundamental data type strongly implies the numerics-oriented focus of J. Great for scientists needing modeling/visualization, not so great for my app. OCaml - Seems to be one of the more popular and established FPs (being of the ML family). 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. I like the interactive toplevel and the native Graphics module. Great for quick-n-dirty prototyping. The Eclipse plugin is less than stellar, so I will probably investigate further with the "native" interface, which has the advantage of being interactive. Python - Didn't check this out, because my impression is that it isn't a very pure FP, which is part of the point of this exercise (though unstated). Dylan - I'd prefer to stick with something more mainstream and having reliable and ongoing user/developer support. Scheme/Lisp - After thinking about it, I realized that I forgot to mention that I prefer statically typed languages. My experience with Lisp was that I was always uncomfortable with the type safety of my programs. F# - Probably my last choice, if all others fail. The main reason being that getting the nice IDE basically requires getting the latest VS, which is basically not going to happen unless M$ throws a free license at me (not that I can't afford it; just that I don't want to spend money on tools for a personal project with no intended revenue to pay for it).

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

VB - Fails the free test on all meaningful levels. In addition, VB is horribly broken in some stupid ways. For instance, property names can hide intrinsic functions, rendering those functions completely inaccessible. Imagine how overjoyed I was to discover that some library author had defined a property called Left, rendering the builtin unusable. And as you can imagine, the error message for this condition was less than illuminating. I think we all know that VB continues to enjoy significant development only because it's Bill's personal baby.

Q - Looks interesting, but seems to be numerics-focused given its history. Also, it's dynamically typed.

Scala - Looks very promising. I like the integration with Java, which was very smart on the part of the developers. I may be able to use Java with Scala the way people used to use VB with C++.

Haskell - I may learn this just because of its extreme FP purity. Unfortunately, I don't have any projects for which Haskell sounds like an obvious first choice.

Conclusion
Given the requirements of my project, I think I will explore OCaml and Scala in some more depth. Thanks for all the suggestions!

### Indeed it Does!

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.

### re: summary

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

### Emacs + Tuareg mode is the best Ocaml IDE on windows

Forget the alpha plugin for Eclipse.

http://www-rocq.inria.fr/~acohen/tuareg/

Which of course runs on windows.

### dynamic typing is a red herring

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.

### Or maybe...

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.

### Like I said :)

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.

### "Static" vs. "Dynamic" Typing

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.

### not a general property

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

### Abstract data types don't depend on static checks

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.

### Ah, yes...

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

### The point of the exercise...

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

### You forgot the real problem.

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.

### Duh...

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.

### Mm

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

Same idea here.

Explain.

### Well,

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

### Why static structural typing?

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.

### You're right.

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

Oz is largely a functional PL (it supports other interesting paradigms as well), it's got decent (and free) tools, and it's available on numerous platforms.

The main caveat (as far as you are concerned) is that it is dynamically typed.

If you want a statically-typed functional language with type inference (and other things like GC) that is sufficiently widely used and supported to have a decent set of tools; you're probably looking at either Scala, Haskell, or one of the ML family--either Standard ML or O'Caml. (F# is basically Caml on .NET). If you are new to the functional paradigm and consider "coming up to speed" on a language more important than learning a new way of doing things, I'd lean towards the ML family--it's strict semantics will be much closer to what your used to, whereas the lazy semantics of Haskell can be surprising to newcomers. Scala is much younger than the either Haskell or Java; and I know little about it. (It looks interesting, though!)

All of Python, Ruby, Lisp, Scheme, Dylan, and Oz are dynamically typed. VB is too, though its type system is rather crippled.

### Python, Ruby are not FP

I can't think of any definition of FP which causes Python or Ruby to be FP. To use one definition: if you expect FP languages to have something to do with the Lambda Calculus, then clearly they don't, and thus aren't. Moreover, I never hear of anyone in FP communities claiming that Python or Ruby are FP languages. They might be of *comparative interest* to people in those communities, and they might borrow some FP language features, but they are not FP languages.

### FP on Eclipse

I've been playing the "better Windows language" game for over 2 years now, and the "better FP Windows language" game for over 1 year. It has driven me nuts. The problem is overconstrained; sacrifices have to be made somewhere. I'm not interested in the same problems you are, I'm a 3D graphics / game AI / assembly coder / learning how to write compilers kinda guy. You seem to have a more "mainstream" client-server GUI coding interest, and so your life should be easier than mine, but I suspect not that much easier.

You don't want VS, and I sympathize. But really, Eclipse is the only thing that's free, as nice as VS, and commercially viable. Emacs and Vim aren't nice by Windows / Mac "ease of use" standards. You'll probably notice the huge Unix bias in FP communities; most of these guys keep using clunky Emacs and don't care what Windows users like.

A few have "gone the other way" and made Eclipse plugins. However, few of the plugins for FP languages are full-featured. I want to say 'none' but I haven't tried them all, so maybe there's a diamond in the rough. The reality is, FP Eclipse programming means you're going to be putting up with underpowered tools. Or else you'll have to hack them yourself, in Java, until they work better. Really that's the only way the situation can ever improve.

I'm currently trying Chicken Scheme and the Schemeway Eclipse plugin. My excuse is that some guy wants me to work on his Alias Maya 3D Eclipse project, and it should be worth money someday. I doubt I'd get my hands dirty with Java just for funzies, it's too boring.

Anyways, run through the list of Eclipse language plugins and pick something. The list is awfully short, the FP list is even shorter still.

### Scala

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

### OT: Scala plugin

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

### Seems like a good idea

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 w

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.

### Implication Graphs

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 puri

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.

### Purity != optimization

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

### Half empty?

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.

### WTF is 'eventually' ?

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

### Economics

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 am, with Chicken Scheme

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

### At least...

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 p

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.

### There's plenty of imperative compiler scheduling research

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 merel

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.

### It's not that simple a priori

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 t

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.

### Safety?

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

### Safety is necessary for optimization

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.

### Aliasing

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 correc

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.

### GHC performance

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

### Performance, once again.

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.

### It has little to do with laziness or partial evaluations

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 imp

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

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.

### Monad optimization sounds like theory to me

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 possibilitie

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.

### I've commented on realities

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 straightforwar

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

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

### Moreover, it's not even in the lab!

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

### Don't be rude.

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.

### Both comments were fully deserved.

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

### I agree

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

### Careful what you agree to

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

### Well...

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.

### No it wouldn't kill me to be more polite

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

### Yes, that's my stance

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.

### None of this is appropriate to LtU

I can tolerate a few OT posts, and things that seem like trolling, but this personal attack, even if well founded, isn't for LtU.

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 m

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.

### Boquist's GRIN is untyped

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

### Sparc architecture.

The 300 Mhz Sparcs he measured on are pretty much the same as the Sparcs of today architecture wise.

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 fur

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.

### Beware of caches and unoptimized competitors

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 completely unoptimized implementations, on HW with pronounced caching problems. I can't be sure of that, and I'm not ever going to be sure of that, because I'm not going to rustle up old SPARCS to to find out. I also wouldn't claim to have treated Boquist's paper with any fairness, I've only skimmed it. But generally, one has to be careful not to simply shoot fish in a barrel. A conservative response is "gee I'd like to see benchmarks on modern machines, against current implementations."

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

### I'm pretty sure it'll outdo G

I'm pretty sure it'll outdo GHC by some margin. There aren't really any fully-native implementations in serious use on x86, everybody goes via C.

### Why?

.. performance differences cited in Boquist's paper are pretty startling in some instances. This leads one to suspect that he was competing against completely unoptimized implementations, on HW with pronounced caching problems.

Did you actually read what the problems with laziness are? Why do you think it only occurs on a Sparc? In what way has computer architecture changed compared to the 300 Mhz Ultra II he was performing his measurements on? You repeatedly claim his results are useless because they are old. You have not once given an explaination of what has changed, in hardware or software, that makes his results invalid.

As I stated above, I have not treated Boquist's paper with any fairness and have only skimmed it. I thought I had answered your other questions previously, that both computers and competing Haskell implementations have changed since then, but I will amplify.

Back in the day, meaning 1997, we had an oldfangled 300MHz Alpha and a newfangled 533MHz Alpha in our lab at DEC. Guess which one was faster? The 300MHz, because it had a proper cache and proper controller for it. Some genius at DEC had come up with this "value line" of products, where the cache was supposed to be unnecessary for certain kinds of applications. Which ones those were, escapes me now. They certainly weren't our OpenGL device drivers! The performance sucked so bad that we nicknamed this clunker "The Yugo" and put a picture of said vehicle on it as a screensaver.

Don't ever assume that computer architectures are unchanging or irrelevant. They change within the same product line in a given model year!

The SGI guys used to rag on us that if we had spent half as much time working on our cache controllers as we had on our CPU, we would have fared a lot better in the marketplace. Probably not true, as Wintel marketing and production strategies are what killed SGI and absorbed DEC. DEC was a fine engineering company but couldn't market its way out of a paper bag.

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

### If you haven't read the paper (but only skimmed it)

then you're on very shaky ground to challenge its results.

<rant>

"I haven't read the paper myself, but until someone demonstrates to me to my satisfaction that its methodology is foolproof and future-proof, I'm simply going to disregard its conclusions as unsupported" is a cheap, pseudo-scientific cop-out. If you have any real criticism of the paper, feel free to address them here. But I can assure you that computer architecture hasn't changed sufficiently much in the past ten years, to invalidate his results.

Repeating the experiments on modern hardware might be interesting. But absent a firm theory as to why the results aren't valid on a modern machine, you're just slinging FUD. Saying "hardware is different" without explaining why it's different, and how that might have an affect, has no significance whatsoever.

</rant>

### Granted, but

everyone who's spent time with real systems knows what can happen, both in benchmarking and in academic research. Also, you paint my response to the paper as far more extreme than it was. I merely advised caution in assuming the results scale.

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

### Scaling results.

Read Ennals thesis then - dated July 2, 2004. For some strange reason he tries to tackle similar problems with a different approach.

### Is so!

MLj and SML.NET have an intermediate language that is a variant of the computational metalanguage, with multiple monads for tracking effect information. This is then used to enable optimizing transformations.

See the papers from ICFP98, HOOTS99, APPSEM00 and PAT05 available from http://research.microsoft.com/~nick/publications.htm

There's certainly *loads* more to be done in this area, both theoretical and practical, but there *is* more than one paper on the subject and a couple of implementations.

### Glad to hear it, I figured th

Glad to hear it, I figured there was probably more from the ML side of things that I hadn't heard about.

### Bookmarked for perusal. Thanks

We seem to all agree that it's "early days" for this stuff, so hopefully, people can agree that pure FP, monads, etc. aren't guaranteeing anything in the performance dept. Rather, it's an area of nascent research. That's been my point all along, and the source of my irritability. I don't like seeing claims for FP that can't much be substantiated yet. 30 years of making claims hasn't gotten FP terribly far into the mainstream, and credibility is lost every time unrealistic claims are made. One can compare the overpromises of the AI industry in the 80's, or the VR industry in the 90's.

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

### Most of this stuff guarantees

Most of this stuff guarantees something if you do the work, in a way that AI and VR couldn't possibly have. We're dealing with hard mathematics here, not a pile of modelling hopes, and every time somebody here says "there's a possible optimisation here" they're talking about something that can be done /any/ time the relevant preconditions're provable. It's all about managing that, and we already know monads provide a better framework for proving such things than imperative code does.

### In theory, practice doesn't matter

In practice, practice matters. Or how does that saying go, exactly? Anyways, given the 30 year history of FP, I wouldn't trivialize the problems of bringing compiler technology into widespread industrial use, or claim it's incomparable to the problems that AI and VR people have faced. Hard mathematics is a pile of modeling hopes. That's what you're managing.

But enough of this. I think we understand each other.

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

### Unfortunately...

It's not quite that simple. Purity is relative. ;) It depends heavily on scoping rules. For instance, modifying local variables does not automatically make a function impure. However, "local variables" aren't always very local, as we all know. The following function is pure, even though it performs operations that are impure in other contexts:
int foo(int n)
{
int x = 0;
while (n-- > 0) x += n;
return x;
}

So even though we modify both x and n, foo() itself is pure, because n and x are both locals (when n is a copy) and the effects of their modification do not escape the function. Now consider this case:
struct bar
{
static int count;
bar() { ++count; }
int baz(int x) pure { return 3 * x; }
};
int bar::count = 0;

int foo(int n)
{
bar b;
return b.baz(n);
}


Now here I've even annotated the member function to highlight the fact that it's obviously pure. Without knowing how b is constructed, just looking at foo(), you would probably assume that it's a pure function. However, as you can see, it's quite impure. The problem is that the impurity of bar::bar() is non-local. But the only way you can know that is by analyzing the scope of everything modified in bar::bar().

Even so, this analysis may yet be tractable. Perhaps there would be different levels of impurity - {pure, dirty, filthy}. So a dirty operation modifies state, but only the state of its arguments, whereas a filthy operation also modifies state outside the scope of its arguments. Dirty operations on local variables do not violate purity, but filthy operations always do.

Unfortunately, that might not be enough to save us. Consider generics. What is the purity of the following:

template <typename T>
void foo(T x)
{
x.bar();
}

Not only do we not know the purity of bar(), even if the body of foo() were empty, we would still not know its purity! That's because in C++, x would be copied, and we don't know that the copy c'tor is pure, or at least merely dirty. If it's filthy, then so is foo(). Furthermore, different instances of T may introduce different levels of purity. So you need to carry along purity information for each instantiation of foo(), which seems to make things much more complicated (though perhaps not yet intractable).

### Effect systems

Indeed. There has been quite some research on so-called "effect systems" in the past 15 years. They extend type systems with information to keep track of effects like the ones you mention.

While they are certainly tractable, their adoptance in practice has been hindered by the fact that they quickly turn into highly bureaucratic beasts. For example, to address your last example you already need a notion of effect polymorphism (obviously, there is no hope to ever get anything like that working in a type system as broken as that of C++).

Btw, Wadler showed that, in principal, effect systems are equivalent to typing with monads (although you needed very complicated monad types to capture everything average effect systems do).

### I think the idea is that you

I think the idea is that you can garantee the purity of some functions, mostly those written in functional style. Not that you can find each and every function application that is side effects free.

### Interactive REPL?

I use Lisp in my daily work, but I've been thinking about branching out a little too.

I've been considering learning OCaml, Haskell or Clean. OCaml seems the most Lispish, so I may pass and move more outside my comfort zone. I'm most impressed with Clean right now, though I really haven't done enough research to be able to rightfully judge one from the other.

However, one thing that has been worrying me is that Haskell and Clean both seem to be Edit-Compile-Load-Run-Debug type languages. I don't need that type of pain from something I'm spending my free time on. I want to be challenged as a programmer, but not _that_ way.

### GHC has 'ghci', an interactiv

GHC has 'ghci', an interactive Haskell shell. Works like any other REPL. I'd imagine Hugs and other Haskell interpreters have something similar.

I have no idea about Clean.

### ...except that, IIRC, you can

...except that, IIRC, you can't enter function definitions in the REPL, you have to edit them in a separate file and reload - very annoying! does anyone know why this is the case?

### It is because you have not bo

It is because you have not bothered to find out how to enter functions at the repl.

### You can

You can enter definitions (use the let keyword - the toplevel is parsed as a do body). You cannot enter type definitions, though.

### hs-plugins

hs-plugins has a neat incremental compiler that's a lot like hi from hmake. I think this will let you put in type definitions as well. If not, it could easily be extended to do so.

--Shae Erisson - ScannedInAvian.com

### GHCi under windows isn't pretty

GHC has 'ghci', an interactive Haskell shell. Works like any other REPL. I'd imagine Hugs and other Haskell interpreters have something similar.

Hugs under Windows is nice. Someone spent the time to make a usable toplevel for it. GHCi is a raw command-line app (or was the last time I checked it), so you're stuck in one of those horrible pseudo-terminal windows. I'm not against the command line by any means, but if you want Windows users then you need to write a simple little GUI front-end to escape the limitations of Microsoft's horrible command windows. Erlang does this. OCaml has a great front-end on the Mac, too. This would be a big win for GHCi.

### If you're using ghci in Emacs

If you're using ghci in Emacs' Haskell-mode, you can just hit C-c C-r to reload the file you're working in. And you have a REPL in the other window/frame. I find this works quite well for programs early in development. It doesn't work as well as Lisp-like systems once you've got a running program with a UI---but then, given that UI has already been declared, it really couldn't.

Have you considered Bigloo Scheme? Bigloo can compile Scheme to C (for UNIX only, I understand), JVM (Java) bytecodes and .NET bytecodes. It can also link to C (only UNIX?), Java and C#, giving you access to two reasonably mature and extensive sets of libraries.

It runs on Windows.

Not sure about Eclipse, but I'm sure there are several Emacs modes for Scheme.

It has an object system.

I've not used Bigloo, but it seems to me to satisfy the above requirements.

It's dynamically typed. ;> For better or worse, my brain is now wired to think in types, and I don't see a compelling reason to rewire it.

### Bigloo can be type annotated

Bigloo also used to share a codebase with OCaml at INRIA.

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

### Dynamically typed still involves types!

You still create types, values still have types. It's not like you're working with raw pointers for everything.

### Yes, yes

I know that dynamically typed languages still have types. All I meant is that I'm used to naming the types explicitly all the time, which you can't do at all in Scheme (without inventing a static type system within it). Yes, I know that static type inference avoids naming types as well, but that isn't the point either.

### Type annotations

Bigloo has type annotations. Scheme identifiers of the form name::type are considered typed variables, and the compiler provides type inference accordingly. Useful for self-documentation, which I've found to be the primary use for static typing anyway.

IIRC there were some gotchas, though. Type declarations are ignored entirely by the interpreter, which isn't a huge problem. But what really killed it for me was that define-struct and define-record don't create types that can be used in type declarations, and if you want to use object types you have to use Bigloo's object system, rather than one of the myriad other Scheme object systems like TinyClos. I guess both of these are reasonable restrictions (though I don't understand why you can't use records), but I wasn't terribly fond of Bigloo's object system, and really didn't want to use it for all the user-defined types in my program.

### Bigloo is its own world

I ran around with Bigloo for awhile. On the positive side, Manuel Serrano is extremely responsive to bugfixes. The problem with Bigloo is it's like a lot of Schemes: you're not doing some standard version, you're doing a very specific implementation with its own major quirks. You have to think of yourself as doing Bigloo rather than doing Scheme. For instance, call/cc is not enabled by default.

I moved on to Chicken Scheme because (1) it has a BSD rather than GPL license, so I can use it as a basis for my own language someday, (2) it's almost as fast as Bigloo, (3) the C++ and SWIG support may be useful, (4) it has a slightly larger user community.

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

### F#, again

"F# - Probably my last choice, if all others fail. The main reason being that getting the nice IDE basically requires getting the latest VS ..."

If you don't want to use MS products for religious reasons, feel free to ignore my post; Otherwise: AFAIK VS Express should be enough for creating and debugging F# code, and it is (still) free (as in free beer): http://lab.msdn.microsoft.com/express/vcsharp

And - IMHO - even if you restrict yourself to free editors and free (think beer, again) tools for the .NET Framework, IDE support for F# is quite comparable to that of most other FP languages I know...

### But do you really want .NET?

It has been demonstrated that all the working components for an F# .NET setup can be obtained for free, as in "free beer." However, we all know that writing to .NET is very much a committment to Microsoft, and not anything like "free speech." Sure there's Mono and Portable.NET, but MS can yank that legal rug at any time. The choice is personal, or ideological, or even practical (for example, fear of MS business models and churn, .NET failing to address certain problem domains). I'm just saying that if the original poster objects to .NET as a target, there's plenty of legitimate reasons for those objections. On the other hand, if he actually likes .NET, then sure, see what F# can do.

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

### But do you really want Windows?

I already noted this early on but I guess no one took notice.

Original post:

...

• Windows implementation - yes, I know Windows is evil, but alternative x86 GUIs just aren't as mature, which leads to the next requirement:
• GUI support - the application I have in mind is a client/server app, and I want the client to have a nice interface; a GUI builder would be best, but a decent GUI API is good enough

...

If you're already using Windows (req 2) and a GUI on Windows (req 3) then to me, the only natural path down this evil Microsoft road is F#. Using .NET libraries and the conciseness of F#, you can have a working windows application that connects to a database with databound grids in about 1 page of code. You get Windows, Easy GUI, statically typed functional language from the ML family, a choice of 2 good IDEs (Emacs in tuareg mode, or VS 2005 (\$) with F# add-in, and you get OOP all in one clean shot.

If you want to avoid Microsoft why don't you avoid it altogether? Use Ocaml with GTK bindings, FreeBSD/Linux, and use inspiration from MLDonkey to create your client/server GUI application. Emacs + tuareg is still available, and so is efuns.

Can the original poster explain why he's anti-Microsoft development tools, yet pro-Microsoft operating system?

### Sometimes your market dictates what OS you use.

I can't speak for the OP, but for instance, I want to make commercial games. The big markets are Windows and the consoles. MacOS is barely viable; Linux isn't.

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