{- |
Module      : Language.Egison.Type.Types
Licence     : MIT

This module defines the type system for Egison.
-}

{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE DeriveAnyClass #-}

module Language.Egison.Type.Types
  ( Type(..)
  , TypeScheme(..)
  , TyVar(..)
  , TensorShape(..)
  , ShapeDimType(..)
  , Constraint(..)
  , ClassInfo(..)
  , InstanceInfo(..)
  , freshTyVar
  , freeTyVars
  , isTensorType
  , isScalarType
  , typeToName
  , typeConstructorName
  , sanitizeMethodName
  , typeExprToType
  , normalizeInductiveTypes
  , capitalizeFirst
  , lowerFirst
  ) where

import           Data.Char        (toLower, toUpper)
import           Data.Hashable    (Hashable)
import           Data.Set         (Set)
import qualified Data.Set         as Set
import           GHC.Generics     (Generic)

import           Language.Egison.AST        (TypeExpr(..))
import           Language.Egison.Type.Index ()

-- | Type variable
newtype TyVar = TyVar String
  deriving (TyVar -> TyVar -> Bool
(TyVar -> TyVar -> Bool) -> (TyVar -> TyVar -> Bool) -> Eq TyVar
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: TyVar -> TyVar -> Bool
== :: TyVar -> TyVar -> Bool
$c/= :: TyVar -> TyVar -> Bool
/= :: TyVar -> TyVar -> Bool
Eq, Eq TyVar
Eq TyVar =>
(TyVar -> TyVar -> Ordering)
-> (TyVar -> TyVar -> Bool)
-> (TyVar -> TyVar -> Bool)
-> (TyVar -> TyVar -> Bool)
-> (TyVar -> TyVar -> Bool)
-> (TyVar -> TyVar -> TyVar)
-> (TyVar -> TyVar -> TyVar)
-> Ord TyVar
TyVar -> TyVar -> Bool
TyVar -> TyVar -> Ordering
TyVar -> TyVar -> TyVar
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
$ccompare :: TyVar -> TyVar -> Ordering
compare :: TyVar -> TyVar -> Ordering
$c< :: TyVar -> TyVar -> Bool
< :: TyVar -> TyVar -> Bool
$c<= :: TyVar -> TyVar -> Bool
<= :: TyVar -> TyVar -> Bool
$c> :: TyVar -> TyVar -> Bool
> :: TyVar -> TyVar -> Bool
$c>= :: TyVar -> TyVar -> Bool
>= :: TyVar -> TyVar -> Bool
$cmax :: TyVar -> TyVar -> TyVar
max :: TyVar -> TyVar -> TyVar
$cmin :: TyVar -> TyVar -> TyVar
min :: TyVar -> TyVar -> TyVar
Ord, Int -> TyVar -> String -> String
[TyVar] -> String -> String
TyVar -> String
(Int -> TyVar -> String -> String)
-> (TyVar -> String) -> ([TyVar] -> String -> String) -> Show TyVar
forall a.
(Int -> a -> String -> String)
-> (a -> String) -> ([a] -> String -> String) -> Show a
$cshowsPrec :: Int -> TyVar -> String -> String
showsPrec :: Int -> TyVar -> String -> String
$cshow :: TyVar -> String
show :: TyVar -> String
$cshowList :: [TyVar] -> String -> String
showList :: [TyVar] -> String -> String
Show, (forall x. TyVar -> Rep TyVar x)
-> (forall x. Rep TyVar x -> TyVar) -> Generic TyVar
forall x. Rep TyVar x -> TyVar
forall x. TyVar -> Rep TyVar x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
$cfrom :: forall x. TyVar -> Rep TyVar x
from :: forall x. TyVar -> Rep TyVar x
$cto :: forall x. Rep TyVar x -> TyVar
to :: forall x. Rep TyVar x -> TyVar
Generic, Eq TyVar
Eq TyVar =>
(Int -> TyVar -> Int) -> (TyVar -> Int) -> Hashable TyVar
Int -> TyVar -> Int
TyVar -> Int
forall a. Eq a => (Int -> a -> Int) -> (a -> Int) -> Hashable a
$chashWithSalt :: Int -> TyVar -> Int
hashWithSalt :: Int -> TyVar -> Int
$chash :: TyVar -> Int
hash :: TyVar -> Int
Hashable)

-- | Shape dimension (can be concrete or variable)
data ShapeDimType
  = DimLit Integer        -- ^ Concrete dimension, e.g., 2
  | DimVar String         -- ^ Dimension variable, e.g., n
  deriving (ShapeDimType -> ShapeDimType -> Bool
(ShapeDimType -> ShapeDimType -> Bool)
-> (ShapeDimType -> ShapeDimType -> Bool) -> Eq ShapeDimType
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: ShapeDimType -> ShapeDimType -> Bool
== :: ShapeDimType -> ShapeDimType -> Bool
$c/= :: ShapeDimType -> ShapeDimType -> Bool
/= :: ShapeDimType -> ShapeDimType -> Bool
Eq, Eq ShapeDimType
Eq ShapeDimType =>
(ShapeDimType -> ShapeDimType -> Ordering)
-> (ShapeDimType -> ShapeDimType -> Bool)
-> (ShapeDimType -> ShapeDimType -> Bool)
-> (ShapeDimType -> ShapeDimType -> Bool)
-> (ShapeDimType -> ShapeDimType -> Bool)
-> (ShapeDimType -> ShapeDimType -> ShapeDimType)
-> (ShapeDimType -> ShapeDimType -> ShapeDimType)
-> Ord ShapeDimType
ShapeDimType -> ShapeDimType -> Bool
ShapeDimType -> ShapeDimType -> Ordering
ShapeDimType -> ShapeDimType -> ShapeDimType
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
$ccompare :: ShapeDimType -> ShapeDimType -> Ordering
compare :: ShapeDimType -> ShapeDimType -> Ordering
$c< :: ShapeDimType -> ShapeDimType -> Bool
< :: ShapeDimType -> ShapeDimType -> Bool
$c<= :: ShapeDimType -> ShapeDimType -> Bool
<= :: ShapeDimType -> ShapeDimType -> Bool
$c> :: ShapeDimType -> ShapeDimType -> Bool
> :: ShapeDimType -> ShapeDimType -> Bool
$c>= :: ShapeDimType -> ShapeDimType -> Bool
>= :: ShapeDimType -> ShapeDimType -> Bool
$cmax :: ShapeDimType -> ShapeDimType -> ShapeDimType
max :: ShapeDimType -> ShapeDimType -> ShapeDimType
$cmin :: ShapeDimType -> ShapeDimType -> ShapeDimType
min :: ShapeDimType -> ShapeDimType -> ShapeDimType
Ord, Int -> ShapeDimType -> String -> String
[ShapeDimType] -> String -> String
ShapeDimType -> String
(Int -> ShapeDimType -> String -> String)
-> (ShapeDimType -> String)
-> ([ShapeDimType] -> String -> String)
-> Show ShapeDimType
forall a.
(Int -> a -> String -> String)
-> (a -> String) -> ([a] -> String -> String) -> Show a
$cshowsPrec :: Int -> ShapeDimType -> String -> String
showsPrec :: Int -> ShapeDimType -> String -> String
$cshow :: ShapeDimType -> String
show :: ShapeDimType -> String
$cshowList :: [ShapeDimType] -> String -> String
showList :: [ShapeDimType] -> String -> String
Show, (forall x. ShapeDimType -> Rep ShapeDimType x)
-> (forall x. Rep ShapeDimType x -> ShapeDimType)
-> Generic ShapeDimType
forall x. Rep ShapeDimType x -> ShapeDimType
forall x. ShapeDimType -> Rep ShapeDimType x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
$cfrom :: forall x. ShapeDimType -> Rep ShapeDimType x
from :: forall x. ShapeDimType -> Rep ShapeDimType x
$cto :: forall x. Rep ShapeDimType x -> ShapeDimType
to :: forall x. Rep ShapeDimType x -> ShapeDimType
Generic, Eq ShapeDimType
Eq ShapeDimType =>
(Int -> ShapeDimType -> Int)
-> (ShapeDimType -> Int) -> Hashable ShapeDimType
Int -> ShapeDimType -> Int
ShapeDimType -> Int
forall a. Eq a => (Int -> a -> Int) -> (a -> Int) -> Hashable a
$chashWithSalt :: Int -> ShapeDimType -> Int
hashWithSalt :: Int -> ShapeDimType -> Int
$chash :: ShapeDimType -> Int
hash :: ShapeDimType -> Int
Hashable)

-- | Tensor shape (dimension sizes)
data TensorShape
  = ShapeLit [Integer]        -- ^ Concrete shape, e.g., [2, 2]
  | ShapeVar String           -- ^ Shape variable, e.g., ns in zeroTensor
  | ShapeMixed [ShapeDimType] -- ^ Mixed shape, e.g., [n, m, 2]
  | ShapeUnknown              -- ^ To be inferred
  deriving (TensorShape -> TensorShape -> Bool
(TensorShape -> TensorShape -> Bool)
-> (TensorShape -> TensorShape -> Bool) -> Eq TensorShape
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: TensorShape -> TensorShape -> Bool
== :: TensorShape -> TensorShape -> Bool
$c/= :: TensorShape -> TensorShape -> Bool
/= :: TensorShape -> TensorShape -> Bool
Eq, Eq TensorShape
Eq TensorShape =>
(TensorShape -> TensorShape -> Ordering)
-> (TensorShape -> TensorShape -> Bool)
-> (TensorShape -> TensorShape -> Bool)
-> (TensorShape -> TensorShape -> Bool)
-> (TensorShape -> TensorShape -> Bool)
-> (TensorShape -> TensorShape -> TensorShape)
-> (TensorShape -> TensorShape -> TensorShape)
-> Ord TensorShape
TensorShape -> TensorShape -> Bool
TensorShape -> TensorShape -> Ordering
TensorShape -> TensorShape -> TensorShape
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
$ccompare :: TensorShape -> TensorShape -> Ordering
compare :: TensorShape -> TensorShape -> Ordering
$c< :: TensorShape -> TensorShape -> Bool
< :: TensorShape -> TensorShape -> Bool
$c<= :: TensorShape -> TensorShape -> Bool
<= :: TensorShape -> TensorShape -> Bool
$c> :: TensorShape -> TensorShape -> Bool
> :: TensorShape -> TensorShape -> Bool
$c>= :: TensorShape -> TensorShape -> Bool
>= :: TensorShape -> TensorShape -> Bool
$cmax :: TensorShape -> TensorShape -> TensorShape
max :: TensorShape -> TensorShape -> TensorShape
$cmin :: TensorShape -> TensorShape -> TensorShape
min :: TensorShape -> TensorShape -> TensorShape
Ord, Int -> TensorShape -> String -> String
[TensorShape] -> String -> String
TensorShape -> String
(Int -> TensorShape -> String -> String)
-> (TensorShape -> String)
-> ([TensorShape] -> String -> String)
-> Show TensorShape
forall a.
(Int -> a -> String -> String)
-> (a -> String) -> ([a] -> String -> String) -> Show a
$cshowsPrec :: Int -> TensorShape -> String -> String
showsPrec :: Int -> TensorShape -> String -> String
$cshow :: TensorShape -> String
show :: TensorShape -> String
$cshowList :: [TensorShape] -> String -> String
showList :: [TensorShape] -> String -> String
Show, (forall x. TensorShape -> Rep TensorShape x)
-> (forall x. Rep TensorShape x -> TensorShape)
-> Generic TensorShape
forall x. Rep TensorShape x -> TensorShape
forall x. TensorShape -> Rep TensorShape x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
$cfrom :: forall x. TensorShape -> Rep TensorShape x
from :: forall x. TensorShape -> Rep TensorShape x
$cto :: forall x. Rep TensorShape x -> TensorShape
to :: forall x. Rep TensorShape x -> TensorShape
Generic, Eq TensorShape
Eq TensorShape =>
(Int -> TensorShape -> Int)
-> (TensorShape -> Int) -> Hashable TensorShape
Int -> TensorShape -> Int
TensorShape -> Int
forall a. Eq a => (Int -> a -> Int) -> (a -> Int) -> Hashable a
$chashWithSalt :: Int -> TensorShape -> Int
hashWithSalt :: Int -> TensorShape -> Int
$chash :: TensorShape -> Int
hash :: TensorShape -> Int
Hashable)

-- | Egison types
data Type
  = TInt                              -- ^ Integer
  | TMathExpr                         -- ^ MathExpr (mathematical expression, unifies with Integer)
  | TPolyExpr                         -- ^ PolyExpr (polynomial expression)
  | TTermExpr                         -- ^ TermExpr (term in polynomial)
  | TSymbolExpr                       -- ^ SymbolExpr (symbolic variable)
  | TIndexExpr                        -- ^ IndexExpr (subscript/superscript index)
  | TFloat                            -- ^ Float (Double)
  | TBool                             -- ^ Bool
  | TChar                             -- ^ Char
  | TString                           -- ^ String
  | TVar TyVar                        -- ^ Type variable, e.g., a
  | TTuple [Type]                     -- ^ Tuple type, e.g., (a, b). Unit type () is TTuple []
  | TCollection Type                  -- ^ Collection type, e.g., [a]
  | TInductive String [Type]          -- ^ Inductive data type with type arguments
  | TTensor Type                      -- ^ Tensor type (only element type is kept). Vector and Matrix are aliases for Tensor
  | THash Type Type                   -- ^ Hash map type
  | TMatcher Type                     -- ^ Matcher type, e.g., Matcher a
  | TFun Type Type                    -- ^ Function type, e.g., a -> b
  | TIO Type                          -- ^ IO type (for IO actions)
  | TIORef Type                       -- ^ IORef type
  | TPort                             -- ^ Port type (file handles)
  | TAny                              -- ^ Any type (for gradual typing)
  deriving (Type -> Type -> Bool
(Type -> Type -> Bool) -> (Type -> Type -> Bool) -> Eq Type
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: Type -> Type -> Bool
== :: Type -> Type -> Bool
$c/= :: Type -> Type -> Bool
/= :: Type -> Type -> Bool
Eq, Eq Type
Eq Type =>
(Type -> Type -> Ordering)
-> (Type -> Type -> Bool)
-> (Type -> Type -> Bool)
-> (Type -> Type -> Bool)
-> (Type -> Type -> Bool)
-> (Type -> Type -> Type)
-> (Type -> Type -> Type)
-> Ord Type
Type -> Type -> Bool
Type -> Type -> Ordering
Type -> Type -> Type
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
$ccompare :: Type -> Type -> Ordering
compare :: Type -> Type -> Ordering
$c< :: Type -> Type -> Bool
< :: Type -> Type -> Bool
$c<= :: Type -> Type -> Bool
<= :: Type -> Type -> Bool
$c> :: Type -> Type -> Bool
> :: Type -> Type -> Bool
$c>= :: Type -> Type -> Bool
>= :: Type -> Type -> Bool
$cmax :: Type -> Type -> Type
max :: Type -> Type -> Type
$cmin :: Type -> Type -> Type
min :: Type -> Type -> Type
Ord, Int -> Type -> String -> String
[Type] -> String -> String
Type -> String
(Int -> Type -> String -> String)
-> (Type -> String) -> ([Type] -> String -> String) -> Show Type
forall a.
(Int -> a -> String -> String)
-> (a -> String) -> ([a] -> String -> String) -> Show a
$cshowsPrec :: Int -> Type -> String -> String
showsPrec :: Int -> Type -> String -> String
$cshow :: Type -> String
show :: Type -> String
$cshowList :: [Type] -> String -> String
showList :: [Type] -> String -> String
Show, (forall x. Type -> Rep Type x)
-> (forall x. Rep Type x -> Type) -> Generic Type
forall x. Rep Type x -> Type
forall x. Type -> Rep Type x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
$cfrom :: forall x. Type -> Rep Type x
from :: forall x. Type -> Rep Type x
$cto :: forall x. Rep Type x -> Type
to :: forall x. Rep Type x -> Type
Generic, Eq Type
Eq Type => (Int -> Type -> Int) -> (Type -> Int) -> Hashable Type
Int -> Type -> Int
Type -> Int
forall a. Eq a => (Int -> a -> Int) -> (a -> Int) -> Hashable a
$chashWithSalt :: Int -> Type -> Int
hashWithSalt :: Int -> Type -> Int
$chash :: Type -> Int
hash :: Type -> Int
Hashable)

-- | Type alias: MathExpr = Integer in Egison
-- Both names refer to the same type (TInt)
tMathExpr :: Type
tMathExpr :: Type
tMathExpr = Type
TInt

-- | Type scheme for polymorphic types (∀a. C a => Type)
-- Includes type constraints for type class support
data TypeScheme = Forall [TyVar] [Constraint] Type
  deriving (TypeScheme -> TypeScheme -> Bool
(TypeScheme -> TypeScheme -> Bool)
-> (TypeScheme -> TypeScheme -> Bool) -> Eq TypeScheme
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: TypeScheme -> TypeScheme -> Bool
== :: TypeScheme -> TypeScheme -> Bool
$c/= :: TypeScheme -> TypeScheme -> Bool
/= :: TypeScheme -> TypeScheme -> Bool
Eq, Int -> TypeScheme -> String -> String
[TypeScheme] -> String -> String
TypeScheme -> String
(Int -> TypeScheme -> String -> String)
-> (TypeScheme -> String)
-> ([TypeScheme] -> String -> String)
-> Show TypeScheme
forall a.
(Int -> a -> String -> String)
-> (a -> String) -> ([a] -> String -> String) -> Show a
$cshowsPrec :: Int -> TypeScheme -> String -> String
showsPrec :: Int -> TypeScheme -> String -> String
$cshow :: TypeScheme -> String
show :: TypeScheme -> String
$cshowList :: [TypeScheme] -> String -> String
showList :: [TypeScheme] -> String -> String
Show, (forall x. TypeScheme -> Rep TypeScheme x)
-> (forall x. Rep TypeScheme x -> TypeScheme) -> Generic TypeScheme
forall x. Rep TypeScheme x -> TypeScheme
forall x. TypeScheme -> Rep TypeScheme x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
$cfrom :: forall x. TypeScheme -> Rep TypeScheme x
from :: forall x. TypeScheme -> Rep TypeScheme x
$cto :: forall x. Rep TypeScheme x -> TypeScheme
to :: forall x. Rep TypeScheme x -> TypeScheme
Generic)

-- | Type class constraint, e.g., "Eq a"
data Constraint = Constraint
  { Constraint -> String
constraintClass :: String  -- ^ Class name, e.g., "Eq"
  , Constraint -> Type
constraintType  :: Type    -- ^ Type argument, e.g., TVar "a"
  } deriving (Constraint -> Constraint -> Bool
(Constraint -> Constraint -> Bool)
-> (Constraint -> Constraint -> Bool) -> Eq Constraint
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: Constraint -> Constraint -> Bool
== :: Constraint -> Constraint -> Bool
$c/= :: Constraint -> Constraint -> Bool
/= :: Constraint -> Constraint -> Bool
Eq, Int -> Constraint -> String -> String
[Constraint] -> String -> String
Constraint -> String
(Int -> Constraint -> String -> String)
-> (Constraint -> String)
-> ([Constraint] -> String -> String)
-> Show Constraint
forall a.
(Int -> a -> String -> String)
-> (a -> String) -> ([a] -> String -> String) -> Show a
$cshowsPrec :: Int -> Constraint -> String -> String
showsPrec :: Int -> Constraint -> String -> String
$cshow :: Constraint -> String
show :: Constraint -> String
$cshowList :: [Constraint] -> String -> String
showList :: [Constraint] -> String -> String
Show, (forall x. Constraint -> Rep Constraint x)
-> (forall x. Rep Constraint x -> Constraint) -> Generic Constraint
forall x. Rep Constraint x -> Constraint
forall x. Constraint -> Rep Constraint x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
$cfrom :: forall x. Constraint -> Rep Constraint x
from :: forall x. Constraint -> Rep Constraint x
$cto :: forall x. Rep Constraint x -> Constraint
to :: forall x. Rep Constraint x -> Constraint
Generic)

-- | Information about a type class
data ClassInfo = ClassInfo
  { ClassInfo -> [String]
classSupers  :: [String]           -- ^ Superclass names
  , ClassInfo -> TyVar
classParam   :: TyVar              -- ^ Type parameter (e.g., 'a' in "class Eq a")
  , ClassInfo -> [(String, Type)]
classMethods :: [(String, Type)]   -- ^ Method names and their types
  } deriving (ClassInfo -> ClassInfo -> Bool
(ClassInfo -> ClassInfo -> Bool)
-> (ClassInfo -> ClassInfo -> Bool) -> Eq ClassInfo
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: ClassInfo -> ClassInfo -> Bool
== :: ClassInfo -> ClassInfo -> Bool
$c/= :: ClassInfo -> ClassInfo -> Bool
/= :: ClassInfo -> ClassInfo -> Bool
Eq, Int -> ClassInfo -> String -> String
[ClassInfo] -> String -> String
ClassInfo -> String
(Int -> ClassInfo -> String -> String)
-> (ClassInfo -> String)
-> ([ClassInfo] -> String -> String)
-> Show ClassInfo
forall a.
(Int -> a -> String -> String)
-> (a -> String) -> ([a] -> String -> String) -> Show a
$cshowsPrec :: Int -> ClassInfo -> String -> String
showsPrec :: Int -> ClassInfo -> String -> String
$cshow :: ClassInfo -> String
show :: ClassInfo -> String
$cshowList :: [ClassInfo] -> String -> String
showList :: [ClassInfo] -> String -> String
Show, (forall x. ClassInfo -> Rep ClassInfo x)
-> (forall x. Rep ClassInfo x -> ClassInfo) -> Generic ClassInfo
forall x. Rep ClassInfo x -> ClassInfo
forall x. ClassInfo -> Rep ClassInfo x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
$cfrom :: forall x. ClassInfo -> Rep ClassInfo x
from :: forall x. ClassInfo -> Rep ClassInfo x
$cto :: forall x. Rep ClassInfo x -> ClassInfo
to :: forall x. Rep ClassInfo x -> ClassInfo
Generic)

-- | Information about a type class instance
data InstanceInfo = InstanceInfo
  { InstanceInfo -> [Constraint]
instContext :: [Constraint]        -- ^ Instance context (e.g., "Eq a" in "{Eq a} Eq [a]")
  , InstanceInfo -> String
instClass   :: String              -- ^ Class name
  , InstanceInfo -> Type
instType    :: Type                -- ^ Instance type
  , InstanceInfo -> [(String, ())]
instMethods :: [(String, ())]      -- ^ Method implementations (placeholder for now)
  } deriving (InstanceInfo -> InstanceInfo -> Bool
(InstanceInfo -> InstanceInfo -> Bool)
-> (InstanceInfo -> InstanceInfo -> Bool) -> Eq InstanceInfo
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: InstanceInfo -> InstanceInfo -> Bool
== :: InstanceInfo -> InstanceInfo -> Bool
$c/= :: InstanceInfo -> InstanceInfo -> Bool
/= :: InstanceInfo -> InstanceInfo -> Bool
Eq, Int -> InstanceInfo -> String -> String
[InstanceInfo] -> String -> String
InstanceInfo -> String
(Int -> InstanceInfo -> String -> String)
-> (InstanceInfo -> String)
-> ([InstanceInfo] -> String -> String)
-> Show InstanceInfo
forall a.
(Int -> a -> String -> String)
-> (a -> String) -> ([a] -> String -> String) -> Show a
$cshowsPrec :: Int -> InstanceInfo -> String -> String
showsPrec :: Int -> InstanceInfo -> String -> String
$cshow :: InstanceInfo -> String
show :: InstanceInfo -> String
$cshowList :: [InstanceInfo] -> String -> String
showList :: [InstanceInfo] -> String -> String
Show, (forall x. InstanceInfo -> Rep InstanceInfo x)
-> (forall x. Rep InstanceInfo x -> InstanceInfo)
-> Generic InstanceInfo
forall x. Rep InstanceInfo x -> InstanceInfo
forall x. InstanceInfo -> Rep InstanceInfo x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
$cfrom :: forall x. InstanceInfo -> Rep InstanceInfo x
from :: forall x. InstanceInfo -> Rep InstanceInfo x
$cto :: forall x. Rep InstanceInfo x -> InstanceInfo
to :: forall x. Rep InstanceInfo x -> InstanceInfo
Generic)

-- | Generate a fresh type variable with a given prefix
freshTyVar :: String -> Int -> TyVar
freshTyVar :: String -> Int -> TyVar
freshTyVar String
prefix Int
n = String -> TyVar
TyVar (String
prefix String -> String -> String
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
n)

-- | Get free type variables from a type
freeTyVars :: Type -> Set TyVar
freeTyVars :: Type -> Set TyVar
freeTyVars Type
TInt             = Set TyVar
forall a. Set a
Set.empty
freeTyVars Type
TMathExpr        = Set TyVar
forall a. Set a
Set.empty
freeTyVars Type
TPolyExpr        = Set TyVar
forall a. Set a
Set.empty
freeTyVars Type
TTermExpr        = Set TyVar
forall a. Set a
Set.empty
freeTyVars Type
TSymbolExpr      = Set TyVar
forall a. Set a
Set.empty
freeTyVars Type
TIndexExpr       = Set TyVar
forall a. Set a
Set.empty
freeTyVars Type
TFloat           = Set TyVar
forall a. Set a
Set.empty
freeTyVars Type
TBool            = Set TyVar
forall a. Set a
Set.empty
freeTyVars Type
TChar            = Set TyVar
forall a. Set a
Set.empty
freeTyVars Type
TString          = Set TyVar
forall a. Set a
Set.empty
freeTyVars (TVar TyVar
v)         = TyVar -> Set TyVar
forall a. a -> Set a
Set.singleton TyVar
v
freeTyVars (TTuple [Type]
ts)      = [Set TyVar] -> Set TyVar
forall (f :: * -> *) a. (Foldable f, Ord a) => f (Set a) -> Set a
Set.unions ((Type -> Set TyVar) -> [Type] -> [Set TyVar]
forall a b. (a -> b) -> [a] -> [b]
map Type -> Set TyVar
freeTyVars [Type]
ts)
freeTyVars (TCollection Type
t)  = Type -> Set TyVar
freeTyVars Type
t
freeTyVars (TInductive String
_ [Type]
ts) = [Set TyVar] -> Set TyVar
forall (f :: * -> *) a. (Foldable f, Ord a) => f (Set a) -> Set a
Set.unions ((Type -> Set TyVar) -> [Type] -> [Set TyVar]
forall a b. (a -> b) -> [a] -> [b]
map Type -> Set TyVar
freeTyVars [Type]
ts)
freeTyVars (TTensor Type
t)      = Type -> Set TyVar
freeTyVars Type
t
freeTyVars (THash Type
k Type
v)      = Type -> Set TyVar
freeTyVars Type
k Set TyVar -> Set TyVar -> Set TyVar
forall a. Ord a => Set a -> Set a -> Set a
`Set.union` Type -> Set TyVar
freeTyVars Type
v
freeTyVars (TMatcher Type
t)     = Type -> Set TyVar
freeTyVars Type
t
freeTyVars (TFun Type
t1 Type
t2)     = Type -> Set TyVar
freeTyVars Type
t1 Set TyVar -> Set TyVar -> Set TyVar
forall a. Ord a => Set a -> Set a -> Set a
`Set.union` Type -> Set TyVar
freeTyVars Type
t2
freeTyVars (TIO Type
t)          = Type -> Set TyVar
freeTyVars Type
t
freeTyVars (TIORef Type
t)       = Type -> Set TyVar
freeTyVars Type
t
freeTyVars Type
TPort            = Set TyVar
forall a. Set a
Set.empty
freeTyVars Type
TAny             = Set TyVar
forall a. Set a
Set.empty

-- | Check if a type is a tensor type
isTensorType :: Type -> Bool
isTensorType :: Type -> Bool
isTensorType (TTensor Type
_) = Bool
True
isTensorType Type
_           = Bool
False

-- | Check if a type is a scalar (non-tensor) type
isScalarType :: Type -> Bool
isScalarType :: Type -> Bool
isScalarType = Bool -> Bool
not (Bool -> Bool) -> (Type -> Bool) -> Type -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Type -> Bool
isTensorType

-- | Convert a Type to a string name for dictionary and method naming
-- This is used for generating instance dictionary names and method names
-- E.g., TInt -> "Integer", TTensor TInt -> "TensorInteger"
typeToName :: Type -> String
-- Note: TInt is normalized to "MathExpr" because Integer = MathExpr in Egison
typeToName :: Type -> String
typeToName Type
TInt = String
"MathExpr"  -- Integer = MathExpr, use MathExpr for dictionary names
typeToName Type
TMathExpr = String
"MathExpr"
typeToName Type
TFloat = String
"Float"
typeToName Type
TBool = String
"Bool"
typeToName Type
TChar = String
"Char"
typeToName Type
TString = String
"String"
typeToName (TVar (TyVar String
v)) = String
v
typeToName (TInductive String
name [Type]
_) = String
name
typeToName (TCollection Type
t) = String
"Collection" String -> String -> String
forall a. [a] -> [a] -> [a]
++ Type -> String
typeToName Type
t
typeToName (TTuple [Type]
ts) = String
"Tuple" String -> String -> String
forall a. [a] -> [a] -> [a]
++ (Type -> String) -> [Type] -> String
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap Type -> String
typeToName [Type]
ts
typeToName (TTensor Type
t) = String
"Tensor" String -> String -> String
forall a. [a] -> [a] -> [a]
++ Type -> String
typeToName Type
t
typeToName Type
_ = String
"Unknown"

-- | Get the type constructor name only, without type parameters
-- Used for generating instance dictionary names (e.g., "eqCollection" not "eqCollectiona")
typeConstructorName :: Type -> String
-- Note: TInt is normalized to "MathExpr" because Integer = MathExpr in Egison
-- and all type class instances are defined for MathExpr, not Integer
typeConstructorName :: Type -> String
typeConstructorName Type
TInt = String
"MathExpr"  -- Integer = MathExpr, use MathExpr for dictionary names
typeConstructorName Type
TMathExpr = String
"MathExpr"
typeConstructorName Type
TPolyExpr = String
"PolyExpr"
typeConstructorName Type
TTermExpr = String
"TermExpr"
typeConstructorName Type
TSymbolExpr = String
"SymbolExpr"
typeConstructorName Type
TIndexExpr = String
"IndexExpr"
typeConstructorName Type
TFloat = String
"Float"
typeConstructorName Type
TBool = String
"Bool"
typeConstructorName Type
TChar = String
"Char"
typeConstructorName Type
TString = String
"String"
typeConstructorName (TVar TyVar
_) = String
""  -- Type variables are ignored
typeConstructorName (TInductive String
name [Type]
_) = String
name  -- Type arguments are ignored
typeConstructorName (TCollection Type
_) = String
"Collection"  -- Element type is ignored
typeConstructorName (TTuple [Type]
_) = String
"Tuple"
typeConstructorName (TTensor Type
_) = String
"Tensor"
typeConstructorName (THash Type
_ Type
_) = String
"Hash"
typeConstructorName (TMatcher Type
_) = String
"Matcher"
typeConstructorName (TFun Type
_ Type
_) = String
"Fun"
typeConstructorName (TIO Type
_) = String
"IO"
typeConstructorName (TIORef Type
_) = String
"IORef"
typeConstructorName Type
TPort = String
"Port"
typeConstructorName Type
TAny = String
"Any"

-- | Sanitize method names for use in identifiers
-- Converts operator symbols to alphanumeric names
-- E.g., "==" -> "eq", "+" -> "plus"
sanitizeMethodName :: String -> String
sanitizeMethodName :: String -> String
sanitizeMethodName String
"==" = String
"eq"
sanitizeMethodName String
"/=" = String
"neq"
sanitizeMethodName String
"<"  = String
"lt"
sanitizeMethodName String
"<=" = String
"le"
sanitizeMethodName String
">"  = String
"gt"
sanitizeMethodName String
">=" = String
"ge"
sanitizeMethodName String
"+"  = String
"plus"
sanitizeMethodName String
"-"  = String
"minus"
sanitizeMethodName String
"*"  = String
"times"
sanitizeMethodName String
"/"  = String
"div"
sanitizeMethodName String
name = String
name

-- | Convert TypeExpr (from AST) to Type (internal representation)
typeExprToType :: TypeExpr -> Type
typeExprToType :: TypeExpr -> Type
typeExprToType TypeExpr
TEInt = Type
TInt
typeExprToType TypeExpr
TEMathExpr = Type
TMathExpr  -- MathExpr is a primitive type
typeExprToType TypeExpr
TEFloat = Type
TFloat
typeExprToType TypeExpr
TEBool = Type
TBool
typeExprToType TypeExpr
TEChar = Type
TChar
typeExprToType TypeExpr
TEString = Type
TString
typeExprToType (TEVar String
name) = TyVar -> Type
TVar (String -> TyVar
TyVar String
name)
typeExprToType (TETuple [TypeExpr]
ts) = [Type] -> Type
TTuple ((TypeExpr -> Type) -> [TypeExpr] -> [Type]
forall a b. (a -> b) -> [a] -> [b]
map TypeExpr -> Type
typeExprToType [TypeExpr]
ts)
typeExprToType (TEList TypeExpr
t) = Type -> Type
TCollection (TypeExpr -> Type
typeExprToType TypeExpr
t)
typeExprToType (TEApp TypeExpr
t1 [TypeExpr]
ts) = 
  case TypeExpr -> Type
typeExprToType TypeExpr
t1 of
    TVar (TyVar String
name) -> 
      -- Special case: convert inductive type names to primitive types
      case (String
name, [TypeExpr]
ts) of
        (String
"MathExpr", [])   -> Type
TMathExpr
        (String
"PolyExpr", [])   -> Type
TPolyExpr
        (String
"TermExpr", [])   -> Type
TTermExpr
        (String
"SymbolExpr", []) -> Type
TSymbolExpr
        (String
"IndexExpr", [])  -> Type
TIndexExpr
        (String, [TypeExpr])
_                  -> String -> [Type] -> Type
TInductive String
name ((TypeExpr -> Type) -> [TypeExpr] -> [Type]
forall a b. (a -> b) -> [a] -> [b]
map TypeExpr -> Type
typeExprToType [TypeExpr]
ts)
    TInductive String
name [Type]
existingTs -> String -> [Type] -> Type
TInductive String
name ([Type]
existingTs [Type] -> [Type] -> [Type]
forall a. [a] -> [a] -> [a]
++ (TypeExpr -> Type) -> [TypeExpr] -> [Type]
forall a b. (a -> b) -> [a] -> [b]
map TypeExpr -> Type
typeExprToType [TypeExpr]
ts)
    Type
baseType -> Type
baseType  -- Can't apply to non-inductive types
typeExprToType (TETensor TypeExpr
elemT) = Type -> Type
TTensor (TypeExpr -> Type
typeExprToType TypeExpr
elemT)
typeExprToType (TEVector TypeExpr
elemT) = Type -> Type
TTensor (TypeExpr -> Type
typeExprToType TypeExpr
elemT)  -- Vector is an alias for Tensor
typeExprToType (TEMatrix TypeExpr
elemT) = Type -> Type
TTensor (TypeExpr -> Type
typeExprToType TypeExpr
elemT)  -- Matrix is an alias for Tensor
typeExprToType (TEDiffForm TypeExpr
elemT) = Type -> Type
TTensor (TypeExpr -> Type
typeExprToType TypeExpr
elemT)  -- DiffForm is an alias for Tensor
typeExprToType (TEMatcher TypeExpr
t) = Type -> Type
TMatcher (TypeExpr -> Type
typeExprToType TypeExpr
t)
typeExprToType (TEFun TypeExpr
t1 TypeExpr
t2) = Type -> Type -> Type
TFun (TypeExpr -> Type
typeExprToType TypeExpr
t1) (TypeExpr -> Type
typeExprToType TypeExpr
t2)
typeExprToType (TEIO TypeExpr
t) = Type -> Type
TIO (TypeExpr -> Type
typeExprToType TypeExpr
t)
typeExprToType (TEConstrained [ConstraintExpr]
_ TypeExpr
t) = TypeExpr -> Type
typeExprToType TypeExpr
t  -- Ignore constraints
typeExprToType (TEPattern TypeExpr
t) = String -> [Type] -> Type
TInductive String
"Pattern" [TypeExpr -> Type
typeExprToType TypeExpr
t]

-- | Normalize inductive type names to primitive types if applicable
-- This is used to convert TInductive "MathExpr" [] to TMathExpr, etc.
normalizeInductiveTypes :: Type -> Type
normalizeInductiveTypes :: Type -> Type
normalizeInductiveTypes (TInductive String
name []) = case String
name of
  String
"MathExpr"   -> Type
TMathExpr
  String
"PolyExpr"   -> Type
TPolyExpr
  String
"TermExpr"   -> Type
TTermExpr
  String
"SymbolExpr" -> Type
TSymbolExpr
  String
"IndexExpr"  -> Type
TIndexExpr
  String
_            -> String -> [Type] -> Type
TInductive String
name []
-- Convert TInductive "Vector", "Matrix", and "DiffForm" to Tensor (they are aliases)
normalizeInductiveTypes (TInductive String
"Vector" [Type
t]) = Type -> Type
TTensor (Type -> Type
normalizeInductiveTypes Type
t)
normalizeInductiveTypes (TInductive String
"Matrix" [Type
t]) = Type -> Type
TTensor (Type -> Type
normalizeInductiveTypes Type
t)
normalizeInductiveTypes (TInductive String
"DiffForm" [Type
t]) = Type -> Type
TTensor (Type -> Type
normalizeInductiveTypes Type
t)
normalizeInductiveTypes (TInductive String
name [Type]
ts) = String -> [Type] -> Type
TInductive String
name ((Type -> Type) -> [Type] -> [Type]
forall a b. (a -> b) -> [a] -> [b]
map Type -> Type
normalizeInductiveTypes [Type]
ts)
normalizeInductiveTypes (TTuple [Type]
ts) = [Type] -> Type
TTuple ((Type -> Type) -> [Type] -> [Type]
forall a b. (a -> b) -> [a] -> [b]
map Type -> Type
normalizeInductiveTypes [Type]
ts)
normalizeInductiveTypes (TCollection Type
t) = Type -> Type
TCollection (Type -> Type
normalizeInductiveTypes Type
t)
normalizeInductiveTypes (THash Type
k Type
v) = Type -> Type -> Type
THash (Type -> Type
normalizeInductiveTypes Type
k) (Type -> Type
normalizeInductiveTypes Type
v)
normalizeInductiveTypes (TMatcher Type
t) = Type -> Type
TMatcher (Type -> Type
normalizeInductiveTypes Type
t)
normalizeInductiveTypes (TFun Type
arg Type
ret) = Type -> Type -> Type
TFun (Type -> Type
normalizeInductiveTypes Type
arg) (Type -> Type
normalizeInductiveTypes Type
ret)
normalizeInductiveTypes (TIO Type
t) = Type -> Type
TIO (Type -> Type
normalizeInductiveTypes Type
t)
normalizeInductiveTypes (TIORef Type
t) = Type -> Type
TIORef (Type -> Type
normalizeInductiveTypes Type
t)
normalizeInductiveTypes (TTensor Type
t) = Type -> Type
TTensor (Type -> Type
normalizeInductiveTypes Type
t)
normalizeInductiveTypes Type
t = Type
t  -- Other types remain unchanged

-- | Capitalize first character
capitalizeFirst :: String -> String
capitalizeFirst :: String -> String
capitalizeFirst []     = []
capitalizeFirst (Char
c:String
cs) = Char -> Char
toUpper Char
c Char -> String -> String
forall a. a -> [a] -> [a]
: String
cs

-- | Lowercase first character
lowerFirst :: String -> String
lowerFirst :: String -> String
lowerFirst []     = []
lowerFirst (Char
c:String
cs) = Char -> Char
toLower Char
c Char -> String -> String
forall a. a -> [a] -> [a]
: String
cs