Julep: More support for working with immutables

[Keno]

This Julep is motivated by the current difficulties of working with immutables, particularly tuples. This issue aims to capture the result of the JuliaCon discussions between @JeffBezanson @carnaval @vtjnash @yuyichao and myself.

Working with tuples as fixed size arrays is currently quite cumbersome, particularly because they are hard to construct (since they can't be changed after constructing). To address

setindex! on a Ref

Ref creates a mutable container around an immutable object. This allows us to create changed immutables by putting them inside a Ref, modifying them in place and then pulling the changed value out. To support this, we can defined setindex! on Ref, giving it an index chain to modify, e.g.

ref = Ref{Tuple{Tuple{Int32,Int64},Int64}}(((1,2),3))
ref[1,1] = 4
@assert ref == ((4,2),3)

On tuples, this should generally be lowered to an appropriate getlementptr and store (assuming the tuples are on the stack) or an appropriate insertelement. This would allow construction of long tuples as follows:

ref = Ref{NTuple{1000,Int64}}()
for i = 1:1000
    ref[i] = i
end
return ref[] # This is now our constructed tuple

Complications with general immutables

This syntax should eventually also extend to generic immutables, but that need not be part of the initial implementation:

immutable foo
y::Int64
end
immutable bar
x::foo
end
ref = Ref{bar}()
ref[:x,:y] = 4
ref[] # bar(foo(4))

However, semantically, we do not want to allow setting arbitrary fields in immutables, because those immutables may then no longer obey invariants imposed by the constructor. To properly support this use case, we propose lowering the above ref[:x,:y] = 4 as (semantically at least)

ref[] = setindex(ref[],:x,setindex(ref[:x],:y,4))

where setindex is a new generic function that creates a copy of the passed in first argument but modifying the identified field to the given new value. To support this in general, a default version of setindex would be created by default unless an inner constructor is specified (i.e. the same way in which default constructors are currently created). People needing to enforce invariants on their immutables would then be expected to provide a method of setindex (perhaps defining it within the type block to get access to new), that checks that the appropriate invariants are maintained. Additionally, setindex would support a field index as a second argument, as well as providing a definition that takes keyword arguments and semantically applies setindex several times to change all arguments.

[tkelman]

Is it wise to rush another new language feature into 0.4 at this point?

[quinnj]

There was some consensus that the more-minimal tuple implementation could be 0.4 material while the rest could be done later.

[ViralBShah]

Is this something that will happen in 0.4?

[mturok]

I just saw this issue, and I'm a bit unclear.

Are we talking about breaking the immutability promise by updating in place, and not immutability as per Haskell? (https://wiki.haskell.org/Functional_programming#Immutable_data)?

Wouldn't we instead want an efficient immutable class - https://en.wikipedia.org/wiki/Persistent_data_structure

Thanks,
Michael

[carnaval]

it only breaks immutability in the implementation, as an optimization. You could implement this feature by copying the whole object so it does not "observationaly" break the immutability contract.

[c42f]

Over at FixedSizeArrays.jl we're fiddling with a multidimensional analog of the proposal above: I want to slice arrays of immutables along dimensions of the immutable fields.

Minimal example:

using FixedSizeArrays

immutable Vec2{T} <: FixedVectorNoTuple{2, T}
    x::T
    y::T
end

# using my hack from SimonDanisch/FixedSizeArrays.jl#59

julia> v = [Vec2(i,j) for i = 1:4, j = 1:4]

julia> v[:x, :, :]
4x4 Array{Int64,2}:
 1  1  1  1
 2  2  2  2
 3  3  3  3
 4  4  4  4

This brings up some questions about the above proposal.

1. The proposed ordering of the index chain in ref[1,2] makes sense when considering a single immutable, but is backward relative to the memory ordering of multidimensional arrays, where the first index varies fastest in memory. I'm not sure there's anything satisfying that can be done about this but it seems an unfortunate overloading of indexing notation if we ever want to generalize to more than zero dimensions.
2. How would the lowering of ref[:x,:y] = 4 into something like ref[] = setindex(ref[],:x,setindex(ref[:x],:y,4)) work? It seems like the parser has no syntactic hint about when to generate this vs the usual lowering to setindex!? For distinguishing between slicing along the fixed vs variable dimensions of an Array{M} with M<:FixedSizeArrays.Mat, I managed a macro @fslice which uses abuses semicolons inside the square brackets, thus, for example, @fslice a[:,:; 1,1] = 10. Unfortunately the associated ref[:x,:y;] looks rather ugly. For distinguishing between slicing along combined vs normal array dimensions, we have @fslice in FixedSizeArrays now thus: @fslice a[:,:,1,1] = 10

I'd be really excited to get some kind of "struct slicing" as a first class concept in julia, because it'd provide a bridge between the worlds of struct-of-array vs array-of-struct memory layouts. In other languages I've used it's generally quite a pain to convert between these two.

[mason-bially]

I'd be really excited to get some kind of "struct slicing" as a first class concept in julia, because it'd provide a bridge between the worlds of struct-of-array vs array-of-struct memory layouts.

👍 to that!

[JeffBezanson]

Needs more work that we don't feel we have time for in 0.5.0.

[andyferris]

This has a 0.6.0 milestone attached... out of curiosity, is this likely to be looked at before the new-year's cutoff?

[Keno]

I'd like to at least have a design in the 0.6 timeframe. The above design doesn't quite feel right yet.

[andyferris]

OK cool, thanks for the update. This is one of those things that I'm really looking forward to :)

[Keno]

As much as I hate to say this, it's a feature. Still possible to do before 1.0 of course.

[AriMKatz]

Lens based approach to this which works pretty well : https://github.com/JuliaObjects/Accessors.jl

@tkf does accessors have any implications also for #31630 ?

[tkf]

cc @jw3126

I'd consider Accessors.jl (and its predecessor Setfield.jl) is strictly more powerful than the approach discussed here. The primary reason is that lens-based approach let us change the type of the field. For example, as I illustrated in Taking a derivative of nested object using lens from Setfield.jl - General Usage - JuliaLang, it can be used for taking derivative of nested field using ForwardDiff.

Decoupling the notion of "nested field location" from the object itself is also very useful. A nice use case is again with AD since it can be used for specifying differentiation "with respect to what." For example, I've used it Bifurcations.jl for specifying the target parameter of the model. It can also be used for reparametrization in an algorithm-agnostic manner (i.e., Kaleido.jl and Bifurcations.jl do not "know" each other).

Furthermore, it is straightforward to derive the ref-based approach based on lens. See Mutabilities.meltproperties https://github.com/tkf/Mutabilities.jl.

That said, I understand that the compiler support can be useful for generating pointer-based manipulation that is more LLVM friendly in some situations. I think it'd be great if we can incorporate Accessors.jl's approach in a way that the compiler can handle some optimizable cases.