composition.al

I can't believe I was allowed to say "relationships between ordered sets"

A few days ago, my friend and colleague Tim did the describe-what-you-do-using-only-the-ten-hundred-words-people-use-the-most-often thing. I’d tried to do it myself and not gotten very far, but Tim’s post got me unstuck. So, here’s a stab at describing my research, with the first two sentences cribbed straight from him.

People tell computers to do things by writing words. To make it easier, they come up with different “word-sets” for the computer. There are word-sets that tell computers to do one thing at a time, and there are word-sets that tell computers to do many things at once.

Usually, when people start out writing words to tell computers to do things, they use the kind of word-set that tells the computer to do one thing at a time. But there are situations where it makes more sense to do many things at once. Suppose that, say, you have four books at your house and you need to take them to your friend’s house. Would you want to pick up one book, go over to her house, leave the book there, go back home, pick up another book, and so on? That would be really slow (and boring), especially if you had to do it every day!

You’d probably rather pick up all the books and take them all at once. But if you wanted to tell a computer to move the books, and you were using a one-thing-at-a-time word-set, then you couldn’t do that. So it’s great to have many-things-at-once word-sets, so that we can get computers to do things faster.

But sometimes there’s a problem with doing many things at once. To see why, imagine that of the four books you’re taking to your friend’s house, one is red and three are blue. Your friend is taking the books from you and putting them on the table in such a way that each one is on top of the next. But, suppose that when she’s done, she wants the red book to be on the bottom, and the blue books to be on top of it. So, you have to be sure she gets the red book before she gets any blue books.

If you give her all the books at the same time, maybe sometimes the red book would end up on the bottom, but other times it wouldn’t. This could cause a problem later: suppose that every day, someone else is going to visit your friend after you leave, and they need a blue book from her, but all they know how to do is take the first book off the top. If that book happens to be the red one, things will go wrong.

The worst part is that things might work fine for a while, because the book on top might happen to be blue for several days — but one day, the red book could end up on top, and things could go wrong with no warning! Because using many-things-at-once word-sets can lead to these kinds of problems, some of those word-sets have been known to cause people a lot of pain. People usually like to be sure of what the computer is going to do when they tell it to do something, and they would rather know right away if there’s a problem with the words they wrote, so they can more easily fix the problem.

The good news is that there are “safe” many-things-at-once word-sets. It can be shown that if you only use words from a safe word-set, the computer will act the same way every time. (To be clear, the computer might not really do exactly the same thing every time, but only in a way that people can’t see. So it will look to people as if it’s doing the same thing every time.) That means that if there’s a problem with the words a person wrote, the problem will appear right away, and that makes it easier to fix.

These safe word-sets are a great idea, but they can be annoying, because with every safe word-set, there are some things you can’t tell the computer to do, even though those things would be safe. To put it another way, with a safe word-set, you can’t write “not-safe things” (things that could act in different ways with no warning), but there are also “safe things” (things that will always act the same) that you might want to write, but can’t.

So, we’re working on a way to make it possible to write more safe things in safe word-sets. With our way, in the case of the red and blue books, you could tell the computer something like “Red comes before blue.” The computer could move the red book, and then it could move all the blue books at the same time. If it tried to move a blue book first, it would be blocked from finishing that part until the red book was in place.

When a set of things (like books) has an order (like when red books come before blue books), we call it an ordered set. Our idea for better safe word-sets works by using order-keeping relationships between ordered sets. We noticed that other safe word-sets work that way, too. But in those other safe word-sets, the relationships are stronger than they have to be, and that’s the reason why there are lots of safe things that you’re not allowed to write in those safe word-sets. So, we relax those relationships in a way that will allow you to write more safe things, but still keep them strong enough that you can’t write not-safe things. It’s probably not possible to ever make a word-set that allows you to write all the safe things and none of the not-safe things, but our idea gets us a little closer to that.

To me, it’s interesting to think about relaxing those relationships. That’s one reason why I like working on this stuff. I also believe that using many-things-at-once word-sets should be easy and fun, and I don’t want people to have to be annoyed when they do it. This is especially important because there are a lot of big jobs for which we really need computers to be able to do many things at once. Having to move just four books one-at-a-time isn’t so bad, but imagine moving huge numbers of books. So, our dream is to have safe many-things-at-once word-sets that are easier and more fun to use than the ones we have today.

Check it!

Once I got started, this wasn’t as painful as I thought it would be. I did really want to be able to say “stack”, or at least “pile”, for the books on the table, though. I also struggled with using “safe” for “deterministic”. After all, a deterministic program could do something awful; the guarantee is that it will predictably do that awful thing.

A funny thing about this exercise is that, modulo technical terms, I don’t think the results sound all that different from how I write normally. The last paragraph, if you drop in “parallel languages” in place of “many-things-at-once word-sets” — and, uh, “goal” in place of “dream” — sounds more or less like something I would actually say. I’m okay with that, I think.

Comments