8.15/3.74 NO 9.97/4.28 proof of /export/starexec/sandbox/benchmark/theBenchmark.hs 9.97/4.28 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 9.97/4.28 9.97/4.28 9.97/4.28 H-Termination with start terms of the given HASKELL could be disproven: 9.97/4.28 9.97/4.28 (0) HASKELL 9.97/4.28 (1) BR [EQUIVALENT, 0 ms] 9.97/4.28 (2) HASKELL 9.97/4.28 (3) COR [EQUIVALENT, 0 ms] 9.97/4.28 (4) HASKELL 9.97/4.28 (5) Narrow [COMPLETE, 0 ms] 9.97/4.28 (6) QDP 9.97/4.28 (7) NonTerminationLoopProof [COMPLETE, 0 ms] 9.97/4.28 (8) NO 9.97/4.28 9.97/4.28 9.97/4.28 ---------------------------------------- 9.97/4.28 9.97/4.28 (0) 9.97/4.28 Obligation: 9.97/4.28 mainModule Main 9.97/4.28 module Main where { 9.97/4.28 import qualified Prelude; 9.97/4.28 data Main.Char = Char MyInt ; 9.97/4.28 9.97/4.28 data Main.HugsException = HugsException ; 9.97/4.28 9.97/4.28 data Main.IO a = IO ((Main.IOError -> Main.IOResult) -> (a -> Main.IOResult) -> Main.IOResult) ; 9.97/4.28 9.97/4.28 data Main.IOError = IOError Main.IOErrorKind (List Main.Char) (List Main.Char) (Main.Maybe (List Main.Char)) ; 9.97/4.28 9.97/4.28 data Main.IOErrorKind = Junk ; 9.97/4.28 9.97/4.28 data Main.IOResult = Hugs_ExitWith MyInt | Hugs_Error Main.IOError | Hugs_Catch Main.IOResult (Main.HugsException -> Main.IOResult) (Main.IOError -> Main.IOResult) (Main.Obj -> Main.IOResult) | Hugs_ForkThread Main.IOResult Main.IOResult | Hugs_DeadThread | Hugs_YieldThread Main.IOResult | Hugs_Return Main.Obj | Hugs_BlockThread (Main.Obj -> Main.IOResult) ((Main.Obj -> Main.IOResult) -> Main.IOResult) ; 9.97/4.28 9.97/4.28 data List a = Cons a (List a) | Nil ; 9.97/4.28 9.97/4.28 data Main.Maybe a = Nothing | Just a ; 9.97/4.28 9.97/4.28 data MyInt = Pos Main.Nat | Neg Main.Nat ; 9.97/4.28 9.97/4.28 data Main.Nat = Succ Main.Nat | Zero ; 9.97/4.28 9.97/4.28 data Main.Obj = Obj ; 9.97/4.28 9.97/4.28 data Tup0 = Tup0 ; 9.97/4.28 9.97/4.28 blockIO :: ((a -> Main.IOResult) -> Main.IO Tup0) -> Main.IO a; 9.97/4.28 blockIO m = Main.IO (blockIOBlockIO0 m); 9.97/4.28 9.97/4.28 blockIOBlockIO0 vw f s = Main.Hugs_BlockThread (pt s fromObj) (blockIOM' vw); 9.97/4.28 9.97/4.28 blockIOM' vw k = threadToIOResult (vw (pt k toObj)); 9.97/4.28 9.97/4.28 const :: a -> b -> a; 9.97/4.28 const k vv = k; 9.97/4.28 9.97/4.28 fromObj :: Main.Obj -> a; 9.97/4.28 fromObj = fromObj; 9.97/4.28 9.97/4.28 pt :: (b -> a) -> (c -> b) -> c -> a; 9.97/4.28 pt f g x = f (g x); 9.97/4.28 9.97/4.28 threadToIOResult :: Main.IO a -> Main.IOResult; 9.97/4.28 threadToIOResult (Main.IO m) = m Main.Hugs_Error (const Main.Hugs_DeadThread); 9.97/4.28 9.97/4.28 toObj :: a -> Main.Obj; 9.97/4.28 toObj = toObj; 9.97/4.28 9.97/4.28 } 9.97/4.28 9.97/4.28 ---------------------------------------- 9.97/4.28 9.97/4.28 (1) BR (EQUIVALENT) 9.97/4.28 Replaced joker patterns by fresh variables and removed binding patterns. 9.97/4.28 ---------------------------------------- 9.97/4.28 9.97/4.28 (2) 9.97/4.28 Obligation: 9.97/4.28 mainModule Main 9.97/4.28 module Main where { 9.97/4.28 import qualified Prelude; 9.97/4.28 data Main.Char = Char MyInt ; 9.97/4.28 9.97/4.28 data Main.HugsException = HugsException ; 9.97/4.28 9.97/4.28 data Main.IO a = IO ((Main.IOError -> Main.IOResult) -> (a -> Main.IOResult) -> Main.IOResult) ; 9.97/4.28 9.97/4.28 data Main.IOError = IOError Main.IOErrorKind (List Main.Char) (List Main.Char) (Main.Maybe (List Main.Char)) ; 9.97/4.28 9.97/4.28 data Main.IOErrorKind = Junk ; 9.97/4.28 9.97/4.28 data Main.IOResult = Hugs_ExitWith MyInt | Hugs_Error Main.IOError | Hugs_Catch Main.IOResult (Main.HugsException -> Main.IOResult) (Main.IOError -> Main.IOResult) (Main.Obj -> Main.IOResult) | Hugs_ForkThread Main.IOResult Main.IOResult | Hugs_DeadThread | Hugs_YieldThread Main.IOResult | Hugs_Return Main.Obj | Hugs_BlockThread (Main.Obj -> Main.IOResult) ((Main.Obj -> Main.IOResult) -> Main.IOResult) ; 9.97/4.28 9.97/4.28 data List a = Cons a (List a) | Nil ; 9.97/4.28 9.97/4.28 data Main.Maybe a = Nothing | Just a ; 9.97/4.28 9.97/4.28 data MyInt = Pos Main.Nat | Neg Main.Nat ; 9.97/4.28 9.97/4.28 data Main.Nat = Succ Main.Nat | Zero ; 9.97/4.28 9.97/4.28 data Main.Obj = Obj ; 9.97/4.28 9.97/4.28 data Tup0 = Tup0 ; 9.97/4.28 9.97/4.28 blockIO :: ((a -> Main.IOResult) -> Main.IO Tup0) -> Main.IO a; 9.97/4.28 blockIO m = Main.IO (blockIOBlockIO0 m); 9.97/4.28 9.97/4.28 blockIOBlockIO0 vw f s = Main.Hugs_BlockThread (pt s fromObj) (blockIOM' vw); 9.97/4.28 9.97/4.28 blockIOM' vw k = threadToIOResult (vw (pt k toObj)); 9.97/4.28 9.97/4.28 const :: a -> b -> a; 9.97/4.28 const k vv = k; 9.97/4.28 9.97/4.28 fromObj :: Main.Obj -> a; 9.97/4.28 fromObj = fromObj; 9.97/4.28 9.97/4.28 pt :: (a -> b) -> (c -> a) -> c -> b; 9.97/4.28 pt f g x = f (g x); 9.97/4.28 9.97/4.28 threadToIOResult :: Main.IO a -> Main.IOResult; 9.97/4.28 threadToIOResult (Main.IO m) = m Main.Hugs_Error (const Main.Hugs_DeadThread); 9.97/4.28 9.97/4.28 toObj :: a -> Main.Obj; 9.97/4.28 toObj = toObj; 9.97/4.28 9.97/4.28 } 9.97/4.28 9.97/4.28 ---------------------------------------- 9.97/4.28 9.97/4.28 (3) COR (EQUIVALENT) 9.97/4.28 Cond Reductions: 9.97/4.28 The following Function with conditions 9.97/4.28 "undefined |Falseundefined; 9.97/4.28 " 9.97/4.28 is transformed to 9.97/4.28 "undefined = undefined1; 9.97/4.28 " 9.97/4.28 "undefined0 True = undefined; 9.97/4.28 " 9.97/4.28 "undefined1 = undefined0 False; 9.97/4.28 " 9.97/4.28 9.97/4.28 ---------------------------------------- 9.97/4.28 9.97/4.28 (4) 9.97/4.28 Obligation: 9.97/4.28 mainModule Main 9.97/4.28 module Main where { 9.97/4.28 import qualified Prelude; 9.97/4.28 data Main.Char = Char MyInt ; 9.97/4.28 9.97/4.28 data Main.HugsException = HugsException ; 9.97/4.28 9.97/4.28 data Main.IO a = IO ((Main.IOError -> Main.IOResult) -> (a -> Main.IOResult) -> Main.IOResult) ; 9.97/4.28 9.97/4.28 data Main.IOError = IOError Main.IOErrorKind (List Main.Char) (List Main.Char) (Main.Maybe (List Main.Char)) ; 9.97/4.28 9.97/4.28 data Main.IOErrorKind = Junk ; 9.97/4.28 9.97/4.28 data Main.IOResult = Hugs_ExitWith MyInt | Hugs_Error Main.IOError | Hugs_Catch Main.IOResult (Main.HugsException -> Main.IOResult) (Main.IOError -> Main.IOResult) (Main.Obj -> Main.IOResult) | Hugs_ForkThread Main.IOResult Main.IOResult | Hugs_DeadThread | Hugs_YieldThread Main.IOResult | Hugs_Return Main.Obj | Hugs_BlockThread (Main.Obj -> Main.IOResult) ((Main.Obj -> Main.IOResult) -> Main.IOResult) ; 9.97/4.28 9.97/4.28 data List a = Cons a (List a) | Nil ; 9.97/4.28 9.97/4.28 data Main.Maybe a = Nothing | Just a ; 9.97/4.28 9.97/4.28 data MyInt = Pos Main.Nat | Neg Main.Nat ; 9.97/4.28 9.97/4.28 data Main.Nat = Succ Main.Nat | Zero ; 9.97/4.28 9.97/4.28 data Main.Obj = Obj ; 9.97/4.28 9.97/4.28 data Tup0 = Tup0 ; 9.97/4.28 9.97/4.28 blockIO :: ((a -> Main.IOResult) -> Main.IO Tup0) -> Main.IO a; 9.97/4.28 blockIO m = Main.IO (blockIOBlockIO0 m); 9.97/4.28 9.97/4.28 blockIOBlockIO0 vw f s = Main.Hugs_BlockThread (pt s fromObj) (blockIOM' vw); 9.97/4.28 9.97/4.28 blockIOM' vw k = threadToIOResult (vw (pt k toObj)); 9.97/4.28 9.97/4.28 const :: b -> a -> b; 9.97/4.28 const k vv = k; 9.97/4.28 9.97/4.28 fromObj :: Main.Obj -> a; 9.97/4.28 fromObj = fromObj; 9.97/4.28 9.97/4.28 pt :: (b -> a) -> (c -> b) -> c -> a; 9.97/4.28 pt f g x = f (g x); 9.97/4.28 9.97/4.28 threadToIOResult :: Main.IO a -> Main.IOResult; 9.97/4.28 threadToIOResult (Main.IO m) = m Main.Hugs_Error (const Main.Hugs_DeadThread); 9.97/4.28 9.97/4.28 toObj :: a -> Main.Obj; 9.97/4.28 toObj = toObj; 9.97/4.28 9.97/4.28 } 9.97/4.28 9.97/4.28 ---------------------------------------- 9.97/4.28 9.97/4.28 (5) Narrow (COMPLETE) 9.97/4.28 Haskell To QDPs 9.97/4.28 9.97/4.28 digraph dp_graph { 9.97/4.28 node [outthreshold=100, inthreshold=100];1[label="blockIO",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3]; 9.97/4.28 3[label="blockIO vz3",fontsize=16,color="black",shape="triangle"];3 -> 4[label="",style="solid", color="black", weight=3]; 9.97/4.28 4[label="IO (blockIOBlockIO0 vz3)",fontsize=16,color="green",shape="box"];4 -> 5[label="",style="dashed", color="green", weight=3]; 9.97/4.28 5[label="blockIOBlockIO0 vz3",fontsize=16,color="grey",shape="box"];5 -> 6[label="",style="dashed", color="grey", weight=3]; 9.97/4.28 6[label="blockIOBlockIO0 vz3 vz4",fontsize=16,color="grey",shape="box"];6 -> 7[label="",style="dashed", color="grey", weight=3]; 9.97/4.28 7[label="blockIOBlockIO0 vz3 vz4 vz5",fontsize=16,color="black",shape="triangle"];7 -> 8[label="",style="solid", color="black", weight=3]; 9.97/4.28 8[label="Hugs_BlockThread (pt vz5 fromObj) (blockIOM' vz3)",fontsize=16,color="green",shape="box"];8 -> 9[label="",style="dashed", color="green", weight=3]; 9.97/4.28 8 -> 10[label="",style="dashed", color="green", weight=3]; 9.97/4.28 9[label="pt vz5 fromObj",fontsize=16,color="grey",shape="box"];9 -> 11[label="",style="dashed", color="grey", weight=3]; 9.97/4.28 10[label="blockIOM' vz3",fontsize=16,color="grey",shape="box"];10 -> 12[label="",style="dashed", color="grey", weight=3]; 9.97/4.28 11[label="pt vz5 fromObj vz6",fontsize=16,color="black",shape="triangle"];11 -> 13[label="",style="solid", color="black", weight=3]; 9.97/4.28 12[label="blockIOM' vz3 vz7",fontsize=16,color="black",shape="triangle"];12 -> 14[label="",style="solid", color="black", weight=3]; 9.97/4.28 13[label="vz5 (fromObj vz6)",fontsize=16,color="green",shape="box"];13 -> 15[label="",style="dashed", color="green", weight=3]; 9.97/4.28 14 -> 16[label="",style="dashed", color="red", weight=0]; 9.97/4.28 14[label="threadToIOResult (vz3 (pt vz7 toObj))",fontsize=16,color="magenta"];14 -> 17[label="",style="dashed", color="magenta", weight=3]; 9.97/4.28 15[label="fromObj vz6",fontsize=16,color="black",shape="triangle"];15 -> 18[label="",style="solid", color="black", weight=3]; 9.97/4.28 17[label="vz3 (pt vz7 toObj)",fontsize=16,color="green",shape="box"];17 -> 21[label="",style="dashed", color="green", weight=3]; 9.97/4.28 16[label="threadToIOResult vz8",fontsize=16,color="burlywood",shape="triangle"];33[label="vz8/IO vz80",fontsize=10,color="white",style="solid",shape="box"];16 -> 33[label="",style="solid", color="burlywood", weight=9]; 9.97/4.28 33 -> 20[label="",style="solid", color="burlywood", weight=3]; 9.97/4.28 18 -> 15[label="",style="dashed", color="red", weight=0]; 9.97/4.28 18[label="fromObj vz6",fontsize=16,color="magenta"];21[label="pt vz7 toObj",fontsize=16,color="grey",shape="box"];21 -> 24[label="",style="dashed", color="grey", weight=3]; 9.97/4.28 20[label="threadToIOResult (IO vz80)",fontsize=16,color="black",shape="box"];20 -> 23[label="",style="solid", color="black", weight=3]; 9.97/4.28 24 -> 22[label="",style="dashed", color="red", weight=0]; 9.97/4.28 24[label="pt vz7 toObj vz10",fontsize=16,color="magenta"];24 -> 28[label="",style="dashed", color="magenta", weight=3]; 9.97/4.28 23[label="vz80 Hugs_Error (const Hugs_DeadThread)",fontsize=16,color="green",shape="box"];23 -> 26[label="",style="dashed", color="green", weight=3]; 9.97/4.28 23 -> 27[label="",style="dashed", color="green", weight=3]; 9.97/4.28 28[label="vz10",fontsize=16,color="green",shape="box"];22[label="pt vz7 toObj vz9",fontsize=16,color="black",shape="triangle"];22 -> 25[label="",style="solid", color="black", weight=3]; 9.97/4.28 26[label="Hugs_Error",fontsize=16,color="green",shape="box"];27[label="const Hugs_DeadThread",fontsize=16,color="grey",shape="box"];27 -> 30[label="",style="dashed", color="grey", weight=3]; 9.97/4.28 25[label="vz7 (toObj vz9)",fontsize=16,color="green",shape="box"];25 -> 29[label="",style="dashed", color="green", weight=3]; 9.97/4.28 30[label="const Hugs_DeadThread vz11",fontsize=16,color="black",shape="triangle"];30 -> 32[label="",style="solid", color="black", weight=3]; 9.97/4.28 29[label="toObj vz9",fontsize=16,color="black",shape="triangle"];29 -> 31[label="",style="solid", color="black", weight=3]; 9.97/4.28 32[label="Hugs_DeadThread",fontsize=16,color="green",shape="box"];31 -> 29[label="",style="dashed", color="red", weight=0]; 9.97/4.28 31[label="toObj vz9",fontsize=16,color="magenta"];} 9.97/4.28 9.97/4.28 ---------------------------------------- 9.97/4.28 9.97/4.28 (6) 9.97/4.28 Obligation: 9.97/4.28 Q DP problem: 9.97/4.28 The TRS P consists of the following rules: 9.97/4.28 9.97/4.28 new_fromObj(vz6, h, []) -> new_fromObj(vz6, h, []) 9.97/4.28 9.97/4.28 R is empty. 9.97/4.28 Q is empty. 9.97/4.28 We have to consider all (P,Q,R)-chains. 9.97/4.28 ---------------------------------------- 9.97/4.28 9.97/4.28 (7) NonTerminationLoopProof (COMPLETE) 9.97/4.28 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 9.97/4.28 Found a loop by semiunifying a rule from P directly. 9.97/4.28 9.97/4.28 s = new_fromObj(vz6, h, []) evaluates to t =new_fromObj(vz6, h, []) 9.97/4.28 9.97/4.28 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 9.97/4.28 * Matcher: [ ] 9.97/4.28 * Semiunifier: [ ] 9.97/4.28 9.97/4.28 -------------------------------------------------------------------------------- 9.97/4.28 Rewriting sequence 9.97/4.28 9.97/4.28 The DP semiunifies directly so there is only one rewrite step from new_fromObj(vz6, h, []) to new_fromObj(vz6, h, []). 9.97/4.28 9.97/4.28 9.97/4.28 9.97/4.28 9.97/4.28 ---------------------------------------- 9.97/4.28 9.97/4.28 (8) 9.97/4.28 NO 9.97/4.32 EOF