Friday, May 31, 2013

Twisting the rules of logic in our code

In philosophy, there are very few things that can't be doubted. The basic laws of logic are among them. There's one that seems completely obvious and indisputable to normal people:

Law of Identity: Everything is identical to itself.

In my audiobook, the professor is going on about how not only is this statement true in our world, it's true in every conceivable world. And I'm thinking, "Oh, I can conceive of such a world where this is false! I've created one!" The programmer can create worlds the philosopher cannot conceive of.

Take Hibernate for example, which tries to represent a database in Java objects. It's optimal to define object identity based on a set of fields, rather than creating a gratuitous sequential ID. But woe betide the programmer who includes in the set of identity fields one that can be updated! I change your last name, and bam, your entity is not identical to itself. Been there, done that, learned not to do it again. It takes rigor, knowledge, and discipline to use Hibernate without creating a world that violates this most basic law of logic.

Whaaa? Why is this even possible? This is exactly what functional programmers are talking about with "reasoning about code." FP is about languages or practices that make sure our programs conform to the laws of logic, so they don't up and surprise us with objects that are not identical to themselves.

In Java, we can violate the Law of Identity when we define .hashcode() poorly and then stick objects in a HashMap. One key goes in, a property referenced in the key's .hashcode() changes, and then we try to get that entry out - no luck. It is not identical to itself. Things also get nutty when .equals() and .hashcode() are not dependent on the same fields. In Java, we have to be careful to create objects that follow the Law of Identity.

A Haskell programmer says, ridiculous! Why would we do this to ourselves?

After the Law of Identity, there's two laws attributed to Liebniz. The first one says identical objects have the same properties. This is a little harder to screw up in Java, unless:

class TrickyBugger {
  public double getHappiness() { return Math.random; }
}

The second form of Liebniz's law says if two things have the same properties, then they are identical. In reality and philosophy this law is controversial. Yet, when it's true, it's useful. In programming we can choose to keep this one true.

Enter the Algebraic Data Type. This is every type in Haskell, and the most useful sort of data type in Scala. A class is an algebraic data type if, when two instances have identical properties, they are considered identical. (All the properties are immutable.) In OO, the Flyweight pattern is an example of this. The concept of ADTs means that even if two instances live at different places in memory, when they have all the same properties, they might as well be the same instance for all we care.

This is useful because it keeps things simple in my head. I don't have to ask myself "should I use == or .equals in this comparison?" It's always .equals(), because properties determine identity. Back in Hibernate, this is the concept I needed. Keys should be ADTs, so naturally their fields will never update.

Programming is supposed to be the epitome of logical work. I went into programming because physics wasn't deterministic enough. Yet, here we are, in super-popular languages and frameworks, violating the most basic laws of logical inference! Programming is deterministic, and we can choose to create modules that conform to the logical principles our brain expects. Let's do that.

1 comment:

  1. I sometimes wonder if anyone ever learns to use Hibernate the right way without using it the wrong way first.

    Good post. I went through the Hibernate learning curve, but I never connected the source of the headaches with the fact that it's idiomatic to use mutable objects in Java.

    Now I have a different problem - we have over a hundred different tables mapped in Hibernate spread across a few applications. It all works swimmingly - but every time we hire a newbie to Hibernate, they have to start scaling the Hibernate learning wall.

    ReplyDelete