| Révision | 384d391175afce9b3e42fec458d2eba3284c5bf1 (tree) |
|---|---|
| l'heure | 2021-12-01 14:00:26 |
| Auteur |  Simon Forman <sforman@hush...> |
| Commiter | Simon Forman |
Switch to Joy kernel.
docs/Recursion_Combinators.ipynb (diff)| @@ -1,21 +1,20 @@ | ||
| 1 | 1 | { |
| 2 | 2 | "cells": [ |
| 3 | 3 | { |
| 4 | - "cell_type": "code", | |
| 5 | - "execution_count": 1, | |
| 6 | - "metadata": {}, | |
| 7 | - "outputs": [], | |
| 8 | - "source": [ | |
| 9 | - "from notebook_preamble import D, DefinitionWrapper, J, V, define" | |
| 10 | - ] | |
| 11 | - }, | |
| 12 | - { | |
| 13 | 4 | "cell_type": "markdown", |
| 14 | 5 | "metadata": {}, |
| 15 | 6 | "source": [ |
| 16 | 7 | "# Recursion Combinators\n", |
| 17 | 8 | "\n", |
| 18 | - "This article describes the `genrec` combinator, how to use it, and several generic specializations.\n", | |
| 9 | + "This article describes the `genrec` combinator and how to use it, then several generic specializations.\n", | |
| 10 | + "\n", | |
| 11 | + "## General Recursive Function\n", | |
| 12 | + "\n", | |
| 13 | + "In Joy recursive functions are defined by four quoted programs and the `genrec` combinator.\n", | |
| 14 | + "\n", | |
| 15 | + " F == [if] [then] [rec1] [rec2] genrec\n", | |
| 16 | + "\n", | |
| 17 | + "This can be thought of as transforming into an \"if..then..else\" expression using the `ifte` combinator and containing a quoted copy of itself in the \"else\" branch:\n", | |
| 19 | 18 | "\n", |
| 20 | 19 | " [if] [then] [rec1] [rec2] genrec\n", |
| 21 | 20 | " ---------------------------------------------------------------------\n", |
| @@ -33,130 +32,123 @@ | ||
| 33 | 32 | "the combinator are again pushed onto the stack bundled up in a quoted\n", |
| 34 | 33 | "form. Then the rec2-part is executed, where it will find the bundled\n", |
| 35 | 34 | "form. Typically it will then execute the bundled form, either with i or\n", |
| 36 | - "with app2, or some other combinator.\"" | |
| 37 | - ] | |
| 38 | - }, | |
| 39 | - { | |
| 40 | - "cell_type": "markdown", | |
| 41 | - "metadata": {}, | |
| 42 | - "source": [ | |
| 35 | + "with app2, or some other combinator.\"\n", | |
| 36 | + "\n", | |
| 43 | 37 | "## Designing Recursive Functions\n", |
| 44 | - "The way to design one of these is to fix your base case and \n", | |
| 45 | - "test and then treat `R1` and `R2` as an else-part \"sandwiching\"\n", | |
| 46 | - "a quotation of the whole function.\n", | |
| 38 | + "\n", | |
| 39 | + "Fix your base case and test functions and then treat `R1` and `R2` as an else-part \"sandwiching\" a quotation of the whole function.\n", | |
| 47 | 40 | "\n", |
| 48 | 41 | "For example, given a (general recursive) function `F`:\n", |
| 49 | 42 | "\n", |
| 50 | - " F == [I] [T] [R1] [R2] genrec\n", | |
| 51 | - " == [I] [T] [R1 [F] R2] ifte\n", | |
| 43 | + " F == [P] [T] [R1] [R2] genrec\n", | |
| 44 | + " == [P] [T] [R1 [F] R2] ifte\n", | |
| 52 | 45 | "\n", |
| 53 | - "If the `[I]` predicate is false you must derive `R1` and `R2` from:\n", | |
| 46 | + "Derive `R1` and `R2` from:\n", | |
| 54 | 47 | "\n", |
| 55 | 48 | " ... R1 [F] R2\n", |
| 56 | 49 | "\n", |
| 57 | - "Set the stack arguments in front and figure out what `R1` and `R2`\n", | |
| 58 | - "have to do to apply the quoted `[F]` in the proper way." | |
| 59 | - ] | |
| 60 | - }, | |
| 61 | - { | |
| 62 | - "cell_type": "markdown", | |
| 63 | - "metadata": {}, | |
| 64 | - "source": [ | |
| 65 | - "## Primitive Recursive Functions\n", | |
| 66 | - "Primitive recursive functions are those where `R2 == i`.\n", | |
| 50 | + "Set the stack arguments in front and figure out what `R1` and `R2` have to do to apply the quoted `[F]` in the proper way.\n", | |
| 67 | 51 | "\n", |
| 68 | - " P == [I] [T] [R] primrec\n", | |
| 69 | - " == [I] [T] [R [P] i] ifte\n", | |
| 70 | - " == [I] [T] [R P] ifte" | |
| 71 | - ] | |
| 72 | - }, | |
| 73 | - { | |
| 74 | - "cell_type": "markdown", | |
| 75 | - "metadata": {}, | |
| 76 | - "source": [ | |
| 77 | 52 | "## [Hylomorphism](https://en.wikipedia.org/wiki/Hylomorphism_%28computer_science%29)\n", |
| 78 | - "A [hylomorphism](https://en.wikipedia.org/wiki/Hylomorphism_%28computer_science%29) is a recursive function `H :: A -> C` that converts a value of type `A` into a value of type `C` by means of:\n", | |
| 79 | 53 | "\n", |
| 80 | - "- A generator `G :: A -> (B, A)`\n", | |
| 81 | - "- A combiner `F :: (B, C) -> C`\n", | |
| 82 | - "- A predicate `P :: A -> Bool` to detect the base case\n", | |
| 83 | - "- A base case value `c :: C`\n", | |
| 54 | + "A [hylomorphism](https://en.wikipedia.org/wiki/Hylomorphism_%28computer_science%29) is a recursive function `H` that converts a value of type `A` into a value of type `C` by means of:\n", | |
| 55 | + "\n", | |
| 56 | + "- A generator `G` from `A` to `(B, A)`\n", | |
| 57 | + "- A combiner `Q` from `(B, C)` to `C`\n", | |
| 58 | + "- A predicate `P` from `A` to `Bool` to detect the base case\n", | |
| 59 | + "- A base case value `c` of type `C`, and\n", | |
| 84 | 60 | "- Recursive calls (zero or more); it has a \"call stack in the form of a cons list\".\n", |
| 85 | 61 | "\n", |
| 86 | - "It may be helpful to see this function implemented in imperative Python code." | |
| 87 | - ] | |
| 88 | - }, | |
| 89 | - { | |
| 90 | - "cell_type": "code", | |
| 91 | - "execution_count": 2, | |
| 92 | - "metadata": {}, | |
| 93 | - "outputs": [], | |
| 94 | - "source": [ | |
| 95 | - "def hylomorphism(c, F, P, G):\n", | |
| 96 | - " '''Return a hylomorphism function H.'''\n", | |
| 62 | + "It may be helpful to see this function implemented in pseudocode (Python).\n", | |
| 97 | 63 | "\n", |
| 98 | - " def H(a):\n", | |
| 99 | - " if P(a):\n", | |
| 100 | - " result = c\n", | |
| 101 | - " else:\n", | |
| 64 | + " def hylomorphism(c, Q, P, G):\n", | |
| 65 | + " '''Return a hylomorphism function H.'''\n", | |
| 66 | + "\n", | |
| 67 | + " def H(a):\n", | |
| 68 | + " if P(a):\n", | |
| 69 | + " return c\n", | |
| 102 | 70 | " b, aa = G(a)\n", |
| 103 | - " result = F(b, H(aa)) # b is stored in the stack frame during recursive call to H().\n", | |
| 104 | - " return result\n", | |
| 71 | + " return Q(b, H(aa))\n", | |
| 72 | + "\n", | |
| 73 | + " return H\n", | |
| 105 | 74 | "\n", |
| 106 | - " return H" | |
| 107 | - ] | |
| 108 | - }, | |
| 109 | - { | |
| 110 | - "cell_type": "markdown", | |
| 111 | - "metadata": {}, | |
| 112 | - "source": [ | |
| 113 | 75 | "Cf. [\"Bananas, Lenses, & Barbed Wire\"](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125)\n", |
| 114 | 76 | "\n", |
| 115 | - "Note that during evaluation of `H()` the intermediate `b` values are stored in the Python call stack. This is what is meant by \"call stack in the form of a cons list\"." | |
| 116 | - ] | |
| 117 | - }, | |
| 118 | - { | |
| 119 | - "cell_type": "markdown", | |
| 120 | - "metadata": {}, | |
| 121 | - "source": [ | |
| 77 | + "Note that during evaluation of `H()` the intermediate `b` values are stored in the Python call stack. This is what is meant by \"call stack in the form of a cons list\".\n", | |
| 78 | + "\n", | |
| 122 | 79 | "## Hylomorphism in Joy\n", |
| 80 | + "\n", | |
| 81 | + " a H\n", | |
| 82 | + " ---------\n", | |
| 83 | + " c\n", | |
| 84 | + "\n", | |
| 123 | 85 | "We can define a combinator `hylomorphism` that will make a hylomorphism combinator `H` from constituent parts.\n", |
| 124 | 86 | "\n", |
| 125 | - " H == [P] c [G] [F] hylomorphism\n", | |
| 87 | + " H == [P] c [G] [Q] hylomorphism\n", | |
| 126 | 88 | "\n", |
| 127 | 89 | "The function `H` is recursive, so we start with `ifte` and set the else-part to\n", |
| 128 | - "some function `J` that will contain a quoted copy of `H`. (The then-part just\n", | |
| 129 | - "discards the leftover `a` and replaces it with the base case value `c`.)\n", | |
| 90 | + "some function `J` that will contain a quoted copy of `H`.\n", | |
| 91 | + "The then-part just discards the leftover `a` and replaces it with the base case value `c`:\n", | |
| 130 | 92 | "\n", |
| 131 | 93 | " H == [P] [pop c] [J] ifte\n", |
| 132 | 94 | "\n", |
| 133 | 95 | "The else-part `J` gets just the argument `a` on the stack.\n", |
| 134 | 96 | "\n", |
| 135 | 97 | " a J\n", |
| 136 | - " a G The first thing to do is use the generator G\n", | |
| 137 | - " aa b which produces b and a new aa\n", | |
| 138 | - " aa b [H] dip we recur with H on the new aa\n", | |
| 139 | - " aa H b F and run F on the result.\n", | |
| 140 | 98 | "\n", |
| 141 | - "This gives us a definition for `J`.\n", | |
| 99 | + "The first thing to do is use the generator `G` which produces values `b` and a new `aa`:\n", | |
| 100 | + "\n", | |
| 101 | + " a G\n", | |
| 102 | + " ----------\n", | |
| 103 | + " aa b\n", | |
| 104 | + "\n", | |
| 105 | + "So:\n", | |
| 106 | + "\n", | |
| 107 | + " J == G J′\n", | |
| 108 | + "\n", | |
| 109 | + "Then we recur with `H` on `aa`:\n", | |
| 110 | + "\n", | |
| 111 | + " aa b [H] dip\n", | |
| 112 | + " ------------------\n", | |
| 113 | + " aa H b\n", | |
| 114 | + " ------------------\n", | |
| 115 | + " cc b\n", | |
| 116 | + "\n", | |
| 117 | + "So:\n", | |
| 118 | + "\n", | |
| 119 | + " J′ == [H] dip J″\n", | |
| 120 | + "\n", | |
| 121 | + "And run `Q` on the result:\n", | |
| 122 | + "\n", | |
| 123 | + " cc b Q\n", | |
| 124 | + " ------------\n", | |
| 125 | + " c\n", | |
| 126 | + "So:\n", | |
| 142 | 127 | "\n", |
| 143 | - " J == G [H] dip F\n", | |
| 128 | + " J″ == Q\n", | |
| 144 | 129 | "\n", |
| 145 | - "Plug it in and convert to genrec.\n", | |
| 130 | + "Summing up:\n", | |
| 146 | 131 | "\n", |
| 147 | - " H == [P] [pop c] [G [H] dip F] ifte\n", | |
| 148 | - " H == [P] [pop c] [G] [dip F] genrec\n", | |
| 132 | + " J == G J′\n", | |
| 133 | + " J′ == [H] dip J″\n", | |
| 134 | + " J″ == Q\n", | |
| 135 | + "\n", | |
| 136 | + "This gives us a definition for `J`:\n", | |
| 137 | + "\n", | |
| 138 | + " J == G [H] dip Q\n", | |
| 139 | + "\n", | |
| 140 | + "Plug it in and convert to genrec:\n", | |
| 141 | + "\n", | |
| 142 | + " H == [P] [pop c] [ J ] ifte\n", | |
| 143 | + " [P] [pop c] [G [H] dip Q] ifte\n", | |
| 144 | + " [P] [pop c] [G] [dip Q] genrec\n", | |
| 149 | 145 | "\n", |
| 150 | 146 | "This is the form of a hylomorphism in Joy, which nicely illustrates that\n", |
| 151 | 147 | "it is a simple specialization of the general recursion combinator.\n", |
| 152 | 148 | "\n", |
| 153 | - " H == [P] c [G] [F] hylomorphism == [P] [pop c] [G] [dip F] genrec" | |
| 154 | - ] | |
| 155 | - }, | |
| 156 | - { | |
| 157 | - "cell_type": "markdown", | |
| 158 | - "metadata": {}, | |
| 159 | - "source": [ | |
| 149 | + " [P] c [G] [Q] hylomorphism\n", | |
| 150 | + " [P] [pop c] [G] [dip Q] genrec\n", | |
| 151 | + "\n", | |
| 160 | 152 | "## Derivation of `hylomorphism` combinator\n", |
| 161 | 153 | "\n", |
| 162 | 154 | "Now we just need to derive a definition that builds the `genrec` arguments\n", |
| @@ -172,8 +164,6 @@ | ||
| 172 | 164 | "- Use `unit` to dequote `c`.\n", |
| 173 | 165 | "- Use `dipd` to untangle `[unit [pop] swoncat]` from the givens.\n", |
| 174 | 166 | "\n", |
| 175 | - "So:\n", | |
| 176 | - "\n", | |
| 177 | 167 | " H == [P] [pop c] [G] [dip F] genrec\n", |
| 178 | 168 | " [P] [c] [pop] swoncat [G] [F] [dip] swoncat genrec\n", |
| 179 | 169 | " [P] c unit [pop] swoncat [G] [F] [dip] swoncat genrec\n", |
| @@ -187,11 +177,17 @@ | ||
| 187 | 177 | }, |
| 188 | 178 | { |
| 189 | 179 | "cell_type": "code", |
| 190 | - "execution_count": 3, | |
| 180 | + "execution_count": 1, | |
| 191 | 181 | "metadata": {}, |
| 192 | - "outputs": [], | |
| 182 | + "outputs": [ | |
| 183 | + { | |
| 184 | + "name": "stdout", | |
| 185 | + "output_type": "stream", | |
| 186 | + "text": [] | |
| 187 | + } | |
| 188 | + ], | |
| 193 | 189 | "source": [ |
| 194 | - "define('hylomorphism == [unit [pop] swoncat] dipd [dip] swoncat genrec')" | |
| 190 | + "[hylomorphism [unit [pop] swoncat] dipd [dip] swoncat genrec] inscribe" | |
| 195 | 191 | ] |
| 196 | 192 | }, |
| 197 | 193 | { |
| @@ -211,11 +207,17 @@ | ||
| 211 | 207 | }, |
| 212 | 208 | { |
| 213 | 209 | "cell_type": "code", |
| 214 | - "execution_count": 4, | |
| 210 | + "execution_count": 2, | |
| 215 | 211 | "metadata": {}, |
| 216 | - "outputs": [], | |
| 212 | + "outputs": [ | |
| 213 | + { | |
| 214 | + "name": "stdout", | |
| 215 | + "output_type": "stream", | |
| 216 | + "text": [] | |
| 217 | + } | |
| 218 | + ], | |
| 217 | 219 | "source": [ |
| 218 | - "define('triangular_number == [1 <=] 0 [-- dup] [+] hylomorphism')" | |
| 220 | + "[triangular_number [1 <=] 0 [-- dup] [+] hylomorphism] inscribe" | |
| 219 | 221 | ] |
| 220 | 222 | }, |
| 221 | 223 | { |
| @@ -227,36 +229,45 @@ | ||
| 227 | 229 | }, |
| 228 | 230 | { |
| 229 | 231 | "cell_type": "code", |
| 230 | - "execution_count": 5, | |
| 232 | + "execution_count": 3, | |
| 231 | 233 | "metadata": {}, |
| 232 | 234 | "outputs": [ |
| 233 | 235 | { |
| 234 | 236 | "name": "stdout", |
| 235 | 237 | "output_type": "stream", |
| 236 | 238 | "text": [ |
| 237 | - "10\n" | |
| 239 | + "10" | |
| 238 | 240 | ] |
| 239 | 241 | } |
| 240 | 242 | ], |
| 241 | 243 | "source": [ |
| 242 | - "J('5 triangular_number')" | |
| 244 | + "5 triangular_number" | |
| 243 | 245 | ] |
| 244 | 246 | }, |
| 245 | 247 | { |
| 246 | 248 | "cell_type": "code", |
| 247 | - "execution_count": 6, | |
| 249 | + "execution_count": 4, | |
| 248 | 250 | "metadata": {}, |
| 249 | 251 | "outputs": [ |
| 250 | 252 | { |
| 251 | 253 | "name": "stdout", |
| 252 | 254 | "output_type": "stream", |
| 253 | 255 | "text": [ |
| 254 | - "[0 0 1 3 6 10 15]\n" | |
| 256 | + "[0 0 1 3 6 10 15 21]" | |
| 255 | 257 | ] |
| 256 | 258 | } |
| 257 | 259 | ], |
| 258 | 260 | "source": [ |
| 259 | - "J('[0 1 2 3 4 5 6] [triangular_number] map')" | |
| 261 | + "clear\n", | |
| 262 | + "\n", | |
| 263 | + "[0 1 2 3 4 5 6 7] [triangular_number] map" | |
| 264 | + ] | |
| 265 | + }, | |
| 266 | + { | |
| 267 | + "cell_type": "markdown", | |
| 268 | + "metadata": {}, | |
| 269 | + "source": [ | |
| 270 | + "Neat!" | |
| 260 | 271 | ] |
| 261 | 272 | }, |
| 262 | 273 | { |
| @@ -407,6 +418,7 @@ | ||
| 407 | 418 | "metadata": {}, |
| 408 | 419 | "source": [ |
| 409 | 420 | "### `range` et. al.\n", |
| 421 | + "\n", | |
| 410 | 422 | "An example of an anamorphism is the `range` function which generates the list of integers from 0 to *n* - 1 given *n*.\n", |
| 411 | 423 | "\n", |
| 412 | 424 | "Each of the above variations can be used to make four slightly different `range` functions." |
| @@ -423,16 +435,37 @@ | ||
| 423 | 435 | }, |
| 424 | 436 | { |
| 425 | 437 | "cell_type": "code", |
| 426 | - "execution_count": 7, | |
| 438 | + "execution_count": 5, | |
| 427 | 439 | "metadata": {}, |
| 428 | - "outputs": [], | |
| 440 | + "outputs": [ | |
| 441 | + { | |
| 442 | + "name": "stdout", | |
| 443 | + "output_type": "stream", | |
| 444 | + "text": [] | |
| 445 | + } | |
| 446 | + ], | |
| 429 | 447 | "source": [ |
| 430 | - "define('range == [0 <=] [] [-- dup] [swons] hylomorphism')" | |
| 448 | + "clear " | |
| 431 | 449 | ] |
| 432 | 450 | }, |
| 433 | 451 | { |
| 434 | 452 | "cell_type": "code", |
| 435 | - "execution_count": 8, | |
| 453 | + "execution_count": 6, | |
| 454 | + "metadata": {}, | |
| 455 | + "outputs": [ | |
| 456 | + { | |
| 457 | + "name": "stdout", | |
| 458 | + "output_type": "stream", | |
| 459 | + "text": [] | |
| 460 | + } | |
| 461 | + ], | |
| 462 | + "source": [ | |
| 463 | + "[range [0 <=] [] [-- dup] [swons] hylomorphism] inscribe" | |
| 464 | + ] | |
| 465 | + }, | |
| 466 | + { | |
| 467 | + "cell_type": "code", | |
| 468 | + "execution_count": 7, | |
| 436 | 469 | "metadata": { |
| 437 | 470 | "scrolled": false |
| 438 | 471 | }, |
| @@ -441,12 +474,12 @@ | ||
| 441 | 474 | "name": "stdout", |
| 442 | 475 | "output_type": "stream", |
| 443 | 476 | "text": [ |
| 444 | - "[4 3 2 1 0]\n" | |
| 477 | + "[4 3 2 1 0]" | |
| 445 | 478 | ] |
| 446 | 479 | } |
| 447 | 480 | ], |
| 448 | 481 | "source": [ |
| 449 | - "J('5 range')" | |
| 482 | + "5 range" | |
| 450 | 483 | ] |
| 451 | 484 | }, |
| 452 | 485 | { |
| @@ -454,17 +487,38 @@ | ||
| 454 | 487 | "metadata": {}, |
| 455 | 488 | "source": [ |
| 456 | 489 | "#### `range` with `H2`\n", |
| 457 | - " H2 == c swap [P] [pop] [G [F] dip] primrec\n", | |
| 458 | - " == [] swap [0 <=] [pop] [-- dup [swons] dip] primrec" | |
| 490 | + " H2 == c swap [P] [pop] [G [F] dip] tailrec\n", | |
| 491 | + " == [] swap [0 <=] [pop] [-- dup [swons] dip] tailrec" | |
| 492 | + ] | |
| 493 | + }, | |
| 494 | + { | |
| 495 | + "cell_type": "code", | |
| 496 | + "execution_count": 8, | |
| 497 | + "metadata": {}, | |
| 498 | + "outputs": [ | |
| 499 | + { | |
| 500 | + "name": "stdout", | |
| 501 | + "output_type": "stream", | |
| 502 | + "text": [] | |
| 503 | + } | |
| 504 | + ], | |
| 505 | + "source": [ | |
| 506 | + "clear " | |
| 459 | 507 | ] |
| 460 | 508 | }, |
| 461 | 509 | { |
| 462 | 510 | "cell_type": "code", |
| 463 | 511 | "execution_count": 9, |
| 464 | 512 | "metadata": {}, |
| 465 | - "outputs": [], | |
| 513 | + "outputs": [ | |
| 514 | + { | |
| 515 | + "name": "stdout", | |
| 516 | + "output_type": "stream", | |
| 517 | + "text": [] | |
| 518 | + } | |
| 519 | + ], | |
| 466 | 520 | "source": [ |
| 467 | - "define('range_reverse == [] swap [0 <=] [pop] [-- dup [swons] dip] primrec')" | |
| 521 | + "[range_reverse [] swap [0 <=] [pop] [-- dup [swons] dip] tailrec] inscribe" | |
| 468 | 522 | ] |
| 469 | 523 | }, |
| 470 | 524 | { |
| @@ -478,12 +532,12 @@ | ||
| 478 | 532 | "name": "stdout", |
| 479 | 533 | "output_type": "stream", |
| 480 | 534 | "text": [ |
| 481 | - "[0 1 2 3 4]\n" | |
| 535 | + "[0 1 2 3 4]" | |
| 482 | 536 | ] |
| 483 | 537 | } |
| 484 | 538 | ], |
| 485 | 539 | "source": [ |
| 486 | - "J('5 range_reverse')" | |
| 540 | + "5 range_reverse" | |
| 487 | 541 | ] |
| 488 | 542 | }, |
| 489 | 543 | { |
| @@ -499,14 +553,35 @@ | ||
| 499 | 553 | "cell_type": "code", |
| 500 | 554 | "execution_count": 11, |
| 501 | 555 | "metadata": {}, |
| 502 | - "outputs": [], | |
| 556 | + "outputs": [ | |
| 557 | + { | |
| 558 | + "name": "stdout", | |
| 559 | + "output_type": "stream", | |
| 560 | + "text": [] | |
| 561 | + } | |
| 562 | + ], | |
| 503 | 563 | "source": [ |
| 504 | - "define('ranger == [0 <=] [pop []] [[--] dupdip] [dip swons] genrec')" | |
| 564 | + "clear " | |
| 505 | 565 | ] |
| 506 | 566 | }, |
| 507 | 567 | { |
| 508 | 568 | "cell_type": "code", |
| 509 | 569 | "execution_count": 12, |
| 570 | + "metadata": {}, | |
| 571 | + "outputs": [ | |
| 572 | + { | |
| 573 | + "name": "stdout", | |
| 574 | + "output_type": "stream", | |
| 575 | + "text": [] | |
| 576 | + } | |
| 577 | + ], | |
| 578 | + "source": [ | |
| 579 | + "[ranger [0 <=] [pop []] [[--] dupdip] [dip swons] genrec] inscribe" | |
| 580 | + ] | |
| 581 | + }, | |
| 582 | + { | |
| 583 | + "cell_type": "code", | |
| 584 | + "execution_count": 13, | |
| 510 | 585 | "metadata": { |
| 511 | 586 | "scrolled": true |
| 512 | 587 | }, |
| @@ -515,12 +590,12 @@ | ||
| 515 | 590 | "name": "stdout", |
| 516 | 591 | "output_type": "stream", |
| 517 | 592 | "text": [ |
| 518 | - "[5 4 3 2 1]\n" | |
| 593 | + "[5 4 3 2 1]" | |
| 519 | 594 | ] |
| 520 | 595 | } |
| 521 | 596 | ], |
| 522 | 597 | "source": [ |
| 523 | - "J('5 ranger')" | |
| 598 | + "5 ranger" | |
| 524 | 599 | ] |
| 525 | 600 | }, |
| 526 | 601 | { |
| @@ -534,16 +609,37 @@ | ||
| 534 | 609 | }, |
| 535 | 610 | { |
| 536 | 611 | "cell_type": "code", |
| 537 | - "execution_count": 13, | |
| 612 | + "execution_count": 14, | |
| 538 | 613 | "metadata": {}, |
| 539 | - "outputs": [], | |
| 614 | + "outputs": [ | |
| 615 | + { | |
| 616 | + "name": "stdout", | |
| 617 | + "output_type": "stream", | |
| 618 | + "text": [] | |
| 619 | + } | |
| 620 | + ], | |
| 540 | 621 | "source": [ |
| 541 | - "define('ranger_reverse == [] swap [0 <=] [pop] [[swons] dupdip --] primrec')" | |
| 622 | + "clear " | |
| 542 | 623 | ] |
| 543 | 624 | }, |
| 544 | 625 | { |
| 545 | 626 | "cell_type": "code", |
| 546 | - "execution_count": 14, | |
| 627 | + "execution_count": 15, | |
| 628 | + "metadata": {}, | |
| 629 | + "outputs": [ | |
| 630 | + { | |
| 631 | + "name": "stdout", | |
| 632 | + "output_type": "stream", | |
| 633 | + "text": [] | |
| 634 | + } | |
| 635 | + ], | |
| 636 | + "source": [ | |
| 637 | + "[ranger_reverse [] swap [0 <=] [pop] [[swons] dupdip --] tailrec] inscribe" | |
| 638 | + ] | |
| 639 | + }, | |
| 640 | + { | |
| 641 | + "cell_type": "code", | |
| 642 | + "execution_count": 16, | |
| 547 | 643 | "metadata": { |
| 548 | 644 | "scrolled": true |
| 549 | 645 | }, |
| @@ -552,19 +648,12 @@ | ||
| 552 | 648 | "name": "stdout", |
| 553 | 649 | "output_type": "stream", |
| 554 | 650 | "text": [ |
| 555 | - "[1 2 3 4 5]\n" | |
| 651 | + "[1 2 3 4 5]" | |
| 556 | 652 | ] |
| 557 | 653 | } |
| 558 | 654 | ], |
| 559 | 655 | "source": [ |
| 560 | - "J('5 ranger_reverse')" | |
| 561 | - ] | |
| 562 | - }, | |
| 563 | - { | |
| 564 | - "cell_type": "markdown", | |
| 565 | - "metadata": {}, | |
| 566 | - "source": [ | |
| 567 | - "Hopefully this illustrates the workings of the variations. For more insight you can run the cells using the `V()` function instead of the `J()` function to get a trace of the Joy evaluation." | |
| 656 | + "5 ranger_reverse" | |
| 568 | 657 | ] |
| 569 | 658 | }, |
| 570 | 659 | { |
| @@ -572,54 +661,77 @@ | ||
| 572 | 661 | "metadata": {}, |
| 573 | 662 | "source": [ |
| 574 | 663 | "## Catamorphism\n", |
| 575 | - "A catamorphism can be defined as a hylomorphism that uses `[uncons swap]` for `[G]`\n", | |
| 576 | - "and `[[] =]` (or just `[not]`) for the predicate `[P]`. A catamorphic function tears down a list term-by-term and makes some new value.\n", | |
| 664 | + "A catamorphic function tears down a list term-by-term and makes some new value.\n", | |
| 665 | + "It can be defined as a hylomorphism that uses `[uncons swap]` for `[G]`\n", | |
| 666 | + "and `[[] =]` (or just `[not]`) for the predicate `[P]`.\n", | |
| 667 | + "\n", | |
| 668 | + " C == [not] c [uncons swap] [F] hylomorphism\n", | |
| 577 | 669 | "\n", |
| 578 | - " C == [not] c [uncons swap] [F] hylomorphism" | |
| 670 | + "An example of a catamorphism is the sum function.\n", | |
| 671 | + "\n", | |
| 672 | + " sum == [not] 0 [uncons swap] [+] hylomorphism" | |
| 579 | 673 | ] |
| 580 | 674 | }, |
| 581 | 675 | { |
| 582 | 676 | "cell_type": "code", |
| 583 | - "execution_count": 15, | |
| 677 | + "execution_count": 17, | |
| 584 | 678 | "metadata": {}, |
| 585 | - "outputs": [], | |
| 679 | + "outputs": [ | |
| 680 | + { | |
| 681 | + "name": "stdout", | |
| 682 | + "output_type": "stream", | |
| 683 | + "text": [] | |
| 684 | + } | |
| 685 | + ], | |
| 586 | 686 | "source": [ |
| 587 | - "define('swuncons == uncons swap') # Awkward name." | |
| 687 | + "clear " | |
| 588 | 688 | ] |
| 589 | 689 | }, |
| 590 | 690 | { |
| 591 | - "cell_type": "markdown", | |
| 691 | + "cell_type": "code", | |
| 692 | + "execution_count": 18, | |
| 592 | 693 | "metadata": {}, |
| 694 | + "outputs": [ | |
| 695 | + { | |
| 696 | + "name": "stdout", | |
| 697 | + "output_type": "stream", | |
| 698 | + "text": [] | |
| 699 | + } | |
| 700 | + ], | |
| 593 | 701 | "source": [ |
| 594 | - "An example of a catamorphism is the sum function.\n", | |
| 595 | - "\n", | |
| 596 | - " sum == [not] 0 [swuncons] [+] hylomorphism" | |
| 702 | + "[sum [not] 0 [uncons swap] [+] hylomorphism] inscribe" | |
| 597 | 703 | ] |
| 598 | 704 | }, |
| 599 | 705 | { |
| 600 | 706 | "cell_type": "code", |
| 601 | - "execution_count": 16, | |
| 707 | + "execution_count": 19, | |
| 602 | 708 | "metadata": {}, |
| 603 | - "outputs": [], | |
| 709 | + "outputs": [ | |
| 710 | + { | |
| 711 | + "name": "stdout", | |
| 712 | + "output_type": "stream", | |
| 713 | + "text": [ | |
| 714 | + "15" | |
| 715 | + ] | |
| 716 | + } | |
| 717 | + ], | |
| 604 | 718 | "source": [ |
| 605 | - "define('sum == [not] 0 [swuncons] [+] hylomorphism')" | |
| 719 | + "[5 4 3 2 1] sum" | |
| 606 | 720 | ] |
| 607 | 721 | }, |
| 608 | 722 | { |
| 609 | 723 | "cell_type": "code", |
| 610 | - "execution_count": 17, | |
| 724 | + "execution_count": 20, | |
| 611 | 725 | "metadata": {}, |
| 612 | 726 | "outputs": [ |
| 613 | 727 | { |
| 614 | 728 | "name": "stdout", |
| 615 | 729 | "output_type": "stream", |
| 616 | - "text": [ | |
| 617 | - "15\n" | |
| 618 | - ] | |
| 730 | + "text": [] | |
| 619 | 731 | } |
| 620 | 732 | ], |
| 621 | 733 | "source": [ |
| 622 | - "J('[5 4 3 2 1] sum')" | |
| 734 | + "clear " | |
| 623 | 735 | ] |
| 624 | 736 | }, |
| 625 | 737 | { |
| @@ -632,64 +744,76 @@ | ||
| 632 | 744 | }, |
| 633 | 745 | { |
| 634 | 746 | "cell_type": "code", |
| 635 | - "execution_count": 18, | |
| 747 | + "execution_count": 21, | |
| 636 | 748 | "metadata": {}, |
| 637 | 749 | "outputs": [ |
| 638 | 750 | { |
| 639 | 751 | "name": "stdout", |
| 640 | 752 | "output_type": "stream", |
| 641 | 753 | "text": [ |
| 754 | + "\n", | |
| 755 | + "==== Help on step ====\n", | |
| 756 | + "\n", | |
| 642 | 757 | "Run a quoted program on each item in a sequence.\n", |
| 643 | 758 | "::\n", |
| 644 | 759 | "\n", |
| 645 | - " ... [] [Q] . step\n", | |
| 646 | - " -----------------------\n", | |
| 647 | - " ... .\n", | |
| 760 | + " ... [] [Q] . step\n", | |
| 761 | + " -----------------------\n", | |
| 762 | + " ... .\n", | |
| 648 | 763 | "\n", |
| 649 | 764 | "\n", |
| 650 | 765 | " ... [a] [Q] . step\n", |
| 651 | 766 | " ------------------------\n", |
| 652 | - " ... a . Q\n", | |
| 767 | + " ... a . Q\n", | |
| 653 | 768 | "\n", |
| 654 | 769 | "\n", |
| 655 | - " ... [a b c] [Q] . step\n", | |
| 656 | - " ----------------------------------------\n", | |
| 657 | - " ... a . Q [b c] [Q] step\n", | |
| 770 | + " ... [a b c] [Q] . step\n", | |
| 771 | + " ----------------------------------------\n", | |
| 772 | + " ... a . Q [b c] [Q] step\n", | |
| 658 | 773 | "\n", |
| 659 | 774 | "The step combinator executes the quotation on each member of the list\n", |
| 660 | 775 | "on top of the stack.\n", |
| 776 | + "\n", | |
| 777 | + "---- end (step)\n", | |
| 778 | + "\n", | |
| 661 | 779 | "\n" |
| 662 | 780 | ] |
| 663 | 781 | } |
| 664 | 782 | ], |
| 665 | 783 | "source": [ |
| 666 | - "J('[step] help')" | |
| 784 | + "[step] help" | |
| 667 | 785 | ] |
| 668 | 786 | }, |
| 669 | 787 | { |
| 670 | 788 | "cell_type": "code", |
| 671 | - "execution_count": 19, | |
| 789 | + "execution_count": 22, | |
| 672 | 790 | "metadata": {}, |
| 673 | - "outputs": [], | |
| 791 | + "outputs": [ | |
| 792 | + { | |
| 793 | + "name": "stdout", | |
| 794 | + "output_type": "stream", | |
| 795 | + "text": [] | |
| 796 | + } | |
| 797 | + ], | |
| 674 | 798 | "source": [ |
| 675 | - "define('sum == 0 swap [+] step')" | |
| 799 | + "[sum 0 swap [+] step] inscribe" | |
| 676 | 800 | ] |
| 677 | 801 | }, |
| 678 | 802 | { |
| 679 | 803 | "cell_type": "code", |
| 680 | - "execution_count": 20, | |
| 804 | + "execution_count": 23, | |
| 681 | 805 | "metadata": {}, |
| 682 | 806 | "outputs": [ |
| 683 | 807 | { |
| 684 | 808 | "name": "stdout", |
| 685 | 809 | "output_type": "stream", |
| 686 | 810 | "text": [ |
| 687 | - "15\n" | |
| 811 | + "15" | |
| 688 | 812 | ] |
| 689 | 813 | } |
| 690 | 814 | ], |
| 691 | 815 | "source": [ |
| 692 | - "J('[5 4 3 2 1] sum')" | |
| 816 | + "[5 4 3 2 1] sum" | |
| 693 | 817 | ] |
| 694 | 818 | }, |
| 695 | 819 | { |
| @@ -712,16 +836,37 @@ | ||
| 712 | 836 | }, |
| 713 | 837 | { |
| 714 | 838 | "cell_type": "code", |
| 715 | - "execution_count": 21, | |
| 839 | + "execution_count": 24, | |
| 716 | 840 | "metadata": {}, |
| 717 | - "outputs": [], | |
| 841 | + "outputs": [ | |
| 842 | + { | |
| 843 | + "name": "stdout", | |
| 844 | + "output_type": "stream", | |
| 845 | + "text": [] | |
| 846 | + } | |
| 847 | + ], | |
| 718 | 848 | "source": [ |
| 719 | - "define('factorial == 1 swap [1 <=] [pop] [[*] dupdip --] primrec')" | |
| 849 | + "clear" | |
| 720 | 850 | ] |
| 721 | 851 | }, |
| 722 | 852 | { |
| 723 | 853 | "cell_type": "code", |
| 724 | - "execution_count": 22, | |
| 854 | + "execution_count": 25, | |
| 855 | + "metadata": {}, | |
| 856 | + "outputs": [ | |
| 857 | + { | |
| 858 | + "name": "stdout", | |
| 859 | + "output_type": "stream", | |
| 860 | + "text": [] | |
| 861 | + } | |
| 862 | + ], | |
| 863 | + "source": [ | |
| 864 | + "[factorial 1 swap [1 <=] [pop] [[*] dupdip --] tailrec] inscribe" | |
| 865 | + ] | |
| 866 | + }, | |
| 867 | + { | |
| 868 | + "cell_type": "code", | |
| 869 | + "execution_count": 26, | |
| 725 | 870 | "metadata": { |
| 726 | 871 | "scrolled": false |
| 727 | 872 | }, |
| @@ -730,12 +875,12 @@ | ||
| 730 | 875 | "name": "stdout", |
| 731 | 876 | "output_type": "stream", |
| 732 | 877 | "text": [ |
| 733 | - "120\n" | |
| 878 | + "120" | |
| 734 | 879 | ] |
| 735 | 880 | } |
| 736 | 881 | ], |
| 737 | 882 | "source": [ |
| 738 | - "J('5 factorial')" | |
| 883 | + "5 factorial" | |
| 739 | 884 | ] |
| 740 | 885 | }, |
| 741 | 886 | { |
| @@ -748,54 +893,65 @@ | ||
| 748 | 893 | " [1 2 3] tails\n", |
| 749 | 894 | " --------------------\n", |
| 750 | 895 | " [[] [3] [2 3]]\n", |
| 751 | - " " | |
| 752 | - ] | |
| 753 | - }, | |
| 754 | - { | |
| 755 | - "cell_type": "markdown", | |
| 756 | - "metadata": {}, | |
| 757 | - "source": [ | |
| 758 | - "We can build as we go, and we want `F` to run after `G`, so we use pattern `H2`:\n", | |
| 896 | + " \n", | |
| 897 | + "\n", | |
| 898 | + "We can build as we go, and we want `Q` to run after `G`, so we use pattern `H2`:\n", | |
| 899 | + "\n", | |
| 900 | + " H2 == c swap [P] [pop] [G [Q] dip] tailrec\n", | |
| 759 | 901 | "\n", |
| 760 | - " H2 == c swap [P] [pop] [G [F] dip] primrec" | |
| 761 | - ] | |
| 762 | - }, | |
| 763 | - { | |
| 764 | - "cell_type": "markdown", | |
| 765 | - "metadata": {}, | |
| 766 | - "source": [ | |
| 767 | 902 | "We would use:\n", |
| 768 | 903 | "\n", |
| 769 | 904 | " c == []\n", |
| 770 | - " F == swons\n", | |
| 905 | + " Q == swons\n", | |
| 771 | 906 | " G == rest dup\n", |
| 772 | 907 | " P == not" |
| 773 | 908 | ] |
| 774 | 909 | }, |
| 775 | 910 | { |
| 776 | 911 | "cell_type": "code", |
| 777 | - "execution_count": 23, | |
| 912 | + "execution_count": 27, | |
| 913 | + "metadata": {}, | |
| 914 | + "outputs": [ | |
| 915 | + { | |
| 916 | + "name": "stdout", | |
| 917 | + "output_type": "stream", | |
| 918 | + "text": [] | |
| 919 | + } | |
| 920 | + ], | |
| 921 | + "source": [ | |
| 922 | + "clear" | |
| 923 | + ] | |
| 924 | + }, | |
| 925 | + { | |
| 926 | + "cell_type": "code", | |
| 927 | + "execution_count": 28, | |
| 778 | 928 | "metadata": {}, |
| 779 | - "outputs": [], | |
| 929 | + "outputs": [ | |
| 930 | + { | |
| 931 | + "name": "stdout", | |
| 932 | + "output_type": "stream", | |
| 933 | + "text": [] | |
| 934 | + } | |
| 935 | + ], | |
| 780 | 936 | "source": [ |
| 781 | - "define('tails == [] swap [not] [pop] [rest dup [swons] dip] primrec')" | |
| 937 | + "[tails [] swap [not] [pop] [rest dup [swons] dip] tailrec] inscribe" | |
| 782 | 938 | ] |
| 783 | 939 | }, |
| 784 | 940 | { |
| 785 | 941 | "cell_type": "code", |
| 786 | - "execution_count": 24, | |
| 942 | + "execution_count": 29, | |
| 787 | 943 | "metadata": {}, |
| 788 | 944 | "outputs": [ |
| 789 | 945 | { |
| 790 | 946 | "name": "stdout", |
| 791 | 947 | "output_type": "stream", |
| 792 | 948 | "text": [ |
| 793 | - "[[] [3] [2 3]]\n" | |
| 949 | + "[[] [3] [2 3]]" | |
| 794 | 950 | ] |
| 795 | 951 | } |
| 796 | 952 | ], |
| 797 | 953 | "source": [ |
| 798 | - "J('[1 2 3] tails')" | |
| 954 | + "[1 2 3] tails" | |
| 799 | 955 | ] |
| 800 | 956 | }, |
| 801 | 957 | { |
| @@ -837,21 +993,14 @@ | ||
| 837 | 993 | ], |
| 838 | 994 | "metadata": { |
| 839 | 995 | "kernelspec": { |
| 840 | - "display_name": "Python 2", | |
| 841 | - "language": "python", | |
| 842 | - "name": "python2" | |
| 996 | + "display_name": "Joypy", | |
| 997 | + "language": "", | |
| 998 | + "name": "thun" | |
| 843 | 999 | }, |
| 844 | 1000 | "language_info": { |
| 845 | - "codemirror_mode": { | |
| 846 | - "name": "ipython", | |
| 847 | - "version": 2 | |
| 848 | - }, | |
| 849 | - "file_extension": ".py", | |
| 850 | - "mimetype": "text/x-python", | |
| 851 | - "name": "python", | |
| 852 | - "nbconvert_exporter": "python", | |
| 853 | - "pygments_lexer": "ipython2", | |
| 854 | - "version": "2.7.15" | |
| 1001 | + "file_extension": ".joy", | |
| 1002 | + "mimetype": "text/plain", | |
| 1003 | + "name": "Joy" | |
| 855 | 1004 | } |
| 856 | 1005 | }, |
| 857 | 1006 | "nbformat": 4, |
Fork