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