"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:

Reply via email to