Better invertible syntax descriptions

This is written in Literate Haskell.

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

module Better.Invertible.Syntax where

import Control.Applicative
import Control.Monad
import Data.Monoid
-- partial-isomorphisms
import Control.Isomorphism.Partial (IsoFunctor)
import qualified Control.Isomorphism.Partial as Iso
-- invertible-syntax
import Text.Syntax.Classes (ProductFunctor, Syntax)
import qualified Text.Syntax.Classes as Syntax

The paper Invertible Syntax Descriptions¹ describes a typeclass-based interface to define parsers and (pretty) printers as a single polymorphic artefact.

It proposes a common abstraction for parsers and printers that is designed to mimic standard typeclasses, i.e., typeclasses of general usefulness, including (but not restricted to) those in the standard library, base. Three newly introduced typeclasses IsoFunctor, ProductFunctor, Syntax.Alternative respectively correspond to Functor, Applicative, Alternative in some abstract sense.

A naive implementation of that interface as a proof of concept is provided in the paper, with the following concrete types:

newtype Parser a = Parser { runParser :: String -> (a, String) }
newtype Printer a = Printer { runPrinter :: a -> String }

Note that Parser is an Applicative (also a Monad), while Printer a is a Monoid (actually deferring to String being a Monoid). More generally, parser combinator (e.g., parsec) and pretty-printer (e.g., pretty) libraries usually implement instances of such standard typeclasses.

However, the paper does not consider whether standard typeclasses could be used to implement the newer ones, even though the latter were designed based on the former.

As I will show here, instances of the three core typeclasses of the paper can be derived from instances of standard typeclasses: Applicative, Alternative, MonadPlus (Monad + Alternative) for parsers, Monoid for printers.

This improves the usability of the new typeclasses, as less work and boilerplate are necessary to implement instances for different parsers and printers.

The only method requiring an implementation specific to each parser and printer is token from the Syntax typeclass.

A standard implementation

To avoid overlapping instances, we define wrappers for parsers and printers.

Parsers

-- Parsing in a context p :: * -> *
newtype Parsing p a = Parsing { parsing :: p a }
  deriving (Functor, Applicative, Monad, Alternative, MonadPlus)

A parser p :: * -> * should be an instance of MonadPlus to imply an IsoFunctor (i.e., a functor from partial isomorphisms to Hask). The constraint could be relaxed to Functor at the cost of (unsafely) assuming total isomorphisms in place of partial ones.

instance MonadPlus p => IsoFunctor (Parsing p) where
  iso <$> Parsing p = Parsing (p >>= aFromMaybe . Iso.apply iso)

aFromMaybe :: Alternative f => Maybe a -> f a
aFromMaybe = maybe empty pure

ProductFunctor and Syntax.Alternative reflect Applicative and Alternative respectively. Below, the instance of Alternative abuses Haskell’s scoping rules for typeclass methods. empty and (<|>) on the right-hand sides refer to methods from Control.Applicative.Alternative, and not to the variables being defined with the same names on the left-hand sides.

instance Applicative p => ProductFunctor (Parsing p) where
  Parsing a <*> Parsing b = Parsing (liftA2 (,) a b)

instance Alternative p => Syntax.Alternative (Parsing p) where
  empty = Parsing empty
  Parsing a <|> Parsing a' = Parsing (a <|> a')

The Syntax typeclass, more precisely, its token method (we may get pure from Applicative), needs a implementation that is specific to the underlying parser type. We may then lift it to Parsing.

instance (MonadPlus p, Syntax p) => Syntax (Parsing p) where
  pure = Parsing . pure
  token = Parsing Syntax.token

Printers

We rely on a printer being a Monoid to implement ProductFunctor.

-- Printing a monoid q :: *
newtype Printing q a = Printing { printing :: a -> Maybe q }

instance IsoFunctor (Printing q) where
  iso <$> Printing q = Printing (Iso.unapply iso >=> q)

instance Monoid q => ProductFunctor (Printing q) where
  Printing f <*> Printing g = Printing (\(a, b) -> f a <> g b)

instance Syntax.Alternative (Printing q) where
  empty = Printing (\_ -> Nothing)
  Printing a <|> Printing a' = Printing (liftA2 (<|>) a a')

Again, a specialized implementation is required for token, but pure can be derived for a Monoid as well.

purePrinting :: (Eq a, Monoid q) => a -> Printing q a
purePrinting a = Printing (\a' -> mempty <$ guard (a == a'))

Concluding remarks

Another benefit these definitions is that they help characterize the expressive power that is expected of parsers and printers implementing such an interface.

In particular, the MonadPlus constraint to implement IsoFunctor is rather strong. The reduced expressiveness of a parser that is only Applicative is often an acceptable drawback in exchange for increased performance, but such parsers do not rightly fit in that interface.

I also believe that it is a mistake to make Syntax a subclass of Alternative. Although it makes type signatures shorter, it is unreasonable to require it for every parser, as error recovery is far from being a universal capability.