30

http://www.freepatentsonline.com/y2014/0196008.html

At least some embodiments described herein relate to a language extension that advances safety in system programming. In accordance with the language extension, 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.

Improve this question
10
  • 4
    The strangest part of all of this: this patent is assigned to Microsoft. Some prominent developers of Haskell (a programming language, first standardized in 1998, where first-class mutability doesn't exist) work(ed) for Microsoft Research. The left hand doesn't know what the right hand is doing, apparently.
    – Rhymoid
    Aug 28, 2014 at 12:07
  • 2
    What's the question here?
    – kenorb
    Aug 28, 2014 at 16:51
  • 4
    @kenorb: IIUC, the tag means "please provide prior art to invalidate the patent": patents.stackexchange.com/tags/prior-art-request/info
    – Blaisorblade
    Aug 28, 2014 at 23:42
  • 2
    IIUC, we are looking for prior art with (a) transitive immutability (b) mutable references from the constructor can't escape it (so that the immutability actually works).
    – Blaisorblade
    Aug 28, 2014 at 23:43
  • 1
    @Blaisorblade: If you summarize exactly what you're looking for as a post to LTU, you'll probably get some pointers.
    – Harold R. Eason
    Aug 29, 2014 at 1:37

13 Answers 13

Reset to default
19

Ada95 introduced constant, which was far as I can tell was the first implementation of immutable type in the Object Oriented Design paradigm.

https://en.wikipedia.org/wiki/Immutable

Nothing like trying to patent a +20 year old idea.

Improve this answer
1
  • The claims in 20140196008 describe quite a bit narrower than just the immutable type. As far as I know, Ada didn't have the ability to say "this object is immutable" on an arbitrary object and cause all fields and references to other objects to also be treated immutable.
    – user8623
    Aug 31, 2014 at 1:01
16

D has had immutable types for years, very similar in definition to the patent claim: http://dlang.org/const3.html

Improve this answer
3
  • This seems to me to be somewhat different to what the patent is describing. D's "immutable" attribute applies to an instance, e.g. one can declare struct X { ... } and then have immutable X x = { ... }; to create an immutable instance of X. The description in the patent seems more like it describes a scheme where you would declare immutable struct X { ... } and then all instances of X would automatically be immutable (except, obviously, during their construction).
    – Jules
    Aug 29, 2014 at 3:01
  • 1
    @Jules but you can apply the immutable attribute to the type which automatically applies it to every instance
    – ratchet freak
    Aug 29, 2014 at 14:00
  • Yah, consider e.g. immutable class A { ... } which defines a type with only immutable instances.
    – Andrei Alexandrescu
    Sep 14, 2014 at 1:27
9

The first release of D 2.000 in 2007 had transitive immutable types in it. https://dlang.org/changelog.html

Improve this answer
8

Object immutability is nothing new. C and C++ have had the const qualifier for years, which achieves exactly what's mentioned in the excerpt you posted and can be imbued in a type by means of a typedef.

However, the abstract from the page you linked mentions:

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

I didn't read the whole thing, but this might be where the novelty of the patent is: it somehow doesn't let modifiable references to an immutable object escape the object's constructor (which is something I don't believe the other examples posted here do, though I might be wrong.)

Improve this answer
3
  • 1
    D allows mutation during construction of immutable objects:
    – Walter Bright
    Aug 28, 2014 at 1:42
  • 1
    @Walter: Sure, as do other languages, but does it guarantee that modifiable references to the object, formed during construction, do not outlive the constructor?
    – Ell
    Aug 28, 2014 at 6:36
  • 2
    In Scala, ML and so on, there is no "mutable" reference which can escape — fields are only set when declared. However, transitive immutability is not provided there (nor is it in C).
    – Blaisorblade
    Aug 29, 2014 at 2:13
6

I am able to find references to immutable objects in Java dating back to at least 2003/2004 here...http://www.javaranch.com/journal/2003/04/immutable.htm

Also for another source of immutability in D, page 159 starts the section on immutability in Ali Cehreli's Programming in D which is copyrighted 2009-2012 http://ddili.org/ders/d.en/Programming_in_D.pdf

Improve this answer
6

To my understanding the third sentence that you quoted:

The immutable type declaration automatically causes...

does not necessarily imply what other users here call transitive immutability. It rather depends on how you define directly or indirectly reachable members.

Also, it seems that some users don't understand that it's not about declaring objects or instances constant but rather declaring a type in such a fashion that all instances of that type are constant by default.

What you are looking for is limited types in Ada (since Ada83). In Ada there is no assignment operation defined for limited types, which prevents any assignment to objects of limited types or assigments to objects of which you have a limited view. The actual specification is rather more intricate and detailed. Here are some references, knock yourselves out:

Wikibooks, Ada Programming (imcomplete but simple explanation of limited types)

Ada83 LRM, 7.4.4 Limited Types

Ada95 LRM, 7.5 Limited Types (Completely revamped specification)

Ada05 LRM, 7.5 Limited Types (There were lot's of changes concerning initialization in this version)

Ada95 Rationale, 7.3 Limited Types (Contains some discussion about limited views)

Improve this answer
2
  • 1
    IMHO indirectly reachable is a meaningless phrase. if i have a graph like data structure of mutable nodes, and i create an immutable type with a node member, does the whole graph get frozen? this interpretaion is more sensible than others.
    – user3125280
    Aug 31, 2014 at 7:12
  • actually, after reading the patent it seems to claim the graph does get frozen - so it does to members and references what a language like c++'s const does for members only.
    – user3125280
    Aug 31, 2014 at 7:28
6

The Lambda-the-Ultimate discussion yielded a couple new answers. One is about Mezzo/ATS, and there are various others which might be relevant.

The other one says that this patent is a copy of work done in prior art in BitC:

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.

Source: http://lambda-the-ultimate.org/node/5028#comment-82141

As far as I can guess, Duffy must be the first inventor in the patent, "Duffy, John J. (Seattle, WA, US)". This makes the statement much more important.

Improve this answer
1
  • Duffy is likely to be referring to Joe Duffy, the team lead of Midori, an experimental OS written in a modified version of C# who is currently working on retrofitting part of those modifications into mainline C#.
    – Matthieu M.
    Mar 23, 2016 at 18:26
5

Google has maintained a public open source set of immutable data structures for Java since Spring of 2008, and used them extensively internally long before that. Presently part of their Guava library, it was originally released as part of the Google Collections library.

Improve this answer
3
  • 2
    That does not have transitive immutability.
    – Blaisorblade
    Aug 28, 2014 at 22:37
  • @Blaisorblade Could you elaborate on why that's a problem? Guava provides immutable collections, which are deeply immutable if they contain immutable objects (primitives, String, etc.), and intentionally not if you use it to hold a mutable structure. I confess, I am not a patent expert, simply a Guava fan.
    – dimo414
    Aug 28, 2014 at 22:49
  • 2
    If the prior art request tries to invalidate the patent, prior art must do everything, not just something similar. And the patent is about transitive immutability — if you have access to a "transitively immutable" data structure, you cannot change data reachable through it, even if those data are mutable themselves: "automatically causes all directly or indirectly reachable members (e.g., fields, methods, properties) of the instance to also be treated as immutable."
    – Blaisorblade
    Aug 28, 2014 at 23:41
4

JavaScript's Object.freeze(obj) was released June 2011 n ES 5.1: http://www.ecma-international.org/ecma-262/5.1/#sec-15.2.3.9

Improve this answer
5
  • 2
    This turns a single object immutable, the patent seems to be about turning all of the instances of a class immutable.
    – tacaswell
    Aug 28, 2014 at 1:25
  • 2
    Also, the patent is for declaring recursive immutability (as I read the summary).
    – hugh jackson
    Aug 28, 2014 at 12:36
  • It should be trivial to extend a base object in JS so that any other object using it as a prototype freezes itself after initialization. Not exactly prior art, but it does challenge the non-obvious requirement.
    – webXL
    Aug 28, 2014 at 20:30
  • @webXL unless there are examples of people having done so, I don't think the fact that it is easy to do it in some language means that the idea itself is non-obvious.
    – Jules
    Aug 29, 2014 at 3:05
  • @Jules I think you meant to write "the idea itself is obvious" since you started off with "don't think that". Yeah, I can see that, but applying read-only protection at the time of creation (by default) versus read-write at the time of creation is pretty obvious. It would be as if no one had ever thought to produce a shoe with synthetic leather and trying to patent that.
    – webXL
    Aug 30, 2014 at 0:36
4

ML has had immutable values (by default) since the early 70's. There are hundreds to thousands of commercial and academic dialects that have been made since then. Particularly relevant here is OCaml, which has "objects", with a keyword to enable mutability. A large percentage of all programming languages today are based on ML in one way or another.

Java (one of the world's most used programming languages) has objects and optional immutability through the "final" keyword. It existed since the early 90's.

In E, it's typical to construct "transitive immutable" versions of objects by pattern, but I can't remember if it has a particular construct to do this automatically.

More lately, Rust and Scala have immutable types with various mechanisms for qualification.

Improve this answer
4
  • 1
    Neither Java nor Scala have transitive immutability. If an immutable object points to a mutable one, the latter is still mutable even when accessed through the immutable reference.
    – Blaisorblade
    Aug 28, 2014 at 22:45
  • Well I didn't want to get into details, but each of the languages I mentioned has different ways of qualifying which parts of structures are immutable/mutable. In Java, a field declared as final, prevents it from being mutated. They can only be set within the constructor. In ML, all user defined types are immutable, but there are builtin mutable references that types can be constructed from. In OCaml, there is a mutable keyword. Is the question about a construct that given any arbitrary mutable type, it makes an immutable version of it? In that case, only Rust from my list would match.
    – Harold R. Eason
    Aug 29, 2014 at 1:28
  • 1
    IANAL, but my understanding is that you need prior art to match pretty tightly: arstechnica.com/tech-policy/2014/06/… (Jump to "Why did the examiner have to allow claim 3?" for the core, or read the whole story if that doesn't make enough sense).
    – Blaisorblade
    Aug 29, 2014 at 1:44
  • Yeah ok, I couldn't be bothered to read that patent, so I just listed stuff which probably matches (if none of them match, the patented idea is probably nonsense in the first place).
    – Harold R. Eason
    Aug 29, 2014 at 1:45
3

Perl's Moose object system has had immutability since 2010

http://search.cpan.org/~stevan/Moose-1.00/lib/Moose/Meta/Class.pm

Improve this answer
1
  • 1
    AFAICT from the (rather confusing) documentation here, the immutability provided is to prevent changes to the class definition (e.g. adding/removing methods) at runtime. Am I reading it incorrectly?
    – Jules
    Aug 29, 2014 at 3:09
3

I am unsure if that counts as prior art, but I once made a proposal to add transitive immutability to RedHat's new ceylon language.

It is available here (will no longer work easily):

https://github.com/simonthum/ceylon-spec/commits/immutable2

but it is fairly easy to see that it assigns an immutability category to every RVALUE and program construct (with the programmer able to declare if the default is not desired), checks if these match with the code, inheritance etc, and generates errors if mismatches are found.

The gist is in there:

https://github.com/simonthum/ceylon-spec/commit/3bd5f1af616b0973a1c4ca787693bf2a4e53fd5c#diff-f6110180082431fb2f6a437ba3e0d2b5R76

That amounts to transitive immutability, although the approach is finer-grained. I don't believe I could possibly be the first to execute this simple corollary of immutability in a mutable environment, but so far, it seems to me, no suggestions seem to have matched as well.

So, I don't know if my work counts (it was on github all the time, was publicly proposed to the ceylon team, but that may not be regarded enough), it never really worked, and is relatively new. I just hope it might help to fend off this silly patent.

Improve this answer
0

Clojure is mentioned in the es-discuss thread ES6,ES7,ES8 and beyond. A Proposed Roadmap. as having these features. It's functional but also has some imperative characteristics. Somebody knowing the language well could probably study the case and determine whether there's anything corresponding to the patent application's notion of safety (which seems to make sense only from an imperative point of view).

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .