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