Copyright	(C) 2017 Google Inc.
License	BSD2 (see the file LICENSE)
Maintainer	Christiaan Baaij <christiaan.baaij@gmail.com>
Safe Haskell	None
Language	Haskell2010

Clash.Core.Evaluator

Description

Call-by-need evaluator based on the evaluator described in:

Maximilian Bolingbroke, Simon Peyton Jones, "Supercompilation by evaluation", Haskell '10, Baltimore, Maryland, USA.

Synopsis

data Heap = Heap PureHeap Supply
type PureHeap = Map TmOccName Term
type Stack = [StackFrame]
data StackFrame
- = Update Id
- | Apply Id
- | Instantiate Type
- | PrimApply Text Type [Type] [Value] [Term]
- | Scrutinise Type [Alt]
data Value
- = Lambda (Bind Id Term)
- | TyLambda (Bind TyVar Term)
- | DC DataCon [Either Term Type]
- | Lit Literal
- | PrimVal Text Type [Type] [Value]
type State = (Heap, Stack, Term)
type PrimEvaluator = Bool -> BindingMap -> TyConMap -> Heap -> Stack -> Text -> Type -> [Type] -> [Value] -> Maybe State
whnf' :: PrimEvaluator -> BindingMap -> TyConMap -> Supply -> Bool -> Term -> Term
whnf :: PrimEvaluator -> BindingMap -> TyConMap -> Bool -> State -> State
isScrut :: Stack -> Bool
unwindStack :: State -> Maybe State
step :: PrimEvaluator -> BindingMap -> TyConMap -> State -> Maybe State
newLetBinding :: TyConMap -> Heap -> Term -> (Heap, Id)
newLetBindings' :: TyConMap -> Heap -> [Either Term Type] -> (Heap, [Either Term Type])
mkAbstr :: (Heap, Term) -> [Either TyVar Type] -> (Heap, Term)
force :: BindingMap -> Heap -> Stack -> Id -> Maybe State
unwind :: PrimEvaluator -> BindingMap -> TyConMap -> Heap -> Stack -> Value -> Maybe State
update :: Heap -> Stack -> Id -> Value -> State
valToTerm :: Value -> Term
toVar :: Id -> Term
toType :: TyVar -> Type
apply :: Heap -> Stack -> Value -> Id -> State
instantiate :: Heap -> Stack -> Value -> Type -> State
primop :: PrimEvaluator -> BindingMap -> TyConMap -> Heap -> Stack -> Text -> Type -> [Type] -> [Value] -> Value -> [Term] -> Maybe State
scrutinise :: Heap -> Stack -> Value -> [Alt] -> State
matchLit :: DataCon -> Literal -> Bool
substAlt :: DataCon -> Rebind [TyVar] [Id] -> [Either Term Type] -> Term -> Term
allocate :: Heap -> Stack -> Bind (Rec [LetBinding]) Term -> State
letSubst :: PureHeap -> Supply -> Id -> (Supply, (TmOccName, (TmOccName, Term)))
uniqueInHeap :: PureHeap -> Supply -> TmOccName -> (Supply, TmName)

Documentation

data Heap Source #

The heap

Constructors

Heap PureHeap Supply

Instances

Show Heap Source #
Instance details Methods showsPrec :: Int -> Heap -> ShowS # show :: Heap -> String # showList :: [Heap] -> ShowS #

type PureHeap = Map TmOccName Term Source #

type Stack = [StackFrame] Source #

The stack

data StackFrame Source #

Constructors

Update Id
Apply Id
Instantiate Type
PrimApply Text Type [Type] [Value] [Term]
Scrutinise Type [Alt]

Instances

Show StackFrame Source #
Instance details Methods showsPrec :: Int -> StackFrame -> ShowS # show :: StackFrame -> String # showList :: [StackFrame] -> ShowS #
Pretty StackFrame Source #
Instance details Methods ppr :: LFresh m => StackFrame -> m Doc Source # pprPrec :: LFresh m => Rational -> StackFrame -> m Doc Source #

data Value Source #

Constructors

Lambda (Bind Id Term)	Functions
TyLambda (Bind TyVar Term)	Type abstractions
DC DataCon [Either Term Type]	Data constructors
Lit Literal	Literals
PrimVal Text Type [Type] [Value]	Clash's number types are represented by their "fromInteger#" primitive function. So some primitives are values.

Instances

Show Value Source #
Instance details Methods showsPrec :: Int -> Value -> ShowS # show :: Value -> String # showList :: [Value] -> ShowS #

type State = (Heap, Stack, Term) Source #

State of the evaluator

type PrimEvaluator = Bool -> BindingMap -> TyConMap -> Heap -> Stack -> Text -> Type -> [Type] -> [Value] -> Maybe State Source #

Function that can evaluator primitives, i.e., perform delta-reduction

whnf' :: PrimEvaluator -> BindingMap -> TyConMap -> Supply -> Bool -> Term -> Term Source #

Evaluate to WHNF starting with an empty Heap and Stack

whnf :: PrimEvaluator -> BindingMap -> TyConMap -> Bool -> State -> State Source #

Evaluate to WHNF given an existing Heap and Stack

isScrut :: Stack -> Bool Source #

Are we in a context where special primitives must be forced.

See [Note: forcing special primitives]

unwindStack :: State -> Maybe State Source #

Completely unwind the stack to get back the complete term

step :: PrimEvaluator -> BindingMap -> TyConMap -> State -> Maybe State Source #

Small-step operational semantics.

newLetBinding :: TyConMap -> Heap -> Term -> (Heap, Id) Source #

newLetBindings' :: TyConMap -> Heap -> [Either Term Type] -> (Heap, [Either Term Type]) Source #

mkAbstr :: (Heap, Term) -> [Either TyVar Type] -> (Heap, Term) Source #

force :: BindingMap -> Heap -> Stack -> Id -> Maybe State Source #

Force the evaluation of a variable.

unwind :: PrimEvaluator -> BindingMap -> TyConMap -> Heap -> Stack -> Value -> Maybe State Source #

Unwind the stack by 1

update :: Heap -> Stack -> Id -> Value -> State Source #

Update the Heap with the evaluated term

valToTerm :: Value -> Term Source #

toVar :: Id -> Term Source #

toType :: TyVar -> Type Source #

apply :: Heap -> Stack -> Value -> Id -> State Source #

Apply a value to a function

instantiate :: Heap -> Stack -> Value -> Type -> State Source #

Instantiate a type-abstraction

primop Source #

Arguments

:: PrimEvaluator
-> BindingMap
-> TyConMap
-> Heap
-> Stack
-> Text	Name of the primitive
-> Type	Type of the primitive
-> [Type]	Applied types
-> [Value]	Applied values
-> Value	The current value
-> [Term]	The remaining terms which must be evaluated to a value
-> Maybe State

Evaluation of primitive operations

scrutinise :: Heap -> Stack -> Value -> [Alt] -> State Source #

Evaluate a case-expression

matchLit :: DataCon -> Literal -> Bool Source #

substAlt :: DataCon -> Rebind [TyVar] [Id] -> [Either Term Type] -> Term -> Term Source #

allocate :: Heap -> Stack -> Bind (Rec [LetBinding]) Term -> State Source #

Allocate let-bindings on the heap

letSubst :: PureHeap -> Supply -> Id -> (Supply, (TmOccName, (TmOccName, Term))) Source #

Create a unique name and substitution for a let-binder

uniqueInHeap :: PureHeap -> Supply -> TmOccName -> (Supply, TmName) Source #

Create a name that's unique in the heap