joy/library.py

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