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