Skip to content
Hallway
0:00 / 0:00

#haskell#scala#monoids

Monoidal Parsing—Edward Kmett

Scala World

5.9K subscribers • 8 videos on Hallway

YouTube
  • Recommended by 1 person: 1 in engineering communities.
  • Presented by Edward Kmett

Advanced. Deep dive for people who know the field.

14K views9 years ago1 recommendation

Programming languagesComputer scienceFunctional programmingAlgorithms

Edward Kmett explains how to parse programs in parallel and incrementally by leveraging monoids and other algebraic structures.

The uploader added no description.

Why it's here

1 person recommends this

Moments people linked to

u/edwardkmettin r/haskell • Recommends

Monoidal Parsing - Edward Kmett - Scala World
81View on Reddit

u/edwardkmettin r/haskell • Mentions

On “Implementing Cellular Automata with Comonads and Dependent Types”

I wrote up something like this a back in 2013 or so in an old series on comonads and cellular automata. I used `data-memocombinators` rather than try to use a Representable Store implementation or the representable-tries package. It was a fun diversion. Rein Henrichs had come up with a cute little SVG presentation for automata and I wanted to play with it. Parts 2 and 3 push this a little further, and produce the CRCs/Adler16s needed for a (much faster/more compact) PNG version, and for warping the space using comonads as well. Cellular Automata and Comonads: 1 | 2 | 3 More on parallel CRCs and parallelizing mandelbrot and using incremental PNG generation round out the series of pos…
14View on Reddit

u/edwardkmettin r/haskell • Mentions

On “GHC 8.4.1 available!”

Once you start using backpack you wind up needing to make a metric boatload of tiny packages in order to organize your code. If you want users to build on top of them they all have to be public packages. This means that, say, if I ever get around to shipping http://github.com/ekmett/coda to hackage there will be dozens of little packages that few users will care about, but in order to expose the 4-5 public parts that other people are supposed to instantiate manually through backpack, all of those packages must exist. Consider coda-set which provides a `containers`-like `Set` that monomorphized to some particular user type and unpacked. To use it the user needs to provide one package that…
13View on Reddit

u/isovectorin r/haskell • Mentions

On “Balanced parenthesis using Monoid?”

You might be thinking of Ed's talk?
10View on Reddit

u/dima_mendeleevin r/haskell • Mentions

On “Balanced parenthesis using Monoid?”

Right! Thanks a lot! That's why I couldn't find the post link, because it was in video.
7View on Reddit

u/mgsloanin r/haskell • Mentions

On “Monoidal Parsing - Edward Kmett - Scala World”

Great talk! I really like the idea of having robust, efficient parsers. It makes a lot of sense to me for this to be a primary concern when designing a language's syntax. It also seems like a really solid argument for there being an advantage to syntax where indentation is significant. At 33m47s, the claim is made that for most binder syntaxes we care about, the scope intervals are always nesting. This seems to be true if all you care about is "What names are in scope"? However, often languages have name shadowing, so this property doesn't work out if we want to answer "Where was this name bound"? I didn't quite follow why the nesting property is helpful, though. I suppose it is be…
5View on Reddit

u/edwardkmettin r/haskell • Mentions

On “Monoidal Parsing in Build Language Servers by Edward Kmett”

Video from my previously linked Scala World talk on the topic: The main new material mentioned here is a bit more detail about how to deal with handling layout monoidally, and I had a much longer time slot to work through the material with the audience. Code: https://github.com/ekmett/coda
5View on Reddit

u/gelisamin r/haskell • Mentions

On “Monoidal Parsing - Edward Kmett - Scala World”

At [20:54]: > In Visual Studio Code, positions here are lines and columns, but we don't do tab stops, it's just the total number of characters on the line. So I could build a little Monoid for gluing together these positions but it's only a Monoid. Presumably, the first "Monoid" in that sentence was meant to be "bicyclic semigroup"? Let's see, how would tab-stops change anything... `<tab>`, `<space><tab>`, ..., `<7*space><tab>` all indent as much as `<8*space>`, more spaces than that indents as much as `<tab><tab>`, etc. To parse that monoidally, we need to take a sequence of spaces and tabs from the middle of a line, and do whatever corresponds to cancelling out the inwards-facing paren…
3View on Reddit

u/hackeryarnin r/haskell • Mentions

On “Want to write a small thesis about Haskell and Category Theory”

Edward Kmett has a great keynote on Monoidal parsing. I think that building on that, as he himself suggests, would be a good start. Sorry for not providing the link earlier. I was trying to remember exactly where I saw it. Should have know it was a Kmett talk.
3View on Reddit

u/lehmacdjin r/ProgrammingLanguages • Mentions

On “Block Comments are a Bad Idea”

I remember listening to this talk by Ed Kmett about monoidal parsers where he talks about this problem.
2View on Reddit

u/isovectorin r/ProgrammingLanguages • Mentions

On “Are there any good resources for making compilers with first class tooling?”

This is a great talk on designing a language to be tooling-friendly: link to this video
2View on Reddit

u/JeffB1517in r/haskell • Mentions

On “Parser for detecting continuation”

Edward Kmett is working on a slightly more complex problem (allowing for insertion in the middle, but possible incomplete). He has a nice method he's playing with called Monoidal Parsing: link to this video ; link to this video
2View on Reddit

u/bjzabaPikelet, Unnamed Binary DDLin r/ProgrammingLanguages • Mentions

On “Are there any good resources for making compilers with first class tooling?”

This might still be too hand wavy, but here's Anders Hejlsberg talking about the motivations. /u/edwardkmett also has an interesting presentation on 'monoidal parsing' which seems to have some similar ideas wrt. parsing, but built on handy algebraic foundations. Not sure where he got to on that though.
1View on Reddit

u/jaspervdjin r/haskell • Mentions

On “Advent of Code 2021 day 10”

using a Monoidal Parser based on the basic example Edward Kmett gives here data Parens a = Par a a | Bad (NonEmpty a) deriving (Show) mkParens :: Char -> Parens Char mkParens c | c `elem` ">])}" = Par c [] | c == '<' = Par [] '>' | c == '' = Par [ ''] | c == '(' = Par [] ')' | c == '{' = Par [] '}' | otherwise = Bad (c :| []) instance Eq a => Semigroup (Parens a) where Bad x <> Bad y = Bad (x <> y) Bad x <> _ = Bad x _ <> Bad y = Bad y Par _ (x : _) <> Pa…
1View on Reddit