The House of David

Saturday, November 21, 2009

Thursday, November 19, 2009

If Code Is Law, then bad law is buggy code

Anyone who is interested in both law and computers has to start with Lawrence Lessig's book Code and Other Laws of Cyberspace. It asserts that "code is law".

You can tell Lessig's book is vintage just from that wonderful word "Cyberspace". Brings me right back to the days of AOL chatrooms it does. I see at the bookstore that he's since updated its title to Code 2.0. Anyway.

With that in mind, we're witnessing the behaviour of the legal code right here in Texas. We've recently passed a law which outlaws marriage. In its exact words: "This state or a political subdivision of this state may not create or recognize any legal status identical or similar to marriage."

This interpretation sounds preposterous but as Gabriel Malor at Ace explains, "that's how laws get written all the time". I write here that the civil code is "an ass" to the degree that it mindlessly follows commands. Our civil laws are naught but a set of algorithms and definitions which work by Strict Constructionism. Computer code works in exactly this way; but unlike the Constitution and the Qur'an - a machine works only this way. To sum up, laws are object-oriented code, and legislators are their programmers.

And if they're not not careful, programmers and legislators may introduce object-oriented programming bugs.

Here, the programmer can instantiate two objects which are identical in all their properties and methods. But when the computer compares the two, they come up different. That is because they are, after all, two separate objects.

Generally programmers will separate out their comparison for whether they are looking twice at the same duck, from that for whether they are looking at two objects which look and quack like ducks.

Texas designed its code for "identical to" which is a test for the second. The problem is that marriage itself is also identical to marriage. Texans should have coded also for a check on whether the incoming test case was marriage, and discounted that case.

So complaints about the hypocrisy of the Liberals who are exploiting this system do not have merit. It's like complaining about the hacker who couldn't design a more secure system himself. He doesn't have to. Code is law; and the Texan code is, now, banning your marriage.

Labels: algorithms, ethics, ghey

posted by Zimri on 16:50 | link |

Wednesday, November 18, 2009

Switch() statement considered harmful

A few months ago I realised that the Select / Case statement in VB.NET 2.0 was a fat O(m) heap of crap. To cut down the value inside the O(), I came up with a class-level static hashtable keyed to a Command-Pattern interface, and I brought up that idea at the 26 September Houston TechFest (in Weisfeld's "generics" session).

I still didn't like that I had to code all this myself, so last week I came up with a run-time dispatcher for the VB.NET language definition. Yes, I was arrogant enough to propose altering Microsoft's compiler...

In the course of my research I found out about Stephen C Kleene's "metamathematics" on Wikipedia, which defined the terms in a comp-sci-ey fashion; and I found c2.com, which informed me that the Switch() has been an annoyance to programmers and their clients for many years. I was done with the theory in fairly short order. I then had the idea of extending this or that Object-Oriented compiler myself. My first thought was to extend Inform 6. (I need hardly mention that I know next to nothing of how compilers work.) The run-time language to which Inform compiles, the "Z Machine", doesn't offer native support for hashtables - much less what I had in mind. It looked too much like hard work.

Today I learnt that much of my effort was moot anyway. C# already offers a compile-time optimiser for switch() statements. D'oh!

That renders the whole project down to supportability. I've been on that side of the help desk for long enough that I know that much is important, which is why I'm posting it; but it's no longer going to win for me fame and fortune.

On the plus side, having done all that, I now have a licence to troll computer blogs' comments. Where they are talking Command-Patterns, delegates, dispatching, and switches - maybe state machines too - I now have something relevant to the topic.

Labels: algorithms

posted by Zimri on 16:45 | link |

The weblog as extended memory

I don't use this blog, primarily, as a means for influencing people. I don't like people enough to do that.

I use this blog as a memory dump. It stores what I know at any given time. (Even if that "knowledge" was false: c.f., the Torah's opinion on unborn life.) If I read an article and disagree with it, I can search through the archive and dig up what I'd said on that subject in the past.

It's nice not to have to keep this clutter in my head.

Labels: algorithms, books, personal, wikipedia

posted by Zimri on 00:28 | link |

Friday, November 13, 2009

Why your project didn't get done on time

Among the programmer's least enjoyable tasks is managing expectations for time taken on project X. This is the difference between his estimate (not necessarily billable time), and the time it takes to get X to the client's desk.

I have created an outline for the snags which have tripped me up over the past 13+ years of slinging code. I am not here to bitch about my job, which I love; nor about my boss and clients, who have all been more than fair. The examples given here are not specific to any one place of work (but there is perhaps a bias toward Web development).

Initial requirements are sometimes optimistic or else aren’t set down until programming is underway.
1. This happens when the project requires a coding method I had not yet tried. I did not always know Javascript for instance.
2. Much of this time is taken up writing the code and seeing if it has any possibility of working.
The requirements can get clarified in the midst of development.
1. This happens when I read the requirements literally, and then do the demo, and then the client points it out.
2. If the exact verbiage wasn't implied in the spec, then we can request an extension - but sometimes things seem obvious to the client that don't to the programmer. ("You wanted an UNDO option?")
The requirements might not have addressed a problem I run across while coding and/or testing.
1. I generally send mail to team lead when this occurs. But it often requires input from a client.
Existent codebase may be complex.
1. In SQL there is always at least one variable that has to follow a lengthy algorithm of rules - and is the reason you're running it on a 5-terabyte server in the first place. (If you're in sales, it's pricing.)
2. In the site itself this happens with the pages which load conditionally.
  1. The role of the login affects what is available.
  2. Subclasses of the page: some fields might be relevant for some choices and not for others. e.g. if you are Canadian, your town is in a "province" and if you are American, a "state".
  3. Code behind here has to be conditional too. If I’m asked to fix something for X, all that code for Y and Z is distracting.
3. This happens where there is a mix of client and server functionality: Javascript versus ASP.
4. This happens where controls are added dynamically.
5. This happens where the web server demands session state (“memory”): preview option, before client saves it.
6. Changing one thing here often ripples across the site.
7. We could fix these to make them more supportable… but that won’t improve the user experience straightaway. Also, “don’t rock the boat”.
A request may depend on some other vendor.
1. Microsoft doesn’t always help. (Get out! I hear the geeks saying...)
  1. Dropdown listboxes do not allow field concatenation. As a result I have to write code to work around this – which subverts my object model and makes it complex.
  2. Checkbox lists are dreadful and I have to write code to disable a checkbox, strikethrough the text, popup tooltips, tick the entries the database says I should tick…
2. Sometimes we buy software that helps out. Sometimes a freeware option exists.
  1. A new language to learn, and code sometimes has to be reengineered to make it compatible.
Testing.
1. The programmer “cannot be the judge of his own case”.
2. The manager has other projects and this delays her ability to react.

Labels: algorithms, apology

posted by Zimri on 16:40 | link |

Thursday, October 29, 2009

The unwinnable debate

I tried to wrestle with Gödel Incompleteness last night. I had to define a few terms, so I cut that part out, and will try again here.

Gödel says, if I'm reading it right, that if any given branch of mathematics is big enough to handle basic arithmetic - then that branch is already too complicated for all theorems in it to be decided true or false. An insoluble problem in that branch might be solved using other branches, but then you'll run into the same underlying flaw with those branches. Nothing in this universe can solve all the problems in mathematics.

This is separate from those debates gone Pascal-complete. (Those debates do have their resolution; the side which invokes Pascal is the loser.) Some debates have no resolution under the terms laid out. It's a sobering thought and, yes, there are religious implication to that as well. Gödel himself thought that God existed. (Gödel's God would have sentenced Pascal to Hell, if he was just, but that is quite another rant.)

Labels: algorithms

posted by Zimri on 12:37 | link |

Proofs and algorithms

I mentioned below that an argument is a class of automaton. I may have jumped ahead a little bit. Really what an argument is, is a chain of reasoning. In mathematics, arguments are conducted in a more formal means. We call these arguments, "proofs".

A mathematical proof assumes that its audience accepts base mathematics and logic. To communicate these findings means that mathematical proofs must be laid out in terms of a "formal language" which all mathematicians are bound to accept. In short, a mathematical proof is itself a mathematical object. That means we might be able to prove things about ways to express mathematical proofs.

That is how we get from arguments to automata; even bad arguments, like Pascal-complete debates, follow these rules.

Labels: algorithms, science

posted by Zimri on 01:25 | link |

Tuesday, October 27, 2009

Slicing pi

Okay, say you've got a number you're trying to find, but it takes too long to get there. Like: you want to find the 31st prime number. Or, the 1,000th digit of Pi.

In the classical methods, you just go and... grunt out all the prime numbers up to #31 using the Eratosthenes Sieve. Or, you calculate pi to 1000 digits.

There are certain things you'd like to do in number theory - like density. You'd like to know if the distribution of numbers in a sequence is random. Dealing with digits in an extended transcendental number, like Pi: if the digits are truly random, in the same density no matter what "snapshot" you take (digit 200 to digit 300, say) - we call that number normal. We don't know if Pi is normal. Because it just takes too long to get as far as digit 200. We have to keep calculating digits 1-199 first.

One David Bailey has got us part of the way, with Pi at least - he wrote a computer programme, with which one Simon Plouffe found a sum which can get you to the place you want to be in the Pi sequence, a lot faster. (If you don't mind hexadecimal; but in the field of computer nerdery, who does?)

We don't yet have that ability to plug in a number and get that sequential prime, though.

Labels: algorithms

posted by Zimri on 19:33 | link |

Quit torturing your kids

I was thinking about longhand multiplication of multidigit numbers. (Even worse: the aptly-labeled Long Division.)

Say you are multiplying 234 x 567.

Here are the steps as we learnt them in, I think, fourth grade:

1. Make a mark below the underline below the two numbers - at the right.
2. Set your position to the right-hand digit on the bottom row.
3. Set your position to the right-hand on the top row.
4. Line up the digits in these positions (4 and 7).
5. Think back to the multiplication tables you memorised in third grade. (If you're me.) (Here it's 28.)
6. Add whatever number you had to "carry". (Here, nothing - first digit and all.)
7. Write down the right part of that number at the mark mentioned in #2 (8).
7. "Carry" the rest - (Put the 2 above the next-to-left digit on top, which is the 3.)
8. Set your position to the next-to-right hand digit on the top row.
9. Go back to #3. Repeat until out of digits on the top.

10. Awesome, we have a number on the bottom (234 x 7 = 1638).
11. Now set your position for the SECOND number, one digit over to the left. (Instead of 7, we'll be working with 6. Or, you know, 5, once we get there...)
12. At the same time, shift where you plan to start the next single-digit multiplication result.
13. Go back to #2. Basically, do the whole thing over again except 234 x 6, or 234 x 5.
14. Those three multiplication results? Add them up. The way you learnt in second grade.

If you ask me, this is about the worst algorithm in the worrrrrld.

For a start, you're telling your brain, on multiple occasions - "quick, what's 4x7?" Most of the time you're also dealing with "carried" numbers which means, in addition, "2+1, STAT!" Every time you go to memory, it's a headache. It's a neural SQL call: connect, SELECT.

Worse, it doesn't scale well. With m digits on the first row and n on the second, the work is on the order of m x n. For my two three-digit numbers I had to do nine sweeps. That includes recalling times-tables, and fer cryinoutloud addition-tables. I particularly enjoyed feeling like a retard when I didn't get them immediately. Nine times to make that double neural SQL call. Computer geeks call this a polynomial-time problem. I call it a pain in the rear.

At least it's soluble in polynomial time unlike that damned rodent problem we had last fortnight; so your computer can manage it. Also it guarantees an exact result (if you did it right). Still, Sammy would never have put up with it.

Nor should you. Here's a better idea: get a slide rule.

I never got to use one of these puppies. By the mid 1980s we had the notion that the Calculator was going to save us. But calculators get stolen, and broken, and run out of battery life. No-one's going to do that to a slide rule and they are cheaper anyway.

A slide rule runs on a logarithmic basis. If you are trying to do 234 x 567, it's the same as doing exp[ln(234) + ln(567)]. In layman's terms -

Find the log of the first number.
Find the log of the second number.
Add those two logs. (This is also a recursive process - it runs as many times as the number of digits in the smaller of the numbers.)
Reverse the log of the total.

So instead of O(n^2), where n is the number of digits; we've got O(n)! And the original had twice as many "SQL calls" (mult and add) as the slide rule did (just add). There are SIGNIFICANT savings here especially if you have a lot of digits and/or a lot of numbers.

You sacrifice a little in accuracy but this is worth it. Numbers that big don't usually have to be that precise.

PS. Also note that polynomial-time processes can be done, in some cases, in linear time...

Labels: algorithms

posted by Zimri on 18:14 | link |

Monday, October 19, 2009

Pascal-completeness

I'm currently seeing a tactic on various comment threads: a (polite) dismissal of findings in modern science, on the grounds that we will all know what the truth is when we die. (There's no point linking to an example; it's easily found.)

Says the person laying out this case - evolutionists (say) have but a "theory". If there's a 90% or even a 99.9% chance that evolution is true, it is still safer for us to be wrong in denying evolution and to deal with that minor bummer, than for us to be be wrong in accepting evolution and... well.

The first step, in any problem, is to find out if the problem fits any known template. In this case we are dealing with a passive-aggressive version of Pascal's Wager, cited here almost five years ago.

A debate develops in much the same way as an automaton, or machine, or running process. Some automata can be grouped into "-complete" classes, which follow principles common across the class. For example, Turing-complete automata: once you know that your machine is Turing-complete, it's just a matter of writing the compiler and then you can run your C program on it. Conversely, the NP-complete problems: once you prove your program is NP-complete, you know you're screwed.

So here, I give you the Pascal-complete argument - once The Wager is laid, the argument has become an argument over the Wager, and the original argument is dead.

There are counters to The Wager but unfortunately, no-one you meet will accept them. Anyone who reacts to an objectively knowable fact about this world, by means of Pascal's Wager (however much Nerf foam s/he wraps it in): that one has shown their hand. They'd have to want to change their outlook and, it's not going to happen. They are not to be reasoned with. evolutionThread.Abort(); if C# is your thing.

In a moderated debate, Pascalian arguments would be slapped out of bounds. If the general population were more rational, then the other observers to the debate would step in.

Real life isn't a debating society; standard-model humans, who aren't up with the literature and have lives outside logic - they judge based on personal feelings. And anyone who puts on their Shatner-face and yells "PASCAAAAL" into the monitor isn't going to win friends.

UPDATE 10/29 - This post assumes that it is intuitive that a debate is like a computer program. I've since written an explanation for that, and linked it here.

Labels: algorithms, misanthropy, religion, science

posted by Zimri on 19:14 | link |

Wednesday, October 14, 2009

Paging Stephen Cook

If you solved the problem Lazy Sammy Squirrel posed for you below, then congratulations. You've won a Fields Medal in mathematics. More: you've got a million dollars for the Millennium Prize. Your name will go down in history with Galois, Reimann, Perelman. Maybe even Newton.

That is because what Sammy had run into was a form of the NP complete puzzle. Finding a polynomial-time solution, or proving that polynomial-time is impossible, remains open. The NP complete class was defined by Stephen Cook as recently as 1971, and traveling-squirrel is just one member of it.

Anyway I would like to talk, today, about what I think is an equivalent in particle physics.

Particle physicists have a "Standard Model" of quarks, gluons etc which Explains Everything... except for the "Everything" part. Mathematically-minded physicists have attempted to refine the model. I am here picking on a branch of these model refineries: the String Theory. This proposes that underneath the Standard Model is a set of multidimensional vibrating strings.

In order for capital-P Physics to take this theory seriously, and not as a glorified Sudoku puzzle, we demand that String Theorists come up with a means for testing. When String Theorists do, they usually propose something hilarious like a hollow titanium donut the radius of Neptune's orbit. Instead of laughing the String Theorists out of the academy as if they were so many Ptolemaists, though, we're still nowhere decades later, and we're still paying these clowns for playing Sudoku. What's up with that, dawg?

I say, stop their funding cold. Absolute-zero cold. They can shop their theories in listservs and blogs like the rest of us kooks.

We need to be funding Stephen Cook instead. (If he's still alive, that is; if not him, then one of his students.) Physics needs to define a class of intractible problems (let's say it needs >1,000,000,000,000,000 eV to test); and to prove that String Theory belongs in that class.

At that point, we can treat all those String Theory hobbyists like we used to treat the guys who solved traveling-salesman in linear time on UseNet. Or, we can demand that String Theorists come up with their version of "approximation algorithms" = tests that show how likely String Theory is.

Until the Stephen Cook of physics comes along, I'm in agreement that it's intuitively clear that the string-theorists are in Internet kook territory.

Labels: algorithms, bullshit, science

posted by Zimri on 17:43 | link |

Tuesday, October 13, 2009

The traveling squirrel problem, I

It was autumn, and all the squirrels in the wood felt the winter approaching. The mornings began later, and colder. Chill breezes ruffled through squirrel-fur as the little rodents jumped between the golden, dry branches of the canopy. On the forest floor, large dead leaves crackled under tiny paws.

At tea-time, when the lady squirrels congregated, they sometimes gossiped over which of the menfolk was strongest, or had the fluffiest coat; or which was the most agile, or the quickest. But there was no debate as to which was the laziest. That dubious honour, all agreed, belonged to Sammy.

In his first year outside the nest, Lazy Sammy had nearly starved; luckily, he found a loose board in Old Man Darby's turnip-shed, and using a few twigs was able to lever it open. He didn't like to climb his tree by hand; so he built a dumbwaiter, with a full network of pulleys, out of a cigar-box and some spools of thread he'd lifted from Darby's home. And then there was the time he got tired of pulling acorns out of a certain walnut tree; so he mixed together some saltpetre and sulfur - and how he got it all is a story in itself - and, long story short, he would have blown off his own tail if the other squirrels had not intervened.

On this autumn, Lazy Sammy was up in his tree-house, deep into sheafs of paper (also "donated" by Mr Darby), frantically scribbling away.

Every year around this time, respectable squirrels would travel from tree to tree collecting nuts. The travel could sometimes take a long time. Lazy Sammy didn't much like traveling and he hoped to get it all over with as soon as possible. That meant, once the nut-bearing trees were marked, finding the shortest route between them.

Normally there'd be just a few trees to visit before it was time to go home. There was no point in plotting a route just to one tree; and if there were two trees, it was just a question of choosing which order to run them in:

But a third tree meant doing measuring, and a decision:

The possible routes were as follows -

2.2+4.1+6.3+12, or

12+6.3+4.1+2.2; 24.6

12+10+4.1+6, or

6+4.1+10+12; 32.1

6+6.3+10+2.2, or

2.2+10+6.3+6; 24.5.

So the last route would be the answer. So he thought. All that math was tiring to Sammy's poor little squirrel head, and he wasn't sure... even with the calculator Old Man Darby had "lent" him. And what if there was a fifth tree? or a sixth?

Sammy decided to take another route, so to speak; he wondered if it was even worth bothering to calculate routes. For that, he had to step back and to look at how he had been going about it. Two trees got him two routes (including the reverse route). Three trees got him six. Four trees got him twenty-four. 2 went to 2; 3 went to 2 x 3; 4 to 2 x 3 x 4...

That looked like a pattern to Sammy.

Sammy went over to his makeshift lift, rolled himself down, went back to Old Man Darby and "borrowed" a few of his maths books (improvising a cart to pull them with, out of a few mislaid toy electric trains), brought them back to his tree and - with help from the motor in Darby's toy train - pulled himself and his precious cargo back into his house.

These books told Sammy that the pattern he had run across, just to look at the problem (let alone solve it) was a "Factorial". The function for the factorial of 4 looked like "4!". It had an Exclamation Point! As if it was shouting! at Sammy! And, considering that 4! would always be bigger than, say, the constant "e" to the power of 4, and 5! always bigger than e⁵, and on and on... more trees would mean a! MUCH!! LOUDER!!! PROBLEM!!1!

Even if half the routes were ignored, as being the backwards-route of some other route; it would still not be enough to drown out the screaming gale of the Factorial.

Sammy's whiskers drooped. The problem wasn't hard. It just took too long. He wouldn't mind if an extra tree took an extra few minutes ("linear time"). He might not even mind if an extra tree meant every other tree had to take an extra few minutes ("polynomial time") - maybe Darby could "share" his computer. But how could this problem be solved in linear (or if it had to be done, polynomial) time?

Labels: algorithms

posted by Zimri on 19:52 | link |

Saturday, November 21, 2009

Meta

Thursday, November 19, 2009

If Code Is Law, then bad law is buggy code

Wednesday, November 18, 2009

Switch() statement considered harmful

The weblog as extended memory

Friday, November 13, 2009

Why your project didn't get done on time

Thursday, October 29, 2009

The unwinnable debate

Proofs and algorithms

Tuesday, October 27, 2009

Slicing pi

Quit torturing your kids

Monday, October 19, 2009

Pascal-completeness

Wednesday, October 14, 2009

Paging Stephen Cook

Tuesday, October 13, 2009

The traveling squirrel problem, I

On this site

Afield

Friends

Table 9