{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Symbolic Evaluation with SymPy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sympy\n",
    "\n",
    "from joy.joy import run\n",
    "from joy.library import UnaryBuiltinWrapper\n",
    "from joy.utils.pretty_print import TracePrinter\n",
    "from joy.utils.stack import list_to_stack\n",
    "\n",
    "from notebook_preamble import D, J, V, define"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "sympy.init_printing()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [SypPy Symbols](http://docs.sympy.org/latest/modules/core.html#module-sympy.core.symbol)\n",
    "\n",
    "The SymPy package provides a powerful and elegant [\"thunk\"](https://en.wikipedia.org/wiki/Thunk) object that can take the place of a numeric value in calculations and \"record\" the operations performed on it.\n",
    "\n",
    "We can create some of these objects and put them on the Joy stack:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "stack = list_to_stack(sympy.symbols('c a b'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we evaluate the `quadratic` program\n",
    "\n",
    "    over [[[neg] dupdip sqr 4] dipd * * - sqrt pm] dip 2 * [/] cons app2\n",
    "\n",
    "The [SypPy Symbols](http://docs.sympy.org/latest/modules/core.html#module-sympy.core.symbol) will become the symbolic expression of the math operations.  Unfortunately, the library `sqrt` function doesn't work with the SymPy objects:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "can't convert expression to float\n",
      "                                            b a c . over [[[neg] dupdip sqr 4] dipd * * - sqrt pm] dip 2 * [/] cons app2\n",
      "                                          b a c a . [[[neg] dupdip sqr 4] dipd * * - sqrt pm] dip 2 * [/] cons app2\n",
      "b a c a [[[neg] dupdip sqr 4] dipd * * - sqrt pm] . dip 2 * [/] cons app2\n",
      "                                            b a c . [[neg] dupdip sqr 4] dipd * * - sqrt pm a 2 * [/] cons app2\n",
      "                       b a c [[neg] dupdip sqr 4] . dipd * * - sqrt pm a 2 * [/] cons app2\n",
      "                                                b . [neg] dupdip sqr 4 a c * * - sqrt pm a 2 * [/] cons app2\n",
      "                                          b [neg] . dupdip sqr 4 a c * * - sqrt pm a 2 * [/] cons app2\n",
      "                                                b . neg b sqr 4 a c * * - sqrt pm a 2 * [/] cons app2\n",
      "                                               -b . b sqr 4 a c * * - sqrt pm a 2 * [/] cons app2\n",
      "                                             -b b . sqr 4 a c * * - sqrt pm a 2 * [/] cons app2\n",
      "                                             -b b . dup mul 4 a c * * - sqrt pm a 2 * [/] cons app2\n",
      "                                           -b b b . mul 4 a c * * - sqrt pm a 2 * [/] cons app2\n",
      "                                          -b b**2 . 4 a c * * - sqrt pm a 2 * [/] cons app2\n",
      "                                        -b b**2 4 . a c * * - sqrt pm a 2 * [/] cons app2\n",
      "                                      -b b**2 4 a . c * * - sqrt pm a 2 * [/] cons app2\n",
      "                                    -b b**2 4 a c . * * - sqrt pm a 2 * [/] cons app2\n",
      "                                    -b b**2 4 a*c . * - sqrt pm a 2 * [/] cons app2\n",
      "                                    -b b**2 4*a*c . - sqrt pm a 2 * [/] cons app2\n",
      "                                 -b -4*a*c + b**2 . sqrt pm a 2 * [/] cons app2\n"
     ]
    }
   ],
   "source": [
    "viewer = TracePrinter()\n",
    "try:\n",
    "    run('over [[[neg] dupdip sqr 4] dipd * * - sqrt pm] dip 2 * [/] cons app2', stack, D, viewer.viewer)\n",
    "except Exception, e:\n",
    "    print e\n",
    "viewer.print_()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can pick out that first symbolic expression obect from the Joy stack:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "S, E = viewer.history[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAGUAAAAWCAYAAADZylKgAAAABHNCSVQICAgIfAhkiAAAA3NJREFUaIHt2GuIVVUUB/CfpWU1wlRYTSFDEUHQ5IxCURBMI9EDouhDH3rYNYSgQII+9ADh4oeIpJoi+iAUlUUFlZEETQ0ZvSw1TaJIU5kgMppeGFFWNn1Y+zKn47l35p6544jcP2wOZ+291v6fu/Z67EsbbbQB7sVm7MMo1uO8GWXUhiEsE47owTp8j5NmktSRhtsxhltL6nfgAK6Go1pEqh5uFmTHsHya95pJLErPT0vqzxO++Lk1dOpjAX7Fb458p2zDH5hdUv+lZOPoljEqwCwMYzdWO7ydUhH8+kvqH4u/8ElJ/dXYi7NrgulKXyswIIrZ75NYfwOex04RWb+I7mRZA51+ccK+xX7xYUO4tizpkujBHJG6evEKfhLf/ZbGXdVDWIol2FUTTodTzsUDeBTvTWL9PDyDs/A+HserOBNP4e4CnUFsEI4fxsPpfTEunhr9prE4PbvxoYi6J7EVl+EddBboPYabcCm+nE6Cs7EFO3BcklU1Tl8dOK1A3iWi5quc/P5k72WcUGCru0nOFVNLX2uS/o/oy809m+buy8mfEHeUAfHttdFRkkNDrBKt3UUZWVX5mrIDP2Te+5L9zTimHMWDUDE1p2xRvx2+MM29kJOP1RnVog1GGigUjecyuhfgHzyYs1nV2CknYiU+FrXkQG6PrZm1a5NsSR1bE2GkwbcUjacnsDdH1LMRxZ1Xd7KzrhmSeUO78WcT+t9l7KwVhXplE/rni2J4KjbhRdGr/y1qylJsz6y/XDhuQxN7ZDHo4Pzei2tEXRvJzX02gb0eEbHrxYHMo5ZKv2mKZYvQafKnbzCjt10cgv4Cm6vS+jvS+9z0vq3F3CvKp6/lSfeuOvOPpPmrmjFa9rKTx37RcRRhkagFH4gasTHJF4hIGcK7OZ1O4+1w7ZY8Kz1PmTrdlqHWeRX9Z9WF2/C1yAaHFaqKa8r8JN8pcnMNJwtHjYk0Njcz93mSX1+wzznK3YgrykfKpqS7x/87wQ68LerjFc0abVWklMGo6OEHxG14WJyuK0XN+Ff079kadw9eF7XnFnwhoqpXRF7XIeJO/HY9Ip0eL+rPa+KGfx1Ox5148xBymjSq6ndf80UvPyruJB+J4t5n/BKWxyV4w3hDsFekhxtL8qsoFykLk94anCEuvPvSGCphr4022mijjTZajv8AHtTyPwIcKPQAAAAASUVORK5CYII=\n",
      "text/latex": [
       "$$- 4 a c + b^{2}$$"
      ],
      "text/plain": [
       "          2\n",
       "-4⋅a⋅c + b "
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q = S[0]\n",
    "q"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Python `math.sqrt()` function causes the \"can't convert expression to float\" exception but `sympy.sqrt()` does not:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAHoAAAAdCAYAAABlqHgGAAAABHNCSVQICAgIfAhkiAAABGhJREFUaIHt2muIVVUUwPGfpqU1ghVWFpMUJJVZPnpgUExK9AAthPrQQ8cQgoIIMnqANPghelBalIRgL3tCmSVBlmVU9lDTLHpoD6aIpKwMQ0pKpw/rDF6v597uOffMVeT84XDn7L3X2uucvfdaa+8zlJSU7D/0yyk3FFuKNKRk32Q6LtvbRpT0Pc9gyN42oqRx+ueQOTC5/izYlpI+JM9AT8TbBdtRsg/yMI7d20aUZCPPim7HD0UbUpKJ27AaW7EZS3FKPYGsAz0Wn+QyraRIOjAfZ4tQ+i+W47CiOrgDZxSlrARchx5c04SONuzA5FoNsq7o8VjThEFZuVq8hB7MbGG/rWRc8vtxEzqGiLH8vXlzOAaPFKGoQdrxh9jG7c8DvQ5/YUATOp5P9BxQq0Haiq61yieLoN8K+uEx/Ka1kysPnWIiduSQPQij8KmIs3m4F+eKk8odtRpVD+pkfJlSDpPwZk5jsnKDSDJmYFsD7a/A09goPMAWkZXOqCPTIVbCj9iOTViGS/ManYPRGCjc9hi8KCb3NrzufzJp3IdpYmy+qdewckBPFw9/gsjmKjlEzJa/G7G+SU7CXXgA7zTQfgiewPF4Fw9hMY7Do7glRWYeVojJtBz3J/fj7fnsfcn45HcEVgrPsBBrcT7eEh+Q0ngQV+E8fJGn85W4p6psquaywkYZIJK9DRiclHWpH6PbcFRK+XCxur+qKr8z0feCmMDVukZktLlTfte9IJH9VWxdK3kyqbs9RW6+2ENPFM/ee7Vl6fxm8aIrWYgjsijJyRzhOSZUlHXJn4xtwC8V92MT/avFeX0RdMo/0GvU3lqdldQ9m1LXU+PqytL5yEToxOS+P5Y0INddx4C066kq+TNFQlLtTbrUH+hDMRsfiti8o6qftRVtFyVlkxp4njS6ZXvGx+voGihyg27pGfeIRMdLOW3djbQONoqVMEW4vQn4qAFd38oWw3+qsmNR0vfsDDpOFUnLkViF58Re8h8Ro6dhfUX7C8RkWJGhj0rm2TNmjsElIk/orqqrd4o4WniVpdIz7t4Q8n1mKzNwt4jVvX+P6svOxMtrdJXMq5BbLyZXR4rOOUn765P7Qcn9uoJt75TPdc9M5G6qUT83qb84r2GV1Nqkv4xZIi6fjM+L6KwO20UekMY4EVvfE57mg6S8XazoZfb8bDrUrq1V74lT779NtSLXaITejDvtfHo4rsXXwmP1Gf3xs8hQ5/ZlRw3QJT1GD0vKN4p418vhYvB7hAsfVFH3WVJ+eUo/I9U5WapDp3wrelUi953ds/82vCFyjQtz2JNKrRW9U8SOWUV2VjCbxT5zosghlouVcJGIwTvF/rIyb7gVr4hYPl14qqEizrYn8q1ggIjR63CwiOVLxEnZVByNG/FaK4yZIhKXZs5gi6BL7ax7mNhvbhZ75vdFAjbWrsOHas7Bq3YlbZuEe7wyp32dsq/o0xKZBeIbwmKxL94qvFEWXU0zWHzgLikpKSkpKWk9/wEOzhV2ng+cdgAAAABJRU5ErkJggg==\n",
      "text/latex": [
       "$$\\sqrt{- 4 a c + b^{2}}$$"
      ],
      "text/plain": [
       "   _____________\n",
       "  ╱           2 \n",
       "╲╱  -4⋅a⋅c + b  "
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sympy.sqrt(q)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Use `sympy.sqrt`\n",
    "This is easy to fix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "D['sqrt'] = UnaryBuiltinWrapper(sympy.sqrt)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now it works just fine."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "(root1, (root2, _)) = run('over [[[neg] dupdip sqr 4] dipd * * - sqrt pm] dip 2 * [/] cons app2', stack, D)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAOAAAAAgCAYAAAALxXRVAAAABHNCSVQICAgIfAhkiAAAB4pJREFUeJztnHuwVVMcxz9ut5e6KVQa0sTIs8hFisztehSV58iMxEGDkVGDNBicaQZNHt1KoQclhHCZxhCpvKKHW4nohrl5xi1NeUUvf3zXcU/77r3P3vucu/c52p+ZPfucvV6/vfb6/dZav7X2hpiYmLylGOgWtRAxMVlwNGrHBclE4NCohcgzWgO746Ogjvtsn2QeUOQSdg3wFfBtSLIUChcAg4B94qNgjnXATXYPM185EPgMaBS1IHnIc0BJ1ELE+GYZatd5hVMPeDvwOrAzRFkKgSbm+C1qQWJ8UwncFbUQXmgBbAGOjVqQPKQfBTaUifmPQ4BtQPuoBcnEYGBz1ELkKZOInVKFTA0wPGoh0rEbgg4AVoQtSIHQkdgpFTV3oPncVqAWmAsc5zHtCtS+8wY7BTwNWBm2IAVAd+J6yQfKgMlAL6Ac2AHMB/b3kHYl0BN373+ktEDrJqOiFiQPuRc4OWoh/ofciNrcNQHTt0TOwoEe4t5gyuoUsKycY7UEKcG2NHC52VZ6FJQCy0Msbwh1C8lDQyw3bE40508Cpi9B7fhXD3FT7Tpv5vFWBWxlzlsbuNxsKz1sDgZ+RMoQBh3RLqTfQyovSkqRd/LzgOkr0NDyYw9xU+3abR23PepRJwAHIONXiTal/IWU+APgWnIwlLVm0Nic/8k24wxkW+kNhVOFDkST/TDYB3gK2AQ8HlKZQUkgo1QWMH1TtNz1KZrL+eVB4AzgUrytWf9tzk1c4lyA2kGlyXcq0ANYgpT9ZeT0mQa8iJ5XzihFFXp1LjO10BQp+JIGLCMIA4G12CvhHKBZSHIMB3ahhpUk8xD0cuBZoBptENiMvIRuz7AMeAH4HjXKn4B5wIU+ZU2QnQKeZNJPBk5AjXsT8AfwFu7ezYeBn4FjfJR3sSnvbJc4bwAb0S6wctQurG3iIOQN3w1c4qP8elgzrjXnVtaIOaQr6mk/wX+lNxQnoUZ0BPKupdMCWddtIchxNDAGGA+85yF+CTATOAx4H3gUeAXoDDyJvTOtAliIGtd84BHzv5T6997QlJpzJ+BD1KCnA1VISRagze9WJgBXAH2ANT7KS7XrWofw/VC9zEXPfIH5vcsSbwN1o5Myh7yCGEaKkEW8xy1SllyPKvp1pHQvAWNRA9oN/IJ9pYfBh0aWdC4mHGdRMXLyrAWam2tJ3HvAlsgaW+mAHvqXluv3m/xeQobFmpdf72CC7HrAKSb9RrTMk87TJuxOy/XJaC5Xju49dbT0UN7NJk+nDuZyE+7FozrSxB1nE1YCbAc+QgblAXPeiIdVhiXAMx4ECEqQSg+LkUgB0pkOtAuh7NHI6vZMu5YkuBd0LTJmKbqb/JfhPgfyQ4LsFHA5zt7wHiZstuW60ytHSQ/lTaL+801nDnJ8ZZpuFAOrTbl9bcL9GsY9GEPDOkeCVHpYdDHlH2X+FwGvekhXg7/306wG7hTkhLD2vkncFbANcDfyAG5GCpZeTlVa3Fnm2pke7seOGvzd44wM+TVGo60a7F+Y7WTyqQworx2LgSccwpoh5ZjjIZ+HqBvF+WUPw2h34y8CtwH7An/ahNfgb6jyLBqvgyq9K7Ae9XZWNphzJguUjQxuVKMKOh9ZqZ54cxZ9jb854o9pv4uRclQjZfJKNzRnbg8sBZ5Ha2Hb0RzwSmBVWvy+SEkX+igjnQrqTw1OQF7DmeiZpJNp11BX1BPPxd4Dmnq+631J6UwjVGdOdXwO6rkyKfzNwK2ofQxxiNMGbdrvDxyJhrzp/pb/tnraKWAVsqgDkDJayaax5arSs5EhE6+hRjUWKaKdobAStFcBPfQu5rfTPU01x3hghLk2CylEH2CRJf5oc05tHGgGtEVKYXUoeKXC5loC1dUMGxkykVoLrnEIv8ic3/KZrxNnoXbgZIAuQt55t15tGHoGa9Azt1v892sYbTk9gyBBGYq67lsdwseZ8PMaoGyv9EJDuXaEs/bXHK0p2R1VqD7eN/8vM2k6mutv2uTXGvjOhJ+aVsZu4Iccy54g+BzwMZw/F9EBjb6qyd33XGYjee1ohHwSb7ikH4HkXY27T2AVMqRlNmGjTR7D3EUVlcDhXiL6IOxKD0IRWl+6H3sPV5gksZ8DtjXXq6nbPAHauTHPhG1nz6F8ymkwyKacLgT7+kGC4Aq41KT9hj09si2Bt5ER7BcgXzs6AO/ivNGij5HlOofwUSZ8Be5v1fs1jK60Rx7AXBJmpWfDNDQcKY9YjiTOTph3qHO0jEVD0o3IibCT+sOc/ub6LjS6GYs80kvRQnwQEgRTwGK0rasKzaXWoV0tE9DmgF1orpUrZqC5mBMTUd3Yvax7N7rH5WR+4yKIYXSlG5qc5oKwKz0bzkcOi6g/Z5fEWQHbovlpLfLeLUbzi+7ULWhb6Y2ULzUn+QnNVwYHlC9BMAU83qSbgvbZvoLW9raihuo3Pzd6A+dmiPMdGuZbuQrJuQONhpI2R8KSxq9hzEiuPswUZqVnS3P04mdM4ZOp/Z6M2uUtNmFJMi+3LLKkCWIYY2L2WlK7gzpHLUhMzN7IF8RfOoiJiYmJiYmJiYmJiYkJgX8BwlKCUbczg2IAAAAASUVORK5CYII=\n",
      "text/latex": [
       "$$\\frac{1}{2 a} \\left(- b - \\sqrt{- 4 a c + b^{2}}\\right)$$"
      ],
      "text/plain": [
       "        _____________\n",
       "       ╱           2 \n",
       "-b - ╲╱  -4⋅a⋅c + b  \n",
       "─────────────────────\n",
       "         2⋅a         "
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "root1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAOAAAAAgCAYAAAALxXRVAAAABHNCSVQICAgIfAhkiAAAB6dJREFUeJztnHeMFVUUhz9hRZCiqIhEkagRKyiuDRWzYMGGWKIm1lGJGjVqrFGjvpCIZC0gKio2sCvqaoixg11BXLDLWrLYFZSIDUHAP373sY/ZO/XNm3lP50smszu3nTlzzp17z73zICcnp2qpAwZmLUROThlsg+y4JrkJ2DRrIaqMdYGV+VFTx9XWJ1kFdPBJOwX4HPgqJVlqhZHA0cAa+VEzx2fA2baHWa1sAHwIdMxakCrkQaB71kLkROYdZNdVhdcb8GLgaWB5irLUAp3M8VvWguREpgm4PGshwtAV+BXYLmtBqpADqLGhTM4qNgGWAL2zFiSI44BFWQtRpdxCHpSqZVqBc7MWohTbEPQQYE7agtQIfcmDUllzKZrPLQYWANOA7UOWnYPsu2qwOeCewNy0BakBBpHrpRpoACYCewDDgH+AF4H1QpSdCwzGP/qfKV3RusklWQtShVwF7JK1EP9BzkQ2d0rM8t1QsHBEiLxnmLb6xWwrcdw9QVGwXyvcbrlKz4J6YHaK7Z1A20LyqBTbTZudzPndmOW7Izv+JUTeol1XzTze7YA9zHlxhdstV+lpszHwHXKGNOiLdiH9nlJ7WVKPopMfxSw/Hg0t3w6Rt2jXfuu4vdEbdQKwPur8mtCmlL+QE78OnEoCQ1l3BWua89JyKw6gXKVXCi+FjkCT/TRYA7gH+Bm4LaU24+KgTqkhZvm10HLX+2guF5Vrgb2Bowi3Zv23OXfyyTMS2UGTqfcOYDdgJnL2x1HQ507gUfS8EqMeKfTkJCt1sRZy8JkJ1+tQnjGMAOZhd8KpQOeY9UblXGAFMqwCwUPQY4EHgBa0QWARihL6PcMG4BHgG2SU3wPPAYdFlNWhPJ3vbMpPBHZExv0z8AfwPP7RzeuBH4FtI7R3hGlvP588zwAL0S6wYcgu3DaxEYqGrwSOjNB+O9wVLzDnHu6MCTIAvWnfJbrSK8XOyIi2RNG1Urqi3nVJCnJsA4wFbgReDZG/OzAF2Bx4DbgZeALYDLgbezBtPDADGdeLwA3m/3ra33ulqTfnfsAbyKDvApqRk0xHm9/dTACOB4YCH0dor2jXCzzS10F6mYae+XTz9wpXvh9oG500eNQVp2OkA+oRr/TLVCanI0U/jZzuMaARGdBK4CfsSg/CobzeGGQEja5rR5BOsKgOBXnmAV3MtQL+b8BuqDd20wc99E9d18eY+h5DHYu7rqjRQYfydD7JlF+IlnlKudekXea6PhHN5Yahey8e3UK0d46p0+sFc6xJDxNRvcjkHWdJ6w4sA95CHco15ryQEKsMM4H7QwgQlzhKD4ND+Q54EXKAUu4CNiyjzrCMRr3u4JJrBeJHQeehzqzIIFP/O/jPgaLgUJ7OZ+MdDd/NpD3kuu71yVEhRHu30P75ljIVBb6Cpht1wAem3eGW9Kgd42qMpbLBkThKD4ND+Q7Y39Sxtfm/A/BkiHKtRPs+zd3B7YqCEO63bwF/B+wJXIEigIuQg5W201yS9z5zbZ8Q92OjlWj3ODmgvjXRaKsV+wez/Uw9TTHltfEmcLtHWmfkHFND1HMdbaO4qKzWMdpu/FHgQmBt4E9LeivRhioPoPE6SOkDgPnobefmB3MO6oH8ZJhhuTYFOWgQLUhBh6JeajDhgkVfEG2O+F3J33XIOVqQM4VlIJoz9wZmAQ+jtbBlaA54IvBeSf7hyElt+gnDeNpPDXZEUcMp6JmUErRraAB6E0/DHgEtPt/5kaT0piPSmZeO90dvriCHPwe4ANnHCR55eqJN+wcDW6Ehb2m8ZdVWT5sDNqMe9RDkjG7KMbaklJ60MZTylKmnETmiraNwE/etAnro/c3fXnq9wxw3AueZa/chHQwFXnblH23OxY0DnYFeSA/ugEJYxluuOUhXky0yBFFcC271SD/cnJ+PWK8X+yJb9OqADkfReb+32lnoGXyMnrlt8T9qx2hlrwBB4jIKvbov8EgfZ9IPilG3Q/lDUFAkcDma96Wx9tcFrSnZjmZ0T6+Z/48xZfqa689a6lsX+Nqk717Sxkrg24Rld4iv81vx/rmIPmj01UJyv+fyEN6joI4oJvGMT/nzkLwf4B8TeA91pA2WtNGmjrP8RRVNwBZhMkagkkp3SMYBO6D1pTHYI1xpUsA+B+xlrrfQtnkCtHPjOZO2jNWH8sWgwdGWdvoT79cPHOLrfJYp+yWrR2S7AS+gTvCAGPXa6AO8gvdGi6FGltM80i8x6XPw/6o+asfoS28UAUySSirdIRkHBL1tlqJQd5YU8A7CvERboKURDUkXoiDCctoPcw4211eg0U0jikjPQgvxcXCIp/M6tK2rGc2lPkO7WiagzQEr0FwrKSajuZgXNyHd2D7WvQLd42yCv7iI0zH6MhBNTpOg0kp3SM4BD0UBi6x/zq6AtwP2QvPTBSh69yaaXwyibUHbzRDkfMU5yfdovnJcTPkc4ul8B1NuEtpn+wRa21uMDDVqfX4MAQ4MyPM1Gua7OQnJ+Q8aDRUsh+MqE7VjDCSpH2aqtNIdknPALujDz5zaJ8h+d0F2c74lrUDwcsvLrjJxOsacnP8txd1Bm2UtSE7O/5FPyH/pICcnJycnJycnJycnJycF/gXtdZJcHV903gAAAABJRU5ErkJggg==\n",
      "text/latex": [
       "$$\\frac{1}{2 a} \\left(- b + \\sqrt{- 4 a c + b^{2}}\\right)$$"
      ],
      "text/plain": [
       "        _____________\n",
       "       ╱           2 \n",
       "-b + ╲╱  -4⋅a⋅c + b  \n",
       "─────────────────────\n",
       "         2⋅a         "
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "root2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At some point I will probably make an optional library of Joy wrappers for SymPy functions, and either load it automatically if SymPy installation is available or have a CLI switch or something.  There's a huge amount of incredibly useful stuff and I don't see why Joy shouldn't expose another interface for using it.  (As an example, the symbolic expressions can be \"lambdafied\" into very fast versions, i.e. a function that takes `a`, `b`, and `c` and computes the value of the root using just low-level fast code, bypassing Joy and Python.  Also, Numpy, &c.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Partial Evaluation\n",
    "\n",
    "[Futamura projections](https://en.wikipedia.org/wiki/Futamura_projection)\n",
    "\n",
    "Starting with the example from [Partial Computation of Programs](http://hdl.handle.net/2433/103401)\n",
    "by [Yoshihiko Futamura](http://fi.ftmr.info/) of a function to compute `u` to the `k`th power:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def F(u, k):\n",
    "    z = 1\n",
    "    while k != 0:\n",
    "        if odd(k):\n",
    "            z = z * u\n",
    "        k = k / 2\n",
    "        u = u * u\n",
    "    return z"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Partial evaluation with `k = 5`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def F5(u):\n",
    "    z = 1 * u\n",
    "    u = u * u\n",
    "    u = u * u\n",
    "    z = z * u\n",
    "    return z"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translate `F(u, k)` to Joy\n",
    "\n",
    "    u k 1                    # z = 1\n",
    "        [pop] [Fw] while     # the while statement\n",
    "        popopd               # discard u k, \"return\" z"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What's Fw?\n",
    "\n",
    "\n",
    "    u k z [pop odd] [Ft] [] ifte   # the if statement\n",
    "          [2 //] dip               # k = k / 2  floordiv\n",
    "          [sqr] dipd               # u = u * u\n",
    "\n",
    "          [[sqr] dip 2 //] dip     # We can merge last two lines."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Helper function Ft (to compute z = z * u).\n",
    "\n",
    "\n",
    "       u k z Ft\n",
    "    ---------------\n",
    "       u k u*z\n",
    "\n",
    "\n",
    "    Ft == [over] dip *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Putting it together:\n",
    "\n",
    "    Ft == [over] dip *\n",
    "    Fb == [[sqr] dip 2 //] dip\n",
    "    Fw == [pop odd] [Ft] [] ifte Fb\n",
    "     F == 1 [pop] [Fw] while popopd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "define('odd == 2 %')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "define('Ft == [over] dip *')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "define('Fb == [[sqr] dip 2 //] dip')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "define('Fw == [pop odd] [Ft] [] ifte Fb')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "define('F == 1 [pop] [Fw] while popopd')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Try it out:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "32\n"
     ]
    }
   ],
   "source": [
    "J('2 5 F')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to elide the tests let's define special versions of `while` and `ifte`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "from joy.joy import joy\n",
    "from joy.library import FunctionWrapper\n",
    "from joy.parser import Symbol\n",
    "from joy.utils.stack import concat\n",
    "\n",
    "\n",
    "S_while = Symbol('while')\n",
    "\n",
    "\n",
    "@FunctionWrapper\n",
    "def while_(S, expression, dictionary):\n",
    "    '''[if] [body] while'''\n",
    "    (body, (if_, stack)) = S\n",
    "    if joy(stack, if_, dictionary)[0][0]:\n",
    "        expression = concat(body, (if_, (body, (S_while, expression))))\n",
    "    return stack, expression, dictionary\n",
    "\n",
    "\n",
    "@FunctionWrapper\n",
    "def ifte(stack, expression, dictionary):\n",
    "    '''[if] [then] [else] ifte'''\n",
    "    (else_, (then, (if_, stack))) = stack\n",
    "    if_res = joy(stack, if_, dictionary)[0][0]\n",
    "    quote = then if if_res else else_\n",
    "    expression = concat(quote, expression)\n",
    "    return (stack, expression, dictionary)\n",
    "\n",
    "\n",
    "D['ifte'] = ifte\n",
    "D['while'] = while_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And with a SymPy symbol for the `u` argument:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "                         u 5 . F\n",
      "                         u 5 . 1 [pop] [Fw] while popopd\n",
      "                       u 5 1 . [pop] [Fw] while popopd\n",
      "                 u 5 1 [pop] . [Fw] while popopd\n",
      "            u 5 1 [pop] [Fw] . while popopd\n",
      "                       u 5 1 . Fw [pop] [Fw] while popopd\n",
      "                       u 5 1 . [pop odd] [Ft] [] ifte Fb [pop] [Fw] while popopd\n",
      "             u 5 1 [pop odd] . [Ft] [] ifte Fb [pop] [Fw] while popopd\n",
      "        u 5 1 [pop odd] [Ft] . [] ifte Fb [pop] [Fw] while popopd\n",
      "     u 5 1 [pop odd] [Ft] [] . ifte Fb [pop] [Fw] while popopd\n",
      "                       u 5 1 . Ft Fb [pop] [Fw] while popopd\n",
      "                       u 5 1 . [over] dip * Fb [pop] [Fw] while popopd\n",
      "                u 5 1 [over] . dip * Fb [pop] [Fw] while popopd\n",
      "                         u 5 . over 1 * Fb [pop] [Fw] while popopd\n",
      "                       u 5 u . 1 * Fb [pop] [Fw] while popopd\n",
      "                     u 5 u 1 . * Fb [pop] [Fw] while popopd\n",
      "                       u 5 u . Fb [pop] [Fw] while popopd\n",
      "                       u 5 u . [[sqr] dip 2 //] dip [pop] [Fw] while popopd\n",
      "      u 5 u [[sqr] dip 2 //] . dip [pop] [Fw] while popopd\n",
      "                         u 5 . [sqr] dip 2 // u [pop] [Fw] while popopd\n",
      "                   u 5 [sqr] . dip 2 // u [pop] [Fw] while popopd\n",
      "                           u . sqr 5 2 // u [pop] [Fw] while popopd\n",
      "                           u . dup mul 5 2 // u [pop] [Fw] while popopd\n",
      "                         u u . mul 5 2 // u [pop] [Fw] while popopd\n",
      "                        u**2 . 5 2 // u [pop] [Fw] while popopd\n",
      "                      u**2 5 . 2 // u [pop] [Fw] while popopd\n",
      "                    u**2 5 2 . // u [pop] [Fw] while popopd\n",
      "                      u**2 2 . u [pop] [Fw] while popopd\n",
      "                    u**2 2 u . [pop] [Fw] while popopd\n",
      "              u**2 2 u [pop] . [Fw] while popopd\n",
      "         u**2 2 u [pop] [Fw] . while popopd\n",
      "                    u**2 2 u . Fw [pop] [Fw] while popopd\n",
      "                    u**2 2 u . [pop odd] [Ft] [] ifte Fb [pop] [Fw] while popopd\n",
      "          u**2 2 u [pop odd] . [Ft] [] ifte Fb [pop] [Fw] while popopd\n",
      "     u**2 2 u [pop odd] [Ft] . [] ifte Fb [pop] [Fw] while popopd\n",
      "  u**2 2 u [pop odd] [Ft] [] . ifte Fb [pop] [Fw] while popopd\n",
      "                    u**2 2 u . Fb [pop] [Fw] while popopd\n",
      "                    u**2 2 u . [[sqr] dip 2 //] dip [pop] [Fw] while popopd\n",
      "   u**2 2 u [[sqr] dip 2 //] . dip [pop] [Fw] while popopd\n",
      "                      u**2 2 . [sqr] dip 2 // u [pop] [Fw] while popopd\n",
      "                u**2 2 [sqr] . dip 2 // u [pop] [Fw] while popopd\n",
      "                        u**2 . sqr 2 2 // u [pop] [Fw] while popopd\n",
      "                        u**2 . dup mul 2 2 // u [pop] [Fw] while popopd\n",
      "                   u**2 u**2 . mul 2 2 // u [pop] [Fw] while popopd\n",
      "                        u**4 . 2 2 // u [pop] [Fw] while popopd\n",
      "                      u**4 2 . 2 // u [pop] [Fw] while popopd\n",
      "                    u**4 2 2 . // u [pop] [Fw] while popopd\n",
      "                      u**4 1 . u [pop] [Fw] while popopd\n",
      "                    u**4 1 u . [pop] [Fw] while popopd\n",
      "              u**4 1 u [pop] . [Fw] while popopd\n",
      "         u**4 1 u [pop] [Fw] . while popopd\n",
      "                    u**4 1 u . Fw [pop] [Fw] while popopd\n",
      "                    u**4 1 u . [pop odd] [Ft] [] ifte Fb [pop] [Fw] while popopd\n",
      "          u**4 1 u [pop odd] . [Ft] [] ifte Fb [pop] [Fw] while popopd\n",
      "     u**4 1 u [pop odd] [Ft] . [] ifte Fb [pop] [Fw] while popopd\n",
      "  u**4 1 u [pop odd] [Ft] [] . ifte Fb [pop] [Fw] while popopd\n",
      "                    u**4 1 u . Ft Fb [pop] [Fw] while popopd\n",
      "                    u**4 1 u . [over] dip * Fb [pop] [Fw] while popopd\n",
      "             u**4 1 u [over] . dip * Fb [pop] [Fw] while popopd\n",
      "                      u**4 1 . over u * Fb [pop] [Fw] while popopd\n",
      "                 u**4 1 u**4 . u * Fb [pop] [Fw] while popopd\n",
      "               u**4 1 u**4 u . * Fb [pop] [Fw] while popopd\n",
      "                 u**4 1 u**5 . Fb [pop] [Fw] while popopd\n",
      "                 u**4 1 u**5 . [[sqr] dip 2 //] dip [pop] [Fw] while popopd\n",
      "u**4 1 u**5 [[sqr] dip 2 //] . dip [pop] [Fw] while popopd\n",
      "                      u**4 1 . [sqr] dip 2 // u**5 [pop] [Fw] while popopd\n",
      "                u**4 1 [sqr] . dip 2 // u**5 [pop] [Fw] while popopd\n",
      "                        u**4 . sqr 1 2 // u**5 [pop] [Fw] while popopd\n",
      "                        u**4 . dup mul 1 2 // u**5 [pop] [Fw] while popopd\n",
      "                   u**4 u**4 . mul 1 2 // u**5 [pop] [Fw] while popopd\n",
      "                        u**8 . 1 2 // u**5 [pop] [Fw] while popopd\n",
      "                      u**8 1 . 2 // u**5 [pop] [Fw] while popopd\n",
      "                    u**8 1 2 . // u**5 [pop] [Fw] while popopd\n",
      "                      u**8 0 . u**5 [pop] [Fw] while popopd\n",
      "                 u**8 0 u**5 . [pop] [Fw] while popopd\n",
      "           u**8 0 u**5 [pop] . [Fw] while popopd\n",
      "      u**8 0 u**5 [pop] [Fw] . while popopd\n",
      "                 u**8 0 u**5 . popopd\n",
      "                        u**5 . \n"
     ]
    }
   ],
   "source": [
    "stack = list_to_stack([5, sympy.symbols('u')])\n",
    "viewer = TracePrinter()\n",
    "try:\n",
    "    (result, _) = run('F', stack, D, viewer.viewer)[0]\n",
    "except Exception, e:\n",
    "    print e\n",
    "viewer.print_()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAABgAAAAWCAYAAADafVyIAAAABHNCSVQICAgIfAhkiAAAAUpJREFUSInt1DtLXUEUBeBPESLXFGITsDEqEdHKaLBMQBvFRsh/SG9nKouAjY0/IsQm2lgoNrENeaEgaKGVjyBaBLQQNRYzSYbjOVduzoWkcMGwmb1n1pr9YPjPMYOfmXWUHmiqg8g2XiT7q3oLXMq8OkVjHQS6sI89vMPjNNhQknwMFezgEabRh36cluTORQu+Y+qXI1ui18IkTOZc7oixxSoCZ9jCkyKBp9F+zrk8FO3XKgLN6MVh0YE9HBfEZoUMJhLfHJ6jE8NYxg8h21toiwQrBQJrMd6e+BZwgAthkt4LTc7FaCR4UxA/ERpYE9IeDEabV/8uIcMvZQQGos0jGY+2WoPvxDehllk8wKZQvpdlBD5Gkp7E14K3/vyU3bWSpp/dKp5hHUt4iBFsCHNdwe5fPPw3mjEvjN05PuEVWnGND2XI7/HvcAOaJEK/e6V+UwAAAABJRU5ErkJggg==\n",
      "text/latex": [
       "$$u^{5}$$"
      ],
      "text/plain": [
       " 5\n",
       "u "
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's try partial evaluation by hand and use a \"stronger\" thunk.\n",
    "\n",
    "Caret underscoring indicates terms that form thunks.  When an arg is unavailable for a computation we just postpone it until the arg becomes available and in the meantime treat the pending computation as one unit.\n",
    "\n",
    "                             u 5 . F\n",
    "                             u 5 . 1 [pop] [Fw] while popopd\n",
    "                           u 5 1 . [pop] [Fw] while popopd\n",
    "                     u 5 1 [pop] . [Fw] while popopd\n",
    "                u 5 1 [pop] [Fw] . while popopd\n",
    "                           u 5 1 . Fw [pop] [Fw] while popopd\n",
    "                           u 5 1 . [pop odd] [Ft] [] ifte Fb [pop] [Fw] while popopd\n",
    "                 u 5 1 [pop odd] . [Ft] [] ifte Fb [pop] [Fw] while popopd\n",
    "            u 5 1 [pop odd] [Ft] . [] ifte Fb [pop] [Fw] while popopd\n",
    "         u 5 1 [pop odd] [Ft] [] . ifte Fb [pop] [Fw] while popopd\n",
    "                           u 5 1 . Ft Fb [pop] [Fw] while popopd\n",
    "                           u 5 1 . [over] dip * Fb [pop] [Fw] while popopd\n",
    "                    u 5 1 [over] . dip * Fb [pop] [Fw] while popopd\n",
    "                             u 5 . over 1 * Fb [pop] [Fw] while popopd\n",
    "                           u 5 u . 1 * Fb [pop] [Fw] while popopd\n",
    "                         u 5 u 1 . * Fb [pop] [Fw] while popopd\n",
    "                           u 5 u . Fb [pop] [Fw] while popopd\n",
    "                           u 5 u . [[sqr] dip 2 //] dip [pop] [Fw] while popopd\n",
    "          u 5 u [[sqr] dip 2 //] . dip [pop] [Fw] while popopd\n",
    "                             u 5 . [sqr] dip 2 // u [pop] [Fw] while popopd\n",
    "                       u 5 [sqr] . dip 2 // u [pop] [Fw] while popopd\n",
    "                               u . sqr 5 2 // u [pop] [Fw] while popopd\n",
    "                               u . dup mul 5 2 // u [pop] [Fw] while popopd\n",
    "                         u dup * . 5 2 // u [pop] [Fw] while popopd\n",
    "                         ^^^^^^^"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "             u dup * 2 u [pop] [Fw] . while popopd\n",
    "                        u dup * 2 u . Fw [pop] [Fw] while popopd\n",
    "                        u dup * 2 u . [pop odd] [Ft] [] ifte Fb [pop] [Fw] while popopd\n",
    "              u dup * 2 u [pop odd] . [Ft] [] ifte Fb [pop] [Fw] while popopd\n",
    "         u dup * 2 u [pop odd] [Ft] . [] ifte Fb [pop] [Fw] while popopd\n",
    "      u dup * 2 u [pop odd] [Ft] [] . ifte Fb [pop] [Fw] while popopd\n",
    "                        u dup * 2 u . Fb [pop] [Fw] while popopd\n",
    "                        u dup * 2 u . [[sqr] dip 2 //] dip [pop] [Fw] while popopd\n",
    "       u dup * 2 u [[sqr] dip 2 //] . dip [pop] [Fw] while popopd\n",
    "                          u dup * 2 . [sqr] dip 2 // u [pop] [Fw] while popopd\n",
    "                    u dup * 2 [sqr] . dip 2 // u [pop] [Fw] while popopd\n",
    "                            u dup * . sqr 2 2 // u [pop] [Fw] while popopd\n",
    "                            u dup * . dup mul 2 2 // u [pop] [Fw] while popopd\n",
    "                      u dup * dup * . 2 2 // u [pop] [Fw] while popopd\n",
    "                      ^^^^^^^^^^^^^\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "w/ `K == u dup * dup *`\n",
    "\n",
    "                 K 1 u [pop] [Fw] . while popopd\n",
    "                            K 1 u . Fw [pop] [Fw] while popopd\n",
    "                            K 1 u . [pop odd] [Ft] [] ifte Fb [pop] [Fw] while popopd\n",
    "                  K 1 u [pop odd] . [Ft] [] ifte Fb [pop] [Fw] while popopd\n",
    "             K 1 u [pop odd] [Ft] . [] ifte Fb [pop] [Fw] while popopd\n",
    "          K 1 u [pop odd] [Ft] [] . ifte Fb [pop] [Fw] while popopd\n",
    "                            K 1 u . Ft Fb [pop] [Fw] while popopd\n",
    "                            K 1 u . [over] dip * Fb [pop] [Fw] while popopd\n",
    "                     K 1 u [over] . dip * Fb [pop] [Fw] while popopd\n",
    "                              K 1 . over u * Fb [pop] [Fw] while popopd\n",
    "                            K 1 K . u * Fb [pop] [Fw] while popopd\n",
    "                          K 1 K u . * Fb [pop] [Fw] while popopd\n",
    "                        K 1 K u * . Fb [pop] [Fw] while popopd\n",
    "                            ^^^^^"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "w/ `L == K u *`\n",
    "\n",
    "                         K 1 L . Fb [pop] [Fw] while popopd\n",
    "                         K 1 L . [[sqr] dip 2 //] dip [pop] [Fw] while popopd\n",
    "        K 1 L [[sqr] dip 2 //] . dip [pop] [Fw] while popopd\n",
    "                           K 1 . [sqr] dip 2 // L [pop] [Fw] while popopd\n",
    "                     K 1 [sqr] . dip 2 // L [pop] [Fw] while popopd\n",
    "                             K . sqr 1 2 // L [pop] [Fw] while popopd\n",
    "                             K . dup mul 1 2 // L [pop] [Fw] while popopd\n",
    "                           K K . mul 1 2 // L [pop] [Fw] while popopd\n",
    "                         K K * . 1 2 // L [pop] [Fw] while popopd\n",
    "                         ^^^^^\n",
    "                         K K * . 1 2 // L [pop] [Fw] while popopd\n",
    "                       K K * 1 . 2 // L [pop] [Fw] while popopd\n",
    "                     K K * 1 2 . // L [pop] [Fw] while popopd\n",
    "                       K K * 0 . L [pop] [Fw] while popopd\n",
    "                     K K * 0 L . [pop] [Fw] while popopd\n",
    "               K K * 0 L [pop] . [Fw] while popopd\n",
    "          K K * 0 L [pop] [Fw] . while popopd\n",
    "          ^^^^^\n",
    "                     K K * 0 L . popopd\n",
    "                             L . "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So:\n",
    "\n",
    "    K == u dup * dup *\n",
    "    L == K u *\n",
    "\n",
    "Our result \"thunk\" would be:\n",
    "    \n",
    "    u dup * dup * u *\n",
    "\n",
    "Mechanically, you could do:\n",
    "\n",
    "    u      dup * dup *  u   *\n",
    "    u u   [dup * dup *] dip *\n",
    "    u dup [dup * dup *] dip *\n",
    "\n",
    "\n",
    "    F5 == dup [dup * dup *] dip *\n",
    "\n",
    "But we can swap the two arguments to the final `*` to get all mentions of `u` to the left:\n",
    "\n",
    "\n",
    "    u u dup * dup * *\n",
    "\n",
    "\n",
    "Then de-duplicate \"u\":\n",
    "\n",
    "\n",
    "    u dup dup * dup * *\n",
    "\n",
    "\n",
    "To arrive at a startlingly elegant form for F5:\n",
    "\n",
    "\n",
    "    F5 == dup dup * dup * *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "          u . dup dup * dup * *\n",
      "        u u . dup * dup * *\n",
      "      u u u . * dup * *\n",
      "     u u**2 . dup * *\n",
      "u u**2 u**2 . * *\n",
      "     u u**4 . *\n",
      "       u**5 . \n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAABgAAAAWCAYAAADafVyIAAAABHNCSVQICAgIfAhkiAAAAUpJREFUSInt1DtLXUEUBeBPESLXFGITsDEqEdHKaLBMQBvFRsh/SG9nKouAjY0/IsQm2lgoNrENeaEgaKGVjyBaBLQQNRYzSYbjOVduzoWkcMGwmb1n1pr9YPjPMYOfmXWUHmiqg8g2XiT7q3oLXMq8OkVjHQS6sI89vMPjNNhQknwMFezgEabRh36cluTORQu+Y+qXI1ui18IkTOZc7oixxSoCZ9jCkyKBp9F+zrk8FO3XKgLN6MVh0YE9HBfEZoUMJhLfHJ6jE8NYxg8h21toiwQrBQJrMd6e+BZwgAthkt4LTc7FaCR4UxA/ERpYE9IeDEabV/8uIcMvZQQGos0jGY+2WoPvxDehllk8wKZQvpdlBD5Gkp7E14K3/vyU3bWSpp/dKp5hHUt4iBFsCHNdwe5fPPw3mjEvjN05PuEVWnGND2XI7/HvcAOaJEK/e6V+UwAAAABJRU5ErkJggg==\n",
      "text/latex": [
       "$$u^{5}$$"
      ],
      "text/plain": [
       " 5\n",
       "u "
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "stack = list_to_stack([sympy.symbols('u')])\n",
    "viewer = TracePrinter()\n",
    "try:\n",
    "    (result, _) = run('dup dup * dup * *', stack, D, viewer.viewer)[0]\n",
    "except Exception, e:\n",
    "    print e\n",
    "viewer.print_()\n",
    "result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I'm not sure how to implement these kinds of thunks.  I think you have to have support in the interpreter, or you have to modify all of the functions like `dup` to check for thunks in their inputs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Working on the compiler, from this:\n",
    "\n",
    "    dup dup * dup * *\n",
    "\n",
    "We can already generate:\n",
    "\n",
    "    ---------------------------------\n",
    "    (a0, stack) = stack\n",
    "    a1 = mul(a0, a0)\n",
    "    a2 = mul(a1, a1)\n",
    "    a3 = mul(a2, a0)\n",
    "    stack = (a3, stack)\n",
    "    ---------------------------------\n",
    "\n",
    "This is pretty old stuff...  (E.g. from 1999, M. Anton Ertl [Compilation of Stack-Based Languages](http://www.complang.tuwien.ac.at/projects/rafts.html) he goes a lot further for Forth.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## \"A Transformation Based Approach to Semantics-Directed Code Generation\"\n",
    "\n",
    "by Arthur Nunes-Harwitt\n",
    "\n",
    "https://dl.acm.org/citation.cfm?doid=2635648.2635652\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    }
   ],
   "source": [
    "def m(x, y): return x * y\n",
    "\n",
    "print m(2, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    }
   ],
   "source": [
    "def m(x): return lambda y: x * y\n",
    "\n",
    "print m(2)(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lambda y: 2 * y\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "def m(x): return \"lambda y: %(x)s * y\" % locals()\n",
    "\n",
    "print m(2)\n",
    "print eval(m(2))(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In Joy:\n",
    "\n",
    "    m == [*] cons\n",
    "\n",
    "    3 2 m i\n",
    "    3 2 [*] cons i\n",
    "    3 [2 *] i\n",
    "    3 2 *\n",
    "    6\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lambda b: 1 if 3 == 0 else b * p(3 - 1, b)\n"
     ]
    }
   ],
   "source": [
    "def p(n, b): # original\n",
    "    return 1 if n == 0 else b * p(n - 1, b)\n",
    "\n",
    "\n",
    "def p(n): # curried\n",
    "    return lambda b: 1 if n == 0 else b * p(n - 1, b)\n",
    "\n",
    "\n",
    "def p(n): # quoted\n",
    "    return \"lambda b: 1 if %(n)s == 0 else b * p(%(n)s - 1, b)\"  % locals()\n",
    "\n",
    "\n",
    "print p(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Original\n",
    "\n",
    "    p == [0 =] [popop 1] [-- over] [dip *] genrec\n",
    "\n",
    "    b n p\n",
    "    b n [0 =] [popop 1] [-- over [p] dip *]\n",
    "\n",
    "    b n -- over [p] dip *\n",
    "    b n-1  over [p] dip *\n",
    "    b n-1 b [p] dip *\n",
    "    b n-1 p b *\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "curried, quoted\n",
    "\n",
    "                        n p\n",
    "    ---------------------------------------------\n",
    "       [[n 0 =] [pop 1] [dup n --] [*] genrec]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lambda b: b * p(3 - 1, b)\n"
     ]
    }
   ],
   "source": [
    "def p(n): # lambda lowered\n",
    "    return (\n",
    "        lambda b: 1\n",
    "        if n == 0 else\n",
    "        lambda b: b * p(n - 1, b)\n",
    "        )\n",
    "\n",
    "\n",
    "def p(n): # lambda lowered quoted\n",
    "    return (\n",
    "        \"lambda b: 1\"\n",
    "        if n == 0 else\n",
    "        \"lambda b: b * p(%(n)s - 1, b)\"  % locals()\n",
    "        )\n",
    "\n",
    "print p(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "    p == [0 =] [[pop 1]] [ [-- [dup] dip p *] cons ]ifte\n",
    "\n",
    "\n",
    "    3 p\n",
    "    3 [-- [dup] dip p *] cons\n",
    "    [3 -- [dup] dip p *]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n"
     ]
    }
   ],
   "source": [
    "def p(n): # expression lifted\n",
    "    if n == 0:\n",
    "        return lambda b: 1\n",
    "    f = p(n - 1)\n",
    "    return lambda b: b * f(b)\n",
    "\n",
    "\n",
    "print p(3)(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lambda b: b * (lambda b: b * (lambda b: b * (lambda b: 1)(b))(b))(b)\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "def p(n): # quoted\n",
    "    if n == 0:\n",
    "        return \"lambda b: 1\"\n",
    "    f = p(n - 1)\n",
    "    return \"lambda b: b * (%(f)s)(b)\"  % locals()\n",
    "\n",
    "print p(3)\n",
    "print eval(p(3))(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    p == [0 =] [pop [pop 1]] [-- p [dupdip *] cons] ifte\n",
    "\n",
    "\n",
    "    3 p\n",
    "    3 -- p [dupdip *] cons\n",
    "    2    p [dupdip *] cons\n",
    "    2 -- p [dupdip *] cons [dupdip *] cons\n",
    "    1    p [dupdip *] cons [dupdip *] cons\n",
    "    1 -- p [dupdip *] cons [dupdip *] cons [dupdip *] cons\n",
    "    0    p [dupdip *] cons [dupdip *] cons [dupdip *] cons\n",
    "    0 pop [pop 1] [dupdip *] cons [dupdip *] cons [dupdip *] cons\n",
    "    [pop 1] [dupdip *] cons [dupdip *] cons [dupdip *] cons\n",
    "    ...\n",
    "    [[[[pop 1] dupdip *] dupdip *] dupdip *]\n",
    "\n",
    "\n",
    "    2 [[[[pop 1] dupdip *] dupdip *] dupdip *] i\n",
    "    2  [[[pop 1] dupdip *] dupdip *] dupdip *\n",
    "    2   [[pop 1] dupdip *] dupdip *  2 *\n",
    "    2    [pop 1] dupdip *  2      *  2 *\n",
    "    2     pop 1  2      *  2      *  2 *\n",
    "              1  2      *  2      *  2 *\n",
    "\n",
    "\n",
    "\n",
    "    p == [0 =] [pop [pop 1]] [--  p    [dupdip *] cons] ifte\n",
    "    p == [0 =] [pop [pop 1]] [-- [p] i [dupdip *] cons] ifte\n",
    "    p == [0 =] [pop [pop 1]] [--]   [i [dupdip *] cons] genrec"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "define('p == [0 =] [pop [pop 1]] [--] [i [dupdip *] cons] genrec')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[[[pop 1] dupdip *] dupdip *] dupdip *]\n"
     ]
    }
   ],
   "source": [
    "J('3 p')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "                                           . 2 [[[[pop 1] dupdip *] dupdip *] dupdip *] i\n",
      "                                         2 . [[[[pop 1] dupdip *] dupdip *] dupdip *] i\n",
      "2 [[[[pop 1] dupdip *] dupdip *] dupdip *] . i\n",
      "                                         2 . [[[pop 1] dupdip *] dupdip *] dupdip *\n",
      "           2 [[[pop 1] dupdip *] dupdip *] . dupdip *\n",
      "                                         2 . [[pop 1] dupdip *] dupdip * 2 *\n",
      "                      2 [[pop 1] dupdip *] . dupdip * 2 *\n",
      "                                         2 . [pop 1] dupdip * 2 * 2 *\n",
      "                                 2 [pop 1] . dupdip * 2 * 2 *\n",
      "                                         2 . pop 1 2 * 2 * 2 *\n",
      "                                           . 1 2 * 2 * 2 *\n",
      "                                         1 . 2 * 2 * 2 *\n",
      "                                       1 2 . * 2 * 2 *\n",
      "                                         2 . 2 * 2 *\n",
      "                                       2 2 . * 2 *\n",
      "                                         4 . 2 *\n",
      "                                       4 2 . *\n",
      "                                         8 . \n"
     ]
    }
   ],
   "source": [
    "V('2 [[[[pop 1] dupdip *] dupdip *] dupdip *] i')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "stack = list_to_stack([sympy.symbols('u')])\n",
    "(result, s) = run('p i', stack, D)[0]\n",
    "result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From this:\n",
    "\n",
    "    p == [0 =] [pop pop 1] [-- over] [dip *] genrec\n",
    "\n",
    "To this:\n",
    "\n",
    "    p == [0 =] [pop [pop 1]] [--] [i [dupdip *] cons] genrec\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Try it with `F()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def odd(n): return n % 2\n",
    "\n",
    "\n",
    "def F(u, k):\n",
    "    z = 1\n",
    "    while k != 0:\n",
    "        if odd(k):\n",
    "            z = z * u\n",
    "        k = k / 2\n",
    "        u = u * u\n",
    "    return z\n",
    "\n",
    "F(2, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def F(k):\n",
    "    def _F(u, k=k):\n",
    "        z = 1\n",
    "        while k != 0:\n",
    "            if odd(k):\n",
    "                z = z * u\n",
    "            k = k / 2\n",
    "            u = u * u\n",
    "        return z\n",
    "    return _F\n",
    "    \n",
    "F(5)(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def F(k):\n",
    "    def _F(u, k=k):\n",
    "        if k == 0:\n",
    "            z = 1\n",
    "        else:\n",
    "            z = F(k / 2)(u)\n",
    "            z *= z\n",
    "            if odd(k):\n",
    "                z = z * u\n",
    "        return z\n",
    "    return _F\n",
    "    \n",
    "F(5)(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def F(k):\n",
    "    if k == 0:\n",
    "        z = lambda u: 1\n",
    "    else:\n",
    "        f = F(k / 2)\n",
    "        def z(u):\n",
    "            uu = f(u)\n",
    "            uu *= uu\n",
    "            return uu * u if odd(k) else uu\n",
    "    return z\n",
    "    \n",
    "F(5)(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def F(k):\n",
    "    if k == 0:\n",
    "        z = lambda u: 1\n",
    "    else:\n",
    "        f = F(k / 2)\n",
    "        if odd(k):\n",
    "            z = lambda u: (lambda fu, u: fu * fu * u)(f(u), u)\n",
    "        else:\n",
    "            z = lambda u: (lambda fu, u: fu * fu)(f(u), u)\n",
    "    return z\n",
    "    \n",
    "F(5)(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def F(k):\n",
    "    if k == 0:\n",
    "        z = \"lambda u: 1\"\n",
    "    else:\n",
    "        f = F(k / 2)\n",
    "        if odd(k):\n",
    "            z = \"lambda u: (lambda fu, u: fu * fu * u)((%(f)s)(u), u)\" % locals()\n",
    "        else:\n",
    "            z = \"lambda u: (lambda fu, u: fu * fu)((%(f)s)(u), u)\" % locals()\n",
    "    return z\n",
    "    \n",
    "source = F(5)\n",
    "print source\n",
    "eval(source)(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hmm..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in range(4):\n",
    "    print F(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def F(k):\n",
    "    if k == 0:\n",
    "        z = \"lambda u: 1\"\n",
    "    elif k == 1:\n",
    "        z = \"lambda u: u\"\n",
    "    else:\n",
    "        f = F(k / 2)\n",
    "        if odd(k):\n",
    "            z = \"lambda u: (lambda fu, u: fu * fu * u)((%(f)s)(u), u)\" % locals()\n",
    "        else:\n",
    "            z = \"lambda u: (lambda fu, u: fu * fu)((%(f)s)(u), u)\" % locals()\n",
    "    return z\n",
    "    \n",
    "source = F(5)\n",
    "print source\n",
    "eval(source)(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in range(4):\n",
    "    print F(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def F(k):\n",
    "    if k == 0:\n",
    "        z = \"lambda u: 1\"\n",
    "    elif k == 1:\n",
    "        z = \"lambda u: u\"\n",
    "    else:\n",
    "        m = k / 2\n",
    "        if odd(k):\n",
    "            if m == 0:\n",
    "                z = \"lambda u: 1\"\n",
    "            elif m == 1:\n",
    "                z = \"lambda u: u * u * u\"\n",
    "            else:\n",
    "                z = \"lambda u: (lambda fu, u: fu * fu * u)((%s)(u), u)\" % F(m)\n",
    "        else:\n",
    "            if m == 0:\n",
    "                z = \"lambda u: 1\"\n",
    "            elif m == 1:\n",
    "                z = \"lambda u: u * u\"\n",
    "            else:\n",
    "                z = \"lambda u: (lambda u: u * u)((%s)(u))\" % F(m)\n",
    "    return z\n",
    "    \n",
    "source = F(5)\n",
    "print source\n",
    "eval(source)(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def F(k):\n",
    "    if k == 0:\n",
    "        z = \"lambda u: 1\"\n",
    "    elif k == 1:\n",
    "        z = \"lambda u: u\"\n",
    "    else:\n",
    "        m = k / 2\n",
    "        if m == 0:\n",
    "            z = \"lambda u: 1\"\n",
    "        \n",
    "        elif odd(k):\n",
    "            if m == 1:\n",
    "                z = \"lambda u: u * u * u\"\n",
    "            else:\n",
    "                z = \"lambda u: (lambda fu, u: fu * fu * u)((%s)(u), u)\" % F(m)\n",
    "        else:\n",
    "            if m == 1:\n",
    "                z = \"lambda u: u * u\"\n",
    "            else:\n",
    "                z = \"lambda u: (lambda u: u * u)((%s)(u))\" % F(m)\n",
    "    return z\n",
    "    \n",
    "source = F(5)\n",
    "print source\n",
    "eval(source)(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "for n in range(7):\n",
    "    source = F(n)\n",
    "    print n, '%2i' % eval(source)(2), source"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So that gets pretty good, eh?\n",
    "\n",
    "\n",
    "But looking back at the definition in Joy, it doesn't seem easy to directly apply this technique to Joy code:\n",
    "\n",
    "    Ft == [over] dip *\n",
    "    Fb == [[sqr] dip 2 //] dip\n",
    "    Fw == [pop odd] [Ft] [] ifte Fb\n",
    "     F == 1 [pop] [Fw] while popopd\n",
    "\n",
    "\n",
    "But a direct translation of the Python code..?\n",
    "\n",
    "\n",
    "    F == [\n",
    "      [[0 =] [pop 1]]\n",
    "      [[1 =] []]\n",
    "      [_F.0]\n",
    "      ] cond\n",
    "\n",
    "    _F.0 == dup 2 // [\n",
    "      [[0 =]     [pop 1]]\n",
    "      [[pop odd] _F.1]\n",
    "      [_F.2]\n",
    "      ] cond\n",
    "\n",
    "    _F.1 == [1 =] [pop [dup dup * *]] [popd F [dupdip over * *] cons] ifte\n",
    "    _F.2 == [1 =] [pop [dup *]]       [popd F [i dup *]         cons] ifte\n",
    "\n",
    "\n",
    "Try it:\n",
    "\n",
    "    5 F\n",
    "    5 [ [[0 =] [pop 1]] [[1 =] []] [_F.0] ] cond\n",
    "    5 _F.0\n",
    "    5 dup 2 // [ [[0 =] [pop 1]] [[pop odd] _F.1] [_F.2] ] cond\n",
    "    5 5 2 //   [ [[0 =] [pop 1]] [[pop odd] _F.1] [_F.2] ] cond\n",
    "\n",
    "    5 2 [ [[0 =] [pop 1]] [[pop odd] _F.1] [_F.2] ] cond\n",
    "    5 2 _F.1\n",
    "    5 2 [1 =] [popop [dup dup * *]] [popd F [dupdip over * *] cons] ifte\n",
    "    5 2                              popd F [dupdip over * *] cons\n",
    "      2                                   F [dupdip over * *] cons\n",
    "\n",
    "    2 F [dupdip over * *] cons\n",
    "\n",
    "    2 F\n",
    "    2 [ [[0 =] [pop 1]] [[1 =] []] [_F.0] ] cond\n",
    "    2 _F.0\n",
    "    2 dup 2 // [ [[0 =] [pop 1]] [[pop odd] _F.1] [_F.2] ] cond\n",
    "    2 2 2 // [ [[0 =] [pop 1]] [[pop odd] _F.1] [_F.2] ] cond\n",
    "    2 1 [ [[0 =] [pop 1]] [[pop odd] _F.1] [_F.2] ] cond\n",
    "    2 1 _F.2\n",
    "    2 1 [1 =] [popop [dup *]] [popd F [i dup *] cons] ifte\n",
    "    2 1 popop [dup *]\n",
    "    [dup *]\n",
    "\n",
    "\n",
    "    2 F     [dupdip over * *] cons\n",
    "    [dup *] [dupdip over * *] cons\n",
    "    [[dup *] dupdip over * *]\n",
    "\n",
    "And here it is in action:\n",
    "\n",
    "    2 [[dup *] dupdip over * *] i\n",
    "    2  [dup *] dupdip over * *\n",
    "    2   dup *  2      over * *\n",
    "    2   2   *  2      over * *\n",
    "    4          2      over * *\n",
    "    4          2      4    * *\n",
    "    4          8             *\n",
    "    32\n",
    "\n",
    "\n",
    "\n",
    "So, it works, but in this case the results of the partial evaluation are more elegant.\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Try it with `hylomorphism()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hylomorphism(c, F, P, G):\n",
    "    '''Return a hylomorphism function H.'''\n",
    "\n",
    "    def H(a):\n",
    "        if P(a):\n",
    "            result = c\n",
    "        else:\n",
    "            b, aa = G(a)\n",
    "            result = F(b, H(aa))\n",
    "        return result\n",
    "\n",
    "    return H"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### First, curry\n",
    "\n",
    "With abuse of syntax:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hylomorphism(c):\n",
    "    return lambda F: lambda P: lambda G: lambda a: (\n",
    "        if P(a):\n",
    "            result = c\n",
    "        else:\n",
    "            b, aa = G(a)\n",
    "            result = F(b)(H(aa))\n",
    "        return result\n",
    "    )\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### lambda lowering\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hylomorphism(c):\n",
    "    def r(a):\n",
    "        def rr(P):\n",
    "            if P(a):\n",
    "                return lambda F: lambda G: c\n",
    "            return lambda F: lambda G: (\n",
    "                    b, aa = G(a)\n",
    "                    return F(b)(H(aa))\n",
    "                )\n",
    "        return rr\n",
    "    return r\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### expression lifting\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hylomorphism(c):\n",
    "    def r(a):\n",
    "        def rr(P):\n",
    "            def rrr(G):\n",
    "                if P(a):\n",
    "                    return lambda F: c\n",
    "                b, aa = G(a)\n",
    "                H = hylomorphism(c)(aa)(P)(G)\n",
    "                return lambda F: F(b)(H(F))\n",
    "            return rrr\n",
    "        return rr\n",
    "    return r\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### quoted\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hylomorphism(c):\n",
    "    def r(a):\n",
    "        def rr(P):\n",
    "            def rrr(G):\n",
    "                if P(a):\n",
    "                    return \"lambda F: %s\" % (c,)\n",
    "                b, aa = G(a)\n",
    "                H = hylomorphism(c)(aa)(P)(G)\n",
    "                return \"lambda F: F(%(b)s)((%(H)s)(F))\" % locals()\n",
    "            return rrr\n",
    "        return rr\n",
    "    return r\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "hylomorphism(0)(3)(lambda n: n == 0)(lambda n: (n-1, n-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def F(a):\n",
    "    def _F(b):\n",
    "        print a, b\n",
    "        return a + b\n",
    "    return _F\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "F(2)(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "eval(hylomorphism(0)(5)(lambda n: n == 0)(lambda n: (n-1, n-1)))(F)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "eval(hylomorphism([])(5)(lambda n: n == 0)(lambda n: (n-1, n-1)))(lambda a: lambda b: [a] + b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "hylomorphism(0)([1, 2, 3])(lambda n: not n)(lambda n: (n[0], n[1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "hylomorphism([])([1, 2, 3])(lambda n: not n)(lambda n: (n[1:], n[1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "eval(hylomorphism([])([1, 2, 3])(lambda n: not n)(lambda n: (n[1:], n[1:])))(lambda a: lambda b: [a] + b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hylomorphism(c):\n",
    "    return lambda a: lambda P: (\n",
    "        if P(a):\n",
    "            result = lambda F: lambda G: c\n",
    "        else:\n",
    "            result = lambda F: lambda G: (\n",
    "                b, aa = G(a)\n",
    "                return F(b)(H(aa))\n",
    "            )\n",
    "        return result\n",
    "    )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hylomorphism(c):\n",
    "    return lambda a: (\n",
    "        lambda F: lambda P: lambda G: c\n",
    "        if P(a) else\n",
    "        lambda F: lambda P: lambda G: (\n",
    "            b, aa = G(a)\n",
    "            return F(b)(H(aa))\n",
    "        )\n",
    "    )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hylomorphism(c):\n",
    "    return lambda a: lambda G: (\n",
    "        lambda F: lambda P: c\n",
    "        if P(a) else\n",
    "        b, aa = G(a)\n",
    "        lambda F: lambda P: F(b)(H(aa))\n",
    "    )\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}