Mutable Syntax in the Mercury Programming Language

Introduction

The Mercury programming language is a compiled, strict, pure, type-safe logical and functional programming language. Its programming methodology is based on predicate logic, with syntax and semantics in line with that of Prolog. Along with logic, it has a fully integrated Hindley-Milner type system with lambda-terms, very much in the style of the Haskell programming language.

The smooth integration of Prolog with Haskell sounds like a marriage of programming paradigms to release the programmer into Coding Nirvana, as it were. This is how it is for most cases, as the language has a consistent design philosophy backed up by well-researched principles and explained by copious and clear documentation with numerous practical examples. What remains are niche constructs, that is: constructs that may be helpful for specific problems, but are not strictly necessary, nor generally applicable.

One such niche construct, one that I turn to quite often when programming in Prolog, is the op/3 declaration, or, the ability to introduce new syntax into the language so that I may model the problem more naturally. This document covers extending the language to include the op/3 declaration in its full breath of functionality.

Alternatives, and Raison d'être

The approach we take is the modify the compiler so that it accepts the op/3 directive in a module and thereafter, within only that module, parse the operator declared with the specification and priority given in the directive. This may seem like a drastic measure, so we must consider the alternatives before choosing this course of action. There are basically four viable, albeit inferior, alternatives:

1. The Mercury programming language provides the grave syntactic construct which converts the standard prefixed call to an infix one:

   fn(X, Y) becomes X `fn` Y

   See, for example, the pprint module, as it used to make extensive use of this style (until it recently deprecated this approach to use one of the builtin operators, instead). Just as the Mercury language developers have discovered, this approach has at least two drawbacks:
   1. these infix "operators" are clearly marked as second-class citizens, unnecessarily lengthening what is supposed to be a concise representation;¹ and,
   2. only binary infix operators are allowed under this syntax; I often find it useful to type values using a postfix type.
2. One could construct a specialized instance of the op_table typeclass from the ops module and thereafter use read_term_with_op_table/4 from the term_io module to parse strings at runtime. See samples/calculator2.m provided with the distribution for an example program that demonstrates this approach.
   This approach also has its own set of associated problems:
   1. Constructing one's own op_table is excessive when using only a few operators and tedious when introducing many operators. This manual process steals precious time away from program development that addresses the problem, itself.
   2. Until now, there was no "cookbook" approach addressing the problem of how to create a mutable syntax. The ops module and the sample calculator program are well-documented and provide good examples of how to implement static syntax, but provide no guidance for constructing dynamic, mutable, syntax. For this, one had to design such a framework from first principles.²
   3. An user-defined op_table instance may only be used at runtime. The Mercury compiler, as implemented, does not allow such tables during module compilation.
3. Third, use one of the available scanners (such as samples/lex/) or parser generators (such as samples/moose/) to create a language syntax-aware preprocessor that substitutes operators and their arguments with the well-formed term replacement. Problems:
   1. This is highly redundant and fruitless exercise, as the compiler has its own parse phase that does the same work, and with the language itself in flux (as is the case for any living language) changes to the syntax quickly render a system created by these means obsolete. Parser generators for other programming languages provide complete grammars for every version of the host programming language, Mercury has no parser generator with such grammars, so this task is left to a user of these kinds of systems.
   2. Furthermore, although the domain-specific languages for these tools closely follow the Mercury programming language to do their work, they do have their own languages that require time and effort to master. When presented with powerful parsing facilities built right into logic programming languages (I'm referring specifically to Definite Clause Grammars (DCGs)), one must weigh the costs of learning these languages before embarking on such an endeavor.
4. Worst for last: as with C/C++, create a specific preprocessor that parses the source file, converting annotated operators to equivalent Mercury terms by following the preprocessing directives. This approach requires so much work (the C preprocesser is a compiler-sized program) and has so many known pitfalls (such as replacing elements inappropriately (in a quoted string, for example) and causing an unacceptable disjunction between the generated executable and the original source base (confusing debugging and error reporting efforts), that it should not receive serious consideration;³ it does not in this document, at any rate.

By embedding the op/3 syntax into the compiler, the changes we make are hygenic in that they are part of the language syntax, not external and blindly unaware of it, as is the case with with C preprocessor and immediate so that they may be used at compile time in the module in which they are declared. This implementation also limits the lexical scope of the operatorwithin the module in which it is declared,⁴ preventing these declarations from corrupting modules that eventually use modules with specialized syntax.

The desired state is to integrate the op/3 declaration fully into the the language, so that, e.g., facts may be stated in their vernacular and still be compiled into executable content in the Mercury idiom, as in this real-world example:

for the open weekly timecard ending date(2006, 1, 6):
  employee cgi_emp_001 billed [
      3 hours on sunday - date(2006, 1, 1),
      16.5 hours on monday - date(2006, 1, 2),
      5 hours on tuesday - date(2006, 1, 3),
      5 hours on wednesday - date(2006, 1, 4)
  ] against contract lt_2005_001.

Far from being a contrived pedagogical example,⁵ the above illustrates the various typing uses of op/3 defined syntax, both prefix ('employee cgi_emp_001') and postfix ('3 hours'). The above fact is certainly "only" a data term (in fact, as well as being a data term, the above fact also contains op/3-based data terms), but fully actualized operators exist as well; the Prolog syntax module is rife with such examples. These uses of op/3-declared syntax (describing entity relationships clearly and as activated syntax) are in no way limited to the rather straightforward problems of accounting, but are also used in production expert systems handling over 1,000,000 transactions per day; the use of these extensions are tied directly to rule findings satisfying customer requirements.

In short, op/3-declared syntax is used extensively in production systems built using Prolog serving real-world requirements under heavy demands. With the preexisting extensions for purity, typing, and functional programming, imagine the utility and expressivity that could be obtained with Mercury so extended!

Implementation

Now that we have justification for modifying the compiler, nothing remains but to get to it. Fortunately, the Mercury compiler, after some study, yields a straightforward implementation approach.

First things first: the ops module uses a discriminator (the type category) to choose among different uses for an operator (e.g. unary '-' verses binary '-'). This discriminator is internal, and, as we need the same functionality when defining new operators, so we externalize that type in library/ops.m by moving the type declaration from the implementation section to the interface.

Given this type, we now decorate predefined (inflexible) op table that will permit additional syntax declarations. For this, we need to index the operator and its category to the syntax declaration, and then make this new type an op_table (typeclass) instance ... we add this type to the interface of compiler/prog_io_util.m:

:- type op_map == map(pair(string, ops.category), op_info).
:- type mercury_op_map ---> mercury_op_map(ops.table, op_map).
:- instance ops.op_table(mercury_op_map).

To further support the new type, we need information against which we index, and we need supporting predicates to construct the information for the parser when encountering the operator (the declarations for this also go into the interface of compiler/prog_io_util.m):

:- type op_info ---> op_info(ops.specifier, ops.priority).
:- func op_specifier_from_string(string) = ops.specifier.
:- func op_category_from_specifier(ops.specifier) = ops.category.

The op_specifier_from_string function simply takes an input string, e.g. "xfx", and coverts it to the equivalent specifier representation, e.g. the functor xfx. Theop_category_from_specifier function follows the (implied) convention of the ops module, which is all prefix specifier types (including binary prefix) are the before categoryand all other specifier types (one of several different infix and postfix possibilities) are the after category type. The complete set of changes are enumerated explicitly in the email on the implementation.

After we augment the functional of the ops module, we need to integrate this into the compiler's parser module (which is actually called prog_io). The efficacious point is where the parser works at the module level,⁶ this occurs, after some initialization in read_module/11, in read_all_items/7. We initialize the op map here (with a call to init_mercury_op_map), and then pass along that nascent syntax map to the calls that parse the items in the module (by modifying the signatures of read_first_item/9 and the recursive callsread_items_loop_2/11 and read_items_loop/10).

So, for example, read_items_loop/9 becomes:

read_items_loop(ModuleName, SourceFileName, !Msgs, !Items, !Error, Syn0, !IO)

... where Syn0 is the new syntax map. This map is initialized in the new read_all_items/7 before calling read_items_loop/10 with the goal:

init_mercury_op_map(init_mercury_op_table, Syntax)

The magic occurs in module parser's read_term_with_op_table/5 (called via read_item/7) which normally scans and parses the items in the module. When it encounters anop/3 declaration, however, it eventually resolves to the process_decl/8 back in the prog_io module, which reads the declaration and then adds the syntax declaration to the op map, enhancing the syntax for the current module.

When read_all_items/7 completes its iteration on a module's items, it exits, discarding the op_map instance and any syntax it accumulated from op/3 declarations in that module, returning the compiler to the base, Mercury-defined, syntax. So that the "next" module starts fresh without syntax from other modules polluting the compilation.

Reconsideration

"Worse is Better"⁷

After some discussion on the Mercury maillist, it was resolved that dynamic syntactic extensions should be external to the compiler. So, Logical Types has developed separate compiliation system that converts modules with syntactic enhancements to plain-jane Mercury equivalents. For modules with no syntactic enhancements, `ltq' is equivalent to `mmc --make --infer-all'. For modules with op/3 declarations in the implementation, `ltq' first parses the module and writes out all terms canonically. After this translation, the system compiles the modules into the resulting executable or library.

Operation

This system reduces rather nicely by using facilities provided by the Mercury compiler, and another declarative system: make. `mmc -M <file>' discovers file's dependencies and stores these in a makefile variable $(.ms) in the file <file>.dv Given this, ltq simply builds a makefile with the enumerated dependencies and then calls the system that manages the dynamic syntax, which then writes out syntactically-enhanced modules in their canonical form (called `dopp'). Both ltq and dopp are available, along with samples as dynamic_ops.tgz.

Conclusion

This study came from my experience with the ease of use of mallable syntax in Prolog and comments in the Mercury sources about the need to add op/3 declarations as well as at least two aborted implementation attempts to do so. In the ensuing process, where I did implement this solution, quite a discussion emerged on the maillist on the estetic of allowing the user to introduce or to change syntax, and how to go about doing it properly. This implementation is one approach, and is offered to assist those who wish to add syntactic extensions to their Mercury systems.

---

Endnotes

1	The normal infix operators do not have this grave branding, and for good reason. Imagine writing algebraic statements, such as the following: Aroot = sqrt((B * B - 4 * A * C) / 2 * A) - B while shackled to the grave syntax: Aroot `=` (sqrt(((B `*` B) `-` (4 `*` A `*` C)) `/` (2 `*` A)) `-` B) Note the extra parentheses -- these are now necessary, as the grave syntax does not communicate operator precedence. Also note that the single-character operators are now three times their original size. Given the above, it's tempting to avoid infix syntax altogether... (setq aroot (- (sqrt (/ (- (* b b) (* 4 a c)) (* 2 a))) b)) ...but I have no desire to write out the parsed internal representation by hand (it may look like Lisp, circa 1965, because the syntax of most Lisps (with one notable exception) is also its parsed internal representation), so the Mercury prefix code is therefore presented: '='(Aroot, '-'(sqrt('/'('-'('*'(B, B), '*'('*'(4, A), C)), '*'(2, A))), B)) There! Isn't the canonical tree syntax so much better than the cons syntax? Drek!
2	This is not all that bad, given the documentation and the calculator2.m sample. In calc4.m we provide a straightforward example using the map type.
3	This pronouncement in no way prevented this author from submitting such a proposal to the Mercury team. Ah, the blessed ignorance of youth! All was not in vain, however: every misstep hides the seeds of greatness: one of the responses showed that samples/expand_term.m (the responder was the author of that module, in fact) provides the functionality of Prolog's term_expansion/2 predicate, which is an essential prerequesite for implementing Aspect-Oriented Programming (AOP) in predicate-logic based languages (specifically Prolog). How aspects are implemented in Mercury shall be a topic for another paper.
4	In ISO Prolog op/3 declarations have global extent.
5	[Bratko2001], § 3.3 demonstrates op/3 declared syntax with such charming statements... :- op(300, xfx, plays). :- op(200, xfy, and). Term1 = jimmy plays football and squash. Term2 = susan plays tennis and basketball and volleyball. ...but then the textbook quickly redeems itself -- it is still my preferred Prolog textbook -- with a meatier problem, which I adapt for your enjoyment: ruth was the executive director at wncog. sally was the executive administrative_assistant at wncog. diane was the director of the human_resources department at wncog. juan was the administrative_assistant of the human_resources department at wncog. sunny was the director of the finance department at wncog. stuart was the director of the operations department at wncog. joe was the system_administrator of the operations department at wncog. ?- Who was the director of the What department at wncog. Who = diane, What = human_resources ; Who = sunny, What = finance ; Who = stuart, What = operations ; no I leave the op/3 declarations as a coding challenge to the enterprising reader.
6	Prolog's op/3 declarations have global extent, but I consider this a mistake in the presence of a module system -- op/3 should only affect the module in which is it declared.
7	"Worse Is Better" the catchy title of one of the most fameous apologies (after Socrates', of course), is available from several sources: http://www.jwz.org/doc/worse-is-better.html is one such.

Works Consulted

[Bratko2001]

Prolog Programming for Artificial Intelligence, 3rd ed., Ivan Bratko, Addison-Wesley, Reading, Massachusetts, 2001.

(article originally posted January 3, 2006)

CoReader x CoState == Silver Bullet

Thesis:

The title reads: 'CoReader x CoState == Silver Bullet' ... of course, it isn't a silver bullet, but it surely reduces (exponential) complexity AND provides just-in-time realized constants that (e.g.) would, and do, strain and break production systems working on very large data sets.

So, it isn't a silver bullet, but it sure-as-heavens-to-betsy puts the 'oh, I'll just generate the (resource intensive) constant' approach and then 'oh, I just wrap each layer in another layer of if-then-else (kill me with code complexity)' approach up and down walls and mops them off the floor, please, and thank you.

Antithesis:

Okay, so the CoReader (co)monad is suppose to give you a constant, and it does ...

CoReader readValue context = (context, readValue) -> context

with the askC function:

askC :: (CoReader r c) -> r

and so you have your constant.

The thing is, the CoReader depends on the context to be preexisting, which can be troublesome for data that are realized from an environment that is established at some point after the program begins to run, and that problem is that if you want a realized constant, you can't have the CoReader be a final value in some program component (the context isn't there yet), and then, if you wait to establish the CoReader until after the data set is realized, then you have all this checking code and establishment code, that can be rerun at any time (and, most likely, every time) you ask for that constant, which means that you don't have a constant at all, but a new value every time you ask over a data stream.

Sub-optimal.

So, how does one get a realized constant from a data stream that takes time to establish and guarantee that, yes, that constant I asked for upstream or in another branch is the same constant that I'm getting now from my CoReader, because I'm not re-creating it each time I ask for a constant from the data stream I get after the program is started and initialized?

... e.g. (or, 'i.e.' in my particular case): a database connection takes time, and is usually not available with a system that needs a CoReader to be constant from the get-go.

My solution, after much head-banging with trying to make the CoReader, itself, be something that it isn't, is to have the CoReader not read the stream directly, because it may not be there or be ready, but to have the CoReader read a different 'stream' entirely: the State monad ...

Or actually, since I don't want to push all my computations thereafter up into the monadic domain, to use the CoState comonad, a.k.a. the Context comonad:

Context context value = Context (context -> value) context

with the very helpful putC function:

putC :: Context (context -> value) context -> newValue -> Context (context -> newValue) context

You're probably scratching your head, saying, "I don't see any putC in the literature..."

And, sure, you are correct, there's 'experiment' and 'modify' but then you see where I'm going ... a little this plus that gets you to putC and that's what we want from our CoState comonad: I'm in a context, gimme the thing I stowed away in there for later use without me having to thread all the baggage of a monad throughout my computation.

You wrap that in a CoReader and then you have the constifying functionality you need to say, hey, once the state is establish, then give me that constant value from then on.

So, given a data stream, context, that comes to us somewhere down the road, we have a CoState comonad, which I'll call box (for a mutable boxed type indexing into that stream, or 'context'), paired with the CoReader, reader, to give you a constant value in the pure-functional (not monadic) domain.

That's half of it.

The other half is this: now that you've got CoState paired with CoReader, you, functionally, know that this is the first read into the context, or if this the nth read where you're just returning the read/realized value.

So, what if you want to do something the first time, that you don't want to do anytime thereafter.

AND, what if you don't wish to encumber yourself with the old

if this-is-the-first-time-i'm-reading-and-initializing-this-stupid-constant
then do-something-special-here
else just-return-the-stupid-constant

logic that, well, encumbers too much programming logic everywhere?

The answer is surprisingly easy, once you have the CoState x CoReader pairing ...

With a little bit of monadic magic to provide the glue.

Because, the first time you read the constant, or, that is to say, just before the first time the constant value is ground to what (it is just about to) be(come), it's value is ... wait for it ...

Nothing.

As in Nothing :: Maybe.

That is, if you lift that (non)value into the monadic domain:

uninitializedValue = Nothing
value x = Just x

And, boom! You use mplus (or (+)) to do something magical the first time:

val (+) magical-initialization-code

equals your solution with dispensing with stupid boolean flags called 'inited' and stupid if-then-else tests everywhere that are now totally unnecessary, ... just redefine askC:

askC reader = realAskC reader (+) magical-initialization-code

and then you just ask for the constant, the reader gives it to you, in the pure-functional domain, and automagically does initialization code only on the first read of that constant.

Synthesis:

Real-world example.

"Yeah, geophf," you're saying, "nice whitepaper, but what can I use it for?"

Um, impress hot babes at cocktail parties?

Get a free 'tall' latte at sbux, ... that is, after you pass over a fiver?

(Okay, seriously, 5 bucks for a small coffee? What has the world come to?)

AND:

So, let's say you're working on one of the world's largest databases (every company claims to have at least one of them ...), and you're getting 10,000 records per hour, and one section is generating up to 5 indices, but you don't know which indices you need, and which you don't, as it depends on data down-stream, and since these records are highly hierarchical XML files, with each of the layers of the hierarchy optional, we're talking WAY down stream.

So, one approach, you just getSequence from the database for all the sequences you may need, and then you're good, you insert rows with the prepopulated sequence.

Hm, 10000 records per hour, 24x7 data feed, and int is how big? 2 billion ... only?

(start-rant: Okay, does EACH AND EVERY TEAM have to relearn that you exhaust int much sooner than expected so that your 'vital system' crashes with dev and production teams working round the clock to change int into a much bigger number, when, after all, these are sequences, not (necessarily) numbers (GUID are hexa-strings-of-numerals, so why not make your precious sequence strings that you will NEVER do arithmetic on anyway, so you've set it as an int, why? :end-rant)

So, from a purely optional data input, you are probably generating all these sequences, and bringing your project to a screeching halt much sooner.

How about this.

Wrap your sequence generator in a CoReader comonad, and wrap each optional insert in the Maybe monad.

What does this give you?

In a hierarchy, it give you that you don't create a sequence you don't use, ever.

And, five levels down, when you actually do do an insert of a child record who's parent wasn't there in the data feed? It 'automagically' generates the parent record from the dataflow trace, inserts that parent first, and then inserts your child record without throwing an 'integrity violation, parent not found' error, and since it's done in the monadic domain, you wrote 0, zero, zip, nada conditional code at each later.

> return layer1 (+) deferInsert1 >>= \deferred1 -> insertm (reader1 askC) [] >>
> return layer2 (+) deferInsert2 >>= \deferred2 -> insertm (reader2 askC) [deferred1] >>

etc, etc, to your heart's content.

Which is a very different thing than:

let seq1 = getSequence
    seq2 = getSequence
    seq3 = getSequence
...
in do val1 <- return layer1
        val2 <- return layer2
        val3 <- return layer3
...
        insertm seq1 val1
        insertm seq2 val2
        insertm seq3 val3
...

This example trivializes things a bit. Looking at it, it's obvious you want to defer the creation of the sequence until you know you have that row to insert into your database. Unfortunately, it is that obvious, and we intend to create thing only when needed, but then the 'real world' rears it's ugly head, and you're looking at a branching data flow where your sequence may be needed downstream if any of the branches result in an insert, and your tree is not binary, but nary, and several layers deep.

What do you do as a programmer?

Well, you just create the sequence, because you know you're going to use, because your test data says so, but the real stream is never that dogmatic and a whole lot sparser than your 'in-a-perfect-world' test cases anticipated.

And you have hundreds of tables, ... and just one of the tables has 100 million records added to it, each month.

Do you see where 'just create the sequence' can be a key factor in crippling your application soon after it goes live?

'Just create the sequence, because for each layer, a layer of complexity is added to this already complex system,' is one approach, and in industry, pretty much the standard approach.

I propose another way; in sum: the way proposed in this paper. Use the CoState x CoReader comonadic pairing to take all the complexity, put it into a paper bag, and then throw that bag into a black hole where you'll never see it again. If your data set is rife with optionality, that is: semideterminism, then wrap that semideterminism in a Maybe monad, and you have a powerful framework that is simple to understand and easy to use.

In a DBMS system I'm working on, the SLOC (lines of code) count decreased, AND the number of sequences generated decreased by a factor of 2-4. We were generating twice to four times as many sequences that we needed, ... per input record. With the CoState x CoReader x Maybe framework in place, this spurious sequence generation stopped, and the code became more declarative: I was saying what was to be done, much more so than how to go about doing it.

Monads in Java

A while back Brent Yorgey http://byorgey.wordpress.com posted a menagerie of types. A very nice survey of types in Haskell, including, among other things, the monadic types.

A reader posted a question, framed with 'you know, it'd be a lot easier for me to understand monads if you provided an implementation in Java.'[1]

Well, that reader really shouldn't have done that.

Really.

Because it got me to thinking, and dangerous things comes out of geophf's thoughts ... like monads in Java.

Let's do this.

Problem Statement

Of course, you just don't write monads for Java. You need some motivation. What's my motivation?

Well, I kept running up against the Null Object pattern, because I kept running up against null in the Java runtime, because there's a whole lot of optionality in the data sets I'm dealing with, and instead of using the Null Object, null is used to represent absence.

Good choice?

Well, it's expedient, and that's about the best I can say for that.

So I had to keep writing the Null Object pattern for each of these optional element types I encountered.

I encounter quite a few of them ... 2,100 of them and counting.

So I generalized the Null object pattern using generic types, and that worked fine ...

But I kept looking at the pattern. The generalization of the Null Object pattern is Nothing, and a present instance is Just that something.

I had implemented non-monadic Maybe.

And the problem with that is that none of the power of Maybe, as a Monad, is available to a generalized Null Object pattern.

Put another way: I wish to do something given that something is present.

Put another-another way: bind.

So, after a long hard look ('do I really want to implement monads? Can't I just settle for 'good enough' ... that really isn't good enough?), I buckled down to do the work of implementing not just Maybe (heh: 'Just Maybe'), but Monad itself.

Did it pay off? Yes, but wait and see. First the implementation. But even before that, let's review what a monad is.

What the Hell is a Monad?

Everybody seems to ask this question when first encountering monads, and everybody seems to come up with their own explanations, so we have tutorials that explain Monads as things as far-ranging from spacesuits to burritos.

My own explanation is to punt ... to category theory.

A monad is simply a triple (that's why it's called a monad, ... because it's a triple), defined thusly:

(T, η, μ)

Simple right?

Don't leave me!

Okay, yes. I understand you are rolling your eyes and saying 'well, that's all Greek to me.'

So allow me to explain in plain language the monad.

Monad is the triple (T, η, μ) where

• T is the Monad Functor
• η is the unit function that lifts an ordinary object (a unit) into the Monad functor; and,
• μ is the join function that takes a composed monad M (M a) and returns the simplified type of the composition, or M a.

And that is (simply) what the hell a Monad is. What a monad can do ... well, there are articles galore about that, and, later, I will provide examples of what Monad gives us ... in Java, no less.

The Implementation

We need to work our way up to Monad. There's a whole framework, a way of thinking, a context, that needs to be in place for Monad to be effective or even to exist. Monad is 'happy' in the functional world, so we need to implement functions.

Or more correctly, 'functionals' ... in Haskell, they are called 'Functors.'

A functor is a container, and the function of functors is to take an ordinary function, which we write: f: a → b (pronounced "the function f from (type) a to (type) b" and means that f takes an argument of type a and returns a result of type b), and give a function g: Functor a → Functor b.

Functor basically is a container for the function fmap: Functor f ⇒ (a → b) → (f a → f b)

Well, is Functor the fundamental type? Well, yes and no.

It is, given that we have functions defined. In Java, we don't have that. We have methods, yes, but we don't have free-standing functions. Let's amend that issue:

  public interface Applicable<T1, T2> {
      public T2 apply(T1 arg) throws Failure;
  };

And what's this Failure thingie? It's simply a functional exception, so:

  public class Failure extends Exception {
      public Failure(String string) { 
          super(string); 
      }
  

      /// and the serialVersionUID for serialization; your IDE can define that
  }

I call a Function 'Applicable' because in functional languages that's what you do: apply a function on (type) a to get (type) b. And, using Java Generics terminology, type a is T1 and type b is T2. So we're using pure Java to write pure Java code and none will be the wiser that we're actually doing Category Theory via a Haskell implementation ... in Java, right?

Right.

So, now we have functions (Applicable), we can provide the declaration of the Functor type:

  public interface Functor<F, T> {
       public <T1> Applicable<? extends Functor<F, T>,
                              ? extends Functor<F, T1>>
          fmap(Applicable<T, T1> f) throws Failure;
  

      public T arg() throws Failure;
  }

The above definition of fmap is the same declaration (in Java) as its functional declaration: it takes a function f: a → b and gives a function g: Functor a → Functor b

Okay, we're half-way there. A Monad is a Functor, and we have Functor declared.

The unit function, η, comes for free in Java: it's called new.

So that leaves the join function μ.

And defining join for a specific monad is simple. Join for the list monad is append. Join for the Maybe monad and the ID monad is arg. What about join for just Monad?

Well, there is no definition of such, but we can declare its type:

  public interface Joinable<F, T> extends Functor<F, T> {
      public Functor<F, ?> join() throws Failure;
  }

Too easy! you complain.

Well, isn't it supposed to be? Join is simply a function that takes a functor and returns functor.

The trick is that we have to ensure that T is of type Functor<F, ?>, and we leave that an implementation detail for each specific monad implementing join.

That was easy!™

Monad

So now that we have all the above, Functor, Join, and Unit, we have Monad:

... BUT WAIT!

And here's the interlude of where the power of Monad comes in: bind.

What is bind? Bind is a function that says: do something in the monadic domain.

Really, that sounds boring, right? But it's a very powerful thing. Because once we are in the monadic domain, we can guarantee things that we cannot in Java category (if there is such).

(There is. I just declared it.)[2]

So, in the monadic domain, a function thus bound can be guaranteed to, e.g., be working with an instance and not a null.

Guaranteed.

AND! ...

Well, what is bind?

Bind is a function that takes an ordinary value and returns a result in the monadic domain:

Monad m ⇒ bind: a → m b

So the 'AND!' of this is that bind can be chained ... meaning we can go from guarantee to guarantee, threading a safe computation from start to finish.

Monad gives us bind.

And the beauty of Monad? bind comes for free, for once join is defined, bind can be defined in terms of join:

Monad m ⇒ bind (f: a → m b) (m a) = join ((fmap f) (m a))

Do you see what is happening here? We are using fmap to lift the function f one step higher into the monadic domain, so fmap f gives the function Monad m ⇒ g: m a → m (m b) so we are not actually passing in a value of type a, we are passing in the Monad m a, and then we get back a type of m (m b) which then join does it magic to simplify to the monadic type m b.

So to the outside world, it looks like we are passing in an a to get an m b but this definition allows monadic chaining, for a becomes m a and then m (m b) is simplified to m b that — and here's the kicker — is passed to the next monadically bound function.

You can chain this as far as you'd like:

m a >>= f >>= g >>= ... >>= h → m z

And since the computation occurs in the monadic domain, you are guaranteed the promise of that domain.

There is the power of monadic programming.

Given that explanation, and remembering that bind can be defined in terms of join, let's define Monad:

  public abstract class Monad<M, A> implements Joinable<M, A> {
      public <T> Monad<M, T> bind(Applicable<A, Monad<M, T>> f) throws Failure {
          Applicable<Monad<M, A>, Monad<M, Monad<M, T>>> a
              = (Applicable<Monad<M, A> Monad<M, Monad<M, T>>>) fmap(f);
          Monad<M, Monad<M, T>> mmonad = a.apply(this);
          return (Monad<M, T>) mmonad.join();
      }
  

      public Monad<M, A> fail(String ex) throws Failure {
          throw new Failure(ex);
      }
  }

The bind implementation is exactly as previously discussed: bind is the application of the fmap of f with the joined result returned. So, we simply define join for subclasses, usually a trivial definition, and we have the power of bind automagically!

Now fail is an interesting beast in subclasses, because in the monadic domain, failure is not always a bad thing, or even an exceptional one, and can be quite, and very, useful. Some examples, fail represents 'zero' in the monadic domain, so 'failure' for list is the empty list, and 'failure' for Maybe is Nothing. So, when failure occurs, the computation can continue gracefully and not always automatically abort from the computation, which happens with the try/catch paradigm.

There you have it: Monads in Java!

The rest of the story: ... Maybe

So, we could've ended this article right now, and you have everything you need to do monadic programming in Java. But so what? A programming paradigm isn't useful if there are no practical applications. So let's give you one: Maybe.

Maybe is a binary type, it is either Nothing or Just x where x is whatever value that is what we're really looking for (as opposed to the usual case in Java: null).

So, let's define the Maybe type in Java.

First is the protocol that extends the Monad:

  public abstract class Maybe<A> extends Monad<Maybe, A> {
  

Do you see how the Maybe type declares itself as a Monad in its own definition? I just love that.

Anyway.

As mentioned before, fail for Maybe is Nothing:

      public Maybe<A> fail(String ex) throws Failure {
          return (Maybe<A>) NOTHING;
      }

(NOTHING is a constant in Maybe to be defined later. Before we define it ('it' being NOTHING), recall that a Monad is a Functor so we have to define fmap. Let's do that now)

      protected abstract <T> Maybe<T> 
              mbBind(Applicable<A, Monad<Maybe, T>> arg) throws Failure;
  

      public <T> Applicable<Maybe<A>, Maybe<T>>
                  fmap(final Applicable<A, T> f) throws Failure {
          return new Applicable<Maybe<A>, Maybe<T>>() {
              public Maybe<T> apply(Maybe<A> arg) throws Failure {
                  Applicable<A, Monad<Maybe, T>> liFted =
                          new Applicable<A, Monad<Maybe, T>>() {
                      public Maybe<T> apply(A arg) throws Failure {
                          return Maybe.pure(f.apply(arg));
                      }
                  };
                  return (Maybe<T>)arg.mbBind(liFted);
              }
          };
      }

No surprises here. fmap lifts the function f: a → b to Maybe m ⇒ g: m a → m b where in this case the Functor is a Monad, and this case, that Monad is Maybe.[3]

There is the small issue(s) of what the static method pure and the method mbBind are, but these depend on the definitions of the subclasses NOTHING and Just, so let's define them now.

      public static final Maybe<?> NOTHING = new Maybe() {
          public String toString() {
              return "Nothing";
          }
          public Object arg() throws Failure {
              throw new Failure("Cannot extract a value from Nothing.");
          }
          public Functor join() throws Failure {
              return this;
          }
          protected Maybe mbBind(Applicable f) {
              return this;
          }
      };

Trivial definition, as the Null Object pattern is trivial. But do note that the bind operation does not perform the f computation, but skips it, returning Nothing, and forwarding the computation. This is expected behavior, for:

Nothing >>= f → Nothing

The definition of the internal class Just is nearly as simple:

      public final static class Just<J> extends Maybe<J> {
          public Just(J obj) {
              _unit = obj;
          }
  

          public Maybe<?> join() throws Failure {
              try {
                  return (Maybe<?>)_unit;
              } catch(ClassCastException ex) {
                  throw new Failure("Joining on a flat structure!");
              }
          }
          public String toString() {
              return "Just " + _unit;
          }
          public Object arg() throws Failure {
              return _unit;
          }
          protected <T> Maybe<T> 
                  mbBind(Applicable<J, Monad<Maybe, T>> f) throws Failure {
              return (Maybe<T>)f.apply(_unit);
          }
          private final J _unit;
      }

As you can see, the slight variation to NOTHING for Just is that join returns the _unit value if it's the Maybe type (and throws a Failure if it isn't), and mbBind applies the monadic function f to the Just value.

And with the definition of Just we get the static method pure:

      public static <T> Maybe<T> pure(T x) {
          return new Just<T>(x);
      }

And then we close out the Maybe implementation with:

}

Simple.

Practical Example

Maybe is useful for any semideterministic programming, that is: where something may be true, or it may not be. But the question I keep getting, from Java coders, is this: "I have these chains of getter methods in my web interface to my data objects to set a result, but I often have nulls in some values gotten along the chain. How do I set the value from what I've gotten, or do nothing if there's a null along the way."

"Fine, no problems ..." I begin, but then they interrupt me.

"No, I'm not done yet! I have like tons of these chained statements, and I don't want to abort on the first one that throws a NullPointerException, I just want to pass through the statement with the null gracefully and continue onto the next assignment. Can your weirdo stuff do that?"

Weirdo stuff? Excusez moi?

I don't feel it's apropos that functionally pure languages have no (mutable) assignment, as that throws provability out the window and is therefore the root of all evil.

No matter how sorely tempted I am.

So, instead I say: "Yeah, that's a bigger problem [soto voce: so you should switch to Haskell!], but the same solution applies."[4]

So, let's go over the problem and a set of solutions.

The problem is something like:

  try {
      foo.setD(getA().getB().getC().getD());
      foo.setE(getA().getB().getC().getE());
  

      bar.setJ(getF().getG().getH().getJ());
      bar.setM(getF().getG().getK().getM());
  

      // and ... oh, more than 2000 more assignments ... 'hypothetically'
  

  } catch(Exception ex) {
      ex.printStackTrace();
  }

And the problem is this: anywhere in any chain of gets, if something goes wrong, the entire computation is stopped from that point, even if there are, oh, let's say, 1000 more valid assignments.

A big, and real, problem. Or 'challenge,' if you prefer.

Now this whole problem would go away if the Null Object pattern was used everywhere. But how to enforce that? In the Java category, you cannot. Even if you make the generic Null Object the base object, the null is still Java's ⊥ — it's 'bottom' — as low as you go in a hierarchy, null is still an allowable argument everywhere.

And if getA(), or getB(), or getC() return null you've just failed out of your entire computation with an access attempt to a null pointer.

Solutions

Solution 1: test until you puke

The first solution is to test for null at every turn. And you know what that looks like, but here you go. Because why? Because if you think it or code it, you've got to look at it, or I've got to look at it, so here it is:

  A a = getA();
  if(a != null) {
      B b = a.getB();
      if(b != null) {
          C c = b.getC();
          if(c != null) {
              foo.setD(c.getD());
          }
      }
  }

What's the problem with this code?

Oh, no problems, just repeat that deep nesting for every single assignment? So you have [oh, let's say 'hypothetically'] 2000 of these deeply nested conditional blocks?

And, besides the fact that it entirely clutters the simple assignment:

foo.setD(getA().getB().getC().getD());

in decision logic and algorithms that are totally unnecessary and entirely too much clutter.

All I'm doing is assigning a D to a foo! So why do I have to juggle all this conditional code in my head to reach that eventual assignment.

Solution 1 is bunk.

Solution 2: narrow the catch

So, solution 1 is untenable. But we need to assign where we can and skip where we can't. So how about this?

  try {
      foo.setD(getA().getB().getC().getD());
  } catch(Exception ex) {
      // Intentionally empty; silently don't assign if we cannot;
  }
  

  try {
      foo.setE(getA().getB().getC().getE());
  } catch(Exception ex) {
      // ditto
  }
  

  try {
      bar.setJ(getF().getG().getH().getJ());
  } catch(Exception ex) {
      // ditto
  }
  

  try {
      bar.setM(getF().getG().getK().getM());
  } catch(Exception ex) {
      // ditto
  }

And I say to this solution, meh! Granted, it's much better than solution 1, but, again, you made a computational flow described declaratively in the problem to be these set of staccato statements, having the reader of your code switch into and out of context for every statement.

Wouldn't it be nice to have all the statements together in one block, because, computationally, that's what is happening: a set of data is collected from one place and moved to another, and that is what we wish to describe by keep these assignment grouped in one block.

Solution 3: Maybe Monad

And that's what we can do with monads. It's going to look a bit different that how you're used to the usual Java fair, as we have to lift the statements in the Java category into expressions in the monadic one.

So here goes.

First of all, we need to define generic functions (not methods![5]) for getting values from objects and setting values into object in the monadic domain:

  public abstract class SetterM<Receiver, Datum>
          implements Applicable<Datum, Monad<Maybe, Receiver>> {
      protected SetterM(Receiver r) {
          this.receiver = r;
      }
  

      // a monadic set function
      public final Monad<Maybe, Receiver> apply(Datum d) throws Failure {
          set(receiver, d);
          return Maybe.pure(receiver);
      }
  

      // subclasses implement with the particular set method being called
      protected abstract void set(Receiver r, Datum d);
  

      private final Receiver receiver;
  }

This declares a generic setter, so to define setD on the foo instance, we would do the following:

      SetterM<Foo, D> setterDinFoo = new SetterM<Foo, D>(foo) {
          protected void set(Foo f, D d) {
              f.setD(d);
          }
      };

The getter functional is similarly defined, with the returned value lifted into (or 'wrapped in,' if you prefer) the Maybe type:

  public abstract class GetterM<Container, Returned>
          implements Applicable<Container, Monad<Maybe, Returned>> {
  

      public Monad<Maybe, Returned> apply(Container c) throws Failure {
          Maybe<Returned> ans = (Maybe<Returned>)Maybe.NOTHING;
          Returned result = get(c); 
  

          // c inside the monad is guaranteed to be an instance
          // but result has NO guarantees!
  

          if(result != null) {
              ans = Maybe.pure(result);  
              // and now ans is inside the monad it must have a value.
              // ... even if that value is NOTHING
          }
          return ans;
      }
  

      protected abstract Returned get(Container c);
  }

With the above declaration, a getter monadic function (again, not method) is simply defined:

      GetterM<A, B> getterBfromA = new GetterM<A, B>() {
          protected B get(A a) {
              return a.getB();
          }
      };

In Haskell, the bind operator has a data-flow look to it: (>>=), so writing one of the 'assignments' is as simple as flowing the data to the setter:

getA >>= getB >>= getC >>= getD >>= setD foo

But we have no operator definitions, so we must soldier on using the Java syntax:

      try {
          getterA.apply(this).bind(getterBfromA).bind(getterCfromB).bind(getterDfromC).bind(setterDinFoo);
      } catch {
          // a superfluous catch block
      }

That's one of the assignment expressions.[6]

Let's walk through what happens with a couple of examples.

Let's say that A has a value of a, but B is null. What happens?

1. getterA forwards Just a to getterBfromA
2. getterBfromA gets a null, converts that into a NOTHING and forwards that to getterCfromB
3. getterCfromB forwards the NOTHING to getterDfromC
4. getterDfromC forwards the NOTHING to setterDinFoo
5. setterDinFoo simply returns NOTHING.

And we're done (that is: we're done doing, literally: NOTHING).

Let's counter with an example where every value has an instance:

1. getterA forwards Just a to getterBfromA
2. getterBfromA gets a b, converts that into Just b and forwards that to getterCfromB
3. getterCfromB gets a c, converts that into Just c and forwards that to getterDfromC
4. getterDfromC gets a d, converts that into Just d and forwards that to setterDinFoo
5. setterDinFoo gets the wrapped d and sets that value in the Foo instance.

Voilà!

The beauty of this methodology is that we can put them all into one block, and every expression will be evaluated and in a type-safe manner, too, as NOTHING will protect us from a null pointer access:

      try {
          getterA.apply(this).bind(getterBfromA).bind(getterCfromB).bind(getterDfromC).bind(setterDinFoo);
  System.out.println("Hey, I've executed the first assignment");
  getterA.apply(this).bind(getterBfromA).bind(getterCfromB).bind(getterEfromC).bind(setterEinFoo);
  System.out.println("...and the second...");
  getterF.apply(this).bind(getterGfromF).bind(getterHfromG).bind(getterJfromH).bind(setterJinBar);
  System.out.println("...and third...");
  getterF.apply(this).bind(getterGfromF).bind(getterKfromG).bind(getterMfromK).bind(setterMinBar);
  System.out.println("...and fourth...");
  

  // another more than 2000 of these expressions
  System.out.println("...and we're done with every assignment we could assign...");
  

      } catch {
          // a superfluous catch block
      }

And, because the monadic Maybe works it does, every assignment that can occur will, and ones that cannot will be 'skipped' (by flowing NOTHING through the rest of the computation, and the proof will be in the pudding ... on the standard output will be all the statements printed.

Summary

We presented an implementation of monads in Java, with a concrete example of the Monad type: the Maybe type. We then showed that by putting a computational set into the monadic domain, the work can be performed in a type-safe manner, even with the possible presence of nulls. This is just one example of practical application of monadic programming in Java: the framework presented here confers the benefits of research of monadic programming in general to projects done in Java. Use the framework to discover for yourself the leverage monadic programming gives.

---

End notes

[1]	Exact verbage: Phil says: January 14, 2009 at 7:01 pm I think that this could all be easily cleared up if one of you FP guys would just show us how to write one of these monad thingies in Javaâ To which a semi-mocking response was: 'you know, objects would be a lot easier for me to understand if you provided an implementation in Haskell.' Exact verbage: Cory says: April 23, 2009 at 6:26 am I may be a bit late to the game here, but Phil, that can be rephrased: I think that this could all be easily cleared up if one of you OO guys would just show us how to write one of these object thingies in Haskellâ Of course you can, but it's a different type of abstraction for a different way of thinking about programmingâ I write 'semi-mocking,' because: 1. OOP with message passing has been implemented in a Haskell-like language: Common Lisp. The Art of the Metaobject Protocol, a wonderful book, covers the 'traditional' object-oriented programming methodology, and its implementation, quite thoroughly and simply.
[2]	I leave it as an exercise to the reader to scope the Java category (Consult the Ω-calculus papers, Cardelli, et al;).
[3]	Monad<Maybe, A> and Maybe<A> are type-equivalent (but try telling the poor Java 1.6 compiler that).
[4]	"The same solution applies!" Geddit? Haskell is an applicative language, so the same solution applies! GEDDIT?
[5]	The distinction I raise here between methods and functions is the following: a method is enclosed in and owned by the defining class. A function, on the other hand, is a free-standing object and not necessarily contained in nor attached to an object.
[6]	Again, there is a distinction between an expression and a statement. An expression returns a value; a statement does not. A statement is purely imperative ... 'do something.' On the other hand, an expression can be purely functional ... 'do'ing nothing, as it were, e.g.: 3 + 4. A pure expression has provable properties that can be attached to it, whereas it is extremely difficult to make assertions about statements in the general sense. The upshot is that having pure (non-side-effecting) expressions in code allows us to reason about that code from a firm theoretical foundational basis. Such code is easier to test and to maintain. Side-effecting statement code make reasoning, testing and maintaining such code rather difficult.

Attributed Variables: their uses and one implementation

Here's a problem that comes up enough, computationally: find a value within some range. You don't know what the value is at the moment, but you will know it, eventually, as the range becomes further restricted by refinements of the constraints or data.

Now, in general, this is an easy problem for Haskell to solve, and Haskell provides more than one way to approach the solution. For example, if we have some x in some domain D, one way to look at an arbitrary x until we find the one, true x we are looking for is the following code snippet:

> [ x | x <- D, ... further constraints ]

More variables? Interrelated ones? No problem:

> [ (x, y, z) | x <- D, y <- D, z <- D, x < y, ... further constraints ]

Okay, let’s take it to the next level. What if the interrelation is such that one variable consumes from the domain, so that value is now unavailable to other variables. Pithily: the variables’ values are mutually exclusive.

Well, one way to go about that is to embed a guard for each variable into the list compression:

> [ (x, y, z) | x <- D, y <- D, y /= x, z <- D, z `notElem` [x,y], ...

The drawback here is that this kind of guarded coding becomes tedious and prone to errors. On top of that we see that the guard follows the select, causing unnecessary backtracking through the search space,[1] especially given that we know the guarded values a priori.

Well, then, we can automate guarded selection with a state (transformer) monad:[2]

> ...
> f = do x <- choose
>        y <- choose
>        z <- choose
> ...
> runStateT f [0..9]

Okay, excellent! All of this works and works well … for a fixed and predetermined variable set.

The Problem

Things start to get tricky for me, programmatically, however, when one set of constrained values spill over onto another set of constrained values, such as the results of one generation in a cellular automata set or genetic (algorithm) pool affect the next set:

> evalStateT (gen row1guards) domain >>= \ans1 ->
>   evalStateT (gen (row2guards ans1)) domain >>= \ans2 ->
>     evalStateT (gen (row3guards ans1 ans2)) domain >>= \ans3 ->
> ... etc

The state transformer isn’t enough, so it needs to be some RWS monad, perhaps pushing the interim results into the Reader monad and the accumulated ones into Writer while the State monad handles the flow of the computation?

It seems to me that the work becomes more about monad management and less about the computation itself.[3]

Then there’s the even more general computation. What if we do not know, a priori, how many values we are generating in our problem solving? The problem space I’m looking at is something like:

For a variable number of variables, map selection and guards for each variable.

How do I write that as a list compression expression, or as a monadic one? The problem with Haskell variables is that they aren't (variables), and so something so easily accomplished in a Prolog program:

kakuro([], Vars, Functor) :-
    Fn =.. [Functor, Vars],
    call(Fn).
kakuro([H|T], Acc, Functor) :-
    assign(H),
    kakuro(T, [H|Acc], Functor).

called with:

?- kakuro([A, B, C, D], [], sum_equals_10).

or:

?- kakuro([X, Y, Z], [], sum_equals_10).

... or with a list of any other length isn't so easily written out in Haskell when I go to attack the problem. After all, what is the type of a list of unbound variables? Haskell doesn't (so easily) allow this, and I was stuck: I didn't know how to proceed using monadic programming or list compression.

A solution

Fortunately for me, I've been studying constraint-based programming, and that research has let me to some papers on attributed variables[4] which faciliate that programming style.

Attributed variables are variables ranging over a domain that can have attributes attached to them that restrict (or constrict) the range of values. It's a very simple step to go from a set of unbound attributed variables to a (simple or façile) constraint solver by adding (constraining) attributes to the variables.

More formally, I declare (denotationally) an attributed variable as:

> data Attribute a = Attribute [Constraint a] (Domain a)

where Constraint and Domain are declared as:

> newtype Constraint a = Constraint { resolve :: a -> Bool }

> type Domain a = [a]

Or, to put words to it, an Attributed Variable is an object that has a set of (constraining) functions over an assigned domain.[5]

The above denotational declaration of attributed variables works, but I find, operationally, grounding an attributed variable once it's reduced to a single value to be useful:

> data Attribute a = Attribute [Constraint a] (Domain a)
>     | Ground a

So, that's my declaration.[8] How is this implemented in practice?

Implementation

The approach I take is that an attributed variable is created in a free state over its domain:

> makeAttrib :: Domain a -> Attribute a
> makeAttrib list = Attribute [] list

And then, as constraints are added to the attributed variable, the system 'tries to solve' the attributed variable over the set of the constraints:

> constrain (Attribute constraints dataset) constraint
>    = solve (Attribute (Constraint constraint:constraints) dataset)
> constrain (Ground x) _ = Ground x

And if the solution results in a singleton list, then the attributed variable becomes Ground:

> solve attr@(Attribute _ []) = attr
> solve attr@(Attribute constraints list@(h:t))
>    = let result = solve' constraints list
>      in if length result == 1
>         then Ground (head result)
>         else Attribute constraints result

Of course, the 'solution' to a Ground attributed variable is itself:

> solve (Ground x) = Ground x

The above code is simply a dispatch along the binary type. The worker-bee, solve' is simply (again) an implementation of the dual of filter:

> solve' :: [Constraint a] -> [a] -> [a]
> solve' _ [] = []
> solve' constraints (h:t) =
>    if   (solveConstraints constraints h)
>    then (h:solve' constraints t)
>    else solve' constraints t

> solveConstraints :: [Constraint a] -> a -> Bool
> solveConstraints [] _ = True
> solveConstraints (f:rest) x = resolve f x && solveConstraints rest x

So something from Control.Applicative to reduce that to a one-liner? I leave that as an exercise to the reader.

And there you have it, that is a working implementation of attributed variables. I have test functions for groundedness, solvability and the current state of the domain of an active attributed variable, but those are simple helper functions, easily implemented, and provided in the attached source code.

Uses

So, now, what do we have?

Now we have variables over which we may specify a domain ('loosely' typing a variable) and then constrain. How can we use such a system?

One way is that we can write constraint logic programs in Haskell. The illustration from Prolog (above) has a nearly direct transliteration into Haskell (with the additional benefit of strong typing):

> kakuro :: [Int] -> Int -> [[Int]]
> kakuro list total = nub $ summer (sort $ map trib list) [] total

> trib :: Int -> Attribute Int
> trib x | x == 0    = makeAttrib [1..9]
>        | otherwise = Ground x

> summer :: [Attribute Int] -> [Int] -> Int -> [[Int]]
> summer [] list total = do
>    guard $ sum list == total
>    return $ sort list
> summer (h:t) list total = do
>     a <- domain $ constrain h (flip notElem list)
>     summer t (a:list) total

And with the above code, we can now do the following:

*Kakuro> kakuro [0,0,0] 10
[[1,2,7],[1,3,6],[1,4,5],[2,3,5]]
*Kakuro> kakuro [0,0,0,0] 10
[[1,2,3,4]]

Note that I use sort above, but attributed variables are not (denotationally) ordered types. Operationally, that is: in logical programming, it makes sense to eliminate early, so if we have Ground values, we wish to consume those first. So, to that end, I declare the following instances:

> instance (Eq a) => Eq (Attribute a) where
>     Ground x == Ground y = x == y
>     _        == _        = False

> instance (Ord a) => Ord (Attribute a) where
>     Ground x <= Ground y = x <= y
>     Ground _ <= _        = True
>     _        <= _    = False

And with those instance declarations, sort automagically works. Neat!

Interlude: Haskell is "Neat"

I don't know about you, but I'm guessing that many of you are taking the gift that Haskell is for granted. Or I suppose I should say 'the way of thinking that using Haskell provides.' Over and over again in industry (yes: stone knives and bearskins) I hear 'that can't be done.' And I find myself puzzled. What's the showstopper here?

For example, this past week at work, we needed to convert a data mapping document in Excel (stop snickering, please) into an equivalently flat XML schema representation with a accompanying XML sample file. So fields of the form:

/Field/Name="BusinessAddress"
/Field/Value="plaintext"

/Field/Name="BusinessAddress"
/Field/Value="encrypted"

And there were enumerated values as well:

/Field/Name="PropertyOccupancyTypeOwnerOccupied"
/Field/Value="plaintext"

/Field/Name="PropertyOccupancyTypeRentedToTenant"
/Field/Value="plaintext"

/Field/Name="PropertyOccupancyTypeVacant"
/Field/Value="plaintext"

There were over 1,000 of these element names. I mentioned I would write a parser to generate the XSD and XML and was told by the development team point-blank that that was impossible and the only way to go about this transcription was manually, line-by-line, by hand.

So I wrote the script. I suppose I could have used Perl, but as I'm on a Windows box, the shell isn't very inviting for Perl-like piping, so I used Haskell, stripping the metainformation and pushing the parsed names into a map (or, to be precise, a Data.Map) where enumerated (mutally exclusive instance) types went into a list named by their type name and other values were singletons. Then for the XSD I simply iterated over the elements of the map (recursively), and for the sample XML file, I just chose an element (in this case, the first element) of each type.

The net result was that all the elements analysis team compiled into an Excel spreadsheet by hand over a six week period I was able to deliver in two days as a full XSD schema and a comprehensive XML sample file.

Two members from the development team assisted me on this task, one of them was the lead developer. He was intrigued and asked me: "What does this script do?" after being impressed that he could generate a schema definition file and a sample file in seconds. So I explained Haskell as a 'data-flow' language and I traced the flow of the input file through the monad and function composition showing the translation of the internal representation into XSD and then, in a different context, into XML. I'm not sure he got my explanation, but he did walk away impressed with what Haskell can do.

Yes, these are simple things: parsing, mapping, iterating. But for most of the software engineering community in industry, it is easier and faster to go through, line-by-line, by hand, than to write a piece of code to automate that process ("Can that even be done?" "No, it's impossible, just do it manually").

I have encountered this over and over again in industry. Teams are willing to expend more than two hundred person hours to a reoccuring task and are willing to accept the associated fatigue errors to schedule systems by hand. Then they are shocked that I build a functional or logic-based system that autogenerates a pristine result in sub-second time.

Where does this leave us?

What I see as status quo is that industry is resigned to slog through repetitive tasks manually, because it's too hard in Language X to consider tackling the problem: more time would be spent writing, compiling and fixing a program to do the task than to do the task by hand.

On the academic side, I see researchers isolated from industry, feeling their advances have no practical use as there appears to be no interest from industry. I attended a talk on dependent types where the thesis was that this typing makes coding more declarative, more powerful and less error prone. I approached the lecturer and asked how I could implement such a system and was asked what application dependent types had for industry.

Hm. Let me think on that for a while.

Why would industry be interested in coding more declaratively, more powerfully, and with less errors? I was flabbergasted that the researcher saw no benefit for industry in his presentation.

We have a powerful tool in Haskell. We can do more, cleaner, safer, and do it faster than the mainstream alternatives industry picks over and over again by default.

I've found, however, that talking about typing, or monads, or pure functional programming only causes the eyes to glaze.

What lights a fire in management's eyes? When you rescue an overdue project, delivering before the deadline, and you educate other workers to be as productive ... perhaps not writing Haskell themselves (I've been asked: "Is it like Pascal?" ... and that's after a code walkthrough), but using the tools you've used to deliver these 'tremendous' results, and earning their trust that when you say, 'just let me write a Haskell script to do that: I'll take a day to write it, and we'll start getting results right away,' that that is actually what happens. I've found that 'we should use Haskell because of [all the wonderful arguments put forward]' does not convince anybody. Delivering 'incredible' and 'impossible' results, significantly faster than anticipated (two days instead of two months for the XML project)? That moves mountains.

Where I work, Haskell is installed on two lead developer's systems other than my own, and I'm given permission to code in Haskell, on a 'we only allow Language X' project.

Other Uses

So attributed variables can be used to help one solve kakuro puzzles, or to write a sudoku solver. Fine.

And I've been inching my way toward attributed variables, so it can be applied to symbolic logic puzzles as well, replacing my Whatever type with attributed variables over the enumerated domain.

So the domain is not restricted to Number, but these are not very interesting or pragmatic examples in and of themselves. Not very gripping.

So how about this example?

*Stocks> makeAttribute [Buy, Sell, Hold]

with Constraints being input feeds filtered through weighted moving averages and other indicators. Now this is a system of keen interest for me and 'currently under active and intense research.'

Will such a system work or not work? I'm not at liberty to say,[9] but here is an area that appears to fit well in the language space of constraint programming.

As problem spaces attacked by software projects — workflow analysis, data mining, planning and scheduling, budgeting, forecasting, (war)gaming, modelling and simulation — many seem good candidates to use constraint-based reasoning. Attributed variables give Haskell programmers another way to express these problem domains.

---

Endnotes:

[1] Y’all don’t mind if I speak logically, and in the logic-programming paradigm, do you?

[2] See my article in The Monad.Reader, issue 11, “MonadPlus: What a Super Monad!” for an implementation of choose, et al.

[3] No, I’m not speaking disparagingly of the monadic programming style. I rather like that style, and use it in my domain language of predicate logic that I layer on top of ‘regular’ Haskell programming. The beauty of monads, for me, is that they are invisible (in coding them) and powerful (in their effect). When the code becomes more about monads and less of what they are there to do is when I see this as an opportunity to examine things in a different light.

[4] http://www.swi-prolog.org/pldoc/doc_for?object=section(2,'6.1',swi('/doc/Manual/attvar.html'))

[5] My representation of Domain is straightforward and workable for most cases, but it hides more than a few compromises (or 'sell-outs') beneath the surface. For example, it makes the (gross) assumption that the range of the domain is enumerable. If Domain is in ℜ that no longer holds (at all), so then Domain shouldn't have a list representation but a pair (or bookending) bounds. But then what if Domain extends beyond ℜ and goes into the surreal numbers?[6] Then we have infintesimals such as '*' (pron: 'star') where:

* > 0, * < 0, * + * = 0

and:

* || 0 (that is: 'star' is incomparable to 0)

So how does one bounds-check on incomparables?

But these concerns are, in the main, not ones to lose one's head over. For the most part, simple linear programming solves a vast majority of the World's problems,[7] and those interesting cases are exactly that: interesting cases.

[6] http://en.wikipedia.org/wiki/Surreal_number

[7] The preface of How to Solve It: Modern Heuristics by Zbigniew Michalewicz and David B. Fogel makes this assertion, from hard-won experience in the field. Seconded.

[8] This is one approach to attributed variables, that is: constraints or attributes are applied to the variable over the domain until it is reduced to a single value, at which point the constraints and even the domain become superfluous and simply go away. An advantage to this approach is that a test for groundedness becomes trivial. A disadvantage is that once grounded one loses the path or information that got one there except through the data flow through the algorithm (the stack trace, as it were). Another disadvantage is that an attributed variable, once grounded, automatically rejects constraints. This may lead to unexpected program behavior, because AV grounded to 5 with a new constraint of x > 23 should fail, but my implementation forwards the 5 value in a success state.

[9] An audit trail of at least a year of data is necessary before any claims can be made.

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