(Pure) Functional Programming Claims IRL

So, THIS happened:

– question from a young programmer

So, does functional programming stack up in the real world? In industry?

Yes. Check my linkin profile. I have been programming, in industry, as long as you have been alive.

Here are some (pure) functional programming examples to back up this claim, because academics can talk all they want, but they are not in there, in the trenches, with you where it counts.

I am, because I happened to have dug a few of those trenches. You're welcome.

Case study 1: ATS-L

Worked on a project in DHS called 'ATS' ('Automated Targeting System'). The existing system ATS-C was a 100,000-line Prolog behemoth that used pure dynamic types (no type hints, nor boxed types) and every rule started with an assert and ended with a retract. And 100,000 lines.

It was impossible to know what was going on in that system, without running the code in the debugger and pulling from the dynamic environment. Consequently, the ATS-C guy had (still has) job security. Not his aim, but that is a nice plus.

It took us 72-hours to go through every line of his code to correct the Int-rollover problem when the primary key exceeded two billion for the index.

So, I was called in to 'help.' HA! But then eventually I built ATS-L. I wrote it in 10,000 lines of purely functional Prolog (yes, that is possible to do, and remain authentic to logic programming in Prolog), so every rule called gave the same truth-verification from the same set of arguments, every time.

Shocker! I know.

I had the same level of functionality of ATS-C and handled 1,000x the number of transactions per hour. And as it was purely functional Prolog, I could reason about my program in the large and in the small. Importantly, so could others, as I passed on that work after maintaining it for three years.

In short: 1/10th the SLOC with the same level of functionality with increased real-time responsiveness and a vastly reduced level of maintenance.

Oh, and I also wrote 726 unit tests and put them on an automated midnight run, generating a report every single day. If my system broke, or something changed, I knew it, and management knew it when the report was automatically emailed to them.

Case Study 2: CDDS

Worked three years in Fannie Mae devising within a team an appraisal review process, CDDS. We had a good team of five engineers and I was given the 'Sales Comparison Approach' which had 600 elements out of 2,100 data elements in over 100 data tables, one of the tables ingested 100 million elements per month. All the elements were optional. All of them, so primary key dependencies were an ... interesting problem. The upshot was that Sales Comparison Approach was an impossible task to code, as we coded it in Java, of course.

What did I do? I coded it in Java.

After I implemented the Maybe type, then the Monad type-class ... in Java.

After I completed the system and tuned it, storing only the values that were present in the submitted forms, my manager reported up the chain that SCA and CDDS would have failed if I had not been there to implement it.

How did I implement it? In Java. I didn't use one for-loop and my if-statements were not there. I used the Maybe-Monad to model semi-determinism, lifting the present data to Just x and the absent data ('null') to Nothing, and then I executed action against the monadic data.

Simple. Provable. Implemented. Done.

Oh, and I had written 1,000 of the 1,100 unit test cases. SCA had 1,000 unit test cases, the rest of the system had a total of 100 unit test cases.

My code coverage was fiiiiiiine.

Case Study 3: Sunset Dates

This one was interesting.

I worked at Freddy Mac for a year, and they had a problem, and that problem was to calculate the sunset date for a mortgage based on the most recent date from one of possibly five indicators, that changed with each possible mortgage transaction.

Three different software teams tackled this problem over a period of six months and none of them implemented a system that passed UAT.

I sat down with the UATester and kept getting part of the story. I lifted our conversations up into the categorical domain, and then dropped that into a Java-implementation (I used both monads and comonads which I had implemented).

It took me two solid months working with this tester and a front-end developer, but we passed UAT and we got the customer and their SMA to sign off on it.

Three person team, purely functional programming ... in Java won that work where standard imperative approaches failed, over and over again.

Funny story. I was seriously asked on that project: "What's a tuple?"

Case Study 4: Dependency Graphs of Program Requirements ('TMQER')

I can't compare what I wrote, in Haskell, to an alternative system, because the alternative, traditional imperative approach was never essayed. We had a set of 521 requirements for a program with many (multiple) parent and child dependencies, so it wasn't a tree, it was a graph. So, I parsed the requirements document into a Haskell Data.Graph and provided not only a distance matrix, as requested (which is not what the customer wanted at all: it was just what they said and thought they wanted), but also clustering reports of which requirements were the 'heaviest' having the most dependencies and which requirements were show-stoppers to how many follow-on requirements.

Then I uploaded my Haskell Graph into Neo4J, making heavily-clustered requirements an obvious visual cue. And we won that contract.

The project wasn't attempted in Java. The project was attempted in R, and it couldn't be done. They estimated the graph manipulation algorithm would be 200-lines of code in R, that they couldn't get working.

With comonads, I did it in one line of Haskell. One line for a graph deforestation algorithm to get to the bare essentials of what was important to the project. Wanna see it?

How hard was that? In Haskell, a pure functional programming language, not hard at all.

Not only that, that we won a contract that our competing companies said was impossible, but our VP got wind of this and started vetting my tech to other companies.

We have a contract in the works, right now, using Haskell and Neo4J on AWS that is answering questions about fuzzy relations in social networks that a company that is expert in social engineering needs us to answer.

And I can answer these questions using graph theory and purely functional programming.

Case study 5: the one that got away

Oh, and then there was the one that got away. It had to do with a neural network I built in Mercury, a purely functional logic programming language with Prolog-like syntax that was able to classify images into 'interesting' and (mostly) 'not-interesting' but 'interesting' had very specific, different meanings, and it was able to classify these images, using a pulse-coupled neural network, in ways that eliminated 99% of waste images quickly so that analysts could concentrate on doing work, as opposed to sieving through the deluge of useless images to get the the ones they needed to see.

I build a working prototype and demoed it.

This had never been done before. Ever.

Then, a Big Six came in and said, 'we can do that for you with 250 programmers and Java' and stole the project. After ten years and billions of dollars, they were unable to reproduce my work.

Pure Functional Programming Claims IRL

So, let's do a real-money tally.

ATS-L in one month, in the three years I maintained it (it is still up and running ten years later, ladies and gentlemen) made $26 million dollars in seizures and rescued three teens being human-trafficked over the border.

CDDS has been in production since the year 2010 and has verified appraisals helping Fannie Mae to make 62 Billion dollars in net profit in one quarter the year it went live, actually contributing to the rescue of Fannie Mae from insolvency.

TMQER has rescued a government run program from failure that has the funding price-tag of over 100 Million dollars of Government (your) taxpayer (your) money. You're welcome.

Sunset dates I wish I had a dollar amount, but you can estimate for me: three teams of business analysts and software engineers over a six month period said it couldn't be done (or tried it and failed). I scrapped all that code, wrote the system from first principals (Category Theory) and got it working and approved in two months. You do the math.

... Oh, and then there's my current project. I might actually be able to own this thing. Hmmmm.

So, yes, Virginia,

1. there is a Santa Clause
2. those academics are actually onto something. (Pure) functional programming actually does matter. It actually does allow you to program better, faster and more cleanly, and with these enhanced skill-sets you become the one they turn to when other teams throw up their hands at an 'impossible' task. And then you deliver, ahead of expectations on both time to deliver and budget costs.

Hm.

Don't know; don't care: Whatever

The Maybe Monad type (covered in this blog in May) is a practical data type in Haskell and is used extensively. Since it is also a MonadPlus type, it is also immediately useful for logic programming, particularly of the semideterministic variety. Personal, I view Maybe as a second-order Boolean type, which, in itself, is a very powerful mode of expression, as George Boole demonstrated. Do yourself a favor, reread his works on algebra, or perhaps some musings from others, such as Dijkstra. Just as Donald Knuth showed that any n-tree could be transformed into an equivalent binary tree, and Paul Tarau put that to good, ahem, clause and effect, the Boolean algebra can model many other forms of algebras ... and does, for, after all, last I checked all my calculations are reduced to boolean representations (some call them binary digits).

Yes, Maybe's all well and good (and for the most part, it is — it's very well-suited to describe a large class of problems). But, as a dyed-in-the-wool logic programmer, Haskell has a bit of a nagging problem capturing the concept of logic variables ... that is, a thing that either may be grounded to a particular value (which Maybe already has when the instance is Just x) or may be free (which Maybe does not have). In short, the problem is with Nothing. And what is the problem? Values resolving to Nothing in a monadic computation, because they represent mzero, or failure, propagate throughout the entire (possibly chained) computation, forcing it to abort. Now, under the Maybe protocol, this is the desired result, but, when doing logic programming, it is often desirable to proceed with the computation until the value is grounded.

Now, deferred computation in Haskell is not a novel concept. In fact, there are several approaches to deferred, or nondeterministic, assignment, including my own unification recipe as well as the credit card transformation (which the author immediately disavows). The problem with these approaches is that they require resolution within that expression. What we need is a data type that captures succinctly this decided or undecided state. This we do with the Whatever data type:

data Whatever x = Only x | Anything

Just like Mabye, Whatever can be monadic:

instance Functor Whatever where
    fmap f (Only x) = Only (f x)
    fmap f Anything = Anything

instance Monad Whatever where
    return x = Only x
    Only x >>= f = f x
    Anything >>= f = Anything

You'll note that the monadic definition of Whatever is the same as Maybe, with the exception that Maybe defines fail on Nothing, whereas Whatever has no such semantics.

Even though Whatever is monadic, the interesting properties of this data type come to the fore in its more ordinary usage ...

instance Eq x ⇒ Eq (Whatever x) where
    Only x ≡ Only y = x ≡ y
    Anything ≡ _    = True
    _ ≡ Anything    = True

... and with that definition, simple logic puzzles, such as the following, can be constructed:

In a certain bank the positions of cashier, manager, and teller are held by Brown, Jones and Smith, though not necessarily respectively.

The teller, who was an only child, earns the least.
Smith, who married Brown's sister, earns more than the manager.

What position does each man fill?¹

An easy enough puzzle solution to construct in Prolog, I suppose, and now given the Whatever data type, easy enough in Haskell, too! Starting from the universe of pairs that contain the solution ...

data Man = Smith | Jones | Brown deriving (Eq, Show)
data Position = Cashier | Manager | Teller deriving (Eq, Show)
type Sibling = Bool
type Ans = (Position, Man)

universe :: [Ans]
universe = [(pos, man) | pos ← [Cashier, Manager, Teller],
                         man ← [Smith, Jones, Brown]]

... we restrict that universe under the constraint of the first rule ("The teller, who was an only child...") by applying "only child"ness to both the Teller and to the Man holding that Position (as obtained from the fact: "... Brown's sister ..."), but, importantly, abstaining from defining a sibling restriction on the other Positions ...

-- first rule definition: The teller must be an only child
sibling :: Position → Whatever Sibling
sibling Teller = Only False
sibling _      = Anything

-- fact: Brown has a sibling
hasSibling :: Man → Whatever Sibling
hasSibling Brown  = Only True
hasSibling _      = Anything

-- seed: the universe constrained by the sibling relation
seed :: [Ans]
seed = filter (λ(pos, man).sibling pos ≡ hasSibling man) universe

And, given that, we need define the rest of the rules. The first implied rule, that each Position is occupied by a different Man is straightforward when implemented by the choose monadic operator defined elsewhere, the other rule concerns the pecking order when it comes to earnings: "The teller ... earns the least" (earnings rule 1) and "Smith, ..., earns more than the manager." (earnings rule 2). This "earnings" predicate we implement monadically, to fit in the domain of choose ...

-- the earnings predicate, a suped-up guard
makesLessThan :: Ans → Ans → StateT [Ans] [] ()

-- earning rule 1: the teller makes less than the others
(Teller, _) `makesLessThan` _ = StateT $ λans. [((), ans)]
_ `makesLessThan` (Teller, _) = StateT $ λ_. []

-- and the general ordering of earnings, allowed as long as it's
-- different people and positions
(pos1, man1) `makesLessThan` (pos2, man2) = StateT $ λans.
        if pos1 ≡ pos2 ∨ man1 ≡ man2 then  []
        else [((), ans)]

... we then complete the earnings predicate in the solution definition:

rules :: StateT [Ans] [] [Ans]
rules = do teller@(Teller, man1) ← choose
           mgr@(Manager, man2) ← choose
           guard $ man1 ≠ man2
           cashier@(Cashier, man3) ← choose
           guard (man1 ≠ man3 ∧ man2 ≠ man3)

           -- we've extracted an unique person for each position,
           -- now we define earnings rule 2: 
           --      "Smith makes more than the manager"
           -- using my good-enough unification2 to find Smith

           let k = const3
           let smith = (second $ k Smith)∈[teller,mgr,cashier]
           mgr `makesLessThan` smith
           return [teller, mgr, cashier]

... and then to obtain the solution, we simply evaluate the rules over the seed:

evalStateT rules seed

The pivotal rôle that the Whatever data type is in the sibling relation (defined by the involuted darts sibling and hasSibling). We can abduce the derived fact that Brown is not an only child, which, with this fact reduces the universe, removing the possibility that Brown may be a Teller ...

universe \\ seed ≡ [(Teller,Brown)]

... but what about the other participants? For Jones, when we are doing the sibling/hasSibling involution, we don't know his familial status (we eventually follow a chain of reasoning that leads us to the knowledge that he is an only child) and, at that point in the reasoning we don't care. For Smith, we never have enough information derived from the problem to determine if he has siblings, and here again, we don't care. That is the power that the Whatever data type gives us,⁴ we may not have enough information reachable from the expression to compute the exact value in question, but we may proceed with the computation anyway. Unlike Maybe's resolution to one of the members of a type (Just x) or to no solution (Nothing), the Whatever data type allows the resolution (Only x), but it also allows the value to remain unresolved within the type constraint (Anything).⁵ So, I present to you, for your logic problem-solving pleasure, the Whatever data type.

---

Endnotes

1	Problem 1 from 101 Puzzles in Thought and Logic, by C. R. Wylie, Jr. Dover Publications, Inc. New York, NY, 1957.
2	f ∈ list = head [x|x ← list, f x ≡ x] When x is atomic, of course f ≡ id, but when x is a compound term, then there are many definitions for f for each data type of x that satisfy the equality f x ≡ x and that do not equate to id. We see one such example in the code above.
3	I really must define a library of combinators for Haskell, à la Smullyan's To Mock a Mockingbird, as I've done for Prolog.
4	This semantic is syntactically implement in Prolog as anonymous logic variables.
5	I find it ironic that Maybe says everything about the resolution of a value, but Whatever allows you to say Nothing about that value's resolution.

Choice with Monads: List, Maybe, Either

We've seen up to now what monads are and how they can be useful in simple ways, such as for heavy lifting on recursive addition. So, monads are useful for housekeeping when you have more work than a computer could handle in a straightforward manner. This work is called deterministic, meaning that the computation occurs in only one way. As we have seen, monads can be helpful with this kind of computation. But monads can be helpful with nondeterministic computations, or computations that proceed along multiple possible paths, as we shall see.

Haskell comes with three kinds of monads that have been used specifically for nondeterministic computation: the Maybe monad, the list data type and, a new one, the Either monad.

We saw the first one in the previous post: the Maybe monad. This monad type has two instances: Nothing and Just x (where x is the specific value of the computation). The Maybe monad is illustrated by the two dialogues below:

Scenario 1
Waiter:	How is the pork chop, can I get you anything to go with that?
Custamah:	Oh, Nothing for me, thanks.
Waiter:	Wonderful, enjoy your meal.
Scenario 2
Waiter:	How is the pork chop, can I get you anything to go with it?
Custamah:	Oh, Just a small bowl of applesauce, please?
Waiter:	Sure, I'll bring that right out.

The waiter in the above two scenarios doesn't know exactly what the customer will want, but that waiter is pretty sure the customer will ask for Nothing or for Just something, and these options describe the Maybe monad type.

Another example of this kind of monad is the list data type. But whereas the Maybe monad allows two options (the answer or failure), the list data type (a monad) allows multiple answers (including no answers, which is represented by the empty list). These kinds of monads form a protocol called the MonadPlus class, just as the more general monad data types form the more general protocol of the Monad class, and just like regular monads, conform to a set of laws.

First, let us specify and explain what the MonadPlus protocol is. All MonadPlus types must have the following two properties defined:

mzero :: m a — the base, or usually interpreted as fail, value; and,
mplus :: m a → m a → m a — a function that chooses a success value when offered two values

For the Maybe MonadPlus type the above properties are defined as follows:

mzero = Nothing
Nothing `mplus` b = b
a       `mplus` b = a

In other words, Nothing is the failure case, and mplus tries to choose a non-Nothing value (roughly: "If a is Nothing, pick b; otherwise pick a." Here's a question for you: what happens when both a and b are Nothing, and for what reason?) Note the interesting semantics of mplus — it is not at all addition, as we expect, for:

Just 3 `mplus` Just 4 = Just 3

Recall that if we wish to do monadic addition, we need to define such an operator.

madd :: (Monad m, Num a) ⇒ m a → m a → m a
madd = liftM2 (+)
Just 3 `madd` Just 4 = Just 7

So, now madd has the triple meaning here: it is not mplus (which is not addition), it is addition for monads containing numbers, and it either heightens awareness or annoys the cause of "MADD". Got all that?

The Maybe type has a special handler, called maybe. Its type signature is:

maybe :: b → (a → b) → Maybe a → b

What does this function do? Well, we've already seen it in action with the monadic Ackermann and Fibonacci solutions. One can read the arguments from right to left, to get the feel of an if-then-else: if the last argument is Just a, then pass a to the second argument (which is a function that converts an a to the proper return type); else execute the first argument. A very compact and useful function when working with Maybe types.

The second most commonly used data type used for non-deterministic computation is the list MonadPlus data type. It has an interesting variation from the Maybe definition:

mzero = []
mplus = (++)

In other words, the empty list ([]) is the base (failure) case, and mplus here actually is addition ('concatenation', to be technically correct); addition, that is, in the list-sense. But it all works out, particularly when it comes to the base cases, for:

[3] `mplus` [] = [3]
Just 3 `mplus` Nothing = Just 3

But, on the other hand, mplus is different when handling non-base cases for the Maybe and list monad types, for:

[3] `mplus` [4] = [3, 4]
Just 3 `mplus` Just 4 = Just 3

But this difference is consistent with the different types: the list monad allows for multiple solutions, whereas the Maybe monad allows only one.

The list data type has too many special functions associated with it to review in this post. I recommend a review of the Haskell online report to get a taste of list's rich functionality, and then read Eric Kidd's post on backtracking with monads for some insights into using list monads in nondeterministic programming.

The third data type that is used, albeit less frequently, for non-deterministic computation is the Either data type. It's structure is as follows:

data Either a b = Left a | Right b

The way Either operates is that it offers a mutually-exclusive choice. For example, little Isabel sits to my Left and her até Elena Marie sits to my Right, so at 4 p.m. I must choose Either one to serve tea first: Left Isabel or Right ElenaMarie.

The interesting distinction of the Either monad to MonadPlus types such as the list data type and the Maybe monad is that both options are weighed equally, or, more to the point, neither is considered to be the base case. This means that Either, qua Either, is not in the MonadPlus class. With this caveat, can the Either type be used for non-deterministic computation? Yes, absolutely!

Not only can the Either type be used in its basic monadic form, but it also can be coerced into the MonadPlus class. How? It's simple, really. By simply choosing one of the branches to be the base (the Haskell library designers chose Left), the Either type now conforms to that protocol. The convention assigns the error message (a String) to the Left and the value sought is assigned to the Right one. This rather reduces Either to a glorified, error-handling, Maybe, and that is how it is used in every-day Haskell code for the most part.

The Either monad also has a special handler, either, with the type signature of:

either :: (a → c) → (b → c) → Either a b → c

This function is in the same vein as the Maybe handler, but complicated by the fact that maybe has only one (success) type to handle, whereas this function has two possible types it deals with — either's type translates as: if the answer from the third argument (Either a b) is Left a, then feed a to the first argument (a function that converts the input value of type a to the output of type c), but if the answer from the third argument is of type Right b, then feed b to the second argument (a function that converts the input value of type b to the output of type c).

What we've seen in this entry is an introduction to the MonadPlus class and three examples of monads that allow for choice, Maybe, the list data type and Either, and saw an example for each which demonstrated their ability to code with choice.

The next entry will further explore the MonadPlus class and some of its powerful functions, such as msum and guard, and how the MonadPlus class allows us to code in a declarative nondeterministic style.

No "fib"bing; getting into the monad groove

The title is groan-inducing, as all my "jokes" are. I guarantee it: once you've finished reading this entry, reread the title, and you won't be able to stop from groaning.

The Fibonacci series goes as follows: 0,1,1,2,3,5,8,13..., or put another way, the current number is obtained by adding the previous two numbers. It is useful for many things, as its limit is the golden ratio, found in nature (the spiral of some crustaceans and the population growth of rabbits [they must be stopped!]) and in artifice (windows, painting, doors, buildings follow the width and height of this ratio)).

Any fibonacci number can be easily computed from the following formula ...

fib :: Integer → Integer
fib n | n ≡ 0     = 0
      | n ≡ 1     = 1
      | otherwise = fib (n-1) + fib (n-2)

... that is, easily computed if this world were purely mathematical, including the caveat that any computable function could be instantly computed. Run on a computer, fib 25 slows noticeably and fib 50 may as well describe the halting problem, because I wasn't going to wait around for it to terminate.

Note the similarity between the computation of the Fibonacci series to the computation of the Ackermann table. They are not the same kind of problem, mind you, as the Ackermann is not primitively recursive; the Fibonacci is "only" doubly (branching) recursive. But they are similar enough in that they can be solved in similar ways. Given that the current Fibonacci number is the sum of the previous two Fibonacci numbers, we need only a (reversed) list to memoize the previous results, so the above sequence becomes:

[..., 13, 8, 5, 3, 2, 1, 1, 0]

and the "next" Fibonacci number would be simply the first two elements of this list (21, in this case). But how do we know where we are in the sequence? Easy: the length of this list tells us where we are, and in this case, the list has 8 elements, meaning the "next" Fib is 9th in the sequence.

So, turning to monads with this list structure for memoization, the code falls out as follows:

fib :: Int → FibS
fib n = get >>= λmem . maybe (fib' n >>= update)
                             return
                             (gimme mem n)

So, fib is now simply a decision: "Do I have the fib requested in the list?" "Yes: gimme it and return it" or "No: compute it and then update the list"

The list is a very slight variation on a regular list type, as we choose to carry around its length (as opposed to recomputing it at each iteration), and we lift this new data type into the State monad (as we did with the Map data type for our Ackermann monad optimization):

data Mem = Mem [Integer] Int
type FibS = State Mem Integer

The actual computation function is lifted into the monadic form with very little variation ...

fib' :: Int → FibS
fib' n | n ≡ 0     = return 0
       | n ≡ 1     = return 1
       | otherwise = liftM2 (+) (fib (n - 1)) (fib (n - 2))

... where monadic addition, liftM2 (+), replaces addition in the usual sense (recall the spot of bother we had "adding" Thing One to Thing Two), and where the plain numbers are lifted into the monad with return. In brief, the substance is now monadic but the structure is the same as our original, plain, fib.

The other housekeeping functions are new for the monadic solution, but what one would expect. The update follows in the same vein as the one for the ackermann monad:

update :: Integer → FibS
update n = do (Mem lst len) ← get
              put (Mem (n:lst) (len + 1))
              return n

An interpretation of the update function is that it is the identity function with the side-effect that it remembers the result that it returns.

The only other function is the self-describing gimme which retrieves a previously-computed fibonacci number from memory:

gimme :: Mem → Int → Maybe Integer
gimme (Mem (h:t) len) n | len ≡ n   = Just h
                        | len > n   = let x = (len - 1) - n
                                      in Just (t !! x)
                        | otherwise = Nothing

This gimme function uses the Maybe monad and its functionality, saying "If I have the value already computed [If the list length is equal to or greater than the requested index], then return Just that value; otherwise I've got Nothing, so you need to compute that value."

In summary, we've decorated the naïve fibonacci algorithm with some memory and three new functions (one manager and two support functions). What is the payoff?

Ready> fib 1500
[no delay]
135511256685631019516369368671484083777860107124184972421335
431532214873108735287506122593540357172653003737788143473202
576992570823565500453499141029242495959974839822286992875272
419318113250950996424476212422002092544399201969604653214384
983053458933789325853933815390935494792961948008381459961871
22583354898000

Ready> fib 50000
[4 second delay]
[10615 digits]

Ready> fib 60000
[2.5 second delay]
*** Exception: stack overflow

These results are a great step forward over the naïve fib implementation (which essentially froze at fib 50) and even memoized implementation reported elsewhere (which ran out of memory after fib 1450).

Huzzah! then for efficient program representation in Haskell and monadic code.