[Caml-list] CFG's and Camlp4

[Caml-list] CFG's and Camlp4

[David McClain]

Actually, after having put off learning Camlp4 for quite some time because
it seemed so arcane, I now decided at the urging of several people to dig
into it.

I have to say that I am quite impressed. Camlp4 represents a kind of
paradigm shift that I was hoping to see when pleading for more modern
approaches. In fact it seems so modern that I'm still trying to wrap my
brain around it.

Already I have several other uses for this preprocessing. But the idea of an
extensible grammar, on the fly, is very appealing. I do huge amounts of Lisp
macrology and came to miss that. I thought to myself that OCaml at least
made up for it by being so darned convenient to use at the functional level
that macros just seemed nonessential. But that isn't quite true, and now
Camlp4 comes to the rescue.

The difficulty I have been having with YACC seems to be caused by the
reduction from LL(1) to LALR(1), where tables have shrunk by coalescing what
appear to be common productions. That is in fact true for expressions and
patterns. However, we (Inria and myself) both expect to use different
semantic actions on these two similar syntactic breeds. That becomes
problematic when the parser folds the two cases together. What I'm doing
would probably work just fine in LL(1), but not entirely correctly in
LALR(1).

[I studied the "Dragon Book" many years ago, and was ever so grateful when
that came to an end. I see now that many of my misconceptions about language
grammar compilers were never properly reoriented during that period. I must
also say that I much prefer the arcane new world of Camlp4. Perhaps I just
like new ideas. I certainly do like new ideas that both work, and force my
brain onto an entirely new plane. YACC was a great idea at the time. I know
it still has heavy use -- I use it myself. But dynamically extensible
grammars seem like a neat new idea.]

David McClain
Senior Corporate Scientist
Avisere, Inc.

+1.520.390.7738 (USA)
david.mcclain@avisere.com



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] CFG's and Camlp4

[Paul Snively]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi David!

On Aug 13, 2004, at 11:11 AM, David McClain wrote:

> Actually, after having put off learning Camlp4 for quite some time 
> because
> it seemed so arcane, I now decided at the urging of several people to 
> dig
> into it.
>
> I have to say that I am quite impressed. Camlp4 represents a kind of
> paradigm shift that I was hoping to see when pleading for more modern
> approaches. In fact it seems so modern that I'm still trying to wrap my
> brain around it.
>
Heh. Yes, having an actual AST-based "preprocessor," especially in a 
language with a proper module system, opens up a whole new set of 
possibilities. The only reason I thought you might not want to use it 
is because its support for going beyond single-token lookahead isn't 
any better than ocamlyacc's. On the other hand, other of its terrific 
qualities likely overcome that single objection, so have fun with it!

> Already I have several other uses for this preprocessing. But the idea 
> of an
> extensible grammar, on the fly, is very appealing. I do huge amounts 
> of Lisp
> macrology and came to miss that. I thought to myself that OCaml at 
> least
> made up for it by being so darned convenient to use at the functional 
> level
> that macros just seemed nonessential. But that isn't quite true, and 
> now
> Camlp4 comes to the rescue.
>
Your path to O'Caml and mine sound very, very similar. If you really 
want to see some magic using Camlp4, let me highly recommend 
<http://www.venge.net/graydon/talks/mkc/html>. :-)

> The difficulty I have been having with YACC seems to be caused by the
> reduction from LL(1) to LALR(1), where tables have shrunk by 
> coalescing what
> appear to be common productions. That is in fact true for expressions 
> and
> patterns. However, we (Inria and myself) both expect to use different
> semantic actions on these two similar syntactic breeds. That becomes
> problematic when the parser folds the two cases together. What I'm 
> doing
> would probably work just fine in LL(1), but not entirely correctly in
> LALR(1).
>
Right. Whether we like it or not, our grammars do generally have to be 
expressed in a way that exposes a reduction-order dependency, which is 
really just a more pragmatic way of saying that they are not 
context-free (are you sick of hearing me say that yet)? Once you have a 
non-context-free grammar, by definition you have order-of-reduction 
dependencies, and therefore whether your parser generator is Left-Left 
or Left-Right matters. This is why GLR is so interesting: it adopts the 
philosophy of "when I encounter an ambiguity I'll just keep all 
possible interpretations of it in mind until I have enough information 
to see which interpretation is the correct one." In simple cases, e.g. 
where operator precedence resolves the ambiguity, you don't need to do 
anything more that specify that precedence. In more complex cases, you, 
the grammar author, must specify how to "merge" the possible 
interpretations. It's quite clever, but perhaps either overkill for 
your needs, or even if not, again, Camlp4's awesome range of features 
outweighs the difference.

> [I studied the "Dragon Book" many years ago, and was ever so grateful 
> when
> that came to an end. I see now that many of my misconceptions about 
> language
> grammar compilers were never properly reoriented during that period. I 
> must
> also say that I much prefer the arcane new world of Camlp4. Perhaps I 
> just
> like new ideas. I certainly do like new ideas that both work, and 
> force my
> brain onto an entirely new plane. YACC was a great idea at the time. I 
> know
> it still has heavy use -- I use it myself. But dynamically extensible
> grammars seem like a neat new idea.]
>
I would have to agree that the venerable Dragon Book is showing its 
age, and that parsing, in particular, has come a long way since then. 
Ironically, though, the Dragon Book talks about a lot more than 
parsing, but you rarely hear anyone talk about what the Dragon Book has 
to say about intermediate compiler representations or code-generation 
issues. My frank thesis is that that means that the parsing stuff was 
trivial and hence easy to remember, but also therefore the first thing 
to fall to progress, whereas the meatier material on the rest of a 
compiler still holds up eh-reasonably-well, although really modern 
research into formal semantics-based compiler development makes me 
wonder how on earth we ever did it any other way.

> David McClain
> Senior Corporate Scientist
> Avisere, Inc.
>
> +1.520.390.7738 (USA)
> david.mcclain@avisere.com
>
>
>
> -------------------
> To unsubscribe, mail caml-list-request@inria.fr Archives: 
> http://caml.inria.fr
> Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: 
> http://caml.inria.fr/FAQ/
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>
Best regards,
Paul

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (Darwin)

iEYEARECAAYFAkEdDSIACgkQbot1wzHBQBVKMACglqEmymfPr25M8VNOkouHrW1E
XKwAn2u2a3l4m+iYrl4SS6yL368DkgF+
=2Rss
-----END PGP SIGNATURE-----

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners