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