Hacker News Reader

Comment by readerrrr | Hacker News Reader

Prior art: typedef const int cint ;

How wrong am I and what is Microsoft smoking?

People tend to over-summarise patents; while the subject of the patent is immutable types, the patent is on a specific method for implementing immutable types. It works a little differently to that method, as it's a type-inference and permissions-checking system.

As with every trivial patent, the valid objection is not that this has already been done, because every trivial patent is somehow a bit different to things which have been done before. This particular formulation allows structures to be changed while they are being constructed, but makes them immutable once construction is complete.

The objection to this patent is that the differences to prior art are all trivial and obvious to somebody skilled in the art: if you tried to make an immutable type for C# then you would get something that looked pretty much like this patent. On that basis, the patent should not have been granted.

> This particular formulation allows structures to be changed while they are being constructed, but makes them immutable once construction is complete.

Equivalent to the following Ruby?

    a = "abc"
    a.upcase!
    a.freeze
    a.downcase! # => RuntimeError: can't modify frozen String

Kind of but the important difference is that Ruby checks that at runtime instead of giving a compile time error.

so like this?

  import Control.Monad.ST
  import Data.STRef

  main = do
          let n = runST $ do n <- newSTRef 5
                             modifySTRef n (+ 10)
                             readSTRef n

          modifySTRef n (+ 10) 
          {-
            ^^^^^^
            Couldn't match expected type IO t0 with actual type ST s0 ()
            In the expression: main
            When checking the type of the IO action main
          -}

          print n

Yes, more like that. There are some extra wrinkles they could add with subtyping, record types, etc but its still going to be a silly thing to patent.

That isn't a type constraint — it's a value-level behavior enforced at runtime.

How can anything that is a pure software construct be granted, post-Alice? It is so frustrating that the USPTO seems nearly unmoved by SCOTUS rulings.

That is not what Alice said. Alice essentially expanded the scope of "abstractness" to include things like "long-standing economic principles" simply "done on a computer". It's a bit confusing because something that should be a prior art issue now becomes an abstractness issue, but apparently it could make it cheaper to knock out bad business method patents so maybe it's not all bad.

These are probably not invalid under the new Alice reasoning, but certainly could be for other reasons for abstractness or non-novelty or obviousness. Someone on reddit looked at the file wrapper and said one of them had received an initial rejection for obviousness and abstractness

Well, they haven't approved the patent yet, so give them a chance.

Yea but that linked list patent... no excuse really. I trolled the vendor once by trying to find out how much they would license the use of the linked list in my existing deployment would be.

I got as far as a lawyer who was able to smell something fishy; because at the time I didn't own a company. Perhaps i should try again...

A deployment prior to the priority date is beyond any doubt not infringing that granted patent. If you can prove the date somehow then you can take on anyone quite easily in court by simply saying "this technical implementation preceded the priority date of the patent it is alleged to infringe, see".

What's the linked list patent in question (publication number preferably)?

I believe the patent in question is 7028023. Prior discussions:

https://news.ycombinator.com/item?id=1165089 https://news.ycombinator.com/item?id=1165471 https://news.ycombinator.com/item?id=4664243

The infamous "linked list" patent didn't cover any version of linked lists we are familiar with. It covered a linked list where each node had multiple "next" pointers that allowed different traversal orders, beyond just back-and-forth like doubly-linked lists. I'm not even sure why anybody would use a single data structure to hold what should really be different lists, so I highly doubt you or anybody else is infringing that one.

That's just a graph.

It's not a skip-list, though it is some kind of a graph. I once tried to think of what kind of a graph it is, because it has some weird properties. It is a directed acyclic graph with 1) a fixed number of paths, 2) and each vertex occurs on each path exactly once, and 3) the paths are mutually exclusive, i.e. you cannot traverse one path half-way to a vertex and then follow another path from that vertex. I'm not sure if "mutually exclusive" is the right term... maybe a formal Graph Theoretic definition could be created based on some sort of coloring or labeling of edges.

But when you put these properties together you essentially get a single structure representing multiple lists. That is, given items 1 - 5, you could arrange the pointers to traverse them in orders [1, 2, 3, 4, 5] or [1, 3, 5, 4, 2] or [5, 4, 1, 2, 3], but not [1, 5, 2] or [1, 2, 3, 2, 1].

What I don't understand is why anyone would put what is essentially a number of different lists into a single list. I see no advantages either in algorithmic complexity (traversal and addition/insertion/deletion operations are still the same complexity) or implementation. In fact, I can easily see the implementation being a nightmare. It's tricky enough deleting a node from a singly-linked list. I cannot imagine a problem this was invented to solve that could not have been solved more easily with multiple linked lists. Maybe the problem was non-technical, e.g. "get a patent to put on my résumé".

You could use the two lists to cache respectively a pre-order and a post-order visit of a graph.

E.g. if you have 1->2 1->4 2->3 3->5 4->5 the lists could be [1,2,4,3,5] and [5,4,3,2,1].

1) There's no real pre- or post- order to this graph, just an arbitrary number of traversal orders, and 2) caching the traversals is a different data structure that no longer infringes this patent.

skip lists?

I have read, not in detail, but enough to get the gist of things, and it is also talking about permissions of storage locations. I'm thus making an informed guess that the whole patent is also about bytecode checking on the CLR level.

Reply on news.ycombinator.com