Sean Werkema's Blog

Beginner and intermediate programmers often think that programming is math. After all, a lot of computer science is math, and computers run on math, and core concepts of the field like Turing Machines and lambda calculus are really pure hard math. You can’t get started in this field without knowing some math.

But programming — or software engineering if you prefer — really isn’t math. Programming, as Donald Knuth rightly noted all the way back in the 1970s, is really literature. We tell the computer stories about how to do things: We write plays, and the computer acts out the play for us. Some of the words that we use in those plays are based on math, but most programming is really a form of storytelling. Code is sometimes compared to poetry, but I think it has the most in common with prose — which is arguably why systems like ChatGPT are so good at it.

My grandmother passed away today, early afternoon.

My cat passed away today, late afternoon.

Both were very old; my grandmother was 91, and my cat was 17.

But both happened on the same day, two hours apart. I was almost holding it together, after my grandmother passed. And then our cat started crying, her stomach in pain.

We’re deleting this date from the calendar. Henceforth, in subsequent years, we will all go straight from October 8 to October 10.

Seriously, we don’t.

I was asked on Discord today why some languages require semicolons and others don’t, and this is one of those surprisingly deep questions that to the best of my knowledge hasn’t been answered very well elsewhere:

• Why do some languages end statements with semicolons?
• Why do other languages explicitly not end statements with semicolons?
• Why do some languages require them but it seems like the compiler could just “figure it out,” since it seems to know when you’ve forgotten them?
• Why are they optional in some languages?
• And, of all things, why the weird shape that is the semicolon? Why not | or $ or even ★ instead?

So let’s talk about semicolons, and try to answer this as well as we can.

I wanted to answer this using only the ten hundred words people use most, so here we go 😀

I work with ideas about computers. I think about the things computers can do, and I try to find ways to make computers do those things better or faster, and I write all those ideas down. And I try to find ways to stop computers from ever being slow, so that we don’t have to make them faster. I also think a lot about if there are things that computers can or can’t do, and if it’s important that computers can or can’t do them. It’s bad for people when computers are slow or when computers can’t do things because we want computers to help us with things we want to do. But making computers do things that they can’t do is hard, and making computers go faster can be hard too. So sometimes I use ideas from other people to make the things computers do faster or better, and sometimes I find my own ideas too, and then I write those ideas down and tell everyone about them so all of us can make computers do more things better.

<< Part 1

Lately, I’ve been growing increasingly obsessed with this problem. While my solution is very fast (O(n) is pretty fast!), I’ve been concerned about a few possible issues with it:

• First, I wasn’t certain it was anything better than locally-optimal. It’s guaranteed not to produce a bad result, but will it produce a good result? I couldn’t be sure.
• Second, it relies on floating-point arithmetic, while most other solutions don’t.

It has the nice upside of being able to operate in constant space (not including the O(k) output space), and linear time, but those two caveats are potentially problematic. If it turned out to be a really bad solution, who’d use it? And the floating-point numbers felt too fuzzy to be safe. So I started poking at it again.

Being a computer scientist is a funny thing. You live on the edge of knowledge in a weird realm that’s not quite mathematics and not quite physical machinery. Like most of the sciences, of course, anything you “discover” was likely already discovered several decades before. But every great once in a while, you bump into a problem that seems to have received very little attention, and you see the existing solutions, and you think, “Huh, it seems like there must be a better way.”

I did that, once, a long time ago: I discovered a really neat technique for computing treemaps on-the-fly for arbitrarily large datasets, and that’s why SpaceMonger 2+ have such incredibly fast renderings. I don’t know for sure if it’s a novel solution, but I haven’t seen anyone else do it. One of these years, I need to properly publish a paper on how that works: I haven’t been intentionally keeping that algorithm private; I just haven’t gotten around to writing up a really good description of how it works.

But today, I’m going to talk about another algorithm entirely: Linear partitioning a sequence of numbers.