Wednesday, September 10, 2008

Make friends with Visitors

A good starting point in understanding functional programming is to understand the difference between Visitor and Strategy patterns. Strategy pattern is what almost all OO programmers are familiar with. You have your graphic objects with their draw methods that faithfully draw the object. From outside the caller has no idea about the underlying implementation. In this model it is easy to add new objects to the system. You can add new shapes, just as long as they implement draw method. The pattern has a weakness in the sense that if you want to add a new function then it would be difficult. Let say we need to add a method to calculate the area of a shape, now every object has to be modified to implement the new method. So you in Strategy pattern you are fixing your class interface but let your data be extensible.

Visitor pattern is also an OO pattern but most programmers are not as familiar with it. The pattern is interesting in the sense that unlike the strategy pattern you fix your classes (say only deal with certain shapes) but let actions be extensible. In visitor pattern to add a new requirement like calculating perimeter would be easy but adding a new shape would be difficult. Assigning a new shape will require change to all the existing actions. The most successful visitor pattern implementation are when you work with a specification where your data is defined but your actions are extensible. Say for instance you want to parse XML tree. The specification of the tree structure is defined but what the application does with the tree is left for the application.

You may think to yourself that if I fix my data types then I would not easily be able to extend my system. The key is that your data type should not just include primitive types. It would need to include primitives to modify and compose basic primitives into more complex structure (like tree).

Peter Seibel does a great job discussing the visitor pattern and its implementation in Java vs Lisp. The ideas presented in the video is not lisp specific, but rather a different way of thinking about a problem. Video of his presentation is available online. Kudos to Peter for his no-power-point presentation.

Friday, September 5, 2008

What do you measure...

In questing Gross Domestic Product(GDP) measurements as valid health economic indicator, Martin Collier of the Glaser Progress Foundation says:

The most simple way to put it is you are what you measure, you get what you measure, and you fix what you measure. It's time to measure what matters most, it's time to measure what we value most, instead of simply valuing what we measure. Source

Interesting...You {are, get, fix} what you measure.

Thursday, September 4, 2008

How little software has changed...

It is amazing how much of Computer Science was done way before it became as popular as it is today. It is also amazing how little it has progressed (at least as is practiced by professionals) since the old days. Back in August of 1978 John Backus (The B in BNF and inventor of FORTRAN) had this to say:

Programming languages appear to be in trouble. Each successive language incorporates, with a little cleaning up, all the features of its predecessors plus a few more. Some languages have manuals exceeding 500 pages; others cram a complex description into shorter manuals by using dense formalisms. The Department of Defense has current plans for a committee-designed language standard that could require a manual as long as 1,000 pages. Each new language claims new and fashionable features, such as strong typing or structured control statements, but the plain fact is that few languages make programming sufficiently cheaper or more reliable to justify the cost of producing and learning to use them.

Since large increases in size bring only small increases in power, smaller, more elegant languages such as Pascal continue to be popular. But there is a desperate need for a powerful methodology to help us think about programs and no conventional language even begins to meet that need. In fact, conventional languages create
unnecessary confusion in the way we think about programs.

For twenty years programming languages have been steadily progressing toward their present condition of obesity; as a result, the study and invention of programming languages has lost much of its excitement. Instead, it is now the province of those who prefer to work with thick compendia of details rather than wrestle with new
ideas. Discussions about programming languages often resemble medieval debates about the number of angels that can dance on the head of a pin instead of exciting
contests between fundamentally differing concepts.

Many creative computer scientists have retreated from inventing languages to inventing tools for describing them. Unfortunately, they have been largely content to apply their elegant new tools to studying the warts and moles of existing languages. After examining the appalling type structure of conventional languages, using the elegant tools developed by Dana Scott, it is surprising that so many of us remain passively content with that structure instead of energetically searching for new ones.

Source: 1977 Turing Award Lecture: Can Programming Be Liberated From the von Neumann Style?

Things seem to have got even worst. C++ had so much issues (aka tricky interview questions) that someone needed to write "Effective C++: 50 Specific Ways to Improve Your Programs and Design", and as if that was not bad enough, he had to do the follow on book: "More Effective C++: 35 New Ways to Improve Your Programs and Designs". Notice it is not talking about effective design, just how to get C++ to work for you, or how to avoid the "gotchas" in the language. For me that was bad enough, so like many others I jumped to the next "successive language" which incorporated "with a little cleaning up, all the features of its predecessors plus a few more". Just look at the size of Java Generic FAQ . Just this one language feature is worst than what John Backus was worried for the whole language: "Some languages have manuals exceeding 500 pages". Here you have a language that the FAQ for just one of its feature is beyond comprehension.

Something is clearly wrong!

What is Computer Science?

Slides for MIT's course on "Structure and Interpretation of Computer Programs" is available on line. The first few slides talk about a key issue that I think is important in understanding the Computer Science and Software in general:

This first thing we need to do is discuss the focus of 6.001. What is this course all about? This seems quite obvious -- this is a course about computer science. But we are going to claim in a rather strange way that this is not really true.

First of all, it is not really about science. It is really much more about engineering or art than it is about science.

...and it is not really about computers. Now that definitely sounds strange! But let me tell you why I claim it is not really about computers. I claim it is not really about computers in the same way that physics is not really just about particle
accelerators, or biology is not really just about microscopes, or geometry is not really about surveying instruments.

In fact, geometry is a good analogy to use here. It has also a terrible name, which comes from two words: GHIA or earth, and METRA or measurement. And to the ancient Egyptians, that is exactly what geometry was -- instruments for measuring the earth, or surveying. Thousands of years ago, the Nile annually flooded, and eventually retreated, wiping out most of the identifying landmarks. It also deposited rich soil in its wake, making the land that it flooded very valuable, but also very hard to keep track of. As a consequence, the Egyptian priesthood had to arbitrate the restoration of land boundaries after the annual flooding. Since there were no landmarks, they needed a better way of determining boundaries, and they invented geometry, or earth measuring. Hence, to the Egyptians, geometry was surveying -- and about surveying instruments. This is a common effect. When a field is just getting started, it’s easy to confuse the essence of the field with its tools, because we usually understand the tools much less well in the infancy of an area. In hindsight, we realize that the important essence of what the Egyptians did was to formalize the notions of space and time which later led to axiomatic methods for dealing with declarative, or What Is kinds of knowledge. --- So geometry not really about measuring devices, but rather about declarative knowledge.

So geometry is not really about surveying, it is actually fundamentally about axioms for dealing with a particular kind of knowledge, known as Declarative, or "what is true" knowledge.

By analogy to geometry, Computer Science is not really about computers -- it is not about the tool. It is actually about the kind of knowledge that computer science makes available to us.

Wednesday, September 3, 2008

"On X"

Paul Graham has interesting book called On Lisp. If you are interested to know more about Lisp programming you can download the book for free or read it on on line. The point of this post is not so much to talk about the Lisp programming language as much as talking about why it is call "On Lisp". Here is what author has to say about it:

Bottom-up design is becoming more important as software grows in complexity. Programs today may have to meet specifications which are extremely complex, or even open-ended. Under such circumstances, the traditional top-down method sometimes breaks down. In its place there has evolved a style of programming quite different from what is currently taught in most computer science courses: a bottom-up style in which a program is written as a series of layers, each one acting as a sort of programming language for the one above. X Windows and TeX are examples of programs written in this style.


The title is intended to stress the importance of bottom-up programming in Lisp. Instead of just writing your program in Lisp, you can write your own language on Lisp, and write your program in that.


Bottom-up design leads naturally to extensible programs. The simplest bottom-up programs consist of two layers: language and program. Complex programs may be written as a series of layers, each one acting as a programming language for the one above. If this philosophy is carried all the way up to the topmost layer, that layer becomes a programming language for the user. Such a program, where extensibility permeates every level, is likely to make a much better programming language than a system which was written as a traditional black box, and then made extensible as an afterthought.

Keep "bottom-up" and more importantly "On XXX" concept in mind as you are trying to understand the functional programming paradigm.

Monday, September 1, 2008

Haskell School of Expression

I am long time imperative programmers (C/C++/Java) that feel I have reached a point where I need a paradigm shift. I am looking more and more into functional programming and it seems to be what I need. Unfortunetly it is painful to pick up the concept of functional programing. There are bits and pieces of nuggets that I have been comming accross that may make the journey easier for new commers. In this blog I intend to share my experience.

A recurring issue in reading the Functional Programming papers is that the concepts are explained in terms of simple mathematical program. For instance, you see volumes written on factorial, Fibonacci numbers, or simple programs. They are all well and good, but - at least for me - it is hard to map from factorial to a business problem I am trying to solve. There are, however, nuggets that have been quite useful for me and I will do my best to share them. Please let me know with your comments what does and doesn't work for you too.

The first must read in the topic of functional programming is the Pual Hudak's book: The Haskell School of Expression
You can read the book on line but I HIGHLY recommend that you get your own copy of the book. It is simply the best starting point on the topic.

From my perspective the best thing about the book is that it shows the functional programming implementation in terms of programs that a OO/Imperative programmers are already familiar with. Almost every Object Oriented book describes the OO concept in a paint-like program. Most people learn OO with geometrical shape objects and their draw methods. Hudak's book implemented the same application in Haskell using Functional Programming concepts. It is quite interesting to see how the FP uses the class and instance concept. The book goes on to implement a Pong application in just 17 lines (see Demo4 ). The book is amazing, even if you are not interested in doing Functional Programming, I bet it would have a major impact in your designs.