Have a look at this: https://github.com/keean/Compositional-Typing-Inference
All parsers output typed fragments. Whenever there is a valid HM type for fragment, this system gives the same principle type, but it can also type open terms (which is a necessary for bottom up typing). In fact it can give a principle typing (note: different from a principle type) for any valid partial parse output. Keean. On 11 June 2015 at 14:21, Jonathan S. Shapiro <[email protected]> wrote: > So now that we contemplate a typed AST, we run into a new problem: how to > type the code emitted by the parser generator. > > If the parse algorithm is any of the "top down" family of algorithms (LL, > PEG, GLL, others), there's no problem. Each production can be implemented > as a procedure, and each procedure returns its result AST as a return > value. The reason this can be typed using a conventional static type system > is that we are't using a separate parse stack. > > But if the parse algorithm is one of the "bottom up" family of algorithms > (LR, GLR, others), the typing seems more complicated, because all of the > shift-reduce algorithms use a separate parse stack. > > The reason a separate parse stack is a bother is that a given "position" > in the parse stack can have distinct types over time as the parse tree is > constructed; we cannot assign any simple static type to a position. > Off-hand, I can't even see how to type the parse stack using dependent > types. I'm sure a way exists, and I'm pretty sure one of the type system > wizards on the list will promptly trot it out and say "it's obvious", but > I'm a simple-minded old-school hacker at heart, and it's not jumping out at > me. Sure, you can use a union type as your stack slot, but it seems > unfortunate to do that when the parse state already tells you what you need > to know. > > Thankfully, there are many reasons to prefer recursive-descent techniques > when they will solve your problem. Most notably error handling. But one of > the places where the shift-reduce approach is actually *better* is in IDEs. > In an IDE, you need to be able to deal with fragmented and/or incomplete > input. Think of it as parse subtrees interspersed with junk. Under those > conditions, the top-down approach simply doesn't work. > > You could, of course, make the parse stack element a union type, but then > you'd end up doing a lot of run-time type checking that you don't need to > do (because the parse state already encodes that). > > It dawned on me this morning that this is why most textbook presentations > of ASTs use a weakly typed AST structure: doing so preserves the ability to > use a separate parse stack. > > > It seems curious that when relative strengths of parsing strategies are > discussed, nobody ever talks about static typing. Or at least I've never > *seen* anyone do so. > > > shap > > _______________________________________________ > bitc-dev mailing list > [email protected] > http://www.coyotos.org/mailman/listinfo/bitc-dev > >
_______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
