Hacker News Reader

Comment by amluto | Hacker News Reader

For those of us who don’t stare at parsers on a regular basis, this seems odd to me:

    newtype Parser a = P (String -> Maybe (String, a))

So, on a successful parse, it returns the result and the rest of the string. That’s seems error prone and rather weak. What ensures that the “rest of the string” is, in fact, a suffix of the input? I assume the purpose of this design is for compatibility with lazy input sequences, where the “rest of the string” could still be lazy. But surely some Haskell type magic could ensure that the supposed lazy suffix is actually a suffix.

If I were writing a serious parser intended for human use with nice error messages, I would want to know the position and length of the parsed output, which I could infer from actual strings with known length, but which I may not be able to efficiently infer from lazy sequences.

So I’m confused. Why is this a good design?

View on HN

> What ensures that the “rest of the string” is, in fact, a suffix of the input?

Nothing, unless you have unit tests. Or use Liquid Haskell:

https://ucsd-progsys.github.io/liquidhaskell/

There are languages that let you express stronger guarantees/requirements via type system, but it’s better not to go down the rabbit hole of dependent typing.

I'm not sure if you meant this to be snarky but that's how it comes across to me! If your questions were genuine, then there are indeed good answers.

> Why is this a good design?

It's simple, so it's a good design for expository purposes.

> If I were writing a serious parser intended for human use with nice error messages, I would want to know the position and length of the parsed output

That's roughly how the fastest Haskell parser, flatparse, works

https://hackage.haskell.org/package/flatparse-0.5.0.1/docs/F...

You could write a very similar article to this one about how flatparse's Parser type is a functor, and then someone could snarkily respond

> So, on a successful parse, it returns the result and the index into the string that it has parsed so far. That’s seems error prone and rather weak. What ensures that the “index into the string that it has parsed so far” is, in fact, the true amount parsed?

> If I were writing a parser for expository purposes, I would just return the unconsumed input.

> So I’m confused. Why is this a good design?

I'm not trying to be snarky. I'm trying to understand why one would design a parser or parser library this way, and what the tradeoffs are. (For better or for worse, I don't find myself writing parsers very often.)

> I'm trying to understand why one would design a parser or parser library this way

Simplicity. None of the industrial strength Haskell parsers (parsec, megaparsec, attoparsec, flatparse, happy) are implemented that way.

> What ensures that the “rest of the string” is, in fact, a suffix of the input?

This is not something you want to guarantee.

takeWhile, dropWhile and many are three parsers which might consume 0 bytes. Backtracking via some kind of try parser would probably be unhappy as well.

> I assume the purpose of this design is for compatibility with lazy input sequences

Probably not.

> I would want to know the position and length of the parsed output I don't understand exactly what you mean by these, but these would like be two 'parser' functions (which don't advance through the string), having types:

    positionOfParsedOutput :: Parser Int
    lengthOfParsedOutput :: Parser Int

I don't think these two are implementable directly from the given definition of Parser.

I'm quite far through a language implementation project, and I'm very happy about having rolled my own parser combinators.

The core I used was:

    newtype Parser s a = Parser { runParser :: s -> Either ByteString (s, a) }

* Either is better than Maybe because it gives you room for an error message.

* s is polymorphic instead of String, and here's why:

Your job becomes insanely easier if you split parsing into a lexing and parsing phases. But a lexer is just another parser, which different inputs and outputs. Look!

    lexer :: Parser String [Token]

    parseExpression :: Parser [Token] Expression

But back to positionOfParsedOutput and lengthOfParsedOutput which I said weren't implementable from the above. Simply replace the String type from your definition with a tuple or a struct, in order to carry the extra information.

    data ParseState =
        ParseState { remaining :: String
                   , pos       :: Int
                   , len       :: Int }

    newtype Parser a = P (ParseState -> Maybe (ParseState, a))

>> What ensures that the “rest of the string” is, in fact, a suffix of the input?

>This is not something you want to guarantee.

>takeWhile, dropWhile and many are three parsers which might consume 0 bytes. Backtracking via some kind of try parser would probably be unhappy as well.

I'm not quibbling about a proper suffix vs a suffix. I'm quibbling about the unparsed tail being a suffix at all. I don't write Haskell code, so my syntax here is probably all wrong, but imagine:

    brokenparse s = Just (42, "rest of string")

or, slightly more realistically:

    brokenparse s = (42, toUpper s)

where toUpper represents something that the actual implementation might have wanted to calculate as an intermediate and then accidentally returned as the "rest" of the input.

A totally type-unsafe Python equivalent would look like:

    def parse(input):
        ... do something
        return (result, input[2:])

and has exactly the same issue. But one could alternatively write it (in Python or most imperative languages) as:

    def parse(input):
        input.consume(some number of symbols)
        return output

or quite a variants thereof, and the result seems safer to me, although considerable care would be needed with backtracking. (And even Rust can't actually make this safe as far as I know due to std::mem::swap.)

It's certainly nice for something like a parser to be written in a pure language or style such that backtracking is essentially free. I would imagine that Haskell could express the constraint that the "rest" output of a parser needs to be a genuine suffix of the input using a universal type / threading trick in the style of runST. Maybe the result would be too much hassle to be used in real life.

What you are looking for is called "dependent types" and is the same mechanism that you have to have to prevent the function you seem to insist is so obviously to you the right way to do it from also being wrong by returning an offset past the end of the string. Being able to express such things as "this function returns an integer which is between 0 and the length of the string passed as the second argument" and "this function returns a sequence which is related in some way to the sequence passed as an argument" is a reasonable thing to want, but almost no programming languages provide the mechanism to do it; that said, the languages which do--such as Idris or Coq--look a LOT closer to Haskell than Python.

> returning an offset past the end of the string

I feel if you're dealing with offsets into strings, it's probably easier to stop doing that rather than try to get the type checker to prove it 'correct'.

I tried a linear types implementation:

    newtype Parser a = P (String ⊸ (String, Maybe a))

    parseChar :: Char -> Parser Char
    parseChar c = P $ \s ->
        case s of
            []     -> ([], Nothing)
            (x:xs) -> if x == c
                          then (xs, Just c)
                          else (xs, Nothing)

This guarantees that the 's' is used exactly once instead of dropped on the floor. It's not great because I wanted to drop it on the floor.

Here's it not compiling when I use the wrong string:

    ...
    then ("some string", Just c)
    ...

    • Couldn't match type ‘'Many’ with ‘'One’
        arising from multiplicity of ‘s’
    • In the second argument of ‘($)’, namely
        ‘\ s
           -> case s of

I had no idea there was such thing as an improper suffix.

Here's a quibble-free parser which returns a tail which is neither a "proper suffix nor a suffix".

    earlyTerminate c = Parser $ \s ->
        case s of
            []                 -> Right (s,  ())
            (x:xs) | x == c    -> Right ("", ())
                   | otherwise -> Left "Not a terminator"

> although considerable care would be needed with backtracking

No shit. Show your example.

    A parser for things
    is a function from strings
    to lists of pairs
    of things and strings.

Not mine, don't remember where I got it.

In this case it's Maybe instead of list, which means no implicit backtracking.

It's very much the case that in a real parser you'll want to do more with errors and location and such.

From where I see it, that belongs in `a`. It's your parsing result.

Wait, so I’m supposed to write a parser that (maybe) returns a tuple containing (result of parsing, where it came from) and (rest of string)? Why?

I don’t know if it has a formal name, but I’ve generally imagined that a lot of the point of a strong typing system is to make representing valid values straightforward and to make representing invalid values impossible. This is the opposite — valid values are nontrivial — I would have to encode the position by hand, which makes any use of, say, fmap quite messy because I need to either define a more complicated functor (and maybe make consuming a subset of the parse tree and tracking that fact impossible) or manually pass position context through. And invalid values are all to easy to represent: the context could fail to match the returned string length or the returned string could fail to be a suffix.

> I would have to encode the position by hand ... or manually pass position context through.

You're having a /r/restofthefuckingowl moment, and I understand the reaction, but calm down :D

There is a little wiggle-room for error, down at the 'unit' level. Here's a parser (based on the above Parser type) which consumes input as long as its predicate matches:

    parseWhile :: (Char -> Bool) -> Parser String
    parseWhile pred = P $ \s -> do
        let some = takeWhile pred s
            rest = dropWhile pred s
        Just (some, rest)

It's verbose, and maybe there's a bug in it? (Side note: it also needs to step through s twice, so it's dumb). Here's a more compact version without the 2 * work:

    parseWhile' :: (Char -> Bool) -> Parser String
    parseWhile' pred = P $ Just . span pred

No type-systemy category-theoretical nonsense will stop me from getting a boolean the wrong way around. Maybe I accidentally implemented skipWhile or parseUntil without realising.

So what's the point?

* You build bigger parts out of smaller parts *

Here's the actual parser for my if-then-else expression in my language:

    parseIfThenElse :: Parser ParseState (Expr Untyped ByteString)
    parseIfThenElse = do
        p <- token TIf   *> parseExpr
        t <- token TThen *> parseExpr
        f <- token TElse *> parseExpr
        pure $ IfThenElse Untyped p t f

No manual plumbing or passing in the above code. What about one step up? Here's code which calls the above:

    parseNonApply :: Parser ParseState (Expr Untyped ByteString)
    parseNonApply = parseLet
                <|> parseIfThenElse
                <|> parseLambda
                <|> parseTerm
                <|> parseNegated
                <|> parseShown
                <|> parseErr
                <|> parseParen

Reply on news.ycombinator.com