docs/Compiling_Joy.rst

   1 .. code:: ipython3
   2
   3     from notebook_preamble import D, J, V, define
   4
   5 Compiling Joy
   6 =============
   7
   8 Given a Joy program like:
   9
  10 ::
  11
  12     sqr == dup mul
  13
  14 .. code:: ipython3
  15
  16     V('23 sqr')
  17
  18
  19 .. parsed-literal::
  20
  21           • 23 sqr
  22        23 • sqr
  23        23 • dup mul
  24     23 23 • mul
  25       529 •
  26
  27
  28 How would we go about compiling this code (to Python for now)?
  29
  30 Naive Call Chaining
  31 -------------------
  32
  33 The simplest thing would be to compose the functions from the library:
  34
  35 .. code:: ipython3
  36
  37     dup, mul = D['dup'], D['mul']
  38
  39 .. code:: ipython3
  40
  41     def sqr(stack, expression, dictionary):
  42         return mul(*dup(stack, expression, dictionary))
  43
  44 .. code:: ipython3
  45
  46     old_sqr = D['sqr']
  47     D['sqr'] = sqr
  48
  49 .. code:: ipython3
  50
  51     V('23 sqr')
  52
  53
  54 .. parsed-literal::
  55
  56         • 23 sqr
  57      23 • sqr
  58     529 •
  59
  60
  61 It's simple to write a function to emit this kind of crude "compiled"
  62 code.
  63
  64 .. code:: ipython3
  65
  66     def compile_joy(name, expression):
  67         term, expression = expression
  68         code = term +'(stack, expression, dictionary)'
  69         format_ = '%s(*%s)'
  70         while expression:
  71             term, expression = expression
  72             code = format_ % (term, code)
  73         return '''\
  74     def %s(stack, expression, dictionary):
  75         return %s
  76     ''' % (name, code)
  77
  78
  79     def compile_joy_definition(defi):
  80         return compile_joy(defi.name, defi.body)
  81
  82
  83 .. code:: ipython3
  84
  85     print(compile_joy_definition(old_sqr))
  86
  87
  88 .. parsed-literal::
  89
  90     def sqr(stack, expression, dictionary):
  91         return mul(*dup(stack, expression, dictionary))
  92
  93
  94
  95 But what about literals?
  96
  97 ::
  98
  99     quoted == [unit] dip
 100
 101 .. code:: ipython3
 102
 103     unit, dip = D['unit'], D['dip']
 104
 105 .. code:: ipython3
 106
 107     # print compile_joy_definition(D['quoted'])
 108     # raises
 109     # TypeError: can only concatenate tuple (not "str") to tuple
 110
 111 For a program like ``foo == bar baz 23 99 baq lerp barp`` we would want
 112 something like:
 113
 114 .. code:: ipython3
 115
 116     def foo(stack, expression, dictionary):
 117         stack, expression, dictionary = baz(*bar(stack, expression, dictionary))
 118         return barp(*lerp(*baq((99, (23, stack)), expression, dictionary)))
 119
 120 You have to have a little discontinuity when going from a symbol to a
 121 literal, because you have to pick out the stack from the arguments to
 122 push the literal(s) onto it before you continue chaining function calls.
 123
 124 Compiling Yin Functions
 125 -----------------------
 126
 127 Call-chaining results in code that does too much work. For functions
 128 that operate on stacks and only rearrange values, what I like to call
 129 "Yin Functions", we can do better.
 130
 131 We can infer the stack effects of these functions (or "expressions" or
 132 "programs") automatically, and the stack effects completely define the
 133 semantics of the functions, so we can directly write out a two-line
 134 Python function for them. This is already implemented in the
 135 ``joy.utils.types.compile_()`` function.
 136
 137 .. code:: ipython3
 138
 139     from joy.utils.types import compile_, doc_from_stack_effect, infer_string
 140     from joy.library import SimpleFunctionWrapper
 141
 142
 143 ::
 144
 145
 146     ---------------------------------------------------------------------------
 147
 148     ModuleNotFoundError                       Traceback (most recent call last)
 149
 150     <ipython-input-14-d5ef3c7560be> in <module>
 151     ----> 1 from joy.utils.types import compile_, doc_from_stack_effect, infer_string
 152           2 from joy.library import SimpleFunctionWrapper
 153
 154
 155     ModuleNotFoundError: No module named 'joy.utils.types'
 156
 157
 158 .. code:: ipython3
 159
 160     stack_effects = infer_string('tuck over dup')
 161
 162 Yin functions have only a single stack effect, they do not branch or
 163 loop.
 164
 165 .. code:: ipython3
 166
 167     for fi, fo in stack_effects:
 168         print doc_from_stack_effect(fi, fo)
 169
 170 .. code:: ipython3
 171
 172     source = compile_('foo', stack_effects[0])
 173
 174 All Yin functions can be described in Python as a tuple-unpacking (or
 175 "-destructuring") of the stack datastructure followed by building up the
 176 new stack structure.
 177
 178 .. code:: ipython3
 179
 180     print source
 181
 182 .. code:: ipython3
 183
 184     exec compile(source, '__main__', 'single')
 185
 186     D['foo'] = SimpleFunctionWrapper(foo)
 187
 188
 189 ::
 190
 191
 192       File "<ipython-input-9-1a7e90bf2d7b>", line 1
 193         exec compile(source, '__main__', 'single')
 194              ^
 195     SyntaxError: invalid syntax
 196
 197
 198
 199 .. code:: ipython3
 200
 201     V('23 18 foo')
 202
 203 Compiling from Stack Effects
 204 ----------------------------
 205
 206 There are times when you're deriving a Joy program when you have a stack
 207 effect for a Yin function and you need to define it. For example, in the
 208 Ordered Binary Trees notebook there is a point where we must derive a
 209 function ``Ee``:
 210
 211 ::
 212
 213        [key old_value left right] new_value key [Tree-add] Ee
 214     ------------------------------------------------------------
 215        [key new_value left right]
 216
 217 While it is not hard to come up with this function manually, there is no
 218 necessity. This function can be defined (in Python) directly from its
 219 stack effect:
 220
 221 ::
 222
 223        [a b c d] e a [f] Ee
 224     --------------------------
 225        [a e c d]
 226
 227 (I haven't yet implemented a simple interface for this yet. What follow
 228 is an exploration of how to do it.)
 229
 230 .. code:: ipython3
 231
 232     from joy.parser import text_to_expression
 233
 234 .. code:: ipython3
 235
 236     Ein = '[a b c d] e a [f]'  # The terms should be reversed here but I don't realize that until later.
 237     Eout = '[a e c d]'
 238     E = '[%s] [%s]' % (Ein, Eout)
 239
 240     print E
 241
 242 .. code:: ipython3
 243
 244     (fi, (fo, _)) = text_to_expression(E)
 245
 246 .. code:: ipython3
 247
 248     fi, fo
 249
 250 .. code:: ipython3
 251
 252     Ein = '[a1 a2 a3 a4] a5 a6 a7'
 253     Eout = '[a1 a5 a3 a4]'
 254     E = '[%s] [%s]' % (Ein, Eout)
 255
 256     print E
 257
 258 .. code:: ipython3
 259
 260     (fi, (fo, _)) = text_to_expression(E)
 261
 262 .. code:: ipython3
 263
 264     fi, fo
 265
 266 .. code:: ipython3
 267
 268     def type_vars():
 269         from joy.library import a1, a2, a3, a4, a5, a6, a7, s0, s1
 270         return locals()
 271
 272     tv = type_vars()
 273     tv
 274
 275 .. code:: ipython3
 276
 277     from joy.utils.types import reify
 278
 279 .. code:: ipython3
 280
 281     stack_effect = reify(tv, (fi, fo))
 282     print doc_from_stack_effect(*stack_effect)
 283
 284 .. code:: ipython3
 285
 286     print stack_effect
 287
 288 Almost, but what we really want is something like this:
 289
 290 .. code:: ipython3
 291
 292     stack_effect = eval('(((a1, (a2, (a3, (a4, s1)))), (a5, (a6, (a7, s0)))), ((a1, (a5, (a3, (a4, s1)))), s0))', tv)
 293
 294 Note the change of ``()`` to ``JoyStackType`` type variables.
 295
 296 .. code:: ipython3
 297
 298     print doc_from_stack_effect(*stack_effect)
 299
 300 Now we can omit ``a3`` and ``a4`` if we like:
 301
 302 .. code:: ipython3
 303
 304     stack_effect = eval('(((a1, (a2, s1)), (a5, (a6, (a7, s0)))), ((a1, (a5, s1)), s0))', tv)
 305
 306 The ``right`` and ``left`` parts of the ordered binary tree node are
 307 subsumed in the tail of the node's stack/list.
 308
 309 .. code:: ipython3
 310
 311     print doc_from_stack_effect(*stack_effect)
 312
 313 .. code:: ipython3
 314
 315     source = compile_('Ee', stack_effect)
 316     print source
 317
 318 Oops! The input stack is backwards...
 319
 320 .. code:: ipython3
 321
 322     stack_effect = eval('((a7, (a6, (a5, ((a1, (a2, s1)), s0)))), ((a1, (a5, s1)), s0))', tv)
 323
 324 .. code:: ipython3
 325
 326     print doc_from_stack_effect(*stack_effect)
 327
 328 .. code:: ipython3
 329
 330     source = compile_('Ee', stack_effect)
 331     print source
 332
 333 Compare:
 334
 335 ::
 336
 337        [key old_value left right] new_value key [Tree-add] Ee
 338     ------------------------------------------------------------
 339        [key new_value left right]
 340
 341 .. code:: ipython3
 342
 343     eval(compile(source, '__main__', 'single'))
 344     D['Ee'] = SimpleFunctionWrapper(Ee)
 345
 346 .. code:: ipython3
 347
 348     V('[a b c d] 1 2 [f] Ee')
 349
 350
 351 Working with Yang Functions
 352 ---------------------------
 353
 354 Consider the compiled code of ``dup``:
 355
 356 .. code:: ipython3
 357
 358
 359     def dup(stack):
 360         (a1, s23) = stack
 361         return (a1, (a1, s23))
 362
 363
 364
 365 To compile ``sqr == dup mul`` we can compute the stack effect:
 366
 367 .. code:: ipython3
 368
 369     stack_effects = infer_string('dup mul')
 370     for fi, fo in stack_effects:
 371         print doc_from_stack_effect(fi, fo)
 372
 373 Then we would want something like this:
 374
 375 .. code:: ipython3
 376
 377
 378     def sqr(stack):
 379         (n1, s23) = stack
 380         n2 = mul(n1, n1)
 381         return (n2, s23)
 382
 383
 384
 385
 386
 387 How about...
 388
 389 .. code:: ipython3
 390
 391     stack_effects = infer_string('mul mul sub')
 392     for fi, fo in stack_effects:
 393         print doc_from_stack_effect(fi, fo)
 394
 395 .. code:: ipython3
 396
 397
 398     def foo(stack):
 399         (n1, (n2, (n3, (n4, s23)))) = stack
 400         n5 = mul(n1, n2)
 401         n6 = mul(n5, n3)
 402         n7 = sub(n6, n4)
 403         return (n7, s23)
 404
 405
 406     # or
 407
 408     def foo(stack):
 409         (n1, (n2, (n3, (n4, s23)))) = stack
 410         n5 = sub(mul(mul(n1, n2), n3), n4)
 411         return (n5, s23)
 412
 413
 414
 415
 416 .. code:: ipython3
 417
 418     stack_effects = infer_string('tuck')
 419     for fi, fo in stack_effects:
 420         print doc_from_stack_effect(fi, fo)
 421
 422
 423 Compiling Yin~Yang Functions
 424 ----------------------------
 425
 426 First, we need a source of Python identifiers. I'm going to reuse
 427 ``Symbol`` class for this.
 428
 429 .. code:: ipython3
 430
 431     from joy.parser import Symbol
 432
 433 .. code:: ipython3
 434
 435     def _names():
 436         n = 0
 437         while True:
 438             yield Symbol('a' + str(n))
 439             n += 1
 440
 441     names = _names().next
 442
 443 Now we need an object that represents a Yang function that accepts two
 444 args and return one result (we'll implement other kinds a little later.)
 445
 446 .. code:: ipython3
 447
 448     class Foo(object):
 449
 450         def __init__(self, name):
 451             self.name = name
 452
 453         def __call__(self, stack, expression, code):
 454             in1, (in0, stack) = stack
 455             out = names()
 456             code.append(('call', out, self.name, (in0, in1)))
 457             return (out, stack), expression, code
 458
 459 A crude "interpreter" that translates expressions of args and Yin and
 460 Yang functions into a kind of simple dataflow graph.
 461
 462 .. code:: ipython3
 463
 464     def I(stack, expression, code):
 465         while expression:
 466             term, expression = expression
 467             if callable(term):
 468                 stack, expression, _ = term(stack, expression, code)
 469             else:
 470                 stack = term, stack
 471                 code.append(('pop', term))
 472
 473         s = []
 474         while stack:
 475             term, stack = stack
 476             s.insert(0, term)
 477         if s:
 478             code.append(('push',) + tuple(s))
 479         return code
 480
 481 Something to convert the graph into Python code.
 482
 483 .. code:: ipython3
 484
 485     strtup = lambda a, b: '(%s, %s)' % (b, a)
 486     strstk = lambda rest: reduce(strtup, rest, 'stack')
 487
 488
 489     def code_gen(code):
 490         coalesce_pops(code)
 491         lines = []
 492         for t in code:
 493             tag, rest = t[0], t[1:]
 494
 495             if tag == 'pop':
 496                 lines.append(strstk(rest) + ' = stack')
 497
 498             elif tag == 'push':
 499                 lines.append('stack = ' + strstk(rest))
 500
 501             elif tag == 'call':
 502                 #out, name, in_ = rest
 503                 lines.append('%s = %s%s' % rest)
 504
 505             else:
 506                 raise ValueError(tag)
 507
 508         return '\n'.join('    ' + line for line in lines)
 509
 510
 511     def coalesce_pops(code):
 512         index = [i for i, t in enumerate(code) if t[0] == 'pop']
 513         for start, end in yield_groups(index):
 514             code[start:end] = \
 515                 [tuple(['pop'] + [t for _, t in code[start:end][::-1]])]
 516
 517
 518     def yield_groups(index):
 519         '''
 520         Yield slice indices for each group of contiguous ints in the
 521         index list.
 522         '''
 523         k = 0
 524         for i, (a, b) in enumerate(zip(index, index[1:])):
 525             if b - a > 1:
 526                 if k != i:
 527                     yield index[k], index[i] + 1
 528                 k = i + 1
 529         if k < len(index):
 530             yield index[k], index[-1] + 1
 531
 532
 533     def compile_yinyang(name, expression):
 534         return '''\
 535     def %s(stack):
 536     %s
 537         return stack
 538     ''' % (name, code_gen(I((), expression, [])))
 539
 540
 541 A few functions to try it with...
 542
 543 .. code:: ipython3
 544
 545     mul = Foo('mul')
 546     sub = Foo('sub')
 547
 548 .. code:: ipython3
 549
 550     def import_yin():
 551         from joy.utils.generated_library import *
 552         return locals()
 553
 554     yin_dict = {name: SimpleFunctionWrapper(func) for name, func in import_yin().iteritems()}
 555
 556     yin_dict
 557
 558     dup = yin_dict['dup']
 559
 560     #def dup(stack, expression, code):
 561     #    n, stack = stack
 562     #    return (n, (n, stack)), expression
 563
 564 ... and there we are.
 565
 566 .. code:: ipython3
 567
 568     print compile_yinyang('mul_', (names(), (names(), (mul, ()))))
 569
 570 .. code:: ipython3
 571
 572     e = (names(), (dup, (mul, ())))
 573     print compile_yinyang('sqr', e)
 574
 575 .. code:: ipython3
 576
 577     e = (names(), (dup, (names(), (sub, (mul, ())))))
 578     print compile_yinyang('foo', e)
 579
 580 .. code:: ipython3
 581
 582     e = (names(), (names(), (mul, (dup, (sub, (dup, ()))))))
 583     print compile_yinyang('bar', e)
 584
 585 .. code:: ipython3
 586
 587     e = (names(), (dup, (dup, (mul, (dup, (mul, (mul, ())))))))
 588     print compile_yinyang('to_the_fifth_power', e)
 589
 590
 591
 592