docs/Compiling_Joy.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "code",
   5    "execution_count": 1,
   6    "metadata": {},
   7    "outputs": [],
   8    "source": [
   9     "from notebook_preamble import D, J, V, define"
  10    ]
  11   },
  12   {
  13    "cell_type": "markdown",
  14    "metadata": {},
  15    "source": [
  16     "# Compiling Joy\n",
  17     "\n",
  18     "Given a Joy program like:\n",
  19     "\n",
  20     "    sqr == dup mul"
  21    ]
  22   },
  23   {
  24    "cell_type": "code",
  25    "execution_count": 2,
  26    "metadata": {},
  27    "outputs": [
  28     {
  29      "name": "stdout",
  30      "output_type": "stream",
  31      "text": [
  32       "      • 23 sqr\n",
  33       "   23 • sqr\n",
  34       "   23 • dup mul\n",
  35       "23 23 • mul\n",
  36       "  529 • \n"
  37      ]
  38     }
  39    ],
  40    "source": [
  41     "V('23 sqr')"
  42    ]
  43   },
  44   {
  45    "cell_type": "markdown",
  46    "metadata": {},
  47    "source": [
  48     "How would we go about compiling this code (to Python for now)?\n",
  49     "\n",
  50     "## Naive Call Chaining\n",
  51     "The simplest thing would be to compose the functions from the library:"
  52    ]
  53   },
  54   {
  55    "cell_type": "code",
  56    "execution_count": 3,
  57    "metadata": {},
  58    "outputs": [],
  59    "source": [
  60     "dup, mul = D['dup'], D['mul']"
  61    ]
  62   },
  63   {
  64    "cell_type": "code",
  65    "execution_count": 4,
  66    "metadata": {},
  67    "outputs": [],
  68    "source": [
  69     "def sqr(stack, expression, dictionary):\n",
  70     "    return mul(*dup(stack, expression, dictionary))"
  71    ]
  72   },
  73   {
  74    "cell_type": "code",
  75    "execution_count": 5,
  76    "metadata": {},
  77    "outputs": [],
  78    "source": [
  79     "old_sqr = D['sqr']\n",
  80     "D['sqr'] = sqr"
  81    ]
  82   },
  83   {
  84    "cell_type": "code",
  85    "execution_count": 6,
  86    "metadata": {},
  87    "outputs": [
  88     {
  89      "name": "stdout",
  90      "output_type": "stream",
  91      "text": [
  92       "    • 23 sqr\n",
  93       " 23 • sqr\n",
  94       "529 • \n"
  95      ]
  96     }
  97    ],
  98    "source": [
  99     "V('23 sqr')"
 100    ]
 101   },
 102   {
 103    "cell_type": "markdown",
 104    "metadata": {},
 105    "source": [
 106     "It's simple to write a function to emit this kind of crude \"compiled\" code."
 107    ]
 108   },
 109   {
 110    "cell_type": "code",
 111    "execution_count": 7,
 112    "metadata": {},
 113    "outputs": [],
 114    "source": [
 115     "def compile_joy(name, expression):\n",
 116     "    term, expression = expression\n",
 117     "    code = term +'(stack, expression, dictionary)'\n",
 118     "    format_ = '%s(*%s)'\n",
 119     "    while expression:\n",
 120     "        term, expression = expression\n",
 121     "        code = format_ % (term, code)\n",
 122     "    return '''\\\n",
 123     "def %s(stack, expression, dictionary):\n",
 124     "    return %s\n",
 125     "''' % (name, code)\n",
 126     "\n",
 127     "\n",
 128     "def compile_joy_definition(defi):\n",
 129     "    return compile_joy(defi.name, defi.body)\n"
 130    ]
 131   },
 132   {
 133    "cell_type": "code",
 134    "execution_count": 10,
 135    "metadata": {},
 136    "outputs": [
 137     {
 138      "name": "stdout",
 139      "output_type": "stream",
 140      "text": [
 141       "def sqr(stack, expression, dictionary):\n",
 142       "    return mul(*dup(stack, expression, dictionary))\n",
 143       "\n"
 144      ]
 145     }
 146    ],
 147    "source": [
 148     "print(compile_joy_definition(old_sqr))"
 149    ]
 150   },
 151   {
 152    "cell_type": "markdown",
 153    "metadata": {},
 154    "source": [
 155     "But what about literals?\n",
 156     "\n",
 157     "    quoted == [unit] dip"
 158    ]
 159   },
 160   {
 161    "cell_type": "code",
 162    "execution_count": 11,
 163    "metadata": {},
 164    "outputs": [],
 165    "source": [
 166     "unit, dip = D['unit'], D['dip']"
 167    ]
 168   },
 169   {
 170    "cell_type": "code",
 171    "execution_count": 12,
 172    "metadata": {},
 173    "outputs": [],
 174    "source": [
 175     "# print compile_joy_definition(D['quoted'])\n",
 176     "# raises\n",
 177     "# TypeError: can only concatenate tuple (not \"str\") to tuple"
 178    ]
 179   },
 180   {
 181    "cell_type": "markdown",
 182    "metadata": {},
 183    "source": [
 184     "For a program like `foo == bar baz 23 99 baq lerp barp` we would want something like:"
 185    ]
 186   },
 187   {
 188    "cell_type": "code",
 189    "execution_count": 13,
 190    "metadata": {},
 191    "outputs": [],
 192    "source": [
 193     "def foo(stack, expression, dictionary):\n",
 194     "    stack, expression, dictionary = baz(*bar(stack, expression, dictionary))\n",
 195     "    return barp(*lerp(*baq((99, (23, stack)), expression, dictionary)))"
 196    ]
 197   },
 198   {
 199    "cell_type": "markdown",
 200    "metadata": {},
 201    "source": [
 202     "You have to have a little discontinuity when going from a symbol to a literal, because you have to pick out the stack from the arguments to push the literal(s) onto it before you continue chaining function calls."
 203    ]
 204   },
 205   {
 206    "cell_type": "markdown",
 207    "metadata": {},
 208    "source": [
 209     "## Compiling Yin Functions\n",
 210     "Call-chaining results in code that does too much work.  For functions that operate on stacks and only rearrange values, what I like to call \"Yin Functions\", we can do better.\n",
 211     "\n",
 212     "We can infer the stack effects of these functions (or \"expressions\" or \"programs\") automatically, and the stack effects completely define the semantics of the functions, so we can directly write out a two-line Python function for them.  This is already implemented in the `joy.utils.types.compile_()` function."
 213    ]
 214   },
 215   {
 216    "cell_type": "code",
 217    "execution_count": 14,
 218    "metadata": {},
 219    "outputs": [
 220     {
 221      "ename": "ModuleNotFoundError",
 222      "evalue": "No module named 'joy.utils.types'",
 223      "output_type": "error",
 224      "traceback": [
 225       "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
 226       "\u001b[0;31mModuleNotFoundError\u001b[0m                       Traceback (most recent call last)",
 227       "\u001b[0;32m<ipython-input-14-d5ef3c7560be>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0;32mfrom\u001b[0m \u001b[0mjoy\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mutils\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtypes\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mcompile_\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdoc_from_stack_effect\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0minfer_string\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      2\u001b[0m \u001b[0;32mfrom\u001b[0m \u001b[0mjoy\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mlibrary\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mSimpleFunctionWrapper\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
 228       "\u001b[0;31mModuleNotFoundError\u001b[0m: No module named 'joy.utils.types'"
 229      ]
 230     }
 231    ],
 232    "source": [
 233     "from joy.utils.types import compile_, doc_from_stack_effect, infer_string\n",
 234     "from joy.library import SimpleFunctionWrapper"
 235    ]
 236   },
 237   {
 238    "cell_type": "code",
 239    "execution_count": null,
 240    "metadata": {},
 241    "outputs": [],
 242    "source": [
 243     "stack_effects = infer_string('tuck over dup')"
 244    ]
 245   },
 246   {
 247    "cell_type": "markdown",
 248    "metadata": {},
 249    "source": [
 250     "Yin functions have only a single stack effect, they do not branch or loop."
 251    ]
 252   },
 253   {
 254    "cell_type": "code",
 255    "execution_count": null,
 256    "metadata": {},
 257    "outputs": [],
 258    "source": [
 259     "for fi, fo in stack_effects:\n",
 260     "    print doc_from_stack_effect(fi, fo)"
 261    ]
 262   },
 263   {
 264    "cell_type": "code",
 265    "execution_count": null,
 266    "metadata": {},
 267    "outputs": [],
 268    "source": [
 269     "source = compile_('foo', stack_effects[0])"
 270    ]
 271   },
 272   {
 273    "cell_type": "markdown",
 274    "metadata": {},
 275    "source": [
 276     "All Yin functions can be described in Python as a tuple-unpacking (or \"-destructuring\") of the stack datastructure followed by building up the new stack structure."
 277    ]
 278   },
 279   {
 280    "cell_type": "code",
 281    "execution_count": null,
 282    "metadata": {},
 283    "outputs": [],
 284    "source": [
 285     "print source"
 286    ]
 287   },
 288   {
 289    "cell_type": "code",
 290    "execution_count": 9,
 291    "metadata": {},
 292    "outputs": [
 293     {
 294      "ename": "SyntaxError",
 295      "evalue": "invalid syntax (<ipython-input-9-1a7e90bf2d7b>, line 1)",
 296      "output_type": "error",
 297      "traceback": [
 298       "\u001b[0;36m  File \u001b[0;32m\"<ipython-input-9-1a7e90bf2d7b>\"\u001b[0;36m, line \u001b[0;32m1\u001b[0m\n\u001b[0;31m    exec compile(source, '__main__', 'single')\u001b[0m\n\u001b[0m         ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m invalid syntax\n"
 299      ]
 300     }
 301    ],
 302    "source": [
 303     "exec compile(source, '__main__', 'single')\n",
 304     "\n",
 305     "D['foo'] = SimpleFunctionWrapper(foo)"
 306    ]
 307   },
 308   {
 309    "cell_type": "code",
 310    "execution_count": null,
 311    "metadata": {},
 312    "outputs": [],
 313    "source": [
 314     "V('23 18 foo')"
 315    ]
 316   },
 317   {
 318    "cell_type": "markdown",
 319    "metadata": {},
 320    "source": [
 321     "## Compiling from Stack Effects\n",
 322     "\n",
 323     "There are times when you're deriving a Joy program when you have a stack effect for a Yin function and you need to define it.  For example, in the Ordered Binary Trees notebook there is a point where we must derive a function `Ee`:\n",
 324     "\n",
 325     "       [key old_value left right] new_value key [Tree-add] Ee\n",
 326     "    ------------------------------------------------------------\n",
 327     "       [key new_value left right]\n",
 328     "\n",
 329     "While it is not hard to come up with this function manually, there is no necessity.  This function can be defined (in Python) directly from its stack effect:\n",
 330     "\n",
 331     "       [a b c d] e a [f] Ee\n",
 332     "    --------------------------\n",
 333     "       [a e c d]\n",
 334     "\n",
 335     "(I haven't yet implemented a simple interface for this yet.  What follow is an exploration of how to do it.)"
 336    ]
 337   },
 338   {
 339    "cell_type": "code",
 340    "execution_count": null,
 341    "metadata": {},
 342    "outputs": [],
 343    "source": [
 344     "from joy.parser import text_to_expression"
 345    ]
 346   },
 347   {
 348    "cell_type": "code",
 349    "execution_count": null,
 350    "metadata": {},
 351    "outputs": [],
 352    "source": [
 353     "Ein = '[a b c d] e a [f]'  # The terms should be reversed here but I don't realize that until later.\n",
 354     "Eout = '[a e c d]'\n",
 355     "E = '[%s] [%s]' % (Ein, Eout)\n",
 356     "\n",
 357     "print E"
 358    ]
 359   },
 360   {
 361    "cell_type": "code",
 362    "execution_count": null,
 363    "metadata": {},
 364    "outputs": [],
 365    "source": [
 366     "(fi, (fo, _)) = text_to_expression(E)"
 367    ]
 368   },
 369   {
 370    "cell_type": "code",
 371    "execution_count": null,
 372    "metadata": {},
 373    "outputs": [],
 374    "source": [
 375     "fi, fo"
 376    ]
 377   },
 378   {
 379    "cell_type": "code",
 380    "execution_count": null,
 381    "metadata": {},
 382    "outputs": [],
 383    "source": [
 384     "Ein = '[a1 a2 a3 a4] a5 a6 a7'\n",
 385     "Eout = '[a1 a5 a3 a4]'\n",
 386     "E = '[%s] [%s]' % (Ein, Eout)\n",
 387     "\n",
 388     "print E"
 389    ]
 390   },
 391   {
 392    "cell_type": "code",
 393    "execution_count": null,
 394    "metadata": {},
 395    "outputs": [],
 396    "source": [
 397     "(fi, (fo, _)) = text_to_expression(E)"
 398    ]
 399   },
 400   {
 401    "cell_type": "code",
 402    "execution_count": null,
 403    "metadata": {},
 404    "outputs": [],
 405    "source": [
 406     "fi, fo"
 407    ]
 408   },
 409   {
 410    "cell_type": "code",
 411    "execution_count": null,
 412    "metadata": {},
 413    "outputs": [],
 414    "source": [
 415     "def type_vars():\n",
 416     "    from joy.library import a1, a2, a3, a4, a5, a6, a7, s0, s1\n",
 417     "    return locals()\n",
 418     "\n",
 419     "tv = type_vars()\n",
 420     "tv"
 421    ]
 422   },
 423   {
 424    "cell_type": "code",
 425    "execution_count": null,
 426    "metadata": {},
 427    "outputs": [],
 428    "source": [
 429     "from joy.utils.types import reify"
 430    ]
 431   },
 432   {
 433    "cell_type": "code",
 434    "execution_count": null,
 435    "metadata": {},
 436    "outputs": [],
 437    "source": [
 438     "stack_effect = reify(tv, (fi, fo))\n",
 439     "print doc_from_stack_effect(*stack_effect)"
 440    ]
 441   },
 442   {
 443    "cell_type": "code",
 444    "execution_count": null,
 445    "metadata": {},
 446    "outputs": [],
 447    "source": [
 448     "print stack_effect"
 449    ]
 450   },
 451   {
 452    "cell_type": "markdown",
 453    "metadata": {},
 454    "source": [
 455     "Almost, but what we really want is something like this:"
 456    ]
 457   },
 458   {
 459    "cell_type": "code",
 460    "execution_count": null,
 461    "metadata": {},
 462    "outputs": [],
 463    "source": [
 464     "stack_effect = eval('(((a1, (a2, (a3, (a4, s1)))), (a5, (a6, (a7, s0)))), ((a1, (a5, (a3, (a4, s1)))), s0))', tv)"
 465    ]
 466   },
 467   {
 468    "cell_type": "markdown",
 469    "metadata": {},
 470    "source": [
 471     "Note the change of `()` to `JoyStackType` type variables."
 472    ]
 473   },
 474   {
 475    "cell_type": "code",
 476    "execution_count": null,
 477    "metadata": {},
 478    "outputs": [],
 479    "source": [
 480     "print doc_from_stack_effect(*stack_effect)"
 481    ]
 482   },
 483   {
 484    "cell_type": "markdown",
 485    "metadata": {},
 486    "source": [
 487     "Now we can omit `a3` and `a4` if we like:"
 488    ]
 489   },
 490   {
 491    "cell_type": "code",
 492    "execution_count": null,
 493    "metadata": {},
 494    "outputs": [],
 495    "source": [
 496     "stack_effect = eval('(((a1, (a2, s1)), (a5, (a6, (a7, s0)))), ((a1, (a5, s1)), s0))', tv)"
 497    ]
 498   },
 499   {
 500    "cell_type": "markdown",
 501    "metadata": {},
 502    "source": [
 503     "The `right` and `left` parts of the ordered binary tree node are subsumed in the tail of the node's stack/list."
 504    ]
 505   },
 506   {
 507    "cell_type": "code",
 508    "execution_count": null,
 509    "metadata": {},
 510    "outputs": [],
 511    "source": [
 512     "print doc_from_stack_effect(*stack_effect)"
 513    ]
 514   },
 515   {
 516    "cell_type": "code",
 517    "execution_count": null,
 518    "metadata": {},
 519    "outputs": [],
 520    "source": [
 521     "source = compile_('Ee', stack_effect)\n",
 522     "print source"
 523    ]
 524   },
 525   {
 526    "cell_type": "markdown",
 527    "metadata": {},
 528    "source": [
 529     "Oops!  The input stack is backwards..."
 530    ]
 531   },
 532   {
 533    "cell_type": "code",
 534    "execution_count": null,
 535    "metadata": {},
 536    "outputs": [],
 537    "source": [
 538     "stack_effect = eval('((a7, (a6, (a5, ((a1, (a2, s1)), s0)))), ((a1, (a5, s1)), s0))', tv)"
 539    ]
 540   },
 541   {
 542    "cell_type": "code",
 543    "execution_count": null,
 544    "metadata": {},
 545    "outputs": [],
 546    "source": [
 547     "print doc_from_stack_effect(*stack_effect)"
 548    ]
 549   },
 550   {
 551    "cell_type": "code",
 552    "execution_count": null,
 553    "metadata": {},
 554    "outputs": [],
 555    "source": [
 556     "source = compile_('Ee', stack_effect)\n",
 557     "print source"
 558    ]
 559   },
 560   {
 561    "cell_type": "markdown",
 562    "metadata": {},
 563    "source": [
 564     "Compare:\n",
 565     "\n",
 566     "       [key old_value left right] new_value key [Tree-add] Ee\n",
 567     "    ------------------------------------------------------------\n",
 568     "       [key new_value left right]\n"
 569    ]
 570   },
 571   {
 572    "cell_type": "code",
 573    "execution_count": null,
 574    "metadata": {},
 575    "outputs": [],
 576    "source": [
 577     "eval(compile(source, '__main__', 'single'))\n",
 578     "D['Ee'] = SimpleFunctionWrapper(Ee)"
 579    ]
 580   },
 581   {
 582    "cell_type": "code",
 583    "execution_count": null,
 584    "metadata": {
 585     "scrolled": true
 586    },
 587    "outputs": [],
 588    "source": [
 589     "V('[a b c d] 1 2 [f] Ee')"
 590    ]
 591   },
 592   {
 593    "cell_type": "code",
 594    "execution_count": null,
 595    "metadata": {},
 596    "outputs": [],
 597    "source": []
 598   },
 599   {
 600    "cell_type": "markdown",
 601    "metadata": {},
 602    "source": [
 603     "## Working with Yang Functions\n",
 604     "\n",
 605     "Consider the compiled code of `dup`:"
 606    ]
 607   },
 608   {
 609    "cell_type": "code",
 610    "execution_count": null,
 611    "metadata": {},
 612    "outputs": [],
 613    "source": [
 614     "\n",
 615     "def dup(stack):\n",
 616     "    (a1, s23) = stack\n",
 617     "    return (a1, (a1, s23))\n",
 618     "\n"
 619    ]
 620   },
 621   {
 622    "cell_type": "markdown",
 623    "metadata": {},
 624    "source": [
 625     "To compile `sqr == dup mul` we can compute the stack effect:"
 626    ]
 627   },
 628   {
 629    "cell_type": "code",
 630    "execution_count": null,
 631    "metadata": {},
 632    "outputs": [],
 633    "source": [
 634     "stack_effects = infer_string('dup mul')\n",
 635     "for fi, fo in stack_effects:\n",
 636     "    print doc_from_stack_effect(fi, fo)"
 637    ]
 638   },
 639   {
 640    "cell_type": "markdown",
 641    "metadata": {},
 642    "source": [
 643     "Then we would want something like this:"
 644    ]
 645   },
 646   {
 647    "cell_type": "code",
 648    "execution_count": null,
 649    "metadata": {},
 650    "outputs": [],
 651    "source": [
 652     "\n",
 653     "def sqr(stack):\n",
 654     "    (n1, s23) = stack\n",
 655     "    n2 = mul(n1, n1)\n",
 656     "    return (n2, s23)\n",
 657     "\n"
 658    ]
 659   },
 660   {
 661    "cell_type": "code",
 662    "execution_count": null,
 663    "metadata": {},
 664    "outputs": [],
 665    "source": []
 666   },
 667   {
 668    "cell_type": "code",
 669    "execution_count": null,
 670    "metadata": {},
 671    "outputs": [],
 672    "source": []
 673   },
 674   {
 675    "cell_type": "markdown",
 676    "metadata": {},
 677    "source": [
 678     "How about..."
 679    ]
 680   },
 681   {
 682    "cell_type": "code",
 683    "execution_count": null,
 684    "metadata": {},
 685    "outputs": [],
 686    "source": [
 687     "stack_effects = infer_string('mul mul sub')\n",
 688     "for fi, fo in stack_effects:\n",
 689     "    print doc_from_stack_effect(fi, fo)"
 690    ]
 691   },
 692   {
 693    "cell_type": "code",
 694    "execution_count": null,
 695    "metadata": {},
 696    "outputs": [],
 697    "source": [
 698     "\n",
 699     "def foo(stack):\n",
 700     "    (n1, (n2, (n3, (n4, s23)))) = stack\n",
 701     "    n5 = mul(n1, n2)\n",
 702     "    n6 = mul(n5, n3)\n",
 703     "    n7 = sub(n6, n4)\n",
 704     "    return (n7, s23)\n",
 705     "\n",
 706     "\n",
 707     "# or\n",
 708     "\n",
 709     "def foo(stack):\n",
 710     "    (n1, (n2, (n3, (n4, s23)))) = stack\n",
 711     "    n5 = sub(mul(mul(n1, n2), n3), n4)\n",
 712     "    return (n5, s23)\n",
 713     "\n"
 714    ]
 715   },
 716   {
 717    "cell_type": "code",
 718    "execution_count": null,
 719    "metadata": {},
 720    "outputs": [],
 721    "source": []
 722   },
 723   {
 724    "cell_type": "code",
 725    "execution_count": null,
 726    "metadata": {},
 727    "outputs": [],
 728    "source": [
 729     "stack_effects = infer_string('tuck')\n",
 730     "for fi, fo in stack_effects:\n",
 731     "    print doc_from_stack_effect(fi, fo)"
 732    ]
 733   },
 734   {
 735    "cell_type": "code",
 736    "execution_count": null,
 737    "metadata": {},
 738    "outputs": [],
 739    "source": []
 740   },
 741   {
 742    "cell_type": "markdown",
 743    "metadata": {},
 744    "source": [
 745     "## Compiling Yin~Yang Functions"
 746    ]
 747   },
 748   {
 749    "cell_type": "markdown",
 750    "metadata": {},
 751    "source": [
 752     "First, we need a source of Python identifiers.  I'm going to reuse `Symbol` class for this."
 753    ]
 754   },
 755   {
 756    "cell_type": "code",
 757    "execution_count": null,
 758    "metadata": {},
 759    "outputs": [],
 760    "source": [
 761     "from joy.parser import Symbol"
 762    ]
 763   },
 764   {
 765    "cell_type": "code",
 766    "execution_count": null,
 767    "metadata": {},
 768    "outputs": [],
 769    "source": [
 770     "def _names():\n",
 771     "    n = 0\n",
 772     "    while True:\n",
 773     "        yield Symbol('a' + str(n))\n",
 774     "        n += 1\n",
 775     "\n",
 776     "names = _names().next"
 777    ]
 778   },
 779   {
 780    "cell_type": "markdown",
 781    "metadata": {},
 782    "source": [
 783     "Now we need an object that represents a Yang function that accepts two args and return one result (we'll implement other kinds a little later.)"
 784    ]
 785   },
 786   {
 787    "cell_type": "code",
 788    "execution_count": null,
 789    "metadata": {},
 790    "outputs": [],
 791    "source": [
 792     "class Foo(object):\n",
 793     "\n",
 794     "    def __init__(self, name):\n",
 795     "        self.name = name\n",
 796     "\n",
 797     "    def __call__(self, stack, expression, code):\n",
 798     "        in1, (in0, stack) = stack\n",
 799     "        out = names()\n",
 800     "        code.append(('call', out, self.name, (in0, in1)))\n",
 801     "        return (out, stack), expression, code"
 802    ]
 803   },
 804   {
 805    "cell_type": "markdown",
 806    "metadata": {},
 807    "source": [
 808     "A crude \"interpreter\" that translates expressions of args and Yin and Yang functions into a kind of simple dataflow graph."
 809    ]
 810   },
 811   {
 812    "cell_type": "code",
 813    "execution_count": null,
 814    "metadata": {},
 815    "outputs": [],
 816    "source": [
 817     "def I(stack, expression, code):\n",
 818     "    while expression:\n",
 819     "        term, expression = expression\n",
 820     "        if callable(term):\n",
 821     "            stack, expression, _ = term(stack, expression, code)\n",
 822     "        else:\n",
 823     "            stack = term, stack\n",
 824     "            code.append(('pop', term))\n",
 825     "\n",
 826     "    s = []\n",
 827     "    while stack:\n",
 828     "        term, stack = stack\n",
 829     "        s.insert(0, term)\n",
 830     "    if s:\n",
 831     "        code.append(('push',) + tuple(s))\n",
 832     "    return code"
 833    ]
 834   },
 835   {
 836    "cell_type": "markdown",
 837    "metadata": {},
 838    "source": [
 839     "Something to convert the graph into Python code."
 840    ]
 841   },
 842   {
 843    "cell_type": "code",
 844    "execution_count": null,
 845    "metadata": {},
 846    "outputs": [],
 847    "source": [
 848     "strtup = lambda a, b: '(%s, %s)' % (b, a)\n",
 849     "strstk = lambda rest: reduce(strtup, rest, 'stack')\n",
 850     "\n",
 851     "\n",
 852     "def code_gen(code):\n",
 853     "    coalesce_pops(code)\n",
 854     "    lines = []\n",
 855     "    for t in code:\n",
 856     "        tag, rest = t[0], t[1:]\n",
 857     "\n",
 858     "        if tag == 'pop':\n",
 859     "            lines.append(strstk(rest) + ' = stack')\n",
 860     "\n",
 861     "        elif tag == 'push':\n",
 862     "            lines.append('stack = ' + strstk(rest))\n",
 863     "\n",
 864     "        elif tag == 'call':\n",
 865     "            #out, name, in_ = rest\n",
 866     "            lines.append('%s = %s%s' % rest)\n",
 867     "\n",
 868     "        else:\n",
 869     "            raise ValueError(tag)\n",
 870     "\n",
 871     "    return '\\n'.join('    ' + line for line in lines)\n",
 872     "\n",
 873     "\n",
 874     "def coalesce_pops(code):\n",
 875     "    index = [i for i, t in enumerate(code) if t[0] == 'pop']\n",
 876     "    for start, end in yield_groups(index):\n",
 877     "        code[start:end] = \\\n",
 878     "            [tuple(['pop'] + [t for _, t in code[start:end][::-1]])]\n",
 879     "\n",
 880     "\n",
 881     "def yield_groups(index):\n",
 882     "    '''\n",
 883     "    Yield slice indices for each group of contiguous ints in the\n",
 884     "    index list.\n",
 885     "    '''\n",
 886     "    k = 0\n",
 887     "    for i, (a, b) in enumerate(zip(index, index[1:])):\n",
 888     "        if b - a > 1:\n",
 889     "            if k != i:\n",
 890     "                yield index[k], index[i] + 1\n",
 891     "            k = i + 1\n",
 892     "    if k < len(index):\n",
 893     "        yield index[k], index[-1] + 1\n",
 894     "\n",
 895     "\n",
 896     "def compile_yinyang(name, expression):\n",
 897     "    return '''\\\n",
 898     "def %s(stack):\n",
 899     "%s\n",
 900     "    return stack\n",
 901     "''' % (name, code_gen(I((), expression, [])))\n"
 902    ]
 903   },
 904   {
 905    "cell_type": "markdown",
 906    "metadata": {},
 907    "source": [
 908     "A few functions to try it with..."
 909    ]
 910   },
 911   {
 912    "cell_type": "code",
 913    "execution_count": null,
 914    "metadata": {},
 915    "outputs": [],
 916    "source": [
 917     "mul = Foo('mul')\n",
 918     "sub = Foo('sub')"
 919    ]
 920   },
 921   {
 922    "cell_type": "code",
 923    "execution_count": null,
 924    "metadata": {},
 925    "outputs": [],
 926    "source": [
 927     "def import_yin():\n",
 928     "    from joy.utils.generated_library import *\n",
 929     "    return locals()\n",
 930     "\n",
 931     "yin_dict = {name: SimpleFunctionWrapper(func) for name, func in import_yin().iteritems()}\n",
 932     "\n",
 933     "yin_dict\n",
 934     "\n",
 935     "dup = yin_dict['dup']\n",
 936     "\n",
 937     "#def dup(stack, expression, code):\n",
 938     "#    n, stack = stack\n",
 939     "#    return (n, (n, stack)), expression"
 940    ]
 941   },
 942   {
 943    "cell_type": "markdown",
 944    "metadata": {},
 945    "source": [
 946     "... and there we are."
 947    ]
 948   },
 949   {
 950    "cell_type": "code",
 951    "execution_count": null,
 952    "metadata": {},
 953    "outputs": [],
 954    "source": [
 955     "print compile_yinyang('mul_', (names(), (names(), (mul, ()))))"
 956    ]
 957   },
 958   {
 959    "cell_type": "code",
 960    "execution_count": null,
 961    "metadata": {},
 962    "outputs": [],
 963    "source": [
 964     "e = (names(), (dup, (mul, ())))\n",
 965     "print compile_yinyang('sqr', e)"
 966    ]
 967   },
 968   {
 969    "cell_type": "code",
 970    "execution_count": null,
 971    "metadata": {
 972     "scrolled": true
 973    },
 974    "outputs": [],
 975    "source": [
 976     "e = (names(), (dup, (names(), (sub, (mul, ())))))\n",
 977     "print compile_yinyang('foo', e)"
 978    ]
 979   },
 980   {
 981    "cell_type": "code",
 982    "execution_count": null,
 983    "metadata": {},
 984    "outputs": [],
 985    "source": [
 986     "e = (names(), (names(), (mul, (dup, (sub, (dup, ()))))))\n",
 987     "print compile_yinyang('bar', e)"
 988    ]
 989   },
 990   {
 991    "cell_type": "code",
 992    "execution_count": null,
 993    "metadata": {},
 994    "outputs": [],
 995    "source": [
 996     "e = (names(), (dup, (dup, (mul, (dup, (mul, (mul, ())))))))\n",
 997     "print compile_yinyang('to_the_fifth_power', e)"
 998    ]
 999   },
1000   {
1001    "cell_type": "code",
1002    "execution_count": null,
1003    "metadata": {},
1004    "outputs": [],
1005    "source": []
1006   },
1007   {
1008    "cell_type": "code",
1009    "execution_count": null,
1010    "metadata": {},
1011    "outputs": [],
1012    "source": []
1013   },
1014   {
1015    "cell_type": "code",
1016    "execution_count": null,
1017    "metadata": {},
1018    "outputs": [],
1019    "source": []
1020   },
1021   {
1022    "cell_type": "code",
1023    "execution_count": null,
1024    "metadata": {},
1025    "outputs": [],
1026    "source": []
1027   }
1028  ],
1029  "metadata": {
1030   "kernelspec": {
1031    "display_name": "Python 2",
1032    "language": "python",
1033    "name": "python2"
1034   },
1035   "language_info": {
1036    "codemirror_mode": {
1037     "name": "ipython",
1038     "version": 3
1039    },
1040    "file_extension": ".py",
1041    "mimetype": "text/x-python",
1042    "name": "python",
1043    "nbconvert_exporter": "python",
1044    "pygments_lexer": "ipython3",
1045    "version": "3.8.3"
1046   }
1047  },
1048  "nbformat": 4,
1049  "nbformat_minor": 2
1050 }