[swift-evolution] Inconsistencies in recursive types

[Tony Allevato]

On Mon, Mar 13, 2017 at 6:38 AM Dimitri Racordon via swift-evolution <
swift-evolution at swift.org> wrote:

> Hello swift-evolution,
>
> I noticed there’s some inconsistencies with recursive types and how the
> compiler handles them. Consider the following cases:
>
>
> *1. Swift is right to refuse compiling this, since there’s no way to
> initialise an instance of `First `:*
>
> struct First {
>     let item: First
> }
> // Error: Value type 'First' cannot have a stored property that references
> itself
>
> However, the message suggests more a compiler limitation rather than the
> actual impossibility to initialize the declared type.
>
>
> *2. Swift is also right not to compile this, but the error messages are
> even less insightful:*
>
> struct First {
>     let item: Second
> }
> // Error: Value type 'First' cannot have a stored property that references
> itself
>
>
> struct Second {
>     let item: First
> }
> // Error: Value type 'Second' cannot have a stored property that
> references itself
>
> The problem isn’t that the value types reference *themselves*. Instead,
> the problem is that there’s a cyclic dependency between `First` and
> `Second` that makes it impossible for neither of these structures to be
> instantiated.
>
>
> *3. Swift should let me do that:*
>
> struct First {
>     let item: First?
> }
>
> The compiler prevents me to declare the above struct, even if there
> actually is a way to initialise an instance of `First` (e.g. `First(item:
> nil)`). The message is identical to that of case #1 (maybe it actually
> *is* a compiler limitation after all?)
>

The problem with this example is that since Optional<T> is a value type (an
enum), this is a value type that is recursive upon itself. Until indirect
struct fields are possible, this can't be supported—there's *one* valid way
to instantiate it without recursion at runtime, but the compiler can't know
what you might try to pass in there, nor can it (I believe) compute the
layout of that type because of the potential recursion.


>
> *4. Swift shouldn’t compile this:*
>
> class First {
>     let item: First
>     init(item: First) {
>         self.item = item
>     }
> }
>
> Like in case #1, there’s no way to instantiate `First`. The fact that it’s
> a reference rather than a value doesn’t change the problem.
>
>
> *5. Similarly to case #4, Swift shouldn’t compile this:*
>
> indirect enum First {
>     case item(First)
> }
>
>
Re: #4 and #5, I've been pondering the same thing lately because I've been
tinkering with an implementation of auto-deriving Equatable/Hashable for
enums in my spare time, and I've been using recursive cases like this to
test edge cases. For something like #5, I can generate the bodies of == and
hashValue, but what good are they for a type that you can't actually get
values of?

In general, having noninstantiable types is good—caseless enums are useful
as a way of namespacing static members. But in the specific case where a
type is impossible to instantiate because of infinite recursion, a compiler
diagnostic sounds like a good idea. I'm trying to think of situations where
that would be valid and someone would need that functionality, but I'm
coming up blank. But, I'm no expert on type systems.



> *6. Cases #4 #5 could be written like case #2, and should also raise
> compilation errors.*
>
>
> Does someone know if these issues have already been discussed and/or
> addressed?
>
> Thanks,
> Dimitri Racordon
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170313/4f8a98da/attachment.html>