nltk.sem.drt

1 # Natural Language Toolkit: Discourse Representation Theory (DRT) 2 # 3 # Author: Dan Garrette <dhgarrette@gmail.com> 4 # 5 # Copyright (C) 2001-2011 NLTK Project 6 # URL: <http://www.nltk.org/> 7 # For license information, see LICENSE.TXT 8 9 from logic import * 10 11 # Import Tkinter-based modules if they are available 12 try: 13 from Tkinter import Canvas 14 from Tkinter import Tk 15 from tkFont import Font 16 from nltk.util import in_idle 17 18 except ImportError:

19 # No need to print a warning here, nltk.draw has already printed one. 20 pass 21 22 -class DrtTokens(Tokens):

23 DRS = 'DRS' 24 DRS_CONC = '+' 25 PRONOUN = 'PRO' 26 OPEN_BRACKET = '[' 27 CLOSE_BRACKET = ']' 28 29 PUNCT = [DRS_CONC, OPEN_BRACKET, CLOSE_BRACKET] 30 31 SYMBOLS = Tokens.SYMBOLS + PUNCT 32 33 TOKENS = Tokens.TOKENS + [DRS] + PUNCT

34

35 36 -class AbstractDrs(object):

37 """ 38 This is the base abstract DRT Expression from which every DRT 39 Expression extends. 40 """ 41

42 - def applyto(self, other):

43 return DrtApplicationExpression(self, other)

44

45 - def __neg__(self):

46 return DrtNegatedExpression(self)

47

48 - def __and__(self, other):

49 raise NotImplementedError()

50

51 - def __or__(self, other):

52 assert isinstance(other, AbstractDrs) 53 return DrtOrExpression(self, other)

54

55 - def __gt__(self, other):

56 assert isinstance(other, AbstractDrs) 57 if isinstance(self, DRS): 58 return DRS(self.refs, self.conds, other) 59 if isinstance(self, DrtConcatenation): 60 return DrtConcatenation(self.first, self.second, other) 61 raise Exception('Antecedent of implication must be a DRS')

62

63 - def equiv(self, other, prover=None):

64 """ 65 Check for logical equivalence. 66 Pass the expression (self <-> other) to the theorem prover. 67 If the prover says it is valid, then the self and other are equal. 68 69 @param other: an C{AbstractDrs} to check equality against 70 @param prover: a C{nltk.inference.api.Prover} 71 """ 72 assert isinstance(other, AbstractDrs) 73 74 f1 = self.simplify().fol(); 75 f2 = other.simplify().fol(); 76 return f1.equiv(f2, prover)

77

78 - def _get_type(self):

79 raise AttributeError("'%s' object has no attribute 'type'" % 80 self.__class__.__name__)

81 type = property(_get_type) 82

83 - def typecheck(self, signature=None):

84 raise NotImplementedError()

85

86 - def __add__(self, other):

87 return DrtConcatenation(self, other, None)

88

89 - def get_refs(self, recursive=False):

90 """ 91 Return the set of discourse referents in this DRS. 92 @param recursive: C{boolean} Also find discourse referents in subterms? 93 @return: C{list} of C{Variable}s 94 """ 95 raise NotImplementedError()

96

97 - def is_pronoun_function(self):

98 """ Is self of the form "PRO(x)"? """ 99 return isinstance(self, DrtApplicationExpression) and \ 100 isinstance(self.function, DrtAbstractVariableExpression) and \ 101 self.function.variable.name == DrtTokens.PRONOUN and \ 102 isinstance(self.argument, DrtIndividualVariableExpression)

103

104 - def make_EqualityExpression(self, first, second):

105 return DrtEqualityExpression(first, second)

106

107 - def make_VariableExpression(self, variable):

108 return DrtVariableExpression(variable)

109

110 - def resolve_anaphora(self):

111 return resolve_anaphora(self)

112

113 - def eliminate_equality(self):

114 def combinator(a, *additional): 115 if len(additional) == 0: 116 return self.__class__(a) 117 elif len(additional) == 1: 118 return self.__class__(a, additional[0])

119 120 return self.visit(lambda e: isinstance(e,Variable) 121 and e or e.eliminate_equality(), combinator, set())

122 123

124 - def pprint(self):

125 """ 126 Draw the DRS 127 """ 128 print self.pretty()

129

130 - def pretty(self):

131 """ 132 Draw the DRS 133 @return: the pretty print string 134 """ 135 return '\n'.join(self._pretty())

136

137 - def draw(self):

138 DrsDrawer(self).draw()

139

140 141 -class DRS(AbstractDrs, Expression):

142 """A Discourse Representation Structure."""

143 - def __init__(self, refs, conds, consequent=None):

144 """ 145 @param refs: C{list} of C{DrtIndividualVariableExpression} for the 146 discourse referents 147 @param conds: C{list} of C{Expression} for the conditions 148 """ 149 self.refs = refs 150 self.conds = conds 151 self.consequent = consequent

152

153 - def replace(self, variable, expression, replace_bound=False, alpha_convert=True):

154 """Replace all instances of variable v with expression E in self, 155 where v is free in self.""" 156 if variable in self.refs: 157 #if a bound variable is the thing being replaced 158 if not replace_bound: 159 return self 160 else: 161 i = self.refs.index(variable) 162 if self.consequent: 163 consequent = self.consequent.replace(variable, expression, True, alpha_convert) 164 else: 165 consequent = None 166 return DRS(self.refs[:i]+[expression.variable]+self.refs[i+1:], 167 [cond.replace(variable, expression, True, alpha_convert) 168 for cond in self.conds], 169 consequent) 170 else: 171 if alpha_convert: 172 # any bound variable that appears in the expression must 173 # be alpha converted to avoid a conflict 174 for ref in (set(self.refs) & expression.free()): 175 newvar = unique_variable(ref) 176 newvarex = DrtVariableExpression(newvar) 177 i = self.refs.index(ref) 178 if self.consequent: 179 consequent = self.consequent.replace(ref, newvarex, True, alpha_convert) 180 else: 181 consequent = None 182 self = DRS(self.refs[:i]+[newvar]+self.refs[i+1:], 183 [cond.replace(ref, newvarex, True, alpha_convert) 184 for cond in self.conds], 185 consequent) 186 187 #replace in the conditions 188 if self.consequent: 189 consequent = self.consequent.replace(variable, expression, replace_bound, alpha_convert) 190 else: 191 consequent = None 192 return DRS(self.refs, 193 [cond.replace(variable, expression, replace_bound, alpha_convert) 194 for cond in self.conds], 195 consequent)

196

197 - def variables(self):

198 """@see: Expression.variables()""" 199 conds_vars = reduce(operator.or_, 200 [c.variables() for c in self.conds], set()) 201 if self.consequent: 202 conds_vars.update(self.consequent.variables()) 203 return conds_vars - set(self.refs)

204

205 - def free(self, indvar_only=True):

206 """@see: Expression.free()""" 207 conds_free = reduce(operator.or_, 208 [c.free(indvar_only) for c in self.conds], set()) 209 if self.consequent: 210 conds_free.update(self.consequent.free()) 211 return conds_free - set(self.refs)

212

213 - def get_refs(self, recursive=False):

214 """@see: AbstractExpression.get_refs()""" 215 if recursive: 216 conds_refs = self.refs + sum((c.get_refs(True) for c in self.conds), []) 217 if self.consequent: 218 conds_refs.extend(self.consequent.get_refs(True)) 219 return conds_refs 220 else: 221 return self.refs

222

223 - def visit(self, function, combinator, default):

224 """@see: Expression.visit()""" 225 parts = self.refs + self.conds 226 if self.consequent: 227 parts.append(self.consequent) 228 return reduce(combinator, map(function, parts), default)

229

230 - def eliminate_equality(self):

231 drs = self 232 i = 0 233 while i < len(drs.conds): 234 cond = drs.conds[i] 235 if isinstance(cond, EqualityExpression) and \ 236 isinstance(cond.first, AbstractVariableExpression) and \ 237 isinstance(cond.second, AbstractVariableExpression): 238 drs = DRS(list(set(drs.refs)-set([cond.second.variable])), 239 drs.conds[:i]+drs.conds[i+1:], 240 drs.consequent) 241 if cond.second.variable != cond.first.variable: 242 drs = drs.replace(cond.second.variable, cond.first, False, False) 243 i = 0 244 i -= 1 245 i += 1 246 247 conds = [] 248 for cond in drs.conds: 249 new_cond = cond.eliminate_equality() 250 new_cond_simp = new_cond.simplify() 251 if not isinstance(new_cond_simp, DRS) or \ 252 new_cond_simp.refs or new_cond_simp.conds or \ 253 new_cond_simp.consequent: 254 conds.append(new_cond) 255 if drs.consequent: 256 consequent = drs.consequent.eliminate_equality() 257 else: 258 consequent = None 259 return DRS(drs.refs, conds, consequent)

260

261 - def simplify(self):

262 if self.consequent: 263 consequent = self.consequent.simplify() 264 else: 265 consequent = None 266 return DRS(self.refs, 267 [cond.simplify() for cond in self.conds], 268 consequent)

269

270 - def fol(self):

271 if self.consequent: 272 accum = None 273 if self.conds: 274 accum = reduce(AndExpression, [c.fol() for c in self.conds]) 275 276 if accum: 277 accum = ImpExpression(accum, self.consequent.fol()) 278 else: 279 accum = self.consequent.fol() 280 281 for ref in self.refs[::-1]: 282 accum = AllExpression(ref, accum) 283 284 return accum 285 286 else: 287 if not self.conds: 288 raise Exception("Cannot convert DRS with no conditions to FOL.") 289 accum = reduce(AndExpression, [c.fol() for c in self.conds]) 290 for ref in map(Variable, self._order_ref_strings(self.refs)[::-1]): 291 accum = ExistsExpression(ref, accum) 292 return accum

293

294 - def _pretty(self):

295 refs_line = ' '.join(self._order_ref_strings(self.refs)) 296 cond_lines = sum([filter(str.strip, cond._pretty()) for cond in self.conds], []) 297 length = max([len(refs_line)] + map(len, cond_lines)) 298 drs = [' _' + '_'*length + '_ ', 299 '| ' + refs_line + ' '*(length-len(refs_line)) + ' |', 300 '|-' + '-'*length + '-|'] + \ 301 ['| ' + line + ' '*(length-len(line)) + ' |' for line in cond_lines] + \ 302 ['|_' + '_'*length + '_|'] 303 if self.consequent: 304 return DrtBinaryExpression._assemble_pretty(drs, DrtTokens.IMP, 305 self.consequent._pretty()) 306 return drs

307

308 - def _order_ref_strings(self, refs):

309 strings = map(str, refs) 310 ind_vars = [] 311 func_vars = [] 312 event_vars = [] 313 other_vars = [] 314 for s in strings: 315 if is_indvar(s): 316 ind_vars.append(s) 317 elif is_funcvar(s): 318 func_vars.append(s) 319 elif is_eventvar(s): 320 event_vars.append(s) 321 else: 322 other_vars.append(s) 323 return sorted(other_vars) + \ 324 sorted(event_vars, key=lambda v: int([v[2:],-1][len(v[2:]) == 0])) + \ 325 sorted(func_vars, key=lambda v: (v[0], int([v[1:],-1][len(v[1:])==0]))) + \ 326 sorted(ind_vars, key=lambda v: (v[0], int([v[1:],-1][len(v[1:])==0])))

327

328 - def __eq__(self, other):

329 r"""Defines equality modulo alphabetic variance. 330 If we are comparing \x.M and \y.N, then check equality of M and N[x/y].""" 331 if isinstance(other, DRS): 332 if len(self.refs) == len(other.refs): 333 converted_other = other 334 for (r1, r2) in zip(self.refs, converted_other.refs): 335 varex = self.make_VariableExpression(r1) 336 converted_other = converted_other.replace(r2, varex, True) 337 if self.consequent == converted_other.consequent and \ 338 len(self.conds) == len(converted_other.conds): 339 for c1, c2 in zip(self.conds, converted_other.conds): 340 if not (c1 == c2): 341 return False 342 return True 343 return False

344

345 - def __str__(self):

346 drs = '([%s],[%s])' % (','.join(self._order_ref_strings(self.refs)), 347 ', '.join(map(str, self.conds))) 348 if self.consequent: 349 return DrtTokens.OPEN + drs + ' ' + DrtTokens.IMP + ' ' + \ 350 str(self.consequent) + DrtTokens.CLOSE 351 return drs

352

353 354 -def DrtVariableExpression(variable):

355 """ 356 This is a factory method that instantiates and returns a subtype of 357 C{DrtAbstractVariableExpression} appropriate for the given variable. 358 """ 359 if is_indvar(variable.name): 360 return DrtIndividualVariableExpression(variable) 361 elif is_funcvar(variable.name): 362 return DrtFunctionVariableExpression(variable) 363 elif is_eventvar(variable.name): 364 return DrtEventVariableExpression(variable) 365 else: 366 return DrtConstantExpression(variable)

367

368 369 -class DrtAbstractVariableExpression(AbstractDrs, AbstractVariableExpression):

370 - def fol(self):

371 return self

372

373 - def get_refs(self, recursive=False):

374 """@see: AbstractExpression.get_refs()""" 375 return []

376

377 - def _pretty(self):

378 s = str(self) 379 blank = ' '*len(s) 380 return [blank, blank, s, blank]

381

382 -class DrtIndividualVariableExpression(DrtAbstractVariableExpression, IndividualVariableExpression):

383 pass

384

385 -class DrtFunctionVariableExpression(DrtAbstractVariableExpression, FunctionVariableExpression):

386 pass

387

388 -class DrtEventVariableExpression(DrtIndividualVariableExpression, EventVariableExpression):

389 pass

390

391 -class DrtConstantExpression(DrtAbstractVariableExpression, ConstantExpression):

392 pass

393

394 395 -class DrtProposition(AbstractDrs, Expression):

396 - def __init__(self, variable, drs):

397 self.variable = variable 398 self.drs = drs

399

400 - def replace(self, variable, expression, replace_bound=False, alpha_convert=True):

401 if self.variable == variable: 402 assert isinstance(expression, DrtAbstractVariableExpression), "Can only replace a proposition label with a variable" 403 return DrtProposition(expression.variable, self.drs.replace(variable, expression, replace_bound, alpha_convert)) 404 else: 405 return DrtProposition(self.variable, self.drs.replace(variable, expression, replace_bound, alpha_convert))

406

407 - def eliminate_equality(self):

408 return DrtProposition(self.variable, self.drs.eliminate_equality())

409

410 - def simplify(self):

411 return DrtProposition(self.variable, self.drs.simplify())

412

413 - def get_refs(self, recursive=False):

414 if recursive: 415 return self.drs.get_refs(True) 416 else: 417 return []

418

419 - def __eq__(self, other):

420 return self.__class__ == other.__class__ and \ 421 self.variable == other.variable and \ 422 self.drs == other.drs

423

424 - def fol(self):

425 return self.drs.fol()

426

427 - def _pretty(self):

428 drs_s = self.drs._pretty() 429 blank = ' '*(len(str(self.variable))+1) 430 return [blank + drs_s[0], 431 str(self.variable) + ':' + drs_s[1]] + \ 432 map(lambda l: blank+l, drs_s[2:])

433

434 - def visit(self, function, combinator, default):

435 return combinator(function(self.variable), function(self.drs))

436

437 - def __str__(self):

438 return 'prop(%s, %s)' % (self.variable, self.drs)

439

440 441 -class DrtNegatedExpression(AbstractDrs, NegatedExpression):

442 - def fol(self):

443 return NegatedExpression(self.term.fol())

444

445 - def get_refs(self, recursive=False):

446 """@see: AbstractExpression.get_refs()""" 447 return self.term.get_refs(recursive)

448

449 - def _pretty(self):

450 term_lines = self.term._pretty() 451 return [' ' + line for line in term_lines[:2]] + \ 452 ['__ ' + term_lines[2]] + \ 453 [' | ' + term_lines[3]] + \ 454 [' ' + line for line in term_lines[4:]]

455

456 -class DrtLambdaExpression(AbstractDrs, LambdaExpression):

457 - def alpha_convert(self, newvar):

458 """Rename all occurrences of the variable introduced by this variable 459 binder in the expression to @C{newvar}. 460 @param newvar: C{Variable}, for the new variable 461 """ 462 return self.__class__(newvar, self.term.replace(self.variable, 463 DrtVariableExpression(newvar), True))

464

465 - def fol(self):

466 return LambdaExpression(self.variable, self.term.fol())

467

468 - def _pretty(self):

469 variables = [self.variable] 470 term = self.term 471 while term.__class__ == self.__class__: 472 variables.append(term.variable) 473 term = term.term 474 var_string = ' '.join(map(str, variables)) + DrtTokens.DOT 475 term_lines = term._pretty() 476 return [' ' + ' '*len(var_string) + line for line in term_lines[:1]] + \ 477 [' \ ' + ' '*len(var_string) + term_lines[1]] + \ 478 [' /\ ' + var_string + term_lines[2]] + \ 479 [' ' + ' '*len(var_string) + line for line in term_lines[3:]]

480

481 -class DrtBinaryExpression(AbstractDrs, BinaryExpression):

482 - def get_refs(self, recursive=False):

483 """@see: AbstractExpression.get_refs()""" 484 if recursive: 485 return self.first.get_refs(True) + self.second.get_refs(True) 486 else: 487 return []

488

489 - def _pretty(self):

490 return DrtBinaryExpression._assemble_pretty(self._pretty_subex(self.first), self.getOp(), self._pretty_subex(self.second))

491 492 @staticmethod

493 - def _assemble_pretty(first_lines, op, second_lines):

494 max_lines = max(len(first_lines), len(second_lines)) 495 first_lines = first_lines + [' '*len(first_lines[0])]*(max_lines-len(first_lines)) 496 second_lines = second_lines + [' '*len(second_lines[0])]*(max_lines-len(second_lines)) 497 return [' ' + first_line + ' ' + ' '*len(op) + ' ' + second_line + ' ' for first_line, second_line in zip(first_lines, second_lines)[:2]] + \ 498 ['(' + first_lines[2] + ' ' + op + ' ' + second_lines[2] + ')'] + \ 499 [' ' + first_line + ' ' + ' '*len(op) + ' ' + second_line + ' ' for first_line, second_line in zip(first_lines, second_lines)[3:]]

500

501 - def _pretty_subex(self, subex):

502 return subex._pretty()

503

504 -class DrtBooleanExpression(DrtBinaryExpression, BooleanExpression):

505 pass

506

507 -class DrtOrExpression(DrtBooleanExpression, OrExpression):

508 - def fol(self):

509 return OrExpression(self.first.fol(), self.second.fol())

510

511 - def _pretty_subex(self, subex):

512 if isinstance(subex, DrtOrExpression): 513 return [line[1:-1] for line in subex._pretty()] 514 return DrtBooleanExpression._pretty_subex(self, subex)

515

516 -class DrtEqualityExpression(DrtBinaryExpression, EqualityExpression):

517 - def fol(self):

518 return EqualityExpression(self.first.fol(), self.second.fol())

519

520 -class DrtConcatenation(DrtBooleanExpression):

521 """DRS of the form '(DRS + DRS)'"""

522 - def __init__(self, first, second, consequent=None):

523 DrtBooleanExpression.__init__(self, first, second) 524 self.consequent = consequent

525

526 - def replace(self, variable, expression, replace_bound=False, alpha_convert=True):

527 """Replace all instances of variable v with expression E in self, 528 where v is free in self.""" 529 first = self.first 530 second = self.second 531 consequent = self.consequent 532 533 # If variable is bound 534 if variable in self.get_refs(): 535 if replace_bound: 536 first = first.replace(variable, expression, replace_bound, alpha_convert) 537 second = second.replace(variable, expression, replace_bound, alpha_convert) 538 if consequent: 539 consequent = consequent.replace(variable, expression, replace_bound, alpha_convert) 540 else: 541 if alpha_convert: 542 # alpha convert every ref that is free in 'expression' 543 for ref in (set(self.get_refs(True)) & expression.free()): 544 v = DrtVariableExpression(unique_variable(ref)) 545 first = first.replace(ref, v, True, alpha_convert) 546 second = second.replace(ref, v, True, alpha_convert) 547 if consequent: 548 consequent = consequent.replace(ref, v, True, alpha_convert) 549 550 first = first.replace(variable, expression, replace_bound, alpha_convert) 551 second = second.replace(variable, expression, replace_bound, alpha_convert) 552 if consequent: 553 consequent = consequent.replace(variable, expression, replace_bound, alpha_convert) 554 555 return self.__class__(first, second, consequent)

556

557 - def eliminate_equality(self):

558 #TODO: at some point. for now, simplify. 559 drs = self.simplify() 560 assert not isinstance(drs, DrtConcatenation) 561 return drs.eliminate_equality()

562

563 - def simplify(self):

564 first = self.first.simplify() 565 second = self.second.simplify() 566 if self.consequent: 567 consequent = self.consequent.simplify() 568 else: 569 consequent = None 570 571 if isinstance(first, DRS) and isinstance(second, DRS): 572 # For any ref that is in both 'first' and 'second' 573 for ref in (set(first.get_refs(True)) & set(second.get_refs(True))): 574 # alpha convert the ref in 'second' to prevent collision 575 newvar = DrtVariableExpression(unique_variable(ref)) 576 second = second.replace(ref, newvar, True) 577 578 return DRS(first.refs + second.refs, first.conds + second.conds, consequent) 579 else: 580 return self.__class__(first, second, consequent)

581

582 - def get_refs(self, recursive=False):

583 """@see: AbstractExpression.get_refs()""" 584 refs = self.first.get_refs(recursive) + self.second.get_refs(recursive) 585 if self.consequent and recursive: 586 refs.extend(self.consequent.get_refs(True)) 587 return refs

588

589 - def getOp(self):

590 return DrtTokens.DRS_CONC

591

592 - def __eq__(self, other):

593 r"""Defines equality modulo alphabetic variance. 594 If we are comparing \x.M and \y.N, then check equality of M and N[x/y].""" 595 if isinstance(other, DrtConcatenation): 596 self_refs = self.get_refs() 597 other_refs = other.get_refs() 598 if len(self_refs) == len(other_refs): 599 converted_other = other 600 for (r1,r2) in zip(self_refs, other_refs): 601 varex = self.make_VariableExpression(r1) 602 converted_other = converted_other.replace(r2, varex, True) 603 return self.first == converted_other.first and \ 604 self.second == converted_other.second and \ 605 self.consequent == converted_other.consequent 606 return False

607

608 - def fol(self):

609 e = AndExpression(self.first.fol(), self.second.fol()) 610 if self.consequent: 611 e = ImpExpression(e, self.consequent.fol()) 612 return e

613

614 - def _pretty(self):

615 drs = DrtBinaryExpression._assemble_pretty(self._pretty_subex(self.first), 616 self.getOp(), 617 self._pretty_subex(self.second)) 618 if self.consequent: 619 drs = DrtBinaryExpression._assemble_pretty(drs, DrtTokens.IMP, 620 self._pretty(self.consequent)) 621 return drs

622

623 - def _pretty_subex(self, subex):

624 if isinstance(subex, DrtConcatenation): 625 return [line[1:-1] for line in subex._pretty()] 626 return DrtBooleanExpression._pretty_subex(self, subex)

627 628

629 - def visit(self, function, combinator, default):

630 """@see: Expression.visit()""" 631 if self.consequent: 632 return combinator(function(self.first), function(self.second), function(self.consequent)) 633 else: 634 return combinator(function(self.first), function(self.second))

635

636 - def __str__(self):

637 first = self._str_subex(self.first) 638 second = self._str_subex(self.second) 639 drs = Tokens.OPEN + first + ' ' + self.getOp() \ 640 + ' ' + second + Tokens.CLOSE 641 if self.consequent: 642 return DrtTokens.OPEN + drs + ' ' + DrtTokens.IMP + ' ' + \ 643 str(self.consequent) + DrtTokens.CLOSE 644 return drs

645

646 - def _str_subex(self, subex):

647 s = str(subex) 648 if isinstance(subex, DrtConcatenation) and subex.consequent is None: 649 return s[1:-1] 650 return s

651

652 653 -class DrtApplicationExpression(AbstractDrs, ApplicationExpression):

654 - def fol(self):

655 return ApplicationExpression(self.function.fol(), self.argument.fol())

656

657 - def get_refs(self, recursive=False):

658 """@see: AbstractExpression.get_refs()""" 659 if recursive: 660 return self.function.get_refs(True) + self.argument.get_refs(True) 661 else: 662 return []

663

664 - def _pretty(self):

665 function, args = self.uncurry() 666 function_lines = function._pretty() 667 args_lines = [arg._pretty() for arg in args] 668 max_lines = max(map(len, [function_lines] + args_lines)) 669 function_lines = function_lines + [' '*len(function_lines[0])]*(max_lines-len(function_lines)) 670 args_lines = [arg_lines + [' '*len(arg_lines[0])]*(max_lines-len(arg_lines)) for arg_lines in args_lines] 671 return [func_line + ' ' + ' '.join(args_line) + ' ' for func_line, args_line in zip(function_lines, zip(*args_lines))[:2]] + \ 672 [function_lines[2] + '(' + ','.join(zip(*args_lines)[2]) + ')'] + \ 673 [func_line + ' ' + ' '.join(args_line) + ' ' for func_line, args_line in zip(function_lines, zip(*args_lines))[3:]]

674

675 -class PossibleAntecedents(list, AbstractDrs, Expression):

676 - def free(self, indvar_only=True):

677 """Set of free variables.""" 678 return set(self)

679

680 - def replace(self, variable, expression, replace_bound=False, alpha_convert=True):

681 """Replace all instances of variable v with expression E in self, 682 where v is free in self.""" 683 result = PossibleAntecedents() 684 for item in self: 685 if item == variable: 686 self.append(expression) 687 else: 688 self.append(item) 689 return result

690

691 - def _pretty(self):

692 s = str(self) 693 blank = ' '*len(s) 694 return [blank,blank,s]

695

696 - def __str__(self):

697 return '[' + ','.join(map(str, self)) + ']'

698

699 700 -class AnaphoraResolutionException(Exception):

701 pass

702

703 704 -def resolve_anaphora(expression, trail=[]):

705 if isinstance(expression, ApplicationExpression): 706 if expression.is_pronoun_function(): 707 possible_antecedents = PossibleAntecedents() 708 for ancestor in trail: 709 for ref in ancestor.get_refs(): 710 refex = expression.make_VariableExpression(ref) 711 712 #========================================================== 713 # Don't allow resolution to itself or other types 714 #========================================================== 715 if refex.__class__ == expression.argument.__class__ and \ 716 not (refex == expression.argument): 717 possible_antecedents.append(refex) 718 719 if len(possible_antecedents) == 1: 720 resolution = possible_antecedents[0] 721 else: 722 resolution = possible_antecedents 723 return expression.make_EqualityExpression(expression.argument, resolution) 724 else: 725 r_function = resolve_anaphora(expression.function, trail + [expression]) 726 r_argument = resolve_anaphora(expression.argument, trail + [expression]) 727 return expression.__class__(r_function, r_argument) 728 729 elif isinstance(expression, DRS): 730 r_conds = [] 731 for cond in expression.conds: 732 r_cond = resolve_anaphora(cond, trail + [expression]) 733 734 # if the condition is of the form '(x = [])' then raise exception 735 if isinstance(r_cond, EqualityExpression): 736 if isinstance(r_cond.first, PossibleAntecedents): 737 #Reverse the order so that the variable is on the left 738 temp = r_cond.first 739 r_cond.first = r_cond.second 740 r_cond.second = temp 741 if isinstance(r_cond.second, PossibleAntecedents): 742 if not r_cond.second: 743 raise AnaphoraResolutionException("Variable '%s' does not " 744 "resolve to anything." % r_cond.first) 745 746 r_conds.append(r_cond) 747 if expression.consequent: 748 consequent = resolve_anaphora(expression.consequent, trail + [expression]) 749 else: 750 consequent = None 751 return expression.__class__(expression.refs, r_conds, consequent) 752 753 elif isinstance(expression, AbstractVariableExpression): 754 return expression 755 756 elif isinstance(expression, NegatedExpression): 757 return expression.__class__(resolve_anaphora(expression.term, trail + [expression])) 758 759 elif isinstance(expression, DrtConcatenation): 760 if expression.consequent: 761 consequent = resolve_anaphora(expression.consequent, trail + [expression]) 762 else: 763 consequent = None 764 return expression.__class__(resolve_anaphora(expression.first, trail + [expression]), 765 resolve_anaphora(expression.second, trail + [expression]), 766 consequent) 767 768 elif isinstance(expression, BinaryExpression): 769 return expression.__class__(resolve_anaphora(expression.first, trail + [expression]), 770 resolve_anaphora(expression.second, trail + [expression])) 771 772 elif isinstance(expression, LambdaExpression): 773 return expression.__class__(expression.variable, resolve_anaphora(expression.term, trail + [expression]))

774

775 776 -class DrsDrawer(object):

777 BUFFER = 3 #Space between elements 778 TOPSPACE = 10 #Space above whole DRS 779 OUTERSPACE = 6 #Space to the left, right, and bottom of the whle DRS 780

781 - def __init__(self, drs, size_canvas=True, canvas=None):

782 """ 783 @param drs: C{AbstractDrs}, The DRS to be drawn 784 @param size_canvas: C{boolean}, True if the canvas size should be the exact size of the DRS 785 @param canvas: C{Canvas} The canvas on which to draw the DRS. If none is given, create a new canvas. 786 """ 787 master = None 788 if not canvas: 789 master = Tk() 790 master.title("DRT") 791 792 font = Font(family='helvetica', size=12) 793 794 if size_canvas: 795 canvas = Canvas(master, width=0, height=0) 796 canvas.font = font 797 self.canvas = canvas 798 (right, bottom) = self._visit(drs, self.OUTERSPACE, self.TOPSPACE) 799 800 width = max(right+self.OUTERSPACE, 100) 801 height = bottom+self.OUTERSPACE 802 canvas = Canvas(master, width=width, height=height)#, bg='white') 803 else: 804 canvas = Canvas(master, width=300, height=300) 805 806 canvas.pack() 807 canvas.font = font 808 809 self.canvas = canvas 810 self.drs = drs 811 self.master = master

812

813 - def _get_text_height(self):

814 """Get the height of a line of text""" 815 return self.canvas.font.metrics("linespace")

816

817 - def draw(self, x=OUTERSPACE, y=TOPSPACE):

818 """Draw the DRS""" 819 self._handle(self.drs, self._draw_command, x, y) 820 821 if self.master and not in_idle(): 822 self.master.mainloop() 823 else: 824 return self._visit(self.drs, x, y)

825

826 - def _visit(self, expression, x, y):

827 """ 828 Return the bottom-rightmost point without actually drawing the item 829 830 @param expression: the item to visit 831 @param x: the top of the current drawing area 832 @param y: the left side of the current drawing area 833 @return: the bottom-rightmost point 834 """ 835 return self._handle(expression, self._visit_command, x, y)

836

837 - def _draw_command(self, item, x, y):

838 """ 839 Draw the given item at the given location 840 841 @param item: the item to draw 842 @param x: the top of the current drawing area 843 @param y: the left side of the current drawing area 844 @return: the bottom-rightmost point 845 """ 846 if isinstance(item, str): 847 self.canvas.create_text(x, y, anchor='nw', font=self.canvas.font, text=item) 848 elif isinstance(item, tuple): 849 # item is the lower-right of a box 850 (right, bottom) = item 851 self.canvas.create_rectangle(x, y, right, bottom) 852 horiz_line_y = y + self._get_text_height() + (self.BUFFER * 2) #the line separating refs from conds 853 self.canvas.create_line(x, horiz_line_y, right, horiz_line_y) 854 855 return self._visit_command(item, x, y)

856

857 - def _visit_command(self, item, x, y):

858 """ 859 Return the bottom-rightmost point without actually drawing the item 860 861 @param item: the item to visit 862 @param x: the top of the current drawing area 863 @param y: the left side of the current drawing area 864 @return: the bottom-rightmost point 865 """ 866 if isinstance(item, str): 867 return (x + self.canvas.font.measure(item), y + self._get_text_height()) 868 elif isinstance(item, tuple): 869 return item

870

871 - def _handle(self, expression, command, x=0, y=0):

872 """ 873 @param expression: the expression to handle 874 @param command: the function to apply, either _draw_command or _visit_command 875 @param x: the top of the current drawing area 876 @param y: the left side of the current drawing area 877 @return: the bottom-rightmost point 878 """ 879 if command == self._visit_command: 880 #if we don't need to draw the item, then we can use the cached values 881 try: 882 #attempt to retrieve cached values 883 right = expression._drawing_width + x 884 bottom = expression._drawing_height + y 885 return (right, bottom) 886 except AttributeError: 887 #the values have not been cached yet, so compute them 888 pass 889 890 if isinstance(expression, DrtAbstractVariableExpression): 891 factory = self._handle_VariableExpression 892 elif isinstance(expression, DRS): 893 factory = self._handle_DRS 894 elif isinstance(expression, DrtNegatedExpression): 895 factory = self._handle_NegatedExpression 896 elif isinstance(expression, DrtLambdaExpression): 897 factory = self._handle_LambdaExpression 898 elif isinstance(expression, BinaryExpression): 899 factory = self._handle_BinaryExpression 900 elif isinstance(expression, DrtApplicationExpression): 901 factory = self._handle_ApplicationExpression 902 elif isinstance(expression, PossibleAntecedents): 903 factory = self._handle_VariableExpression 904 elif isinstance(expression, DrtProposition): 905 factory = self._handle_DrtProposition 906 else: 907 raise Exception, expression.__class__.__name__ 908 909 (right, bottom) = factory(expression, command, x, y) 910 911 #cache the values 912 expression._drawing_width = right - x 913 expression._drawing_height = bottom - y 914 915 return (right, bottom)

916

917 - def _handle_VariableExpression(self, expression, command, x, y):

918 return command(str(expression), x, y)

919

920 - def _handle_NegatedExpression(self, expression, command, x, y):

921 # Find the width of the negation symbol 922 right = self._visit_command(DrtTokens.NOT, x, y)[0] 923 924 # Handle term 925 (right, bottom) = self._handle(expression.term, command, right, y) 926 927 # Handle variables now that we know the y-coordinate 928 command(DrtTokens.NOT, x, self._get_centered_top(y, bottom - y, self._get_text_height())) 929 930 return (right, bottom)

931

932 - def _handle_DRS(self, expression, command, x, y):

933 left = x + self.BUFFER #indent the left side 934 bottom = y + self.BUFFER #indent the top 935 936 # Handle Discourse Referents 937 if expression.refs: 938 refs = ' '.join(map(str, expression.refs)) 939 else: 940 refs = ' ' 941 (max_right, bottom) = command(refs, left, bottom) 942 bottom += (self.BUFFER * 2) 943 944 # Handle Conditions 945 if expression.conds: 946 for cond in expression.conds: 947 (right, bottom) = self._handle(cond, command, left, bottom) 948 max_right = max(max_right, right) 949 bottom += self.BUFFER 950 else: 951 bottom += self._get_text_height() + self.BUFFER 952 953 # Handle Box 954 max_right += self.BUFFER 955 return command((max_right, bottom), x, y)

956

957 - def _handle_ApplicationExpression(self, expression, command, x, y):

958 function, args = expression.uncurry() 959 if not isinstance(function, DrtAbstractVariableExpression): 960 #It's not a predicate expression ("P(x,y)"), so leave arguments curried 961 function = expression.function 962 args = [expression.argument] 963 964 # Get the max bottom of any element on the line 965 function_bottom = self._visit(function, x, y)[1] 966 max_bottom = max([function_bottom] + [self._visit(arg, x, y)[1] for arg in args]) 967 968 line_height = max_bottom - y 969 970 # Handle 'function' 971 function_drawing_top = self._get_centered_top(y, line_height, function._drawing_height) 972 right = self._handle(function, command, x, function_drawing_top)[0] 973 974 # Handle open paren 975 centred_string_top = self._get_centered_top(y, line_height, self._get_text_height()) 976 right = command(DrtTokens.OPEN, right, centred_string_top)[0] 977 978 # Handle each arg 979 for (i,arg) in enumerate(args): 980 arg_drawing_top = self._get_centered_top(y, line_height, arg._drawing_height) 981 right = self._handle(arg, command, right, arg_drawing_top)[0] 982 983 if i+1 < len(args): 984 #since it's not the last arg, add a comma 985 right = command(DrtTokens.COMMA + ' ', right, centred_string_top)[0] 986 987 # Handle close paren 988 right = command(DrtTokens.CLOSE, right, centred_string_top)[0] 989 990 return (right, max_bottom)

991

992 - def _handle_LambdaExpression(self, expression, command, x, y):

993 # Find the width of the lambda symbol and abstracted variables 994 variables = DrtTokens.LAMBDA + str(expression.variable) + DrtTokens.DOT 995 right = self._visit_command(variables, x, y)[0] 996 997 # Handle term 998 (right, bottom) = self._handle(expression.term, command, right, y) 999 1000 # Handle variables now that we know the y-coordinate 1001 command(variables, x, self._get_centered_top(y, bottom - y, self._get_text_height())) 1002 1003 return (right, bottom)

1004

1005 - def _handle_BinaryExpression(self, expression, command, x, y):

1006 # Get the full height of the line, based on the operands 1007 first_height = self._visit(expression.first, 0, 0)[1] 1008 second_height = self._visit(expression.second, 0, 0)[1] 1009 line_height = max(first_height, second_height) 1010 1011 # Handle open paren 1012 centred_string_top = self._get_centered_top(y, line_height, self._get_text_height()) 1013 right = command(DrtTokens.OPEN, x, centred_string_top)[0] 1014 1015 # Handle the first operand 1016 first_height = expression.first._drawing_height 1017 (right, first_bottom) = self._handle(expression.first, command, right, self._get_centered_top(y, line_height, first_height)) 1018 1019 # Handle the operator 1020 right = command(' %s ' % expression.getOp(), right, centred_string_top)[0] 1021 1022 # Handle the second operand 1023 second_height = expression.second._drawing_height 1024 (right, second_bottom) = self._handle(expression.second, command, right, self._get_centered_top(y, line_height, second_height)) 1025 1026 # Handle close paren 1027 right = command(DrtTokens.CLOSE, right, centred_string_top)[0] 1028 1029 return (right, max(first_bottom, second_bottom))

1030

1031 - def _handle_DrtProposition(self, expression, command, x, y):

1032 # Find the width of the negation symbol 1033 right = command(expression.variable, x, y)[0] 1034 1035 # Handle term 1036 (right, bottom) = self._handle(expression.term, command, right, y) 1037 1038 return (right, bottom)

1039

1040 - def _get_centered_top(self, top, full_height, item_height):

1041 """Get the y-coordinate of the point that a figure should start at if 1042 its height is 'item_height' and it needs to be centered in an area that 1043 starts at 'top' and is 'full_height' tall.""" 1044 return top + (full_height - item_height) / 2

1045

1046 1047 -class DrtParser(LogicParser):

1048 """A lambda calculus expression parser."""

1049 - def __init__(self):

1050 LogicParser.__init__(self) 1051 1052 self.operator_precedence = dict( 1053 [(x,1) for x in DrtTokens.LAMBDA_LIST] + \ 1054 [(x,2) for x in DrtTokens.NOT_LIST] + \ 1055 [(APP,3)] + \ 1056 [(x,4) for x in DrtTokens.EQ_LIST+Tokens.NEQ_LIST] + \ 1057 [(DrtTokens.DRS_CONC,5)] + \ 1058 [(x,6) for x in DrtTokens.OR_LIST] + \ 1059 [(x,7) for x in DrtTokens.IMP_LIST] + \ 1060 [(None,8)])

1061

1062 - def get_all_symbols(self):

1063 """This method exists to be overridden""" 1064 return DrtTokens.SYMBOLS

1065

1066 - def isvariable(self, tok):

1067 return tok not in DrtTokens.TOKENS

1068

1069 - def handle(self, tok, context):

1070 """This method is intended to be overridden for logics that 1071 use different operators or expressions""" 1072 if tok in DrtTokens.NOT_LIST: 1073 return self.handle_negation(tok, context) 1074 1075 elif tok in DrtTokens.LAMBDA_LIST: 1076 return self.handle_lambda(tok, context) 1077 1078 elif tok == DrtTokens.OPEN: 1079 if self.inRange(0) and self.token(0) == DrtTokens.OPEN_BRACKET: 1080 return self.handle_DRS(tok, context) 1081 else: 1082 return self.handle_open(tok, context) 1083 1084 elif tok.upper() == DrtTokens.DRS: 1085 self.assertNextToken(DrtTokens.OPEN) 1086 return self.handle_DRS(tok, context) 1087 1088 elif self.isvariable(tok): 1089 return self.handle_variable(tok, context)

1090

1091 - def make_NegatedExpression(self, expression):

1092 return DrtNegatedExpression(expression)

1093

1094 - def handle_DRS(self, tok, context):

1095 # a DRS 1096 refs = self.handle_refs() 1097 if self.inRange(0) and self.token(0) == DrtTokens.COMMA: #if there is a comma (it's optional) 1098 self.token() # swallow the comma 1099 conds = self.handle_conds(context) 1100 self.assertNextToken(DrtTokens.CLOSE) 1101 return DRS(refs, conds, None)

1102

1103 - def handle_refs(self):

1104 self.assertNextToken(DrtTokens.OPEN_BRACKET) 1105 refs = [] 1106 while self.inRange(0) and self.token(0) != DrtTokens.CLOSE_BRACKET: 1107 # Support expressions like: DRS([x y],C) == DRS([x,y],C) 1108 if refs and self.token(0) == DrtTokens.COMMA: 1109 self.token() # swallow the comma 1110 refs.append(self.get_next_token_variable('quantified')) 1111 self.assertNextToken(DrtTokens.CLOSE_BRACKET) 1112 return refs

1113

1114 - def handle_conds(self, context):

1115 self.assertNextToken(DrtTokens.OPEN_BRACKET) 1116 conds = [] 1117 while self.inRange(0) and self.token(0) != DrtTokens.CLOSE_BRACKET: 1118 # Support expressions like: DRS([x y],C) == DRS([x, y],C) 1119 if conds and self.token(0) == DrtTokens.COMMA: 1120 self.token() # swallow the comma 1121 conds.append(self.parse_Expression(context)) 1122 self.assertNextToken(DrtTokens.CLOSE_BRACKET) 1123 return conds

1124

1125 - def make_EqualityExpression(self, first, second):

1126 """This method serves as a hook for other logic parsers that 1127 have different equality expression classes""" 1128 return DrtEqualityExpression(first, second)

1129

1130 - def get_BooleanExpression_factory(self, tok):

1131 """This method serves as a hook for other logic parsers that 1132 have different boolean operators""" 1133 if tok == DrtTokens.DRS_CONC: 1134 return lambda first, second: DrtConcatenation(first, second, None) 1135 elif tok in DrtTokens.OR_LIST: 1136 return DrtOrExpression 1137 elif tok in DrtTokens.IMP_LIST: 1138 def make_imp_expression(first, second): 1139 if isinstance(first, DRS): 1140 return DRS(first.refs, first.conds, second) 1141 if isinstance(first, DrtConcatenation): 1142 return DrtConcatenation(first.first, first.second, second) 1143 raise Exception('Antecedent of implication must be a DRS')

1144 return make_imp_expression 1145 else: 1146 return None

1147

1148 - def make_BooleanExpression(self, factory, first, second):

1149 return factory(first, second)

1150

1151 - def make_ApplicationExpression(self, function, argument):

1152 return DrtApplicationExpression(function, argument)

1153

1154 - def make_VariableExpression(self, name):

1155 return DrtVariableExpression(Variable(name))

1156

1157 - def make_LambdaExpression(self, variables, term):

1158 return DrtLambdaExpression(variables, term)

1159

1160 1161 -def demo():

1162 print '='*20 + 'TEST PARSE' + '='*20 1163 parser = DrtParser() 1164 print parser.parse(r'([x,y],[sees(x,y)])') 1165 print parser.parse(r'([x],[man(x), walks(x)])') 1166 print parser.parse(r'\x.\y.([],[sees(x,y)])') 1167 print parser.parse(r'\x.([],[walks(x)])(john)') 1168 print parser.parse(r'(([x],[walks(x)]) + ([y],[runs(y)]))') 1169 print parser.parse(r'(([],[walks(x)]) -> ([],[runs(x)]))') 1170 print parser.parse(r'([x],[PRO(x), sees(John,x)])') 1171 print parser.parse(r'([x],[man(x), -([],[walks(x)])])') 1172 print parser.parse(r'([],[(([x],[man(x)]) -> ([],[walks(x)]))])') 1173 1174 print '='*20 + 'Test fol()' + '='*20 1175 print parser.parse(r'([x,y],[sees(x,y)])').fol() 1176 1177 print '='*20 + 'Test alpha conversion and lambda expression equality' + '='*20 1178 e1 = parser.parse(r'\x.([],[P(x)])') 1179 print e1 1180 e2 = e1.alpha_convert(Variable('z')) 1181 print e2 1182 print e1 == e2 1183 1184 print '='*20 + 'Test resolve_anaphora()' + '='*20 1185 print resolve_anaphora(parser.parse(r'([x,y,z],[dog(x), cat(y), walks(z), PRO(z)])')) 1186 print resolve_anaphora(parser.parse(r'([],[(([x],[dog(x)]) -> ([y],[walks(y), PRO(y)]))])')) 1187 print resolve_anaphora(parser.parse(r'(([x,y],[]) + ([],[PRO(x)]))')) 1188 1189 print '='*20 + 'Test pprint()' + '='*20 1190 parser.parse(r"([],[])").pprint() 1191 parser.parse(r"([],[([x],[big(x), dog(x)]) -> ([],[bark(x)]) -([x],[walk(x)])])").pprint() 1192 parser.parse(r"([x,y],[x=y]) + ([z],[dog(z), walk(z)])").pprint() 1193 parser.parse(r"([],[([x],[]) | ([y],[]) | ([z],[dog(z), walk(z)])])").pprint() 1194 parser.parse(r"\P.\Q.(([x],[]) + P(x) + Q(x))(\x.([],[dog(x)]))").pprint()

1195

1196 1197 -def test_draw():

1198 expressions = [ 1199 r'x', 1200 r'([],[])', 1201 r'([x],[])', 1202 r'([x],[man(x)])', 1203 1204 r'([x,y],[sees(x,y)])', 1205 r'([x],[man(x), walks(x)])', 1206 r'\x.([],[man(x), walks(x)])', 1207 r'\x y.([],[sees(x,y)])', 1208 r'([],[(([],[walks(x)]) + ([],[runs(x)]))])', 1209 1210 r'([x],[man(x), -([],[walks(x)])])', 1211 r'([],[(([x],[man(x)]) -> ([],[walks(x)]))])' 1212 ] 1213 1214 for e in expressions: 1215 d = DrtParser().parse(e) 1216 d.draw()

1217 1218 1219 if __name__ == '__main__': 1220 demo() 1221

Source Code for Module nltk.sem.drt