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