Loop.hs

--
-- Copyright (c) 2009-2011, ERICSSON AB
-- All rights reserved.
-- 
-- Redistribution and use in source and binary forms, with or without
-- modification, are permitted provided that the following conditions are met:
-- 
--     * Redistributions of source code must retain the above copyright notice, 
--       this list of conditions and the following disclaimer.
--     * Redistributions in binary form must reproduce the above copyright
--       notice, this list of conditions and the following disclaimer in the
--       documentation and/or other materials provided with the distribution.
--     * Neither the name of the ERICSSON AB nor the names of its contributors
--       may be used to endorse or promote products derived from this software
--       without specific prior written permission.
-- 
-- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
-- AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
-- IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 
-- DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
-- FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
-- DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
-- SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-- CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
-- OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-- OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
--

{-# LANGUAGE UndecidableInstances #-}

module Feldspar.Core.Constructs.Loop
where

import Control.Monad (forM_, when)

import Language.Syntactic
import Language.Syntactic.Interpretation.Semantics
import Language.Syntactic.Constructs.Binding

import Feldspar.Range
import Feldspar.Core.Types
import Feldspar.Core.Interpretation
import Feldspar.Core.Constructs.Binding
import Feldspar.Core.Constructs.Literal

data LoopM m a
  where
    While :: (Size (m ()) ~ AnySize) => LoopM m (m Bool :-> m a :-> Full (m ()))
    For   :: (Size (m ()) ~ AnySize) => LoopM m (Length :-> (Index -> m a) :-> Full (m ()))

data Loop a
  where
    ForLoop   :: Type a => Loop (Length :-> a :-> (Index -> a -> a) :-> Full a)
    WhileLoop :: Type a => Loop (a :-> (a -> Bool) :-> (a -> a) :-> Full a)

instance WitnessCons (LoopM m)
  where
    witnessCons While = ConsWit
    witnessCons For   = ConsWit

instance WitnessCons Loop
  where
    witnessCons ForLoop   = ConsWit
    witnessCons WhileLoop = ConsWit

instance WitnessSat Loop
  where
    type SatContext Loop = TypeCtx
    witnessSat ForLoop   = SatWit
    witnessSat WhileLoop = SatWit

instance MaybeWitnessSat TypeCtx (LoopM m)
  where
    maybeWitnessSat _ _ = Nothing

instance MaybeWitnessSat TypeCtx Loop
  where
    maybeWitnessSat = maybeWitnessSatDefault

instance Monad m => Semantic (LoopM m)
  where
    semantics While = Sem "while" while
      where
        while cond body = do
                            c <- cond
                            when c (body >> while cond body)
    semantics For = Sem "for" for
      where
        for 0 _    = return ()
        for l body = forM_ [0..l-1] body

instance Semantic Loop
  where
    semantics ForLoop = Sem "forLoop" forLoop
      where
        forLoop 0 init _    = init
        forLoop l init body = foldl (flip body) init [0..l-1]
    semantics WhileLoop = Sem "whileLoop" whileLoop
      where
        whileLoop init cond body = go init
          where
            go st | cond st   = go $ body st
                  | otherwise = st

instance Monad m => ExprEq   (LoopM m) where exprEq = exprEqSem; exprHash = exprHashSem
instance Monad m => Render   (LoopM m) where renderPart = renderPartSem
instance Monad m => ToTree   (LoopM m)
instance Monad m => Eval     (LoopM m) where evaluate = evaluateSem
instance Monad m => EvalBind (LoopM m) where evalBindSym = evalBindSymDefault
instance Sharable (LoopM m)
  -- Will not be shared anyway, because 'maybeWitnessSat' returns 'Nothing'

instance ExprEq   Loop where exprEq = exprEqSem; exprHash = exprHashSem
instance Render   Loop where renderPart = renderPartSem
instance ToTree   Loop
instance Eval     Loop where evaluate = evaluateSem
instance EvalBind Loop where evalBindSym = evalBindSymDefault
instance Sharable Loop

instance (AlphaEq dom dom dom env, Monad m) =>
    AlphaEq (LoopM m) (LoopM m) dom env
  where
    alphaEqSym = alphaEqSymDefault

instance AlphaEq dom dom dom env => AlphaEq Loop Loop dom env
  where
    alphaEqSym = alphaEqSymDefault

instance SizeProp (LoopM m)
  where
    sizeProp While _ = AnySize
    sizeProp For   _ = AnySize

instance SizeProp Loop
  where
    sizeProp ForLoop   (_ :* _ :* WrapFull step :* Nil) = infoSize step
    sizeProp WhileLoop (_ :* _ :* WrapFull step :* Nil) = infoSize step



instance ( MonadType m
         , LoopM m :<: dom
         , Lambda TypeCtx :<: dom
         , WitnessCons (LoopM m)
         , MaybeWitnessSat TypeCtx dom
         , Optimize dom dom
         )
      => Optimize (LoopM m) dom
  where
    optimizeFeat for@For (len :* step :* Nil) = do
        len' <- optimizeM len
        let szI     = infoSize (getInfo len')
            ixRange = rangeByRange 0 (szI-1)
        step' <- optimizeFunction optimizeM (mkInfo ixRange) step
        case getInfo step' of
          Info{} -> constructFeat for (len' :* step' :* Nil)

    optimizeFeat a args = optimizeFeatDefault a args

    constructFeatUnOpt While args = constructFeatUnOptDefaultTyp voidTypeRep While args
    constructFeatUnOpt For   args = constructFeatUnOptDefaultTyp voidTypeRep For   args

instance ( Variable TypeCtx :<: dom
         , Lambda TypeCtx :<: dom
         , Loop :<: dom
         , Optimize dom dom
         , AlphaEq dom dom dom [(VarId, VarId)]
         )
      => Optimize Loop dom
  where
    optimizeFeat ForLoop (len :* init :* step :* Nil) = do
        len'  <- optimizeM len
        init' <- optimizeM init
        let szI     = infoSize (getInfo len')
            ixRange = Range 0 (upperBound szI-1)
        step' <- optimizeFunction
            (optimizeFunctionFix optimizeM (getInfo init'))
            (mkInfo ixRange)
            step
        constructFeat ForLoop (len' :* init' :* step' :* Nil)

    optimizeFeat WhileLoop (init :* cond :* body :* Nil) = do
        init' <- optimizeM init
        let info = getInfo init'
        body' <- optimizeFunctionFix optimizeM info body
        let info' = info { infoSize = infoSize (getInfo body') }
        cond' <- optimizeFunction optimizeM info' cond
        constructFeat WhileLoop (init' :* cond' :* body' :* Nil)

    constructFeatOpt ForLoop (len :* init :* step :* Nil)
        | Just 0 <- viewLiteral len = return init
        | Just 1 <- viewLiteral len = do
          let len' = stripDecor len -- TODO strip since betaReduce can't handle decorations
              init' = stripDecor init
              step' = stripDecor step
          optimizeM $ betaReduce typeCtx init' $ betaReduce typeCtx (appSymCtx typeCtx $ Literal 0) step'
        -- TODO add an optional unroll limit?

      -- ForLoop len init (const id) ==> init
    constructFeatOpt ForLoop (len :* init :* step :* Nil)
        | alphaEq step' (fun `asTypeOf` step') = optimizeM $ stripDecor init
      where
        step' = stripDecor step
        fun = appSymCtx typeCtx (Lambda 0) $ appSymCtx typeCtx (Lambda 1) $ appSymCtx typeCtx (Variable 1)

      -- TODO ForLoop len init (flip (const f)) ==> step (len - 1) init
      -- This optimization requires that the len > 0

    constructFeatOpt feat args = constructFeatUnOpt feat args

    constructFeatUnOpt = constructFeatUnOptDefault