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