Introduction to state monads

I went to my first Zurich FSharp meeting the other day and made a presentation on how to program with state monads in F#.

The presentation is designed to pull you off the ground, to a higher order programming style, using the state and maybe monad as stepping stones. It finishes with stateful lifting.

Here is a link to a slightly improved version: youtube .

Link to sources are below but I would recommend that if you really do not know this type of programming and want to learn, then you should type it back in and allow yourself some creative liberty. This is usually a much better way to learn, than to just copy code!

You can watch it here if you want:

ModularStateMonadsInFSharp.pdf
XState1.fs
XState2.fs
Script.fsx

From Chinese famines to agile

A recent economist reviews a book on the "The Great Chinese Famine 1958-1962" and writes the following:

"The Great Leap Forward was the high point of ignorant Maoist folly. Chairman Mao said in 1957 that China could well overtake the industrial output of Britain within 15 years. People left the fields to build backyard furnaces in which pots and pans were melted down to produce steel. The end product was unusable. As farmers abandoned the land, their commune leaders reported hugely exaggerated grain output to show their ideological fervour. The state took its share on the basis of these inflated figures and villagers were left with little or nothing to eat. When they complained, they were labelled counter-revolutionary and punished severely. As the cadres feasted, the people starved. Mr Yang calculates that about 36m died as a result."

When I read this, I could not help thinking that too many software development teams are starved from doing the right thing because they have promised, or someone promised for them, something they cannot deliver. The result and its dynamics are not very different from the story above, let me paraphrase this as follows:
Someone with authority decides that X will be developed in Y amount of time. No one in development dares to contradict the order and work is started. Given the predefined schedule, no solid analysis can be made (aka harvest sowed) but more importantly little effort is made to make the project "self-consistent" across all its requirements, for example that it is defined to be usable from day one (aka making sure the village stays sustainable). As there is not enough resources "to go around" (aka not enough food for all), there is no point thinking about "fixing" the problems as they accumulate (aka farms are deserted, crops rot, nothing is done to fix this), and so developer will "just write code" with the foremost goal of fulfill the initial request (aka pots and pans will be melted) but as design and cohesive goals are lacking, as well as the developer team's understanding of what they are really trying to deliver (aka farmers do not know how to work steel), the effort to fit things together to cover the scope the project just grows and grows... Upon failing to deliver, and there will be a few failed deliveries, moral will plummet, as will productivity, key people may leave (aka farmers and their family starve to death). In the end mush pain and suffering will happen before something is done. One option is to pull the plug on the project, the other is to go agile with it: throw away the promised time line, build a backlog, see what you can do, at which point you can still decide to pull the plug.

This, maybe bleak, example of failure does lead us to an observation: capitalism does put pressure on management to avoid the scenario above. The problem is that many managers, even under pressure to make a profit, do not know how to avoid this scenario! They do not understand how projects differ, like everyone else they know best how to do what they did before. Therefore from time to time, you will see them kicking off projects that ultimately will be disastrous.

Agile does not keep you from making mistakes, but applied well, it will alert you of your follies (or others people follies) before they destroy you. Understanding how different types of projects need different style of leadership is helpful (see blog entry on greenfield projects, and on legacy projects).

Functional meets Fortran

I decided my life needed a little bit more math, and so to decided to add a few differential equations in some F# code. Math in code means applied math and lots of arrays, but arrays are a pain functional style. So heres my appoach.

I have written many numerial applications, mostly in C++, yet also some in Fortran. I mention Fortran because it has the notion of equivalence, where you can map arrays on to each other.  Equivalence is like C unions for array and there to  reminds us is that arrays do not need to be managed as dynamic memory.

A functional style of programming is a lot about preserving your invariants with immutability, yet immutable vectors are not a solution (yet). Still, numerical code has its own invariants, and therefore some immutability is possible, and should be exploited to write robust code.  In my case, I have vectors and matrices; Their sizes are invariant, and so is the structure of the matrices, they have lots of zeros, they are sparse.  The approach is then to specialize a state monad to maintain size, and structure in an immutable manner, while allocating mutable vectors only within the core of the numerical engine.

Long ago I wrote an matrix assembly algorithm. You can see it as a sparse matrix structure inference code. It was really pretty simple: the final matrix is an assembly of many small sparse matrices, finding the final structure can be seen as solving a set of matrix structure equations, the algorithm defines an order of traversal for all this matrix points and then proceeds to "crawl" across all matrices at once, working out all the local structures. In a functional style of programming, I can use the same newVar like concept you would find in a constraint or inference solver, extend it with an equivalent newEq, to build a monadic environment to support my numerical code. The result is that "application code" just uses variable and defines equations, these are then assembled and only later does the code allocate just a few very large arrays to store the real data associated to the problem

This approach is "easy" because all invariants are built first and then used. Much modern applied math depends on hieararchical and adaptive grids. Hierarchy is probably easy to bring in to a functional style, adaptive grids maybe less obvious.