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