you can’t do that actually, because patent applications are kept secret for at least 18 months; and the result is the Patent Office could be considering now whether to issue a patent, and they won’t tell you. And this is not just an academic, theoretical possibility.
For instance, in 1984 the Compress program was written, a program for compressing files using the data compression algorithm, and at that time there was no patent on that algorithm for compressing files. The author got the algorithm from an article in a journal. That was when we thought that the purpose of computer science journals was to publish algorithms so people could use them.
He wrote this program, he released it, and in 1985 a patent was issued on that algorithm. But the patent holder was cunning and didn’t immediately go around telling people to stop using it. The patent holder figured, “Let’s let everybody dig their grave deeper.” A few years later they started threatening people; it became clear we couldn’t use Compress, so I asked for people to suggest other algorithms we could use for compressing files.
And somebody wrote and said, “I developed another data compression algorithm that works better, I’ve written a program, I’d like to give it to you.” So we got ready to release it, and a week before it was ready to be released, I read in the New York Times weekly patent column, which I rarely saw—it’s a couple of times a year I might see it—but just by luck I saw that someone had gotten a patent for “inventing a new method of compressing data.” And so I said we had better look at this, and sure enough it covered the program we were about to release. But it could have been worse: the patent could have been issued a year later, or two years later, or three years later, or five years later.
Anyway, someone else came up with another, even better compression algorithm, which was used in the program gzip, and just about everybody who wanted to compress files switched to gzip, so it sounds like a happy ending. But you’ll hear more later. It’s not entirely so happy.
So, you can’t find out about the patents that are being considered even though they may prohibit your work once they come out, but you can find out about the already issued patents. They’re all published by the Patent Office. The problem is you can’t read them all, because there are too many of them.
In the US I believe there are hundreds of thousands of software patents; keeping track of them would be a tremendous job. So you’re going to have to search for relevant patents. And you’ll find a lot of relevant patents, but you won’t necessarily find them all.
For instance, in the 80s and 90s, there was a patent on “natural order recalculation” in spreadsheets. Somebody once asked me for a copy of it, so I looked in our computer file which lists the patent numbers. And then I pulled out the drawer to get the paper copy of this patent and xeroxed it and sent it to him. And when he got it, he said, “I think you sent me the wrong patent. This is something about compilers.” So I thought maybe our file has the wrong number in it. I looked in it again, and sure enough it said, “A method for compiling formulas into object code.” So I started to read it to see if it was indeed the wrong patent. I read the claims, and sure enough it was the natural order recalculation patent, but it didn’t use those terms. It didn’t use the term “spreadsheet.” In fact, what the patent prohibited was dozens of different ways of implementing topological sort—all the ways they could think of. But I don’t think it used the term “topological sort.”
So if you were writing a spreadsheet and you tried to find relevant patents by searching, you might have found a lot of patents. But you wouldn’t have found this one until you told somebody, “Oh, I’m working on a spreadsheet,” and he said, “Oh, did you know those other companies that are making spreadsheets are getting sued?” Then you would have found out.
Well, you can’t find all the patents by searching, but you can find a lot of them. And then you’ve got to figure out what they mean, which is hard, because patents are written in tortuous legal language which is very hard to understand the real meaning of. So you’re going to have to spend a lot of time talking with an expensive lawyer explaining what you want to do in order to find out from the lawyer whether you’re allowed to do it.
Even the patent holders often can’t recognize just what their patents mean. For instance, there’s somebody named Paul Heckel who released a program for displaying a lot of data on a small screen, and based on a couple of the ideas in that program he got a couple of patents.
I once tried to find a simple way to describe what claim 1 of one of those patents covered. I found that I couldn’t find any simpler way of saying it than what was in the patent itself; and that sentence, I couldn’t manage to keep it all in my mind at once, no matter how hard I tried.
And Heckel couldn’t follow it either, because when he saw HyperCard, all he noticed was it was nothing like his program. It didn’t occur to him that the way his patent was written it might prohibit HyperCard; but his lawyer had that idea, so he threatened Apple. And then he threatened Apple’s customers, and eventually Apple made a settlement with him which is secret, so we don’t know who really won. And this is just an illustration of how hard it is for anybody to understand what a patent does or doesn’t prohibit.
In fact, I once gave this speech and Heckel was in the audience. And at this point he jumped up and said, “That’s not true, I just didn’t know the scope of my protection.” And I said, “Yeah, that’s what I said,” at which point he sat down and that was the end of my experience being heckled by Heckel. If I had said no, he probably would have found a way to argue with me.
Anyway, after a long, expensive conversation with a lawyer, the lawyer will give you an answer like this:
If you do something in this area, you’re almost certain to lose a lawsuit; if you do something in this area, there’s a considerable chance of losing a lawsuit; and if you really want to be safe you’ve got to stay out of this area. But there’s a sizeable element of chance in the outcome of any lawsuit.
So now that you have clear, predictable rules for doing business, what are you actually going to do? Well, there are three things that you could do to deal with the issue of any particular patent. One is to avoid it, another is to get a license for it, and the third is to invalidate it. So I’ll talk about these one by one.
First, there’s the possibility of avoiding the patent, which means, don’t implement what it prohibits. Of course, if it’s hard to tell what it prohibits, it might be hard to tell what would suffice to avoid it.
A couple of years ago Kodak sued Sun [for] using a patent for something having to do with object- oriented programming, and Sun didn’t think it was infringing that patent. But the court decided it was; and when other people look at that patent they haven’t the faintest idea whether that decision was right or not. No one can tell what that patent does or doesn’t cover, but Sun had to pay hundreds of millions of dollars because of violating a completely incomprehensible law.
Sometimes you can tell what you need to avoid, and sometimes what you need to avoid is an algorithm.
For instance, I saw a patent for something like the fast Fourier transform, but it ran twice as fast. Well, if the ordinary FFT is fast enough for your application then that’s an easy way to avoid this other one. And most of the time that would work. Once in a while you might be trying to do something where it runs doing FFT all the time, and it’s just barely fast enough using the faster algorithm. And then you can’t avoid it, although maybe you could wait a couple of years for a faster computer. But that’s going to be rare. Most of the time that patent will to be easy to avoid.
On the other hand, a patent on an algorithm may be impossible to avoid. Consider the LZW data compression algorithm. Well, as I explained, we found a better data compression algorithm, and everybody who wanted to compress files switched to the program gzip which used the better algorithm. And the reason is, if you just want to compress the file and uncompress it later, you can tell people to use this program to uncompress it; then you can use any program with any algorithm, and you only care how well it works.
But LZW is used for other things, too; for instance the PostScript language specifies operators for LZW compression and LZW uncompression. It’s no use having another, better algorithm because it makes a different format of data. They’re not interoperable. If you compress it with the gzip algorithm, you won’t be able to uncompress it using LZW. So no matter how good your other algorithm is, and no matter what it is, it just doesn’t enable you to implement PostScript according to the specs.
But I noticed that users rarely ask their printers to compress things. Generally the only thing they want their printers to do is to uncompress; and I also noticed that both of the patents on the LZW algorithm were written in such a way that if your system can only uncompress, it’s not forbidden. These patents were written so that they covered compression, and they had other claims covering both compression and uncompression; but there was no claim covering only uncompression. So I realized that if we implement only the uncompression for LZW, we would
