Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.

Close

Immutability

2009-11-09
2013-05-28
  • Nice proposal in http://tecomp.sourceforge.net/index.php?file=doc/papers/lang/immutability.txt.

    Does this work with object tests (downcasts) as well? How are you sure that you cannot downcast a "readable T" to "T" if an "immutable T" is attached to it?

    What about inheritance. Is it possible to have

       class U inherit immutable T …. end

    ?

     
  • Helmut Brandl
    Helmut Brandl
    2009-11-09

    to your specific questions:

    <h2> Does it work with object test? </h2>

    Why not? What is the problem of writing

        rt: readable T
        …
        create {T} rt.make ( …. )
        if attached {T} rt as t then
            - this path is entered
        elseif attached {immutable T} rt as it then
            - this path is not entered
        end
        …
        create {immutable T} rt.make ( …. )
        - the if executed here would enter the elseif path

    <h2> Inheritance </h2>

    The declaration

        class C inherit immutable T … end

    shall not be allowed. Since a descendant has access to all attributes of its parents, it can change whatever it wants. The same applies to readable. However with generics it makes perfect sense to write

        class CG …. end

     
  • Sorry if I missed the obvious, but how does the compiler tell if a feature modifies the object, or not?

    Consider

    <code>
    class<br>
    T<br>
    <br>
    feature<br>
    reset<br>
    do<br>
    member.reset<br>
    end<br>
    <br>
    member: ANOTHER_T - Some type with 'reset' feature<br>
    <br>
    end<br>
    </code>
    In this example an object of type T isn't modified, technically speaking, if the reset feature is called, Yet one can argue it's definitely not the same object. How can a compiler tell?

    Regards,<br>
    David.

     
  • Helmut Brandl
    Helmut Brandl
    2009-11-10

    I have forgotten to specify that changing an object means to call commands with it as a target. An entity of type readable T or immutable T simply does not allow commands to be called. This can be checked by the compiler.

    If the designer of a class does not adhere to the command/query separation and allows modification of objects by queries, the object is not really immutable.

    Therefore your example above is safe. The feature "reset" of type "immutable T" or "readable T" cannot be called. The compiler does not let you do that.

    However you made a good point which I did not describe enough in the white paper as well. If an immutable object returns an attribute with a normal type (as your member: ANOTHER_T above), a client can get a reference to member and modify the member without any problems.

    Therefore the properties readable and immutable have to be deep. I.e. a readable expression can only return readable types and an immutable expression can only return immutable types.

    Then immutability/readability of a type generates a "closed" world.

     
  • Helmut Brandl
    Helmut Brandl
    2009-11-10

    I have added some more description to the paper. Hope that it is clearer now.

    Regards
    Helmut

     
  • Thanks for the clarification. The text at http://tecomp.sourceforge.net/index.php?file=doc/papers/lang/immutability.txt is unchanged for me, but no big deal I get the idea.

    Three things:

    1) You might want to consider making some commands available: creation procedures. I'm not saying they should or shouldn't be available, I'm just opening a new avenue for discussion.

    2) Prohibiting commands can be to restrictive in some cases. Take the LIST class from EiffelStudio for instance. It has some features for parsing elements in the list: start, forth, exhausted. An immutable list can't be parsed this way, you get to use at(i:INTEGER) or stuff like that.

    I blame the designer of LIST, but the library is there and you know the story about existing code base.

    Bottom line is, some queries can't be done without commands.

    3) What about

    <code>
    class CG<br>
    feature<br>
    x: T - Can I do that?<br>
    y: readable T - Or that?<br>
    …<br>
    </code>

    This looks valid to me, but immutable T conforms to readable T and not the other way around, so it's some twist that couldn't be done before.

    Regards,<br>
    David.

     
  • Helmut Brandl
    Helmut Brandl
    2009-11-10

    ad 1) Clearly, creation procedures shall be availalbe. Otherwise it were not possible to create immutable objects. I don't  consider creation as a modification.

    ad 2) The problems of internal cursors….. I don't know how to solve this problem. But I am not very concerned about it either. I want to find a way to statically verify assertions. If the concept of immutability helps to achieve that, maybe the internal iterators of LIST are no longer necessary. But I don't know a way on allowing some commands on immutable objects and some commands not. start and forth are definitely state changing commands which modify the list (not the content, but the cursor) and item will return different values after each call to forth.

    ad3) I didn't get the point. If you define

        class CG ….

    then the class can declare attributes of type T without any problems. But usually CG will not declare attributes of type T but of type G. And since G is constrained to immutable types, any attribute of type G is immutable (e.g. the keys in a HASH_MAP).

    Can you explain your concern again?

     
  • Forget about 3), I shouldn't be posting at 3am. :)

    I think this could create a whole new class of CAT calls, but they can probably be detected as easily as others, and not happen with good design.

    Regarding 2), if the new syntax can't accomodate existing libraries, or provide benefits sufficiently compelling to suggest a modification of these libraries, then it has low chances of success.

    Like you described in your paper, a class can be redesigned and be split in 3 classes that each provide the appropriate interface, don't create backward compatibility issues, and don't change the language. It's a huge effort, but it works.

    I'm not a fan of new keywords, but you could add something like the 'query' keyword to mark a feature as immutable (even though it's a command). After all, such occurence should be rare.

    Regards,<br>
    David.

     
  • Helmut Brandl
    Helmut Brandl
    2009-11-10

    ad 2) The concept does not invalidate existing code.  LIST can be used as before. But if you have an immutable LIST, you cannot call features like start and forth on it. If some queries of LIST use that features, they change the object. But you can use them on immutable objects, because immutability just means "no commands possible". If a query internally uses start and forth and restores the original values at the end, there is no problem. Queries can be called on immutable objects. Fullstop. If the query is not designed with CQS, the compiler has currently no chance to detect that.

    For a verifying compiler it should be possible to check, if a query of LIST restores the original value of the cursor after iteration (and asserts that in its postcondition).

    This is the base of comand query separation. Queries should not have visible side effects. But the compiler currently does not enforce it.

     
  • I'll set aside the issue with LIST for now.

    I assume we can use immutable types as parameters of a feature? If so, consider:

    <pre>
    myquery(x: immutable T): BOOLEAN
        do
            - Some stuff wih x here
        end

    test
        local
            callresult: BOOLEAN
        do
            callresult := myquery(global)
        end
       
    global: T - Created somewhere

    </pre>
    Am I correct if I say that, in myquery, global becomes x by a conversion?

    This is from your text:
    <pre>
    - conversions
         t  := it            - attach deep_twin of `it'  to  `t'
         it := t             - attach deep_twin of `t'  to  `it'
    </pre>

    If so, myquery could just call deep_twin explicitely:

    <pre>
    myquery(x:T): BOOLEAN
        local
            x_converted: T
        do
            x_converted := x.deep_twin
            - Some stuff with x_converted here
        end
    </pre>

    In this case there is no performance gain.

    You mentioned the following in a post above:<br>
    <i>The declaration</i>
    <code>
    class C inherit immutable T … end
    </code>
    <i>shall not be allowed</i>

    So, really,

    <code>
    class CG
    </code>
    means
    <code>
    class CG
    </code>

    Applying to HASH_MAP we have:

    <pre>
    class
    HASH_MAP

    feature
    extend(value: VALUE; key: KEY)
        do
            - insert value and key
        end
    - Rest of HASH_MAP
    end

    class
        SOME_CLASS
       
    feature
    hash_table: HASH_MAP[ARRAY,STRING]

    test
        local
            value; ARRAY
            key: STRING
        do
            create value.make_empty
            key := "foo"
            hash_table.extend(value, key)
        end
    end

    </pre>

    For hashtable KEY is the immutable version of STRING, and any call to extend does a deep_twin of arguments. There is no performance gain.

    Now, let's say there is no conversion from T to immutable T, and one can use a reference to T as a reference to immutable T directly. Notice that in my example, global is not a local object but an attribute of the class. It could be modified outside myquery in a separate thread. Indeed, it's often an issue when dealing with attached/detached references. How do immutable types behave with respect to multi-threading?

    Regards,<br>
    David.

     
  • Sorry about formatting, it looked ok when I hit enter,  no clue what happended then.

    Regards,<br>
    David.

     
  • Helmut Brandl
    Helmut Brandl
    2009-11-12

    Sorry David for the delay in the response and thank you for your
    discussion. Your points are rather good and help me to think more
    about the details and impacts of such a language extension.

    ## Your example

    In your statement

         callresult := myquery(global)

    global gets converted to immutable T by deep twinning.

    I'll come to the performance aspect later.

    ## Main motivation

    The main motivation of the proposal is to write correct SW with
    respect to invariants of a class. Whenever you have an imported
    object (i.e. received from clients) in your invariant, you can
    specify the object to be immutable. The compiler does all the
    necessary conversions for you.

    You can achieve the same by calling deep_twin explicitely. But
    having marked an entity as immutable, the compiler does the job
    for you and you cannot forget to do the conversion.

    The object can have queries giving its clients access to the
    objects within the invariant. But the access to the objects is
    via immutable references. No deep twinning is necessary
    here. Since the clients cannot change (i.e. call commands on)
    immutable entities, the invariant is protected.

    ## Performance aspects

    Even if the main motivation for the proposal is not performance
    improvement, there is plenty of room for performance gains.

    First of all objects can be created as immutable from the
    beginning. I assume that manifest strings e.g. could have the
    type "immutable STRING". Or you can create the objects via

        key: immutable KEY
        …
        create key.make( …. )      - object is created as immutable,
                                     - no conversion needed here
       
        hash_map.extend(value, key)  - no conversion needed here either

    Even if the received objects are not immutable, the conversion
    needs to be done only once. Once in the "immutable world" no more
    conversions are necessary. E.g. the HASH_MAP can have an
    iteration facility letting you iterate over all the key value
    pairs. Any query returning a key will return it as immutable
    KEY. No conversion necessary here.

    The compiler can optimize more aggresively. If you create a
    mutable object just for passing it to a class as immutable and
    the mutable is no longer used, the compiler can squeeze out the
    conversion, because it is not necessary.

    ## Syntax

    The syntax may not yet be optimal. I've just proposed a syntax to
    discuss the concept. However I would stick to the form

        class CG ….

    which is consistent with the already existing

        class CG

    This syntax specifies the constraint that all actual generics
    must be immutable and the class definition of CG can rely on this
    fact.

    ## Concurrency

    I have not yet analyzed the impacts on concurrency. But
    immutability shall help here as well, because no thread can
    modify an immutable object.

    But there is a "however". Immutability in the sense of my
    proposal is not semantically immutability in all
    aspects. Immutability just means the inability to call commands
    on immutable objects. You still can design queries which do
    modify the internal state (e.g. caching some results). That would
    case problems with concurrency.

     
  • About concurrency, my concern was only if you could have two references to the same object, one normal and one immutable. But it's not the case, so normal rules apply.

    It looks like all my questions are answered, I'll post if something else comes to mind.

    Regards,<br>
    David.