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