joy/library.py

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