Explore unboxed parser representations
- Dominant language
- Haskell
- Stars
- 323
- Forks
- 87
- PR merge metrics
- No merged PRs in 30d
Description
There is a nice library by Ed Kmett called parsnip: https://hackage.haskell.org/package/parsnip-0/
This represents a parser as follows:
```haskell
newtype Option a = Option# (# a | (##) #)
type Result s a = (# Option a, Addr#, State# s #)
newtype Parser s a = Parser
{ runParser :: Addr# -> State# s -> Result s a
}
```
Here is how the Alex parser for monad-bytestring looks:
```haskell
newtype Alex a = Alex { unAlex :: AlexState -> Either String (AlexState, a) }
-- monad-bytestring wrapper
data AlexState = AlexState {
alex_pos :: !AlexPosn, -- position at current input location
alex_bpos:: !Int64, -- bytes consumed so far
alex_inp :: ByteString.ByteString, -- the current input
alex_chr :: !Char, -- the character before the input
alex_scd :: !Int -- the current startcode
, alex_ust :: AlexUserState -- AlexUserState will be defined in the user program
}
```
It seems this sort of unboxing experiment is not so far out of reach for a wrapper that could produce potentially very fast code. On top of that, as it is user-generated code it seems reasonable that it might be quite horrid to actually read. How feasible would it be to add a wrapper inspired by parsnip?
Contributor guide
Research direction
Start by comparing parsnip's unboxed Parser and Result representations with the Alex parser and monad-bytestring wrapper shown in the issue. Determine whether Alex's generated parser entry point and state representation can support this approach without an established design. Done would be a documented feasibility result and a scoped implementation plan for the wrapper.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- haskell
- Domain
- compilers
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100