7 ms·

Don't worry, your Parser is a functor

40 points by ubavic 3y ago

KineticLensman 3y ago
This might not help much with practical compiler writing, but there are some great math-y games here as well: https://ubavic.rs/snake/snake.html https://ubavic.rs/snake/snake.html
amluto 3y ago
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?
- mixedCase 3y ago
  From where I see it, that belongs in `a`. It's your parsing result.
  - amluto 3y ago
    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.
    - mrkeen 3y ago
      > 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
- antipurist 3y ago
  > 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/ 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.
- tome 3y ago
  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/FlatParse-Basic.html#t:ParserT 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?
  - amluto 3y ago
    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.)
    - tome 3y ago
      > 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.
- mrkeen 3y ago
  > 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))
  - amluto 3y ago
    >> 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.
- dllthomas 3y ago
  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.
alexvitkov 3y ago
No, a parser is not an functor, an applicative or god forbid a monad. The ratio of the effort academics spend thinking formally about parsers relatively to how often you need to write a parser is probably 50:1. Not as bad as sorting algorithms, where they take up 50% of a CS curriculum, but still pretty bad. A parser reads an array of tokens and spits out a tree. You can write one for any relatively sane grammar by hand in two hours if you need to, infix operators & precedence rules included, with the added benefits of decent performance, the ability to have good errors and the peace of mind that you're not confined by what can be neatly expressed by parser combinators.
- Kuraj 3y ago
  The sorting algorithms are just a tool in learning about algorithm complexity.
  - alexvitkov 3y ago
    If that's the case, it would probably be enough to show O(N^2) algorithm, a O(N*logN) one, and maybe throw in Bogo sort for fun. Even if it's just a learning exercise, if the kids are gonna have to study these algorithms in depth, surely you could pick something more useful as an example to show them, rather than the 10th NlogN sorting algorithm.
    - singron 3y ago
      That's what we did. If you actually spent 50% of your CS degree on learning every nlogn sort, then you went to a particularly bad CS program.
- armchairhacker 3y ago
  This hand-written parser is a functor: data Parser a = Parser { actualParser :: HandWrittenParser } instance Functor Parser where fmap _ p = Parser $ actualParser p instance Applicative Parser where pure _ = Parser undefined _ <*> p = Parser $ actualParser p instance Monad Parser where p >>= _ = Parser $ actualParser p parse :: String -> Parser a -> Either ParseError a parse str p = fmap unsafeCoerce $ handWrittenParse str $ actualParser p
bruce343434 3y ago
I don't mean to be anti-intellectual. But as someone who doesn't know much Haskell and likes to hand roll a precedence climber, my reaction to this is "so what?". But really, what are the implications of this? What does this mean for the code that does the actual parsing, how does this transform how you specify the rules of the grammar in code?
- contravariant 3y ago
  Well it means that if you've got a parser that returns 'a' and a function from 'a' to 'b' then you can make a parser that returns 'b'. And if you've also got a function from 'b' to 'c' then function composition basically does what you'd expect. Which, you know, sounds extremely trivial. The applicative part is a bit more interesting, it means if you've got a parser that returns a function 'a -> b' and a parser that returns an input 'a' for that function then you can make a parser that returns 'b'. This would have been interesting in general categories, but in Haskell function types with currying and application isn't really a remarkable feature so preserving this structure becomes more of a necessity than an interesting feature.
  - marcosdumay 3y ago
    Well, I've had to use parsers in other languages that weren't pure or where one couldn't just translate the "Result a" equivalent to "Result b". That always lead to a bunch of annoyingly error-prone boilerplate. But yeah, that's it. I'd say that half of the Haskell's value is avoiding a bunch of annoyingly error-prone boilerplate... everywhere and recursively.
    - contravariant 3y ago
      Yeah I suppose that is the other side of the coin. Knowing about functors makes it easier to intuit what utilitu functions to write to avoid boilerplate. But sometimes the 'mysticism' gets in the way, this article spends a lot of words on technicalities but very little on the intuition that this should be fairly trivially true. This might make sense in the context for which this article is written, but why this article is on the front page of HN I don't understand.

40 points by ubavic 3y ago

This might not help much with practical compiler writing, but there are some great math-y games here as well: https://ubavic.rs/snake/snake.html https://ubavic.rs/snake/snake.html

amluto 3y ago

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?

mixedCase 3y ago
From where I see it, that belongs in `a`. It's your parsing result.
- amluto 3y ago
  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.
  - mrkeen 3y ago
    > 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
antipurist 3y ago
> 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/ 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.
tome 3y ago
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/FlatParse-Basic.html#t:ParserT 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?
- amluto 3y ago
  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.)
  - tome 3y ago
    > 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.
mrkeen 3y ago
> 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))
- amluto 3y ago
  >> 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.
dllthomas 3y ago
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.

alexvitkov 3y ago

No, a parser is not an functor, an applicative or god forbid a monad. The ratio of the effort academics spend thinking formally about parsers relatively to how often you need to write a parser is probably 50:1. Not as bad as sorting algorithms, where they take up 50% of a CS curriculum, but still pretty bad. A parser reads an array of tokens and spits out a tree. You can write one for any relatively sane grammar by hand in two hours if you need to, infix operators & precedence rules included, with the added benefits of decent performance, the ability to have good errors and the peace of mind that you're not confined by what can be neatly expressed by parser combinators.

Kuraj 3y ago
The sorting algorithms are just a tool in learning about algorithm complexity.
- alexvitkov 3y ago
  If that's the case, it would probably be enough to show O(N^2) algorithm, a O(N*logN) one, and maybe throw in Bogo sort for fun. Even if it's just a learning exercise, if the kids are gonna have to study these algorithms in depth, surely you could pick something more useful as an example to show them, rather than the 10th NlogN sorting algorithm.
  - singron 3y ago
    That's what we did. If you actually spent 50% of your CS degree on learning every nlogn sort, then you went to a particularly bad CS program.
armchairhacker 3y ago
This hand-written parser is a functor: data Parser a = Parser { actualParser :: HandWrittenParser } instance Functor Parser where fmap _ p = Parser $ actualParser p instance Applicative Parser where pure _ = Parser undefined _ <*> p = Parser $ actualParser p instance Monad Parser where p >>= _ = Parser $ actualParser p parse :: String -> Parser a -> Either ParseError a parse str p = fmap unsafeCoerce $ handWrittenParse str $ actualParser p

bruce343434 3y ago

I don't mean to be anti-intellectual. But as someone who doesn't know much Haskell and likes to hand roll a precedence climber, my reaction to this is "so what?". But really, what are the implications of this? What does this mean for the code that does the actual parsing, how does this transform how you specify the rules of the grammar in code?

contravariant 3y ago
Well it means that if you've got a parser that returns 'a' and a function from 'a' to 'b' then you can make a parser that returns 'b'. And if you've also got a function from 'b' to 'c' then function composition basically does what you'd expect. Which, you know, sounds extremely trivial. The applicative part is a bit more interesting, it means if you've got a parser that returns a function 'a -> b' and a parser that returns an input 'a' for that function then you can make a parser that returns 'b'. This would have been interesting in general categories, but in Haskell function types with currying and application isn't really a remarkable feature so preserving this structure becomes more of a necessity than an interesting feature.
- marcosdumay 3y ago
  Well, I've had to use parsers in other languages that weren't pure or where one couldn't just translate the "Result a" equivalent to "Result b". That always lead to a bunch of annoyingly error-prone boilerplate. But yeah, that's it. I'd say that half of the Haskell's value is avoiding a bunch of annoyingly error-prone boilerplate... everywhere and recursively.
  - contravariant 3y ago
    Yeah I suppose that is the other side of the coin. Knowing about functors makes it easier to intuit what utilitu functions to write to avoid boilerplate. But sometimes the 'mysticism' gets in the way, this article spends a lot of words on technicalities but very little on the intuition that this should be fairly trivially true. This might make sense in the context for which this article is written, but why this article is on the front page of HN I don't understand.