Getty Ritter 9958ca9f66 Fixed type error in example program | 8 years ago | |
---|---|---|
Data | 8 years ago | |
example | 8 years ago | |
.gitignore | 9 years ago | |
LICENSE | 9 years ago | |
README.md | 8 years ago | |
Setup.hs | 9 years ago | |
s-cargot.cabal | 8 years ago |
S-Cargot is a library for parsing and emitting S-expressions, designed to be flexible, customizable, and extensible. Different uses of S-expressions often understand subtly different variations on what an S-expression is. The goal of S-Cargot is to create several reusable components that can be repurposed to nearly any S-expression variant.
S-Cargot does not aim to be the fastest or most efficient s-expression library. If you need speed, then it would probably be best to roll your own [AttoParsec]() parser. Wherever there's a choice, S-Cargot errs on the side of maximum flexibility, which means that it should be easy to plug together components to understand various existing flavors of s-expressions or to extend it in various ways to accomodate new flavors.
S-expressions were originally the data representation format in
Lisp implementations, but have found broad uses outside of that as
a data representation and storage format. S-expressions are often
understood as a representation for binary trees with optional values
in the leaf nodes: an empty leaf is represented with empty
parens ()
, a non-empty leaf is represented as the scalar value
it contains (often tokens like x
or other programming language
literals), and an internal node is represented as (x . y)
where
x
and y
are standing in for other s-expressions. In Lisp
parlance, an internal node is called a cons cell, and the first
and second elements inside it are called the car and the cdr,
for historical reasons. Non-empty lef nodes are referred to
in the s-cargot library as atoms.
Often, s-expressions are used to represent lists, in which case
the list is treated as a right-branching tree with an empty leaf as
the far right child of the tree. S-expression languages have a
shorthand way of representing these lists: instead of writing successsively
nested pairs, as in (1 . (2 . (3 . ()))
, they allow the sugar
(1 2 3)
. This is the most common way of writing s-expressions,
even in languages that allow raw cons cells (or "dotted pairs") to
be written.
The s-cargot library refers to expressions where every right-branching sequence ends in an empty leaf as well-formed s-expressions. Note that any s-expression which can be written without using a dotted pair is necessarily well-formed.
Unfortunately, while in common use, s-expressions do not have a single formal standard. They are often defined in an ad-hoc way, which means that s-expressions used in different contexts will, despite sharing a common parentheses-delimited structure, differ in various respects. Additionally, because s-expressions are used as the concrete syntax for languages of the Lisp family, they often have conveniences (such as comment syntaxes) and other bits of syntactic sugar (such as reader macros, which are described more fully later) that make parsing them much more complicated. Even ignoring those features, the atoms recognized by a given s-expression variation can differ widely.
The s-cargot library was designed to accomodate several different kinds of s-expression formats, so that an s-expression format can be easily expressed as a combination of existing features. It includes a few basic variations on s-expression languages as well as the tools for parsing and emitting more elaborate s-expressions variations without having to reimplement the basic plumbing yourself.
The central way of interacting with the S-Cargot library is by creating
and modifying datatypes which represent specifications for parsing and
printing s-expressions. Each of those types has two type parameters, which
are often called atom
and carrier
:
+------ the type that represents an atom or value
|
| +- the Haskell representation of the SExpr itself
| |
parser :: SExprParser atom carrier
printer :: SExprPrinter atom carrier
Various functions will be provided that modify the carrier type (i.e. the output type of parsing or input type of serialization) or the language recognized by the parsing.
There are three built-in representations of S-expression lists: two of them are isomorphic, as one or the other might be better for processing S-expression data in a particular circumstance, and the third represents only the well-formed subset of possible S-expressions.
-- cons-based representation
data SExpr atom
= SCons (SExpr atom) (SExpr atom)
| SNil
| SAtom atom
-- list-based representation
data RichSExpr atom
= RSList [RichSExpr atom]
| RSDotList [RichSExpr atom] atom
| RSAtom atom
-- well-formed representation
data WellFormedSExpr atom
= WFSList [WellFormedSExpr atom]
| WFSAtom atom
The WellFormedSExpr
representation should be structurally
identical to the RichSExpr
representation in all cases where
no improper lists appear in the source. Both of those are
often more convenient than writing multiple nested SCons
constructors in Haskell.
Functions for converting back and forth between
representations are provided, but you can also modify a
SExprSpec
to parse to or serialize from a particular
representation using the asRich
and asWellFormed
functions.
>>> decode basicParser "(a b)"
Right [SCons (SAtom "a") (SCons (SAtom "b") SNil)]
>>> decode (asRich basicParser) "(a b)"
Right [RSList [RSAtom "a",RSAtom "b"]]
>>> decode (asWellFormed basicParser) "(a b)"
Right [WFSList [WFSAtom "a",WFSAtom "b"]]
>>> decode basicParser "(a . b)"
Right [SCons (SAtom "a") (SAtom "b")]
>>> decode (asRich basicParser) "(a . b)"
Right [RSDotted [RSAtom "a"] "b"]
>>> decode (asWellFormed basicParser) "(a . b)"
Left "Found atom in cdr position"
These names and patterns can be quite long, so S-Cargot also exports several pattern synonyms that can be used both as expressions and in pattern-matches to make working with these types less verbose. These are each contained in their own module, as their names conflict with each other, so it's recommended to only import the type that you plan on working with:
>>> import Data.SCargot.Repr.Basic
>>> A 2 ::: A 3 ::: A 4 ::: Nil
SCons (SAtom 2) (SCons (SAtom 3) (SComs (SAtom 4) SNil))
>>> import Data.SCargot.Repr.WellFormed
>>> L [A 1,A 2,A 3]
WFSList [WFSAtom 1,WFSAtom 2,WFSAtom 3]
>>> let sexprSum (L xs) = sum (map sexprSum xs); sexprSum (A n) = n
>>> :t sexprSum
sexprSum :: Num a => WellFormedSExpr a -> a
>>> sexprSum (L [A 2, L [A 3, A 4]])
9
If you are using GHC 7.10, several of these will be powerful bidirectional pattern synonyms that allow both constructing and pattern-matching on s-expressions in non-trivial ways:
>>> import Data.SCargot.Repr.Basic
>>> L [ A 2, A 3, A 4 ]
SCons (SAtom 2) (SCons (SAtom 3) (SComs (SAtom 4) SNil))
Any type can serve as an underlying atom type provided that it has
a Parsec parser or a serializer (i.e. a way of turning it
into Text
.) For these examples, I'm going to use a very simple
serializer that is roughly like the one found in Data.SCargot.Basic
,
which parses symbolic tokens of letters, numbers, and some
punctuation characters. This means that the 'serializer' here
is just the identity function:
parser :: SExprParser Text (SExpr Text)
parser = mkParser (pack <$> many1 (alphaNum <|> oneOf "+-*/!?"))
printer :: SExprPrinter Text (SExpr Text)
printer = flatPrint id
A more elaborate atom type would distinguish between different varieties of token, so a small example (that understands just identifiers and numbers) is
import Data.Text (Text, pack)
data Atom = Ident Text | Num Int deriving (Eq, Show)
pAtom :: Parser Atom
pAtom = ((Num . read) <$> many1 digit)
<|> (Ident . pack) <$> takeWhile1 isAlpha)
sAtom :: Atom -> Text
sAtom (Ident t) = t
sAtom (Num n) = pack (show n)
myParser :: SExprParser Atom (SExpr Atom)
myParser = mkParser pAtom
myPrinter :: SExprPrinter Atom (SExpr Atom)
myPrinter = flatPrint sAtom
We can then use this newly created atom type within an S-expression for both parsing and serialization:
>>> decode myParser "(foo 1)"
Right [SCons (SAtom (Ident "foo")) (SCons (SAtom (Num 1)) SNil)]
>>> encode mySpec [L [A (Num 0), A (Ident "bar")]]
"(0 bar)"
Several common atom types appear in the module
Data.SCargot.Common
,
including various kinds of identifiers and number literals. The
long-term plan for S-Cargot is to include more and more kinds of
built-in atoms, in order to make putting together an S-Expression
parser even easier. If you have a common syntax for an atom type
that you think should be represented there, please
suggest it in an issue!
As pointed out above, there are three different carrier types that are used to represent S-expressions by the library, but you can use any type as a carrier type for a spec. This is particularly useful when you want to parse into your own custom tree-like type. For example, if we wanted to parse a small S-expression-based arithmetic language, we could define a data type and transformations from and to an S-expression type:
import Data.Char (isDigit)
import Data.SCargot.General
import Data.Text (Text)
import qualified Data.Text as T
data Expr = Add Expr Expr | Num Int deriving (Eq, Show)
toExpr :: RichSExpr Text -> Either String Expr
toExpr (L [A "+", l, r]) = Add <$> toExpr l <*> toExpr r
toExpr (A c)
| T.all isDigit c = pure (Num (read (T.unpack c)))
| otherwise = Left "Non-numeric token as argument"
toExpr _ = Left "Unrecognized s-expr"
fromExpr :: Expr -> RichSExpr Text
fromExpr (Add x y) = L [A "+", fromExpr x, fromExpr y]
fromExpr (Num n) = A (T.pack (show n))
then we could use the convertSpec
function to add this directly to
the SExprSpec
:
>>> let parser' = setCarrier toExpr (asRich myParser)
>>> :t parser'
SExprParser Atom Expr
>>> decode parser' "(+ 1 2)"
Right [Add (Num 1) (Num 2)]
>>> decode parser' "(0 1 2)"
Left "Unrecognized s-expr"
By default, an S-expression parser does not include a comment syntax, but
the provided withLispComments
function will cause it to understand
traditional Lisp line-oriented comments that begin with a semicolon:
>>> decode basicParser "(this ; has a comment\n inside)\n"
Left "(line 1, column 7):\nunexpected \";\"\nexpecting space or atom"
>>> decode (withLispComments basicParser) "(this ; has a comment\n inside)\n"
Right [SCons (SAtom "this") (SCons (SAtom "inside") SNil)]
Additionally, you can provide your own comment syntax in the form of an Parsec parser. Any Parsec parser can be used, so long as it meets the following criteria:
try
For example, the following adds C++-style comments to an S-expression format:
>>> let cppComment = string "//" >> manyTill newline >> return ()
>>> decode (setComment cppComment basicParser) "(a //comment\n b)\n"
Right [SCons (SAtom "a") (SCons (SAtom "b") SNil)]
The
Data.SCargot.Comments
module defines some helper functions for creating comment syntaxes, so the
cppComment
parser above could be defined as simply
>>> let cppComment = lineComment "//"
>>> decode (setComment cppComment basicParser) "(a //comment\n b)\n"
Right [SCons (SAtom "a") (SCons (SAtom "b") SNil)]
Additionally, a handful of common comment syntaxes are defined in
Data.SCargot.Comments
,
including C-style, Haskell-style, and generic scripting-language-style
comments, so in practice, we could write the above example as
>>> decode (withCLikeLineComments basicParser) "(a //comment\n b)\n"
Right [SCons (SAtom "a") (SCons (SAtom "b") SNil)]
A reader macro is a Lisp macro---a function that operates on syntactic
structures---which is invoked during the scanning phase of a Lisp parser. This
allows the lexical syntax of a Lisp to be modified. The most commonly
seen reader macro is the quote, which allows the syntax 'expr
to stand as sugar
for the s-expression (quote expr)
. The S-Cargot library accomodates
this by keeping a map from characters to Haskell functions that can be used as
readers. There is a special case for the aforementioned quote, but that
could easily be written by hand as
>>> let quote expr = SCons (SAtom "quote") (SCons expr SNil)
>>> let addQuoteReader = addReader '\'' (\ parse -> fmap quoteExpr parse)
>>> decode (addQuoteReader basicParser) "'foo"
Right [SCons (SAtom "quote") (SCons (SAtom "foo") SNil)]
A reader macro is passed the parser that invoked it, so that it can
perform recursive calls into the parser, and can return any SExpr
it would like. It
may also take as much or as little of the remaining parse stream as it
would like; for example, the following reader macro does not bother
parsing anything else and merely returns a new token:
>>> let qmReader = addReader '?' (\ _ -> pure (SAtom "huh"))
>>> decode (qmReader basicParser) "(?1 2)"
Right [SCons (SAtom "huh") (SCons (SAtom "1") (SCons (SAtom "2") SNil))]
Reader macros in S-Cargot can be used to define bits of Lisp
syntax that are not typically considered the purview of S-expression
parsers. For example, to allow square brackets as a subsitute for
proper lists, we could define a reader macro that is indicated by the
[
character and repeatedly calls the parser until a ]
character
is reached:
>>> let vec p = (char ']' *> pure SNil) <|> (SCons <$> p <*> vec p)
>>> let withVecReader = addReader '[' vec
>>> decode (asRich (withVecReader basicParser)) "(1 [2 3])"
Right [RSList [RSAtom "1",RSList [RSAtom "2",RSAtom "3"]]]
The s-cargot library also includes a simple but often adequate
pretty-printing system for s-expressions. A printer that prints a
single-line s-expression is created with flatPrint
:
>>> let printer = flatPrint id
>>> :t printer
SExprPrinter Text (SCargot Text)
>>> Text.putStrLn $ encode printer [L [A "foo", A "bar"]]
(foo bar)
A printer that tries to pretty-print an s-expression to fit
attractively within an 80-character limit can be created with
basicPrint
:
>>> let printer = basicPrint id
>>> let sentence = "this stupendously preposterously supercalifragilisticexpialidociously long s-expression"
>>> let longSexpr = L [A word | word <- Text.words sentence ]
>>> Text.putStrLn $ encodeOne printer longSexpr
(this
stupendously
preposterously
supercalifragilisticexpialidociously
long
s-expression)
A printer created with basicPrint
will "swing" things that are too
long onto the subsequent line, indenting it a fixed number of spaces.
We can modify the number of spaces with setIndentAmount
:
>>> let printer = setIndentAmount 4 (basicPrint id)
>>> Text.putStrLn $ encodeOne printer longSexpr
(this
stupendously
preposterously
supercalifragilisticexpialidociously
long
s-expression)
We can also modify what counts as the 'maximum width', which for a
basicPrint
printer is 80 by default:
>>> let printer = setMaxWidth 8 (basicPrint id)
>>> Text.putStrLn $ encodeOne printer (L [A "one", A "two", A "three"])
(one
two
three)
Or remove the maximum, which will put the whole s-expression onto one line, regardless of its length:
>>> let printer = removeMaxWidth (basicPrint id)
>>> Text.putStrLn $ encodeOne printer longSexpr
(this stupendously preposterously supercalifragilisticexpialidociously long s-expression)
We can also specify an indentation strategy, which decides how to
indent subsequent expressions based on the head of a given
expression. The default is to always "swing" subsequent expressions
to the next line, but we could also specify the Align
constructor, which
will print the first two expressions on the same line and then any subsequent
expressions horizontally aligned with the second one, like so:
>>> let printer = setIndentStrategy (\ _ -> Align) (setMaxWidth 8 (basicPrint id))
>>> Text.putStrLn $ encodeOne printer (L [A "one", A "two", A "three", A "four"])
(one two
three
four)
Or we could choose to keep some number of expressions on the same line and afterwards swing the subsequent ones:
>>> let printer = setIndentStrategy (\ _ -> SwingAfter 1) (setMaxWidth 8 (basicPrint id))
>>> Text.putStrLn $ encodeOne printer (L [A "one", A "two", A "three", A "four"])
(one two
three
four)
For lots of situations, we might want to choose a different indentation strategy based
on the first expression within a proper list: for example, Common Lisp source code is often
formatted so that, following a defun
token, we have the function name and arguments
on the same line, and then the body of the function indented some amount subsequently.
We can express an approximation of that strategy like this:
>>> let strategy (A ident) | "def" `Text.isPrefixOf` ident = SwingAfter 2; strategy _ = Align
>>> let printer = setIndentStrategy strategy (setMaxWidth 20 (basicPrint id))
>>> let fact = L [A "defun", A "fact", L [A "x"], L [A "product", L [A "range", A "1", A "x"]]]
>>> Text.putStrLn $ encodeOne printer fact
(defun fact (x)
(product (range 1 x)))
>>> let app = L [A "apply", L [A "lambda", L [A "y"], L [A "fact", A "y"]], L [A "+", A "2", A "3"]]
(apply (lambda (y) (fact y)
(+ 2 3))
Here is a final example which implements a limited arithmetic language with Haskell-style line comments and a special reader macro to understand hex literals:
{-# LANGUAGE OverloadedStrings #-}
module SCargotExample where
import Control.Applicative ((<|>))
import Data.Char (isDigit)
import Data.SCargot
import Data.SCargot.Repr.Basic
import Data.Text (Text, pack)
import Numeric (readHex)
import Text.Parsec (anyChar, char, digit, many1, manyTill, newline, satisfy, string)
import Text.Parsec.Text (Parser)
-- Our operators are going to represent addition, subtraction, or
-- multiplication
data Op = Add | Sub | Mul deriving (Eq, Show)
-- The atoms of our language are either one of the aforementioned
-- operators, or positive integers
data Atom = AOp Op | ANum Int deriving (Eq, Show)
-- Once parsed, our language will consist of the applications of
-- binary operators with literal integers at the leaves
data Expr = EOp Op Expr Expr | ENum Int deriving (Eq, Show)
-- Conversions to and from our Expr type
toExpr :: SExpr Atom -> Either String Expr
toExpr (A (AOp op) ::: l ::: r ::: Nil) = EOp op <$> toExpr l <*> toExpr r
toExpr (A (ANum n)) = pure (ENum n)
toExpr sexpr = Left ("Unable to parse expression: " ++ show sexpr)
fromExpr :: Expr -> SExpr Atom
fromExpr (EOp op l r) = A (AOp op) ::: fromExpr l ::: fromExpr r ::: Nil
fromExpr (ENum n) = A (ANum n) ::: Nil
-- Parser and serializer for our Atom type
pAtom :: Parser Atom
pAtom = ((ANum . read) <$> many1 digit)
<|> (char '+' *> pure (AOp Add))
<|> (char '-' *> pure (AOp Sub))
<|> (char '*' *> pure (AOp Mul))
sAtom :: Atom -> Text
sAtom (AOp Add) = "+"
sAtom (AOp Sub) = "-"
sAtom (AOp Mul) = "*"
sAtom (ANum n) = pack (show n)
-- Our comment syntax is going to be Haskell-like:
hsComment :: Parser ()
hsComment = string "--" >> manyTill anyChar newline >> return ()
-- Our custom reader macro: grab the parse stream and read a
-- hexadecimal number from it:
hexReader :: Reader Atom
hexReader _ = (A . ANum . rd) <$> many1 (satisfy isHexDigit)
where isHexDigit c = isDigit c || c `elem` hexChars
rd = fst . head . readHex
hexChars :: String
hexChars = "AaBbCcDdEeFf"
-- Our final s-expression parser and printer:
myLangParser :: SExprParser Atom Expr
myLangParser
= setComment hsComment -- set comment syntax to be Haskell-style
$ addReader '#' hexReader -- add hex reader
$ setCarrier toExpr -- convert final repr to Expr
$ mkParser pAtom -- create spec with Atom type
mkLangPrinter :: SExprPrinter Atom Expr
mkLangPrinter
= setFromCarrier fromExpr
$ setIndentStrategy (const Align)
$ basicPrint sAtom
>>> decode myLangParser "(+ (* 2 20) 10) (* 10 10)"
[EOp Add (EOp Mul (ENum 2) (ENum 20)) (ENum 10),EOp Mul (ENum 10) (ENum 10)]
Keep in mind that you often won't need to write all this by hand, as you can often use a variety of built-in atom types, reader macros, comment types, and representations, but it's a useful illustration of all the options that are available to you should you need them!