implement immutable types

[StefanKarpinski]

The conclusion of our last discussion on immutability versus mutability was that it is largely a psychological distinction:

• when an object is identified by its value, then it should be immutable: integers, floats, complexes, strings;
• when an object is a container, whose identity can remain the same while its contents change, then it should be mutable: arrays, linked list nodes, tree nodes.

To declare that a new concrete type is immutable, prefix its declaration with immutable:

immutable type Complex{T<:Real} <: Number
  re::T
  im::T
end

Alternately, only the immutable keyword could be used:

immutable Complex{T<:Real} <: Number
  re::T
  im::T
end

[ViralBShah]

I was unaware of the importance of this until Stefan pointed this out to me:

julia> a = Complex(1,1)
1 + 1im

julia> b = a
1 + 1im

julia> a.re = 2
2 + 1im

julia> a
2 + 1im

julia> b
2 + 1im

[StefanKarpinski]

Note: I proposed that Immutable could be an abstract type in this email thread. Jeff seems hesitant about this idea and no conclusion was reached.

[JeffBezanson]

I have a plan. Complex numbers are important for 1.0; we especially need them for FFTs and the LAPACK interface. And we need to at least match the capabilities of matlab, octave, fortran, etc. Therefore I'm going to try to define Complex64 and Complex128 as bits types, which will give us the packed arrays, immutability, and performance we need. Complex{Foo} can wait for 2.0.

[StefanKarpinski]

Ok, that's definitely a plan. I think the packed arrays are much more important than the immutability. For v1.0 we can just say "don't mutate complex numbers" and leave it at that. Any chance we can do it that way?

[JeffBezanson]

Yeah, this way complex will work like other numeric types, in julia as well as other languages. You won't be able to mutate it or access fields with dot syntax. And we can already stack allocate bits types, so we could get some great performance. Only downside is you can't have complex with arbitrary component types, but that doesn't have many use cases. But, it's easy to define new complex types in julia.

[StefanKarpinski]

Can we can keep Complex{T} and have Complex64 and Complex128 as special types that implement the same basic functionality but more efficiently? Also, should those be called Complex32 and Complex64 instead? I know they have twice that many bits, but you could argue that the naming is after the size of each part, not the total.

[JeffBezanson]

Yes, we can keep it (maybe at the cost of some confusion), and the complex math routines can be made generic enough.
I think the names should refer to the total size of the type, like complex*16 in fortran.

[BinarySplit]

I feel there is a need for this, if only to restrict hashing to immutable values in the same way that Python does.

Take this example:

julia> a = [1]; b = [2]; c = {a=>"one", b=>"two"}; a[1] = 2; b[1] = 1; c
{[1]=>"two",[2]=>"one",}

julia> c[[1]]
key not found: [1]
in ref, /home/lachlan/julia/j/table.j:19

julia> c[a]
key not found: [2]
in ref, /home/lachlan/julia/j/table.j:19

julia> c[[1]] = "ONE"; c[[2]] = "TWO"; c
{[1]=>"two",[2]=>"TWO",[2]=>"one",[1]=>"ONE",}

If the hash function is only defined for immutable types by default, then potentially confusing/error-prone situations like this could be avoided. I would be forced to use tuples instead of arrays for my hashtable keys.

Apologies in advance if I am joining an already decided conversation. I can't see the linked discussion threads in the julia-math Google Group as I am not a member.

[JeffBezanson]

Yes, technically you are right on this. I'm familiar with http://home.pipeline.com/~hbaker1/ObjectIdentity.html.

Computing hash values of arrays, and comparing arrays both make sense, but not using them as table keys. In fact the only use that comes to mind is memoizing certain kinds of functions. But if a memoizer copied arrays before using them as keys, it would be safe in practice. Disallowing that seems too strict.

[StefanKarpinski]

There's also issue #359, which proposes using const fields to express fine-grained immutability. I fully immutable object would be one in which all fields are const. I think that copying non-const objects upon insertion into a hash is a pretty reasonable way to go. Of course, you can still iterate the keys and then modify the copied key, which might be even more confusing. In order to really solve this, we would need immutable versions of all types :-/

[khinsen]

I believe that immutable data structures are very important for writing robust code and become even more important when parallel programming is taken into account. The functional programming community has made this point quite clearly.

What I think a modern programming language should have is the possibility to define fully immutable data structures, including immutable container types, with the possibility to test at compile time (through the type system) and at runtime if a given piece of data is immutable. Immutable container types can be implemented efficiently using persistent data structures (check out the Clojure language (http://clojure.org/) for a real-life implementation). A fully immutable data structure is an immutable whose fields (for structure-like types) and/or elements (for container types) are immutable as well.

The advantage of immutable data structures is that they can be safely passed around between functions and concurrent tasks, stored in files or sent over the network, without anyone being able to mess them up, not even accidentally. For an extended argumentation, see http://doi.ieeecomputersociety.org/10.1109/MCSE.2012.11 (ask me for a copy if you can't access it).