Trees that Grow in the hsSyn AST

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Trees that Grow in the hsSyn AST

Alan & Kim Zimmerman
Hi all

You may be aware that Shayan Najd presented the paper  "Trees that Grow"[1] at HIW last year.

Based on the following mandate

> As in my previous email to Shayan (attached).  Wiki page, describe goals, design,

> approach.  Point to prototype implementation.  Seek comments.   You can say that

>I am supportive!

>

> Simon

We have set up a Wiki page at [2] describing a prototype implementation of the first stage of this for the hsSyn AST, which is to change the polymorphic variable from one of RdrName / Name / Id to an index type. This is presented as a fabricator diff at [3].

Please take a look and provide feedback.

Regards
  Alan

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

RE: Trees that Grow in the hsSyn AST

GHC - devs mailing list

Folks

 

Do take a look at this:

 

·        We propose to re-engineer HsSyn itself.  This will touch a lot of code.

·        But it’s very neat, and will bring big long-term advantages

·        And we can do it a bit at a time

 

The wiki page https://ghc.haskell.org/trac/ghc/wiki/ImplementingTreesThatGrow has the details. 

 

It’s entirely an internal change, not a change to GHC’s specification, so it’s independent of the GHC proposals process.  But I’d value the opinion of other GHC devs.

 

Alan has done a prototype first step, which worked out rather well.  Rather than having

               HsExpr Id

(which we all know means “HsExpr after the typechecker” but tha’s a bit inexplicit, we have

               HsExpr GhcTc

meaning “HsExpr after GHC’s Tc pass”.   In some ways this is quite superficial, but it unlocks the Trees That Grow machiney.

 

Please ask questions etc.  Alan and Shayan can record the answers in the wiki.  I’m inclined to go ahead with this, so yell soon if you disagree.

 

Simon

 

From: ghc-devs [mailto:[hidden email]] On Behalf Of Alan & Kim Zimmerman
Sent: 24 May 2017 22:52
To: [hidden email]
Subject: Trees that Grow in the hsSyn AST

 

Hi all

You may be aware that Shayan Najd presented the paper  "Trees that Grow"[1] at HIW last year.

Based on the following mandate

> As in my previous email to Shayan (attached).  Wiki page, describe goals, design,

> approach.  Point to prototype implementation.  Seek comments.   You can say that

>I am supportive!

> 

> Simon

 

We have set up a Wiki page at [2] describing a prototype implementation of the first stage of this for the hsSyn AST, which is to change the polymorphic variable from one of RdrName / Name / Id to an index type. This is presented as a fabricator diff at [3].

Please take a look and provide feedback.

Regards

  Alan


_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

RE: Trees that Grow in the hsSyn AST

David Feuer-2
In reply to this post by Alan & Kim Zimmerman
I haven't looked in detail yet, but there seem to be good ideas. I have two questions:

1. Which is better to start with: HsSyn or Core? Intuition suggests this sort of thing could be very helpful for making zapping more reliable and ensuring its efficiency, but there may be better reasons to start with HsSyn.

2. If we're making intrusive changes to representations, would now be a sensible era to consider switching to a different variable representation (unbound, bound, abt, etc)?


David Feuer
Well-Typed, LLP

-------- Original message --------
From: Simon Peyton Jones via ghc-devs <[hidden email]>
Date: 5/25/17 6:48 PM (GMT-05:00)
To: Alan & Kim Zimmerman <[hidden email]>, [hidden email]
Subject: RE: Trees that Grow in the hsSyn AST

Folks

Do take a look at this:


·        We propose to re-engineer HsSyn itself.  This will touch a lot of code.

·        But it’s very neat, and will bring big long-term advantages

·        And we can do it a bit at a time

The wiki page https://ghc.haskell.org/trac/ghc/wiki/ImplementingTreesThatGrow has the details.

It’s entirely an internal change, not a change to GHC’s specification, so it’s independent of the GHC proposals process.  But I’d value the opinion of other GHC devs.

Alan has done a prototype first step, which worked out rather well.  Rather than having
               HsExpr Id
(which we all know means “HsExpr after the typechecker” but tha’s a bit inexplicit, we have
               HsExpr GhcTc
meaning “HsExpr after GHC’s Tc pass”.   In some ways this is quite superficial, but it unlocks the Trees That Grow machiney.

Please ask questions etc.  Alan and Shayan can record the answers in the wiki.  I’m inclined to go ahead with this, so yell soon if you disagree.

Simon

From: ghc-devs [mailto:[hidden email]] On Behalf Of Alan & Kim Zimmerman
Sent: 24 May 2017 22:52
To: [hidden email]
Subject: Trees that Grow in the hsSyn AST

Hi all

You may be aware that Shayan Najd presented the paper  "Trees that Grow"[1] at HIW last year.
Based on the following mandate
> As in my previous email to Shayan (attached).  Wiki page, describe goals, design,
> approach.  Point to prototype implementation.  Seek comments.   You can say that
>I am supportive!
>
> Simon

We have set up a Wiki page at [2] describing a prototype implementation of the first stage of this for the hsSyn AST, which is to change the polymorphic variable from one of RdrName / Name / Id to an index type. This is presented as a fabricator diff at [3].
Please take a look and provide feedback.
Regards
  Alan


[1] http://www.jucs.org/jucs_23_1/trees_that_grow/jucs_23_01_0042_0062_najd.pdf<https://na01.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.jucs.org%2Fjucs_23_1%2Ftrees_that_grow%2Fjucs_23_01_0042_0062_najd.pdf&data=02%7C01%7Csimonpj%40microsoft.com%7C5faccc0d2d534c42c23e08d4a2ef36d8%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C1%7C636312595690311243&sdata=fbLJdJqSyXgacCEJwVH880aLsHDgDY46hrc%2FtDXv4VQ%3D&reserved=0>
[2] https://ghc.haskell.org/trac/ghc/wiki/ImplementingTreesThatGrow
[3] https://phabricator.haskell.org/D3609

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Trees that Grow in the hsSyn AST

Shayan Najd Javadipour-2
Hi David, 

Which is better to start with: HsSyn or Core? Intuition suggests this sort of thing could be very helpful for making zapping more reliable and ensuring its efficiency, but there may be better reasons to start with HsSyn.

- Why not making Core growable as well?
We just have not considered making Core AST growable so far, though it is entirely doable if needed. 
Specially, if you have some motivating examples that a growable Core AST "could be very helpful" like for "making zapping more reliable and ensuring its efficiency", let us know; we can consider making Core growable as well (possibly as an independent project). 

- Why not making Core growable first?
Here the idea is to make HsSyn AST growable for the long-term goals stated on the wiki page, like getting rid of the multiple representations of Haskell syntax (i.e., HsSyn, Template Haskell, and Haskell-Src-Exts).
I imagine making Core AST growable does not get us closer to our current long-term goals (except maybe as an experiment to study the impact of such AST changes on GHC, like we did in D3609)

2. If we're making intrusive changes to representations, would now be a sensible era to consider switching to a different variable representation (unbound, bound, abt, etc)?
 
- While we are at it, can we consider improving some bits of the AST?
For the first few steps, I really hope to keep the changes to representations as little as possible, at least to ease the reviewing process and to avoid introducing bugs (provided the large scale of the changes).
For the next steps, we can indeed consider such improvements. (We do so for source locations, at least)

Do you have some specific changes in mind? Specially the ones that may overlap with our work? 

Thanks.

/Shayan



On Fri, May 26, 2017 at 2:11 AM, David Feuer <[hidden email]> wrote:
I haven't looked in detail yet, but there seem to be good ideas. I have two questions:

1. Which is better to start with: HsSyn or Core? Intuition suggests this sort of thing could be very helpful for making zapping more reliable and ensuring its efficiency, but there may be better reasons to start with HsSyn.

2. If we're making intrusive changes to representations, would now be a sensible era to consider switching to a different variable representation (unbound, bound, abt, etc)?


David Feuer
Well-Typed, LLP

-------- Original message --------
From: Simon Peyton Jones via ghc-devs <[hidden email]>
Date: 5/25/17 6:48 PM (GMT-05:00)
To: Alan & Kim Zimmerman <[hidden email]>, [hidden email]
Subject: RE: Trees that Grow in the hsSyn AST

Folks

Do take a look at this:


·        We propose to re-engineer HsSyn itself.  This will touch a lot of code.

·        But it’s very neat, and will bring big long-term advantages

·        And we can do it a bit at a time

The wiki page https://ghc.haskell.org/trac/ghc/wiki/ImplementingTreesThatGrow has the details.

It’s entirely an internal change, not a change to GHC’s specification, so it’s independent of the GHC proposals process.  But I’d value the opinion of other GHC devs.

Alan has done a prototype first step, which worked out rather well.  Rather than having
               HsExpr Id
(which we all know means “HsExpr after the typechecker” but tha’s a bit inexplicit, we have
               HsExpr GhcTc
meaning “HsExpr after GHC’s Tc pass”.   In some ways this is quite superficial, but it unlocks the Trees That Grow machiney.

Please ask questions etc.  Alan and Shayan can record the answers in the wiki.  I’m inclined to go ahead with this, so yell soon if you disagree.

Simon

From: ghc-devs [mailto:[hidden email]] On Behalf Of Alan & Kim Zimmerman
Sent: 24 May 2017 22:52
To: [hidden email]
Subject: Trees that Grow in the hsSyn AST

Hi all

You may be aware that Shayan Najd presented the paper  "Trees that Grow"[1] at HIW last year.
Based on the following mandate
> As in my previous email to Shayan (attached).  Wiki page, describe goals, design,
> approach.  Point to prototype implementation.  Seek comments.   You can say that
>I am supportive!
>
> Simon

We have set up a Wiki page at [2] describing a prototype implementation of the first stage of this for the hsSyn AST, which is to change the polymorphic variable from one of RdrName / Name / Id to an index type. This is presented as a fabricator diff at [3].
Please take a look and provide feedback.
Regards
  Alan


[1] http://www.jucs.org/jucs_23_1/trees_that_grow/jucs_23_01_0042_0062_najd.pdf<https://na01.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.jucs.org%2Fjucs_23_1%2Ftrees_that_grow%2Fjucs_23_01_0042_0062_najd.pdf&data=02%7C01%7Csimonpj%40microsoft.com%7C5faccc0d2d534c42c23e08d4a2ef36d8%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C1%7C636312595690311243&sdata=fbLJdJqSyXgacCEJwVH880aLsHDgDY46hrc%2FtDXv4VQ%3D&reserved=0>
[2] https://ghc.haskell.org/trac/ghc/wiki/ImplementingTreesThatGrow
[3] https://phabricator.haskell.org/D3609

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs



_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

RE: Trees that Grow in the hsSyn AST

GHC - devs mailing list
In reply to this post by Alan & Kim Zimmerman

1. Which is better to start with: HsSyn or Core? Intuition suggests this sort of thing could be very helpful for making zapping more reliable and ensuring its efficiency, but there may be better reasons to start with HsSyn.

 

Definitely HsSyn.  It’s big, riddled with extra info, and has many purposes for different people.  Core is small, tight, nailed down.  I don’t want to mess with it.

 

2. If we're making intrusive changes to representations, would now be a sensible era to consider switching to a different variable representation (unbound, bound, abt, etc)?

 

I don’t think so.  The issues are quite orthogonal, and no one (to my knowledge) has proposed any vaguely plausible change to variable bindings that would scale to what GHC does.   In contrast, this stuff is “just” re-engineering.

 

Simon

 

From: David Feuer [mailto:[hidden email]]
Sent: 26 May 2017 01:11
To: Simon Peyton Jones <[hidden email]>; Alan & Kim Zimmerman <[hidden email]>; [hidden email]
Subject: RE: Trees that Grow in the hsSyn AST

 

I haven't looked in detail yet, but there seem to be good ideas. I have two questions:

 

1. Which is better to start with: HsSyn or Core? Intuition suggests this sort of thing could be very helpful for making zapping more reliable and ensuring its efficiency, but there may be better reasons to start with HsSyn.

 

2. If we're making intrusive changes to representations, would now be a sensible era to consider switching to a different variable representation (unbound, bound, abt, etc)?

 

 

David Feuer

Well-Typed, LLP

 

-------- Original message --------

From: Simon Peyton Jones via ghc-devs <[hidden email]>

Date: 5/25/17 6:48 PM (GMT-05:00)

To: Alan & Kim Zimmerman <[hidden email]>, [hidden email]

Subject: RE: Trees that Grow in the hsSyn AST

 

Folks

Do take a look at this:


·        We propose to re-engineer HsSyn itself.  This will touch a lot of code.

·        But it’s very neat, and will bring big long-term advantages

·        And we can do it a bit at a time

The wiki page https://ghc.haskell.org/trac/ghc/wiki/ImplementingTreesThatGrow has the details.

It’s entirely an internal change, not a change to GHC’s specification, so it’s independent of the GHC proposals process.  But I’d value the opinion of other GHC devs.

Alan has done a prototype first step, which worked out rather well.  Rather than having
               HsExpr Id
(which we all know means “HsExpr after the typechecker” but tha’s a bit inexplicit, we have
               HsExpr GhcTc
meaning “HsExpr after GHC’s Tc pass”.   In some ways this is quite superficial, but it unlocks the Trees That Grow machiney.

Please ask questions etc.  Alan and Shayan can record the answers in the wiki.  I’m inclined to go ahead with this, so yell soon if you disagree.

Simon

From: ghc-devs [[hidden email]] On Behalf Of Alan & Kim Zimmerman
Sent: 24 May 2017 22:52
To: [hidden email]
Subject: Trees that Grow in the hsSyn AST

Hi all

You may be aware that Shayan Najd presented the paper  "Trees that Grow"[1] at HIW last year.
Based on the following mandate
> As in my previous email to Shayan (attached).  Wiki page, describe goals, design,
> approach.  Point to prototype implementation.  Seek comments.   You can say that
>I am supportive!
>
> Simon

We have set up a Wiki page at [2] describing a prototype implementation of the first stage of this for the hsSyn AST, which is to change the polymorphic variable from one of RdrName / Name / Id to an index type. This is presented as a fabricator diff at [3].
Please take a look and provide feedback.
Regards
  Alan


[1] http://www.jucs.org/jucs_23_1/trees_that_grow/jucs_23_01_0042_0062_najd.pdf<https://na01.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.jucs.org%2Fjucs_23_1%2Ftrees_that_grow%2Fjucs_23_01_0042_0062_najd.pdf&data=02%7C01%7Csimonpj%40microsoft.com%7C5faccc0d2d534c42c23e08d4a2ef36d8%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C1%7C636312595690311243&sdata=fbLJdJqSyXgacCEJwVH880aLsHDgDY46hrc%2FtDXv4VQ%3D&reserved=0>
[2] https://ghc.haskell.org/trac/ghc/wiki/ImplementingTreesThatGrow
[3] https://phabricator.haskell.org/D3609


_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Trees that Grow in the hsSyn AST

David Feuer-2
On Friday, May 26, 2017 9:03:15 AM EDT Simon Peyton Jones wrote:
> 1. Which is better to start with: HsSyn or Core? Intuition suggests this sort of thing could be very helpful for making zapping more reliable and ensuring its efficiency, but there may be better reasons to start with HsSyn.
>
> Definitely HsSyn.  It’s big, riddled with extra info, and has many purposes for different people.  Core is small, tight, nailed down.  I don’t want to mess with it.

Don't get me wrong. I wasn't suggesting that Core should come first; I have absolutely no basis to make any suggestion in that regard. I was just wondering what led to the decision to start with HsSyn. Are you suggesting that Core wouldn't benefit from these ideas? I surely don't see why not. Information about arity and strictness, at least, is introduced in specific compiler phases. I believe that some information needed for join points is only valid/available between certain phases. Making such things explicit in the types seems like it can only help.

> 2. If we're making intrusive changes to representations, would now be a sensible era to consider switching to a different variable representation (unbound, bound, abt, etc)?
>
> I don’t think so.  The issues are quite orthogonal, and no one (to my knowledge) has proposed any vaguely plausible change to variable bindings that would scale to what GHC does.   In contrast, this stuff is “just” re-engineering.

All right; I figured it wouldn't hurt to ask. May I ask what sorts of scaling problems you mean?

David
_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

RE: Trees that Grow in the hsSyn AST

GHC - devs mailing list
| just wondering what led to the decision to start with HsSyn. Are you
| suggesting that Core wouldn't benefit from these ideas? I surely don't

Core, unlike HsSyn, is heavily optimised and transformed.  It's hard to see how the transformations could soundly maintain arbitrary auxiliary information.  Also unlike HsSyn, Core is a very small language, so it's no big deal to transform it into something else.


| All right; I figured it wouldn't hurt to ask. May I ask what sorts of
| scaling problems you mean?

Simply maintaining a finite map from binders to another binder, or arbitrary other info (eg strictness) can be challenging.  Try it!

Simon

| -----Original Message-----
| From: David Feuer [mailto:[hidden email]]
| Sent: 30 May 2017 22:06
| To: Simon Peyton Jones <[hidden email]>
| Cc: Alan & Kim Zimmerman <[hidden email]>; [hidden email]
| Subject: Re: Trees that Grow in the hsSyn AST
|
| On Friday, May 26, 2017 9:03:15 AM EDT Simon Peyton Jones wrote:
| > 1. Which is better to start with: HsSyn or Core? Intuition suggests
| this sort of thing could be very helpful for making zapping more reliable
| and ensuring its efficiency, but there may be better reasons to start
| with HsSyn.
| >
| > Definitely HsSyn.  It’s big, riddled with extra info, and has many
| purposes for different people.  Core is small, tight, nailed down.  I
| don’t want to mess with it.
|
| Don't get me wrong. I wasn't suggesting that Core should come first; I
| have absolutely no basis to make any suggestion in that regard. I was
| just wondering what led to the decision to start with HsSyn. Are you
| suggesting that Core wouldn't benefit from these ideas? I surely don't
| see why not. Information about arity and strictness, at least, is
| introduced in specific compiler phases. I believe that some information
| needed for join points is only valid/available between certain phases.
| Making such things explicit in the types seems like it can only help.
|
| > 2. If we're making intrusive changes to representations, would now be a
| sensible era to consider switching to a different variable representation
| (unbound, bound, abt, etc)?
| >
| > I don’t think so.  The issues are quite orthogonal, and no one (to my
| knowledge) has proposed any vaguely plausible change to variable bindings
| that would scale to what GHC does.   In contrast, this stuff is “just”
| re-engineering.
|
| All right; I figured it wouldn't hurt to ask. May I ask what sorts of
| scaling problems you mean?
|
| David
_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Loading...