Monday, January 08, 2007

Why I should learn Lisp

At the beginning of 2006, I had promised myself that I will learn Ruby and the tricks of the trade of functional programming. I do Java for a day job and get paid for consulting on enterprise Java architectures. I like Java, I love the Java community, I am a big fan of some of the great cool Java frameworks that are out there. I used to do C++ as well five years back and took great pride in designing allocators and smart pointers. All these were part of the application codebase, and despite using productive libraries like Boost, infrastructure code management (aka memory management and memory leaks) took away most of my night's sleep, at the expense of the geek feeling that I am doing C++. Java was the language that took away from me the pride of writing destructors and allocators. But in course of this sense of loss, I realized that I was now programming at a higher level of abstraction with the entire memory management left to the programming runtime. I was deep into encapsulation and better object orientation and embraced each successive release of Java with great enthusiasm.

One day, after reading a few pages of the pickaxe book and doing some hunting on the internet for Ruby evangelists, I came up with the following piece of Ruby code as the implementation of the Strategy Design Pattern :


class Filter
  def filter(values)
    new_list = []
    values.each { |v| filter_strategy(v, new_list) }
    new_list
  end
end

class EvenFilter < Filter
  def even?(i)
    i%2 == 0
  end

  def filter_strategy(value, list)
    if even?(value)
      list << value
    end
  end
end

of = EvenFilter.new
array = [1,2,3,4,5]
puts of.filter(array)



On further introspection, more reading of the pickaxe book and more rummaging through the musings of Java bashers in LtU, the light of lambda dawned on me. Looked like I was going through the enlightenment of the functional programming paradigms, the enhanced expressivity and abstraction that higher order procedures add to the programs. I could appreciate the value of lexical closures, bottom-up programming and functional abstractions. The new class for Strategy implementation is adapted from Nathan Murray's excellent presentation on Higher Order Procedures in Ruby :


class FilterNew
  def filter(strategy)
    lambda do |list|
      new_list = []
      list.each do |element|
        new_list << element if strategy.call(element)
      end
      new_list
    end
  end
end

of = FilterNew.new
filter_odds = of.filter( lambda{|i| i % 2 != 0} )
array = [1,2,3,4,5]
puts filter_odds.call(array)



The Disappearing Strategy Classes

In the new implementation, where is the strategy class that is supposed to be hooked polymorphically in the context and provide the flexible OO implementation ?

It has disappeared into the powerful abstraction of the language. The method filter() in the second example does not return the newly created list, unlike the first one - it returns a procedure, which can act on other sets of data. The second example is an implementation at a much higher level of abstraction, which adds to the expressivity of the intended functionality.

In fact with functional programming paradigms, many of the design patterns which GOF have carefully listed in the celebrated book on Design Patterns, simply go away in a language that allows user to program at a higher level of abstraction. Have a look at this excellent presentation by Norvig.

As Paul rightly mentions in his post, the paradigms of functional programming hides a lot of accidental complexity mainly because of the following traits, which the language offers :

  1. Higher level of abstraction, which leads to lesser LOC, and hence reduced number of bugs

  2. Side-effect free pure functional code, which liberates the programmer from managing state and sequence of execution

  3. Improved concurrency and scalability because of the stateless and side-effect-free programming model



Ruby or Lisp ?

People look upon Lisp as the language of the Gods, someone has mentioned Ruby as an acceptable Lisp, many others consider Ruby as lying midway between Java and Lisp. Ruby is an object-oriented language with functional programming capabilities, while Lisp came into being in 1958 with the landmark 'eval' function of John McCarthy. As Paul Graham says :
With macros, closures, and run-time typing, Lisp transcends object-oriented programming.

Lisp and Smalltalk have been the main inspirations to Matz behind designing the Ruby language. May be Ruby is more pragmatic than Lisp, but the roots of Ruby are definitely engrained within the concepts of pure macros, lexical closures and extensibility mechanisms that Lisp provides. Lisp is the true embodiment of "code-as-data" paradigm. Lispers claim that Lisp (or any of its dialects) is definitely more expressive than Ruby, Lisp macros can extend the language more seamlessly than Ruby blocks. I am not qualified enough to comment on this. But my only observation is that behind the nice Lispy DSL that Rails provide, its implementation looks really clumsy and possibly would have been much more cleaner in Lisp.

Not only Ruby, functional programming constructs are beginning to make their appearence in modern day OO languages as well. C# and Visual Basic already offer lambdas and comprehensions, Java will have closures in the next release - the Lisp style is promising to come back.

Still I do not think Lisp is going to make mainstream, yet I need to learn Lisp to be a better fit in today's world of changing programming paradigms.

13 comments:

Anonymous said...

At the risk of sounding monotonous (or possibly monotonic), perhaps you should consider learning Haskell rather than Lisp. Haskell is a pure functional language, so you will not be distracted by non-pure constructs and worries about whether they are appropriate in a given context. Haskell also has strong static typing. Whether you like strong type systems or not, you will understand the issues much better after learning Haskell.

BTW, thanks for the compliment.

Paul.

Anonymous said...

I don't intend to disagree with Paul Johnson, but there is still a relative shortage of good high-level Haskell books compared to the classics using Lisp and Scheme. So, perhaps you might still look at Lisp, at least enough to try your hands on SICP and other key works. They work for Haskellers too.

SICP stands for Structure and Interpretation of Computer Programs, and you can find the text on the web. Whether it's appropriate for you, you only can decide. But you can find it recommended highly in several places, I'm sure.

Anonymous said...

what's the deal with your filtering? if you think in terms of first-class functions, you can just pass the boolean function into some global filtering function, like so

def filter(lst)
lst.inject([]) {|accum,elem|
yield(elem) ? [elem]+accum : accum }
end

so you'd have filter (1..5) {|i| i%2==0}.

incidentally haskell has filter built-in, so you can just do

filter (\i->i%2==0) [1..5]

this has the friendly name 'find_all' in the enumerable class.

Anonymous said...

what's the deal with your filtering? if you think in terms of first-class functions, you can just pass the boolean function into some global filtering function, like so

def filter(lst)
lst.inject([]) {|accum,elem|
yield(elem) ? [elem]+accum : accum }
end

so you'd have filter (1..5) {|i| i%2==0}.

incidentally haskell has filter built-in, so you can just do

filter (\i->i%2==0) [1..5]

ruby has this too; it's 'find_all' in the enumerable class.

Anonymous said...

Enumerable ( the parent of both Hash & Array ) has a number of iteration methods built in.

So ...

You could do exactly what you are looking at with either :

[1,2,3,4,5].collect { |x| x % 2 == 0 }

and if you don't like the name you can always use:

module Enumerable
# alias the built in collect method
# to the name filter.
alias_method :filter, :collect
end

[1,2,3,4,5].filter { |x| x % 2 == 0 }

... just passing along the information.

jd.

Anonymous said...

Haskell has even:

>> filter even [1..5]
=> [2,4]

Also, % is not modulo in Haskell, but `mod` is:

>> filter (\i -> i `mod` 2 == 0) [1..5]
=> [2,4]

The Haskell equivalent of your strategy code is:

>> filterOdds = filter odd
>> filterOdds [1..5]
=> [2,4]

The normal way to do this in Ruby is:

>> (1..5).reject{|i| i % 2 != 0}
=> [2,4]

or with a def:

>> def filter_odds(arr)
>> arr.reject{|i| i % 2 != 0}
>> end

You can call it like this:

>> filter_odds([1,2,3,4,5])

or like this:

>> f = method(:filter_odds)
>> f.call([1,2,3,4,5])

Learn to program.

Anonymous said...

In Common Lisp you'd write in a functional style:

CL-USER 1 > (remove-if-not 'evenp (list 1 2 3 4 5))
(2 4)

For many things the object-oriented programming style (as you shown in Ruby) adds just too much unnecessary complication.

But when you need it (say, for larger architectures), Common Lisp has the Common Lisp Object System built in.

Common Lisp provides the dynamic features comparable to Ruby, but typical Common Lisp implementations will be able to generate much faster code - using an incremental or a batch compiler.

Brendan said...

I have been making my living doing Rails full-time for more than a year now and have pushed Ruby around enough to find enough edges not just in Rails, but in the Ruby language itself, where pretty much only the power of macros would solve the problem the way I wanted to. So now I'm working my way through Paul Graham's book ANSI Common Lisp and am getting excited by the possibilities.

Anonymous said...

nice post

Wicked Web Programmers said...

Thanks.Lisp programs can manipulate source code as a data structure giving rise to the macro systems.

Jack Kinsella said...

Even shorter version of the strategy filter in ruby

class FilterNew
def filter(strategy)
lambda do |list|
list.select { |element| element if strategy.call(element) }
end
end
end

Anonymous said...

For almost every position I have held, the product implementation language had already been chosen. I had to learn what was there and become proficient in its use. Before I left private sector eight years ago, those languages included Perl and C++, because that is what Legato used. I also maintained a CoStandby For Windows configuration utility that was written in Java.

Leaving the private sector eight years ago meant becoming very proficient in Informix 4GL, whether I liked it or not. Please trust me when I say you do not want to be a hero by re-writing a municipal tax collection system, because you are used to programming in C/C++. You go with what you have and start designing your way into more modern languages. I did just that.

Before picking a "pure" functional programming language like Haskell or a not so pure, the question for me has had to be what will be useful in the market. I chose Clojure for that reason.

Whether it is the right or wrong kind of Lisp did not matter to me. Because it is a JVM language, I can easier introduce some carefully developed pieces into our production environment without totally wigging everyone out.

Thanks for this post. It was interesting as were the other comments.

Anonymous said...

may I guess that you eat your corn in spirals not rows? This appears to be a trait of analysis thinking rather than algebraic. Also may explain my interest in Ruby and Lisp. Cheers