srtree 3.0.0.7 → 3.0.1.0
raw patch · 4 files changed
+382/−2 lines, 4 filesPVP ok
version bump matches the API change (PVP)
API changes (from Hackage documentation)
+ Algorithm.EqSat.Simplify: isConstPos :: ConstrFun
+ Algorithm.EqSat.Simplify: isConstPt :: ConstrFun
+ Algorithm.EqSat.Simplify: isEven :: ConstrFun
+ Algorithm.EqSat.Simplify: isInteger :: ConstrFun
+ Algorithm.EqSat.Simplify: isNotParam :: ConstrFun
+ Algorithm.EqSat.Simplify: isNotZero :: ConstrFun
+ Algorithm.EqSat.Simplify: isPositive :: ConstrFun
+ Algorithm.EqSat.Simplify: isValid :: ConstrFun
+ Algorithm.EqSat.Simplify: rewritesMergeOnly :: [Rule]
+ Algorithm.EqSat.Simplify: rewritesWithParam :: [Rule]
+ Algorithm.EqSat.Simplify: type ConstrFun = Pattern -> Condition
+ Text.ParseRule: conditionRegistry :: Map String ConstrFun
+ Text.ParseRule: instance GHC.Internal.Classes.Eq Text.ParseRule.ArrKind
+ Text.ParseRule: instance GHC.Internal.Show.Show Text.ParseRule.ArrKind
+ Text.ParseRule: knownConditions :: [String]
+ Text.ParseRule: parsePat :: ByteString -> Either String Pattern
+ Text.ParseRule: parsePatExpr :: ParsePat
+ Text.ParseRule: parseRule :: ByteString -> Either String Rule
+ Text.ParseRule: parseRules :: ByteString -> Either String [Rule]
+ Text.ParseRule: resolveRules :: String -> IO (Either String [Rule])
+ Text.ParseRule: rulesetByName :: String -> Maybe [Rule]
+ Text.ParseRule: rulesetNames :: [String]
+ Text.ParseRule: type ParsePat = Parser Pattern
Files
- ChangeLog.md +23/−0
- src/Algorithm/EqSat/Simplify.hs +23/−1
- src/Text/ParseRule.hs +334/−0
- srtree.cabal +2/−1
ChangeLog.md view
@@ -1,5 +1,28 @@ # Changelog for srtree +## 3.0.1.0++- **User-supplied equivalence rules** (new exposed module `Text.ParseRule`):+ parsing and resolution of user-written eqsat rules and rule sets.+ - `parseRule` / `parseRules`: rule syntax `lhs -> rhs` (also `=>`),+ `lhs <=> rhs` (also `==`), optional conditions on the matched wildcards+ (`x / x -> 1 | isNotZero(x), isPositive(y)`). Patterns use the usual+ expression syntax; `v<i>` or a single letter `[a-zA-Z]` are wildcards.+ Validation rejects unbound target/condition variables and unknown+ predicates. `#` comments; one rule per line or `;`-separated.+ - `conditionRegistry`: the named condition predicates usable in rules+ (`isConst`, `isConstPos`, `isNotParam`, `isNotZero`, `isEven`,+ `isInteger`, `isPositive`, `isValid`).+ - `rulesetNames` / `rulesetByName` / `resolveRules`: builtin rule sets+ (`default`, `params`, `simple`, `constant`, `basic`, `fun`,+ `merge-only`), `@FILE` rule files, or inline `;`-separated rules.+- **`Algorithm.EqSat.Simplify`**: new `rewritesMergeOnly` rule set (rules that+ only merge e-classes or shrink expressions without introducing new+ sub-expressions: `x + 0 -> x`, `x * 1 -> x`, `x - x -> 0`, `x / x -> 1`,+ ...). Newly exported: `ConstrFun`, `isConstPt`, `isConstPos`, `isNotParam`,+ `isNotZero`, `isEven`, `isInteger`, `isPositive`, `isValid`,+ `rewritesWithParam`.+ ## 3.0.0.7 - **Bound profile-likelihood walk restarts** (`ConfidenceIntervals`): the
src/Algorithm/EqSat/Simplify.hs view
@@ -12,7 +12,7 @@ -- Module containing the algebraic rules and simplification function. -- ------------------------------------------------------------------------------module Algorithm.EqSat.Simplify ( Rule(..), simplifyEqSatDefault, applyMergeOnlyDftl, rewrites, rewritesParams, rewriteBasic, rewritesFun, rewritesSimple, rewritesWithConstant, myCost ) where+module Algorithm.EqSat.Simplify ( Rule(..), ConstrFun, simplifyEqSatDefault, applyMergeOnlyDftl, rewrites, rewritesParams, rewriteBasic, rewritesFun, rewritesSimple, rewritesWithConstant, rewritesWithParam, rewritesMergeOnly, isConstPt, isConstPos, isNotParam, isNotZero, isEven, isInteger, isPositive, isValid, myCost ) where import Algorithm.EqSat (eqSat, applySingleMergeOnlyEqSat) import Algorithm.EqSat.Egraph@@ -248,6 +248,28 @@ rewritesSimple :: [Rule] rewritesSimple = rewriteBasic <> constReduction <> rewritesFun++-- | merge-only rules: only merge e-classes or shrink expressions without+-- introducing new structural sub-expressions. Useful to remove redundancy+-- without inflating the e-class count (e.g. before fitting a large graph).+rewritesMergeOnly :: [Rule]+rewritesMergeOnly =+ [+ -- x + 0 = x+ NAry EAdd [Ch (Fixed (Const 0)), Rest 'r'] :=> NAry EAdd [Rest 'r']+ -- x * 1 = x+ , NAry EMul [Ch (Fixed (Const 1)), Rest 'r'] :=> NAry EMul [Rest 'r']+ -- x * 0 = 0 (provided every factor is valid)+ , NAry EMul [Ch (Fixed (Const 0)), Rest 'r'] :=> 0 :| allValidRest 'r'+ -- x - x = 0+ , "x" - "x" :=> 0+ -- x / x = 1+ , "x" / "x" :=> 1 :| isNotZero "x"+ , "x" ** 1 :=> "x"+ , powabs 1 "x" :=> 1+ , 1 ** "x" :=> 1+ , recip (recip "x") :=> "x" :| isNotZero "x"+ ] powabs l r = Fixed (Bin PowerAbs l r) -- | default cost function for simplification
+ src/Text/ParseRule.hs view
@@ -0,0 +1,334 @@+{-# language OverloadedStrings #-}+-----------------------------------------------------------------------------+-- |+-- Module : Text.ParseRule+-- Copyright : (c) Fabricio Olivetti 2021 - 2024+-- License : BSD3+-- Maintainer : fabricio.olivetti@gmail.com+-- Stability : experimental+-- Portability :+--+-- Parser and resolver for user-supplied equality-saturation rewrite rules+-- and rule sets.+--+-- A rule is written as+--+-- > lhs -> rhs -- one-way rewrite+-- > lhs <=> rhs -- bidirectional (two one-way rules)+-- > lhs -> rhs | isNotZero(x) -- conditional rule+-- > lhs -> rhs | isPositive(x), isInteger(y)+--+-- Patterns use the same expression syntax as 'parsePat': @x<i>@ is feature+-- variable @i@, @t<i>@ is parameter @i@, @v<i>@ or any single letter @[a-zA-Z]@+-- is a pattern variable (wildcard), and numeric literals are constants.+-- Operators: @+@ @-@ @*@ @/@ @^@ @**@ @|**|@ (power of absolute value) @aq@ and+-- the unary functions @sin@ @cos@ @tan@ @log@ @exp@ @sqrt@ @abs@ @recip@+-- @cbrt@ @square@ @cube@ @logabs@ @sqrtabs@ (and capitalized aliases).+--+-- Conditions refer to a fixed registry of named predicates ('conditionRegistry')+-- applied to a pattern variable, e.g. @isNotZero(x)@. Every variable occurring+-- in the target (and in a condition) must also occur in the source; for a+-- bidirectional rule both sides must use the same variables.+--+-- A rule set is either one of the builtin names ('rulesetNames'), a file+-- prefixed with @\@@ containing one rule per line (@#@ comments), or an inline+-- rule list with rules separated by @;@. Use 'resolveRules' to accept any of+-- the three spellings.+--+-----------------------------------------------------------------------------+module Text.ParseRule+ ( ParsePat, parsePat, parsePatExpr+ , parseRule, parseRules+ , conditionRegistry, knownConditions+ , rulesetNames, rulesetByName, resolveRules+ ) where++import Control.Applicative ((<|>))+import Data.Attoparsec.ByteString.Char8 hiding ( match, takeWhile )+import Data.Attoparsec.Expr+import qualified Data.ByteString.Char8 as B+import Data.Char (isAlpha)+import Data.List (dropWhileEnd, intercalate, isInfixOf, isPrefixOf, nub)+import Data.List.Split (splitOn)+import qualified Data.Map.Strict as Map+import System.Directory (doesFileExist)++import Data.SRTree+import Algorithm.EqSat.Egraph (NOp(..))+import Algorithm.EqSat.DB+import Algorithm.EqSat.Simplify+ ( ConstrFun, isConstPt, isConstPos, isNotParam, isNotZero+ , isEven, isInteger, isPositive, isValid+ , rewrites, rewritesParams, rewritesSimple, rewritesWithConstant+ , rewriteBasic, rewritesFun, rewritesMergeOnly+ )++-- * Pattern parsing++type ParsePat = Parser Pattern++-- | parses a string representing a pattern expression (e.g. @v0 * x0 + t0@).+-- Pattern variables can be written as @v<i>@ or as a single letter @[a-zA-Z]@+-- (e.g. @x + 0@).+parsePat :: B.ByteString -> Either String Pattern+parsePat = eitherResult . (`feed` "") . parse parsePatExpr . putEOL . B.strip++putEOL :: B.ByteString -> B.ByteString+putEOL bs | B.null bs = bs+ | B.last bs == '\n' = bs+ | otherwise = B.snoc bs '\n'++parsePatExpr :: ParsePat+parsePatExpr = parsePatternExpr (prefixOps : binOps) [] var+ where+ prefixOps = Prelude.map (uncurry prefix)+ [ ("id", id), ("abs", abs)+ , ("sinh", sinh), ("cosh", cosh), ("tanh", tanh)+ , ("sin", sin), ("cos", cos), ("tan", tan)+ , ("asinh", asinh), ("acosh", acosh), ("atanh", atanh)+ , ("asin", asin), ("acos", acos), ("atan", atan)+ , ("sqrtabs", sqrtabs'), ("sqrt", sqrt), ("cbrt", cbrt'), ("square", (**2))+ , ("logabs", logabs'), ("log", log), ("exp", exp), ("cube", cube'), ("recip", recip')+ , ("Id", id), ("Abs", abs)+ , ("Sinh", sinh), ("Cosh", cosh), ("Tanh", tanh)+ , ("Sin", sin), ("Cos", cos), ("Tan", tan)+ , ("ASinh", asinh), ("ACosh", acosh), ("ATanh", atanh)+ , ("ASin", asin), ("ACos", acos), ("ATan", atan)+ , ("SqrtAbs", sqrtabs'), ("Sqrt", sqrt), ("Cbrt", cbrt'), ("Square", (**2))+ , ("LogAbs", logabs'), ("Log", log), ("Exp", exp), ("Recip", recip'), ("Cube", cube')+ , ("|log|", logabs'), ("|Log|", logabs'), ("|sqrt|", sqrtabs'), ("|Sqrt|", sqrtabs')+ , ("√", sqrt), ("|√|", sqrtabs')+ ]+ binOps = [[binary "^" (**) AssocLeft], [binary "**" (**) AssocLeft]+ , [binary "*" (*) AssocLeft, binary "/" (/) AssocLeft]+ , [binary "+" (+) AssocLeft, binary "-" (-) AssocLeft]+ , [binary "|**|" powabs AssocLeft], [binary "|^|" powabs AssocLeft]+ , [binary "aq" aq AssocLeft], [binary "|/|" aq AssocLeft]+ ]+ powabs l r = Fixed $ Bin PowerAbs l r+ aq l r = Fixed $ Bin AQ l r+ logabs' t = Fixed $ Uni LogAbs t+ sqrtabs' t = Fixed $ Uni SqrtAbs t+ cbrt' t = Fixed $ Uni Cbrt t+ cube' t = Fixed $ Uni Cube t+ recip' t = Fixed $ Uni Recip t++ var = do char 'x'+ ix <- decimal+ pure $ Fixed $ Var ix+ <|> do char 't'+ ix <- decimal+ pure $ Fixed $ Param ix+ <|> do char 'v'+ ix <- decimal+ pure $ VarPat (toEnum $ ix+65)+ <|> do c <- letter_ascii+ pure $ VarPat c+ <?> "var"++-- | Creates a parser for a binary operator+binary :: B.ByteString -> (a -> a -> a) -> Assoc -> Operator B.ByteString a+binary name fun = Infix (do{ string (B.cons ' ' (B.snoc name ' ')) <|> string name; pure fun })++-- | Creates a parser for a unary function+prefix :: B.ByteString -> (a -> a) -> Operator B.ByteString a+prefix name fun = Prefix (do{ string name; pure fun })++-- | Envelopes the parser in parens+parens :: Parser a -> Parser a+parens e = do{ string "("; e' <- e; string ")"; pure e' } <?> "parens"++parsePatternExpr :: [[Operator B.ByteString Pattern]] -> [ParsePat -> ParsePat] -> ParsePat -> ParsePat+parsePatternExpr table binFuns var =+ do e <- expr+ many1' space+ pure e+ where+ term = parens expr <|> choice (Prelude.map ($ expr) binFuns) <|> coef <|> var <?> "term"+ expr = buildExpressionParser table term+ coef = Fixed . Const <$> signed double <?> "const"++-- * Rule parsing++-- | A rule direction: one-way ('Dir') or bidirectional ('Bi').+data ArrKind = Dir | Bi deriving (Eq, Show)++-- | Parses a single rewrite rule @lhs -> rhs@, @lhs => rhs@, @lhs <=> rhs@ or+-- @lhs == rhs@, optionally followed by @| cond1(x), cond2(y)@.+parseRule :: B.ByteString -> Either String Rule+parseRule raw =+ case dropWhile isSpace . takeWhile (/= '#') $ B.unpack raw of+ "" -> Left "empty rule"+ s -> do+ (lhsStr, arr, rhsRest) <- splitArrow s+ let (rhsStr, condStr) = splitConds rhsRest+ lhs <- parsePat (B.pack lhsStr)+ rhs <- parsePat (B.pack rhsStr)+ conds <- mapM parseCond (filter (not . null) (splitOn "," condStr))+ validateRule lhs rhs arr conds+ let base = case arr of+ Dir -> lhs :=> rhs+ Bi -> lhs :==: rhs+ pure $ foldl (:|) base [cf arg | (_, arg, cf) <- conds]++-- | Parses a rule set: one rule per line, @#@ comments, and/or @;@-separated+-- rules within a line.+parseRules :: B.ByteString -> Either String [Rule]+parseRules txt = go 1 (lines (B.unpack txt))+ where+ go _ [] = Right []+ go i (l:ls) =+ let pieces = filter (not . all isSpace) (splitOn ";" (takeWhile (/= '#') l))+ in case traverse (parseRule . B.pack) pieces of+ Left e -> Left ("line " <> show i <> ": " <> e)+ Right rs -> fmap (rs <>) (go (i+1) ls)++-- | Splits at the first rule arrow. Longest arrow first at each position so+-- that @<=>@ wins over @=>@.+splitArrow :: String -> Either String (String, ArrKind, String)+splitArrow = go ""+ where+ go _ [] = Left "a rule must contain an arrow ('->' for one-way, '<=>' for bidirectional)"+ go acc s@(c:cs)+ | Just (arr, n) <- matchArrow s = Right (reverse acc, arr, drop n s)+ | otherwise = go (c:acc) cs+ matchArrow s+ | "<=>" `isPrefixOf` s = Just (Bi, 3)+ | "->" `isPrefixOf` s = Just (Dir, 2)+ | "=>" `isPrefixOf` s = Just (Dir, 2)+ | "==" `isPrefixOf` s = Just (Bi, 2)+ | otherwise = Nothing++-- | Splits the right-hand side of a rule at the condition separator @|@.+-- A @|@ is only a condition separator when it is followed by @name(...)@, so+-- the @|**|@, @|log|@, ... operators are not confused with conditions.+splitConds :: String -> (String, String)+splitConds = go ""+ where+ go acc [] = (reverse acc, "")+ go acc s@(c:cs)+ | c == '|', isCondStart (dropWhile isSpace cs) = (reverse acc, dropWhile isSpace cs)+ | otherwise = go (c:acc) cs+ isCondStart s = case span isAlpha s of+ (_:_, rest) -> case dropWhile isSpace rest of+ ('(':_) -> True+ _ -> False+ _ -> False++-- | Parses a single condition @name(arg)@ where @arg@ is a pattern variable.+-- Returns the condition name (for error messages), the argument pattern and+-- the predicate.+parseCond :: String -> Either String (String, Pattern, ConstrFun)+parseCond s0 =+ let s = dropWhile isSpace s0+ (name, rest) = span isAlpha s+ rest1 = dropWhile isSpace rest+ in if null name+ then Left ("invalid condition '" <> s0 <> "': expected name(patternVar)")+ else case rest1 of+ '(' : rest2 -> case break (== ')') rest2 of+ (argStr, ')':_) -> do+ arg <- parsePat (B.pack argStr)+ cf <- maybe (Left ("unknown condition '" <> name <> "'. Known conditions: "+ <> intercalate ", " (Map.keys conditionRegistry)))+ Right (Map.lookup name conditionRegistry)+ pure (name, arg, cf)+ _ -> Left ("unterminated condition '" <> s0 <> "': missing ')'")+ _ -> Left ("expected '(' after condition name in '" <> s0 <> "'")++-- | Checks that every target/condition variable is bound by the source+-- pattern. A bidirectional rule must bind the same variables on both sides+-- (its conditions are applied to both directions).+validateRule :: Pattern -> Pattern -> ArrKind -> [(String, Pattern, ConstrFun)] -> Either String ()+validateRule lhs rhs arr conds = do+ let lv = patVars lhs+ rv = patVars rhs+ case arr of+ Dir -> case filter (`notElem` lv) rv of+ [] -> Right ()+ vs -> Left ("unbound target variable(s) " <> show vs+ <> ": every target variable must appear in the source pattern")+ Bi -> if null (filter (`notElem` lv) rv) && null (filter (`notElem` rv) lv)+ then Right ()+ else Left "both sides of a bidirectional ('<=>') rule must use the same pattern variables"+ mapM_ (\(_, arg, _) -> case arg of+ VarPat c | c `elem` lv -> Right ()+ VarPat c -> Left ("condition variable '" <> [c] <> "' does not appear in the source pattern")+ _ -> Left "condition arguments must be pattern variables (e.g. isNotZero(x))")+ conds++-- | The pattern variables occurring in a pattern.+patVars :: Pattern -> [Char]+patVars = nub . go+ where+ go (VarPat c) = [c]+ go Hole = []+ go (Fixed t) = case t of+ Var _ -> []+ Param _ -> []+ Const _ -> []+ Y _ -> []+ Uni _ a -> go a+ Bin _ a b -> go a <> go b+ go (NAry _ cs) = concatMap child cs+ child (Ch p) = go p+ child (Rest c) = [c]+ child (MapP p c) = c : go p++-- * Conditions and rule sets++-- | Registry of the named condition predicates usable in user rules. Each+-- predicate constrains the e-class bound to a pattern variable.+conditionRegistry :: Map.Map String ConstrFun+conditionRegistry = Map.fromList+ [ ("isConst", isConstPt)+ , ("isConstPt", isConstPt)+ , ("isConstPos", isConstPos)+ , ("isNotParam", isNotParam)+ , ("isNotZero", isNotZero)+ , ("isEven", isEven)+ , ("isInteger", isInteger)+ , ("isPositive", isPositive)+ , ("isValid", isValid)+ ]++-- | The names accepted in 'conditionRegistry'.+knownConditions :: [String]+knownConditions = Map.keys conditionRegistry++-- | Builtin rule set names.+rulesetNames :: [String]+rulesetNames = ["default", "params", "simple", "constant", "basic", "fun", "merge-only"]++-- | Looks up a builtin rule set by name.+rulesetByName :: String -> Maybe [Rule]+rulesetByName "default" = Just rewrites+rulesetByName "params" = Just rewritesParams+rulesetByName "simple" = Just rewritesSimple+rulesetByName "constant" = Just rewritesWithConstant+rulesetByName "basic" = Just rewriteBasic+rulesetByName "fun" = Just rewritesFun+rulesetByName "merge-only" = Just rewritesMergeOnly+rulesetByName _ = Nothing++-- | Resolves a rule set specification: a builtin name ('rulesetNames'),+-- @\@FILE@ with one rule per line, or inline rules separated by @;@ (e.g.+-- @\"x + 0 -> x; log(exp(x)) <=> x\"@). The empty string and @\"default\"@+-- select the default rule set. Returns a user-readable error message when the+-- specification cannot be resolved.+resolveRules :: String -> IO (Either String [Rule])+resolveRules spec+ | null trimmed = pure (Right rewrites)+ | Just rs <- rulesetByName trimmed = pure (Right rs)+ | ('@':path) <- trimmed =+ do ok <- doesFileExist path+ if not ok+ then pure (Left ("rules file not found: " <> path))+ else parseRules <$> B.readFile path+ | any (`isInfixOf` spec) ["->", "<=>", "=>", "=="] = pure (parseRules (B.pack spec))+ | otherwise = pure (Left ("unknown rule set '" <> spec <> "'. Use a builtin name ("+ <> intercalate ", " rulesetNames+ <> "), @FILE with one rule per line, or inline rules such as "+ <> "'x + 0 -> x' (multiple rules separated by ';')."))+ where+ trimmed = dropWhileEnd isSpace (dropWhile isSpace spec)
srtree.cabal view
@@ -5,7 +5,7 @@ -- see: https://github.com/sol/hpack name: srtree-version: 3.0.0.7+version: 3.0.1.0 synopsis: A general library to work with Symbolic Regression expression trees. description: A Symbolic Regression Tree data structure to work with mathematical expressions with support to first order derivative and simplification; license: BSD3@@ -55,6 +55,7 @@ Data.SRTree.Recursion Numeric.Optimization.NLOPT Numeric.Optimization.NLOPT.Bindings+ Text.ParseRule Text.ParseSR Text.ParseSR.IO other-modules: