Thursday, July 8, 2010

Bilski says software is not patentable

The US Supreme Court's decision In re Bilski doesn't say much, but I think it says more than perhaps Justice Kennedy intended. In particular I think it is possible to argue that software is not a patentable subject matter.

The Court rejected the "machine or transformation" test as being too narrow; it would seem to exclude things, including business methods, that are "processes" or "methods" under the usual English meanings of those words. But the Court also refers to precedents in Benson, Flook and Diehr (three previous cases), and states that these were used to decide Bilski. It follows that the principles in those precedents are the ones that should generally be applied. Crucially the Court also declined to endorse anything in the State Street decision that originally opened the floodgates to software patents.

The Benson case involved a patent for converting BCD into pure binary. It was held to be an unpatentable abstract idea because the method in the patent was derived from a formula, and so a patent on the method was in effect a patent on the formula.

The Flook case was for a patent on setting alarm thresholds based on a "mathematical algorithm". Again the patent was overturned. In this case a key principle made in the decision was that any mathematical algorithm must be assumed to be "well known". This is a crucial point; a patent can include things that were already known, provided it combines them in a novel way, or with some novel element. The invention has to be considered as a whole, but adding a "trivial post-solution activity" such as setting an alarm wasn't considered to be inventive enough if the formula used was considered to be part of prior art. This means that any "mathematical algorithm" you might come up with is considered as "well known" even if you are the first person to invent it. It can go into a patent, but it doesn't add to the novelty.

Diehr was concerned with a patent for curing rubber. The patent described a machine that measured the mould temperature continuously, pushed the temperature readings through a "mathematical formula" (which was in fact very well known in practice as well as in the narrow legal sense), and opened the mould when the output reached a certain value. The patent was upheld because the novelty lay in the use of continuous measurements to control mould opening, rather than a precomputed delay as had previously been the practice. The fact that a formula was embedded in a computer program as part of the invention did not change this.

So where does this leave software patents? The Court followed the reasoning in the precedents to conclude that since the concept of "hedging" in the Bilski patent was reduced to a mathematical formula in Claim 4, that formula could not be considered a novel contribution. Nothing else in the patent was novel, so they rejected it.

Following this reasoning, it would seem that anything that can be reduced to a "mathematical formula" or "mathematical algorithm" is not patentable. It is possible that Justice Kennedy made a layman's error in his thinking here by assuming that all "mathematical formulae" are concerned with real numbers, as were all the formulae considered in Bilski and the precedents listed.

But of course any computer scientist or mathematician will tell you that this is not true. The whole of discrete mathematics is concerned with mathematical formulae and algorithms that are not related to real numbers.

So it would seem that formulae and algorithms related to discrete mathematics would fall under this rule as well. The Court uses the term "algorithm" and "formula" as synonyms, as indeed they are. To see this, consider the QuickSort algorithm:

  1. If there are only 0 or 1 items in the list to be sorted then stop.
  2. Take the first item from the list of things to be sorted. Call this the "pivot".
  3. Divide the rest of the items into two sublists; (a) those less than the pivot, and (b) the rest.
  4. Apply this whole algorithm to each of the two sublists from step 3, thereby sorting the sublists.
  5. Assemble the sorted list by taking the sorted sublist (a), appending the pivot, and then appending the sorted sublist (b).
This is clearly a method or process. It is also an algorithm. It can also be represented as a formula:

sort [] = []
sort [x] = [x]
sort (pivot:rest) = sort sublistA ++ [pivot] ++ sort sublistB
where (sublistA, sublistB) = partition (< pivot) rest


This is QuickSort written in Haskell. Every Haskell program has a well-defined translation to a formula in the Lambda Calculus, and the Lambda Calculus is part of mathematics. Haskell is turing-complete, which means that any process that can be written as a sequence of steps for manipulating information of any sort can also be written as a Haskell program. Therefore any such process can be reduced to a "mathematical formula". Since mathematical formulae are not patentable subject matter it follows that no process for manipulating information is patentable subject matter.

It might be argued that the use of the modifier "mathematical" by the Court is an attempt to distinguish mathematical formulae and algorithms from non-mathematical ones. But in reality there is no such distinction.

Merriam-Webster defines mathematics as:
the science of numbers and their operations, interrelations, combinations, generalizations, and abstractions and of space configurations and their structure, measurement, transformations, and generalizations
This is a poor definition, since it seems to ignore many topics that are conventionally considered part of mathematics even though they have no apparent relationship to numbers, such as graph theory and topology.
The Britannica is rather more useful, defining mathematics as:

[The] science of structure, order, and relation that has evolved from counting, measuring, and describing the shapes of objects.

It deals with logical reasoning and quantitative calculation. [...]

So is there a class of algorithms or formulae that is not "mathematical" in nature? Clearly not. If any algorithm can be recast as a formula. If such a formula is a product of logical reasoning then it falls under the ambit of mathematics. Even if we take the more limited definition of Merriam-Webster, Godel showed how any logical statement can be recast as a statement of number theory.

Another possible objection to my argument is that mathematics is "abstract" while a process is "concrete". But this is a distinction without a difference. It suggests that the algorithm for QuickSort, expressed as a series of steps, is somehow more concrete than the equivalent formulation in Lambda Calculus. Of course any formulation of QuickSort is going to be longer than the typical single line that non-mathematicians think of when presented with the phrase "mathematical formula", but this would imply that patentability is determined by length, which is clearly nonsense. A mathematical formula that takes a dozen pages to write down is still a mathematical formula.

So I have to conclude that anything capable of being expressed as a computer program is not patentable subject matter under US law.

This probably extends to business method patents as well. Since any business method is the manipulation of information, it follows that it can be written as a computer program (and in fact many Internet businesses have been built by doing exactly that). Even if the business method requires human judgement at some point, that judgement can be treated simply as another input to the program.

To return to where I started, the Supreme Court says that business methods are not a-priori unpatentable, since they are processes and methods. Bilski may not have had sufficient novelty once the formula was stripped out, but the Court wanted to allow for the possibility of a set of business methods that were sufficiently novel. However by following the court's own reasoning it is clear that this set is empty.

3 comments:

Anonymous said...

Consulting opportunities for Haskell programmers in coming patent fights, then.

Bruce Lewis said...

Overall great summary of Benson, Flook and Diehr. One correction on Diehr: You write "The patent was upheld" which does not accurately describe the decision.

A patent must pass three tests to be upheld: It must be statutory subject matter, novel, and non-obvious. The Supreme Court only examined whether the patent was statutory subject matter. The majority wrote, "It may later be determined that the respondents' process is not deserving of patent protection because it fails to satisfy the statutory conditions of novelty under §102 or nonobviousness under §103." So they didn't exactly uphold the patent.

adrianstovall said...

"I can provide the mathematical formula for a chair using boolean logic and the equation for an infinite plane. That does not make the invention non-patentable. Valid patents, generally speaking, are novel and non-obvious applications of the laws of nature and/or mathematics."

While I am somewhat skeptical that you can provide the mathematical formula for a chair in boolean logic, I'll stipulate that you can, for the purposes of furthering this discussion.

If you can do that, *and* the design of said chair is novel and non-obvious, *and* your formula describes a physical object, or a process to create a physical object, then yes, it is patentable.

You should not be able to patent software for the same reason that you cannot patent a formula for an infinite plane...both of the patent descriptions are completely abstract (i.e. there is no tangible result).

To inject the missing piece to your closing sentence, I would say "Valid patents, generally speaking, are novel and non-obvious applications of the laws of nature and/or mathematics embodied in a machine or process that produces a tangible result."

Generally, this is wrapped up in the machine-or-transformation test which is a rethinking of the earlier "concrete, useful, and tangible" test.

Software *never* produces a tangible result, is not a machine, and is not capable of transforming anything. Software is instructions, formulas, algorithms...math written by human artists known as programmers.