joy/library.py

   1 # -*- coding: utf-8 -*-
   2 #
   3 #    Copyright © 2014, 2015, 2017, 2018 Simon Forman
   4 #
   5 #    This file is part of Thun
   6 #
   7 #    Thun is free software: you can redistribute it and/or modify
   8 #    it under the terms of the GNU General Public License as published by
   9 #    the Free Software Foundation, either version 3 of the License, or
  10 #    (at your option) any later version.
  11 #
  12 #    Thun is distributed in the hope that it will be useful,
  13 #    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 #    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 #    GNU General Public License for more details.
  16 #
  17 #    You should have received a copy of the GNU General Public License
  18 #    along with Thun.  If not see <http://www.gnu.org/licenses/>.
  19 #
  20 '''
  21 This module contains the Joy function infrastructure and a library of
  22 functions.  Its main export is a Python function initialize() that
  23 returns a dictionary of Joy functions suitable for use with the joy()
  24 function.
  25 '''
  26 from inspect import getdoc
  27 from functools import wraps
  28 from inspect import getmembers, isfunction
  29 import operator, math
  30
  31 from .parser import text_to_expression, Symbol
  32 from .utils.stack import list_to_stack, iter_stack, pick, concat
  33 from .utils.brutal_hackery import rename_code_object
  34
  35 from .utils import generated_library as genlib
  36
  37
  38 _dictionary = {}
  39
  40
  41 def inscribe(function):
  42   '''A decorator to inscribe functions into the default dictionary.'''
  43   _dictionary[function.name] = function
  44   return function
  45
  46
  47 def initialize():
  48   '''Return a dictionary of Joy functions for use with joy().'''
  49   return _dictionary.copy()
  50
  51
  52 ALIASES = (
  53   ('add', ['+']),
  54   ('and', ['&']),
  55   ('bool', ['truthy']),
  56   ('mul', ['*']),
  57   ('truediv', ['/']),
  58   ('mod', ['%', 'rem', 'remainder', 'modulus']),
  59   ('eq', ['=']),
  60   ('ge', ['>=']),
  61   ('getitem', ['pick', 'at']),
  62   ('gt', ['>']),
  63   ('le', ['<=']),
  64   ('lshift', ['<<']),
  65   ('lt', ['<']),
  66   ('ne', ['<>', '!=']),
  67   ('rshift', ['>>']),
  68   ('sub', ['-']),
  69   ('xor', ['^']),
  70   ('succ', ['++']),
  71   ('pred', ['--']),
  72   ('rolldown', ['roll<']),
  73   ('rollup', ['roll>']),
  74   ('id', ['•']),
  75   )
  76
  77
  78 def add_aliases(D, A):
  79   '''
  80   Given a dict and a iterable of (name, [alias, ...]) pairs, create
  81   additional entries in the dict mapping each alias to the named function
  82   if it's in the dict.  Aliases for functions not in the dict are ignored.
  83   '''
  84   for name, aliases in A:
  85     try:
  86       F = D[name]
  87     except KeyError:
  88       continue
  89     for alias in aliases:
  90       D[alias] = F
  91
  92
  93 definitions = ('''\
  94 of == swap at
  95 product == 1 swap [*] step
  96 flatten == [] swap [concat] step
  97 quoted == [unit] dip
  98 unquoted == [i] dip
  99 enstacken == stack [clear] dip
 100 disenstacken == ? [uncons ?] loop pop
 101 ? == dup truthy
 102 dinfrirst == dip infra first
 103 nullary == [stack] dinfrirst
 104 unary == nullary popd
 105 binary == nullary [popop] dip
 106 ternary == unary [popop] dip
 107 pam == [i] map
 108 run == [] swap infra
 109 sqr == dup mul
 110 size == 0 swap [pop ++] step
 111 cleave == [i] app2 [popd] dip
 112 average == [sum 1.0 *] [size] cleave /
 113 gcd == 1 [tuck modulus dup 0 >] loop pop
 114 least_fraction == dup [gcd] infra [div] concat map
 115 *fraction == [uncons] dip uncons [swap] dip concat [*] infra [*] dip cons
 116 *fraction0 == concat [[swap] dip * [*] dip] infra
 117 down_to_zero == [0 >] [dup --] while
 118 range_to_zero == unit [down_to_zero] infra
 119 anamorphism == [pop []] swap [dip swons] genrec
 120 range == [0 <=] [1 - dup] anamorphism
 121 while == swap [nullary] cons dup dipd concat loop
 122 dupdipd == dup dipd
 123 primrec == [i] genrec
 124 step_zero == 0 roll> step
 125 codireco == cons dip rest cons
 126 make_generator == [codireco] ccons
 127 '''
 128 # ifte == [nullary not] dipd branch
 129 # ifte == [nullary] dipd swap branch
 130
 131 ##ccons == cons cons
 132 ##unit == [] cons
 133 ##second == rest first
 134 ##third == rest rest first
 135 ##swons == swap cons
 136 ##swoncat == swap concat
 137
 138 ##Zipper
 139 ##z-down == [] swap uncons swap
 140 ##z-up == swons swap shunt
 141 ##z-right == [swons] cons dip uncons swap
 142 ##z-left == swons [uncons swap] dip swap
 143
 144 ##Quadratic Formula
 145 ##divisor == popop 2 *
 146 ##minusb == pop neg
 147 ##radical == swap dup * rollup * 4 * - sqrt
 148 ##root1 == + swap /
 149 ##root2 == - swap /
 150 ##q0 == [[divisor] [minusb] [radical]] pam
 151 ##q1 == [[root1] [root2]] pam
 152 ##quadratic == [q0] ternary i [q1] ternary
 153
 154 # Project Euler
 155 ##'''\
 156 ##PE1.1 == + dup [+] dip
 157 ##PE1.2 == dup [3 & PE1.1] dip 2 >>
 158 ##PE1.3 == 14811 swap [PE1.2] times pop
 159 ##PE1 == 0 0 66 [7 PE1.3] times 4 PE1.3 pop
 160 ##'''
 161 #PE1.2 == [PE1.1] step
 162 #PE1 == 0 0 66 [[3 2 1 3 1 2 3] PE1.2] times [3 2 1 3] PE1.2 pop
 163 )
 164
 165
 166 def FunctionWrapper(f):
 167   '''Set name attribute.'''
 168   if not f.__doc__:
 169     raise ValueError('Function %s must have doc string.' % f.__name__)
 170   f.name = f.__name__.rstrip('_')  # Don't shadow builtins.
 171   return f
 172
 173
 174 def SimpleFunctionWrapper(f):
 175   '''
 176   Wrap functions that take and return just a stack.
 177   '''
 178   @FunctionWrapper
 179   @wraps(f)
 180   @rename_code_object(f.__name__)
 181   def inner(stack, expression, dictionary):
 182     return f(stack), expression, dictionary
 183   return inner
 184
 185
 186 def BinaryBuiltinWrapper(f):
 187   '''
 188   Wrap functions that take two arguments and return a single result.
 189   '''
 190   @FunctionWrapper
 191   @wraps(f)
 192   @rename_code_object(f.__name__)
 193   def inner(stack, expression, dictionary):
 194     (a, (b, stack)) = stack
 195     result = f(b, a)
 196     return (result, stack), expression, dictionary
 197   return inner
 198
 199
 200 def UnaryBuiltinWrapper(f):
 201   '''
 202   Wrap functions that take one argument and return a single result.
 203   '''
 204   @FunctionWrapper
 205   @wraps(f)
 206   @rename_code_object(f.__name__)
 207   def inner(stack, expression, dictionary):
 208     (a, stack) = stack
 209     result = f(a)
 210     return (result, stack), expression, dictionary
 211   return inner
 212
 213
 214 class DefinitionWrapper(object):
 215   '''
 216   Provide implementation of defined functions, and some helper methods.
 217   '''
 218
 219   def __init__(self, name, body_text, doc=None):
 220     self.name = self.__name__ = name
 221     self.body = text_to_expression(body_text)
 222     self._body = tuple(iter_stack(self.body))
 223     self.__doc__ = doc or body_text
 224     self._compiled = None
 225
 226   def __call__(self, stack, expression, dictionary):
 227     if self._compiled:
 228       return self._compiled(stack, expression, dictionary)
 229     expression = list_to_stack(self._body, expression)
 230     return stack, expression, dictionary
 231
 232   @classmethod
 233   def parse_definition(class_, defi):
 234     '''
 235     Given some text describing a Joy function definition parse it and
 236     return a DefinitionWrapper.
 237     '''
 238     name, proper, body_text = (n.strip() for n in defi.partition('=='))
 239     if not proper:
 240       raise ValueError('Definition %r failed' % (defi,))
 241     return class_(name, body_text)
 242
 243   @classmethod
 244   def add_definitions(class_, defs, dictionary):
 245     '''
 246     Scan multi-line string defs for definitions and add them to the
 247     dictionary.
 248     '''
 249     for definition in _text_to_defs(defs):
 250       class_.add_def(definition, dictionary)
 251
 252   @classmethod
 253   def add_def(class_, definition, dictionary):
 254     '''
 255     Add the definition to the dictionary.
 256     '''
 257     F = class_.parse_definition(definition)
 258     dictionary[F.name] = F
 259
 260
 261 def _text_to_defs(text):
 262   return (line.strip() for line in text.splitlines() if '==' in line)
 263
 264
 265 #
 266 # Functions
 267 #
 268
 269
 270 # Load the auto-generated primitives into the dictionary.
 271 for name, primitive in getmembers(genlib, isfunction):
 272   inscribe(SimpleFunctionWrapper(primitive))
 273
 274
 275 @inscribe
 276 @SimpleFunctionWrapper
 277 def parse(stack):
 278   '''Parse the string on the stack to a Joy expression.'''
 279   text, stack = stack
 280   expression = text_to_expression(text)
 281   return expression, stack
 282
 283
 284 @inscribe
 285 @SimpleFunctionWrapper
 286 def getitem(stack):
 287   '''
 288   ::
 289
 290     getitem == drop first
 291
 292   Expects an integer and a quote on the stack and returns the item at the
 293   nth position in the quote counting from 0.
 294   ::
 295
 296        [a b c d] 0 getitem
 297     -------------------------
 298                 a
 299
 300   '''
 301   n, (Q, stack) = stack
 302   return pick(Q, n), stack
 303
 304
 305 @inscribe
 306 @SimpleFunctionWrapper
 307 def drop(stack):
 308   '''
 309   ::
 310
 311     drop == [rest] times
 312
 313   Expects an integer and a quote on the stack and returns the quote with
 314   n items removed off the top.
 315   ::
 316
 317        [a b c d] 2 drop
 318     ----------------------
 319            [c d]
 320
 321   '''
 322   n, (Q, stack) = stack
 323   while n > 0:
 324     try:
 325       _, Q = Q
 326     except ValueError:
 327       raise IndexError
 328     n -= 1
 329   return Q, stack
 330
 331
 332 @inscribe
 333 @SimpleFunctionWrapper
 334 def take(stack):
 335   '''
 336   Expects an integer and a quote on the stack and returns the quote with
 337   just the top n items in reverse order (because that's easier and you can
 338   use reverse if needed.)
 339   ::
 340
 341        [a b c d] 2 take
 342     ----------------------
 343            [b a]
 344
 345   '''
 346   n, (Q, stack) = stack
 347   x = ()
 348   while n > 0:
 349     try:
 350       item, Q = Q
 351     except ValueError:
 352       raise IndexError
 353     x = item, x
 354     n -= 1
 355   return x, stack
 356
 357
 358 @inscribe
 359 @SimpleFunctionWrapper
 360 def choice(stack):
 361   '''
 362   Use a Boolean value to select one of two items.
 363   ::
 364
 365         A B False choice
 366      ----------------------
 367                A
 368
 369
 370         A B True choice
 371      ---------------------
 372                B
 373
 374   Currently Python semantics are used to evaluate the "truthiness" of the
 375   Boolean value (so empty string, zero, etc. are counted as false, etc.)
 376   '''
 377   (if_, (then, (else_, stack))) = stack
 378   return then if if_ else else_, stack
 379
 380
 381 @inscribe
 382 @SimpleFunctionWrapper
 383 def select(stack):
 384   '''
 385   Use a Boolean value to select one of two items from a sequence.
 386   ::
 387
 388         [A B] False select
 389      ------------------------
 390                 A
 391
 392
 393         [A B] True select
 394      -----------------------
 395                B
 396
 397   The sequence can contain more than two items but not fewer.
 398   Currently Python semantics are used to evaluate the "truthiness" of the
 399   Boolean value (so empty string, zero, etc. are counted as false, etc.)
 400   '''
 401   (flag, (choices, stack)) = stack
 402   (else_, (then, _)) = choices
 403   return then if flag else else_, stack
 404
 405
 406 @inscribe
 407 @SimpleFunctionWrapper
 408 def max_(S):
 409   '''Given a list find the maximum.'''
 410   tos, stack = S
 411   return max(iter_stack(tos)), stack
 412
 413
 414 @inscribe
 415 @SimpleFunctionWrapper
 416 def min_(S):
 417   '''Given a list find the minimum.'''
 418   tos, stack = S
 419   return min(iter_stack(tos)), stack
 420
 421
 422 @inscribe
 423 @SimpleFunctionWrapper
 424 def sum_(S):
 425   '''Given a quoted sequence of numbers return the sum.
 426
 427   sum == 0 swap [+] step
 428   '''
 429   tos, stack = S
 430   return sum(iter_stack(tos)), stack
 431
 432
 433 @inscribe
 434 @SimpleFunctionWrapper
 435 def remove(S):
 436   '''
 437   Expects an item on the stack and a quote under it and removes that item
 438   from the the quote.  The item is only removed once.
 439   ::
 440
 441        [1 2 3 1] 1 remove
 442     ------------------------
 443             [2 3 1]
 444
 445   '''
 446   (tos, (second, stack)) = S
 447   l = list(iter_stack(second))
 448   l.remove(tos)
 449   return list_to_stack(l), stack
 450
 451
 452 @inscribe
 453 @SimpleFunctionWrapper
 454 def unique(S):
 455   '''Given a list remove duplicate items.'''
 456   tos, stack = S
 457   I = list(iter_stack(tos))
 458   list_to_stack(sorted(set(I), key=I.index))
 459   return list_to_stack(sorted(set(I), key=I.index)), stack
 460
 461
 462 @inscribe
 463 @SimpleFunctionWrapper
 464 def sort_(S):
 465   '''Given a list return it sorted.'''
 466   tos, stack = S
 467   return list_to_stack(sorted(iter_stack(tos))), stack
 468
 469
 470 @inscribe
 471 @SimpleFunctionWrapper
 472 def clear(stack):
 473   '''Clear everything from the stack.
 474   ::
 475
 476        ... clear
 477     ---------------
 478
 479   '''
 480   return ()
 481
 482
 483 @inscribe
 484 @SimpleFunctionWrapper
 485 def unstack(stack):
 486   '''
 487   The unstack operator expects a list on top of the stack and makes that
 488   the stack discarding the rest of the stack.
 489   '''
 490   return stack[0]
 491
 492
 493 @inscribe
 494 @SimpleFunctionWrapper
 495 def reverse(S):
 496   '''Reverse the list on the top of the stack.
 497   ::
 498
 499     reverse == [] swap shunt
 500   '''
 501   (tos, stack) = S
 502   res = ()
 503   for term in iter_stack(tos):
 504     res = term, res
 505   return res, stack
 506
 507
 508 @inscribe
 509 @SimpleFunctionWrapper
 510 def concat_(S):
 511   '''Concatinate the two lists on the top of the stack.
 512   ::
 513
 514        [a b c] [d e f] concat
 515     ----------------------------
 516            [a b c d e f]
 517
 518 '''
 519   (tos, (second, stack)) = S
 520   return concat(second, tos), stack
 521
 522
 523 @inscribe
 524 @SimpleFunctionWrapper
 525 def shunt(stack):
 526   '''Like concat but reverses the top list into the second.
 527   ::
 528
 529     shunt == [swons] step == reverse swap concat
 530
 531        [a b c] [d e f] shunt
 532     ---------------------------
 533          [f e d a b c]
 534
 535   '''
 536   (tos, (second, stack)) = stack
 537   while tos:
 538     term, tos = tos
 539     second = term, second
 540   return second, stack
 541
 542
 543 @inscribe
 544 @SimpleFunctionWrapper
 545 def zip_(S):
 546   '''
 547   Replace the two lists on the top of the stack with a list of the pairs
 548   from each list.  The smallest list sets the length of the result list.
 549   '''
 550   (tos, (second, stack)) = S
 551   accumulator = [
 552     (a, (b, ()))
 553     for a, b in zip(iter_stack(tos), iter_stack(second))
 554     ]
 555   return list_to_stack(accumulator), stack
 556
 557
 558 @inscribe
 559 @SimpleFunctionWrapper
 560 def succ(S):
 561   '''Increment TOS.'''
 562   (tos, stack) = S
 563   return tos + 1, stack
 564
 565
 566 @inscribe
 567 @SimpleFunctionWrapper
 568 def pred(S):
 569   '''Decrement TOS.'''
 570   (tos, stack) = S
 571   return tos - 1, stack
 572
 573
 574 @inscribe
 575 @SimpleFunctionWrapper
 576 def pm(stack):
 577   '''
 578   Plus or minus
 579   ::
 580
 581        a b pm
 582     -------------
 583        a+b a-b
 584
 585   '''
 586   a, (b, stack) = stack
 587   p, m, = b + a, b - a
 588   return m, (p, stack)
 589
 590
 591 def floor(n):
 592   return int(math.floor(n))
 593
 594 floor.__doc__ = math.floor.__doc__
 595
 596
 597 @inscribe
 598 @SimpleFunctionWrapper
 599 def divmod_(S):
 600   '''
 601   divmod(x, y) -> (quotient, remainder)
 602
 603   Return the tuple (x//y, x%y).  Invariant: div*y + mod == x.
 604   '''
 605   a, (b, stack) = S
 606   d, m = divmod(a, b)
 607   return d, (m, stack)
 608
 609
 610 def sqrt(a):
 611   '''
 612   Return the square root of the number a.
 613   Negative numbers return complex roots.
 614   '''
 615   try:
 616     r = math.sqrt(a)
 617   except ValueError:
 618     assert a < 0, repr(a)
 619     r = math.sqrt(-a) * 1j
 620   return r
 621
 622
 623 #def execute(S):
 624 #  (text, stack) = S
 625 #  if isinstance(text, str):
 626 #    return run(text, stack)
 627 #  return stack
 628
 629
 630 @inscribe
 631 @SimpleFunctionWrapper
 632 def id_(stack):
 633   '''The identity function.'''
 634   return stack
 635
 636
 637 @inscribe
 638 @SimpleFunctionWrapper
 639 def void(stack):
 640   '''True if the form on TOS is void otherwise False.'''
 641   form, stack = stack
 642   return _void(form), stack
 643
 644
 645 def _void(form):
 646   return any(not _void(i) for i in iter_stack(form))
 647
 648
 649
 650 ##  transpose
 651 ##  sign
 652 ##  take
 653
 654
 655 @inscribe
 656 @FunctionWrapper
 657 def words(stack, expression, dictionary):
 658   '''Print all the words in alphabetical order.'''
 659   print(' '.join(sorted(dictionary)))
 660   return stack, expression, dictionary
 661
 662
 663 @inscribe
 664 @FunctionWrapper
 665 def sharing(stack, expression, dictionary):
 666   '''Print redistribution information.'''
 667   print("You may convey verbatim copies of the Program's source code as"
 668         ' you receive it, in any medium, provided that you conspicuously'
 669         ' and appropriately publish on each copy an appropriate copyright'
 670         ' notice; keep intact all notices stating that this License and'
 671         ' any non-permissive terms added in accord with section 7 apply'
 672         ' to the code; keep intact all notices of the absence of any'
 673         ' warranty; and give all recipients a copy of this License along'
 674         ' with the Program.'
 675         ' You should have received a copy of the GNU General Public License'
 676         ' along with Thun.  If not see <http://www.gnu.org/licenses/>.')
 677   return stack, expression, dictionary
 678
 679
 680 @inscribe
 681 @FunctionWrapper
 682 def warranty(stack, expression, dictionary):
 683   '''Print warranty information.'''
 684   print('THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY'
 685         ' APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE'
 686         ' COPYRIGHT HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM'
 687         ' "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR'
 688         ' IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES'
 689         ' OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE'
 690         ' ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS'
 691         ' WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE'
 692         ' COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION.')
 693   return stack, expression, dictionary
 694
 695
 696 # def simple_manual(stack):
 697 #   '''
 698 #   Print words and help for each word.
 699 #   '''
 700 #   for name, f in sorted(FUNCTIONS.items()):
 701 #     d = getdoc(f)
 702 #     boxline = '+%s+' % ('-' * (len(name) + 2))
 703 #     print('\n'.join((
 704 #       boxline,
 705 #       '| %s |' % (name,),
 706 #       boxline,
 707 #       d if d else '   ...',
 708 #       '',
 709 #       '--' * 40,
 710 #       '',
 711 #       )))
 712 #   return stack
 713
 714
 715 @inscribe
 716 @FunctionWrapper
 717 def help_(S, expression, dictionary):
 718   '''Accepts a quoted symbol on the top of the stack and prints its docs.'''
 719   ((symbol, _), stack) = S
 720   word = dictionary[symbol]
 721   print(getdoc(word))
 722   return stack, expression, dictionary
 723
 724
 725 #
 726 # § Combinators
 727 #
 728
 729
 730 # Several combinators depend on other words in their definitions,
 731 # we use symbols to prevent hard-coding these, so in theory, you
 732 # could change the word in the dictionary to use different semantics.
 733 S_choice = Symbol('choice')
 734 S_first = Symbol('first')
 735 S_getitem = Symbol('getitem')
 736 S_genrec = Symbol('genrec')
 737 S_loop = Symbol('loop')
 738 S_i = Symbol('i')
 739 S_ifte = Symbol('ifte')
 740 S_infra = Symbol('infra')
 741 S_step = Symbol('step')
 742 S_times = Symbol('times')
 743 S_swaack = Symbol('swaack')
 744 S_truthy = Symbol('truthy')
 745
 746
 747 @inscribe
 748 @FunctionWrapper
 749 def i(stack, expression, dictionary):
 750   '''
 751   The i combinator expects a quoted program on the stack and unpacks it
 752   onto the pending expression for evaluation.
 753   ::
 754
 755        [Q] i
 756     -----------
 757         Q
 758
 759   '''
 760   quote, stack = stack
 761   return stack, concat(quote, expression), dictionary
 762
 763
 764 @inscribe
 765 @FunctionWrapper
 766 def x(stack, expression, dictionary):
 767   '''
 768   ::
 769
 770     x == dup i
 771
 772     ... [Q] x = ... [Q] dup i
 773     ... [Q] x = ... [Q] [Q] i
 774     ... [Q] x = ... [Q]  Q
 775
 776   '''
 777   quote, _ = stack
 778   return stack, concat(quote, expression), dictionary
 779
 780
 781 @inscribe
 782 @FunctionWrapper
 783 def b(stack, expression, dictionary):
 784   '''
 785   ::
 786
 787     b == [i] dip i
 788
 789     ... [P] [Q] b == ... [P] i [Q] i
 790     ... [P] [Q] b == ... P Q
 791
 792   '''
 793   q, (p, (stack)) = stack
 794   return stack, concat(p, concat(q, expression)), dictionary
 795
 796
 797 @inscribe
 798 @FunctionWrapper
 799 def dupdip(stack, expression, dictionary):
 800   '''
 801   ::
 802
 803     [F] dupdip == dup [F] dip
 804
 805     ... a [F] dupdip
 806     ... a dup [F] dip
 807     ... a a   [F] dip
 808     ... a F a
 809
 810   '''
 811   F, stack = stack
 812   a = stack[0]
 813   return stack, concat(F, (a,  expression)), dictionary
 814
 815
 816 @inscribe
 817 @FunctionWrapper
 818 def infra(stack, expression, dictionary):
 819   '''
 820   Accept a quoted program and a list on the stack and run the program
 821   with the list as its stack.
 822   ::
 823
 824        ... [a b c] [Q] . infra
 825     -----------------------------
 826        c b a . Q [...] swaack
 827
 828   '''
 829   (quote, (aggregate, stack)) = stack
 830   return aggregate, concat(quote, (stack, (S_swaack, expression))), dictionary
 831
 832
 833 @inscribe
 834 @FunctionWrapper
 835 def genrec(stack, expression, dictionary):
 836   '''
 837   General Recursion Combinator.
 838   ::
 839
 840                           [if] [then] [rec1] [rec2] genrec
 841     ---------------------------------------------------------------------
 842        [if] [then] [rec1 [[if] [then] [rec1] [rec2] genrec] rec2] ifte
 843
 844   From "Recursion Theory and Joy" (j05cmp.html) by Manfred von Thun:
 845   "The genrec combinator takes four program parameters in addition to
 846   whatever data parameters it needs. Fourth from the top is an if-part,
 847   followed by a then-part. If the if-part yields true, then the then-part
 848   is executed and the combinator terminates. The other two parameters are
 849   the rec1-part and the rec2-part. If the if-part yields false, the
 850   rec1-part is executed. Following that the four program parameters and
 851   the combinator are again pushed onto the stack bundled up in a quoted
 852   form. Then the rec2-part is executed, where it will find the bundled
 853   form. Typically it will then execute the bundled form, either with i or
 854   with app2, or some other combinator."
 855
 856   The way to design one of these is to fix your base case [then] and the
 857   test [if], and then treat rec1 and rec2 as an else-part "sandwiching"
 858   a quotation of the whole function.
 859
 860   For example, given a (general recursive) function 'F':
 861   ::
 862
 863       F == [I] [T] [R1] [R2] genrec
 864
 865   If the [I] if-part fails you must derive R1 and R2 from:
 866   ::
 867
 868       ... R1 [F] R2
 869
 870   Just set the stack arguments in front, and figure out what R1 and R2
 871   have to do to apply the quoted [F] in the proper way.  In effect, the
 872   genrec combinator turns into an ifte combinator with a quoted copy of
 873   the original definition in the else-part:
 874   ::
 875
 876       F == [I] [T] [R1]   [R2] genrec
 877         == [I] [T] [R1 [F] R2] ifte
 878
 879   Primitive recursive functions are those where R2 == i.
 880   ::
 881
 882       P == [I] [T] [R] primrec
 883         == [I] [T] [R [P] i] ifte
 884         == [I] [T] [R P] ifte
 885
 886   '''
 887   (rec2, (rec1, stack)) = stack
 888   (then, (if_, _)) = stack
 889   F = (if_, (then, (rec1, (rec2, (S_genrec, ())))))
 890   else_ = concat(rec1, (F, rec2))
 891   return (else_, stack), (S_ifte, expression), dictionary
 892
 893
 894 @inscribe
 895 @FunctionWrapper
 896 def map_(S, expression, dictionary):
 897   '''
 898   Run the quoted program on TOS on the items in the list under it, push a
 899   new list with the results (in place of the program and original list.
 900   '''
 901 #  (quote, (aggregate, stack)) = S
 902 #  results = list_to_stack([
 903 #    joy((term, stack), quote, dictionary)[0][0]
 904 #    for term in iter_stack(aggregate)
 905 #    ])
 906 #  return (results, stack), expression, dictionary
 907   (quote, (aggregate, stack)) = S
 908   if not aggregate:
 909     return (aggregate, stack), expression, dictionary
 910   batch = ()
 911   for term in iter_stack(aggregate):
 912     s = term, stack
 913     batch = (s, (quote, (S_infra, (S_first, batch))))
 914   stack = (batch, ((), stack))
 915   return stack, (S_infra, expression), dictionary
 916
 917
 918 #def cleave(S, expression, dictionary):
 919 #  '''
 920 #  The cleave combinator expects two quotations, and below that an item X.
 921 #  It first executes [P], with X on top, and saves the top result element.
 922 #  Then it executes [Q], again with X, and saves the top result.
 923 #  Finally it restores the stack to what it was below X and pushes the two
 924 #  results P(X) and Q(X).
 925 #  '''
 926 #  (Q, (P, (x, stack))) = S
 927 #  p = joy((x, stack), P, dictionary)[0][0]
 928 #  q = joy((x, stack), Q, dictionary)[0][0]
 929 #  return (q, (p, stack)), expression, dictionary
 930
 931
 932 @inscribe
 933 @FunctionWrapper
 934 def branch(stack, expression, dictionary):
 935   '''
 936   Use a Boolean value to select one of two quoted programs to run.
 937
 938   ::
 939
 940       branch == roll< choice i
 941
 942   ::
 943
 944         False [F] [T] branch
 945      --------------------------
 946                F
 947
 948         True [F] [T] branch
 949      -------------------------
 950                   T
 951
 952   '''
 953   (then, (else_, (flag, stack))) = stack
 954   return stack, concat(then if flag else else_, expression), dictionary
 955
 956
 957 @inscribe
 958 @FunctionWrapper
 959 def ifte(stack, expression, dictionary):
 960   '''
 961   If-Then-Else Combinator
 962   ::
 963
 964                   ... [if] [then] [else] ifte
 965        ---------------------------------------------------
 966           ... [[else] [then]] [...] [if] infra select i
 967
 968
 969
 970
 971                 ... [if] [then] [else] ifte
 972        -------------------------------------------------------
 973           ... [else] [then] [...] [if] infra first choice i
 974
 975
 976   Has the effect of grabbing a copy of the stack on which to run the
 977   if-part using infra.
 978   '''
 979   (else_, (then, (if_, stack))) = stack
 980   expression = (S_infra, (S_first, (S_choice, (S_i, expression))))
 981   stack = (if_, (stack, (then, (else_, stack))))
 982   return stack, expression, dictionary
 983
 984
 985 @inscribe
 986 @FunctionWrapper
 987 def cond(stack, expression, dictionary):
 988   '''
 989   This combinator works like a case statement.  It expects a single quote
 990   on the stack that must contain zero or more condition quotes and a
 991   default quote.  Each condition clause should contain a quoted predicate
 992   followed by the function expression to run if that predicate returns
 993   true.  If no predicates return true the default function runs.
 994
 995   It works by rewriting into a chain of nested `ifte` expressions, e.g.::
 996
 997             [[[B0] T0] [[B1] T1] [D]] cond
 998       -----------------------------------------
 999          [B0] [T0] [[B1] [T1] [D] ifte] ifte
1000
1001   '''
1002   conditions, stack = stack
1003   if conditions:
1004     expression = _cond(conditions, expression)
1005     try:
1006       # Attempt to preload the args to first ifte.
1007       (P, (T, (E, expression))) = expression
1008     except ValueError:
1009       # If, for any reason, the argument to cond should happen to contain
1010       # only the default clause then this optimization will fail.
1011       pass
1012     else:
1013       stack = (E, (T, (P, stack)))
1014   return stack, expression, dictionary
1015
1016
1017 def _cond(conditions, expression):
1018   (clause, rest) = conditions
1019   if not rest:  # clause is [D]
1020     return clause
1021   P, T = clause
1022   return (P, (T, (_cond(rest, ()), (S_ifte, expression))))
1023
1024
1025 @inscribe
1026 @FunctionWrapper
1027 def dip(stack, expression, dictionary):
1028   '''
1029   The dip combinator expects a quoted program on the stack and below it
1030   some item, it hoists the item into the expression and runs the program
1031   on the rest of the stack.
1032   ::
1033
1034        ... x [Q] dip
1035     -------------------
1036          ... Q x
1037
1038   '''
1039   (quote, (x, stack)) = stack
1040   expression = (x, expression)
1041   return stack, concat(quote, expression), dictionary
1042
1043
1044 @inscribe
1045 @FunctionWrapper
1046 def dipd(S, expression, dictionary):
1047   '''
1048   Like dip but expects two items.
1049   ::
1050
1051        ... y x [Q] dip
1052     ---------------------
1053          ... Q y x
1054
1055   '''
1056   (quote, (x, (y, stack))) = S
1057   expression = (y, (x, expression))
1058   return stack, concat(quote, expression), dictionary
1059
1060
1061 @inscribe
1062 @FunctionWrapper
1063 def dipdd(S, expression, dictionary):
1064   '''
1065   Like dip but expects three items.
1066   ::
1067
1068        ... z y x [Q] dip
1069     -----------------------
1070          ... Q z y x
1071
1072   '''
1073   (quote, (x, (y, (z, stack)))) = S
1074   expression = (z, (y, (x, expression)))
1075   return stack, concat(quote, expression), dictionary
1076
1077
1078 @inscribe
1079 @FunctionWrapper
1080 def app1(S, expression, dictionary):
1081   '''
1082   Given a quoted program on TOS and anything as the second stack item run
1083   the program and replace the two args with the first result of the
1084   program.
1085   ::
1086
1087               ... x [Q] . app1
1088      -----------------------------------
1089         ... [x ...] [Q] . infra first
1090   '''
1091   (quote, (x, stack)) = S
1092   stack = (quote, ((x, stack), stack))
1093   expression = (S_infra, (S_first, expression))
1094   return stack, expression, dictionary
1095
1096
1097 @inscribe
1098 @FunctionWrapper
1099 def app2(S, expression, dictionary):
1100   '''Like app1 with two items.
1101   ::
1102
1103             ... y x [Q] . app2
1104      -----------------------------------
1105         ... [y ...] [Q] . infra first
1106             [x ...] [Q]   infra first
1107
1108   '''
1109   (quote, (x, (y, stack))) = S
1110   expression = (S_infra, (S_first,
1111     ((x, stack), (quote, (S_infra, (S_first,
1112       expression))))))
1113   stack = (quote, ((y, stack), stack))
1114   return stack, expression, dictionary
1115
1116
1117 @inscribe
1118 @FunctionWrapper
1119 def app3(S, expression, dictionary):
1120   '''Like app1 with three items.
1121   ::
1122
1123             ... z y x [Q] . app3
1124      -----------------------------------
1125         ... [z ...] [Q] . infra first
1126             [y ...] [Q]   infra first
1127             [x ...] [Q]   infra first
1128
1129   '''
1130   (quote, (x, (y, (z, stack)))) = S
1131   expression = (S_infra, (S_first,
1132     ((y, stack), (quote, (S_infra, (S_first,
1133     ((x, stack), (quote, (S_infra, (S_first,
1134       expression))))))))))
1135   stack = (quote, ((z, stack), stack))
1136   return stack, expression, dictionary
1137
1138
1139 @inscribe
1140 @FunctionWrapper
1141 def step(S, expression, dictionary):
1142   '''
1143   Run a quoted program on each item in a sequence.
1144   ::
1145
1146           ... [] [Q] . step
1147        -----------------------
1148                  ... .
1149
1150
1151          ... [a] [Q] . step
1152       ------------------------
1153                ... a . Q
1154
1155
1156        ... [a b c] [Q] . step
1157     ----------------------------------------
1158                  ... a . Q [b c] [Q] step
1159
1160   The step combinator executes the quotation on each member of the list
1161   on top of the stack.
1162   '''
1163   (quote, (aggregate, stack)) = S
1164   if not aggregate:
1165     return stack, expression, dictionary
1166   head, tail = aggregate
1167   stack = quote, (head, stack)
1168   if tail:
1169     expression = tail, (quote, (S_step, expression))
1170   expression = S_i, expression
1171   return stack, expression, dictionary
1172
1173
1174 @inscribe
1175 @FunctionWrapper
1176 def times(stack, expression, dictionary):
1177   '''
1178   times == [-- dip] cons [swap] infra [0 >] swap while pop
1179   ::
1180
1181        ... n [Q] . times
1182     ---------------------  w/ n <= 0
1183              ... .
1184
1185
1186        ... 1 [Q] . times
1187     ---------------------------------
1188              ... . Q
1189
1190
1191        ... n [Q] . times
1192     ---------------------------------  w/ n > 1
1193              ... . Q (n - 1) [Q] times
1194
1195   '''
1196   # times == [-- dip] cons [swap] infra [0 >] swap while pop
1197   (quote, (n, stack)) = stack
1198   if n <= 0:
1199     return stack, expression, dictionary
1200   n -= 1
1201   if n:
1202     expression = n, (quote, (S_times, expression))
1203   expression = concat(quote, expression)
1204   return stack, expression, dictionary
1205
1206
1207 # The current definition above works like this:
1208
1209 #             [P] [Q] while
1210 # --------------------------------------
1211 #    [P] nullary [Q [P] nullary] loop
1212
1213 #   while == [pop i not] [popop] [dudipd] primrec
1214
1215 #def while_(S, expression, dictionary):
1216 #  '''[if] [body] while'''
1217 #  (body, (if_, stack)) = S
1218 #  while joy(stack, if_, dictionary)[0][0]:
1219 #    stack = joy(stack, body, dictionary)[0]
1220 #  return stack, expression, dictionary
1221
1222
1223 @inscribe
1224 @FunctionWrapper
1225 def loop(stack, expression, dictionary):
1226   '''
1227   Basic loop combinator.
1228   ::
1229
1230        ... True [Q] loop
1231     -----------------------
1232           ... Q [Q] loop
1233
1234        ... False [Q] loop
1235     ------------------------
1236               ...
1237
1238   '''
1239   quote, (flag, stack) = stack
1240   if flag:
1241     expression = concat(quote, (quote, (S_loop, expression)))
1242   return stack, expression, dictionary
1243
1244
1245 @inscribe
1246 @FunctionWrapper
1247 def cmp_(stack, expression, dictionary):
1248   '''
1249   cmp takes two values and three quoted programs on the stack and runs
1250   one of the three depending on the results of comparing the two values:
1251   ::
1252
1253            a b [G] [E] [L] cmp
1254         ------------------------- a > b
1255                 G
1256
1257            a b [G] [E] [L] cmp
1258         ------------------------- a = b
1259                     E
1260
1261            a b [G] [E] [L] cmp
1262         ------------------------- a < b
1263                         L
1264   '''
1265   L, (E, (G, (b, (a, stack)))) = stack
1266   expression = concat(G if a > b else L if a < b else E, expression)
1267   return stack, expression, dictionary
1268
1269
1270 #  FunctionWrapper(cleave),
1271 #  FunctionWrapper(while_),
1272
1273
1274 for F in (
1275   BinaryBuiltinWrapper(operator.add),
1276   BinaryBuiltinWrapper(operator.and_),
1277   BinaryBuiltinWrapper(operator.div),
1278   BinaryBuiltinWrapper(operator.eq),
1279   BinaryBuiltinWrapper(operator.floordiv),
1280   BinaryBuiltinWrapper(operator.ge),
1281   BinaryBuiltinWrapper(operator.gt),
1282   BinaryBuiltinWrapper(operator.le),
1283   BinaryBuiltinWrapper(operator.lshift),
1284   BinaryBuiltinWrapper(operator.lt),
1285   BinaryBuiltinWrapper(operator.mod),
1286   BinaryBuiltinWrapper(operator.mul),
1287   BinaryBuiltinWrapper(operator.ne),
1288   BinaryBuiltinWrapper(operator.or_),
1289   BinaryBuiltinWrapper(operator.pow),
1290   BinaryBuiltinWrapper(operator.rshift),
1291   BinaryBuiltinWrapper(operator.sub),
1292   BinaryBuiltinWrapper(operator.truediv),
1293   BinaryBuiltinWrapper(operator.xor),
1294
1295   UnaryBuiltinWrapper(abs),
1296   UnaryBuiltinWrapper(bool),
1297   UnaryBuiltinWrapper(floor),
1298   UnaryBuiltinWrapper(operator.neg),
1299   UnaryBuiltinWrapper(operator.not_),
1300   UnaryBuiltinWrapper(sqrt),
1301   ):
1302   inscribe(F)
1303 del F  # Otherwise Sphinx autodoc will pick it up.
1304
1305
1306 add_aliases(_dictionary, ALIASES)
1307
1308
1309 DefinitionWrapper.add_definitions(definitions, _dictionary)