joy/library.py

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