Functional Language Summary

I've been hearing a lot about functional programming lately (and the circle of life continues); I found Functional Programming For The Rest of Us to be a nice summary. Here's what I got from it:

Atoms of FP:

• All "variables" are immutable, often called "symbols"
• Program state is kept in functions (specifically, arguments passed on the stack to functions), not variables
• Functions are first class citizens, i.e. functions can be passed as arguments
• "currying" is a convenience syntax for adapting a function to an alternate function signature
• "closures" are functions that are allowed mutable state and access to state outside their lexical scope to bridge functional and non-functional languages

Implications:

• Functions cannot cause side effects ("variables" are immutable)
• FP is great for unit testing (only have to test outputs against inputs -- don't have to test side effects)
• FP is great for debugging (no need to worry about external state affecting function results -- results are only based on the input)
• No need for multi-threaded locks, as state is immutable
• This makes functional programs automatically parallelizeable
• Can hot swap new function definitions w/o effecting existing instances
• Don't need to evaluate a function 'til the results are needed

FP sounds great! Why do we mess around w/ anything else?!?

I read that a few weeks back and it really piqued my interest.

After discussion about this with a few others on CodeProject.com, the general consensus was that performance is a problem with functional languages due to all the stack copying. This seems to be confirmed in the few functional languages I've looked at. Consider Ericsson's new built-for-reliability-and-tolerance functional language, Erlang. Erlang is great for reliability (another nice thing about functional languages is that you can unit test and mathematically reason about every function, since there's no "variables" being shared). While Erlang is great for reliability, it is not meant for performance; it runs so slowly that they recommend writing a seperate C++ app for anything that needs any kind of reasonable performance.

A few Haskell programmers chimed in on the performance problem, stating it certainly exists for functional languages.

The article mentions that functional language compilers can optimize away these things, but I'm not so sure given all the examples I've looked at.

Now, what's interesting to me is is that C# continues to integrate functional features. Lambda expressions (v3), anonymous methods, even delegates are functional in nature. And things like "yield return" generate state machines where the yielded results only get executed if you try to iterate over each one, just as it is with functional languages.

I think this is one area where C# has a big, big edge over Java. Java has no concept of delegates even; you can't pass a function around as a variable like you can in C#. No anonymous methods, lambda expressions, state machines, and so on. C# has a huge leg-up here and continues to grow as more functional language techniques are added to the C# language.

To echo something that Judah said, some of the performance "issues" can be mitigated by a really smart environment. While I don't mean to trivialize performance questions, I've found that for *most* software the performance hit of a functional is more than offset by the other benefits. For a great intro, check out the Berkeley webcast for CS 61A. It's interesting to see how, once you support lambda, you can do pretty much anything from invent new control structures to create object orientation. Once of the things I really like about Ruby for instance is unless, which behaves like if (!expression). Even if Ruby didn't have unless, since it has lambdas, it would be one of the first things I'd have written:

def unless(predicate)
  if !predicate && block_given?
    yield
  end
end

unless child.past_bedtime?
  child.watch_tv
end

"FP sounds great! Why do we mess around w/ anything else?!?"

I think FP gets fuzzy around the edges. The pure functional style is great as long as you don't need to get data into or out of your system. What's the pure functional equivalent of Console.Read/Console.Write?

I find ythe IO subsystem to be an interesting point of comparison for functional languages.

Most FP systems I've used (StandardML, PolyML) dont do debugging, because you are expected to prove things work instead. ouch.

However, it is good to know, just like a bit of Prolog is handy too. Once you know functional programming, all the later C++ standard libs make sense as an attempt to retrofit FP and curried functions onto a language that wasnt designed for it.

Take a look at the John Backus 1977 ACM Turing Award lecture. Google for: "backus ACM award lecture". It was printed in Communications of the ACM: "John W. Backus: Can Programming Be Liberated From the von Neumann Style? A Functional Style and its Algebra of Programs. Commun. ACM 21(8): 613-641(1978)". A PDF file is available from ACM (and out in the open on web too).

"Why do we mess around w/ anything else?!?"

The classic answer to this is: while functional programming makes certain things tasks that would be a nightmare in procedural languages dead easy, the converse is also true - certain things that are dead easy in procedural code are a nightmare in functional languages.

It's useful to have both kinds of tool in your toolbox.

And there's the killer feature: sometimes side effects are the whole point. When I deposit money with my bank, it matters to me that this has a persistent side effect on my balance.

By the way, your definition of 'closure' looks wrong to me. I've always known closure to mean a function plus its lexical environment. (Yes, the lexical environment extends beyond the scope of the function body itself - that part is important. But mutability is not a defining feature. And these things really aren't about bridging between functional and non-functional behaviour - you can use closures in a purely functional world, and that's where the idea originated.)

Note that even in a pure functional world with its immutable variables, the lexical environment can be different in different contexts. Consider this:

static Func[int, int] MakeAdder(int delta) { return delegate(int i) { return i + delta; } }

This returns a closure - a function (in this case an anonymous method) plus the lexical environment. In practice the closure only captures those parts of the lexical environment that the function actually uses - the 'delta' free variable in this case. Of course the value of 'delta' will depend on what value is bound to that free variable by whoever uses the MakeAdder function.

Note that I'm using a pure functional programming style here - no side effects. The value of the 'delta' variable is not mutated. It happens to take on different values in different contexts, but that's true of the arguments of any function even in a pure functional system.

(In other words, just because variables are immutable doesn't mean they always have the same value. It just means for any particular invocation of their containing scope, they have a fixed value.)

So closures don't have to be about bridging the gap between functional and non-functional languages, and nor do they have to be about mutable state. Some languages, such as C#, allow variables in the captured scope to be mutable. Some don't. This is an optional feature of closures. (Although some consider mutability to be a defining non-feature, and therefore consider C# anon methods to be something different from closures. Opinion is divided on the matter: some thing mutability is optional, some thing closures by definition don't support mutability. But I think you're in a minority of one by declaring that mutability is a feature so central to the essence of a closure that it's the first feature you list!)

So I don't think you quite nailed that one.

There *is* a framework for bridging the gap between the pure functional world and the side-effectful real world, enabling functional code to do things like IO. The mechanism used here is called, somewhat confusingly for those of us in the world of Microsoft tools, a 'monad'. And incidentally, monad theory (which in turn is part of category theory, a branch of discrete mathematics) is the theoretical basis that underpins the design of a lot of LINQ.

I "got" FP when I started using Flex's powerful databinding mechanisms.

Because event code can get so verbose and interconnected I stopped using events and started using only direct databinding to functions.

The code just started to shrink and become more readable, it was amazing. I think (hope) Avalon also has these smart binding mechanisms.

SMaine is right about interfacing with IO of course. Here languages such as scheme introduce a limited form of normal order evaluation to deal with streams. Ian hits it on the head that we need both. In the end, what I really want is exactly that: a dynamic language with a *nice*, moldable syntax that allows me to select the right paradigm (procedural, OO, functional, event-driven) for the task at hand, being equally comfortable to work with in each of those scenarios. Oh yeah and then I want smart guys like you to worry about making a debugger and making it fast enough. ;)

You might want to have a look at Clean:
http://www.cs.ru.nl/~clean/

It's a "state-of-the-art pure and lazy functional programming language" with a "fast compiler, the worlds one-and-only programming environment entirely written in a pure functional language" and a lot of libraries including I/O, TCP/IP and even a game library.

All of that sounds good.

Anyone know if there's a way to do things like disk i/o *without* breaking any of the tenets that Chris listed, or is one required to write functions with side-effects?