docs/Types.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "metadata": {},
   6    "source": [
   7     "# The Blissful Elegance of Typing Joy\n",
   8     "\n",
   9     "This notebook presents a simple type inferencer for Joy code.  It can infer the stack effect of most Joy expressions.  It's built largely by means of existing ideas and research.  (A great overview of the existing knowledge is a talk [\"Type Inference in Stack-Based Programming Languages\"](http://prl.ccs.neu.edu/blog/2017/03/10/type-inference-in-stack-based-programming-languages/) given by Rob Kleffner on or about 2017-03-10 as part of a course on the history of programming languages.)\n",
  10     "\n",
  11     "The notebook starts with a simple inferencer based on the work of Jaanus Pöial which we then progressively elaborate to cover more Joy semantics.  Along the way we write a simple \"compiler\" that emits Python code for what I like to call Yin functions.  (Yin functions are those that only rearrange values in stacks, as opposed to Yang functions that actually work on the values themselves.)\n",
  12     "\n"
  13    ]
  14   },
  15   {
  16    "cell_type": "markdown",
  17    "metadata": {},
  18    "source": [
  19     "## Part I: Pöial's Rules\n",
  20     "\n",
  21     "[\"Typing Tools for Typeless Stack Languages\" by Jaanus Pöial\n",
  22     "](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.212.6026)\n",
  23     "\n",
  24     "    @INPROCEEDINGS{Pöial06typingtools,\n",
  25     "        author = {Jaanus Pöial},\n",
  26     "        title = {Typing tools for typeless stack languages},\n",
  27     "        booktitle = {In 23rd Euro-Forth Conference},\n",
  28     "        year = {2006},\n",
  29     "        pages = {40--46}\n",
  30     "    }"
  31    ]
  32   },
  33   {
  34    "cell_type": "markdown",
  35    "metadata": {},
  36    "source": [
  37     "### First Rule\n",
  38     "This rule deals with functions (and literals) that put items on the stack `(-- d)`:\n",
  39     "\n",
  40     "\n",
  41     "       (a -- b)∘(-- d)\n",
  42     "    ---------------------\n",
  43     "         (a -- b d)"
  44    ]
  45   },
  46   {
  47    "cell_type": "markdown",
  48    "metadata": {},
  49    "source": [
  50     "### Second Rule\n",
  51     "This rule deals with functions that consume items from the stack `(a --)`:\n",
  52     "\n",
  53     "       (a --)∘(c -- d)\n",
  54     "    ---------------------\n",
  55     "         (c a -- d)"
  56    ]
  57   },
  58   {
  59    "cell_type": "markdown",
  60    "metadata": {},
  61    "source": [
  62     "### Third Rule\n",
  63     "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*](https://en.wikipedia.org/wiki/Robinson's_unification_algorithm) or a type conflict declared.\n",
  64     "\n",
  65     "       (a -- b t[i])∘(c u[j] -- d)   t <= u (t is subtype of u)\n",
  66     "    -------------------------------\n",
  67     "       (a -- b     )∘(c      -- d)   t[i] == t[k] == u[j]\n",
  68     "                                             ^\n",
  69     "\n",
  70     "       (a -- b t[i])∘(c u[j] -- d)   u <= t (u is subtype of t)\n",
  71     "    -------------------------------\n",
  72     "       (a -- b     )∘(c      -- d)   t[i] == u[k] == u[j]"
  73    ]
  74   },
  75   {
  76    "cell_type": "markdown",
  77    "metadata": {},
  78    "source": [
  79     "Let's work through some examples by hand to develop an intuition for the algorithm."
  80    ]
  81   },
  82   {
  83    "cell_type": "markdown",
  84    "metadata": {},
  85    "source": [
  86     "There's a function in one of the other notebooks.\n",
  87     "\n",
  88     "    F == pop swap roll< rest rest cons cons\n",
  89     "\n",
  90     "It's all \"stack chatter\" and list manipulation so we should be able to deduce its type."
  91    ]
  92   },
  93   {
  94    "cell_type": "markdown",
  95    "metadata": {},
  96    "source": [
  97     "### Stack Effect Comments\n",
  98     "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):\n",
  99     "\n",
 100     "    pop (1 --)\n",
 101     "\n",
 102     "    swap (1 2 -- 2 1)\n",
 103     "\n",
 104     "    roll< (1 2 3 -- 2 3 1)\n",
 105     "\n",
 106     "These commands alter the stack but don't \"look at\" the values so these numbers represent an \"Any type\"."
 107    ]
 108   },
 109   {
 110    "cell_type": "markdown",
 111    "metadata": {},
 112    "source": [
 113     "### `pop swap`\n",
 114     "\n",
 115     "    (1 --) (1 2 -- 2 1)\n",
 116     "    \n",
 117     "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:\n",
 118     "\n",
 119     "    (0 --) (1 2 -- 2 1)\n",
 120     "\n",
 121     "Following the second rule:\n",
 122     "    \n",
 123     "    (1 2 0 -- 2 1)"
 124    ]
 125   },
 126   {
 127    "cell_type": "markdown",
 128    "metadata": {},
 129    "source": [
 130     "### `pop∘swap roll<`\n",
 131     "\n",
 132     "    (1 2 0 -- 2 1) (1 2 3 -- 2 3 1)\n",
 133     "\n",
 134     "Let's re-label them:\n",
 135     "\n",
 136     "    (1a 2a 0a -- 2a 1a) (1b 2b 3b -- 2b 3b 1b)"
 137    ]
 138   },
 139   {
 140    "cell_type": "markdown",
 141    "metadata": {},
 142    "source": [
 143     "Now we follow the rules.\n",
 144     "\n",
 145     "We must unify `1a` and `3b`, and `2a` and `2b`, replacing the terms in the forms:\n",
 146     "\n",
 147     "    (1a 2a 0a -- 2a 1a) (1b 2b 3b -- 2b 3b 1b)\n",
 148     "                                                w/  {1a: 3b}\n",
 149     "    (3b 2a 0a -- 2a   ) (1b 2b    -- 2b 3b 1b)\n",
 150     "                                                w/  {2a: 2b}\n",
 151     "    (3b 2b 0a --      ) (1b       -- 2b 3b 1b)\n",
 152     "\n",
 153     "Here we must apply the second rule:\n",
 154     "\n",
 155     "       (3b 2b 0a --) (1b -- 2b 3b 1b)\n",
 156     "    -----------------------------------\n",
 157     "         (1b 3b 2b 0a -- 2b 3b 1b)\n",
 158     "\n",
 159     "Now we de-label the type, uh, labels:\n",
 160     "\n",
 161     "    (1b 3b 2b 0a -- 2b 3b 1b)\n",
 162     "\n",
 163     "    w/ {\n",
 164     "        1b: 1,\n",
 165     "        3b: 2,\n",
 166     "        2b: 3,\n",
 167     "        0a: 0,\n",
 168     "        }\n",
 169     "\n",
 170     "    (1 2 3 0 -- 3 2 1)\n",
 171     "\n",
 172     "And now we have the stack effect comment for `pop∘swap∘roll<`."
 173    ]
 174   },
 175   {
 176    "cell_type": "markdown",
 177    "metadata": {},
 178    "source": [
 179     "### Compiling `pop∘swap∘roll<`\n",
 180     "The simplest way to \"compile\" this function would be something like:"
 181    ]
 182   },
 183   {
 184    "cell_type": "code",
 185    "execution_count": 1,
 186    "metadata": {},
 187    "outputs": [],
 188    "source": [
 189     "def poswrd(s, e, d):\n",
 190     "    return rolldown(*swap(*pop(s, e, d)))"
 191    ]
 192   },
 193   {
 194    "cell_type": "markdown",
 195    "metadata": {},
 196    "source": [
 197     "However, internally this function would still be allocating tuples (stack cells) and doing other unnecesssary work.\n",
 198     "\n",
 199     "Looking ahead for a moment, from the stack effect comment:\n",
 200     "\n",
 201     "    (1 2 3 0 -- 3 2 1)\n",
 202     "\n",
 203     "We should be able to directly write out a Python function like:"
 204    ]
 205   },
 206   {
 207    "cell_type": "code",
 208    "execution_count": 2,
 209    "metadata": {},
 210    "outputs": [],
 211    "source": [
 212     "def poswrd(stack):\n",
 213     "    (_, (a, (b, (c, stack)))) = stack\n",
 214     "    return (c, (b, (a, stack)))"
 215    ]
 216   },
 217   {
 218    "cell_type": "markdown",
 219    "metadata": {},
 220    "source": [
 221     "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."
 222    ]
 223   },
 224   {
 225    "cell_type": "markdown",
 226    "metadata": {},
 227    "source": [
 228     "### Functions on Stacks\n",
 229     "These are slightly tricky.\n",
 230     "\n",
 231     "    rest ( [1 ...] -- [...] )\n",
 232     "\n",
 233     "    cons ( 1 [...] -- [1 ...] )"
 234    ]
 235   },
 236   {
 237    "cell_type": "markdown",
 238    "metadata": {},
 239    "source": [
 240     "### `pop∘swap∘roll< rest`\n",
 241     "\n",
 242     "    (1 2 3 0 -- 3 2 1) ([1 ...] -- [...])\n",
 243     "\n",
 244     "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):\n",
 245     "\n",
 246     "    (1 2 3 0 -- 3 2 1) ([4 ...] -- [...])\n",
 247     "\n",
 248     "Unify and update:\n",
 249     "\n",
 250     "    (1       2 3 0 -- 3 2 1) ([4 ...] -- [...])\n",
 251     "                                                 w/ {1: [4 ...]}\n",
 252     "    ([4 ...] 2 3 0 -- 3 2  ) (        -- [...])\n",
 253     "\n",
 254     "Apply the first rule:\n",
 255     "\n",
 256     "       ([4 ...] 2 3 0 -- 3 2) (-- [...])\n",
 257     "    ---------------------------------------\n",
 258     "         ([4 ...] 2 3 0 -- 3 2 [...])\n",
 259     "\n",
 260     "And there we are."
 261    ]
 262   },
 263   {
 264    "cell_type": "markdown",
 265    "metadata": {},
 266    "source": [
 267     "### `pop∘swap∘roll<∘rest rest`\n",
 268     "\n",
 269     "Let's do it again.\n",
 270     "\n",
 271     "    ([4 ...] 2 3 0 -- 3 2 [...]) ([1 ...] -- [...])\n",
 272     "\n",
 273     "Re-label (the tails of the lists on each side each get their own label):\n",
 274     "\n",
 275     "    ([4 .0.] 2 3 0 -- 3 2 [.0.]) ([5 .1.] -- [.1.])\n",
 276     "\n",
 277     "Unify and update (note the opening square brackets have been omited in the substitution dict, this is deliberate and I'll explain below):\n",
 278     "\n",
 279     "    ([4 .0.]   2 3 0 -- 3 2 [.0.]  ) ([5 .1.] -- [.1.])\n",
 280     "                                                        w/ { .0.] : 5 .1.] }\n",
 281     "    ([4 5 .1.] 2 3 0 -- 3 2 [5 .1.]) ([5 .1.] -- [.1.])"
 282    ]
 283   },
 284   {
 285    "cell_type": "markdown",
 286    "metadata": {},
 287    "source": [
 288     "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."
 289    ]
 290   },
 291   {
 292    "cell_type": "markdown",
 293    "metadata": {},
 294    "source": [
 295     "Next we unify and find our two terms are the same already: `[5 .1.]`:\n",
 296     "\n",
 297     "    ([4 5 .1.] 2 3 0 -- 3 2 [5 .1.]) ([5 .1.] -- [.1.])\n",
 298     "\n",
 299     "Giving us:\n",
 300     "\n",
 301     "    ([4 5 .1.] 2 3 0 -- 3 2) (-- [.1.])\n",
 302     "\n",
 303     "From here we apply the first rule and get:\n",
 304     "\n",
 305     "    ([4 5 .1.] 2 3 0 -- 3 2 [.1.])\n",
 306     "\n",
 307     "Cleaning up the labels:\n",
 308     "\n",
 309     "    ([4 5 ...] 2 3 1 -- 3 2 [...])\n",
 310     "\n",
 311     "This is the stack effect of `pop∘swap∘roll<∘rest∘rest`."
 312    ]
 313   },
 314   {
 315    "cell_type": "markdown",
 316    "metadata": {},
 317    "source": [
 318     "### `pop∘swap∘roll<∘rest∘rest cons`\n",
 319     "\n",
 320     "    ([4 5 ...] 2 3 1 -- 3 2 [...]) (1 [...] -- [1 ...])\n",
 321     "\n",
 322     "Re-label:\n",
 323     "\n",
 324     "    ([4 5 .1.] 2 3 1 -- 3 2 [.1.]) (6 [.2.] -- [6 .2.])\n",
 325     "\n",
 326     "Unify:\n",
 327     "\n",
 328     "    ([4 5 .1.] 2 3 1 -- 3 2 [.1.]) (6 [.2.] -- [6 .2.])\n",
 329     "                                                         w/ { .1.] : .2.] }\n",
 330     "    ([4 5 .2.] 2 3 1 -- 3 2      ) (6       -- [6 .2.])\n",
 331     "                                                         w/ {2: 6}\n",
 332     "    ([4 5 .2.] 6 3 1 -- 3        ) (        -- [6 .2.])\n",
 333     "\n",
 334     "First rule:\n",
 335     "\n",
 336     "    ([4 5 .2.] 6 3 1 -- 3 [6 .2.])\n",
 337     "\n",
 338     "Re-label:\n",
 339     "\n",
 340     "    ([4 5 ...] 2 3 1 -- 3 [2 ...])\n",
 341     "\n",
 342     "Done."
 343    ]
 344   },
 345   {
 346    "cell_type": "markdown",
 347    "metadata": {},
 348    "source": [
 349     "### `pop∘swap∘roll<∘rest∘rest∘cons cons`\n",
 350     "One more time.\n",
 351     "\n",
 352     "    ([4 5 ...] 2 3 1 -- 3 [2 ...]) (1 [...] -- [1 ...])\n",
 353     "\n",
 354     "Re-label:\n",
 355     "\n",
 356     "    ([4 5 .1.] 2 3 1 -- 3 [2 .1.]) (6 [.2.] -- [6 .2.])\n",
 357     "\n",
 358     "Unify:\n",
 359     "\n",
 360     "    ([4 5 .1.] 2 3 1 -- 3 [2 .1.]) (6 [.2.] -- [6 .2.]  )\n",
 361     "                                                           w/ { .2.] : 2 .1.] }\n",
 362     "    ([4 5 .1.] 2 3 1 -- 3        ) (6       -- [6 2 .1.])\n",
 363     "                                                           w/ {3: 6}\n",
 364     "    ([4 5 .1.] 2 6 1 --          ) (        -- [6 2 .1.])\n",
 365     "\n",
 366     "First or second rule:\n",
 367     "\n",
 368     "    ([4 5 .1.] 2 6 1 -- [6 2 .1.])\n",
 369     "\n",
 370     "Clean up the labels:\n",
 371     "\n",
 372     "    ([4 5 ...] 2 3 1 -- [3 2 ...])\n",
 373     "\n",
 374     "And there you have it, the stack effect for `pop∘swap∘roll<∘rest∘rest∘cons∘cons`.\n",
 375     "\n",
 376     "    ([4 5 ...] 2 3 1 -- [3 2 ...])"
 377    ]
 378   },
 379   {
 380    "cell_type": "markdown",
 381    "metadata": {},
 382    "source": [
 383     "From this stack effect comment it should be possible to construct the following Python code:"
 384    ]
 385   },
 386   {
 387    "cell_type": "code",
 388    "execution_count": 3,
 389    "metadata": {},
 390    "outputs": [],
 391    "source": [
 392     "def F(stack):\n",
 393     "    (_, (d, (c, ((a, (b, S0)), stack)))) = stack\n",
 394     "    return (d, (c, S0)), stack"
 395    ]
 396   },
 397   {
 398    "cell_type": "markdown",
 399    "metadata": {},
 400    "source": [
 401     "## Part II: Implementation"
 402    ]
 403   },
 404   {
 405    "cell_type": "markdown",
 406    "metadata": {},
 407    "source": [
 408     "### Representing Stack Effect Comments in Python\n",
 409     "\n",
 410     "I'm going to use pairs of tuples of type descriptors, which will be integers or tuples of type descriptors:"
 411    ]
 412   },
 413   {
 414    "cell_type": "code",
 415    "execution_count": 4,
 416    "metadata": {},
 417    "outputs": [],
 418    "source": [
 419     "roll_dn = (1, 2, 3), (2, 3, 1)\n",
 420     "\n",
 421     "pop = (1,), ()\n",
 422     "\n",
 423     "swap = (1, 2), (2, 1)"
 424    ]
 425   },
 426   {
 427    "cell_type": "markdown",
 428    "metadata": {},
 429    "source": [
 430     "### `compose()`"
 431    ]
 432   },
 433   {
 434    "cell_type": "code",
 435    "execution_count": 5,
 436    "metadata": {},
 437    "outputs": [],
 438    "source": [
 439     "def compose(f, g):\n",
 440     "\n",
 441     "    (f_in, f_out), (g_in, g_out) = f, g\n",
 442     "\n",
 443     "    # First rule.\n",
 444     "    #\n",
 445     "    #       (a -- b) (-- d)\n",
 446     "    #    ---------------------\n",
 447     "    #         (a -- b d)\n",
 448     "\n",
 449     "    if not g_in:\n",
 450     "\n",
 451     "        fg_in, fg_out = f_in, f_out + g_out\n",
 452     "\n",
 453     "    # Second rule.\n",
 454     "    #\n",
 455     "    #       (a --) (c -- d)\n",
 456     "    #    ---------------------\n",
 457     "    #         (c a -- d)\n",
 458     "\n",
 459     "    elif not f_out:\n",
 460     "\n",
 461     "        fg_in, fg_out = g_in + f_in, g_out\n",
 462     "\n",
 463     "    else: # Unify, update, recur.\n",
 464     "\n",
 465     "        fo, gi = f_out[-1], g_in[-1]\n",
 466     "\n",
 467     "        s = unify(gi, fo)\n",
 468     "\n",
 469     "        if s == False:  # s can also be the empty dict, which is ok.\n",
 470     "            raise TypeError('Cannot unify %r and %r.' % (fo, gi))\n",
 471     "\n",
 472     "        f_g = (f_in, f_out[:-1]), (g_in[:-1], g_out)\n",
 473     "\n",
 474     "        if s: f_g = update(s, f_g)\n",
 475     "\n",
 476     "        fg_in, fg_out = compose(*f_g)\n",
 477     "\n",
 478     "    return fg_in, fg_out"
 479    ]
 480   },
 481   {
 482    "cell_type": "markdown",
 483    "metadata": {},
 484    "source": [
 485     "### `unify()`"
 486    ]
 487   },
 488   {
 489    "cell_type": "code",
 490    "execution_count": 6,
 491    "metadata": {},
 492    "outputs": [],
 493    "source": [
 494     "def unify(u, v, s=None):\n",
 495     "    if s is None:\n",
 496     "        s = {}\n",
 497     "\n",
 498     "    if isinstance(u, int):\n",
 499     "        s[u] = v\n",
 500     "    elif isinstance(v, int):\n",
 501     "        s[v] = u\n",
 502     "    else:\n",
 503     "        s = False\n",
 504     "\n",
 505     "    return s"
 506    ]
 507   },
 508   {
 509    "cell_type": "markdown",
 510    "metadata": {},
 511    "source": [
 512     "### `update()`"
 513    ]
 514   },
 515   {
 516    "cell_type": "code",
 517    "execution_count": 7,
 518    "metadata": {},
 519    "outputs": [],
 520    "source": [
 521     "def update(s, term):\n",
 522     "    if not isinstance(term, tuple):\n",
 523     "        return s.get(term, term)\n",
 524     "    return tuple(update(s, inner) for inner in term)"
 525    ]
 526   },
 527   {
 528    "cell_type": "markdown",
 529    "metadata": {},
 530    "source": [
 531     "### `relabel()`"
 532    ]
 533   },
 534   {
 535    "cell_type": "code",
 536    "execution_count": 8,
 537    "metadata": {},
 538    "outputs": [
 539     {
 540      "data": {
 541       "text/plain": [
 542        "(((1,), ()), ((1001, 1002), (1002, 1001)))"
 543       ]
 544      },
 545      "execution_count": 8,
 546      "metadata": {},
 547      "output_type": "execute_result"
 548     }
 549    ],
 550    "source": [
 551     "def relabel(left, right):\n",
 552     "    return left, _1000(right)\n",
 553     "\n",
 554     "def _1000(right):\n",
 555     "    if not isinstance(right, tuple):\n",
 556     "        return 1000 + right\n",
 557     "    return tuple(_1000(n) for n in right)\n",
 558     "\n",
 559     "relabel(pop, swap)"
 560    ]
 561   },
 562   {
 563    "cell_type": "markdown",
 564    "metadata": {},
 565    "source": [
 566     "### `delabel()`"
 567    ]
 568   },
 569   {
 570    "cell_type": "code",
 571    "execution_count": 9,
 572    "metadata": {},
 573    "outputs": [
 574     {
 575      "data": {
 576       "text/plain": [
 577        "(((0,), ()), ((1, 2), (2, 1)))"
 578       ]
 579      },
 580      "execution_count": 9,
 581      "metadata": {},
 582      "output_type": "execute_result"
 583     }
 584    ],
 585    "source": [
 586     "def delabel(f):\n",
 587     "    s = {u: i for i, u in enumerate(sorted(_unique(f)))}\n",
 588     "    return update(s, f)\n",
 589     "\n",
 590     "def _unique(f, seen=None):\n",
 591     "    if seen is None:\n",
 592     "        seen = set()\n",
 593     "    if not isinstance(f, tuple):\n",
 594     "        seen.add(f)\n",
 595     "    else:\n",
 596     "        for inner in f:\n",
 597     "            _unique(inner, seen)\n",
 598     "    return seen\n",
 599     "\n",
 600     "delabel(relabel(pop, swap))"
 601    ]
 602   },
 603   {
 604    "cell_type": "markdown",
 605    "metadata": {},
 606    "source": [
 607     "### `C()`\n",
 608     "\n",
 609     "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.)"
 610    ]
 611   },
 612   {
 613    "cell_type": "code",
 614    "execution_count": 10,
 615    "metadata": {},
 616    "outputs": [],
 617    "source": [
 618     "def C(f, g):\n",
 619     "    f, g = relabel(f, g)\n",
 620     "    fg = compose(f, g)\n",
 621     "    return delabel(fg)"
 622    ]
 623   },
 624   {
 625    "cell_type": "markdown",
 626    "metadata": {},
 627    "source": [
 628     "Let's try it out."
 629    ]
 630   },
 631   {
 632    "cell_type": "code",
 633    "execution_count": 11,
 634    "metadata": {},
 635    "outputs": [
 636     {
 637      "data": {
 638       "text/plain": [
 639        "((1, 2, 0), (2, 1))"
 640       ]
 641      },
 642      "execution_count": 11,
 643      "metadata": {},
 644      "output_type": "execute_result"
 645     }
 646    ],
 647    "source": [
 648     "C(pop, swap)"
 649    ]
 650   },
 651   {
 652    "cell_type": "code",
 653    "execution_count": 12,
 654    "metadata": {},
 655    "outputs": [
 656     {
 657      "data": {
 658       "text/plain": [
 659        "((3, 1, 2, 0), (2, 1, 3))"
 660       ]
 661      },
 662      "execution_count": 12,
 663      "metadata": {},
 664      "output_type": "execute_result"
 665     }
 666    ],
 667    "source": [
 668     "C(C(pop, swap), roll_dn)"
 669    ]
 670   },
 671   {
 672    "cell_type": "code",
 673    "execution_count": 13,
 674    "metadata": {},
 675    "outputs": [
 676     {
 677      "data": {
 678       "text/plain": [
 679        "((2, 0, 1), (1, 0, 2))"
 680       ]
 681      },
 682      "execution_count": 13,
 683      "metadata": {},
 684      "output_type": "execute_result"
 685     }
 686    ],
 687    "source": [
 688     "C(swap, roll_dn)"
 689    ]
 690   },
 691   {
 692    "cell_type": "code",
 693    "execution_count": 14,
 694    "metadata": {},
 695    "outputs": [
 696     {
 697      "data": {
 698       "text/plain": [
 699        "((3, 1, 2, 0), (2, 1, 3))"
 700       ]
 701      },
 702      "execution_count": 14,
 703      "metadata": {},
 704      "output_type": "execute_result"
 705     }
 706    ],
 707    "source": [
 708     "C(pop, C(swap, roll_dn))"
 709    ]
 710   },
 711   {
 712    "cell_type": "code",
 713    "execution_count": 15,
 714    "metadata": {},
 715    "outputs": [
 716     {
 717      "data": {
 718       "text/plain": [
 719        "((3, 1, 2, 0), (2, 1, 3))"
 720       ]
 721      },
 722      "execution_count": 15,
 723      "metadata": {},
 724      "output_type": "execute_result"
 725     }
 726    ],
 727    "source": [
 728     "poswrd = reduce(C, (pop, swap, roll_dn))\n",
 729     "poswrd"
 730    ]
 731   },
 732   {
 733    "cell_type": "markdown",
 734    "metadata": {},
 735    "source": [
 736     "### Stack Functions\n",
 737     "Here's that trick to represent functions like `rest` and `cons` that manipulate stacks.  We use a cons-list of tuples and give the tails their own numbers.  Then everything above already works. "
 738    ]
 739   },
 740   {
 741    "cell_type": "code",
 742    "execution_count": 16,
 743    "metadata": {},
 744    "outputs": [],
 745    "source": [
 746     "rest = ((1, 2),), (2,)\n",
 747     "\n",
 748     "cons = (1, 2), ((1, 2),)"
 749    ]
 750   },
 751   {
 752    "cell_type": "code",
 753    "execution_count": 17,
 754    "metadata": {},
 755    "outputs": [
 756     {
 757      "data": {
 758       "text/plain": [
 759        "(((3, 4), 1, 2, 0), (2, 1, 4))"
 760       ]
 761      },
 762      "execution_count": 17,
 763      "metadata": {},
 764      "output_type": "execute_result"
 765     }
 766    ],
 767    "source": [
 768     "C(poswrd, rest)"
 769    ]
 770   },
 771   {
 772    "cell_type": "markdown",
 773    "metadata": {},
 774    "source": [
 775     "Compare this to the stack effect comment we wrote above:\n",
 776     "\n",
 777     "    ((  (3, 4), 1, 2, 0 ), ( 2, 1,   4  ))\n",
 778     "    (   [4 ...] 2  3  0  --  3  2  [...])\n",
 779     "\n",
 780     "The translation table, if you will, would be:\n",
 781     "\n",
 782     "    {\n",
 783     "    3: 4,\n",
 784     "    4: ...],\n",
 785     "    1: 2,\n",
 786     "    2: 3,\n",
 787     "    0: 0,\n",
 788     "    }"
 789    ]
 790   },
 791   {
 792    "cell_type": "code",
 793    "execution_count": 18,
 794    "metadata": {},
 795    "outputs": [
 796     {
 797      "data": {
 798       "text/plain": [
 799        "(((3, (4, 5)), 1, 2, 0), ((2, (1, 5)),))"
 800       ]
 801      },
 802      "execution_count": 18,
 803      "metadata": {},
 804      "output_type": "execute_result"
 805     }
 806    ],
 807    "source": [
 808     "F = reduce(C, (pop, swap, roll_dn, rest, rest, cons, cons))\n",
 809     "\n",
 810     "F"
 811    ]
 812   },
 813   {
 814    "cell_type": "markdown",
 815    "metadata": {},
 816    "source": [
 817     "Compare with the stack effect comment and you can see it works fine:\n",
 818     "\n",
 819     "    ([4 5 ...] 2 3 1 -- [3 2 ...])\n",
 820     "      3 4  5   1 2 0     2 1  5"
 821    ]
 822   },
 823   {
 824    "cell_type": "markdown",
 825    "metadata": {},
 826    "source": [
 827     "### Dealing with `cons` and `uncons`\n",
 828     "However, if we try to compose e.g. `cons` and `uncons` it won't work:"
 829    ]
 830   },
 831   {
 832    "cell_type": "code",
 833    "execution_count": 19,
 834    "metadata": {},
 835    "outputs": [],
 836    "source": [
 837     "uncons = ((1, 2),), (1, 2)"
 838    ]
 839   },
 840   {
 841    "cell_type": "code",
 842    "execution_count": 20,
 843    "metadata": {},
 844    "outputs": [
 845     {
 846      "name": "stdout",
 847      "output_type": "stream",
 848      "text": [
 849       "Cannot unify (1, 2) and (1001, 1002).\n"
 850      ]
 851     }
 852    ],
 853    "source": [
 854     "try:\n",
 855     "    C(cons, uncons)\n",
 856     "except Exception, e:\n",
 857     "    print e"
 858    ]
 859   },
 860   {
 861    "cell_type": "markdown",
 862    "metadata": {},
 863    "source": [
 864     "#### `unify()` version 2\n",
 865     "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:"
 866    ]
 867   },
 868   {
 869    "cell_type": "code",
 870    "execution_count": 21,
 871    "metadata": {},
 872    "outputs": [],
 873    "source": [
 874     "def unify(u, v, s=None):\n",
 875     "    if s is None:\n",
 876     "        s = {}\n",
 877     "    elif s:\n",
 878     "        u = update(s, u)\n",
 879     "        v = update(s, v)\n",
 880     "\n",
 881     "    if isinstance(u, int):\n",
 882     "        s[u] = v\n",
 883     "\n",
 884     "    elif isinstance(v, int):\n",
 885     "        s[v] = u\n",
 886     "\n",
 887     "    elif isinstance(u, tuple) and isinstance(v, tuple):\n",
 888     "\n",
 889     "        if len(u) != 2 or len(v) != 2:\n",
 890     "            # Not a type error, caller passed in a bad value.\n",
 891     "            raise ValueError(repr((u, v)))  # FIXME this message sucks.\n",
 892     "\n",
 893     "        (a, b), (c, d) = u, v\n",
 894     "        s = unify(a, c, s)\n",
 895     "        if s != False:\n",
 896     "            s = unify(b, d, s)\n",
 897     "    else:\n",
 898     "        s = False\n",
 899     "\n",
 900     "    return s"
 901    ]
 902   },
 903   {
 904    "cell_type": "code",
 905    "execution_count": 22,
 906    "metadata": {},
 907    "outputs": [
 908     {
 909      "data": {
 910       "text/plain": [
 911        "((0, 1), (0, 1))"
 912       ]
 913      },
 914      "execution_count": 22,
 915      "metadata": {},
 916      "output_type": "execute_result"
 917     }
 918    ],
 919    "source": [
 920     "C(cons, uncons)"
 921    ]
 922   },
 923   {
 924    "cell_type": "markdown",
 925    "metadata": {},
 926    "source": [
 927     "## Part III: Compiling Yin Functions\n",
 928     "Now consider the Python function we would like to derive:"
 929    ]
 930   },
 931   {
 932    "cell_type": "code",
 933    "execution_count": 23,
 934    "metadata": {},
 935    "outputs": [],
 936    "source": [
 937     "def F_python(stack):\n",
 938     "    (_, (d, (c, ((a, (b, S0)), stack)))) = stack\n",
 939     "    return (d, (c, S0)), stack"
 940    ]
 941   },
 942   {
 943    "cell_type": "markdown",
 944    "metadata": {},
 945    "source": [
 946     "And compare it to the input stack effect comment tuple we just computed:"
 947    ]
 948   },
 949   {
 950    "cell_type": "code",
 951    "execution_count": 24,
 952    "metadata": {},
 953    "outputs": [
 954     {
 955      "data": {
 956       "text/plain": [
 957        "((3, (4, 5)), 1, 2, 0)"
 958       ]
 959      },
 960      "execution_count": 24,
 961      "metadata": {},
 962      "output_type": "execute_result"
 963     }
 964    ],
 965    "source": [
 966     "F[0]"
 967    ]
 968   },
 969   {
 970    "cell_type": "markdown",
 971    "metadata": {},
 972    "source": [
 973     "The stack-de-structuring tuple has nearly the same form as our input stack effect comment tuple, just in the reverse order:\n",
 974     "\n",
 975     "    (_, (d, (c, ((a, (b, S0)), stack))))\n",
 976     "\n",
 977     "Remove the punctuation:\n",
 978     "\n",
 979     "     _   d   c   (a, (b, S0))\n",
 980     "\n",
 981     "Reverse the order and compare:\n",
 982     "\n",
 983     "     (a, (b, S0))   c   d   _\n",
 984     "    ((3, (4, 5 )),  1,  2,  0)\n",
 985     "\n",
 986     "Eh?"
 987    ]
 988   },
 989   {
 990    "cell_type": "markdown",
 991    "metadata": {},
 992    "source": [
 993     "And the return tuple "
 994    ]
 995   },
 996   {
 997    "cell_type": "code",
 998    "execution_count": 25,
 999    "metadata": {},
1000    "outputs": [
1001     {
1002      "data": {
1003       "text/plain": [
1004        "((2, (1, 5)),)"
1005       ]
1006      },
1007      "execution_count": 25,
1008      "metadata": {},
1009      "output_type": "execute_result"
1010     }
1011    ],
1012    "source": [
1013     "F[1]"
1014    ]
1015   },
1016   {
1017    "cell_type": "markdown",
1018    "metadata": {},
1019    "source": [
1020     "is similar to the output stack effect comment tuple:\n",
1021     "\n",
1022     "    ((d, (c, S0)), stack)\n",
1023     "    ((2, (1, 5 )),      )\n",
1024     "\n",
1025     "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.)"
1026    ]
1027   },
1028   {
1029    "cell_type": "markdown",
1030    "metadata": {},
1031    "source": [
1032     "### Python Identifiers\n",
1033     "We want to substitute Python identifiers for the integers.  I'm going to repurpose `joy.parser.Symbol` class for this:"
1034    ]
1035   },
1036   {
1037    "cell_type": "code",
1038    "execution_count": 26,
1039    "metadata": {},
1040    "outputs": [],
1041    "source": [
1042     "from collections import defaultdict\n",
1043     "from joy.parser import Symbol\n",
1044     "\n",
1045     "\n",
1046     "def _names_for():\n",
1047     "    I = iter(xrange(1000))\n",
1048     "    return lambda: Symbol('a%i' % next(I))\n",
1049     "\n",
1050     "\n",
1051     "def identifiers(term, s=None):\n",
1052     "    if s is None:\n",
1053     "        s = defaultdict(_names_for())\n",
1054     "    if isinstance(term, int):\n",
1055     "        return s[term]\n",
1056     "    return tuple(identifiers(inner, s) for inner in term)"
1057    ]
1058   },
1059   {
1060    "cell_type": "markdown",
1061    "metadata": {},
1062    "source": [
1063     "### `doc_from_stack_effect()`\n",
1064     "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."
1065    ]
1066   },
1067   {
1068    "cell_type": "code",
1069    "execution_count": 27,
1070    "metadata": {},
1071    "outputs": [],
1072    "source": [
1073     "def doc_from_stack_effect(inputs, outputs):\n",
1074     "    return '(%s--%s)' % (\n",
1075     "        ' '.join(map(_to_str, inputs + ('',))),\n",
1076     "        ' '.join(map(_to_str, ('',) + outputs))\n",
1077     "    )\n",
1078     "\n",
1079     "\n",
1080     "def _to_str(term):\n",
1081     "    if not isinstance(term, tuple):\n",
1082     "        try:\n",
1083     "            t = term.prefix == 's'\n",
1084     "        except AttributeError:\n",
1085     "            return str(term)\n",
1086     "        return '[.%i.]' % term.number if t else str(term)\n",
1087     "\n",
1088     "    a = []\n",
1089     "    while term and isinstance(term, tuple):\n",
1090     "        item, term = term\n",
1091     "        a.append(_to_str(item))\n",
1092     "\n",
1093     "    try:\n",
1094     "        n = term.number\n",
1095     "    except AttributeError:\n",
1096     "        n = term\n",
1097     "    else:\n",
1098     "        if term.prefix != 's':\n",
1099     "            raise ValueError('Stack label: %s' % (term,))\n",
1100     "\n",
1101     "    a.append('.%s.' % (n,))\n",
1102     "    return '[%s]' % ' '.join(a)"
1103    ]
1104   },
1105   {
1106    "cell_type": "markdown",
1107    "metadata": {},
1108    "source": [
1109     "### `compile_()`\n",
1110     "Now we can write a compiler function to emit Python source code.  (The underscore suffix distiguishes it from the built-in `compile()` function.)"
1111    ]
1112   },
1113   {
1114    "cell_type": "code",
1115    "execution_count": 28,
1116    "metadata": {},
1117    "outputs": [],
1118    "source": [
1119     "def compile_(name, f, doc=None):\n",
1120     "    if doc is None:\n",
1121     "        doc = doc_from_stack_effect(*f)\n",
1122     "    inputs, outputs = identifiers(f)\n",
1123     "    i = o = Symbol('stack')\n",
1124     "    for term in inputs:\n",
1125     "        i = term, i\n",
1126     "    for term in outputs:\n",
1127     "        o = term, o\n",
1128     "    return '''def %s(stack):\n",
1129     "    \"\"\"%s\"\"\"\n",
1130     "    %s = stack\n",
1131     "    return %s''' % (name, doc, i, o)"
1132    ]
1133   },
1134   {
1135    "cell_type": "markdown",
1136    "metadata": {},
1137    "source": [
1138     "Here it is in action:"
1139    ]
1140   },
1141   {
1142    "cell_type": "code",
1143    "execution_count": 29,
1144    "metadata": {},
1145    "outputs": [
1146     {
1147      "name": "stdout",
1148      "output_type": "stream",
1149      "text": [
1150       "def F(stack):\n",
1151       "    \"\"\"([3 4 .5.] 1 2 0 -- [2 1 .5.])\"\"\"\n",
1152       "    (a5, (a4, (a3, ((a0, (a1, a2)), stack)))) = stack\n",
1153       "    return ((a4, (a3, a2)), stack)\n"
1154      ]
1155     }
1156    ],
1157    "source": [
1158     "source = compile_('F', F)\n",
1159     "\n",
1160     "print source"
1161    ]
1162   },
1163   {
1164    "cell_type": "markdown",
1165    "metadata": {},
1166    "source": [
1167     "Compare:"
1168    ]
1169   },
1170   {
1171    "cell_type": "code",
1172    "execution_count": 30,
1173    "metadata": {},
1174    "outputs": [],
1175    "source": [
1176     "def F_python(stack):\n",
1177     "    (_, (d, (c, ((a, (b, S0)), stack)))) = stack\n",
1178     "    return ((d, (c, S0)), stack)"
1179    ]
1180   },
1181   {
1182    "cell_type": "markdown",
1183    "metadata": {},
1184    "source": [
1185     "Next steps:"
1186    ]
1187   },
1188   {
1189    "cell_type": "code",
1190    "execution_count": 31,
1191    "metadata": {},
1192    "outputs": [
1193     {
1194      "data": {
1195       "text/plain": [
1196        "<function F>"
1197       ]
1198      },
1199      "execution_count": 31,
1200      "metadata": {},
1201      "output_type": "execute_result"
1202     }
1203    ],
1204    "source": [
1205     "L = {}\n",
1206     "\n",
1207     "eval(compile(source, '__main__', 'single'), {}, L)\n",
1208     "\n",
1209     "L['F']"
1210    ]
1211   },
1212   {
1213    "cell_type": "markdown",
1214    "metadata": {},
1215    "source": [
1216     "Let's try it out:"
1217    ]
1218   },
1219   {
1220    "cell_type": "code",
1221    "execution_count": 32,
1222    "metadata": {},
1223    "outputs": [],
1224    "source": [
1225     "from notebook_preamble import D, J, V\n",
1226     "from joy.library import SimpleFunctionWrapper"
1227    ]
1228   },
1229   {
1230    "cell_type": "code",
1231    "execution_count": 33,
1232    "metadata": {},
1233    "outputs": [],
1234    "source": [
1235     "D['F'] = SimpleFunctionWrapper(L['F'])"
1236    ]
1237   },
1238   {
1239    "cell_type": "code",
1240    "execution_count": 34,
1241    "metadata": {
1242     "scrolled": true
1243    },
1244    "outputs": [
1245     {
1246      "name": "stdout",
1247      "output_type": "stream",
1248      "text": [
1249       "[3 2 ...]\n"
1250      ]
1251     }
1252    ],
1253    "source": [
1254     "J('[4 5 ...] 2 3 1 F')"
1255    ]
1256   },
1257   {
1258    "cell_type": "markdown",
1259    "metadata": {},
1260    "source": [
1261     "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.)\n",
1262     "\n",
1263     "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."
1264    ]
1265   },
1266   {
1267    "cell_type": "markdown",
1268    "metadata": {},
1269    "source": [
1270     "### Compiling Library Functions\n",
1271     "We can use `compile_()` to generate many primitives in the library from their stack effect comments:"
1272    ]
1273   },
1274   {
1275    "cell_type": "code",
1276    "execution_count": 35,
1277    "metadata": {},
1278    "outputs": [],
1279    "source": [
1280     "def defs():\n",
1281     "\n",
1282     "    rolldown = (1, 2, 3), (2, 3, 1)\n",
1283     "\n",
1284     "    rollup = (1, 2, 3), (3, 1, 2)\n",
1285     "\n",
1286     "    pop = (1,), ()\n",
1287     "\n",
1288     "    swap = (1, 2), (2, 1)\n",
1289     "\n",
1290     "    rest = ((1, 2),), (2,)\n",
1291     "    \n",
1292     "    rrest = C(rest, rest)\n",
1293     "\n",
1294     "    cons = (1, 2), ((1, 2),)\n",
1295     "\n",
1296     "    uncons = ((1, 2),), (1, 2)\n",
1297     "    \n",
1298     "    swons = C(swap, cons)\n",
1299     "\n",
1300     "    return locals()"
1301    ]
1302   },
1303   {
1304    "cell_type": "code",
1305    "execution_count": 36,
1306    "metadata": {
1307     "scrolled": true
1308    },
1309    "outputs": [
1310     {
1311      "name": "stdout",
1312      "output_type": "stream",
1313      "text": [
1314       "\n",
1315       "def cons(stack):\n",
1316       "    \"\"\"(1 2 -- [1 .2.])\"\"\"\n",
1317       "    (a1, (a0, stack)) = stack\n",
1318       "    return ((a0, a1), stack)\n",
1319       "\n",
1320       "\n",
1321       "def pop(stack):\n",
1322       "    \"\"\"(1 --)\"\"\"\n",
1323       "    (a0, stack) = stack\n",
1324       "    return stack\n",
1325       "\n",
1326       "\n",
1327       "def rest(stack):\n",
1328       "    \"\"\"([1 .2.] -- 2)\"\"\"\n",
1329       "    ((a0, a1), stack) = stack\n",
1330       "    return (a1, stack)\n",
1331       "\n",
1332       "\n",
1333       "def rolldown(stack):\n",
1334       "    \"\"\"(1 2 3 -- 2 3 1)\"\"\"\n",
1335       "    (a2, (a1, (a0, stack))) = stack\n",
1336       "    return (a0, (a2, (a1, stack)))\n",
1337       "\n",
1338       "\n",
1339       "def rollup(stack):\n",
1340       "    \"\"\"(1 2 3 -- 3 1 2)\"\"\"\n",
1341       "    (a2, (a1, (a0, stack))) = stack\n",
1342       "    return (a1, (a0, (a2, stack)))\n",
1343       "\n",
1344       "\n",
1345       "def rrest(stack):\n",
1346       "    \"\"\"([0 1 .2.] -- 2)\"\"\"\n",
1347       "    ((a0, (a1, a2)), stack) = stack\n",
1348       "    return (a2, stack)\n",
1349       "\n",
1350       "\n",
1351       "def swap(stack):\n",
1352       "    \"\"\"(1 2 -- 2 1)\"\"\"\n",
1353       "    (a1, (a0, stack)) = stack\n",
1354       "    return (a0, (a1, stack))\n",
1355       "\n",
1356       "\n",
1357       "def swons(stack):\n",
1358       "    \"\"\"(0 1 -- [1 .0.])\"\"\"\n",
1359       "    (a1, (a0, stack)) = stack\n",
1360       "    return ((a1, a0), stack)\n",
1361       "\n",
1362       "\n",
1363       "def uncons(stack):\n",
1364       "    \"\"\"([1 .2.] -- 1 2)\"\"\"\n",
1365       "    ((a0, a1), stack) = stack\n",
1366       "    return (a1, (a0, stack))\n",
1367       "\n"
1368      ]
1369     }
1370    ],
1371    "source": [
1372     "for name, stack_effect_comment in sorted(defs().items()):\n",
1373     "    print\n",
1374     "    print compile_(name, stack_effect_comment)\n",
1375     "    print"
1376    ]
1377   },
1378   {
1379    "cell_type": "markdown",
1380    "metadata": {},
1381    "source": [
1382     "## Part IV: Types and Subtypes of Arguments\n",
1383     "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."
1384    ]
1385   },
1386   {
1387    "cell_type": "markdown",
1388    "metadata": {},
1389    "source": [
1390     "### \"Number\" Type\n",
1391     "\n",
1392     "Consider the definition of `sqr`:\n",
1393     "\n",
1394     "    sqr == dup mul\n",
1395     "\n",
1396     "\n",
1397     "The `dup` function accepts one *anything* and returns two of that:\n",
1398     "\n",
1399     "    dup (1 -- 1 1)\n",
1400     "\n",
1401     "And `mul` accepts two \"numbers\" (we're ignoring ints vs. floats vs. complex, etc., for now) and returns just one:\n",
1402     "\n",
1403     "    mul (n n -- n)\n",
1404     "\n",
1405     "So we're composing:\n",
1406     "\n",
1407     "    (1 -- 1 1)∘(n n -- n)\n",
1408     "\n",
1409     "The rules say we unify 1 with `n`:\n",
1410     "\n",
1411     "       (1 -- 1 1)∘(n n -- n)\n",
1412     "    ---------------------------  w/  {1: n}\n",
1413     "       (1 -- 1  )∘(n   -- n)\n",
1414     "\n",
1415     "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:\n",
1416     "\n",
1417     "       (n n -- n)∘(1 -- 1 1)\n",
1418     "    ---------------------------  w/  {1: n}\n",
1419     "       (n n --  )∘(  -- n n) \n",
1420     "\n",
1421     "The important thing here is that the mapping is going the same way in both cases, from the \"any\" integer to the number"
1422    ]
1423   },
1424   {
1425    "cell_type": "markdown",
1426    "metadata": {},
1427    "source": [
1428     "### Distinguishing Numbers\n",
1429     "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:\n",
1430     "\n",
1431     "    mul (n2 n1 -- n3)\n",
1432     "\n",
1433     "\n",
1434     "       (1  -- 1  1)∘(n2 n1 -- n3)\n",
1435     "    --------------------------------  w/  {1: n2}\n",
1436     "       (n2 -- n2  )∘(n2    -- n3)\n",
1437     "\n",
1438     "\n",
1439     "       (n2 n1 -- n3)∘(1 -- 1  1 )\n",
1440     "    --------------------------------  w/  {1: n3}\n",
1441     "       (n2 n1 --   )∘(  -- n3 n3) \n",
1442     "\n"
1443    ]
1444   },
1445   {
1446    "cell_type": "markdown",
1447    "metadata": {},
1448    "source": [
1449     "### Distinguishing Types\n",
1450     "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?\n",
1451     "\n",
1452     "       (a -- b t[i])∘(c u[j] -- d)   t <= u (t is subtype of u)\n",
1453     "    -------------------------------\n",
1454     "       (a -- b     )∘(c      -- d)   t[i] == t[k] == u[j]\n",
1455     "                                             ^\n",
1456     "\n",
1457     "       (a -- b t[i])∘(c u[j] -- d)   u <= t (u is subtype of t)\n",
1458     "    -------------------------------\n",
1459     "       (a -- b     )∘(c      -- d)   t[i] == u[k] == u[j]\n",
1460     "\n",
1461     "The indices `i`, `k`, and `j` are the number part of our labels and `t` and `u` are the domains.\n",
1462     "\n",
1463     "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."
1464    ]
1465   },
1466   {
1467    "cell_type": "code",
1468    "execution_count": 37,
1469    "metadata": {},
1470    "outputs": [],
1471    "source": [
1472     "class AnyJoyType(object):\n",
1473     "\n",
1474     "    prefix = 'a'\n",
1475     "\n",
1476     "    def __init__(self, number):\n",
1477     "        self.number = number\n",
1478     "\n",
1479     "    def __repr__(self):\n",
1480     "        return self.prefix + str(self.number)\n",
1481     "\n",
1482     "    def __eq__(self, other):\n",
1483     "        return (\n",
1484     "            isinstance(other, self.__class__)\n",
1485     "            and other.prefix == self.prefix\n",
1486     "            and other.number == self.number\n",
1487     "        )\n",
1488     "\n",
1489     "    def __ge__(self, other):\n",
1490     "        return issubclass(other.__class__, self.__class__)\n",
1491     "\n",
1492     "    def __add__(self, other):\n",
1493     "        return self.__class__(self.number + other)\n",
1494     "    __radd__ = __add__\n",
1495     "    \n",
1496     "    def __hash__(self):\n",
1497     "        return hash(repr(self))\n",
1498     "\n",
1499     "\n",
1500     "class NumberJoyType(AnyJoyType): prefix = 'n'\n",
1501     "class FloatJoyType(NumberJoyType): prefix = 'f'\n",
1502     "class IntJoyType(FloatJoyType): prefix = 'i'\n",
1503     "\n",
1504     "\n",
1505     "class StackJoyType(AnyJoyType):\n",
1506     "    prefix = 's'\n",
1507     "\n",
1508     "\n",
1509     "_R = range(10)\n",
1510     "A = map(AnyJoyType, _R)\n",
1511     "N = map(NumberJoyType, _R)\n",
1512     "S = map(StackJoyType, _R)"
1513    ]
1514   },
1515   {
1516    "cell_type": "markdown",
1517    "metadata": {},
1518    "source": [
1519     "Mess with it a little:"
1520    ]
1521   },
1522   {
1523    "cell_type": "code",
1524    "execution_count": 38,
1525    "metadata": {},
1526    "outputs": [],
1527    "source": [
1528     "from itertools import permutations"
1529    ]
1530   },
1531   {
1532    "cell_type": "markdown",
1533    "metadata": {},
1534    "source": [
1535     "\"Any\" types can be specialized to numbers and stacks, but not vice versa:"
1536    ]
1537   },
1538   {
1539    "cell_type": "code",
1540    "execution_count": 39,
1541    "metadata": {},
1542    "outputs": [
1543     {
1544      "name": "stdout",
1545      "output_type": "stream",
1546      "text": [
1547       "a0 >= n0 -> True\n",
1548       "a0 >= s0 -> True\n",
1549       "n0 >= a0 -> False\n",
1550       "n0 >= s0 -> False\n",
1551       "s0 >= a0 -> False\n",
1552       "s0 >= n0 -> False\n"
1553      ]
1554     }
1555    ],
1556    "source": [
1557     "for a, b in permutations((A[0], N[0], S[0]), 2):\n",
1558     "    print a, '>=', b, '->', a >= b"
1559    ]
1560   },
1561   {
1562    "cell_type": "markdown",
1563    "metadata": {},
1564    "source": [
1565     "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):"
1566    ]
1567   },
1568   {
1569    "cell_type": "code",
1570    "execution_count": 40,
1571    "metadata": {},
1572    "outputs": [
1573     {
1574      "name": "stdout",
1575      "output_type": "stream",
1576      "text": [
1577       "a0 >= n0 -> True\n",
1578       "a0 >= f0 -> True\n",
1579       "a0 >= i0 -> True\n",
1580       "n0 >= a0 -> False\n",
1581       "n0 >= f0 -> True\n",
1582       "n0 >= i0 -> True\n",
1583       "f0 >= a0 -> False\n",
1584       "f0 >= n0 -> False\n",
1585       "f0 >= i0 -> True\n",
1586       "i0 >= a0 -> False\n",
1587       "i0 >= n0 -> False\n",
1588       "i0 >= f0 -> False\n"
1589      ]
1590     }
1591    ],
1592    "source": [
1593     "for a, b in permutations((A[0], N[0], FloatJoyType(0), IntJoyType(0)), 2):\n",
1594     "    print a, '>=', b, '->', a >= b"
1595    ]
1596   },
1597   {
1598    "cell_type": "markdown",
1599    "metadata": {},
1600    "source": [
1601     "### Typing `sqr`"
1602    ]
1603   },
1604   {
1605    "cell_type": "code",
1606    "execution_count": 41,
1607    "metadata": {},
1608    "outputs": [],
1609    "source": [
1610     "dup = (A[1],), (A[1], A[1])\n",
1611     "\n",
1612     "mul = (N[1], N[2]), (N[3],)"
1613    ]
1614   },
1615   {
1616    "cell_type": "code",
1617    "execution_count": 42,
1618    "metadata": {},
1619    "outputs": [
1620     {
1621      "data": {
1622       "text/plain": [
1623        "((a1,), (a1, a1))"
1624       ]
1625      },
1626      "execution_count": 42,
1627      "metadata": {},
1628      "output_type": "execute_result"
1629     }
1630    ],
1631    "source": [
1632     "dup"
1633    ]
1634   },
1635   {
1636    "cell_type": "code",
1637    "execution_count": 43,
1638    "metadata": {},
1639    "outputs": [
1640     {
1641      "data": {
1642       "text/plain": [
1643        "((n1, n2), (n3,))"
1644       ]
1645      },
1646      "execution_count": 43,
1647      "metadata": {},
1648      "output_type": "execute_result"
1649     }
1650    ],
1651    "source": [
1652     "mul"
1653    ]
1654   },
1655   {
1656    "cell_type": "markdown",
1657    "metadata": {},
1658    "source": [
1659     "### Modifying the Inferencer\n",
1660     "Re-labeling still works fine:"
1661    ]
1662   },
1663   {
1664    "cell_type": "code",
1665    "execution_count": 44,
1666    "metadata": {},
1667    "outputs": [
1668     {
1669      "data": {
1670       "text/plain": [
1671        "(((a1,), (a1, a1)), ((n1001, n1002), (n1003,)))"
1672       ]
1673      },
1674      "execution_count": 44,
1675      "metadata": {},
1676      "output_type": "execute_result"
1677     }
1678    ],
1679    "source": [
1680     "foo = relabel(dup, mul)\n",
1681     "\n",
1682     "foo"
1683    ]
1684   },
1685   {
1686    "cell_type": "markdown",
1687    "metadata": {},
1688    "source": [
1689     "#### `delabel()` version 2\n",
1690     "The `delabel()` function needs an overhaul.  It now has to keep track of how many labels of each domain it has \"seen\"."
1691    ]
1692   },
1693   {
1694    "cell_type": "code",
1695    "execution_count": 45,
1696    "metadata": {},
1697    "outputs": [],
1698    "source": [
1699     "from collections import Counter\n",
1700     "\n",
1701     "\n",
1702     "def delabel(f, seen=None, c=None):\n",
1703     "    if seen is None:\n",
1704     "        assert c is None\n",
1705     "        seen, c = {}, Counter()\n",
1706     "\n",
1707     "    try:\n",
1708     "        return seen[f]\n",
1709     "    except KeyError:\n",
1710     "        pass\n",
1711     "\n",
1712     "    if not isinstance(f, tuple):\n",
1713     "        seen[f] = f.__class__(c[f.prefix] + 1)\n",
1714     "        c[f.prefix] += 1\n",
1715     "        return seen[f]\n",
1716     "\n",
1717     "    return tuple(delabel(inner, seen, c) for inner in f)"
1718    ]
1719   },
1720   {
1721    "cell_type": "code",
1722    "execution_count": 46,
1723    "metadata": {},
1724    "outputs": [
1725     {
1726      "data": {
1727       "text/plain": [
1728        "(((a1,), (a1, a1)), ((n1, n2), (n3,)))"
1729       ]
1730      },
1731      "execution_count": 46,
1732      "metadata": {},
1733      "output_type": "execute_result"
1734     }
1735    ],
1736    "source": [
1737     "delabel(foo)"
1738    ]
1739   },
1740   {
1741    "cell_type": "markdown",
1742    "metadata": {},
1743    "source": [
1744     "#### `unify()` version 3"
1745    ]
1746   },
1747   {
1748    "cell_type": "code",
1749    "execution_count": 47,
1750    "metadata": {},
1751    "outputs": [],
1752    "source": [
1753     "def unify(u, v, s=None):\n",
1754     "    if s is None:\n",
1755     "        s = {}\n",
1756     "    elif s:\n",
1757     "        u = update(s, u)\n",
1758     "        v = update(s, v)\n",
1759     "\n",
1760     "    if u == v:\n",
1761     "        return s\n",
1762     "\n",
1763     "    if isinstance(u, AnyJoyType) and isinstance(v, AnyJoyType):\n",
1764     "        if u >= v:\n",
1765     "            s[u] = v\n",
1766     "            return s\n",
1767     "        if v >= u:\n",
1768     "            s[v] = u\n",
1769     "            return s\n",
1770     "        raise TypeError('Cannot unify %r and %r.' % (u, v))\n",
1771     "\n",
1772     "    if isinstance(u, tuple) and isinstance(v, tuple):\n",
1773     "        if len(u) != len(v) != 2:\n",
1774     "            raise TypeError(repr((u, v)))\n",
1775     "        for uu, vv in zip(u, v):\n",
1776     "            s = unify(uu, vv, s)\n",
1777     "            if s == False: # (instead of a substitution dict.)\n",
1778     "                break\n",
1779     "        return s\n",
1780     " \n",
1781     "    if isinstance(v, tuple):\n",
1782     "        if not stacky(u):\n",
1783     "            raise TypeError('Cannot unify %r and %r.' % (u, v))\n",
1784     "        s[u] = v\n",
1785     "        return s\n",
1786     "\n",
1787     "    if isinstance(u, tuple):\n",
1788     "        if not stacky(v):\n",
1789     "            raise TypeError('Cannot unify %r and %r.' % (v, u))\n",
1790     "        s[v] = u\n",
1791     "        return s\n",
1792     "\n",
1793     "    return False\n",
1794     "\n",
1795     "\n",
1796     "def stacky(thing):\n",
1797     "    return thing.__class__ in {AnyJoyType, StackJoyType}"
1798    ]
1799   },
1800   {
1801    "cell_type": "markdown",
1802    "metadata": {},
1803    "source": [
1804     "Rewrite the stack effect comments:"
1805    ]
1806   },
1807   {
1808    "cell_type": "code",
1809    "execution_count": 48,
1810    "metadata": {},
1811    "outputs": [],
1812    "source": [
1813     "def defs():\n",
1814     "\n",
1815     "    rolldown = (A[1], A[2], A[3]), (A[2], A[3], A[1])\n",
1816     "\n",
1817     "    rollup = (A[1], A[2], A[3]), (A[3], A[1], A[2])\n",
1818     "\n",
1819     "    pop = (A[1],), ()\n",
1820     "\n",
1821     "    popop = (A[2], A[1],), ()\n",
1822     "\n",
1823     "    popd = (A[2], A[1],), (A[1],)\n",
1824     "\n",
1825     "    popdd = (A[3], A[2], A[1],), (A[2], A[1],)\n",
1826     "\n",
1827     "    swap = (A[1], A[2]), (A[2], A[1])\n",
1828     "\n",
1829     "    rest = ((A[1], S[1]),), (S[1],)\n",
1830     "\n",
1831     "    rrest = C(rest, rest)\n",
1832     "\n",
1833     "    cons = (A[1], S[1]), ((A[1], S[1]),)\n",
1834     "\n",
1835     "    ccons = C(cons, cons)\n",
1836     "\n",
1837     "    uncons = ((A[1], S[1]),), (A[1], S[1])\n",
1838     "\n",
1839     "    swons = C(swap, cons)\n",
1840     "\n",
1841     "    dup = (A[1],), (A[1], A[1])\n",
1842     "\n",
1843     "    dupd = (A[2], A[1]), (A[2], A[2], A[1])\n",
1844     "\n",
1845     "    mul = (N[1], N[2]), (N[3],)\n",
1846     "    \n",
1847     "    sqrt = C(dup, mul)\n",
1848     "\n",
1849     "    first = ((A[1], S[1]),), (A[1],)\n",
1850     "\n",
1851     "    second = C(rest, first)\n",
1852     "\n",
1853     "    third = C(rest, second)\n",
1854     "\n",
1855     "    tuck = (A[2], A[1]), (A[1], A[2], A[1])\n",
1856     "\n",
1857     "    over = (A[2], A[1]), (A[2], A[1], A[2])\n",
1858     "    \n",
1859     "    succ = pred = (N[1],), (N[2],)\n",
1860     "    \n",
1861     "    divmod_ = pm = (N[2], N[1]), (N[4], N[3])\n",
1862     "\n",
1863     "    return locals()"
1864    ]
1865   },
1866   {
1867    "cell_type": "code",
1868    "execution_count": 49,
1869    "metadata": {},
1870    "outputs": [],
1871    "source": [
1872     "DEFS = defs()"
1873    ]
1874   },
1875   {
1876    "cell_type": "code",
1877    "execution_count": 50,
1878    "metadata": {},
1879    "outputs": [
1880     {
1881      "name": "stdout",
1882      "output_type": "stream",
1883      "text": [
1884       "ccons = (a1 a2 [.1.] -- [a1 a2 .1.])\n",
1885       "cons = (a1 [.1.] -- [a1 .1.])\n",
1886       "divmod_ = (n2 n1 -- n4 n3)\n",
1887       "dup = (a1 -- a1 a1)\n",
1888       "dupd = (a2 a1 -- a2 a2 a1)\n",
1889       "first = ([a1 .1.] -- a1)\n",
1890       "mul = (n1 n2 -- n3)\n",
1891       "over = (a2 a1 -- a2 a1 a2)\n",
1892       "pm = (n2 n1 -- n4 n3)\n",
1893       "pop = (a1 --)\n",
1894       "popd = (a2 a1 -- a1)\n",
1895       "popdd = (a3 a2 a1 -- a2 a1)\n",
1896       "popop = (a2 a1 --)\n",
1897       "pred = (n1 -- n2)\n",
1898       "rest = ([a1 .1.] -- [.1.])\n",
1899       "rolldown = (a1 a2 a3 -- a2 a3 a1)\n",
1900       "rollup = (a1 a2 a3 -- a3 a1 a2)\n",
1901       "rrest = ([a1 a2 .1.] -- [.1.])\n",
1902       "second = ([a1 a2 .1.] -- a2)\n",
1903       "sqrt = (n1 -- n2)\n",
1904       "succ = (n1 -- n2)\n",
1905       "swap = (a1 a2 -- a2 a1)\n",
1906       "swons = ([.1.] a1 -- [a1 .1.])\n",
1907       "third = ([a1 a2 a3 .1.] -- a3)\n",
1908       "tuck = (a2 a1 -- a1 a2 a1)\n",
1909       "uncons = ([a1 .1.] -- a1 [.1.])\n"
1910      ]
1911     }
1912    ],
1913    "source": [
1914     "for name, stack_effect_comment in sorted(DEFS.items()):\n",
1915     "    print name, '=', doc_from_stack_effect(*stack_effect_comment)"
1916    ]
1917   },
1918   {
1919    "cell_type": "code",
1920    "execution_count": 51,
1921    "metadata": {},
1922    "outputs": [],
1923    "source": [
1924     "globals().update(DEFS)"
1925    ]
1926   },
1927   {
1928    "cell_type": "markdown",
1929    "metadata": {},
1930    "source": [
1931     "#### Compose `dup` and `mul`"
1932    ]
1933   },
1934   {
1935    "cell_type": "code",
1936    "execution_count": 52,
1937    "metadata": {},
1938    "outputs": [
1939     {
1940      "data": {
1941       "text/plain": [
1942        "((n1,), (n2,))"
1943       ]
1944      },
1945      "execution_count": 52,
1946      "metadata": {},
1947      "output_type": "execute_result"
1948     }
1949    ],
1950    "source": [
1951     "C(dup, mul)"
1952    ]
1953   },
1954   {
1955    "cell_type": "markdown",
1956    "metadata": {},
1957    "source": [
1958     "Revisit the `F` function, works fine."
1959    ]
1960   },
1961   {
1962    "cell_type": "code",
1963    "execution_count": 53,
1964    "metadata": {},
1965    "outputs": [
1966     {
1967      "data": {
1968       "text/plain": [
1969        "(((a1, (a2, s1)), a3, a4, a5), ((a4, (a3, s1)),))"
1970       ]
1971      },
1972      "execution_count": 53,
1973      "metadata": {},
1974      "output_type": "execute_result"
1975     }
1976    ],
1977    "source": [
1978     "F = reduce(C, (pop, swap, rolldown, rest, rest, cons, cons))\n",
1979     "F"
1980    ]
1981   },
1982   {
1983    "cell_type": "code",
1984    "execution_count": 54,
1985    "metadata": {},
1986    "outputs": [
1987     {
1988      "name": "stdout",
1989      "output_type": "stream",
1990      "text": [
1991       "([a1 a2 .1.] a3 a4 a5 -- [a4 a3 .1.])\n"
1992      ]
1993     }
1994    ],
1995    "source": [
1996     "print doc_from_stack_effect(*F)"
1997    ]
1998   },
1999   {
2000    "cell_type": "markdown",
2001    "metadata": {},
2002    "source": [
2003     "Some otherwise inefficient functions are no longer to be feared.  We can also get the effect of combinators in some limited cases."
2004    ]
2005   },
2006   {
2007    "cell_type": "code",
2008    "execution_count": 55,
2009    "metadata": {},
2010    "outputs": [],
2011    "source": [
2012     "def neato(*funcs):\n",
2013     "    print doc_from_stack_effect(*reduce(C, funcs))"
2014    ]
2015   },
2016   {
2017    "cell_type": "code",
2018    "execution_count": 56,
2019    "metadata": {},
2020    "outputs": [
2021     {
2022      "name": "stdout",
2023      "output_type": "stream",
2024      "text": [
2025       "(a1 a2 a3 -- a2 a1 a3)\n"
2026      ]
2027     }
2028    ],
2029    "source": [
2030     "# e.g. [swap] dip\n",
2031     "neato(rollup, swap, rolldown)"
2032    ]
2033   },
2034   {
2035    "cell_type": "code",
2036    "execution_count": 57,
2037    "metadata": {},
2038    "outputs": [
2039     {
2040      "name": "stdout",
2041      "output_type": "stream",
2042      "text": [
2043       "(a1 a2 a3 a4 -- a3 a4)\n"
2044      ]
2045     }
2046    ],
2047    "source": [
2048     "# e.g. [popop] dipd\n",
2049     "neato(popdd, rolldown, pop)"
2050    ]
2051   },
2052   {
2053    "cell_type": "code",
2054    "execution_count": 58,
2055    "metadata": {},
2056    "outputs": [
2057     {
2058      "name": "stdout",
2059      "output_type": "stream",
2060      "text": [
2061       "(a1 a2 a3 -- a3 a2 a1)\n"
2062      ]
2063     }
2064    ],
2065    "source": [
2066     "# Reverse the order of the top three items.\n",
2067     "neato(rollup, swap)"
2068    ]
2069   },
2070   {
2071    "cell_type": "markdown",
2072    "metadata": {},
2073    "source": [
2074     "#### `compile_()` version 2\n",
2075     "Because the type labels represent themselves as valid Python identifiers the `compile_()` function doesn't need to generate them anymore:"
2076    ]
2077   },
2078   {
2079    "cell_type": "code",
2080    "execution_count": 59,
2081    "metadata": {},
2082    "outputs": [],
2083    "source": [
2084     "def compile_(name, f, doc=None):\n",
2085     "    inputs, outputs = f\n",
2086     "    if doc is None:\n",
2087     "        doc = doc_from_stack_effect(inputs, outputs)\n",
2088     "    i = o = Symbol('stack')\n",
2089     "    for term in inputs:\n",
2090     "        i = term, i\n",
2091     "    for term in outputs:\n",
2092     "        o = term, o\n",
2093     "    return '''def %s(stack):\n",
2094     "    \"\"\"%s\"\"\"\n",
2095     "    %s = stack\n",
2096     "    return %s''' % (name, doc, i, o)"
2097    ]
2098   },
2099   {
2100    "cell_type": "code",
2101    "execution_count": 60,
2102    "metadata": {},
2103    "outputs": [
2104     {
2105      "name": "stdout",
2106      "output_type": "stream",
2107      "text": [
2108       "def F(stack):\n",
2109       "    \"\"\"([a1 a2 .1.] a3 a4 a5 -- [a4 a3 .1.])\"\"\"\n",
2110       "    (a5, (a4, (a3, ((a1, (a2, s1)), stack)))) = stack\n",
2111       "    return ((a4, (a3, s1)), stack)\n"
2112      ]
2113     }
2114    ],
2115    "source": [
2116     "print compile_('F', F)"
2117    ]
2118   },
2119   {
2120    "cell_type": "markdown",
2121    "metadata": {},
2122    "source": [
2123     "But it cannot magically create new functions that involve e.g. math and such.  Note that this is *not* a `sqr` function implementation:"
2124    ]
2125   },
2126   {
2127    "cell_type": "code",
2128    "execution_count": 61,
2129    "metadata": {},
2130    "outputs": [
2131     {
2132      "name": "stdout",
2133      "output_type": "stream",
2134      "text": [
2135       "def sqr(stack):\n",
2136       "    \"\"\"(n1 -- n2)\"\"\"\n",
2137       "    (n1, stack) = stack\n",
2138       "    return (n2, stack)\n"
2139      ]
2140     }
2141    ],
2142    "source": [
2143     "print compile_('sqr', C(dup, mul))"
2144    ]
2145   },
2146   {
2147    "cell_type": "markdown",
2148    "metadata": {},
2149    "source": [
2150     "(Eventually I should come back around to this becuase it's not tooo difficult to exend this code to be able to compile e.g. `n2 = mul(n1, n1)` for `mul` with the right variable names and insert it in the right place.  It requires a little more support from the library functions, in that we need to know to call `mul()` the Python function for `mul` the Joy function, but since *most* of the math functions (at least) are already wrappers it should be straightforward.)"
2151    ]
2152   },
2153   {
2154    "cell_type": "markdown",
2155    "metadata": {},
2156    "source": [
2157     "#### `compilable()`\n",
2158     "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:"
2159    ]
2160   },
2161   {
2162    "cell_type": "code",
2163    "execution_count": 62,
2164    "metadata": {},
2165    "outputs": [],
2166    "source": [
2167     "from itertools import imap\n",
2168     "\n",
2169     "\n",
2170     "def compilable(f):\n",
2171     "    return isinstance(f, tuple) and all(imap(compilable, f)) or stacky(f)"
2172    ]
2173   },
2174   {
2175    "cell_type": "code",
2176    "execution_count": 63,
2177    "metadata": {
2178     "scrolled": false
2179    },
2180    "outputs": [
2181     {
2182      "name": "stdout",
2183      "output_type": "stream",
2184      "text": [
2185       "ccons = (a1 a2 [.1.] -- [a1 a2 .1.])\n",
2186       "cons = (a1 [.1.] -- [a1 .1.])\n",
2187       "dup = (a1 -- a1 a1)\n",
2188       "dupd = (a2 a1 -- a2 a2 a1)\n",
2189       "first = ([a1 .1.] -- a1)\n",
2190       "over = (a2 a1 -- a2 a1 a2)\n",
2191       "pop = (a1 --)\n",
2192       "popd = (a2 a1 -- a1)\n",
2193       "popdd = (a3 a2 a1 -- a2 a1)\n",
2194       "popop = (a2 a1 --)\n",
2195       "rest = ([a1 .1.] -- [.1.])\n",
2196       "rolldown = (a1 a2 a3 -- a2 a3 a1)\n",
2197       "rollup = (a1 a2 a3 -- a3 a1 a2)\n",
2198       "rrest = ([a1 a2 .1.] -- [.1.])\n",
2199       "second = ([a1 a2 .1.] -- a2)\n",
2200       "swap = (a1 a2 -- a2 a1)\n",
2201       "swons = ([.1.] a1 -- [a1 .1.])\n",
2202       "third = ([a1 a2 a3 .1.] -- a3)\n",
2203       "tuck = (a2 a1 -- a1 a2 a1)\n",
2204       "uncons = ([a1 .1.] -- a1 [.1.])\n"
2205      ]
2206     }
2207    ],
2208    "source": [
2209     "for name, stack_effect_comment in sorted(defs().items()):\n",
2210     "    if compilable(stack_effect_comment):\n",
2211     "        print name, '=', doc_from_stack_effect(*stack_effect_comment)"
2212    ]
2213   },
2214   {
2215    "cell_type": "markdown",
2216    "metadata": {},
2217    "source": [
2218     "## Part V: Functions that use the Stack\n",
2219     "\n",
2220     "Consider the `stack` function which grabs the whole stack, quotes it, and puts it on itself:\n",
2221     "\n",
2222     "    stack (...     -- ... [...]        )\n",
2223     "    stack (... a   -- ... a [a ...]    )\n",
2224     "    stack (... b a -- ... b a [a b ...])\n",
2225     "\n",
2226     "We would like to represent this in Python somehow. \n",
2227     "To do this we use a simple, elegant trick.\n",
2228     "\n",
2229     "    stack         S   -- (         S,           S)\n",
2230     "    stack     (a, S)  -- (     (a, S),      (a, S))\n",
2231     "    stack (a, (b, S)) -- ( (a, (b, S)), (a, (b, S)))\n",
2232     "\n",
2233     "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."
2234    ]
2235   },
2236   {
2237    "cell_type": "markdown",
2238    "metadata": {},
2239    "source": [
2240     "### `stack∘uncons`\n",
2241     "Let's try composing `stack` and `uncons`.  We want this result:\n",
2242     "\n",
2243     "    stack∘uncons (... a -- ... a a [...])"
2244    ]
2245   },
2246   {
2247    "cell_type": "markdown",
2248    "metadata": {},
2249    "source": [
2250     "The stack effects are:\n",
2251     "\n",
2252     "    stack = S -- (S, S)\n",
2253     "\n",
2254     "    uncons = ((a, Z), S) -- (Z, (a, S))"
2255    ]
2256   },
2257   {
2258    "cell_type": "markdown",
2259    "metadata": {},
2260    "source": [
2261     "Unifying:\n",
2262     "\n",
2263     "      S    -- (S, S) ∘ ((a, Z), S) -- (Z, (a,   S   ))\n",
2264     "                                                        w/ { S: (a, Z) }\n",
2265     "    (a, Z) --        ∘             -- (Z, (a, (a, Z)))\n",
2266     "\n",
2267     "So:\n",
2268     "\n",
2269     "    stack∘uncons == (a, Z) -- (Z, (a, (a, Z)))\n",
2270     "\n",
2271     "It works."
2272    ]
2273   },
2274   {
2275    "cell_type": "markdown",
2276    "metadata": {},
2277    "source": [
2278     "### `stack∘uncons∘uncons`\n",
2279     "Let's try `stack∘uncons∘uncons`:\n",
2280     "\n",
2281     "    (a, S     ) -- (S,      (a, (a, S     ))) ∘ ((b, Z),  S`             ) -- (Z, (b,   S`   ))\n",
2282     "    \n",
2283     "                                                                                    w/ { S: (b, Z) }\n",
2284     "                                                                                    \n",
2285     "    (a, (b, Z)) -- ((b, Z), (a, (a, (b, Z)))) ∘ ((b, Z),  S`             ) -- (Z, (b,   S`   ))\n",
2286     "    \n",
2287     "                                                                                    w/ { S`: (a, (a, (b, Z))) }\n",
2288     "                                                                                    \n",
2289     "    (a, (b, Z)) -- ((b, Z), (a, (a, (b, Z)))) ∘ ((b, Z), (a, (a, (b, Z)))) -- (Z, (b, (a, (a, (b, Z)))))\n",
2290     "\n",
2291     "    (a, (b, Z)) -- (Z, (b, (a, (a, (b, Z)))))\n",
2292     "\n",
2293     "It works."
2294    ]
2295   },
2296   {
2297    "cell_type": "markdown",
2298    "metadata": {},
2299    "source": [
2300     "#### `compose()` version 2\n",
2301     "This function has to be modified to use the new datastructures and it is no longer recursive, instead recursion happens as part of unification.  Further, the first and second of Pöial's rules are now handled automatically by the unification algorithm.  (One easy way to see this is that now an empty stack effect comment is represented by a `StackJoyType` instance which is not \"falsey\" and so neither of the first two rules' `if` clauses will ever be `True`.  Later on I change the \"truthiness\" of `StackJoyType` to false to let e.g. `joy.utils.stack.concat` work with our stack effect comment cons-list tuples.)"
2302    ]
2303   },
2304   {
2305    "cell_type": "code",
2306    "execution_count": 64,
2307    "metadata": {},
2308    "outputs": [],
2309    "source": [
2310     "def compose(f, g):\n",
2311     "    (f_in, f_out), (g_in, g_out) = f, g\n",
2312     "    s = unify(g_in, f_out)\n",
2313     "    if s == False:  # s can also be the empty dict, which is ok.\n",
2314     "        raise TypeError('Cannot unify %r and %r.' % (f_out, g_in))\n",
2315     "    return update(s, (f_in, g_out))"
2316    ]
2317   },
2318   {
2319    "cell_type": "markdown",
2320    "metadata": {},
2321    "source": [
2322     "I don't want to rewrite all the defs myself, so I'll write a little conversion function instead.  This is programmer's laziness."
2323    ]
2324   },
2325   {
2326    "cell_type": "code",
2327    "execution_count": 65,
2328    "metadata": {},
2329    "outputs": [],
2330    "source": [
2331     "def sequence_to_stack(seq, stack=StackJoyType(23)):\n",
2332     "    for item in seq: stack = item, stack\n",
2333     "    return stack\n",
2334     "\n",
2335     "NEW_DEFS = {\n",
2336     "    name: (sequence_to_stack(i), sequence_to_stack(o))\n",
2337     "    for name, (i, o) in DEFS.iteritems()\n",
2338     "}\n",
2339     "NEW_DEFS['stack'] = S[0], (S[0], S[0])\n",
2340     "NEW_DEFS['swaack'] = (S[1], S[0]), (S[0], S[1])\n",
2341     "globals().update(NEW_DEFS)"
2342    ]
2343   },
2344   {
2345    "cell_type": "code",
2346    "execution_count": 66,
2347    "metadata": {},
2348    "outputs": [
2349     {
2350      "data": {
2351       "text/plain": [
2352        "((a1, s1), (s1, (a1, (a1, s1))))"
2353       ]
2354      },
2355      "execution_count": 66,
2356      "metadata": {},
2357      "output_type": "execute_result"
2358     }
2359    ],
2360    "source": [
2361     "C(stack, uncons)"
2362    ]
2363   },
2364   {
2365    "cell_type": "code",
2366    "execution_count": 67,
2367    "metadata": {},
2368    "outputs": [
2369     {
2370      "data": {
2371       "text/plain": [
2372        "((a1, (a2, s1)), (s1, (a2, (a1, (a1, (a2, s1))))))"
2373       ]
2374      },
2375      "execution_count": 67,
2376      "metadata": {},
2377      "output_type": "execute_result"
2378     }
2379    ],
2380    "source": [
2381     "reduce(C, (stack, uncons, uncons))"
2382    ]
2383   },
2384   {
2385    "cell_type": "markdown",
2386    "metadata": {},
2387    "source": [
2388     "The display function should be changed too."
2389    ]
2390   },
2391   {
2392    "cell_type": "markdown",
2393    "metadata": {},
2394    "source": [
2395     "### `doc_from_stack_effect()` version 2\n",
2396     "Clunky junk, but it will suffice for now."
2397    ]
2398   },
2399   {
2400    "cell_type": "code",
2401    "execution_count": 68,
2402    "metadata": {},
2403    "outputs": [],
2404    "source": [
2405     "def doc_from_stack_effect(inputs, outputs):\n",
2406     "    switch = [False]  # Do we need to display the '...' for the rest of the main stack?\n",
2407     "    i, o = _f(inputs, switch), _f(outputs, switch)\n",
2408     "    if switch[0]:\n",
2409     "        i.append('...')\n",
2410     "        o.append('...')\n",
2411     "    return '(%s--%s)' % (\n",
2412     "        ' '.join(reversed([''] + i)),\n",
2413     "        ' '.join(reversed(o + [''])),\n",
2414     "    )\n",
2415     "\n",
2416     "\n",
2417     "def _f(term, switch):\n",
2418     "    a = []\n",
2419     "    while term and isinstance(term, tuple):\n",
2420     "        item, term = term\n",
2421     "        a.append(item)\n",
2422     "    assert isinstance(term, StackJoyType), repr(term)\n",
2423     "    a = [_to_str(i, term, switch) for i in a]\n",
2424     "    return a\n",
2425     "\n",
2426     "\n",
2427     "def _to_str(term, stack, switch):\n",
2428     "    if not isinstance(term, tuple):\n",
2429     "        if term == stack:\n",
2430     "            switch[0] = True\n",
2431     "            return '[...]'\n",
2432     "        return (\n",
2433     "            '[.%i.]' % term.number\n",
2434     "            if isinstance(term, StackJoyType)\n",
2435     "            else str(term)\n",
2436     "        )\n",
2437     "\n",
2438     "    a = []\n",
2439     "    while term and isinstance(term, tuple):\n",
2440     "        item, term = term\n",
2441     "        a.append(_to_str(item, stack, switch))\n",
2442     "    assert isinstance(term, StackJoyType), repr(term)\n",
2443     "    if term == stack:\n",
2444     "        switch[0] = True\n",
2445     "        end = '...'\n",
2446     "    else:\n",
2447     "        end = '.%i.' % term.number\n",
2448     "    a.append(end)\n",
2449     "    return '[%s]' % ' '.join(a)"
2450    ]
2451   },
2452   {
2453    "cell_type": "code",
2454    "execution_count": 69,
2455    "metadata": {
2456     "scrolled": false
2457    },
2458    "outputs": [
2459     {
2460      "name": "stdout",
2461      "output_type": "stream",
2462      "text": [
2463       "ccons = (a1 a2 [.1.] -- [a1 a2 .1.])\n",
2464       "cons = (a1 [.1.] -- [a1 .1.])\n",
2465       "divmod_ = (n2 n1 -- n4 n3)\n",
2466       "dup = (a1 -- a1 a1)\n",
2467       "dupd = (a2 a1 -- a2 a2 a1)\n",
2468       "first = ([a1 .1.] -- a1)\n",
2469       "mul = (n1 n2 -- n3)\n",
2470       "over = (a2 a1 -- a2 a1 a2)\n",
2471       "pm = (n2 n1 -- n4 n3)\n",
2472       "pop = (a1 --)\n",
2473       "popd = (a2 a1 -- a1)\n",
2474       "popdd = (a3 a2 a1 -- a2 a1)\n",
2475       "popop = (a2 a1 --)\n",
2476       "pred = (n1 -- n2)\n",
2477       "rest = ([a1 .1.] -- [.1.])\n",
2478       "rolldown = (a1 a2 a3 -- a2 a3 a1)\n",
2479       "rollup = (a1 a2 a3 -- a3 a1 a2)\n",
2480       "rrest = ([a1 a2 .1.] -- [.1.])\n",
2481       "second = ([a1 a2 .1.] -- a2)\n",
2482       "sqrt = (n1 -- n2)\n",
2483       "stack = (... -- ... [...])\n",
2484       "succ = (n1 -- n2)\n",
2485       "swaack = ([.1.] -- [.0.])\n",
2486       "swap = (a1 a2 -- a2 a1)\n",
2487       "swons = ([.1.] a1 -- [a1 .1.])\n",
2488       "third = ([a1 a2 a3 .1.] -- a3)\n",
2489       "tuck = (a2 a1 -- a1 a2 a1)\n",
2490       "uncons = ([a1 .1.] -- a1 [.1.])\n"
2491      ]
2492     }
2493    ],
2494    "source": [
2495     "for name, stack_effect_comment in sorted(NEW_DEFS.items()):\n",
2496     "    print name, '=', doc_from_stack_effect(*stack_effect_comment)"
2497    ]
2498   },
2499   {
2500    "cell_type": "code",
2501    "execution_count": 70,
2502    "metadata": {},
2503    "outputs": [
2504     {
2505      "name": "stdout",
2506      "output_type": "stream",
2507      "text": [
2508       "\n",
2509       "(... -- ... [...])\n",
2510       "\n",
2511       "(... a1 -- ... a1 a1 [...])\n",
2512       "\n",
2513       "(... a2 a1 -- ... a2 a1 a1 a2 [...])\n",
2514       "\n",
2515       "(... a1 -- ... a1 [a1 ...])\n"
2516      ]
2517     }
2518    ],
2519    "source": [
2520     "print ; print doc_from_stack_effect(*stack)\n",
2521     "print ; print doc_from_stack_effect(*C(stack, uncons))\n",
2522     "print ; print doc_from_stack_effect(*reduce(C, (stack, uncons, uncons)))\n",
2523     "print ; print doc_from_stack_effect(*reduce(C, (stack, uncons, cons)))"
2524    ]
2525   },
2526   {
2527    "cell_type": "code",
2528    "execution_count": 71,
2529    "metadata": {},
2530    "outputs": [
2531     {
2532      "name": "stdout",
2533      "output_type": "stream",
2534      "text": [
2535       "(... a2 a1 [.1.] -- ... [a2 a1 .1.] [[a2 a1 .1.] ...])\n"
2536      ]
2537     }
2538    ],
2539    "source": [
2540     "print doc_from_stack_effect(*C(ccons, stack))"
2541    ]
2542   },
2543   {
2544    "cell_type": "code",
2545    "execution_count": 72,
2546    "metadata": {},
2547    "outputs": [
2548     {
2549      "data": {
2550       "text/plain": [
2551        "((s1, (a1, (a2, s2))), (((a2, (a1, s1)), s2), ((a2, (a1, s1)), s2)))"
2552       ]
2553      },
2554      "execution_count": 72,
2555      "metadata": {},
2556      "output_type": "execute_result"
2557     }
2558    ],
2559    "source": [
2560     "Q = C(ccons, stack)\n",
2561     "\n",
2562     "Q"
2563    ]
2564   },
2565   {
2566    "cell_type": "markdown",
2567    "metadata": {},
2568    "source": [
2569     "#### `compile_()` version 3\n",
2570     "This makes the `compile_()` function pretty simple as the stack effect comments are now already in the form needed for the Python code:"
2571    ]
2572   },
2573   {
2574    "cell_type": "code",
2575    "execution_count": 73,
2576    "metadata": {},
2577    "outputs": [],
2578    "source": [
2579     "def compile_(name, f, doc=None):\n",
2580     "    i, o = f\n",
2581     "    if doc is None:\n",
2582     "        doc = doc_from_stack_effect(i, o)\n",
2583     "    return '''def %s(stack):\n",
2584     "    \"\"\"%s\"\"\"\n",
2585     "    %s = stack\n",
2586     "    return %s''' % (name, doc, i, o)"
2587    ]
2588   },
2589   {
2590    "cell_type": "code",
2591    "execution_count": 74,
2592    "metadata": {},
2593    "outputs": [
2594     {
2595      "name": "stdout",
2596      "output_type": "stream",
2597      "text": [
2598       "def Q(stack):\n",
2599       "    \"\"\"(... a2 a1 [.1.] -- ... [a2 a1 .1.] [[a2 a1 .1.] ...])\"\"\"\n",
2600       "    (s1, (a1, (a2, s2))) = stack\n",
2601       "    return (((a2, (a1, s1)), s2), ((a2, (a1, s1)), s2))\n"
2602      ]
2603     }
2604    ],
2605    "source": [
2606     "print compile_('Q', Q)"
2607    ]
2608   },
2609   {
2610    "cell_type": "code",
2611    "execution_count": null,
2612    "metadata": {},
2613    "outputs": [],
2614    "source": []
2615   },
2616   {
2617    "cell_type": "code",
2618    "execution_count": null,
2619    "metadata": {},
2620    "outputs": [],
2621    "source": []
2622   },
2623   {
2624    "cell_type": "code",
2625    "execution_count": null,
2626    "metadata": {},
2627    "outputs": [],
2628    "source": []
2629   },
2630   {
2631    "cell_type": "code",
2632    "execution_count": null,
2633    "metadata": {},
2634    "outputs": [],
2635    "source": []
2636   },
2637   {
2638    "cell_type": "code",
2639    "execution_count": null,
2640    "metadata": {},
2641    "outputs": [],
2642    "source": []
2643   },
2644   {
2645    "cell_type": "code",
2646    "execution_count": 75,
2647    "metadata": {},
2648    "outputs": [],
2649    "source": [
2650     "unstack = (S[1], S[0]), S[1]\n",
2651     "enstacken = S[0], (S[0], S[1])"
2652    ]
2653   },
2654   {
2655    "cell_type": "code",
2656    "execution_count": 76,
2657    "metadata": {},
2658    "outputs": [
2659     {
2660      "name": "stdout",
2661      "output_type": "stream",
2662      "text": [
2663       "([.1.] --)\n"
2664      ]
2665     }
2666    ],
2667    "source": [
2668     "print doc_from_stack_effect(*unstack)"
2669    ]
2670   },
2671   {
2672    "cell_type": "code",
2673    "execution_count": 77,
2674    "metadata": {},
2675    "outputs": [
2676     {
2677      "name": "stdout",
2678      "output_type": "stream",
2679      "text": [
2680       "(-- [.0.])\n"
2681      ]
2682     }
2683    ],
2684    "source": [
2685     "print doc_from_stack_effect(*enstacken)"
2686    ]
2687   },
2688   {
2689    "cell_type": "code",
2690    "execution_count": 78,
2691    "metadata": {},
2692    "outputs": [
2693     {
2694      "name": "stdout",
2695      "output_type": "stream",
2696      "text": [
2697       "(a1 [.1.] -- a1)\n"
2698      ]
2699     }
2700    ],
2701    "source": [
2702     "print doc_from_stack_effect(*C(cons, unstack))"
2703    ]
2704   },
2705   {
2706    "cell_type": "code",
2707    "execution_count": 79,
2708    "metadata": {},
2709    "outputs": [
2710     {
2711      "name": "stdout",
2712      "output_type": "stream",
2713      "text": [
2714       "(a1 [.1.] -- [[a1 .1.] .2.])\n"
2715      ]
2716     }
2717    ],
2718    "source": [
2719     "print doc_from_stack_effect(*C(cons, enstacken))"
2720    ]
2721   },
2722   {
2723    "cell_type": "code",
2724    "execution_count": 80,
2725    "metadata": {},
2726    "outputs": [
2727     {
2728      "data": {
2729       "text/plain": [
2730        "((s1, (a1, s2)), (a1, s1))"
2731       ]
2732      },
2733      "execution_count": 80,
2734      "metadata": {},
2735      "output_type": "execute_result"
2736     }
2737    ],
2738    "source": [
2739     "C(cons, unstack)"
2740    ]
2741   },
2742   {
2743    "cell_type": "code",
2744    "execution_count": null,
2745    "metadata": {},
2746    "outputs": [],
2747    "source": []
2748   },
2749   {
2750    "cell_type": "markdown",
2751    "metadata": {},
2752    "source": [
2753     "## Part VI: Multiple Stack Effects\n",
2754     "..."
2755    ]
2756   },
2757   {
2758    "cell_type": "code",
2759    "execution_count": 81,
2760    "metadata": {},
2761    "outputs": [],
2762    "source": [
2763     "class IntJoyType(NumberJoyType): prefix = 'i'\n",
2764     "\n",
2765     "\n",
2766     "F = map(FloatJoyType, _R)\n",
2767     "I = map(IntJoyType, _R)"
2768    ]
2769   },
2770   {
2771    "cell_type": "code",
2772    "execution_count": 82,
2773    "metadata": {},
2774    "outputs": [],
2775    "source": [
2776     "muls = [\n",
2777     "     ((I[2], (I[1], S[0])), (I[3], S[0])),\n",
2778     "     ((F[2], (I[1], S[0])), (F[3], S[0])),\n",
2779     "     ((I[2], (F[1], S[0])), (F[3], S[0])),\n",
2780     "     ((F[2], (F[1], S[0])), (F[3], S[0])),\n",
2781     "]"
2782    ]
2783   },
2784   {
2785    "cell_type": "code",
2786    "execution_count": 83,
2787    "metadata": {},
2788    "outputs": [
2789     {
2790      "name": "stdout",
2791      "output_type": "stream",
2792      "text": [
2793       "(i1 i2 -- i3)\n",
2794       "(i1 f2 -- f3)\n",
2795       "(f1 i2 -- f3)\n",
2796       "(f1 f2 -- f3)\n"
2797      ]
2798     }
2799    ],
2800    "source": [
2801     "for f in muls:\n",
2802     "    print doc_from_stack_effect(*f)"
2803    ]
2804   },
2805   {
2806    "cell_type": "code",
2807    "execution_count": 84,
2808    "metadata": {},
2809    "outputs": [
2810     {
2811      "name": "stdout",
2812      "output_type": "stream",
2813      "text": [
2814       "(a1 -- a1 a1) (i1 i2 -- i3) (i1 -- i2)\n",
2815       "(a1 -- a1 a1) (f1 f2 -- f3) (f1 -- f2)\n"
2816      ]
2817     }
2818    ],
2819    "source": [
2820     "for f in muls:\n",
2821     "    try:\n",
2822     "        e = C(dup, f)\n",
2823     "    except TypeError:\n",
2824     "        continue\n",
2825     "    print doc_from_stack_effect(*dup), doc_from_stack_effect(*f), doc_from_stack_effect(*e)"
2826    ]
2827   },
2828   {
2829    "cell_type": "code",
2830    "execution_count": 85,
2831    "metadata": {},
2832    "outputs": [],
2833    "source": [
2834     "from itertools import product\n",
2835     "\n",
2836     "\n",
2837     "def meta_compose(F, G):\n",
2838     "    for f, g in product(F, G):\n",
2839     "        try:\n",
2840     "            yield C(f, g)\n",
2841     "        except TypeError:\n",
2842     "            pass\n",
2843     "\n",
2844     "\n",
2845     "def MC(F, G):\n",
2846     "    return sorted(set(meta_compose(F, G)))"
2847    ]
2848   },
2849   {
2850    "cell_type": "code",
2851    "execution_count": 86,
2852    "metadata": {},
2853    "outputs": [
2854     {
2855      "name": "stdout",
2856      "output_type": "stream",
2857      "text": [
2858       "(n1 -- n2)\n"
2859      ]
2860     }
2861    ],
2862    "source": [
2863     "for f in MC([dup], [mul]):\n",
2864     "    print doc_from_stack_effect(*f)"
2865    ]
2866   },
2867   {
2868    "cell_type": "code",
2869    "execution_count": 87,
2870    "metadata": {},
2871    "outputs": [
2872     {
2873      "name": "stdout",
2874      "output_type": "stream",
2875      "text": [
2876       "(f1 -- f2)\n",
2877       "(i1 -- i2)\n"
2878      ]
2879     }
2880    ],
2881    "source": [
2882     "for f in MC([dup], muls):\n",
2883     "    print doc_from_stack_effect(*f)"
2884    ]
2885   },
2886   {
2887    "cell_type": "markdown",
2888    "metadata": {},
2889    "source": [
2890     "### Representing an Unbounded Sequence of Types\n",
2891     "\n",
2892     "We can borrow a trick from [Brzozowski's Derivatives of Regular Expressions](https://en.wikipedia.org/wiki/Brzozowski_derivative) to 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](https://en.wikipedia.org/wiki/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:\n",
2893     "\n",
2894     "    A*"
2895    ]
2896   },
2897   {
2898    "cell_type": "markdown",
2899    "metadata": {},
2900    "source": [
2901     "The `A*` works by splitting the universe into two alternate histories:\n",
2902     "\n",
2903     "    A* -> 0 | A A*\n",
2904     "\n",
2905     "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."
2906    ]
2907   },
2908   {
2909    "cell_type": "markdown",
2910    "metadata": {},
2911    "source": [
2912     "Consider unifying two stacks (the lowercase letters are any type variables of the kinds we have defined so far):\n",
2913     "\n",
2914     "    [a A* b .0.] U [c d .1.]\n",
2915     "                              w/ {c: a}\n",
2916     "    [  A* b .0.] U [  d .1.]"
2917    ]
2918   },
2919   {
2920    "cell_type": "markdown",
2921    "metadata": {},
2922    "source": [
2923     "Now we have to split universes to unify `A*`.  In the first universe it disappears:\n",
2924     "\n",
2925     "    [b .0.] U [d .1.]\n",
2926     "                       w/ {d: b, .1.: .0.} \n",
2927     "         [] U []"
2928    ]
2929   },
2930   {
2931    "cell_type": "markdown",
2932    "metadata": {},
2933    "source": [
2934     "While in the second it spawns an `A`, which we will label `e`:\n",
2935     "\n",
2936     "    [e A* b .0.] U [d .1.]\n",
2937     "                            w/ {d: e}\n",
2938     "    [  A* b .0.] U [  .1.]\n",
2939     "                            w/ {.1.: A* b .0.}\n",
2940     "    [  A* b .0.] U [  A* b .0.]"
2941    ]
2942   },
2943   {
2944    "cell_type": "markdown",
2945    "metadata": {},
2946    "source": [
2947     "Giving us two unifiers:\n",
2948     "\n",
2949     "    {c: a,  d: b,  .1.:      .0.}\n",
2950     "    {c: a,  d: e,  .1.: A* b .0.}"
2951    ]
2952   },
2953   {
2954    "cell_type": "code",
2955    "execution_count": 88,
2956    "metadata": {},
2957    "outputs": [],
2958    "source": [
2959     "class KleeneStar(object):\n",
2960     "\n",
2961     "    kind = AnyJoyType\n",
2962     "\n",
2963     "    def __init__(self, number):\n",
2964     "        self.number = number\n",
2965     "        self.count = 0\n",
2966     "        self.prefix = repr(self)\n",
2967     "\n",
2968     "    def __repr__(self):\n",
2969     "        return '%s%i*' % (self.kind.prefix, self.number)\n",
2970     "\n",
2971     "    def another(self):\n",
2972     "        self.count += 1\n",
2973     "        return self.kind(10000 * self.number + self.count)\n",
2974     "\n",
2975     "    def __eq__(self, other):\n",
2976     "        return (\n",
2977     "            isinstance(other, self.__class__)\n",
2978     "            and other.number == self.number\n",
2979     "        )\n",
2980     "\n",
2981     "    def __ge__(self, other):\n",
2982     "        return self.kind >= other.kind\n",
2983     "\n",
2984     "    def __add__(self, other):\n",
2985     "        return self.__class__(self.number + other)\n",
2986     "    __radd__ = __add__\n",
2987     "    \n",
2988     "    def __hash__(self):\n",
2989     "        return hash(repr(self))\n",
2990     "\n",
2991     "class AnyStarJoyType(KleeneStar): kind = AnyJoyType\n",
2992     "class NumberStarJoyType(KleeneStar): kind = NumberJoyType\n",
2993     "#class FloatStarJoyType(KleeneStar): kind = FloatJoyType\n",
2994     "#class IntStarJoyType(KleeneStar): kind = IntJoyType\n",
2995     "class StackStarJoyType(KleeneStar): kind = StackJoyType\n",
2996     "\n",
2997     "\n",
2998     "As = map(AnyStarJoyType, _R)\n",
2999     "Ns = map(NumberStarJoyType, _R)\n",
3000     "Ss = map(StackStarJoyType, _R)"
3001    ]
3002   },
3003   {
3004    "cell_type": "markdown",
3005    "metadata": {},
3006    "source": [
3007     "#### `unify()` version 4\n",
3008     "Can now return multiple results..."
3009    ]
3010   },
3011   {
3012    "cell_type": "code",
3013    "execution_count": 89,
3014    "metadata": {},
3015    "outputs": [],
3016    "source": [
3017     "def unify(u, v, s=None):\n",
3018     "    if s is None:\n",
3019     "        s = {}\n",
3020     "    elif s:\n",
3021     "        u = update(s, u)\n",
3022     "        v = update(s, v)\n",
3023     "\n",
3024     "    if u == v:\n",
3025     "        return s,\n",
3026     "\n",
3027     "    if isinstance(u, AnyJoyType) and isinstance(v, AnyJoyType):\n",
3028     "        if u >= v:\n",
3029     "            s[u] = v\n",
3030     "            return s,\n",
3031     "        if v >= u:\n",
3032     "            s[v] = u\n",
3033     "            return s,\n",
3034     "        raise TypeError('Cannot unify %r and %r.' % (u, v))\n",
3035     "\n",
3036     "    if isinstance(u, tuple) and isinstance(v, tuple):\n",
3037     "        if len(u) != len(v) != 2:\n",
3038     "            raise TypeError(repr((u, v)))\n",
3039     "            \n",
3040     "        a, b = v\n",
3041     "        if isinstance(a, KleeneStar):\n",
3042     "            # Two universes, in one the Kleene star disappears and unification\n",
3043     "            # continues without it...\n",
3044     "            s0 = unify(u, b)\n",
3045     "            \n",
3046     "            # In the other it spawns a new variable.\n",
3047     "            s1 = unify(u, (a.another(), v))\n",
3048     "            \n",
3049     "            t = s0 + s1\n",
3050     "            for sn in t:\n",
3051     "                sn.update(s)\n",
3052     "            return t\n",
3053     "\n",
3054     "        a, b = u\n",
3055     "        if isinstance(a, KleeneStar):\n",
3056     "            s0 = unify(v, b)\n",
3057     "            s1 = unify(v, (a.another(), u))\n",
3058     "            t = s0 + s1\n",
3059     "            for sn in t:\n",
3060     "                sn.update(s)\n",
3061     "            return t\n",
3062     "\n",
3063     "        ses = unify(u[0], v[0], s)\n",
3064     "        results = ()\n",
3065     "        for sn in ses:\n",
3066     "            results += unify(u[1], v[1], sn)\n",
3067     "        return results\n",
3068     " \n",
3069     "    if isinstance(v, tuple):\n",
3070     "        if not stacky(u):\n",
3071     "            raise TypeError('Cannot unify %r and %r.' % (u, v))\n",
3072     "        s[u] = v\n",
3073     "        return s,\n",
3074     "\n",
3075     "    if isinstance(u, tuple):\n",
3076     "        if not stacky(v):\n",
3077     "            raise TypeError('Cannot unify %r and %r.' % (v, u))\n",
3078     "        s[v] = u\n",
3079     "        return s,\n",
3080     "\n",
3081     "    return ()\n",
3082     "\n",
3083     "\n",
3084     "def stacky(thing):\n",
3085     "    return thing.__class__ in {AnyJoyType, StackJoyType}"
3086    ]
3087   },
3088   {
3089    "cell_type": "code",
3090    "execution_count": 90,
3091    "metadata": {},
3092    "outputs": [
3093     {
3094      "data": {
3095       "text/plain": [
3096        "(a1*, s1)"
3097       ]
3098      },
3099      "execution_count": 90,
3100      "metadata": {},
3101      "output_type": "execute_result"
3102     }
3103    ],
3104    "source": [
3105     "a = (As[1], S[1])\n",
3106     "a"
3107    ]
3108   },
3109   {
3110    "cell_type": "code",
3111    "execution_count": 91,
3112    "metadata": {},
3113    "outputs": [
3114     {
3115      "data": {
3116       "text/plain": [
3117        "(a1, s2)"
3118       ]
3119      },
3120      "execution_count": 91,
3121      "metadata": {},
3122      "output_type": "execute_result"
3123     }
3124    ],
3125    "source": [
3126     "b = (A[1], S[2])\n",
3127     "b"
3128    ]
3129   },
3130   {
3131    "cell_type": "code",
3132    "execution_count": 92,
3133    "metadata": {},
3134    "outputs": [
3135     {
3136      "name": "stdout",
3137      "output_type": "stream",
3138      "text": [
3139       "{s1: (a1, s2)} -> (a1*, (a1, s2)) (a1, s2)\n",
3140       "{a1: a10001, s2: (a1*, s1)} -> (a1*, s1) (a10001, (a1*, s1))\n"
3141      ]
3142     }
3143    ],
3144    "source": [
3145     "for result in unify(b, a):\n",
3146     "    print result, '->', update(result, a), update(result, b)"
3147    ]
3148   },
3149   {
3150    "cell_type": "code",
3151    "execution_count": 93,
3152    "metadata": {},
3153    "outputs": [
3154     {
3155      "name": "stdout",
3156      "output_type": "stream",
3157      "text": [
3158       "{s1: (a1, s2)} -> (a1*, (a1, s2)) (a1, s2)\n",
3159       "{a1: a10002, s2: (a1*, s1)} -> (a1*, s1) (a10002, (a1*, s1))\n"
3160      ]
3161     }
3162    ],
3163    "source": [
3164     "for result in unify(a, b):\n",
3165     "    print result, '->', update(result, a), update(result, b)"
3166    ]
3167   },
3168   {
3169    "cell_type": "markdown",
3170    "metadata": {},
3171    "source": [
3172     "\n",
3173     "    (a1*, s1)       [a1*]       (a1, s2)        [a1]\n",
3174     "\n",
3175     "    (a1*, (a1, s2)) [a1* a1]    (a1, s2)        [a1]\n",
3176     "\n",
3177     "    (a1*, s1)       [a1*]       (a2, (a1*, s1)) [a2 a1*]"
3178    ]
3179   },
3180   {
3181    "cell_type": "code",
3182    "execution_count": 94,
3183    "metadata": {},
3184    "outputs": [
3185     {
3186      "name": "stdout",
3187      "output_type": "stream",
3188      "text": [
3189       "([n1* .1.] -- n0)\n"
3190      ]
3191     }
3192    ],
3193    "source": [
3194     "sum_ = ((Ns[1], S[1]), S[0]), (N[0], S[0])\n",
3195     "\n",
3196     "print doc_from_stack_effect(*sum_)"
3197    ]
3198   },
3199   {
3200    "cell_type": "code",
3201    "execution_count": 95,
3202    "metadata": {},
3203    "outputs": [
3204     {
3205      "name": "stdout",
3206      "output_type": "stream",
3207      "text": [
3208       "(-- [n1 n2 n3 .1.])\n"
3209      ]
3210     }
3211    ],
3212    "source": [
3213     "f = (N[1], (N[2], (N[3], S[1]))), S[0]\n",
3214     "\n",
3215     "print doc_from_stack_effect(S[0], f)"
3216    ]
3217   },
3218   {
3219    "cell_type": "code",
3220    "execution_count": 96,
3221    "metadata": {},
3222    "outputs": [
3223     {
3224      "name": "stdout",
3225      "output_type": "stream",
3226      "text": [
3227       "{s1: (n1, (n2, (n3, s1)))} -> (n0, s0)\n",
3228       "{n1: n10001, s1: (n2, (n3, s1))} -> (n0, s0)\n",
3229       "{n1: n10001, s1: (n3, s1), n2: n10002} -> (n0, s0)\n",
3230       "{n1: n10001, s1: (n1*, s1), n3: n10003, n2: n10002} -> (n0, s0)\n"
3231      ]
3232     }
3233    ],
3234    "source": [
3235     "for result in unify(sum_[0], f):\n",
3236     "    print result, '->', update(result, sum_[1])"
3237    ]
3238   },
3239   {
3240    "cell_type": "markdown",
3241    "metadata": {},
3242    "source": [
3243     "#### `compose()` version 3\n",
3244     "This function has to be modified to yield multiple results."
3245    ]
3246   },
3247   {
3248    "cell_type": "code",
3249    "execution_count": 97,
3250    "metadata": {},
3251    "outputs": [],
3252    "source": [
3253     "def compose(f, g):\n",
3254     "    (f_in, f_out), (g_in, g_out) = f, g\n",
3255     "    s = unify(g_in, f_out)\n",
3256     "    if not s:\n",
3257     "        raise TypeError('Cannot unify %r and %r.' % (f_out, g_in))\n",
3258     "    for result in s:\n",
3259     "        yield update(result, (f_in, g_out))\n"
3260    ]
3261   },
3262   {
3263    "cell_type": "code",
3264    "execution_count": null,
3265    "metadata": {},
3266    "outputs": [],
3267    "source": []
3268   },
3269   {
3270    "cell_type": "code",
3271    "execution_count": 98,
3272    "metadata": {},
3273    "outputs": [],
3274    "source": [
3275     "def meta_compose(F, G):\n",
3276     "    for f, g in product(F, G):\n",
3277     "        try:\n",
3278     "            for result in C(f, g):\n",
3279     "                yield result\n",
3280     "        except TypeError:\n",
3281     "            pass\n",
3282     "\n",
3283     "\n",
3284     "def C(f, g):\n",
3285     "    f, g = relabel(f, g)\n",
3286     "    for fg in compose(f, g):\n",
3287     "        yield delabel(fg)"
3288    ]
3289   },
3290   {
3291    "cell_type": "code",
3292    "execution_count": 99,
3293    "metadata": {},
3294    "outputs": [
3295     {
3296      "name": "stdout",
3297      "output_type": "stream",
3298      "text": [
3299       "(f1 -- f2)\n",
3300       "(i1 -- i2)\n"
3301      ]
3302     }
3303    ],
3304    "source": [
3305     "for f in MC([dup], muls):\n",
3306     "    print doc_from_stack_effect(*f)"
3307    ]
3308   },
3309   {
3310    "cell_type": "code",
3311    "execution_count": 100,
3312    "metadata": {},
3313    "outputs": [
3314     {
3315      "name": "stdout",
3316      "output_type": "stream",
3317      "text": [
3318       "([n1* .1.] -- [n1* .1.] n1)\n"
3319      ]
3320     }
3321    ],
3322    "source": [
3323     "\n",
3324     "\n",
3325     "for f in MC([dup], [sum_]):\n",
3326     "    print doc_from_stack_effect(*f)"
3327    ]
3328   },
3329   {
3330    "cell_type": "code",
3331    "execution_count": 101,
3332    "metadata": {},
3333    "outputs": [
3334     {
3335      "name": "stdout",
3336      "output_type": "stream",
3337      "text": [
3338       "(a1 [.1.] -- n1)\n",
3339       "(n1 [n1* .1.] -- n2)\n"
3340      ]
3341     }
3342    ],
3343    "source": [
3344     "\n",
3345     "\n",
3346     "for f in MC([cons], [sum_]):\n",
3347     "    print doc_from_stack_effect(*f)"
3348    ]
3349   },
3350   {
3351    "cell_type": "code",
3352    "execution_count": 102,
3353    "metadata": {},
3354    "outputs": [
3355     {
3356      "name": "stdout",
3357      "output_type": "stream",
3358      "text": [
3359       "(a1 [.1.] -- [a1 .1.]) ([n1 n1* .1.] -- n0) (n1 [n1* .1.] -- n2)\n"
3360      ]
3361     }
3362    ],
3363    "source": [
3364     "sum_ = (((N[1], (Ns[1], S[1])), S[0]), (N[0], S[0]))\n",
3365     "print doc_from_stack_effect(*cons),\n",
3366     "print doc_from_stack_effect(*sum_),\n",
3367     "\n",
3368     "for f in MC([cons], [sum_]):\n",
3369     "    print doc_from_stack_effect(*f)"
3370    ]
3371   },
3372   {
3373    "cell_type": "code",
3374    "execution_count": 103,
3375    "metadata": {},
3376    "outputs": [
3377     {
3378      "data": {
3379       "text/plain": [
3380        "(a4, (a1*, (a3, s1)))"
3381       ]
3382      },
3383      "execution_count": 103,
3384      "metadata": {},
3385      "output_type": "execute_result"
3386     }
3387    ],
3388    "source": [
3389     "a = (A[4], (As[1], (A[3], S[1])))\n",
3390     "a"
3391    ]
3392   },
3393   {
3394    "cell_type": "code",
3395    "execution_count": 104,
3396    "metadata": {},
3397    "outputs": [
3398     {
3399      "data": {
3400       "text/plain": [
3401        "(a1, (a2, s2))"
3402       ]
3403      },
3404      "execution_count": 104,
3405      "metadata": {},
3406      "output_type": "execute_result"
3407     }
3408    ],
3409    "source": [
3410     "b = (A[1], (A[2], S[2]))\n",
3411     "b"
3412    ]
3413   },
3414   {
3415    "cell_type": "code",
3416    "execution_count": 105,
3417    "metadata": {},
3418    "outputs": [
3419     {
3420      "name": "stdout",
3421      "output_type": "stream",
3422      "text": [
3423       "{a1: a4, s2: s1, a2: a3}\n",
3424       "{a1: a4, s2: (a1*, (a3, s1)), a2: a10003}\n"
3425      ]
3426     }
3427    ],
3428    "source": [
3429     "for result in unify(b, a):\n",
3430     "    print result"
3431    ]
3432   },
3433   {
3434    "cell_type": "code",
3435    "execution_count": 106,
3436    "metadata": {},
3437    "outputs": [
3438     {
3439      "name": "stdout",
3440      "output_type": "stream",
3441      "text": [
3442       "{s2: s1, a2: a3, a4: a1}\n",
3443       "{s2: (a1*, (a3, s1)), a2: a10004, a4: a1}\n"
3444      ]
3445     }
3446    ],
3447    "source": [
3448     "for result in unify(a, b):\n",
3449     "    print result"
3450    ]
3451   },
3452   {
3453    "cell_type": "markdown",
3454    "metadata": {},
3455    "source": [
3456     "## Part VII: Typing Combinators\n",
3457     "\n",
3458     "In order to compute the stack effect of combinators you kinda have to have the quoted programs they expect available.  In the most general case, the `i` combinator, you can't say anything about its stack effect other than it expects one quote:\n",
3459     "\n",
3460     "    i (... [.1.] -- ... .1.)\n",
3461     "\n",
3462     "Or\n",
3463     "\n",
3464     "    i (... [A* .1.] -- ... A*)\n",
3465     "\n",
3466     "Consider the type of:\n",
3467     "\n",
3468     "    [cons] dip\n",
3469     "\n",
3470     "Obviously it would be:\n",
3471     "\n",
3472     "    (a1 [..1] a2 -- [a1 ..1] a2)\n",
3473     "\n",
3474     "`dip` itself could have:\n",
3475     "\n",
3476     "    (a1 [..1] -- ... then what?\n",
3477     "\n",
3478     "\n",
3479     "Without any information about the contents of the quote we can't say much about the result."
3480    ]
3481   },
3482   {
3483    "cell_type": "markdown",
3484    "metadata": {},
3485    "source": [
3486     "### Hybrid Inferencer/Interpreter\n",
3487     "I think there's a way forward.  If we convert our list (of terms we are composing) into a stack structure we can use it as a *Joy expression*, then we can treat the *output half* of a function's stack effect comment as a Joy interpreter stack, and just execute combinators directly.  We can hybridize the compostition function with an interpreter to evaluate combinators, compose non-combinator functions, and put type variables on the stack.  For combinators like `branch` that can have more than one stack effect we have to \"split universes\" again and return both."
3488    ]
3489   },
3490   {
3491    "cell_type": "markdown",
3492    "metadata": {},
3493    "source": [
3494     "#### Joy Types for Functions\n",
3495     "We need a type variable for Joy functions that can go in our expressions and be used by the hybrid inferencer/interpreter.  They have to store a name and a list of stack effects."
3496    ]
3497   },
3498   {
3499    "cell_type": "code",
3500    "execution_count": 107,
3501    "metadata": {},
3502    "outputs": [],
3503    "source": [
3504     "class FunctionJoyType(AnyJoyType):\n",
3505     "\n",
3506     "    def __init__(self, name, sec, number):\n",
3507     "        self.name = name\n",
3508     "        self.stack_effects = sec\n",
3509     "        self.number = number\n",
3510     "\n",
3511     "    def __add__(self, other):\n",
3512     "        return self\n",
3513     "    __radd__ = __add__\n",
3514     "\n",
3515     "    def __repr__(self):\n",
3516     "        return self.name"
3517    ]
3518   },
3519   {
3520    "cell_type": "markdown",
3521    "metadata": {},
3522    "source": [
3523     "#### Specialized for Simple Functions and Combinators\n",
3524     "For non-combinator functions the stack effects list contains stack effect comments (represented by pairs of cons-lists as described above.)"
3525    ]
3526   },
3527   {
3528    "cell_type": "code",
3529    "execution_count": 108,
3530    "metadata": {},
3531    "outputs": [],
3532    "source": [
3533     "class SymbolJoyType(FunctionJoyType):\n",
3534     "    prefix = 'F'"
3535    ]
3536   },
3537   {
3538    "cell_type": "markdown",
3539    "metadata": {},
3540    "source": [
3541     "For combinators the list contains Python functions. "
3542    ]
3543   },
3544   {
3545    "cell_type": "code",
3546    "execution_count": 109,
3547    "metadata": {},
3548    "outputs": [],
3549    "source": [
3550     "class CombinatorJoyType(FunctionJoyType):\n",
3551     "\n",
3552     "    prefix = 'C'\n",
3553     "\n",
3554     "    def __init__(self, name, sec, number, expect=None):\n",
3555     "        super(CombinatorJoyType, self).__init__(name, sec, number)\n",
3556     "        self.expect = expect\n",
3557     "\n",
3558     "    def enter_guard(self, f):\n",
3559     "        if self.expect is None:\n",
3560     "            return f\n",
3561     "        g = self.expect, self.expect\n",
3562     "        new_f = list(compose(f, g, ()))\n",
3563     "        assert len(new_f) == 1, repr(new_f)\n",
3564     "        return new_f[0][1]"
3565    ]
3566   },
3567   {
3568    "cell_type": "markdown",
3569    "metadata": {},
3570    "source": [
3571     "For simple combinators that have only one effect (like ``dip``) you only need one function and it can be the combinator itself."
3572    ]
3573   },
3574   {
3575    "cell_type": "code",
3576    "execution_count": 110,
3577    "metadata": {},
3578    "outputs": [],
3579    "source": [
3580     "import joy.library\n",
3581     "\n",
3582     "dip = CombinatorJoyType('dip', [joy.library.dip], 23)"
3583    ]
3584   },
3585   {
3586    "cell_type": "markdown",
3587    "metadata": {},
3588    "source": [
3589     "For combinators that can have more than one effect (like ``branch``) you have to write functions that each implement the action of one of the effects."
3590    ]
3591   },
3592   {
3593    "cell_type": "code",
3594    "execution_count": 111,
3595    "metadata": {},
3596    "outputs": [],
3597    "source": [
3598     "def branch_true(stack, expression, dictionary):\n",
3599     "    (then, (else_, (flag, stack))) = stack\n",
3600     "    return stack, concat(then, expression), dictionary\n",
3601     "\n",
3602     "def branch_false(stack, expression, dictionary):\n",
3603     "    (then, (else_, (flag, stack))) = stack\n",
3604     "    return stack, concat(else_, expression), dictionary\n",
3605     "\n",
3606     "branch = CombinatorJoyType('branch', [branch_true, branch_false], 100)"
3607    ]
3608   },
3609   {
3610    "cell_type": "markdown",
3611    "metadata": {},
3612    "source": [
3613     "You can also provide an optional stack effect, input-side only, that will then be used as an identity function (that accepts and returns stacks that match the \"guard\" stack effect) which will be used to guard against type mismatches going into the evaluation of the combinator."
3614    ]
3615   },
3616   {
3617    "cell_type": "markdown",
3618    "metadata": {},
3619    "source": [
3620     "#### `infer()`\n",
3621     "With those in place, we can define a function that accepts a sequence of Joy type variables, including ones representing functions (not just values), and attempts to grind out all the possible stack effects of that expression.\n",
3622     "\n",
3623     "One tricky thing is that type variables *in the expression* have to be updated along with the stack effects after doing unification or we risk losing useful information.  This was a straightforward, if awkward, modification to the call structure of `meta_compose()` et. al."
3624    ]
3625   },
3626   {
3627    "cell_type": "code",
3628    "execution_count": 112,
3629    "metadata": {},
3630    "outputs": [],
3631    "source": [
3632     "ID = S[0], S[0]  # Identity function.\n",
3633     "\n",
3634     "\n",
3635     "def infer(*expression):\n",
3636     "    return sorted(set(_infer(list_to_stack(expression))))\n",
3637     "\n",
3638     "\n",
3639     "def _infer(e, F=ID):\n",
3640     "    _log_it(e, F)\n",
3641     "    if not e:\n",
3642     "        return [F]\n",
3643     "\n",
3644     "    n, e = e\n",
3645     "\n",
3646     "    if isinstance(n, SymbolJoyType):\n",
3647     "        eFG = meta_compose([F], n.stack_effects, e)\n",
3648     "        res = flatten(_infer(e, Fn) for e, Fn in eFG)\n",
3649     "\n",
3650     "    elif isinstance(n, CombinatorJoyType):\n",
3651     "        fi, fo = n.enter_guard(F)\n",
3652     "        res = flatten(_interpret(f, fi, fo, e) for f in n.stack_effects)\n",
3653     "\n",
3654     "    elif isinstance(n, Symbol):\n",
3655     "        assert n not in FUNCTIONS, repr(n)\n",
3656     "        func = joy.library._dictionary[n]\n",
3657     "        res = _interpret(func, F[0], F[1], e)\n",
3658     "\n",
3659     "    else:\n",
3660     "        fi, fo = F\n",
3661     "        res = _infer(e, (fi, (n, fo)))\n",
3662     "\n",
3663     "    return res\n",
3664     "\n",
3665     "\n",
3666     "def _interpret(f, fi, fo, e):\n",
3667     "    new_fo, ee, _ = f(fo, e, {})\n",
3668     "    ee = update(FUNCTIONS, ee)  # Fix Symbols.\n",
3669     "    new_F = fi, new_fo\n",
3670     "    return _infer(ee, new_F)\n",
3671     "\n",
3672     "\n",
3673     "def _log_it(e, F):\n",
3674     "    _log.info(\n",
3675     "        u'%3i %s ∘ %s',\n",
3676     "        len(inspect_stack()),\n",
3677     "        doc_from_stack_effect(*F),\n",
3678     "        expression_to_string(e),\n",
3679     "        )"
3680    ]
3681   },
3682   {
3683    "cell_type": "markdown",
3684    "metadata": {},
3685    "source": [
3686     "#### Work in Progress\n",
3687     "And that brings us to current Work-In-Progress.  The mixed-mode inferencer/interpreter `infer()` function seems to work well.  There are details I should document, and the rest of the code in the `types` module (FIXME link to its docs here!) should be explained...  There is cruft to convert the definitions in `DEFS` to the new `SymbolJoyType` objects, and some combinators.  Here is an example of output from the current code :"
3688    ]
3689   },
3690   {
3691    "cell_type": "code",
3692    "execution_count": 1,
3693    "metadata": {
3694     "scrolled": true
3695    },
3696    "outputs": [
3697     {
3698      "ename": "ZeroDivisionError",
3699      "evalue": "integer division or modulo by zero",
3700      "output_type": "error",
3701      "traceback": [
3702       "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
3703       "\u001b[0;31mZeroDivisionError\u001b[0m                         Traceback (most recent call last)",
3704       "\u001b[0;32m<ipython-input-1-9a9d60354c35>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0;36m1\u001b[0m\u001b[0;34m/\u001b[0m\u001b[0;36m0\u001b[0m  \u001b[0;31m# (Don't try to run this cell!  It's not going to work.  This is \"read only\" code heh..)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      2\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      3\u001b[0m \u001b[0mlogging\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbasicConfig\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mformat\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;34m'%(message)s'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mstream\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0msys\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mstdout\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mlevel\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mlogging\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mINFO\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m \u001b[0mglobals\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mupdate\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mFUNCTIONS\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
3705       "\u001b[0;31mZeroDivisionError\u001b[0m: integer division or modulo by zero"
3706      ]
3707     }
3708    ],
3709    "source": [
3710     "1/0  # (Don't try to run this cell!  It's not going to work.  This is \"read only\" code heh..)\n",
3711     "\n",
3712     "logging.basicConfig(format='%(message)s', stream=sys.stdout, level=logging.INFO)\n",
3713     "\n",
3714     "globals().update(FUNCTIONS)\n",
3715     "\n",
3716     "h = infer((pred, s2), (mul, s3), (div, s4), (nullary, (bool, s5)), dipd, branch)\n",
3717     "\n",
3718     "print '-' * 40\n",
3719     "\n",
3720     "for fi, fo in h:\n",
3721     "    print doc_from_stack_effect(fi, fo)"
3722    ]
3723   },
3724   {
3725    "cell_type": "markdown",
3726    "metadata": {},
3727    "source": [
3728     "The numbers at the start of the lines are the current depth of the Python call stack.  They're followed by the current computed stack effect (initialized to `ID`) then the pending expression (the inference of the stack effect of which is the whole object of the current example.)\n",
3729     "\n",
3730     "In this example we are implementing (and inferring) `ifte` as `[nullary bool] dipd branch` which shows off a lot of the current implementation in action.\n",
3731     "\n",
3732     "      7 (--) ∘ [pred] [mul] [div] [nullary bool] dipd branch\n",
3733     "      8 (-- [pred ...2]) ∘ [mul] [div] [nullary bool] dipd branch\n",
3734     "      9 (-- [pred ...2] [mul ...3]) ∘ [div] [nullary bool] dipd branch\n",
3735     "     10 (-- [pred ...2] [mul ...3] [div ...4]) ∘ [nullary bool] dipd branch\n",
3736     "     11 (-- [pred ...2] [mul ...3] [div ...4] [nullary bool ...5]) ∘ dipd branch\n",
3737     "     15 (-- [pred ...5]) ∘ nullary bool [mul] [div] branch\n",
3738     "     19 (-- [pred ...2]) ∘ [stack] dinfrirst bool [mul] [div] branch\n",
3739     "     20 (-- [pred ...2] [stack ]) ∘ dinfrirst bool [mul] [div] branch\n",
3740     "     22 (-- [pred ...2] [stack ]) ∘ dip infra first bool [mul] [div] branch\n",
3741     "     26 (--) ∘ stack [pred] infra first bool [mul] [div] branch\n",
3742     "     29 (... -- ... [...]) ∘ [pred] infra first bool [mul] [div] branch\n",
3743     "     30 (... -- ... [...] [pred ...1]) ∘ infra first bool [mul] [div] branch\n",
3744     "     34 (--) ∘ pred s1 swaack first bool [mul] [div] branch\n",
3745     "     37 (n1 -- n2) ∘ [n1] swaack first bool [mul] [div] branch\n",
3746     "     38 (... n1 -- ... n2 [n1 ...]) ∘ swaack first bool [mul] [div] branch\n",
3747     "     41 (... n1 -- ... n1 [n2 ...]) ∘ first bool [mul] [div] branch\n",
3748     "     44 (n1 -- n1 n2) ∘ bool [mul] [div] branch\n",
3749     "     47 (n1 -- n1 b1) ∘ [mul] [div] branch\n",
3750     "     48 (n1 -- n1 b1 [mul ...1]) ∘ [div] branch\n",
3751     "     49 (n1 -- n1 b1 [mul ...1] [div ...2]) ∘ branch\n",
3752     "     53 (n1 -- n1) ∘ div\n",
3753     "     56 (f2 f1 -- f3) ∘ \n",
3754     "     56 (i1 f1 -- f2) ∘ \n",
3755     "     56 (f1 i1 -- f2) ∘ \n",
3756     "     56 (i2 i1 -- f1) ∘ \n",
3757     "     53 (n1 -- n1) ∘ mul\n",
3758     "     56 (f2 f1 -- f3) ∘ \n",
3759     "     56 (i1 f1 -- f2) ∘ \n",
3760     "     56 (f1 i1 -- f2) ∘ \n",
3761     "     56 (i2 i1 -- i3) ∘ \n",
3762     "    ----------------------------------------\n",
3763     "    (f2 f1 -- f3)\n",
3764     "    (i1 f1 -- f2)\n",
3765     "    (f1 i1 -- f2)\n",
3766     "    (i2 i1 -- f1)\n",
3767     "    (i2 i1 -- i3)"
3768    ]
3769   },
3770   {
3771    "cell_type": "markdown",
3772    "metadata": {},
3773    "source": [
3774     "## Conclusion\n",
3775     "We built a simple type inferencer, and a kind of crude \"compiler\" for a subset of Joy functions.  Then we built a more powerful inferencer that actually does some evaluation and explores branching code paths"
3776    ]
3777   },
3778   {
3779    "cell_type": "markdown",
3780    "metadata": {},
3781    "source": [
3782     "Work remains to be done:\n",
3783     "\n",
3784     "- the rest of the library has to be covered\n",
3785     "- figure out how to deal with `loop` and `genrec`, etc..\n",
3786     "- extend the types to check values (see the appendix)\n",
3787     "- other kinds of \"higher order\" type variables, OR, AND, etc..\n",
3788     "- maybe rewrite in Prolog for great good?\n",
3789     "- definitions\n",
3790     "  - don't permit composition of functions that don't compose\n",
3791     "  - auto-compile compilable functions\n",
3792     "- Compiling more than just the Yin functions.\n",
3793     "- getting better visibility (than Python debugger.)\n",
3794     "- DOOOOCS!!!!  Lots of docs!\n",
3795     "  - docstrings all around\n",
3796     "  - improve this notebook (it kinda falls apart at the end narratively.  I went off and just started writing code to see if it would work.  It does, but now I have to come back and describe here what I did."
3797    ]
3798   },
3799   {
3800    "cell_type": "markdown",
3801    "metadata": {},
3802    "source": [
3803     "## Appendix: Joy in the Logical Paradigm\n",
3804     "\n",
3805     "For *type checking* 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`.  If you do that you can take advantage of the *logical relational* nature of the stack effect comments to \"compute in reverse\" as it were.  There's a working demo of this at the end of the `types` module.  But if you're interested in all that you should just use Prolog!\n",
3806     "\n",
3807     "Anyhow, type *checking* is a few easy steps away."
3808    ]
3809   },
3810   {
3811    "cell_type": "code",
3812    "execution_count": null,
3813    "metadata": {},
3814    "outputs": [],
3815    "source": [
3816     "def _ge(self, other):\n",
3817     "    return (issubclass(other.__class__, self.__class__)\n",
3818     "            or hasattr(self, 'accept')\n",
3819     "            and isinstance(other, self.accept))\n",
3820     "\n",
3821     "AnyJoyType.__ge__ = _ge\n",
3822     "AnyJoyType.accept = tuple, int, float, long, str, unicode, bool, Symbol\n",
3823     "StackJoyType.accept = tuple"
3824    ]
3825   }
3826  ],
3827  "metadata": {
3828   "kernelspec": {
3829    "display_name": "Python 2",
3830    "language": "python",
3831    "name": "python2"
3832   },
3833   "language_info": {
3834    "codemirror_mode": {
3835     "name": "ipython",
3836     "version": 2
3837    },
3838    "file_extension": ".py",
3839    "mimetype": "text/x-python",
3840    "name": "python",
3841    "nbconvert_exporter": "python",
3842    "pygments_lexer": "ipython2",
3843    "version": "2.7.12"
3844   }
3845  },
3846  "nbformat": 4,
3847  "nbformat_minor": 2
3848 }