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