On Sat, May 30, 2015 at 11:40 AM, Jonathan S. Shapiro <s...@eros-os.org> wrote: > 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:
Maybe we had a misunderstanding. The Node<_> solution I gave a week ago is something that I believe can already be applied in pertty much any language with generics. (But it seems useful primarily when you don't have subclasses, since subclasses already let you factor out common fields to the superclass.) So BitC will automatically have a statically-checked solution to your problem, one way or another. > 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. I like this. I figure the only reason why you wouldn't want this is that invariant parts impose constraints on the layouts of the leg records. With invariant parts that are not all at the front, you cannot find a layout for the legs independently. This would not be problematic though if the programmer dictates the layouts, and BitC just checks that they make sense together. But you probably know all about this, so I don't have a problem with it if you don't. > 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> I think this is my Node<_> idea. > What happens here is that the recursiveness of the type gets "threaded" > through the AST type by means of the parameter type. Sure, but that's not a new thing. We've all "threaded recursiveness" through pair, function, and probably collection types before, right? Recursive types wouldn't be so useful if they couldn't use existing type constructors! :) You don't need to do anything special when defining "AST"/"Node" in order it thread recursiveness through it later. (Actually though, in total languages (e.g. proof assistants), you do need to be careful which type constructors you "thread recursiveness through". It's not always allowed. But languages with ordinary recursive types give up totality, and all definable type constructors are "threadable".) By "thread recursiveness" through a type constructor, we mean pass a recurrence (a reference to something currently being recursively defined) to the type constructor, I assume. > 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. If you have subtyping like that, then couldn't you just define the invariant fields in ASTTree, and they'd be inherited by every leg? No need to factor using parametric polymorphism if you want subtype polymorphism anyway... > 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? Yes and no. AST<T> doesn't depend on ASTTree, so the definition of AST isn't part of the recursive definition. AST< T <: ASTTree> does depend on ASTTree, but that's just because we plugged it in ourselves. > 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. I think you took my solution as some fancy new language idea, but it isn't. It's just a trick people can already use in existing languages with generics. _______________________________________________ bitc-dev mailing list bitc-dev@coyotos.org http://www.coyotos.org/mailman/listinfo/bitc-dev
