joy/library.py

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