haskell / haskell/alex

Explore unboxed parser representations

Open
#193 0 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.