Functional Programming

In my quest to incorporate more declarative programming techniques (especially, from functional and logical programming) in my applications and eliminate all the cruft left behind from traditional imperative programming, I found a number of items on the web.

There are some in the blogosphere that are newly converted to functional programming. Larry O’Brien wrote “Premature Non-Functional Programming the Root of All Evil?” Bruce Lewis wrote that functional programming is “the Programming Style that Saved my Marriage.”

For those who miss their beloved assignment operator, I found this quote from a Lambda the Ultimate archive.

What if an object deep in the hierarchy must be updated?
For example, when processing an XML DOM, an attribute of an XML node many levels deep may be changed. How is that supposed to be handled with referential transparency? does the whole tree need to be copied?

It's one thing that I have not understood how to handle in functional languages. Does anybody have an answer on this?

Yes. You copy the whole tree, but because referential transparency allows you to share implementations, you only reconstruct the parts of the tree which have changed. This means that the path from the root to the changed node is the only thing that's different, which means changes cost you about log N in the size of the tree. Still more expensive than in-place update in terms of space cost, but I believe that SVN is more or less implemented this way, and it seems to work just fine for that.

The reason why I like functional programming.

• Conciseness. Functional programs tend to be a fraction of the size of imperative programs.
• More Reliable. Functional program more closely resemble the specification, are more understandable, and tend to work the first time. Values are always internally consistent. Subtle bugs are rare.
• Persistence. I always have access to previous versions of my data from which to compare with my more recent data.
• Optimization. There are more opportunities to eliminate infrastructure taxes, allowing the computer to do more of the work that traditionally programmers would do by hand.
• Lazy Evaluation & Lazy Data. This is the ability to delay the evaluation of arguments of a function until they are needed.

With functional programming, suddenly all the cruft I use to deal with disappears. I also think that functional programming is much better for reuse, which is the theme of this article on the Rise and Fall of Object Orientation. Composition’s impact on reuse is multiplicative, whereas inheritance’s is merely additive, which is why features like generics (which are functions on types) and LINQ.are so expressive.

Member functions (or methods, as they are called in other programming languages) are a fundamental aspect of OOP. Think for minute: What could be more logical and properly designed than a member function that is familiar with the intimate details of its object?

Obvious advantages not withstanding, member functions are disfavored in state-of-the-art C++ libraries. The problem is that a member function is useful only for a single class. This is the bane of code reuse. Think, for example, of a library of containers. If each container class defines its own size() member function, you will end up writing numerous size() functions that basically do the same thing.

Don Box captured my sentiment yesterday, “if only I could wish away a lot of the stuff that distracted/stunted the industry back in the late 80's and 1990's, but I can't.” All the new innovations we are seeing in languages herald back to the earlier era of functional programming.

The naysayers say that functional programs are less efficient. I don’t think functional programs need to be slower or require more memory. A functional representation of a document may be more compact than a traditional one, because recurring elements within the document are shared. For example, in my application, text is represented in terms of sentences, words, and paragraphs, better suited for functional manipulation. The variable cost in memory of entering a new word in such a document is 4 bytes (a shared object reference) whereas it would be about 12 bytes in a document organized as a character stream (where an average word consumes 5 characters and one space).

I picked up on a few resources on the Web on efficient functional data structures. I noticed this thesis by Chris Okasaki on Purely Functional Data Structures, who also has a book at Amazon of the same name.

I also discovered treaps for efficiently implement large lists—immutable or not. Treaps which combine trees and heap to create randomized balanced binary trees. Treaps are simpler to write and understand than other structures I use like red-black trees, splay trees and skip lists and run just as fast. Why haven’t I noticed them before? I looked at my Cormen’s Introduction to Algorithms text and realized that they were hidden in the problems section at the end of chapter on Red-Black trees. They are my new favorite data structure.

Comments

[David Stone]

It is interesting how much LINQ is brining the more functional aspects of earlier languages like Lisp to .NET.

As a side note, treaps are fun aren't they? In my CSE 100 class, we had to implement treaps. They're pretty spiffy. And, contrary to popular belief, they're not that hard to implement. :)

[Jack H]

Speaking of efficient sequences, you might want to check out the work that Ralph Hinze and Ross Patterson have done on "finger trees" at:
http://www.soi.city.ac.uk/~ross/papers/FingerTree.html

Finger Trees underly the implementation of the Data.Sequence library in the Haskell base.

Ross Paterson's work on Applicative Arrows (and Arrows, generally) might also interest you in this regard.

[Dejan Jelovic]

Re Treaps:

Be careful with asymptotical speeds of various data structures, they tend to have little relevance on today's architectures. What matters most is data density and cache-hit rates.

Red-black trees, for example, are awful. Check out Judy (http://judy.sourceforge.net/doc/10minutes.htm) for an example of a data structure designed with the cache hierarchy in mind.

At one point languages with only immutable variables have almost caught up with the performance of languages that offer mutable variables, but in the last few years the gap has dramatically widened again on real-world benchmarks.

Dejan

[Wesner Moise]

I am careful with asymptotic. The tree structures I use hold a list of values per node for better locality.

Thanks for the links on finger trees and arrows.

[optionsScalper]

Hey Wes,

Long time, no talk. Hope things are well.

I have my head buried in FP with F#. I think that the key to a lot of this stuff is the ability to mix, i.e. FP, OO, imperative in any useful combination. FP, like OO and imperative stuff is a tool. With IL, CLR and other .NET infrastructure, choices for implementation open dramatically.

I think that there are places where FP in pure form provide for huge advantage on the .NET platform, e.g. SQLCLR implemented in F#, BizTalk Rules in F#, etc. These are "naturally occuring" as functions in their implementations.

Lambdas, closures, type inference, parametric polymorphism (generics) and other features are implemented in F#. It has serious performance too. My friend Chad, just wrote an article using F# on a Grid Computing Platform.

http://cs.jjbresearch.org/blogs/os/archive/2006/05/12/ChadFSharpGridComputing.aspx

I'm looking forward to more advances in Ruby.NET implementations and other languages as well.

I've opened hubFS - THE place for F#. If you are looking at different FP languages in .NET, give this a look:

http://cs.hubFS.net

Regards,

---O