{ "cells": [ { "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 <=" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [] } ], "source": [ "[_p [abs] ii <=] inscribe" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "23 -18" ] } ], "source": [ "clear 23 -18" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 23 -18 • _p\n", " 23 -18 • [abs] ii <=\n", "23 -18 [abs] • ii <=\n", " 23 • abs -18 abs <=\n", " 23 • -18 abs <=\n", " 23 -18 • abs <=\n", " 23 18 • <=\n", " false • \n", "\n", "false" ] } ], "source": [ "[_p] trace" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [] } ], "source": [ "clear" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Short-Circuiting Boolean Combinators\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": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [] } ], "source": [ "[&& [nullary] cons [nullary [false]] dip branch] inscribe\n", "[|| [nullary] cons [nullary] dip [true] branch] inscribe" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "false" ] } ], "source": [ "clear \n", "[true] [false] &&" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "false" ] } ], "source": [ "clear \n", "[false] [true] &&" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "true" ] } ], "source": [ "clear \n", "[true] [false] ||" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "true" ] } ], "source": [ "clear \n", "[false] [true] ||" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [] } ], "source": [ "clear" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Translating the Conditionals\n", "\n", "Given those, we can define `x != y || x >= 0` as:\n", "\n", " _a == [!=] [pop 0 >=] ||" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [] } ], "source": [ "[_a [!=] [pop 0 >=] ||] inscribe" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "And `(abs(x) <= abs(y) && (x != y || x >= 0))` as:\n", "\n", " _b == [_p] [_a] &&" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [] } ], "source": [ "[_b [_p] [_a] &&] inscribe" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It's a little rough, but, as I say, with a little familiarity it becomes\n", "legible." ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "23 -18" ] } ], "source": [ "clear 23 -18" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 23 -18 • _b\n", " 23 -18 • [_p] [_a] &&\n", " 23 -18 [_p] • [_a] &&\n", " 23 -18 [_p] [_a] • &&\n", " 23 -18 [_p] [_a] • [nullary] cons [nullary [false]] dip branch\n", " 23 -18 [_p] [_a] [nullary] • cons [nullary [false]] dip branch\n", " 23 -18 [_p] [[_a] nullary] • [nullary [false]] dip branch\n", "23 -18 [_p] [[_a] nullary] [nullary [false]] • dip branch\n", " 23 -18 [_p] • nullary [false] [[_a] nullary] branch\n", " 23 -18 [_p] • [stack] dinfrirst [false] [[_a] nullary] branch\n", " 23 -18 [_p] [stack] • dinfrirst [false] [[_a] nullary] branch\n", " 23 -18 [_p] [stack] • dip infrst [false] [[_a] nullary] branch\n", " 23 -18 • stack [_p] infrst [false] [[_a] nullary] branch\n", " 23 -18 [-18 23] • [_p] infrst [false] [[_a] nullary] branch\n", " 23 -18 [-18 23] [_p] • infrst [false] [[_a] nullary] branch\n", " 23 -18 [-18 23] [_p] • infra first [false] [[_a] nullary] branch\n", " 23 -18 • _p [-18 23] swaack first [false] [[_a] nullary] branch\n", " 23 -18 • [abs] ii <= [-18 23] swaack first [false] [[_a] nullary] branch\n", " 23 -18 [abs] • ii <= [-18 23] swaack first [false] [[_a] nullary] branch\n", " 23 • abs -18 abs <= [-18 23] swaack first [false] [[_a] nullary] branch\n", " 23 • -18 abs <= [-18 23] swaack first [false] [[_a] nullary] branch\n", " 23 -18 • abs <= [-18 23] swaack first [false] [[_a] nullary] branch\n", " 23 18 • <= [-18 23] swaack first [false] [[_a] nullary] branch\n", " false • [-18 23] swaack first [false] [[_a] nullary] branch\n", " false [-18 23] • swaack first [false] [[_a] nullary] branch\n", " 23 -18 [false] • first [false] [[_a] nullary] branch\n", " 23 -18 false • [false] [[_a] nullary] branch\n", " 23 -18 false [false] • [[_a] nullary] branch\n", " 23 -18 false [false] [[_a] nullary] • branch\n", " 23 -18 • false\n", " 23 -18 false • \n", "\n", "23 -18 false" ] } ], "source": [ "[_b] trace" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [] } ], "source": [ "clear" ] }, { "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": [ "## 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" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [] } ], "source": [ "[spiral_next\n", "\n", "[_b]\n", "[[ !-] [[++]] [[--]] ifte dip]\n", "[[pop !-] [--] [++] ifte ]\n", "ifte\n", "\n", "] inscribe" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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": "markdown", "metadata": {}, "source": [ "Let's try it out:" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0 0" ] } ], "source": [ "clear 0 0" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 0" ] } ], "source": [ "spiral_next" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 -1" ] } ], "source": [ "spiral_next" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0 -1" ] } ], "source": [ "spiral_next" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "-1 -1" ] } ], "source": [ "spiral_next" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "-1 0" ] } ], "source": [ "spiral_next" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "-1 1" ] } ], "source": [ "spiral_next" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0 1" ] } ], "source": [ "spiral_next" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 1" ] } ], "source": [ "spiral_next" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2 1" ] } ], "source": [ "spiral_next" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2 0" ] } ], "source": [ "spiral_next" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2 -1" ] } ], "source": [ "spiral_next" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2 -2" ] } ], "source": [ "spiral_next" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 -2" ] } ], "source": [ "spiral_next" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0 -2" ] } ], "source": [ "spiral_next" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "-1 -2" ] } ], "source": [ "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:" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " [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 ++] • codi reco\n", "[0 [dup ++] codireco] 0 [dup ++] • cons dip reco\n", "[0 [dup ++] codireco] [0 dup ++] • dip reco\n", " • 0 dup ++ [0 [dup ++] codireco] reco\n", " 0 • dup ++ [0 [dup ++] codireco] reco\n", " 0 0 • ++ [0 [dup ++] codireco] reco\n", " 0 1 • [0 [dup ++] codireco] reco\n", " 0 1 [0 [dup ++] codireco] • reco\n", " 0 1 [0 [dup ++] codireco] • rest cons\n", " 0 1 [[dup ++] codireco] • cons\n", " 0 [1 [dup ++] codireco] • \n", "\n", "0 [1 [dup ++] codireco]" ] } ], "source": [ "clear\n", "\n", "[0 [dup ++] codireco] [x] trace" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [] } ], "source": [ "clear" ] }, { "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": 35, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0 1]" ] } ], "source": [ "[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": "code", "execution_count": 36, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [] } ], "source": [ "clear" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Here it is in action:" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0 0] [0 1] [-1 1] [-1 0]" ] } ], "source": [ "[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.\n", "\n", "Or you can leave out `dup` and let the value stay in the generator until you want it:" ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[2 4]" ] } ], "source": [ "clear\n", "\n", "[0 0] [[spiral_next] infra] make_generator 50 [x] times first" ] }, { "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_Pa == [abs] ii <=\n", " _spn_Pb == [!=] [pop 0 >=] ||\n", " _spn_P == [_spn_Pa] [_spn_Pb] &&\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.)" ] } ], "metadata": { "kernelspec": { "display_name": "Joypy", "language": "", "name": "thun" }, "language_info": { "file_extension": ".joy", "mimetype": "text/plain", "name": "Joy" } }, "nbformat": 4, "nbformat_minor": 2 }