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         '''Given a quoted sequence of numbers return the sum.
 483
 484         sum == 0 swap [+] step
 485         '''
 486         tos, stack = S
 487         return sum(iter_stack(tos)), stack
 488
 489
 490 @inscribe
 491 @SimpleFunctionWrapper
 492 def remove(S):
 493         '''
 494         Expects an item on the stack and a quote under it and removes that item
 495         from the the quote.  The item is only removed once.
 496         ::
 497
 498                          [1 2 3 1] 1 remove
 499                 ------------------------
 500                                                 [2 3 1]
 501
 502         '''
 503         (tos, (second, stack)) = S
 504         l = list(iter_stack(second))
 505         l.remove(tos)
 506         return list_to_stack(l), stack
 507
 508
 509 @inscribe
 510 @SimpleFunctionWrapper
 511 def unique(S):
 512         '''Given a list remove duplicate items.'''
 513         tos, stack = S
 514         I = list(iter_stack(tos))
 515         return list_to_stack(sorted(set(I), key=I.index)), stack
 516
 517
 518 @inscribe
 519 @SimpleFunctionWrapper
 520 def sort_(S):
 521         '''Given a list return it sorted.'''
 522         tos, stack = S
 523         return list_to_stack(sorted(iter_stack(tos))), stack
 524
 525
 526 @inscribe
 527 @SimpleFunctionWrapper
 528 def clear(stack):
 529         '''Clear everything from the stack.
 530         ::
 531
 532                 clear == stack [pop stack] loop
 533
 534                          ... clear
 535                 ---------------
 536
 537         '''
 538         return ()
 539
 540
 541 @inscribe
 542 @SimpleFunctionWrapper
 543 def disenstacken(stack):
 544         '''
 545         The disenstacken operator expects a list on top of the stack and makes that
 546         the stack discarding the rest of the stack.
 547         '''
 548         return stack[0]
 549
 550
 551 @inscribe
 552 @SimpleFunctionWrapper
 553 def reverse(S):
 554         '''Reverse the list on the top of the stack.
 555         ::
 556
 557                 reverse == [] swap shunt
 558         '''
 559         (tos, stack) = S
 560         res = ()
 561         for term in iter_stack(tos):
 562                 res = term, res
 563         return res, stack
 564
 565
 566 @inscribe
 567 @SimpleFunctionWrapper
 568 def concat_(S):
 569         '''Concatinate the two lists on the top of the stack.
 570         ::
 571
 572                          [a b c] [d e f] concat
 573                 ----------------------------
 574                                          [a b c d e f]
 575
 576         '''
 577         (tos, (second, stack)) = S
 578         return concat(second, tos), stack
 579
 580
 581 @inscribe
 582 @SimpleFunctionWrapper
 583 def shunt(stack):
 584         '''Like concat but reverses the top list into the second.
 585         ::
 586
 587                 shunt == [swons] step == reverse swap concat
 588
 589                          [a b c] [d e f] shunt
 590                 ---------------------------
 591                                  [f e d a b c]
 592
 593         '''
 594         (tos, (second, stack)) = stack
 595         while tos:
 596                 term, tos = tos
 597                 second = term, second
 598         return second, stack
 599
 600
 601 @inscribe
 602 @SimpleFunctionWrapper
 603 def zip_(S):
 604         '''
 605         Replace the two lists on the top of the stack with a list of the pairs
 606         from each list.  The smallest list sets the length of the result list.
 607         '''
 608         (tos, (second, stack)) = S
 609         accumulator = [
 610                 (a, (b, ()))
 611                 for a, b in zip(iter_stack(tos), iter_stack(second))
 612                 ]
 613         return list_to_stack(accumulator), stack
 614
 615
 616 @inscribe
 617 @SimpleFunctionWrapper
 618 def succ(S):
 619         '''Increment TOS.'''
 620         (tos, stack) = S
 621         return tos + 1, stack
 622
 623
 624 @inscribe
 625 @SimpleFunctionWrapper
 626 def pred(S):
 627         '''Decrement TOS.'''
 628         (tos, stack) = S
 629         return tos - 1, stack
 630
 631
 632 @inscribe
 633 @SimpleFunctionWrapper
 634 def pm(stack):
 635         '''
 636         Plus or minus
 637         ::
 638
 639                          a b pm
 640                 -------------
 641                          a+b a-b
 642
 643         '''
 644         a, (b, stack) = stack
 645         p, m, = b + a, b - a
 646         return m, (p, stack)
 647
 648
 649 def floor(n):
 650         return int(math.floor(n))
 651
 652 floor.__doc__ = math.floor.__doc__
 653
 654
 655 @inscribe
 656 @SimpleFunctionWrapper
 657 def divmod_(S):
 658         '''
 659         divmod(x, y) -> (quotient, remainder)
 660
 661         Return the tuple (x//y, x%y).  Invariant: div*y + mod == x.
 662         '''
 663         a, (b, stack) = S
 664         d, m = divmod(a, b)
 665         return d, (m, stack)
 666
 667
 668 def sqrt(a):
 669         '''
 670         Return the square root of the number a.
 671         Negative numbers return complex roots.
 672         '''
 673         try:
 674                 r = math.sqrt(a)
 675         except ValueError:
 676                 assert a < 0, repr(a)
 677                 r = math.sqrt(-a) * 1j
 678         return r
 679
 680
 681 #def execute(S):
 682 #  (text, stack) = S
 683 #  if isinstance(text, str):
 684 #    return run(text, stack)
 685 #  return stack
 686
 687
 688 @inscribe
 689 @SimpleFunctionWrapper
 690 def id_(stack):
 691         '''The identity function.'''
 692         return stack
 693
 694
 695 @inscribe
 696 @SimpleFunctionWrapper
 697 def void(stack):
 698         '''True if the form on TOS is void otherwise False.'''
 699         form, stack = stack
 700         return _void(form), stack
 701
 702
 703 def _void(form):
 704         return any(not _void(i) for i in iter_stack(form))
 705
 706
 707
 708 ##  transpose
 709 ##  sign
 710 ##  take
 711
 712
 713 @inscribe
 714 @FunctionWrapper
 715 def words(stack, expression, dictionary):
 716         '''Print all the words in alphabetical order.'''
 717         print(' '.join(sorted(dictionary)))
 718         return stack, expression, dictionary
 719
 720
 721 @inscribe
 722 @FunctionWrapper
 723 def sharing(stack, expression, dictionary):
 724         '''Print redistribution information.'''
 725         print("You may convey verbatim copies of the Program's source code as"
 726         ' you receive it, in any medium, provided that you conspicuously'
 727         ' and appropriately publish on each copy an appropriate copyright'
 728         ' notice; keep intact all notices stating that this License and'
 729         ' any non-permissive terms added in accord with section 7 apply'
 730         ' to the code; keep intact all notices of the absence of any'
 731         ' warranty; and give all recipients a copy of this License along'
 732         ' with the Program.'
 733         ' You should have received a copy of the GNU General Public License'
 734         ' along with Thun.  If not see <http://www.gnu.org/licenses/>.')
 735         return stack, expression, dictionary
 736
 737
 738 @inscribe
 739 @FunctionWrapper
 740 def warranty(stack, expression, dictionary):
 741         '''Print warranty information.'''
 742         print('THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY'
 743         ' APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE'
 744         ' COPYRIGHT HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM'
 745         ' "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR'
 746         ' IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES'
 747         ' OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE'
 748         ' ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS'
 749         ' WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE'
 750         ' COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION.')
 751         return stack, expression, dictionary
 752
 753
 754 # def simple_manual(stack):
 755 #   '''
 756 #   Print words and help for each word.
 757 #   '''
 758 #   for name, f in sorted(FUNCTIONS.items()):
 759 #     d = getdoc(f)
 760 #     boxline = '+%s+' % ('-' * (len(name) + 2))
 761 #     print('\n'.join((
 762 #       boxline,
 763 #       '| %s |' % (name,),
 764 #       boxline,
 765 #       d if d else '   ...',
 766 #       '',
 767 #       '--' * 40,
 768 #       '',
 769 #       )))
 770 #   return stack
 771
 772
 773 @inscribe
 774 @FunctionWrapper
 775 def help_(S, expression, dictionary):
 776         '''Accepts a quoted symbol on the top of the stack and prints its docs.'''
 777         ((symbol, _), stack) = S
 778         word = dictionary[symbol]
 779         print(HELP_TEMPLATE % (symbol, getdoc(word), symbol))
 780         return stack, expression, dictionary
 781
 782
 783 #
 784 # § Combinators
 785 #
 786
 787
 788 # Several combinators depend on other words in their definitions,
 789 # we use symbols to prevent hard-coding these, so in theory, you
 790 # could change the word in the dictionary to use different semantics.
 791 S_choice = Symbol('choice')
 792 S_first = Symbol('first')
 793 S_genrec = Symbol('genrec')
 794 S_getitem = Symbol('getitem')
 795 S_i = Symbol('i')
 796 S_ifte = Symbol('ifte')
 797 S_infra = Symbol('infra')
 798 S_loop = Symbol('loop')
 799 S_pop = Symbol('pop')
 800 S_primrec = Symbol('primrec')
 801 S_step = Symbol('step')
 802 S_swaack = Symbol('swaack')
 803 S_times = Symbol('times')
 804
 805
 806 @inscribe
 807 @FunctionWrapper
 808 def i(stack, expression, dictionary):
 809         '''
 810         The i combinator expects a quoted program on the stack and unpacks it
 811         onto the pending expression for evaluation.
 812         ::
 813
 814                          [Q] i
 815                 -----------
 816                                 Q
 817
 818         '''
 819         quote, stack = stack
 820         return stack, concat(quote, expression), dictionary
 821
 822
 823 @inscribe
 824 @FunctionWrapper
 825 def x(stack, expression, dictionary):
 826         '''
 827         ::
 828
 829                 x == dup i
 830
 831                 ... [Q] x = ... [Q] dup i
 832                 ... [Q] x = ... [Q] [Q] i
 833                 ... [Q] x = ... [Q]  Q
 834
 835         '''
 836         quote, _ = stack
 837         return stack, concat(quote, expression), dictionary
 838
 839
 840 @inscribe
 841 @FunctionWrapper
 842 def b(stack, expression, dictionary):
 843         '''
 844         ::
 845
 846                 b == [i] dip i
 847
 848                 ... [P] [Q] b == ... [P] i [Q] i
 849                 ... [P] [Q] b == ... P Q
 850
 851         '''
 852         q, (p, (stack)) = stack
 853         return stack, concat(p, concat(q, expression)), dictionary
 854
 855
 856 @inscribe
 857 @FunctionWrapper
 858 def dupdip(stack, expression, dictionary):
 859         '''
 860         ::
 861
 862                 [F] dupdip == dup [F] dip
 863
 864                 ... a [F] dupdip
 865                 ... a dup [F] dip
 866                 ... a a   [F] dip
 867                 ... a F a
 868
 869         '''
 870         F, stack = stack
 871         a = stack[0]
 872         return stack, concat(F, (a,  expression)), dictionary
 873
 874
 875 @inscribe
 876 @FunctionWrapper
 877 def infra(stack, expression, dictionary):
 878         '''
 879         Accept a quoted program and a list on the stack and run the program
 880         with the list as its stack.  Does not affect the rest of the stack.
 881         ::
 882
 883                          ... [a b c] [Q] . infra
 884                 -----------------------------
 885                          c b a . Q [...] swaack
 886
 887         '''
 888         (quote, (aggregate, stack)) = stack
 889         return aggregate, concat(quote, (stack, (S_swaack, expression))), dictionary
 890
 891
 892 @inscribe
 893 @FunctionWrapper
 894 def genrec(stack, expression, dictionary):
 895         '''
 896         General Recursion Combinator.
 897         ::
 898
 899                                   [if] [then] [rec1] [rec2] genrec
 900             ---------------------------------------------------------------------
 901                [if] [then] [rec1 [[if] [then] [rec1] [rec2] genrec] rec2] ifte
 902
 903         From "Recursion Theory and Joy" (j05cmp.html) by Manfred von Thun:
 904         "The genrec combinator takes four program parameters in addition to
 905         whatever data parameters it needs. Fourth from the top is an if-part,
 906         followed by a then-part. If the if-part yields true, then the then-part
 907         is executed and the combinator terminates. The other two parameters are
 908         the rec1-part and the rec2-part. If the if-part yields false, the
 909         rec1-part is executed. Following that the four program parameters and
 910         the combinator are again pushed onto the stack bundled up in a quoted
 911         form. Then the rec2-part is executed, where it will find the bundled
 912         form. Typically it will then execute the bundled form, either with i or
 913         with app2, or some other combinator."
 914
 915         The way to design one of these is to fix your base case [then] and the
 916         test [if], and then treat rec1 and rec2 as an else-part "sandwiching"
 917         a quotation of the whole function.
 918
 919         For example, given a (general recursive) function 'F':
 920         ::
 921
 922                         F == [I] [T] [R1] [R2] genrec
 923
 924         If the [I] if-part fails you must derive R1 and R2 from:
 925         ::
 926
 927                         ... R1 [F] R2
 928
 929         Just set the stack arguments in front, and figure out what R1 and R2
 930         have to do to apply the quoted [F] in the proper way.  In effect, the
 931         genrec combinator turns into an ifte combinator with a quoted copy of
 932         the original definition in the else-part:
 933         ::
 934
 935                         F == [I] [T] [R1]   [R2] genrec
 936                           == [I] [T] [R1 [F] R2] ifte
 937
 938         Primitive recursive functions are those where R2 == i.
 939         ::
 940
 941                         P == [I] [T] [R] tailrec
 942                           == [I] [T] [R [P] i] ifte
 943                           == [I] [T] [R P] ifte
 944
 945         '''
 946         (rec2, (rec1, stack)) = stack
 947         (then, (if_, _)) = stack
 948         F = (if_, (then, (rec1, (rec2, (S_genrec, ())))))
 949         else_ = concat(rec1, (F, rec2))
 950         return (else_, stack), (S_ifte, expression), dictionary
 951
 952
 953 @inscribe
 954 @FunctionWrapper
 955 def map_(S, expression, dictionary):
 956         '''
 957         Run the quoted program on TOS on the items in the list under it, push a
 958         new list with the results in place of the program and original list.
 959         '''
 960         # (quote, (aggregate, stack)) = S
 961         # results = list_to_stack([
 962         # joy((term, stack), quote, dictionary)[0][0]
 963         # for term in iter_stack(aggregate)
 964         # ])
 965         # return (results, stack), expression, dictionary
 966         (quote, (aggregate, stack)) = S
 967         if not aggregate:
 968                 return (aggregate, stack), expression, dictionary
 969         batch = ()
 970         for term in iter_stack(aggregate):
 971                 s = term, stack
 972                 batch = (s, (quote, (S_infra, (S_first, batch))))
 973         stack = (batch, ((), stack))
 974         return stack, (S_infra, expression), dictionary
 975
 976
 977 @inscribe
 978 @FunctionWrapper
 979 def primrec(stack, expression, dictionary):
 980         '''
 981         From the "Overview of the language JOY":
 982
 983         > The primrec combinator expects two quoted programs in addition to a
 984         data parameter. For an integer data parameter it works like this: If
 985         the data parameter is zero, then the first quotation has to produce
 986         the value to be returned. If the data parameter is positive then the
 987         second has to combine the data parameter with the result of applying
 988         the function to its predecessor.
 989
 990         5  [1]  [*]  primrec
 991
 992         > Then primrec tests whether the top element on the stack (initially
 993         the 5) is equal to zero. If it is, it pops it off and executes one of
 994         the quotations, the [1] which leaves 1 on the stack as the result.
 995         Otherwise it pushes a decremented copy of the top element and
 996         recurses. On the way back from the recursion it uses the other
 997         quotation, [*], to multiply what is now a factorial on top of the
 998         stack by the second element on the stack.
 999
1000                 n [Base] [Recur] primrec
1001
1002            0 [Base] [Recur] primrec
1003         ------------------------------
1004               Base
1005
1006            n [Base] [Recur] primrec
1007         ------------------------------------------ n > 0
1008            n (n-1) [Base] [Recur] primrec Recur
1009
1010         '''
1011         recur, (base, (n, stack)) = stack
1012         if n <= 0:
1013                 expression = concat(base, expression)
1014         else:
1015                 expression = S_primrec, concat(recur, expression)
1016                 stack = recur, (base, (n - 1, (n, stack)))
1017         return stack, expression, dictionary
1018
1019
1020 #def cleave(S, expression, dictionary):
1021 #  '''
1022 #  The cleave combinator expects two quotations, and below that an item X.
1023 #  It first executes [P], with X on top, and saves the top result element.
1024 #  Then it executes [Q], again with X, and saves the top result.
1025 #  Finally it restores the stack to what it was below X and pushes the two
1026 #  results P(X) and Q(X).
1027 #  '''
1028 #  (Q, (P, (x, stack))) = S
1029 #  p = joy((x, stack), P, dictionary)[0][0]
1030 #  q = joy((x, stack), Q, dictionary)[0][0]
1031 #  return (q, (p, stack)), expression, dictionary
1032
1033
1034 @inscribe
1035 @FunctionWrapper
1036 def branch(stack, expression, dictionary):
1037         '''
1038         Use a Boolean value to select one of two quoted programs to run.
1039
1040         ::
1041
1042                         branch == roll< choice i
1043
1044         ::
1045
1046                                 False [F] [T] branch
1047                  --------------------------
1048                                                          F
1049
1050                                 True [F] [T] branch
1051                  -------------------------
1052                                                                         T
1053
1054         '''
1055         (then, (else_, (flag, stack))) = stack
1056         return stack, concat(then if flag else else_, expression), dictionary
1057
1058
1059 ##@inscribe
1060 ##@FunctionWrapper
1061 ##def ifte(stack, expression, dictionary):
1062 ##  '''
1063 ##  If-Then-Else Combinator
1064 ##  ::
1065 ##
1066 ##                  ... [if] [then] [else] ifte
1067 ##       ---------------------------------------------------
1068 ##          ... [[else] [then]] [...] [if] infra select i
1069 ##
1070 ##
1071 ##
1072 ##
1073 ##                ... [if] [then] [else] ifte
1074 ##       -------------------------------------------------------
1075 ##          ... [else] [then] [...] [if] infra first choice i
1076 ##
1077 ##
1078 ##  Has the effect of grabbing a copy of the stack on which to run the
1079 ##  if-part using infra.
1080 ##  '''
1081 ##  (else_, (then, (if_, stack))) = stack
1082 ##  expression = (S_infra, (S_first, (S_choice, (S_i, expression))))
1083 ##  stack = (if_, (stack, (then, (else_, stack))))
1084 ##  return stack, expression, dictionary
1085
1086
1087 @inscribe
1088 @FunctionWrapper
1089 def cond(stack, expression, dictionary):
1090         '''
1091         This combinator works like a case statement.  It expects a single quote
1092         on the stack that must contain zero or more condition quotes and a
1093         default quote.  Each condition clause should contain a quoted predicate
1094         followed by the function expression to run if that predicate returns
1095         true.  If no predicates return true the default function runs.
1096
1097         It works by rewriting into a chain of nested `ifte` expressions, e.g.::
1098
1099                                                 [[[B0] T0] [[B1] T1] [D]] cond
1100                         -----------------------------------------
1101                                  [B0] [T0] [[B1] [T1] [D] ifte] ifte
1102
1103         '''
1104         conditions, stack = stack
1105         if conditions:
1106                 expression = _cond(conditions, expression)
1107                 try:
1108                         # Attempt to preload the args to first ifte.
1109                         (P, (T, (E, expression))) = expression
1110                 except ValueError:
1111                         # If, for any reason, the argument to cond should happen to contain
1112                         # only the default clause then this optimization will fail.
1113                         pass
1114                 else:
1115                         stack = (E, (T, (P, stack)))
1116         return stack, expression, dictionary
1117
1118
1119 def _cond(conditions, expression):
1120         (clause, rest) = conditions
1121         if not rest:  # clause is [D]
1122                 return clause
1123         P, T = clause
1124         return (P, (T, (_cond(rest, ()), (S_ifte, expression))))
1125
1126
1127 @inscribe
1128 @FunctionWrapper
1129 def dip(stack, expression, dictionary):
1130         '''
1131         The dip combinator expects a quoted program on the stack and below it
1132         some item, it hoists the item into the expression and runs the program
1133         on the rest of the stack.
1134         ::
1135
1136                          ... x [Q] dip
1137                 -------------------
1138                                  ... Q x
1139
1140         '''
1141         (quote, (x, stack)) = stack
1142         expression = (x, expression)
1143         return stack, concat(quote, expression), dictionary
1144
1145
1146 @inscribe
1147 @FunctionWrapper
1148 def dipd(S, expression, dictionary):
1149         '''
1150         Like dip but expects two items.
1151         ::
1152
1153                          ... y x [Q] dip
1154                 ---------------------
1155                                  ... Q y x
1156
1157         '''
1158         (quote, (x, (y, stack))) = S
1159         expression = (y, (x, expression))
1160         return stack, concat(quote, expression), dictionary
1161
1162
1163 @inscribe
1164 @FunctionWrapper
1165 def dipdd(S, expression, dictionary):
1166         '''
1167         Like dip but expects three items.
1168         ::
1169
1170                          ... z y x [Q] dip
1171                 -----------------------
1172                                  ... Q z y x
1173
1174         '''
1175         (quote, (x, (y, (z, stack)))) = S
1176         expression = (z, (y, (x, expression)))
1177         return stack, concat(quote, expression), dictionary
1178
1179
1180 @inscribe
1181 @FunctionWrapper
1182 def app1(S, expression, dictionary):
1183         '''
1184         Given a quoted program on TOS and anything as the second stack item run
1185         the program and replace the two args with the first result of the
1186         program.
1187         ::
1188
1189                                                         ... x [Q] . app1
1190                  -----------------------------------
1191                                 ... [x ...] [Q] . infra first
1192         '''
1193         (quote, (x, stack)) = S
1194         stack = (quote, ((x, stack), stack))
1195         expression = (S_infra, (S_first, expression))
1196         return stack, expression, dictionary
1197
1198
1199 @inscribe
1200 @FunctionWrapper
1201 def app2(S, expression, dictionary):
1202         '''Like app1 with two items.
1203         ::
1204
1205                                                 ... y x [Q] . app2
1206                  -----------------------------------
1207                                 ... [y ...] [Q] . infra first
1208                                                 [x ...] [Q]   infra first
1209
1210         '''
1211         (quote, (x, (y, stack))) = S
1212         expression = (S_infra, (S_first,
1213                 ((x, stack), (quote, (S_infra, (S_first,
1214                         expression))))))
1215         stack = (quote, ((y, stack), stack))
1216         return stack, expression, dictionary
1217
1218
1219 @inscribe
1220 @FunctionWrapper
1221 def app3(S, expression, dictionary):
1222         '''Like app1 with three items.
1223         ::
1224
1225                                                 ... z y x [Q] . app3
1226                  -----------------------------------
1227                                 ... [z ...] [Q] . infra first
1228                                                 [y ...] [Q]   infra first
1229                                                 [x ...] [Q]   infra first
1230
1231         '''
1232         (quote, (x, (y, (z, stack)))) = S
1233         expression = (S_infra, (S_first,
1234                 ((y, stack), (quote, (S_infra, (S_first,
1235                 ((x, stack), (quote, (S_infra, (S_first,
1236                         expression))))))))))
1237         stack = (quote, ((z, stack), stack))
1238         return stack, expression, dictionary
1239
1240
1241 @inscribe
1242 @FunctionWrapper
1243 def step(S, expression, dictionary):
1244         '''
1245         Run a quoted program on each item in a sequence.
1246         ::
1247
1248                                         ... [] [Q] . step
1249                          -----------------------
1250                                                                  ... .
1251
1252
1253                                  ... [a] [Q] . step
1254                         ------------------------
1255                                                          ... a . Q
1256
1257
1258                          ... [a b c] [Q] . step
1259                 ----------------------------------------
1260                                                                  ... a . Q [b c] [Q] step
1261
1262         The step combinator executes the quotation on each member of the list
1263         on top of the stack.
1264         '''
1265         (quote, (aggregate, stack)) = S
1266         if not aggregate:
1267                 return stack, expression, dictionary
1268         head, tail = aggregate
1269         stack = quote, (head, stack)
1270         if tail:
1271                 expression = tail, (quote, (S_step, expression))
1272         expression = S_i, expression
1273         return stack, expression, dictionary
1274
1275
1276 @inscribe
1277 @FunctionWrapper
1278 def times(stack, expression, dictionary):
1279         '''
1280         times == [-- dip] cons [swap] infra [0 >] swap while pop
1281         ::
1282
1283                          ... n [Q] . times
1284                 ---------------------  w/ n <= 0
1285                                                  ... .
1286
1287
1288                          ... 1 [Q] . times
1289                 ---------------------------------
1290                                                  ... . Q
1291
1292
1293                          ... n [Q] . times
1294                 ---------------------------------  w/ n > 1
1295                                                  ... . Q (n - 1) [Q] times
1296
1297         '''
1298         # times == [-- dip] cons [swap] infra [0 >] swap while pop
1299         (quote, (n, stack)) = stack
1300         if n <= 0:
1301                 return stack, expression, dictionary
1302         n -= 1
1303         if n:
1304                 expression = n, (quote, (S_times, expression))
1305         expression = concat(quote, expression)
1306         return stack, expression, dictionary
1307
1308
1309 # The current definition above works like this:
1310
1311 #             [P] [Q] while
1312 # --------------------------------------
1313 #    [P] nullary [Q [P] nullary] loop
1314
1315 #   while == [pop i not] [popop] [dudipd] tailrec
1316
1317 #def while_(S, expression, dictionary):
1318 #  '''[if] [body] while'''
1319 #  (body, (if_, stack)) = S
1320 #  while joy(stack, if_, dictionary)[0][0]:
1321 #    stack = joy(stack, body, dictionary)[0]
1322 #  return stack, expression, dictionary
1323
1324
1325 @inscribe
1326 @FunctionWrapper
1327 def loop(stack, expression, dictionary):
1328         '''
1329         Basic loop combinator.
1330         ::
1331
1332                          ... True [Q] loop
1333                 -----------------------
1334                                         ... Q [Q] loop
1335
1336                          ... False [Q] loop
1337                 ------------------------
1338                                                         ...
1339
1340         '''
1341         quote, (flag, stack) = stack
1342         if flag:
1343                 expression = concat(quote, (quote, (S_loop, expression)))
1344         return stack, expression, dictionary
1345
1346
1347 @inscribe
1348 @FunctionWrapper
1349 def cmp_(stack, expression, dictionary):
1350         '''
1351         cmp takes two values and three quoted programs on the stack and runs
1352         one of the three depending on the results of comparing the two values:
1353         ::
1354
1355                                          a b [G] [E] [L] cmp
1356                                 ------------------------- a > b
1357                                                                 G
1358
1359                                          a b [G] [E] [L] cmp
1360                                 ------------------------- a = b
1361                                                                                 E
1362
1363                                          a b [G] [E] [L] cmp
1364                                 ------------------------- a < b
1365                                                                                                 L
1366         '''
1367         L, (E, (G, (b, (a, stack)))) = stack
1368         expression = concat(G if a > b else L if a < b else E, expression)
1369         return stack, expression, dictionary
1370
1371
1372 #  FunctionWrapper(cleave),
1373 #  FunctionWrapper(while_),
1374
1375
1376 for F in (
1377
1378         #divmod_ = pm = __(n2, n1), __(n4, n3)
1379
1380         BinaryBuiltinWrapper(operator.eq),
1381         BinaryBuiltinWrapper(operator.ge),
1382         BinaryBuiltinWrapper(operator.gt),
1383         BinaryBuiltinWrapper(operator.le),
1384         BinaryBuiltinWrapper(operator.lt),
1385         BinaryBuiltinWrapper(operator.ne),
1386
1387         BinaryBuiltinWrapper(operator.xor),
1388         BinaryBuiltinWrapper(operator.lshift),
1389         BinaryBuiltinWrapper(operator.rshift),
1390
1391         BinaryBuiltinWrapper(operator.and_),
1392         BinaryBuiltinWrapper(operator.or_),
1393
1394         BinaryBuiltinWrapper(operator.add),
1395         BinaryBuiltinWrapper(operator.floordiv),
1396         BinaryBuiltinWrapper(operator.mod),
1397         BinaryBuiltinWrapper(operator.mul),
1398         BinaryBuiltinWrapper(operator.pow),
1399         BinaryBuiltinWrapper(operator.sub),
1400         BinaryBuiltinWrapper(operator.truediv),
1401
1402         UnaryBuiltinWrapper(bool),
1403         UnaryBuiltinWrapper(operator.not_),
1404
1405         UnaryBuiltinWrapper(abs),
1406         UnaryBuiltinWrapper(operator.neg),
1407         UnaryBuiltinWrapper(sqrt),
1408
1409         UnaryBuiltinWrapper(floor),
1410         UnaryBuiltinWrapper(round),
1411         ):
1412         inscribe(F)
1413 del F  # Otherwise Sphinx autodoc will pick it up.
1414
1415
1416 for name, primitive in getmembers(genlib, isfunction):
1417         inscribe(SimpleFunctionWrapper(primitive))
1418
1419
1420 add_aliases(_dictionary, ALIASES)
1421
1422
1423 DefinitionWrapper.add_definitions(definitions, _dictionary)