docs/Square_Spiral.md

   1 # Square Spiral Example Joy Code
   2
   3
   4 Here is the example of Joy code from the `README` file:
   5
   6     [[[abs]ii <=][[<>][pop !-]||]&&][[!-][[++]][[--]]ifte dip][[pop !-][--][++]ifte]ifte
   7
   8 It might seem unreadable but with a little familiarity it becomes just as
   9 legible as any other notation.  Some layout helps:
  10
  11     [   [[abs] ii <=]
  12         [
  13             [<>] [pop !-] ||
  14         ] &&
  15     ]
  16     [[    !-] [[++]] [[--]] ifte dip]
  17     [[pop !-]  [--]   [++]  ifte    ]
  18     ifte
  19
  20 This function accepts two integers on the stack and increments or
  21 decrements one of them such that the new pair of numbers is the next
  22 coordinate pair in a square spiral (like the kind used to construct an
  23 Ulam Spiral).
  24
  25
  26
  27 ## Original Form
  28
  29 It's adapted from [the original code on StackOverflow](https://stackoverflow.com/questions/398299/looping-in-a-spiral/31864777#31864777):
  30
  31
  32 > If all you're trying to do is generate the first N points in the spiral
  33 > (without the original problem's constraint of masking to an N x M
  34 > region), the code becomes very simple:
  35
  36     void spiral(const int N)
  37     {
  38         int x = 0;
  39         int y = 0;
  40         for(int i = 0; i < N; ++i)
  41         {
  42             cout << x << '\t' << y << '\n';
  43             if(abs(x) <= abs(y) && (x != y || x >= 0))
  44                 x += ((y >= 0) ? 1 : -1);
  45             else
  46                 y += ((x >= 0) ? -1 : 1);
  47         }
  48     }
  49
  50 ## Translation to Joy
  51
  52 I'm going to make a function that take two ints (`x` and `y`) and
  53 generates the next pair, we'll turn it into a generator later using the
  54 `x` combinator.
  55
  56 ### First Boolean Predicate
  57
  58 We need a function that computes `abs(x) <= abs(y)`, we can use `ii` to
  59 apply `abs` to both values and then compare them
  60 with `<=`:
  61
  62     [abs] ii <=
  63
  64
  65 ```Joy
  66 [_p [abs] ii <=] inscribe
  67 ```
  68
  69
  70
  71
  72 ```Joy
  73 clear 23 -18
  74 ```
  75
  76     23 -18
  77
  78
  79 ```Joy
  80 [_p] trace
  81 ```
  82
  83           23 -18 • _p
  84           23 -18 • [abs] ii <=
  85     23 -18 [abs] • ii <=
  86               23 • abs -18 abs <=
  87               23 • -18 abs <=
  88           23 -18 • abs <=
  89            23 18 • <=
  90            false •
  91
  92     false
  93
  94
  95 ```Joy
  96 clear
  97 ```
  98
  99
 100
 101 ### Short-Circuiting Boolean Combinators
 102
 103 I've defined two short-circuiting Boolean combinators `&&` and `||` that
 104 each accept two quoted predicate programs, run the first, and
 105 conditionally run the second only if required (to compute the final
 106 Boolean value).  They run their predicate arguments `nullary`.
 107
 108
 109 ```Joy
 110 [&& [nullary] cons [nullary [false]] dip branch] inscribe
 111 [|| [nullary] cons [nullary] dip [true] branch] inscribe
 112 ```
 113
 114
 115
 116
 117 ```Joy
 118 clear
 119 [true] [false] &&
 120 ```
 121
 122     false
 123
 124
 125 ```Joy
 126 clear
 127 [false] [true] &&
 128 ```
 129
 130     false
 131
 132
 133 ```Joy
 134 clear
 135 [true] [false] ||
 136 ```
 137
 138     true
 139
 140
 141 ```Joy
 142 clear
 143 [false] [true] ||
 144 ```
 145
 146     true
 147
 148
 149 ```Joy
 150 clear
 151 ```
 152
 153
 154
 155 ### Translating the Conditionals
 156
 157 Given those, we can define `x != y || x >= 0` as:
 158
 159     _a == [!=] [pop 0 >=] ||
 160
 161
 162 ```Joy
 163 [_a [!=] [pop 0 >=] ||] inscribe
 164 ```
 165
 166
 167
 168 And `(abs(x) <= abs(y) && (x != y || x >= 0))` as:
 169
 170     _b == [_p] [_a] &&
 171
 172
 173 ```Joy
 174 [_b [_p] [_a] &&] inscribe
 175 ```
 176
 177
 178
 179 It's a little rough, but, as I say, with a little familiarity it becomes
 180 legible.
 181
 182
 183 ```Joy
 184 clear 23 -18
 185 ```
 186
 187     23 -18
 188
 189
 190 ```Joy
 191 [_b] trace
 192 ```
 193
 194                                           23 -18 • _b
 195                                           23 -18 • [_p] [_a] &&
 196                                      23 -18 [_p] • [_a] &&
 197                                 23 -18 [_p] [_a] • &&
 198                                 23 -18 [_p] [_a] • [nullary] cons [nullary [false]] dip branch
 199                       23 -18 [_p] [_a] [nullary] • cons [nullary [false]] dip branch
 200                       23 -18 [_p] [[_a] nullary] • [nullary [false]] dip branch
 201     23 -18 [_p] [[_a] nullary] [nullary [false]] • dip branch
 202                                      23 -18 [_p] • nullary [false] [[_a] nullary] branch
 203                                      23 -18 [_p] • [stack] dinfrirst [false] [[_a] nullary] branch
 204                              23 -18 [_p] [stack] • dinfrirst [false] [[_a] nullary] branch
 205                              23 -18 [_p] [stack] • dip infrst [false] [[_a] nullary] branch
 206                                           23 -18 • stack [_p] infrst [false] [[_a] nullary] branch
 207                                  23 -18 [-18 23] • [_p] infrst [false] [[_a] nullary] branch
 208                             23 -18 [-18 23] [_p] • infrst [false] [[_a] nullary] branch
 209                             23 -18 [-18 23] [_p] • infra first [false] [[_a] nullary] branch
 210                                           23 -18 • _p [-18 23] swaack first [false] [[_a] nullary] branch
 211                                           23 -18 • [abs] ii <= [-18 23] swaack first [false] [[_a] nullary] branch
 212                                     23 -18 [abs] • ii <= [-18 23] swaack first [false] [[_a] nullary] branch
 213                                               23 • abs -18 abs <= [-18 23] swaack first [false] [[_a] nullary] branch
 214                                               23 • -18 abs <= [-18 23] swaack first [false] [[_a] nullary] branch
 215                                           23 -18 • abs <= [-18 23] swaack first [false] [[_a] nullary] branch
 216                                            23 18 • <= [-18 23] swaack first [false] [[_a] nullary] branch
 217                                            false • [-18 23] swaack first [false] [[_a] nullary] branch
 218                                   false [-18 23] • swaack first [false] [[_a] nullary] branch
 219                                   23 -18 [false] • first [false] [[_a] nullary] branch
 220                                     23 -18 false • [false] [[_a] nullary] branch
 221                             23 -18 false [false] • [[_a] nullary] branch
 222              23 -18 false [false] [[_a] nullary] • branch
 223                                           23 -18 • false
 224                                     23 -18 false •
 225
 226     23 -18 false
 227
 228
 229 ```Joy
 230 clear
 231 ```
 232
 233
 234
 235 ### The Increment / Decrement Branches
 236
 237 Turning to the branches of the main `if` statement:
 238
 239     x += ((y >= 0) ? 1 : -1);
 240
 241 Rewrite as a hybrid (pseudo-code) `ifte` expression:
 242
 243     [y >= 0] [x += 1] [X -= 1] ifte
 244
 245 Change each C phrase to Joy code:
 246
 247     [0 >=] [[++] dip] [[--] dip] ifte
 248
 249 Factor out the dip from each branch:
 250
 251     [0 >=] [[++]] [[--]] ifte dip
 252
 253 Similar logic applies to the other branch:
 254
 255     y += ((x >= 0) ? -1 : 1);
 256
 257     [x >= 0] [y -= 1] [y += 1] ifte
 258
 259     [pop 0 >=] [--] [++] ifte
 260
 261 ## Putting the Pieces Together
 262
 263 We can assemble the three functions we just defined in quotes and give
 264 them them to the `ifte` combinator.  With some arrangement to show off
 265 the symmetry of the two branches, we have:
 266
 267     [[[abs] ii <=] [[<>] [pop !-] ||] &&]
 268     [[    !-] [[++]] [[--]] ifte dip]
 269     [[pop !-]  [--]   [++]  ifte    ]
 270     ifte
 271
 272
 273 ```Joy
 274 [spiral_next
 275
 276 [_b]
 277 [[    !-] [[++]] [[--]] ifte dip]
 278 [[pop !-]  [--]   [++]  ifte    ]
 279 ifte
 280
 281 ] inscribe
 282 ```
 283
 284
 285
 286 As I was writing this up I realized that, since the `&&` combinator
 287 doesn't consume the stack (below its quoted args), I can unquote the
 288 predicate, swap the branches, and use the `branch` combinator instead of
 289 `ifte`:
 290
 291     [[abs] ii <=] [[<>] [pop !-] ||] &&
 292     [[pop !-]  [--]   [++]  ifte    ]
 293     [[    !-] [[++]] [[--]] ifte dip]
 294     branch
 295
 296 Let's try it out:
 297
 298
 299 ```Joy
 300 clear 0 0
 301 ```
 302
 303     0 0
 304
 305
 306 ```Joy
 307 spiral_next
 308 ```
 309
 310     1 0
 311
 312
 313 ```Joy
 314 spiral_next
 315 ```
 316
 317     1 -1
 318
 319
 320 ```Joy
 321 spiral_next
 322 ```
 323
 324     0 -1
 325
 326
 327 ```Joy
 328 spiral_next
 329 ```
 330
 331     -1 -1
 332
 333
 334 ```Joy
 335 spiral_next
 336 ```
 337
 338     -1 0
 339
 340
 341 ```Joy
 342 spiral_next
 343 ```
 344
 345     -1 1
 346
 347
 348 ```Joy
 349 spiral_next
 350 ```
 351
 352     0 1
 353
 354
 355 ```Joy
 356 spiral_next
 357 ```
 358
 359     1 1
 360
 361
 362 ```Joy
 363 spiral_next
 364 ```
 365
 366     2 1
 367
 368
 369 ```Joy
 370 spiral_next
 371 ```
 372
 373     2 0
 374
 375
 376 ```Joy
 377 spiral_next
 378 ```
 379
 380     2 -1
 381
 382
 383 ```Joy
 384 spiral_next
 385 ```
 386
 387     2 -2
 388
 389
 390 ```Joy
 391 spiral_next
 392 ```
 393
 394     1 -2
 395
 396
 397 ```Joy
 398 spiral_next
 399 ```
 400
 401     0 -2
 402
 403
 404 ```Joy
 405 spiral_next
 406 ```
 407
 408     -1 -2
 409
 410 ## Turning it into a Generator with `x`
 411
 412 It can be used with the x combinator to make a kind of generator for
 413 spiral square coordinates.
 414
 415
 416 We can use `codireco` to make a generator
 417
 418     codireco == cons dip rest cons
 419
 420 It will look like this:
 421
 422     [value [F] codireco]
 423
 424 Here's a trace of how it works:
 425
 426
 427 ```Joy
 428 clear
 429
 430 [0 [dup ++] codireco] [x] trace
 431 ```
 432
 433                [0 [dup ++] codireco] • x
 434                [0 [dup ++] codireco] • 0 [dup ++] codireco
 435              [0 [dup ++] codireco] 0 • [dup ++] codireco
 436     [0 [dup ++] codireco] 0 [dup ++] • codireco
 437     [0 [dup ++] codireco] 0 [dup ++] • codi reco
 438     [0 [dup ++] codireco] 0 [dup ++] • cons dip reco
 439     [0 [dup ++] codireco] [0 dup ++] • dip reco
 440                                      • 0 dup ++ [0 [dup ++] codireco] reco
 441                                    0 • dup ++ [0 [dup ++] codireco] reco
 442                                  0 0 • ++ [0 [dup ++] codireco] reco
 443                                  0 1 • [0 [dup ++] codireco] reco
 444            0 1 [0 [dup ++] codireco] • reco
 445            0 1 [0 [dup ++] codireco] • rest cons
 446              0 1 [[dup ++] codireco] • cons
 447              0 [1 [dup ++] codireco] •
 448
 449     0 [1 [dup ++] codireco]
 450
 451
 452 ```Joy
 453 clear
 454 ```
 455
 456
 457
 458 But first we have to change the `spiral_next` function to work on a
 459 quoted pair of integers, and leave a copy of the pair on the stack.
 460 From:
 461
 462        y x spiral_next
 463     ---------------------
 464             y' x'
 465
 466 to:
 467
 468        [x y] [spiral_next] infra
 469     -------------------------------
 470                [x' y']
 471
 472
 473 ```Joy
 474 [0 0] [spiral_next] infra
 475 ```
 476
 477     [0 1]
 478
 479 So our generator is:
 480
 481     [[x y] [dup [spiral_next] infra] codireco]
 482
 483 Or rather:
 484
 485     [[0 0] [dup [spiral_next] infra] codireco]
 486
 487 There is a function `make_generator` that will build the generator for us
 488 out of the value and stepper function:
 489
 490        [0 0] [dup [spiral_next] infra] make_generator
 491     ----------------------------------------------------
 492          [[0 0] [dup [spiral_next] infra] codireco]
 493
 494
 495 ```Joy
 496 clear
 497 ```
 498
 499
 500
 501 Here it is in action:
 502
 503
 504 ```Joy
 505 [0 0] [dup [spiral_next] infra] make_generator x x x x pop
 506 ```
 507
 508     [0 0] [0 1] [-1 1] [-1 0]
 509
 510 Four `x` combinators, four pairs of coordinates.
 511
 512 Or you can leave out `dup` and let the value stay in the generator until you want it:
 513
 514
 515 ```Joy
 516 clear
 517
 518 [0 0] [[spiral_next] infra] make_generator 50 [x] times first
 519 ```
 520
 521     [2 4]
 522
 523 ## Conclusion
 524
 525 So that's an example of Joy code.  It's a straightforward translation of
 526 the original.  It's a little long for a single definition, you might
 527 break it up like so:
 528
 529     _spn_Pa == [abs] ii <=
 530     _spn_Pb == [!=] [pop 0 >=] ||
 531     _spn_P  == [_spn_Pa] [_spn_Pb] &&
 532
 533     _spn_T == [    !-] [[++]] [[--]] ifte dip
 534     _spn_E == [pop !-]  [--]   [++]  ifte
 535
 536     spiral_next == _spn_P [_spn_E] [_spn_T] branch
 537
 538 This way it's easy to see that the function is a branch with two
 539 quasi-symmetrical paths.
 540
 541 We then used this function to make a simple generator of coordinate
 542 pairs, where the next pair in the series can be generated at any time by
 543 using the `x` combinator on the generator (which is just a quoted
 544 expression containing a copy of the current pair and the "stepper
 545 function" to generate the next pair from that.)