joy/utils/types.py

   1 from collections import Counter
   2 from itertools import imap
   3 from joy.utils.stack import concat
   4 from joy.parser import Symbol
   5
   6
   7 class AnyJoyType(object):
   8   '''
   9   Joy type variable.  Represents any Joy value.
  10   '''
  11
  12   accept = tuple, int, float, long, complex, str, unicode, bool, Symbol
  13   prefix = 'a'
  14
  15   def __init__(self, number):
  16     self.number = number
  17
  18   def __repr__(self):
  19     return self.prefix + str(self.number)
  20
  21   def __eq__(self, other):
  22     return (
  23       isinstance(other, self.__class__)
  24       and other.prefix == self.prefix
  25       and other.number == self.number
  26     )
  27
  28   def __ge__(self, other):
  29     return (
  30       issubclass(other.__class__, self.__class__)
  31       or isinstance(other, self.accept)
  32       )
  33
  34   def __le__(self, other):
  35     # 'a string' >= AnyJoyType() should be False.
  36     return issubclass(self.__class__, other.__class__)
  37
  38   def __add__(self, other):
  39     return self.__class__(self.number + other)
  40   __radd__ = __add__
  41
  42   def __hash__(self):
  43     return hash(repr(self))
  44
  45
  46 class BooleanJoyType(AnyJoyType):
  47   accept = bool
  48   prefix = 'b'
  49
  50
  51 class NumberJoyType(AnyJoyType):
  52   accept = int, float, long, complex
  53   prefix = 'n'
  54
  55
  56 class FloatJoyType(NumberJoyType):
  57   accept = float
  58   prefix = 'f'
  59
  60
  61 class IntJoyType(FloatJoyType):
  62   accept = int
  63   prefix = 'i'
  64
  65
  66 class TextJoyType(FloatJoyType):
  67   accept = basestring
  68   prefix = 't'
  69
  70
  71 class StackJoyType(AnyJoyType):
  72
  73   accept = tuple
  74   prefix = 's'
  75
  76   def __nonzero__(self):
  77     # Imitate () at the end of cons list.
  78     return False
  79
  80
  81 class JoyTypeError(Exception): pass
  82
  83
  84 def reify(meaning, name, seen=None):
  85   '''
  86   Apply substitution dict to term, returning new term.
  87   '''
  88   if isinstance(name, tuple):
  89     return tuple(reify(meaning, inner) for inner in name)
  90   safety = 101
  91   while name in meaning and safety:
  92     safety -= 1
  93     name = meaning[name]
  94   if not safety:
  95       raise ValueError('Cycle in substitution dict: %s' % (meaning,))
  96   return name
  97
  98
  99 def relabel(left, right):
 100   '''
 101   Re-number type variables to avoid collisions between stack effects.
 102   '''
 103   return left, _1000(right)
 104
 105
 106 def _1000(right):
 107   if not isinstance(right, tuple):
 108     return 1000 + right
 109   return tuple(_1000(n) for n in right)
 110
 111
 112 def delabel(f, seen=None, c=None):
 113   '''
 114   Fix up type variable numbers after relabel().
 115   '''
 116   if seen is None:
 117     assert c is None
 118     seen, c = {}, Counter()
 119
 120   try:
 121     return seen[f]
 122   except KeyError:
 123     pass
 124
 125   if not isinstance(f, tuple):
 126     try:
 127       seen[f] = f.__class__(c[f.prefix] + 1)
 128     except (TypeError,  # FunctionJoyTypes break this.
 129         AttributeError):  # Symbol
 130       seen[f] = f
 131     else:
 132       c[f.prefix] += 1
 133     return seen[f]
 134
 135   return tuple(delabel(inner, seen, c) for inner in f)
 136
 137
 138 def unify(u, v, s=None):
 139   '''
 140   Return a substitution dict representing a unifier for u and v.
 141   '''
 142   if s is None:
 143     s = {}
 144   elif s:
 145     u = reify(s, u)
 146     v = reify(s, v)
 147
 148   if isinstance(u, AnyJoyType) and isinstance(v, AnyJoyType):
 149     if u >= v:
 150       s[u] = v
 151     elif v >= u:
 152       s[v] = u
 153     else:
 154       raise JoyTypeError('Cannot unify %r and %r.' % (u, v))
 155
 156   elif isinstance(u, tuple) and isinstance(v, tuple):
 157     if len(u) != len(v) != 2:
 158       raise ValueError(repr((u, v)))  # Bad input.
 159     (a, b), (c, d) = u, v
 160     s = unify(b, d, unify(a, c, s))
 161
 162   elif isinstance(v, tuple):
 163     if not _stacky(u):
 164       raise JoyTypeError('Cannot unify %r and %r.' % (u, v))
 165     s[u] = v
 166
 167   elif isinstance(u, tuple):
 168     if not _stacky(v):
 169       raise JoyTypeError('Cannot unify %r and %r.' % (v, u))
 170     s[v] = u
 171
 172   else:
 173     raise JoyTypeError('Cannot unify %r and %r.' % (u, v))
 174
 175   return s
 176
 177
 178 def _stacky(thing):
 179   return thing.__class__ in {AnyJoyType, StackJoyType}
 180
 181
 182 def _compose(f, g):
 183   '''
 184   Return the stack effect of the composition of two stack effects.
 185   '''
 186   # Relabel, unify, update, delabel.
 187   (f_in, f_out), (g_in, g_out) = relabel(f, g)
 188   fg = reify(unify(g_in, f_out), (f_in, g_out))
 189   return delabel(fg)
 190
 191
 192 def compose(*functions):
 193   '''
 194   Return the stack effect of the composition of some of stack effects.
 195   '''
 196   return reduce(_compose, functions)
 197
 198
 199 def compilable(f):
 200   '''
 201   Return True if a stack effect represents a function that can be
 202   automatically compiled (to Python), False otherwise.
 203   '''
 204   return isinstance(f, tuple) and all(imap(compilable, f)) or _stacky(f)
 205
 206
 207 def doc_from_stack_effect(inputs, outputs):
 208   '''
 209   Return a crude string representation of a stack effect.
 210   '''
 211   switch = [False]  # Do we need to display the '...' for the rest of the main stack?
 212   i, o = _f(inputs, switch), _f(outputs, switch)
 213   if switch[0]:
 214     i.append('...')
 215     o.append('...')
 216   return '(%s--%s)' % (
 217     ' '.join(reversed([''] + i)),
 218     ' '.join(reversed(o + [''])),
 219   )
 220
 221
 222 def _f(term, switch):
 223   a = []
 224   while term and isinstance(term, tuple):
 225     item, term = term
 226     a.append(item)
 227   assert isinstance(term, (tuple, StackJoyType)), repr(term)
 228   a = [_to_str(i, term, switch) for i in a]
 229   return a
 230
 231
 232 def _to_str(term, stack, switch):
 233   if not isinstance(term, tuple):
 234     if term == stack:
 235       switch[0] = True
 236       return '[...]'
 237     return (
 238       '[...%i]' % term.number
 239       if isinstance(term, StackJoyType)
 240       else str(term)
 241     )
 242
 243   a = []
 244   while term and isinstance(term, tuple):
 245     item, term = term
 246     a.append(_to_str(item, stack, switch))
 247   assert isinstance(term, (tuple, StackJoyType)), repr(term)
 248   if term == stack:
 249     switch[0] = True
 250     end = '' if term == () else '...'
 251     #end = '...'
 252   else:
 253     end = '' if term == () else '...%i' % term.number
 254   a.append(end)
 255   return '[%s]' % ' '.join(a)
 256
 257
 258 def compile_(name, f, doc=None):
 259   '''
 260   Return a string of Python code implementing the function described
 261   by the stack effect.  If no doc string is passed doc_from_stack_effect()
 262   is used to generate one.
 263   '''
 264   i, o = f
 265   if doc is None:
 266     doc = doc_from_stack_effect(i, o)
 267   return '''def %s(stack):
 268   """
 269   ::
 270
 271   %s
 272
 273   """
 274   %s = stack
 275   return %s''' % (name, doc, i, o)
 276
 277
 278 _functions = {}
 279
 280
 281 def __(*seq):
 282   stack = StackJoyType(23)
 283   for item in seq: stack = item, stack
 284   return stack
 285
 286
 287 def stack_effect(*inputs):
 288   def _stack_effect(*outputs):
 289     def _apply_to(function):
 290       i, o = _functions[function.name] = __(*inputs), __(*outputs)
 291       function.__doc__ += (
 292         '\nStack effect::\n\n    '  # '::' for Sphinx docs.
 293         + doc_from_stack_effect(i, o)
 294         )
 295       return function
 296     return _apply_to
 297   return _stack_effect
 298
 299
 300 def ef(*inputs):
 301   def _ef(*outputs):
 302     return __(*inputs), __(*outputs)
 303   return _ef
 304
 305
 306 def show(DEFS):
 307   for name, stack_effect_comment in sorted(DEFS.iteritems()):
 308     t = ' *'[compilable(stack_effect_comment)]
 309     print name, '=', doc_from_stack_effect(*stack_effect_comment), t
 310
 311
 312 def generate_library_code(DEFS, f=None):
 313   if f is None:
 314     import sys
 315     f = sys.stdout
 316   print >> f, '# GENERATED FILE. DO NOT EDIT.\n'
 317   for name, stack_effect_comment in sorted(DEFS.iteritems()):
 318     if not compilable(stack_effect_comment):
 319       continue
 320     print >> f
 321     print >> f, compile_(name, stack_effect_comment)
 322     print >> f
 323
 324
 325 ##if __name__ == '__main__':
 326 ##  show()