[racket-dev] Merging nonterminals in union-language

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/20130228/eb2f6c7d/attachment.html>