Defining Functions With Syntax

Defining Functions With Syntax

[Noah Lavine]

Hello all,

I was just going through updating the PEG documentation when I
encountered a very weird situation, and I don't know how to solve it.
As you probably know, the PEG system can take an s-expression
representation of a PEG grammar (a "peg s-exp") and turn it into a
function that can parse strings of this grammar. A macro called
'define-nonterm' does this at compile-time, but what if you build up a
PEG grammar at runtime and want to parse something with it?

The PEG documentation recommends doing '(eval `(define-nonterm as body
,exp) (interaction-environment))', where 'exp' is whatever your
s-expression is. This seems like a bad idea to me, because a) it also
defines a variable 'as', which is not needed and maybe not what you
want and b) it seems unnecessarily complicated. This recommendation is
especially strange because part of the PEG API is the function
'peg-sexp-compile', which actually turns a peg s-exp into a parsing
function. Unfortunately, peg-sexp-compile returns syntax, because that
is what is convenient for define-nonterm.

So at long last, my question is this: is there a way to take some
syntax and turn it directly into a function, without putting it inside
a macro and calling 'eval'? I think there should be, but I don't see
it in the manual. If there is not, I'd like to figure out an API and
add it.

Thanks,
Noah

Re: Defining Functions With Syntax

[Andy Wingo]

Hi Noah,

On Tue 20 Sep 2011 21:00, Noah Lavine <noah.b.lavine@gmail.com> writes:

> what if you build up a PEG grammar at runtime and want to parse
> something with it?

Broadly speaking, you either interpret it or you compile it.  You can do
either using the Scheme compiler, or you can write your own interpreter
or compiler.

First, using the Scheme compiler: being a macro, `define-nonterm'
extends the Scheme compiler with support for PEG grammers.  If you want
to compile at runtime you can call `compile' on your expression.  You
could also call `eval', to interpret at runtime.  I'm not sure which is
the right thing; `compile' will probably be quick (and certainly produce
faster code) but it loads up the compiler, which is a few megabytes of
code I think.

> The PEG documentation recommends doing '(eval `(define-nonterm as body
> ,exp) (interaction-environment))', where 'exp' is whatever your
> s-expression is. This seems like a bad idea to me, because a) it also
> defines a variable 'as', which is not needed and maybe not what you
> want and b) it seems unnecessarily complicated.

Regarding the first, you can `(let () (define-nonterm as body ,exp) as)'
or something, in which the `as' definition doesn't leak beyond that
inner lexical contour.

It is complicated though.  The other option is to write a PEG
interpreter or compiler in Scheme.  An interpreter would interpret the
s-expressions directly, or some simplified form of them.  A compiler
would pre-process the s-expressions to produce a procedure, built from
closures.

For example here is a simple matcher that matches pairs:

  (use-modules (system base pmatch))
  (define (make-pair-matcher pat)
    (pmatch pat
      ((head . tail)
       (let ((hmatch (make-pair-matcher head))
             (tmatch (make-pair-matcher tail)))
         (lambda (x)
           (and (pair? x) (hmatch (car x)) (tmatch (cdr x))))))
      (datum
       (lambda (x) (eq? x datum)))))

  ((make-pair-matcher '(foo . bar)) '(foo . bar))
  => #t

I say that this is "compiled" because the matcher code is wired together
from closures, whose code is compiled, and matching against a datum
doesn't dispatch against the pattern at runtime: that path is computed
(compiled) already by the `make-pair-matcher' procedure.

Does that help any?

Andy
-- 
http://wingolog.org/

Re: Defining Functions With Syntax

[Mark H Weaver]

Andy Wingo <wingo@pobox.com> writes:
> On Tue 20 Sep 2011 21:00, Noah Lavine <noah.b.lavine@gmail.com> writes:
>> The PEG documentation recommends doing '(eval `(define-nonterm as body
>> ,exp) (interaction-environment))', where 'exp' is whatever your
>> s-expression is. This seems like a bad idea to me, because a) it also
>> defines a variable 'as', which is not needed and maybe not what you
>> want and b) it seems unnecessarily complicated.
>
> Regarding the first, you can `(let () (define-nonterm as body ,exp) as)'
> or something, in which the `as' definition doesn't leak beyond that
> inner lexical contour.
>
> It is complicated though.  The other option is to write a PEG
> interpreter or compiler in Scheme.  An interpreter would interpret the
> s-expressions directly, or some simplified form of them.  A compiler
> would pre-process the s-expressions to produce a procedure, built from
> closures.
>
> For example here is a simple matcher that matches pairs:
>
>   (use-modules (system base pmatch))
>   (define (make-pair-matcher pat)
>     (pmatch pat
>       ((head . tail)
>        (let ((hmatch (make-pair-matcher head))
>              (tmatch (make-pair-matcher tail)))
>          (lambda (x)
>            (and (pair? x) (hmatch (car x)) (tmatch (cdr x))))))
>       (datum
>        (lambda (x) (eq? x datum)))))
>
>   ((make-pair-matcher '(foo . bar)) '(foo . bar))
>   => #t
>
> I say that this is "compiled" because the matcher code is wired together
> from closures, whose code is compiled, and matching against a datum
> doesn't dispatch against the pattern at runtime: that path is computed
> (compiled) already by the `make-pair-matcher' procedure.

It occurs to me that, with a sufficiently powerful peval, a PEG compiler
written in the above style could be the only implementation we need.

If the s-expression is a compile-time constant, and if the PEG compiler
is written in purely-functional style and confined within a single
top-level form, then peval should be able to produce the parser
procedure at compile-time.  Otherwise, it would be produced at run-time.

This is part of the reason partial evaluation is so exciting.  It's not
just about increasing the speed of existing programs.  More importantly,
it allows you to write new programs more elegantly.

     Mark

Re: Defining Functions With Syntax

[Noah Lavine]

Hello,

> If the s-expression is a compile-time constant, and if the PEG compiler
> is written in purely-functional style and confined within a single
> top-level form, then peval should be able to produce the parser
> procedure at compile-time.  Otherwise, it would be produced at run-time.
>
> This is part of the reason partial evaluation is so exciting.  It's not
> just about increasing the speed of existing programs.  More importantly,
> it allows you to write new programs more elegantly.

I agree, and in fact I sent an email a few days ago saying the same
thing. :-) I suspect that any macro that doesn't introduce variable
bindings could be written that way, which would be excellent. It might
also be much easier to write, because there are better debugging
facilities for interpreters than macros, like the trace command and
the debugger. I hope peval gets to that point soon.

Since you've brought it up, I've been thinking of a feature I would
want before using that style. peval by default will have to restrict
what it inlines to save space. I'd like a way to guarantee that the
things I want inlined would be inlined, by calling peval myself. So
the best way to do PEG might be something like

  (define (peg-sexp-compile sexp)
    (peval (lambda (string) (peg-sexp-interpret sexp string)) #:full))

or something along those lines, where #:full indicates that all of
peg-sexp-interpret should be inlined. (Although in real life you'd
want a much better way to indicate what should be inlined, and I don't
know what it is yet. I haven't thought through the interface at all.)

That is a long term idea for peval, though. It looks like there are
many more urgent things to do.

Noah

Re: Defining Functions With Syntax

[Noah Lavine]

Hello,

> It is complicated though.  The other option is to write a PEG
> interpreter or compiler in Scheme.  An interpreter would interpret the
> s-expressions directly, or some simplified form of them.  A compiler
> would pre-process the s-expressions to produce a procedure, built from
> closures.

Yes indeed. The thing is, we already have a compiler written in
Scheme. The trouble is that it compiles S-expressions to syntax, and
then it takes some trouble to get that syntax into a procedure. I
think it might be cleaner if I could directly convert syntax into a
procedure. For instance, what about doing

  (compile (peg-sexp-compile <some-s-expression>) #:from scheme-syntax
#:to value)

? That seems like a nice API to me.

Noah

Re: Defining Functions With Syntax

[Andy Wingo]

On Wed 21 Sep 2011 20:03, Noah Lavine <noah.b.lavine@gmail.com> writes:

>> It is complicated though.  The other option is to write a PEG
>> interpreter or compiler in Scheme.  An interpreter would interpret the
>> s-expressions directly, or some simplified form of them.  A compiler
>> would pre-process the s-expressions to produce a procedure, built from
>> closures.
>
> Yes indeed. The thing is, we already have a compiler written in
> Scheme. The trouble is that it compiles S-expressions to syntax, and
> then it takes some trouble to get that syntax into a procedure. I
> think it might be cleaner if I could directly convert syntax into a
> procedure. For instance, what about doing
>
>   (compile (peg-sexp-compile <some-s-expression>) #:from scheme-syntax
> #:to value)
>
> ? That seems like a nice API to me.

You could do the same with #:from 'scheme, no?

Andy
-- 
http://wingolog.org/

Re: Defining Functions With Syntax

[Noah Lavine]

>> For instance, what about doing
>>
>>   (compile (peg-sexp-compile <some-s-expression>) #:from scheme-syntax
>> #:to value)
>>
>> ? That seems like a nice API to me.
>
> You could do the same with #:from 'scheme, no?

I don't think so, because I think #:from 'scheme expects an
S-expression, but peg-sexp-compile returns a syntax object. I might be
wrong, though.

Noah

Re: Defining Functions With Syntax

[Andy Wingo]

On Wed 21 Sep 2011 20:44, Noah Lavine <noah.b.lavine@gmail.com> writes:

> I think #:from 'scheme expects an S-expression, but peg-sexp-compile
> returns a syntax object. I might be wrong, though.

  (compile #'1) => 1

Compiling a syntax object works.

Andy
-- 
http://wingolog.org/

Re: Defining Functions With Syntax

[Noah Lavine]

Oh, excellent! I had assumed it did not. I will update the PEG documentation.

On Wed, Sep 21, 2011 at 3:22 PM, Andy Wingo <wingo@pobox.com> wrote:
> On Wed 21 Sep 2011 20:44, Noah Lavine <noah.b.lavine@gmail.com> writes:
>
>> I think #:from 'scheme expects an S-expression, but peg-sexp-compile
>> returns a syntax object. I might be wrong, though.
>
>  (compile #'1) => 1
>
> Compiling a syntax object works.
>
> Andy
> --
> http://wingolog.org/
>