Hacker News new | past | comments | ask | show | jobs | submit login
Microsoft filed patent applications for scoped and immutable types (dlang.org)
206 points by chx on Aug 27, 2014 | hide | past | web | favorite | 86 comments

For those who are claiming prior art, I suggest you open a question up at "Ask Patents" (StackExchange site).

"Ask Patents" has been used by the USPTO to overturn patent requests.


Source? (Seems unlikely the USPTO would use a end-user forums to make a decision)

> The America Invents Act changed the law to allow the public to submit examples of prior art while a patent application is being examined. And that’s why the USPTO asked us to set up Ask Patents, a Stack Exchange site where software developers like you can submit examples of prior art to stop crappy software patents even before they’re issued.


Yes, they did. They asked a lot of folks to do a lot of things. That does not mean it is actually used.

I've talked with the ask patents folks before, and from what i remember, they send email to the examiners. That's it.

They try to occasionally look and see if the stuff they cite was cited by the examiners, but then they assume that if that is the case, that they were the reason the examiner found it. While I understand how hard it is to know why examiners did things in general (You can see exactly what they searched for through PAIR data, but not what results it turned up), this is a very very suspect methodology.

People really need to stop always quoting Joel - he is not a definitive go-to software spokesperson, and has some very strong (and often wrong) opinions about things -- shaped by years at Microsoft doing things only the Microsoft way.


He is puffing his product in this blog post -- nothing more.

He's stating facts about his startup. It's not like he's giving some opinion on something he's not qualified for. It's like saying we shouldn't ask Woz we he made Apple Basic.

Well, StackExchange is hardly a "startup" anymore.

And, this particular blog post is Joel up-talking the new "ask patents" exchange and describing why he feels it's needed.... so... it is a puff piece.

I don't know why you are being downvoted when you are, sadly, 100% correct.

patents.stackexchange is probably not the end source for them to base a decision on, but rather a place to find real sources of prior art for patent applications. So it seems very likely to me.

Patent examiners are generally not allowed to search external sources for information about unpublished apps. I've had this discussion numerous times with examiners and PTO officials while working on improving prior art finding on google.com/patents.

They have a very fixed number of sources they search, and are generally not allowed to search elsewhere with unpublished app info.

So I can pretty much 100% guarantee you they are not searching patents.stackexchange for information.

(Plus, patents.stackexchange themselves do not suggest examiners use it that way. They email examiners).

For published apps (this was recently published), they are allowed to do more, but they generally don't anyway. They stick to the databases/etc that are available to them internally.

I haven't read the immutability patent in detail, but it seems like the problem they are considering is not completely trivial. I've seen research papers on similar topics. Example: http://www.cs.ru.nl/E.Poll/papers/esop07.pdf

I think one should have a careful look at it to check if there is anything new here. Maybe there is.

Edit: Found a recent paper by some of the patent authors that looks related: https://homes.cs.washington.edu/~csgordon/papers/oopsla12.pd...

That being said, it clearly shouldn't be possible to patent such ideas.

I've been doing a lot of reading in this area lately, and it's not trivial stuff. The central idea of this field of inquiry is using the type system to limit the proliferation and capabilities of aliases. Concurrency is one application: a class of race conditions can be prevented if you can statically guarantee that only one read/write reference to an object exists, potentially in the face of many read-only references. But there are also applications to memory management: you can use annotations to ensure that, e.g. that no aliases to objects in a region outlive the region. No existing system is really satisfactory in terms of annotation overhead versus the ability to accommodate arbitrary object graphs.

IMHO, figuring out a usable system should at least pass the obviousness hurdle to patentability. I think the real issue is that it neither costs much money to develop these ideas, nor does anyone make any money off compiler technology, so the rationale for patents isn't really implicated. If the idea was backed by real world testing of its usability in production systems, I think that could merit a patent, because that is expensive R&D someone could free-ride off of.

One thing I'll note in regards to Microsoft patents is that for basically the entire lifetime of the company filing patents has been considered important.

On the other hand, that doesn't necessarily mean Microsoft wants to keep them closed. On the Roslyn team we received a number of patents on some new algorithms and data structures to do fast and incremental parsing with immutable data structures. When Roslyn was open sourced all the code and patents went under Apache and are now open under its conditions.

That OOPSLA paper is essentially the patent (it was written by the patent authors). It's basically baking many forms of immmutability (e.g., immutable to view, but not when owned, vs. immutable in the entire object graph) into the type system.

As far as I can see, if any software is patentable, that is.

"As far as I can see, if any software is patentable, that is. "

Why? It has been known you could do this for years. There is literally nothing special about their model, other than baking it into a type system, which everyone knew you could do, but nobody had bothered to try to sell to programmers.

You don't seem to understand the patent system. It doesn't matter how obvious something is. There's a good likelihood someone at the overworked, understaffed USPTO will rubber stamp it. Bombarding the USPTO with patents for any and everything you can possibly think of is a valid strategy, because once you get it, it's a lot of work and expense to overturn and you can start extorting people in the meantime.

Microsoft didn't start out with this attitude, but when it was applied to them, they decided join in and hard.

If you're a programmer who can do more than write a for loop that counts to 10, I can almost guarantee you've violated a patent. In fact, I used to joke about getting a patent on the for loop. If Fortran, or whatever language first had for loops, had been created today, there would probably be a patent granted for it.

"You don't seem to understand the patent system." 1. I"m a registered patent attorney. 2. I run www.google.com/patents 3. I talk to examiners frequently 4. I spent years of my life working for patent reform in DC

Trust me, I understand how the patent system works.

The USPTO is not horribly understaffed. They have other issues. One of the main issues is actually that the patent examiners are union, and the union is not really on board with them being asked to do significantly more work (IE searching harder), unless they get significantly more pay. In a lot of cases, they can't get significantly more pay, because there are salary caps on federal employees, etc.

> The USPTO is not horribly understaffed. They have other issues. One of the main issues is actually that the patent examiners are union, and the union is not really on board with them being asked to do significantly more work (IE searching harder), unless they get significantly more pay. In a lot of cases, they can't get significantly more pay, because there are salary caps on federal employees, etc.

Is that not something you could solve with more employees? If the task does not lend to parallelization, let each team work 2k weeks on every application instead of the current k weeks and employ doubly the amount of teams.

"Is that not something you could solve with more employees? If the task does not lend to parallelization, let each team work 2k weeks on every application instead of the current k weeks and employ doubly the amount of teams."

The USPTO does not have the budget to double their staff. They are also getting pushed as hard as possible to lower pendency periods, which are already 3+ years in a lot of cases.

If they did double their staff, the union would just demand even more concession, because they would have more power, not less. If they doubled pendency, they'd get murdered by congress.

So they can't really win.

Note that the "not searching harder" problem cuts both ways. Examiners get rewarded for moving applications off their desks regardless of whether they are approved or rejected. As such, I have seen as many frivolous rejections as I've seen frivolous approvals. One rejection I saw cited some unrelated reference and literally just made arguments up. There are no stats on this, obviously, but my anecdotal guess is examiners would prefer slightly to err on the side of rejection than approval. YMMV.

The paper is novel enough for OOPSLA -- seems fine to me.

They do more than bake it into the type system. They allow immutable types to be assigned to mutable types. But they don't allow those values to be mutated, even from the mutable types.

That is type checking fails when you try to violate the constraint of the type, not when you assign one type to another that is incompatible.

Which is a fairly simple application of well known typestate analysis?

I'm not sure it's simple, but it is related. If you read their paper you'll see they talk about the relationship of this work to Bierhoff and Aldrich's paper "Modular TypeState Checking of Alised Objects" and Naden, et al's paper on Permissions.

It shouldn't be possible to patent such ideas.

But in the current legal environment, it would be crazy of a company like Microsoft not to try and get a patent on anything they can get away with. Especially so now that the the America Invents Act is in effect. Being first to file means that they no long have the option of being altruistic and just letting their inventions sit around unpatented. That leaves an opening for someone else to swoop in, get the patent, and try to sue them for "infringing" on something they invented first.

Which is admittedly an awful situation. It really shouldn't be possible to patent such ideas.

Anyone who gives you that story is trying to mislead you, using the rule change as cover. What first to file does is change the rule for who gets priority when multiple parties file overlapping patents. Before priority went to the "first to invent" now it goes to the "first to file" (avoiding the expensive process of figuring out which applicant invented first). It has no effect on a party that publishes an invention with no intention of patenting it.

It easy to see how this patent application can actually come to life:

At the end of every sprint or dev milestone, an email goes out from some PM or dev manager, asking people for "ideas to be patented." Somebody then collects all of these ideas. Because applications cost money and units have budgets, then there is a preliminary amount of "filtering": ideas that are "cool," the latest shiny feature (who cares if it has been developed elsewhere for ages), etc. This goes from things like tiles for UI to really deep advancements in cloud computing. The specs are a source of leads. Obviously in many cases the list includes a bunch of relatively minor advances (since a lot of development at MS is mostly incremental) that may be prior art except to the junior dev and PM who think they just discovered how to square the circle. There may be some preferential treatment here for patents to special people, given that there is a little bit of money that, if approved, goes back to the employees too. There is a column in some spreadsheet that classifies the patent ideas based on their perceived awesomeness.

At some point the list of patents has to be sent to some IP lawyer. The IP lawyer does real work here, but is also looking at thing like competitive aspects the team might have missed: i.e. if it is in an important business area, then it gets an extra boost to become an application. An exec probably approves the list too.

When the list is approved for applications, the job is then to make sure the application is written by the members of the team and the lawyers. This takes a lot of time and a lot of work, but since the specs already exist, people use that as the basis.

When you get a patent application granted, you get a little plaque which you hang on your wall and/or a little cube you stack on your desk. The higher the stack the more your patent prowess. Given how some people have been at the company for long, they can accumulate 20+ of these cubes. You get an aura of inventor.

Obviously, people find that it is beneficial to get a patent (the plaque, the cube, the little cash), and would lobby for these ideas to be in the approved set, or at least to participate in the shiny specs because the rule is that everybody who was even remotely involved in the patent gets to be listed in it (therefore, managers get a lot of patents because they were in meetings where the idea was discussed and maybe contributed to it).

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.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)?

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.

The first thing that came to mind in terms of prior art for the immutable object type was JavaScript's Object.freeze(obj) which was released in ES 5.1 (2011):


Edit: replaced Object.seal with Object.freeze

The D programming language introduced transitive immutable types in 2007 with version 2.000.


Jared Parsons is the VsVim guy. I heard they are working on a systems programing language for Microsoft.


Does anyone know how do companies incentivize employees to come up with such patents? Does the patenting initiative come from the employee that "invents" or is this decision made by someone else?

I can't speak for MS, but in most companies where I've worked the process is something like this.

- Fill in an internal form

- Have a chat with an internal lawyer / patent expert

- Receive a (small) payment if it is submitted to the patent office.

- Receive a (bigger) payment if the patent is granted.

- Receive a (huge) payment if the patent is used / sold / cross-licenced.

The exact process and payments will depend on country and company.

And, yes, it is possible to game this system. For a good study, read "Surely you're joking, Mr Feynman" http://books.google.co.uk/books?id=Z7g-BAAAQBAJ&pg=PT170&lpg...

I was sort of darkly amused by the messaging eBay sends out to solicit patent ideas from employees. One of the primary themes is "don't worry if it's obvious; obvious ideas are still patentable".

Well, money is money and capitalism is capitalism. I have a pretty big internal debate about the morality of our patent system, but probably wouldn't bat an eye about proposing/provisioning/filing one for a nice bonus.

Also, the lawyers are expensive and have to be worth their money.

To play the devil's advocate: Something obvious to YOU may not be obvious to just anyone "skilled in the art".

That said, they probably didn't mean that :(

It's not just "skilled in the art", someone of "ordinary skill in the art".

And with all the complaints you inevitably read whenever an interviewing thread happens about candidates unable to code up FizzBuzz, you can guess what the level of "ordinary skill" in our industry is...

That's almost exactly how it worked at IBM. Plus there was always pressure from management to file patents.

>there was always pressure from management to file patents //

IBM's past technical disclosure bulletins (TDB) [I think they stopped them a while back] suggest that there wasn't "always" pressure just that they realise[d] that their patent portfolio is one of their greatest assets - strongly encouraging employees to flag apparent innovations (and getting upstream oversight of those innovations) means that IBM can make the most of the inventiveness of their employees though.

The public benefit is early disclosure of every possible innovation and the TDB helped to disseminate details of tech that may not have been well known.

I could see how that would encourage every employee to try to churn as many "inventions" as possible, especially since patent deals are usually made in bulk, and not over specific patents. So even if the patent is crappy, there's a chance you can get a big payout.

Yes and no. Patents are often licensed or traded in bulk, but only a foolish entity would pay anything for a patent they have not read. However, patents are typically traded as part of a portfolio, and often the portfolio is structured so that it has a few really good ones and a bunch of nuisance or filler patents. Ideally you don't want to pay for those at all, but the seller won't sell anything other than the whole portfolio. Say they offer it for some amount X. So essentially you have to go back and say, "look, these 3 are OK but the rest are really narrow/useless/invalid/crappy, so we think your portfolio is worth much less than X." And negotiation happens.

I can't say how the bonuses are handed out once a portfolio is sold. Ideally, you'd guess the inventors of the "better" patents would get bigger bonuses. The most likely scenario, unfortunately, is that the inventors get nothing, and very likely are not even aware. It's a shame inventors are so unaware of the value companies reap from their IP.

I haven't worked at companies who think along these lines, but friends of mine in the private sector have received bonuses similar to those they'd get for excellent annual performance: a stock grant or cash bonus ($3-5k, although I'm sure it varies).

For us, it's $1500 for the first application, and $750 for subsequent ones.

On issuance, you just get a plaque.

I worked briefly at Orange Labs (R&D branch of France Telecoms) - they showed off how many patents they'd had approved and gave employees a bonus (~£1000 I think) if they published a patent.

Some people are actually proud of their patents, even in CS area. I was pretty surprised about it, but someone I know was really happy that they got their 13th patent granted.

I am proud of some of my patents. The inventions behind them are works of art just like what an open-source contribution may be. These are not inventions that everyone or anyone could come up with. At least in one remarkable case, many people were working on the problem at hand but could not figure even how to start.

To summarize, do not confuse bad cases from good cases. You cannot have a blanket statement of the type, "some people are proud of their open-source contributions ... I was surprised about it".

Yes I can, this is my statement. At least for the CS related people. I'm not confusing good and bad cases, I disagree with the abstract ideas patents (any programs included) completely and other patents to some extent. Basically I disagree with the current state where if I came up with the same idea you did and patented, I owe you something. Both because I don't and because it's not feasible to actually check all granted patents before you do anything.

What is flawed is the state of the affairs in the patent mechanism, not the premise of the patents in principle. I am against the issues resulting from frivolous patents too. Unfortunately, in my opinion, most people against patents do not reason about their philosophy making it harder to convince the authorities against patents.

My understanding is that before patents, people and companies would invent but keep their invention a trade secret for as long as they can, which meant they had exclusivity to the invention. Patents allow such exclusivity for a limited period of time in exchange of disclosing the invention and losing rights over it after a specified period.

The patents applicability criterion correspondingly includes non-obviousness which is to judge if someone else could come up with the same invention without investing significant time and effort or not. Majority of the ideas are "supposed to be" ruled out by this criterion.

The state of the affairs however is that most obvious of the things get patented because (1) obviousness is unmeasurable, and (2) searching the prior art fully is impractical.

Short message: You cannot call all swans white simply because most you see are white.

So it's the patent that makes you proud? Would you not feel proud if you didn't have the piece of government-issued paper?

Correction to my previous comment: I feel proud of the invention indeed, not the patent-sans-the-invention.

That is actually the case for most people outside the HN / open-source bubble. When you read a media outlet or the EFF make flat broad statements that "engineers hate software patents", you now know that they are, at best, pandering, or at worst simply lying.

The truth is, the vast majority of software engineers don't even know what a patent is. Of the rest, some are neutral, some are pro-, and some are anti-software patent. Of course, you only ever hear from the latter group because they think it's a big problem, and the rest really don't see anything wrong.

Similar to what WorldWideWayne is saying, it's possible to be anti-patent and still have some sense of pride over being granted one. The two are far from mutually exclusive. I'm strongly opposed to software patents but would still be giddy if I got one for some neat search algorithm.

I suggest reading about collective action, tragedy of the commons, and prisoners' dilemma. Acting alone and then convincing others to join you will make a difference, but we need to stop thinking about ourselves and start thinking about the society and future we would want to live in if we were suddenly dropped in with no assets or contacts.

I'm quite familiar with all of them, and I completely agree. I'm simply pointing out that there's a divide between the things that make us happy on a conscious level and a visceral level. I'd liken getting a patent to eating the last piece of pizza. I know it's bad for me, and I know I've deprived others of the experience so I should _feel_ bad, but it was also tasty so I can't help but feel somewhat satisfied.

I see something wrong with "the system" but I'd still file a patent for the monetary bonus and the prestige that you get in many circles. My individual action here isn't going to change the system either way.

Same reason that I don't vote. I think a lot of people fall into this category of thinking.

But ask yourself, why do you feel something is wrong with the system? My guess is because you've only been exposed to the media outrage built around cherrypicked examples of bad patents. I've read hundreds of patents, most of which could be called "software patents", and the reality is much more mundane and boring: the vast majority of patents are not groundbreaking or even interesting, but they are not overly broad or vague or obvious either, and very rarely are they infringed by anybody because they solve a narrow problem that nobody else has.

I talked to a Microsoft guy who has a patent in his name, but was now kind of embarrassed about it. He said that he didn't have much leeway when he first started there. So in this case the decision came from his superiors.

Looks good on a resume.

A while back, someone was on HN asking why trust levels were so low when it came to MS. If that person is still reading HN, the answer is "behaviour like this".

What are they smoking? It could be hilariously funny (like this http://www.theonion.com/articles/microsoft-patents-ones-zero... ) if it wasn't so crazy but true.

I still need to understand how the patent office can still validate such patent.

I've read over and over that the patent system is bad, but isn't it just the patent office being incompetent instead ? Isn't that rather an expertise problem ? Or are experts not even asked at all on those subjects ?

Can't anybody sue the patent office for abusive patents ? Or is it just that the people at the patent office just depends on congress, thus making it biased ?

It says right in the title, "filed", not "granted" or "validated".

not talking about this one in particular. what about other creepy patents ?

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact