joy/library.py

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