Why Real Programmers Don't Take The USPTO Seriously: Doubly-Linked List Patented

from the oh-come-on dept

Tue, Mar 23rd 2010 2:52am — Mike Masnick

It's pretty difficult to find software engineers who take the patent system seriously. There are a few, but it's still pretty difficult. For the most part, they recognize that code is just a tool: you can make it do all sorts of things, given enough time and resources, but that doesn't mean that doing any particular thing in code is an "invention" that no one else should be able to do. And then, sometimes, they discover that something pretty basic and old has suddenly been given a patent. Brad Feld discusses his discovery that doubly linked lists were apparently patented in 2006 (patent number 7,028,023):

The prior art was extremely thin, only went back to 1995, and didn't mention that entire computer languages have been created around the list as a core data structure. One of my first Pascal programming exercises in high school (in 1981 -- on an Apple II using USDC Pascal) was to write a series of operations on lists, including both linked and doubly-linked lists (I always thought it was funny they were called "doubly-linked" instead of "double-linked" lists.) Anyone who ever graduated from MIT and took 6.001 learned to love all varieties of the linked list, including the doubly-linked one. That was 1984 for me by the way.

Ironically, Wikipedia had great entries -- with source code no less -- about both linked lists and doubly-linked lists. The linked list history goes back to 2001, well before the patent was filed.

Another day, another reason to question why software is patentable at all -- and to question who approves these kinds of patents.

Thank you for reading this Techdirt post. With so many things competing for everyone’s attention these days, we really appreciate you giving us your time. We work hard every day to put quality content out there for our community.

Techdirt is one of the few remaining truly independent media outlets. We do not have a giant corporation behind us, and we rely heavily on our community to support us, in an age when advertisers are increasingly uninterested in sponsoring small, independent sites — especially a site like ours that is unwilling to pull punches in its reporting and analysis.

While other websites have resorted to paywalls, registration requirements, and increasingly annoying/intrusive advertising, we have always kept Techdirt open and available to anyone. But in order to continue doing so, we need your support. We offer a variety of ways for our readers to support us, from direct donations to special subscriptions and cool merchandise — and every little bit helps. Thank you.

–The Techdirt Team

Filed Under: doubly-linked lists, patents, prior art, uspto

116 Comments

If you liked this post, you may also be interested in...

Reader Comments

Subscribe: RSS

View by: Time | Thread

Cheong, 23 Mar 2010 @ 3:16am

IT Court
Perheps we should have a court / patent department specially for technology related things...

The judge / officials should have satisfactory background in dealing with modern technologies. And if there are juries, briefing should be provided by specilists to explain what the case is about and what consequences it may have.

Hope that it'll make less non-sensible judgement of the kind.
[ link to this | view in chronology ]
- John Fenderson (profile), 23 Mar 2010 @ 6:46am
  
  Re: IT Court
  Or perhaps we should disallow software patents altogether. It seems to me that they fall squarely in the "mathematical processes" category and therefore should not be patentable.
  [ link to this | view in chronology ]
Anonymous Coward, 23 Mar 2010 @ 3:34am

You have GOT to be kidding me. It actually is a patent on doubly-linked lists. :P
[ link to this | view in chronology ]
Anonymous Coward, 23 Mar 2010 @ 3:54am

To get technical
A doubly-linked list is just one that you can traverse forward and backward. This patent is for a multiply-linked list which you can traverse in any pre-defined order. The douby-linked list is one type of a multiply linked list. Nevertheless the patent is still stupid. Multiply-linked lists have been around longer than I have.
[ link to this | view in chronology ]
- abc gum, 23 Mar 2010 @ 4:53am
  
  Re: To get technical
  Is there also a divide-linked list ?
  I prefer the logarithmic-linked list.
  [ link to this | view in chronology ]
  - Steven (profile), 23 Mar 2010 @ 7:30am
    
    Re: Re: To get technical
    Wouldn't a 'logarithmic-linked list' be a tree structure?
    [ link to this | view in chronology ]
    - Anonymous Coward, 25 Mar 2010 @ 8:58pm
      
      Re: Re: Re: To get technical
      I think that what was meant was a 'skip list', or some thing like it (see wikipedia for an explanation)
      [ link to this | view in chronology ]
- ethorad (profile), 23 Mar 2010 @ 5:11am
  
  Re: To get technical
  Dammit, after reading that doubly-linked lists were patented I was about to apply for a patent on triply-linked lists!
  [ link to this | view in chronology ]
- Spaceman Spiff (profile), 23 Mar 2010 @ 6:26am
  
  Re: To get technical
  The Art of Computer Programming, Vol. 3, Searching and Sorting by Donald Knuth, Copyright 1973. Sections 6.2.2-6.2.4 have numerous examples of multiple linked lists (binary & multiway trees) and discusses them in detail. In fact, he gets into the discussion of a degenerate binary tree being in effect a doubly-linked list...
  [ link to this | view in chronology ]
Mike C. (profile), 23 Mar 2010 @ 4:03am

Gee... thanks....
As a programmer, I now have to dislike you because I am now aware of the patent. I guess this means that my company division with 300+ programmers can no longer use doubly-linked lists in any of our code.... greeeaaaaat.

Can someone get the EFF on this... I've got an idea for an app I want to start working on in 10-15 years... :-)

/patent system is a joke
[ link to this | view in chronology ]
- greg.fenton (profile), 23 Mar 2010 @ 7:21am
  
  Re: Gee... thanks....
  You read about the existence of the patent on the internet. That doesn't prove anything. Unless you have physically seen the patent papers at a USPTO branch, there is no way for you to know that this patent exists.
  [ link to this | view in chronology ]
Glurbie, 23 Mar 2010 @ 4:38am

Crap!
I can't tell you how many programs I've written using this incredibly advanced technology. Do I have to go back and pay royalties now? Maybe instead I should go through my old Graph Theory textbook to see if I can get a few defensive patents of my own. No one has patented arranging a linked-list as a bipartite graph yet have they?
[ link to this | view in chronology ]
TriZz, 23 Mar 2010 @ 4:47am

This is crap
My business partner is a web developer by day and does some innovative stuff. He was researching once how to get Flash to do something...and he couldn't find anything. Posting on forums led him to a bunch of "you can't do that" responses.

So, he essentially made it happen. I wouldn't call it inventing...but it certainly hadn't been done before. Figured it out is probably a better term.

His response was to go into that same forum and post the code for everyone.

He did this, not to be a braggart, but rather to give back to the community. He wouldn't be the web developer that he is today if people hadn't helped him and freely shared code when he was first starting out. And this is his way of showing his appreciation. It could spark someone else to "figure out" how to do other innovative stuff, thus progressing the field.

If only we all thought like that...
[ link to this | view in chronology ]
- Anonymous Coward, 23 Mar 2010 @ 4:55am
  
  Re: This is crap
  And now someone is busy with a patent application
  [ link to this | view in chronology ]
abc gum, 23 Mar 2010 @ 4:58am

I've heard stories about how you can not patent the wheel because there is plenty of prior art. However, now I'm not so sure that it can not be done. And the title could even be "Wheel".
[ link to this | view in chronology ]
- Anonymous Coward, 23 Mar 2010 @ 8:16pm
  
  Re:
  Someone already has a patent on the wheel.
  
  http://www.newscientist.com/article/dn965-wheel-patented-in-australia.html
  [ link to this | view in chronology ]
Anonymous Coward, 23 Mar 2010 @ 5:14am

You should really fix the subject
As noted above (by another AC) this is a patent on multiply-linked lists, not doubly-linked lists. (It doesn't talk about any of the optimizations for doubly-linked lists.)

With many CS patents, the question appears to be more -- who's the first person to have a reason to do this? -- but in this case, unless it was purely an abuse of the PTO, it seems fair to guess that some young programmer independently realized that there are applications for which a multiply-linked list is an appropriate data structure.

Either way, it'd be an argument against patents for software.

The wiki version prior to submission of the patent (which was Sep 26, 2002) covers only a simple explanation of linked lists -- so the history for that document isn't prior art. OTOH, the current version links to the patent and notes the techniques were in use for decades before the patent was filed.
[ link to this | view in chronology ]
- SomeGuy (profile), 23 Mar 2010 @ 6:04am
  
  Re: You should really fix the subject
  "there are applications for which a multiply-linked list is an appropriate data structure."
  
  And this is non-obvious how?
  [ link to this | view in chronology ]
  - Anonymous Coward, 23 Mar 2010 @ 6:30am
    
    Re: Re: You should really fix the subject
    I didn't say it wasn't obvious -- just that I'd guess a young programmer (who hadn't been taught the data structure) encountered such a situation and was happy with this after they came up with it as a solution.
    
    Though personally, I haven't had any applications where a multiply linked list seemed appropriate -- there are other ways to store multiple paths through a list; and maintaining a multiply-linked list (additions, deletions, etc) can be expensive, depending on various factors.
    [ link to this | view in chronology ]
Anonymous Coward, 23 Mar 2010 @ 5:15am

Im patenting unitary linked lists.
[ link to this | view in chronology ]
angry dude, 23 Mar 2010 @ 5:34am

SOFTWARE = HARDWARE
yes, punks

write it on your little brainless foreheads, lemmings

it is impossible, legally or otherwise, to separate software from hardware implementation - they are two sides of the same coin

It's just a lot easier to change "sofware" running on e.g. general-purpose CPU as opposed to changing e.g. ASIC design

BTW, what you call "software patents" date back to those old times when computers didnt exist ...

How abot that, little idiots ?
[ link to this | view in chronology ]
- Anonymous Coward, 23 Mar 2010 @ 5:59am
  
  Re: SOFTWARE = HARDWARE
  Got anything of real substance to post or did you just feel like hurling insults? Going by your username I'm going with the "you're a troll" option.
  [ link to this | view in chronology ]
  - angry dude, 23 Mar 2010 @ 6:07am
    
    Re: Re: SOFTWARE = HARDWARE
    A patent troll, that's right
    
    with one patent, dozen pubs as well as 2 MS degrees and a PhD
    
    Now shut up
    
    Gosh, how I hate this f@#$%^& blog
    [ link to this | view in chronology ]
    - greg.fenton (profile), 23 Mar 2010 @ 7:23am
      
      Re: Re: Re: SOFTWARE = HARDWARE
      Welcome back. Go away.
      [ link to this | view in chronology ]
    - Anonymous Coward, 23 Mar 2010 @ 8:29am
      
      Re: Re: Re: SOFTWARE = HARDWARE
      Oh, your imaginary patent and the degrees from clown school?
      [ link to this | view in chronology ]
      - ChurchHatesTucker (profile), 23 Mar 2010 @ 9:00am
        
        Re: Re: Re: Re: SOFTWARE = HARDWARE
        "Oh, your imaginary patent and the degrees from clown school?"
        
        Since they're handing out patents like Little League trophies, I don't doubt he has one. Clown School, however, has higher standards of comedy than that.
        [ link to this | view in chronology ]
        
        angry dude, 23 Mar 2010 @ 9:41am
        
        Re: Re: Re: Re: Re: SOFTWARE = HARDWARE
        Clown School ?
        
        Ha... I guess you can call it clown school
        
        http://en.wikipedia.org/wiki/Moscow_Institute_of_Physics_and_Technology
        
        I still remember some pretty crazy things going on in the student dorm back then
        
        Esp on April 1, we had a huge all campus all night discoteque followed by some wild wild stuff...
        
        After that it was all downhill, fun-wise
        
        Get ready for Fools' Day, punks !
        [ link to this | view in chronology ]
        
        ChurchHatesTucker (profile), 26 Mar 2010 @ 8:43pm
        
        Re: Re: Re: Re: Re: Re: SOFTWARE = HARDWARE
        Yeah, you still haven't risen to the level of clown school grads. So, don't get too comfortable there.
        [ link to this | view in chronology ]
    - Ronald J Riley (profile), 23 Mar 2010 @ 9:58am
      
      Re: Re: Re: SOFTWARE = HARDWARE
      "Gosh, how I hate this f@#$%^& blog"
      
      You should pity them.
      
      This is where all the programming drones hang out. The kind who day after day crank out repetitive unimaginative code. Because they are not capable of an original thought they think that they should be free to copy those who are. That is all they know, copy and copy some more. Think how unimaginative they are.
      
      The problem is that 99% of the programming community is like this. They are equivalent to the poor slob who stood between a pallet of parts on a production line and loaded those parts on a conveyor all day long, day after day, week after week for 20-30 years.
      
      Ronald J. Riley,
      
      I am speaking only on my own behalf.
      Affiliations:
      President - www.PIAUSA.org - RJR at PIAUSA.org
      Executive Director - www.InventorEd.org - RJR at InvEd.org
      Senior Fellow - www.PatentPolicy.org
      President - Alliance for American Innovation
      Caretaker of Intellectual Property Creators on behalf of deceased founder Paul Heckel
      Washington, DC
      Direct (810) 597-0194 / (202) 318-1595 - 9 am to 8 pm EST.
      [ link to this | view in chronology ]
      - Anonymous Coward, 23 Mar 2010 @ 1:44pm
        
        Re: Re: Re: Re: SOFTWARE = HARDWARE
        Hi, RJR, how is your hypocrisy doing?
        [ link to this | view in chronology ]
      - BearGriz72 (profile), 23 Mar 2010 @ 3:05pm
        
        Re: Re: Re: Re: SOFTWARE = HARDWARE
        Re: RJR � My Thoughts
        If You Want More Information
        
        Please DNFTT
        [ link to this | view in chronology ]
- Anonymous Coward, 23 Mar 2010 @ 6:18am
  
  Re: SOFTWARE = HARDWARE
  So it's okay to patent things taught in schools?
  
  brb patenting calculus.
  [ link to this | view in chronology ]
  - Andrew F (profile), 23 Mar 2010 @ 9:35am
    
    Re: Re: SOFTWARE = HARDWARE
    Newton: Hurrah, I've invited Calculus!
    Leibniz: But ... so have I!
    Newton: ...
    Leibniz: ...
    Newton: Look, an elegant solution to the 3-body problem!
    Leibniz: What? Where?
    Newton scurries off to the patent office.
    [ link to this | view in chronology ]
- jason, 23 Mar 2010 @ 7:19am
  
  Re: SOFTWARE = HARDWARE
  Bullshit. Software does not equal Hardware.
  
  Within logic and set theory you can prove the concept of a general purpose machine to do computations. That is the basis for the computer. The set of all possible computer programs is the set of all programming statements that can be put together to form them. This is why they're called computer LANGUAGES. Writing programs becomes then more like writing a book than inventing. And books (and software) are COPYRIGHTED (or copylefted ;-) but are not inventions that are patentable.
  
  This should be clear to any honest computer scientist. The hardware can be patentable because it is a literal tangible thing, but as many hardware companies have found out (hello IBM) patenting your bus and other internal constructs make your machine design less desirable and loses you market share. Thats not to say that things like chip fabrication procedures shouldn't be patentable, but even then that kind of thing is probably better off as a trade secret.
  
  At the end of the day, if push came to shove, I could maybe be convinced that an entire computer language might be patentable, as it creates the context from which all programs written in it will come into being. But then, how many people would learn and use a computer language that enforced ownership over every program you would ever create.
  
  Software patents are bad, horrendously bad.
  [ link to this | view in chronology ]
  - Ronald J Riley (profile), 23 Mar 2010 @ 10:02am
    
    Re: Re: SOFTWARE = HARDWARE
    "Bullshit. Software does not equal Hardware."
    
    Yes it does. You just are not knowledgeable enough to understand it.
    
    Ronald J. Riley,
    
    I am speaking only on my own behalf.
    Affiliations:
    President - www.PIAUSA.org - RJR at PIAUSA.org
    Executive Director - www.InventorEd.org - RJR at InvEd.org
    Senior Fellow - www.PatentPolicy.org
    President - Alliance for American Innovation
    Caretaker of Intellectual Property Creators on behalf of deceased founder Paul Heckel
    Washington, DC
    Direct (810) 597-0194 / (202) 318-1595 - 9 am to 8 pm EST.
    [ link to this | view in chronology ]
    - Steven (profile), 23 Mar 2010 @ 11:09am
      
      Re: Re: Re: SOFTWARE = HARDWARE
      I find it interesting that your only argument in all of the 'software = hardware' threads amount to, 'everybody here is too stupid to understand'. I also find it amusing that you have replied to each response in this thread but mine.
      
      You seem to have no valid arguments and serve only to fling insults. Once again I understand that I am just feeding a troll.
      [ link to this | view in chronology ]
      - Anonymous Coward, 23 Mar 2010 @ 1:45pm
        
        Re: Re: Re: Re: SOFTWARE = HARDWARE
        Troll Radar (Patented) = If the signature has more content than the post, the poster is a troll. Also be on the lookout for the inclusion of dead people in a signature claiming the poster speaks only for himself.
        [ link to this | view in chronology ]
    - Anonymous Coward, 23 Mar 2010 @ 10:02pm
      
      Re: Re: Re: SOFTWARE = HARDWARE
      No it is not. See, I can do it too!
      
      I am speaking only on my own behalf.
      Affiliations:
      Organization 1
      Organization 2
      Organization 3
      Committee 1
      Some Dead Guy
      God
      The Entire United States
      Martians
      Bacteria
      [ link to this | view in chronology ]
- Steven (profile), 23 Mar 2010 @ 7:44am
  
  Re: SOFTWARE = HARDWARE
  Would it be possible to turn any software into hardware? Yes. Does that mean software should be patentable? No.
  
  Why? Because the reverse is not true. Not all hardware can be done in software. If it CAN be done in software, it should not be eligible for patent protection. If it requires specific hardware then that hardware could be considered eligible for a patent if it meets patent requirements.
  
  Although I personally think patents are a drain on our society.
  
  My personal solution. Make patents and copyright last one year. Wait two years. If we can say that sufficient innovation/creation is not happening increase the appropriate term by one year (wait two years, rinse, repeat). If extending by a year has no effect, or a negative effect, reduce by two years.
  [ link to this | view in chronology ]
  - angry dude, 23 Mar 2010 @ 7:50am
    
    Re: Re: SOFTWARE = HARDWARE
    F@#$ your GF once a week - wait a month -not pregnant yet ?
    rinse, repeat
    then F@## her every 2 weeks, rince repaet
    then cut off you balls
    
    Seriosly dude you are a f@@#%^^ moron without a clue
    [ link to this | view in chronology ]
    - Steven (profile), 23 Mar 2010 @ 7:55am
      
      Re: Re: Re: SOFTWARE = HARDWARE
      That's a very crude but basically accurate description of what I've done. Two boys and now I'm 'fixed'. Although she was my wife.
      
      :)
      [ link to this | view in chronology ]
      - angry dude, 23 Mar 2010 @ 7:59am
        
        Re: Re: Re: Re: SOFTWARE = HARDWARE
        By "fixed" you mean you don't have your balls anymore ?
        
        It shows in your thinking process
        [ link to this | view in chronology ]
        
        Steven (profile), 23 Mar 2010 @ 8:18am
        
        Re: Re: Re: Re: Re: SOFTWARE = HARDWARE
        Oh I still have them. But they are not longer attached in a way that allows me to further procreate.
        [ link to this | view in chronology ]
  - Anonymous Coward, 25 Mar 2010 @ 9:10pm
    
    Re: Re: SOFTWARE = HARDWARE
    err, you can certainly emulate any digital computer system in software, some things are just hard... That doesn't really change the fact that BOTH things are mathematical constructs...
    
    Hardware is different in that although at a high level it is equivalent to software how you deal with the real world means you can make it faster/better somehow, like if you figured out how to make logic gates that switch 10x faster you could patent that. But the logic could stay the same and just be faster... the LOGIC is the part of hardware that is like software but hardware design is a lot more than just the logic.
    [ link to this | view in chronology ]
- Anonymous Coward, 23 Mar 2010 @ 10:13am
  
  Re: SOFTWARE = HARDWARE
  Software is not hardware. Everything done in software can be done with a pencil, paper, and a whole lack of social life. This is to say that without hardware doing quite a number of tasks is computationally infeasible (and impractical) but can be done. Honestly, the entire basis of Computer Science rests on this fact. Saying otherwise is being intellectually dishonest.
  [ link to this | view in chronology ]
  - Ronald J Riley (profile), 23 Mar 2010 @ 10:16am
    
    Re: Re: SOFTWARE = HARDWARE
    If you had a broader background you would understand that hardware and software solutions are traded off all the time. As computing power has increased the scope of software in lieu of hardware solutions have also increased.
    
    Ronald J. Riley,
    
    I am speaking only on my own behalf.
    Affiliations:
    President - www.PIAUSA.org - RJR at PIAUSA.org
    Executive Director - www.InventorEd.org - RJR at InvEd.org
    Senior Fellow - www.PatentPolicy.org
    President - Alliance for American Innovation
    Caretaker of Intellectual Property Creators on behalf of deceased founder Paul Heckel
    Washington, DC
    Direct (810) 597-0194 / (202) 318-1595 - 9 am to 8 pm EST.
    [ link to this | view in chronology ]
    - Anonymous Coward, 23 Mar 2010 @ 12:03pm
      
      Re: Re: Re: SOFTWARE = HARDWARE
      I do have a broad background, and I do understand that hardware and software solutions are traded off all the time. However, that doesn't mean that that software is hardware.
      
      For example the algorithm for AES (Advanced Encryption Standard) can be done in software or hardware. Further that same algorithm has been done in pencil and paper. It's mathematics.
      [ link to this | view in chronology ]
      - Steven (profile), 23 Mar 2010 @ 12:09pm
        
        Re: Re: Re: Re: SOFTWARE = HARDWARE
        It's also been done in a comic:
        
        http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html
        [ link to this | view in chronology ]
    - Anonymous Coward, 25 Mar 2010 @ 9:11pm
      
      Re: Re: Re: SOFTWARE = HARDWARE
      How does this change the mathematical nature of software?
      [ link to this | view in chronology ]
- Lawrence D'Oliveiro, 23 Mar 2010 @ 2:38pm
  
  Re: SOFTWARE = HARDWARE
  angry dude sputtered:
  
  it is impossible, legally or otherwise, to separate software from hardware implementation - they are two sides of the same coin
  
  If that’s true, then does that mean, if software can be patented like hardware, then hardware can be copyrighted like software, too?
  
  If they’re the same thing, then why do they need two kinds of legal protection, both patent and copyright? Surely one is enough?
  [ link to this | view in chronology ]
  - angry dude, 24 Mar 2010 @ 7:04am
    
    Re: Re: SOFTWARE = HARDWARE
    "If that’s true, then does that mean, if software can be patented like hardware, then hardware can be copyrighted like software, too?"
    
    Absolutely YES
    
    Hardware designs can be protected by copyright-like rights
    
    (e.g. semiconductor chip layouts etc)
    
    http://en.wikipedia.org/wiki/Mask_work
    
    you didn't know it, punky ?
    [ link to this | view in chronology ]
- Anonymous Coward, 25 Mar 2010 @ 9:02pm
  
  Re: SOFTWARE = HARDWARE
  and in computer systems both are math, so how does this change the discussion?
  [ link to this | view in chronology ]
WammerJammer (profile), 23 Mar 2010 @ 5:40am

No more freedom
Just about everything you code anymore, if it is a procedure, has been patented by someone. That patent also probably relies on 20 other patents to be legal. It's turning into a bunch of bull.
[ link to this | view in chronology ]
- Anonymous Coward, 23 Mar 2010 @ 8:27pm
  
  Re: No more freedom
  "That patent also probably relies on 20 other patents to be legal."
  
  It's called dependencies, except instead of software dependencies, we have created legal dependencies.
  [ link to this | view in chronology ]
MRK, 23 Mar 2010 @ 6:34am

The problem is not patents for Software, the problem is the USPTO routinely fails to check for obviousness and searching for prior art when it comes to software.

Software patents that are overly broad should never be granted, and the sad fact is the USPTO office has been granting overly broad, vague patents in all disciplines for far too long.

If someone were to write an specific algorithm that solves a particular problem, that exact algorithm is patentable. But only that algorithm. If someone can come up with another means of solving that problem it should not violate the patent.

The argument that "All software is math, and you cannot patent math" does not apply. Simply because all sciences can be broken down into mathematical formula if you go far enough. For example Chemistry is really just applied physics and thus mathematics, but no one would seriously argue that the Pharma companies should not be able to patent their latest drugs.

If one wanted to make the argument to get rid of all patents, that perhaps society no longer needs them, I could agree with that. But there is no reason to exclude software over other types of patents simply because the USPTO isn't doing its job properly. The problem is with how USPTO grants patents (read: far too loosely). Not software patents specifically.
[ link to this | view in chronology ]
- Anonymous Coward, 23 Mar 2010 @ 6:57am
  
  Re: @MRK
  Could you then point out some good software patents which are examples of why we shouldn't abolish software patents? As in -- a patent which leads to useful advances.
  
  Generally the companies doing interesting software choose to handle inventions as trade secrets.
  
  Software patents are an unmitigated disaster: no one in the software industry uses them to find better solutions, they're just used as a tool for litigation.
  
  I'm not convinced that better management at the USPTO would improve matters -- you'd need to reach the point where it was often faster and better to look for a patent than to solve the problem from first principles. (Assuming the goal of patents is to advance the useful arts and sciences, rather than benefiting established companies at the expense of new ones.) And given that patents don't generally explain the problems for which they are inappropriate, you'd often wind up with a suboptimal solution (not that that's different from the status quo).
  
  Copyright for existing solutions (software libraries) is a different matter -- there's a lot of benefit in not having every company re-implement the same algorithms with their own new bugs -- but software patents aren't software, just a blueprint which would need to be filled in anyway.
  [ link to this | view in chronology ]
  - MRK, 23 Mar 2010 @ 7:28am
    
    Re: Re: @MRK
    Compression algorithms, and the Fast inverse square root come to mind what would be "Good" software patents. Google/Wikipedia either of those turns up interesting finds. I simply don't have the time to dig through the USPTO archives to find specific examples.
    
    I'm not saying Software Patents have not been a total disaster. I simply assert that the problem lies in how the courts have allowed Patent Trolling to run amok. And the USPTO granting obviously stupid patents.
    
    The system needs reform. But I think tossing software patents out would be throwing the baby out with the bath water.
    [ link to this | view in chronology ]
    - angry dude, 23 Mar 2010 @ 7:44am
      
      Re: Re: Re: @MRK
      RSA patent or Karmarkar patent are the classical examples of good "software" patents (promoting progress A LOT)
      
      Mind you, RSA patent was framed as hardware patent - you can build a specialized chip for doing this
      
      same with speech compression patents used for cell phones
      
      Build a custom ASIC and voila - you have a piece of harware
      [ link to this | view in chronology ]
      - Lawrence D'Oliveiro, 23 Mar 2010 @ 2:47pm
        
        Re: RSA Patent
        angry dude sputtered:
        
        RSA patent or Karmarkar patent are the classical examples of good "software" patents (promoting progress A LOT)
        
        Actually, the patent itself promoted no progress at all. The most popular applications of RSA were in Free Software on the Internet (PGP, OpenSSL etc), where royalty deals don’t work.
        
        RSA even released the patent into the public domain earlier than they had to. If the patent really was “promoting the progress”, they would have hung onto it for the full duration. After all, more duration, more progress, right?
        [ link to this | view in chronology ]
      - Anonymous Coward, 25 Mar 2010 @ 9:18pm
        
        Re: Re: Re: Re: @MRK
        and speex or CELT out perform the codecs used in phones in quality/bandwidth with absolutely NO patent motivation needed (actually patents are sort of indirectly the motivation, they are explicitly being created with the goal of being patent free...)
        [ link to this | view in chronology ]
    - Ben (profile), 23 Mar 2010 @ 8:38am
      
      Tossing patents
      Perhaps you already have seen this, but if not:
      
      http://levine.sscnet.ucla.edu/general/intellectual/againstfinal.htm
      
      I've recently started reading it, and it's been enlightening so far.
      [ link to this | view in chronology ]
    - greg.fenton (profile), 23 Mar 2010 @ 10:14am
      
      Re: Re: Re: @MRK
      Why on earth do you think that mathematical formulas "good patents"? Seriously?
      Where do you draw the line between a "hard" algorithm vs. other hard problems such as application scalability?
      Yesterday's compression algorithm was "tough" yesterday and extremely trivial today. Did Huffman encoding deserve a patent?
      If someone ever solves an NP-Complete problem, do you feel they will deserve a patent on the solution? Written up the right way, that patent would block/tax anyone solving all other NP-Complete problems.
      [ link to this | view in chronology ]
      - angry dude, 23 Mar 2010 @ 11:40am
        
        Re: Re: Re: Re: @MRK
        "Did Huffman encoding deserve a patent? "
        
        You are joking, right ?
        
        Of course it did
        
        As well as LZW compression, LPC or CELP coding for speech, MPEG encoding for audio etc.
        
        Those are kinds of "software" patents that promote progress and improve quality of life, including your life, little retarded fella
        [ link to this | view in chronology ]
        
        greg.fenton (profile), 23 Mar 2010 @ 12:28pm
        
        Re: Re: Re: Re: Re: @MRK
        No, I am not joking. Why on earth does Huffman deserve a patent?
        [ link to this | view in chronology ]
        
        Anonymous Coward, 23 Mar 2010 @ 8:34pm
        
        Re: Re: Re: Re: Re: @MRK
        Saying that an algorithm, piece of code or software, or mathematical formula promotes the progress and improves quality of life is far different than saying that a patent on such a thing promotes the progress and improves the quality of life. A patent on such things harms the progress and reduces the quality of life being that monopolies harm the economy and give the monopoly holder less incentive to innovate and prevents everyone else from innovating on said invention.
        [ link to this | view in chronology ]
        
        angry dude, 24 Mar 2010 @ 7:10am
        
        Re: Re: Re: Re: Re: Re: @MRK
        Except for the fact that without patent protection available in the first place those things would never be invented or at least publicly disclosed
        
        Elementary Logic 101
        
        Back to school, little punk
        [ link to this | view in chronology ]
        
        Anonymous Coward, 24 Mar 2010 @ 2:26pm
        
        Re: Re: Re: Re: Re: Re: Re: @MRK
        Except that...almost the entire basis of current mathematical knowledge was never patented and was still "invented" or "publicly disclosed."
        
        Elementary History 001
        
        Back to bridge, little troll.
        [ link to this | view in chronology ]
        
        Anonymous Coward, 25 Mar 2010 @ 9:30pm
        
        Re: Re: Re: Re: Re: Re: Re: @MRK
        Er, did you miss the bit where Huffman coding was NEVER patented? And some of the most important stuff in CS doesn't even involve stuff you could patent even under the current patent system (because it's a proof and not an algorithm).
        
        Go look, most of the most important algorithms ever invented were never patented, so please explain why the people who created them need a patent motivation.
        
        Huffman coding is still one of the most widely used compression algorithms, it is a part of a very large number of video and audio codecs, and all sorts of other stuff, then there's LZMA, and bz2 both of which were based on things that were never patented (AND they are open source so not only is there a good description of the algorithm out there, the actual implementation is disclosed).
        
        Alan Turning and Alonzo Church didn't need patents to write some of the most important, foundational, papers in computer science. Claude Shannon didn't patent anything when he basically created information theory (on which all compression is based at some level)
        [ link to this | view in chronology ]
      - Anonymous Coward, 25 Mar 2010 @ 9:21pm
        
        Re: Re: Re: Re: @MRK
        err, we DO know algorithms for NP complete problems, it's just that they tend to take an awfully long time to run... and there's a million dollar prize if you come up with polytime algorithm for one of the problems (Most computer science people have serious doubts that such an algorithm exists, you get the prize for proving it doesn't too)
        [ link to this | view in chronology ]
  - Ronald J Riley (profile), 23 Mar 2010 @ 10:07am
    
    Re: Re: @MRK
    "Generally the companies doing interesting software choose to handle inventions as trade secrets."
    
    Which means that they do not advance the art by teaching. It also means that when someone does come along and teach with a patent that the idiot who used trade secret is toast, rightfully so.
    
    Ronald J. Riley,
    
    I am speaking only on my own behalf.
    Affiliations:
    President - www.PIAUSA.org - RJR at PIAUSA.org
    Executive Director - www.InventorEd.org - RJR at InvEd.org
    Senior Fellow - www.PatentPolicy.org
    President - Alliance for American Innovation
    Caretaker of Intellectual Property Creators on behalf of deceased founder Paul Heckel
    Washington, DC
    Direct (810) 597-0194 / (202) 318-1595 - 9 am to 8 pm EST.
    [ link to this | view in chronology ]
    - Steven (profile), 23 Mar 2010 @ 10:40am
      
      Re: Re: Re: @MRK
      I know I'm just feeding a troll, but...
      
      I challenge you to find a single 'real' programmer who was ever taught via patents.
      
      "It also means that when someone does come along and teach with a patent that the idiot who used trade secret is toast"
      
      Hmm... Is that because the one that has the patent will now sue the one that did the original innovation? Wow, that sure sounds fair, right, and just. (should I put a sarc mark here?)
      [ link to this | view in chronology ]
      - greg.fenton (profile), 23 Mar 2010 @ 12:34pm
        
        Re: Re: Re: Re: @MRK
        Hmm... Is that because the one that has the patent will now sue the one that did the original innovation?
        
        Of course, it's even worse than that when it comes to software. For the most part, the software patents we're seeing being rewarded aren't due to their genius, but merely for the fact that the applicant was the first to the USPTO.
        Software is still a young enough field that just about every few days a new branch opens. Patents will (does) massively stiffle innovation in these fields.
        Real programmers know this.
        Not sure why RJR is even commenting on software patents. By his own philosophy he should not since he doesn't have any software patents (and he isn't a real programmer).
        [ link to this | view in chronology ]
    - Anonymous Coward, 23 Mar 2010 @ 1:46pm
      
      Re: Re: Re: @MRK
      Yeah, I know all my textbooks are actually just teaching code from patents that are files 25+ years into the future, by MAGIC!
      [ link to this | view in chronology ]
    - Anonymous Coward, 23 Mar 2010 @ 8:35pm
      
      Re: Re: Re: @MRK
      "Which means that they do not advance the art by teaching. It also means that when someone does come along and teach with a patent that the idiot who used trade secret is toast, rightfully so."
      
      Except we have patents in place and trade secrets still exist. Microsoft has many patents yet their software is still closed source. There is little to no evidence that patents have eliminated or reduced the use of trade secrets.
      [ link to this | view in chronology ]
- McBeese, 23 Mar 2010 @ 7:22am
  
  Re:
  @MRK. Disagree. I think there are at least three problems: 1) The USPTO is incompetent in the execution of their mandate, 2) software structure should not be patentable, any more than a paragraph structure or an exclamation point within a work of text is patentable, and 3) too many supposed 'software programmers' only work with the highest and most simple languages and tools, so concepts like linked lists, recursion, etc., are new and foreign to them.
  [ link to this | view in chronology ]
  - MRK, 23 Mar 2010 @ 7:49am
    
    Re: Re:
    Err. My post does not conflict with any of your three points. I clearly stated the USPTO has dropped the ball on this one. I never said software structure should be patentable. And while you can blame poor education of the current crop of computer programmers, its still the USPTO office's job to separate out the good from the bad, which they clearly have failed at.
    
    So we are in agreement!
    [ link to this | view in chronology ]
    - McBeese, 23 Mar 2010 @ 8:34am
      
      Re: Re: Re:
      Oh, ok. I thought you were saying that the USPTO was doing a bad job but s/w patents were ok. My mistake.
      
      Yes, I think we agree then.
      [ link to this | view in chronology ]
Anonymous Coward, 23 Mar 2010 @ 6:39am

software should not be patentable
or copyrightable either but that's another argument completely
[ link to this | view in chronology ]
- JEDIDIAH, 23 Mar 2010 @ 6:46am
  
  Patent trolls are the real theives
  Much too much of this stuff falls under the catgory of:
  
  Give me a description of the device and I will have an undergraduate computer science class create an implementation for you. It really is a case of someone else stealing from me the product of my own intellect.
  
  I can stumble upon an entire idea and implement it on my own without realizing someone else has already done it already (patented or not). This is very common in software. It's not terribly burdensome either. It's certainly a lesser burden than being in a minefield of patent trolls.
  [ link to this | view in chronology ]
  - Anonymous Coward, 23 Mar 2010 @ 6:55am
    
    Re: Patent trolls are the real theives
    I'd like to patent the idea of a a bullet to the brain pan as a cure for patent trolls.
    [ link to this | view in chronology ]
- Spaceman Spiff (profile), 24 Mar 2010 @ 8:04am
  
  Patentable software
  I disagree with Anonymous Coward (at least one of them) that software should not be patentable. I say that because I hold one that I think is worthy of it, and to blanket agree would be at best disingenuous. In general however, most software patents are "patently" bogus! If the USPTO would subject software patent applications to the same rigor they subject hardware patents (non-obvious solution to a problem, no relevant prior art, etc), then the system would not be so FUBAR. Unfortunately, that situation does not seem to be in the stars.
  
  In the process of getting my patent, I had a wonderful opportunity to see how screwed up the US Patent Office is. It took 4 years to get granted, during which time the examiner was citing totally unrelated patents as prior art reasons why it should not be granted. I don't know how much legal time was wasted on the process since that was handled by the company I worked for at the time. In any case, from the examiner comments on the rejections I could tell that he/she was clueless about what we were actually trying to patent - a means to extend classes and behavior in compiled (binary code) systems by specification and not programming - a key component to truly adaptive systems.
  [ link to this | view in chronology ]
  - angry dude, 24 Mar 2010 @ 9:11am
    
    Re: Patentable software
    4 years to grant ?
    
    Lucky you
    
    How about 4 years til 1st office action ?
    
    "If the USPTO would subject software patent applications to the same rigor they subject hardware patents (non-obvious solution to a problem, no relevant prior art, etc),"
    
    Ua kidding right ?
    
    Perhaps you don't know but a simple ethernet plug has some 600 patents on it
    
    Hardware patenting is also screwed big time
    [ link to this | view in chronology ]
Lurchicus, 23 Mar 2010 @ 6:44am

Say what?
I used to work on an operating system in the 70's called MPX-32 that was written in assembler and the entire system was built around doubly linked lists, from memory management through task scheduling.

The idea that someone can wander in in 2006 and make a patent on this is insane.
[ link to this | view in chronology ]
Jay, 23 Mar 2010 @ 7:01am

OMG. I think I can't code anything!!! Afraid I may be accused of infringing some patent!!
[ link to this | view in chronology ]
Tyanna, 23 Mar 2010 @ 7:21am

Wow...seriously? This makes me sad.

How can a fundamental concept of CS be patented? Is Newton's law of motion patented? How about the theory of relativity?

Just...gah!

I guess the only thing to do now is to patent Bubble Sort.... ;)
[ link to this | view in chronology ]
Craig B, 23 Mar 2010 @ 7:48am

Let's call the USPTO
The patent:
http://www.google.com/patents?id=Szh4AAAAEBAJ&printsec=abstract#v=onepage&q=&f= false

The primary examiner's phone number (John Breene):
http://www.uspto.gov/web/patents/contacts/tcmgrs.htm

John Breene, 571-272-4107, Supervisory Patent Examiner of Art Unit #2162. We should all give him a call and ask what he was thinking when he allowed this to go through, in the 4 years (2002-2006) he had to examine it.
[ link to this | view in chronology ]
Ronald J Riley (profile), 23 Mar 2010 @ 9:46am

Piracy & Fairness Coalition Members Sponsorship
"This post is part of the IT Innovation series, sponsored by Sun & Intel."

REAL programmers DO take the USPTO seriously. It is the REAL programmers who actually invent something who file for patents and second and third rate ones and their corporate counterparts who while about the patent system.

Mike, this patent is on a VERY narrow linked list concept and it seems unlikely that it has much use. It most certainly does not impact the majority of linked list uses. It is a shame that you and your sponsors saw fit to leave the impression that this patent covered the broad concept.

What I found more interesting is that finally we have a public head on admission that two members of the Coalition for Patent Piracy & Fairness are sponsoring TechDIRT posts on patent issues. This is most certainly the kind of "insight" we have come to expect.

Ronald J. Riley,

I am speaking only on my own behalf.
Affiliations:
President - www.PIAUSA.org - RJR at PIAUSA.org
Executive Director - www.InventorEd.org - RJR at InvEd.org
Senior Fellow - www.PatentPolicy.org
President - Alliance for American Innovation
Caretaker of Intellectual Property Creators on behalf of deceased founder Paul Heckel
Washington, DC
Direct (810) 597-0194 / (202) 318-1595 - 9 am to 8 pm EST.
[ link to this | view in chronology ]
- Steven (profile), 23 Mar 2010 @ 10:30am
  
  Re: Piracy & Fairness Coalition Members Sponsorship
  I'm thinking you didn't read the patent in question. FYI I am a real programmer.
  
  I just finished reading the whole patent. Not only does it appear to cover any and all implementations of a multi linked list (except for a linked list with two or fewer items), it also appears to cover any software that makes use of such a list.
  [ link to this | view in chronology ]
- Mike Masnick (profile), 23 Mar 2010 @ 11:27am
  
  Re: Piracy & Fairness Coalition Members Sponsorship
  What I found more interesting is that finally we have a public head on admission that two members of the Coalition for Patent Piracy & Fairness are sponsoring TechDIRT posts on patent issues. This is most certainly the kind of "insight" we have come to expect.
  
  Ronald, no sponsors have any say in the content of these posts. I haven't spoken to anyone at Sun or Intel about any of the content I write, and haven't even talked to anyone at either company in months. Given what each company has said publicly about patents, neither agrees with my position.
  
  Please, keep your conspiracy theories to being logical.
  [ link to this | view in chronology ]
  - angry dude, 23 Mar 2010 @ 11:46am
    
    Re: Re: Piracy & Fairness Coalition Members Sponsorship
    "I haven't spoken to anyone at Sun or Intel about any of the content I write, and haven't even talked to anyone at either company in months."
    
    Ha
    
    everybody and his dog knows what you'll be writing about patents and copyrights
    
    no need to even ask - they like your idiotic writings the way they are...
    [ link to this | view in chronology ]
- Anonymous Coward, 23 Mar 2010 @ 12:45pm
  
  Re: Piracy & Fairness Coalition Members Sponsorship
  "It is the REAL programmers who actually invent something who file for patents"
  
  The whole point of this article is that this patent filer did NOT invent something. He took a very fundamental and very old data structure from computer science and slapped his name on it.
  
  "Mike, this patent is on a VERY narrow linked list concept and it seems unlikely that it has much use."
  
  What!? You'd be hard pressed to find an experienced programmer that hasn't crossed this one at some time.
  [ link to this | view in chronology ]
- Anonymous Coward, 23 Mar 2010 @ 1:47pm
  
  Re: Piracy & Fairness Coalition Members Sponsorship
  Good thing RJR offers such substantial evidence to back up his claims instead of just resorting to lame insults and dead people.
  [ link to this | view in chronology ]
- Mike Masnick (profile), 23 Mar 2010 @ 2:12pm
  
  Re: Piracy & Fairness Coalition Members Sponsorship
  Oh, in the meantime, Ronald, I've been asking you repeatedly over the past few weeks to provide a *single* study that supports your position and disproves the studies that we've presented here over the years.
  
  To date, you have refused to do so.
  
  We'll keep waiting...
  [ link to this | view in chronology ]
MAC, 23 Mar 2010 @ 9:49am

USPTO: Stupidity knows no bounds...
Great!

Now I can go out and patent a user interface that uses pointing devices like mice, trackballs, cursor keys, little sensors that track my eyeballs and, don't forget, spoken commands!

With the profits I'll startup US Robotics and develop robots whose sole purpose in existence is to inundate the USPTO with more and more troll patents and of course, find the violators!

What's not to like?
[ link to this | view in chronology ]
- Ronald J Riley (profile), 23 Mar 2010 @ 10:19am
  
  Re: USPTO: Stupidity knows no bounds...
  The problem with this is that you are not bright enough to produce a real invention of enough value to draw the attention of those patent pirating companies who like to whine about mythical patent trolls.
  
  Ronald J. Riley,
  
  I am speaking only on my own behalf.
  Affiliations:
  President - www.PIAUSA.org - RJR at PIAUSA.org
  Executive Director - www.InventorEd.org - RJR at InvEd.org
  Senior Fellow - www.PatentPolicy.org
  President - Alliance for American Innovation
  Caretaker of Intellectual Property Creators on behalf of deceased founder Paul Heckel
  Washington, DC
  Direct (810) 597-0194 / (202) 318-1595 - 9 am to 8 pm EST.
  [ link to this | view in chronology ]
  - TAR (The-Anti-Riley), 23 Mar 2010 @ 4:49pm
    
    Ronald J Riley's Stupidity knows no bounds...
    I am speaking only on my own behalf. :p
    [ link to this | view in chronology ]
  - Anonymous Coward, 23 Mar 2010 @ 10:02pm
    
    Re: Re: USPTO: Stupidity knows no bounds...
    So, RJR, what coding have you done? I mean, besides the massively hilarious signature and the 3 horribly designed websites.
    [ link to this | view in chronology ]
Anonymous Coward, 23 Mar 2010 @ 10:32am

PL-1 & Multiply Linked Lists
Is anyone here still familiar with PL-1? I seem to recall that PL-1 was set up to specifically take advantage of multiply-linked lists. Does anyone know or remember?
[ link to this | view in chronology ]
staf, 23 Mar 2010 @ 11:16am

do as I say
"For the most part, they recognize that code is just a tool: you can make it do all sorts of things, given enough time and resources, but that doesn't mean that doing any particular thing in code is an "invention" that no one else should be able to do."

Or so Intel and Sun would like them to think. Their view is "if we didn't create it, then neither can anyone else".
[ link to this | view in chronology ]
Spanky, 23 Mar 2010 @ 11:58am

re
I got news for you - linked lists go way back before 2001. Maybe as far as Ada Lovelace.

In cases like these, I have to ask myself if people like the USPTO are abysmally stupid, or criminals on the take. If I assume they're stupid, the logic just don't work out.
[ link to this | view in chronology ]
- Anonymous Coward, 23 Mar 2010 @ 12:28pm
  
  Re: re
  You have limited yourself too much, and have focused only on incompetence or nefarious. Neither is likely true. Part of the problem is that the USPTO has a bunch of over-worked people who are relatively inexperienced in a variety of areas. Because of that inexperience, they are limited to what they have in their files, which, when it comes to software, is likely far less than what exists.
  [ link to this | view in chronology ]
MAC, 23 Mar 2010 @ 12:37pm

Hey Ronald McDonald...
The problem is you are too @### arrogant to realize that equating hardware to software is like equating the brain to the mind. They are not the same! The brain supports the mind but it is not the mind.
The mind is the culmination of experiences in ones life, the brain is it's hardware that stores those experiences and the processes around them...
[ link to this | view in chronology ]
- angry dude, 23 Mar 2010 @ 1:29pm
  
  Re: Hey Ronald McDonald...
  Be my guest and try to isolate/separate mind from brain
  
  Then you can put your little retarded mind in a glass bottle and store it forever for humanity
  [ link to this | view in chronology ]
Lawrence D'Oliveiro, 23 Mar 2010 @ 3:00pm

Prior Art
There’s an old Computer Science concept called a plex (for example, see section 2.3.3 here). It’s basically a generalization of a linked list to include multiple links. How similar is the patent to this?
[ link to this | view in chronology ]
Lawrence D'Oliveiro, 23 Mar 2010 @ 3:56pm

How To Read A Patent
Andrew Tridgell gave a nice talk at the recent linux.conf.au conference where he explains how to read a patent application, and why you should read them and forget the triple-damages issue.

He also gives an interesting suggestion as to how Free Software developers should react when threatened with a patent lawsuit: that we should pool our intellects to come up with a workaround, and then make sure everybody in the world knows about that workaround. That way, even those licensees of the patent who are developing proprietary software can make use of that workaround. So the patent owner doesn’t just lose the case against the Free Software project, they lose their existing revenue stream as well.

Basically, patent holders should learn that Free Software developers are BAMFs, and stay away from them.
[ link to this | view in chronology ]
- angry dude, 24 Mar 2010 @ 7:15am
  
  Re: How To Read A Patent
  "Basically, patent holders should learn that Free Software developers are BAMFs, and stay away from them."
  
  yeah, right, I know
  
  and I stay away from those FSF punks as long as they stay away from my patent
  (which was not only published at uspto.gov but was also disclosed to eveybody at 2 major international conferences and the work was cited many many times in various publications around the world)
  [ link to this | view in chronology ]
  - Anonymous Coward, 24 Mar 2010 @ 2:27pm
    
    Re: Re: How To Read A Patent
    Oh, still going on about your imaginary patent? Fun.
    [ link to this | view in chronology ]
Anonymous Coward, 23 Mar 2010 @ 5:20pm

Not doubly-linked list!
OK, I read it. This is not a patent on doubly-linked lists. Well, not quite.

It's a patent on singly linked lists with additional chains of single links in case you need to traverse a subset of the list or the whole list in another order. Doubly-linked lists are a special case.

Yes, this is still obvious, and yes, there's still plenty of prior art.
[ link to this | view in chronology ]
- Pseudonym, 23 Mar 2010 @ 5:46pm
  
  Re: Not doubly-linked list!
  Gah, posted before I finished.
  
  I looked through some old source code, and I did find an example of a general subset/reordering problem from the 4.3BSD source code circa 1986. Each process belongs to two doubly-linked list:
  - The run queue or sleep queue (depending if it's runnable or sleeping).
  - The list of all active or all zombie processes (depending if it's active or zombie).
  Linux today maintains no fewer than 14 pointers per task, and the code to do this predates 2006 by quite a while.
  
  While that's the oldest source code I could find, it's not the oldest reference to the technique in the literature. The original paper on the DLX algorithm, popularised by Knuth in 2000 or so, was submitted for publication in 1978 by Hitotumatu and Noshita.
  
  And, of course, compilers have been using multiply-linked lists for symbol table management essentially forever, since back in the day, you had to maintain both links to manage the hash table and links to manage nested namespaces. I have a book written in 1979 by Richard Bornat which describes a symbol table organisation which uses five pointers per node. The technique was considered to be well-known even then. I seem to recall, for example, the BLISS/11 monograph talking about multi-pointer lists for various tasks; that was written in 1974 about code written in 1971.
  
  I think it'd be hard to find an earlier published reference than that for a very simple reason: Programmers don't like wasting time stating the obvious. And this is as obvious as it gets.
  [ link to this | view in chronology ]
Danny, 24 Mar 2010 @ 2:05pm

Easy...
...and to question who approves these kinds of patents.
These approvals are made by people who don't have a full understanding of software. Such people can be easily misled into thinking that is common knowledge or even a tool of the trade is somehow patenable.
[ link to this | view in chronology ]
Thomas Jones, 25 Mar 2010 @ 8:56pm

If you actually read the patent it seems to a patent on a doubly linked list on crack...

I don't think this actually covers any sane implementation of a linked list... or it covers pretty much all of them, so either it is invalid (by prior art) or it covers essentially nothing...
[ link to this | view in chronology ]
Aaron (profile), 25 Mar 2010 @ 9:08pm

lists == specialized graphs
Lists are just specialized graphs and the more links you add to the list the further you tread in to general graph theory. Dijkstra, et al. already provided us with proofs for graph traversal algorithms that cover the most efficient methods of traversal. Oh, and Dijkstra was rather anti-hardware. He did almost all his work with a fountain pen and paper as he realized software was most emphatically NOT hardware, but rather a mathematical construct and often symbolized in computer hardware by the switching on and off of electrical potentials. Note I said symbolized, not the same thing as. Software can also be symbolized in the english language, or a formal mathematical specification.

Software == Math and hardware == a turing complete machine that does Math.
[ link to this | view in chronology ]
darryl, 22 Apr 2010 @ 2:07pm

Still little understanding
Such simplistic views on patents and inventions.

First, it's not the doubly-linked list that is patents it's 'A method of linking lists by some unique means'.

Just as the patent 'on the steam engine' is not that simplistic, it would have been worded, and diagramed very specifically.

That means if you come up with another different way of using steam to drive an engine, you can go patent that.

As for software and hardware, it's all the same thing.
Software is an abstraction, on the real physical level it's a specific configuration of many millions of swtiches.

Next clock cycle, it's a new configuration, the invention is in the METHOD of achieving something, not the something itself.

You dont patent 'the steam engine' you patent a specific method of generating torque from stream'.

Is a switch any more or less 'real' or physical if it is turned ON of OFF ?? NO.

The invention is in how you turn on or off specific hardware in a specific combination to achieve a specific result. (what we call software, but can be hardware as well).
In the real physical world there is no distinction between software and hardware. As well if you want to get right down to it, electrons have mass, therefore they are physical, just as real as a transistor or a ford pickup.
[ link to this | view in chronology ]
darryl, 22 Apr 2010 @ 6:53pm

Still little understanding
Such simplistic views on patents and inventions.

First, it's not the doubly-linked list that is patents it's 'A method of linking lists by some unique means'.

Just as the patent 'on the steam engine' is not that simplistic, it would have been worded, and diagramed very specifically.

That means if you come up with another different way of using steam to drive an engine, you can go patent that.

As for software and hardware, it's all the same thing.
Software is an abstraction, on the real physical level it's a specific configuration of many millions of swtiches.

Next clock cycle, it's a new configuration, the invention is in the METHOD of achieving something, not the something itself.

You dont patent 'the steam engine' you patent a specific method of generating torque from stream'.

Is a switch any more or less 'real' or physical if it is turned ON of OFF ?? NO.

The invention is in how you turn on or off specific hardware in a specific combination to achieve a specific result. (what we call software, but can be hardware as well).
In the real physical world there is no distinction between software and hardware. As well if you want to get right down to it, electrons have mass, therefore they are physical, just as real as a transistor or a ford pickup.
[ link to this | view in chronology ]
patentsystem, 25 May 2010 @ 11:14am

Ugh. I just want to take the patent bar, but no ... they don't allow people who have an APPLIED MATHEMATICS background sit for the exam? What kind of tomfoolery is this? Oh yeah, and my minor in comp sci doesn't count either. Why? Because apparently, Duke, is not ABET worthy in computer science.

What a joke.
[ link to this | view in chronology ]
yuregininsesi, 24 Jun 2010 @ 4:18pm

A doubly-linked list is just one that you can traverse forward and backward. This patent is for a multiply-linked list which you can traverse in any pre-defined order. The douby-linked list is one type of a multiply linked list. Nevertheless the patent is still stupid. Multiply-linked lists have been around longer than I have.
[ link to this | view in chronology ]