{- |
    Module      :  $Header$
    Description :  Definition of the intermediate language (IL)
    Copyright   :  (c) 1999 - 2003 Wolfgang Lux
                                   Martin Engelke
                       2016 - 2017 Finn Teegen
    License     :  BSD-3-clause

    Maintainer  :  bjp@informatik.uni-kiel.de
    Stability   :  experimental
    Portability :  portable

   The module 'IL' defines the intermediate language which will be
   compiled into abstract machine code. The intermediate language removes
   a lot of syntactic sugar from the Curry source language.  Top-level
   declarations are restricted to data type and function definitions. A
   newtype definition serves mainly as a hint to the backend that it must
   provide an auxiliary function for partial applications of the
   constructor (Newtype constructors must not occur in patterns
   and may be used in expressions only as partial applications.).

   Type declarations use a de-Bruijn indexing scheme (starting at 0) for
   type variables. In the type of a function, all type variables are
   numbered in the order of their occurence from left to right, i.e., a
   type '(Int -> b) -> (a,b) -> c -> (a,c)' is translated into the
   type (using integer numbers to denote the type variables)
   '(Int -> 0) -> (1,0) -> 2 -> (1,2)'.

   Pattern matching in an equation is handled via flexible and rigid
   'Case' expressions. Overlapping rules are translated with the
   help of 'Or' expressions. The intermediate language has three
   kinds of binding expressions, 'Exist' expressions introduce a
   new logical variable, 'Let' expression support a single
   non-recursive variable binding, and 'Letrec' expressions
   introduce multiple variables with recursive initializer expressions.
   The intermediate language explicitly distinguishes (local) variables
   and (global) functions in expressions.

   Note: this modified version uses haskell type 'Integer'
   instead of 'Int' for representing integer values. This provides
   an unlimited range of integer constants in Curry programs.
-}

module IL.Type
  ( -- * Data types
    Module (..), Decl (..), ConstrDecl (..), Type (..), Literal (..)
  , ConstrTerm (..), Expression (..), Eval (..), Alt (..), Binding (..)
  ) where

import Curry.Base.Ident

import Base.Expr

data Module = Module ModuleIdent [ModuleIdent] [Decl]
    deriving (Module -> Module -> Bool
(Module -> Module -> Bool)
-> (Module -> Module -> Bool) -> Eq Module
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Module -> Module -> Bool
$c/= :: Module -> Module -> Bool
== :: Module -> Module -> Bool
$c== :: Module -> Module -> Bool
Eq, Int -> Module -> ShowS
[Module] -> ShowS
Module -> String
(Int -> Module -> ShowS)
-> (Module -> String) -> ([Module] -> ShowS) -> Show Module
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Module] -> ShowS
$cshowList :: [Module] -> ShowS
show :: Module -> String
$cshow :: Module -> String
showsPrec :: Int -> Module -> ShowS
$cshowsPrec :: Int -> Module -> ShowS
Show)

data Decl
  = DataDecl         QualIdent Int [ConstrDecl]
  | ExternalDataDecl QualIdent Int
  | FunctionDecl     QualIdent [(Type, Ident)] Type Expression
  | ExternalDecl     QualIdent Type
    deriving (Decl -> Decl -> Bool
(Decl -> Decl -> Bool) -> (Decl -> Decl -> Bool) -> Eq Decl
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Decl -> Decl -> Bool
$c/= :: Decl -> Decl -> Bool
== :: Decl -> Decl -> Bool
$c== :: Decl -> Decl -> Bool
Eq, Int -> Decl -> ShowS
[Decl] -> ShowS
Decl -> String
(Int -> Decl -> ShowS)
-> (Decl -> String) -> ([Decl] -> ShowS) -> Show Decl
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Decl] -> ShowS
$cshowList :: [Decl] -> ShowS
show :: Decl -> String
$cshow :: Decl -> String
showsPrec :: Int -> Decl -> ShowS
$cshowsPrec :: Int -> Decl -> ShowS
Show)

data ConstrDecl = ConstrDecl QualIdent [Type]
    deriving (ConstrDecl -> ConstrDecl -> Bool
(ConstrDecl -> ConstrDecl -> Bool)
-> (ConstrDecl -> ConstrDecl -> Bool) -> Eq ConstrDecl
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: ConstrDecl -> ConstrDecl -> Bool
$c/= :: ConstrDecl -> ConstrDecl -> Bool
== :: ConstrDecl -> ConstrDecl -> Bool
$c== :: ConstrDecl -> ConstrDecl -> Bool
Eq, Int -> ConstrDecl -> ShowS
[ConstrDecl] -> ShowS
ConstrDecl -> String
(Int -> ConstrDecl -> ShowS)
-> (ConstrDecl -> String)
-> ([ConstrDecl] -> ShowS)
-> Show ConstrDecl
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [ConstrDecl] -> ShowS
$cshowList :: [ConstrDecl] -> ShowS
show :: ConstrDecl -> String
$cshow :: ConstrDecl -> String
showsPrec :: Int -> ConstrDecl -> ShowS
$cshowsPrec :: Int -> ConstrDecl -> ShowS
Show)

data Type
  = TypeConstructor QualIdent [Type]
  | TypeVariable    Int
  | TypeArrow       Type Type
  | TypeForall      [Int] Type
    deriving (Type -> Type -> Bool
(Type -> Type -> Bool) -> (Type -> Type -> Bool) -> Eq Type
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Type -> Type -> Bool
$c/= :: Type -> Type -> Bool
== :: Type -> Type -> Bool
$c== :: Type -> Type -> Bool
Eq, Int -> Type -> ShowS
[Type] -> ShowS
Type -> String
(Int -> Type -> ShowS)
-> (Type -> String) -> ([Type] -> ShowS) -> Show Type
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Type] -> ShowS
$cshowList :: [Type] -> ShowS
show :: Type -> String
$cshow :: Type -> String
showsPrec :: Int -> Type -> ShowS
$cshowsPrec :: Int -> Type -> ShowS
Show)

data Literal
  = Char  Char
  | Int   Integer
  | Float Double
    deriving (Literal -> Literal -> Bool
(Literal -> Literal -> Bool)
-> (Literal -> Literal -> Bool) -> Eq Literal
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Literal -> Literal -> Bool
$c/= :: Literal -> Literal -> Bool
== :: Literal -> Literal -> Bool
$c== :: Literal -> Literal -> Bool
Eq, Int -> Literal -> ShowS
[Literal] -> ShowS
Literal -> String
(Int -> Literal -> ShowS)
-> (Literal -> String) -> ([Literal] -> ShowS) -> Show Literal
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Literal] -> ShowS
$cshowList :: [Literal] -> ShowS
show :: Literal -> String
$cshow :: Literal -> String
showsPrec :: Int -> Literal -> ShowS
$cshowsPrec :: Int -> Literal -> ShowS
Show)

data ConstrTerm
    -- |literal patterns
  = LiteralPattern Type Literal
    -- |constructors
  | ConstructorPattern Type QualIdent [(Type, Ident)]
    -- |default
  | VariablePattern Type Ident
  deriving (ConstrTerm -> ConstrTerm -> Bool
(ConstrTerm -> ConstrTerm -> Bool)
-> (ConstrTerm -> ConstrTerm -> Bool) -> Eq ConstrTerm
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: ConstrTerm -> ConstrTerm -> Bool
$c/= :: ConstrTerm -> ConstrTerm -> Bool
== :: ConstrTerm -> ConstrTerm -> Bool
$c== :: ConstrTerm -> ConstrTerm -> Bool
Eq, Int -> ConstrTerm -> ShowS
[ConstrTerm] -> ShowS
ConstrTerm -> String
(Int -> ConstrTerm -> ShowS)
-> (ConstrTerm -> String)
-> ([ConstrTerm] -> ShowS)
-> Show ConstrTerm
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [ConstrTerm] -> ShowS
$cshowList :: [ConstrTerm] -> ShowS
show :: ConstrTerm -> String
$cshow :: ConstrTerm -> String
showsPrec :: Int -> ConstrTerm -> ShowS
$cshowsPrec :: Int -> ConstrTerm -> ShowS
Show)

data Expression
    -- |literal constants
  = Literal Type Literal
    -- |variables
  | Variable Type Ident
    -- |functions
  | Function Type QualIdent Int
    -- |constructors
  | Constructor Type QualIdent Int
    -- |applications
  | Apply Expression Expression
    -- |case expressions
  | Case Eval Expression [Alt]
    -- |non-deterministic or
  | Or Expression Expression
    -- |exist binding (introduction of a free variable)
  | Exist Ident Type Expression
    -- |let binding
  | Let Binding Expression
    -- |letrec binding
  | Letrec [Binding] Expression
    -- |typed expression
  | Typed Expression Type
  deriving (Expression -> Expression -> Bool
(Expression -> Expression -> Bool)
-> (Expression -> Expression -> Bool) -> Eq Expression
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Expression -> Expression -> Bool
$c/= :: Expression -> Expression -> Bool
== :: Expression -> Expression -> Bool
$c== :: Expression -> Expression -> Bool
Eq, Int -> Expression -> ShowS
[Expression] -> ShowS
Expression -> String
(Int -> Expression -> ShowS)
-> (Expression -> String)
-> ([Expression] -> ShowS)
-> Show Expression
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Expression] -> ShowS
$cshowList :: [Expression] -> ShowS
show :: Expression -> String
$cshow :: Expression -> String
showsPrec :: Int -> Expression -> ShowS
$cshowsPrec :: Int -> Expression -> ShowS
Show)

data Eval
  = Rigid
  | Flex
    deriving (Eval -> Eval -> Bool
(Eval -> Eval -> Bool) -> (Eval -> Eval -> Bool) -> Eq Eval
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Eval -> Eval -> Bool
$c/= :: Eval -> Eval -> Bool
== :: Eval -> Eval -> Bool
$c== :: Eval -> Eval -> Bool
Eq, Int -> Eval -> ShowS
[Eval] -> ShowS
Eval -> String
(Int -> Eval -> ShowS)
-> (Eval -> String) -> ([Eval] -> ShowS) -> Show Eval
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Eval] -> ShowS
$cshowList :: [Eval] -> ShowS
show :: Eval -> String
$cshow :: Eval -> String
showsPrec :: Int -> Eval -> ShowS
$cshowsPrec :: Int -> Eval -> ShowS
Show)

data Alt = Alt ConstrTerm Expression
    deriving (Alt -> Alt -> Bool
(Alt -> Alt -> Bool) -> (Alt -> Alt -> Bool) -> Eq Alt
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Alt -> Alt -> Bool
$c/= :: Alt -> Alt -> Bool
== :: Alt -> Alt -> Bool
$c== :: Alt -> Alt -> Bool
Eq, Int -> Alt -> ShowS
[Alt] -> ShowS
Alt -> String
(Int -> Alt -> ShowS)
-> (Alt -> String) -> ([Alt] -> ShowS) -> Show Alt
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Alt] -> ShowS
$cshowList :: [Alt] -> ShowS
show :: Alt -> String
$cshow :: Alt -> String
showsPrec :: Int -> Alt -> ShowS
$cshowsPrec :: Int -> Alt -> ShowS
Show)

data Binding = Binding Ident Expression
    deriving (Binding -> Binding -> Bool
(Binding -> Binding -> Bool)
-> (Binding -> Binding -> Bool) -> Eq Binding
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Binding -> Binding -> Bool
$c/= :: Binding -> Binding -> Bool
== :: Binding -> Binding -> Bool
$c== :: Binding -> Binding -> Bool
Eq, Int -> Binding -> ShowS
[Binding] -> ShowS
Binding -> String
(Int -> Binding -> ShowS)
-> (Binding -> String) -> ([Binding] -> ShowS) -> Show Binding
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Binding] -> ShowS
$cshowList :: [Binding] -> ShowS
show :: Binding -> String
$cshow :: Binding -> String
showsPrec :: Int -> Binding -> ShowS
$cshowsPrec :: Int -> Binding -> ShowS
Show)

instance Expr Expression where
  fv :: Expression -> [Ident]
fv (Variable          _ v :: Ident
v) = [Ident
v]
  fv (Apply           e1 :: Expression
e1 e2 :: Expression
e2) = Expression -> [Ident]
forall e. Expr e => e -> [Ident]
fv Expression
e1 [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ Expression -> [Ident]
forall e. Expr e => e -> [Ident]
fv Expression
e2
  fv (Case         _ e :: Expression
e alts :: [Alt]
alts) = Expression -> [Ident]
forall e. Expr e => e -> [Ident]
fv Expression
e  [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ [Alt] -> [Ident]
forall e. Expr e => e -> [Ident]
fv [Alt]
alts
  fv (Or              e1 :: Expression
e1 e2 :: Expression
e2) = Expression -> [Ident]
forall e. Expr e => e -> [Ident]
fv Expression
e1 [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ Expression -> [Ident]
forall e. Expr e => e -> [Ident]
fv Expression
e2
  fv (Exist           v :: Ident
v _ e :: Expression
e) = (Ident -> Bool) -> [Ident] -> [Ident]
forall a. (a -> Bool) -> [a] -> [a]
filter (Ident -> Ident -> Bool
forall a. Eq a => a -> a -> Bool
/= Ident
v) (Expression -> [Ident]
forall e. Expr e => e -> [Ident]
fv Expression
e)
  fv (Let (Binding v :: Ident
v e1 :: Expression
e1) e2 :: Expression
e2) = Expression -> [Ident]
forall e. Expr e => e -> [Ident]
fv Expression
e1 [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ (Ident -> Bool) -> [Ident] -> [Ident]
forall a. (a -> Bool) -> [a] -> [a]
filter (Ident -> Ident -> Bool
forall a. Eq a => a -> a -> Bool
/= Ident
v) (Expression -> [Ident]
forall e. Expr e => e -> [Ident]
fv Expression
e2)
  fv (Letrec          bds :: [Binding]
bds e :: Expression
e) = (Ident -> Bool) -> [Ident] -> [Ident]
forall a. (a -> Bool) -> [a] -> [a]
filter (Ident -> [Ident] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`notElem` [Ident]
vs) ([Expression] -> [Ident]
forall e. Expr e => e -> [Ident]
fv [Expression]
es [Ident] -> [Ident] -> [Ident]
forall a. [a] -> [a] -> [a]
++ Expression -> [Ident]
forall e. Expr e => e -> [Ident]
fv Expression
e)
    where (vs :: [Ident]
vs, es :: [Expression]
es) = [(Ident, Expression)] -> ([Ident], [Expression])
forall a b. [(a, b)] -> ([a], [b])
unzip [(Ident
v, Expression
e') | Binding v :: Ident
v e' :: Expression
e' <- [Binding]
bds]
  fv (Typed             e :: Expression
e _) = Expression -> [Ident]
forall e. Expr e => e -> [Ident]
fv Expression
e
  fv _                       = []

instance Expr Alt where
  fv :: Alt -> [Ident]
fv (Alt (ConstructorPattern _ _ vs :: [(Type, Ident)]
vs) e :: Expression
e) = (Ident -> Bool) -> [Ident] -> [Ident]
forall a. (a -> Bool) -> [a] -> [a]
filter (Ident -> [Ident] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`notElem` ((Type, Ident) -> Ident) -> [(Type, Ident)] -> [Ident]
forall a b. (a -> b) -> [a] -> [b]
map (Type, Ident) -> Ident
forall a b. (a, b) -> b
snd [(Type, Ident)]
vs) (Expression -> [Ident]
forall e. Expr e => e -> [Ident]
fv Expression
e)
  fv (Alt (VariablePattern       _ v :: Ident
v) e :: Expression
e) = (Ident -> Bool) -> [Ident] -> [Ident]
forall a. (a -> Bool) -> [a] -> [a]
filter (Ident
v Ident -> Ident -> Bool
forall a. Eq a => a -> a -> Bool
/=) (Expression -> [Ident]
forall e. Expr e => e -> [Ident]
fv Expression
e)
  fv (Alt _                           e :: Expression
e) = Expression -> [Ident]
forall e. Expr e => e -> [Ident]
fv Expression
e