Monday, October 01, 2012

Towards better refactoring support in IDEs for functional programming


A couple of days back I was thinking how we could improve the state of IDEs and let them give rich feedbacks to users focusing on code improvement and refactoring. When you write Java programs, IntelliJ IDEA is possibly the best IDE you can have with an extensive set of refactoring tools. But most of these are targeted towards reducing boilerplates and do refactor based on structural changes only (e.g. replace constructor with builder or use interfaces wherever possible etc.). Can we improve the state of the art when we are using a semantically richer language like Scala or Haskell ? How about suggesting some idioms that relate to the paradigm of functional programming and explore some of the best practices suggested by the masters of the trade ?

I always find many programmers use Option.get in Scala when they should be using higher order structures instead. Here's an example of the anti-pattern ..

if oName.isDefined oName.get.toUpperCase else "Name not present"

which should ideally be refactored to

oName.map(_.toUpperCase).getOrElse("Name not present")

The advantage with the latter is that it's more composable and can be pipelined to other higher order functions down the line without introducing any temporary variables.

Many people also use pattern matching for destructuring an Option ..

oName match {
  case Some(n) => n.toUpperCase
  case _ => "Name not present"
}

This is also not what idioms espouse and is almost equivalent to explicit null checking.

Can an IDE suggest such refactoring ? I tweeted about my thoughts and almost immediately Mirko, who is doing some great stuff on the Scala IDE, added this to his list of ideas. Nice!

Here's another idea. How about suggesting some program transformations for functional programming ? I know Scala is not a pure functional language and we don't have effect tracking. I have seen people use side-effecting functions in map, which, I know is a strict no-no. But again, the compiler doesn't complain. Still we can have the IDE suggest some refactorings assuming the programmer uses purity as per recommendations. After all, these are suggestions only and can enlighten a programmer with some of the realizations of how to model based on the best practices.

Consider this ..

(-1000000 to 1000000).map(_ + 1).filter(_ > 0)

Here the map is executed on all the elements and then filter processes the whole output. One option to optimize will be to defer the computations using view ..

(-1000000 to 1000000).view.map(_ + 1).filter(_ > 0)

But this doesn't reduce the load of computation on map. It just prevents the creation of a temporary list as an output of the map. We can apply a transformation called filter promotion that does the filtering first so that map can operate on a potentially smaller list. Of course this assumes that both functions are *pure* so that operations can be reordered - but that's what we should anyway ensure while doing functional programming .. right ? Here's the transformation ..

(-1000000 to 1000000).filter(((_: Int) > 0) compose ((_: Int) + 1)).map(_ + 1)

which can be further simplified into ..

(-1000000 to 1000000).filter((_: Int) >= 0).map(_ + 1)

.. and this has same computation load on filter but potentially less load on map, since it now has to process a filtered list.

Can we have such transformations available in the IDE ? I am a faithful user of vim, but with such enrichments I may consider going back to an IDE. TYhis really has no limits. Consider Wadler's free theorems. Many times we tend to write functions whose arguments are more specialized in types than what's required. Generalization of such functions using polymorphic arguments can lead to better abstraction and verification through free theorems. An IDE can suggest all these and may also help generate properties for property based testing using tools like QuickCheck and ScalaCheck. But that's discussion for another day ..

P.S. Simon Thompson's Haskell The Craft of Functional Programming 3rd edition discusses lots of similar transformations in various chapters that discuss reasoning or Haskell programs.

6 comments:

Daniel Yokomizo said...

Mix something like GHC's rewrite rules [1], add the ideas from Mel Ó Cinnéide's automated refactoring research [2], and the state of art in Refactoring Functional Programs [3]. That's the general gist of what I've been studying in this area.

[1] http://www.haskell.org/ghc/docs/6.12.2/html/users_guide/rewrite-rules.html
[2] http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/c/Cinn=eacute=ide:Mel_=Oacute=.html
[3] http://www.cs.kent.ac.uk/projects/refactor-fp/

Mirko Stocker said...

Great post!

I think that an IDE could be very helpful in teaching good/idiomatic style to programmers new to Scala, and this is also a long term goal of my scala-refactoring library.

The first step I did (it's not yet available in the IDE but I have it in a branch) is warning and automatically refactoring pattern matching on Option (see my blog post and the tests for the current implementation).

Debasish Ghosh said...

Daniel -

Thanks for the links. I am already having lots of ideas about refactoring, studying what Simon Thompson is doing with user driven extensible refactoring. Your links will definitely help. Trying to view refactoring as term rewriting, graph transformations backed by DSLs are what I was thinking more about. Will study the ghc rewrite rules more and see into the recent research pointers that u have given.

Debasish Ghosh said...

Mirko -

Looking forward to some more of refactoring goodness from Scala / Eclipse IDE. I think with ASTs available now, we can make much semantically richer IDEs and even allow users to add a few ..

OlegYch said...

Wouldn't it be better to refactor map.filter to collect?

Dave Stevens said...

I am surprised by the amount of these types of suggestions (and thus refactoring) that the Jetbrains Resharper plugin for Visual Studio does make. Obviously the c# laguage and type system are no where near as rich as Scala, forget Haskell, but it does have limited local inference, lambda syntax and linq expressions. These suggestions can get annoying once you have leveled up to a certain point because they do not always result in better code. They definitely helped me to pick up the new language features when they were first added though.