Functional Parsing - Computerphile 

Profile picture checks out.

Because it is normal. He's done this kind of code many times before.

And no StackOverflow screen up!

The Graham Haskell Compiler

That's totally normal

Yup, compilers are one of the more functionally pure things you can program. They are VERY complex, but they just are fancy "String input, string output" machines when you look at the big picture

Now go learn apl

That's a cool one.

I think it sounds like an ideal explanation, when you know the subject well beforehand, interesting.

> claims we don't need to know Haskell > isn't explicit about which words are imported from his module and which are keywords.

As of the finished module in 19:35: 　 The import declaration allows use of the exported definitions from module Parsing. There's also a standard library module Prelude which is imported by default if not mentioned. 　 Equals= defines values. 　 Do and >=) operator, i.e.: do { b >= (\b -> c) 　 Module Prelude exports typeclass methods add(+), multiply(*), alternate(), bind(>>=), and return, and also exports the implementations of (+) and (*) for whichever of the various number types the end program might use. The defaulting rules in the REPL session seem to select the Integer type. 　 Module Parsing defines type Parse, function char, and method implementations for (), (>>=), and return. The bind(>>=) method does all the heavy lifting of combining two parsers into one larger parser. 　 The main module defines functions expr, term, and factor.

That's one of the key takeaways of Functional programming, "Higher-Order Functions", or functions that use other functions as parameters. A short and sweet paper is the Functional Pearl about Sixth-Order Functions. Why would you need a Sixth-Order Function? When you are using parser combinators!

Doesn't sound like something I would need a video for. It's clear from the name "parser combinator". It's clearly something that combines parsers into a parser, and then it's obvious those are then combined by further combinators and that's how you can build the whole root parser. - This video shows how to do that with monadic combinators, and the which I guess is just a concat function for the lists.

The operator is most likely a custom operator definited in the package.

... and then the example parser doesn't even return a tree, but just an integer.

@@PauxloE Agreed - I guess the video couldn't get much longer though, but I'd have loved to see his parser return an AST and then implement the logic to interpret it!

@@PauxloE It evaluates the tree as it goes along., and it is walking the tree even though we're not seeing it. To get a tree, you'd modify the grammar to so that the do block returns a tree, rather than the the result of evaluating the math expression. The biggest problem I see with this toy example is there's no error handling. Malformed input can just get lost without affecting the tree or warning the user.

gi70st I can fix that for you... It takes an array of chars and gives back an AST

It was so confusing how he did that switcheroo. I was there thinking "how does `return (x+y)` make it produce a node `"+"` with branches `x` and `y`?" And even after acknowledging that this is really evaluation, he kept calling it a parser, even though the beginning of the video he insisted that what a parser is to him is something that produces a tree as output.

what is the name of the book? okok i just google it. =D

@@keestv3116 Programming in Haskell :)

I, too, used the book. Excellent resource for starting Haskell.

> Parsing in Haskell was a bit hard in the beginning though. Getting used to all those new operators (, , , among others) was brain-breaking, initially.

Oh he wrote that book. That book got me through first year in uni. I bought it in desperation for my resit. It was the only module I had to resit and I still harbour a special hatred of Haskell.

He sounds unambiguously Irish to me, but as far as I know, he is actually Scottish.

One of the limitations of top-down parsing methods such as functional parsing is that left recursion results in parsers that loop. One possible solution is to transform the grammar first to eliminate the left recursion. Another is to define special-purpose combinators to parse operators that associate to the left.

instance Alternative Parser where empty = P (\inp -> []) p q = P (\inp -> case parse p inp of [] -> parse q inp [(v, out)] -> [(v, out)]) this special 'or' operator executes left side parsing (in this case '-' char followed by natural number), if it succeeds it returns result, if not it will return right side parsing result (in this case just natural number)

That gets into recursion schemes. Instead of consuming strings, you consume and rebuild trees. There's quite a bit involved there as different schemes have drastically different capabilities. The important bit is that those pieces compose well, and have some very nice optimisations.

It backtracks. It tries to do the '+' case and if it can't it backtracks and does just the term case.

It's not just you - there's a reason quite a few experimental compilers are implemented in Haskell.

@@JobvanderZwan Thanks for the info - makes a lot more sense to me than people pushing Haskell as a general-purpose programming language. At least that's how I feel right now (I do Python for a living), but I might revise my judgement in the future :-)

Agreed. In my current lecture we're implementing a parser in OCaml (close enough I guess). The thing is that parser/compiler need a lot of things that are close to theory (recursion, trees etc...) and pattern matching, all of which is at home in any functional language.

He replaced the Tree-type with an arbitrary Type 'a'. So a parser can now calculate anything you want. You might want to keep calculating a tree, then a would be equal to Tree or you want to calculate something different like e.g. an integer (a=Int).

To be specific, the 'a' is a type variable. In Java, C++, Rust, or similar syntaxes it would be the T in Parser. In Haskell syntax, types and their parameters are written one after the other without brackets, just like Haskell values. Some examples and their C-like equivalents: List (Pair Int Char) = List Pair (List Int) Char = Pair List Pair Int Char = List (this is probably an error.) Parser a = Parser In C-like syntax type variables have to be introduced explicitly, such as with the template keyword in C++, but in Haskell you know any name that starts with a lowercase letter is a variable. Again, just like in term-level expressions.

You can say that a tokeniser is a parser from a String to a List of Tokens. Rinse and repeat with the List of Tokens until you have what you want.

I felt that way when I first saw Haskell, too. I've been learning it as a hobby since August and it's totally revitalized my interest in computer science on the whole.

s/yo/to/ !

That's not a sign of manhood. It's a sign that he has a clinical case of needing to be different. ;-)

​@@lepidoptera9337Yeah, "different". Because he uses the text editor that comes with every computer ever. He is so quirky :/

@@sebastiangudino9377 It doesn't come with Windows, child. Why would it? Windows has specialized IDEs of all sorts for all kinds of R&D. I am currently using Eclipse with an embedded microcontroller environment. The hardware debugger is fully integrated with the code editor and I can step through my program line by line. I could never do that with vi. OK, now you got your two minutes of attention. I hope your basement has gotten a little warmer. ;-)

@@lepidoptera9337 WSL is a POSIX system that comes with windows from Windows 10 onwards. It includes vi

It's effectively the State Monad.

@@Dan-gs3kg If all parsers always produce singleton list, then parser monad = state monad as you said. So parser monad could be used as state monad. *But can you show the converse?* because that is what it means for me to say 'parser monad is effectively state monad' and I don't yet see how.

@@ancbi I'm a bit fast and loose here, but you can see the correspondence between say: > Parser a = P (String -> (a, String)) > State s a = S (s -> (a, s)) Where (s ~ String), and (~) is Type Equality The more general statement: > Parses a = P (String -> [(a, String)]) Is a bit different, but then we can also make a more general statement about what the State effect is. > StateT s m a = S (s -> m (a, s)) Where (s ~ String, m ~ List), we get (Parses) Where (s ~ String, m ~ Identity), we get (Parser) If we want zero or one parse results, we replace List with Maybe, if we want literate parse errors, then we use Either. All of this hinges off of the initial State Effect.

@@Dan-gs3kg Hey. Thanks for making it clear. It was my ignorance of StateT making me say what I said.

@@ancbi you're welcome. If you want to look at how "stacked" a parser combinator library gets look for the packages: megaparsec, parser-combinators, and yoctoparsec. The first is a fully featured library that generally dominates in performance, and expressiveness in both passing and error reporting. Yet it operates on the same principle seen previously. The second is a library that can interface with any parser combinator library. This is possible because of the algebraic structure of parser combinators. In other words, those principles are very permissive. And the third is very reductive of what a parser combinator library is. It's effectively a pile of free theorems (invariants) and one primitive: The single token matching primitive. At some point you figure out that a principled outlook is the most constructive.

Of course it's not useful. It's an example for explanation no industry standard parser. Subtraction and division are incredible similar to their counterparts. A negation would be a different rule like "-" expr but this introduces a parse conflict since the "-" can be subtraction or negation (so called "shift/reduce conflict). That needs to be handled but suddenly the video would be 1hr long and way harder to follow.

> parse expr "2 + 3 * 4 / -(-10/5)" *Drake nah meme > 2 + 3 * 4 / -(-10/5) *Drake yeah meme

@@JNCressey I just realized that I want all my compiler errors to be presented as memes

I think you're referring to the difference between a binary and unary minus operator. / has essentially the same precedence as multiplication so it shouldn't be hard.

@@gabe_owner Well partially, yes, I'd like to see how both unary and binary operators get handled. But I'm also not seeing exactly how operators with equal precedence (like +- and */) get handled with this scheme as well, so an example of that would be helpful.

It is, but more of a stone tool than this kind of weapon.

Apple, definitely upgrade your GHC. Try not to use the versions of GHC that come with the package managers of various OS choices as they tend to be quite out of date. Use the curl (or wget) install scripts that you’ll find on the websites for either of the things I’m about to mention in quotes. Either install the Haskell “Stack” tool for managing isolated sandboxed versions of GHC on your system (so you can have different projects operating with different GHC versions) or use “ghcup” to install Cabal for you to do something similar. But yeah, avoid whatever is in your package manager like the plague. And GHC 7.6.3 is pretty out of date with how monads are implemented. There’s been some significant language shifts since then.

Apple also add the line “return = pure” within the Monad instance declaration (...just above the definition for (>>=) is where you’d normally put it).

NWN thank you very much! Unfortunately I need to use specifically this version for my university coursework

Apple that’s a shame. What university/subject is this? Lectures should really update their course materials + backend. In GHC 7.10 the “Functor-Applicative-Monad Proposal” was implemented that made all Monads have Applicative as a superclass, which is a pretty big change and something that should be part of your learning ecosystem.

Yes that guy is a genious

Well, the same I guess.

@@bingloveskoki Nah, this one is just a toy :)

painful

What is the main definition of a parser, i thought it was breaking out information from structured data using rules?

@@JmanNo42 Yep, and the structured data is always a tree when calculating expressions. Operations always return a single result.

its a variation of it. Basically a functional/monadic version of it. Solves some problems like running out of Stack. It also makes backtracking a lot easier and the syntax smoother (but more complex). It also means that you can skip the lexer part. recursive descent rarely works well in imperative languages and it has a lot of boilerplate. It works a lot better in functional and is a lot compacter. EDIT: The correct term is "parser combinator" when you wanna lookup more on google/wikipedia.

@@_aullik Backtracking? Wouldn't one want his grammar deterministic? So that, you know, parsing time is linear in the length of the input.

​@@Ceelvain Yes and no. Specially if you are context sensitive (which is completely possible here) backtracking can give you some nice advantages. Obviously for the cost of performance. That being said, if you keep the parts where you use backtracking short and/or use mnemonics. This way the performance overhead is pretty slim. If you make mistakes with this, it will cost you performance. The big advantage however is fast prototyping and relatively easy unit testing and that you can do things you cant with regular parser generators. Best case performance is close to parser generators as you can skip lexing. What I have seen in the real world however is usually quite a bit worse. However if I only have to build parser for smaller (max 1k lines) Inputs I prefer this option.

One way that parser combinators differ from recursive descent parsers is that they are declarative, rather than imperative. This means that, for example, you might choose to implement the resulting parser as a LR(1) parser, or maybe using CYK, because the parser itself does not describe the implementation, but only the grammar. Of course, all the actual parser combinator libraries I know use recursive descent in the end :)

​@@_aullik Recursive descent has worked very well in imperative languages for many decades. As for skipping lexing, that is a matter of optimisation, as I understand it.

The implementation reflects the grammar. Alternative parse paths are separated by (), where alternate expressions of the same term are separated by (|).

I don't think it does, but that's because this is a pretty naive implementation (which is totally fine BTW - that way more people can understand what roughly happens behind the screen). If you want O(n), take a look at a full parser implementation like Parsec, Megaparsec or Attoparsec (just to name a few).

No. It may have to do a bit of backtracking when the parser should take the second possibility in the sub-parsers. This means re-parsing some stuff, making it non-linear in complexity. For example, consider the simple case "2" and the parser from the video. First, it tries to parse this string as 'term+expr', which expands to 'factor*term+expr' and ultimately '(expr)*term+expr'. The '(expr)' fails, so it tries the second alternative of 'factor', which is 'int'. This succeeds, so it goes back up the tree to parse '*term+expr' out of (2, ""), which fails. Therefore, it tries the second alternative of 'term' in 'term+expr'. This ends up parsing (2, "") again, with '+expr' left over to parse out of the empty string. This again fails, so the second case of the 'expr' parser is used, which eventually succeeds after another round of backtracking in the 'term' and 'factor' parsers to produce the final result: (2, "")

I mean, a parser could be built on a for-loop. Parsing is basically just the process of reading some data, like a mathematical expression, and understanding it. Math expressions can't always be calculated left-to-right (i.e. in the order you or your program would read them), like (1 + 3 * (7 - 1)), so one approach you may take is to decode the expression into objects -- a tree structure -- and then, after you've read and understood the whole expression, you'd use that data to calculate it in the right order. The video's approach is to use functions that are chained in sequence, and those functions could in theory use a for loop. For example, we may have a parser function for variable names, which would want to use a for-loop to read until it sees a character that can't be a variable name. We may have a parser function for whole numbers rather than single digits, which would take the same approach.

Programming language interpreters and compilers. JSON parsers, syntax highlighters, linters, transpilers (like Babel) web browsers that parse html and css, web scrapers all use parsers. Whether the average working programmer uses them is another story. Another example would be if you find yourself making a DSL for adding content to your video game and would rather not write the content in C#, you might consider writing a parser. Anytime you take input and transform it to produce some for of structured output, you are in essence writing or using a parser

According to LangSec, all input should be parsed into a well defined structure (i.e. a type that represents only the set of valid input) before being processed. That way you aren't making assumptions about your input that can be exploited by attackers. The type of parser used should match the complexity of the Grammer used to define valid input, following Chomsky's hierarchy of Grammers.

Either don't return a list of possible results, return a proper stream of possible results, or something else. Eg "Parser a = String -> (a, String)" which only returns the one. The grammar is very literate, though the snag is learning what the combinators mean initially.

parzer

It uses recursion. Higher precedence operators appear lower in the stack. It does multiplication before adding because in the grammer and parser multiplication has to be parsed and evaluated before addition. Look up Jack Crenshaw's series Let's Build A Compiler for another explanation. His approach uses recursive descent parsing instead of parser combinators but it is the same idea

You should make a video. I would like to see how it works

It's giving a list of all the ways the input can match an expr with something left over. The last example gives the answer "it can't be an expr with anything left over". In a context where you could have an expr or something else, it would first pass the whole string to the expr parser, then pass the whole string to the other parser; choices remember the original string, and pass that to each parser, rather than passing the unconsumed part to the next parser like sequences do. If the expr parser gave [(nothing,"(2+4")], that would mean it was okay for an expr to consist of nothing.

I'm not going to lie, this seems like a terrible idea. Using repeated string replace is a great way to turn your parser (anything that fills the ROLE of a parser, no matter the mechanism) into a turing machine that treats malformed/malicious input as a turing-complete programming language. I'd recommend looking into the LangSec approach to parsing. The computational power of the automaton you use to parse input should match the complexity of Grammer required to describe the set of valid inputs. No more and no less.

There are all kinds of words that are pronounced differently in each dialect

Terminal + vim & ghci