DATA Program
  | Program
      blocks : BlocksTop

DATA BlocksTop
  | Top
      blocks : Blocks
  | None

TYPE Blocks = [Block]

DATA Block
  | Itf
      itf : Itf
  | Data
      data : Data
  | Type
      type : Type
  | Section
      code : Code
  | Item
      name : Ident
      item : Item
  | DataSem
      sem  : DataSem

DATA Itf
  | Itf
      pos    : Pos
      name   : Ident
      vars   : Vars
      visits : ItfVisits

TYPE ItfVisits = [ItfVisit]

DATA ItfVisit
  | Visit
      pos    : Pos
      name   : Ident
      cyclic : Bool
      vars   : Vars
      attrs  : Attrs

TYPE Attrs = [Attr]

DATA Attr
  | Inh
      name : Ident
      type : String
  | Syn
      name : Ident
      type : String

DATA Data
  | Data
      pos    : Pos
      name   : Ident
      vars   : Vars
      cons   : Cons
      exts   : Exts

TYPE Vars = [Var]

DATA Var
  | Var
      name   : Ident

TYPE Exts = [Ext]

DATA Ext
  | Ext
      name   : Ident

TYPE Cons = [Con]

DATA Con
  | Con
      pos    : Pos
      name   : Ident
      vars   : Vars
      fields : Fields

TYPE Fields = [Field]

DATA Field
  | Field
      name       : Ident
      type       : FieldType

DATA FieldType
  | Term     type : String
  | Nonterm  name : Ident

DATA Type
  | Alias
      pos    : Pos
      name   : Ident
      type   : AliasType
      vars   : Vars

DATA AliasType
  | Prod   fields : {[Ident]}
  | List   type   : Ident
  | Maybe  type   : Ident

DATA DataSem
  | Sem
      pos     : Pos
      tp      : Ident
      vars    : Vars
      mbMonad : {Maybe String}
      cyclic  : Bool
      stmts   : {Stmts}
      clauses : ClausesTop

TYPE SemCons = [SemCon]

DATA SemCon
  | Con
      pos     : Pos
      name    : Ident
      fields  : SemFields

TYPE SemFields = [SemField]

DATA SemField
  | Field
      pos     : Pos
      name    : Ident
      type    : {Either Ident String}

DATA Code
  | Code
      items : Items

TYPE MaybeBoundCode = MAYBE BoundCode

DATA BoundCode
  | Code
      bind : Bind
      pos  : Pos
      code : Code

TYPE Items = [Item]

DATA Item
  | Plain
      pos      : Pos
      txt      : String
  | Attr
      pos      : Pos
      child    : Ident
      name     : Ident
  | Sem
      pos      : Pos
      name     : Ident
      tp       : Ident
      vars     : Vars
      mbMonad  : {Maybe String}
      first    : SemVisit
  | CoSem
      pos      : Pos
      name     : Ident
      tp       : Ident
      visit    : Ident
      vars     : Vars
      mbMonad  : {Maybe String}
      first    : SemVisit
  | DataSem
      sem      : DataSem
  | Detach  -- requires visits up to but not including this visit to be invoked
      pos      : Pos
      visit    : Ident
      name     : Ident
  | Construct
      pos      : Pos
      data     : Ident
      con      : Ident
      fields   : ExprFields
  | Brackets
      pos      : Pos
      items    : Items
      posEnd   : Pos

TYPE ExprFields = [ExprField]

DATA ExprField
  | Field
      name  : Ident
      code  : Code

DATA SemVisit
  | Visit
      pos      : Pos
      name     : Ident
      cyclic   : Bool
      attrs    : VisitAttrs
      stmts    : Stmts
      clauses  : ClausesTop
  | Internal
      pos      : Pos
      name     : Ident
      cyclic   : Bool
      stmts    : Stmts
      clauses  : ClausesTop
  | Impl
  | Prependable  -- maybe prepended by other visits
      pos      : Pos
      name     : Ident
      actual   : {SemVisit}
  | End

TYPE VisitAttrs = [VisitAttr]

DATA VisitAttr
  | Chn
      name  : Ident
      type  : String

DATA ClausesTop
  | Top
      clauses : Clauses
  | Impl
      clauses : {Clauses}

TYPE Clauses = [Clause]

DATA Clause
  | Clause
      pos     : Pos
      name    : Ident
      stmts   : Stmts
      next    : SemVisit

TYPE Stmts = [Stmt]

DATA Stmt
  | Eval
      mode    : Mode
      pat     : Pat
      code    : BoundCode
  | Attach
      pos     : Pos
      mbVisit : {Maybe Ident}
      name    : Ident
      type    : Ident
      code    : MaybeBoundCode
  | Invoke
      pos     : Pos
      visit   : Ident
      name    : Ident
      code    : MaybeBoundCode
  | Default
      allowEmpty : Bool
      pos        : Pos
      name       : Ident
      mbCode     : MaybeBoundCode
  | Rename
      pos        : Pos
      child      : Ident
      subst      : Renames

TYPE Renames = [Rename]
DATA Rename | Rename
  source : Ident
  dest   : Ident

DATA Mode
  | Match
  | Assert

DATA Bind
  | Fun
  | Monadic

TYPE Pats = [Pat]

DATA Pat
  | Con
      name   : Ident
      pats   : Pats
  | AttrCon
      con    : Ident
      name   : Ident
      dt     : Ident
  | Attr
      child  : Ident
      name   : Ident
  | Tup
      pats   : Pats
  | List
      pats   : Pats
  | Cons
      hd     : Pat
      tl     : Pat
  | Underscore
      pos    : Pos

DATA AttrTypePat
  | VisLocal
  | ProdLocal
  | Lhs
  | Child
  | Visit

DATA AttrTypeCode
  | VisLocal
  | ProdLocal
  | Lhs
  | Child
  | Visit

TYPE ImplStmts = [ImplStmt]

DATA ImplStmt
  | Invoke
      pos        : Pos
      child      : Ident
      visit      : Ident
      itf        : Ident
  | DefaultChild
      pos        : Pos
      allowEmpty : Bool
      child      : Ident
      name       : Ident
      mbCodeRef  : {Maybe Int}
  | DefaultSyn
      pos        : Pos
      allowEmpty : Bool
      name       : Ident
      mbCodeRef  : {Maybe Int}
  | DefaultVisLocal
      pos        : Pos
      name       : Ident