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?

Solution 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.

Solution 2

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

Solution 3

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.

Solution 4

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.

Solution 5

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.

View more solutions

Comments

[Artyom Shalkhakov]

I have a comment here: many programs are written in a top-down fashion, a practical exposition to the process of software development in a functional language is given in the book "Functional Programming in Concurrent Clean" (the language itself is very academic, though).

[Gabriel Ščerbák]

1. Parnas argues that most programs should be bottom-up and then faked to look like top-down, so those approaches should be mixed, there is no right answer.

[Gabriel Ščerbák]

2. Objects provide behaviour depending on their encapsulated structured state, in FP you have all state and structure explicit and behaviour (functions) is separated from the structure. So for data modeling, you use maps for objects, but when designing applications, objects cannot be replaced with functions - FP is a large expression generated and evaluated through pipelines, OOP is about creating the model and sending messages between objects.

[Sandeep]

I asked a related question sometime back : " how does one model data from relational databases in clojure ?" stackoverflow.com/questions/3067261/…

[CesarGon]

@Svante: I suggest that a methodology is the "specification of the process to follow together with the work products to be used and generated, plus the consideration of the people and tools involved, during an information-based domain development effort", as per ISO/IEC 24744 (iso.org/iso/catalogue_detail.htm?csnumber=38854)

[Michael Ekstrand]

I appreciate that you put the question mark after model-based - I doubt know that a methodology, if it exists, will be model-based, at least in the same way that OOA/D is. In my FP work, I frequently start with data types, but do not do any full modeling of real-world entities.

[Zak]

PG claims elsewhere that Lisp programs are simultaneously built top-down and bottom-up, meeting in the middle like an arch. This is more to do with the fact that Lisp supports syntactic abstraction through macros than that it's functional. The basic idea is to figure out how you would write your code in a language ideally suited to the task at hand, then extend Lisp so that you can.

[lfborjas]

Hehe, in on of the SICP lectures Hal Abelson says, half in jest, something along the lines of "There is a famous methodology, or should I say mythology, called software engineering [...] making complicated diagrams and requirements and then building systems with them; those people haven't programmed much". I come from a "Java School", where for ages we where taught UML and artifacts and stuff, and whilst a little of it is good, too much planning and scheming (pun intended) is more harmful than useful: you never know how your software will be until you get to actually code.

[Alex Blakemore]

@GabrielŠčerbák Dave Parnas also argued that design should not be done from the top-down or from the bottom-up, but instead should proceed "least likely to change first". That allows the most stable assumptions to be the ones most deeply baked into the design.

[Thorsten]

I like the 90% pipeline and 10% macro approach. It seems quite natural to think of a functional program as a pipeline of transformations on immutable data. I'm not sure if I understand what you mean by "put all the intelligence into the data, not the code", since the approach to have 100 functions working on 1 data structure (rather than 10 functions on 10 datastructures) seems to imply the opposite. Aren't data structures in OOP more intelligent than in FP, since they have their own behaviour build in?

[Thorsten]

I understand the approach to first build the language towards the problem domain until a level of abstraction is reached that no repetitive patterns occur anymore in the code, than solve the problem with that abstractions.

[Thorsten]

But how does it look like when "the model is a set of business rules expressed in the DSL"? In a Java EE application the model is written as POJO-Entities, that are called from controller-EJBs which in turn update view-JSPs - for example. Are there similar architectural patterns (like the MVC-pattern) in FP? How does that look like?

[Thorsten]

These practices sound quite familiar to me. I still think somebody should write the functional equivalent to "Object-Oriented Software Engineering using UML, Patterns and Java" by Bruegge/Dutoit instead of the sixth book "Programing in Clojure". It could be called "Functional Software Engineering using Clojure and ??what??". Do they use UML and patterns in FP? I remember Paul Graham wrote that patterns are a sign for a lack of abstraction in Lisp, that should be remedied by the introduction of new macros.

[Thorsten]

Thats a great article, the good old times in Computer Science must have been really impressively good, when all these concepts survived until today's renaissance. It's probably due to the strong foundations in math.

[Thorsten]

But if you translate patterns as best practices, there might be patterns in the FP world too, worth to be shared with the uninitialized.

[mathk]

There are some intresting principle design in the PAIP book. norvig.com/paip.html

[Gabriel Ščerbák]

there are also functional programming patterns (schemes of recursion etc.)

[sclv]

There's no reason you can't have a MVC pattern in FP, precisely like that. FP still lets you build rich data structures, and arguably with ADTs and pattern matching, lets you build much richer ones. If anything, since FP separates data and behavior, MVC type systems arise much more naturally.

[Michael Ekstrand]

IMO visitor is not fold - fold is a subset of visitor. Multiple dispatch is not (directly) captured by fold.

[Zak]

The approach of making impossible values unrepresentable is less applicable to languages with dynamic typing like Clojure and Scheme than to languages with static typing like Haskell and ML.

[John Cromartie]

This. THIS. THIS! I am reading this paper, and it's really interesting how it seems to cover all the bases of what it takes to build real systems, while maintaining minimal mutable state in a highly controlled fashion. I'm toying with building Pong and Tetris in a FRelP style (excuse the strange initialism, but there is already another more popular FRP: Functional Reactive Programming).

[sclv]

@Michael -- actually you can capture multiple dispatch with various sorts of higher order catamorphisms very neatly. Jeremy Gibbons' work is one place to look for this, but I'd recommend work on datatype-generic programming in general -- I'm particularly fond of the compos paper.

[sclv]

@Zak -- well, you can't statically check that they're unrepresentable, but you can build your data structures the same way anyway.

[Alex Miller]

I agree that I see diagrams used much less frequently to describe functional designs and I think that's a shame. It is admittedly difficult to represent the equivalent of a sequence diagram when using a lot of HOF. But I wish the space of how to describe functional designs with pictures was being better explored. As much as I hate UML (as spec), I find UML (as sketch) to be quite useful in Java and wish there were best practices on how to do the equivalent. I've been experimenting a bit on doing this with Clojure protocols and records, but have nothing I really like.

[Michael Ekstrand]

@sclv thanks for the reference.

[Thorsten]

I actually knew something about algebraic data types and signatures because I took a course on this book (Moving Object Databases by Güting): tinyurl.com/6y7qmjn. But without basic knowledge in FP it did not occur to me that this could be a general approach to the design of programs in this paradigm.

[Kris Nuttycombe]

Visitor can be used to implement a fold, but the Visitor pattern is not about folding. The correct functional programming analogue for Visitor is pattern matching or multimethods; when implemented properly (where Visitor is Visitor<T> where each visit method returns a value of type T instead of void) Visitor is exactly equivalent to a multiple-dispatch function of arity 1. It's even a monad!

[Thorsten]

After reading the paper I think that clojure would be the perfect language for FR(el)P, at least for the essential logic, the accidental state and control and the other components. I wonder how to make a relational definition of the essential state in clojure without reinventing sql (without its flaws)? Or is the idea to simply use a good relational (sql) DB and built a functional program on top of it without the conceptual mismatch introduced by OOP?

[Don Moe]

@Thorsten Mens sana in corpore sano. Yes a good RDBMS, a good schema and a FP layer. No more impedance mismatch because you are not fighting against the RDBMS. I have pages of design notes on a tentative SQL lib which would embody such a design. However even when your application doesn't need to go to disk, relational modeling can yield interesting Clojure code.

[Thorsten]

@cgrand Could you give a little example how relational modeling would translate to clojure data stuctures? Just guessing, I would define map=table, then one map-key is primary key and some others are secondary keys and you normalize the whole model just like you would do with tables. That simple?

[Don Moe]

@Thorsten the basic idea is set=table, map=index. The hard part is keeping indexes and tables synced but this problem can be solved with better set types. One simple set type I implemented is the keyed-set which is a set which uses a key function to test for unicity. This means that conjing a value insert or update, calling get with the primary-key fields returns the whole row.

[Thorsten]

@cgrand maybe I'm a bit spoiled by the middleware that abstracts the database away in OOP, but I still find it difficult to imagine the interaction between the model and the RDBMS. Without such enhanced types and a SQL lib, wouldn't your application become contaminated by SQL statements very fast? As an example, I read about two open source ERP systems, one in Python, the other one heavily based on SQL statements (I don't remember the language). The pure OOP Python system was seen as very convenient for modular community development, the other system as an almost unmaintainable SQL hell.

[Don Moe]

@Thorsten, I misunderstood you: in your last comment I thought you were talking about relational modeling in pure Clojure (no db). Clojure is in need for an excellent relational mapper, I consider ClojureQL interesting for queries but it is lacking on db updates

[Don Moe]

@Thorsten, (hit enter too soon) I said "no more impedance mismatch", not "no more middleware". We need a good dblib, in the meantime you are on your own -- but SQL contamination is not unavoidabke, it's not because you are writing SQL by hand that it must be littered all over your whole codebase. You can and should segregate all db access in a separate namespace. Nothing new though. :-/ I'd like to point you to a cool lib. You still have to bridge the two worlds but it's easier than with OO because they are conceptually closer.

[Thorsten]

@cgrand thanks for your patience, now I'm able to better connect my OOP experiences to the Clojure world. So abstraction by layers of middleware is still a valid and useful concept in the Clojure world, and it might be even easier and more convenient without the impedence mismatch between (OO) application and (relational) database, but it simply does not exist yet, since Clojure is still a recent phenomenon.

[Thorsten]

@cgrand no, no misunderstanding, "relational modeling in pure Clojure (no db)" was part of my question - how to realize relational modeling with the Clojure language features and then how to persist the data-structures while abstracting the actual database-system away. (set=table, map=index) sounds very interesting, but I'am afraid I would need to see an example to really understand the idea. Could you provide a link to some related source code, or is this still some (secret) innovation in the making?

[Thorsten]

I found something interesting, a Clojure library for (the non-relational) Amazon Simple DB from Rich Hickey himself: github.com/richhickey/sdb/commit/…

[Aky]

+1 for "Thank God that the software-engineering people have not yet discovered functional programming." ;)

[Marcin]

OO is itself a way of trying to programme with types, so the approaches are not so different. The problem with OO designs usually seem to derive from people not knowing what they are doing.

[knb]

wayback.archive.org/web/jsp/…

[Svante]

There have been enough large scale systems been build with functional languages now. Even if there had not, this is not an argument at all.

[Hippias Minor]

Well, name some of them? I just know very few "Erlang" systems. [medium size] But Haskel? Clojure? Lisp?

[Hippias Minor]

And that [ writing big systems ] is the real argument. Because that is the test case. This test case show that if this functional style is usefull and can we do practical things with it in real world.

[Hippias Minor]

Finally, we need methodology when complexity of system getting large.So if anyone come with a real methodology, he-she should make her hand dirty with some systems which has big complexity. Otherwise it will be ivory tower paper based toy methodology

[Hippias Minor]

Lasly Erlang is not a pure functional language. And with a pure functional language like Haskel, you can do very limited things in real life.

[Svante]

First, "No one has done this before, so it is impossible" is not an argument. Second, "No one has done this before" is plain wrong.

[Hippias Minor]

Well, you should take classic logic course :-) . I said there is no enough experience in our industry with functional style. So, we are still in immature state to formalize a design strategy for functional style.Of course the more we implement our design with functional style, we will get more info and mature methodologies.

[Hippias Minor]

May be you have experience Svante, what is the biggest project in size you implement with a functional programming style so far?Or anybody you know. Like to hear your-her-his experince.

[Svante]

I personally know the programmers of two independent instances of medium to big e-commerce systems implemented in Lisp, and I know several more by name, and I know that there is more than what I know.

[Svante]

The funny thing about languages not anally "OOP" is that they often give you freedom from "design methodologoililogies", to think for yourself, and to cut your program in the most appropriate manner, instead of blindly following a set pattern and living with the bureaucratic boilerplate. Sorry, no 10-point 3-week course here.

[Hippias Minor]

I agree that we should stay away from "blindly following" set of rules or patterns and I also dislike the word "methodology". OOP and Functional styles are just tools to create solutions. Both have advantages and disadvantages. Sorry but functional programming is not a silver bullet. And programming styles are not "religious".

[Hippias Minor]

Medium to big e-commerce systems implemented in Lisp? Svante ever you try to read Lisp code more than 10 pages?You can write those systems in Fortran even in assembly langugage if you are "masochist". Sorry for your friends.:-)

[Hippias Minor]

And Lisp is not "pure functional". With pure function programming languages you can do very limited things in real life.In the old days there is even Lisp machines. Then they "gone".Nobody even remember Lisp Machines nowadays.

[Svante]

I have seen things you wouldn't believe.

[murtaza52]

what are the tools you are using to do BDD in clojure ?

[Marc]

I like Midje. It's up to date and very expressive. Check it out: github.com/marick/Midje

[V Krishan]

The link to the Northeastern page appears to be dead.

[Artyom Shalkhakov]

James, you are right, and I don't remember what was in there to fix it, unfortunately. I only know that HtDP authors went on to create Pyret language (and probably, are revising the 2nd edition of HtDP to use it instead of Racket, formerly PLT Scheme).

[Ashish Negi]

just to start with : this is storm github.com/apache/storm written mainly in clojure. for haskell github.com/jgm/pandoc pandoc.. i hope you would find them interesting.

[xtreak]

Correct link : web.archive.org/web/20120618115736/http://web.mac.com/…

[David Ongaro]

"That is the question"? Maybe if they will become mainstream is a question, but to ask if they will be used for big systems just shows a fundamental misunderstanding about what functional programming is. Functional programming is about writing big systems. For small systems it doesn't really matter what you use and it may be fine to conflate all concerns into stateful objects and deal with the aftermath later.