Type Inference Story

(an example used as fodder for TheValueOfResearch)

I work for a research group interesting in knowledge representation. Frame based representations, by and large. And have been given the task of writing a constraint engine. Something that takes sentences written in some constraint language and verifies that they hold in a knowledge base.

Designing the constraint language is pretty straightforward-- lots of AI people have already done this and there's something of a standard out there (KIF -- the KnowledgeInterchangeFormat?).

But there's a software engineering factor: Constraint engines are slow. Theorem provers, in general, are not tractable beasts. So anything I can do to throw out sentences, before getting down to the slow task of proving theorems, is a big help.

So I thought about implementation, and I thought about algorithms, and I read a few recent papers and I thought some more (no quantifiable benefit yet, except understanding the problem). And it occurred to me that I could, in linear time, discard a whole class of sentences as unsatisfiable by simply reasoning about the predicates used in the sentences. Because predicates have type information implicitly encoded in them. If I can deduce that some variable is implicitly both a string and a frame, I can automatically deduce that the sentence can't be satisfied.

So I come up with a formal type system for the underlying representation (something that hitherto hadn't really been documented) and I come up with an algorithm that's pretty neat and I go into Ray's office (Ray's a very good programmer who works in the office next to me) for validation of the basic ideas.

And I explain the idea behind inferring types. And Ray looks confused. I explain the idea again and plunge ahead to talk about the algorithm. After which, the conversation went something like this:

Ray: That's pretty complicated

Me: Not really. The implementation boils down to multiple visitors on the parse tree. And I already have the visitor structure in place for other validation stuff.

Ray: Are you sure you can figure out the types from the sentences ?

Me: Well, not all the time. But if I can't, then the constraint engine is gonna fail anyway.

Ray: Why not ask the user ?

Me: I don't have to. I can compute it automatically.

Ray: Why not, in the first release, while we're still evolving the constraint language, keep the code simple ?

Me: It is pretty simple.

Ray: I declare my types when I'm writing code.

Me: You want them to declare their variable types ?

Ray: It seems reasonable.

Ray was right, of course. In release 1, while we're still experimenting with the underlying representation, a whole chunk of code devoted to inferring the types of variables is simply a bad idea.

So, on some scale, I wasted a week. The project got a formal definition of the underlying type system (which won't make it into any near-term code) and I designed a subsystem that won't make it into the codebase. Moreover, since the constraint language will be evolving for a while, and I will learn more as it does so, the eventual TypeInference system will look quite a bit different from my current design.

On the other hand, I wouldn't have known how complex the type inference code was, had I not spent time thinking about it. And if the code was simple, the decision would have been different. And I'm fairly certain that the understanding I gained will help me avoid subtle mistakes in other sections of the code (or, at the very least, spot them sooner).

But if RonJeffries were to ask me to quantify the value of the week spent thinking about type inferencing, or to justify spending time thinking and designing something that never made it into the code, I'd be hard pressed for answers. And, for me, programming is always like this. I always muddle around and I always think about tangents.

Do other people do things much differently ?

WilliamGrosso

I like to think a lot; it is my favorite hobby. But, imagine how that scenario would have gone if every time your friend told you that what you were thinking about was too complicated, you showed him tested working code that does it. It freaks people out. I did this last week to some people who couldn't decide on a design. I coded and tested it up several different ways and showed it to them.

This isn't avoiding thinking.. your thoughts get better because you are getting feedback from the code. That said, it is not XP because there is nothing to stop you from doing too much as you sit alone churning out tested correct code like a machine. so, in some ways it is even hazardous. The people you impress may want to take the code, and you forget to refactor. But, it is fun to do. Even for me, and I spend too much time in my head.

-- MichaelFeathers

William, your job is research. Your mission is to learn. It's OK, I gather, to take extra think time in your group, because you're trying to learn about knowledge representation, not deliver something to a schedule.

For someone doing the same job in a company delivering knowledge representation on a schedule, things might be different. Having the conversation with Ray before the week of investment might have saved a week on the schedule, making the guys with the money happier, resulting in revenue earlier, and putting a Porsche in your garage sooner.

The extreme rules like DoTheSimplestThingThatCouldPossiblyWork remind us not to go off on tangents on our own. When we get the inference idea, we know we "can't" work on it, so we talk to Ray. Ray sets us straight.

If we still think the investment is worthwhile, our rules cause us to talk to the customer - it's their money. If they share our enthusiasm, they schedule the work. If they don't, we don't do it, or do it truly on our own time, not on theirs.

The extreme rules are a network of feedback loops that help keep the project on track. They are there to help us focus on doing what is asked for, with high quality, in the shortest time consistent with that quality. When we find that our human characteristics lead us astray too often, we put a rule or process in place to help us stay on track. The rules are about steering - sometimes, to steer well, you have to look up and see where you are really headed.

--RonJeffries

The above is what really happened, the first week of this month (Nov, 1998 for those reading this in future centuries). And so I wrote it up, as an example to see what XP says about that way of doing things. It's a weak example because, as is pointed out right below it, I currently work in a research lab and, to some extent, the goal is to have me think. But it's a good example because it's real, because I'm trying to be JustaProgrammer, and because I distrust hypothetical examples when talking about methodologies.

I don't think the "your job is research" answer suffices. When my job was being a research mathematician, I did things this way. When I was a consultant building software for the Defense Department, I did things this way. Now that I'm a programmer in an AI research lab, I do things this way.

So my way of thinking is "research oriented." Fine. Now how do other people approach the problem of designing complex code systems?

I don't know how to begin to understand a problem without thinking about similar problems. I don't know how to begin to understand a solution without thinking about similar solutions. And this means designing stuff that won't be built, coding stuff that won't be used, and thinking about things like how to generalize the code.

And I'm reading RonJeffries's answer above as coming very close to "The more you understand, the better suited XP is." Which seems plausible to me. It means that, say rev 1 of a product is not built by XP-like methodologies, but that, by rev 4, it darn well better be. Which also seems plausible to me.

Or have I figured it wrong again ?

WilliamGrosso

There are things you don't ProgramYourWayOut of. Operating systems, distributed deadlock, mutual exclusion, distributed failure recovery, type correctness, ... . For these problems, you need to sit down and think, prove, imagine, use math, etc. There are problems where you NeedToHaveCertainty you are right before you start typing... also, there are more problems you can program your way out of.

Now, XP's assertions are cunningly stated in a way that gives them an escape clause (and I don't mean this in either a facetious or derogatory way). Ron might (correctly) point out that DoTheSimplestThingThatCouldPossiblyWork will imply that for a distributed failure recovery algorithm, you are not permitted to type in something fairly random for the simplest test case and then add test cases until your algorithm is magically up to the state of the art (On the other hand, he might point out something else, I'll wait and see). It is just that a casual reading of that rule gives the impression you can program your way into complex algorithms. Similarly with WorstThingsFirst. For any worst thing you can name, the rule says, if it really is the worst, then attend to it first, otherwise don't.

So in the absence of competing expertise, only you can say whether what you are doing is the simplest that will work or handling the worst danger. However, none of my reading indicates that "The more you understand, the better suited XP is" - rather, an assertion I get is that, "Your lack of knowledge is probably not as dangerous as you think it is, and more of that lack of knowledge can be fixed by programming up a small, relatively simple solution than you expect."

--AlistairCockburn

Doesn't SpikeSolution fit into this somewhere?