packages feed

data-treify (empty) → 0.3.1

raw patch · 10 files changed

+665/−0 lines, 10 filesdep +basedep +containersdep +tysetup-changed

Dependencies added: base, containers, ty

Files

+ LICENSE view
@@ -0,0 +1,25 @@+Copyright (c) 2009 Andy Gill+All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions+are met:+1. Redistributions of source code must retain the above copyright+   notice, this list of conditions and the following disclaimer.+2. 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.+3. The names of the authors may not be used to endorse or promote products+   derived from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``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 AUTHORS 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.+
+ Makefile view
@@ -0,0 +1,1 @@+include ../conal-cabal-make.inc
+ Setup.lhs view
@@ -0,0 +1,3 @@+#!/usr/bin/env runhaskell+> import Distribution.Simple+> main = defaultMain
+ data-treify.cabal view
@@ -0,0 +1,90 @@+Name:               data-treify+Version:            0.3.1+Synopsis:           Reify a recursive data structure into an explicit graph.+Description:	    This package is a (probably temporary) fork of Andy gill's data-reify package.+		    .+		    'data-reify' provided the ability to turn recursive structures into explicit graphs. +		    Many (implicitly or explicitly) recursive data structure can be given this ability, via+		    a type class instance. This gives an alternative to using 'Ref' for observable sharing.+		    .+		    Observable sharing in general is unsafe, so we use the IO monad to bound this effect,+		    but can be used safely even with 'unsafePerformIO' if some simple conditions are met.+		    Typically this package will be used to tie the knot with DSL's that depend of+		    observable sharing, like Lava.+ 		    .+		    Providing an instance for 'MuRef' is the mechanism for allowing a structure to be +		    reified into a graph, and several examples of this are provided.+		    .+		    Version 0.2 of 'data-reify' uses 'StableName's, and is much faster.+		    Version 0.3 provided two versions of 'MuRef', the mono-typed version, for trees of a single type,+		    and the dynamic-typed version, for trees of different types.+		    .+		    &#169; 2009 Andy Gill; BSD3 license.++Category:            Language, Data, Parsing, Reflection +License:             BSD3+License-file:        LICENSE+Author:              Andy Gill+Maintainer:          Andy Gill <andygill@ku.edu>+Copyright:           (c) 2009 Andy Gill+Homepage:            http://ittc.ku.edu/~andygill/data-reify.php+Stability:	     alpha+build-type: 	     Simple+Cabal-Version:       >= 1.6++Library+  Build-Depends: base<5, containers, ty+  Hs-Source-Dirs: src+  Exposed-modules:+       Data.TReify+       Data.Reify.TGraph+       CustomTy+       Exp+  Ghc-Options:  -Wall+++-- Library+--   Build-Depends: base, containers+--   Hs-Source-Dirs: src+--   Exposed-modules:+--        Data.Reify,+--        Data.Dynamic.Reify,+--        Data.Reify.Graph+--   Ghc-Options:  -Wall+++-- Executable data-reify-test1+--   Build-Depends:  base+--   Main-Is:        Test1.hs+--   Hs-Source-Dirs: ., test+--   buildable: False++-- Executable data-reify-test2+--   Build-Depends:  base+--   Main-Is:        Test2.hs+--   Hs-Source-Dirs: ., test+--   buildable: False++-- Executable data-reify-test3+--   Build-Depends:  base+--   Main-Is:        Test3.hs+--   Hs-Source-Dirs: ., test+--   buildable: False++-- Executable data-reify-test4+--   Build-Depends:  base+--   Main-Is:        Test4.hs+--   Hs-Source-Dirs: ., test+--   buildable: False++-- Executable data-reify-test5+--   Build-Depends:  base+--   Main-Is:        Test5.hs+--   Hs-Source-Dirs: ., test+--   buildable: False++-- Executable data-reify-test6+--   Build-Depends:  base+--   Main-Is:        Test6.hs+--   Hs-Source-Dirs: ., test+--   buildable: False
+ src/CustomTy.hs view
@@ -0,0 +1,47 @@+{-# LANGUAGE GADTs #-}+{-# OPTIONS_GHC -Wall #-}+----------------------------------------------------------------------+-- |+-- Module      :  CustomTy+-- Copyright   :  (c) Conal Elliott 2009+-- License     :  GPL-3+-- +-- Maintainer  :  conal@conal.net+-- Stability   :  experimental+-- +-- Custom Ty & Typable+----------------------------------------------------------------------++module CustomTy (Ty(..),Typeable,ty, module Data.IsTy) where++import Control.Applicative (liftA2)++-- ty package+import Data.Proof.EQ+import Data.IsTy++-- | Typed type representation.  Alternative to Data.Ty in the ty package+data Ty a where+  Bool    :: Ty Bool+  Integer :: Ty Integer+  Float   :: Ty Float+  (:*:)   :: Ty a -> Ty b -> Ty (a,b)+  (:->:)  :: Ty a -> Ty b -> Ty (a -> b)++instance IsTy Ty where+  Bool     `tyEq` Bool       = Just Refl+  Integer  `tyEq` Integer    = Just Refl+  Float    `tyEq` Float      = Just Refl+  (a:*:b)  `tyEq` (a':*:b')  = liftA2 liftEq2 (tyEq a a') (tyEq b b')+  (a:->:b) `tyEq` (a':->:b') = liftA2 liftEq2 (tyEq a a') (tyEq b b')+  tyEq _     _               = Nothing+++-- | Replacement for Typeable and the ty package's ty.+class Typeable a where ty :: Ty a++instance Typeable Bool                               where ty = Bool+instance Typeable Integer                            where ty = Integer+instance Typeable Float                              where ty = Float+instance (Typeable a, Typeable b) => Typeable (a,b)  where ty = ty :*: ty+instance (Typeable a, Typeable b) => Typeable (a->b) where ty = ty :->: ty
+ src/Data/Junk.hs view
@@ -0,0 +1,76 @@++-- From TReify.hs, line 53, 06/05/2009 12:44:32 PM:++data Bind n where+  Bind :: V a -> n V a -> Bind n++-- From TReify.hs, line 45, 06/05/2009 12:48:14 PM:++-- Hm.  How to get Graph and reifyGraph not have to know about Ty and+-- tyEq?  I'd rather not build in that dependency, since Ty isn't+-- universal.  It handles some types and not others.  Is there a way to+-- fix Ty?  Perhaps an unsafeCoerce hack.  Done!  Now Ty uses TypeRef and+-- an unsafeCoerce.++-- From TReify.hs, line 84, 06/05/2009 01:40:29 PM:++mylookup' st tab =+   do tab2 <- M.lookup (hashStableName st) tab+      Prelude.lookup st tab2++-- From TReify.hs, line 62, 06/05/2009 05:22:13 PM:++-- TODO: Move the following defs to TGraph.hs++type Id = Int++data V a = V Id (Ty a)++-- data Shield2 f g = forall a. Shield2 (f a) (g a)++-- type Bind n = Shield V (n V)++data Bind n = forall a. Bind (V a) (n V a)++data Graph n a = Graph [Bind n] (V a)++-- From TReify.hs, line 23, 06/05/2009 05:25:54 PM:++-- import Data.Reify.TGraph++-- | 'MuRef' is a class that provided a way to reference into a specific type,+-- and a way to map over the deferenced internals.++-- class MuRef a where+--   type DeRef a :: * -> *++--   mapDeRef :: (Applicative m) +--            => (a -> m          u)+--            -> (a -> m (DeRef a u)++--   -- specialized for use here:+--   mapDeRef :: (a -> IO          Int )+--            -> (a -> IO (DeRef a Int))+++-- From Ty.hs, line 37, 06/07/2009 04:36:31 PM:+++tyEq :: Ty a -> Ty b -> Maybe (a :=: b)+Ty a `tyEq` Ty b | a == b    = unsafeCoerce (Just Refl)+                 | otherwise = Nothing++ty :: Typeable a => Ty a+ty = tyOf (undefined :: a)++tyOf :: Typeable a => a -> Ty a+tyOf a = Ty (typeOf a)++-- From Ty.hs, line 36, 06/07/2009 04:37:13 PM:++tyEq :: Ty a -> Ty b -> Maybe (a :=: b)+Ty a `tyEq` Ty b | a == b    = unsafeCoerce (Just Refl)+                 | otherwise = Nothing++ty :: Typeable a => Ty a+ty = tyOf (undefined :: a)
+ src/Data/Reify/Junk.hs view
@@ -0,0 +1,10 @@++-- From TGraph.hs, line 14, 06/05/2009 05:19:00 PM:++-- | Typed binding pair, parameterized by variable and node type+-- constructors. +data Bind n v where+  Bind :: v a -> n v a -> Bind n v++-- | Graph, described by bindings and a root variable+data Graph n v a = Graph [Bind n v] (v a)
+ src/Data/Reify/TGraph.hs view
@@ -0,0 +1,46 @@+{-# LANGUAGE GADTs, ExistentialQuantification, FlexibleContexts+           , UndecidableInstances+  #-}+{-# OPTIONS_GHC -Wall #-}++module Data.Reify.TGraph+  ( ShowF(..), Id, V(..), Bind(..), Graph(..)+  ) where++-- import Data.IsTy++-- | Identifiers+type Id = Int++-- | Typed variables+data V ty a = V Id (ty a)++instance Eq (V ty a) where V i _ == V j _ = i == j++-- | Typed binding pair, parameterized by variable and node type+-- constructors. +data Bind ty n = forall a. Bind (V ty a) (n (V ty) a)++class ShowF f where+  showF :: f a -> String                -- maybe Show a => ++instance ShowF (V ty) where+  -- showF (V i t) = parens $ show i ++ "::" ++ show t+  showF (V i _) = 'x' : show i++-- parens :: String -> String+-- parens = ("(" ++) . (++ ")")++instance Show (V ty a) where show = showF++instance ShowF (n (V ty)) => Show (Bind ty n) where+  show (Bind v n) = showF v ++" = "++ showF n++-- | Graph, described by bindings and a root variable+data Graph ty n a = Graph [Bind ty n] (V ty a)++-- We could generalize V out of Bind and Graph.+++instance (ShowF (n (V ty)), Show (V ty a)) => Show (Graph ty n a) where+  show (Graph netlist start) = "let " ++ show netlist ++ " in " ++ show start
+ src/Data/TReify.hs view
@@ -0,0 +1,85 @@+{-# LANGUAGE UndecidableInstances, TypeFamilies, BangPatterns, Rank2Types+           , ExistentialQuantification, PatternGuards, ScopedTypeVariables+           , MultiParamTypeClasses, GADTs+  #-}+{-# OPTIONS_GHC -Wall #-}++-- Variation on Andy's Data.Reify.  This version uses Int in place of+-- Unique and handles /typed/ nodes.++module Data.TReify (+        MuRef(..),+        module Data.Reify.TGraph,+        reifyGraph+        ) where++import Control.Concurrent.MVar+-- import Control.Monad+import Control.Applicative (Applicative)+import System.Mem.StableName (StableName, makeStableName, hashStableName)+import Data.IntMap as M++import Data.IsTy++import Data.Proof.EQ ((:=:)(..))+import Data.Reify.TGraph+++class MuRef ty h where+  type DeRef h :: (* -> *) -> * -> *  -- DeRef h v a++  mapDeRef :: forall m v. (Applicative m)+           => (forall a. ty a -> h a -> m (        v a))+           -> (forall a. ty a -> h a -> m (DeRef h v a))+++data StableBind ty h = forall a. StableBind (V ty a) (StableName (h a))+++-- | 'reifyGraph' takes a data structure that admits 'MuRef', and returns+-- a 'Graph' that contains the dereferenced nodes, with their children as+-- 'Integer' rather than recursive values.+reifyGraph :: (IsTy ty, MuRef ty h) => ty a -> h a -> IO (Graph ty (DeRef h) a)+reifyGraph tya ha = do rt1   <- newMVar M.empty+                       rt2   <- newMVar []+                       root  <- findNodes rt1 rt2 tya ha+                       binds <- readMVar rt2+                       return (Graph binds root)+++findNodes :: forall ty h a. (IsTy ty, MuRef ty h) +          => MVar (IntMap [StableBind ty h])+          -> MVar [Bind ty (DeRef h)]+          -> ty a -> h a -> IO (V ty a)+findNodes rt1 rt2 tya ha =+  do nextI <- newMVar 0+     let newIndex = modifyMVar nextI (\ n -> return (n+1,n))+         loop :: ty b -> h b -> IO (V ty b)+         loop tyb !hb = do+               st  <- makeStableName hb+               tab <- takeMVar rt1+               case mylookup tyb st tab of+                 Just var -> do putMVar rt1 tab+                                return $ var+                 Nothing -> +                   do i <- newIndex+                      let var = V i tyb+                      putMVar rt1 $+                        M.insertWith (++) (hashStableName st) [StableBind var st] tab+                      res <- mapDeRef loop tyb hb+                      tab' <- takeMVar rt2+                      putMVar rt2 $ Bind var res : tab'+                      return var+       in loop tya ha+++mylookup :: forall ty h a. IsTy ty =>+            ty a -> StableName (h a) -> IntMap [StableBind ty h] -> Maybe (V ty a)+mylookup tya sta tab =+   M.lookup (hashStableName sta) tab >>= llookup+ where+   llookup :: [StableBind ty h] -> Maybe (V ty a)+   llookup [] = Nothing+   llookup (StableBind v@(V _ tyb) stb : binds') +     | Just Refl <- tya `tyEq` tyb, sta == stb = Just v+     | otherwise                               = llookup binds'
+ src/Exp.hs view
@@ -0,0 +1,282 @@+{-# LANGUAGE GADTs, KindSignatures, TypeOperators, PatternGuards+           , ScopedTypeVariables, TypeFamilies, FlexibleInstances+           , MultiParamTypeClasses, FlexibleContexts+  #-}+{-# OPTIONS_GHC -Wall -fno-warn-missing-methods -fno-warn-missing-signatures #-}++module Exp where++import Control.Applicative (pure,(<$>),(<*>))+import qualified Data.IntMap as I+import Data.Maybe (fromMaybe) -- ,fromJust++-- package ty+import Data.Proof.EQ++-- Import one of the following but not both+import Data.Ty+-- import CustomTy++import Data.TReify++{--------------------------------------------------------------------+    Expressions+--------------------------------------------------------------------}++data Op :: * -> * where+  Add :: Num a  => Op (a -> a -> a)+  Mul :: Num a  => Op (a -> a -> a)+  Lit :: Show a => a -> Op a++instance ShowF Op where+  showF Add = "Add"+  showF Mul = "Mul"+  showF (Lit a) = show a++instance Show (Op a) where show = showF++-- Expressions, parameterized by variable type (constructor) and+-- expression type.+data E :: (* -> *) -> * -> * where+  Op   :: Op a -> E v a+  (:^) :: (Typeable a, Typeable b) =>+          E v (a -> b) -> E v a -> E v b+  Let  :: v a -> E v a -> E v b -> E v b+  Var  :: v a -> E v a++data N :: (* -> *) -> * -> * where+  ON  :: Op a -> N v a+  App :: (Typeable a, Typeable b) =>+         v (a -> b) -> v a -> N v b++instance ShowF v => ShowF (N v) where+  showF (ON o)    = unwords ["ON" ,showF o]+  showF (App a b) = unwords ["App",showF a,showF b]++instance Show (E (V Ty) a) where+  show (Op o) = show o+  show (u :^ v) = parens $ unwords [show u,show v]+  show (Let v a b) = unwords ["let",show v,"=",show a,"in",show b]+  show (Var v) = show v+++parens :: String -> String+parens = ("(" ++) . (++ ")")+++instance MuRef Ty (E v) where+  type DeRef (E v) = N+  mapDeRef _ _ (Op o)   = pure $ ON o+  mapDeRef k _ (f :^ a) = App <$> k ty f <*> k ty a+  mapDeRef _ _ Let{}    = notSupp "Let"+  mapDeRef _ _ Var{}    = notSupp "Var"++notSupp :: String -> a+notSupp meth = error $ "mapDeRef on E: "++meth++" not supported"++-- TODO: Consider splitting Let/Var off from E.  Then E wouldn't need the+-- v parameter.+-- +-- I could use N and Mu to define an E without Let & Var and then use a+-- standard MuRef instance and a standard extension to include Let & Var.+-- Wouldn't be as convenient for simplification rules, because of the+-- explicit Mu constructors.  Consider it, however, since it makes a+-- simple type distinction between the input to CSE and the output.  Oh,+-- and I could have different ways to embed Let.  For C-like languages, I+-- could restrict the lets to be on the outside (odd for conditionals,+-- though).+++nodeE :: N v a -> E v a+nodeE (ON o)    = Op o+nodeE (App u v) = Var u :^ Var v++unGraph :: Typeable a => Graph Ty N a -> E (V Ty) a+unGraph (Graph binds root) =+  foldr (\ (Bind v n) -> Let v (nodeE n)) (Var root) (reverse binds)+++-- Convert expressions to simple SSA forms+ssa :: Typeable a => E (V Ty) a -> IO (E (V Ty) a)+ssa = fmap unGraph . reifyGraph ty++++children :: N (V Ty) a -> [Id]+children (ON  _)   = []+children (App (V a _) (V b _)) = [a,b]++childrenB :: Bind Ty N -> [Id]+childrenB (Bind _ n) = children n+++-- Number of references for each node.  Important: partially apply, so+-- that the binding list can be converted just once into an efficiently+-- searchable representation.+uses :: [Bind Ty N] -> (Id -> Int)+uses = fmap (fromMaybe 0) .+       flip I.lookup .+       histogram .+       concatMap childrenB++-- histogram :: Ord k => [k] -> I.Map k Int+-- histogram = foldr (\ k -> I.insertWith (+) k 1) I.empty++histogram :: [Int] -> I.IntMap Int+histogram = foldr (\ k -> I.insertWith (+) k 1) I.empty++-- bindsF :: [Bind v] -> (Ty a -> v a -> N v a)+-- bindsF = undefined++-- Slow version+bindsF' :: [Bind Ty N] -> (V Ty a -> N (V Ty) a)+bindsF' [] _ = error "bindsF: ran out of bindings"+bindsF' (Bind (V i a) n : binds') v@(V i' a')+  | Just Refl <- a `tyEq` a', i == i' = n+  | otherwise                         = bindsF' binds' v++-- Fast version, using an IntMap.  Important: partially apply.+bindsF :: forall n a. [Bind Ty n] -> (V Ty a -> n (V Ty) a)+bindsF binds = \ (V i' a') -> extract a' (I.lookup i' m)+ where+   m :: I.IntMap (Bind Ty n)+   m = I.fromList [(i,b) | b@(Bind (V i _) _) <- binds]+   extract :: Ty a' -> Maybe (Bind Ty n) -> n (V Ty) a'+   extract _ Nothing            = error "bindsF: variable not found"+   extract a' (Just (Bind (V _ a) n))+     | Just Refl <- a `tyEq` a' = n+     | otherwise                = error "bindsF: wrong type"++unGraph2 :: Graph Ty N a -> E (V Ty) a+unGraph2 (Graph binds root) = foldr llet (var' root) (reverse binds)+ where+   -- Wrap a let if non-trivial+   llet :: Bind Ty N -> E (V Ty) b -> E (V Ty) b+   llet bind | trivial bind = id+   llet (Bind v n) = Let v (nodeE' n)+   -- How many uses of variable+   count :: Id -> Int+   count = uses binds+   -- Bindings as IntMap lookup+   psf :: V Ty a -> N (V Ty) a+   psf = bindsF binds+   -- Too trivial to bother abstracting.+   trivial :: Bind Ty N -> Bool+   trivial (Bind _ (ON _))                = True+   trivial (Bind (V i _) _) | count i < 2 = True+   trivial _                              = False+   -- Like nodeE but with inlining of trivial bindings+   nodeE' :: N (V Ty) a -> E (V Ty) a+   nodeE' (ON o)    = Op o+   nodeE' (App a b) = var' a :^ var' b+   -- Variable reference or inline+   var' :: V Ty a -> E (V Ty) a+   var' v | trivial (Bind v n) = nodeE' n+          | otherwise          = Var v+    where+      n = psf v++-- TODO: generalize unGraph2 from V.++-- | Common subexpression elimination+cse :: Typeable a => E (V Ty) a -> IO (E (V Ty) a)+cse = fmap unGraph2 . reifyGraph ty+++{--------------------------------------------------------------------+    Utilities for convenient expression building+--------------------------------------------------------------------}++op2 :: (Typeable a, Typeable b, Typeable c) =>+       Op (a -> b -> c) -> E v a -> E v b -> E v c+op2 h a b = Op h :^ a :^ b++instance Eq (E v a)++instance (Typeable a, Num a) => Num (E (V Ty) a) where+  fromInteger x = Op (Lit (fromInteger x))+  (+) = op2 Add+  (*) = op2 Mul++sqr :: Num a => a -> a+sqr x = x * x++{--------------------------------------------------------------------+    Testing+--------------------------------------------------------------------}++-- type-specialize+reify :: (MuRef Ty h, Typeable a) => h a -> IO (Graph Ty (DeRef h) a)+reify = reifyGraph ty++-- test expressions+e1 = 3 + 5 :: E (V Ty) Integer+e2 = e1 * e1+e3 = 3 + 3 :: E (V Ty) Integer+++{-+  > e1+  ((Add 3) 5)+  > reify e1+  let [x0 = App x1 x4,x4 = ON 5,x1 = App x2 x3,x3 = ON 3,x2 = ON Add] in x0+  > ssa e1+  let x2 = Add in let x3 = 3 in let x1 = (x2 x3) in let x4 = 5 in let x0 = (x1 x4) in x0+  > cse e1+  ((Add 3) 5)++  > e2+  ((Mul ((Add 3) 5)) ((Add 3) 5))+  > reify e2+  let [x0 = App x1 x3,x1 = App x2 x3,x3 = App x4 x7,x7 = ON 5,x4 = App x5 x6,x6 = ON 3,x5 = ON Add,x2 = ON Mul] in x0+  > ssa e2+  let x2 = Mul in let x5 = Add in let x6 = 3 in let x4 = (x5 x6) in let x7 = 5 in let x3 = (x4 x7) in let x1 = (x2 x3) in let x0 = (x1 x3) in x0+  > cse e2+  let x3 = ((Add 3) 5) in ((Mul x3) x3)++  > e3+  ((Add 3) 3)+  > reify e3+  let [x0 = App x1 x3,x1 = App x2 x3,x3 = ON 3,x2 = ON Add] in x0+  > +  > ssa e3+  let x2 = Add in let x3 = 3 in let x1 = (x2 x3) in let x0 = (x1 x3) in x0+  > cse e3+  ((Add 3) 3)+-}++test :: Int -> E (V Ty) Integer+test n = iterate sqr e1 !! n++{-+  > test 2+  ((Mul ((Mul ((Add 3) 5)) ((Add 3) 5))) ((Mul ((Add 3) 5)) ((Add 3) 5)))+  > reify (test 2)+  let [x0 = App x1 x3,x1 = App x2 x3,x3 = App x4 x6,x4 = App x5 x6,x6 = App x7 x10,x10 = ON 5,x7 = App x8 x9,x9 = ON 3,x8 = ON Add,x5 = ON Mul,x2 = ON Mul] in x0+  > ssa (test 2)+  let x2 = Mul in let x5 = Mul in let x8 = Add in let x9 = 3 in let x7 = (x8 x9) in let x10 = 5 in let x6 = (x7 x10) in let x4 = (x5 x6) in let x3 = (x4 x6) in let x1 = (x2 x3) in let x0 = (x1 x3) in x0+  > cse (test 2)+  let x6 = ((Add 3) 5) in let x3 = ((Mul x6) x6) in ((Mul x3) x3)++  > test 5+  ((Mul ((Mul ((Mul ((Mul ((Mul ((Add 3) 5)) ((Add 3) 5))) ((Mul ((Add 3) 5)) ((Add 3) 5)))) ((Mul ((Mul ((Add 3) 5)) ((Add 3) 5))) ((Mul ((Add 3) 5)) ((Add 3) 5))))) ((Mul ((Mul ((Mul ((Add 3) 5)) ((Add 3) 5))) ((Mul ((Add 3) 5)) ((Add 3) 5)))) ((Mul ((Mul ((Add 3) 5)) ((Add 3) 5))) ((Mul ((Add 3) 5)) ((Add 3) 5)))))) ((Mul ((Mul ((Mul ((Mul ((Add 3) 5)) ((Add 3) 5))) ((Mul ((Add 3) 5)) ((Add 3) 5)))) ((Mul ((Mul ((Add 3) 5)) ((Add 3) 5))) ((Mul ((Add 3) 5)) ((Add 3) 5))))) ((Mul ((Mul ((Mul ((Add 3) 5)) ((Add 3) 5))) ((Mul ((Add 3) 5)) ((Add 3) 5)))) ((Mul ((Mul ((Add 3) 5)) ((Add 3) 5))) ((Mul ((Add 3) 5)) ((Add 3) 5))))))+  > reify (test 5)+  let [x0 = App x1 x3,x1 = App x2 x3,x3 = App x4 x6,x4 = App x5 x6,x6 = App x7 x9,x7 = App x8 x9,x9 = App x10 x12,x10 = App x11 x12,x12 = App x13 x15,x13 = App x14 x15,x15 = App x16 x19,x19 = ON 5,x16 = App x17 x18,x18 = ON 3,x17 = ON Add,x14 = ON Mul,x11 = ON Mul,x8 = ON Mul,x5 = ON Mul,x2 = ON Mul] in x0+  > ssa (test 5)+  let x2 = Mul in let x5 = Mul in let x8 = Mul in let x11 = Mul in let x14 = Mul in let x17 = Add in let x18 = 3 in let x16 = (x17 x18) in let x19 = 5 in let x15 = (x16 x19) in let x13 = (x14 x15) in let x12 = (x13 x15) in let x10 = (x11 x12) in let x9 = (x10 x12) in let x7 = (x8 x9) in let x6 = (x7 x9) in let x4 = (x5 x6) in let x3 = (x4 x6) in let x1 = (x2 x3) in let x0 = (x1 x3) in x0+  > cse (test 5)+  let x15 = ((Add 3) 5) in let x12 = ((Mul x15) x15) in let x9 = ((Mul x12) x12) in let x6 = ((Mul x9) x9) in let x3 = ((Mul x6) x6) in ((Mul x3) x3)+-}++e4 = e1 ^ (29 :: Integer)++{-+  > e4+  ((Mul ((Mul ((Mul ((Mul ((Mul ((Add 3) 5)) ((Add 3) 5))) ((Mul ((Add 3) 5)) ((Add 3) 5)))) ((Mul ((Mul ((Add 3) 5)) ((Add 3) 5))) ((Mul ((Add 3) 5)) ((Add 3) 5))))) ((Mul ((Mul ((Mul ((Add 3) 5)) ((Add 3) 5))) ((Mul ((Add 3) 5)) ((Add 3) 5)))) ((Mul ((Mul ((Add 3) 5)) ((Add 3) 5))) ((Mul ((Add 3) 5)) ((Add 3) 5)))))) ((Mul ((Mul ((Mul ((Mul ((Add 3) 5)) ((Add 3) 5))) ((Mul ((Add 3) 5)) ((Add 3) 5)))) ((Mul ((Mul ((Add 3) 5)) ((Add 3) 5))) ((Mul ((Add 3) 5)) ((Add 3) 5))))) ((Mul ((Mul ((Mul ((Add 3) 5)) ((Add 3) 5))) ((Mul ((Add 3) 5)) ((Add 3) 5)))) ((Add 3) 5))))+  > reify e4+  let [x0 = App x1 x20,x20 = App x21 x23,x23 = App x24 x15,x24 = App x25 x9,x25 = ON Mul,x21 = App x22 x6,x22 = ON Mul,x1 = App x2 x3,x3 = App x4 x6,x4 = App x5 x6,x6 = App x7 x9,x7 = App x8 x9,x9 = App x10 x12,x10 = App x11 x12,x12 = App x13 x15,x13 = App x14 x15,x15 = App x16 x19,x19 = ON 5,x16 = App x17 x18,x18 = ON 3,x17 = ON Add,x14 = ON Mul,x11 = ON Mul,x8 = ON Mul,x5 = ON Mul,x2 = ON Mul] in x0+  > ssa e4+  let x2 = Mul in let x5 = Mul in let x8 = Mul in let x11 = Mul in let x14 = Mul in let x17 = Add in let x18 = 3 in let x16 = (x17 x18) in let x19 = 5 in let x15 = (x16 x19) in let x13 = (x14 x15) in let x12 = (x13 x15) in let x10 = (x11 x12) in let x9 = (x10 x12) in let x7 = (x8 x9) in let x6 = (x7 x9) in let x4 = (x5 x6) in let x3 = (x4 x6) in let x1 = (x2 x3) in let x22 = Mul in let x21 = (x22 x6) in let x25 = Mul in let x24 = (x25 x9) in let x23 = (x24 x15) in let x20 = (x21 x23) in let x0 = (x1 x20) in x0+  > cse e4+  let x15 = ((Add 3) 5) in let x12 = ((Mul x15) x15) in let x9 = ((Mul x12) x12) in let x6 = ((Mul x9) x9) in ((Mul ((Mul x6) x6)) ((Mul x6) ((Mul x9) x15)))+-}