sfscala.org: Li Haoyi, FastParse: Fast, Programmable, Modern Parser-Combinators in Scala
Recording: sfscala.org: Li Haoyi, FastParse: Fast, Programmable, Modern Parser-Combinators in Scala
[Applause] um cool so this talk is going to be about fast pass which is a par combinator Library I wrote um if any of you want to follow along online the slides are online at tinyurl.com fastar the agenda for for today we will spend some minutes talking about passing text some minutes talking about fast pass go a bit more into the internals and other details about it and then we'll spend some time live coding and I'll leave 10 minutes for questions so my name is hoe and I'm currently on the Dropbox developer tools team previously I was on Dropbox web infrastructure and in my open open source work I've done a bunch of things in with SCA JS and with emonite um but today's talk is going to be none of those today's talk is going to be about paring text so if you are a developer and someone gives you a text file that and tells you hey there's in important data in this text file these are the tools that you typically have to deal with it starting from the most convenient but least flexible string split and string replace to the most heavyduty but most flexible Lex Yak or antor so the ones on top are really convenient but don't really work once you get past something like a file with one one string per line if you have a file with comma separated and you need to escape commer your this this will not work it's too much for that you can use regx but reg xers don't really work for anything recursive common recursive things include things like math or Json or yaml or any of these very common formats which are recursive um so that doesn't work so if you can't use regex you'll fall back to a handroll recursive desent parser so that looks something like this this is example from the Scala compiler you basically have a bunch of methods every method returns some data structure and parses some string that is usually a member of the object that's all these methods are part of so enumerators will try to parse the first enumerator have a wire Loop keep checking things next token pass the next numerator convert the into a list passing each numerator you'll check the token you'll check whether it's the first token you'll call other methods and these methods will go on and call other methods Each of which will par a particular um a particular section of text so these are very common and in fact it's so common that these are things that people ask you if you go for programming interview hey interview candidate write me a parasa for some kind of math expression and you have to do it in 40 minutes and it people like it because it's tedious it's repetitive and it's very error prone so gives you lots of things to ding during the interview debrief later um so Scola uses a hand roll because send parsel the other things that people tend to use to write parsers is Lex and antler or yak and the other tools which are similar bison gyon these are things which are used by intell by the python interpreter by the Ruby interpreter you basically write your you write your grammar in some kind of abstract syntax and then that get generates a parsel in like C code or Java code which you then can evaluate sorry that can compile to get a parser object of some sort of parel method which you then can run at run time so this generates very fast parel but it's kind of conf complex and confusing first because you need a multi-stage compilation process I'm no longer compiling my par I'm compiling the thing that'll compile into my parel and as a result is complex and so for example this is example from the Ruby Yak file and you can see that apart from the Pretty elegant grammar definitions up here you have these Mex thin really naughty imperative C code as well as these things that look like comments but I'm quite sure are not actually comments because we take them out the parel will break and it's the same on the right so you have a nice grammar definition with a bunch of pretty icky imperative code with a bunch of magic variables which I'm quite sure are macros in order to be compiled into a parser which will then be compiled into something you can call so some of you some of you if you have similar thoughts as me may ask why do par why do people use parser generators instead of configurable pass parsers I mean I don't have a web app generator to write my web app unless I'm using rubby on Rails but people here probably won't be I won't have a type Checker generated to to write my type Checker code I won't have a matrix math generator to write my Matrix code I have a matrix library or I have a type Checker maybe in the library or have a web app framework so why do people in writing parsers tend to use parsel generators and the answer is that you don't really need to have parer generators so this is something I discovered a few years ago if I want to par math I just import Scala util parsing combinate parsing combinator the all extend this weird trait and then I can immediately start defining what looks like a grammar in scolar code similar things can be done in F or or hascal or other languages so plus is a string plus a number is a repeated I'm using a regex here but a repeated digit from 0 to 9 and an expression is a number Fall by plus Fall by number and that's it this is your parsel I can immedately call do pars all on uh string and get some useful result or I can call parasol on a invalid string and get a error which is exactly what you are no need for a complex regex no need for while loops and many function calls you define your grammar and you're done another thing that's nice about this is that the parsers are all statically typed so I know that plus pares a string I know that num pares a list of strings I know that expression gives pares a list of strings Follow by string Follow by list of strings I can't screw that up you can transform the Paras very easily so let's say I don't want this I don't want this weird syntax tree structure I want the number which is the result of the expression I simply say well instead of passing a list of strings I'm going to map you make the strings into one big string and then convert it to an integer and instead of passing this weird list followed by a or well after convert this to integer this will be pass an integer so instead of passing a integer Follow by a string Follow by integer I'm going to map it ignore the ignore the string in the middle because I don't care what the plus parts is it's always do the parts of plus and pick the left and the right integers and add them and that's all you need in order to parse actual numbers sorry to evaluate the actual arithmetic while you're parsing the numbers so that's great and what's even better is the fact that it's totally trivial to make your parsers recursive so I just need to Define another Rule and have these two rules recursively depend on each other so an expression is a side you could use a better name I'm just calling it a side a side Follow by plus Follow by side and I add it up same as just now a side is either paren with expression in the middle or it is a number and that makes perfect sense and suddenly you have a completely correct completely recursive ma math evaluator in four lines of code so next time someone ask you to do this during interview you should totally whip out par combinators and finish interview in like 5 minutes and spend other 45 minutes chatting so that's great and Par combinators are great but they have their problems which is why people don't actually use them Chief among the problems in my opinion is the performance which if you look at this is a benchmark for parsing Json using Jackson which is a common Java Library using spray Json which is a common scalar library and using scalar par combinators and something which would take one second to paring Jackson would take 5 minutes of par using scal par combinators so as much as you say performance doesn't matter 1 second to 5 minutes does matter in that I can click on a button and wait one second if you make me click on the button and wait 5 minutes I'll be really unhappy and similarly if I click on a button and and it waits 1 minute that's fine but if I click on the button and you make me wait 5 hours I will be extremely unhappy so this isn't a 300% slowdown this is a 300 times slowdown or 3 30,000 per slowdown in exchange for getting very nice Sy tax to write the parser in so there's another parser combinated Library out there which in a scal community called parabolic 2 and it's meant to be very fast I think it's used in AKA HTTP AKA streams and other things so it is used in the real world and it's fast enough not 300 times slower than a hand R parsel but it has problems how fast is fast how fast is fast well it turns out that parabol 2 is within a factor of three or four of the fastest handrolled um Json pares you can find on the market in scy and Java so if something takes one second using a handrolled 1500 line imperative parer full of Y loops and mutable variables everywhere using a 50 line of 40 line parabolic parser it would take 3 seconds instead of 1 second and maybe that's okay in exchange for saving like 20x your verbosity in writing the parsel and that means if you want to par something you can do it quickly without having to spend weeks carefully crafting this huge thousand line code code base but what are the pro what are the other problems with parabol that I hinted that one problem with parboil in my opinion which is the biggest one is the error messages par this is an error message that parboil 2 tend to give you and the thing is Powerball 2 doesn't just just give you this it gives you eight pages of this when you make a mistake so this is equivalent to PowerAll 2 saying you are wrong they're not telling you anything after that because there's no way you can figure out what went wrong with this error message and if I tell you what did go wrong it is I got the number of parameters wrong in my Lambda maybe I shouldn't have gotten it wrong but parall 2 also could have just told me that rather than spitting out 15 kilobytes of text at me so if we add this to our existing tool tool set we have all the old school things that people have known since 1965 and then you have scalar par combinators super convenient super fast to write and flexible but very very very slow 300X 30,000 per slower you have parall two which is fast 1/3 1/3 of speed 3x slow is maybe still pretty fast very flexible but gives you crazy error messages and the API is is such that it will you will find these error messages you trust me you will not be able to avoid it no matter how hard you read the documentation it will explode in your face so into this crowded Market steps fast par fast par at its core looks like this a parser which is parameterized paror of a type T has a method par which takes an input string and a index to start that you can start somewhere halfway through the string it returns a result when you par something which is either a successful par with a s with a value and um the index at which it succeeded you can parse a partial parse so for example you can parse the first 20 characters of The Stream without having to go all the way um and it can return a failure which tells you the last parel which failed for example maybe it failed to par an expression maybe it failed to pass a close PR and uh the index at which that last parel was tried and failed so it is a very simplified overview but give you a feel of what fast pars is like you have a parser you call pars you get something which can either be success or failure that's it um from the outside how do you use fast pass use fast pass like this this looks very similar to what you saw earlier with the par combinators differences I don't need to extend anything here that's convenient I guess the import is different that's no big deal I had to wrap all the parsers in this weird P thing which P stands for parser but since you're going to be wrapping everything in parsa parsa par parsa I just called it P and some things are called differently instead of using a regx I have this thing called Char in and pass sequence of characters instead of repeat parasor parasa do repeat which is the same um you have this weird do exclamation mark operator which is what you use to capture a string because you don't care about most strings in your paring so instead of having to manually ignore the strings you don't care about which are going to be many of them like every per every comma every plus you don't care about um with fast pass we I asked you to annotate the passes you do care about with a estimation Mark map is the same um this looks exactly the the same this looks the same instead of mapping and ignoring the middle uh plus I just have a toule because I the plus is ignored by default unless I use exclamation mark to capture it so there's some details which are different but overall it looks about the same four lines you get a nice recursive math parser and you can parse things that and it works including recursive things and you can parse bad things and it will fail so that's what F fast parse looks like again all the pares are typed and this is a set of operators that fast parus gives you so it's not a tiny set but it's may be okay so the basic ones are all on the left a string can be used to parse anything it returns unit because you don't because you probably don't care about most things you're parsing unless you use dot exclamation mark in which case it returns a the parel will provide a string which is the thing that was pared Tia between two parsers will give will give you a parsel that parses one after the other and will then give you a return a tle of both values so is not quite so simple if the thing on the on the left is a tle it'll be a bigger tupple and a bigger Tuple but it's close enough it just gives you a toule of the values that you care about A or B will try a and then it'll attempt B after that and it'll return something which is the common superclass of A and B so if a is returns a vector B returns a list A or B will par that returns a sequence for example cut is same as sequence except I'll go into more details later but why it's different repeat makes sense if it returns a a now returns a sequence optional returns option you have look ahead positive and negative just like reg X's you have all the same map flat map and filter so if I have a par returns a string I map it to an integer and I have a par returns an integer and these are similar to The what you see on Collections and you have a few like predicates which are generally useful like I want to par some character satisfying a function I want to par some character in a list of characters I want to keep I want to par a string in some set of strings without having to manually do Like A or B or C or D or e or F you just have put the list of strings into string in and you'll pass any of them so how does fast par compare about performance well fast paris's performance is within a for a Json par within a hair of parabol 2's performance so again about three to four times slower than a handroll recursive descend parser but 85x faster yes that's correct 85x faster than scalar par combinators so performance is okay it's not as fast as Jackson but it is not terrible it will not take you 5 minutes instead of 1 second it'll take three to four seconds another par benchmarked is the Scala par Britain using scal fast pars and it's about 11x slower than Scala compilers fast 10 roll recursive descend parer so this is about as fast as you can expect in Scala probably and this is about as slow as you can expect fast pars to perform in comparison as the grammar get more complex fast pars performs worse compared to a handroll parsa and there aren't that many grammars which are more complex in the Scala language grammar so this is about the worst case you can find like 700 lines of parsa combinat code versus 7,000 lines of very fast recursive descent code so why can fast parus be 85 times faster than scalar parus combinators even though it looks exactly the same from the outside and the answer is that the outside is not all that matters the inside also matters and so if you look at what's inside scalar par combinators for example this is a cut operator which I still haven't explained but I'll explain soon but it basically pareles the thing on the left followed by thing on the right and if the thing on the right then fails it won't backtrack but we'll go into more details later so you have this once parel thing which takes a Lambda you this really elegant monadic like this bwing to a p pass into this commit thing which P itself is this Lambda or by name parameter which gets wrapped in Lambda gets bound to a b and it returns this new Tilda thing which has a and b inside and I name it very elegant very FP very monadic very slow so let's look at why it's slow here I'm allocating an object with two fields at minimum I'm passing in A and B it's probably going to have two Fields I didn't actually check but probably has two Fields here I'm allocating a Lambda with capture which captures two things two variables know in closing scope p and this so when you allocate a Lambda which captures which captures things it allocates a object with these two things as fields and initializes and puts them on the object here I'm allocating another Lambda with three things in scope object which with three Fields here I'm calling commit which takes a p and presumably returns something that's not P otherwise why would I call it and because it's all nicely pure functional this must return something else so it's at least it's object with at least one more field here commit itself is a by name parameter so the parameter gets wrapped again in a Lambda and so that's another allocation with at least one field and all this happens for every character you pass so for example I to I want to pass a unic code Escape it would be slash followed by U followed by digit followed by digit followed by digit I think followed by one more digit every character you par every two bytes or 16 bits of text you par will need to allocate what 1 2 3 4 five objects I believe the Java object overhead is 12 bytes per object so that's 60 bytes of object header plus 32 bytes sorry four bytes per field so that's two six five six I think there is 7 n so that's another 36 bytes in the fields of the these objects so you're allocating about 100 bytes every time you pass a single character and then you wonder why it's slow very functional so what does fast pares internals look like Fast pares internals do not look functional at all in fact they look really gross and ugly so here you have a whole bunch of pattern matches we have a whole bunch of these mutable things which kind of just to remind you how ugly it is to be M mutable you have these methods which you call with tons and tons of parameters you have a bunch of if statement that's going so far at sticking off the line onto the next line um you have a bunch of ORS and other more pattern matches and more functions call method calls but this has some very nice properties for one there are no lambdas on this page everything fits in a single method it's not a tiny method but it's not a huge method either compared to the methods you find in Java libraries this is not that much bite code it's a moderately sized method secondly this performs zero allocations in the case that tracing is off not one not two zero and I've run with J profiler to make sure of that so for example I would allocate a list here but if you don't tell me to trace things I'll will not allocate anything thing I would allocate a bigger list here but if left hand side is nil and right hand side is nil it will return nil and will not allocate anything so Zero allocations versus 100 btes of allocations per character you parse is probably the bulk of the reason why fast parse is 85x faster than scal par combinators the internals are much much much faster even though the externals look almost exactly the same let's talk a bit about error handling because that's what you do a lot when you're parsing things so here this is the same par I showed you earlier here I'm trying to par some gibberish syntax which looks almost correct except it has this x here and this syntax has no X in it so that should fail and this is saying that well I was trying to par a par Follow by expression followed by closed parent or a number at index zero instead you gave me this why doesn't it tell me it couldn't pass the X and the answer is that fast par has a pretty following F scalar par combinators has a pretty dumb but very predictable mode of operation it tries to thing on the left as far as possible and if it finishes it finishes and returns whatever it was meant to pass if it fails it backtracks out and tries the thing on the right so in this case when I'm already in here it will try to parse the P open p it'll then parse an expression which will then parse the numbers and it parse two plus three overall it'll then attempt to parse a close P which will then fail because it'll find X like what's this x I want to close pen and then what will it do well it doesn't know that number can't start with the open pen 2 plus three like you or I may know that number cannot start with open print 2 plus three but fast pars is not smart enough to know that and therefore fast pars will back out of this guy come to this side try it obviously it'll be it'll fail because it wants the crack it from zero to 9 it finds a open par and then it'll back out of both of these fellas and then it'll tell you well both of them failed I don't know which one you wanted but both of them failed and here it's here's the index which it failed and similarly because this thing failed they'll back out of this thing and end up back at zero so that's not very useful and if only you could tell fast par what like when not to back out like I know we've come to we've crossed a open prayer and it can definitely not be a number you don't know but I know and the way you tell fast paret is with a cut after you cross the cut no backing out you are committed you will keep going and if you fail the error must be somewhere after the cut and you just add this cut after open print and fast parus is able to tell you well I was I was expecting a closed prayer in that index seven you gave me X close close plus 4 and that's actually a perfect error message that's perfectly precise and there was no code in this parcel which is meant to do error handling except for the cut to make sure that fast pass doesn't doesn't back out too much and it's not even magic like you can follow fast poers going in here going here going here failing coming back coming back being unable to back out and then giving an error message is totally predictable which is great earlier I showed you how fast power had a very simple data structure and in reality is slightly more complicated than that in particular in the case for error handling so this is what it actually looks like and the most interesting thing apart from the fact that we have the input we have the index we have some random Trace data which we might not care about is that you have this lazy chased failure object which basically if you ask for it will run the same par using the same parser which I happen to store over here starting at the same index which I happen to start store over here with the same input but with additional instrumentation to tell you later more about what went wrong this cost something it does it's not free it cost I think two or three times as much as original part so the total cost is three or 4X as much as the original failed pars but if you want to debug it or you want to help your user debug it this could be useful so let's see what this two or 3x slowdown gives you if I'm paring the same thing here I know it's going to be a failure so I'm just going to cast it I can ask for the trace of the traced failure maybe not a very good name but whatever so if I say fail. trace. trace it will tell me that I was trying to par an expression at index zero which callus me to try and pass aside index zero which caused me to try and pass an expression index one which caused me to try and pass aside index 3 which is here I believe which caused me to try and par either a Clos P or a character from 0 to 9 at index 7 and you gave me an X so this is very detailed and this actually helps quite a lot it's not it's not just I failed at index 7 or I failed the index 7 um you are wrong it's I failed index 7 because I tried this at index sh because I tried this index one because I tried this to index zero and these are things that could have succeeded but you gave me this and all of this is entirely for free I did not write any of that error handling error reporting code here all that's handled by fast pars you just tell fast pars what the grammar looks like and fast par if you ask for it gives you very nice error reports so Trace gives you a string because that's often what you want just to print it out and see what the hell is going on but it does not hide from you the structured data of what actually was failing so if you want to do more interesting things with it for example you want to inspect which frames have certain Pars in or which which indexes something failed at you don't need to like parse it out from the error message you have this structured list of frames which you can get get from it and you have of course a seven and the pen available without asking for Trac which is what is shown by default in the default error message so apart from that you have trace. Trace pares which is what gives you this thing here in the original Trace error message in that F the the last thing that fast passs Tred to parse was a closed Paran but earlier in the parsing it tried a character in 0 to 9 at the same index and that failed and so if you turn on tracing fast pass will remember that at the cost of some performance and we'll tell you that later and it's actually correct like if you look at this character X this could this x could have been a closed par or this x could have been a number from0 to 9 and that's totally correct and fast par knows it you don't need to tell it that and it's done it's done in a very predictable way and lastly you can ask for the full stack which is the same as the stack which you see on the left but which has all the anonymous intermediate parsers so in fast pars everything's a parser so expression and side are parsers but side Tilda plus Tilda side is a parser P Tilda expression Tilda Clos p is a parer these are all parsers you did not give them names but if you're trying to debug something that's behaving weirdly this is very useful to see to be able to look at why would we do this what are the use cases if your par is wrong you can debug it very easily so it is much easier to debug than 1,500 lines of while loops and go and if statements and mutable variables if your users put something wrong into the input box that you are then parsing you can tell the user you did something wrong and you can't you you don't you don't just tell them syntax error index s you can say syntax error index 7 because I was trying to pass a method definition index 4 because I was trying to pass a class definition index 2 so this is kind of much more detailed error reporting which fast pass puts in effort to collect so if you want to you can put in effort to provide to your users rather than just bailing out with a random string and lastly you can customize the error messages much more for example if I know that every time something passes and fails the user probably made some mistake not guaranteed but like probably confident enough that I would want to tell the user well I don't need to go back into the parser and put random code here to throw an exception in my with the string I want instead I can just after the fact say hey failure does your stack contain this parel like this is literally a parsel object being compared to another parcel object this's not some string or some special syntax does your stat contain the parer food out side yes okay here's a m message so that's the kind of thing that this is meant to be used for so to demonstrate what kind of of error messages just gives you in real code here are some examples from a Scala parser from the Scala parer I wrote versus a scalar parser that the Scala team has worked on for a long time it's much faster than than the fast pass version so what's wrong with this syntax come on no one knows what's wrong with this syntax I need a new line that's wrong what's wrong with this syntax I have two cases in and I need like an arrow or something in between the two cases in order to make it work so Scala C says error expected by case found fast power says I expected either a pipe for Arrow or a uni code arrow and I found a case which is comparable except for the F pack that in the fast par Scala Paras I did not put any effort to try and collect this information so down automatically and it's arguably more correct because you could have put a pipe here and it would have continued passing um here's another case VAR equals 2 what's wrong with this I need a variable name so Scala C says illegal s of simple pattern okay not so I need to put something there something that's simple and is a pattern not sure what fast par says I expected either a binding Follow by infix pattern or just the infix pattern itself or I follow or I expected some kind of variable ID but you gave me equals two so this is a kind of thing that in Fast Parts you get exactly for free a pretty reasonable uh error message and it's not it's not the perfect error message but it's pretty close to what you can what you can want and if you want to because all these are actually objects and not just strings you can drill into them and show more things if you wish to so debugging the thing you do a lot with pares when you working on them is you're debugging them because once you stop debugging them they're done and you go home so first par actually use a log method which says whenever this par gets tried whenever it finishes success or failure print something and let me see so I'm going to log the side parsel and I'm going to log the expression parel cuz I know something's wrong with this but I'm not sure what this doing like why is it misbehaving I'm not sure so this is what you get from adding those two log statements printed to your console the stuff on the right is what you get the stuff on the left isn't what you get but you can derive it by looking at the parser and by looking at input text and Counting characters so if you want to you could pretty print this better but by default You by default you only are showed this stuff but it's pretty detailed you can see it try the expression try the side try the expression try the side this side finish from index one finish index two tries another side index three tries expression index four try index four succeeds the index five tries index six succeeds index seven the expression I tried earlier index four succeeds at index 7 the side I tried earlier index 3 then fails at index 7 and you can see the failure propagating back out of the out of the call stack and this is the kind of thing that makes it really easy to debug Parcels it becomes a mechanical thing rather than intellect ual thing something's wrong add logs okay one of these people one of these people seems to be misbehaving look at his children add logs to them which one's not getting called at the correct time okay one of them behaving ad logs eventually at the point where something's obviously wrong and you fix it and then you move on so while let's talk of debugging the Bas the long and short of it is that you don't spend the you you don't tend to spend time working with parsers that actually work you tend to spend lots of time working with parsers which don't work so once your par is done you are done and so fast parus actually is optimized to give you a great experience when your parel is not working and even for your users when your user is putting things into the input box on your website and wondering why it's not working it sucks to have like syntax error at line seven throwing at you it's much better to say like well I expected a curly brace or a pipe or a equal sign and you gave me an X that's a much better experience for a user to to get let's talk a bit about implementation details so fast pass like scal par combinators is a straightforward recursive descent for those of you who know it is a passing expression grammar so but what that means is that it tries if in the case of let's go back to example in the case of something like this it tries this then it tries this if either them fails it backtracks out unless you put a cut in the case of something like a or it tries a thing on the left if it fails and there's no cut it'll backtrack out and try a thing on the right and if you have multiple ores it will then try from left to right to right to right to right and it's very simple and relatively predictable so there are no fancy algorithms there's no GL there's no there's the worst case performance is always exponential for with this kind of recursive descent parer there's no fancy like if I have ambiguous grammar let's disambiguate it or let's keep all possible parses and disambiguated later there's none of that fast parse Works basically mechanically there's no asynchronous or push parsing there's no XML sax style um event based parsing it doesn't par late it doesn't par anything but a string it's pretty simple to understand and it doesn't do any sort of macro optimizations or or parasa based Transformations like what you write is what will execute in a very predictable way it's as objectoriented as you can ask for so everything is a parer plus T um you can Implement your own parer plus T it has the par function that you can Implement and it's really straightforward even though it's externally immutable the insides of each parity are optimizing very fast that's what is what I showed you earlier we use y Loops inside we use tail recursive functions we use pattern matching we don't use lambdas we use bit sets instead of normal sets because they faster and all this together with mutable failures and successes inside the parasa what help it make it 85 times faster than scalar pars combinators so what have I used Fast pars for so on the example on the website on the documentation page fast pars also compiles to Scala GS you can write pares that run in the browser like you can see that here is an here's an arithmetic parel which is a bit more complete it does precedence it does plus minus time divide and actually evaluates all of them separately so you can see if I do like 1+ 2+ 3 + 4 p p time 17 you get a reasonable answer if I mess it up you can see that oh you gave me a close par I expected a number or paren like a set of pars stuff inside paren being this fell there is a example of a white space insensitive parel which fast par supports out of the box so we can put as many as many spaces in your par as you want in certain places and it will ignore them here you can see we are customizing we are customizing a space to mean anything which is a length space repeated zero or more times indentation based grammars so fast pars lets you very easily par things like this one times 4 7 and it does this in a honestly pretty remarkably simple way so the parel is parameterized based on how much the indentation it can parse and when I want to parse an indented block that's further indented I simply instantiate a new parser and find out how much deeper it has to be and use the mouth deeper to instantiate my new parser and start parsing from there so this is so you don't need any like lexer hack you don't need any pre-processor to inject synthetic tokens into your token stream like if you had a Lexa parser traditional way of doing it you just have this nice recursive parser which can sanate itself and you're done you can pass arbitrary white space indented code or syntax yaml what there's a Json parel um pretty complete one that is what I use for The Benchmark and there's maybe like 30 lines of code total 40 lines of code and it runs pretty fast and it parses the EST which I Define down here um and this shows most of the details what you need to care about when writing pares for example here's how you parse uni code escapes here is how here is how you parse an array which is a square bracket followed by a Json expression more than one separated by commas followed by a space followed by a closed square bracket this gives me this then gives me a sequence of of JS values because JS Json expression passes a j js. value so rep gives me a sequence un converted into a js. array so I you map it using this um that's a more slightly more real world parasor there's a python parasor which I wrote recently which before we talk about python Paras we can look take a moment to look at the error messages the Json parasa gives you so I remove this quote from the start of a object key dictionary key and it says I found four numbers quote colon you give I expected the code and again this is basically for free I did not have any error reporting code in this except for putting Cuts in a few relevant places there's a python parasa which is another example of a wh space sensitive wh space sensitive parel indentation sensitive parel so you can see that we do a similar trick where let's make this bigger where a state the par the thing which contains all the par state parel for statements is itself parameterized based on how indented it is so if I want to par something that's deeper I have a paror which looks ahead to find how many more what the next indent level is and then I simply flat map it and instantiate a new a new set of parsers with that indent level and go from there so it's very straightforward um and then I have the last one to show off here is the Scala parasor which you can see the error messages it shows off so here I found end of input expected a close close comment here I found uh pen sorry curly new line I expected some kind of either backtick ID or a plane ID and this is all in the Scala parcel's case is written about 700 lines of parel combinated code and that is used for uh for my for for markup language I wrote which is what I use to write all this documentation which basically looks like that so in my opinion paring text isn't that hard once you have proper tools for it like parel combinators are great in fact they're very very good except that they are incredibly incredibly slow and then the spray people went and made paril 2 which is very very fast but then has crazy crazy error messages and and I thought well it can't be that hard if the spray people could make it fast and the scalar people could make it convenient and have good error messages why can't we have something that's fast and have good error messages and it turns out you just need to replace a bunch of Mo ads with Y loops and you get something that's both convenient fast flexible and has great errors in a pretty Pleasant API so um I have 10 minutes budgeted for demo so let's do the demo does anyone want to suggest a language that's not Json I want they want me to par any language ask has girl how do you okay let's try parsing has girl how do you par how do you par has girl so here's a hello world project um big big big okay so here I can see you have a library depends on Fast passs um make a bit bigger let's go to my main method So currently it's just printing hello world how do you par hascal I don't actually know how paral I think you have you have something like let is that right so let's try doing that let Val let equals a parel of let and I need to import fast par do all and then let's write some unit test so print line let. par let and let's pin line let. par BL okay so I par lets what do you put after lets in hasal you know Hull yeah sure so you need a variable name okay let's do variable name so a variable name is a par not a variable okay identifier is a parasor which has I guess has some kind alpha numeric so CH let's stick with Alpha numerics for now and do operators later if you have time so I guess A to Z A to Z this A to Z syntax isn't special isn't particular to Fast Pass sorry let's make this bigger this A to Z syntax isn't particular fast poers it's just a normal like character range and then I don't know do you use underscores in hascal maybe I don't know hcll um okay primes let's do that um let's also build some kind of syntax tree so I'm going to have a let is going to have some kind of variable name have more than one variable name no no okay let's do that so Val um let's do a let is equal to a let followed by I'm just going to call this white space so more than one white space for now who cares about new lines Follow by white space followed by identifier okay what's wrong with identifier wrong forward reference so I probably need move this into the object body and then I'll stop complaining okay so I run it you can see that the parasit is failing because it expected a character in A to Z A to Z underscore Prime at index tree instead it found the end of input so I'm going to call it let Fu and now it's going to par nothing because I didn't capture anything so let's capture the identifier with a bang um now it's prints a success F that's that's probably not right oh because I forgot to say is more than one character so you so as you can see I'm I'm only par passsing it's only paring until index five which is 1 2 3 4 5 so that's clearly not right so one thing you can do to make it part to the end is to make it part to the end and then you'll say expect I I expect the end of input I still found like two o's what what are those doing there so now I can say well I very identifying is more than one character so let's do that okay now it's succeeding passing F and let's map this into uh lead so now you can see that identifier is a okay you can't see because intelligent doesn't scroll it up but identifier is a parer of Main dolet and type checks you get a let with a you get let with a Fu inside okay what else does hasal have yeah but equals right and then I need an expression you are you looking up on your on your phone no okay so what goes in okay so here I'm going have a dummy paral expression um okay let's f equals so like let equals expression in some other expression okay so expression followed by in followed by what so it has be recursive right I can put another let in there you could or you can do like aever whatever in C okay so let's just do this let's just do the recursive case first um so let something let WP space identifier I need put a white space here so I'm going I'm going to get tired of doing all this whitespace handling soon so I'm going to use fast pares whitespace API so and so what this does is I'm going to use I'm going to say white space is anything which is uh uh more than one space maybe it needs new lines who knows I'll figure that out later and then I'll import fast pass do no API and I'll import fastp pass
whitespace api. all and that should make it compile oops what's wrong um okay this is not fast pass this is my own I Define it up here okay so failure so I need to have some kind of expression I'm just going to call my expression like f for now we can figure that out later that's not right my expression fast pass let's let f equals F my expression in and presumably I need some kind of expression node so what can expression node be um so let's do that and then okay so presumably I want to be able to have some kind of expression in the in the syntax tree so let's do that and a let must have for now let's just say let some identifier bound which is going to be an expression and um let's call it like returned or something which is an expression so now I'm identified I don't to map my identify to a let because identify shouldn't return a let should just return a string which it now does if you look at this and can see the tiny tiny text um and I'm going to say well the expression must capture something and going to say I don't care what it capture is going to be an expression a and I'm going to map this into case ident um let's call let call this left hand side and right hand side goes to goes to let ident left hand side right hand side okay so now I have this thing paring nothing so let's try and make some more interesting Expressions um I guess an expression can let's say an expression can be dummy expression so let's say this is the only expression you can ever have in hascal other than a let so an expression is going to be a dummy expression or a let um what's wrong so recursive value needs type okay so compiler is complaining so I'm going to annotate this as a pass of an arbitrary expression now it's okay so now I can pass let F in my expression in my expression I can also pass let's make quite space eat up new lines because this is getting very annoying so come on format let F my expression expression let Fu equals my expression in my expression okay failure um let's see if we can figure out why it failed so it's complaining that well after considering expression right um problem well over here I'm saying that an expression is a dummy expression or a let and a is followed by two two expressions so that should be correct so let's try logging it see what happens um okay so it's trying to pass a let at index zero that's over here it then it then fails because it tried to pass identify index three that's over here that seems fine you then try to pass a character in zero to something so let's log the Char the identifiers to see what's happening I think can't really make out so it tries to pass identifier index tree and it fails so let's try to log the Char in itself and to to make our things simple I'm just going to like remove uppercase characters for now because making my logs annoying to read um so it tried to pass a Char in at index three um ah okay so here's my mistake over here I said this means that a Qui space is anything which is a new a space followed by a new line at least once so that's clearly wrong so this needs to be character in uh space or a new line um let's remove the login because it's really Vose and getting hard to read um and get rid of this logging too okay we business so I'm passing two expressions equivalently to this equivalently to this Char in I could also use if I wish to I could also use something like this like a white space or a new line This equivalent it also passes okay so clearly expression can't just be a constant thing expression must be a trait expression let's make it sealed and then let's make let extend expression and let's make another um case object let's make a case class dummy expression extends expression do I have Case Case whoops case class there we go okay so let's make the compiler happy what's wrong here plural what's wrong here this needs to be dummy this still needs to be the arbitrary expression this returns a let which is correct um okay so I have a let of a fo of a dummy expression and dummy expression so that doesn't seem right but let's let's see why this is not right um so the problem here is that in this arbitary expression this lead here you can't see it but this is a parel of lead but when I capture and then map it I'm discarding the lead that it returns and I'm replacing it with a fixed dummy expression so that's clear wrong and that's because this map to dummy expression should be on the dummy expression rule because that's the one that has returns dummy expression the let par just returns a let okay so that gives me a let of full of D expression and a let or fo of dummy expression okay so what else does Haskell have St uh what does a we statement look like it's something end oh okay so aware is equal to okay so so what what what what do I put what do I put after aware so the where goes at the end of an expression it's something like where x equals something right yeah okay so aware is followed by expression followed by equals followed by a another expression and then so there only one where for now we can do we can do multiple it shouldn't be hard but let's let's let's start off with let's start off with where only goes at the end of a let or at end of any expression okay any have expression so um so let's make let's make that its own EST node where so it takes the expression and it has a let's only assume it just has one so have we have a bound which is a ident and name like thing which is is an expression that's like totally a wrong B which is a string and image expression okay so um so at the end of any expression can be aware Clause wrong why is it wrong okay so um I'm telling it after this there's a wear Clause the problem is that now this doesn't just return expression returns expression and where itself is a par of expression of two expressions so what I want to do here is let me see if I can figure this out um I'm going to make the wear Clause optional for now so this that should at least make the existing thing pass and I'm going to map this to say case let's call this left hand side none goes to left hand side and I know this is going to crash I put in aware but whatever um okay so that looks like it's still passing the correct thing we're back into something works mode where my expression equals my expression okay so now that's going to blow up with a match error because I didn't handle this case so let's just do like some I don't know what I don't know what is in here let's let's ask the compiler what's in here here intellig what's in here is a toule of expression so it's I'm quite sure this should let's let's say this is an identifier for now I'm quite sure you kind have arbitrary expression so this is going to be ident expression is going to be aware left hand side uh I call it Bound for some reason and expression okay why is it complaining expected string actually main do expression ah so you can see here it's here it's also complaining that it actually is a parel of couple of string and Main expression but here I and on T as two expressions so that's wrong so if I make this string that should shut up and that should work where so the problem is that I forgot to make where extend expression extends expression okay and it works and let's try another thing let f equals my expression where my expression equals my expression in let Fu equals my expression okay so that's it for the live coding I'm not going to do anymore cool so yeah I I I don't know hasal so whatever so I'll take questions what was the AR um so so where where is my DOT rep here it is um do rep takes a minimum number of iterations so I could say I need to rep zero which is default which means that zero or more I could do one or more and it also takes optional separator which is what we use just now for Json so you have a comma or something in between you can use that any other questions is there are there anyc in yes so every operator is uh is a extension method and the reason for that is that you may want different sets of operators at different times for example I here I want a white space aware set of operators and here I want a non-white space aware set of operators remember white the the white space itself can be arbitrarily complex may have comments and stuff inside so that means that all of these are are provided by an implicit which is provided like Yeah by this implicit here and apart from that there is one more set of implicits which is used to do the turning things into tles so if if you look at if let's um okay what why is it called why is it complaining did I break it no I didn't break it so if I do something like Val x equals a parsa of string capture Val b equals a paror of that Val C equals a parcer of that Val DS a par of that and do Val E equals paror of a f by B should be a small a so you can't well so this is a parsel of string string um you see compiles if I make it follow to C it then says it's a parel of string string string and if I make C return unit it then becomes string string again so there's a bit of implicit magic that it does to make the tles longer so that's slight maybe confusing in some cases but I try to keep it minimal so you don't have unit the it's awesome sorry you don't have tles of string unit string yeah I don't have tles of string unit string and uh and the thing which creates a new tles if if the thing is a unit that's being not added it will not do anything which is great because it doesn't allocate any memory um over there yeah sure honestly I have no clue as far as I can tell nobody involved in that discussion except me has ever used this Library so there a bunch of people who have used the library like in the scholar Community people use it a reasonable amount but a lot of people saying that like oh we should use fast power ER like hey is it actually better and some other gu like I don't know someone should go find out if it's better and third person says that it might be better someone should try and no one's actually actually trying it so at some point when someone actually tries it maybe has sends a chance but for now as far as I can tell it's all talk any other questions going once going twice you look hesitant I have no to remember what it was okay well you you look like you had your hand up can you par streams at all um you cannot par streams there is a pull request open that would make it able to par streams but I haven't accepted it because it makes performance a lot worse um and we haven't quite figured out how to make that work gen generically well while keeping performance good yeah okay yeah the arrow it look like an arrow right yeah this was a par combinators yeah so in paral combinators this Arrow says that par open par Follow by expression but ignore the value of open p and similarly for the arrow in the other direction means the opposite ignore the thing on the right and fast par doesn't need this because by default we just ignore everything and only you have to say do exclamation mark if you actually want something cool anything else going once going twice yeah is there anything to there is not so for example if I do um let's delete my beautiful hascal parel because it's and let's I deleted the main method too that's silly of me so if I say like if I say a equals b and b equals a and I try do a do par like BL let's just do a for now recursive value needs type okay so this is a par of string this is a par of string and then like it just like blows your stack so I I haven't thought of a clever way to make it actually detected I'm sure it's possible but I don't know okay so if you have something that's yes that trampolines would make it uh probably yeah and like if you have something as a thousand levels deep like it's quite possible that your programmer will have a stack Overflow trying to par it in his head what's going on yeah like you probably shouldn't me you can but like yeah so like explicitly didn't want to do any fancy like fancy runtime so there's no like asynchronous nness or trampolines and stuff because that really slows down by a lot and in most cases I'm defining most cases as my cases but in most cases you probably don't need them here anything else going once going twice gone okay thanks w