1)abbrev domain PATTERN Pattern 2++ Patterns for use by the pattern matcher 3++ Author: Manuel Bronstein 4++ Date Created: 10 Nov 1988 5++ Description: Patterns for use by the pattern matcher. 6++ Keywords: pattern, matching. 7-- Not exposed. 8-- Patterns are optimized for quick answers to structural questions. 9Pattern(R : SetCategory) : Exports == Implementation where 10 B ==> Boolean 11 SI ==> SingleInteger 12 Z ==> Integer 13 SY ==> Symbol 14 O ==> OutputForm 15 BOP ==> BasicOperator 16 QOT ==> Record(num : %, den : %) 17 REC ==> Record(val : %, exponent : NonNegativeInteger) 18 RSY ==> Record(tag : SI, val : SY, pred : List Any, bad : List Any) 19 KER ==> Record(tag : SI, op : BOP, arg : List %) 20 PAT ==> Union(ret : R, ker : KER, exp : REC, qot : QOT, sym : RSY) 21 22-- the following MUST be the name of the formal exponentiation operator 23 POWER ==> '%power 24 25-- the 4 SYM_ constants must be disting powers of 2 (bitwise arithmetic) 26 SYM_GENERIC ==> 1::SI 27 SYM_MULTIPLE ==> 2::SI 28 SYM_OPTIONAL ==> 4::SI 29 30 PAT_PLUS ==> 1::SI 31 PAT_TIMES ==> 2::SI 32 PAT_LIST ==> 3::SI 33 PAT_ZERO ==> 4::SI 34 PAT_ONE ==> 5::SI 35 PAT_EXPT ==> 6::SI 36 37 Exports ==> Join(SetCategory, RetractableTo R, RetractableTo SY) with 38 0 : constant -> % ++ 0 39 1 : constant -> % ++ 1 40 isPlus : % -> Union(List %, "failed") 41 ++ isPlus(p) returns \spad{[a1, ..., an]} if \spad{n > 1} 42 ++ and \spad{p = a1 + ... + an}, 43 ++ and "failed" otherwise. 44 isTimes : % -> Union(List %, "failed") 45 ++ isTimes(p) returns \spad{[a1, ..., an]} if \spad{n > 1} and 46 ++ \spad{p = a1 * ... * an}, and 47 ++ "failed" otherwise. 48 isOp : (%, BOP) -> Union(List %, "failed") 49 ++ isOp(p, op) returns \spad{[a1, ..., an]} if \spad{p = op(a1, ..., an)}, and 50 ++ "failed" otherwise. 51 isOp : % -> Union(Record(op:BOP, arg:List %), "failed") 52 ++ isOp(p) returns \spad{[op, [a1, ..., an]]} if 53 ++ \spad{p = op(a1, ..., an)}, and 54 ++ "failed" otherwise; 55 isExpt : % -> Union(REC, "failed") 56 ++ isExpt(p) returns \spad{[q, n]} if \spad{n > 0} and \spad{p = q ^ n}, 57 ++ and "failed" otherwise. 58 isQuotient : % -> Union(QOT, "failed") 59 ++ isQuotient(p) returns \spad{[a, b]} if \spad{p = a / b}, and 60 ++ "failed" otherwise. 61 isList : % -> Union(List %, "failed") 62 ++ isList(p) returns \spad{[a1, ..., an]} if \spad{p = [a1, ..., an]}, 63 ++ "failed" otherwise; 64 isPower : % -> Union(Record(val:%, exponent:%), "failed") 65 ++ isPower(p) returns \spad{[a, b]} if \spad{p = a ^ b}, and 66 ++ "failed" otherwise. 67 elt : (BOP, List %) -> % 68 ++ \spad{elt(op, [a1, ..., an])} returns \spad{op(a1, ..., an)}. 69 "+" : (%, %) -> % 70 ++ \spad{a + b} returns the pattern \spad{a + b}. 71 "*" : (%, %) -> % 72 ++ \spad{a * b} returns the pattern \spad{a * b}. 73 "^" : (%, NonNegativeInteger) -> % 74 ++ \spad{a ^ n} returns the pattern \spad{a ^ n}. 75 "^" : (%, %) -> % 76 ++ \spad{a ^ b} returns the pattern \spad{a ^ b}. 77 "/" : (%, %) -> % 78 ++ \spad{a / b} returns the pattern \spad{a / b}. 79 depth : % -> NonNegativeInteger 80 ++ depth(p) returns the nesting level of p. 81 convert : List % -> % 82 ++ \spad{convert([a1, ..., an])} returns the pattern \spad{[a1, ..., an]}. 83 copy : % -> % 84 ++ copy(p) returns a recursive copy of p. 85 inR? : % -> B 86 ++ inR?(p) tests if p is an atom (i.e. an element of R). 87 quoted? : % -> B 88 ++ quoted?(p) tests if p is of the form 's for a symbol s. 89 symbol? : % -> B 90 ++ symbol?(p) tests if p is a symbol. 91 constant? : % -> B 92 ++ constant?(p) tests if p contains no matching variables. 93 generic? : % -> B 94 ++ generic?(p) tests if p is a single matching variable. 95 multiple? : % -> B 96 ++ multiple?(p) tests if p is a single matching variable 97 ++ allowing list matching or multiple term matching in a 98 ++ sum or product. 99 optional? : % -> B 100 ++ optional?(p) tests if p is a single matching variable 101 ++ which can match an identity. 102 hasPredicate? : % -> B 103 ++ hasPredicate?(p) tests if p has predicates attached to it. 104 predicates : % -> List Any 105 ++ predicates(p) returns \spad{[p1, ..., pn]} such that the predicate 106 ++ attached to p is p1 and ... and pn. 107 setPredicates : (%, List Any) -> % 108 ++ \spad{setPredicates(p, [p1, ..., pn])} attaches the predicate 109 ++ p1 and ... and pn to p. 110 withPredicates : (%, List Any) -> % 111 ++ \spad{withPredicates(p, [p1, ..., pn])} makes a copy of p and attaches 112 ++ the predicate p1 and ... and pn to the copy, which is 113 ++ returned. 114 patternVariable : (SY, B, B, B) -> % 115 ++ patternVariable(x, c?, o?, m?) creates a pattern variable x, 116 ++ which is constant if \spad{c? = true}, optional if \spad{o? = true}, 117 ++ and multiple if \spad{m? = true}. 118 setTopPredicate : (%, List SY, Any) -> % 119 ++ \spad{setTopPredicate(x, [a1, ..., an], f)} returns x with 120 ++ the top-level predicate set to \spad{f(a1, ..., an)}. 121 topPredicate : % -> Record(var : List SY, pred : Any) 122 ++ topPredicate(x) returns \spad{[[a1, ..., an], f]} where the top-level 123 ++ predicate of x is \spad{f(a1, ..., an)}. 124 ++ Note: n is 0 if x has no top-level 125 ++ predicate. 126 hasTopPredicate? : % -> B 127 ++ hasTopPredicate?(p) tests if p has a top-level predicate. 128 resetBadValues : % -> % 129 ++ resetBadValues(p) initializes the list of "bad values" for p 130 ++ to \spad{[]}. 131 ++ Note: p is not allowed to match any of its "bad values". 132 addBadValue : (%, Any) -> % 133 ++ addBadValue(p, v) adds v to the list of "bad values" for p. 134 ++ Note: p is not allowed to match any of its "bad values". 135 getBadValues : % -> List Any 136 ++ getBadValues(p) returns the list of "bad values" for p. 137 ++ Note: p is not allowed to match any of its "bad values". 138 variables : % -> List % 139 ++ variables(p) returns the list of matching variables 140 ++ appearing in p. 141 optpair : List % -> Union(List %, "failed") 142 ++ optpair(l) returns l has the form \spad{[a, b]} and 143 ++ a is optional, and 144 ++ "failed" otherwise; 145 146 Implementation ==> add 147 Rep := Record(cons? : B, pat : PAT, lev : NonNegativeInteger, 148 topvar : List SY, toppred : Any) 149 150 import from PAT 151 152 dummy : BOP := operator(new()$Symbol) 153 nopred := coerce(0$Integer)$AnyFunctions1(Integer) 154 155 mkPat : (B, PAT, NonNegativeInteger) -> % 156 mkrsy : (SY, B, B, B) -> RSY 157 SYM2O : RSY -> O 158 PAT2O : PAT -> O 159 patcopy : PAT -> PAT 160 bitSet? : (SI , SI) -> B 161 pateq? : (PAT, PAT) -> B 162 LPAT2O : ((O, O) -> O, List %) -> O 163 taggedElt : (SI, List %) -> % 164 isTaggedOp : (%, SI) -> Union(List %, "failed") 165 incmax : List % -> NonNegativeInteger 166 167 coerce(r : R) : % == mkPat(true, [r], 0) 168 mkPat(c, p, l) == [c, p, l, empty(), nopred] 169 hasTopPredicate? x == not empty?(x.topvar) 170 topPredicate x == [x.topvar, x.toppred] 171 setTopPredicate(x, l, f) == (x.topvar := l; x.toppred := f; x) 172 constant? p == p.cons? 173 depth p == p.lev 174 inR? p == p.pat case ret 175 symbol? p == p.pat case sym 176 isPlus p == isTaggedOp(p, PAT_PLUS) 177 isTimes p == isTaggedOp(p, PAT_TIMES) 178 isList p == isTaggedOp(p, PAT_LIST) 179 isExpt p == (p.pat case exp => p.pat.exp; "failed") 180 isQuotient p == (p.pat case qot => p.pat.qot; "failed") 181 hasPredicate? p == not empty? predicates p 182 quoted? p == symbol? p and zero?(p.pat.sym.tag) 183 generic? p == symbol? p and bitSet?(p.pat.sym.tag, SYM_GENERIC) 184 multiple? p == symbol? p and bitSet?(p.pat.sym.tag, SYM_MULTIPLE) 185 optional? p == symbol? p and bitSet?(p.pat.sym.tag, SYM_OPTIONAL) 186 bitSet?(a, b) == And(a, b) ~= 0 187 coerce(p : %) : O == PAT2O(p.pat) 188 p1 : % ^ p2 : % == taggedElt(PAT_EXPT, [p1, p2]) 189 LPAT2O(f, l) == reduce(f, [x::O for x in l])$List(O) 190 retract(p:%):R == (inR? p => p.pat.ret; error "Not retractable") 191 convert(l : List %) : % == taggedElt(PAT_LIST, l) 192 retractIfCan(p:%):Union(R,"failed") ==(inR? p => p.pat.ret;"failed") 193 withPredicates(p, l) == setPredicates(copy p, l) 194 coerce(sy : SY) : % == patternVariable(sy, false, false, false) 195 copy p == [constant? p, patcopy(p.pat), p.lev, p.topvar, p.toppred] 196 197 -- returns [a, b] if #l = 2 and optional? a, "failed" otherwise 198 optpair l == 199 empty? rest rest l => 200 b := first rest l 201 optional?(a := first l) => l 202 optional? b => reverse l 203 "failed" 204 "failed" 205 206 incmax l == 207 1 + reduce("max", [p.lev for p in l], 0)$List(NonNegativeInteger) 208 209 p1 = p2 == 210 (p1.cons? = p2.cons?) and (p1.lev = p2.lev) and 211 (p1.topvar = p2.topvar) and 212 ((EQ(p1.toppred, p2.toppred)$Lisp) pretend B) and 213 pateq?(p1.pat, p2.pat) 214 215 isPower p == 216 (u := isTaggedOp(p, PAT_EXPT)) case "failed" => "failed" 217 [first(u::List(%)), second(u::List(%))] 218 219 taggedElt(n, l) == 220 mkPat(every?(constant?, l), [[n, dummy, l]$KER], incmax l) 221 222 elt(o, l) == 223 is?(o, POWER) and #l = 2 => first(l) ^ last(l) 224 mkPat(every?(constant?, l), [[0, o, l]$KER], incmax l) 225 226 isOp p == 227 (p.pat case ker) and zero?(p.pat.ker.tag) => 228 [p.pat.ker.op, p.pat.ker.arg] 229 "failed" 230 231 isTaggedOp(p, t) == 232 (p.pat case ker) and (p.pat.ker.tag = t) => p.pat.ker.arg 233 "failed" 234 235 if R has Monoid then 236 1 == 1::R::% 237 else 238 1 == taggedElt(PAT_ONE, empty()) 239 240 if R has AbelianMonoid then 241 0 == 0::R::% 242 else 243 0 == taggedElt(PAT_ZERO, empty()) 244 245 p : % ^ n : NonNegativeInteger == 246 p = 0 and n > 0 => 0 247 p = 1 or zero? n => 1 248 (n = 1) => p 249 mkPat(constant? p, [[p, n]$REC], 1 + (p.lev)) 250 251 p1 / p2 == 252 p2 = 1 => p1 253 mkPat(constant? p1 and constant? p2, [[p1, p2]$QOT], 254 1 + max(p1.lev, p2.lev)) 255 256 p1 + p2 == 257 p1 = 0 => p2 258 p2 = 0 => p1 259 (u1 := isPlus p1) case List(%) => 260 (u2 := isPlus p2) case List(%) => 261 taggedElt(PAT_PLUS, concat(u1::List %, u2::List %)) 262 taggedElt(PAT_PLUS, concat(u1::List %, p2)) 263 (u2 := isPlus p2) case List(%) => 264 taggedElt(PAT_PLUS, concat(p1, u2::List %)) 265 taggedElt(PAT_PLUS, [p1, p2]) 266 267 p1 * p2 == 268 p1 = 0 or p2 = 0 => 0 269 p1 = 1 => p2 270 p2 = 1 => p1 271 (u1 := isTimes p1) case List(%) => 272 (u2 := isTimes p2) case List(%) => 273 taggedElt(PAT_TIMES, concat(u1::List %, u2::List %)) 274 taggedElt(PAT_TIMES, concat(u1::List %, p2)) 275 (u2 := isTimes p2) case List(%) => 276 taggedElt(PAT_TIMES, concat(p1, u2::List %)) 277 taggedElt(PAT_TIMES, [p1, p2]) 278 279 isOp(p, o) == 280 (p.pat case ker) and zero?(p.pat.ker.tag) and (p.pat.ker.op =o) => 281 p.pat.ker.arg 282 "failed" 283 284 predicates p == 285 symbol? p => p.pat.sym.pred 286 empty() 287 288 setPredicates(p, l) == 289 generic? p => (p.pat.sym.pred := l; p) 290 error "Can only attach predicates to generic symbol" 291 292 resetBadValues p == 293 generic? p => (p.pat.sym.bad := empty()$List(Any); p) 294 error "Can only attach bad values to generic symbol" 295 296 addBadValue(p, a) == 297 generic? p => 298 if not member?(a, p.pat.sym.bad) then 299 p.pat.sym.bad := concat(a, p.pat.sym.bad) 300 p 301 error "Can only attach bad values to generic symbol" 302 303 getBadValues p == 304 generic? p => p.pat.sym.bad 305 error "Not a generic symbol" 306 307 SYM2O p == 308 sy := (p.val)::O 309 empty?(p.pred) => sy 310 paren infix(message(" | "), sy, 311 reduce("and",[sub(message("f"), i::O) for i in 1..#(p.pred)])$List(O)) 312 313 variables p == 314 constant? p => empty() 315 generic? p => [p] 316 q := p.pat 317 q case ret => empty() 318 q case exp => variables(q.exp.val) 319 q case qot => concat!(variables(q.qot.num), variables(q.qot.den)) 320 q case ker => concat [variables r for r in q.ker.arg] 321 empty() 322 323 PAT2O p == 324 p case ret => (p.ret)::O 325 p case sym => SYM2O(p.sym) 326 p case exp => (p.exp.val)::O ^ (p.exp.exponent)::O 327 p case qot => (p.qot.num)::O / (p.qot.den)::O 328 p.ker.tag = PAT_PLUS => LPAT2O("+", p.ker.arg) 329 p.ker.tag = PAT_TIMES => LPAT2O("*", p.ker.arg) 330 p.ker.tag = PAT_LIST => (p.ker.arg)::O 331 p.ker.tag = PAT_ZERO => 0::Integer::O 332 p.ker.tag = PAT_ONE => 1::Integer::O 333 l := [x::O for x in p.ker.arg]$List(O) 334 (u := display(p.ker.op)) case "failed" =>prefix(name(p.ker.op)::O,l) 335 (u::(List O -> O)) l 336 337 patcopy p == 338 p case ret => [p.ret] 339 p case sym => 340 [[p.sym.tag, p.sym.val, copy(p.sym.pred), copy(p.sym.bad)]$RSY] 341 p case ker=>[[p.ker.tag, p.ker.op, [copy x for x in p.ker.arg]]$KER] 342 p case qot => [[copy(p.qot.num), copy(p.qot.den)]$QOT] 343 [[copy(p.exp.val), p.exp.exponent]$REC] 344 345 pateq?(p1, p2) == 346 p1 case ret => (p2 case ret) and (p1.ret = p2.ret) 347 p1 case qot => 348 (p2 case qot) and (p1.qot.num = p2.qot.num) 349 and (p1.qot.den = p2.qot.den) 350 p1 case sym => 351 (p2 case sym) and (p1.sym.val = p2.sym.val) 352 and set(p1.sym.pred) =$Set(Any) set(p2.sym.pred) 353 and set(p1.sym.bad) =$Set(Any) set(p2.sym.bad) 354 p1 case ker => 355 (p2 case ker) and (p1.ker.tag = p2.ker.tag) 356 and (p1.ker.op = p2.ker.op) and (p1.ker.arg = p2.ker.arg) 357 (p2 case exp) and (p1.exp.exponent = p2.exp.exponent) 358 and (p1.exp.val = p2.exp.val) 359 360 retractIfCan(p:%):Union(SY, "failed") == 361 symbol? p => p.pat.sym.val 362 "failed" 363 364 mkrsy(t, c?, o?, m?) == 365 c? => [0, t, empty(), empty()] 366 mlt := (m? => SYM_MULTIPLE; 0) 367 opt := (o? => SYM_OPTIONAL; 0) 368 [Or(Or(SYM_GENERIC, mlt), opt), t, empty(), empty()] 369 370 patternVariable(sy, c?, o?, m?) == 371 rsy := mkrsy(sy, c?, o?, m?) 372 mkPat(zero?(rsy.tag), [rsy], 0) 373 374)abbrev package PATTERN1 PatternFunctions1 375++ Utilities for handling patterns 376++ Author: Manuel Bronstein 377++ Date Created: 28 Nov 1989 378++ Description: Tools for patterns; 379++ Keywords: pattern, matching. 380PatternFunctions1(R : SetCategory, D : Type) : with 381 suchThat : (Pattern R, D -> Boolean) -> Pattern R 382 ++ suchThat(p, f) makes a copy of p and adds the predicate 383 ++ f to the copy, which is returned. 384 suchThat : (Pattern R, List(D -> Boolean)) -> Pattern R 385 ++ \spad{suchThat(p, [f1, ..., fn])} makes a copy of p and adds the 386 ++ predicate f1 and ... and fn to the copy, which is returned. 387 suchThat : (Pattern R, List Symbol, List D -> Boolean) -> Pattern R 388 ++ \spad{suchThat(p, [a1, ..., an], f)} returns a copy of p with 389 ++ the top-level predicate set to \spad{f(a1, ..., an)}. 390 predicate : Pattern R -> (D -> Boolean) 391 ++ predicate(p) returns the predicate attached to p, the 392 ++ constant function true if p has no predicates attached to it. 393 satisfy? : (D, Pattern R) -> Boolean 394 ++ satisfy?(v, p) returns f(v) where f is the predicate 395 ++ attached to p. 396 satisfy? : (List D, Pattern R) -> Boolean 397 ++ \spad{satisfy?([v1, ..., vn], p)} returns \spad{f(v1, ..., vn)} 398 ++ where f is the 399 ++ top-level predicate attached to p. 400 addBadValue : (Pattern R, D) -> Pattern R 401 ++ addBadValue(p, v) adds v to the list of "bad values" for p; 402 ++ p is not allowed to match any of its "bad values". 403 badValues : Pattern R -> List D 404 ++ badValues(p) returns the list of "bad values" for p; 405 ++ p is not allowed to match any of its "bad values". 406 == add 407 A1D ==> AnyFunctions1(D) 408 A1 ==> AnyFunctions1(D -> Boolean) 409 A1L ==> AnyFunctions1(List D -> Boolean) 410 411 applyAll : (List Any, D) -> Boolean 412 st : (Pattern R, List Any) -> Pattern R 413 414 st(p, l) == withPredicates(p, concat(predicates p, l)) 415 predicate p == (d1 : D) : Boolean +-> applyAll(predicates p, d1) 416 addBadValue(p, v) == addBadValue(p, coerce(v)$A1D) 417 badValues p == [retract(v)$A1D for v in getBadValues p] 418 suchThat(p, l, f) == setTopPredicate(copy p, l, coerce(f)$A1L) 419 suchThat(p : Pattern R, f : D -> Boolean) == st(p, [coerce(f)$A1]) 420 satisfy?(d : D, p : Pattern R) == applyAll(predicates p, d) 421 422 satisfy?(l : List D, p : Pattern R) == 423 empty?((rec := topPredicate p).var) => true 424 retract(rec.pred)$A1L l 425 426 applyAll(l, d) == 427 for f in l repeat 428 not(retract(f)$A1 d) => return false 429 true 430 431 suchThat(p : Pattern R, l : List(D -> Boolean)) == 432 st(p, [coerce(f)$A1 for f in l]) 433 434)abbrev package PATTERN2 PatternFunctions2 435++ Lifting of maps to patterns 436++ Author: Manuel Bronstein 437++ Date Created: 28 Nov 1989 438++ Description: Lifts maps to patterns; 439++ Keywords: pattern, matching. 440PatternFunctions2(R : SetCategory, S : SetCategory) : with 441 map : (R -> S, Pattern R) -> Pattern S 442 ++ map(f, p) applies f to all the leaves of p and 443 ++ returns the result as a pattern over S. 444 == add 445 map(f, p) == 446 (r := (retractIfCan p)@Union(R, "failed")) case R => 447 f(r::R)::Pattern(S) 448 (u := isOp p) case Record(op : BasicOperator, arg : List Pattern R) => 449 ur := u::Record(op : BasicOperator, arg : List Pattern R) 450 (ur.op) [map(f, x) for x in ur.arg] 451 (v := isQuotient p) case Record(num : Pattern R, den : Pattern R) => 452 vr := v::Record(num : Pattern R, den : Pattern R) 453 map(f, vr.num) / map(f, vr.den) 454 (l := isPlus p) case List(Pattern R) => 455 reduce("+", [map(f, x) for x in l::List(Pattern R)]) 456 (l := isTimes p) case List(Pattern R) => 457 reduce("*", [map(f, x) for x in l::List(Pattern R)]) 458 (x := isPower p) case 459 Record(val : Pattern R, exponent : Pattern R) => 460 xr := x::Record(val : Pattern R, exponent : Pattern R) 461 map(f, xr.val) ^ map(f, xr.exponent) 462 (w := isExpt p) case 463 Record(val : Pattern R, exponent : NonNegativeInteger) => 464 wr := w::Record(val : Pattern R, exponent : NonNegativeInteger) 465 map(f, wr.val) ^ wr.exponent 466 sy := retract(p)@Symbol 467 setPredicates(sy::Pattern(S), copy predicates p) 468 469)abbrev category PATAB Patternable 470++ Category of sets that can be converted to useful patterns 471++ Author: Manuel Bronstein 472++ Date Created: 29 Nov 1989 473++ Description: 474++ An object S is Patternable over an object R if S can 475++ lift the conversions from R into \spadtype{Pattern(Integer)} and 476++ \spadtype{Pattern(Float)} to itself; 477++ Keywords: pattern, matching. 478Patternable(R : Type) : Category == with 479 if R has ConvertibleTo Pattern Integer then 480 ConvertibleTo Pattern Integer 481 if R has ConvertibleTo Pattern Float then 482 ConvertibleTo Pattern Float 483 484--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd. 485--All rights reserved. 486-- 487--Redistribution and use in source and binary forms, with or without 488--modification, are permitted provided that the following conditions are 489--met: 490-- 491-- - Redistributions of source code must retain the above copyright 492-- notice, this list of conditions and the following disclaimer. 493-- 494-- - Redistributions in binary form must reproduce the above copyright 495-- notice, this list of conditions and the following disclaimer in 496-- the documentation and/or other materials provided with the 497-- distribution. 498-- 499-- - Neither the name of The Numerical ALgorithms Group Ltd. nor the 500-- names of its contributors may be used to endorse or promote products 501-- derived from this software without specific prior written permission. 502-- 503--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 504--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 505--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 506--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 507--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 508--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 509--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 510--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 511--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 512--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 513--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 514