Mutually recursive types v3

rectypes.md

This is a writeup of a proposal for mutually recursive type declarations. This has some history. The original issue here is JuliaLang/julia#269. There were previous attempts in JuliaLang/julia#32581 and JuliaLang/julia#32658.

General proposal overview

The general idea is to have a scoped declaration syntax for recursive types:

recursive type Edge
	struct Node
		edges::Vector{Edge}
	end

	struct Edge
		nodes::Vector{Node}
	end
end

Semantically, all struct declarations inside a recursive type block create IncompleteStruct types. There are also IncompleteUnion and IncompleteUnionAll types. apply_type inside recursive type blocks is extended to be able to produce these from the ordinary syntax.

Finally, constant assignments inside these blocks are deferred until the end of the block and executed atomically, i.e. the above is semantically lowered to:

let Edge = IncompleteStruct()
	Node = IncompleteStruct(svec(apply_type_or_incomplete(Vector, Edge)))
	Edge = IncompleteStruct(svec(apply_type_or_incomplete(Vector, Node)))
	(Node, Edge) = resolve_incompletes(Node, Edge)
	multi_decare_const(GlobalRef(@__MODULE__, :Node), Node, GlobalRef(@__MODULE__, :Edge), Edge)
end

This is semantically more similar to #32658 than #32581. However, there are also some important differences:

1. Rather than having a single Placeholder type and using the ordinary type data structures, there is a complete separate hierarchy of incomplete types. The idea is to restrict what operations can be done on incomplete types to only those that explicily opt in to handle incomplete types.

2. There is syntactic structure to the intended lifetime of the incomplete types. In particular, they are not supposed to really escapet the recursive type block (it would be legal and well defined for them to do so, but it shouldn't really happen in day-to-day work). A particular motivation for this is to properly encode the intended replacement semantics for Revise. If the assignment to the recursively defined types is not atomic (with respect to world-age), it becomes ambiguous whether a changed definition is a linear extension of the previous recursive type nest or intended to replace the entire recursive structure. The proposed structure makes this semantically unambigous.

What's the stance on recursive Union types and recursive type bounds?

recursive type JSONObject
    const JSONObject = Union{
        String,
        Float64,
        Int64,
        Bool,
        Vector{JSONObject},
        Dict{String, JSONObject}
    }
end

recursive type Foo
    struct Foo <: AbstractIterable{Foo}
        # ...
    end
end

These are pretty complicated type-theoretically, so I think that we'd want to forbid them (they are beyond what inference / subtyping / dispatch can understand today)

Nonetheless, it would be nice to know that the semantics support this if we want to do them one day.

Syntactically allowed, but for now probably an error at resolve time.