Long Time no See

I realise it has been almost two months since I last blogged, I can only plead two excuses for this lapse. The first reason is that I have met an incredible woman and have dedicated a substantial amount of time recently in getting to know her better. The second is that on the 26th of December, Tucana Technologies (my employer) closed its doors. This is an incredible blow as without reservation, this was the best job I have ever had. I can only hope that I will be able to find something half as involving, challanging, and inspiring as my work on Kowari and RDF. Anyway, unless I should suddenly find myself with employment I should be able to address some of the unfinished posts I have lined up for this blog over the next week or two.

On that note, I have spent some time trying to install GHC under OSX 10.2, unfortunately the only install I have been able to find and install thus far is for 10.3. If anyone out there knows of a package or install method for 10.2 it would be much appreciated.

Finally if anyone is interested in employing a Senior Computer Systems Engineer with a strong background in metadata, RDF, and in the use and design of more languages than you can poke a stick at, feel free to contact me on andrae@humbug.org.au; CV available on request.

Well worth the time.

Went back and watched two of the Little Languages 2 Workshop presentations. Specifically Joe Armstrong and Todd Proebsting's presentations on "Concurrency Orientated Programming", and "Disruptive Programming Language Technologies" respectively. I highly recommend both these talks to anyone who is the slightest bit interested in programming languages, or has any serious involvement in development. It is just unfortunate that they are only available as real-video. Still if you have r-v installed, they are both well worth the time.

• Concurrency Oriented Programming in Erlang (invited talk); Joe Armstrong, Swedish Institute of Computer Science.
• Disruptive Programming Language Technologies (invited talk); Todd Proebsting, Microsoft Research.

Note these are links to the two sessions of the workshop. It's convenient that both my favourite talks from this workshop happen to be first in each session.

The Theory of Classification.

Andrew Newman came across this set of articles on OO theory. I stumbled across them about a year ago, read the first few, changed jobs, and promptly forgot to go find them again. I remember them as well worth the time to read.

This is the first article in a regular series on object-oriented type theory, aimed specifically at non-theoreticians. The object-oriented notion of classification has for long been a fascinating issue for type theory, chiefly because no other programming paradigm has so sought to establish systematic sets of relationships between all of its types. Over the series, we shall seek to find answers to questions such as: What is the difference between a type and a class? What do we mean by the the notion of plug-in compatibility? What is the difference between subtyping and subclassing? Can we explain inheritance, method combination and template instantiation? Along the way, we shall survey a number of different historical approaches, such as subtyping, F-bounds, matching and state machines and seek to show how these models explain the differences in the behaviour of popular object-oriented languages such as Java, C++, Smalltalk and Eiffel. The series is titled "The Theory of Classification", because we believe that all of these concepts can be united in a single theoretical model, demonstrating that the object-oriented notion of class is a first-class mathematical concept!

Anyway, the links:

"The Theory of Classification"

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, and 15.

Links found.

Just noting that I have updated the Arrows 'n Robots summary with links to citeseer and Wan's thesis page on the Yale-group pages. Also wanted to dump the url to the Yale group here so next time I can find it more easily.

http://haskell.cs.yale.edu/yale/ http://haskell.cs.yale.edu/yale/publications.html

Category Theory

I have had a few people ask me to explain the utility and signifigance of category theory. This proves rather difficult given I am a complete novice in this area myself; desprately trying to keep my head above water in the simplest of papers. Still I found this paragraph useful, and I decided to post it here so I can find it again.

Category theory unifies mathematical structures in a second, perhaps even more important, manner. Once a type of structure has been defined, it quickly becomes imperative to determine how new structures can be constructed out of the given one and how given structures can be decomposed into more elementary substructures. For instance, given two sets A and B, set theory allows us to construct their cartesian product A X B. For an example of the second sort, given a finite abelian group, it can be decomposed into a product of some of its subgroups. In both cases, it is necessary to know how structures of a certain kind combine. The nature of these combinations might appear to be considerably different when looked at from too close. Category theory reveals that many of these constructions are in fact special cases of objects in a category with what is called a "universal property". Indeed, from a categorical point of view, a set-theoretical cartesian product, a direct product of groups, a direct product of abelian groups, a product of topological spaces and a conjunction of propositions in a deductive system are all instances of a categorical concept: the categorical product. What characterizes the latter is a universal property. Formally, a product for two objects a and b in a category C is an object c of C together with two morphisms, called the projections, p: c → a and q: c → b such that, and this is the universal property, for all object d with morphisms f: d → a and g: d → b, there is a unique morphism h: d → c such that p o h = f and q o h = g. Notice that we have defined a product for a and b and not the product for a and b. Indeed, products and, in fact, every object with a universal property, are defined up to (a unique) isomorphism. Thus, in category theory, the nature of the elements constituting a certain construction is irrelevant. What matters is the way an object is related to the other objects of the category, that is, the morphisms going in and the morphisms going out, or, put differently, how certain structures can be mapped into it and how it can map its structure into other structures of the same kind.

Jean-Pierre Marquis, Stanford Encyclopedia of Philosophy: Category Theory

Arrows, Robots, and Functional Reactive Programming --- Summary

First some background reading from the bibliography I'll have to read eventually:

• John Hughes. Generalising monads to arrows. Science of Computer Programming, 37:67-111, May 2000
• Ross Paterson. A Notation for Arrow-based Libraries. In ICFP'01: International Conference on Functional Programming, pages 229-240, Firenze, Italy, 2001
• Zhanyong Wan. Functional Reactive Programming for Real-Time Embedded Systems. PhD thesis, Department of Computer Science, Yale University, December 2002
• Zhanyong Wan, Walid Taha, and Paul Hudak. Real-time FRP. In Proceedings of Sixth ACM SIGPLAN '00 Conference on Programming Language Design and Implementation (PLDI), pages 242-252, Vancouver, BC, Canada, June 2000. ACM, ACM Press.
• Zhanyong Wan, Walid Taha, and Paul Hudak. Event-driven FRP. In Proceedings of Fourth International Symposium on Practical Aspects of Declarative Languages. ACM, Jan 2002

Naturally when you are using FRP the core concept is that of the signal. So we define signal to have the type Signal a = Time -> a, ie a function of Time returning a value of type 'a'; s(t). The robot used throughout the paper is a simple differential drive with a handful of basic sensors. So given two signals vr(t) -> vr::Signal Double and vl(t)vl::Signal Double which are the velocities of the right and left wheels respectively we can write an reactive program for calculating the robots position:

x     = (1 / 2) * integral ((vr + vl) * sin theta)
y     = (1 / 2) * integral ((vr + vl) * cos theta)
theta = (1 / l) * integral (vr - vl)

Of course the nice thing about this program is that it is a direct transliteration of the physics equations governing the motion of such a robot! This is why FRP is important.

Such programs are clear, consise, correct, and unfortunately completely unworkable in the general case. The problem is that while in the small (with simple toy examples) you couldn't get better than this, larger programs tend to lead to opaque space and time management with the resultant space and time leaks. The focus on this paper is how to retain most of the legibility and good domain match of FRP while preventing leaks. The FRP DSL developed in this paper is called Yampa, and it solves the leak problem by disallowing signals as first class values. Instead signals are manipulated indirectly via set of combinators called signal transformers or signal functions.

SF a b = Signal a -> Signal b

This of course is very similar to the Haskell IO or State monads, and reminisent of Hutton's Monadic Parser Combinators. On the other hand, as presaged by the subject, the authors use Arrows rather than Monads as the basis for their combinator library.

A good analogy for this idea is a state or IO monad, where the state is hidden, and a program consists of a linear sequencing of actions that are eventually run by an interpreter or the operating system. But in fact arrows are more general than monads, and in particular the composition of signal functions does not have to be completely linear

Specifically Arrow contains a fixedpoint combinator loop which provides access to recursion.

The basic combinators include.

lift function: arr :: ( a -> b ) -> SF a b

Takes a normal function from type 'a' to 'b', and returns a signal-function/transformer that will convert a signal of type 'Signal a' to 'Signal b'.

compose: (>>>) :: SF a b -> SF b c -> SF a c

Takes two signal functions and returns the composition of them

tuping: (&&&) :: SF a b -> SF a c -> SF a (b, c)

This permits you to take one signal and apply two functions to it similtaniously producing two signals both independently derived from the input. And of course, once you have tupled outputs....

tuple-transform: (***) :: SF a b -> SF c d -> SF (a c) (b d)

Take two signal functions and returns a transformer that applies them to the respective signals in a tupled signal.

Now arr, (>>>), and (&&&) form a minimal universal set. However to fit the Arrow framework defined by Hughes, we use the original minimal set defined as arr, (>>>), and first (which only takes one argument, and applies it to the first signal in the tuple, passing the second unchanged).

Some standard combinators provided:

• identity :: SF a a
• constant :: b -> SF a b
• time :: SF a Time

Also the standard arrow combinators (remember, when thinking of FRP, just substitute 'SF' for 'a' in the type-sigs):

• arr :: Arrow a => (b -> c) -> a b c
• arr2 :: Arrow a => (b -> c -> d) -> a (b, c) d
• (>>>) :: Arrow a => a b c -> a c d -> a b d
• (<<<) :: Arrow a => a c d -> a b c -> a b d
• first :: Arrow a => a b c -> a (b, d) (c, d)
• second :: Arrow a => a b c -> a (d, b) (d, c)
• (***) :: Arrow a => a b c -> a b' c' ->a (b, b') (c, c')
• (&&&) :: Arrow a => a b c -> a b c' -> a b (c, c')
• loop :: Arrow a => a (b, d) (c, d) -> a b c

Note that with loop, 'd' provides a channel for feedback, and hence recursion. Notice also the strong streamish feel to the api. I would like to see a Arrow based treatment of the unix-pipe concept. I think it could result in a powerful scripting framework. Also worth noting that some signal functions are stateful (integral is one example), and as such cannot be defined without access to the underlying signals (forbidden). Hence they must either be pre-defined, or defined as a combination of pre-defined stateful signal functions.

So now convert the original FRP expression for x(t) to raw arrow-form:

x = (1/2) * integral ((vr + vl) * cos theta)

given: vrSF :: SF RobotInput Velocity  (SF that extracts vr from a RobotInput)
   and vlSF :: SF RobotInput Velocity  (SF that extracts vl from a RobotInput)
   and thetaSF :: SF RobotInput Angle

xSF :: SF RobotInput Distance   -- Signal Function transforming RobotInput -> Distance
xSF = (((vrSF && vlSF) >>> arr2 (+)) &&& (thetaSF >>> arr cos)) >>> arr2 (*) >>> integral >>> arr (/2)
  or slightly more legible:
xSF = let v = (vrSF &&& vlSF) >>> arr2 (+)
          t = thetaSF >>> arr cos
      in (v &&& t) >>> arr2 (*) >>> integral >>> arr (/2)
  which isn't all that much better.

So what we have gained above is the ability to mediate access to signals behind a reasonably safe, yet complete abstraction. However the loss in clarity is striking. Fortunately there is a proposed arrow-syntax that is similar to Haskell's monadic do-syntax.

xSF' :: SF RobotInput Distance
xSF' = proc inp -> do
  vr    <- vrSF     -< inp
  vl    <- vlSF     -< inp
  theta <- thetaSF  -< inp
  i     <- integral -< (vr + vl) * cos theta
  returnA -< (i / 2)

Which while not as nice as the original FRP, has the triple advantage of being declarative, legible, and safe!

It is important to note that the arrow syntax allows one to get a handle on a signal's values (or samples), but not on the signals themselves. In other words, first recalling that a signal function SF a can be thought of as a type Signal a -> Signal b, which in turn can be thought of as type (Time -> a) -> (Time -> b), the syntax allows getting a handle on values of type a and b, but not on values of type Time -> a or Time -> b.

Although I can't reproduce it here, Fig 2 is dramatic. The correspondance between arrow-based signal-functions, and the signal-flow-diagrams shown is striking, and exciting. I have been excited about the potential of FRP to liberate UI programming from the tyranny of the state-machine; Fig 2 amazed at the clarity available. I am now, more than ever, convinced that I am on the right track.

Events diverge from Signals slightly in that while they are also temporal values, event's don't so much change from one value to another over time, as simply not exist between 'impulses' (in the signal processing sense). In fact their is an isomorphism between impulse-streams vs. continuous-signals and event-streams vs. signals. In previous papers the authors accepted this distinction as signifigant, and the two were treated seperately. However by noting an isomorphism between Event a and Maybe a they are able to define a signal of type Signal (Event b) ie. an event stream, which becomes a signal that can be thought of as alternating between Nothing and Just a. A signal function of type SF a (Event b) generates an event stream, and is called an event source.

There are a number of combinators for use with event-streams. I'm just going to list them with minimal discussion, for more than that see the paper.

switch, dSwitch :: SF a (b, Event c) -> (c -> SF a b) -> SF a b  
        -- switch or delayed-switch.  Note the function from the event payload to a new SF a b.

rSwitch, drSwitch :: SF a b -> SF (a, Event (SF a b)) b 
        -- note event is defined to carry an SF (possibly inserted by tag), this allows for recurring switch.

tag :: Event a -> b -> Event b

mergeBy :: (a -> a -> a) -> Event a -> Event a -> Event a
lMerge, rMerge :: Event a -> Event a -> Event a
  -- Different ways of handing event collision.

-- Useful event-sources:

edge :: SF Bool (Event ())
  -- Obtain an edge trigged event-stream from a (Signal Boolean)

never :: SF a (Event b)
now :: b -> SF a (Event b)
after :: Time -> b -> SF a (Event b)
repeatably :: Time -> b -> SF a (Event b)

-- Useful event-stream transform back to signal space:

hold :: a -> SF (Event a) a
accum :: a -> SF (Event (a -> a)) (Event a)

accumHold :: a -> SF (Event (a -> a)) a
accumHold init = accum init >>> hold init

Finally just to show how it goes together, the paper implements a few robot controllers. First you implement your robot's controller as a signal function from RobotInput to RobotOutput. So a FRP mapping from the robots sensor-signals to signals which the signal-function-processor will apply to the robot's actuators. This controller is actually parametised by the robots properties, but that isn't surprising:

type RobotController = RobotProperties -> SF RobotInput RobotOutput.

Finally the FRP engine is implemented as a function from a controller to IO(). In the case of the RobotSimulator implemented for the paper, the engine also takes a second controller and a world description.

runSim :: Maybe WorldTemplate -> RobotController -> RobotController -> IO ()

Of course, returning the IO monad, this can be trivially instansated as as Haskell main function.

All in all a fascinating paper --- well worth the time to read.

Arrows, Robots, and Functional Reactive Programming --- Prelude

Now this is a fun paper. I mean, Category Theory, FRP, and you get to play with Robots! What more could you want? So lets take these three elements individually, and then I will try and summarise the paper.

Category Theory

My understanding of Category Theory is as a systematic treatment of abstraction and generalisation. It allows us to take collections of mathmatical proofs and theorms that have the same structure/form, abstract them into a categorical notation, and then generalise them by providing mappings from the categorial constructs to concepts in specific domains. This is naturally of signifigant interest to type-theorists who treat programs as proofs and want access to the power of parametic/polymorphic types and functions without sacrificing rigor. Arrows are a concept from category theory, a generalisation of Monads which beyond just lifting sequencing to a first-class object, allow parametised composition of sequencing. This gives us the ability to support the more complex temporal sequencing of operations required by...

Functional Reactive Programming

Or as that is a bit of a mouthful, FRP; is one of the most intuitive and widespread programming paradigms in use today. It is an approach to programming that has been made so unobtrusive that four of the five other members of my family use it (in the form of a spreadsheet) without realising they are programming. At a basic level, FRP introduces a new paramatised datatype into the language, the time-varying 'signal'. By then permitting functions to be defined that accept these signals and return time-varying signals, you eliminate the shared-state, duplicated-logic, fragmented code paths, and explicit state-machines spawned by current, traditional event-driven approaches. As a basis for comparison, just imagine comparing a traditional spreadsheet with one where to implement a formula for a cell you would have to attach an 'onChange' callback to each referenced cell that recalculated the value.

Robots

Robots have a number of constraints that have not been traditionally considered strengths of functional programming.

• Large numbers of discrete and continuous time-varying inputs that are most definately *note* referentially transparent.
• Real-time constraints that impose a requirement to avoid time-leaks, which encourages the use of imperative operation sequences. Execution of which can be easilly suspended and resumed as higher priority tasks require resources.
• Extensive use of embedded controllers and limited compuational resources that place a premium on transparency of resource use and strict avoidance of space-leaks.
• A history of research largely based on low level system languages (ie MIML) and assembly, which makes for a hostile reception for many of the assumptions of higher-level functional programming

Of course FRP is a natural fit to the first problem. However it has traditionally done so by trading off certainty and predictability in both time and space analysis. This paper attempts to address these two problems in order to allow the exploitation of FRP's natural (theoretical) fit to robotics to be exploited.

Bananas, Lenses, Envelopes, and Barbed Wire --- Finale

Finished the Bananas and Lenses paper on the weekend, along with another on FRP that I'll summarise later. Section 4 takes the previous work based on Lists from section 2 and combines it with the category-theory results from section 3 to develop a theory of cata/ana/hylo/para -morphisms over arbitary datatypes. Section 5 is a very brief extension to parametric types.

Unfortunately I simply don't have enough category theory to follow the discussion properly, let alone explain it here. I think it is probably time to make another visit to Amazon and pick up a book or two on category theory. I'm thinking probably Pierce's introduction, and possibly Crole's "Categories for Types" on the basis of the review there. I've already read Pierce's intro, and it is mercifully brief and yet even from a quick reading I found I remembered enough to follow fragments of the paper. Unfortunately I found it too brief to allow me to learn enough to follow the rest :/.

Anyway, this paper was just for fun; fun was had; and I come away with a fresh perspective on recursion. That counts as a win for me.

Back.

Got back on saturday from a week long holiday helping run a holiday computer-camp for high-school kids. Now mostly recovered, and will probably blog a little on it later.

In the meantime thought I might quickly point at an interesting Wired article I found on slashdot. Looking at one of the most interesting economic effects of the net, the growth of niche markets. Recommended reading The Long Tail.

Just how stupid do you think we are?

Seen on #prolog on freenode:

--> Initial_KK (noemail@CPE00e0292573fd-CM400026081604.cpe.net.cable.rogers.com) has joined #prolog
<Initial_KK> hi All
<Initial_KK> what's this program do?
<Initial_KK> member(X,[X|_]).
<Initial_KK> member(X,[_|T]) :- member(X,T).

My guess? Your Homework you lazy slob.

Orthogonality == Flexible ?

As a core developer of Kowari I am regularly faced with both the good and the unfortunate aspects of RDF. One thing I continually run up against is the seemingly arbitary distinctions between subject, predicate, and object nodes. In this particular case, I still can't find out why RDF won't permit blank nodes as predicates. The same goes for Literals as subjects and predicates. Having a string literal as a predicate or subject is a little strange, and almost certainly bad style, but a typed literal most certainly makes sense. If I want to make statements about the number 5 (LT 6, GT 4, isPrime, isOdd, etc) currently we either have to use bnodes, or fake URIs, so we get:

_:bnA <owl:sameAs> '5'^^<xmls:decimal>
_:bnB <owl:sameAs> '4'^^<xmls:decimal>
_:bnC <owl:sameAs> '6'^^<xmls:decimal>
_:bnA <lessThan> _:bnC
_:bnA <greaterThan> _:bnB
....

vs.

'5'^^<xmls:decimal> <lessThan> '6'^^<xmls:decimal>
'5'^^<xmls:decimal> <greaterThan> '4'^^<xmls:decimal>
...

This is particularly important when you consider what's involved in merging two such documents. Consider trying to insert a document containing primes, with a document containing prime-factors. As we are currently forced to use bnodes, and bnode-refid's are only valid within a single document we are going to have to stuff around doing bnode unification.

Finally the fact that a URI is itself perfectly fine as a typed literal, suggests that all we really need is bnodes and typed literals (and a fair bit of syntactic sugar, but that's a serialisation issue, so we can ignore that for semantics). At the end of the day, RDF is very cool, but I suspect a fully orthogonal triple-store is even cooler. I suppose it's just fortunate that Kowari is an RDF-store built on top of a generic triple-store ;)

Reading

Sometimes life throws you a curve ball. The past week I have been scrambling to help my parents respond to their landlords reasonable, yet highly inconvenient, desire to sell their house vacant possession. Consequently my blog has been neglected of late.

I enjoy reading essays, and I have definately enjoyed reading some of Malcolm Gladwell's contributions to the New Yorker (Gladwell also wrote The Tipping Point, a book I am going to have to read that discusses the effects of non-linearity in social systems). I particularly enjoyed Blowing Up, a look at non-linearity applied to the stock-market; The Mosquito Killer, a facinating look at the anti-malaria campaigns of the 20th century, and DDT in particular; The Dead Zone, the hunt for the Spanish Flu; The Coolhunt, a curious look into the 'cool hunters', a profession I never realised existed. Finally The Tipping Point, an article written four years before the publication of Gladwell's book, a reminder that non-linearity is a fact of life, and humans are particularly bad at anticipating the ramifications.

Scheme Cookbook.

A few of my friends are also in the process of learning scheme. Stumbled across this interesting site which will not doubt be useful: The Scheme Cookbook. Greg, with his habit of implementing cat will likely be particularly interested in the chapter on Files and Directories.

Paul Graham is at it again.

Paul Graham has published yet another essay. This time the topic is, not inappropriately, essays. As expected, the essay is worth the time to read --- if nothing else his essays are entertaining. Graham presents the essay as a form of exploratory reasoning, attempting to differentiate it from the dissertation which he presents as far more rhetorical in nature. To illustrate this he draws an analogy between the relationship between thought and essay and between conversation and dialogue.

Fundamentally an essay is a train of thought-- but a cleaned-up train of thought, as dialogue is cleaned-up conversation. Real thought, like real conversation, is full of false starts. It would be exhausting to read. You need to cut and fill to emphasize the central thread, like an illustrator inking over a pencil drawing. But don't change so much that you lose the spontaneity of the original.

I couldn't help wondering if a better analogy would be the relationship between blog and essay. I certainly don't take the time to polish my blog posts Paul takes to polish his essays.

I personally found it thought provoking, and if that is a common experience, I guess that would make it a successful essay. I certainly wasn't surprised to see it dwell on Graham's other bug-bear, the shocking state of the modern high-school curricula. Still I find some irony in my main response: pondering the possibility that the internet may trigger a resurgence in the importance placed on rhetoric and the essayist in our society; this would certainly be no bad thing.

Equality and Equivalence.

My previous entry on the implementation of Object.equals() has attracted some comment, but the principle response was from Adrian Sutton, who objected to my example of a buggy equals implementation.

In one respect his criticism is valid; in general a subclass should delegate to its superclass for inheritited state equality. To do otherwise is to break encapsulation, and duplicate code. On the otherhand his complaint misses the point:

Class B is incorrectly assuming that it knows how to compare class A's data, and more importantly class B is changing the behavior of A in a way that is not compatible with the original model. Essentially, class A defines equality as having the same n1 values and class B is in the wrong for changing that. [emph added]

What Adrian misses is that if B is unable to meaningfully extend A's definition of equality then A should indicate that by declaring its implementation final, in the absence of a final declaration, B is entitled to extend it. I give an example of a meaningful use of final/instanceof in the Shape/Circle/Ellipse example at the end of the post, which I chose as it conveniently demonstrates all three cases associated with appropriate use of instanceof:

1. Abstract class implementing equals using instanceof to allow proper delegation of equality in subclasses.
2. Extensible concrete class, uses instanceof to allow subclassing; equals declared final to enforce contract
3. Subclassing the concrete class, overriding accessors permitting inherited (unoverridable) equals method to operate correctly (besides meeting the superclass contract ;).

On the other hand Adrian is mistaken when he suggests that the use of getClass() in equals is a bug. There are two flaws with his reasoning. The first arises from a confusion between syntax and semantics. Adrian offers a code fragment, suggesting that it would need A to use instanceof for correctness:

class C extends A {
  public getValue() {
    return n1;
  }
}

The confusion is in thinking this defines a new class. This is a discussion of semantics, hence any class offered as a counter example must needs be a new class semantically, while the above is strictly syntax. The easiest way to approach the semantics of a class is as a function constructing independent, concurrent, finite automata. Now C doesn't define any new states, and doesn't define any new behaviour (state transitions), semantically then it doesn't define a new class --- mathmatically, C is still isomorphic up to congruence with A, so in a very real sense they are the same class. What C actually defines is a function. A new, if rather clumsy, projection on A returning n1. I had better make it clear that I'm not suggesting there is a non-clumsy way of doing this, rather that the reason why it is valid to want an C to be equivalent to a A is that C doesn't define a new class, just a new function. Hence it is a completely different case to B, which is a non-congruent class. If you have a concrete class that must support subclassing, instanceof is a bug.

Moreover this is exactly what we would expect when we consider what it actually means for two objects to be equivalent. Remember, an object is an FA, and as such there is a well established body of work on the meaning of equivalence, anyone interested should read up on simulation and bisimulation. Informally however the key is recognising that the bundling of state and behaviour provided by an object is not just something we get to ignore when it becomes inconvenient, at least not without losing correctness. That if we are serious about OO, we are not just answering the question "are we currently in the same state?", but "are we in the same state, and will we remain in the same state in response to the same stimula?". In other words, it doesn't matter that B.n1 == A.n1, if A and B have different behaviours they aren't the same object.

It becomes particularly important to recognise this when you face the prospect of also implementing Comparable. The problem here is that the contract for compareTo is that of a Total Order. The best you can manage on A U B is a Pre-order, and once again you are left with the prospect of subtle and obscure bugs. From the javadoc for Comparable:

This interface imposes a total ordering on the objects of each class that implements it. This ordering is referred to as the class's natural ordering, and the class's compareTo method is referred to as its natural comparison method. ... For the mathematically inclined, the relation that defines the natural ordering on a given class C is:

       {(x, y) such that x.compareTo((Object)y) <= 0}.

The quotient for this total order is:

       {(x, y) such that x.compareTo((Object)y) == 0}.

It follows immediately from the contract for compareTo that the quotient is an equivalence relation on C, and that the natural ordering is a total order on C. When we say that a class's natural ordering is consistent with equals, we mean that the quotient for the natural ordering is the equivalence relation defined by the class's equals(Object) method:

     {(x, y) such that x.equals((Object)y)}.

Yet after all this, I do share Adrian's pain in this. The unfortunate fact is that if the author implemented A.equals properly, but forgot to include an accessor to A.n1, there is no clean way of gaining access to it. If you do find yourself in this fix, you are left with either direct bytecode hacking (the JVM doesn't know about the access permissions, so you can just access n1 directly), or package injection (if n1 doesn't have private scope). Alternatively, if the author has followed Adrian's advice, it becomes impossible to implement B correctly, and as Adrian's use of instanceof is wrong at a semantic level, no amount of bytecode hackery will save you.

So yet again we come back to my original point. Either you are implementing an abstract class; or you are writing a concrete class and can support either subclass equivalence, or polymorphic equality. "But I need both"!? Tough; Java doesn't support both, and a good engineer knows to work within the limitations of their tools. That a sizable segment of the java community continues to ignore the limitations of their language by presenting incorrect code, pretending that both are achievable, is a sad indictment on the state of that community.

Bananas, Lenses, Envelopes, and Barbed Wire --- Section 3

Apparently the paper gives all it's definitions in terms of the category CPO (Complete Partial Orders); not entirely sure what the difference is between a complete and an incomplete partial-order is, so the signifigance probably escapes me. Alot of this section is also reminisent of Piece's Introduction to Category Theory, so I should probably go back and reread that.

Functors: I remember functors being fun reading in Pierce. In this case we are interested in bifunctors and monofunctors; being types into types and functions into functions; and just functions into functions respectively. Both cases preserve id and compose.

Products: Standard category fare. We have the bifunctor (at least I assume it's a bifunctor, the paper dosn't say, but it meets the defn' above) || which takes two types and maps to the type of pairs of those two types (the paper's example: D||D' = {(d,d') | d <- D, d <- D'} --- I'm using <- instead of the 'element of' symbol, I really need to get a better blog editor, one I can type symbols into easily; (f||g)(x,x') = (f x, g x') ) and the expected projection and tupling combinators.

Sum: Interesting, latent-typing as a functor, or at least something that looks like latent-typing to me. Also interesting to note the use of bottom (_|_) to include undecidability.

 D|D'          = ({tag0}||D}) U ({tag1}||D'}) U {_|_}
(f|g) _|_      = _|_
(f|g) (tag0,x) = (tag0, f x)
(f|g) (tag1,x) = (tag1, g x)

Also worth noting the injection and selection operators:

i0 x = ({tag0},x)
i1 y = ({tag1},y)
f v g --- which applies f to arguments tagged 0,
                and g to arguments tagged 1.

Arrow: Some type of 'wrapping' function. The example given is (f -> g) h = g $ h $ f. This suggests some sort of injection into f -> g, but I'm not entirely sure how. Apparently this is related to curry, uncurry, and eval, but again I don't see the relationship.

Identity, Constants: Pretty much as expected. Lifting and Sectioning, will require a little more thought.

Interesting definition of a constant as a function of 1 -> A. 1 of course having only a single member void. Also given p::A->bool, and p? a = i0 a or i1 a if p a is true/false respectively, you have f v g $ p? modeling if p then f else g.

The rest of section 3 easily exceeds my grasp of category theory. We define a representation for categorical recursion, then move on to recursive types, specifically the least-fixed-point of a monofunctor. Three examples given are cons-lists, binary trees, and natural numbers.

Having covered to background theory, the paper moves on to definitions of our operators over arbitary data types. That will have to wait until I've recovered from section 3 ;).

Bananas, Lenses, Envelopes, and Barbed Wire.

Read the first two sections of "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire" over lunch. So far a very interesting paper, although looking ahead, I suspect it will probably endup exausting my understanding of category theory reasonably soon.

The paper has 6 sections. Section 1 is a short introduction, motivation, and review of the literature; section 2, a short introduction to the four recursion operators cata, ana, hylo, and para; section 3 draws from category theory to outline a theory of algebraic data types used in the rest of the paper; section 4, a formal definition of the operators introduced in Sect2 using the theory developed in Sect3; section 5 extends some of sect4 to parametized types; section 6 is the conclusion, acknowlegements, and references.

The paper aims to define a series of four 'recursion operators'; cata, ana, hylo, and para, and then use them as the basis for a functional programming calculus. These operators correspond to constructors for cata-, ana-, hylo-, and paramorphisms respectively. The reason for doing this is that unstructured recursion isn't amenable to structual analysis and manipulation, so it is preferable to generalise various recursive forms into various forms of structured recursion before trying to develop the calculus.

The examples given are all with respect to your standard inductive list data-type:

A* -> Nil | Cons(A A*)

(It's possibly worth noting that this is a direct algebraic analogue to your standard linked-list definition in an imperative language)

Cata

Constructs a catamorphism, more generally known as a right fold. Think of it as collapsing a list into a value. It takes two parameters, a binary function and an identity.

h = cata(b, .) 
  ->  h Nil          = b
      h (Cons(a,as)) = a . h(as)

and

h :: A* -> B
b :: B
. :: A -> B -> B

cata is denoted using 'banana brackets': (|b, a|). A good example of a catamorphism is length().

length = cata(0, (+) $ 1)  
  note: (+) $ 1  is the right assoc composition of addition and the 1
        function (which ignores its argument and returns 1)
 
proof by substitution:

length Nil = 0
length (Cons(a,as)) =  ((+) $ 1) a length(as)
                    => (+) 1(a) length(as)
                    => 1 + length(as)

Which is of course the standard definition of length::A* -> N

Ana

Constructs an anamorphism, more generally known as an unfold. This is naturally the inverse of a fold, and expands a value into a list. It takes two parameters, an induction function and a termination predicate.

h = ana(g, p) 
  ->  h b = | p b  -> Nil
            | else -> Cons(a, h b') where (a, b') = g b

and

h :: B -> A*
g :: B -> (A B)
p :: A -> boolean

ana is denoted with 'lense brackets' ([g, p]). A good example of an anamorphism is zip, an easier one to follow is count(n), which returns the list of numbers incrementing from n.

count n = ana(g, False) where False a = false,
                              g a = (a, a + 1)

Hylo

Constructs a hylomorphism. This is your classic inductive recursion from one value to another (think factorial, or fibonacci). This can be represented as an anamorphism that builds the recursive call-stack, followed by an catamorphism that folds the stack into a result.

h = hylo(c, ., g, p) 
  ->  h a = | p a  -> c
            | else -> b . (h a') where (b, a') = g a

and

h :: A -> C
c :: C
. :: B -> C -> C


g :: A -> (B A)
p :: A -> boolean

hylo is denoted using 'envelope brackets': [|(c, .), (g, p)|]. A good example of a hylomorphism is factorial.

fact n = [|(1, *),(g, p)|] where g n -> (n, n - 1),
                                 p = | 0    -> true
                                     | else -> false

substitute:

fact = hylo(c, ., g, p) 
  ->  fact n = | n == 0  -> 1
               | else    -> b * (fact a') where (b, a') = (n, n - 1)
            => | else    -> n * (fact (n - 1)).

Which is of course the classic factorial

Para

Constructs a paramorphism. This is the weakest description of any of the four. I can't really claim to understand para, but it is immediately recognisable as structured recursion over inductive datatypes. I'm hoping that the definition will be provided later in the paper, but unlike the other three, this intro section only provided examples. It does however cite another paper by one of the authors Meertens, Paramorphisms. The example for numbers (Num ::= 0 | 1 + num):

h = para(b, .) 
  ->  h 0       = b
      h (1 + n) = n . (h n)

para is denoted using 'barbed-wire brackets': [<b, .>]. Factorial can be written as a paramorphism as:

fact n = [< 1, (g) >] where n g m -> (1 + n) * m

Object.equals()

Like many languages Java provides two equality methods to test objects for equivalence. The first is accessed via the '==' operator and does a simple heap reference comparison. The other is a standard method on Object, equals() which is intended to be overridden by the programmer to perform a value-based comparison. Now the equivalence operator is defined by the language spec, and ultimately implemented by the JVM developers, hence not our concern. Unfortunately the java community has failed to properly document the subtleties involved in writing a correct equals method, and so I continue to come across incorrect implementations and worse, incorrect recommendations.

But first we have to understand what we are dealing with. Fundamentally when we are defining an equals method on a class A, what we are defining is an Equivalence Relation over the set of all objects of class A. This is important because it highlights that we can define our equals method to return anything we want provided we meet three rules.

• Reflexivity: a.equals(a) -> true
• Symmetry: a.equals(b) <-> b.equals(a)
• Transitivity: a.equals(b) && b.equals(c) -> a.equals(c)

If we break any of these rules someone will suffer subtle and devious bugs.

Node: To save typing I'm going to leave out the hashCode method in each of these examples, but be aware if you override equals() you *must* override hashCode() to match.

One consequence of the requirements is that we must ensure that any test we use in our equals implementation meets these requirements as well. So lets consider the standard mistake:

class A {
  int n1;
  public boolean equals(Object o) {
    if (!(o instanceof A)) {
      return false;
    } else {
      A rhs = (A)o;
      return this.n1 == rhs.n1;
    }
  }
}

This is a very common implementation of equals, it has even made its way into a number of Java books. Worse, the bug only manifests in the presence of implementation inheritance of concrete classes.

class B extends A { 
  int n2;
  public boolean equals(Object o) {
    if (!(o instanceof B)) {
      return false;
    } else {
      B rhs = (B)o;
      return this.n1 == rhs.n1 && this.n2 == rhs.n2;
    }
  }
}

To demonstrate the bug lets define a simple function on A's:

static printEqual(A a1, A a2) {
  if (a1.equals(a2)) {
    System.out.println("EQUAL");
  } else {
    System.out.println("NOT-EQUAL");
  }
}

And test it:

  A test1 = new A();
  A test2 = new B();
  printEqual(test1, test2);
      => Prints "EQUAL"
  printEqual(test2, test1);
      => Prints "NOT-EQUAL" !!!!

And we've broken symmetry. This will bite you. There is no situation when an asymmetrical equality is not a bug. Unfortunately it is scary how many places on the net this is presented as the exemplar equals() implementation.

So what does a correct equals method look like. Well there are two. The first is very straight forward, and should be the default choice.

class A {
  int n1;
  public boolean equals(Object o) {
    if (o == this) {
      return true;
    } else if (o == null || !getClass().equals(o.getClass())) {
      return false;
    } else {
      A rhs = (A)o;
      return this.n1 == rhs.n1;
    }
  }
}

class B extends A { 
  int n2;
  public boolean equals(Object o) {
    if (!super.equals(o)) {
      return false;
    } else {
      B rhs = (B)o;
      return this.n2 == rhs.n2;


    }
  }
}

Now test1 != test2 AND test2 != test1. Also, by delegating from B to A at the start of B::equals() we ensure any inaccessible state in A is handled appropriately, and more importantly, that the equality code for A isn't duplicated in B. If you can't delegate from B->A like this, then it suggests that your B isn't actually an A, and you should check your class design (you probably should be using delegation rather than inheritance).

There are times however when you would really like an B to compare equal to an A. The classic example is the circle/ellipse or square/rectangle shape examples. It would be really nice if an ellipse with equal axes compared equal to an equivalent instance of a circle sub-class. The way we can achieve this is to recognise that the core requirement of a correct equals implementation is that the operations we use to implement meet the same reflexivity/symmetry/transitivity requirements as the method itself. Next note that instanceof is only asymmetric in the subclass; and in fact any operation in the subclass will lead to asymmetry! So if we do need subclassed equality, we can't permit a subclass to override the equals() method.

abstract class Shape {
  public boolean equals(Object o) {
    if (o == this) {
      return true;
    } else if (o instanceof Shape) {
      // !! Note: instanceof is safe here as Shape is abstract.
      Shape rhs = (Shape)o;
      return [shape specific comparison --- maybe position];
    } else {
      return false;
    }
  }
}

class Ellipse extends Shape { 
  int minor, major;

  public int getMinor() { return minor; }
  public int getMajor() { return major; }

  // !!! NOTE THE USE OF *final* to prevent asymmetry!
  // Also note the exclusive use of accessors.
  public final boolean equals(Object o) {
    if (!super.equals(o)) {
      return false;
    } else if (getClass().equals(o.getClass())) {
      Eclipse rhs = (Eclipse)o;
      return this.getMajor == rhs.getMajor()
          && this.getMinor == rhs.getMinor();
    } else {
      return false;
    }
  }
}

public Circle extends Ellipse {
  public Circle(int radius) { major = minor = radius; }
  public int getRadius()    { return major; }
}

Note that this is probably a rather clumbersome hierachy. A better approach would be:

public abstract class Ellipse {
  public abstract int getMajor();
  public abstract int getMinor();
  public final boolean equals(Object o) {
    if (!super.equals(o)) {
      return false;
    } else {
      Eclipse rhs = (Eclipse)o;
      return this.getMajor == rhs.getMajor()
          && this.getMinor == rhs.getMinor();
    }
  }
}

public class EllipseImpl {
  int major, minor;
  ...
}

public class CircleImpl {
  int radius;
  public int getMajor() { return radius; }
  ...
}

Note that an CircleImpl will still compare equal with an appropriate EllipseImpl.

Please. If you are programming Java, believe me, these really are the only two options open to you. I really am very tired of tracking down the subtle bugs that result when this advice is ignored.

SICP Lectures.

A friend of mine is studying CS at UQ, and this year they are using The Structure and Interpretation of Computer Programs as a first year text. I am personally pleased to see UQ buck the 'vocational education' trend that has been decimating IT degree courses recently. OTOH it does make life a little tougher on the students, and although this is a good thing, there are ways of making life a little easier. One is to point students at the videos of SICP lectures given by Abelson and Sussman at MIT. I have watched them and they are very good, I highly recommend them to anyone approaching the book looking for some extra insight into the material. It is also worth pointing at the online version of the book in case anyone wasn't aware it was available.

Cale the Corporatist Corsair

Apparently the BSA are looking for a new name for their new mascot. I'm a little surprised at their honesty, personally I find a corporate extortionist weasel who attempts to indoctrinate tech-savvy kids into acquiescing to the corporatist annexation of their public-domain rights, rather appropriate for the BSA.

Personally I'm pushing for "Cale the Corporatist Corsair".