joy/library.py

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