5 ms·

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

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
garethrowlands 3y ago
More things are parsers that that though. Here's an article that gives that kind of perspective, https://lexi-lambda.github.io/blog/2019/11/05/parse-don-t-validate/ https://lexi-lambda.github.io/blog/2019/11/05/parse-don-t-va...
garethrowlands 3y ago
A parser isn't a functor in much the same way as a list isn't a functor.
cryptonector 3y ago
> A parser reads an array of tokens and spits out a tree. [...] A parser need not perform I/O -- it need not "read" the tokens. It can function with just normal function arguments only -- it can be pure.
- alexvitkov 3y ago
  "Read" does not imply I/O, you "read" from memory as well
  - cryptonector 3y ago
    The distinction is important. "Reading from memory" (function arguments) is pure, but doing I/O is not. A pure parser can be a functor, while one that does I/O not so much.
carapace 3y ago
You misspelled "curriculum".
mrkeen 3y ago
> No, a parser is not an functor, an applicative or god forbid a monad. Here is my Parser and its Functor, Applicative and Monad definitions: newtype Parser s a = Parser { runParser :: s -> Either String (s, a) } instance Functor (Parser s) where fmap :: (a -> b) -> Parser s a -> Parser s b fmap f (Parser run) = Parser $ \s -> (\(s',a) -> (s', f a)) <$> run s instance Applicative (Parser s) where pure :: a -> Parser s a pure x = Parser $ \s -> Right (s, x) (<*>) :: Parser s (a -> b) -> Parser s a -> Parser s b pf <*> px = Parser $ \s -> case runParser pf s of Left l -> Left l Right (s', f) -> case runParser px s' of Left l -> Left l Right (ss', a) -> Right (ss', f a) instance Monad (Parser s) where return :: a -> Parser s a return = pure (>>=) :: Parser s a -> (a -> Parser s b) -> Parser s b ma >>= f = Parser $ \s -> case runParser ma s of Left l -> Left l Right (s', a) -> runParser (f a) s'
FeepingCreature 3y ago
Have written parsers, can confirm. (With the maybe one exception that "reads an array of tokens" and "spits out a tree" may be interpreted loosely if sufficiently high performance is required.)
- alexvitkov 3y ago
  In my experience the output is always a heterogenous tree of nodes, even if sufficient performance is required. Which is not great since that's quite literally the worst possible data structure imaginable for modern CPUs, but I'm not aware of any other sane way to represent the common outputs of a parser - ASTs, GUI layout trees.
  - viraptor 3y ago
    https://www.cs.cornell.edu/~asampson/blog/flattening.html https://www.cs.cornell.edu/~asampson/blog/flattening.html Flattened AST. Not conceptually different, but a much better performance of implementation.
  - cryptonector 3y ago
    Parsers like simdjson output a sequence of tuples, not trees. You can do a lot with that even if you need a tree in the end because you can filter the stream first, thus using very little memory until you get to the part you're interested in, which you then hydrate by constructing the equivalent tree using just that part of the stream.
josephcsible 3y ago
> No, a parser is not an functor, an applicative or god forbid a monad. What? The post gives a proof of how they are, and you just assert the result is wrong with no evidence whatsoever.
- alexvitkov 3y ago
  A parser is not a functor, you can represent a parser as a frankensteined combination of functors. What I'm saying is that you probably shouldn't.
  - itishappy 3y ago
    Can you say why? I'm struggling to understand your point.
    - alexvitkov 3y ago
      My point is that parsers structured as a combination of parser combinators are worse than hand-rolled parsers, because: 1. It's not hard to write a parser, and one you it's a problem you don't have to solve very often, so the ungodly amount of time people spend thinking about their formal properties and attempting to come up with new parsing methodologies is baffling. Just witnessing the literature leads people to believe writing a parser by hand is some Herculean task, they don't attempt it, they pick up a weird parser combinator library and have bad time. 2. You're limited by what can be expressed by your parsing methodology of choice, which usually means a context-free grammar. There's even fairly basic formats that can't be expressed as a CFG (https://en.wikipedia.org/wiki/Bencode https://en.wikipedia.org/wiki/Bencode). If you're sure your requirements won't change, this is not an issue, but if you're not, a custom parser can give you peace of mind, since it can be extended with literally anything thrown your way. 3. Performance
      - aidenn0 3y ago
        > ...pick up a weird parser combinator library and have bad time. > You're limited by what can be expressed by your parsing methodology of choice, which usually means a context-free grammar. I know those two quotes were from separate points, but parser combinators are not limited to CFGs; pretty much any recursive-descent parser (parser combinators included) will have zero issue with your Bencode example. I pretty much agree with the rest of your post, except for the fact that it's unusual for an entire year to go by in which I don't write a parser. Also, some parser libraries (though not parser combinators) can statically find ambiguities in grammar definitions, which can be helpful if you are designing the language.

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

garethrowlands 3y ago

More things are parsers that that though. Here's an article that gives that kind of perspective, https://lexi-lambda.github.io/blog/2019/11/05/parse-don-t-validate/ https://lexi-lambda.github.io/blog/2019/11/05/parse-don-t-va...

garethrowlands 3y ago

A parser isn't a functor in much the same way as a list isn't a functor.

cryptonector 3y ago

> A parser reads an array of tokens and spits out a tree. [...] A parser need not perform I/O -- it need not "read" the tokens. It can function with just normal function arguments only -- it can be pure.

alexvitkov 3y ago
"Read" does not imply I/O, you "read" from memory as well
- cryptonector 3y ago
  The distinction is important. "Reading from memory" (function arguments) is pure, but doing I/O is not. A pure parser can be a functor, while one that does I/O not so much.

carapace 3y ago

You misspelled "curriculum".

mrkeen 3y ago

> No, a parser is not an functor, an applicative or god forbid a monad. Here is my Parser and its Functor, Applicative and Monad definitions: newtype Parser s a = Parser { runParser :: s -> Either String (s, a) } instance Functor (Parser s) where fmap :: (a -> b) -> Parser s a -> Parser s b fmap f (Parser run) = Parser $ \s -> (\(s',a) -> (s', f a)) <$> run s instance Applicative (Parser s) where pure :: a -> Parser s a pure x = Parser $ \s -> Right (s, x) (<*>) :: Parser s (a -> b) -> Parser s a -> Parser s b pf <*> px = Parser $ \s -> case runParser pf s of Left l -> Left l Right (s', f) -> case runParser px s' of Left l -> Left l Right (ss', a) -> Right (ss', f a) instance Monad (Parser s) where return :: a -> Parser s a return = pure (>>=) :: Parser s a -> (a -> Parser s b) -> Parser s b ma >>= f = Parser $ \s -> case runParser ma s of Left l -> Left l Right (s', a) -> runParser (f a) s'

FeepingCreature 3y ago

Have written parsers, can confirm. (With the maybe one exception that "reads an array of tokens" and "spits out a tree" may be interpreted loosely if sufficiently high performance is required.)

alexvitkov 3y ago
In my experience the output is always a heterogenous tree of nodes, even if sufficient performance is required. Which is not great since that's quite literally the worst possible data structure imaginable for modern CPUs, but I'm not aware of any other sane way to represent the common outputs of a parser - ASTs, GUI layout trees.
- viraptor 3y ago
  https://www.cs.cornell.edu/~asampson/blog/flattening.html https://www.cs.cornell.edu/~asampson/blog/flattening.html Flattened AST. Not conceptually different, but a much better performance of implementation.
- cryptonector 3y ago
  Parsers like simdjson output a sequence of tuples, not trees. You can do a lot with that even if you need a tree in the end because you can filter the stream first, thus using very little memory until you get to the part you're interested in, which you then hydrate by constructing the equivalent tree using just that part of the stream.

josephcsible 3y ago

> No, a parser is not an functor, an applicative or god forbid a monad. What? The post gives a proof of how they are, and you just assert the result is wrong with no evidence whatsoever.

alexvitkov 3y ago
A parser is not a functor, you can represent a parser as a frankensteined combination of functors. What I'm saying is that you probably shouldn't.
- itishappy 3y ago
  Can you say why? I'm struggling to understand your point.
  - alexvitkov 3y ago
    My point is that parsers structured as a combination of parser combinators are worse than hand-rolled parsers, because: 1. It's not hard to write a parser, and one you it's a problem you don't have to solve very often, so the ungodly amount of time people spend thinking about their formal properties and attempting to come up with new parsing methodologies is baffling. Just witnessing the literature leads people to believe writing a parser by hand is some Herculean task, they don't attempt it, they pick up a weird parser combinator library and have bad time. 2. You're limited by what can be expressed by your parsing methodology of choice, which usually means a context-free grammar. There's even fairly basic formats that can't be expressed as a CFG (https://en.wikipedia.org/wiki/Bencode https://en.wikipedia.org/wiki/Bencode). If you're sure your requirements won't change, this is not an issue, but if you're not, a custom parser can give you peace of mind, since it can be extended with literally anything thrown your way. 3. Performance
    - aidenn0 3y ago
      > ...pick up a weird parser combinator library and have bad time. > You're limited by what can be expressed by your parsing methodology of choice, which usually means a context-free grammar. I know those two quotes were from separate points, but parser combinators are not limited to CFGs; pretty much any recursive-descent parser (parser combinators included) will have zero issue with your Bencode example. I pretty much agree with the rest of your post, except for the fact that it's unusual for an entire year to go by in which I don't write a parser. Also, some parser libraries (though not parser combinators) can statically find ambiguities in grammar definitions, which can be helpful if you are designing the language.