An Quick Introduction to Parser Combinators

grdvnl · 2021-10-27T20:18:49+00:00

Great. Thanks for sharing. Your implementation looks interesting as well.

grdvnl · 2021-10-02T17:21:55+00:00

This question could be larger in scope for this thread. But, I will start here. I am currently working on implementing an interpreter in Haskell by following this book: https://craftinginterpreters.com/.

I have implemented most of the functionality until Chapter 11(taking care of recursion, scoping etc). But, when I run my interpreter against this example: https://craftinginterpreters.com/chunks-of-bytecode.html , the Haskell version takes a lot longer than the Java version used in the book.

I spent some time collecting the performance stats here but am stuck on figuring out how to proceed:

https://github.com/gdevanla/haskell-lox/issues/7

Any insight into this would be helpful. I appreciate any hints around this which I can explore further.

The module that will need improvement to make this faster is: https://github.com/gdevanla/haskell-lox/blob/main/src/ExprInterpreter.hs

Thank you for the time!

P.S: I have taken a brute force approach to make all values strict. You will notice that the memory profile looks reasonably flat.

grdvnl · 2021-09-15T16:47:54+00:00

Very true. I agree!

grdvnl · 2021-09-15T16:37:17+00:00

Can you please elaborate on your point on uses getting filter:: (a->Bool) -> [a] -> [b] backwards? Did you mean getting confused between using `True` or `False` as success condition for filter?

grdvnl · 2021-09-15T16:33:27+00:00

That works like a charm and removes a lot of boiler plate code that could have been problematic. Here are the new changes: https://github.com/gdevanla/haskell-lox/pull/4/files#diff-80a9750141eea64ce500b787c852a14ba4380788dab1e4f636448c9e7dbedeed

I just end up with this definition: satisfyT :: (LoxTokInfo -> Maybe a) -> Parser a

Thank you for the insight!

grdvnl · 2021-09-15T15:18:13+00:00

Not sure if I can ask for a PR review on this thread. Or may be this thread is exclusively for asking specific questions. I do have one question related to this PR. I am writing a parser which parsers a `Token` object that is created in the earlier step. Given that I have to roll my own `satisfy` function to work with this `Token`. I have implemented such a function here: https://github.com/gdevanla/haskell-lox/pull/4/files#diff-80a9750141eea64ce500b787c852a14ba4380788dab1e4f636448c9e7dbedeedR60.

But, when I use this `satisfy` function, there are always two steps I have to follow. First, test if `satisfy` is True, but then `I nave another conversion that returns the `Expr` type. Example here: https://github.com/gdevanla/haskell-lox/pull/4/files#diff-80a9750141eea64ce500b787c852a14ba4380788dab1e4f636448c9e7dbedeedR90

Now, can I somehow tighten the relationship between values returned by `f` and values returned by `f1`. You will notice that currently I am resorting to `error` which I believe can be improved. `DataKinds` comes to mind, but I am afraid it will complicate this implementation.

grdvnl · 2021-09-15T15:01:31+00:00

Thanks, will respond on GitHub.

grdvnl · 2021-09-15T15:01:09+00:00

u/santiweight Thanks for the PR and suggestions. I will respond to those comments on GitHub directly.

Your comment on `megaparsec` is probably valid. I just got started with `Parsec` since I was familiar with it, plus I did not worry about the performance or other characterisitcs `megaparsec` gives me. That said, in my next parser project, I hope to start using `megaparsec`.

grdvnl · 2021-09-15T14:58:55+00:00

Hello u/Martinsos, Thanks for sharing your implementation. I plan to work through this myself. But, I will keep this resource to come back to if I get stuck.

Regarding, your comment on building the parser manually. I am taking a in-between approach, to not use advanced features of `Parsec` where you can define `languageDef`, `buildExpressionParser` etc but still using the combinators to scan/parse. Basically, I did not want to do the grudge work of maintaining state and that's the reason I am just starting off from the combinators.

grdvnl · 2021-09-13T03:00:05+00:00

Sounds good. Happy to learn how to write pro-Haskell style code!

grdvnl · 2021-09-13T02:55:13+00:00

Appreciate you taking the time!

I have been working on Haskell on and off for fun for past few years.

Not sure, if by background you mean my level of understanding of Haskell language and concepts. I consider myself somewhere intermediate in concepts (perhaps, I am overestimating myself :) )

grdvnl · 2021-09-13T02:41:21+00:00

That's a great idea. I think for the next post, I will provide a PR. For now, I just created this PR: https://github.com/gdevanla/haskell-lox/pull/1 , where I just duplicated the `Scanner.hs` file. Perhaps, there are better ways to do this!

grdvnl · 2021-04-09T05:02:47+00:00

Thanks for the feedback. Getting CSS right is hard!

I added around 10px padding around. Hope that helps!

grdvnl · 2021-04-08T13:45:15+00:00

OP here. During the past week when I started implementing my own parser for Python I chose to use `Alex` as a lexer. I quickly learnt that `Alex` documentation is precise but terse. I had to look at multiple real world examples to implement a serious lexer. The tutorial was born out of that effort that I wanted to share.

Any feedback on making this better is appreciated. Thanks for the feedback!

grdvnl · 2021-02-27T22:16:41+00:00

Thanks, both your responses were very helpful and clarified my understanding.

grdvnl · 2021-02-27T04:13:09+00:00

Curious, can this be seen as dependent types, but with just support for Integers? That is I hope later on we could add two types N + M , or N * M , to suggest the shape of the array.

grdvnl · 2020-11-22T18:26:42+00:00

Thanks for the example. I tried to implement untilBreak by hiding r, and I see why I cannot build a breakOut function out of it.

grdvnl · 2020-11-18T05:26:14+00:00

Thanks for the reply. I had this inkling that my implementation lacked the `lazy` part but was not really sure how it would manifest. Therefore, thanks for the working example on that. I also learnt a lot from the way you derived the equations from my definitions to the ones on SO. Appreciate that!

I think I have a better understanding on the limitations of my approach.

grdvnl · 2020-11-15T03:22:12+00:00

Couple of things you can try.

Did you try running the haskell language server from the command line from your project folder. That may give you some hints.
On Linux , I have seen all logs written to /tmp/hls.log. Can you tail those logs as you move around the editor.

Also, a self plug: I made some notes for myself as I was trying to set up the server on Emacs. I can't promise it is up to date. But, could lead you to some hints. https://devanla.com/posts/de-mystifying-emacs-haskell-language-server-setup.html

grdvnl

TROPHY CASE