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