[racket-dev] Merging nonterminals in union-language

From: Robby Findler (robby at eecs.northwestern.edu)
Date: Sat Mar 2 21:48:15 EST 2013

Thanks for the pull request (and sorry for the delay in replying here).
I've pushed your commit and another one that covers things like docs and
otherwise a few other changes to your commit. Please let me know if things
don't work out for you.

Robby


On Thu, Feb 28, 2013 at 10:47 PM, William J. Bowman
<wjb at williamjbowman.com>wrote:

> 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 --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/dev/archive/attachments/20130302/bea9f158/attachment-0001.html>

Posted on the dev mailing list.