joy/library.py

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