'List' leads off with the letter 'Lambda' (λ)

I was revisiting the Project Euler problems recently, and one of the problems addressed lexicographic permutations.

Well, problem solved if you're using C++ or other languages that have lexicographic_permutation packaged with their standard library set. Some languages do and some don't, but that discussion is not à propos to this article, nor even what lexicographic permutations are or how to go about getting to them.¹

But something common enough did come up in the solving of that problem, which is the question of appending to the end of lists effectively.

Now, I have a prejudice: I love lists, and by that I mean to say is that in more than a few functional and logical programming languages, the List Data Structure (uttered with reverence, and with not even (barely) a hint of mocking) provides a facility for grouping and then operating on sets of objects that I find unparalleled in other programming languages and paradigms. I can, for example, in Haskell create a list simply by typing [0..9] or ["Mary", "Sue", "Bob"], and if I'm feeling old-fashioned and gutsy, I can iterate through those lists inductively with a:

doSomething [] = []
doSomething (h:t) = f h : doSomething t

Or if I wish to embrace the modern era of programming (like, oh, since the 1970ish-es),² I can use map or fold to go anywhere I want to with a list. I mean, come on! fold is, after all, the 'program transformer function.' If I don't like my list as it is now (or if I don't even like it being a list at all), I just fold over it until it's exactly how I want it to be.

Like the above function, it's really just a specialization of map, isn't it?

map _ [] = []
map f (h:t) = f h : map f t

And map is just a specialization of fold, right?

foldr ((:) . f) [] ≡ map f

So, yeah, lists rock my world.

But, you complain, I know language X [yes, the great language (flame-)war, with endless debates in the imperial senate, continues] and language X has lists and map, so what's the big deal?

The big deal is this: have you ever tried to construct a list in language X? Is it easy as the example I provided above?

No, but ...

Yeah, no, it's not as easy. In fact, I've done quite a bit of programming in language X, and I put forward that constructing and then destructuring lists is a painfully long and tedious process:

BidirectionalLinkedList list = new BidirectionalLinkedList();
list.add("Mary");
list.add("Sue");
list.add("Bob");

Blech!

BUT THEN it gets better when you do destructuring:

BidirectionalLinkedList newlist = new BidirectionalLinkedList();
for(String elem : list) { newlist.add(doit(elem)); }


Um, and that's only after the "stunning" advances that the STL started with functionals³ grafted onto the language, so have you seen the contortions you have to go through to create a functional object to map with? And don't you dare get your template parameter off because the compiler error...? shudder!

Enough of that.

So lists are structures or collections, and structures can be viewed as objects (phenomenon), and that is a very useful and powerful way to view them and to define them:

data List t = [] | (t : List t)

No problem with that and everything is right with the world.

... until it isn't.

This definitely works, and works well, for lists in general, and it also works great most of the time for working with the elements of the list. After all, in practice, we are most concerned with the element we have worked on most recently, so, in most cases, the element we just put in is the element we'd most likely to be retrieving ... AND (generally) our interest diminishes the further (in time) we are from an element, and that translates directly into where elements are found in a list.

Generally.

So, in general, lists work just fine; great, in fact.

There are specific cases where what we care about is not the most recent element, but another ordering is important. Two cases spring immediately to mind: first, queuing, and secondly (and commonly and specifically), document assembly.

In these two cases we wish to push onto the end of the list new elements, and the above definition doesn't give us access to the last element or position of the list. And to get that access, we must reverse the list so the last element becomes the first, or prepend to a reversed list. Either of these options has at least a cost in linear time when reverse is (eventually) called.

Or, we must call append or a function like it to append elements to the end of the working list; this also has linear costs. Either way, we pay the full price.

Now there are objects that do give us immediate access to that last element and position: deques and queues, for example, but when we go there, we give up the ease of composition and decomposition that we have with lists. We pay a penalty in expressitively with these types or in performance when using lists against their nature.

Or do we?

Well, one way of looking at lists is as objects, and above we gave a definition of lists as objects, but this is not the only way to view lists. I propose another way of looking at lists: lists can be viewed as functions.⁴

(:) :: t → [t] → [t]

The above definition says that (:) (pronounced 'cons') takes an element and a list and gives a list.

Yeah, so? you ask, for this is already a well-known function in the list lexicon.

I propose we look at this function in an entirely different way:

(:) :: t → ([t] → [t])

In this case, (:) constructs a list function from a seed element. This allows us to use this function a novel but perfectly acceptable way:

x |> list = (x:) . list

What we are saying here is that (|>) (pronounced 'put to front') is an operator that takes an x and puts that value on the front of list, just like (:) does.

The difference here (heh: 'difference') (sorry, mathematician humor) is what list is. For (:), list is of type [a] (or, directly and tautologically: list is a list), but for (|>), list is of type [a] → [a]. Or, translating: list is a function.

So? You've just reinvented the wheel with lists as functions now. Big deal.

Well, actually, what I've done is to reinvent the wheel as a meta-wheel, and so the big deal is this:

list <| x = list . (x:)

What we have here with (<|) (pronounced 'put to back') is a function that adds an element to the end of a list in — wait for it! — constant time. For 'regular' lists the best you can do that operation is in linear time, and so my work of constructing a document by appending to the end of a list that was occurring in O(n²) time has just gone to a linear-time operation. Not a big deal for a small document, but we found that once a document became more than a page or two, the operation went from 'a blink of an eye' to 'keeping your eyes closed until the cows came home ... that had been eaten by wolves.' This is not the case with lists as functions: document construction became reasonable endeavor (that is, it occurred so quickly for us mere humans, living in this non-nanosecond-time, we didn't notice the elapsed time).

So, I've been a sly thing in one respect. I still haven't told you what a (functional) list is. I've defined the object view of lists, and I've declared what a function view of lists, but haven't defined them.

Here. Allow me to define them now:

empty = id

There you go. There are the 'definitions.' I say 'definitions' because with that sole definition, everything works, for to ground a functional list, we simply pass it an empty list:

empty [] ⇒ []

Or even whatever list we are working with:

empty [1,2,3] ⇒ [1,2,3]

When you append something to an empty list, you get that something back.

AND empty works as the seed of the 'put to' operators:

(5 |> 6 |> 2 |> empty) [1,2,4] ⇒ [5,6,2,1,2,4]

and:

(empty <| 1 <| 2 <| 3) [4,5,6] ⇒ [1,2,3,4,5,6]

It all works!

Summary
In this article we've demonstrated that there's more than one way to look at, specifically, lists. The standard way is to view them is as objects, and for the most cases, that works, and works well: this view provides a syntax that makes list processing simple and intuitive.

We've also shown that that is not the sole way to view things, and this view can be constraining, particularly when lists are played against type as a queue or a document assembler. In these cases it becomes simpler, declaratively, to view lists as functions, and not only does that provide a syntax for simple list construction either at the beginning or the end of the list, but also provide constant-time construction at either end. Furthermore, defining this view is as simple as viewing the empty list as id and then using the partial function of (:) ('cons'). That's the generative view. Then, to extract the ("real") list from that view, it's as simple as sending a list (for example, []) to that functional list to ground the value for disposition.

In these special cases of working at the back end of a list, that aren't all that rare, the functional view of list processing gives the programmer expressivity and efficiency, eliminating the chore of appending to the end or reversing the target list. I quite enjoy list processing this way: it gives me a fresh perspective on an old friend and makes list processing in these cases easy and fun.

Endnotes

1	There is an article at http://wordaligned.org/articles/next-permutation that provides a simple, clear explanation of the lexicographic permutation algorithm with a very nice demonstrative example if you are so inclined to investigate.
2	Laurent Siklóssy, Let's Talk Lisp talks about MAPCAR in chapter 6. And, if I may: this book is one of the rare ones. It's one of those books like Smullyan's To Mock a Mockingbird or van der Linden's Deep C Secrets (with a fish on the orange book cover, no less!) or, and let us not forget the ultimate: Hofstadter's Gödel, Escher and Bach: the Eternal Golden Braid (I mean, even the title is a pun, Doug doesn't waste time in having fun, does he? He gets right to it!) that make you a better person but you don't notice it, but everybody else does, because you are constantly busting out laughing or grinning from ear-to-ear at the cleverness of their prose. Why do books about esoterica have to be so heavy! These esoteric books show that they don't have to be heavy in the lightness they deal with the subject (and deal with dealing with these esoteric subjects). And who is that bright young man who left such a feisty review of that book back in (*le gasp!*) 2001? I can see a promising future for that boy, just so long as he doesn't get too big for his britches. À propose de rien, what are britches? *ahem* Yes, so those books are three of my favorites ... which ones are yours?
3	Bjarne Stroustrup, The C++ Programming Language, 3rd ed., §18.4
4	Such a view of lists has a name: these functional list types are called difference lists from the Prolog community. The standard Haskell library does not have Data.DList [sad loss, I say!] but this type is provided by Don Stewart of Galois in the hackageDB under the dlist package. The Data.DList works great, but I've implemented my own system that is more than twice as fast as I provide several specialized implementations of difference list operators that take a more direct approach in their implementations (foldr is elegant but can be a costly operation). If you'd like to use my Data.DiffList package please contact me, and I'll be delighted to share this library.

Math is hard

So, here's an interesting, everyday conundrum, sent to me by a reader:

Hello my mathematical genius friend. :) [should I edit that out? *blush*]

I have been sent the following mathematical joke of sorts. The person who sent it to me claims there are no flaws in it. But obviously there has to be a flaw, because the conclusion is incorrect. The problem is that I don't know how to explain the flaw---but I suspect it happens in that third line where it attempts to equate squared cents with squared dollars. Is there any way that you could explain the flaw in such a way that a seventeen year old Norwegian would understand? Don't worry, you don't have to say it in Norwegian, he speaks English.

If you don't mind having a look at this and explaining, I would be ever so obliged. And no pressure, but...pants may be on the line in this little bet I've entered into.

1. $1= 100¢ (so $0.1 = 10¢)
2. And, 100¢ = 10¢²
3. Then, 10¢² = $0.1²
4. $0.1² = $0.01
5. $0.01 = 1¢

The implied conclusion is

∴ 'a dime squared equals one penny'

Then we say 'Q.E.D.'.

Hm, if pants are on the line for my dear reader, I wonder what's on the line for moi-self (that is faux-French) (and 'faux' is French)? A review? Or two? Or three? Of my stories?

Let's leave my preening aside.

So, who sees the fallacies above that lead to the absurd conclusion?

If you do not see it, please think on this awhile before looking at the answer.

---

The answer

From basically the get-go this problem statement is erroneous and imprecise, but this comes from a fundamental laxity in understanding of what operators are and what operators do. Certainly, the first premise is correct: One hundred pennies does indeed equate to one dollar, for

1. 100¢ = $1

is a statement of fact about the conversion from one set of units (pennies or ¢) to another set (dollars or $). But already the trickster plays fast and loose, for indeed:

1. ... (so $0.1 = 10¢)

is still correct but the (implied) conclusion makes a statement about the square of dimes, not about the square of tenths of dollars.

Do you see the fallacy now?

No? Let's continue.

So 1. is true, insofar as I can throw it, and days where my back gives out (ah! me poor bones!) that's not very far, but it's far enough for this problem statement, so long as it goes no farther than that.

But it does. *sigh*

So now let's get into the lies:

2. 100¢ = (10¢)² [parentheses implied and erroneous]

This is a lie. It's a lie, lie, lie, lie, lie, lie, lie!

Huh?

The lie is this: a square of a thing is not the thing itself, and even if you know nothing about mathematics, you can prove this to yourself. Socrates did it with an unlettered and untutored slave boy, and you are further along than what Socrates had to work with.

So let's prove 2. false with an analogue.

Take a foot rule (sorry, my readers who do not follow the British Imperial system, which, oddly enough, includes Brits these days, too) and a large piece of butcher paper. Draw a line on the butcher paper measuring one foot.

a. _ = 1 foot.

Now, 'square' that line, by drawing three more lines to make a foot square on the butcher paper.

b. ❏ = 1 foot square.

So, is

c? 1 foot = 1 foot square

Obviously not! for that would be to say:

c? _ = ❏

Or, put another way, 'one thing of one thing is equivalent to one thing of entirely a different thing'. One gulp of water does not equal one gulp of bleach. One I wish to have with my breakfast, the other, I do not, as my father very unfortunately discovered the hard way one not-so-fine morning.

"But, but, but ..." you stutter angrily, "but isn't '10² = 100' a statement of fact?"

Yes, indeed, it is, but please remember '10 ≠ 10 things' is also a statement of fact. Number (with a capital 'N') is a class of classes as, e.g., Introduction to Mathematical Philosophy so clearly and succinctly explains.

The link goes right to the book, all 228 pages of it. It's a quick read, so please (re)read it.

So to state:

2. 100¢ = (10¢)² [parentheses implied and erroneous]

is to state a falsehood.

How do we correct it? Well, by replacing the (implied) error with an explicit (corrected) ordering:

2. 100¢ = 10²¢

Do you see the correction? It the former case, we erroneously squared the units along with the number, in the latter case we do not square the units, we square the number solely.

Do I need to go any further? Or, do the fallacies fall out obviously in the rest of the assertions?

For completeness sake, I will review each step.

3. (10¢)² = ($0.1)² [parentheses implied and erroneous]

No. (10 pennies) squared does not equal (1 dime) squared.
But, a statement of fact of conversion is that (10 pennies) = (1 dime), but that's as far as it goes, and no farther.

If we square pennies we have a new unit of measure called, I don't know: (¢²), and (¢²) does not equal dimes. Not in this world.

4. ($0.1)² = $0.01 [parentheses implied and erroneous]

Again, no.
Again: $(0.1²) = $0.01, but again, that is as far as you can go with that statement.

5. $0.01 = 1¢

is just a reformulation of the first statement and is true, yes, but redundant.

Remember from Frege's predicate calculus:

q |- p [read: 'q implied by p' or 'if p then q']

[Shoot! why don't they have an 'implied by' HTML character?]
But if:

¬p [read: 'not p' or 'p is not true (or provable)']

Then you can say anything you like for q, or, more correctly, you cannot say anything at all about q, because q does not depend on ¬p, it depends on p.

So, as it were: 'If I had done the laundry, we wouldn't have had this argument' and 'I didn't do the laundry' means I don't have a leg to stand on about why we had this argument, honey.

(Oops, sorry, ... but it's not like I have had this experience at all ...)

And, to the point of this article: 'If a (10 one-hundredths of a dollar) squared were to equal (10 pennies) squared, then ...'

Well, then anything, because '(10 one-hundredths of a dollar) squared = (10 pennies) squared' is false. So say away, because anything coming from a false premise is an absurd conclusion: whirled (black eyed) peas, butterflies flapping in the Amazon, and the Number 23. They may be true enough in their own right, but you can say nothing about them from the false premise.

So, let's take the absurd conclusion:

∴ 'a dime squared equals one penny'

and reformulate it to be a true statement.

Well, the first thing we have to do it to get rid of the '∴', so let's do that, and then state the plain facts:

'a dime squared equals one penny' is an absurdity.

Q.E.D.

---

What can we take away from this?

Let's examine another absurity:

'Math is hard.'

No.

No, my dear ladies and gentlemen, 'Math' isn't 'hard.' Math is simple. Math can even be easy, for we learned from the Greeks, after all, that Math is one of the humanities. Math is simply a language. A language that can describe things exactly as they are and exactly as they are not. And precisely at that. It can even describe imprecision precisely. The 'hard'ness of mathematics comes from us, when we don't wish to be precise in what we are talking or thinking about.

Being precise ... well, that can be hard, I suppose, so then perhaps it's more precise not to say 'Math is hard' but to say 'Life is hard.'

Yes. That's true. 'Life is hard' as we choose to make it.

Oh, well. I never promised you a Rose Garden.

Realized Constants are Comonadic

An interesting problem that often arises is "to make" constants. Put another way, it often happens that a system acquires information over time. The system may wish to formalize what it has acquired by creating a constant value.

Here's the problem, however: "Variables don't; Constants aren't"^citation?

Or, put another way:

1. One man's constant is another man's variable.

To make a constant sometime down the road, as it were, in languages that have logic variables is simplicity itself: once a variable is unified with a value, it keeps that value throughout that proof.

In "pure" functional languages, that is, languages that do not have side effects, the same can be said.

What about the rest of the world? Take Java, for example. One can make a variable keep its value by declaring that variable final, but that is not helpful if we do not know what our constant value is to be at the time of object creation.

In what scenario could this possibly occur? We need a constant value, but we do not know what it is?

Actually, this situation arises quite frequently. Let's take a concrete example. You have many databases in your database management system, and at compile time you do not know on which port your DBMS is running nor do you know which database the user wishes to query. That's fine, you can lazily create the database connection and access the value through a method:

2. Functions delay binding; data structures induce binding. Moral: Structure data late in the programming process.

But what's not fine is this: the user is data-mining, examining chunks at a time, occasionally calling for the next chunk. How does one know that one has fallen off the end of the table? A simple SELECT on the maximum indexed key will tell you that, but to do that with every query? This seems wasteful. So, once we do the query once, let's just store that value in a variable with a flag to say we've already looked it up.

That sounds suspiciously like a lazily initialized constant, right?

But here's the rub: code that sets a flag allows for other code to unset it, just as code that sets a constant value allows other code to unset that. Using just plain-old regular variables gives no guarantee that the variable, once set, stays set at that constant value.

What to do?

Well, what is the work-flow of this process? We perform an action, checking that we are still within the bounds the valid domain, but the domain only becomes valid after program start, so we cannot make the bounds constant using the final keyword on the variable. This is a very common programming action ... sort of like ... dare I say ... a design pattern. Gee, I wish there was one invented that did all this.

In fact, there does exist such a pattern, and it comes from us via Category Theory. The programming language Haskell has incorporated elements of Category theory in its use of monads and arrows, but the downside of these ways of thinking about computation is that one must "lift" the entire computation into that domain, transforming the original computation to work in that regime.

No, what is needed is something less intrusive, and I found that less intrusive thing when I read an article by sigfpe on comonadic plumbing. In this article he describes three different ways of looking at constants: 1. as a constant, 2. as the Reader Monad, 3. or as the Reader Comonad.

The first one is sometimes untenable, given the programming need, and doesn't work for our case.

The second one is useful if one is already programming in a monad. Umm ... how many OO programmers use monads? Hands up.

[sound of crickets] ... thought so.

The third one allows one to use the constant on demand. And here's the thing, the comonad is very easily comprehended: it has a value that can be extracted "down" from the comonad, it allows a value to be extended over the comonad.

This sounds, in OO parlance, very much like an object. Let's ignore the extentionability of the comonad for now and simply look at extraction (this narrowed functionality is a thing in and of itself. Objects of this type are called Copointed, but let us not be too dogmatic here). Creating such a type is simplicity itself:

> public interface Comonad<T> { public T extract(); }

Um, yawn?

But that is the power of pattern language: not the ability to create these incredibly complex things in a controlled way (they do do that), but the ability to recognize that such and so is a pattern and then encapsulate behavior into the pattern.

Using the comonad pattern, we need simply to make our "maximum row number of Table x" an implementation of the Comonad interface, and then, when we do have enough information to create the database connection (that is, we now have our domain in which our constant resides), we instantiate the comonadic object (which is that domain). Whenever extract is called, it simply returns the constant value required, with the implementation that it does a database look up the first time, then it does the internal constant value look up all other times. Since the Comonad interface does not have methods to change its internals (here), so long as one has the copointed object, the value extract has a guarantee that it remains constant.

Summary

This article examined a commonly recurring problem: one needs to constify a value at some point during a program run and guarantee that it remain constant after being created. A simplification of the comonad was offered as a pattern that is simple to define and to implement.

Animal as RDR, part III

Examples: Building, running and modifying RDR systems

The previous entries showed the implementation of the model of a simple Ripple-Down Rules (RDR) system. This entry will show how to implement the rules for such a system from scratch as well as how to run and then to modify such a system. Again, we are using the computer game Animal as the basis of these examples.

Let's start off by implementing RDR system modelled in the first entry on this topic. But first, we need a couple of improvements. The addRule I had originally implemented wasn't an example for ease of use as it was ...

] addRule :: BinDir
]            → RuleTree a b c k v
]            → Environment k v b c
]            → Condition a (Knowledge k v)
]            → Conclusion b c (Knowledge k v)
]            → RuleTreeEnv a b c k v
] addRule dir (Zip hist branch) env cond concl 
]         = let rule = Branch (Rule cond concl) Leaf Leaf
]               newbr = fromJust $ mutate dir rule branch
]               newtree = return $ settle (Zip hist newbr)
]           in  RuleEnv newtree env

... so I changed it so that it fit more neatly into building rules in sequence:

> addRule :: BinDir → Rule a b c (Knowledge k v)
>            → RuleTree a b c k v → RuleTree a b c k v
> addRule dir rule (Zip hist branch)
>         = let ruleB = Branch rule Leaf Leaf
>           in  Zip hist (mutate dir ruleB branch)

This new implementation has now replaced the previous one in the implementation entry. Also, constructing Rules themselves was a bit labour-intensive, so I've added the following function to simplify building simple rules:

> type SimpleRule = Rule String String String 
>                        (Knowledge String String)

> mkRule :: String → String → SimpleRule
> mkRule key ans = Rule (present key) (assume ans)

Also, recall that:

(>>|) :: Monad m ⇒ m a → (a → b) → m b

This function simply reorders the arguments of liftM, so why have it? I find it useful in the flow of building monadic systems, as demonstrated below.

Building

And with that, let us build our Animal guessing game knowledge base:

> animalTree :: Zipper BinDir (BinaryTree SimpleRule)
>               → Zipper BinDir (BinaryTree SimpleRule)
> animalTree tree = fromJust 
>                   (return tree >>|
>                    addRule L (mkRule "has four legs" "pony") >>=
>                    advance L >>|
>                    addRule L (mkRule "barks" "dog") >>|
>                    addRule R (mkRule "swims" "fish") >>=
>                    advance L >>|
>                    addRule R (mkRule "purrs" "cat") >>=
>                    withdraw >>=
>                    advance R >>|
>                    addRule R (mkRule "spins web" "spider") >>|
>                    reset)

The function reset is from the Data.Zipper module:

> reset :: (Mutable c dir c, Transitive c dir)
>             ⇒ Zipper dir c → Zipper dir c
> reset z@(Zip [] _) = z
> reset (Zip ((dir, h):t) elt) = reset (Zip t $ mutate dir elt h)

Looking at animalTree above, I say with unmasked pride that I feel (>>|) shows its hidden strength: I could not imagine puzzling out the proper way to write the above definition using liftM and have it follow the natural flow that it does with its current implementation. Also note that it is vital that reset be called after a set of changes to a knowledge base occur, to reset (obviously) the focus to the top-level (default) rule, and to correct the tree containing that knowledge.

Running

Now that we have our animalTree, we need one more function to extract the result (follow the Conclusion) of runRule:

> runConcl :: RuleTreeEnv a b c k v → c
> runConcl (RuleEnv _ (Env ks (Concl _ f))) = f ks

Now, we could set up an interactive question-answer session to tease the animal we are guessing from our hidden thoughts, but, since interactive I/O is a sin in functional languages (see the fall from grace in Lazy K), let's "pretend" our way through an interactive session, recording the results of the questions into the Environment:

> rtests :: IO ()
> rtests = let RuleEnv tree env  = initKB "default" (assume "none")
>              newTree = animalTree tree
>              spider = updateEnv "spins web" "true" env
>              chat   = updateEnv "has four legs" "true" $
>                                 updateEnv "purrs" "true" env
>              spy = runConcl (answer $ RuleEnv newTree spider)
>              cat = runConcl (answer $ RuleEnv newTree chat)
>          in  do print newTree
>                 print spy
>                 print cat

As expected, spy is "spider" (in answer to the question "Does it spin a web?"), and cat is "cat" (in answer to the questions "Does it have four legs?" followed by "Does it purr?").

Modifying

All is well and good with the world, yes? Certainly, when we receive the expected answers from our knowledge base, but let's explore the world a bit beyond what we've captured. Not everything that swims is a fish:

> fishey = let RuleEnv tree env  = initKB "default" (assume "none")
>              newTree = animalTree tree
>              duck   = updateEnv "swims" "true" 
>                                 $ updateEnv "flies" "true" env
>              noDuck = runConcl (answer $ RuleEnv newTree duck)
>          in  print noDuck

We find that noDuck is a "fish". Perhaps it's a "flying fish", but it definitely wasn't the animal we were guessing, so we need to update our knowledge base to give us the desired answer. Fortunately, the system returns the Rule that rendered the Conclusion, so modifying the system proceeds directly:

> duckey = let RuleEnv tree env  = initKB "default" (assume "none")
>              newTree = animalTree tree
>              duck   = updateEnv "swims" "true" 
>                                 $ updateEnv "flies" "true" env
>              re@(RuleEnv noDuckTree _) = answer $ RuleEnv newTree duck
>              noDuck = runConcl re
>              duckTree = addRule L (mkRule "flies" "duck") noDuckTree
>              ducky = runConcl (answer $ RuleEnv duckTree duck)
>          in  print (noDuck, ducky)

With the modification in place, that is, the addition of the new EXCEPT Rule, we find that the animal that swims and flies is, indeed, a "duck", as expected. That's Just ducky!

Knowledge in context

Of course, there is the flying fish conundrum, so a better ordering would be to have the Conclusion of that Rule actually be "flying fish" and its EXCEPT clause (with the Condition being something like "webbed feet" or "feathers") rendering the "duck" Conclusion. While we're on the topic of structuring knowledge, not everything that purrs is a cat. The knowledge base could have had a very different structure if the Condition of the first Rule was "purrs". Trekkers know the answer to that one: "tribble", obviously! The follow-on EXCEPT clause (with the Condition of "four legs") would then clarify to the feline nature.

This demonstrates knowledge in context, where in one context, the context of "having four legs", the attribute of purring leads to "cat", but in another context (the blank context, but that context could be elaborated with some Rules that put us in the context of the Star Trek, um, multiverse?), the very same attribute leads to "tribble". Under this new context, "four legs" leads back to our "chat chapeau" (that is Viennese) [I am really running rampant with my `pataphorisms, I do apologize and will work to check myself, but topic of επιστήμη λόγος does rather lend itself to such openings [which I have relentlessly pursued ... again!]] Furthermore, the quiddity of "four legs" is, itself, context-based. In one sense it leads to every little girl's dream (a "pony") and following (EXCEPTing) that, several other species, and in another context, it leads to non-tribble purring creatures. This is a rather fundamental restructuring of our presumptions from the first article on this topic. I don't have a simple function that restructures knowledge assumptions in fundamental ways; I don't see the benefit of having one, so let's simply rewrite our knowledge base from scratch with our gained experience:

> startrek tree = fromJust
>                 (return tree >>|
>                  addRule L (mkRule "purrs" "tribble") >>=
>                  advance L >>|
>                  addRule L (mkRule "has four legs" "cat") >>|
>                  addTree R (firstRule (animalTree tree)) >>|
>                  reset)
>      where addTree dir (Zip _ branch) (Zip hist tree)
>                      = Zip hist $ mutate dir branch tree
>            firstRule = fromJust . advance L

Not as painful as I thought! There are a couple of points to note, however:

1. The path to discovering a "cat" is duplicated, redundantly. This is fine, however: real knowledge is messy and contains redundancies, and this redundancy doesn't impact the (speed) efficiency of this knowledge base in any way; and,
2. We are back to missing our "duck". I leave that as an exercise to you to re-add.

Summary

This concludes the series of articles on the explanation, implementation and demonstration of a simple Ripple-Down Rules (RDR) system. In these articles we showed that such systems are easy to implement in Haskell and then to use. Knowledge management, in and of itself, is a rather deep and tricky topic (we have hinted at such trickiness in our "Trouble with Tribbles"), but RDR, using the concept of knowledge in context provides a method that allows modelling this knowledge more directly and allows manipulation of assumptions without adding too much difficulty to the task of knowledge engineering.

Animal as RDR, part II

Implementation study

In the last entry, we introduced what RDR (ripple-down rules) are and reviewed the types that comprise an example system. This entry will show how those types are used to implement such a system.

> module RDRFinding where

This module scans the RDR tree in context to give BOTH the best-fitting conclusion AND the final Branch that led to the ultimate conclusion (in the form of a zipper so that the branch may be replace in place using standard operations on the zipper).

> import RDRTypes
> import Data.Transitive
> import Data.Zipper
> import Data.BinaryTree
> import Data.Map (Map)
> import qualified Data.Map as Map
> import Control.Monad.State
> import Data.Maybe

You have already encountered the above imported modules, but the next two modules need an introduction. The first

> import Control.Monad.Utils

contains my weird and wonderful syntax when I'm using monads for parsing or logic tasks. The parsing syntax you've seen before (see the critique), but I do add one new syntactic construct:

(>>|) :: m a → (a → b) → m b

because I'm always doing "m >>= return . f", and liftM seems to feel oddly backwards when I'm visualizing data flow. The next

> import Data.Mutable

provides a generic operation for changing a data structure:

class Mutable t dir val | t → dir, t → val where
   mutate :: dir → val → t → Maybe t

So, what's the game? We have an Environment (a set of attributed values) combined with a RuleTree into the State Monad. What we do is guide the values in the environment through the rule tree (where a successful Condition chooses the EXCEPT branch and displaces the currently saved Conclusion with the one associated with this Rule, and conversely if the Condition fails, the ELSE branch is selected, without displacing the currently saved Conclusion). When we reach a Leaf, we return our current position in the tree (the current state of the Zipper) along with the last valid Conclusion. All this is done by runRule:

> runRule :: RuleFinding a b c k v
> runRule = get >>= λ (RuleEnv root env) . runRule' root env

> runRule' :: RuleTree a b c k v → Environment k v b c
>                                → RuleFinding a b c k v
> runRule' tree env@(Env ks curr)
>         = branch tree >>: λ (cond, conc) .
>           let (dir, concl) = liftZdir (testCond cond env conc)
>           in  advance dir tree >>: λ path .
>               put (RuleEnv path (Env ks concl)) >> runRule
>    where x >>: f = tryS curr x f

Whew! This is a mouthful in the number of functions it introduces, but conceptually, runRule is rather straightforward. Let's break it down.

The function runRule, itself, merely destructures the RuleTreeEnv term, passing that information to runRule', so let's move right on to that worker function. First, let's examine the funny syntactic construct, (>>:) — what is this monadic operator doing? We see from its definition that it calls tryS:

> tryS :: a → Maybe b → (b → State c a) → State c a
> tryS x may f = maybe (return x) f may

So, tryS lifts the State Monad into semideterminism (using the Maybe Monad). As an aside, perhaps, then, runRule' could be rewritten as a StateT over the Maybe Monad ... perhaps an intrepid reader will gain a ⊥-trophy for an implementation and explanation?

Using that monadic operator, (>>:), we get the current branch in focus (bailing if the focus is on a Leaf) ...

> branch :: RuleTree a b c k v
>                → Maybe (Condition a (Knowledge k v), 
>                          Conclusion b c (Knowledge k v))
> branch (Zip _ (Branch (Rule cond conc) _ _)) = Just (cond, conc)
> branch (Zip _ Leaf)                          = Nothing

... then we test the condition at that Branch ...

> testCond :: Condition a (Knowledge k v)
>             → Environment k v ca cb
>             → Conclusion ca cb (Knowledge k v)
>             → Either (Environment k v ca cb)
>                       (Environment k v ca cb)
> testCond (Cond _ test) env@(Env kb _) conc1 
>          | test kb   = Left $ Env kb conc1
>          | otherwise = Right env

> liftZdir :: Either (Environment k v ca cb) 
>                    (Environment k v ca cb)
>             → (BinDir, Conclusion ca cb (Knowledge k v))
> liftZdir test = either (λ (Env _ c) . (L, c))
>                        (λ (Env _ c) . (R, c))
>                        test

I do this little pas de deux between testCond and liftZdir because somehow it just feels right to use the Either type here. Perhaps, sometime later Arrows will come into play. At any rate, liftZdir . testCond can be considered one function that returns the appropriate leg of the branch to continue finding the best viable Conclusion, as well as the best current Conclusion reached from applying the Environment to the Condition.

Given that information, we now advance down that path, updating the state, and continue to test recursively, until we reach a Leaf, at which point we have our answer (the ultimate viable Conclusion).

If we're happy with that answer, we call runRule with a new transaction (in other words, a fresh Environment), and the Zipper pointing back at the top of the RuleTree. If we're not happy, then we're given the ability to add a new Rule to the RuleTree. We do this with addRule:

> addRule :: BinDir → Rule a b c (Knowledge k v)
>            → RuleTree a b c k v → RuleTree a b c k v
> addRule dir rule (Zip hist branch)
>         = let ruleB = Branch rule Leaf Leaf
>           in  Zip hist (mutate dir ruleB branch)

The above functions are the meat of the implementation for this simple RDR system. There are a few conveniences that the following functions provide. The first one is answer that scans the rule tree, making the best conclusion, and then backs up one step to provide the user access to the branch in case the precipitating rule finding wasn't exactly giving the desired result.

> answer :: RuleTreeEnv a b c k v → RuleTreeEnv a b c k v
> answer rule = let RuleEnv z ans = execState runRule rule
>               in  RuleEnv (fromJust $ withdraw z) ans

The next three functions help to automate the creation of the rule parts, Conditions and Conclusions. The function mkCond creates a test function with the assumption that the knowledge store contains a (k,v) pair. It does the lookup in the knowledge store and passes the extracted values to the test function (which, as with any good predicate, returns either True or False). If we can't find the key, I guess, for now, we'll assume the returned value is False:

> mkCond :: Ord k ⇒ k → (v → Bool) → Condition k (Knowledge k v)
> mkCond key fn = Cond key $ λ ks . maybe False fn (Map.lookup key ks)

> present :: Ord k ⇒ k → Condition k (Knowledge k v)
> present = flip mkCond (const True)

> assume :: k → Conclusion k k env
> assume key = Concl key (const key)

This completes the implementation of this RDR system. The next entry will create a small RDR system, based on the game Animal, to demonstrate how the system works.

Animal: an RDR implementation study, part I: types

Synopsis

Ripple-down rules provide a fast and efficient representation of knowledge in context for use, e.g., by expert systems. We present here a complete implementation of one type of RDR system in Haskell. But what analogy is sufficient to describe what an RDR system is? The literature, albeit comprehensive, seems to concentrate more on the details of making such a system work, but none have presented the essence: the computer guessing-game Animal does a good job of this illustration, and we use it here to build an example knowledge base for this RDR system.

Motivation/Introduction

As a knowledge engineer I have worked with Subject-Matter Experts (SMEs) to build various rule-based expert systems. A common pitfall of such systems, its ὕβρις, is that they attempt to abstract decision making from any context. And, as such, fail to notice the nuances or have the situational awareness needed to render useful judgments. In a knowledge-engineered rule-based/bayesian-like hybrid system I developed, the bayesian decisions lead to over 99% of the positive findings in the transactions analyzed.

This would be the end of the story if there were no hard limits, but there are always such hard limits. Bayesian-like systems tend to scorn the advice and guidance of SMEs: the data set itself is the experts, not the SMEs. Despite the success of using the data, bayesian-like systems also tend to overreact — only 1 transaction out of 1000 transactions it flagged actually lead to a decision — these systems need serious throttling to be successful. Resources, then, are a real-world constraints that rule-based systems better model than bayesian systems in practice. In fact, hard constraints in general are modeled much better by rule-based systems.

But the rule-based systems, popularized by, e.g., iLog JRules™ and used in many expert systems, do not speak the language of the SMEs. Having worked with SMEs across the U.S.A. over a period of years, rules invariably tend to be defined by exception. Whenever we, as the knowledge-engineers, attempt to nail down a definition with the SMEs, the conversations always proceed as follows:

SME: Yeah, a CC transaction of over $57.38 is always suspect.
Me: So, we'll flag those, then [thinking: Ha! that was an easy rule; finally!]
SME: No, no, no! Only from young males or senior citizens in the following three income brackets.
Me: Oh, okay, I'll add that to the constraint.
SME: No, but it needs to be in the following zip-codes ...

Several hours later we're still ironing out the rule, and then, as lunch break approaches, the chair either tables the rule or passes a simplified, useless, version of it.

Note how the rule set was defined above, the SMEs agreed to a general case, and then continue to refine that definition by adding (often conflicting) constraints. In a context-free rule-based system, modelling such a rule set is by no means impossible, but the task quickly becomes a chore in the nightmare of complexity.

RDRs (Ripple-down Rules), on the other hand, embrace the context. The syntax of an RDR system is as follows:

<rule> ::= IF condition THEN conclusion
<knowledge base> ::= ⊥
                   | <rule> 
                     EXCEPT <knowledge base>
                     ELSE   <knowledge base>

The semantics is as follows. If the condition is met, then that conclusion is saved as a viable result (replacing any prior conclusion) and the EXCEPT branch is followed recursively until ⊥, at which time the most recently saved conclusion is the result. On the other hand, if condition fails, the ELSE branch is selected and followed recursively. Of course, the knowledge base must be applied to something. In this system, we have a very simple environment where the condition tests for the presence of a String in that environment.

The initial knowledge base for every RDR system starts as:

IF (const True) THEN none EXCEPT ⊥ ELSE ⊥

As the SMEs interact with the RDR system, they add to knowledge to refine the conclusions guided by refinements in the conditions. The system is very permissive, redundancy is permitted, even encouraged, because a condition in depth of one path of EXCEPTs and ELSEs has a very different meaning, in context, than along another path.

Example

Our RDR system with be the Animal guessing game with the following knowledge base:

IF (const True) THEN "not an animal"
  EXCEPT IF (present "four legs") THEN "pony"
         EXCEPT IF (present "barks") THEN "dog"
                EXCEPT ⊥
                ELSE IF (present "meows") THEN "cat"
                     EXCEPT ⊥
                     ELSE ⊥
         ELSE IF (present "swims") THEN "fish"
              EXCEPT ⊥
              ELSE IF (present "spins web") THEN "spider"
                   EXCEPT ⊥
                   ELSE ⊥
  ELSE ⊥

Types

> module RDRTypes where

> import Control.Monad.State
> import Data.Map (Map)
> import qualified Data.Map as Map

I must apologize for not introducing the next three modules properly. These modules are part of my canon and will be introduced in depth elsewhere. For now, I must settle for the following descriptions:

> import Data.Transitive

defines a generic protocol of walking a data structure one step at a time, either "forward" (with advance) or backward (with withdraw).

> import Data.Zipper

The "simple Ariadne zipper" illustrated in the Haskell Wikibooks.

> import Data.BinaryTree

The only novel structure here is that the tree is shaped to conform to the structure of RDRs: the data is in the branch, not the leaves.

From Predicate Logic-based Incremental KA, Barry Drake and Ghassan Beydoun (Nov 2000), file named PRDR.pdf

2.1. Ripple Down Rules (RDR)
An RDR knowledge base is a collection of simple rules organised in a binary tree structure. Each rule has the form, "If condition then conclusion". Every rule can have two branches to other rules: a false-branch (also called the “or” branch) and a true-branch (also called the “exception” branch). An example RDR tree is shown in figure 2.1. When a rule is satisfied, the true branch is taken, otherwise a false branch is taken. The root node of an RDR tree contains the default rule whose condition is always satisfied, that is, it is of the form, “If true then default conclusion”. This default rule has only a true-branch.

The RDR IF-THEN rule contains a condition and conclusion that interact with the Environment (defined later) to inform the decision of the system.

> data Condition a env = Cond a (env → Bool)
> instance Show a ⇒ Show (Condition a env) where
>     show (Cond c _) = "IF " ++ show c

> data Conclusion a b env = Concl a (env → b)
> instance Show a ⇒ Show (Conclusion a b env) where
>    show (Concl c _) = "THEN " ++ show c

Given the above, an IF-THEN Rule is simply the conjunction of the the Condition and Conclusion:

> data Rule a b c kb
>      = Rule (Condition a kb) (Conclusion b c kb)
> instance (Show a, Show b) ⇒ Show (Rule a b c kb) where
>    show (Rule a b) = show a ++ " " ++ show b

The Environment is composed of a dictionary (keys to values) and the current most valid conclusion under consideration. In our example (Animal), we merely test for the existence of a key, but more complex system usually treat the keys as attributed values and perform more than simple existence-check tests.

> type Knowledge k v = Map k v
> data Environment k v a b
>    = Env (Knowledge k v) (Conclusion a b (Knowledge k v))
> instance (Show k, Show v, Show a)
>          ⇒ Show (Environment k v a b) where
>    show (Env kv conc) = "{" ++ show kv ++ ": "
>                             ++ show conc ++ "}"

The above elements are what comprise the simple types for the RDR system, so what is left is those elements that form the structure. This system is in the shape of a binary tree, so, of course, we use that data structure. As we append new rule branches to leaves of the tree, we use the Zipper data type to allow us to add these nodes in place.

> type RuleBranch a b c k v
>      = BinaryTree (Rule a b c (Knowledge k v))
> type RuleTree a b c k v
>      = Zipper BinDir (RuleBranch a b c k v)

> data RuleTreeEnv a b c k v = RuleEnv (RuleTree a b c k v)
>                                      (Environment k v b c)
> instance (Show a, Show b, Show k, Show v)
>          => Show (RuleTreeEnv a b c k v) where
>    show (RuleEnv tree env) = "| " ++ show tree ++ " : "
>                                   ++ show env ++ " |"

The RDR system is built around the concept of context, and the State Monad captures that concept well. The final type is used to shuttle around the knowledge base as well as the currently viable conclusion based on the rule finding.

> type RuleFinding a b c k v
>      = State (RuleTreeEnv a b c k v)
>              (Conclusion b c (Knowledge k v))

The above types describe the RDR system. In the next entry, we will show the implementation of the system when it comes to building and adding rules as well as traversing the rule tree to reach a conclusion.

What is declarative programming?

The concept has been bandied about, and has entered into more popular discussion with the broad acceptance of XML. Beside the overall definition, however ("Declarative is the 'what' of programming; imperative, the 'how'"), I haven't heard a definition that sketches, even, what declarative programming is and how it looks like.

For the "quartet of programming styles", being: imperative, object-oriented, functional, and logical, it seems pretty clear that there are well-defined general boundaries (with enough wiggle room to cause fanatics to enjoy flame-wars as the mood struck them) to separate one style from another, with languages easily falling into one or more of those camps:

• C: imperative
• Smalltalk/Java: imperative/object-oriented
• Lisp(and Scheme and Dylan and ...)/Haskell/ML: functional
• Prolog (Mercury): logical

This was all clear-cut and well and good.

But for classifying something as "declarative programming" it seemed that there has been talk of its benefits or drawbacks, but not much more than superficial talk of what it is. Camps from both the functional programming community and the logic programming community stake claims over the declarativeness of their programming languages, but how does one recognize code as declarative? What is the measure by which the "declarativeness" of such code may be ascertained?

Up until recently, I have been troubled by such misgivings only marginally. I had it from authority, a Lisp giant, Patrick Winston, in a Prolog book (Bratko's 3rd ed of "Prolog Programming for Artificial Intelligence"), that the logical style of Prolog is declarative and the functional style is not. Before your send your flame, here's the quote:

"[...] In my view, modern Lisp is the champion of these [imperative] languages, for Lisp in its Common Lisp form is enormously expressive, but how to do something is still what the Lisp programmer is allowed to be expressive about. Prolog, on the other hand, is a language that clearly breaks away from the how-type languges, encouraging the programmer to describe situations and problems, not the detailed means by which the problems are to be solved.

Consequently, an introduction to Prolog is important for all students of Computer Science, for there is no better way to see what the notion of what-type programming is all about. [...]"

I add here that I also view the bulk of Haskell in this light: although it is possible to code declaratively in Haskell, most Haskell code I see is concern with solving the problem (the "how") instead of describing the problem (the "what"). Put another way, it is natural to use the functional and imperative (with monadic do) styles, and it takes effort to use the logic style.

That has been my prejudice until recently, but then recent correspondence with colleagues, including David F. Place, who recently had an excellent article in the Monad.Reader about Monoid, has opened this issue for reexamination. So, I turn to you, gentle reader. I present two very different programs below. One written in the logic style; one, functional. Both solve the same problem, and both authors claim their own version is definitively declarative. I view the world through a particular lense, so I see one perspective. But I am burning with curiosity: do you see A) or B) as declarative, or both, or neither? If so, how do you justify your position?

A) the "logical" program approach:

import Control.Monad.State
import Data.List

splits :: (Eq a) ⇒ [a] → [(a, [a])]
splits list = list >>= λx . return (x, delete x list)

choose :: Eq a ⇒ StateT [a] [] a
choose = StateT $ λs . splits s

sendmory' :: StateT [Int] [ ] [Int]
sendmory' =
     do
       let m = 1
       let o = 0
       s ← choose
       guard (s > 7)
       e ← choose
       d ← choose
       y ← choose
       n ← choose
       r ← choose
       guard (num [s, e, n, d ] + num [m, o, r , e ]
              ≡ num [m, o, n, e, y ])
       return [s, e, n, d , m, o, r , y ]

B) the functional program approach (provided by David F. Place):

solve input accept return
    = solve' [] input [0..9] accept return

solve' bindings [] _ accept return 
          | accept bindings = [return bindings]
          | otherwise = []
solve' bindings ((_,g):xs) digits accept return
          = concatMap f $ g digits
     where f n = solve' (bindings++[n]) xs
                          (delete n digits)
                          accept return

num = foldl ((+) . (*10)) 0

sendMoreMoney =
     solve (('m', const [1]) :
            ('o', const [0]) :
            ('s', filter ( > 7)) :
            (zip "edynr" (repeat id)))
       (λ [m,o,s,e,d,y,n,r] . num [s,e,n,d] 
                                  + num [m,o,r,e]
                                  ≡ num [m,o,n,e,y])
       (λ [m,o,s,e,d,y,n,r] . [s,e,n,d,m,o,r,y])