[racket-dev] Merging nonterminals in union-language

I am at Northeastern. I use my own address as a central point for the
multiple present and past addresses, and usually don't bother
spoofing the `from' header. Perhaps I'll add a note about that to my
email signature.

Thanks for the tips about reduction semantics! 

I've created a pull request.

William Bowman

On Thu, Feb 28, 2013 at 08:18:12PM -0600, Robby Findler wrote:
> Yeah, I agree it does make sense to do this kind of merging with examples
> like the one you posted or else you get very very bad performance in
> matching. And the merging is coming about because of the way the language
> is structured; it isn't accidental "lucky" merging; you expect the same
> productions to show up multiple times because of the way the grammars are
> constructed.
> 
> Overall, I agree with you that this is a reasonable request. I would be
> happier if I could say that Redex's module language were anywhere close to
> being ready because if it were, there would be a better way to do this. But
> in the meantime, I think your extension is a good one. Your email suggests
> that you are unaffiliated but I think you're actually at Northeastern? Can
> someone there help you make this push? If not, I'd be happy to do it.
> 
> Meanwhile, as to your Redex code, two points about reduction-semantics
> style: you should put both "v" and "E" into the extension not the
> originals: typically both concepts are a part of standard reduction. But,
> if you have a need of values in the original language, (for, say, defining
> Eval) then you should make it a separate non-terminal, not a production of
> 'e'. In your specific example, you run into trouble if you want to make
> pair strict, since you want only (pair v v) in the v non-terminal, but
> (pair e e) in the e non-terminal. FWIW.
> 
> Robby
> 
> 
> On Thu, Feb 28, 2013 at 3:04 PM, William J. Bowman
> <wjb at williamjbowman.com>wrote:
> 
> > By the way, when I was tinkering, I originally got my example working
> > *without* merging nts (lines 1967-1983). I only added it after
> > inspecting the output of `compiled-lang-lang'. The resulting
> > union-language had the same nonterminal in a language several times with
> > overlapping right-hand-sides, so I merged them
> >
> > William Bowman
> >
> > On Thu, Feb 28, 2013 at 02:05:59PM -0600, Robby Findler wrote:
> > > The reason I didn't do that is very much related to lines 1967-1983 in
> > your
> > > diff.
> > >
> > > That isn't a good idea: what you really want to do there is check to see
> > if
> > > different patterns generate the same languages or not. But that's not
> > > something that is easily done (I'm guessing it is computable, but very
> > very
> > > expensive. It may not be computable, tho, for all I know.)
> > >
> > > One could allow unioning by just keeping all productions, and I guess I
> > > wouldn't mind an extension to define-union-language via a keyword that
> > did
> > > that, tho.
> > >
> > > In your case, is there not a way to refactor your grammars so that you
> > > don't need this capability? Could you maybe make a small, representative
> > > example to post to the list? I find that kind of thing to be quite
> > helpful
> > > for me to understand what the best change to Redex is.
> > >
> > > Robby
> > >
> > >
> > >
> > > On Thu, Feb 28, 2013 at 1:46 PM, William J. Bowman
> > > <wjb at williamjbowman.com>wrote:
> > >
> > > > Hello all,
> > > >
> > > > I've been hacking on some languages in Redex, and found myself
> > > > abstracting commons parts into base languages, and gradually building
> > new
> > > > languages via `define-extended-language' and `define-union-language'.
> > > > Unfortunately, I hit a wall when I discovered `define-union-language'
> > > > doesn't like to union languages that define the same nonterminals.
> > > >
> > > > Consider this toy example:
> > https://gist.github.com/bluephoenix47/5054403
> > > >
> > > > This seems like a sensible thing to want to do, so I forked racket
> > wrote a
> > > > patch:
> > > >
> > > >
> > https://github.com/bluephoenix47/racket/commit/0a7781b2be2643778f8d8d10d771ab1ce2dc622b
> > > >
> > > > Unfortunately, several Redex tests fail (http://sprunge.us/fPHU)
> > because
> > > > they expect an error when languages which define the same nonterminals
> > > > are used in `define-union-language'.
> > > >
> > > > Is this *desired* behavior? If so, why? It seems very reasonable to
> > want
> > > > to merge the nonterminals of languages.
> > > >
> > > > --
> > > >
> > > > William J. Bowman
> > > >
> > > > _________________________
> > > >   Racket Developers list:
> > > >   http://lists.racket-lang.org/dev
> > > >
> > > >
> >
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 836 bytes
Desc: Digital Signature
URL: <http://lists.racket-lang.org/dev/archive/attachments/20130228/d772e584/attachment.sig>