The computer science community has tried to explain this to the patent industry, but these explanations have fallen on deaf ears. So I thought I would try a different tack.

Google has just been ordered to pay $5M for infringing patent 5,893,120 (hereafter "Patent 120"). This patent covers a very simple data structure and the algorithms for manipulating it. In fact much of the text of the patent is a pseudo-code implementation in a Pascal-like language. So I thought I would provide a practical demonstration of what has, until now, been a theoretical proposition; the reduction of a software patent to set of mathematical formulae. The result is below, and is also posted here (although I believe that the paste-bin will eventually expire).

I chose this patent partly because it is comparatively simple (there are 95 lines of Haskell source code in the file), but also because it is potentially important; Google's "infringement" consisted of using Linux, which uses this algorithm. Hence anyone using Linux is a potential target.

Red Hat is reportedly seeking a declarative judgement that this patent is invalid, and Google is expected to appeal, so this is not over yet. If anyone knows how I can contact their lawyers to draw these formulae to their attention, I'd be grateful.

**Edit 1:**A brief overview of the relationship between Haskell and the Lambda Calculus can be found here.

**Edit 2:**Of course a judge isn't going to know the Lambda Calculus from a lump of rock, but that is what expert witnesses are for. Get a professor of mathematics from an internationally recognised university to testify that these are formulae in the Lambda Calculus, and that the Lambda Calculus is part of mathematics, and you have a sound legal proof. The only thing the patent holders could do is find another professor to testify differently.

**Edit 3:**Sorry about the broken formatting. If you want to review the code you can either look at this colourised version or copy and paste it into your favourite editor.

Edit 4: This post has been slashdotted. Rather than try to respond to all the various comments individually I have posted a general response to the common themes.

In the meantime, here are the formulae:

{- |

The claims of United States Patent 5,893,120 may be reduced to a set

of mathematical formulae expressed in the Typed Lambda Calculus, also

known as System F. This file contains these formulae. The language

used is Haskell, which is a version of System F with extra "syntactic

sugar" to make it useful for practical purposes.

It happens that formulae expressed in Haskell can also be transated by

a Haskell compiler into executable computer programs. However that

does not make a Haskell function any less of a mathematical formula.

Otherwise the quadratic formula

> x = (-b +/- sqrt (b^2 - 4ac))/2a

would be rendered patentable subject material by the same argument.

-}

module Patent120 where

import Data.Char (ord)

-- The "ord" function defines a bijection between text characters and

-- numbers.

import Data.Map (Map)

import qualified Data.Map as M

-- The Data.Map module is a standard module defined entirely as a set

-- of Haskell formulae, in the same way as this module. The "import"

-- means that these formulae are incorporated with the formulae given

-- here.

{-

Claim 1. An information storage and retrieval system, the system

comprising:

a linked list to store and provide access to records stored in a

memory of the system, at least some of the records automatically

expiring,

a record search means utilizing a search key to access the linked

list,

the record search means including a means for identifying and removing

at least some of the expired ones of the records from the linked list

when the linked list is accessed, and

means, utilizing the record search means, for accessing the linked

list and, at the same time, removing at least some of the expired ones

of the records in the linked list.

-}

-- | A record with Birth value below some threshold is considered "expired".

type Birth = Integer

-- | Records in the list have their birth recorded, and also contain

-- a key and a value.

data Record k a = Record Birth k a

-- | True iff the record is older than the threshold argument.

expired t (Record b _ _) = b < t -- | True iff the record matches the key. matches k (Record _ k1 _) = k == k1 -- | The value stored in a record. value (Record _ _ v) = v -- | Records are stored in a linked list in the system memory. type Storage k a = [Record k a] -- | The "search1" function includes a threshold age parameter. -- It returns both the items that match the key and the linked list -- with the expired items removed. -- -- The recitation of "means" cannot be used to disguise the formula -- given here. Otherwise any mathematical formula could be patented -- by reciting e.g. "addition means" and "multiplication means" that are -- mechanically derived from the formula. search1 :: (Eq k) => Birth -> k -> Storage k a -> (Storage k a, [a])

search1 t k records = foldr nextItem ([], []) records

where

nextItem r@(Record b k2 v) (retained,found) =

(if b > t then r:retained else retained,

if k == k2 then v:found else found)

{-

Claim 2. The information storage and retrieval system according to

claim 1 further including means for dynamically determining maximum

number for the record search means to remove in the accessed linked

list of records.

-}

-- | Similar to "search1", but with an added parameter for the maximum

-- number of records to remove.

search2 :: (Eq k) => Int -> Birth -> k -> Storage k a -> (Storage k a, [a])

search2 n t k = (\(_,x,y) -> (x,y)) . foldr nextItem (n,[],[])

where

nextItem r@(Record b k2 v) (n2,retained,found) =

(n2-1,

if b > t || n2 == 0 then r:retained else retained,

if k == k2 then v:found else found)

{-

Claim 3. A method for storing and retrieving information records using

a linked list to store and provide access to the records, at least

some of the records automatically expiring, the method comprising the

steps of:

accessing the linked list of records,

identifying at least some of the automatically expired ones of the

records, and

removing at least some of the automatically expired records from the

linked list when the linked list is accessed.

Claim 4. The method according to claim 3 further including the step of

dynamically determining maximum number of expired ones of the records

to remove when the linked list is accessed.

-}

-- | Claim 3 can be reduced to the same formula as Claim 1. The use of

-- a sequence of steps cannot disguise the fact that this represents

-- a mathematical formula. Otherwise it would be possible to patent

-- any mathematical formula simply by reciting the steps in evaluating

-- it. e.g. "step 3: the addition of the results of step 1 and step 2"

search3 :: (Eq k) => Birth -> k -> Storage k a -> (Storage k a, [a])

search3 = search1

-- | Likewise Claim 4 can be reduced to the same formula as Claim 2.

search4 :: (Eq k) => Int -> Birth -> k -> Storage k a -> (Storage k a, [a])

search4 = search2

{-

Claim 5. An information storage and retrieval system, the system

comprising:

a hashing means to provide access to records stored in a memory of the

system and using an external chaining technique to store the records

with same hash address, at least some of the records automatically

expiring,

a record search means utilizing a search key to access a linked list

of records having the same hash address,

the record search means including means for identifying and removing

at least some expired ones of the records from the linked list of

records when the linked list is accessed, and

meals, utilizing the record search means, for inserting, retrieving,

and deleting records from the system and, at the same time, removing

at least some expired ones of the records in the accessed linked list

of records.

-}

-- | Every key has a hash code. Strings of characters may be used as

-- keys.

class (Eq k) => Hashable k where

hash :: k -> Int -- Every key has a hash code.

instance Hashable Char where hash = ord

instance (Hashable a) => Hashable [a] where

hash = foldr (\x h -> ((hash x + h) * 53 + 1) `mod` 1733) 0

type HashedStore k a = Map Int [Record k a]

-- | Access a hashed store with a function that returns the modified list of records.

hashAccess5 :: (Hashable k) =>

(Storage k a -> (Storage k a, [a])) -> Birth -> k -> HashedStore k a -> (HashedStore k a, [a])

hashAccess5 f t k store = (M.insert h retained store, result)

where

h = hash k

(retained, result) = case M.lookup h store of

Just records -> f $ filter (expired t) records

Nothing -> ([], [])

-- | Search using hashAccess.

search5 :: (Hashable k) => Birth -> k -> HashedStore k a -> (HashedStore k a, [a])

search5 t k = hashAccess5 srch t k

where srch store = (store, map value $ filter (matches k) store)

-- | Insert using hashAccess.

insert5 :: (Hashable k) => Birth

-- ^ Expiry threshold for old entries.

-> Birth

-- ^ Birth date for new entry.

-> k -> a -> HashedStore k a -> HashedStore k a

insert5 t b k v = fst . hashAccess5 (\store -> (Record b k v : store, [])) t k

-- | Delete using hashAccess

delete5 :: (Hashable k) => Birth -> k -> HashedStore k a -> HashedStore k a

delete5 t k = fst . hashAccess5 (\store -> (filter (not . deleted) store, [])) t k

where deleted (Record _ k1 _) = (k == k1)

{-

Claim 6. The information storage and retrieval system according to

claim 5 further including means for dynamically determining maximum

number for the record search means to remove in the accessed linked

list of records.

-}

-- | Access a hashed store with a function that returns the modified list of records. The "Int"

-- argument is the maxiumum number of expired records to remove.

hashAccess6 :: (Hashable k) =>

Int -> (Storage k a -> (Storage k a, [a])) -> Birth -> k -> HashedStore k a -> (HashedStore k a, [a])

hashAccess6 n f t k store = (M.insert h retained store, result)

where

h = hash k

(retained, result) = case M.lookup h store of

Just records -> f $ filterN n (expired t) records

Nothing -> ([], [])

filterN _ _ [] = []

filterN n1 p (x:xs) = if n1 <= 0 || p x then x : filterN n1 p xs else filterN (n1-1) p xs -- | Search using hashAccess. search6 :: (Hashable k) => Int -> Birth -> k -> HashedStore k a -> (HashedStore k a, [a])

search6 n t k = hashAccess6 n srch t k

where srch store = (store, map value $ filter (matches k) store)

-- | Insert using hashAccess.

insert6 :: (Hashable k) => Int

-> Birth

-- ^ Expiry threshold for old entries.

-> Birth

-- ^ Birth date for new entry.

-> k -> a -> HashedStore k a -> HashedStore k a

insert6 n t b k v = fst . hashAccess6 n (\store -> (Record b k v : store, [])) t k

-- | Delete using hashAccess

delete6 :: (Hashable k) => Int -> Birth -> k -> HashedStore k a -> HashedStore k a

delete6 n t k = fst . hashAccess6 n (\store -> (filter (not . deleted) store, [])) t k

where deleted (Record _ k1 _) = (k == k1)

{-

Claim 7. A method for storing and retrieving information records using

a hashing technique to provide access to the records and using an

external chaining technique to store the records with same hash

address, at least some of the records automatically expiring, the

method comprising the steps of:

accessing a linked list of records having same hash address,

identifying at least some of the automatically expired ones of the records,

removing at least some of the automatically expired records from the

linked list when the linked list is accessed, and

inserting, retrieving or deleting one of the records from the system

following the step of removing.

Claim 8. The method according to claim 7 further including the step of

dynamically determining maximum number of expired ones of the records

to remove when the linked list is accessed.

-}

-- | As with Claim 3 vs Claim 1, the formulae for Claim 7 are the same as for Claim 5

hashAccess7 :: (Hashable k) =>

(Storage k a -> (Storage k a, [a])) -> Birth -> k -> HashedStore k a -> (HashedStore k a, [a])

hashAccess7 = hashAccess5

search7 :: (Hashable k) => Birth -> k -> HashedStore k a -> (HashedStore k a, [a])

search7 = search5

insert7 :: (Hashable k) => Birth

-- ^ Expiry threshold for old entries.

-> Birth

-- ^ Birth date for new entry.

-> k -> a -> HashedStore k a -> HashedStore k a

insert7 = insert5

delete7 :: (Hashable k) => Birth -> k -> HashedStore k a -> HashedStore k a

delete7 = delete5

-- | And the formulae for Claim 8 are the same as for Claim 6

hashAccess8 :: (Hashable k) =>

Int -> (Storage k a -> (Storage k a, [a])) -> Birth -> k -> HashedStore k a -> (HashedStore k a, [a])

hashAccess8 = hashAccess6

search8 :: (Hashable k) => Int -> Birth -> k -> HashedStore k a -> (HashedStore k a, [a])

search8 = search6

insert8 :: (Hashable k) => Int

-> Birth

-- ^ Expiry threshold for old entries.

-> Birth

-- ^ Birth date for new entry.

-> k -> a -> HashedStore k a -> HashedStore k a

insert8 = insert6

delete8 :: (Hashable k) => Int -> Birth -> k -> HashedStore k a -> HashedStore k a

delete8 = delete6

## 64 comments:

Good work! I noticed your quadratic formula has a couple of signs wrong. Should the expression not be (-b +/- sqrt(b^2 - 4ac))/2a ? The point is still valid no matter what the algorithm. Thanks.

I agree - patents are a poor tool for almost everything, and especially poor for software.

But you're trying to argue in the wrong way here: your post seems almost deliberately obtuse. There's a sorities paradox element to it. A little bit of mathematics is not patentable, even when it builds on a bunch of stuff that came before, but put the whole abstract thing together, and people see it as forming something else. One could reduce the description of many physical gadgets to mathematical formulae, but that wouldn't gadgets any less patentable. Numbers aren't patentable (to my knowledge), but even though you can encode any amount of information as a large number, that still doesn't get you out of the copyright and patent territory.

Another way to put it is that the law means what judges decide it to mean, not what it says, and judges are humans, not machines. They judge laws by what they believe their intent to be, and by how they are phrased, in some mixed proportion that varies according to the judge. Trying to argue entirely based on a mechanical interpretation of law is autistic, in the worst way - i.e. stupid in an almost medical fashion.

I have to disagree with your 'Bilski ruling renders all software unpatentable' comment. The USPTO has proven to be more subtle than this in their Press Release 10-35. There are ways handle Bilskis without ruining the patent system (see http://jverstry.blogspot.com/2010/09/ending-software-patents-is-not-solution.html).

@Barry Kelly

"One could reduce the description of many physical gadgets to mathematical formulae." The description of a mechanical invention, perhaps, but the description is not what is covered by the patent. The application of the invention is what is covered. Here Paul shows that the software application can be reduced to a purely mathematical formula. This is not a step that should be brushed off quite so flippantly. Judges are human and can be thrown off the idea that many software patents are, by their nature, purely mathematical entities by what amount to levels of indirection in the application of the patented ideas. But showing that, in fact, all of the cruft can be boiled away and the math laid bare but still remain in a functional state will be hard even for the 5th circuit in East Texas to ignore.

Essentially, what this means is someone can come along and patent a particular application of a software idea but someone else can reduce it to lambda calculus (un-patentable) and build a different useful higher abstraction from that formula, skirting the original patent. Now, that would not stop someone from trying to patent as many forms of applying that idea as possible (I am sure they will try) but if someone wants to use a software idea, there will be some application method that remains un-patented.

Nice work! Kudos for reading through and actually understanding the patent to the point that you could show it as a mathematical proof.

The most common misconception geeks have in these matters is that abstract math is unpatentable, and that software patents are purely abstract, and hence unpatentable.

OK, let's look at this patent. This patent claims to conserve memory by removing expired records for garbage collection. Please show, in pure abstract mathematics, that the memory saved by this technique does NOT result in fewer physical RAM chips in a datacenter, thus saving substantial real-world, non-abstract money. I'm sure there's a monad converting lesser memory usage into hard cash somewhere on the Internet. No? Does that mean striving to use less computer resources like RAM has no practical, monetary impact?

I agree there is a problem with this patent, but arguing it's a purely abstract mathematical algorithm is not it. Not when it's trivial to show that it saves RAM, which is a physical, finite resource, resulting in real world advantages. The real problem is that we should be able to prove that this is a rather obvious method of reclaiming memory. Frankly, it's shocking that even with Google's backing, their lawyers could not find relevant prior art to kill this patent.

Barry Kelly, the Haskell code above is indeed a piece of pure mathematics. There is no "sorites paradox" about this. In case this is not immediately clear, here is a quick translation of the first claim (The other claims may be translated in a similar way) into natural language. Note that the text is basically indistinguishable from what you might find in a mathematical paper or monograph. (Especially in the introductory sections, where definitions are often presented)

- We define a "birth" as an integer.

- We define a "record" parameterized on types

K,Vas a triple containing a birthb, a keykof typeKand a valuevof typeV.- We say that a record

ris "expired" with respect to thresholdtif the record's birth is lower thant.- We say that a record

r"matches" a keykif the record's key is equal tok.- We say that the "value" of a record is

vif the record's value is equal tov.- We define a "storage" parameterized on types

K,Vas a sequence of records of typesKandV.Let us define an auxiliary function, known as the

right foldof a binary functionfover a sequencexs, given a zero argumentz. It is defined by induction as follows:-- If the sequence is empty, then the result is

z.-- Otherwise, let

xbe the first element of the sequence, andxs'be the sequence comprising all other elements. Note thatxs'may be empty. Then, the result is given by the binary operationf, withxas first argument andx'as second argument, wherex'is the right fold offoverxs'with zero argumentz.We will define a function below, named "search1". The function is parameterized on a key type

Kand takes three arguments: a birtht, a keykand a storagersof key typeKand value typeV. It returns an ordered pair, comprising a storage of key typeKand value typeVand a sequence of values of typeV.-- Let us define a binary function

next item, parameterized by birth thresholdtand keyk. Its first argument is a recordr. Its second argument is an ordered pair, comprising a storageretainedand a sequence of valuesvs. It returns an ordered pair, defined as follows:..-- The first element is a storage. If the birth of

ris greater than the thresholdt, then the first element of the storage isrand all other elements are given byretained. Otherwise, the storage isretained...-- The second element is a sequence of values. If the key of

ris equal tok, then the first element of the sequence is the value ofrand all other elements are given byvs. Otherwise, the sequence isvs.We can now define search1 as the right fold of

next itemover the storagers, where the zero argument is the ordered pair comprising the empty storage as first component and the empty sequence of values as second component....

Give us a break. Brevity is the soul of wit. Boil it down to the math!

We will now define a function, named "search2". The function is parameterized on key and value types

K,V. It takes four arguments: an integern, a birtht, a keykand a storagersof key and value typesK,V.-- Let us define a binary function

next_item_2, parameterized by birth thresholdtand keyk. Its first argument is a recordr. Its second argument is an ordered triple, comprising an integern_2, a storageretainedand a sequence of valuesvs. It returns an ordered triple, defined as follows:..-- The first component is an integer. It is given by

n_2 - 1...-- The second component is a storage. If the birth of

ris greater than the thresholdtorn_2equals 0, then the first element of the storage isrand all other elements are given byretained. If neiher condition is true, the storage isretained...-- The third component is a sequence of values. If the key of

ris equal tok, then the first element of the sequence is the value ofrand all other elements are given byvs. Otherwise, the sequence isvs.Consider the result of right-folding the binary function

next_item_2over the storagers, with the zero argument being the triple given bynas first component, the empty storage as second component and the empty sequence of values as third component.This gives a triple

ucomprising an integer, a storage and a sequence of values. Then, the result ofsearch2is the ordered pair comprising the second and third component fromu.Anonymous - there are none more blind than those who will not see. I've tried to explain how normal people see this. That's as far as I can go.

Barry Kelly, perhaps you're right that "normal people" might be unwilling to look at these similarities. But all it takes is some expert witnesses testifying that the formulae in the OP describe a pure mathematical algorithm, that the natural language above is a close paraphrasing of these formulae, and that a large number of mathematical papers have been published which contain very similar language.

Judges are very unwilling to interpret provision vacuously, so if the prohibition on patents covering "mathematical formulae" and "mathematical algorithms" is to have any meaning at all, it mus apply to the above algorithm.

You've put so much effort into it already, you might as well formulate it as an even more obviously mathematical proof, in Coq or Agda or something.

The argument from Lambda Calculus fails because it is misleadingly narrow. Algorithmic information theory allows one to equivalently show that

allpatentable subject matter is mathematics, but the people who like those consequences would like to ban all patents and not just software patents. This kind of selective logic damages the credibility of the argument, ignoring the technical merits.More generally though, the conflation with an application of mathematics and a mathematical theorem is improper. Algorithms are generally applications of mathematics, not theorems, and therefore are patentable subject matter. You can patent a sorting algorithm but you can't patent the concept of sorting (for which there are infinite algorithms). Chemical process patents are exactly analogous to algorithm patents in every aspect but I rarely see that pondered either.

The reason computer algorithm patents are allowed in Europe is that they are direct abstractions of electronic circuits, and electronic circuits are generally construed to be patentable subject matter. So-called "business method" patents are a different matter; they lack sufficient precision in their description to be simultaneously useful and valid.

All of patent law deals with interpretations, most of which are involve varying degrees of subtly.

The Federal Circuit Court has provided a great deal of well-written guidance. This particularly applies to what is and is not patentable.

The issue of what is and is not patentable is not black and white, such as, “mathematical formulas are not patentable,” or “software is patentable.”

A process that creates something useful and tangible is patentable, whether or not that process involves a calculation. What is not patentable is a “pure” formula that is not tied to something tangible. Data structures are tricky. The newer rules (yes, lots of mistakes were made in the past) are that generalized data structures, such as a table or a linked list, do not count as “tangible.” However, if those data structures are used (critically) to perform useful work, such as to refine steel or to serve up ads on websites, then the ENTIRE process is patentable. Subject, of course to all the other restrictions, such as non-obviousness.

These rules are not really new. They are the same rules that apply to mechanical inventions. For example, you cannot patent a “law of nature,” even it is something complex and nobody else knew about it. You can, however, patent a new device that takes advantage of this law of nature. For example, you cannot patent super-conductivity, but you can patent a useful device that uses super-conductivity.

Even mechanical inventions could be reduced to equations. CAD systems and hardware description languages are such examples. However, these “mathematical” representations have no bearing on the patentability.

Thus, the “deaf ears” referred to are those practitioners in the field who are following well-established law.

You don’t have to like current patent law. Many people don’t. European rules, for example, are different that ours. Note that not liking is distinct from not understanding.

- Registered Patent Agent

Kim:

"A process that creates something useful and tangible is patentable, whether or not that process involves a calculation. What is not patentable is a “pure” formula that is not tied to something tangible. Data structures are tricky. "Wait a moment.

Data structures are tricky?

Think about a variable. Something as simple as "x". Is this tricky? Is this patentable?

How about a vector? A hash?

In which moment the data structures stop being pure mathematics and start to be "tricky" and patentable?

Registered patent agent:

"The argument from Lambda Calculus fails because it is misleadingly narrow. Algorithmic information theory allows one to equivalently show that all patentable subject matter is mathematics..."Your argument fails because is misleadingly broad.

You say that everything can be proved to be mathematics, so, the part of the law that says that mathematics is not patentable is basically useless.

"...but the people who like those consequences would like to ban all patents and not just software patents".I guess you are one of those who would like that everything could be patentable, including software and mathematics.

Nice argument, but unfortunately I have to agree with Barry Kelly on this one. However, that does not mean the whole idea of patenting does not need some serious reworking. The original idea of the patent was to protect little guys from big guys stealing their ideas and unfairly competing with them. In today's world patents are the domain of big guys who use them to stop little guys innovating and they simply create a greater ability for the big guys to monopolize a market.

Barry Kelly, you miss the point as most people do:

"One could reduce the description of many physical gadgets to mathematical formulae,"

And one would not have a single gadget in one's possession.

The software is not *described* by mathematical formula. The software *is* a mathematical formula.

It is unpatentable. Distribution of software is per se incapable of being a patent infringement, just as distribution of blueprints is incapable of being a patent infrignment.

Executing the software on a general-purpose computer? That is merely what the general-purpose computer is designed to do. Computers are machines for computing mathematical formulas. Why do you think they're called COMPUTE-rs? The computer is of course patenable, but running an individual formula (piece of software) on it is not patentable, it's merely the purpose for which the computer was designed and sold.

You can't patent every individual book which may come off a printing press, nor can you patent the "process of printing Moby Dick on a printing press". The printing press patent covers everything physical, everything real-world, everything patentable.

You can of course *copyright* the software, just as you can copyright the specific expression of any given mathematical formula. Most math books *are* copyrighted. A specific way of writing the quadratic formula is certainly copyrightable. And there are always alternative expressions for it, such as

(-0.5)b/a + ( (0.25)(b/a)**2 - c/a )**(1/2)

So copyright doesn't pose any problems.

Patenting mathematics is unacceptable, and software is mathematics. It's amazing how many people miss this point. You can encode any amount of information as a large number, and it's *copyrightable*, but *no amount of information is patentable*. Information is simply not patentable. Only real-world applications of that information are patentable. The "patent bargain" in fact requires that the information itself be distributed freely.

So if you patented something involving software (something with real-world content, say, a rubber-curing process), the LAW says that the software can be freely redistributed, apart from copyright restrictions.

Software IS math. Perhaps only people who've studied math understand this. The people who INVENTED software were all mathematicians and they ALL understand this.

It's very problematic that judges don't understand this. It's nothing to do with "autistic" -- it has to do with the fact that judges don't understand software. *Every single person involved in the creation of the field of programming, every single one, knows that software is pure mathematical formulas.* In fact there is absolutely no way to patent pure software without patenting math and causing professors to infringe the patent through pure mental activity. The ignorance of judges is no excuse for this.

"Please show, in pure abstract mathematics, that the memory saved by this technique does NOT result in fewer physical RAM chips in a datacenter,"

I don't have to show that in abstract mathematics; the people making the patent have to prove, NOT using abstract mathematics, that the technique actually DOES result in fewer physical RAM chips; then they have to limit their patent claims to the case where it actually does result in fewer physical RAM chips.

At which point Google is not infringing, because it is not "using fewer RAM chips" as a result of applying this. In fact, Google's just distributing software -- math. Google is *incapable* of infringing directly. It's the responsibility of the hardware manufacturer to decide whether they want this.

This is the most *basic* refutation of Anonymous's claim. In fact, application of this mathematics to minimize resource usage is probably both obvious and non-original, as well.

"Algorithmic information theory allows one to equivalently show that all patentable subject matter is mathematics,"

No, it doesn't. It only shows that the *description* of the subject matter is mathematics.

There is a key and very important legal difference between the *description* of something and the actual thing. The *blueprints* for a patented device can be distributed and copied freely -- they must, essentially, be specified in the patent and published! The actual *device* is what is restricted.

The problem for those who wish to patent software is that software, being pure math, is nothing more than blueprints. The actual patentable invention was the general-purpose computer. Improvements in the hardware remain patentable. The software was never, and is never patentable (though it's copyrightable).

"Even mechanical inventions could be reduced to equations."

Bullshit. Have you ever plugged in an equation and turned it on, and had it cut a piece of wood?

"CAD systems and hardware description languages are such examples."

No. They are examples of *mathematical descriptions* of mechanical inventions. The descriptions are completely unpatentable, and in fact patent law requires that they be freely and openly published and redistributed, last I checked. Only the actual invention can be patented.

"However, these “mathematical” representations have no bearing on the patentability."

... of the physical item. But in software, there *IS NO PHYSICAL ITEM*.

I realize that the cleverer patent lawyers will claim that combining the sotware with a computer creates a physical item.

Nope. The physical item already exists, and it's already patented: it's the computer, and its function, as patented, is to do any mathematical computation whatsoever. Running software on it is merely using it for its intended purpose.

"A process that creates something useful and tangible is patentable, whether or not that process involves a calculation. What is not patentable is a “pure” formula that is not tied to something tangible."

Exactly. This is why all software is unpatentable. None of it is tangible. This is also why the rubber-curing case was arguably decided correctly -- in that case the patent was NOT on the software.

The Federal Circuit, however, went bonkers and started allowing patenting of pure mathematics with no tangible product. Bilski smacked that down hard. Data structures are not tangible. Serving up ads on websites is not tangible either (ever touched an ad? No, I didn't think so). The vast majority of software patents are simply not on processes which genuinely transform matter in a new way -- they are on pure abstract symbol manipulation, which is pure mathematics, not applied mathematics.

Barry Kelly wrote:

"Anonymous - there are none more blind than those who will not see. I've tried to explain how normal people see this"

You're saying you're one of the "normal" people who refuses to see and is therefore as blind as they get? I don't get where you're going with this. Any actual "person having ordinary skill in the art" knows that software is pure math and unpatentable, and I can provide the references, from Knuth to Bill Gates, for that statement.

Kim said, "You can patent a sorting algorithm but you can't patent the concept of sorting...."

I think this might have been true prior to Bilski, but since that ruling I am not sure that algorithms are patentable. The USPTO guidance of 2010 July 27 says if "Machine is generically recited such that it covers any machine capable of performing the claimed step(s)" - then this weighs _against_ patentability.

From this, it would seem to me that the "machine" would have to be a specific kind of machine. In the case of the Google code, the algorithm works in any computer. The patent does not apply to a particular use of the computer, e.g., processing insurance claims.

I would read the USPTO guidance as meaning that the application of the patent must be very specific - domain specific. It would seem to exclude general purpose algorithms that work in any computer.

You're forgetting the idea of the invention. Anything can be boiled down to simple math, blue prints, etc... innovation can't be mathematical.

Barry Kelly is right on the reduction. (Though, wrong that patents are a poor tool).

What Barry Kelly and Kim said.

Neroden should disclose that (s)he is espousing an opinion.

Who cares that software is a nonphysical description? It's an executable description, people sell such description as products that do useful things. So it's patentable after all...

I should note that patent is written in plain language and not as executable language. Like mechanical patents cover all possible physical implementations of patent, software patent covers all possible executable implementations of patent.

To the anonyous going on about saving RAM.

Garbage collection takes RAM to operate.

Get it?

Whether this saves RAM or not depends heavily on a lot of factors, none of which seem to be mentioned in the patent.

Get it?

Should I point out that hashing algorithms tend to blow up unless fairly carefully designed for the subject text being hashed, and that general hashing algorithms tend to take, ahem, lots of RAM on the average?

Get it yet?

Should I point out that, near as I can tell, this patent does not even attempt to describe a hash or the text being hashed or anything that an engineer could point to, to make the patented "device" function according to the description?

Do you get it yet?

(Dang, if I keep this up, I'm going to start shouting, even though I know that shouting only makes people who will not hear feel picked upon. Somebody else please draw what ought to be the obvious conclusion in my place, because I'm afraid I can't just say that there is nothing in this patent but wishful thinking and describing how ideal machines ought to behave in a perfect world, nothing to help real engineers build real machines that actually behave any better than tons of software that well predates this patent, ... )

Reminds me of when the DeCSS code was made illegal and someone encoded it as a prime number, making it the first "outlawed number" ever.

> Data structures are tricky.

Ignoring for a moment the fact that even the data structures are mathematics.

I was taught hashes and linked lists, and the trick of using them together where two keys hash to the same value. I was taught it at university, circa 1980. It was not cutting edge even then.

So even if data structures were "tricky", they are firmly unpatentable due to prior art.

It seems to me that the only aspect of this patent that is not ruled out due to prior art, is the idea of removing expired elements during a search. Even I, as a failed mathematician, software engineer, can reduce that to pure mathematic formulae.

I know you are talking about the US courts but thought it might be interesting to mention that some of the generally most well regarded Law Lords (highest as was judges in Britain) of the 20th Century actually did math's at places like Cambridge before taking up law.

Clever. Although I would have done it lisp instead. But seriously, though, this patent crap is a huge drain on the economy and needs to stop.

www.awkwardengineer.com

On the argument between those believing that nifty software plus general-purpose computer = patentable and those believing the opposite...

It has been stated already (numerous times) that all software is math. If you understand that the context of that statement is for software meant to be executed on a general-purpose computer (a turing machine, which all modern servers, desktops, laptops, tablets, and mobile devices are), then you may understand why this is so.

Software used to direct a machine of this type is what defines the operation of the machine. The novel, patentable inventions in this case are the machine itself, and any improvements to it that cause it to work more efficiently, or additions to it (peripherals, etc) that allow it to produce *new* *physical* effects.

Software instructs the machine to manipulate data, and manipulating data is the domain of mathematics. If I am given a binary-encoded value (or set of such values) as an input, and turn that data into a different set as output, the transformation can *always* be described as a mathematical formula.

In some cases, multiple formulae must work together and on multiple sets of data (a formula acting as a "driver" to retrieve bits from a set of data that defines a construct embodying a "file" contained within another construct embodying a "folder", etc, etc.), but it is all math. If it wasn't, and if such math wasn't well understood, software development for modern day general purpose computers would not be possible.

The physical components of a general-purpose computer can cause physical effects (the recording of information encoded as magnetic patterns on a metallic disk platter, the illumination of phosphors on a cathode ray tube, or the alignment of crystals placed in an array on an LCD screen being examples), but software only ever does the job of manipulating numbers.

I agree with Barry Kelly. The goal of this invention is to "prevent performance deterioration" on a specific class of machine. The software algorithm offered in the patent is a

configuration specificationfor that class of machine which accomplishes thatconcrete goalunder a specific set of circumstances.Indeed, software patents are tricky mechanisms for avoiding loss of wealth, for all of the reasons discussed here and elsewhere. Care must be taken to verify the existence and veracity of claims of impact to concrete objects such as machines and people.

Would you allow your blog entry "Patent 5,893,120 reduced to mathematical formulae" to be reposted to groklaw.net?

I completely disagree with you, and you show a complete failure to research what the law actually says. It is true that science (e.g., math) is not patentable. However, there is a difference between science and the application of science. NOVEL and NONOBVIOUS applications of science to achieve useful ends ARE patentable. Using your logic, mechanical inventions would not be patentable either because a mechanical device in its simplest form is just atoms, and atoms already exist in nature. Instead, the law looks at these mechanical inventions at a higher level of abstractness, and the same is true for software. It isn't the math that is patented, but the methods that may use math to accomplish some useful result. In Bilski, the Supreme Court merely muddied the waters and again empowered the judiciary by giving the decisionmaker free discretion to decide whatever it wants. In sum, Bilski was a "because I said so" decision. Any serious reliance on Bilski is misplaced. The Sp. Ct. punted and did not create new law.

"...It isn't the math that is patented, but the methods that may use math to accomplish some useful result..."

And there's the crux of this cognitive dissonance. The methods we're speaking of are software functions/subroutines/classes/modules/applications/etc. All of those labels encapsulate one or more easily-identifiable algorithms, in every case (as far as software written to run on a modern general purpose computer is concerned).

The methods *are* math. That's the point. The algorithm itself (the thing that says, given x, return y) is not patentable. It can be protected against plagiarism via copyright, but we begin to have trouble when we say "Hey, I patented x + y = z, but only when f > 7.632".

Earlier..."...It is true that science (e.g., math) is not patentable..."

So far, so good...

"...However, there is a difference between science and the application of science..."

Still with you...

"...NOVEL and NONOBVIOUS applications of science to achieve useful ends ARE patentable..."

No argument there, I don't think.

"...Using your logic, mechanical inventions would not be patentable either because a mechanical device in its simplest form is just atoms, and atoms already exist in nature..."

Didn't see anyone talk about that yet, but if the day comes when we have replicators, then manufacturing will become a software-based process, and that statement would be true. At present, that statement is not true, because no general-purpose machine for controlled manipulation of subatomic particles into human-scale objects exists.

"...Instead, the law looks at these mechanical inventions at a higher level of abstractness, and the same is true for software..."

Mechanical inventions are not special because of a higher degree of abstractness, they are special because they have a tangible effect on real things in the physical world.

Software does not have any effect on anything in the physical world because it exists as an abstraction.

I cannot touch software in the same way that I cannot touch a recipe, prose, or the family of patterns known as "plaid". I can identify all of those things, and they are meaningful, but they are not tangible...they have no effect in the physical world, and are not patentable.

I *can* touch a general purpose computer in the same way that I can touch a meat grinder, a printing press, or a loom. Those things *do* have an effect in the physical world and (prior art aside) may be patentable.

adrianstovall puts it very well. Thank you.

My only useful addition is to point out that recipes ARE patentable (surprise!)

To reiisi blog guy going on about factors unrelated to the invention being claimed.

Patents need to only describe the invention being claimed.

Get it?

Whether there are a lot of other factors or not, as long as they are orthogonal to the invention, they need not be mentioned in the patent.

Get it?

Should I point out that if you invent a novel transmission for cars, you don't need to describe the rest of the car, because the rest of the car is "well known in the art", and describing everything would tend to create, ahem, lots of redundant material that an examiner would have to unnecessarilly wade through.

Get it yet?

Should I point out that, near as I can tell, the method described in this patent can apply to any hashtable using chaining regardless of the hash function being used or the data being hashed. Or are you claiming that expiring records in RAM should

neverbe cleaned up? Should I further point out that a patent only needs to describe the claimed invention in sufficient detail for a person of ordinary skill (a code monkey, in this case) to implement it, and as related comments around the web show, even someone in the first semester of code monkey school can read this patent and implement it?Do you get it yet?

(I may have misunderstood this last part in the parentheses... but there's a lot of other material that will teach real engineers how to build real machines in the real world, and those are not the contribution made by this patent, and hence it does not need to describe them at all. As long as the method described by this patent can be applied to "ideal" machines or "real" machines by a code monkey, the rest of the details are irrelevant and, hence, abstracted away.)

@neroden and everybody hammering on the "software is abstract mathematics" argument: you seem to be under the misconception that only physical objects are patentable. Please look into "method" patents (which is what most software patents are): http://en.wikipedia.org/wiki/Method_(patent)

Relevant quote: "Thus, one might speak of a process for making soap or candles, or speak of a method for curing headaches comprising administering a therapeutically effective dosage of aspirin."

Note that they don't claim the actual product or things, but a

wayto produce or use them. Yes, even if they are performed by a human.Hence, as Kim said, recipes are patentable (depending on what the recipe is for).

I'm sorry, but anyone who argues that this algorithm is more than just abstract math is an idiot. It's just a very long piece of abstract math. It doesn't matter if you can apply the math to a real-world system. You can do the same with bit shifts, which are abstract math, and can be easily done in registers on a CPU. Patents themselves are flawed ideas anyways - you can't claim to own the rights to an idea or concept anyways. It's not a property, it's easily reproduced infinitely and modified in the blink of an eye by the vast parallel human intellect. For the same reason you can't claim intellectual property on music. It's just tripe and this is a just a very solid proof of one kind of illegitimacy in copyright/patent/etc. law.

Nice work. ;)

"Hence, as Kim said, recipes are patentable (depending on what the recipe is for)."

The difference is that practicing a recipe actually manipulates and transforms material substances, software ONLY manipulates numbers. Whereas a recipe might include a step such as "boil sweetened solution for two minutes", 'software' merely states things such as "move 7 to 11".

And even a step such as "move 7 to 11" is presuming too much; the concept of "move" is itself just a number that when encountered in a context results in a fixed sequence of additions and multiplications -- all of which is "math".

A recipe is essentially a sequence of instructions. Read the quoted example of the Aspirin dosage. Yes, a doctor simply telling a patient to "take two and call me in the morning" is a patentable method. The patient does not even have to be performing those instructions for it to be patentable.

So now how does that extend to software? You do the math (pun intended ;-)).

"Didn't see anyone talk about that yet, but if the day comes when we have replicators, then manufacturing will become a software-based process, and that statement would be true. At present, that statement is not true, because no general-purpose machine for controlled manipulation of subatomic particles into human-scale objects exists."

I'm sorry. I think you missed the point of my analogy. Your post reduced the method in Google's patent to just math. I get that. My point is that any mechanical invention can be reduced to just atoms, too. But, nobody goes around and says that mechanical devices shouldn't be patentable because that would be the same as trying to patent an atom. The analogy extends to copyrights as well. A book can be reduced to a collection of words. If you say that patentability is determined based on what something is comprised of, then nothing would be patentable or copyrightable. Intellectual property allows authors and inventors to patent or copyright the novel/original arrangements of algorithms, of atoms, and of words. I'm an electrical engineer. I understand computers from both a hardware and software perspective. So, it isn't that I don't understand that algorithms include math. It is just that I think inventors can add value by the methods they create that include math that they put together to accomplish new and useful results.

"I cannot touch software in the same way that I cannot touch a recipe, prose, or the family of patterns known as "plaid". I can identify all of those things, and they are meaningful, but they are not tangible...they have no effect in the physical world, and are not patentable.

I *can* touch a general purpose computer in the same way that I can touch a meat grinder, a printing press, or a loom. Those things *do* have an effect in the physical world and (prior art aside) may be patentable."

Whether you can touch something doesn't seem like a great way to determine whether something should be protected by intellectual property. If you spent a lot of time and effort creating something (regardless of its tangibility), you not would want others to just come in and copy you and freeload off all your effort. Think about R&D for drugs. Why would those companies spend billions of dollars to make drugs that could be later copied easily by generics if patents did not exist? If you wrote a book, would you want Random House and all those other publishers to swoop in and reprint your book and make a ton of money from it without compensating you? Same goes for photographers. Clearly, there are tons of examples of "abstract" things that people are willing to pay money for. Intellectual property allows artists, inventors, authors, etc. to be compensated for the value they add to society. A patent is what allows an inventor to get funding from investors for a start-up company. If patents didn't exist, it would be much harder for the little guys to compete with the big companies.

"...The analogy extends to copyrights as well. A book can be reduced to a collection of words..."

Two things to note there. First, copyright is a very different protection. Copyright protects expression (creative work).

Second, while that collection of words can be copyrighted, a single word cannot.

"...If you say that patentability is determined based on what something is comprised of, then nothing would be patentable or copyrightable..."

I don't say that, specifically. Interestingly, patent law *does* in fact, say that, as does copyright law. They have to say that because if they did not, there would be no context for understanding whether a work could be protected by copyright or if an invention could be protected by patent law.

"...Intellectual property allows authors and inventors to patent or copyright the novel/original arrangements of algorithms, of atoms, and of words..."

That's absolutely correct. My argument is not that software should not be protected, but that patents are an inappropriate tool to cover a creative work, which is what software is. There is an element of engineering involved in the creation of software, but only insofar as a given piece of software is meant to manipulate data in a specific way.

People tend to associate software with computers and other hardware inventions, which is fine, but they must also understand that hardware and software are completely different things.

Software is useful, yes, and it helps us direct computers to do useful things, yes, but (and this is where the patentability argument comes in) patent law is meant to cover inventions, processes, and machines.

My earlier note about recipes was a good jumping-off point for an explanation of what is different about recipes and software, and there's a note about drugs and chemicals here, as well. If a recipe is a simple list of ingredients, with no instructions on how to combine them, then it is not, in fact, patentable.

In the same way, what is protected about drugs and chemicals is not the list of ingredients in the compound (though they may be protected as trade secrets), but the process of beginning with those physical ingredients, combining them in a specific process, and ending up with a compound that performs a useful function in the real world.

Software *never* does that last step of causing an effect in the real world. There is always hardware required to manifest some physical effect.

Countless hours of R & D may go into creating software or a user interface, but, again, that's a creative work, not an invention. I'm a programmer. I write software for a living. I understand how important intellectual property is and that software has value.

I also understand how software works, and what it is incapable of. There's no piece of software, no matter how cleverly written, that does more than turning numbers into other numbers.

"...A patent is what allows an inventor to get funding from investors for a start-up company. If patents didn't exist, it would be much harder for the little guys to compete with the big companies..."

A patent is one thing that makes investors feel more secure investing in a start-up company, yes. I do not argue that patents should not exist, I argue that patents are not an appropriate tool for protecting software.

In the world of software, patents are a terrible *hindrance* to the furthering of the arts, just as they would be in other more "formal" mathematics.

Continuing to allow software development to be understood as "invention", rather than publishing forces us into a position where, at some point, no software, regardless of how trivial, will be able to be developed without a legitimate fear of infringing on a patent.

With copyright (which already protects all software that is published) in place, your work is protected from copying as well as books have been for centuries.

Sorry for the deletion...had to fix a broken link...

"...Algorithms are generally applications of mathematics, not theorems, and therefore are patentable subject matter. You can patent a sorting algorithm but you can't patent the concept of sorting (for which there are infinite algorithms)..."

Where did you hear that?

In Gottschalk v. Benson, the court "...emphasized that its decision did not preclude computer software from being patented, but rather precluded the patentability of software where the only useful characteristic was an algorithm...".

Which just means that the court understood software poorly enough that it did not realize that its note about the decision not precluding patentability was incorrect.

Whenever I think about whether software should be patentable, I always think of the spreadsheet program. Whoever invented that program back in the day deserved a patent because it truly is an amazing tool. The fact that the function is provided by a computer is irrelevant. Brilliant inventions deserve patent protection. As far as calculating inventions go, it makes no sense to say that an abacus could qualify as patentable subject matter because it is tangible but a spreadsheet program would not.

@Adrian

"My argument is not that software should not be protected, but that patents are an inappropriate tool to cover a creative work, which is what software is." Ok... this makes more sense than saying programs shouldn't be patentable b/c they are just math. At least we are in agreement that a program is a creative work (i.e., not just math). I can agree that patents aren't perfectly suited to protecting programs... for example... a 20 year term is way too long for protecting a computer program because the innovation is so fast.

"..Ok... this makes more sense than saying programs shouldn't be patentable b/c they are just math. At least we are in agreement that a program is a creative work (i.e., not just math). I can agree that patents aren't perfectly suited to protecting programs... for example... a 20 year term is way too long for protecting a computer program because the innovation is so fast."

Just to be clear, I agree that software is a creative work, which means that it should be protected by copyright, yes. I also most definitely also *do* mean that software is fundamentally mathematics, which is why it should not *also* be afforded patent protection.

You mentioned the spreadsheet as an example of software that should have received patent protection, and that's a perfect example to use as an explanation of why software patents are not just inappropriate, but harmful.

For reference: http://en.wikipedia.org/wiki/Spreadsheet

VisiCalc (the first commonly-used commercial spreadsheet program) is probably what you're thinking of when you say "spreadsheet".

It was published in 1979, and, had patent protection been an accepted protection for software at that time, there would have been no competing spreadsheet software until 1999 (assuming the US Railway Association, Capex Corp and Rene K. Pardo and Remy Landau had not already sued them into submission with their own patents).

The first 9 versions of Microsoft Excel were released in that timeframe, as was every version of Lotus 1-2-3. Every version of Quattro Pro (when it was still a Borland product) was published in that timeframe.

The difference that competition and alternative implementations make in software products is enormous.

If VisiCalc or its predecessors had obtained an enforceable patent on the idea of an automatically calculating spreadsheet program, every software developer trying to do calculations on arrays would have been effectively hamstrung. That would have severely limited advancements in software application development.

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.

Please correct me if I'm wrong, but the patent system is to help out smaller players in protecting their inventions. Patents help distribute wealth among more people, right?

So now we have a situation where patents and the Patent Office seem to be working to keep wealth concentrated among fewer people.

So is the system of patenting broken, or is it the execution of the mandates of the Patent Office that is screwed up?

@Elijah Gregory

"Please correct me if I'm wrong, but the patent system is to help out smaller players in protecting their inventions. Patents help distribute wealth among more people, right?

So now we have a situation where patents and the Patent Office seem to be working to keep wealth concentrated among fewer people.

So is the system of patenting broken, or is it the execution of the mandates of the Patent Office that is screwed up?"

Not exactly, but sort of. The patent system in the US is meant to protect inventors, period. Early in the history of the USPTO, most inventors were individuals, and patent law helped them to protect their inventions from theft by predatory manufacturers.

If I come up with a novel method for heating water using electricity passed through a ceramic-coated piece of conductive wire, when wood stoves are the norm, and start building electric burners, I want to be able to either produce them myself, or get market price for my invention.

Patents don't distribute wealth, they enable newcomers in technology to enter the market with an idea and give them a limited amount of time to create products using it without fear of direct competition.

The patent system is a startup-enabler, if you will, or it was, at least. Today, established companies register more patents than individuals.

With actual inventions, the patent system still works fairly well. It is easy to find prior art, the operation of a machine or process can be understood, etc.

With software patents, we have a problem of comprehension (as evidenced by the discussion on this thread). I will admit that 10 years ago, I didn't understand why software should not be patentable, myself. The immediate tendency of people (myself included) seems to be to think of software as either a physical thing or to believe that it has a physical effect when used...neither of those thoughts is correct.

As a side effect of preventing innovation by software developers who do not have patents of their own to leverage, yes, software patents do tend to keep wealth concentrated in the hands of players with big patent portfolios.

Interestingly, many of the developers today who are working on software that is in danger due to lawsuits are working on software for which the code is open-source. So, even when there is no direct profit motive on the part of the software developer, there is a barrier to innovation being raised.

In short, the problem is worse than you think, and it's about control as much as it is about money

interesting post. i pulled the filing on this case. google is represented by Quinn Emanuel and Potter Minton. Here are some attorneys listed on the docket; google them for contact info. Do send along the post, I'm sure they'd appreciate it.

Cheryl A Berry

Andrew J Bramhall

Todd Michael Briggs

Evette D Pennypacker

Antonio Sistos

Michael E Jones (of Potter Minton PC)

Hey nerds, get it through your head:

The law is not executable, the law is interpreted by a human being.

In regard to this discussion, I have a couple of questions: whether a novel and useful algorithm implemented in software of a microcontroller (which controls a physical machine) is patentable? Almost every such apparatus is a finite automata that can be designed either in a form of a set of hardware devices (like flip-flops, registers, etc.) or as a corresponding microcontroller's program. Thus, whether such new algorithm is patentable?

MichaelK

You made some decent points there. I looked on the internet for the issue and found most individuals will go along with your website.

Thanks for sharing the great information. I really appreciate it.

are cavities genetic

Win a lottery

I always encourage the bloggers who share their knowledge with people. And you are one of them. Keep it up.

buy twitter followers

Post a Comment