joy/library.py

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