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