packages feed

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 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: