joy/utils/types.py

   1 # -*- coding: utf_8
   2 from logging import getLogger
   3
   4 _log = getLogger(__name__)
   5
   6 from collections import Counter
   7 from itertools import imap, chain, product
   8 from inspect import stack as inspect_stack
   9 from joy.utils.stack import concat, expression_to_string, list_to_stack
  10 from joy.parser import Symbol, text_to_expression
  11
  12
  13 class AnyJoyType(object):
  14   '''
  15   Joy type variable.  Represents any Joy value.
  16   '''
  17
  18   accept = tuple, int, float, long, complex, str, unicode, bool, Symbol
  19   prefix = 'a'
  20
  21   def __init__(self, number):
  22     self.number = number
  23
  24   def __repr__(self):
  25     return self.prefix + str(self.number)
  26
  27   def __eq__(self, other):
  28     return (
  29       isinstance(other, self.__class__)
  30       and other.prefix == self.prefix
  31       and other.number == self.number
  32     )
  33
  34   def __ge__(self, other):
  35     return (
  36       issubclass(other.__class__, self.__class__)
  37       or isinstance(other, self.accept)
  38       )
  39
  40   def __le__(self, other):
  41     # 'a string' >= AnyJoyType() should be False.
  42     return issubclass(self.__class__, other.__class__)
  43
  44   def __add__(self, other):
  45     return self.__class__(self.number + other)
  46   __radd__ = __add__
  47
  48   def __hash__(self):
  49     return hash(repr(self))
  50
  51
  52 class BooleanJoyType(AnyJoyType):
  53   accept = bool
  54   prefix = 'b'
  55
  56
  57 class NumberJoyType(AnyJoyType):
  58   accept = bool, int, float, long, complex
  59   prefix = 'n'
  60
  61
  62 class FloatJoyType(NumberJoyType):
  63   accept = float
  64   prefix = 'f'
  65
  66
  67 class IntJoyType(FloatJoyType):
  68   accept = int
  69   prefix = 'i'
  70
  71
  72 class TextJoyType(FloatJoyType):
  73   accept = basestring
  74   prefix = 't'
  75
  76
  77 class StackJoyType(AnyJoyType):
  78
  79   accept = tuple
  80   prefix = 's'
  81
  82   def __nonzero__(self):
  83     # Imitate () at the end of cons list.
  84     return False
  85
  86
  87 class KleeneStar(object):
  88     u'''
  89     A sequence of zero or more `AnyJoyType` variables would be:
  90
  91        A*
  92
  93     The `A*` works by splitting the universe into two alternate histories:
  94
  95        A* → ∅
  96
  97        A* → A A*
  98
  99     The Kleene star variable disappears in one universe, and in the other
 100     it turns into an `AnyJoyType` variable followed by itself again.
 101
 102     We have to return all universes (represented by their substitution
 103     dicts, the "unifiers") that don't lead to type conflicts.
 104     '''
 105
 106     kind = AnyJoyType
 107
 108     def __init__(self, number):
 109         assert number
 110         self.number = number
 111         self.count = 0
 112         self.prefix = repr(self)
 113
 114     def __repr__(self):
 115         return '%s%i*' % (self.kind.prefix, self.number)
 116
 117     def another(self):
 118         self.count += 1
 119         return self.kind(10000 * self.number + self.count)
 120
 121     def __eq__(self, other):
 122         return (
 123             isinstance(other, self.__class__)
 124             and other.number == self.number
 125         )
 126
 127     def __ge__(self, other):
 128         return self.kind >= other.kind
 129
 130     def __add__(self, other):
 131         return self.__class__(self.number + other)
 132     __radd__ = __add__
 133
 134     def __hash__(self):
 135         return hash(repr(self))
 136
 137
 138 class AnyStarJoyType(KleeneStar): kind = AnyJoyType
 139 class NumberStarJoyType(KleeneStar): kind = NumberJoyType
 140 class FloatStarJoyType(KleeneStar): kind = FloatJoyType
 141 class IntStarJoyType(KleeneStar): kind = IntJoyType
 142 class StackStarJoyType(KleeneStar): kind = StackJoyType
 143 class TextStarJoyType(KleeneStar): kind = TextJoyType
 144
 145
 146 class FunctionJoyType(AnyJoyType):
 147
 148     def __init__(self, name, sec, number):
 149         self.name = name
 150         self.stack_effects = sec
 151         self.number = number
 152
 153     def __add__(self, other):
 154         return self
 155     __radd__ = __add__
 156
 157     def __repr__(self):
 158         return self.name
 159
 160
 161 class SymbolJoyType(FunctionJoyType):
 162     '''
 163     Represent non-combinator functions.
 164
 165     These type variables carry the stack effect comments and can
 166     appear in expressions (as in quoted programs.)
 167     '''
 168     prefix = 'F'
 169
 170
 171 class CombinatorJoyType(FunctionJoyType):
 172     '''
 173     Represent combinators.
 174
 175     These type variables carry Joy functions that implement the
 176     behaviour of Joy combinators and they can appear in expressions.
 177     For simple combinators the implementation functions can be the
 178     combinators themselves.
 179
 180     These types can also specify a stack effect (input side only) to
 181     guard against being used on invalid types.
 182     '''
 183
 184     prefix = 'C'
 185
 186     def __init__(self, name, sec, number, expect=None):
 187         super(CombinatorJoyType, self).__init__(name, sec, number)
 188         self.expect = expect
 189
 190     def enter_guard(self, f):
 191         if self.expect is None:
 192             return f
 193         g = self.expect, self.expect
 194         new_f = list(poly_compose(f, g, ()))
 195         assert len(new_f) == 1, repr(new_f)
 196         return new_f[0][1]
 197
 198
 199 class JoyTypeError(Exception): pass
 200
 201
 202 def reify(meaning, name, seen=None):
 203   '''
 204   Apply substitution dict to term, returning new term.
 205   '''
 206   if isinstance(name, tuple):
 207     return tuple(reify(meaning, inner) for inner in name)
 208   safety = 101
 209   while name in meaning and safety:
 210     safety -= 1
 211     name = meaning[name]
 212   if not safety:
 213       raise ValueError('Cycle in substitution dict: %s' % (meaning,))
 214   return name
 215
 216
 217 def relabel(left, right):
 218   '''
 219   Re-number type variables to avoid collisions between stack effects.
 220   '''
 221   return left, _1000(right)
 222
 223
 224 def _1000(right):
 225   if not isinstance(right, tuple):
 226     return 1000 + right
 227   return tuple(_1000(n) for n in right)
 228
 229
 230 def delabel(f, seen=None, c=None):
 231   '''
 232   Fix up type variable numbers after relabel().
 233   '''
 234   if seen is None:
 235     assert c is None
 236     seen, c = {}, Counter()
 237
 238   try:
 239     return seen[f]
 240   except KeyError:
 241     pass
 242
 243   if not isinstance(f, tuple):
 244     try:
 245       seen[f] = f.__class__(c[f.prefix] + 1)
 246     except (TypeError,  # FunctionJoyTypes break this.
 247         AttributeError):  # Symbol
 248       seen[f] = f
 249     else:
 250       c[f.prefix] += 1
 251     return seen[f]
 252
 253   return tuple(delabel(inner, seen, c) for inner in f)
 254
 255
 256 def uni_unify(u, v, s=None):
 257   '''
 258   Return a substitution dict representing a unifier for u and v.
 259   '''
 260   if s is None:
 261     s = {}
 262   elif s:
 263     u = reify(s, u)
 264     v = reify(s, v)
 265
 266   if isinstance(u, AnyJoyType) and isinstance(v, AnyJoyType):
 267     if u >= v:
 268       s[u] = v
 269     elif v >= u:
 270       s[v] = u
 271     else:
 272       raise JoyTypeError('Cannot unify %r and %r.' % (u, v))
 273
 274   elif isinstance(u, tuple) and isinstance(v, tuple):
 275     if len(u) != len(v) != 2:
 276       raise ValueError(repr((u, v)))  # Bad input.
 277     (a, b), (c, d) = u, v
 278     s = uni_unify(b, d, uni_unify(a, c, s))
 279
 280   elif isinstance(v, tuple):
 281     if not _stacky(u):
 282       raise JoyTypeError('Cannot unify %r and %r.' % (u, v))
 283     s[u] = v
 284
 285   elif isinstance(u, tuple):
 286     if not _stacky(v):
 287       raise JoyTypeError('Cannot unify %r and %r.' % (v, u))
 288     s[v] = u
 289
 290   else:
 291     raise JoyTypeError('Cannot unify %r and %r.' % (u, v))
 292
 293   return s
 294
 295
 296 def _log_uni(U):
 297   def inner(u, v, s=None):
 298     _log.debug(
 299       '%3i %s U %s   w/ %s',
 300       len(inspect_stack()), u, v, s,
 301       )
 302     res = U(u, v, s)
 303     _log.debug(
 304       '%3i %s U %s   w/ %s => %s',
 305       len(inspect_stack()), u, v, s, res,
 306       )
 307     return res
 308   return inner
 309
 310
 311 @_log_uni
 312 def unify(u, v, s=None):
 313     '''
 314     Return a tuple of substitution dicts representing unifiers for u and v.
 315     '''
 316     if s is None:
 317         s = {}
 318     elif s:
 319         u = reify(s, u)
 320         v = reify(s, v)
 321
 322     if u == v:
 323         res = s,
 324
 325     elif isinstance(u, tuple) and isinstance(v, tuple):
 326         if len(u) != 2 or len(v) != 2:
 327             if _that_one_special_case(u, v):
 328                 return s,
 329             raise ValueError(repr((u, v)))  # Bad input.
 330
 331
 332         (a, b), (c, d) = v, u
 333         if isinstance(a, KleeneStar):
 334             if isinstance(c, KleeneStar):
 335                 s = _lil_uni(a, c, s)  # Attempt to unify the two K-stars.
 336                 res = unify(d, b, s[0])
 337
 338             else:
 339                 # Two universes, in one the Kleene star disappears and
 340                 # unification continues without it...
 341                 s0 = unify(u, b)
 342
 343                 # In the other it spawns a new variable.
 344                 s1 = unify(u, (a.another(), v))
 345
 346                 res = s0 + s1
 347                 for sn in res:
 348                     sn.update(s)
 349
 350         elif isinstance(c, KleeneStar):
 351             res = unify(v, d) + unify(v, (c.another(), u))
 352             for sn in res:
 353               sn.update(s)
 354
 355         else:
 356             res = tuple(flatten(unify(d, b, sn) for sn in unify(c, a, s)))
 357
 358     elif isinstance(v, tuple):
 359         if not _stacky(u):
 360             raise JoyTypeError('Cannot unify %r and %r.' % (u, v))
 361         s[u] = v
 362         res = s,
 363
 364     elif isinstance(u, tuple):
 365         if not _stacky(v):
 366             raise JoyTypeError('Cannot unify %r and %r.' % (v, u))
 367         s[v] = u
 368         res = s,
 369
 370     else:
 371         res = _lil_uni(u, v, s)
 372
 373     return res
 374
 375
 376 def _that_one_special_case(u, v):
 377     '''
 378     Handle e.g. ((), (n1*, s1)) when type-checking sum, product, etc...
 379     '''
 380     return (
 381         u == ()
 382         and len(v) == 2
 383         and isinstance(v[0], KleeneStar)
 384         and isinstance(v[1], StackJoyType)
 385         )
 386
 387
 388 def flatten(g):
 389   return list(chain.from_iterable(g))
 390
 391
 392 def _lil_uni(u, v, s):
 393     if u >= v:
 394         s[u] = v
 395         return s,
 396     if v >= u:
 397         s[v] = u
 398         return s,
 399     raise JoyTypeError('Cannot unify %r and %r.' % (u, v))
 400
 401
 402 def _stacky(thing):
 403   return thing.__class__ in {AnyJoyType, StackJoyType}
 404
 405
 406 def _compose(f, g):
 407   '''
 408   Return the stack effect of the composition of two stack effects.
 409   '''
 410   # Relabel, unify, update, delabel.
 411   (f_in, f_out), (g_in, g_out) = relabel(f, g)
 412   fg = reify(uni_unify(g_in, f_out), (f_in, g_out))
 413   return delabel(fg)
 414
 415
 416 def compose(*functions):
 417   '''
 418   Return the stack effect of the composition of some of stack effects.
 419   '''
 420   return reduce(_compose, functions)
 421
 422
 423 def compilable(f):
 424   '''
 425   Return True if a stack effect represents a function that can be
 426   automatically compiled (to Python), False otherwise.
 427   '''
 428   return isinstance(f, tuple) and all(imap(compilable, f)) or _stacky(f)
 429
 430
 431 def doc_from_stack_effect(inputs, outputs):
 432   '''
 433   Return a crude string representation of a stack effect.
 434   '''
 435   switch = [False]  # Do we need to display the '...' for the rest of the main stack?
 436   i, o = _f(inputs, switch), _f(outputs, switch)
 437   if switch[0]:
 438     i.append('...')
 439     o.append('...')
 440   return '(%s--%s)' % (
 441     ' '.join(reversed([''] + i)),
 442     ' '.join(reversed(o + [''])),
 443   )
 444
 445
 446 def _f(term, switch):
 447   a = []
 448   while term and isinstance(term, tuple):
 449     item, term = term
 450     a.append(item)
 451   assert isinstance(term, (tuple, StackJoyType)), repr(term)
 452   a = [_to_str(i, term, switch) for i in a]
 453   return a
 454
 455
 456 def _to_str(term, stack, switch):
 457   if not isinstance(term, tuple):
 458     if term == stack:
 459       switch[0] = True
 460       return '[...]'
 461     return (
 462       '[...%i]' % term.number
 463       if isinstance(term, StackJoyType)
 464       else str(term)
 465     )
 466
 467   a = []
 468   while term and isinstance(term, tuple):
 469     item, term = term
 470     a.append(_to_str(item, stack, switch))
 471   assert isinstance(term, (tuple, StackJoyType)), repr(term)
 472   if term == stack:
 473     switch[0] = True
 474     end = '' if term == () else '...'
 475     #end = '...'
 476   else:
 477     end = '' if term == () else '...%i' % term.number
 478   a.append(end)
 479   return '[%s]' % ' '.join(a)
 480
 481
 482 def compile_(name, f, doc=None):
 483   '''
 484   Return a string of Python code implementing the function described
 485   by the stack effect.  If no doc string is passed doc_from_stack_effect()
 486   is used to generate one.
 487   '''
 488   i, o = f
 489   if doc is None:
 490     doc = doc_from_stack_effect(i, o)
 491   return '''def %s(stack):
 492   """
 493   ::
 494
 495   %s
 496
 497   """
 498   %s = stack
 499   return %s''' % (name, doc, i, o)
 500
 501
 502 def _poly_compose(f, g, e):
 503     (f_in, f_out), (g_in, g_out) = f, g
 504     for s in unify(g_in, f_out):
 505         yield reify(s, (e, (f_in, g_out)))
 506
 507
 508 def poly_compose(f, g, e):
 509     '''
 510     Yield the stack effects of the composition of two stack effects.  An
 511     expression is carried along and updated and yielded.
 512     '''
 513     f, g = relabel(f, g)
 514     for fg in _poly_compose(f, g, e):
 515         yield delabel(fg)
 516
 517
 518 def _meta_compose(F, G, e):
 519     for f, g in product(F, G):
 520         try:
 521             for result in poly_compose(f, g, e): yield result
 522         except JoyTypeError:
 523             pass
 524
 525
 526 def meta_compose(F, G, e):
 527     '''
 528     Yield the stack effects of the composition of two lists of stack
 529     effects.  An expression is carried along and updated and yielded.
 530     '''
 531     res = sorted(set(_meta_compose(F, G, e)))
 532     if not res:
 533         raise JoyTypeError('Cannot unify %r and %r.' % (F, G))
 534     return res
 535
 536
 537 _S0 = StackJoyType(0)
 538 ID = _S0, _S0  # Identity function.
 539
 540
 541 def _infer(e, F=ID):
 542     _log_it(e, F)
 543     if not e:
 544         return [F]
 545
 546     n, e = e
 547
 548     if isinstance(n, SymbolJoyType):
 549         eFG = meta_compose([F], n.stack_effects, e)
 550         res = flatten(_infer(e, Fn) for e, Fn in eFG)
 551
 552     elif isinstance(n, CombinatorJoyType):
 553         fi, fo = n.enter_guard(F)
 554         res = flatten(_interpret(f, fi, fo, e) for f in n.stack_effects)
 555
 556     elif isinstance(n, Symbol):
 557         if n in FUNCTIONS:
 558           res =_infer((FUNCTIONS[n], e), F)
 559         else:
 560           raise JoyTypeError
 561         #   print n
 562         #   func = joy.library._dictionary[n]
 563         #   res = _interpret(func, F[0], F[1], e)
 564
 565     else:
 566         fi, fo = F
 567         res = _infer(e, (fi, (n, fo)))
 568
 569     return res
 570
 571
 572 def _interpret(f, fi, fo, e):
 573   new_fo, ee, _ = f(fo, e, {})
 574   ee = reify(FUNCTIONS, ee)  # Fix Symbols.
 575   new_F = fi, new_fo
 576   return _infer(ee, new_F)
 577
 578
 579 def _log_it(e, F):
 580     _log.info(
 581         u'%3i %s ∘ %s',
 582         len(inspect_stack()),
 583         doc_from_stack_effect(*F),
 584         expression_to_string(e),
 585         )
 586
 587
 588 def infer(*expression):
 589     '''
 590     Return a list of stack effects for a Joy expression.
 591
 592     For example::
 593
 594         h = infer(pop, swap, rolldown, rest, rest, cons, cons)
 595         for fi, fo in h:
 596             print doc_from_stack_effect(fi, fo)
 597
 598     Prints::
 599
 600         ([a4 a5 ...1] a3 a2 a1 -- [a2 a3 ...1])
 601
 602     '''
 603     return sorted(set(_infer(list_to_stack(expression))))
 604
 605
 606 def infer_string(string):
 607     e = reify(FUNCTIONS, text_to_expression(string))  # Fix Symbols.
 608     return sorted(set(_infer(e)))
 609
 610
 611 def infer_expression(expression):
 612     e = reify(FUNCTIONS, expression)  # Fix Symbols.
 613     return sorted(set(_infer(e)))
 614
 615
 616 def type_check(name, stack):
 617     '''
 618     Trinary predicate.  True if named function type-checks, False if it
 619     fails, None if it's indeterminate (because I haven't entered it into
 620     the FUNCTIONS dict yet.)
 621     '''
 622     try:
 623         func = FUNCTIONS[name]
 624     except KeyError:
 625         return # None, indicating unknown
 626
 627     for fi, fo in infer(func):
 628         try:
 629           U = unify(fi, stack)
 630         except (JoyTypeError, ValueError), e:
 631             #print >> sys.stderr, name, e, stack
 632             continue
 633         #print U
 634         return True
 635     return False
 636
 637
 638 FUNCTIONS = {}  # Polytypes (lists of stack effects.)
 639 _functions = {}  # plain ol' stack effects.
 640
 641
 642 def __(*seq):
 643   stack = StackJoyType(23)
 644   for item in seq: stack = item, stack
 645   return stack
 646
 647
 648 def stack_effect(*inputs):
 649   def _stack_effect(*outputs):
 650     def _apply_to(function):
 651       i, o = _functions[function.name] = __(*inputs), __(*outputs)
 652       function.__doc__ += (
 653         '\nStack effect::\n\n    '  # '::' for Sphinx docs.
 654         + doc_from_stack_effect(i, o)
 655         )
 656       return function
 657     return _apply_to
 658   return _stack_effect
 659
 660
 661 def ef(*inputs):
 662   def _ef(*outputs):
 663     return __(*inputs), __(*outputs)
 664   return _ef
 665
 666
 667 def combinator_effect(number, *expect):
 668     def _combinator_effect(c):
 669         C = FUNCTIONS[c.name] = CombinatorJoyType(c.name, [c], number)
 670         if expect: C.expect = __(*expect)
 671         return c
 672     return _combinator_effect
 673
 674
 675 def show(DEFS):
 676   for name, stack_effect_comment in sorted(DEFS.iteritems()):
 677     t = ' *'[compilable(stack_effect_comment)]
 678     print name, '=', doc_from_stack_effect(*stack_effect_comment), t
 679
 680
 681 def generate_library_code(DEFS, f=None):
 682   if f is None:
 683     import sys
 684     f = sys.stdout
 685   print >> f, '# GENERATED FILE. DO NOT EDIT.\n'
 686   for name, stack_effect_comment in sorted(DEFS.iteritems()):
 687     if not compilable(stack_effect_comment):
 688       continue
 689     print >> f
 690     print >> f, compile_(name, stack_effect_comment)
 691     print >> f
 692
 693
 694 ##if __name__ == '__main__':
 695 ##  show()