joy/library.py

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