I want to try to "unpack" something I hinted at the other day in the AST thread. This may be a well-known thing that I simply haven't stumbled across. It could also just be a bad idea.
Original problem: I want to build an AST in which the parent/child constraints are described by statically described type relations in a closed union. There are many **non-variant** fields to this AST. There appears to be no good way to describe this type in languages that cleanly separate product, record, and union types. So far as I can tell, the possible solutions are: 1. Add an element to every union leg for the non-variant part. 2. Make the union an element of the non-variant part, and check for sanity dynamically (e.g. using a checking procedure). >From a language design perspective, there seem to be two possible ways to deal with this sort of pattern: 1. Allow non-variant fields The first - the simple one - is simply to allow unions to have non-variant parts. Semantically, this is the same as adding a "reference to invariant part" to every leg, but it is textually much simpler. Because it's simple, it's probably the right approach for now, and I think it's generally useful to have non-variant parts mixed with variant parts. There are some examples of data structures in C that exploit the absence of tags to do something even more interesting: specify variant parts that are *intermingled* with the non-variant parts. Usually this is done for the sake of layout, or for the sake of matching some externally specified message layout. Once again, I don't think this changes the semantics of union types. 2. Support type-indexed types explicitly This approach is suggested by the AST<T> idea that somebody put forward. The idea here is that T is a leg type of some union. So AST<T = expr> might have a field "children: T", and the corresponding union leg definition might be something like: union ASTTree .... expr : e1 : AST<mulexpr>, e2 : AST<mulexpr> What happens here is that the recursiveness of the type gets "threaded" through the AST type by means of the parameter type. Depending on your point of view, the AST.expr field can be viewed has having type "expr" (which is a leg type of ASTTree) or might have type ASTTree. In this intuition, I'm viewing "expr" as a subtype of ASTree. The two parts of this that are a bit unusual are that the type AST< T <: ASTTree > and the type ASTTree are co-recursively defined, so we probably end up needing something similar to letrec for this definition. Perhaps typerec? Anyway, this is the general sort of intuition that I was groping for. I wanted to describe it a bit more clearly so that people could ponder it and react if they wish. shap
_______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
