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   like a case statement; works by rewriting into a chain of ifte.
1148
1149   [..[[Bi] Ti]..[D]] -> ...
1150
1151
1152         [[[B0] T0] [[B1] T1] [D]] cond
1153   -----------------------------------------
1154      [B0] [T0] [[B1] [T1] [D] ifte] ifte
1155
1156   '''
1157   conditions, stack = stack
1158   if conditions:
1159     expression = _cond(conditions, expression)
1160     try:
1161       # Attempt to preload the args to first ifte.
1162       (P, (T, (E, expression))) = expression
1163     except ValueError:
1164       # If, for any reason, the argument to cond should happen to contain
1165       # only the default clause then this optimization will fail.
1166       pass
1167     else:
1168       stack = (E, (T, (P, stack)))
1169   return stack, expression, dictionary
1170
1171
1172 def _cond(conditions, expression):
1173   (clause, rest) = conditions
1174   if not rest:  # clause is [D]
1175     return clause
1176   P, T = clause
1177   return (P, (T, (_cond(rest, ()), (S_ifte, expression))))
1178
1179
1180 @inscribe
1181 @FunctionWrapper
1182 def dip(stack, expression, dictionary):
1183   '''
1184   The dip combinator expects a quoted program on the stack and below it
1185   some item, it hoists the item into the expression and runs the program
1186   on the rest of the stack.
1187   ::
1188
1189        ... x [Q] dip
1190     -------------------
1191          ... Q x
1192
1193   '''
1194   (quote, (x, stack)) = stack
1195   expression = (x, expression)
1196   return stack, pushback(quote, expression), dictionary
1197
1198
1199 @inscribe
1200 @FunctionWrapper
1201 def dipd(S, expression, dictionary):
1202   '''
1203   Like dip but expects two items.
1204   ::
1205
1206        ... y x [Q] dip
1207     ---------------------
1208          ... Q y x
1209
1210   '''
1211   (quote, (x, (y, stack))) = S
1212   expression = (y, (x, expression))
1213   return stack, pushback(quote, expression), dictionary
1214
1215
1216 @inscribe
1217 @FunctionWrapper
1218 def dipdd(S, expression, dictionary):
1219   '''
1220   Like dip but expects three items.
1221   ::
1222
1223        ... z y x [Q] dip
1224     -----------------------
1225          ... Q z y x
1226
1227   '''
1228   (quote, (x, (y, (z, stack)))) = S
1229   expression = (z, (y, (x, expression)))
1230   return stack, pushback(quote, expression), dictionary
1231
1232
1233 @inscribe
1234 @FunctionWrapper
1235 def app1(S, expression, dictionary):
1236   '''
1237   Given a quoted program on TOS and anything as the second stack item run
1238   the program and replace the two args with the first result of the
1239   program.
1240   ::
1241
1242               ... x [Q] . app1
1243      -----------------------------------
1244         ... [x ...] [Q] . infra first
1245   '''
1246   (quote, (x, stack)) = S
1247   stack = (quote, ((x, stack), stack))
1248   expression = (S_infra, (S_first, expression))
1249   return stack, expression, dictionary
1250
1251
1252 @inscribe
1253 @FunctionWrapper
1254 def app2(S, expression, dictionary):
1255   '''Like app1 with two items.
1256   ::
1257
1258             ... y x [Q] . app2
1259      -----------------------------------
1260         ... [y ...] [Q] . infra first
1261             [x ...] [Q]   infra first
1262
1263   '''
1264   (quote, (x, (y, stack))) = S
1265   expression = (S_infra, (S_first,
1266     ((x, stack), (quote, (S_infra, (S_first,
1267       expression))))))
1268   stack = (quote, ((y, stack), stack))
1269   return stack, expression, dictionary
1270
1271
1272 @inscribe
1273 @FunctionWrapper
1274 def app3(S, expression, dictionary):
1275   '''Like app1 with three items.
1276   ::
1277
1278             ... z y x [Q] . app3
1279      -----------------------------------
1280         ... [z ...] [Q] . infra first
1281             [y ...] [Q]   infra first
1282             [x ...] [Q]   infra first
1283
1284   '''
1285   (quote, (x, (y, (z, stack)))) = S
1286   expression = (S_infra, (S_first,
1287     ((y, stack), (quote, (S_infra, (S_first,
1288     ((x, stack), (quote, (S_infra, (S_first,
1289       expression))))))))))
1290   stack = (quote, ((z, stack), stack))
1291   return stack, expression, dictionary
1292
1293
1294 @inscribe
1295 @FunctionWrapper
1296 def step(S, expression, dictionary):
1297   '''
1298   Run a quoted program on each item in a sequence.
1299   ::
1300
1301           ... [] [Q] . step
1302        -----------------------
1303                  ... .
1304
1305
1306          ... [a] [Q] . step
1307       ------------------------
1308                ... a . Q
1309
1310
1311        ... [a b c] [Q] . step
1312     ----------------------------------------
1313                  ... a . Q [b c] [Q] step
1314
1315   The step combinator executes the quotation on each member of the list
1316   on top of the stack.
1317   '''
1318   (quote, (aggregate, stack)) = S
1319   if not aggregate:
1320     return stack, expression, dictionary
1321   head, tail = aggregate
1322   stack = quote, (head, stack)
1323   if tail:
1324     expression = tail, (quote, (S_step, expression))
1325   expression = S_i, expression
1326   return stack, expression, dictionary
1327
1328
1329 @inscribe
1330 @FunctionWrapper
1331 def times(stack, expression, dictionary):
1332   '''
1333   times == [-- dip] cons [swap] infra [0 >] swap while pop
1334   ::
1335
1336        ... n [Q] . times
1337     ---------------------  w/ n <= 0
1338              ... .
1339
1340
1341        ... 1 [Q] . times
1342     ---------------------------------
1343              ... . Q
1344
1345
1346        ... n [Q] . times
1347     ---------------------------------  w/ n > 1
1348              ... . Q (n - 1) [Q] times
1349
1350   '''
1351   # times == [-- dip] cons [swap] infra [0 >] swap while pop
1352   (quote, (n, stack)) = stack
1353   if n <= 0:
1354     return stack, expression, dictionary
1355   n -= 1
1356   if n:
1357     expression = n, (quote, (S_times, expression))
1358   expression = pushback(quote, expression)
1359   return stack, expression, dictionary
1360
1361
1362 # The current definition above works like this:
1363
1364 #             [P] [Q] while
1365 # --------------------------------------
1366 #    [P] nullary [Q [P] nullary] loop
1367
1368 #   while == [pop i not] [popop] [dudipd] primrec
1369
1370 #def while_(S, expression, dictionary):
1371 #  '''[if] [body] while'''
1372 #  (body, (if_, stack)) = S
1373 #  while joy(stack, if_, dictionary)[0][0]:
1374 #    stack = joy(stack, body, dictionary)[0]
1375 #  return stack, expression, dictionary
1376
1377
1378 @inscribe
1379 @FunctionWrapper
1380 def loop(stack, expression, dictionary):
1381   '''
1382   Basic loop combinator.
1383   ::
1384
1385        ... True [Q] loop
1386     -----------------------
1387           ... Q [Q] loop
1388
1389        ... False [Q] loop
1390     ------------------------
1391               ...
1392
1393   '''
1394   quote, (flag, stack) = stack
1395   if flag:
1396     expression = pushback(quote, (quote, (S_loop, expression)))
1397   return stack, expression, dictionary
1398
1399
1400 @inscribe
1401 @FunctionWrapper
1402 def cmp_(stack, expression, dictionary):
1403     '''
1404     cmp takes two values and three quoted programs on the stack and runs
1405     one of the three depending on the results of comparing the two values:
1406
1407            a b [G] [E] [L] cmp
1408         ------------------------- a > b
1409                 G
1410
1411            a b [G] [E] [L] cmp
1412         ------------------------- a = b
1413                     E
1414
1415            a b [G] [E] [L] cmp
1416         ------------------------- a < b
1417                         L
1418     '''
1419     L, (E, (G, (b, (a, stack)))) = stack
1420     expression = pushback(G if a > b else L if a < b else E, expression)
1421     return stack, expression, dictionary
1422
1423
1424 #def nullary(S, expression, dictionary):
1425 #  '''
1426 #  Run the program on TOS and return its first result without consuming
1427 #  any of the stack (except the program on TOS.)
1428 #  '''
1429 #  (quote, stack) = S
1430 #  result = joy(stack, quote, dictionary)
1431 #  return (result[0][0], stack), expression, dictionary
1432 #
1433 #
1434 #def unary(S, expression, dictionary):
1435 #  (quote, stack) = S
1436 #  _, return_stack = stack
1437 #  result = joy(stack, quote, dictionary)[0]
1438 #  return (result[0], return_stack), expression, dictionary
1439 #
1440 #
1441 #def binary(S, expression, dictionary):
1442 #  (quote, stack) = S
1443 #  _, (_, return_stack) = stack
1444 #  result = joy(stack, quote, dictionary)[0]
1445 #  return (result[0], return_stack), expression, dictionary
1446 #
1447 #
1448 #def ternary(S, expression, dictionary):
1449 #  (quote, stack) = S
1450 #  _, (_, (_, return_stack)) = stack
1451 #  result = joy(stack, quote, dictionary)[0]
1452 #  return (result[0], return_stack), expression, dictionary
1453
1454
1455 #  FunctionWrapper(binary),
1456 #  FunctionWrapper(cleave),
1457 #  FunctionWrapper(nullary),
1458 #  FunctionWrapper(ternary),
1459 #  FunctionWrapper(unary),
1460 #  FunctionWrapper(while_),
1461
1462
1463 for F in (
1464   BinaryBuiltinWrapper(operator.add),
1465   BinaryBuiltinWrapper(operator.and_),
1466   BinaryBuiltinWrapper(operator.div),
1467   BinaryBuiltinWrapper(operator.eq),
1468   BinaryBuiltinWrapper(operator.floordiv),
1469   BinaryBuiltinWrapper(operator.ge),
1470   BinaryBuiltinWrapper(operator.gt),
1471   BinaryBuiltinWrapper(operator.le),
1472   BinaryBuiltinWrapper(operator.lshift),
1473   BinaryBuiltinWrapper(operator.lt),
1474   BinaryBuiltinWrapper(operator.mod),
1475   BinaryBuiltinWrapper(operator.mul),
1476   BinaryBuiltinWrapper(operator.ne),
1477   BinaryBuiltinWrapper(operator.or_),
1478   BinaryBuiltinWrapper(operator.pow),
1479   BinaryBuiltinWrapper(operator.rshift),
1480   BinaryBuiltinWrapper(operator.sub),
1481   BinaryBuiltinWrapper(operator.truediv),
1482   BinaryBuiltinWrapper(operator.xor),
1483
1484   UnaryBuiltinWrapper(abs),
1485   UnaryBuiltinWrapper(bool),
1486   UnaryBuiltinWrapper(floor),
1487   UnaryBuiltinWrapper(operator.neg),
1488   UnaryBuiltinWrapper(operator.not_),
1489   UnaryBuiltinWrapper(sqrt),
1490   ):
1491   inscribe(F)
1492 del F  # Otherwise Sphinx autodoc will pick it up.
1493
1494
1495 add_aliases(_dictionary, ALIASES)
1496
1497
1498 DefinitionWrapper.add_definitions(definitions, _dictionary)