docs/Compiling_Joy.md

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