joy/library.py

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