


% -----------------------------------------------------------------------------
\section{Direct values don't reference suspensions}
Direct values are guaranteed not to be suspensions, or to reference suspensions. Their types are like the originals except we drop the @Mk...Susp@ constructors. Don't use the word ``strict'' as strictness is a property of a function. We could rename ``Direct'' to ``Unlifted'', but the latter feels more denotational than operational. The following types obviously don't contain suspensions.

\begin{quote}
\begin{code}
data DirectInt      = MkDirectInt   Int#
data DirectFloat    = MkDirectFloat Float#
\end{code}
\end{quote}
These are still magic/meta data types that don't contain suspensions. We can't define them in regular Haskell because there is nothing stopping the user from writing :

\begin{code}
(let y = mkDirectInt 5; y' = id y in ..) :: DirectInt
\end{code}
Without strictness analysis or inlining the binding for @y'@ builds a suspension. \TODO{Could we make the kind of unlifted types? Make it a subkind of '*'. During Core to STG translation don't suspend function applications who's result is of the unlifted kind. Maybe call this subkind @\&@}

For polymorphic / container types if we want to prevent them from being instantited with suspension carrying types we need to constrain them. Use the @IsDirect@ type class. Do we really need the stupid-theta?. We want to require @a@ to be instantiated with a type in the class @IsDirect@, but never need a dictionary because there are no methods associated with that class. Maybe having the context in the instance for @DirectArray@ is enough.


\begin{quote}
\begin{code}
data IsDirect a => DirectArray a  
    = MkDirectArray (Array# a)
\end{code}
\end{quote}
Here is the definition of @IsDirect@:

\begin{quote}
\begin{code}
class    IsDirect a 
instance IsDirect DirectInt
instance IsDirect a => IsDirect (DirectArray a)
instance IsDirect (a :#> b)
\end{code}
\end{quote}
Define the type of direct functions that allow partial application but are guaranteed not to reference suspended function applications.

\begin{quote}
\begin{code}
data (:#>) a b
  = MkDirectFun (a -#> b)

  | forall c. IsDirect c
  => MkDirectApp1Of2       (c -#> a -#> b)   c 

  | forall d c. (IsDirect d, IsDirect c) 
  => MkDirectApp2Of3 (d -#> c -#> a -#> b) d c
  ...
\end{code}
\end{quote}
Now rewrite the type of @parMap#@ to require that the argument function does not reference suspensions.

\begin{quote}
\begin{code}
parMap :: (a :#> b) -#> Array a -#> Array b
\end{code}
\end{quote}

\TODO{Maybe we don't need the outer arrows to be unboxed. Perhaps just:}

\begin{quote}
\begin{code}
parMap :: (a :#> b) -> Array a -> Array b
\end{code}
\end{quote}
Wouldn't it be nice if we could pass in a regular function to @parMap@ but have it force any suspensions referenced by it before starting the data parallel computation? Next section shows how.








% --------------------------------------------------------------------------------


We we will now build explicit  boxed functions @(:->)@ based on these more primitive types. As Haskell supports partial application as well as laziness, there are several run-time ways of representing the boxed function of type, say, @a :-> b@. They are: a (wrapped) use of an arity-1 boxed function, a partial application of a function of higher arity, or a suspension of some function application. We can model these cases as follows:

\begin{code}
data (:->) a b
 =             MkFun                 (a -#> b)
 | forall c.   MkApp1Of2       (c -#> a -#> b)   c 
 | forall d c. MkApp2Of3 (d -#> c -#> a -#> b) d c
 ...
 | forall c.   MkSusp1       (c -#> (a :-> b))   c
 | forall d c. MkSusp2 (d -#> c -#> (a :-> b)) d c
 ... 
\end{code}

\TODO{These are meta/magic constructors, and must be fully applied.} \TODO{ Maybe we want a general mechanism for defining data constructors that must be fully applied. Plenty of ``little'' languages in papers use these as the default anyway. } We then want a new primop that unpacks a regular function into the explicit form. This might not be that hard to come up with, considering that heap objects have such a regular structure.

\begin{code}
   unpackFun :: (a -> b) -> (a :-> b)
\end{code}


We can then define the primitive function that performs boxed application in terms of this type. This is the Eval/Apply method from \TODO{cite}. Overload the space operator (application) to work for unboxed functions as well. 
\begin{code}
  apply :: (a :-> b) -#> a -#> b
  apply fun arg
   = case fun of
       MkFun     f       -> f       arg
       MkApp1Of2 f    xc -> f    xc arg
       MkApp2Of3 f xd xc -> f xd xc arg
       ...
       MkSusp1   f    xc -> apply (f    xc) arg
       MkSusp2   f xd xc -> apply (f xd xc) arg
       ...


% -----------------------------------------------------------------------------
\section{Laziness}
Model thunks (suspended function applications) by defining a new constructor to be a part of every lifted data type.

\begin{quote}
\begin{code}
data Int 
    =           MkInt      Int#
    | forall c. MkIntSusp  (c :-> Int) c 

data Array a
    =           MkArray     (Array# a)
    | forall c. MkArraySusp (c :-> Array a) c

\end{code}
\end{quote}
The forcing function.

\begin{quote}
\begin{code}
forceInt :: Int -#> Int#
forceInt i
 = case i of
     MkInt ii       -> ii
     MkIntSusp f x  -> apply f x

-- or with real GHC
forceInt :: Int -#> Int#
forceInt i
 = case i of
     I# i -> i

forceArray :: Array a -> Array# a
forceArray ...
\end{code}
\end{quote}
We can now rewrite our original example using unboxed functions and explicit thunks and partial applications. Doing this exposes the graph nature of the program of the program and the reference to the offending thunk.

\begin{code}
  let x        = MkIntSusp (MkFun parSum#) arr1
      g' x' y' = MkInt (add# (forceInt x')
                             (forceInt y'))
  in  MkArraySusp (MkApp1Of2 parMap# 
                             (MkApp1Of2 g' x))
                  arr1

  parSum# :: Array Int -#> Int
  parMap# :: (a :-> b) -#> Array a -#> Array b
  add#    :: Int# -#> Int# -#> Int#

\end{code}


% -----------------------------------------------------------------------------
\section{The kind of direct values}
The kind of boxed values that don't reference suspensions: @&@

\begin{code}
data DirectInt&     = MkDirectInt Int#
data DirectFloat&   = MkDirectFloat Int#

data DirectArray& (a : &) 
	= MkDirectArray& (Array# a)
	
	
\end{code}
Rewrite direct functions using this kind instead.

\begin{quote}
\begin{code}
data (:&>) a b
  = MkDirectFun& (a -#> b)

  | forall (c : &)
  => MkDirectApp1Of2&       (c -#> a -#> b)   c 

  | forall (d : &) (c : &).
  => MkDirectApp2Of3& (d -#> c -#> a -#> b) d c
  ...
\end{code}
\end{quote}
Note that @a@ and @b@ can have kind @*@ because an object of type @a (:&>) b@ never contains values of types @a@ or @b@ (they are phantom / immaterial in that type).


% -----------------------------------------------------------------------------
\section{Forceable}
Define a type class to force a value to normal form (and not just whnf). This is similar to @deepSeq@, except the argument and return types can be different. We use the @IsDirect@ type class to record the fact that the result does not contain thunks.

\begin{quote}
\begin{code}
class IsDirect b => Forceable a b  | a -> b where
    force :: a -> b

instance Forceable DirectInt DirectInt where
 force = id

instance Forceable Int DirectInt where
 force i   = MkDirectInt (forceInt i)

instance Forceable Int DirectArray where
 force arr = MkDirectArray (forceArray arr)
\end{code}
\end{quote}
To get back to the original version

\begin{quote}
\begin{code}
class Wrapable a b  | a -> b where
    wrap :: a -> b

instance Wrapable DirectInt Int where ...
instance Wrapable DirectArray Array where ...

\end{code}
\end{quote}
We also want to be able to force the closures of functions.


\begin{quote}
\begin{code}	
instance Forceable (a :-> b) (a :#> b) where
 force fun
  = case fun of
     MkFun     f       -> MkDirectFun f
     MkApp1Of2 f    xc -> MkDirectApp1Of2 f (wrap (force xc))
     MkApp2Of3 f xd xc ->
     ...
     MkSusp1   f    xc -> .. etc
     MkSusp2   f xd xc -> .. etc
     ...
\end{code}
\end{quote}
Rewrite type of @parMap@ to require a direct argument.


\begin{quote}
\begin{code}
  parMap :: Forceable a b
         => (b :&> c) -> Array a -> Array c
\end{code}
\end{quote}



