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