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