Mutually recursive type

struct A
b::B
end

struct B
a::A
end

how to do this?

5 Likes

Hi Freddy and welcome!

fyi, dependent type means something else. What you’re trying are usually called mutually recursive types.

an internal constructor is the normal method.

julia> struct A{T}
           b::T
           A(x) = new{B}(x)
       end

julia> struct B
           a::Union{A,Nothing}
       end

julia> A(B(A(B(nothing))))
A{B}(B(A{B}(B(nothing))))

This is kind of a workaround until Julia gets forward declarations or becomes aware of mutually recursive types.

But it works. Let us know if you want further explanation of this idiom.

3 Likes

https://github.com/JuliaLang/julia/issues/269

Yes, it doesn’t work in this exact syntax. At the moment, you need a generic parameter and an internal constructor. It’s not ideal. Did my example not work for you? Do you need additional help? Give me a sign.

https://groups.google.com/forum/#!topic/julia-users/kVKUK3Hd6ok

it’s been 5 years! I asked the same thing.

I see your conundrum. I can’t make the syntax you want materialize because I’m not a core dev. I can only tell you what different syntax accomplishes the same thing, and it’s in the example I posted.

My impression is that this is more of an ideological issue than about solving a real problem–which isn’t to say it’s not important. Julia should be smart enough to handle mutually recursive types automatically, but it is possible to do what you want, just not in the way you want to write it.

2 Likes

Since you are presumably aware of the issue mentioned in that discussion and it is still open, it is not clear why you asked again.

4 Likes

A small off-topic comment, if I may.

There is a tension in open-source development that I see frequently. This thread is another instance of it. Some people tend to approach an open-source projects like one approaches the products of a private venture in a capitalist culture. They feel entitled to improvements, fast development, requested features… This of course causes some grief in developers, which don’t get payed for that work. I think it is very important to get people to understand the type of relation here. It is more like science than business. It’s important, I believe, to keep an attitude of respect and gratitude whenever offering criticism on an open-source project. It’s been 5 years, yes, probably for very good reasons. Probably because of the overwhelming weight carried by very few shoulders, while most of us stand aside watching and enjoying the result of their work. Usually, the work of open-source developers grows out of personal passion for the project. We don’t want to burn that passion down. Let them feel the love, please!

(End of rant.)

9 Likes

Alternatively, pay Julia Computing to do the work. Then, it’s more like a business than a science. :laughing:

2 Likes

If the forward declarations would be implemented, would this lead to longer compile times?

There are some “complaints” about the time it takes to the first plot already.

My naive thinking is, that forward declarations could double (or so) compile time therefor benefits and downsides must be balanced in this case.

1 Like

It definitely shouldn’t double compile-times, but it would probably add to them a little. My naive thinking is that you’d only have to pay for it if you’re using it. i.e. if you use an undeclared symbol while declaring a struct, the compiler will have to tuck it away for later and use it then.

Alternatively, the compiler could just postpone evaluation of the struct bodies until they are actually required, or until all top-level symbols in the module/script have been declared.

It shouldn’t be too expensive, if my musings are correct.

1 Like

I would think that would lead to infinite memory utilization, i.e struct A needs space for struct B which needs space for struct A and on and on?

Wouldn’t both of them need to be mutable so they become objects on the heap rather than stack to even begin to work? Like:

mutable struct A
    foo::B
end

mutable struct B
    foo::A
end 

I did run into something where I kind of wanted two objects to reference each other but I ended up doing:

struct C
    foo::UInt
end

struct A
    common::C
end

struct B
    common::C
end 

Which worked in my case.

This may be a little bit off-topic, but since the forward declaration is ubiquitously used in C, it’s a pain point when mapping such C struct to Julia. AFAIK, workarounds like struct A{T} cannot guarantee the underlying memory layout consistency between Julia and C.

No. Using a type parameter has nothing to do with the layout. It’s also not really a work around since it force you to explicitly introduce a break to the cycle. This does not matter much right now but if we ever going to allow non-pointerfree immutable types to be stored inline, such a property will be very important.

1 Like

no. mutability does not equal storage type of a field. At least one of A or B must not be stored inline but they could well be both immutable. That’s exactly why explicitly breaking the cycle is important if pointerfree-ness is uncoupled from field storage type since then the layout of the storage type will not depend on the type paramter

1 Like