Don't worry, your Parser is a functor | Hacker News Reader

Don't worry, your Parser is a functor

blog.ubavic.rs

40 pointsubavic59 comments

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?

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.

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.

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.

As the last sentence might imply, it's not meant to be so much of value for building parsers as for proving things about the parsers as-built...

It means you can map over parsers. For example, if you have a parser that returns numbers formatted as strings you can turn it directly into a parser that returns a number.

I learned Haskell this year.

After reading this article, the conclusion I drew was, "Cool, so I can `fmap` over my parser now and transform what I parse using functions."

To answer your other questions: I'm not sure it means much for the code that does the actual parsing, nor how you specify the grammar's rules, it's more about being able to transform the output using functions.

If your static analyzer is a function, you could now write `fmap staticAnalyzer myParser`.

> about being able to transform the output using functions.

Can't one always use functions to transform other functions' outputs?

> If your static analyzer is a function, you could now write `fmap staticAnalyzer myParser`.

rolls eyes

    def compile(text):
        ast = parse(text)
        ir, symtable = static_analyze(ast)
        asm = lower(ir, symtable)
        return assemble(asm)

Ability to write that in the point-free style is really not that important, IMHO.

Yes, but if it we're talking about parser monads, then usually you can't apply a function directly to a parser's result without either:

1. Being within the same monad. For example, you can `bind` a `Parser a` to a function only if it returns `Parser b`.

2. Performing an actual action and breaking it out of its monad.

For example, if you're using the Parsec library, and you have a `Parser Int`, you can't get to that int without using a function like `parse`, performs the actual action of parsing input text.

With a functor, you can compose a `Parser a` within an `a -> b` function, instead of having to return `Parser b` in your function.

So if you have a `Parser Int`, and you want to turn it into a parser that multiplies its parsed input by 2, you can write `fmap (*2) myParser`, instead of having to write `myParser >>= \a -> return (a * 2)`.

Parsers being functors means it's easier to compose them with other things, without having to actually perform the parse until you need to.

I don't get the last part of the comment. `myParser >>= \a -> return (a * 2)` doesn't have to parse immediately, right? You could push that function at the end of a list and only apply it during `parse` anyway.

Correct, that function doesn't have to parse immediately, but it does have to be aware your monad exists.

This isn't a problem if you're the one writing the function, but if you're using a 3rd party library that doesn't know about your monad, then fmap can be very useful.

Right, so you're essentially talking about how in e.g.

    class Parser:
        def __init__(self, text):
            self.text = text
            self.result = None
            # other inners state/context fields

        def parse(self):
            self.parse_top_level()
            return self.result

    def parse(text):
        return Parser(text).result

the free function "parse" throws away the inner context. When one uses parser combinators, there is no single monolithic Parser class which one may extend with whatever additional methods necessary (and maybe take some free functions as callbacks, why not); instead there are lots of smaller functions returning the leftover contexts together with the results, and you have to combine them somehow, together with free functions.

> without having to actually perform the parse until you need to.

I'd rather parse my input before starting semantic analysis on it. Although if you really want to have a one-pass translator, literally being a composition three functions, `parse`, `analyze`, `emit`, with no visible intermediary structures then yeah, this allows for it.

But I'd argue that's more complicated than having three non-entwined passes with explicit, designed data structures serving as interfaces between them instead of invisibly unevaluated thunks; not to mention the sheer complexity of doing everything in one go (why do people even claim the single-pass compilers are simple?)

You make a valid point about the added complexity of combining parser combinators with functors and other concepts.

Honestly, if I were writing a compiler, I would go with your approach as well.

It opens up a huge toolbox of tools that work with Functors and Applicative to make parsing easier, and proves that using those tools will work predictably.

As someone who works primary in a functional language I'm pretty convinced that most of these types of things are elegant solutions to self-created problems.

tbh this is how I feel about most tech.

I was in front-end dev for many years and a lot of the framework features felt like that. Now I'm doing back-end devops stuff and Helm/K8s/Terraform really feel like that. Everywhere you look, it's nothing but hammer factory factory factories.

In general, if your reaction to finally understanding "functors" is "so what?", there's a reasonably good chance that means you've actually understood them: https://jerf.org/iri/post/2958/

The useful thing about functors isn't that they are particularly complicated, it is that they are a useful interface to be able to write things generically over. It's very similar to iterators. Being able to present items out of some collection one at a time is "so what?" It is not interesting on its own. But having a common interface over them allows for a lot of good code to be written that you can't write in a language that lacks them, and have to one-off ad-hoc all the time.

That a Parser is a Functor means you can apply all the functor tools in writing them. This is one of the appeals of parser combinators, which is again not that they are some sort of brilliant insight on their own, but that they work well with the generalized tools rather than needing specific implementations of them.

If your reaction to iterators is “so what?” then I would say you fundamentally don’t understand computation.

Asking “so what?” about iterators has plenty of useful answers that will aide you in programming. The same is not really true about functors.

The linked article goes into detail about what I mean about that, but what I mean is that some of these concepts have a lot of mystery around them that are not deserved. Many people penetrate this mystery and then wonder what the deal was with the mystery. For these particular concepts, that's generally a good sign.

Iterators are important... but they are not conceptually complicated. They're just a way of getting a "next element". Behind that may be a lot of complexity for some particular iterator, but that complexity should be accounted to the implementation, not the concept of iterator.

> Iterators are important... but they are not conceptually complicated.

To me, the essence of asking “so what?” is primarily about importance not complexity. When you ask “so what?” You’re essentially asking “Why should I care? What can this do for me?” It doesn’t really matter whether or not the subject is complex.

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

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?

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

> 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.

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.

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.)

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.

https://www.cs.cornell.edu/~asampson/blog/flattening.html

Flattened AST. Not conceptually different, but a much better performance of implementation.

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.

> 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.

GP isn’t actually saying that a parser isn’t a functor. They’re loudly and performatively saying that they don’t care.

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.

Can you say why? I'm struggling to understand your point.

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). 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

> ...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.

I agree with this

I struggled with this formal bullshit despite having exp. with handwritten parsers for PL.

Well, the post shows that the given function is a functor.

However, I might argue that calling the function a "parser" is a bit of a stretch. In a toy, abstract sense, sure, and maybe there's a formal definition of "parser" that it conforms to, but just because it's named a "parser" doesn't really mean that's all a "parser" is when we talk about it in other contexts.

Parsers, to me, in a professional software engineering sense, need to have error handling, performance and memory guarantees, the ability to do "best case" parsing and return a number of errors all at once, and so on.

So one interpretation of "No, a parser is not a functor", despite the proof here, is "I reject that the toy example here being called a parser is sufficiently close to what I would call a 'parser', and what a 'parser' is to me is not a functor [because of these other things not captured by the example]".

I tend to agree with that. Haskellers don't have an exclusive claim to terminology, and I don't think "parser" is defined formally enough that we all must agree on it.

The sorting algorithms are just a tool in learning about algorithm complexity.

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.

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.

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

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-va...

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

> 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.

"Read" does not imply I/O, you "read" from memory as well

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.

You misspelled "curriculum".

> 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'

Reply on news.ycombinator.com