Narrowing.curry 17.7 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
------------------------------------------------------------------------------
--- Library for representation and computation of narrowings on first-order
--- terms and representation of narrowing strategies.
---
--- @author Jan-Hendrik Matthes
--- @version November 2016
--- @category algorithm
------------------------------------------------------------------------------

module Rewriting.Narrowing
  ( NStrategy, Narrowing (..), NarrowingTree (..), NOptions (..)
  , defaultNOptions, showNarrowing, stdNStrategy, imNStrategy, omNStrategy
  , loNStrategy, lazyNStrategy, wnNStrategy, narrowBy, narrowByL, narrowingBy
  , narrowingByL, narrowingTreeBy, narrowingTreeByL, solveEq, solveEqL
  , dotifyNarrowingTree, writeNarrowingTree
  ) where

import Maybe (fromMaybe, mapMaybe)
import List (maximum)
Michael Hanus 's avatar
Michael Hanus committed
20 21

import Data.FiniteMap (eltsFM)
22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
import Rewriting.DefinitionalTree
import Rewriting.Position
import Rewriting.Rules
import Rewriting.Strategy (RStrategy, poRStrategy, reduce)
import Rewriting.Substitution
import Rewriting.Term
import Rewriting.Unification (UnificationError (..), unify, unifiable)
import State

-- ---------------------------------------------------------------------------
-- Representation of narrowing strategies
-- ---------------------------------------------------------------------------

--- A narrowing strategy represented as a function that takes a term rewriting
--- system and a term and returns a list of triples consisting of a position,
--- a rule and a substitution, parameterized over the kind of function
--- symbols, e.g., strings.
type NStrategy f = TRS f -> Term f -> [(Pos, Rule f, Subst f)]

-- ---------------------------------------------------------------------------
-- Representation of narrowings on first-order terms
-- ---------------------------------------------------------------------------

--- Representation of a narrowing on first-order terms, parameterized over the
--- kind of function symbols, e.g., strings.
---
--- @cons NTerm t         - The narrowed term `t`.
--- @cons NStep t p sub n - The narrowing of term `t` at position `p` with
---                         substitution `sub` to narrowing `n`.
data Narrowing f = NTerm (Term f) | NStep (Term f) Pos (Subst f) (Narrowing f)

-- ---------------------------------------------------------------------------
-- Representation of narrowing trees for first-order terms
-- ---------------------------------------------------------------------------

--- Representation of a narrowing tree for first-order terms, parameterized
--- over the kind of function symbols, e.g., strings.
---
--- @cons NTree t ns - The narrowing of term `t` to a new term with a list of
---                    narrowing steps `ns`.
data NarrowingTree f = NTree (Term f) [(Pos, Subst f, NarrowingTree f)]

-- ---------------------------------------------------------------------------
-- Representation of narrowing options for solving term equations
-- ---------------------------------------------------------------------------

--- Representation of narrowing options for solving term equations,
--- parameterized over the kind of function symbols, e.g., strings.
---
--- @field normalize - Indicates whether a term should be normalized before
---                    computing further narrowing steps.
--- @field rStrategy - The reduction strategy to normalize a term.
data NOptions f = NOptions { normalize :: Bool, rStrategy :: RStrategy f }

--- The default narrowing options.
Michael Hanus 's avatar
Michael Hanus committed
77
defaultNOptions :: Eq f => NOptions f
78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
defaultNOptions = NOptions { normalize = False, rStrategy = poRStrategy }

-- ---------------------------------------------------------------------------
-- Pretty-printing of narrowings on first-order terms
-- ---------------------------------------------------------------------------

-- \x2192 = RIGHTWARDS ARROW

--- Transforms a narrowing into a string representation.
showNarrowing :: (f -> String) -> Narrowing f -> String
showNarrowing s (NTerm t)         = showTerm s t
showNarrowing s (NStep t p sub n)
  = (showTerm s t) ++ "\n\x2192" ++ "[" ++ (showPos p) ++ ", "
      ++ (showSubst s (restrictSubst sub (tVars t))) ++ "] "
      ++ (showNarrowing s n)

-- ---------------------------------------------------------------------------
-- Definition of common narrowing strategies
-- ---------------------------------------------------------------------------

--- The standard narrowing strategy.
Michael Hanus 's avatar
Michael Hanus committed
99
stdNStrategy :: Eq f => NStrategy f
100 101 102 103 104 105
stdNStrategy trs t = [(p, rule, sub) |
                      p <- positions t, let tp = t |> p, isConsTerm tp,
                      rule@(l, _) <- trs,
                      (Right sub) <- [unify [(tp, l)]]]

--- The innermost narrowing strategy.
Michael Hanus 's avatar
Michael Hanus committed
106
imNStrategy :: Eq f => NStrategy f
107 108 109 110 111 112
imNStrategy trs t = [(p, rule, sub) |
                     p <- positions t, let tp = t |> p, isPattern trs tp,
                     rule@(l, _) <- trs,
                     (Right sub) <- [unify [(tp, l)]]]

--- The outermost narrowing strategy.
Michael Hanus 's avatar
Michael Hanus committed
113
omNStrategy :: Eq f => NStrategy f
114 115 116 117 118 119
omNStrategy trs t = let ns = stdNStrategy trs t
                     in [n | n@(p, _, _) <- ns,
                             all (\p' -> not (above p' p))
                                 [p' | (p', _, _) <- ns, p' /= p]]

--- The leftmost outermost narrowing strategy.
Michael Hanus 's avatar
Michael Hanus committed
120
loNStrategy :: Eq f => NStrategy f
121 122 123 124 125 126 127
loNStrategy trs t
  = let ns = stdNStrategy trs t
     in [n | n@(p, _, _) <- ns,
             all (\p' -> not ((above p' p) || (leftOf p' p)))
                 [p' | (p', _, _) <- ns, p' /= p]]

--- The lazy narrowing strategy.
Michael Hanus 's avatar
Michael Hanus committed
128
lazyNStrategy :: Eq f => NStrategy f
129 130 131 132 133 134
lazyNStrategy trs t
  = let lps = lazyPositions trs t
     in filter (\(p, _, _) -> elem p lps) (stdNStrategy trs t)

--- Returns a list of all lazy positions in a term according to the given term
--- rewriting system.
Michael Hanus 's avatar
Michael Hanus committed
135
lazyPositions :: Eq f => TRS f -> Term f -> [Pos]
136 137 138 139 140 141 142 143 144 145 146
lazyPositions _   (TermVar _)       = []
lazyPositions trs t@(TermCons _ ts)
  | isRedex trs t = if null rs then lps else eps:lps
  | otherwise     = [i:p | (i, t') <- zip [1..] ts, p <- lazyPositions trs t']
  where
    ftrs = filter ((eqConsPattern t) . fst) trs
    rs = [r | r@(l, _) <- ftrs, unifiable [(t, l)]]
    dps = [i | (i, _) <- zip [1..] ts, any (isDemandedAt i) ftrs]
    lps = [i:p | i <- dps, p <- lazyPositions trs (ts !! (i - 1))]

--- The weakly needed narrowing strategy.
Michael Hanus 's avatar
Michael Hanus committed
147
wnNStrategy :: Eq f => NStrategy f
148 149 150 151 152 153 154 155 156 157 158 159
wnNStrategy trs t
  = let dts = defTrees trs
        v = fromMaybe 0 (minVarInTRS trs)
     in case loDefTrees dts t of
          Nothing          -> []
          (Just (_, []))   -> []
          (Just (p, dt:_)) -> [(p .> q, r, sub) |
                               (q, r, sub) <- wnNStrategy' dts v (t |> p) dt]

--- Returns the narrowing steps for the weakly needed narrowing strategy
--- according to the given definitional tree and the given next possible
--- variable.
Michael Hanus 's avatar
Michael Hanus committed
160
wnNStrategy' :: Eq f => [DefTree f] -> VarIdx -> Term f -> DefTree f
161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238
             -> [(Pos, Rule f, Subst f)]
wnNStrategy' _   v t (Leaf r)
  = let rule@(l, _) = renameRuleVars v (normalizeRule r)
     in [(eps, rule, sub) | (Right sub) <- [unify [(t, l)]]]
wnNStrategy' dts v t (Branch pat p dts')
  = case selectDefTrees dts (t |> p) of
      []     -> concatMap (wnNStrategy' dts v t) (filterDTS dts')
      (dt:_) -> case unify [(t, renameTermVars v (normalizeTerm pat))] of
                  (Left _)    -> []
                  (Right tau) ->
                    let tau' = restrictSubst tau (tVars t)
                        t' = applySubst tau' t
                        v' = max v (maybe 0 (+ 1) (maxVarInTerm t'))
                     in [(p .> p', rule, composeSubst sub tau') |
                         (p', rule, sub) <- wnNStrategy' dts v' (t' |> p) dt]
  where
    filterDTS = filter (\dt -> let dtp = renameTermVars v (dtPattern dt)
                                in unifiable [(t, dtp)])
wnNStrategy' dts v t (Or _ dts') = concatMap (wnNStrategy' dts v t) dts'

-- ---------------------------------------------------------------------------
-- Functions for narrowings on first-order terms
-- ---------------------------------------------------------------------------

--- Narrows a term with the given strategy and term rewriting system by the
--- given number of steps.
narrowBy :: NStrategy f -> TRS f -> Int -> Term f -> [(Subst f, Term f)]
narrowBy s trs n t | n <= 0    = []
                   | otherwise = let v = maybe 0 (+ 1) (maxVarInTerm t)
                                  in narrowBy' v emptySubst s trs n t

--- Narrows a term with the given strategy and list of term rewriting systems
--- by the given number of steps.
narrowByL :: NStrategy f -> [TRS f] -> Int -> Term f -> [(Subst f, Term f)]
narrowByL s trss = narrowBy s (concat trss)

--- Narrows a term with the given strategy, the given term rewriting system,
--- the already existing substitution and the given next possible variable by
--- the given number of steps.
narrowBy' :: VarIdx -> Subst f -> NStrategy f -> TRS f -> Int -> Term f
          -> [(Subst f, Term f)]
narrowBy' v sub s trs n t
  | n <= 0    = [(sub, t)]
  | otherwise = case s (renameTRSVars v (normalizeTRS trs)) t of
                  []       -> [(sub, t)]
                  ns@(_:_) -> concatMap combine ns
  where
    combine (p, (_, r), sub')
      = let t' = applySubst sub' (replaceTerm t p r)
            rsub' = restrictSubst sub' (tVars t)
            v' = case mapMaybe maxVarInTerm (eltsFM rsub') of
                   []       -> v
                   vs@(_:_) -> (maximum vs) + 1
         in narrowBy' v' (composeSubst rsub' sub) s trs (n - 1) t'

--- Returns a list of narrowings for a term with the given strategy, the given
--- term rewriting system and the given number of steps.
narrowingBy :: NStrategy f -> TRS f -> Int -> Term f -> [Narrowing f]
narrowingBy s trs n t | n <= 0    = []
                      | otherwise = let v = maybe 0 (+ 1) (maxVarInTerm t)
                                     in narrowingBy' v emptySubst s trs n t

--- Returns a list of narrowings for a term with the given strategy, the given
--- list of term rewriting systems and the given number of steps.
narrowingByL :: NStrategy f -> [TRS f] -> Int -> Term f -> [Narrowing f]
narrowingByL s trss = narrowingBy s (concat trss)

--- Returns a list of narrowings for a term with the given strategy, the given
--- term rewriting system, the already existing substitution, the given next
--- possible variable and the given number of steps.
narrowingBy' :: VarIdx -> Subst f -> NStrategy f -> TRS f -> Int -> Term f
             -> [Narrowing f]
narrowingBy' v sub s trs n t
  | n <= 0    = [NTerm t]
  | otherwise = case s (renameTRSVars v (normalizeTRS trs)) t of
                  []       -> [NTerm t]
                  ns@(_:_) -> concatMap combine ns
  where
Michael Hanus 's avatar
Michael Hanus committed
239
    -- combine :: (Pos, Rule f, Subst f) -> [Narrowing f]
240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272
    combine (p, (_, r), sub')
      = let t' = applySubst sub' (replaceTerm t p r)
            rsub' = restrictSubst sub' (tVars t)
            phi = composeSubst rsub' sub
            v' = case mapMaybe maxVarInTerm (eltsFM rsub') of
                   []       -> v
                   vs@(_:_) -> (maximum vs) + 1
         in map (NStep t p phi) (narrowingBy' v' phi s trs (n - 1) t')

--- Returns a narrowing tree for a term with the given strategy, the given
--- term rewriting system and the given number of steps.
narrowingTreeBy :: NStrategy f -> TRS f -> Int -> Term f -> NarrowingTree f
narrowingTreeBy s trs n t
  | n <= 0    = NTree t []
  | otherwise = let v = maybe 0 (+ 1) (maxVarInTerm t)
                 in narrowingTreeBy' v emptySubst s trs n t

--- Returns a narrowing tree for a term with the given strategy, the given
--- list of term rewriting systems and the given number of steps.
narrowingTreeByL :: NStrategy f -> [TRS f] -> Int -> Term f
                  -> NarrowingTree f
narrowingTreeByL s trss = narrowingTreeBy s (concat trss)

--- Returns a narrowing tree for a term with the given strategy, the given
--- term rewriting system, the already existing substitution, the given next
--- possible variable and the given number of steps.
narrowingTreeBy' :: VarIdx -> Subst f -> NStrategy f -> TRS f -> Int
                  -> Term f -> NarrowingTree f
narrowingTreeBy' v sub s trs n t
  | n <= 0    = NTree t []
  | otherwise = NTree t (map combine (s trs' t))
  where
    trs' = renameTRSVars v (normalizeTRS trs)
Michael Hanus 's avatar
Michael Hanus committed
273
    --combine :: (Pos, Rule f, Subst f) -> (Pos, Subst f, NarrowingTree f)
274 275 276 277 278 279 280 281 282 283 284 285 286 287
    combine (p, (_, r), sub')
      = let t' = applySubst sub' (replaceTerm t p r)
            rsub' = restrictSubst sub' (tVars t)
            phi = composeSubst rsub' sub
            v' = case mapMaybe maxVarInTerm (eltsFM rsub') of
                   []       -> v
                   vs@(_:_) -> (maximum vs) + 1
         in (p, phi, narrowingTreeBy' v' phi s trs (n - 1) t')

--- Solves a term equation with the given strategy, the given term rewriting
--- system and the given options. The term has to be of the form
--- `TermCons c [l, r]` with `c` being a constructor like `=`. The term `l`
--- and the term `r` are the left-hand side and the right-hand side of the
--- term equation.
Michael Hanus 's avatar
Michael Hanus committed
288
solveEq :: Eq f => NOptions f -> NStrategy f -> TRS f -> Term f -> [Subst f]
289 290 291 292 293 294 295 296 297 298 299 300 301 302
solveEq _    _ _   (TermVar _)       = []
solveEq opts s trs t@(TermCons _ ts)
  = case ts of
      [_, _] -> let vs = tVars t
                    v = maybe 0 (+ 1) (maxVarInTerm t)
                 in map ((flip restrictSubst) vs)
                        (solveEq' opts v emptySubst s trs t)
      _      -> []

--- Solves a term equation with the given strategy, the given list of term
--- rewriting systems and the given options. The term has to be of the form
--- `TermCons c [l, r]` with `c` being a constructor like `=`. The term `l`
--- and the term `r` are the left-hand side and the right-hand side of the
--- term equation.
Michael Hanus 's avatar
Michael Hanus committed
303
solveEqL :: Eq f => NOptions f -> NStrategy f -> [TRS f] -> Term f -> [Subst f]
304 305 306 307 308 309 310 311
solveEqL opts s trss = solveEq opts s (concat trss)

--- Solves a term equation with the given strategy, the given term rewriting
--- system, the already existing substitution, the given next possible
--- variable and the given options. The term has to be of the form
--- `TermCons c [l, r]` with `c` being a constructor like `=`. The term `l`
--- and the term `r` are the left-hand side and the right-hand side of the
--- term equation.
Michael Hanus 's avatar
Michael Hanus committed
312 313
solveEq' :: Eq f =>
            NOptions f -> VarIdx -> Subst f -> NStrategy f -> TRS f -> Term f
314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329
         -> [Subst f]
solveEq' _    _ _   _ _   (TermVar _)       = []
solveEq' opts v sub s trs t@(TermCons _ ts)
  = case ts of
      [_, _] -> case unify [(l, r)] of
                  (Left (Clash t1 t2)) | (isRedex trs t1) || (isRedex trs t2)
                                          -> concatMap solve (s trs' nt)
                                       | otherwise -> []
                  (Left (OccurCheck _ _)) -> []
                  (Right sub')            -> [composeSubst sub' sub]
      _      -> []
  where
    trs' = renameTRSVars v (normalizeTRS trs)
    nt@(TermCons _ [l, r]) = if (normalize opts)
                               then reduce (rStrategy opts) trs t
                               else t
Michael Hanus 's avatar
Michael Hanus committed
330
    --solve :: (Pos, Rule f, Subst f) -> [Subst f]
331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383
    solve (p, (_, r'), sub')
      = let t' = applySubst sub' (replaceTerm nt p r')
            rsub' = restrictSubst sub' (tVars nt)
            v' = case mapMaybe maxVarInTerm (eltsFM rsub') of
                   []       -> v
                   vs@(_:_) -> (maximum vs) + 1
         in solveEq' opts v' (composeSubst rsub' sub) s trs t'

-- ---------------------------------------------------------------------------
-- Graphical representation of narrowing trees
-- ---------------------------------------------------------------------------

--- A node represented as a pair of an integer and a term and parameterized
--- over the kind of function symbols, e.g., strings.
type Node f = (Int, Term f)

--- An edge represented as a tuple of a start node, a substitution and an end
--- node and parameterized over the kind of function symbols, e.g., strings.
type Edge f = (Node f, Subst f, Node f)

--- A graph represented as a pair of nodes and edges and parameterized over
--- the kind of function symbols, e.g., strings.
type Graph f = ([Node f], [Edge f])

--- Transforms a narrowing tree into a graph representation.
toGraph :: NarrowingTree f -> Graph f
toGraph ng = fst (fst (runState (toGraph' ng) 0))
  where
    toGraph' :: NarrowingTree f -> State Int (Graph f, Node f)
    toGraph' (NTree t ngs)
      = newIdx `bindS`
          (\i -> let n = (i, t)
                  in (mapS (edge n) ngs) `bindS`
                       (\gs -> let (ns, es) = unzip gs
                                in returnS ((n:(concat ns), concat es), n)))
    edge :: Node f -> (Pos, Subst f, NarrowingTree f) -> State Int (Graph f)
    edge n1 (_, sub, ng')
      = (toGraph' ng') `bindS`
          (\((ns, es), n2) -> returnS (ns, (n1, sub, n2):es))
    newIdx :: State Int Int
    newIdx = getS `bindS` (\i -> (putS (i + 1)) `bindS_` (returnS i))

--- Transforms a narrowing tree into a graphical representation by using the
--- *DOT graph description language*.
dotifyNarrowingTree :: (f -> String) -> NarrowingTree f -> String
dotifyNarrowingTree s ng
  = "digraph NarrowingTree {\n\t"
      ++ "node [fontname=Helvetica,fontsize=10,shape=box];\n"
      ++ (unlines (map showNode ns))
      ++ "\tedge [fontname=Helvetica,fontsize=10];\n"
      ++ (unlines (map showEdge es)) ++ "}"
  where
    (ns, es) = toGraph ng
Michael Hanus 's avatar
Michael Hanus committed
384

385 386
    showNode (n, t) = "\t" ++ (showVarIdx n) ++ " [label=\"" ++ (showTerm s t)
                        ++ "\"];"
Michael Hanus 's avatar
Michael Hanus committed
387

388 389 390 391 392 393 394 395
    showEdge ((n1, t), sub, (n2, _))
      = "\t" ++ (showVarIdx n1) ++ " -> " ++ (showVarIdx n2) ++ " [label=\""
          ++ (showSubst s (restrictSubst sub (tVars t))) ++ "\"];"

--- Writes the graphical representation of a narrowing tree with the
--- *DOT graph description language* to a file with the given filename.
writeNarrowingTree :: (f -> String) -> NarrowingTree f -> String -> IO ()
writeNarrowingTree s ng fn = writeFile fn (dotifyNarrowingTree s ng)