Patent on "safe" transitive immutability for object types — prior art?

Apparently, Microsoft applied for a patent on "safe" transitive immutability for object types. I use "safe" to summarize a useful feature: even though object constructors can set fields of an immutable object, the mutable reference to this cannot escape the constructor and become visible to other code. I say "transitive" because contained objects are immutable even though their types would be mutable.

  • On http://patents.stackexchange.com/q/10128/6081, people asked for prior art on this patent application. The question listed some obvious answers, including functional languages (ML, Scala, Rust), but most seem not to be for transitive immutability (except D), or not necessarily to be safe. IANAL, but it seems to me that prior art must match pretty tightly with the content of the patent claims, so one would probably need prior art on a combination with both features.
  • A curiosity: Is is common to apply (and get) patents for PL features? As a researcher in the field, should I worry about patent infringement?

Patent abstract:

A language extension that advances safety in system programming in that an entire type may be declared to be immutable in the case in which all instances of that type are immutable. The immutable type declaration automatically causes any instances of that type to be treated as immutable, and automatically causes all directly or indirectly reachable members (e.g., fields, methods, properties) of the instance to also be treated as immutable. Furthermore, any construction time reference that allows for field assignment of the instance is not permitted to survive beyond the point at which the instance becomes accessible to its creator. Accordingly, this instance, and any other instance of that same type, will be immutable from the very time of construction. The ability to classify all such instances as immutable is beneficial as the immutable characteristic permits actions that normally would not be allowed due to resource access safety.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Probably no one with a job

Probably no one with a job in this field is going to answer that question publicly. Not because the answer is bad, but our companies/universities forbid us from talking about anything legal.

Thanks for the warning

Thanks. I won't think anymore posting such a question is harmless.

Do not read the patent.

Not only are software patents not valid in the UK, using phantom types to propagate immutabity is obvious. Note I have not read the patent. Explicitly specifying immutability is the same as explicitly specifying mutability. Hence an ML ref or Haskell ST monad is a valid mechanism for enforcing this with clear prior art (in the sense that is explicitly marks and safely transmits mutability). All it requires is the judge to accept the law of the excluded middle, which should be straightforward providing mutable is accepted as the opposite to immutable.

The other point is that ideas are not patentable, so they cannot have patented immutable data and safe transmission of such, but the mechanism by which that is achieved. If you are interested in languages like this you should not read the patent. Even posting the patent here to make people aware of it could be considered a bad thing for the community.

Also the academics I know in the UK are allowed to be expert witnesses, which would imply they are allowed to comment on legal matters.

Sure, in a court of law. But

Sure, in a court of law. But in an online forum?

Contracts?

I don't know the specifics of what's in their contracts, but that part of my comment is probably detracting from the important part of the discussion. Perhaps people could check their contracts, and simply comment that they are not allowed to comment?

Treble damages

Reading the patent also exposes you and your employer to the risk of treble damages (in the U.S.) for willful violation. This is one of those situations, like not knowing the combination of the safe in a store where you work, where ignorance is strategically better than knowledge.

I would think posting on a

I would think posting on a forum that you have deliberately chosen not to read a patent that from its title covers something you are working on might also not be the best strategy for avoiding a finding of "willful violation", but IANAL.

Better to respond with your position.

I am not a layer either, but how can you wilfully violate something when you don't know what it is? The idea itself is not patentable, so it is only their method that is protected. If one has not read the method, how could one copy it? If it were to turn out that my independently developed method were the same it would be purely accidental. Further one could say that independent invention means it is obvious (to one skilled in the art) and therefore an invalid patent in the first place.

If I had not said I had not read it, then it might be assumed that as a member of the forum I had the opportunity to read it. In a case of the balance of evidence, contemporary evidence with a consistent timeline is more valuable than a statement at a later date. In my experience it is better to set out your position in return at the earliest opportunity.

Willingful violation incurs

Willingful violation incurs treble damages in the states; anyways, I won't read patents.

There are some things people only talk about over beer.

Transitive immutability

I'm curious in discussing the language design proposed. Thanks for the warnings — my own research seems different enough to be quite safe. But I won't be reading further on the patent, and refrain from similar postings in the future.

That said, I'm not sure of your technical argument (though that might be because you had to avoid looking at the details).

Explicitly specifying immutability is the same as explicitly specifying mutability. Hence an ML ref or Haskell ST monad is a valid mechanism for enforcing this with clear prior art (in the sense that is explicitly marks and safely transmits mutability).

I'm not sure on either statement. For Haskell, I'm not sure if you refer to STRef (which is the analogue of ML refs) or to the ST monad itself somehow; I'll talk about STRef.
1) A transformation from a language with explicit mutability to a language with explicit immutability is bijective, yes, but it does not keep the same annotation overhead, nor is the number of produced annotation bounded in the number of consumed annotations.
2) Mutability and immutability are also not duals for other reasons — most language designers are partial to immutability hence try hard to make designs asymmetric. For instance, ML refs/Haskell STRef require one more indirection for mutability — see below for why it matters.
3) More importantly, if you get normally mutable data through a value of immutable type, it becomes immutable as well — that's what I meant with transitive immutability.
Translating this to mutability, once you access an immutable value through a ML ref/Haskell STRef, you could in fact mutate it without restriction, as if all members were cells and not direct pointers. I think this is closer to Lisp's set! than to ML/Haskell mutation, which requires pointers to have an extra level of boxing, but I'm not expert on either Lisp or ML.
Back to immutability in this context, fetching an immutable pointer would require "inlining" STRefs in the pointed data.

Mezzo, probably ATS

Immutable types as in D are prior art for a previous patent, still pending:
https://www.google.com/patents/US20090327999?dq=mutable+types

The feature described here is best realized through linear typing. It is precisely avaiable in this form in the research language Mezzo (constructor mutation allows to turn uniquely-owned data into duplicable data), and I suppose it must be available in ATS as well, though I haven't seen the exact thing described.

For Mezzo, see for example this example of destination-passing-style map, where a mutable cell is turned into a immutable list cons-cell by this line of code:

      tag of c0 <- Cons;

Preventing escape of mutability

With a compositional type-checking/inference algorithm, its trivial to mark all types immutable that are referenced in a data-structure. At the point in type checking when any type is marked immutable, you simply follow the type graph and mark all types in the data structure immutable recursively. If we are using a union-find representation of the type graph, all types which are connected will be a member of the same equivalence class, so the immutability will automatically propagate to any reference to that value, but not to unconnected instances of the same type.

In other words you trivially modify the unification rule to allow an immutable type to unify with a mutable type, resulting in an immutable type. Providing type-checking/inference occurs compositionally this will allow mutable references within a program fragment, but not allow it outside the fragment where any containing data has been marked immutable. The containment of mutability will be determined by fragment composition, and hence by lexical scoping.

Edit: I think its probably better to consider mutability a requirement as part of the type context. As such unifying an immutable and a mutable type would result in a mutable (hence inference is treating immutable to be a subtype of mutable). Immutability as a constraint would be something the needs enforcing, so would be best as a type constraint that effectively statically checks the type requirement is immutable, or propagates immutability as above. This unfortunately seems to be a 'cast' operation from mutable to immutable, which seams reasonable. The inverse would require a copy from immutable to mutable.

BitC

BitC did a lot of work on mutability/immutability annotations to scope the propagation of mutation. Like a stronger "const" that meant "transitively immutable", and they also toyed with another notion of "transitively read only". These ideas came from E's notions of deeply frozen objects.

Yes

As far as I can tell, this work is a direct transcription of explanations I made to people at Microsoft about BitC immutability. The particular approach to immutability that they have applied to patent has been discussed multiple times on the BitC programming language list, not as something that we had any doubts or difficulties with, but as something that we took for granted as obviously doable. We even discussed the escape analysis necessary to ensure constructor safety.

This is the second case of a patent application by someone on the Midori group since my departure that appears to be directly based on my own work and/or my discussions at Microsoft regarding my prior work and the prior work of others. I do know that Duffy has done a bunch of work on resolving some issues in C# that preclude proper implementation of readonly, but he is not the inventor of either the notion of transitive immutability in a programming language nor of immutability permitting construction. Both were discussed on the BitC list prior to my arrival at Microsoft, including a much more general form of immutable initialization relying on confinement. I discussed this work with Duffy while I was at Microsoft. Heck, I've done a Ph.D. dissertation and two formal verification efforts on this topic; it's hardly new.

Given this, I think there is a problem insofar as the patent fails to credit an inventor at Microsoft (me), but more to the point, the patent application fails to cite prior art about which they knew: BitC, EROS, and KeyKOS. Given the prior work, I would have refused to support this filing on the basis of prior art.

Many people at Microsoft hold the view that outsiders can't do anything interesting. They are, in my experience, appallingly unaware of prior art in the field, and sincerely believe that they have invented many things that have existed for some time.

Double Yes

read-only meaning "transitively read-only" was in KeyKOS ("sense keys" iirc) when I used it in the 80's; given how central that concept (along with transitive effective immutability via COW nodes) was to the security story, I'd imagine it had been in GNOSIS even before then.

Yes and no

Transitive read only was certainly in KeyKOS and GNOSIS, but the patent is dealing with a different set of issues.

To be clear: during the brief time I was at Microsoft, Duffy was investigating questions that would have led him in this direction, which is how we came to be discussing it. It's very possible that he simply forgot about our discussions and reinvented the solution. And if he has a solution that works in a future .Net framework, then more power to him.

It's the patenting of prior art that I object to.

Thanks a lot for the comment

Thanks a lot for your answer. I quoted it in the parent discussion, hope I didn't misunderstand anything:

http://patents.stackexchange.com/a/10214/6081

You are welcome to contribute there directly.

I looked at your profile, but your homepage link is 404 — the website mentions Jonathan Shapiro:

http://www.eros-os.org/~shap

Of course you are entitled to be anonymous, but I'm sure people seeing this discussion and trying to invalidate the patent would be happy to know who you are if you don't mind.

I'm also sorry to hear your comments about Microsoft — given both Meijer and Peyton Jones work there, I'd have hoped for better (not that I generally like Microsoft in any sort of way).

MSR != MSFT

that is all. :-)

MSR files patents also.

MSR files patents also; I have my own personal opinion about this, but I can't share it.

Note that Meijer left Microsoft a couple of years ago. I don't think he ever worked for MSR (he was associated with VB).

Microsoft is also a big company with a lot of diverse behavior like any big company (it is rumored that Google files patents also).

LtU patents

it is rumored that Google files patents also

Indeed, but it was the first time I heard about patenting *programming language features* -- although on further inspection it appears MS has been doing that for a few years already. Does Google also patent language features?

My understanding of the patent situation was that software isn't patentable, but lawyers find hole by masquerading software as parts of mechanical devices. Patenting programming languages feels like a whole new level of absurdity.

I find this both depressing (they're coming at our doors!) and amusing in some ways: it's official, the industry cares about programming languages.

Only sound type systems

Only sound type systems should be patentable.

Aren't unsound type systems

Aren't unsound type systems the new hip thing?

I thought patents are there

I thought patents are there to encourage innovation...

Nah

That's a common misconception. Encouraging innovation is the excuse for patents. Their primary function is to stifle competition. One of the things to keep an eye on in an economy is the fraction of resources that go into maniplating the legal system for advantage rather than making better products. When that ratio gets too high, the economy is in deep doodoo.

If you haven't noticed the

If you haven't noticed the sarcasm there's nothing more I can do for you.

Who, me?

Who, me?

Whomever failed to

Whomever failed to appreciate the ellipsis at the end of my previous message.

Lawyers need jobs too

I dread to think what would happen if we had gangs of unemployed lawyers wandering about.

Software is patentable

Unfortunately, software is patentable. The status of this changed quite a long time ago.

Not in the UK or Europe

Not in the UK or Europe. although there appear to be some ways around it. See: http://en.wikipedia.org/wiki/Software_patents_under_United_Kingdom_patent_law

Unfortunately

Unfortunately, no relevant player can afford to ignore the American market, so that does not make much of a practical difference. Globalisation means that you always get the union of regional dysfunctionality.

PS: Has the UK already become not Europe? :)

Simple mistake

I migrated that server a couple of weeks ago and forgot to check the web server config. It's serving again now; thanks for letting me know.