Is there a software-engineering methodology for functional programming?

Question

Software Engineering as it is taught today is entirely focused on object-oriented programming and the 'natural' object-oriented view of the world. There is a detailed methodology that describes how to transform a domain model into a class model with several steps and a lot of (UML) artifacts like use-case-diagrams or class-diagrams. Many programmers have internalized this approach and have a good idea about how to design an object-oriented application from scratch.

The new hype is functional programming, which is taught in many books and tutorials. But what about functional software engineering? While reading about Lisp and Clojure, I came about two interesting statements:

1. Functional programs are often developed bottom up instead of top down ('On Lisp', Paul Graham)

2. Functional Programmers use Maps where OO-Programmers use objects/classes ('Clojure for Java Programmers', talk by Rich Hickley).

So what is the methodology for a systematic (model-based ?) design of a functional application, i.e. in Lisp or Clojure? What are the common steps, what artifacts do I use, how do I map them from the problem space to the solution space?

Answer 1

Thank God that the software-engineering people have not yet discovered functional programming. Here are some parallels:

• Many OO "design patterns" are captured as higher-order functions. For example, the Visitor pattern is known in the functional world as a "fold" (or if you are a pointy-headed theorist, a "catamorphism"). In functional languages, data types are mostly trees or tuples, and every tree type has a natural catamorphism associated with it.

  These higher-order functions often come with certain laws of programming, aka "free theorems".

• Functional programmers use diagrams much less heavily than OO programmers. Much of what is expressed in OO diagrams is instead expressed in types, or in "signatures", which you should think of as "module types". Haskell also has "type classes", which is a bit like an interface type.

  Those functional programmers who use types generally think that "once you get the types right; the code practically writes itself."

  Not all functional languages use explicit types, but the How To Design Programs book, an excellent book for learning Scheme/Lisp/Clojure, relies heavily on "data descriptions", which are closely related to types.

So what is the methodology for a systematic (model-based ?) design of a functional application, i.e. in Lisp or Clojure?

Any design method based on data abstraction works well. I happen to think that this is easier when the language has explicit types, but it works even without. A good book about design methods for abstract data types, which is easily adapted to functional programming, is Abstraction and Specification in Program Development by Barbara Liskov and John Guttag, the first edition. Liskov won the Turing award in part for that work.

Another design methodology that is unique to Lisp is to decide what language extensions would be useful in the problem domain in which you are working, and then use hygienic macros to add these constructs to your language. A good place to read about this kind of design is Matthew Flatt's article Creating Languages in Racket. The article may be behind a paywall. You can also find more general material on this kind of design by searching for the term "domain-specific embedded language"; for particular advice and examples beyond what Matthew Flatt covers, I would probably start with Graham's On Lisp or perhaps ANSI Common Lisp.

What are the common steps, what artifacts do I use?

Common steps:

1. Identify the data in your program and the operations on it, and define an abstract data type representing this data.

2. Identify common actions or patterns of computation, and express them as higher-order functions or macros. Expect to take this step as part of refactoring.

3. If you're using a typed functional language, use the type checker early and often. If you're using Lisp or Clojure, the best practice is to write function contracts first including unit tests—it's test-driven development to the max. And you will want to use whatever version of QuickCheck has been ported to your platform, which in your case looks like it's called ClojureCheck. It's an extremely powerful library for constructing random tests of code that uses higher-order functions.

Answer 2

OO programming tightly couples data with behavior. Functional programming separates the two. So you don't have class diagrams, but you do have data structures, and you particularly have algebraic data types. Those types can be written to very tightly match your domain, including eliminating impossible values by construction.

So there aren't books and books on it, but there is a well established approach to, as the saying goes, make impossible values unrepresentable.

In so doing, you can make a range of choices about representing certain types of data as functions instead, and conversely, representing certain functions as a union of data types instead so that you can get, e.g., serialization, tighter specification, optimization, etc.

Then, given that, you write functions over your adts such that you establish some sort of algebra -- i.e. there are fixed laws which hold for these functions. Some are maybe idempotent -- the same after multiple applications. Some are associative. Some are transitive, etc.

Now you have a domain over which you have functions which compose according to well behaved laws. A simple embedded DSL!

Oh, and given properties, you can of course write automated randomized tests of them (ala QuickCheck).. and that's just the beginning.

Answer 3

Honestly if you want design recipes for functional programs, take a look at the standard function libraries such as Haskell's Prelude. In FP, patterns are usually captured by higher order procedures (functions that operate on functions) themselves. So if a pattern is seen, often a higher order function is simply created to capture that pattern.

A good example is fmap. This function takes a function as an argument and applies it to all the "elements" of the second argument. Since it is part of the Functor type class, any instance of a Functor (such as a list, graph, etc...) may be passed as a second argument to this function. It captures the general behavior of applying a function to every element of its second argument.

Answer 4

There is the "program calculation" / "design by calculation" style associated with Prof. Richard Bird and the Algebra of Programming group at Oxford University (UK), I don't think its too far-fetched to consider this a methodology.

Personally while I like the work produced by the AoP group, I don't have the discipline to practice design in this way myself. However that's my shortcoming, and not one of program calculation.

Answer 5

While this might be considered naive and simplistic, I think "design recipes" (a systematic approach to problem solving applied to programming as advocated by Felleisen et al. in their book HtDP) would be close to what you seem to be looking for.

Here, a few links:

http://www.northeastern.edu/magazine/0301/programming.html

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.86.8371

Answer 6

One approach is to create an internal DSL within the functional programming language of choice. The "model" then is a set of business rules expressed in the DSL.

Answer 7

For Clojure, I recommend going back to good old relational modeling. Out of the Tarpit is an inspirational read.

Answer 8

See my answer to another post:

How does Clojure aproach Separation of Concerns?

I agree more needs to be written on the subject on how to structure large applications that use an FP approach (Plus more needs to be done to document FP-driven UIs)

Answer 9

Personally I find that all the usual good practices from OO development apply in functional programming as well - just with a few minor tweaks to take account of the functional worldview. From a methodology perspective, you don't really need to do anything fundamentally different.

My experience comes from having moved from Java to Clojure in recent years.

Some examples:

• Understand your business domain / data model - equally important whether you are going to design an object model or create a functional data structure with nested maps. In some ways, FP can be easier because it encourages you to think about data model separately from functions / processes but you still have to do both.

• Service orientation in design - actually works very well from a FP perspective, since a typical service is really just a function with some side effects. I think that the "bottom up" view of software development sometimes espoused in the Lisp world is actually just good service-oriented API design principles in another guise.

• Test Driven Development - works well in FP languages, in fact sometimes even better because pure functions lend themselves extremely well to writing clear, repeatable tests without any need for setting up a stateful environment. You might also want to build separate tests to check data integrity (e.g. does this map have all the keys in it that I expect, to balance the fact that in an OO language the class definition would enforce this for you at compile time).

• Prototying / iteration - works just as well with FP. You might even be able to prototype live with users if you get very extremely good at building tools / DSL and using them at the REPL.

Answer 10

I've found Behavior Driven Development to be a natural fit for rapidly developing code in both Clojure and SBCL. The real upside of leveraging BDD with a functional language is that I tend to write much finer grain unit tests than I usually do when using procedural languages because I do a much better job of decomposing the problem into smaller chunks of functionality.

Answer 11

Object Oriented design isn't the same thing as software engineering. Software engineering has to do with the entire process of how we go from requirements to a working system, on time and with a low defect rate. Functional programming may be different from OO, but it does not do away with requirements, high level and detailed designs, verification and testing, software metrics, estimation, and all that other "software engineering stuff".

Furthermore, functional programs do exhibit modularity and other structure. Your detailed designs have to be expressed in terms of the concepts in that structure.

Answer 12

Well,

Generally many Functional Programming Languages are used at universities for a long time for "small toy problems".

They are getting more popular now since OOP has difficulties with "paralel programming" because of "state".And sometime functional style is better for problem at hand like Google MapReduce.

I am sure that, when functioanl guys hit the wall [ try to implement systems bigger than 1.000.000 lines of code], some of them will come with new software-engineering methodologies with buzz words :-). They should answer the old question: How to divide system into pieces so that we can "bite" each pieces one at a time? [ work iterative, inceremental en evolutionary way] using Functional Style.

It is sure that Functional Style will effect our Object Oriented Style.We "still" many concepts from Functional Systems and adapted to our OOP languages.

But will functional programs will be used for such a big systems?Will they become main stream? That is the question.

And Nobody can come with realistic methodology without implementing such a big systems, making his-her hands dirty. First you should make your hands dirty then suggest solution. Solutions-Suggestions without "real pains and dirt" will be "fantasy".

Answer 13

I've recently found this book: Functional and Reactive Domain Modeling

I think is perfectly in line with your question.

From the book description:

Functional and Reactive Domain Modeling teaches you how to think of the domain model in terms of pure functions and how to compose them to build larger abstractions. You will start with the basics of functional programming and gradually progress to the advanced concepts and patterns that you need to know to implement complex domain models. The book demonstrates how advanced FP patterns like algebraic data types, typeclass based design, and isolation of side-effects can make your model compose for readability and verifiability.