Re: Make peg.el a built-in library?

[Augusto Stoffel <arstoffel@gmail.com>]

On Sun, 26 Sep 2021 at 08:06, Eric Abrahamsen <eric@ericabrahamsen.net> wrote:

> Augusto Stoffel <arstoffel@gmail.com> writes:
>
>> I think it would be really cool to have PEGs built into Emacs.  Things
>> like json.el could be simplified by at least (log10 2) orders of
>> magnitude with PEGs.  Whatever the use case of `rx' is, PEGs are
>> probably the "real" solution.
>>
>> But I suspect this would only take traction with a fast and robust C
>> implementation like Lua's LPEG (see below for a reason).
>
> I wonder if it would make sense to adopt this elisp library for now, see
> if people use it (or want to use it but complain about speed), and
> consider translating to C if they do?

Yes, that sounds reasonable.  But the efficiency problem isn't even just
about speed, it's also about which patterns you can run at all without
exhausting the call stack.  Without the “tail call optimization” that I
mentioned in the previous message, I think much of the appeal of PEGs is
gone...

>
> The elisp version has generic methods for `peg-normalize' (and
> `peg--macroexpand', though I guess that's private) which would allow
> library authors to write new peg expressions. We'd lose that with C,
> though I suppose speed vs extensibility is always the tradeoff with
> C vs Elisp.

I'm not sure I understand this comment, and I confess I didn't look
closely at peg.el.  But there's a difference between _defining_ a
pattern and _executing_ it.  If the basic PEG vocabulary (sequence,
ordered choice, repetition, grammars, etc.) is implemented in C, you can
define all sorts of combinators, such as

     (define-peg-rule search (patt)
       (or patt (and (any) (search patt))))

[or whatever the syntax is for grammars/recursive definitions], and
executing the patterns doesn't involve any Lisp calls.

>
> In a previous message I complained a little bit about the entry-points
> to PEG as it stands now -- they're all macros. Maybe if we were thinking
> in terms of a future C translation, we could narrow the API down a
> little and lock it down, and discourage authors from using anything that
> wouldn't be made available by the future version.

I can't say anything useful here without studying peg.el a bit, but I
think it would be ideal if PEGs are just values (which, in particular,
you can manipulate without naming) and there are functions that allow
making new PEGs out of old ones.

And once again, Lua's LPEG is a fantastic library.  It might be worth
taking a look at how it works.

>
> Eric