{ "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 }