"Doug Ransom" <[EMAIL PROTECTED]> wrote,
> Has anyone had experience with Parsec vs. -- the Parser combinators
> supplied with Manuel M. T. Chakravarty's Compiler Toolkit: Self-optimizing
> LL(1) parser combinators?
>
> As someone trying to learn FP, I have been playing with the Compiler Toolkit
> lexical analyzer combinators, but I have had some roadblocks:
> - there are no examples and the tests do not cover the typical use cases.
The main example at the moment is the C lexer and parser
that is part of C->Haskell:
http://www.cse.unsw.edu.au/~chak/haskell/c2hs/
(You will find all source and instructions for CVS access at
that page.)
Moreover, I have recently implemented another (smaller, and
thus, hopefully easier to understand) lexer and parser with
the combinators. I attach the source code of the
lexer/parser and the AST at this message. The grammer of
the accepted language is part of the initial comment of the
parser module.
> - regular expression support is limited -- there is no "." operator to match
> any char, nor any exclusion operator i.e. [^abc] for anything in abc.
> I anticipate success, but I think the Compiler Toolkit needs some
> improvements.
There is no need for "." or [^abc] as Haskell list operators
can be used to "simulate" them. The following is from the C
lexer and matches all visible characters and all characters
except newline, respectively:
visible = alt [' '..'\127']
anyButNL = alt (['\0'..'\255'] \\ ['\n'])
I agree that the documentation of the toolkit should be
improved :-/
Anyway, generally, let me know if you have any specific
improvements.
Cheers,
Manuel
PS: Sorry, for the late reply, but I just returned from ICFP
- which was great btw.
-- Flattening Prototype: parser for the lambda calculus with parallel arrays
--
-- Authors: Nepal Team
-- Created: 13 September 2000
--
-- Version $Revision: 1.3 $ from $Date: 2000/09/15 12:16:24 $
--
-- Copyright (c) 2000 Chakravarty, Keller, Lechtchinsky & Pfannenstiel
--
-- This file is free software; you can redistribute it and/or modify
-- it under the terms of the GNU General Public License as published by
-- the Free Software Foundation; either version 2 of the License, or
-- (at your option) any later version.
--
-- This file is distributed in the hope that it will be useful,
-- but WITHOUT ANY WARRANTY; without even the implied warranty of
-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-- GNU General Public License for more details.
--
--- DESCRIPTION ---------------------------------------------------------------
--
-- Parses a sugared version of the lambda calculus with parallel arrays.
--
--- DOCU ----------------------------------------------------------------------
--
-- language: Haskell 98
--
-- Grammar of the accepted language:
--
-- ident -> alphanumeric identifiers with lower and upper letters plus the
-- characters `_' and `''
-- ifxide -> string of symbols from "!#$%&*+-/:<=>?^|~"
-- int -> one or more digits
--
-- type -> `/' ide `::' expr
-- | ftype
-- ftype -> [stype `->'] ftype
-- stype -> [stype `+' ] ptype
-- ptype -> [btype `*' ] type
-- btype -> `()' | `Bool' | `Int'
-- | `[:' type `]'
-- | `(' type `)'
--
-- expr -> `\' ident `::' type `.' expr
-- | `/' ident `::' type `.' expr
-- | lexpr
-- | iexpr
-- iexpr -> iexpr ifxide aexpr
-- aexpr -> aexpr bexpr
-- bexpr -> `()' | `(,)'| `false' | true' | int | ident
-- | `(' ifxide `)'
-- | `(' expr `)'
-- | `(' expr `,' expr `)'
--
-- lexpr -> `let' bind_1 ... bind_n `in' expr (n > 1)
-- bind -> ident args `::' type `=' expr ';'
-- args -> arg_1 ... arg_n (n > 0)
-- arg -> `(' ident `::' type `)'
--
-- script -> bind_1 ... bind_n main (n > 0)
-- main -> `main' `=' expr
--
-- Note: This module uses the self-optimising parsers from the CTKlight,
-- which rely on existentially quantified type variables - a feature
-- not included in Haskell 98.
--
--- TODO ----------------------------------------------------------------------
--
module Parser (
parseScript, parseExpr, parseType
) where
import Common (Position, Pos(..), nopos)
import Utils (Tag(tag))
import Errors (showError)
import Lexers (Lexer, Regexp, (>||<), (>|<), (+>), star, plus, epsilon,
char, string, alt, lexaction, ctrlLexer, execLexer)
import Parsers (Token, Parser, (<|>), (*>), (-*>), (*->), list, list1, many,
many1, sep1, seplist1, skip, token, action, execParser)
import CoreAST
import Trafo (mkPair, mkPairPos)
-- lexical analysis
-- ----------------
-- token definition
--
data AToken = TokLParen Position -- `('
| TokRParen Position -- `)'
| TokUnit Position -- `()'
| TokLArray Position -- `[:'
| TokRArray Position -- `]'
| TokArrow Position -- `->'
| TokDot Position -- `.'
| TokSemic Position -- `;'
| TokComma Position -- `,'
| TokPlus Position -- `+'
| TokMul Position -- `*'
| TokDiv Position -- `/'
| TokBackSl Position -- `\'
| TokTypeOf Position -- `::'
| TokEqual Position -- `='
| TokBool Position -- `Bool'
| TokInt Position -- `Int'
| TokLet Position -- `let'
| TokIn Position -- `in'
| TokFalse Position -- `false'
| TokTrue Position -- `true'
| TokMain Position -- `main'
| TokIntLit Position Int -- integer constant
| TokIdent Position Ident -- identifier
| TokInfix Position Ident -- identifier
instance Pos AToken where
posOf (TokLParen pos ) = pos
posOf (TokRParen pos ) = pos
posOf (TokUnit pos ) = pos
posOf (TokLArray pos ) = pos
posOf (TokRArray pos ) = pos
posOf (TokArrow pos ) = pos
posOf (TokDot pos ) = pos
posOf (TokSemic pos ) = pos
posOf (TokComma pos ) = pos
posOf (TokPlus pos ) = pos
posOf (TokMul pos ) = pos
posOf (TokBackSl pos ) = pos
posOf (TokDiv pos ) = pos
posOf (TokTypeOf pos ) = pos
posOf (TokEqual pos ) = pos
posOf (TokBool pos ) = pos
posOf (TokInt pos ) = pos
posOf (TokLet pos ) = pos
posOf (TokIn pos ) = pos
posOf (TokFalse pos ) = pos
posOf (TokTrue pos ) = pos
posOf (TokMain pos ) = pos
posOf (TokIntLit pos _) = pos
posOf (TokIdent pos _) = pos
posOf (TokInfix pos _) = pos
instance Show AToken where
show (TokLParen _ ) = "("
show (TokRParen _ ) = ")"
show (TokUnit _ ) = "()"
show (TokLArray _ ) = "[:"
show (TokRArray _ ) = "]"
show (TokArrow _ ) = "->"
show (TokDot _ ) = "."
show (TokSemic _ ) = ";"
show (TokComma _ ) = ","
show (TokPlus _ ) = "+"
show (TokMul _ ) = "*"
show (TokDiv _ ) = "/"
show (TokBackSl _ ) = "\\"
show (TokTypeOf _ ) = "::"
show (TokEqual _ ) = "="
show (TokBool _ ) = "Bool"
show (TokInt _ ) = "Int"
show (TokLet _ ) = "let"
show (TokIn _ ) = "in"
show (TokFalse _ ) = "false"
show (TokTrue _ ) = "true"
show (TokMain _ ) = "main"
show (TokIntLit _ i) = show i
show (TokIdent _ s) = s
show (TokInfix _ s) = s
instance Tag AToken where
tag (TokLParen _ ) = 1
tag (TokRParen _ ) = 2
tag (TokUnit _ ) = 3
tag (TokLArray _ ) = 4
tag (TokRArray _ ) = 5
tag (TokArrow _ ) = 7
tag (TokDot _ ) = 8
tag (TokSemic _ ) = 9
tag (TokComma _ ) = 10
tag (TokPlus _ ) = 11
tag (TokMul _ ) = 12
tag (TokDiv _ ) = 13
tag (TokBackSl _ ) = 14
tag (TokTypeOf _ ) = 17
tag (TokEqual _ ) = 18
tag (TokBool _ ) = 19
tag (TokInt _ ) = 20
tag (TokLet _ ) = 21
tag (TokIn _ ) = 22
tag (TokFalse _ ) = 23
tag (TokTrue _ ) = 24
tag (TokMain _ ) = 25
tag (TokIntLit _ _) = 26
tag (TokIdent _ _) = 27
tag (TokInfix _ _) = 28
-- for the parser
--
instance Token AToken
instance Eq AToken where
t1 == t2 = tag t1 == tag t2
instance Ord AToken where
t1 <= t2 = tag t1 <= tag t2
-- local state instantiation
--
type LexState = ()
type ALexer = Lexer LexState AToken
type ARegexp = Regexp LexState AToken
-- lexer specification
--
lexer :: ALexer
lexer = identOrKW
>||< intconst
>||< op -- operator
>||< seper -- separator
>||< whitespace
-- whitespace
--
-- * horizontal and vertical tabs, newlines, and form feeds are filter out by
-- `Lexers.ctrlLexer'
--
whitespace :: ALexer
whitespace = (char ' ' `lexaction` \_ _ -> Nothing)
>||< ctrlLexer
-- identifiers and keywords
--
identOrKW :: ALexer
identOrKW =
letter +> (letter >|< digit)`star` epsilon
`lexaction` \cs pos -> Just $ (idkwtok $! pos) cs
where
idkwtok pos "Bool" = TokBool pos
idkwtok pos "Int" = TokInt pos
idkwtok pos "let" = TokLet pos
idkwtok pos "in" = TokIn pos
idkwtok pos "false" = TokFalse pos
idkwtok pos "true" = TokTrue pos
idkwtok pos "main" = TokMain pos
idkwtok pos cs = TokIdent pos cs
-- integer constants
--
intconst :: ALexer
intconst = digit`plus` epsilon
`lexaction` \cs pos -> Just $ TokIntLit pos (read cs)
-- symbols and infix operators
--
op :: ALexer
op =
special`plus` epsilon
`lexaction` \cs pos -> Just $ (idoptok $! pos) cs
where
idoptok pos "->" = TokArrow pos
idoptok pos "+" = TokPlus pos
idoptok pos "*" = TokMul pos
idoptok pos "/" = TokDiv pos
idoptok pos "::" = TokTypeOf pos
idoptok pos "=" = TokEqual pos
idoptok pos cs = TokInfix pos cs
seper :: ALexer
seper = sym "(" TokLParen
>||< sym ")" TokRParen
>||< sym "()" TokUnit
>||< sym "[:" TokLArray
>||< sym "]" TokRArray
>||< sym "." TokDot
>||< sym ";" TokSemic
>||< sym "," TokComma
>||< sym "\\" TokBackSl
where
sym cs con = string cs `lexaction` \_ pos -> Just (con pos)
letter, digit, visible :: Regexp s t
letter = alt ['a'..'z'] >|< alt ['A'..'Z'] >|< char '_' >|< char '\''
special = alt "!#$%&*+-/:<=>?^|~"
digit = alt ['0'..'9']
visible = alt [' '..'\127']
-- generate a token sequence out of a string denoting a lambda expression
-- (EXPORTED)
--
-- * the given position is attributed to the first character in the string
--
-- * stop if there is an error
--
lexExpr :: String -> Position -> [AToken]
lexExpr cs pos = let (ts, _, errs) = execLexer lexer (cs, pos, ())
in
if null errs then ts
else
error . unlines . map showError $ errs
-- syntactical analysis
-- --------------------
-- local parser instance
--
type AParser r = Parser () AToken r
-- action threading the position through into the result
--
actionWithPos :: Token t
=> Parser a t (s, Position)
-> (s -> r)
-> Parser a t (r, Position)
p `actionWithPos` f = p `action` \(r, pos) -> (f r, pos)
-- action threading the position through into the result
--
actionWithPos' :: Token t
=> Parser a t Position
-> r
-> Parser a t (r, Position)
p `actionWithPos'` r = p `action` \pos -> (r, pos)
-- action adding a position contained in the parseing result
--
actionGetPos :: (Token t , Pos s)
=> Parser a t s -> (s -> r) -> Parser a t (r, Position)
p `actionGetPos` f = p `action` \r -> (f r, posOf r)
-- given a token constructor, yield a parser accepting such tokens
--
tokenp :: (Position -> AToken) -> AParser Position
tokenp con = token (con nopos)
`action` posOf
-- given a token and a corresponding structure node, yield a parser doing the
-- conversion
--
tokenpTo :: (Position -> AToken) -> a -> AParser (a, Position)
tok `tokenpTo` con = tokenp tok
`action` \pos -> (con, pos)
-- given a token and a corresponding structure node, yield a parser doing the
-- conversion without the position
--
tokenpTo_ :: (Position -> AToken) -> a -> AParser a
tok `tokenpTo_` con = tok `tokenpTo` con
`action` \(r, _) -> r
-- given a token and a corresponding structure node, which represents an
-- expression with a position attribute, yield a parser doing the conversion
--
tokenpToPExpr :: (Position -> AToken)
-> SExpr Position
-> AParser PExpr
tok `tokenpToPExpr` con = tok `tokenpTo` con
`action` \(e, pos) -> e :> pos
-- accept an identifier
--
idp :: AParser (Ident, Position)
idp = token (TokIdent nopos undefined)
`action` \(TokIdent pos ide) -> (ide, pos)
-- accept an infix operator
--
infixp :: AParser (String, Position)
infixp = (token (TokInfix nopos undefined)
`actionGetPos` \(TokInfix _ ide) -> ide)
<|>
tokenp TokPlus
`actionWithPos'` "+"
<|>
tokenp TokMul
`actionWithPos'` "*"
<|>
tokenp TokDiv
`actionWithPos'` "/"
-- accept an integer
--
intp :: AParser (Int, Position)
intp = token (TokIntLit nopos undefined)
`actionGetPos` \(TokIntLit _ i) -> i
-- the following routines parse a type
--
-- * they use left-factorisation to get an LL(1) grammar
-- parse a primitive type
--
primTypep :: AParser Type
primTypep = (TokUnit
`tokenpTo_` TPrim UnitT)
<|>
(TokBool
`tokenpTo_` TPrim BoolT)
<|>
(TokInt
`tokenpTo_` TPrim IntT)
<|>
(idp
`action` \(ide, _) -> TVar ide)
<|>
( tokenp TokLArray
-*> typep
*-> tokenp TokRArray
`action` PArr)
<|>
( tokenp TokLParen
-*> typep
*-> tokenp TokRParen)
-- parse a sum type
--
prodTypep :: AParser Type
prodTypep = seplist1 (tokenp TokMul) primTypep
`action` foldl1 (:*)
-- parse a sum type
--
sumTypep :: AParser Type
sumTypep = seplist1 (tokenp TokPlus) prodTypep
`action` foldl1 (:+)
-- parse a functional type
--
funTypep :: AParser Type
funTypep = sep1 (\l _ r -> l :-> r) (tokenp TokArrow) sumTypep
-- parse a complete type
--
typep :: AParser Type
typep = ( tokenp TokDiv
-*> idp
*-> tokenp TokDot
*> typep
`action` \((ide, _), t) -> TRec ide t)
<|>
funTypep
-- the following routines parse an expression
--
-- * they use left-factorisation to get an LL(1) grammar
-- parse a primitive expression
--
primExprp :: AParser PExpr
primExprp = (TokUnit
`tokenpToPExpr` AConst Unit)
<|>
(TokFalse
`tokenpToPExpr` (AConst $ Bool False))
<|>
(TokTrue
`tokenpToPExpr` (AConst $ Bool True))
<|>
(intp
`action` \(i, pos) -> AConst (Int i) :> pos)
<|>
(idp
`action` \(ide, pos) -> AVar ide :> pos)
<|>
( tokenp TokLParen
-*> exprp
*> tokenp TokComma
*> exprp
*-> tokenp TokRParen
`action` \((e1, pos), e2) ->
AApp (AApp (AVar "(,)" :> pos) e1 :> pos) e2 :> pos)
<|>
( tokenp TokLParen
-*> infixp
*-> tokenp TokRParen
`action` \(ide, pos) -> AVar ide :> pos)
<|>
( tokenp TokLParen
-*> exprp
*-> tokenp TokRParen)
-- parse an application
--
appExprp :: AParser PExpr
appExprp = list1 primExprp
`action` foldl1 (\e1 e2 -> (AApp e1 e2) :> posOf e1)
-- parse an infix operator application
--
infixExprp :: AParser PExpr
infixExprp = -- !!!FIXME: associativity is screwed
--sep1 (\e op e' -> Var op :$ e :$ e') infixp appExprp
-- `action` foldl1 (\(e, op) e' -> Var op :$ e :$ e')
appExprp *> many (flip (.)) id suffix
`action`
\(prim, suffixFun) -> suffixFun prim
where
suffix = infixp
*> infixExprp
`action` \((ide, pos), e) ->
\e' -> (AApp (AVar ide :> pos)
(mkPairPos e' e pos)) :> pos
-- parse a let expression
--
letExprp :: AParser PExpr
letExprp = tokenp TokLet
*> list1 bindp
*-> tokenp TokIn
*> exprp
`action`
\((posLet, bnds), e') -> foldr (combine posLet) e' bnds
where
combine posLet ((ide, posBind), t, e) e' =
AApp (AAbs ide t e' :> posBind) e :> posLet
-- parse a let binding
--
bindp :: AParser ((Ident, Position), Type, PExpr)
bindp = idp
*> argsp
*-> tokenp TokTypeOf
*> typep
*-> tokenp TokEqual
*> exprp
*-> tokenp TokSemic
`action`
\(((ide, args), t), e) ->
let
ts = map snd args
abstr ((ide, pos), t) e = AAbs ide t e :> pos
in
(ide,
foldr (:->) t ts,
foldr abstr e args)
-- parse a set of arguments
--
argsp :: AParser [((Ident, Position), Type)]
argsp = many (:) [] argp
where
argp = tokenp TokLParen
-*> idp
*-> tokenp TokTypeOf
*> typep
*-> tokenp TokRParen
-- parse a complete expression
--
exprp :: AParser PExpr
exprp = ( tokenp TokBackSl
-*> idp
*-> tokenp TokTypeOf
*> typep
*-> tokenp TokDot
*> exprp
`action` \(((ide, pos), t), e) -> AAbs ide t e :> pos)
<|>
( tokenp TokDiv
-*> idp
*-> tokenp TokTypeOf
*> typep
*-> tokenp TokDot
*> exprp
`action` \(((ide, pos), t), e) -> AVRec ide t e :> pos)
<|>
letExprp
<|>
infixExprp
-- parse a script
--
scriptp :: AParser PExpr
scriptp = list bindp
*> tokenp TokMain
*-> tokenp TokEqual
*> exprp
*-> tokenp TokSemic
`action` \((bnds, posMain), body) ->
foldr (combine posMain) body bnds
where
combine posMain ((ide, posBind), t, e) e' =
AApp (AAbs ide t e' :> posBind) e :> posMain
-- parse a script (EXPORTED)
--
-- * the given position is attributed to the first character in the string
--
-- * stop if there is an error
--
parseScript :: Position -> String -> PExpr
parseScript = doParse scriptp
-- parse an expression (EXPORTED)
--
-- * the given position is attributed to the first character in the string
--
-- * stop if there is an error
--
parseExpr :: Position -> String -> PExpr
parseExpr = doParse exprp
-- parse a type expression (EXPORTED)
--
-- * the given position is attributed to the first character in the string
--
-- * stop if there is an error
--
parseType :: Position -> String -> Type
parseType = doParse typep
-- parse an entity specified by the given parser
--
-- * the given position is attributed to the first character in the string
--
-- * stop if there is an error
--
doParse :: AParser a -> Position -> String -> a
doParse parser pos cs = let toks = lexExpr cs pos
(t, errs, toks') = execParser parser () toks
in
if null errs
then
if null toks' then t
else
error $ "Trailing garbage: " ++ show toks'
else
error . unlines . map showError $ errs
-- Local Variables:
-- haskell-hugs-program-args: ("+." "-98"
"-P../hipar/base/errors:../hipar/base/admin:../hipar/base/general:../hipar/base/syntax:")
-- End:
-- Flattening Prototype: Core Abstract Syntax
--
-- Authors: Nepal Team
-- Created: 29 February 2000
--
-- Version $Revision: 1.9 $ from $Date: 2000/09/15 12:16:23 $
--
-- Copyright (c) 2000 Chakravarty, Keller, Lechtchinsky & Pfannenstiel
--
-- This file is free software; you can redistribute it and/or modify
-- it under the terms of the GNU General Public License as published by
-- the Free Software Foundation; either version 2 of the License, or
-- (at your option) any later version.
--
-- This file is distributed in the hope that it will be useful,
-- but WITHOUT ANY WARRANTY; without even the implied warranty of
-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-- GNU General Public License for more details.
--
--- DESCRIPTION ---------------------------------------------------------------
--
-- Abstract syntax tree for a lambda calculus enriched with parallel arrays
--
--- DOCU ----------------------------------------------------------------------
--
-- language: Haskell 98
--
--- TODO ----------------------------------------------------------------------
--
-- * H98 non-conformance in instance declaration for `PExpr'
--
module CoreAST (
Ident, Type(..), TScheme(..), PrimType(..), Expr(..), Const(..),
AExpr(..), SExpr(..), erase, attr,
TExpr, PExpr,
showScript
) where
import Char (isAlphaNum)
import Common (Position, Pos(posOf))
import Pretty
infixl 5 :+
infixl 4 :*
infixr 3 :->
infixl 2 :$
-- preliminaries
-- -------------
-- we represent identifiers naively as strings (EXPORTED)
--
type Ident = String
-- types
-- -----
-- AST of core types (EXPORTED)
--
data Type = TPrim PrimType -- primitive type
| TVar Ident -- type variable
| Type :* Type -- product
| Type :+ Type -- sum
| Type :-> Type -- functional
| TRec Ident Type -- recursive type
| PArr Type -- parallel array
instance Show Type where
show = show . pretty
-- AST of type schemes (EXPORTED)
--
data TScheme = TScheme [Ident] Type
instance Show TScheme where
show = show . pretty
-- primitive types (EXPORTED)
--
data PrimType = UnitT | BoolT | IntT
| BoolArrT | IntArrT -- only in the target language
deriving (Eq)
instance Show PrimType where
show = show . pretty
-- expressions
-- -----------
-- AST of core expressions (EXPORTED)
--
data Expr = Const Const -- constant
| Var Ident -- variable (also primitive names)
| Abs Ident Type Expr -- lambda abstraction
| Expr :$ Expr -- application
| VRec Ident Type Expr -- recursive binding
instance Show Expr where
show = show . pretty
-- AST of constants (EXPORTED)
--
data Const = Unit -- unit value
| Bool Bool -- boolean constant
| Int Int -- integer constant
instance Show Const where
show = show . pretty
-- attributed expressions
-- ----------------------
-- AST of attributed core expressions (EXPORTED)
--
data AExpr a = SExpr a :> a -- attribute
data SExpr a = AConst Const -- constant
| AVar Ident -- variable (also primitive names)
| AAbs Ident Type (AExpr a) -- lambda abstraction
| AApp (AExpr a) (AExpr a) -- application
| AVRec Ident Type (AExpr a) -- recursive binding
instance Show (AExpr a) where
show = show . erase
-- remove attributes (EXPORTED)
--
erase :: AExpr a -> Expr
erase (e :> _) = serase e
where
serase (AConst c ) = Const c
serase (AVar v ) = Var v
serase (AAbs ide t e) = Abs ide t (erase e)
serase (AApp e1 e2 ) = erase e1 :$ erase e2
serase (AVRec ide t e) = VRec ide t (erase e)
-- add trivial attributes (EXPORTED)
--
attr :: Expr -> AExpr ()
attr e = sattr e :> ()
where
sattr (Const c ) = AConst c
sattr (Var v ) = AVar v
sattr (Abs ide t e) = AAbs ide t (attr e)
sattr (e1 :$ e2 ) = AApp (attr e1) (attr e2)
sattr (VRec ide t e) = AVRec ide t (attr e)
-- typed expressions
-- -----------------
-- AST of typed core expressions (EXPORTED)
--
type TExpr = AExpr Type
-- expressions with a position attribute
-- -------------------------------------
-- AST of core expressions with a position attribute (EXPORTED)
--
type PExpr = AExpr Position
-- !!!FIXME: this is not really Haskell 98
instance Pos PExpr where
posOf (_ :> a) = a
-- pretty printing routines
-- -------------------------
times, plus, arrow :: (Pretty a, Pretty b) => a -> b -> Int -> Doc
times = infixOp LeftAssoc 7 "*"
plus = infixOp LeftAssoc 6 "+"
arrow = infixOp RightAssoc 5 "->"
instance Pretty Type where
prettyPrec _ (TPrim pt) = pretty pt
prettyPrec _ (TVar ide) = text ide
prettyPrec p (t1 :* t2) = t1 `times` t2 $ p
prettyPrec p (t1 :+ t2) = t1 `plus` t2 $ p
prettyPrec p (t1 :-> t2) = t1 `arrow` t2 $ p
prettyPrec p (TRec ide t) = parens `usedWhen` (p > 0) $
cat [
char '/',
text ide,
char '.'
] `hang` 2 $ pretty t
prettyPrec p (PArr t) = cat [text "[:", pretty t, text "]"]
instance Pretty TScheme where
prettyPrec _ (TScheme ides t) = cat [text "\\/", hsepTexts ides, char '.']
`hang` 2 $ pretty t
where
hsepTexts = hsep . map text
instance Pretty PrimType where
prettyPrec _ UnitT = text "()"
prettyPrec _ BoolT = text "Bool"
prettyPrec _ IntT = text "Int"
prettyPrec _ BoolArrT = text "BoolArr"
prettyPrec _ IntArrT = text "IntArr"
-- special rendering of applications
--
-- * when the first argument of an application is an abstraction, we render it
-- as a let-in expression
--
-- * curried binary applications of functions whose lexeme starts with a symbol
-- (not alphanum, nor underscore, nor hyphen), we render it as a binary
-- infix operator
--
-- * binary applications of the function with the lexeme "(,)", we render it as
-- "(a1, a2)", ie, they represent pairs
--
app :: Expr -> Expr -> Int -> Doc
app (Abs ide t e) e' p =
let
(bnds, body) = collectBinds (Abs ide t e) e'
in
parens `usedWhen` (p > 0) $
sep [
text "let" `hang` 2 $
vcat . map (\(ide, t, e) -> bind ide t e) $ bnds,
text "in",
pretty body
]
app (Var "(,)" :$ arg1) arg2 p =
sep [
char '(' <> prettyPrec 0 arg1 <> char ',',
prettyPrec 0 arg2 <> char ')'
]
app (Var (c:cs)) (Var "(,)" :$ arg1 :$ arg2) p
| not (isAlphaNum c || c == '_' || c == '\'') =
parens `usedWhen` (p > 0) $
hsep [
prettyPrec 1 arg1 ,
text (c:cs),
prettyPrec 2 arg2
]
app arg1 arg2 p =
parens `usedWhen` (p > 1) $
prettyPrec 1 arg1 <+> prettyPrec 2 arg2
-- collect all abstraction-application pairs that can be rendered as bindings
--
collectBinds :: Expr -> Expr -> ([(Ident, Type, Expr)], Expr)
collectBinds (Abs ide t e) e' =
case e of
(e1 :$ e2) -> let (bnds, body) = collectBinds e1 e2
in
( (ide, t, e') : bnds, body)
_ -> ([(ide, t, e')], e)
collectBinds e e' = ([], e :$ e')
-- rendering of a let binding
--
-- * when the bound value is a function, we render it as a function binding
--
bind :: Ident -> Type -> Expr -> Doc
bind ide t e =
let
(args, body) = collectArgs e
resultType = dropArgsFromType (length args) t
in
(text ide `hang` 2 $
sep (prettyArgs args ++ [text "::" <+> resultType <+> equals])) `hang` 2 $
pretty body <> semi
where
collectArgs (Abs ide t e) = let (args, body) = collectArgs e
in
((ide, t) : args, body)
collectArgs e = ([], e)
--
prettyArgs [] = []
prettyArgs ((ide, t) : args) = (parens $
hsep [text ide, text "::", pretty t]
) : prettyArgs args
--
dropArgsFromType 0 t = pretty t
dropArgsFromType n (_ :-> t) = dropArgsFromType (n - 1) t
dropArgsFromType _ _ = text "<<error>>"
instance Pretty Expr where
prettyPrec p (Const c) = prettyPrec p c
prettyPrec p (Var ide@(c:_))
| not (isAlphaNum c || c == '_' || c == '\'')
= hcat [char '(', text ide, char ')']
| otherwise = text ide
prettyPrec p (Abs ide t e) = parens `usedWhen` (p > 0) $
cat [
char '\\',
sep [
text ide,
text "::",
pretty t
],
char '.'
] `hang` 2 $ pretty e
prettyPrec p (e1 :$ e2) = e1 `app` e2 $ p
prettyPrec p (VRec ide t e) = parens `usedWhen` (p > 0) $
cat [
char '/',
sep [
text ide,
text "::",
pretty t
],
char '.'
] `hang` 2 $ pretty e
instance Pretty Const where
prettyPrec _ Unit = text "()"
prettyPrec _ (Bool b) = toDoc b
prettyPrec _ (Int i) = toDoc i
-- a script is a let-in cascade where we omit the let-in and render the body
-- as a binding to a variable `main' (EXPORTED)
--
showScript :: Expr -> String
showScript = show . prettyScript . extract
where
extract (e1 :$ e2) = collectBinds e1 e2
extract e = ([], e) -- no binding
prettyScript (bnds, body) =
(vcat . map (\(ide, t, e) -> bind ide t e) $ bnds)
$$
(text "main =" `hang` 2 $
pretty body <> semi)
-- Local Variables:
-- haskell-hugs-program-args: ("+." "-P../hipar/base/syntax:")
-- End: