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