Functional Programming

5/13/2006 2:39:54 AM

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

 

Navigation

Categories

About

Net Undocumented is a blog about the internals of .NET including Xamarin implementations. Other topics include managed and web languages (C#, C++, Javascript), computer science theory, software engineering and software entrepreneurship.

Social Media