Copyright© 2019 Elias Castegren and Kiko Fernandez-Reyes
LicenseMIT
Stabilityexperimental
Portabilityportable
Safe HaskellNone

Final.AST

Contents

Description

This module includes functionality for creating an Abstract Syntax Tree (AST), backtraces (Backtrace), as well as helper functions for checking different aspects of the AST. The AST abstract over their kind Phase, where Phase represent the current state of the AST. For example, after parsing the AST is of Parsed Phase; after type checking with tcProgram the returned AST is of Checked Phase, indicating that the AST has been type checked.

Synopsis

Documentation

type Name = String Source #

isConstructorName :: [Char] -> Bool Source #

Check if a name is a constructor name

AST declarations

Declaration for the Abstract Syntax Tree of the language. This section contains the type, class, methods, fields and expressions represented as an AST. The AST is produced by a parser. For more information on building parsers, we recommend to read megaparsec.

data Type (p :: Phase f) Source #

Representation of types abstracting over the Phase

Constructors

ClassType Name

Represents a class of name Name

IntType

Represents integers

BoolType

Represents booleans

Arrow

Represents a function type

Fields

UnitType

Represents the unit (void) type

Instances
Typecheckable (Type :: Phase (Proxy :: Type -> Type) -> Type) (Type :: Phase Identity -> Type) Source # 
Instance details

Defined in Final.Typechecker

Eq (Type p) Source # 
Instance details

Defined in Final.AST

Methods

(==) :: Type p -> Type p -> Bool

(/=) :: Type p -> Type p -> Bool

Show (Type p) Source # 
Instance details

Defined in Final.AST

Methods

showsPrec :: Int -> Type p -> ShowS

show :: Type p -> String

showList :: [Type p] -> ShowS

Backtraceable (Type p) Source # 
Instance details

Defined in Final.AST

Precheckable (Type p) (Type Checked) Source # 
Instance details

Defined in Final.Typechecker

newtype Program (ip :: Phase f) Source #

The representation of a program in the form of an AST node.

Constructors

Program [ClassDef ip]

Programs are simply a list of class definitions (ClassDef) in a certain Phase

Instances
Typecheckable (Program :: Phase (Proxy :: Type -> Type) -> Type) (Program :: Phase Identity -> Type) Source # 
Instance details

Defined in Final.Typechecker

Show (Program ip) Source # 
Instance details

Defined in Final.AST

Methods

showsPrec :: Int -> Program ip -> ShowS

show :: Program ip -> String

showList :: [Program ip] -> ShowS

data Phase (f :: * -> *) where Source #

Phases that have already been passed. This has been thought as going through different phases of a compiler. We assume that there is a total order between phases.

Constructors

Parsed 

Fields

  • :: Phase Proxy

    Initial status of an AST node after parsing

Checked 

Fields

  • :: Phase Identity

    Status of an AST node after type checking

data ClassDef (ip :: Phase f) Source #

A representation of a class in the form of an AST node. As an example:

class Foo:
  val x: Int
  var y: Bool
  def main(): Int
    42

the code above, after parsing, would generate the following AST:

ClassDef {cname = "Foo"
         ,fields = [FieldDef {fname = "x"
                             ,ftype = IntType
                             ,fmod = Val}]
         ,methods = [MethodDef {mname = "main"
                               ,mparams = []
                               ,mtype = IntType
                               ,mbody = [IntLit {etype = Proxy, ival = 42}]
                               }]}

Constructors

ClassDef 

Fields

Instances
Typecheckable (ClassDef :: Phase (Proxy :: Type -> Type) -> Type) (ClassDef :: Phase Identity -> Type) Source # 
Instance details

Defined in Final.Typechecker

Show (ClassDef ip) Source # 
Instance details

Defined in Final.AST

Methods

showsPrec :: Int -> ClassDef ip -> ShowS

show :: ClassDef ip -> String

showList :: [ClassDef ip] -> ShowS

Backtraceable (ClassDef p) Source # 
Instance details

Defined in Final.AST

Precheckable (ClassDef Parsed) ClassEntry Source # 
Instance details

Defined in Final.Typechecker

data Mod Source #

Field qualifiers in a class. It is thought for a made up syntax such as:

class Foo:
  val x: Int
  var y: Bool

This indicates that the variable x is immutable, and y can be mutated.

Constructors

Var

Indicates that the field can be mutated

Val

Indicates that the field is immutable

Instances
Eq Mod Source # 
Instance details

Defined in Final.AST

Methods

(==) :: Mod -> Mod -> Bool

(/=) :: Mod -> Mod -> Bool

Show Mod Source # 
Instance details

Defined in Final.AST

Methods

showsPrec :: Int -> Mod -> ShowS

show :: Mod -> String

showList :: [Mod] -> ShowS

data FieldDef (p :: Phase f) Source #

Representation of a field declaration in the form of an AST node. As an example, the following code:

class Foo:
  val x: Int

could be parsed to the following field representation:

FieldDef {fname = "x"
         ,ftype = IntType
         ,fmod = Val}

Constructors

FieldDef 

Fields

Instances
Typecheckable (FieldDef :: Phase (Proxy :: Type -> Type) -> Type) (FieldDef :: Phase Identity -> Type) Source # 
Instance details

Defined in Final.Typechecker

Show (FieldDef p) Source # 
Instance details

Defined in Final.AST

Methods

showsPrec :: Int -> FieldDef p -> ShowS

show :: FieldDef p -> String

showList :: [FieldDef p] -> ShowS

Backtraceable (FieldDef p) Source # 
Instance details

Defined in Final.AST

Precheckable (FieldDef Parsed) FieldEntry Source # 
Instance details

Defined in Final.Typechecker

isValField :: FieldDef p -> Bool Source #

Helper function to check whether a FieldDef is immutable.

isVarField :: FieldDef p -> Bool Source #

Helper function to check whether a FieldDef is mutable.

data Param (p :: Phase f) Source #

Representation of parameters in the form of an AST.

Constructors

Param 

Fields

Instances
Typecheckable (Param :: Phase (Proxy :: Type -> Type) -> Type) (Param :: Phase Identity -> Type) Source # 
Instance details

Defined in Final.Typechecker

Show (Param p) Source # 
Instance details

Defined in Final.AST

Methods

showsPrec :: Int -> Param p -> ShowS

show :: Param p -> String

showList :: [Param p] -> ShowS

Backtraceable (Param p) Source # 
Instance details

Defined in Final.AST

Precheckable (Param Parsed) (Param Checked) Source # 
Instance details

Defined in Final.Typechecker

data MethodDef (ip :: Phase f) Source #

Representation of a method declaration in the form of an AST. For example:

class Foo:
  def main(): Int
    42

the code above, after parsing, would generate the following AST:

ClassDef {cname = "Foo"
         ,fields = []
         ,methods = [MethodDef {mname = "main"
                               ,mparams = []
                               ,mtype = IntType
                               ,mbody = [IntLit {etype = Proxy, ival = 42}]
                               }]}

Constructors

MethodDef 

Fields

Instances
Typecheckable (MethodDef :: Phase (Proxy :: Type -> Type) -> Type) (MethodDef :: Phase Identity -> Type) Source # 
Instance details

Defined in Final.Typechecker

Show (MethodDef ip) Source # 
Instance details

Defined in Final.AST

Methods

showsPrec :: Int -> MethodDef ip -> ShowS

show :: MethodDef ip -> String

showList :: [MethodDef ip] -> ShowS

Backtraceable (MethodDef p) Source # 
Instance details

Defined in Final.AST

Precheckable (MethodDef Parsed) MethodEntry Source # 
Instance details

Defined in Final.Typechecker

commaSep :: Show t => [t] -> String Source #

Takes a list of things that can be shown, and creates a comma separated string.

data Op Source #

Representation of integer operations

Constructors

Add 
Sub 
Mul 
Div 
Instances
Eq Op Source # 
Instance details

Defined in Final.AST

Methods

(==) :: Op -> Op -> Bool

(/=) :: Op -> Op -> Bool

Show Op Source # 
Instance details

Defined in Final.AST

Methods

showsPrec :: Int -> Op -> ShowS

show :: Op -> String

showList :: [Op] -> ShowS

data Expr (p :: Phase f) Source #

Representation of expressions in the form of an AST node. The language is expression-based, so there are no statements. As an example, the following identity function:

let id = \x: Int -> x
in id 42

would be parsed as this Expr:

Let {etype = Proxy
    ,name = "id"
    ,val = Lambda {etype = Proxy
                  ,params = [Param "x" IntType]
                  ,body =   FunctionCall {etype = Proxy
                                         ,target = VarAccess Proxy "id"
                                         ,args = [IntLit Proxy 42]}
                  }
    ,body  :: Expr p
    }

Constructors

BoolLit

Representation of a boolean literal

Fields

IntLit

Representation of an integer literal

Fields

Null 

Fields

Lambda

Representation of a lambda expression

Fields

VarAccess

Representation of a variable access

Fields

FieldAccess 

Fields

  • etype :: f (Type p)

    Type of the expression

  • target :: Expr p

    The target in a field access, e.g., x.foo, then x is the target.

  • name :: Name

    Variable name

Assignment 

Fields

  • etype :: f (Type p)

    Type of the expression

  • lhs :: Expr p

    Left-hand side expression

  • rhs :: Expr p

    Right-hand side expression

MethodCall 

Fields

  • etype :: f (Type p)

    Type of the expression

  • target :: Expr p

    The target in a field access, e.g., x.foo, then x is the target.

  • name :: Name

    Variable name

  • args :: [Expr p]

    The arguments of the method call

FunctionCall 

Fields

  • etype :: f (Type p)

    Type of the expression

  • target :: Expr p

    The target in a field access, e.g., x.foo, then x is the target.

  • args :: [Expr p]

    The arguments of the method call

If 

Fields

  • etype :: f (Type p)

    Type of the expression

  • cond :: Expr p

    The condition in the if-else expression

  • thn :: Expr p

    The body of the then branch

  • els :: Expr p

    The body of the else branch

Let 

Fields

  • etype :: f (Type p)

    Type of the expression

  • name :: Name

    Variable name

  • val :: Expr p

    Expression that will bound variable name with value val

  • body :: Expr p

    The body of the lambda abstraction

BinOp 

Fields

  • etype :: f (Type p)

    Type of the expression

  • op :: Op

    Binary operation

  • lhs :: Expr p

    Left-hand side expression

  • rhs :: Expr p

    Right-hand side expression

New

It is useful to decouple the type of the expression from the type of the instantiated class. This distinction becomes important whenever we have subtyping, e.g., an interface Animal where `Animal x = new Dog`

Fields

  • etype :: f (Type p)

    Type of the expression

  • ty :: Type p

    The class that one instantiates, e.g., `new C`

  • args :: [Expr p]

    The arguments of the method call

Cast 

Fields

  • etype :: f (Type p)

    Type of the expression

  • body :: Expr p

    The body of the lambda abstraction

  • ty :: Type p

    The class that one instantiates, e.g., `new C`

Instances
Typecheckable (Expr :: Phase (Proxy :: Type -> Type) -> Type) (Expr :: Phase Identity -> Type) Source # 
Instance details

Defined in Final.Typechecker

Show (Expr p) Source # 
Instance details

Defined in Final.AST

Methods

showsPrec :: Int -> Expr p -> ShowS

show :: Expr p -> String

showList :: [Expr p] -> ShowS

Backtraceable (Expr p) Source # 
Instance details

Defined in Final.AST

Helper functions

The helper functions of this section operate on AST nodes to check for different properties. As an example, to check whether an expression is a field, instead of having to pattern match in all places, i.e.,

exampleFunction :: Expr -> Bool
exampleFunction expr =
  -- does some stuff
  ...
  case expr of
    FieldAccess expr -> True
    _                -> False

we define the isFieldAccess helper function, which checks whether a given expression is a FieldAccess:

exampleFunction :: Expr -> Bool
exampleFunction expr =
  -- does some stuff
  ...
  isFieldAccess expr

thisName :: Name Source #

Constant for the name this, commonly used in object-oriented languages.

isArrowType :: Type p -> Bool Source #

Checks whether a Type is a function (arrow) type

isFieldAccess :: Expr p -> Bool Source #

Checks whether an expression is a FieldAccess.

isVarAccess :: Expr p -> Bool Source #

Checks whether an expression is a VarAccess.

isThisAccess :: Expr p -> Bool Source #

Checks whether an expression is a VarAccess of this.

isLVal :: Expr p -> Bool Source #

Checks whether an expression is an lval.

isClassType :: Type p -> Bool Source #

Helper function to check whether a Type is a class

getType :: Expr Checked -> Type Checked Source #

Helper function to extract the type from an expression.

setType :: Type Checked -> Expr Checked -> Expr Checked Source #

Sets the type of an expression e to t.

usesVar :: Expr p -> Name -> Bool Source #

Helper function that checks whether an expression uses a variable. This helper function can be used to throw a warning if the variable is unused.

Backtrace declarations

newtype Backtrace Source #

Representation of a backtrace

Constructors

Backtrace [BacktraceNode]

The representation of a backtrace consists of a list of backtrace nodes

Instances
Show Backtrace Source # 
Instance details

Defined in Final.AST

Methods

showsPrec :: Int -> Backtrace -> ShowS

show :: Backtrace -> String

showList :: [Backtrace] -> ShowS

Semigroup Backtrace Source # 
Instance details

Defined in Final.AST

Methods

(<>) :: Backtrace -> Backtrace -> Backtrace

sconcat :: NonEmpty Backtrace -> Backtrace

stimes :: Integral b => b -> Backtrace -> Backtrace

emptyBt :: Backtrace Source #

Helper function for starting with an empty backtrace

data BacktraceNode where Source #

Representation of different kinds of Backtrace nodes. The backtrace nodes contain all the available information that can be shown to the developer after a crash.

Constructors

BTClass :: ClassDef p -> BacktraceNode

Represents the backtrace of a class

BTParam :: Param p -> BacktraceNode

Represents the backtrace of parameters

BTField :: FieldDef p -> BacktraceNode

Represents the backtrace of a field

BTMethod :: MethodDef p -> BacktraceNode

Represents the backtrace of a method

BTExpr :: Expr p -> BacktraceNode

Represents the backtrace of an expression

BTType :: Type p -> BacktraceNode

Represents the backtrace of a type

Instances
Show BacktraceNode Source # 
Instance details

Defined in Final.AST

Methods

showsPrec :: Int -> BacktraceNode -> ShowS

show :: BacktraceNode -> String

showList :: [BacktraceNode] -> ShowS

class Backtraceable a where Source #

The type class defines how to create a Backtrace node, combinator backtrace, and how to push a new node to an existing backtrace.

Minimal complete definition

backtrace

Methods

backtrace :: a -> BacktraceNode Source #

Create a backtrace node

push :: a -> Backtrace -> Backtrace Source #

Create a new backtrace node and append it to the existing backtrace

Instances
Backtraceable (Expr p) Source # 
Instance details

Defined in Final.AST

Backtraceable (MethodDef p) Source # 
Instance details

Defined in Final.AST

Backtraceable (Param p) Source # 
Instance details

Defined in Final.AST

Backtraceable (FieldDef p) Source # 
Instance details

Defined in Final.AST

Backtraceable (ClassDef p) Source # 
Instance details

Defined in Final.AST

Backtraceable (Type p) Source # 
Instance details

Defined in Final.AST