-
Notifications
You must be signed in to change notification settings - Fork 7
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
General-purpose AST reflection #212
Comments
Hi Lucas,
Thanks for looking into this. I'll look this over, and past notes from
you, and let you know what I think.
Cheers,
Eric
…On Fri, Dec 15, 2017 at 1:52 PM, Lucas Kramer ***@***.***> wrote:
Overview
I am proposing that we add a general-purpouse AST reflection library to
Silver. This would be useful for implementing embedded host-language AST
literals (#194 <#194>), and may
find other uses as well.
Essentially, I am proposing something sort of like hackUnparse, except
that it outputs a generic tree structure instead of a string.
closed nonterminal AST with pp;
abstract production nonterminalAST
top::AST ::= prodName::String children::ASTs annotations::NamedASTs
{}
abstract production listAST
top::AST ::= vals::ASTs
{}
abstract production stringAST
top::AST ::= s::String
{}
-- Etc...
nonterminal ASTs with pp;
nonterminal NamedASTs with pp;
-- All the expected cons and nil productions here
nonterminal NamedAST with pp;
abstract production namedAST
top::NamedAST ::= n::String v::AST
{}
It would also be possible to designate certain types occuring in the tree
that should not be reflected, but instead placed directly in the result
tree.
nonterminal ASTProd;
abstract production astProd
top::ASTProd ::= prod::(AST ::= a)
{}
-- Foreign function
function reflectAST
AST ::= escapes::[Pair<String ASTProd>] value::a
{}
escapes here is a list of pairs of the names of types to escape from
reflection and wrapping bridge productions for them. Note that the ASTProd
nonterminal is effectively like a newtype in Haskell, since the
productions in escapes vary in type.
Example
grammar example:abstractsyntax;
nonterminal Expr with ...;
abstract production fooExpr
top::Expr ::= a::Expr b::Foo c::Decorated Bar
{}
abstract production bazExpr
top::Expr ::= prod::(Expr ::= Expr)
{}
nonterminal Foo with ...;
nonterminal Bar with ...;
-- A bunch more productions here
abstract production fooAST
top::AST ::= f::Foo
{}
abstract production decBarAST
top::AST ::= b::Decorated Bar
{}
abstract production unaryProdAST
top::AST ::= prod::(Expr ::= Expr)
{}
-- A production body somewhere
local ast::Expr = ...;
local reflectedAST::AST =
reflectAST([
pair("example:abstractsyntax:Foo", astProd(fooAST)),
pair("Decorated example:abstractsyntax:Bar", astProd(decBarAST)),
pair("(example:abstractsyntax:Expr ::= example:abstractsyntax:Expr)", astProd(unaryProdAST)]);
Implementation
The implementation is essentially straightforward: a map is built of all
the escaped types and their bridge productions. A recursive foreign
function somewhat similar to hackUnparse will then transverse the tree,
first checking if the object has a type name in the map and if so applying
the associated production, or otherwise recursively transforming any
children and applying the appropriate default production.
A few things to resolve here:
- We need some way of getting the name of any type as a string. I
suggest that we add an interface TypeNamed to the runtime with a
method String getTypeName(), implemented by Node, DecoratedNode,
NodeFactory, ConsCell, StringCatter, IOToken, etc. The generated
translation for a nonterminal would provide an implementation for this
method. Foreign types could implement this interface as well, or otherwise
an error would be raised on encountering a foreign type not implementing
the interface.
- For reflecting the values of annotations, we need some general way
of finding and accessing all annotations for a nonterminal in a generalized
way. I suggest that we add abstract methods String[]
getAnnotationNames() and Object getAnnotation(final String name) to
the Node class, which would have implementations generated in each
nonterminal class.
- I'm not sure how to best handle type-parametric nonterminals. One
option I guess would be to leave the implementation of getTypeName to
the generated production classes, and generate code to infer the type
parameters from the types of the children. Initially though we can probably
just not support escaping type-parametric nonterminals.
@tedinski <https://github.com/tedinski> @ericvanwyk
<https://github.com/ericvanwyk> Thoughts on this? I'll probably start
working on implementing this in the next week or so if there aren't any
major objections.
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
<#212>, or mute the thread
<https://github.com/notifications/unsubscribe-auth/ADOhdwxOlA0WOtV0-_teJLWrJDaPdblAks5tAs4bgaJpZM4RD7Yk>
.
|
Hi Lucas, I'm a bit confused by this. It isn't clear why we need a new As I understand things, we want to run some version of an ableC parser on a string, giving us a tree with some ableC type. Perhaps while(..., ....) as an ableC:Stmt typed value. But what we need is a Silver tree: applicationExpr(baseExpr(qNameId(nameIdLower(terminal(IdLower_t("while"))))) , ... ). This is the Silver tree that silver would generate when parsing "while(..., ...)" if it was written in a forwarding clause for some ableC extension perhaps. Or are you doing something entirely different? I don't see how the AST gets used. -Eric |
The basic issue is how we would convert from an ableC tree to a Silver tree. I'm not sure what you mean by "run some version of an ableC parser on a string" - the idea is that the ableC grammar would be embedded directly in the Silver grammar, as detailed in #194. There will then be some concrete production in the Silver tree that has as a child the ableC concrete syntax, which is then transformed into an ableC AST of some type ( |
By "run some version of an ableC parser" I meant what you've said in your first paragraph above. What was missing (or what I missed) was the bit in the last paragraph of converting this I don't understand your Also, if Maybe a less contrived example would help. Also, how much of this can be generated from a nice Silver extensions? What you had in #194 for the Decls example is not so bad to read. But I don't see how that connects to this. Thanks. |
Yeah, that's a typo. I meant to pass in
Yes. The point of this example was just trying to show of some of the various proposed features.
References don't typically make up a structural part of an AST that we would want to handle recursively - they can point to anything, and can even create cycles. Note that the main ableC AST doesn't contain references, they are only present in 'auxiliary' trees such as Functions, references, terminals, etc. are all types that can only exist as a 'leaf' in the reflected AST. Since they all have unique types, some sort of new production on the
Sure. For example in the ableC extension to Silver, we would have something like
Make sense?
Not sure I understand the question. But hopefully the example helped? |
OK, much better! Without an example it was difficult to even see what your intentions were. This makes much more sense. I thought much of the other Silver code was to be written as part of an ableC extension, not the extension to Silver to support ableC. Minor comment - do we want a default production for What if someone is building an extension that extends some other extension? How easy would it be to create a new version of Silver for ableC + some-random-extension? We certainly need to do some work on Silver to make creating multiple domain-specific instances of Silver more feasible. The "silver" script we have now is not so useful. Silver should build in a way much more like ableC does. |
Since
Basically there are 3 components I am thinking of adding here:
Adding more extensions would be as simple as adding them to the top-level Silver parser, I think, since an extension to ableC would now be effectively also be an extension to Silver, which has become a host language containing ableC as a component. |
OK, I think this sounds like it is worth trying. @tedinski - last chance to object before we start on this. Any comments? |
I have thoughts about things related to the concrete syntax embedding, but maybe that can wait, since many of them would mostly amount to tweaks that would ensure a smooth path between "stuffing the ablec grammar into silver" as just a first prototype method on the way to something better. I like the idea of reflecting trees as a tool here. This would let us deprecate I do lose the thread in that stuff, though.
i.e. We'd do this for syntax embedding:
This avoids the need for new I think, possibly, you hadn't planned on |
Actually, implementing |
I hadn't given much thought to |
|
@tedinski - about the |
I'm not positive this is exactly what Ted is thinking, but the way I understand it is this: Once we have an ableC tree (a
What I still don't understand, though, is would |
@ericvanwyk basically,
...to an
No, but only because we need special type information. Basically, we'd need to know the exact output type of We'd probably want to make this behave identically to a function, so people can |
I guess what I was envisioning was translating the overall tree directly to the Silver
Ah, a new production in the Silver compiler, not the reflection library - sort of like |
@tedinski What are your thoughts on the dynamic type-checking for reification of |
@tedinski I've started to work on implementing the |
Another issue that I have run across is in attempting to reify productions with type variables not bound on the LHS of the signature. For example, in reifying |
You are finding all the fun corner cases! Let me just see if I understand correctly? The trouble is that we get as far as having to Good question. Any ideas? I does sound to me like maybe this is something that foreign types might have to provide somehow... One thought: we could modify
There's a function called
Ah, for this we'd need to accept any type, I suppose. But you're right there's a problem! We need to make sure those types are the same where they should be the same. e.g.
Oh my, this is getting complicated.
This is a good idea, but it's also biting off a big chunk right away. Can we break this into pieces? What if we error out on any foreign type with a type parameter, and any production with existential variables (type variables in the children that aren't in the LHS). This would allow us to implement something that sometimes/usually works, and then get to figuring out how to handle these new issues, right? (And maybe discover any other new issues along the way?) I do think we should handle these before we decide this feature is done, but I just think we should get something to working without its scope blowing up too big right away. :)
Yeah, it does seem to be blowing up... |
Yeah, but not just for foreign types. Remember, we are shoving anything that isn't a nonterminal, list, or builtin type into But yes, for foreign types this would need to be explicitly specified, somehow. We can probably just raise a runtime error when reifying any foreign type that doesn't have a TypeRep specified (
I thought about doing this instead, but it turns out to be pretty complicated in practice. Also it doesn't stop somebody from constructing a
That is generally my plan, but I am changing the implementation of |
Just a heads-up... |
Eh, subclassing those is not a good approach. Can't those be special cased with |
Hmm. I guess so? There are a bunch of (generated) places where I need to
get a the type of an object, but I suppose I could do this in a static
helper function that handles all these cases.
…On Jan 16, 2018 11:54 PM, "Ted Kaminski" ***@***.***> wrote:
Eh, subclassing those is not a good approach. Can't those be special cased
with instanceof or something?
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
<#212 (comment)>,
or mute the thread
<https://github.com/notifications/unsubscribe-auth/AIE1irKcMo3D520wiEjvLfEG3SYBPnhmks5tLXzwgaJpZM4RD7Yk>
.
|
Does Silver really not have a way of writing type expressions for functions with named parameters? |
Also another question: Can partial application of something with named parameters ever yield something else with named parameters, or do all non-provided named params need to be converted to ordered? |
Hah, yeah. Annotations never really got completed as a feature beyond what was necessary to make location work okay.
Honestly, I forget the state of this implementation. I believe the answer is: we WANT that to be possible, but (a) the lack of type expressions and (b) the need to invent appropriate syntax means that it's not currently possible. But maybe the runtime object for partial application is capable of supporting it... |
OK, thanks. I was a bit confused because the runtime seemed to support this, but I couldn't actually figure out how to test it. |
Alright, part 1 (reflection) and part 2 (reification) are now done (pending figuring out why Jenkins is failing...), so on to part 3 (
My question is where all of this should live.
The issue is how to avoid making the |
Could just not use any of the attributes from langutil. |
I mean, I guess I could... but to me it seems not really a good idea to have multiple attributes with the same name in our standard libraries. That would force anybody wanting to import both |
You can give them different names: |
OK, since #217 with all the reflection library stuff is now merged and building properly, this feature is essentially complete, so I'm closing this issue now. |
Overview
I am proposing that we add a general-purpouse AST reflection library to Silver. This would be useful for implementing embedded host-language AST literals (#194), and may find other uses as well.
Essentially, I am proposing something sort of like
hackUnparse
, except that it outputs a generic tree structure instead of a string.It would also be possible to designate certain types occuring in the tree that should not be reflected, but instead placed directly in the result tree.
escapes
here is a list of pairs of the names of types to escape from reflection and wrapping bridge productions for them. Note that theASTProd
nonterminal is effectively like anewtype
in Haskell, since the productions inescapes
vary in type.Example
Implementation
The implementation is essentially straightforward: a map is built of all the escaped types and their bridge productions. A recursive foreign function somewhat similar to
hackUnparse
will then transverse the tree, first checking if the object has a type name in the map and if so applying the associated production, or otherwise recursively transforming any children and applying the appropriate default production.A few things to resolve here:
TypeNamed
to the runtime with a methodString getTypeName()
, implemented byNode
,DecoratedNode
,NodeFactory
,ConsCell
,StringCatter
,IOToken
, etc. The generated translation for a nonterminal would provide an implementation for this method. Foreign types could implement this interface as well, or otherwise an error would be raised on encountering a foreign type not implementing the interface.String[] getAnnotationNames()
andObject getAnnotation(final String name)
to theNode
class, which would have implementations generated in each nonterminal class.getTypeName
to the generated production classes, and generate code to infer the type parameters from the types of the children. Initially though we can probably just not support escaping type-parametric nonterminals.@tedinski @ericvanwyk Thoughts on this? I'll probably start working on implementing this in the next week or so if there aren't any major objections.
The text was updated successfully, but these errors were encountered: