cflp 2009.1.26 → 2009.1.28

raw patch · 4 files changed

+45/−25 lines, 4 filesdep +level-monaddep +stream-monadPVP ok

version bump matches the API change (PVP)

Dependencies added: level-monad, stream-monad

API changes (from Hackage documentation)

Files

• cflp.cabal +3/−3
• src/CFLP/Control/Strategy.lhs +1/−2
• src/CFLP/Data/Narrowing.lhs +16/−16
• src/CFLP/Strategies.lhs +25/−4

@@ -1,5 +1,5 @@ Name:          cflp-Version:       2009.1.26+Version:       2009.1.28 Cabal-Version: >= 1.6 Synopsis:      Constraint Functional-Logic Programming in Haskell Description:   This package provides combinators for constraint@@ -8,7 +8,7 @@                compiling programs written in an FLP language like Curry                 or Toy. Another application of FLP is demand driven                 test-case generation.-Category:      Control+Category:      Control, Monads License:       BSD3 License-File:  LICENSE Author:        Sebastian Fischer@@ -22,7 +22,7 @@  Library   Build-Depends:    base >= 4, mtl, syb, containers,-                    control-monad-omega, logict,+                    control-monad-omega, logict, level-monad, stream-monad,                     random, MonadRandom,                     value-supply,                     HUnit

@@ -107,8 +107,7 @@  The operation ->   choose _ _ [x] = x->   choose _ _ xs  = foldr mplus mzero xs+>   choose _ _ xs = foldr1 mplus (mzero:xs)  uses `mplus` and `mzero` to construct the choice. Note that these are the automatically derived operations.

@@ -18,7 +18,10 @@ > > import CFLP.Control.Monad.Update > import CFLP.Control.Strategy->++The application of `unknown` to a constraint store and a unique+identifier represents a logic variable of an arbitrary type. + > unknown :: (Monad s, Strategy c s, MonadUpdate c s, Narrow a) >         => ID -> Nondet c s a > unknown u = freeVar u (delayed (isNarrowedID u) (`narrow`u))@@ -26,14 +29,6 @@ > isNarrowedID :: Strategy c s => ID -> Context c -> s Bool > isNarrowedID (ID us) (Context c) = isNarrowed c (supplyValue us) -The application of `unknown` to a constraint store and a unique-identifier represents a logic variable of an arbitrary type. --> class Narrow a->  where->   narrow :: (Monad s, Strategy c s, MonadUpdate c s)->          => Context c -> ID -> Nondet c s a- Logic variables of type `a` can be narrowed to head-normal form if there is an instance of the type class `Narrow`. A constraint store may be used to find the possible results which are returned in a monad@@ -41,9 +36,10 @@ non-deterministic generator using `oneOf`, but for specific types different strategies may be implemented. -> (?) :: (Monad s, Strategy c s, MonadUpdate c s)->     => Nondet c s a -> Nondet c s a -> ID -> Nondet c s a-> (x ? y) u = delayed (isNarrowedID u) (\c -> oneOf [x,y] c u)+> class Narrow a+>  where+>   narrow :: (Monad s, Strategy c s, MonadUpdate c s)+>          => Context c -> ID -> Nondet c s a  The operator `(?)` wraps the combinator `oneOf` to generate a delayed non-deterministic choice that is executed whenever it is@@ -51,11 +47,15 @@ current constraint store, the arguments of `(?)` are shared among all executions and *not* reexecuted. -> oneOf :: (Strategy c s, MonadUpdate c s)->       => [Nondet c s a] -> Context c -> ID -> Nondet c s a-> oneOf xs (Context c) (ID us)->   = Typed (choose c (supplyValue us) (map untyped xs))+> (?) :: (Monad s, Strategy c s, MonadUpdate c s)+>     => Nondet c s a -> Nondet c s a -> ID -> Nondet c s a+> (x ? y) u = delayed (isNarrowedID u) (\c -> oneOf [x,y] c u)  The operation `oneOf` takes a list of non-deterministic values and returns a non-deterministic value that yields one of the elements in the given list.++> oneOf :: (Strategy c s, MonadUpdate c s)+>       => [Nondet c s a] -> Context c -> ID -> Nondet c s a+> oneOf xs (Context c) (ID us)+>   = Typed (choose c (supplyValue us) (map untyped xs))

@@ -5,17 +5,21 @@ other modules in this package.  > {-# LANGUAGE->       FlexibleInstances+>       MultiParamTypeClasses,+>       FlexibleInstances,+>       TypeFamilies >   #-} > > module CFLP.Strategies ( >->   dfs, limDFS, iterDFS, diag, rndDFS+>   dfs, limDFS, iterDFS, bfs, diag, fair, rndDFS > >  ) where >-> import Control.Monad.Omega > import Control.Monad.Logic+> import Control.Monad.Omega+> import Control.Monad.Levels+> import Control.Monad.Stream > > import CFLP > import CFLP.Strategies.CallTimeChoice@@ -29,7 +33,7 @@  > instance Enumerable []    where enumeration = id > instance Enumerable Logic where enumeration = observeAll->+> -- using `Logic` instead of `[]` destroys sharing. Investigate. > dfs :: [CTC (Monadic (UpdateT (StoreCTC ()) Logic)) (StoreCTC ())] > dfs = [callTimeChoice monadic] @@ -55,12 +59,29 @@ >                 (StoreCTC (DepthCtx (DepthLimCtx ())))] > iterDFS = map limitedDepthFirstSearch [0..] +breadth-first search:++> instance Enumerable Levels where enumeration = breadthFirstSearch+>+> bfs :: [CTC (Monadic (UpdateT (StoreCTC ()) Levels)) (StoreCTC ())]+> bfs = [callTimeChoice monadic]+ Fair diagonalization by Luke Palmer:  > instance Enumerable Omega where enumeration = runOmega > > diag :: [CTC (Monadic (UpdateT (StoreCTC ()) Omega)) (StoreCTC ())] > diag = [callTimeChoice monadic]++Fair interleaving by Oleg Kiselyov:++Instead of using `Monadic` we provide a custom instance of+`Strategy`. We need to suspend choices in order to ensure fairness.++> instance Enumerable Stream where enumeration = runStream+>+> fair :: [CTC (Monadic (UpdateT (StoreCTC ()) Stream)) (StoreCTC ())]+> fair = [callTimeChoice monadic]  We combine randomization with depth-first search. Here, it is crucial to use the call-time choice transformer *before* the randomizer