Colm programming language released: best parser-writer ever • Hacker News Board

Re: Colm programming language released: best parser-writer ever

#11

Post by thurston » Wed, May 18, 2011, 5:06 PM UTC

ScottBurson wrote: post #10

Thurston claims that no previous grammar system supports his three requirements of generalized parsing, grammar-dependent scanning, and context-dependent parsing. I would argue that Prolog Definite Clause Grammars, which date back to the early 1970s, have all three of these properties. Furthermore, since the context is maintained functionally, by threading additional values through the productions, no "undo actions"…

Where is the grammar-dependent scanning?

Note that threading the context through the parse tree while maintaining fully generalized parsing requires keeping all versions of the parsing context in memory. Consider making a C++ parser in that way ... ie every time you modify the structures you build in memory you make a copy of them first.

Re: Colm programming language released: best parser-writer ever

#12

Post by audreyt » Wed, May 18, 2011, 5:11 PM UTC

colomon wrote: post #6

It would be interesting to see someone who understood both this and Perl 6's grammars to do a comparison. Based on Colm's quick description and my rough understanding of Perl 6 grammars, they sound like they are roughly equally powerful. But I admit I'm not sure I understand what "transformation language" means...

Although similar in expressive power, Colm offers instruction logging to auto-reverse global state changes upon backtracking, something Perl 6 grammars does not (yet) support; at the moment we need to manually manage them with embedded blocks.

Re: Colm programming language released: best parser-writer ever

#13

Post by alan-crowe » Wed, May 18, 2011, 5:17 PM UTC

ScottBurson wrote: post #10

Thurston claims that no previous grammar system supports his three requirements of generalized parsing, grammar-dependent scanning, and context-dependent parsing. I would argue that Prolog Definite Clause Grammars, which date back to the early 1970s, have all three of these properties. Furthermore, since the context is maintained functionally, by threading additional values through the productions, no "undo actions"…

I remember, back in 1985, trying to write a parser in Prolog on a VAX 11/750. I didn't know what I was doing and my code fell into the exponential case trap. Even minimalist examples appeared to crash as they took unreasonably long, so I wasn't getting clues to the problem, and just gave up.

Consequently I want to rephrase the first sentence of your third paragraph. The problem with DCGs is performance: they're exponential in the naive case. That might not sound too bad today, but back in 1985 the hype was that Prolog let you program declaratively. Just declare what a parse looks like. Reasonable performance in the naive case was the popular selling point for Prolog.

Re: Colm programming language released: best parser-writer ever

#14

Post by swannodette » Wed, May 18, 2011, 5:23 PM UTC

thurston wrote: post #11

ScottBurson wrote: post #10

Thurston claims that no previous grammar system supports his three requirements of generalized parsing, grammar-dependent scanning, and context-dependent parsing. I would argue that Prolog Definite Clause Grammars, which date back to the early 1970s, have all three of these properties. Furthermore, since the context is maintained functionally, by threading additional values through the productions, no "undo actions"…

Where is the grammar-dependent scanning? Note that threading the context through the parse tree while maintaining fully generalized parsing requires keeping all versions of the parsing context in memory. Consider making a C++ parser in that way ... ie every time you modify the structures you build in memory you make a copy of them first.

If your data structures are persistent data structures you don't incur the costs of copying.

Re: Colm programming language released: best parser-writer ever

#15

Post by thurston » Wed, May 18, 2011, 5:27 PM UTC

DrCatbox wrote: post #9

I am more interested in DSNP, how come this project has not received more fame than the infamous Disapora? http://www.complang.org/dsnp/

There are some difficult problems in that space. I've posted to HN and reddit a few times, but mostly I've been working on it quietly so I can focus. Lately, that's starting to change. I'll be talking about it at FSW 11 in Berlin in a few weeks.

Re: Colm programming language released: best parser-writer ever

#16

Post by thurston » Wed, May 18, 2011, 5:28 PM UTC

swannodette wrote: post #14

thurston wrote: post #11

Earlier quoted context omitted.

Where is the grammar-dependent scanning? Note that threading the context through the parse tree while maintaining fully generalized parsing requires keeping all versions of the parsing context in memory. Consider making a C++ parser in that way ... ie every time you modify the structures you build in memory you make a copy of them first.

If your data structures are persistent data structures you don't incur the costs of copying.

Then you forgo generalized parsing.

Edit: indeed I did not follow what you meant.

Re: Colm programming language released: best parser-writer ever

#17

Post by [deleted] » Wed, May 18, 2011, 5:29 PM UTC

thurston wrote: post #8

colomon wrote: post #6

It would be interesting to see someone who understood both this and Perl 6's grammars to do a comparison. Based on Colm's quick description and my rough understanding of Perl 6 grammars, they sound like they are roughly equally powerful. But I admit I'm not sure I understand what "transformation language" means...

If they are then I don't deserve to be called "Dr. Thurston!"

[deleted]

Re: Colm programming language released: best parser-writer ever

#18

Post by haberman » Wed, May 18, 2011, 5:30 PM UTC

From my quick scan of the thesis, the basic design seems to be a programming language in which you write both the parser and any transformations you want to perform. It's not clear whether there is an easily-accessible parse tree serialization that you can use to load the output into another language, or whether you'd have to invent that yourself.

I think it's generally a hard sell if you try to convince people that they need to write their algorithms in your special language. Parsing tools deliver value because grammars are easier to write than the imperative code that implements those grammars. That value offsets the cost of having to learn a new special-purpose language. But imperative programming languages are already pretty good at tree traversal and transformation, so there's little benefit to using a special-purpose language for this.

I think that the next big thing in parsing will be a runtime that easily integrates into other languages so that the parsing framework can handle only the parsing and all of the tree traversal and transformation can be performed using whatever language the programmer was already using. This requires much less buy-in to a special-purpose language.

Re: Colm programming language released: best parser-writer ever

#19

Post by audreyt » Wed, May 18, 2011, 5:35 PM UTC

[deleted] wrote: post #17

thurston wrote: post #8

Earlier quoted context omitted.

If they are then I don't deserve to be called "Dr. Thurston!"

[deleted]

Interestingly, I parsed thurston's response not as an appeal to authority, but as self-mocking humor (i.e. "wow, if Perl 6 does that too, maybe my PhD was unwarranted!"). I guess English parsing is non-deterministic too... :-)

Re: Colm programming language released: best parser-writer ever

#20

Post by anigbrowl » Wed, May 18, 2011, 5:39 PM UTC

[deleted] wrote: post #17

thurston wrote: post #8

Earlier quoted context omitted.

If they are then I don't deserve to be called "Dr. Thurston!"

[deleted]

Good grief. Have a sense of humor; the grandparent response was obviously made with tongue firmly in cheek.