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