Recover the square spiral example code.

[joypy/Thun.git] / docs / Square_Spiral.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from notebook_preamble import J, V, define"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Square Spiral Example Joy Code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Here is the example of Joy code from the `README` file:\n",
    "\n",
    "    [[[abs]ii <=][[<>][pop !-]||]&&][[!-][[++]][[--]]ifte dip][[pop !-][--][++]ifte]ifte\n",
    "\n",
    "It might seem unreadable but with a little familiarity it becomes just as\n",
    "legible as any other notation.  Some layout helps:\n",
    "\n",
    "    [   [[abs] ii <=]\n",
    "        [\n",
    "            [<>] [pop !-] ||\n",
    "        ] &&\n",
    "    ]\n",
    "    [[    !-] [[++]] [[--]] ifte dip]\n",
    "    [[pop !-]  [--]   [++]  ifte    ]\n",
    "    ifte\n",
    "\n",
    "This function accepts two integers on the stack and increments or\n",
    "decrements one of them such that the new pair of numbers is the next\n",
    "coordinate pair in a square spiral (like the kind used to construct an\n",
    "Ulam Spiral).  \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Original Form\n",
    "\n",
    "It's adapted from [the original code on StackOverflow](https://stackoverflow.com/questions/398299/looping-in-a-spiral/31864777#31864777):\n",
    "\n",
    "\n",
    "> If all you're trying to do is generate the first N points in the spiral\n",
    "> (without the original problem's constraint of masking to an N x M\n",
    "> region), the code becomes very simple:\n",
    "\n",
    "    void spiral(const int N)\n",
    "    {\n",
    "        int x = 0;\n",
    "        int y = 0;\n",
    "        for(int i = 0; i < N; ++i)\n",
    "        {\n",
    "            cout << x << '\\t' << y << '\\n';\n",
    "            if(abs(x) <= abs(y) && (x != y || x >= 0))\n",
    "                x += ((y >= 0) ? 1 : -1);\n",
    "            else\n",
    "                y += ((x >= 0) ? -1 : 1);\n",
    "        }\n",
    "    }"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Translation to Joy\n",
    "\n",
    "I'm going to make a function that take two ints (`x` and `y`) and\n",
    "generates the next pair, we'll turn it into a generator later using the\n",
    "`x` combinator."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### First Boolean Predicate\n",
    "\n",
    "We need a function that computes `abs(x) <= abs(y)`, we can use `ii` to\n",
    "apply `abs` to both values and then compare them\n",
    "with `<=`:\n",
    "\n",
    "    [abs] ii <=\n",
    "\n",
    "I've defined two short-circuiting Boolean combinators `&&` and `||` that\n",
    "each accept two quoted predicate programs, run the first, and\n",
    "conditionally run the second only if required (to compute the final\n",
    "Boolean value).  They run their predicate arguments `nullary`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "define('&& [nullary] cons [nullary [0]] dip branch')\n",
    "define('|| [nullary] cons [nullary] dip [1] branch')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given those, we can define `x != y || x >= 0` as:\n",
    "\n",
    "    [<>] [pop 0 >=] ||\n",
    "\n",
    "And `(abs(x) <= abs(y) && (x != y || x >= 0))` as:\n",
    "\n",
    "    [[abs] ii <=] [[<>] [pop 0 >=] ||] &&\n",
    "\n",
    "It's a little rough, but, as I say, with a little familiarity it becomes\n",
    "legible."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Increment / Decrement Branches\n",
    "\n",
    "Turning to the branches of the main `if` statement:\n",
    "\n",
    "    x += ((y >= 0) ? 1 : -1);\n",
    "\n",
    "Rewrite as a hybrid (pseudo-code) `ifte` expression:\n",
    "\n",
    "    [y >= 0] [x += 1] [X -= 1] ifte\n",
    "\n",
    "Change each C phrase to Joy code:\n",
    "\n",
    "    [0 >=] [[++] dip] [[--] dip] ifte\n",
    "\n",
    "Factor out the dip from each branch:\n",
    "\n",
    "    [0 >=] [[++]] [[--]] ifte dip\n",
    "\n",
    "Similar logic applies to the other branch:\n",
    "\n",
    "    y += ((x >= 0) ? -1 : 1);\n",
    "\n",
    "    [x >= 0] [y -= 1] [y += 1] ifte\n",
    "\n",
    "    [pop 0 >=] [--] [++] ifte"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### \"Not Negative\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "define('!- 0 >=')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Putting the Pieces Together\n",
    "\n",
    "We can assemble the three functions we just defined in quotes and give\n",
    "them them to the `ifte` combinator.  With some arrangement to show off\n",
    "the symmetry of the two branches, we have:\n",
    "\n",
    "    [[[abs] ii <=] [[<>] [pop !-] ||] &&]\n",
    "    [[    !-] [[++]] [[--]] ifte dip]\n",
    "    [[pop !-]  [--]   [++]  ifte    ]\n",
    "    ifte\n",
    "\n",
    "As I was writing this up I realized that, since the `&&` combinator\n",
    "doesn't consume the stack (below its quoted args), I can unquote the\n",
    "predicate, swap the branches, and use the `branch` combinator instead of\n",
    "`ifte`:\n",
    "\n",
    "    [[abs] ii <=] [[<>] [pop !-] ||] &&\n",
    "    [[pop !-]  [--]   [++]  ifte    ]\n",
    "    [[    !-] [[++]] [[--]] ifte dip]\n",
    "    branch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "define('spiral_next [[[abs] ii <=] [[<>] [pop !-] ||] &&] [[!-] [[++]] [[--]] ifte dip] [[pop !-] [--] [++] ifte] ifte')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's try it out:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 0\n"
     ]
    }
   ],
   "source": [
    "J('0 0 spiral_next')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 -1\n"
     ]
    }
   ],
   "source": [
    "J('1 0 spiral_next')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 -1\n"
     ]
    }
   ],
   "source": [
    "J('1 -1 spiral_next')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-1 -1\n"
     ]
    }
   ],
   "source": [
    "J('0 -1 spiral_next')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Turning it into a Generator with `x`\n",
    "\n",
    "It can be used with the x combinator to make a kind of generator for\n",
    "spiral square coordinates.\n",
    "\n",
    "\n",
    "We can use `codireco` to make a generator\n",
    "\n",
    "    codireco ::= cons dip rest cons\n",
    "\n",
    "It will look like this:\n",
    "\n",
    "    [value [F] codireco]\n",
    "\n",
    "Here's a trace of how it works:\n",
    "\n",
    "               [0 [dup ++] codireco] . x\n",
    "               [0 [dup ++] codireco] . 0 [dup ++] codireco\n",
    "             [0 [dup ++] codireco] 0 . [dup ++] codireco\n",
    "    [0 [dup ++] codireco] 0 [dup ++] . codireco\n",
    "    [0 [dup ++] codireco] 0 [dup ++] . cons dip rest cons\n",
    "    [0 [dup ++] codireco] [0 dup ++] . dip rest cons\n",
    "                                     . 0 dup ++ [0 [dup ++] codireco] rest cons\n",
    "                                   0 . dup ++ [0 [dup ++] codireco] rest cons\n",
    "                                 0 0 . ++ [0 [dup ++] codireco] rest cons\n",
    "                                 0 1 . [0 [dup ++] codireco] rest cons\n",
    "           0 1 [0 [dup ++] codireco] . rest cons\n",
    "             0 1 [[dup ++] codireco] . cons\n",
    "             0 [1 [dup ++] codireco] . "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But first we have to change the `spiral_next` function to work on a\n",
    "quoted pair of integers, and leave a copy of the pair on the stack.\n",
    "From:\n",
    "\n",
    "       y x spiral_next\n",
    "    ---------------------\n",
    "            y' x'\n",
    "\n",
    "to:\n",
    "\n",
    "       [x y] [spiral_next] infra\n",
    "    -------------------------------\n",
    "               [x' y']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0 1]\n"
     ]
    }
   ],
   "source": [
    "J('[0 0] [spiral_next] infra')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So our generator is:\n",
    "\n",
    "    [[x y] [dup [spiral_next] infra] codireco]\n",
    "\n",
    "Or rather:\n",
    "\n",
    "    [[0 0] [dup [spiral_next] infra] codireco]\n",
    "\n",
    "There is a function `make_generator` that will build the generator for us\n",
    "out of the value and stepper function:\n",
    "\n",
    "       [0 0] [dup [spiral_next] infra] make_generator\n",
    "    ----------------------------------------------------\n",
    "         [[0 0] [dup [spiral_next] infra] codireco]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here it is in action:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0 0] [0 1] [-1 1] [-1 0]\n"
     ]
    }
   ],
   "source": [
    "J('[0 0] [dup [spiral_next] infra] make_generator x x x x pop')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Four `x` combinators, four pairs of coordinates."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion\n",
    "\n",
    "So that's an example of Joy code.  It's a straightforward translation of\n",
    "the original.  It's a little long for a single definition, you might\n",
    "break it up like so:\n",
    "\n",
    "         _spn_P ::= [[abs] ii <=] [[<>] [pop !-] ||] &&\n",
    "\n",
    "         _spn_T ::= [    !-] [[++]] [[--]] ifte dip\n",
    "         _spn_E ::= [pop !-]  [--]   [++]  ifte\n",
    "\n",
    "    spiral_next ::= _spn_P [_spn_E] [_spn_T] branch\n",
    "\n",
    "This way it's easy to see that the function is a branch with two\n",
    "quasi-symmetrical paths.\n",
    "\n",
    "We then used this function to make a simple generator of coordinate\n",
    "pairs, where the next pair in the series can be generated at any time by\n",
    "using the `x` combinator on the generator (which is just a quoted\n",
    "expression containing a copy of the current pair and the \"stepper\n",
    "function\" to generate the next pair from that.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "define('_spn_P [[abs] ii <=] [[<>] [pop !-] ||] &&')\n",
    "define('_spn_T [!-] [[++]] [[--]] ifte dip')\n",
    "define('_spn_E [pop !-] [--] [++] ifte')\n",
    "define('spiral_next _spn_P [_spn_E] [_spn_T] branch')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "                                                               . 23 18 spiral_next\n",
      "                                                            23 . 18 spiral_next\n",
      "                                                         23 18 . spiral_next\n",
      "                                                         23 18 . _spn_P [_spn_E] [_spn_T] branch\n",
      "                                                         23 18 . [[abs] ii <=] [[<>] [pop !-] ||] && [_spn_E] [_spn_T] branch\n",
      "                                           23 18 [[abs] ii <=] . [[<>] [pop !-] ||] && [_spn_E] [_spn_T] branch\n",
      "                        23 18 [[abs] ii <=] [[<>] [pop !-] ||] . && [_spn_E] [_spn_T] branch\n",
      "                        23 18 [[abs] ii <=] [[<>] [pop !-] ||] . [nullary] cons [nullary [0]] dip branch [_spn_E] [_spn_T] branch\n",
      "              23 18 [[abs] ii <=] [[<>] [pop !-] ||] [nullary] . cons [nullary [0]] dip branch [_spn_E] [_spn_T] branch\n",
      "              23 18 [[abs] ii <=] [[[<>] [pop !-] ||] nullary] . [nullary [0]] dip branch [_spn_E] [_spn_T] branch\n",
      "23 18 [[abs] ii <=] [[[<>] [pop !-] ||] nullary] [nullary [0]] . dip branch [_spn_E] [_spn_T] branch\n",
      "                                           23 18 [[abs] ii <=] . nullary [0] [[[<>] [pop !-] ||] nullary] branch [_spn_E] [_spn_T] branch\n",
      "                                           23 18 [[abs] ii <=] . [stack] dinfrirst [0] [[[<>] [pop !-] ||] nullary] branch [_spn_E] [_spn_T] branch\n",
      "                                   23 18 [[abs] ii <=] [stack] . dinfrirst [0] [[[<>] [pop !-] ||] nullary] branch [_spn_E] [_spn_T] branch\n",
      "                                   23 18 [[abs] ii <=] [stack] . dip infra first [0] [[[<>] [pop !-] ||] nullary] branch [_spn_E] [_spn_T] branch\n",
      "                                                         23 18 . stack [[abs] ii <=] infra first [0] [[[<>] [pop !-] ||] nullary] branch [_spn_E] [_spn_T] branch\n",
      "                                                 23 18 [18 23] . [[abs] ii <=] infra first [0] [[[<>] [pop !-] ||] nullary] branch [_spn_E] [_spn_T] branch\n",
      "                                   23 18 [18 23] [[abs] ii <=] . infra first [0] [[[<>] [pop !-] ||] nullary] branch [_spn_E] [_spn_T] branch\n",
      "                                                         23 18 . [abs] ii <= [18 23] swaack first [0] [[[<>] [pop !-] ||] nullary] branch [_spn_E] [_spn_T] branch\n",
      "                                                   23 18 [abs] . ii <= [18 23] swaack first [0] [[[<>] [pop !-] ||] nullary] branch [_spn_E] [_spn_T] branch\n",
      "                                                   23 18 [abs] . [dip] dupdip i <= [18 23] swaack first [0] [[[<>] [pop !-] ||] nullary] branch [_spn_E] [_spn_T] branch\n",
      "                                             23 18 [abs] [dip] . dupdip i <= [18 23] swaack first [0] [[[<>] [pop !-] ||] nullary] branch [_spn_E] [_spn_T] branch\n",
      "                                                   23 18 [abs] . dip [abs] i <= [18 23] swaack first [0] [[[<>] [pop !-] ||] nullary] branch [_spn_E] [_spn_T] branch\n",
      "                                                            23 . abs 18 [abs] i <= [18 23] swaack first [0] [[[<>] [pop !-] ||] nullary] branch [_spn_E] [_spn_T] branch\n",
      "                                                            23 . 18 [abs] i <= [18 23] swaack first [0] [[[<>] [pop !-] ||] nullary] branch [_spn_E] [_spn_T] branch\n",
      "                                                         23 18 . [abs] i <= [18 23] swaack first [0] [[[<>] [pop !-] ||] nullary] branch [_spn_E] [_spn_T] branch\n",
      "                                                   23 18 [abs] . i <= [18 23] swaack first [0] [[[<>] [pop !-] ||] nullary] branch [_spn_E] [_spn_T] branch\n",
      "                                                         23 18 . abs <= [18 23] swaack first [0] [[[<>] [pop !-] ||] nullary] branch [_spn_E] [_spn_T] branch\n",
      "                                                         23 18 . <= [18 23] swaack first [0] [[[<>] [pop !-] ||] nullary] branch [_spn_E] [_spn_T] branch\n",
      "                                                         False . [18 23] swaack first [0] [[[<>] [pop !-] ||] nullary] branch [_spn_E] [_spn_T] branch\n",
      "                                                 False [18 23] . swaack first [0] [[[<>] [pop !-] ||] nullary] branch [_spn_E] [_spn_T] branch\n",
      "                                                 23 18 [False] . first [0] [[[<>] [pop !-] ||] nullary] branch [_spn_E] [_spn_T] branch\n",
      "                                                   23 18 False . [0] [[[<>] [pop !-] ||] nullary] branch [_spn_E] [_spn_T] branch\n",
      "                                               23 18 False [0] . [[[<>] [pop !-] ||] nullary] branch [_spn_E] [_spn_T] branch\n",
      "                  23 18 False [0] [[[<>] [pop !-] ||] nullary] . branch [_spn_E] [_spn_T] branch\n",
      "                                                         23 18 . 0 [_spn_E] [_spn_T] branch\n",
      "                                                       23 18 0 . [_spn_E] [_spn_T] branch\n",
      "                                              23 18 0 [_spn_E] . [_spn_T] branch\n",
      "                                     23 18 0 [_spn_E] [_spn_T] . branch\n",
      "                                                         23 18 . _spn_E\n",
      "                                                         23 18 . [pop !-] [--] [++] ifte\n",
      "                                                23 18 [pop !-] . [--] [++] ifte\n",
      "                                           23 18 [pop !-] [--] . [++] ifte\n",
      "                                      23 18 [pop !-] [--] [++] . ifte\n",
      "                                      23 18 [pop !-] [--] [++] . [nullary not] dipd branch\n",
      "                        23 18 [pop !-] [--] [++] [nullary not] . dipd branch\n",
      "                                                23 18 [pop !-] . nullary not [--] [++] branch\n",
      "                                                23 18 [pop !-] . [stack] dinfrirst not [--] [++] branch\n",
      "                                        23 18 [pop !-] [stack] . dinfrirst not [--] [++] branch\n",
      "                                        23 18 [pop !-] [stack] . dip infra first not [--] [++] branch\n",
      "                                                         23 18 . stack [pop !-] infra first not [--] [++] branch\n",
      "                                                 23 18 [18 23] . [pop !-] infra first not [--] [++] branch\n",
      "                                        23 18 [18 23] [pop !-] . infra first not [--] [++] branch\n",
      "                                                         23 18 . pop !- [18 23] swaack first not [--] [++] branch\n",
      "                                                            23 . !- [18 23] swaack first not [--] [++] branch\n",
      "                                                            23 . 0 >= [18 23] swaack first not [--] [++] branch\n",
      "                                                          23 0 . >= [18 23] swaack first not [--] [++] branch\n",
      "                                                          True . [18 23] swaack first not [--] [++] branch\n",
      "                                                  True [18 23] . swaack first not [--] [++] branch\n",
      "                                                  23 18 [True] . first not [--] [++] branch\n",
      "                                                    23 18 True . not [--] [++] branch\n",
      "                                                   23 18 False . [--] [++] branch\n",
      "                                              23 18 False [--] . [++] branch\n",
      "                                         23 18 False [--] [++] . branch\n",
      "                                                         23 18 . --\n",
      "                                                         23 17 . \n"
     ]
    }
   ],
   "source": [
    "V('23 18 spiral_next')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}