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