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