Parting Philosophers Problem

JimBlizzard hosts a periodic gathering called the PortlandNerdDinner?. At last nights dinner ChrisSells raised, for the second dinner in a row, the question: "What is going to take programming to the next level?" I started rambling about how TestDrivenDevelopment will influence language design, especially type systems, but this was leading to the next language, not the next language level. Rising to this challenge I suggested that to reach the next level, we will have to stop founding our reasoning about programs on logic. With logic we follow long chains of reasoning and conclude that something will certainly be true. Although such reasoning has served us well, it also limits our thinking about what might be possible. Consider a computing environment where lots can be known with statistical reliability, but nothing is known for sure. We often find ourselves in exactly this situation and deal with it by asserting logical structure over it and then program near forever trying to make that logic be true. How do you find the largest element in an array? You search the array. What if multiple threads are writing the array? You lock them out. What if locking isn't possible? Surely there is a next step even here to assert logic over this problem. That is what we do because we assume a logical architecture and struggle illogically to maintain it. To amplify my point I proposed what I am now calling the PartingPhilosophersProblem:

This is a practical problem in that we were, in fact, eating dinner and would eventually need to leave. I won't further specify the problem other than to say that although we didn't all know each other, and no solution had been offered by the host, none of us was particularly worried that we would be stuck there overnight for failure to detect the leave signal. From where did we get this confidence?

Evolution has bestowed us with considerable machinery that adheres to what I will, for lack of a better name, call our social architecture. ArloBelshee pointed out the amazing "relevance filtering" that this social architecture supports when it distinguishes emotional state from the visual field (do people look like they are ready to leave?), and suggested our realization of the social architecture has physical limits (250 max of some social bond, I forget which.)

Chris wanted to know how we might program without having to write all those statements. Just turning the statements to pictures or something wasn't going to solve the problem so long as we hang on to logical notions like correct and complete. We enjoyed reverse engineering our own social machinery and would have, I am sure, started suggesting language features except that the restaurant staff started stacking chairs and we knew it was time to leave. -- WardCunningham

Question for Ward: aren't you affraid that after this heresy the ghost of EwDijkstra may show up to your next dinner ?

Not at all. I said something nice abou him just a few days ago on ProofsCanBeSimple. It is only because logic works so well that it blinds us so completely. -- Ward


A dinner is a ProCess. Words are spoken, thoughts are sparked, and conversation flows. Serve chicken, you get one conversation. Serve duck, another. The dinner comes to its end when the synchronized chemical signals of fatigue, satiety, and need-for-elimination cause a decay in conversation. If we were describing an individual we'd be content to describe the ending of dinner as an ApproachAvoidanceGradient. Only because of the IllusionOfIndividuality, are we loath to describe a dinner this way.

Our programming model, which any way you slice it comes down to the VonNeumannArchitecture, continues the IllusionOfIndividuality. We speak of CPU and memory, not transistors. We speak of procedures, logic, and I/O, not signals. We orient our systems by maintaining the social conceit of static objects and projective states - though we know there are no such critters. And when the mass of unnecessary behaviours implicit in the IllusionOfIndividuality impinges on our own ProCess, we feel oppressed and unnatural - we desire to part from them. And then we fear them and ourselves.

A new ProCess of programming must begin with a personal transformation. Beck described his internalization of TestFirst somewhere round here. Other transformations are possible, and will have far more profound effects on our work.


By what method did you reach your conclusion about limits? Exactly. How will you know what is possible then implement it? Exactly.

I used the method of showoffish-speculation, which neither proves or disproves, but may induce imagination. -- Ward

Correctness and imagination and logical thought are not enemies. They work well together. It seems somewhat like overweight people who want to eat all they want and expect a pill to fix it. Maybe you just need to get better at logical notions?

I don't doubt social architecture, when known, will be subject to logical analysis. I only doubt that logic will guide us to its discovery. -- Ward

Discovery is the interaction of layers. Insight and logic work together, building on each other. We don't really know where insight comes from, though it has been observed in fmri. A logicless person will not discover anything. Like a computer with only logic will not discover anything. You wish to embrace a direction to make a leap. It's harder than that.


This sounds a lot like the problems addressed by FuzzyLogic and FuzzyMath?. DinnerOver is a fuzzy value based on calculations based on other fuzzy and discrete values. When some threshold for DinnerOver.true is passed, it's time to leave. -- EricHodges

On a more serious note: I think Ward is wrong when he says that we will have to stop founding our reasoning about programs on logic.

There are forms of intelligence that are different in nature then the workings of a mechanical inference engine Prolog style. It is even doubtful (at least according to EwDijkstra and JeanYvesGirard ) that our ability to perform mathematics and discover new theorems and apply the right mathematics to the right problem is anywhere similar to the mechanism that our programs are using.

In applying logic and math or advancing logic and math people use imagination, intuition, experience in addition to laws of logic. The essential problem is that as far as we can tell, we have no clue whether computer can do the same. In other words, if we can decide easily on PartinPhilosophersProblem? and many other (trivial for us && deadly for a computer ) problems try to teach a computer how to drive a car, you'll get billions of dollars from Nasa, the jury is still out whether computers can do the same.

So there's this minor hurdle that we do not know as of current state of the art knowledge whether we can program computer in this sense (and we won't know until we are able to understand more about our own intelligence). Then there's a second hurdle that this type of intelligence may be well suited to decide PartingPhilosophersProblem, but is certainly not enough to calculate the resistance of a bridge or the trajectory of a spaceship while giving up logic and mathematics.

Therefore calling for a stop in founding our reasoning about programs on logic is naive and premature. It may be useful to perform explorations on trying to impart our seemingly different kind of intelligence to computer programs (is Ward's idea on combining XP with genetic programming already failed, lingering, on the course for success or what ? Jon got a fulltime job -- Ward) but this should be done in parallel as it seems to have different areas of applicability, and we really do not know if it works, how well it works, in what areas it works. We certainly have enough math and logic at our disposal to raise the quality of programming by an order of magnitude at least, provided we convince ourselves that knowing a little bit of math and logic is worth the effort, rather than following at all costs the pie in the sky kind of projects. --CostinCozianu


See photos of the philosophers at http://snowstormlife.com/wiki/default.aspx/MyWiki.Pnd041404.


Posted my thoughts over here: http://snowstormlife.com/wiki/default.aspx/MyWiki.WhenIsALeapALeap -- JimBlizzard
Based on an insightful conversation long ago with a co-worker, I would suggest that a higher level of PatternMatching would be a logical (P.I.) next step. All living creatures use PatternMatching to survive - this gradient of light leads to food, that pattern of sound means a predator is near, etc. -- PeteHardie
Getting beyond decideability issues, seems like the current focus of the programming crowd at this dinner. I think it might have let you all wax philosphically about this barrier.

I think programming needs to be able to allow for chaos and noise to some degree in the next level, this means begging the question on decideability for now. After all from a logical view point it's futile.

The next level needs to allow programs, agents, services, programmers, products support, and the user to flail away at an acceptable configuration which can ever change over time against some form of constant and durable set of data and environmental features. I struggle lately with what is a good balance between a well-defined thing and an arbitrary thing in design. But I think this is just typical writers block, authors must get.

What I'm getting at are context senstive programs and systems. This is very much an arbitrary thing in some use case instances and a very controlled thing in other use case instances. I don't believe the answer will ever remain constant, but I due feel current uses of computers are heading too far toward the controlled thing and that seems to be what stagnating programming now and as it has in the past.

What I would like to see is services take off. But how? I not sure, but cool services are the fulcrum of the next big disruptive programming thing in my imagination and I have yet to put it to paper. Of course the FCC, the big MEDIA conglomerates are all in the way of this as well as coporate cultures and public policies. Digital communcation technologies are so amorphous and fluid that corporate cultures and governments just don't get it yet. For that matter certain generations just don't get it. We have a lot of big institution posturing to be players in that connectedness and these economics and public policies that are a big part of this slow down in programming more than anything else.

As far as the next big leap in programming, we're there, society isn't. -- PeterEvans

EditText of this page (last edited March 2, 2007) or FindPage with title or text search