generation of self-referential immutable types in Julia

Question

Julia lang documentation explains how inner constructors and the new() function can be used to construct self-referential objects:

  type SelfReferential
      obj::SelfReferential
      SelfReferential() = (x = new(); x.obj = x)
    end

However this approach does not work for immutable types, because it essentially uses mutation of the incompletely initialized instance x.

How can I generate a self-referential immutable object in Julia?

Answer 1

Since you seemed to have used Haskell before, I will tailor this answer from a functional programming perspective. A common use case of self-referential immutable types is in creating a lazy list.

As a strict (i.e. not lazy) language, it is not possible for an immutable object to directly reference itself.

This does not preclude, however, referencing itself indirectly, using a mutable object like a Ref or Vector.

For the particular case of lazy structures, I might recommend confining the mutability to a special object, say, Lazy{T}. For instance,

import Base: getindex
type Lazy
    thunk
    value
    Lazy(thunk) = new(thunk)
end

evaluate!(lazy::Lazy) = (lazy.value = lazy.thunk(); lazy.value)
getindex(lazy::Lazy) = isdefined(lazy, :value) ? lazy.value : evaluate!(lazy)

Then, for instance, it's possible to make a simple lazy list as follows:

import Base: first, tail, start, next, done, iteratorsize, HasLength, SizeUnknown
abstract List
immutable Cons <: List
    head
    tail::Lazy
end
immutable Nil <: List end

macro cons(x, y)
    quote
        Cons($(esc(x)), Lazy(() -> $(esc(y))))
    end
end

first(xs::Cons) = xs.head
tail(xs::Cons) = xs.tail[]
start(xs::Cons) = xs
next(::Cons, xs) = first(xs), tail(xs)
done(::List, ::Cons) = false
done(::List, ::Nil) = true
iteratorsize(::Nil) = HasLength()
iteratorsize(::Cons) = SizeUnknown()

Which indeed works as it would in a language like Haskell:

julia> xs = @cons(1, ys)
Cons(1,Lazy(false,#3,#undef))

julia> ys = @cons(2, xs)
Cons(2,Lazy(false,#5,#undef))

julia> [take(xs, 5)...]
5-element Array{Int64,1}:
 1
 2
 1
 2
 1

This functionality may seem complex, but it luckily has already been implemented in Lazy.jl.

---

It is important to note that the above code creates a lot of overhead due to type instability and mutable types. If your goal in using immutable was not expressiveness, but rather performance, then obviously such an approach is not appropriate. But it is in general not possible to have a stack-allocated structure that references itself, so in cases where you want maximal performance, it's best to avoid self-reference entirely.