Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Parsing and pretty printing with prisms

Parsing and pretty printing with prisms

YOW! Lambda Jam 2016 talk on the fresnel library for unified parsing and printing using prisms.

Fraser Tweedale

April 29, 2016
Tweet

More Decks by Fraser Tweedale

Other Decks in Programming

Transcript

  1. Prism primer ghci> :t _Right _Right :: Prism (Either c

    a) (Either c b) a b ghci> preview _Right (Right 42) Just 42 ghci> preview _Right (Left "nope") Nothing ghci> review _Right 42 Right 42 ghci> preview (_Left . _Right) (Left (Right 42)) Just 42
  2. ASN.1 and DER BasicConstraints ::= SEQUENCE { cA BOOLEAN DEFAULT

    FALSE, pathLenConstraint INTEGER (0..MAX) OPTIONAL }
  3. Data.X509.Ext instance Extension ExtBasicConstraints where extDecode [Start Sequence,End Sequence] =

    ... extDecode [Start Sequence,Boolean b,End Sequence] = ... extDecode [Start Sequence,Boolean b,IntVal v,End Sequence] = ... extDecode _ = Left "unknown sequence"
  4. Parser newtype Parser a = Parser { runParser :: String

    -> Maybe (a, String) } char :: Parser Char char = Parser $ \s -> case s of "" -> Nothing (c : s ) -> Just (c, s )
  5. Control.Lens.Cons uncons :: (Cons s s a a) => s

    -> Maybe (a, s) -- look familiar?
  6. Control.Lens.Cons class Cons s t a b where _Cons ::

    Prism s t (a, s) (b, t) instance Cons ByteString ByteString Word8 Word8 instance Cons Text Text Char Char instance Cons [a] [b] a b instance Cons (Vector a) (Vector b) a b -- and many more!
  7. Redefining the parser type Parser s a = Prism s

    s (a, s) (a, s) char :: (Cons s s a a) => Parser s a char = _Cons runParser :: Parser s a -> s -> Maybe (a, s) runParser = preview
  8. But if the parser is a Prism. . . type

    Parser s a = Prism s s (a, s) (a, s) char :: (Cons s s a a) => Parser s a char = _Cons runParser :: Parser s a -> s -> Maybe (a, s) runParser = preview runPrinter :: Parser s a -> (a, s) -> s runPrinter = review
  9. Parser ∧ printer → grammar type Grammar s a =

    Prism s s (a, s) (a, s) element :: (Cons s s a a) => Grammar s a element = _Cons runParser :: Grammar s a -> s -> Maybe (a, s) runParser = preview runPrinter :: Grammar s a -> (a, s) -> s runPrinter = review
  10. Convenience functions parse :: Grammar s a -> s ->

    Maybe a parse g s = fmap fst (preview g s) print :: (Monoid s) => Grammar s a -> a -> s print g a = review g (a, mempty)
  11. Grammar - map (<<$>>) :: Prism a a b b

    -> Grammar s a -> Grammar s b p <<$>> g = g . swapped . aside p . swapped swapped :: Iso (a, b) (c, d) (b, a) (d, c) aside :: Prism s t a b -> Prism (e, s) (e, t) (e, a) (e, b)
  12. Grammar - product (<<*>>) :: Grammar s a -> Grammar

    s b -> Grammar s (a, b) g1 <<*>> g2 = g1 . aside g2 . productIso where productIso = iso (\(a, (b, s)) -> ((a, b), s)) (\((a, b), s) -> (a, (b, s)))
  13. Grammar - sum (<<+>>) :: Grammar s a -> Grammar

    s b -> Grammar s (Either a b) g1 <<+>> g2 = prism (\(x, s) -> either (review g1 . (,s)) (review g2 . (,s)) x) (\s -> first Left <$> preview g1 s <|> first Right <$> preview g2 s)
  14. Grammar - list many :: Grammar s a -> Grammar

    s [a] many g = isoList <<$>> (g <<*>> many g) <<+>> success () isoList :: Iso (Either (a, [a]) ()) [a] isoList = ... -- like pure :: Applicative f => a -> f a success :: a -> Grammar s a success a = prism snd (Just . (a,))
  15. Grammar - basic grammars satisfy :: (Cons s s a

    a) => (a -> Bool) -> Grammar s a satisfy f = prism id (\a -> guard (f a) >> pure a) <<$>> element symbol :: (Cons s s a a, Eq a) => a -> Grammar s a symbol a = satisfy (== a) eof :: (Cons s s a a) => Grammar s () eof = prism snd (\s -> maybe (Just ((), s)) (const Nothing) (uncons s))
  16. Grammar - delimiters literal :: (Cons s s a a,

    Eq a) => a -> Grammar s () match :: Grammar s a -> a -> Grammar s () between :: Grammar s () -> Grammar s () -> Grammar s a -> Grammar s a
  17. Grammar - combinators (<<*) :: Grammar s a -> Grammar

    s () -> Grammar s a (*>>) :: Grammar s () -> Grammar s a -> Grammar s a many1 :: Grammar s a -> Grammar s (NonEmpty a) replicate :: Natural -> Grammar s a -> Grammar s [a]
  18. Grammar - bind bind :: Grammar s a -> (a

    -> Grammar s b) -> (b -> a) -> Grammar s b bind p f g = prism (\(b, s) -> review p (g b, review (f (g b)) (b, s))) (preview p >=> \(a, s ) -> preview (f a) s )
  19. Grammar - bind ghci> let g = bind integral (\n

    -> replicate n alpha)) length ghci> parse (many g) "1a2ab3abc4bad!" Just ["a","ab","abc"] ghci> print (many g) ["hello", "world"] :: String "5hello5world"
  20. Deriving Isos for custom types {-# LANGUAGE TemplateHaskell #-} import

    Data.Fresnel.TH (makeIso) data Foo = A Int Char | B Bool makeIso Foo -- results in splice -- _Foo :: Iso (Either (Int, Char) Bool) Foo _Foo = ...
  21. Putting it all together data PhoneNumber = PhoneNumber { areaCode

    :: String , localNumber :: String } deriving (Show) makeIso PhoneNumber phoneNumber :: Cons s s Char Char => Grammar s PhoneNumber phoneNumber = _PhoneNumber <<$>> between (literal ( ) (literal ) ) (replicate 2 digit) <<* match (many space) " " <<*>> replicate 8 (match (many space) "" *>> digit)
  22. Putting it all together ghci> parse phoneNumber ("(07)3456 78 9

    0" :: String) Just (PhoneNumber "07" "34567890") ghci> print phoneNumber (PhoneNumber "07" "34567890") :: String "(07) 34567890"
  23. Primitive types boolean :: (Cons s s ASN1 ASN1) =>

    Grammar s Bool integer :: (Cons s s ASN1 ASN1) => Grammar s Integer octetString :: (Cons s s ASN1 ASN1) => Grammar s B.ByteString oid :: (Cons s s ASN1 ASN1) => Grammar s OID
  24. OPTIONAL, DEFAULT and SEQUENCE opt :: Grammar s a ->

    Grammar s (Maybe a) def :: (Eq a) => a -> Grammar s a -> Grammar s a sequence :: (Cons s s ASN1 ASN1) => Grammar s a -> Grammar s a
  25. ASN.1 grammar - example data BasicConstraints = NotCA | CA

    (Maybe Natural) _BasicConstraints :: Iso (Bool, Maybe Natural) BasicConstraints _BasicConstraints = ... basicConstraints :: (Cons s s ASN1 ASN1) => Grammar s BasicConstraints basicConstraints = _BasicConstraints <<$>> sequence ( def False boolean <<*>> opt (natural <<$>> integer) )
  26. How did I get here? 1. Evaluate existing solutions 2.

    Write Cons-based parser (to parse [ASN1])
  27. How did I get here? 1. Evaluate existing solutions 2.

    Write Cons-based parser (to parse [ASN1]) 3. Hmm. . . _Cons is a prism. . .
  28. How did I get here? 1. Evaluate existing solutions 2.

    Write Cons-based parser (to parse [ASN1]) 3. Hmm. . . _Cons is a prism. . . 4. Type tetris
  29. How did I get here? 1. Evaluate existing solutions 2.

    Write Cons-based parser (to parse [ASN1]) 3. Hmm. . . _Cons is a prism. . . 4. Type tetris 5. fresnel is born
  30. Advantages One module; many stream and element types Don’t repeat

    yourself Reuse existing optics ASN.1 grammar corresponds to spec
  31. Resources and related topics Invertible Syntax Descriptions Paper: www.informatik.uni-marburg.de/~rendel/unparse/ Libraries:

    boomerang, roundtrip, invertible-syntax Christian Marie’s YLJ2015 talk Experiment in combining Applicative and Divisible https://github.com/charleso/portmanteau lens
  32. Fin © 2016 Fraser Tweedale Except where otherwise noted this

    work is licensed under http://creativecommons.org/licenses/by/4.0/ Slides https://github.com/ frasertweedale/talks/ Email [email protected] Twitter @hackuador