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