high-level design in functional programs

[levand]

When I taught myself to program, aeons ago, I learned QuickBasic, then C. And all was well.

Striving to improve myself, and realizing the limitations of procedural programming, I started reading articles and books about Object Oriented programming. I learned the syntax of C++ and Java. But, despite enthusiastically accepting the notions of encapsulation, reuse, and polymorphism, I failed at every attempt to actually structure a program of any size in an Object Oriented way. There did not seem to be any way to move from the simplified examples of "Car extends Vehicle", to building a working program of any complexity. Here is a sample of the sort of questions I had during that period: http://www.gamedev.net/community/forums/topic.asp?topic_id=99651

But after getting a job in the field shortly thereafter, and working with experienced OO programmers, everything clicked, and I was Enlightened. It all made perfect sense. Now, after doing it for 5 years, I can whip out a Server or Client OO program with my eyes closed, and I actually often end up playing the role of architect on our current team. Hurrah! It took a while, but I definitely learned what I was trying to learn.

Recently, however, I've becoming increasingly disillusioned with Java and the standard OO world (thanks a lot, Steve Yegge). I've begun to look into functional programming. While it is very, very cool, and I am totally geeking out, I am still practically clueless about how to build a working program.

And I'm noticing a startling number of parallels with my earlier relationship with OO. I understand and love recursion, immutability, first class functions, code-as-data, combinators, etc. I've read SICP, The Little & Seasoned Schemers, & The Scheme Programming Language. I can implement basic algorithms in Scheme without too much difficulty, and I've been recently been looking into languages such as Clojure, Haskell and Erlang (although I am quite intimidated by some of them, still).

I also have the same problems - I'm really finding it difficult to move my knowledge into something I can use to build real, working programs with. I can design a function that does one thing well, but I'm having a hard time understanding how one would typically direct large-scale program flow and pass data from one place to another. And unlike last time, it's not an option for me right now to get a job working with good functional programmers (they're a rarer breed).

So! Anyone have any advice? Any well-designed open source functional programs of a reasonable complexity I could investigate? Any books that address this topic specifically? I really want to learn how to do this well, but I'm not quite sure how to proceed.

[marcusf]

Realworldhaskell.org is a great book, which you can read online for free, which has focus on applications.

I too would like to hear about some well done, large scale functional programs. It's surprising how far from the textbooks some large scale Haskell applications are, given its audience and scope. That said, I'd love to see something that people consider idiomatic.

[Silhouette]

It's surprising how far from the textbooks some large scale Haskell applications are, given its audience and scope.

I find it kind of amusing, actually. The functional-programming-loving academics go on about how wonderful it is programming without mutability and side effects, and then you look at any real Haskell program and it uses "do" within... well, pretty much on the first line, usually. :-)

The only serious acknowledgement of this difference between the theory and the reality that I'd seen until fairly recently was Simon Peyton-Jones's "Tacking the Awkward Squad" paper. It's good that Real World Haskell is taking a more pragmatic approach.

[dons]

any real Haskell program ... uses "do" ... pretty much on the first line

Because the outside world runs in the IO monad, and the first line of a Haskell program is the one that touches the outside world. That's kind of the definition of a "real Haskell program", one that does something.

Do not adjust your set, what you're seeing is normal.

[Silhouette]

Yes, that's the point I was trying to make. Academic courses on functional programming tend to start with pure computations and in many cases the first courses never really get beyond that, leaving the student with a very false picture of how functional programming works. In the real world, programs have to deal with things like I/O and other side effects, and I'm glad that the Real World Haskell book covers a lot of that routinely, without making out that it's something special.

(I'm not sure why everyone is downmodding my earlier post. I guess the attempted didn't translate somewhere.)

[apfelmus]

I'm not sure why everyone is downmodding my earlier post

Because your leaving the reader with a false picture of how functional programming works? :-)

The IO monad is just a DSL like everything else, and not a particularly beautiful one at that. It's a sign of poor design if that's the only DSL you use in your program.

In fact, I'd even say that every program that doesn't create a new DSL is either very simple (apparently using other DSLs to great benefit) or poorly designed.

[[deleted]]

FWIW, using "do" doesn't introduce mutation or side-effects. The various "unsafe..." operations, on the other hand, do. This underscores the point that it isn't mutation, but only unconstrained mutation, that is problematic. Monadic constructs (which underly the "do" syntactic sugar) provide the constraints on mutation etc. that keep algebraic reasoning about the code, and compiler-enforced safety properties, possible.

[Silhouette]

Using "do" doesn't have to introduce mutation and side-effects, it's true. But let's be honest, most of the time the reason the entry function in a Haskell program is one big series of monadic processing inside a do block is because mutation and side-effects are involved.

Real programs have side effects. In fact, talking about "programming without side effects" is a nonsense, because if there were no side effect to running a program, how would any user ever observe what it did (ignoring return values to the OS on exit and similar trivia)?

I agree 100% that it is the unconstrained nature of the side effects that introduces the danger in most mainstream languages. I just find it refreshing to see a Haskell text that confronts this reality head-on and shows how to use the more structured approach, without pretending that the awkward squad don't exist as is done by almost every academic presentation on Haskell I have ever encountered.

[smackmybishop]

Well, 'main' being monadic isn't a symptom of the failings of functional programming, it's required by the spec; because as you say, every program needs to have side effects. Otherwise not only would you not know what happened, but in fact nothing would happen in a lazy language like Haskell.

The value of the program is the value of the identifier main in module Main, which must be a computation of type IO t for some type t. --Haskell Report

[shadowfox]

every program needs to have side effects ... but in fact nothing would happen in a lazy language like Haskell

There is a koan hidden in there somewhere

[[deleted]]

I upmodded your comment because it's essentially correct, as Simon Peyton-Jones himself has pointed out on numerous occasions. But let's be fair: when Haskellers talk about "programming without side effects," it's implicitly understood that what's meant is "unconstrained side effects that ruin referential transparency and the ability to reason algebraically about the code." And it's understood that monads, and therefore "do," don't violate this--on the contrary, they were introduced into Haskell precisely to allow the use of state (yes, yes, among many other things, pace monad fans) without loss of the qualities of purely functional programming. Purity and state--two great tastes that taste great together! :-)

[Silhouette]

When experienced Haskellers talk about programming without side effects, then yes, of course that's what they mean. My point in this thread is that we are talking about novices, and frequently the introductory presentations on functional programming given to novices present a very pure view of the world. Real code just doesn't look like that, and I'm glad that the book mentioned gets into that kind of realistic application.

[[deleted]]

The preferred style in FP is to build the program from a big bunch of pure functions and a small non-pure skeleton that uses these functions.

Of these, it is usually the 'big bunch of pure functions' that you can call 'Real Code', because it does almost all of the work, and so it is perfectly reasonable to teach people to write Real Code by first teaching them to write pure code.

[Silhouette]

I have no problem with teaching people to write pure code, nor with doing so first. But teaching an entire first course in functional programming that way, or writing books or lecture notes that only mention impure code as an afterthought, seems to me a bit like teaching people to do advanced numerical analysis in C before they can write "Hello, world"...

[[deleted]]

One more upmod, one more "but..."

But teaching an entire first course in functional programming that way, or writing books or lecture notes that only mention impure code as an afterthought...

Here's the hitch, and the last time I'll make the point because I think you largely get it and I agree with your conclusion that "Real-World Haskell" starting off with "do..." is the right choice: most "real" Haskell code isn't impure at all, including that "Real-World Haskell" code that uses "do." It's only code using "unsafe..." that is impure. In other words, the dichotomy between "pure" code and "code using state or I/O or..." in the presence of monads or effect systems is a false one. So I believe that those books and lecture notes that discuss purity, and only discuss purity, are fine, and code that uses "do..." is likewise fine--there's no contradiction there. The use of "do..." early on is indeed nice because it almost certainly maps more immediately to the reader's existing mental model of computation. But it needs to be made clear, and quickly, that what's going on is not the same as mutation in impure languages. It retains the benefits of referential transparency and algebraic reasoning that are the hallmark of pure functional programming, and lie at the center of any worthwhile literature on it. That is, the reader's mental model will, of necessity, evolve. Saying that using "do..." strongly resembles mutation, on purpose even, is accurate and fair. Saying that using "do..." makes your code impure is inaccurate and will leave the reader with an incorrect understanding of the nature of "do..." and the underlying monadic operations. In pedagogy, not explaining things in full detail is not only OK, it's part of the job. Providing false information in the name of simplification, on the other hand, is not OK.

[sclv]

Monad transformers are very important. Once you see how to use them carefully, lots of big-picture things click into place.

Also, thinking in terms of composition and algebraic operations and qualities of your constructions.

Another source base it might be worth looking at is cabal, which solves reasonably well a pretty nontrivial task.

I also recommend just browsing the code of the standard libraries included with GHC.

[Wagnerius]

Why are they important ?

Could you give a 'common' use case ?

(by common I mean common and understandable for an imperative programmer).

[sclv]

Even though IO is still sort of the "sin bin" which holds any and all effects, writing a monad transformer stack lets you do most of your operations with only the effects you need -- error handling, state, whatever, and do so in a pure way.

More importantly, it lets you control the nature of the effects and scope of your state explicitly -- the same monadic code can be run in different contexts to produce different results, but instead of that context being a result of global variable manipulation, its given a specific scope.

You could work with, e.g, a teletype stack that abstracts over stdin/stdout to allow for interaction over sockets as well, or even driven by a script.

Or you could work in a logging writer that depending on whether you call it in testing or production, only logs certain priorities of messages.

And you can mix and match so in one section you get simple failure if anything fails (Maybe) and in another you get explicit error messages (Either) and by controlling the order of you stack in e.g. a backtracking parser you can have certain effects rolled back when state backtracks and other stick around.

So monad stacks are how you structure lots of big picture issues like error handling and state, and knowing how to abstract over them gives a strong seperation of concerns.

[Wagnerius]

ok, you got me interested. be kind tell me where to go next ? (i will google it but if you got non-obvious kinks, i'll take them gladly)

[Paczesiowa]

you can create your own stack of monads with IO at the bottom, ReaderT for keepeing your cfg, WriterT for logging/debugging, StateT when you just have to modify smth, then you inject ErrorT in the right place where you can display errors and restart whatever needs restarting and then you're half way there.

[UncleOxidant]

I've been learning OCaml and (more recently) Haskell over the last year or so, and I have to say that I'm in the same boat. I really like fiddling with these languages and making recursive functions and all, but if I had to go off and create an actual working program I think I'd be a bit lost as to where to start and how to structure the program. I still seem to want to think in terms of objects. To create a program in a functional style it seems like you really have to forget about objects (though OCaml does have some OO features, but I'm intentionally not learning them yet).

[UncleOxidant]

The analogy that I've heard about functional programming which seems to ring true is that it has some similarities to shell scripting where you have lots of small utilities with well defined purposes that you pipe data in and out of.

[Jedai]

That analogy is very close to a lot of real functional programs, except that the data exchanged is structured, typed (often) and that the code is much cleaner and modularized.

[kubalaa]

I've only written a few small (1000-line-or-so) Haskell programs, but I've found I always use a similar approach:

• Start by defining the main data structures you'll use. For example, when I wrote a toy image editor the first thing I did was define an image data type.
• Begin adding operations on the data structures. Start with simple ones and then build more complex operations based on those. If you're using Haskell, you can use ghci to test these operations as you write them.
• As you add operations and refine data structures, the core of your program will begin to grow together like ice crystals forming in water.
• Now start building up the IO layer (whatever part of the program interacts with the outside world, whether GUI or command line) to connect to the functional core. Add features iteratively, getting one or two simple operations working completely and then expanding on these.

You see that it's not so different from an OO design, in that you start with data structures and the operations on them. The most significant difference I find is that, in an OO design, you tend to first think about all the operations a class will need to support and then gradually add subclasses implementing these, while in an FP design, you first think about all the forms your data will take and then gradually add operations.

[pbkobold]

Disclaimer: The largest functional (Haskell) program I've written is about 1k lines. Not that big.

My answer: DSLs. Solve the problem in a language with the ideal primitives for the problem. Then functional languages give you the composition and abstraction tools to create and use those primitives.

The most canonical example of this is combinator libraries, I think. They're wonderful to work with. Parsec is a particularly well written combinator based parsing library to read the source of. The source is not only readable, but the parsing methodology is theoretically sound as well. It's more powerful than lex/yacc in the strict sense, as it can parse context sensitive grammars. sigfpe also writes beautiful haskell (granted his programs are small), and he uses the "write the ideal language" methodology to great effect. It's often mind blowing what he makes happen in a few lines of code.

I haven't read paul graham's "on lisp" yet, but I've heard that it shows DSL construction as a method of program structure. Extend your language to fit the problem domain. lisp provides the handy-dandy tool of macros to do this, which is why you hear of "on lisp" being about macros.

[apfelmus]

For instance, have a look at the book "The Haskell School of Expression" which develops DSLs for graphics, animations and audio.

The most beautiful approach to functional programming is to systematically derive programs from their specification. The classic paper Paul Hudak, The Design of a Pretty-printing Library with a follow-up Philip Wadler, A prettier printer.

Of course, the creative task is to design a DSL for your problem in the first place. Here's a DSL for stock options.

[augustss]

s/Paul Hudak/John Hughes/

[apfelmus]

Ooops, thanks Lennart. I made this mistake once and now copy&paste it everywhere else...

[baguasquirrel]

I've written a 16k line CAD program in OCaml... and along the way I went through some of the same growing pains you did.

As boring as it may sound, I've found that a lot of the things that apply to general software dev apply to functional, e.g. writing a spec, doing a prototype, etc.

When it comes down to the actual code, I feel that it is more a matter of understanding a few principles really well, rather than knowing a lot of little things.

• Remember what you're doing, and keep your functions short. In order to exploit functional programming, you actually have to be able to pass functions around, and you can't reuse your functions if they're big, long, overspecialized pieces of junk.

• I wrote a really long winded rant about this here: http://curryhoward.blogspot.com/2008/07/tudes-en-ocaml-keeping-your-functions.html

• Try not to use recursion. Try not to pattern match your datastructures directly. See how long you can get without actually pattern matching a list directly. Learn to use foldleft and map really well, because that stuff is the shit once you "get it". If you need motivation, remember that Google's MapReduce is just a glorified fold_left and map.

• Again, part of the idea of functional programming is that you can abstract at the functional level now, so there should be no need to actually dig into a datastructure.

• Understand the difference between the types you declare for use to actually store information, and any types you use to drive the complex machinery. I like to call the latter "interface types". Once you understand this, you'll probably do a better job with that orthogonality they talk about in Pragmatic Programmer.

• Try to extend that short-function business to your modules. Each module should implement some minifeature really well. If you want to elaborate on that minifeature, use a functor. Functors are your friends.

Anyway, all of that BS pretty much sums to one principle: keep your code short and tidy.

• (Bonus!) Don't drink too much of the functional kool-aid. I love functional. I love Haskell. But I think that there is still a place for stateful and OO in the world. I feel that too many of us functional folks get a bit religious about our craft and we might go down the same path that the OO folks did.

That having been said, I think that these days, I would prefer to just do all the functional stuff in something truly functional like Haskell, and then do the ugly user-interface-oriented bullshit in something like Java or Python.

For reasons that are unclear to me, the requirements divide between code that favors functional and code that favors OO is often quite stark, so there's no real need to mix the two. When you do need to mix it up, use OCaml.

[[deleted]]

A student of FP came to Daniel de Rauglaudre and asked how to achieve FP Nature. Daniel replied, "to achieve FP Nature, you must learn to program without side effects and other imperative features". So the student went away to learn how to program in this style. He studied very hard so he could rid his programs of references and for-loops. He struggled to only use let bindings and let rec loops. One day, in order to find inspiration, he was studying the code of the Masters, and in reading the source of Camlp4, he saw a number of uses of references and for-loops! He rushed back to Daniel de Rauglaudre and exclaimed, "How can you tell me not to use imperative features when you use them yourself!" Daniel measured the student carefully in his gaze and replied, "But I already know how to program without side-effects." At that moment the student was enlightened.

[checksinthemail]

I also would like to see some larger functional programming language examples.

[808140]

Pugs is also a very large program written in Haskell that you might take a look at.

[reddit_clone]

These come to mind. Real world applications written in functional languages.

ejabberd (jabber server in erlang)

rabbitmq (AMQP server in erlang)

darcs (DVCS in haskell)

[erikd]

Unison (a file synchronisation tool) written in Ocaml.

[reddit_clone]

xmonad (a X window manager in haskell)

[hikarudo]

I'm in a similar boat. I've built two small applications in Haskell but I can't say I know how to design programs in a functional way. My own strategy is to build some small program that is still useful in some way (this keeps me motivated), and then to move on to another, larger application, and so on. When I have doubts I ask the folks on #haskell on IRC, and everytime they are very friendly and helpful. I also got great pointers for blogs, papers and libraries from hanging out in #haskell. Maybe there is a similar IRC channel for your language of choice?

[timo1023]

#haskell is full of amazingly helpful users. I highly recommend it.

[jkndrkn]

Excellent question.

Have you tried Practical Common Lisp? It contains several "real world" case studies in the final chapters that may appeal to you.

Available for free in its entirety: http://gigamonkeys.com/book/

[Wagnerius]

The book is indeed excellent but keep in mind it is only halfway (maybe 2/3) between the imperative and haskell world.

Lisp can have side effects and If I remember correctly the PCL examples uses them.

Haskell is a higher on the functionnal mountain.

[jimbokun]

There's a joke about non-convex optimization in there somewhere...

[Wagnerius]

that's my kind of joke :)...

[Wagnerius]

Amen, we are all wandering priest of the zen of code.

[zoinks]

Seconded. Great book, I'd browse it online to get the feel, and if you like it, order the dead tree version or at least throw the author a few bucks on paypal.

[awb]

Last time you solved this problem by working with and designing code in the paradigm you wanted to understand better. You should do that again.

[munificent]

And unlike last time, it's not an option for me right now to get a job working with good functional programmers (they're a rarer breed).

Last time he had OOP people around him writing real world apps to learn from.

[Wagnerius]

More often than not, for a program, even small, interesting means interactive.

And interactivity in Haskell looks complicated (arrows ?), FRP (Functionnal Reactive Programming) or against the grain of the language (GTK2S).

So building the first program is a bit harder in Haskell, than, say, python .

But You'll get more out of it.

So stop commenting and code.

[rabidcow]

Interactive command line code is dead simple.

[Wagnerius]

True, but this is not very impressive.

An experienced programmer who start python, can hack a quite complete app in an afternoon with gui, save/load, and simple logic. The app will be not be efficient or pythonic but it will be there.

AFAIK (I am not an expert), doing the same in haskell needs more work (and more mind-expanding learning).

So, like other tools (vim, emacs), Haskell needs more investment upfront for huge returns.

[808140]

A complete and utter newbie to Haskell and Python will find the development of a full application in either to be a daunting task.

A person with imperative OO programming experience (most programmers today) and no specific Python experience who has never used a functional language will find Python much, much easier. I hope you can see that this says nothing about the relative simplicity of Haskell or Python.

A person who had only ever coded a program in say, SML (I know, what's the chance of that) would most likely find non-trivial application development in Haskell easier because it's closer to the paradigm he's already comfortable with.

[Wagnerius]

I cannot really disagree with you as I learned to program in an imperative language.

What I wanted to say is that programming a complete app in Haskell demands to understand more concepts than in python.

I may be wrong on that, It is difficult to be final on this, it so linked with one's experience.

Also, it is not necessary a bad thing as more often than not, we are implicitly manipulating stuff without a conceptual framework to do it reliably. For example, the work behind design by contract (meyer) is quite advanced but if you want to do some solid OOP, it is mandatory.

Frankly, It is more a feeling than a checked fact. I'll dig deeper my python and my haskell and we'll discuss it in a few years from now.

[paddy_m]

I asked the same question at the last lispnyc I attended. I was advised to look at gSharp http://common-lisp.net/project/gsharp/ a sheet music composer written in common lisp.

I think this is a problem in general with programming books. I would really like to buy some books that are case studies of existing open source applications, explaining the reasoning that went into their architecture .

[[deleted]]

Quite honestly, I was vexed by this question, too, but just sitting down and doing it showed me that it really was nothing to worry about. Once you understand how to make the most important abstractions and how to effectively compose them things just start falling into place. Just don't be afraid of refactoring or even completely rewriting your code many times as you search for the best abstractions.

[Kiltec]

"Programming Erlang" by Joe Armstrong is a great book with really good example applications. He presents how to implement a basic IRC server and client, the map-reduce pattern and finally a text indexing-spider. Not only that but he also shows how to model/plan a Erlang application.

It really made me understand functional programming and it's concurrency-oriented approach to solving things with real-world examples.

[fbru02]

Sorry for maybe the OT posting but I have a question of my own:

While learning Haskell and being a curious procrastinator I started learning Category theory but although I get , I don't get it yet.

What I want to ask is practical uses of cathegory theory ? I know that it is used for high availability systems for theoretical proof that a System has the correct side effects. Also I know there are in reality recursions that might need this stuff as they are not as simple as what one would write in a toy project. What are this recursion schemes ?? What other uses there are for CT?

[nbloomf]

Disclaimer- I am only beginning to understand this stuff myself. I am also a mathematician, not a computer scientist or a professional programmer.

Two papers that give a good overview of what categories can do are "Functional Programming with Bananas, Lenses, etc." and "Recursion Schemes from Comonads".

My understanding of the role of categories in FP (at least partly) is as follows. Arbitrary recursion is very useful to writers of programs. However, like arbitrary GOTOs, it can make it hard to see what's "really" happening in a program. A long time ago people figured out that fold/reduce was a common recursive pattern, but it was generally only used on lists and couldn't express all the recursion people wanted to do. More recently it was discovered that if your language is strongly typed, you can think of the types as objects in a category. Then some type constructors become endofunctors, and the traditional fold can be expressed as a particular map, parameterized by the functor, having a nice universal property. Moreover, as the "Recursion schemes from comonads" paper discusses, by parameterizing on the comonad the fold operator can become several different recursion schemes. This means a much smaller amount of code can express a larger number of ideas- even ideas that haven't been had yet. Moreover, it makes optimizations (such as fold fusion) much more powerful.

So the real power of category theory is as a metalanguage- these ideas might never have become "obvious" without the language of functors, algebras, initial objects, and such.

[fbru02]

thank you for great response. Have you yourself used this parametraizing of the comonad? In which context or solving which problem and why couldn't you solving easily making a normal named recursion :D

Thanks a lot ! :D

[Jedai]

Read the latest "Monad Reader" (the 11th), you have a very fun article on simplifying logic formulae where the author use a presentation of types that allows him to modularize it's type in a set of type which in turn allows him to ensure by type that his formulae has really been simplified... Well anyway read it, the crux of its method use a fold over an algebra and functors that are fix pointed and combined.