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