On 20/04/2013 10:31 PM, Warp wrote:
> I'm assuming that implementing a recursive descent parser ought to be
> relatively simple in Haskell, given how recursive in nature functional
> programming is.

Indeed.

> (Of course this also assumes that it's easy and efficient
> in Haskell to have the input as a byte array, and it's efficient to read
> said array byte by byte, without much copying things around.)

*Reading* from an array is easy. You only need to copy things if they 
change, and reading from something doesn't change it.

> Most languages have some kind of standard functionality for parsing the
> former.

The trouble starts when the literals you're trying to parse don't match 
the format that the standard function expects. (E.g., some languages 
allow "+7" as a valid integer, and others don't.)

> Parsing UTF-8 encoded characters is a bit trickier, especially if the
> language does not offer standard utility functions for that purpose.

Haskell provides a way to read from a file, decoding UTF-8 on the fly. 
I'm not sure how it's implemented internally though. You end up with a 
packed array of characters which you can iterate over.

> (Remember that we are writing an extremely *efficient* parser here. That
> means no copying characters around and parsing them separately. They have
> to be parsed in-place, where they appear in the byte array.)

You're probably going to struggle to get this level of efficiency from a 
programming language that uses garbage collection. Even if all the data 
is in a flat array, the array might get copied from place to place 
occasionally by the garbage collector.

(Having said that, I'm not sure whether or not Haskell's GC does any 
special handling for "large" objects. Some GCs handle these specially, 
which usually means storing them in a separate area that doesn't get 
scanned as often, so they don't need to be copied as much.)

Post a reply to this message