docs/Types.md

   1
   2 # Type Inference
   3
   4 ## Pöial's Rules
   5
   6 ["Typing Tools for Typeless Stack Languages" by Jaanus Pöial
   7 ](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.212.6026)
   8
   9     @INPROCEEDINGS{Pöial06typingtools,
  10         author = {Jaanus Pöial},
  11         title = {Typing tools for typeless stack languages},
  12         booktitle = {In 23rd Euro-Forth Conference},
  13         year = {2006},
  14         pages = {40--46}
  15     }
  16
  17 ### First Rule
  18 This rule deals with functions (and literals) that put items on the stack `(-- d)`:
  19
  20
  21        (a -- b)∘(-- d)
  22     ---------------------
  23          (a -- b d)
  24
  25 ### Second Rule
  26 This rule deals with functions that consume items from the stack `(a --)`:
  27
  28        (a --)∘(c -- d)
  29     ---------------------
  30          (c a -- d)
  31
  32 ### Third Rule
  33 The third rule is actually two rules.  These two rules deal with composing functions when the second one will consume one of items the first one produces.  The two types must be *unified* or a type conflict declared.
  34
  35        (a -- b t[i])∘(c u[j] -- d)   t <= u (t is subtype of u)
  36     -------------------------------
  37        (a -- b     )∘(c      -- d)   t[i] == t[k] == u[j]
  38                                              ^
  39
  40        (a -- b t[i])∘(c u[j] -- d)   u <= t (u is subtype of t)
  41     -------------------------------
  42        (a -- b     )∘(c      -- d)   t[i] == u[k] == u[j]
  43
  44 ## Examples
  45 Let's work through some examples by hand to develop an intuition for the algorithm.
  46
  47 There's a function in one of the other notebooks.
  48
  49     F == pop swap roll< rest rest cons cons
  50
  51 It's all "stack chatter" and list manipulation so we should be able to deduce its type.
  52
  53 ### Stack Effect Comments
  54 Joy function types will be represented by Forth-style stack effect comments.  I'm going to use numbers instead of names to keep track of the stack arguments.  (A little bit like [De Bruijn index](https://en.wikipedia.org/wiki/De_Bruijn_index), at least it reminds me of them):
  55
  56     pop (1 --)
  57
  58     swap (1 2 -- 2 1)
  59
  60     roll< (1 2 3 -- 2 3 1)
  61
  62 These commands alter the stack but don't "look at" the values so these numbers represent an "Any type".
  63
  64 ### `pop swap`
  65
  66     (1 --) (1 2 -- 2 1)
  67
  68 Here we encounter a complication. The argument numbers need to be made unique among both sides.   For this let's change `pop` to use 0:
  69
  70     (0 --) (1 2 -- 2 1)
  71
  72 Following the second rule:
  73
  74     (1 2 0 -- 2 1)
  75
  76 ### `pop∘swap roll<`
  77
  78     (1 2 0 -- 2 1) (1 2 3 -- 2 3 1)
  79
  80 Let's re-label them:
  81
  82     (1a 2a 0a -- 2a 1a) (1b 2b 3b -- 2b 3b 1b)
  83
  84 Now we follow the rules.
  85
  86 We must unify `1a` and `3b`, and `2a` and `2b`, replacing the terms in the forms:
  87
  88     (1a 2a 0a -- 2a 1a) (1b 2b 3b -- 2b 3b 1b)
  89                                                 w/  {1a: 3b}
  90     (3b 2a 0a -- 2a   ) (1b 2b    -- 2b 3b 1b)
  91                                                 w/  {2a: 2b}
  92     (3b 2b 0a --      ) (1b       -- 2b 3b 1b)
  93
  94 Here we must apply the second rule:
  95
  96        (3b 2b 0a --) (1b -- 2b 3b 1b)
  97     -----------------------------------
  98          (1b 3b 2b 0a -- 2b 3b 1b)
  99
 100 Now we de-label the type, uh, labels:
 101
 102     (1b 3b 2b 0a -- 2b 3b 1b)
 103
 104     w/ {
 105         1b: 1,
 106         3b: 2,
 107         2b: 3,
 108         0a: 0,
 109         }
 110
 111     (1 2 3 0 -- 3 2 1)
 112
 113 And now we have the stack effect comment for `pop∘swap∘roll<`.
 114
 115 ### Compiling `pop∘swap∘roll<`
 116 The simplest way to "compile" this function would be something like:
 117
 118
 119 ```python
 120 def poswrd(s, e, d):
 121     return roll_down(*swap(*pop(s, e, d)))
 122 ```
 123
 124 However, internally this function would still be allocating tuples (stack cells) and doing other unnecesssary work.
 125
 126 Looking ahead for a moment, from the stack effect comment:
 127
 128     (1 2 3 0 -- 3 2 1)
 129
 130 We should be able to directly write out a Python function like:
 131
 132
 133 ```python
 134 def poswrd(stack):
 135     (_, (a, (b, (c, stack)))) = stack
 136     return (c, (b, (a, stack)))
 137 ```
 138
 139 This eliminates the internal work of the first version.  Because this function only rearranges the stack and doesn't do any actual processing on the stack items themselves all the information needed to implement it is in the stack effect comment.
 140
 141 ### Functions on Lists
 142 These are slightly tricky.
 143
 144     rest ( [1 ...] -- [...] )
 145
 146     cons ( 1 [...] -- [1 ...] )
 147
 148 ### `pop∘swap∘roll< rest`
 149
 150     (1 2 3 0 -- 3 2 1) ([1 ...] -- [...])
 151
 152 Re-label (instead of adding left and right tags I'm just taking the next available index number for the right-side stack effect comment):
 153
 154     (1 2 3 0 -- 3 2 1) ([4 ...] -- [...])
 155
 156 Unify and update:
 157
 158     (1       2 3 0 -- 3 2 1) ([4 ...] -- [...])
 159                                                  w/ {1: [4 ...]}
 160     ([4 ...] 2 3 0 -- 3 2  ) (        -- [...])
 161
 162 Apply the first rule:
 163
 164        ([4 ...] 2 3 0 -- 3 2) (-- [...])
 165     ---------------------------------------
 166          ([4 ...] 2 3 0 -- 3 2 [...])
 167
 168 And there we are.
 169
 170 ### `pop∘swap∘roll<∘rest rest`
 171
 172 Let's do it again.
 173
 174     ([4 ...] 2 3 0 -- 3 2 [...]) ([1 ...] -- [...])
 175
 176 Re-label (the tails of the lists on each side each get their own label):
 177
 178     ([4 .0.] 2 3 0 -- 3 2 [.0.]) ([5 .1.] -- [.1.])
 179
 180 Unify and update (note the opening square brackets have been omited in the substitution dict, this is deliberate and I'll explain below):
 181
 182     ([4 .0.]   2 3 0 -- 3 2 [.0.]  ) ([5 .1.] -- [.1.])
 183                                                         w/ { .0.] : 5 .1.] }
 184     ([4 5 .1.] 2 3 0 -- 3 2 [5 .1.]) ([5 .1.] -- [.1.])
 185
 186 How do we find `.0.]` in `[4 .0.]` and replace it with `5 .1.]` getting the result `[4 5 .1.]`?  This might seem hard, but because the underlying structure of the Joy list is a cons-list in Python it's actually pretty easy.  I'll explain below.
 187
 188 Next we unify and find our two terms are the same already: `[5 .1.]`:
 189
 190     ([4 5 .1.] 2 3 0 -- 3 2 [5 .1.]) ([5 .1.] -- [.1.])
 191
 192 Giving us:
 193
 194     ([4 5 .1.] 2 3 0 -- 3 2) (-- [.1.])
 195
 196 From here we apply the first rule and get:
 197
 198     ([4 5 .1.] 2 3 0 -- 3 2 [.1.])
 199
 200 Cleaning up the labels:
 201
 202     ([4 5 ...] 2 3 1 -- 3 2 [...])
 203
 204 This is the stack effect of `pop∘swap∘roll<∘rest∘rest`.
 205
 206 ### `pop∘swap∘roll<∘rest∘rest cons`
 207
 208     ([4 5 ...] 2 3 1 -- 3 2 [...]) (1 [...] -- [1 ...])
 209
 210 Re-label:
 211
 212     ([4 5 .1.] 2 3 1 -- 3 2 [.1.]) (6 [.2.] -- [6 .2.])
 213
 214 Unify:
 215
 216     ([4 5 .1.] 2 3 1 -- 3 2 [.1.]) (6 [.2.] -- [6 .2.])
 217                                                          w/ { .1.] : .2.] }
 218     ([4 5 .2.] 2 3 1 -- 3 2      ) (6       -- [6 .2.])
 219                                                          w/ {2: 6}
 220     ([4 5 .2.] 6 3 1 -- 3        ) (        -- [6 .2.])
 221
 222 First rule:
 223
 224     ([4 5 .2.] 6 3 1 -- 3 [6 .2.])
 225
 226 Re-label:
 227
 228     ([4 5 ...] 2 3 1 -- 3 [2 ...])
 229
 230 Done.
 231
 232 ### `pop∘swap∘roll<∘rest∘rest∘cons cons`
 233 One more time.
 234
 235     ([4 5 ...] 2 3 1 -- 3 [2 ...]) (1 [...] -- [1 ...])
 236
 237 Re-label:
 238
 239     ([4 5 .1.] 2 3 1 -- 3 [2 .1.]) (6 [.2.] -- [6 .2.])
 240
 241 Unify:
 242
 243     ([4 5 .1.] 2 3 1 -- 3 [2 .1.]) (6 [.2.] -- [6 .2.]  )
 244                                                            w/ { .2.] : 2 .1.] }
 245     ([4 5 .1.] 2 3 1 -- 3        ) (6       -- [6 2 .1.])
 246                                                            w/ {3: 6}
 247     ([4 5 .1.] 2 6 1 --          ) (        -- [6 2 .1.])
 248
 249 First or second rule:
 250
 251     ([4 5 .1.] 2 6 1 -- [6 2 .1.])
 252
 253 Clean up the labels:
 254
 255     ([4 5 ...] 2 3 1 -- [3 2 ...])
 256
 257 And there you have it, the stack effect for `pop∘swap∘roll<∘rest∘rest∘cons∘cons`.
 258
 259     ([4 5 ...] 2 3 1 -- [3 2 ...])
 260
 261 From this stack effect comment it should be possible to construct the following Python code:
 262
 263
 264 ```python
 265 def F(stack):
 266     (_, (d, (c, ((a, (b, S0)), stack)))) = stack
 267     return (d, (c, S0)), stack
 268 ```
 269
 270 ## Implementation
 271
 272 ### Representing Stack Effect Comments in Python
 273
 274 I'm going to use pairs of tuples of type descriptors, which will be integers or tuples of type descriptors:
 275
 276
 277 ```python
 278 roll_dn = (1, 2, 3), (2, 3, 1)
 279
 280 pop = (1,), ()
 281
 282 swap = (1, 2), (2, 1)
 283 ```
 284
 285 ### `compose()`
 286
 287
 288 ```python
 289 def compose(f, g):
 290
 291     (f_in, f_out), (g_in, g_out) = f, g
 292
 293     # First rule.
 294     #
 295     #       (a -- b) (-- d)
 296     #    ---------------------
 297     #         (a -- b d)
 298
 299     if not g_in:
 300
 301         fg_in, fg_out = f_in, f_out + g_out
 302
 303     # Second rule.
 304     #
 305     #       (a --) (c -- d)
 306     #    ---------------------
 307     #         (c a -- d)
 308
 309     elif not f_out:
 310
 311         fg_in, fg_out = g_in + f_in, g_out
 312
 313     else: # Unify, update, recur.
 314
 315         fo, gi = f_out[-1], g_in[-1]
 316
 317         s = unify(gi, fo)
 318
 319         if s == False:  # s can also be the empty dict, which is ok.
 320             raise TypeError('Cannot unify %r and %r.' % (fo, gi))
 321
 322         f_g = (f_in, f_out[:-1]), (g_in[:-1], g_out)
 323
 324         if s: f_g = update(s, f_g)
 325
 326         fg_in, fg_out = compose(*f_g)
 327
 328     return fg_in, fg_out
 329 ```
 330
 331 ### `unify()`
 332
 333
 334 ```python
 335 def unify(u, v, s=None):
 336     if s is None:
 337         s = {}
 338
 339     if u == v:
 340         return s
 341
 342     if isinstance(u, int):
 343         s[u] = v
 344         return s
 345
 346     if isinstance(v, int):
 347         s[v] = u
 348         return s
 349
 350     return False
 351 ```
 352
 353 ### `update()`
 354
 355
 356 ```python
 357 def update(s, term):
 358     if not isinstance(term, tuple):
 359         return s.get(term, term)
 360     return tuple(update(s, inner) for inner in term)
 361 ```
 362
 363 ### `relabel()`
 364
 365
 366 ```python
 367 def relabel(left, right):
 368     return left, _1000(right)
 369
 370 def _1000(right):
 371     if not isinstance(right, tuple):
 372         return 1000 + right
 373     return tuple(_1000(n) for n in right)
 374
 375 relabel(pop, swap)
 376 ```
 377
 378
 379
 380
 381     (((1,), ()), ((1001, 1002), (1002, 1001)))
 382
 383
 384
 385 ### `delabel()`
 386
 387
 388 ```python
 389 def delabel(f):
 390     s = {u: i for i, u in enumerate(sorted(_unique(f)))}
 391     return update(s, f)
 392
 393 def _unique(f, seen=None):
 394     if seen is None:
 395         seen = set()
 396     if not isinstance(f, tuple):
 397         seen.add(f)
 398     else:
 399         for inner in f:
 400             _unique(inner, seen)
 401     return seen
 402
 403 delabel(relabel(pop, swap))
 404 ```
 405
 406
 407
 408
 409     (((0,), ()), ((1, 2), (2, 1)))
 410
 411
 412
 413 ### `C()`
 414
 415 At last we put it all together in a function `C()` that accepts two stack effect comments and returns their composition (or raises and exception if they can't be composed due to type conflicts.)
 416
 417
 418 ```python
 419 def C(f, g):
 420     f, g = relabel(f, g)
 421     fg = compose(f, g)
 422     return delabel(fg)
 423 ```
 424
 425 Let's try it out.
 426
 427
 428 ```python
 429 C(pop, swap)
 430 ```
 431
 432
 433
 434
 435     ((1, 2, 0), (2, 1))
 436
 437
 438
 439
 440 ```python
 441 C(C(pop, swap), roll_dn)
 442 ```
 443
 444
 445
 446
 447     ((3, 1, 2, 0), (2, 1, 3))
 448
 449
 450
 451
 452 ```python
 453 C(swap, roll_dn)
 454 ```
 455
 456
 457
 458
 459     ((2, 0, 1), (1, 0, 2))
 460
 461
 462
 463
 464 ```python
 465 C(pop, C(swap, roll_dn))
 466 ```
 467
 468
 469
 470
 471     ((3, 1, 2, 0), (2, 1, 3))
 472
 473
 474
 475
 476 ```python
 477 poswrd = reduce(C, (pop, swap, roll_dn))
 478 poswrd
 479 ```
 480
 481
 482
 483
 484     ((3, 1, 2, 0), (2, 1, 3))
 485
 486
 487
 488 ### List Functions
 489 Here's that trick to represent functions like `rest` and `cons` that manipulate lists.  We use a cons-list of tuples and give the tails their own numbers.  Then everything above already works.
 490
 491
 492 ```python
 493 rest = ((1, 2),), (2,)
 494
 495 cons = (1, 2), ((1, 2),)
 496 ```
 497
 498
 499 ```python
 500 C(poswrd, rest)
 501 ```
 502
 503
 504
 505
 506     (((3, 4), 1, 2, 0), (2, 1, 4))
 507
 508
 509
 510 Compare this to the stack effect comment we wrote above:
 511
 512     ((  (3, 4), 1, 2, 0 ), ( 2, 1,   4  ))
 513     (   [4 ...] 2  3  0  --  3  2  [...])
 514
 515 The translation table, if you will, would be:
 516
 517     {
 518     3: 4,
 519     4: ...],
 520     1: 2,
 521     2: 3,
 522     0: 0,
 523     }
 524
 525
 526 ```python
 527 F = reduce(C, (pop, swap, roll_dn, rest, rest, cons, cons))
 528
 529 F
 530 ```
 531
 532
 533
 534
 535     (((3, (4, 5)), 1, 2, 0), ((2, (1, 5)),))
 536
 537
 538
 539 Compare with the stack effect comment and you can see it works fine:
 540
 541     ([4 5 ...] 2 3 1 -- [3 2 ...])
 542
 543 ### Dealing with `cons` and `uncons`
 544 However, if we try to compose e.g. `cons` and `uncons` it won't work:
 545
 546
 547 ```python
 548 uncons = ((1, 2),), (1, 2)
 549 ```
 550
 551
 552 ```python
 553 try:
 554     C(cons, uncons)
 555 except Exception, e:
 556     print e
 557 ```
 558
 559     Cannot unify (1, 2) and (1001, 1002).
 560
 561
 562 #### `unify()` version 2
 563 The problem is that the `unify()` function as written doesn't handle the case when both terms are tuples.  We just have to add a clause to deal with this recursively:
 564
 565
 566 ```python
 567 def unify(u, v, s=None):
 568     if s is None:
 569         s = {}
 570     else:
 571         u = update(s, u)
 572         v = update(s, v)
 573
 574     if u == v:
 575         return s
 576
 577     if isinstance(u, int):
 578         s[u] = v
 579         return s
 580
 581     if isinstance(v, int):
 582         s[v] = u
 583         return s
 584
 585     if isinstance(u, tuple) and isinstance(v, tuple):
 586         if len(u) != len(v) != 2:
 587             raise ValueError(repr((u, v)))
 588         for uu, vv in zip(u, v):
 589             s = unify(uu, vv, s)
 590             if s == False: # (instead of a substitution dict.)
 591                 break
 592         return s
 593
 594     return False
 595 ```
 596
 597
 598 ```python
 599 C(cons, uncons)
 600 ```
 601
 602
 603
 604
 605     ((0, 1), (0, 1))
 606
 607
 608
 609 ## Compiling
 610 Now consider the Python function we would like to derive:
 611
 612
 613 ```python
 614 def F_python(stack):
 615     (_, (d, (c, ((a, (b, S0)), stack)))) = stack
 616     return (d, (c, S0)), stack
 617 ```
 618
 619 And compare it to the input stack effect comment tuple we just computed:
 620
 621
 622 ```python
 623 F[0]
 624 ```
 625
 626
 627
 628
 629     ((3, (4, 5)), 1, 2, 0)
 630
 631
 632
 633 The stack-de-structuring tuple has nearly the same form as our input stack effect comment tuple, just in the reverse order:
 634
 635     (_, (d, (c, ((a, (b, S0)), stack))))
 636
 637 Remove the punctuation:
 638
 639      _   d   c   (a, (b, S0))
 640
 641 Reverse the order and compare:
 642
 643      (a, (b, S0))   c   d   _
 644     ((3, (4, 5 )),  1,  2,  0)
 645
 646 Eh?
 647
 648 And the return tuple
 649
 650
 651 ```python
 652 F[1]
 653 ```
 654
 655
 656
 657
 658     ((2, (1, 5)),)
 659
 660
 661
 662 is similar to the output stack effect comment tuple:
 663
 664     ((d, (c, S0)), stack)
 665     ((2, (1, 5 )),      )
 666
 667 This should make it pretty easy to write a Python function that accepts the stack effect comment tuples and returns a new Python function (either as a string of code or a function object ready to use) that performs the semantics of that Joy function (described by the stack effect.)
 668
 669 ### Python Identifiers
 670 We want to substitute Python identifiers for the integers.  I'm going to repurpose `joy.parser.Symbol` class for this:
 671
 672
 673 ```python
 674 from collections import defaultdict
 675 from joy.parser import Symbol
 676
 677
 678 def _names_for():
 679     I = iter(xrange(1000))
 680     return lambda: Symbol('a%i' % next(I))
 681
 682
 683 def identifiers(term, s=None):
 684     if s is None:
 685         s = defaultdict(_names_for())
 686     if isinstance(term, int):
 687         return s[term]
 688     return tuple(identifiers(inner, s) for inner in term)
 689 ```
 690
 691 ### `doc_from_stack_effect()`
 692 As a convenience I've implemented a function to convert the Python stack effect comment tuples to reasonable text format.  There are some details in how this code works that related to stuff later in the notebook, so you should skip it for now and read it later if you're interested.
 693
 694
 695 ```python
 696 def doc_from_stack_effect(inputs, outputs):
 697     return '(%s--%s)' % (
 698         ' '.join(map(_to_str, inputs + ('',))),
 699         ' '.join(map(_to_str, ('',) + outputs))
 700     )
 701
 702
 703 def _to_str(term):
 704     if not isinstance(term, tuple):
 705         try:
 706             t = term.prefix == 's'
 707         except AttributeError:
 708             return str(term)
 709         return '[.%i.]' % term.number if t else str(term)
 710
 711     a = []
 712     while term and isinstance(term, tuple):
 713         item, term = term
 714         a.append(_to_str(item))
 715
 716     try:
 717         n = term.number
 718     except AttributeError:
 719         n = term
 720     else:
 721         if term.prefix != 's':
 722             raise ValueError('Stack label: %s' % (term,))
 723
 724     a.append('.%s.' % (n,))
 725     return '[%s]' % ' '.join(a)
 726 ```
 727
 728 ### `compile_()`
 729 Now we can write a compiler function to emit Python source code.  (The underscore suffix distiguishes it from the built-in `compile()` function.)
 730
 731
 732 ```python
 733 def compile_(name, f, doc=None):
 734     if doc is None:
 735         doc = doc_from_stack_effect(*f)
 736     inputs, outputs = identifiers(f)
 737     i = o = Symbol('stack')
 738     for term in inputs:
 739         i = term, i
 740     for term in outputs:
 741         o = term, o
 742     return '''def %s(stack):
 743     """%s"""
 744     %s = stack
 745     return %s''' % (name, doc, i, o)
 746 ```
 747
 748 Here it is in action:
 749
 750
 751 ```python
 752 source = compile_('F', F)
 753
 754 print source
 755 ```
 756
 757     def F(stack):
 758         """([3 4 .5.] 1 2 0 -- [2 1 .5.])"""
 759         (a5, (a4, (a3, ((a0, (a1, a2)), stack)))) = stack
 760         return ((a4, (a3, a2)), stack)
 761
 762
 763 Compare:
 764
 765
 766 ```python
 767 def F_python(stack):
 768     (_, (d, (c, ((a, (b, S0)), stack)))) = stack
 769     return ((d, (c, S0)), stack)
 770 ```
 771
 772 Next steps:
 773
 774
 775 ```python
 776 L = {}
 777
 778 eval(compile(source, '__main__', 'single'), {}, L)
 779
 780 L['F']
 781 ```
 782
 783
 784
 785
 786     <function F>
 787
 788
 789
 790 Let's try it out:
 791
 792
 793 ```python
 794 from notebook_preamble import D, J, V
 795 from joy.library import SimpleFunctionWrapper
 796 ```
 797
 798
 799 ```python
 800 D['F'] = SimpleFunctionWrapper(L['F'])
 801 ```
 802
 803
 804 ```python
 805 J('[4 5 ...] 2 3 1 F')
 806 ```
 807
 808     [3 2 ...]
 809
 810
 811 With this, we have a partial Joy compiler that works on the subset of Joy functions that manipulate stacks (both what I call "stack chatter" and the ones that manipulate stacks on the stack.)
 812
 813 I'm probably going to modify the definition wrapper code to detect definitions that can be compiled by this partial compiler and do it automatically.  It might be a reasonable idea to detect sequences of compilable functions in definitions that have uncompilable functions in them and just compile those.  However, if your library is well-factored this might be less helpful.
 814
 815 ### Compiling Library Functions
 816 We can use `compile_()` to generate many primitives in the library from their stack effect comments:
 817
 818
 819 ```python
 820 def defs():
 821
 822     roll_down = (1, 2, 3), (2, 3, 1)
 823
 824     roll_up = (1, 2, 3), (3, 1, 2)
 825
 826     pop = (1,), ()
 827
 828     swap = (1, 2), (2, 1)
 829
 830     rest = ((1, 2),), (2,)
 831
 832     rrest = C(rest, rest)
 833
 834     cons = (1, 2), ((1, 2),)
 835
 836     uncons = ((1, 2),), (1, 2)
 837
 838     swons = C(swap, cons)
 839
 840     return locals()
 841 ```
 842
 843
 844 ```python
 845 for name, stack_effect_comment in sorted(defs().items()):
 846     print
 847     print compile_(name, stack_effect_comment)
 848     print
 849 ```
 850
 851
 852     def cons(stack):
 853         """(1 2 -- [1 .2.])"""
 854         (a1, (a0, stack)) = stack
 855         return ((a0, a1), stack)
 856
 857
 858     def pop(stack):
 859         """(1 --)"""
 860         (a0, stack) = stack
 861         return stack
 862
 863
 864     def rest(stack):
 865         """([1 .2.] -- 2)"""
 866         ((a0, a1), stack) = stack
 867         return (a1, stack)
 868
 869
 870     def roll_down(stack):
 871         """(1 2 3 -- 2 3 1)"""
 872         (a2, (a1, (a0, stack))) = stack
 873         return (a0, (a2, (a1, stack)))
 874
 875
 876     def roll_up(stack):
 877         """(1 2 3 -- 3 1 2)"""
 878         (a2, (a1, (a0, stack))) = stack
 879         return (a1, (a0, (a2, stack)))
 880
 881
 882     def rrest(stack):
 883         """([0 1 .2.] -- 2)"""
 884         ((a0, (a1, a2)), stack) = stack
 885         return (a2, stack)
 886
 887
 888     def swap(stack):
 889         """(1 2 -- 2 1)"""
 890         (a1, (a0, stack)) = stack
 891         return (a0, (a1, stack))
 892
 893
 894     def swons(stack):
 895         """(0 1 -- [1 .0.])"""
 896         (a1, (a0, stack)) = stack
 897         return ((a1, a0), stack)
 898
 899
 900     def uncons(stack):
 901         """([1 .2.] -- 1 2)"""
 902         ((a0, a1), stack) = stack
 903         return (a1, (a0, stack))
 904
 905
 906
 907 ## Types and Subtypes of Arguments
 908 So far we have dealt with types of functions, those dealing with simple stack manipulation.  Let's extend our machinery to deal with types of arguments.
 909
 910 ### "Number" Type
 911
 912 Consider the definition of `sqr`:
 913
 914     sqr == dup mul
 915
 916
 917 The `dup` function accepts one *anything* and returns two of that:
 918
 919     dup (1 -- 1 1)
 920
 921 And `mul` accepts two "numbers" (we're ignoring ints vs. floats vs. complex, etc., for now) and returns just one:
 922
 923     mul (n n -- n)
 924
 925 So we're composing:
 926
 927     (1 -- 1 1)∘(n n -- n)
 928
 929 The rules say we unify 1 with `n`:
 930
 931        (1 -- 1 1)∘(n n -- n)
 932     ---------------------------  w/  {1: n}
 933        (1 -- 1  )∘(n   -- n)
 934
 935 This involves detecting that "Any type" arguments can accept "numbers".  If we were composing these functions the other way round this is still the case:
 936
 937        (n n -- n)∘(1 -- 1 1)
 938     ---------------------------  w/  {1: n}
 939        (n n --  )∘(  -- n n)
 940
 941 The important thing here is that the mapping is going the same way in both cases, from the "any" integer to the number
 942
 943 ### Distinguishing Numbers
 944 We should also mind that the number that `mul` produces is not (necessarily) the same as either of its inputs, which are not (necessarily) the same as each other:
 945
 946     mul (n2 n1 -- n3)
 947
 948
 949        (1  -- 1  1)∘(n2 n1 -- n3)
 950     --------------------------------  w/  {1: n2}
 951        (n2 -- n2  )∘(n2    -- n3)
 952
 953
 954        (n2 n1 -- n3)∘(1 -- 1  1 )
 955     --------------------------------  w/  {1: n3}
 956        (n2 n1 --   )∘(  -- n3 n3)
 957
 958
 959
 960 ### Distinguishing Types
 961 So we need separate domains of "any" numbers and "number" numbers, and we need to be able to ask the order of these domains.  Now the notes on the right side of rule three make more sense, eh?
 962
 963        (a -- b t[i])∘(c u[j] -- d)   t <= u (t is subtype of u)
 964     -------------------------------
 965        (a -- b     )∘(c      -- d)   t[i] == t[k] == u[j]
 966                                              ^
 967
 968        (a -- b t[i])∘(c u[j] -- d)   u <= t (u is subtype of t)
 969     -------------------------------
 970        (a -- b     )∘(c      -- d)   t[i] == u[k] == u[j]
 971
 972 The indices `i`, `k`, and `j` are the number part of our labels and `t` and `u` are the domains.
 973
 974 By creative use of Python's "double underscore" methods we can define a Python class hierarchy of Joy types and use the `issubclass()` method to establish domain ordering, as well as other handy behaviour that will make it fairly easy to reuse most of the code above.
 975
 976
 977 ```python
 978 class AnyJoyType(object):
 979
 980     prefix = 'a'
 981
 982     def __init__(self, number):
 983         self.number = number
 984
 985     def __repr__(self):
 986         return self.prefix + str(self.number)
 987
 988     def __eq__(self, other):
 989         return (
 990             isinstance(other, self.__class__)
 991             and other.prefix == self.prefix
 992             and other.number == self.number
 993         )
 994
 995     def __ge__(self, other):
 996         return issubclass(other.__class__, self.__class__)
 997
 998     def __add__(self, other):
 999         return self.__class__(self.number + other)
1000     __radd__ = __add__
1001
1002     def __hash__(self):
1003         return hash(repr(self))
1004
1005
1006 class NumberJoyType(AnyJoyType): prefix = 'n'
1007 class FloatJoyType(NumberJoyType): prefix = 'f'
1008 class IntJoyType(FloatJoyType): prefix = 'i'
1009
1010
1011 class StackJoyType(AnyJoyType):
1012     prefix = 's'
1013
1014
1015 _R = range(10)
1016 A = map(AnyJoyType, _R)
1017 N = map(NumberJoyType, _R)
1018 S = map(StackJoyType, _R)
1019 ```
1020
1021 Mess with it a little:
1022
1023
1024 ```python
1025 from itertools import permutations
1026 ```
1027
1028 "Any" types can be specialized to numbers and stacks, but not vice versa:
1029
1030
1031 ```python
1032 for a, b in permutations((A[0], N[0], S[0]), 2):
1033     print a, '>=', b, '->', a >= b
1034 ```
1035
1036     a0 >= n0 -> True
1037     a0 >= s0 -> True
1038     n0 >= a0 -> False
1039     n0 >= s0 -> False
1040     s0 >= a0 -> False
1041     s0 >= n0 -> False
1042
1043
1044 Our crude [Numerical Tower](https://en.wikipedia.org/wiki/Numerical_tower) of *numbers* > *floats* > *integers* works as well (but we're not going to use it yet):
1045
1046
1047 ```python
1048 for a, b in permutations((A[0], N[0], FloatJoyType(0), IntJoyType(0)), 2):
1049     print a, '>=', b, '->', a >= b
1050 ```
1051
1052     a0 >= n0 -> True
1053     a0 >= f0 -> True
1054     a0 >= i0 -> True
1055     n0 >= a0 -> False
1056     n0 >= f0 -> True
1057     n0 >= i0 -> True
1058     f0 >= a0 -> False
1059     f0 >= n0 -> False
1060     f0 >= i0 -> True
1061     i0 >= a0 -> False
1062     i0 >= n0 -> False
1063     i0 >= f0 -> False
1064
1065
1066 ### Typing `sqr`
1067
1068
1069 ```python
1070 dup = (A[1],), (A[1], A[1])
1071
1072 mul = (N[1], N[2]), (N[3],)
1073 ```
1074
1075
1076 ```python
1077 dup
1078 ```
1079
1080
1081
1082
1083     ((a1,), (a1, a1))
1084
1085
1086
1087
1088 ```python
1089 mul
1090 ```
1091
1092
1093
1094
1095     ((n1, n2), (n3,))
1096
1097
1098
1099 ### Modifying the Inferencer
1100 Re-labeling still works fine:
1101
1102
1103 ```python
1104 foo = relabel(dup, mul)
1105
1106 foo
1107 ```
1108
1109
1110
1111
1112     (((a1,), (a1, a1)), ((n1001, n1002), (n1003,)))
1113
1114
1115
1116 #### `delabel()` version 2
1117 The `delabel()` function needs an overhaul.  It now has to keep track of how many labels of each domain it has "seen".
1118
1119
1120 ```python
1121 from collections import Counter
1122
1123
1124 def delabel(f, seen=None, c=None):
1125     if seen is None:
1126         assert c is None
1127         seen, c = {}, Counter()
1128
1129     try:
1130         return seen[f]
1131     except KeyError:
1132         pass
1133
1134     if not isinstance(f, tuple):
1135         seen[f] = f.__class__(c[f.prefix])
1136         c[f.prefix] += 1
1137         return seen[f]
1138
1139     return tuple(delabel(inner, seen, c) for inner in f)
1140 ```
1141
1142
1143 ```python
1144 delabel(foo)
1145 ```
1146
1147
1148
1149
1150     (((a0,), (a0, a0)), ((n0, n1), (n2,)))
1151
1152
1153
1154 #### `unify()` version 3
1155
1156
1157 ```python
1158 def unify(u, v, s=None):
1159     if s is None:
1160         s = {}
1161     else:
1162         u = update(s, u)
1163         v = update(s, v)
1164
1165     if u == v:
1166         return s
1167
1168     if isinstance(u, AnyJoyType) and isinstance(v, AnyJoyType):
1169         if u >= v:
1170             s[u] = v
1171             return s
1172         if v >= u:
1173             s[v] = u
1174             return s
1175         raise TypeError('Cannot unify %r and %r.' % (u, v))
1176
1177     if isinstance(u, tuple) and isinstance(v, tuple):
1178         if len(u) != len(v) != 2:
1179             raise TypeError(repr((u, v)))
1180         for uu, vv in zip(u, v):
1181             s = unify(uu, vv, s)
1182             if s == False: # (instead of a substitution dict.)
1183                 break
1184         return s
1185
1186     if isinstance(v, tuple):
1187         if not stacky(u):
1188             raise TypeError('Cannot unify %r and %r.' % (u, v))
1189         s[u] = v
1190         return s
1191
1192     if isinstance(u, tuple):
1193         if not stacky(v):
1194             raise TypeError('Cannot unify %r and %r.' % (v, u))
1195         s[v] = u
1196         return s
1197
1198     return False
1199
1200
1201 def stacky(thing):
1202     return thing.__class__ in {AnyJoyType, StackJoyType}
1203 ```
1204
1205 Rewrite the stack effect comments:
1206
1207
1208 ```python
1209 def defs():
1210
1211     roll_down = (A[1], A[2], A[3]), (A[2], A[3], A[1])
1212
1213     roll_up = (A[1], A[2], A[3]), (A[3], A[1], A[2])
1214
1215     pop = (A[1],), ()
1216
1217     popop = (A[2], A[1],), ()
1218
1219     popd = (A[2], A[1],), (A[1],)
1220
1221     popdd = (A[3], A[2], A[1],), (A[2], A[1],)
1222
1223     swap = (A[1], A[2]), (A[2], A[1])
1224
1225     rest = ((A[1], S[1]),), (S[1],)
1226
1227     rrest = C(rest, rest)
1228
1229     cons = (A[1], S[1]), ((A[1], S[1]),)
1230
1231     ccons = C(cons, cons)
1232
1233     uncons = ((A[1], S[1]),), (A[1], S[1])
1234
1235     swons = C(swap, cons)
1236
1237     dup = (A[1],), (A[1], A[1])
1238
1239     dupd = (A[2], A[1]), (A[2], A[2], A[1])
1240
1241     mul = (N[1], N[2]), (N[3],)
1242
1243     sqrt = C(dup, mul)
1244
1245     first = ((A[1], S[1]),), (A[1],)
1246
1247     second = C(rest, first)
1248
1249     third = C(rest, second)
1250
1251     tuck = (A[2], A[1]), (A[1], A[2], A[1])
1252
1253     over = (A[2], A[1]), (A[2], A[1], A[2])
1254
1255     succ = pred = (N[1],), (N[2],)
1256
1257     divmod_ = pm = (N[2], N[1]), (N[4], N[3])
1258
1259     return locals()
1260 ```
1261
1262
1263 ```python
1264 DEFS = defs()
1265 ```
1266
1267
1268 ```python
1269 for name, stack_effect_comment in sorted(DEFS.items()):
1270     print name, '=', doc_from_stack_effect(*stack_effect_comment)
1271 ```
1272
1273     ccons = (a0 a1 [.0.] -- [a0 a1 .0.])
1274     cons = (a1 [.1.] -- [a1 .1.])
1275     divmod_ = (n2 n1 -- n4 n3)
1276     dup = (a1 -- a1 a1)
1277     dupd = (a2 a1 -- a2 a2 a1)
1278     first = ([a1 .1.] -- a1)
1279     mul = (n1 n2 -- n3)
1280     over = (a2 a1 -- a2 a1 a2)
1281     pm = (n2 n1 -- n4 n3)
1282     pop = (a1 --)
1283     popd = (a2 a1 -- a1)
1284     popdd = (a3 a2 a1 -- a2 a1)
1285     popop = (a2 a1 --)
1286     pred = (n1 -- n2)
1287     rest = ([a1 .1.] -- [.1.])
1288     roll_down = (a1 a2 a3 -- a2 a3 a1)
1289     roll_up = (a1 a2 a3 -- a3 a1 a2)
1290     rrest = ([a0 a1 .0.] -- [.0.])
1291     second = ([a0 a1 .0.] -- a1)
1292     sqrt = (n0 -- n1)
1293     succ = (n1 -- n2)
1294     swap = (a1 a2 -- a2 a1)
1295     swons = ([.0.] a0 -- [a0 .0.])
1296     third = ([a0 a1 a2 .0.] -- a2)
1297     tuck = (a2 a1 -- a1 a2 a1)
1298     uncons = ([a1 .1.] -- a1 [.1.])
1299
1300
1301
1302 ```python
1303 globals().update(DEFS)
1304 ```
1305
1306 #### Compose `dup` and `mul`
1307
1308
1309 ```python
1310 C(dup, mul)
1311 ```
1312
1313
1314
1315
1316     ((n0,), (n1,))
1317
1318
1319
1320 Revisit the `F` function, works fine.
1321
1322
1323 ```python
1324 F = reduce(C, (pop, swap, roll_down, rest, rest, cons, cons))
1325 F
1326 ```
1327
1328
1329
1330
1331     (((a0, (a1, s0)), a2, a3, a4), ((a3, (a2, s0)),))
1332
1333
1334
1335
1336 ```python
1337 print doc_from_stack_effect(*F)
1338 ```
1339
1340     ([a0 a1 .0.] a2 a3 a4 -- [a3 a2 .0.])
1341
1342
1343 Some otherwise inefficient functions are no longer to be feared.  We can also get the effect of combinators in some limited cases.
1344
1345
1346 ```python
1347 def neato(*funcs):
1348     print doc_from_stack_effect(*reduce(C, funcs))
1349 ```
1350
1351
1352 ```python
1353 # e.g. [swap] dip
1354 neato(roll_up, swap, roll_down)
1355 ```
1356
1357     (a0 a1 a2 -- a1 a0 a2)
1358
1359
1360
1361 ```python
1362 # e.g. [popop] dip
1363 neato(popdd, roll_down, pop)
1364 ```
1365
1366     (a0 a1 a2 a3 -- a2 a3)
1367
1368
1369
1370 ```python
1371 # Reverse the order of the top three items.
1372 neato(roll_up, swap)
1373 ```
1374
1375     (a0 a1 a2 -- a2 a1 a0)
1376
1377
1378 #### `compile_()` version 2
1379 Because the type labels represent themselves as valid Python identifiers the `compile_()` function doesn't need to generate them anymore:
1380
1381
1382 ```python
1383 def compile_(name, f, doc=None):
1384     inputs, outputs = f
1385     if doc is None:
1386         doc = doc_from_stack_effect(inputs, outputs)
1387     i = o = Symbol('stack')
1388     for term in inputs:
1389         i = term, i
1390     for term in outputs:
1391         o = term, o
1392     return '''def %s(stack):
1393     """%s"""
1394     %s = stack
1395     return %s''' % (name, doc, i, o)
1396 ```
1397
1398
1399 ```python
1400 print compile_('F', F)
1401 ```
1402
1403     def F(stack):
1404         """([a0 a1 .0.] a2 a3 a4 -- [a3 a2 .0.])"""
1405         (a4, (a3, (a2, ((a0, (a1, s0)), stack)))) = stack
1406         return ((a3, (a2, s0)), stack)
1407
1408
1409 But it cannot magically create new functions that involve e.g. math and such.  Note that this is *not* a `sqr` function implementation:
1410
1411
1412 ```python
1413 print compile_('sqr', C(dup, mul))
1414 ```
1415
1416     def sqr(stack):
1417         """(n0 -- n1)"""
1418         (n0, stack) = stack
1419         return (n1, stack)
1420
1421
1422 #### `compilable()`
1423 The functions that *can* be compiled are the ones that have only `AnyJoyType` and `StackJoyType` labels in their stack effect comments.  We can write a function to check that:
1424
1425
1426 ```python
1427 from itertools import imap
1428
1429
1430 def compilable(f):
1431     return isinstance(f, tuple) and all(imap(compilable, f)) or stacky(f)
1432 ```
1433
1434
1435 ```python
1436 for name, stack_effect_comment in sorted(defs().items()):
1437     if compilable(stack_effect_comment):
1438         print name, '=', doc_from_stack_effect(*stack_effect_comment)
1439 ```
1440
1441     ccons = (a0 a1 [.0.] -- [a0 a1 .0.])
1442     cons = (a1 [.1.] -- [a1 .1.])
1443     dup = (a1 -- a1 a1)
1444     dupd = (a2 a1 -- a2 a2 a1)
1445     first = ([a1 .1.] -- a1)
1446     over = (a2 a1 -- a2 a1 a2)
1447     pop = (a1 --)
1448     popd = (a2 a1 -- a1)
1449     popdd = (a3 a2 a1 -- a2 a1)
1450     popop = (a2 a1 --)
1451     rest = ([a1 .1.] -- [.1.])
1452     roll_down = (a1 a2 a3 -- a2 a3 a1)
1453     roll_up = (a1 a2 a3 -- a3 a1 a2)
1454     rrest = ([a0 a1 .0.] -- [.0.])
1455     second = ([a0 a1 .0.] -- a1)
1456     swap = (a1 a2 -- a2 a1)
1457     swons = ([.0.] a0 -- [a0 .0.])
1458     third = ([a0 a1 a2 .0.] -- a2)
1459     tuck = (a2 a1 -- a1 a2 a1)
1460     uncons = ([a1 .1.] -- a1 [.1.])
1461
1462
1463 ## Functions that use the Stack
1464
1465 Consider the `stack` function which grabs the whole stack, quotes it, and puts it on itself:
1466
1467     stack (...     -- ... [...]        )
1468     stack (... a   -- ... a [a ...]    )
1469     stack (... b a -- ... b a [a b ...])
1470
1471 We would like to represent this in Python somehow.
1472 To do this we use a simple, elegant trick.
1473
1474     stack         S   -- (         S,           S)
1475     stack     (a, S)  -- (     (a, S),      (a, S))
1476     stack (a, (b, S)) -- ( (a, (b, S)), (a, (b, S)))
1477
1478 Instead of representing the stack effect comments as a single tuple (with N items in it) we use the same cons-list structure to hold the sequence and `unify()` the whole comments.
1479
1480 ### `stack∘uncons`
1481 Let's try composing `stack` and `uncons`.  We want this result:
1482
1483     stack∘uncons (... a -- ... a a [...])
1484
1485 The stack effects are:
1486
1487     stack = S -- (S, S)
1488
1489     uncons = ((a, Z), S) -- (Z, (a, S))
1490
1491 Unifying:
1492
1493       S    -- (S, S) ∘ ((a, Z), S) -- (Z, (a,   S   ))
1494                                                         w/ { S: (a, Z) }
1495     (a, Z) --        ∘             -- (Z, (a, (a, Z)))
1496
1497 So:
1498
1499     stack∘uncons == (a, Z) -- (Z, (a, (a, Z)))
1500
1501 It works.
1502
1503 ### `stack∘uncons∘uncons`
1504 Let's try `stack∘uncons∘uncons`:
1505
1506     (a, S     ) -- (S,      (a, (a, S     ))) ∘ ((b, Z),  S`             ) -- (Z, (b,   S`   ))
1507
1508                                                                                     w/ { S: (b, Z) }
1509
1510     (a, (b, Z)) -- ((b, Z), (a, (a, (b, Z)))) ∘ ((b, Z),  S`             ) -- (Z, (b,   S`   ))
1511
1512                                                                                     w/ { S`: (a, (a, (b, Z))) }
1513
1514     (a, (b, Z)) -- ((b, Z), (a, (a, (b, Z)))) ∘ ((b, Z), (a, (a, (b, Z)))) -- (Z, (b, (a, (a, (b, Z)))))
1515
1516     (a, (b, Z)) -- (Z, (b, (a, (a, (b, Z)))))
1517
1518 It works.
1519
1520 #### `compose()` version 2
1521 This function has to be modified to use the new datastructures and it is no longer recursive, instead recursion happens as part of unification.
1522
1523
1524 ```python
1525 def compose(f, g):
1526
1527     (f_in, f_out), (g_in, g_out) = f, g
1528
1529     if not g_in:
1530         fg_in, fg_out = f_in, stack_concat(g_out, f_out)
1531
1532     elif not f_out:
1533         fg_in, fg_out = stack_concat(f_in, g_in), g_out
1534
1535     else: # Unify and update.
1536
1537         s = unify(g_in, f_out)
1538
1539         if s == False:  # s can also be the empty dict, which is ok.
1540             raise TypeError('Cannot unify %r and %r.' % (fo, gi))
1541
1542         fg_in, fg_out = update(s, (f_in, g_out))
1543
1544     return fg_in, fg_out
1545
1546
1547 stack_concat = lambda q, e: (q[0], stack_concat(q[1], e)) if q else e
1548 ```
1549
1550 I don't want to rewrite all the defs myself, so I'll write a little conversion function instead.  This is programmer's laziness.
1551
1552
1553 ```python
1554 def sequence_to_stack(seq, stack=StackJoyType(23)):
1555     for item in seq: stack = item, stack
1556     return stack
1557
1558 NEW_DEFS = {
1559     name: (sequence_to_stack(i), sequence_to_stack(o))
1560     for name, (i, o) in DEFS.iteritems()
1561 }
1562
1563 globals().update(NEW_DEFS)
1564 ```
1565
1566
1567 ```python
1568 stack = S[0], (S[0], S[0])
1569 ```
1570
1571
1572 ```python
1573 C(stack, uncons)
1574 ```
1575
1576
1577
1578
1579     ((a0, s0), (s0, (a0, (a0, s0))))
1580
1581
1582
1583
1584 ```python
1585 C(C(stack, uncons), uncons)
1586 ```
1587
1588
1589
1590
1591     ((a0, (a1, s0)), (s0, (a1, (a0, (a0, (a1, s0))))))
1592
1593
1594
1595 The display function should be changed too.
1596
1597 ### `doc_from_stack_effect()` version 2
1598 Clunky junk, but it will suffice for now.
1599
1600
1601 ```python
1602 def doc_from_stack_effect(inputs, outputs):
1603     switch = [False]  # Do we need to display the '...' for the rest of the main stack?
1604     i, o = _f(inputs, switch), _f(outputs, switch)
1605     if switch[0]:
1606         i.append('...')
1607         o.append('...')
1608     return '(%s--%s)' % (
1609         ' '.join(reversed([''] + i)),
1610         ' '.join(reversed(o + [''])),
1611     )
1612
1613
1614 def _f(term, switch):
1615     a = []
1616     while term and isinstance(term, tuple):
1617         item, term = term
1618         a.append(item)
1619     assert isinstance(term, StackJoyType), repr(term)
1620     a = [_to_str(i, term, switch) for i in a]
1621     return a
1622
1623
1624 def _to_str(term, stack, switch):
1625     if not isinstance(term, tuple):
1626         if term == stack:
1627             switch[0] = True
1628             return '[...]'
1629         return (
1630             '[.%i.]' % term.number
1631             if isinstance(term, StackJoyType)
1632             else str(term)
1633         )
1634
1635     a = []
1636     while term and isinstance(term, tuple):
1637         item, term = term
1638         a.append(_to_str(item, stack, switch))
1639     assert isinstance(term, StackJoyType), repr(term)
1640     if term == stack:
1641         switch[0] = True
1642         end = '...'
1643     else:
1644         end = '.%i.' % term.number
1645     a.append(end)
1646     return '[%s]' % ' '.join(a)
1647 ```
1648
1649
1650 ```python
1651 for name, stack_effect_comment in sorted(NEW_DEFS.items()):
1652     print name, '=', doc_from_stack_effect(*stack_effect_comment)
1653 ```
1654
1655     ccons = (a0 a1 [.0.] -- [a0 a1 .0.])
1656     cons = (a1 [.1.] -- [a1 .1.])
1657     divmod_ = (n2 n1 -- n4 n3)
1658     dup = (a1 -- a1 a1)
1659     dupd = (a2 a1 -- a2 a2 a1)
1660     first = ([a1 .1.] -- a1)
1661     mul = (n1 n2 -- n3)
1662     over = (a2 a1 -- a2 a1 a2)
1663     pm = (n2 n1 -- n4 n3)
1664     pop = (a1 --)
1665     popd = (a2 a1 -- a1)
1666     popdd = (a3 a2 a1 -- a2 a1)
1667     popop = (a2 a1 --)
1668     pred = (n1 -- n2)
1669     rest = ([a1 .1.] -- [.1.])
1670     roll_down = (a1 a2 a3 -- a2 a3 a1)
1671     roll_up = (a1 a2 a3 -- a3 a1 a2)
1672     rrest = ([a0 a1 .0.] -- [.0.])
1673     second = ([a0 a1 .0.] -- a1)
1674     sqrt = (n0 -- n1)
1675     succ = (n1 -- n2)
1676     swap = (a1 a2 -- a2 a1)
1677     swons = ([.0.] a0 -- [a0 .0.])
1678     third = ([a0 a1 a2 .0.] -- a2)
1679     tuck = (a2 a1 -- a1 a2 a1)
1680     uncons = ([a1 .1.] -- a1 [.1.])
1681
1682
1683
1684 ```python
1685 print ; print doc_from_stack_effect(*stack)
1686 print ; print doc_from_stack_effect(*C(stack, uncons))
1687 print ; print doc_from_stack_effect(*C(C(stack, uncons), uncons))
1688 print ; print doc_from_stack_effect(*C(C(stack, uncons), cons))
1689 ```
1690
1691
1692     (... -- ... [...])
1693
1694     (... a0 -- ... a0 a0 [...])
1695
1696     (... a1 a0 -- ... a1 a0 a0 a1 [...])
1697
1698     (... a0 -- ... a0 [a0 ...])
1699
1700
1701
1702 ```python
1703 print doc_from_stack_effect(*C(ccons, stack))
1704 ```
1705
1706     (... a1 a0 [.0.] -- ... [a1 a0 .0.] [[a1 a0 .0.] ...])
1707
1708
1709
1710 ```python
1711 Q = C(ccons, stack)
1712
1713 Q
1714 ```
1715
1716
1717
1718
1719     ((s0, (a0, (a1, s1))), (((a1, (a0, s0)), s1), ((a1, (a0, s0)), s1)))
1720
1721
1722
1723 #### `compile_()` version 3
1724 This makes the `compile_()` function pretty simple as the stack effect comments are now already in the form needed for the Python code:
1725
1726
1727 ```python
1728 def compile_(name, f, doc=None):
1729     i, o = f
1730     if doc is None:
1731         doc = doc_from_stack_effect(i, o)
1732     return '''def %s(stack):
1733     """%s"""
1734     %s = stack
1735     return %s''' % (name, doc, i, o)
1736 ```
1737
1738
1739 ```python
1740 print compile_('Q', Q)
1741 ```
1742
1743     def Q(stack):
1744         """(... a1 a0 [.0.] -- ... [a1 a0 .0.] [[a1 a0 .0.] ...])"""
1745         (s0, (a0, (a1, s1))) = stack
1746         return (((a1, (a0, s0)), s1), ((a1, (a0, s0)), s1))
1747
1748
1749
1750 ```python
1751 unstack = (S[1], S[0]), S[1]
1752 enstacken = S[0], (S[0], S[1])
1753 ```
1754
1755
1756 ```python
1757 print doc_from_stack_effect(*unstack)
1758 ```
1759
1760     ([.1.] --)
1761
1762
1763
1764 ```python
1765 print doc_from_stack_effect(*enstacken)
1766 ```
1767
1768     (-- [.0.])
1769
1770
1771
1772 ```python
1773 print doc_from_stack_effect(*C(cons, unstack))
1774 ```
1775
1776     (a0 [.0.] -- a0)
1777
1778
1779
1780 ```python
1781 print doc_from_stack_effect(*C(cons, enstacken))
1782 ```
1783
1784     (a0 [.0.] -- [[a0 .0.] .1.])
1785
1786
1787
1788 ```python
1789 C(cons, unstack)
1790 ```
1791
1792
1793
1794
1795     ((s0, (a0, s1)), (a0, s0))
1796
1797
1798
1799 ## Multiple Stack Effects
1800 ...
1801
1802
1803 ```python
1804 class IntJoyType(NumberJoyType): prefix = 'i'
1805
1806
1807 F = map(FloatJoyType, _R)
1808 I = map(IntJoyType, _R)
1809 ```
1810
1811
1812 ```python
1813 muls = [
1814      ((I[2], (I[1], S[0])), (I[3], S[0])),
1815      ((F[2], (I[1], S[0])), (F[3], S[0])),
1816      ((I[2], (F[1], S[0])), (F[3], S[0])),
1817      ((F[2], (F[1], S[0])), (F[3], S[0])),
1818 ]
1819 ```
1820
1821
1822 ```python
1823 for f in muls:
1824     print doc_from_stack_effect(*f)
1825 ```
1826
1827     (i1 i2 -- i3)
1828     (i1 f2 -- f3)
1829     (f1 i2 -- f3)
1830     (f1 f2 -- f3)
1831
1832
1833
1834 ```python
1835 for f in muls:
1836     try:
1837         e = C(dup, f)
1838     except TypeError:
1839         continue
1840     print doc_from_stack_effect(*dup), doc_from_stack_effect(*f), doc_from_stack_effect(*e)
1841 ```
1842
1843     (a1 -- a1 a1) (i1 i2 -- i3) (i0 -- i1)
1844     (a1 -- a1 a1) (f1 f2 -- f3) (f0 -- f1)
1845
1846
1847
1848 ```python
1849 from itertools import product
1850
1851
1852 def meta_compose(F, G):
1853     for f, g in product(F, G):
1854         try:
1855             yield C(f, g)
1856         except TypeError:
1857             pass
1858
1859
1860 def MC(F, G):
1861     return sorted(set(meta_compose(F, G)))
1862 ```
1863
1864
1865 ```python
1866 for f in MC([dup], muls):
1867     print doc_from_stack_effect(*f)
1868 ```
1869
1870     (f0 -- f1)
1871     (i0 -- i1)
1872
1873
1874
1875 ```python
1876 for f in MC([dup], [mul]):
1877     print doc_from_stack_effect(*f)
1878 ```
1879
1880     (n0 -- n1)
1881
1882
1883 ## `concat`
1884
1885 How to deal with `concat`?
1886
1887     concat ([.0.] [.1.] -- [.0. .1.])
1888
1889 We would like to represent this in Python somehow...
1890
1891
1892 ```python
1893 concat = (S[0], S[1]), ((S[0], S[1]),)
1894 ```
1895
1896 But this is actually `cons` with the first argument restricted to be a stack:
1897
1898     ([.0.] [.1.] -- [[.0.] .1.])
1899
1900 What we have implemented so far would actually only permit:
1901
1902     ([.0.] [.1.] -- [.2.])
1903
1904
1905 ```python
1906 concat = (S[0], S[1]), (S[2],)
1907 ```
1908
1909
1910 Which works but can lose information.  Consider `cons concat`, this is how much information we *could* retain:
1911
1912     (1 [.0.] [.1.] -- [1 .0. .1.])
1913
1914 As opposed to just:
1915
1916     (1 [.0.] [.1.] -- [.2.])
1917
1918 ### Brzo...'s Derivitives of Regular Expressions
1919
1920 We can invent a new type of type variable, a "sequence type" (I think this is what they mean in the literature by that term...) or "Kleene Star" type.  I'm going to represent it as a type letter and the asterix, so a sequence of zero or more `AnyJoyType` variables would be:
1921
1922     A*
1923
1924 The `A*` works by splitting the universe into two alternate histories:
1925
1926     A* -> 0 | A A*
1927
1928 The Kleene star variable disappears in one universe, and in the other it turns into an `AnyJoyType` variable followed by itself again.  We have to return all universes (represented by their substitution dicts, the "unifiers") that don't lead to type conflicts.
1929
1930 Consider unifying two stacks (the lowercase letters are any type variables of the kinds we have defined so far):
1931
1932     [a A* b .0.] U [c d .1.]
1933                               w/ {c: a}
1934     [  A* b .0.] U [  d .1.]
1935
1936 Now we have to split universes to unify `A*`.  In the first universe it disappears:
1937
1938     [b .0.] U [d .1.]
1939                        w/ {d: b, .1.: .0.}
1940          [] U []
1941
1942 While in the second it spawns an `A`, which we will label `e`:
1943
1944     [e A* b .0.] U [d .1.]
1945                             w/ {d: e}
1946     [  A* b .0.] U [  .1.]
1947                             w/ {.1.: A* b .0.}
1948     [  A* b .0.] U [  .1.]
1949
1950 Giving us two unifiers:
1951
1952     {c: a,  d: b,  .1.:      .0.}
1953     {c: a,  d: e,  .1.: A* b .0.}
1954
1955
1956 ```python
1957 class KleeneStar(object):
1958
1959     kind = AnyJoyType
1960
1961     def __init__(self, number):
1962         self.number = number
1963         self.count = 0
1964         self.prefix = repr(self)
1965
1966     def __repr__(self):
1967         return '%s%i*' % (self.kind.prefix, self.number)
1968
1969     def another(self):
1970         self.count += 1
1971         return self.kind(10000 * self.number + self.count)
1972
1973     def __eq__(self, other):
1974         return (
1975             isinstance(other, self.__class__)
1976             and other.number == self.number
1977         )
1978
1979     def __ge__(self, other):
1980         return self.kind >= other.kind
1981
1982     def __add__(self, other):
1983         return self.__class__(self.number + other)
1984     __radd__ = __add__
1985
1986     def __hash__(self):
1987         return hash(repr(self))
1988
1989 class AnyStarJoyType(KleeneStar): kind = AnyJoyType
1990 class NumberStarJoyType(KleeneStar): kind = NumberJoyType
1991 #class FloatStarJoyType(KleeneStar): kind = FloatJoyType
1992 #class IntStarJoyType(KleeneStar): kind = IntJoyType
1993 class StackStarJoyType(KleeneStar): kind = StackJoyType
1994
1995
1996 As = map(AnyStarJoyType, _R)
1997 Ns = map(NumberStarJoyType, _R)
1998 Ss = map(StackStarJoyType, _R)
1999 ```
2000
2001 #### `unify()` version 4
2002 Can now return multiple results...
2003
2004
2005 ```python
2006 def unify(u, v, s=None):
2007     if s is None:
2008         s = {}
2009     elif s:
2010         u = update(s, u)
2011         v = update(s, v)
2012
2013     if u == v:
2014         return s,
2015
2016     if isinstance(u, AnyJoyType) and isinstance(v, AnyJoyType):
2017         if u >= v:
2018             s[u] = v
2019             return s,
2020         if v >= u:
2021             s[v] = u
2022             return s,
2023         raise TypeError('Cannot unify %r and %r.' % (u, v))
2024
2025     if isinstance(u, tuple) and isinstance(v, tuple):
2026         if len(u) != len(v) != 2:
2027             raise TypeError(repr((u, v)))
2028
2029         a, b = v
2030         if isinstance(a, KleeneStar):
2031             # Two universes, in one the Kleene star disappears and unification
2032             # continues without it...
2033             s0 = unify(u, b)
2034
2035             # In the other it spawns a new variable.
2036             s1 = unify(u, (a.another(), v))
2037
2038             t = s0 + s1
2039             for sn in t:
2040                 sn.update(s)
2041             return t
2042
2043         a, b = u
2044         if isinstance(a, KleeneStar):
2045             s0 = unify(v, b)
2046             s1 = unify(v, (a.another(), u))
2047             t = s0 + s1
2048             for sn in t:
2049                 sn.update(s)
2050             return t
2051
2052         ses = unify(u[0], v[0])
2053         results = ()
2054         for sn in ses:
2055             results += unify(u[1], v[1], sn)
2056         return results
2057
2058     if isinstance(v, tuple):
2059         if not stacky(u):
2060             raise TypeError('Cannot unify %r and %r.' % (u, v))
2061         s[u] = v
2062         return s,
2063
2064     if isinstance(u, tuple):
2065         if not stacky(v):
2066             raise TypeError('Cannot unify %r and %r.' % (v, u))
2067         s[v] = u
2068         return s,
2069
2070     return ()
2071
2072
2073 def stacky(thing):
2074     return thing.__class__ in {AnyJoyType, StackJoyType}
2075 ```
2076
2077
2078 ```python
2079 a = (As[1], S[1])
2080 a
2081 ```
2082
2083
2084
2085
2086     (a1*, s1)
2087
2088
2089
2090
2091 ```python
2092 b = (A[1], S[2])
2093 b
2094 ```
2095
2096
2097
2098
2099     (a1, s2)
2100
2101
2102
2103
2104 ```python
2105 for result in unify(b, a):
2106     print result, '->', update(result, a), update(result, b)
2107 ```
2108
2109     {s1: (a1, s2)} -> (a1*, (a1, s2)) (a1, s2)
2110     {a1: a10001, s2: (a1*, s1)} -> (a1*, s1) (a10001, (a1*, s1))
2111
2112
2113
2114 ```python
2115 for result in unify(a, b):
2116     print result, '->', update(result, a), update(result, b)
2117 ```
2118
2119     {s1: (a1, s2)} -> (a1*, (a1, s2)) (a1, s2)
2120     {a1: a10002, s2: (a1*, s1)} -> (a1*, s1) (a10002, (a1*, s1))
2121
2122
2123
2124     (a1*, s1)       [a1*]       (a1, s2)        [a1]
2125
2126     (a1*, (a1, s2)) [a1* a1]    (a1, s2)        [a1]
2127
2128     (a1*, s1)       [a1*]       (a2, (a1*, s1)) [a2 a1*]
2129
2130
2131 ```python
2132 sum_ = ((Ns[1], S[1]), S[0]), (N[0], S[0])
2133
2134 print doc_from_stack_effect(*sum_)
2135 ```
2136
2137     ([n1* .1.] -- n0)
2138
2139
2140
2141 ```python
2142 f = (N[1], (N[2], (N[3], S[1]))), S[0]
2143
2144 print doc_from_stack_effect(S[0], f)
2145 ```
2146
2147     (-- [n1 n2 n3 .1.])
2148
2149
2150
2151 ```python
2152 for result in unify(sum_[0], f):
2153     print result, '->', update(result, sum_[1])
2154 ```
2155
2156     {s1: (n1, (n2, (n3, s1)))} -> (n0, s0)
2157     {n1: n10001, s1: (n2, (n3, s1))} -> (n0, s0)
2158     {n1: n10001, s1: (n3, s1), n2: n10002} -> (n0, s0)
2159     {n1: n10001, s1: (n1*, s1), n3: n10003, n2: n10002} -> (n0, s0)
2160
2161
2162 #### `compose()` version 3
2163 This function has to be modified to use the new datastructures and it is no longer recursive, instead recursion happens as part of unification.
2164
2165
2166 ```python
2167 def compose(f, g):
2168
2169     (f_in, f_out), (g_in, g_out) = f, g
2170
2171     if not g_in:
2172         yield f_in, stack_concat(g_out, f_out)
2173
2174     elif not f_out:
2175         yield stack_concat(f_in, g_in), g_out
2176
2177     else: # Unify and update.
2178
2179         s = unify(g_in, f_out)
2180
2181         if not s:
2182             raise TypeError('Cannot unify %r and %r.' % (fo, gi))
2183
2184         for result in s:
2185             yield update(result, (f_in, g_out))
2186
2187 ```
2188
2189
2190 ```python
2191 def meta_compose(F, G):
2192     for f, g in product(F, G):
2193         try:
2194             for result in C(f, g):
2195                 yield result
2196         except TypeError:
2197             pass
2198
2199
2200 def C(f, g):
2201     f, g = relabel(f, g)
2202     for fg in compose(f, g):
2203         yield delabel(fg)
2204 ```
2205
2206
2207 ```python
2208 for f in MC([dup], muls):
2209     print doc_from_stack_effect(*f)
2210 ```
2211
2212     (a0 -- f0)
2213     (a0 -- i0)
2214
2215
2216
2217 ```python
2218
2219
2220 for f in MC([dup], [sum_]):
2221     print doc_from_stack_effect(*f)
2222 ```
2223
2224     ([n0* .0.] -- [n0* .0.] n0)
2225
2226
2227
2228 ```python
2229
2230
2231 for f in MC([cons], [sum_]):
2232     print doc_from_stack_effect(*f)
2233 ```
2234
2235     (a0 [.0.] -- n0)
2236     (n0 [n0* .0.] -- n1)
2237
2238
2239
2240 ```python
2241 sum_ = (((N[1], (Ns[1], S[1])), S[0]), (N[0], S[0]))
2242 print doc_from_stack_effect(*cons),
2243 print doc_from_stack_effect(*sum_),
2244
2245 for f in MC([cons], [sum_]):
2246     print doc_from_stack_effect(*f)
2247 ```
2248
2249     (a1 [.1.] -- [a1 .1.]) ([n1 n1* .1.] -- n0) (n0 [n0* .0.] -- n1)
2250
2251
2252
2253 ```python
2254 a = (A[4], (As[1], (A[3], S[1])))
2255 a
2256 ```
2257
2258
2259
2260
2261     (a4, (a1*, (a3, s1)))
2262
2263
2264
2265
2266 ```python
2267 b = (A[1], (A[2], S[2]))
2268 b
2269 ```
2270
2271
2272
2273
2274     (a1, (a2, s2))
2275
2276
2277
2278
2279 ```python
2280 for result in unify(b, a):
2281     print result
2282 ```
2283
2284     {a1: a4, s2: s1, a2: a3}
2285     {a1: a4, s2: (a1*, (a3, s1)), a2: a10003}
2286
2287
2288
2289 ```python
2290 for result in unify(a, b):
2291     print result
2292 ```
2293
2294     {s2: s1, a2: a3, a4: a1}
2295     {s2: (a1*, (a3, s1)), a2: a10004, a4: a1}
2296
2297
2298 ### represent `concat`
2299
2300     ([.0.] [.1.] -- [A*(.0.) .1.])
2301
2302 Meaning that `A*` on the right-hand side should all the crap from `.0.`.
2303
2304     ([      .0.] [.1.] -- [      A* .1.])
2305     ([a     .0.] [.1.] -- [a     A* .1.])
2306     ([a b   .0.] [.1.] -- [a b   A* .1.])
2307     ([a b c .0.] [.1.] -- [a b c A* .1.])
2308
2309
2310
2311 or...
2312
2313     ([       .0.] [.1.] -- [       .1.])
2314     ([a      .0.] [.1.] -- [a      .1.])
2315     ([a b    .0.] [.1.] -- [a b    .1.])
2316     ([a b  c .0.] [.1.] -- [a b  c .1.])
2317     ([a A* c .0.] [.1.] -- [a A* c .1.])
2318
2319
2320
2321     (a, (b, S0)) . S1 = (a, (b, (A*, S1)))
2322
2323
2324 ```python
2325 class Astar(object):
2326     def __repr__(self):
2327         return 'A*'
2328
2329
2330 def concat(s0, s1):
2331     a = []
2332     while isinstance(s0, tuple):
2333         term, s0 = s0
2334         a.append(term)
2335     assert isinstance(s0, StackJoyType), repr(s0)
2336     s1 = Astar(), s1
2337     for term in reversed(a):
2338         s1 = term, s1
2339     return s1
2340 ```
2341
2342
2343 ```python
2344 a, b = (A[1], S[0]), (A[2], S[1])
2345 ```
2346
2347
2348 ```python
2349 concat(a, b)
2350 ```
2351
2352
2353
2354
2355     (a1, (A*, (a2, s1)))
2356
2357
2358
2359 ## Joy in the Logical Paradigm
2360 For this to work the type label classes have to be modified to let `T >= t` succeed, where e.g. `T` is `IntJoyType` and `t` is `int`
2361
2362
2363 ```python
2364 F = reduce(C, (pop, swap, roll_down, rest, rest, cons, cons))
2365
2366 print doc_from_stack_effect(*F)
2367 ```
2368
2369
2370     ---------------------------------------------------------------------------
2371
2372     ValueError                                Traceback (most recent call last)
2373
2374     <ipython-input-113-4b4cb6ff86e5> in <module>()
2375           1 F = reduce(C, (pop, swap, roll_down, rest, rest, cons, cons))
2376           2
2377     ----> 3 print doc_from_stack_effect(*F)
2378
2379
2380     <ipython-input-101-ddee30dbb1a6> in C(f, g)
2381          10 def C(f, g):
2382          11     f, g = relabel(f, g)
2383     ---> 12     for fg in compose(f, g):
2384          13         yield delabel(fg)
2385
2386
2387     <ipython-input-100-4237a6bb159d> in compose(f, g)
2388           1 def compose(f, g):
2389           2
2390     ----> 3     (f_in, f_out), (g_in, g_out) = f, g
2391           4
2392           5     if not g_in:
2393
2394
2395     <ipython-input-101-ddee30dbb1a6> in C(f, g)
2396          10 def C(f, g):
2397          11     f, g = relabel(f, g)
2398     ---> 12     for fg in compose(f, g):
2399          13         yield delabel(fg)
2400
2401
2402     <ipython-input-100-4237a6bb159d> in compose(f, g)
2403           1 def compose(f, g):
2404           2
2405     ----> 3     (f_in, f_out), (g_in, g_out) = f, g
2406           4
2407           5     if not g_in:
2408
2409
2410     <ipython-input-101-ddee30dbb1a6> in C(f, g)
2411          10 def C(f, g):
2412          11     f, g = relabel(f, g)
2413     ---> 12     for fg in compose(f, g):
2414          13         yield delabel(fg)
2415
2416
2417     <ipython-input-100-4237a6bb159d> in compose(f, g)
2418           1 def compose(f, g):
2419           2
2420     ----> 3     (f_in, f_out), (g_in, g_out) = f, g
2421           4
2422           5     if not g_in:
2423
2424
2425     <ipython-input-101-ddee30dbb1a6> in C(f, g)
2426          10 def C(f, g):
2427          11     f, g = relabel(f, g)
2428     ---> 12     for fg in compose(f, g):
2429          13         yield delabel(fg)
2430
2431
2432     <ipython-input-100-4237a6bb159d> in compose(f, g)
2433           1 def compose(f, g):
2434           2
2435     ----> 3     (f_in, f_out), (g_in, g_out) = f, g
2436           4
2437           5     if not g_in:
2438
2439
2440     <ipython-input-101-ddee30dbb1a6> in C(f, g)
2441          10 def C(f, g):
2442          11     f, g = relabel(f, g)
2443     ---> 12     for fg in compose(f, g):
2444          13         yield delabel(fg)
2445
2446
2447     <ipython-input-100-4237a6bb159d> in compose(f, g)
2448           1 def compose(f, g):
2449           2
2450     ----> 3     (f_in, f_out), (g_in, g_out) = f, g
2451           4
2452           5     if not g_in:
2453
2454
2455     ValueError: need more than 1 value to unpack
2456
2457
2458
2459 ```python
2460 from joy.parser import text_to_expression
2461 ```
2462
2463
2464 ```python
2465 s = text_to_expression('[3 4 ...] 2 1')
2466 s
2467 ```
2468
2469
2470 ```python
2471 L = unify(F[1], s)
2472 L
2473 ```
2474
2475
2476 ```python
2477 F[1]
2478 ```
2479
2480
2481 ```python
2482 F[1][0]
2483 ```
2484
2485
2486 ```python
2487 s[0]
2488 ```
2489
2490 ## Typing Combinators
2491
2492 TBD
2493
2494 This is an open subject.
2495
2496 The obvious thing is that you now need two pairs of tuples to describe the combinators' effects,  a stack effect comment and an expression effect comment:
2497
2498     dip (a [F] --)--(-- F a)
2499
2500 One thing that might help is...
2501
2502 ## Abstract Interpretation
2503
2504 ## Something else...
2505     [4 5 ...] 2 1 0 pop∘swap∘roll<∘rest∘rest∘cons∘cons
2506     [4 5 ...] 2 1       swap∘roll<∘rest∘rest∘cons∘cons
2507     [4 5 ...] 1 2            roll<∘rest∘rest∘cons∘cons
2508     1 2 [4 5 ...]                  rest∘rest∘cons∘cons
2509     1 2   [5 ...]                       rest∘cons∘cons
2510     1 2     [...]                            cons∘cons
2511     1     [2 ...]                                 cons
2512         [1 2 ...]
2513
2514 Eh?