| Copyright | (c) Kimiyuki Onaka 2020 |
|---|---|
| License | Apache License 2.0 |
| Maintainer | kimiyuki95@gmail.com |
| Stability | experimental |
| Portability | portable |
| Safe Haskell | None |
| Language | Haskell2010 |
Jikka.Core.Language.Expr
Description
Expr module has the basic data types for our core language.
They are similar to the GHC Core language.
Synopsis
- newtype VarName = VarName String
- unVarName :: VarName -> String
- newtype TypeName = TypeName String
- unTypeName :: TypeName -> String
- data Type
- data DataStructure
- data Semigroup'
- data Builtin
- = Negate
- | Plus
- | Minus
- | Mult
- | FloorDiv
- | FloorMod
- | CeilDiv
- | CeilMod
- | Pow
- | Abs
- | Gcd
- | Lcm
- | Min2 Type
- | Max2 Type
- | Iterate Type
- | Not
- | And
- | Or
- | Implies
- | If Type
- | BitNot
- | BitAnd
- | BitOr
- | BitXor
- | BitLeftShift
- | BitRightShift
- | MatAp Int Int
- | MatZero Int
- | MatOne Int
- | MatAdd Int Int
- | MatMul Int Int Int
- | MatPow Int
- | VecFloorMod Int
- | MatFloorMod Int Int
- | ModNegate
- | ModPlus
- | ModMinus
- | ModMult
- | ModInv
- | ModPow
- | ModMatAp Int Int
- | ModMatAdd Int Int
- | ModMatMul Int Int Int
- | ModMatPow Int
- | Cons Type
- | Snoc Type
- | Foldl Type Type
- | Scanl Type Type
- | Build Type
- | Len Type
- | Map Type Type
- | Filter Type
- | At Type
- | SetAt Type
- | Elem Type
- | Sum
- | Product
- | ModSum
- | ModProduct
- | Min1 Type
- | Max1 Type
- | ArgMin Type
- | ArgMax Type
- | All
- | Any
- | Sorted Type
- | Reversed Type
- | Range1
- | Range2
- | Range3
- | Tuple [Type]
- | Proj [Type] Int
- | LessThan Type
- | LessEqual Type
- | GreaterThan Type
- | GreaterEqual Type
- | Equal Type
- | NotEqual Type
- | Fact
- | Choose
- | Permute
- | MultiChoose
- | ConvexHullTrickInit
- | ConvexHullTrickGetMin
- | ConvexHullTrickInsert
- | SegmentTreeInitList Semigroup'
- | SegmentTreeGetRange Semigroup'
- | SegmentTreeSetPoint Semigroup'
- data Literal
- data Expr
- pattern Fun2Ty :: Type -> Type -> Type -> Type
- pattern Fun3Ty :: Type -> Type -> Type -> Type -> Type
- pattern Fun1STy :: Type -> Type
- pattern Fun2STy :: Type -> Type
- pattern Fun3STy :: Type -> Type
- pattern FunLTy :: Type -> Type
- vectorTy :: Int -> Type
- matrixTy :: Int -> Int -> Type
- pattern UnitTy :: Type
- pattern ConvexHullTrickTy :: Type
- pattern SegmentTreeTy :: Semigroup' -> Type
- pattern LitInt' :: Integer -> Expr
- pattern Lit0 :: Expr
- pattern Lit1 :: Expr
- pattern Lit2 :: Expr
- pattern LitMinus1 :: Expr
- pattern LitBool' :: Bool -> Expr
- pattern LitTrue :: Expr
- pattern LitFalse :: Expr
- pattern Builtin :: Builtin -> Expr
- pattern App2 :: Expr -> Expr -> Expr -> Expr
- pattern App3 :: Expr -> Expr -> Expr -> Expr -> Expr
- pattern App4 :: Expr -> Expr -> Expr -> Expr -> Expr -> Expr
- pattern AppBuiltin :: Builtin -> Expr -> Expr
- pattern AppBuiltin2 :: Builtin -> Expr -> Expr -> Expr
- pattern AppBuiltin3 :: Builtin -> Expr -> Expr -> Expr -> Expr
- pattern Lam2 :: VarName -> Type -> VarName -> Type -> Expr -> Expr
- pattern Lam3 :: VarName -> Type -> VarName -> Type -> VarName -> Type -> Expr -> Expr
- pattern LamId :: VarName -> Type -> Expr
- data ToplevelExpr
- type Program = ToplevelExpr
Documentation
unTypeName :: TypeName -> String Source #
Type represents the types of our core language. This is similar to the Type of GHC Core.
See also commentarycompilertype-type.
\[ \newcommand\int{\mathbf{int}} \newcommand\bool{\mathbf{bool}} \newcommand\list{\mathbf{list}} \begin{array}{rl} \tau ::= & \alpha \\ \vert & \int \\ \vert & \bool \\ \vert & \list(\tau) \\ \vert & \tau \times \tau \times \dots \times \tau \\ \vert & \tau \to \tau \vert & \mathrm{data-structure} \end{array} \]
Constructors
| VarTy TypeName | |
| IntTy | |
| BoolTy | |
| ListTy Type | |
| TupleTy [Type] | |
| FunTy Type Type | |
| DataStructureTy DataStructure |
data DataStructure Source #
Constructors
| ConvexHullTrick | |
| SegmentTree Semigroup' |
Instances
| Eq DataStructure Source # | |
Defined in Jikka.Core.Language.Expr Methods (==) :: DataStructure -> DataStructure -> Bool # (/=) :: DataStructure -> DataStructure -> Bool # | |
| Ord DataStructure Source # | |
Defined in Jikka.Core.Language.Expr Methods compare :: DataStructure -> DataStructure -> Ordering # (<) :: DataStructure -> DataStructure -> Bool # (<=) :: DataStructure -> DataStructure -> Bool # (>) :: DataStructure -> DataStructure -> Bool # (>=) :: DataStructure -> DataStructure -> Bool # max :: DataStructure -> DataStructure -> DataStructure # min :: DataStructure -> DataStructure -> DataStructure # | |
| Read DataStructure Source # | |
Defined in Jikka.Core.Language.Expr Methods readsPrec :: Int -> ReadS DataStructure # readList :: ReadS [DataStructure] # | |
| Show DataStructure Source # | |
Defined in Jikka.Core.Language.Expr Methods showsPrec :: Int -> DataStructure -> ShowS # show :: DataStructure -> String # showList :: [DataStructure] -> ShowS # | |
data Semigroup' Source #
Constructors
| SemigroupIntPlus | |
| SemigroupIntMin | |
| SemigroupIntMax |
Instances
| Eq Semigroup' Source # | |
Defined in Jikka.Core.Language.Expr | |
| Ord Semigroup' Source # | |
Defined in Jikka.Core.Language.Expr Methods compare :: Semigroup' -> Semigroup' -> Ordering # (<) :: Semigroup' -> Semigroup' -> Bool # (<=) :: Semigroup' -> Semigroup' -> Bool # (>) :: Semigroup' -> Semigroup' -> Bool # (>=) :: Semigroup' -> Semigroup' -> Bool # max :: Semigroup' -> Semigroup' -> Semigroup' # min :: Semigroup' -> Semigroup' -> Semigroup' # | |
| Read Semigroup' Source # | |
Defined in Jikka.Core.Language.Expr Methods readsPrec :: Int -> ReadS Semigroup' # readList :: ReadS [Semigroup'] # readPrec :: ReadPrec Semigroup' # readListPrec :: ReadPrec [Semigroup'] # | |
| Show Semigroup' Source # | |
Defined in Jikka.Core.Language.Expr Methods showsPrec :: Int -> Semigroup' -> ShowS # show :: Semigroup' -> String # showList :: [Semigroup'] -> ShowS # | |
Constructors
| Negate | \(: \int \to \int\) |
| Plus | \(: \int \to \int \to \int\) |
| Minus | \(: \int \to \int \to \int\) |
| Mult | \(: \int \to \int \to \int\) |
| FloorDiv | \(: \int \to \int \to \int\) |
| FloorMod | \(: \int \to \int \to \int\) |
| CeilDiv | \(: \int \to \int \to \int\) |
| CeilMod | \(: \int \to \int \to \int\) |
| Pow | \(: \int \to \int \to \int\) |
| Abs | \(: \int \to \int\) |
| Gcd | \(: \int \to \int \to \int\) |
| Lcm | \(: \int \to \int \to \int\) |
| Min2 Type | \(: \forall \alpha. \alpha \to \alpha \to \alpha\) |
| Max2 Type | \(: \forall \alpha. \alpha \to \alpha \to \alpha\) |
| Iterate Type | iterated application \((\lambda k f x. f^k(x)): \forall \alpha. \int \to (\alpha \to \alpha) \to \alpha \to \alpha\) |
| Not | \(: \bool \to \bool\) |
| And | \(: \bool \to \bool \to \bool\) |
| Or | \(: \bool \to \bool \to \bool\) |
| Implies | \(: \bool \to \bool \to \bool\) |
| If Type | \(: \forall \alpha. \bool \to \alpha \to \alpha \to \alpha\) |
| BitNot | \(: \int \to \int\) |
| BitAnd | \(: \int \to \int \to \int\) |
| BitOr | \(: \int \to \int \to \int\) |
| BitXor | \(: \int \to \int \to \int\) |
| BitLeftShift | \(: \int \to \int \to \int\) |
| BitRightShift | \(: \int \to \int \to \int\) |
| MatAp Int Int | matrix application \(: \int^{H \times W} \to \int^W \to \int^H\) |
| MatZero Int | zero matrix \(: \to \int^{n \times n}\) |
| MatOne Int | unit matrix \(: \to \int^{n \times n}\) |
| MatAdd Int Int | matrix addition \(: \int^{H \times W} \to \int^{H \times W} \to \int^{H \times W}\) |
| MatMul Int Int Int | matrix multiplication \(: \int^{H \times n} \to \int^{n \times W} \to \int^{H \times W}\) |
| MatPow Int | matrix power \(: \int^{n \times n} \to \int \to \int^{n \times n}\) |
| VecFloorMod Int | vector point-wise floor-mod \(: \int^{n} \to \int \to \int^{n}\) |
| MatFloorMod Int Int | matrix point-wise floor-mod \(: \int^{H \times W} \to \int \to \int^{H \times W}\) |
| ModNegate | \(: \int \to \int \to \int\) |
| ModPlus | \(: \int \to \int \to \int \to \int\) |
| ModMinus | \(: \int \to \int \to \int \to \int\) |
| ModMult | \(: \int \to \int \to \int \to \int\) |
| ModInv | \(: \int \to \int \to \int\) |
| ModPow | \(: \int \to \int \to \int \to \int\) |
| ModMatAp Int Int | matrix application \(: \int^{H \times W} \to \int^W \to \int \to \int^H\) |
| ModMatAdd Int Int | matrix addition \(: \int^{H \times W} \to \int^{H \times W} \to \int \to \int^{H \times W}\) |
| ModMatMul Int Int Int | matrix multiplication \(: \int^{H \times n} \to \int^{n \times W} \to \int \to \int^{H \times W}\) |
| ModMatPow Int | matrix power \(: \int^{n \times n} \to \int \to \int^{n \times n}\) |
| Cons Type | \(: \forall \alpha. \alpha \to \list(\alpha) \to \list(\alpha)\) |
| Snoc Type | \(: \forall \alpha. \list(alpha) \to \alpha \to \list(\alpha)\) |
| Foldl Type Type | \(: \forall \alpha \beta. (\beta \to \alpha \to \beta) \to \beta \to \list(\alpha) \to \beta\) |
| Scanl Type Type | \(: \forall \alpha \beta. (\beta \to \alpha \to \beta) \to \beta \to \list(\alpha) \to \list(\beta)\) |
| Build Type | \(\lambda f a n.\) repeat |
| Len Type | \(: \forall \alpha. \list(\alpha) \to \int\) |
| Map Type Type | \(: \forall \alpha \beta. (\alpha \to \beta) \to \list(\alpha) \to \list(\beta)\) |
| Filter Type | \(: \forall \alpha \beta. (\alpha \to \bool) \to \list(\alpha) \to \list(\beta)\) |
| At Type | \(: \forall \alpha. \list(\alpha) \to \int \to \alpha\) |
| SetAt Type | \(: \forall \alpha. \list(\alpha) \to \int \to \alpha \to \list(\alpha)\) |
| Elem Type | \(: \forall \alpha. \alpha \to \list(\alpha) \to \bool\) |
| Sum | \(: \list(\int) \to \int\) |
| Product | \(: \list(\int) \to \int\) |
| ModSum | \(: \list(\int) \to \int \to \int\) |
| ModProduct | \(: \list(\int) \to \int \to \int\) |
| Min1 Type | \(: \forall \alpha. \list(\alpha) \to \alpha\) |
| Max1 Type | \(: \forall \alpha. \list(\alpha) \to \alpha\) |
| ArgMin Type | \(: \forall \alpha. \list(\alpha) \to \int\) |
| ArgMax Type | \(: \forall \alpha. \list(\alpha) \to \int\) |
| All | \(: \list(\bool) \to \bool\) |
| Any | \(: \list(\bool) \to \bool\) |
| Sorted Type | \(: \forall \alpha. \list(\alpha) \to \list(\alpha)\) |
| Reversed Type | \(: \forall \alpha. \list(\alpha) \to \list(\alpha)\) |
| Range1 | \(: \int \to \list(\int)\) |
| Range2 | \(: \int \to \int \to \list(\int)\) |
| Range3 | \(: \int \to \int \to \int \to \list(\int)\) |
| Tuple [Type] | \(: \forall \alpha_0 \alpha_1 \dots \alpha _ {n - 1}. \alpha_0 \to \dots \to \alpha _ {n - 1} \to \alpha_0 \times \dots \times \alpha _ {n - 1}\) |
| Proj [Type] Int | \(: \forall \alpha_0 \alpha_1 \dots \alpha _ {n - 1}. \alpha_0 \times \dots \times \alpha _ {n - 1} \to \alpha_i\) |
| LessThan Type | \(: \forall \alpha. \alpha \to \alpha \to \bool\) |
| LessEqual Type | \(: \forall \alpha. \alpha \to \alpha \to \bool\) |
| GreaterThan Type | \(: \forall \alpha. \alpha \to \alpha \to \bool\) |
| GreaterEqual Type | \(: \forall \alpha. \alpha \to \alpha \to \bool\) |
| Equal Type | \(: \forall \alpha. \alpha \to \alpha \to \bool\) |
| NotEqual Type | \(: \forall \alpha. \alpha \to \alpha \to \bool\) |
| Fact | \(: \int \to \int\) |
| Choose | \(: \int \to \int \to \int\) |
| Permute | \(: \int \to \int \to \int\) |
| MultiChoose | \(: \int \to \int \to \int\) |
| ConvexHullTrickInit | \(: \mathrm{convex-hull-trick}\) |
| ConvexHullTrickGetMin | \(: \mathrm{convex-hull-trick} \to \int \to \int\) |
| ConvexHullTrickInsert | \(: \mathrm{convex-hull-trick} \to \int \to \int \to \mathrm{convex-hull-trick}\) |
| SegmentTreeInitList Semigroup' | \(: \forall S. \list(S) \to \mathrm{segment-tree}(S)\) |
| SegmentTreeGetRange Semigroup' | \(: \forall S. \mathrm{segment-tree}(S) \to \int \to \int \to S\) |
| SegmentTreeSetPoint Semigroup' | \(: \forall S. \mathrm{segment-tree}(S) \to \int \to S \to \mathrm{segment-tree}(S)\) |
Constructors
| LitBuiltin Builtin | |
| LitInt Integer | \(: \forall \alpha. \int\) |
| LitBool Bool | \(: \forall \alpha. \bool\) |
| LitNil Type | \(: \forall \alpha. \list(\alpha)\) |
| LitBottom Type String | \(: \bot : \forall \alpha. \alpha\). The second argument is its error message. |
Expr represents the exprs of our core language. This is similar to the Expr of GHC Core.
See also commentarycompilercore-syn-type.
\[ \begin{array}{rl} e ::= & x \\ \vert & \mathrm{literal}\ldots \\ \vert & e_0(e_1, e_2, \dots, e_n) \\ \vert & \lambda ~ x_0\colon \tau_0, x_1\colon \tau_1, \dots, x_{n-1}\colon \tau_{n-1}. ~ e \\ \vert & \mathbf{let} ~ x\colon \tau = e_1 ~ \mathbf{in} ~ e_2 \end{array} \]
Constructors
| Var VarName | |
| Lit Literal | |
| App Expr Expr | The functions are not curried. |
| Lam VarName Type Expr | The lambdas are also not curried. |
| Let VarName Type Expr Expr | This "let" is not recursive. |
pattern ConvexHullTrickTy :: Type Source #
pattern SegmentTreeTy :: Semigroup' -> Type Source #
data ToplevelExpr Source #
ToplevelExpr is the toplevel exprs. In our core, "let rec" is allowed only on the toplevel.
\[ \begin{array}{rl} \mathrm{tle} ::= & e \\ \vert & \mathbf{let}~ x: \tau = e ~\mathbf{in}~ \mathrm{tle} \\ \vert & \mathbf{let~rec}~ x(x: \tau, x: \tau, \dots, x: \tau): \tau = e ~\mathbf{in}~ \mathrm{tle} \end{array} \]
Constructors
| ResultExpr Expr | |
| ToplevelLet VarName Type Expr ToplevelExpr | |
| ToplevelLetRec VarName [(VarName, Type)] Type Expr ToplevelExpr |
Instances
| Eq ToplevelExpr Source # | |
Defined in Jikka.Core.Language.Expr | |
| Ord ToplevelExpr Source # | |
Defined in Jikka.Core.Language.Expr Methods compare :: ToplevelExpr -> ToplevelExpr -> Ordering # (<) :: ToplevelExpr -> ToplevelExpr -> Bool # (<=) :: ToplevelExpr -> ToplevelExpr -> Bool # (>) :: ToplevelExpr -> ToplevelExpr -> Bool # (>=) :: ToplevelExpr -> ToplevelExpr -> Bool # max :: ToplevelExpr -> ToplevelExpr -> ToplevelExpr # min :: ToplevelExpr -> ToplevelExpr -> ToplevelExpr # | |
| Read ToplevelExpr Source # | |
Defined in Jikka.Core.Language.Expr Methods readsPrec :: Int -> ReadS ToplevelExpr # readList :: ReadS [ToplevelExpr] # | |
| Show ToplevelExpr Source # | |
Defined in Jikka.Core.Language.Expr Methods showsPrec :: Int -> ToplevelExpr -> ShowS # show :: ToplevelExpr -> String # showList :: [ToplevelExpr] -> ShowS # | |
type Program = ToplevelExpr Source #