joy/library.py

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