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