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 logging import getLogger
  28
  29 _log = getLogger(__name__)
  30 _log.info('Loading library.')
  31
  32 from inspect import getdoc
  33 from functools import wraps
  34 from itertools import count
  35 from inspect import getmembers, isfunction
  36 import operator, math
  37
  38 from .parser import text_to_expression, Symbol
  39 from .utils.stack import expression_to_string, list_to_stack, iter_stack, pick, concat
  40 from .utils.brutal_hackery import rename_code_object
  41
  42 from .utils import generated_library as genlib
  43 from .utils.types import (
  44   compose,
  45   ef,
  46   stack_effect,
  47   AnyJoyType,
  48   AnyStarJoyType,
  49   BooleanJoyType,
  50   NumberJoyType,
  51   NumberStarJoyType,
  52   StackJoyType,
  53   StackStarJoyType,
  54   FloatJoyType,
  55   IntJoyType,
  56   SymbolJoyType,
  57   CombinatorJoyType,
  58   TextJoyType,
  59   _functions,
  60   FUNCTIONS,
  61   infer,
  62   infer_expression,
  63   JoyTypeError,
  64   combinator_effect,
  65   poly_combinator_effect,
  66   doc_from_stack_effect,
  67   )
  68
  69
  70 _SYM_NUMS = count().next
  71 _COMB_NUMS = count().next
  72
  73
  74 _R = range(10)
  75 A = a0, a1, a2, a3, a4, a5, a6, a7, a8, a9 = map(AnyJoyType, _R)
  76 B = b0, b1, b2, b3, b4, b5, b6, b7, b8, b9 = map(BooleanJoyType, _R)
  77 N = n0, n1, n2, n3, n4, n5, n6, n7, n8, n9 = map(NumberJoyType, _R)
  78 S = s0, s1, s2, s3, s4, s5, s6, s7, s8, s9 = map(StackJoyType, _R)
  79 F = f0, f1, f2, f3, f4, f5, f6, f7, f8, f9 = map(FloatJoyType, _R)
  80 I = i0, i1, i2, i3, i4, i5, i6, i7, i8, i9 = map(IntJoyType, _R)
  81 T = t0, t1, t2, t3, t4, t5, t6, t7, t8, t9 = map(TextJoyType, _R)
  82
  83
  84 _R = range(1, 11)
  85 As = map(AnyStarJoyType, _R)
  86 Ns = map(NumberStarJoyType, _R)
  87 Ss = map(StackStarJoyType, _R)
  88
  89
  90 sec0 = stack_effect(t1)()
  91 sec1 = stack_effect(s0, i1)(s1)
  92 sec2 = stack_effect(s0, i1)(a1)
  93 sec_binary_cmp = stack_effect(n1, n2)(b1)
  94 sec_binary_ints = stack_effect(i1, i2)(i3)
  95 sec_binary_logic = stack_effect(b1, b2)(b3)
  96 sec_binary_math = stack_effect(n1, n2)(n3)
  97 sec_unary_logic = stack_effect(a1)(b1)
  98 sec_unary_math = stack_effect(n1)(n2)
  99 sec_Ns_math = stack_effect((Ns[1], s1),)(n0)
 100
 101 _dictionary = {}
 102
 103
 104 def inscribe(function):
 105   '''A decorator to inscribe functions into the default dictionary.'''
 106   _dictionary[function.name] = function
 107   return function
 108
 109
 110 def initialize():
 111   '''Return a dictionary of Joy functions for use with joy().'''
 112   return _dictionary.copy()
 113
 114
 115 ALIASES = (
 116   ('add', ['+']),
 117   ('and', ['&']),
 118   ('bool', ['truthy']),
 119   ('mul', ['*']),
 120   ('floordiv', ['/floor', '//']),
 121   ('floor', ['round']),
 122   ('truediv', ['/']),
 123   ('mod', ['%', 'rem', 'remainder', 'modulus']),
 124   ('eq', ['=']),
 125   ('ge', ['>=']),
 126   ('getitem', ['pick', 'at']),
 127   ('gt', ['>']),
 128   ('le', ['<=']),
 129   ('lshift', ['<<']),
 130   ('lt', ['<']),
 131   ('ne', ['<>', '!=']),
 132   ('rshift', ['>>']),
 133   ('sub', ['-']),
 134   ('xor', ['^']),
 135   ('succ', ['++']),
 136   ('pred', ['--']),
 137   ('rolldown', ['roll<']),
 138   ('rollup', ['roll>']),
 139   ('eh', ['?']),
 140   ('id', [u'•']),
 141   )
 142
 143
 144 def add_aliases(D, A):
 145   '''
 146   Given a dict and a iterable of (name, [alias, ...]) pairs, create
 147   additional entries in the dict mapping each alias to the named function
 148   if it's in the dict.  Aliases for functions not in the dict are ignored.
 149   '''
 150   for name, aliases in A:
 151     try:
 152       F = D[name]
 153     except KeyError:
 154       continue
 155     for alias in aliases:
 156       D[alias] = F
 157
 158
 159 def yin_functions():
 160   '''
 161   Return a dict of named stack effects.
 162
 163   "Yin" functions are those that only rearrange items in stacks and
 164   can be defined completely by their stack effects.  This means they
 165   can be auto-compiled.
 166   '''
 167   # pylint: disable=unused-variable
 168   cons = ef(a1, s0)((a1, s0))
 169   ccons = compose(cons, cons)
 170   dup = ef(a1)(a1, a1)
 171   dupd = ef(a2, a1)(a2, a2, a1)
 172   dupdd = ef(a3, a2, a1)(a3, a3, a2, a1)
 173   first = ef((a1, s1),)(a1,)
 174   over = ef(a2, a1)(a2, a1, a2)
 175   pop = ef(a1)()
 176   popd = ef(a2, a1,)(a1)
 177   popdd = ef(a3, a2, a1,)(a2, a1,)
 178   popop = ef(a2, a1,)()
 179   popopd = ef(a3, a2, a1,)(a1)
 180   popopdd = ef(a4, a3, a2, a1,)(a2, a1)
 181   rest = ef((a1, s0),)(s0,)
 182   rolldown = ef(a1, a2, a3)(a2, a3, a1)
 183   rollup = ef(a1, a2, a3)(a3, a1, a2)
 184   rrest = compose(rest, rest)
 185   second = compose(rest, first)
 186   stack = s0, (s0, s0)
 187   swaack = (s1, s0), (s0, s1)
 188   swap = ef(a1, a2)(a2, a1)
 189   swons = compose(swap, cons)
 190   third = compose(rest, second)
 191   tuck = ef(a2, a1)(a1, a2, a1)
 192   uncons = ef((a1, s0),)(a1, s0)
 193   unswons = compose(uncons, swap)
 194   stuncons = compose(stack, uncons)
 195   stununcons = compose(stack, uncons, uncons)
 196   unit = ef(a1)((a1, ()))
 197
 198   first_two = compose(uncons, uncons, pop)
 199   fourth = compose(rest, third)
 200
 201   _Tree_add_Ee = compose(pop, swap, rolldown, rrest, ccons)
 202   _Tree_get_E = compose(popop, second)
 203   _Tree_delete_clear_stuff = compose(rollup, popop, rest)
 204   _Tree_delete_R0 = compose(over, first, swap, dup)
 205
 206   return locals()
 207
 208
 209 definitions = ('''\
 210 ii == [dip] dupdip i
 211 of == swap at
 212 product == 1 swap [*] step
 213 flatten == [] swap [concat] step
 214 quoted == [unit] dip
 215 unquoted == [i] dip
 216 enstacken == stack [clear] dip
 217 ? == dup truthy
 218 disenstacken == ? [uncons ?] loop pop
 219 dinfrirst == dip infra first
 220 nullary == [stack] dinfrirst
 221 unary == nullary popd
 222 binary == nullary [popop] dip
 223 ternary == unary [popop] dip
 224 pam == [i] map
 225 run == [] swap infra
 226 sqr == dup mul
 227 size == 0 swap [pop ++] step
 228 fork == [i] app2
 229 cleave == fork [popd] dip
 230 average == [sum 1.0 *] [size] cleave /
 231 gcd == 1 [tuck modulus dup 0 >] loop pop
 232 least_fraction == dup [gcd] infra [div] concat map
 233 *fraction == [uncons] dip uncons [swap] dip concat [*] infra [*] dip cons
 234 *fraction0 == concat [[swap] dip * [*] dip] infra
 235 down_to_zero == [0 >] [dup --] while
 236 range_to_zero == unit [down_to_zero] infra
 237 anamorphism == [pop []] swap [dip swons] genrec
 238 range == [0 <=] [1 - dup] anamorphism
 239 while == swap [nullary] cons dup dipd concat loop
 240 dupdipd == dup dipd
 241 primrec == [i] genrec
 242 step_zero == 0 roll> step
 243 codireco == cons dip rest cons
 244 make_generator == [codireco] ccons
 245 ifte == [nullary not] dipd branch
 246 '''
 247 #
 248 #
 249 # ifte == [nullary] dipd swap branch
 250 # genrec == [[genrec] cons cons cons cons] nullary swons concat ifte
 251
 252 # Another definition for while. FWIW
 253 # while == over [[i] dip nullary] ccons [nullary] dip loop
 254
 255 ##ccons == cons cons
 256 ##unit == [] cons
 257 ##second == rest first
 258 ##third == rest rest first
 259 ##swons == swap cons
 260 ##swoncat == swap concat
 261
 262 ##Zipper
 263 ##z-down == [] swap uncons swap
 264 ##z-up == swons swap shunt
 265 ##z-right == [swons] cons dip uncons swap
 266 ##z-left == swons [uncons swap] dip swap
 267
 268 ##Quadratic Formula
 269 ##divisor == popop 2 *
 270 ##minusb == pop neg
 271 ##radical == swap dup * rollup * 4 * - sqrt
 272 ##root1 == + swap /
 273 ##root2 == - swap /
 274 ##q0 == [[divisor] [minusb] [radical]] pam
 275 ##q1 == [[root1] [root2]] pam
 276 ##quadratic == [q0] ternary i [q1] ternary
 277
 278 # Project Euler
 279 ##'''\
 280 ##PE1.1 == + dup [+] dip
 281 ##PE1.2 == dup [3 & PE1.1] dip 2 >>
 282 ##PE1.3 == 14811 swap [PE1.2] times pop
 283 ##PE1 == 0 0 66 [7 PE1.3] times 4 PE1.3 pop
 284 ##'''
 285 #PE1.2 == [PE1.1] step
 286 #PE1 == 0 0 66 [[3 2 1 3 1 2 3] PE1.2] times [3 2 1 3] PE1.2 pop
 287 )
 288
 289
 290 def FunctionWrapper(f):
 291   '''Set name attribute.'''
 292   if not f.__doc__:
 293     raise ValueError('Function %s must have doc string.' % f.__name__)
 294   f.name = f.__name__.rstrip('_')  # Don't shadow builtins.
 295   return f
 296
 297
 298 def SimpleFunctionWrapper(f):
 299   '''
 300   Wrap functions that take and return just a stack.
 301   '''
 302   @FunctionWrapper
 303   @wraps(f)
 304   @rename_code_object(f.__name__)
 305   def inner(stack, expression, dictionary):
 306     return f(stack), expression, dictionary
 307   return inner
 308
 309
 310 def BinaryBuiltinWrapper(f):
 311   '''
 312   Wrap functions that take two arguments and return a single result.
 313   '''
 314   @FunctionWrapper
 315   @wraps(f)
 316   @rename_code_object(f.__name__)
 317   def inner(stack, expression, dictionary):
 318     (a, (b, stack)) = stack
 319     result = f(b, a)
 320     return (result, stack), expression, dictionary
 321   return inner
 322
 323
 324 def UnaryBuiltinWrapper(f):
 325   '''
 326   Wrap functions that take one argument and return a single result.
 327   '''
 328   @FunctionWrapper
 329   @wraps(f)
 330   @rename_code_object(f.__name__)
 331   def inner(stack, expression, dictionary):
 332     (a, stack) = stack
 333     result = f(a)
 334     return (result, stack), expression, dictionary
 335   return inner
 336
 337
 338 class DefinitionWrapper(object):
 339   '''
 340   Provide implementation of defined functions, and some helper methods.
 341   '''
 342
 343   def __init__(self, name, body_text, doc=None):
 344     self.name = self.__name__ = name
 345     self.body = text_to_expression(body_text)
 346     self._body = tuple(iter_stack(self.body))
 347     self.__doc__ = doc or body_text
 348     self._compiled = None
 349
 350   def __call__(self, stack, expression, dictionary):
 351     if self._compiled:
 352       return self._compiled(stack, expression, dictionary)  # pylint: disable=E1102
 353     expression = list_to_stack(self._body, expression)
 354     return stack, expression, dictionary
 355
 356   @classmethod
 357   def parse_definition(class_, defi):
 358     '''
 359     Given some text describing a Joy function definition parse it and
 360     return a DefinitionWrapper.
 361     '''
 362     name, proper, body_text = (n.strip() for n in defi.partition('=='))
 363     if not proper:
 364       raise ValueError('Definition %r failed' % (defi,))
 365     return class_(name, body_text)
 366
 367   @classmethod
 368   def add_definitions(class_, defs, dictionary):
 369     '''
 370     Scan multi-line string defs for definitions and add them to the
 371     dictionary.
 372     '''
 373     for definition in _text_to_defs(defs):
 374       class_.add_def(definition, dictionary)
 375
 376   @classmethod
 377   def add_def(class_, definition, dictionary, fail_fails=False):
 378     '''
 379     Add the definition to the dictionary.
 380     '''
 381     F = class_.parse_definition(definition)
 382     _log.info('Adding definition %s := %s', F.name, expression_to_string(F.body))
 383     dictionary[F.name] = F
 384
 385   @classmethod
 386   def load_definitions(class_, filename, dictionary):
 387     with open(filename) as f:
 388       lines = [line for line in f if '==' in line]
 389     for line in lines:
 390       class_.add_def(line, dictionary)
 391
 392
 393 def _text_to_defs(text):
 394   return (line.strip() for line in text.splitlines() if '==' in line)
 395
 396
 397 #
 398 # Functions
 399 #
 400
 401
 402 @inscribe
 403 @sec0
 404 @FunctionWrapper
 405 def inscribe_(stack, expression, dictionary):
 406   '''
 407   Create a new Joy function definition in the Joy dictionary.  A
 408   definition is given as a string with a name followed by a double
 409   equal sign then one or more Joy functions, the body. for example:
 410
 411       sqr == dup mul
 412
 413   If you want the definition to persist over restarts, enter it into
 414   the definitions.txt resource.
 415   '''
 416   definition, stack = stack
 417   DefinitionWrapper.add_def(definition, dictionary, fail_fails=True)
 418   return stack, expression, dictionary
 419
 420
 421 @inscribe
 422 @SimpleFunctionWrapper
 423 def parse(stack):
 424   '''Parse the string on the stack to a Joy expression.'''
 425   text, stack = stack
 426   expression = text_to_expression(text)
 427   return expression, stack
 428
 429
 430 @inscribe
 431 @SimpleFunctionWrapper
 432 def infer_(stack):
 433   '''Attempt to infer the stack effect of a Joy expression.'''
 434   E, stack = stack
 435   effects = infer_expression(E)
 436   e = list_to_stack([(fi, (fo, ())) for fi, fo in effects])
 437   return e, stack
 438
 439
 440 @inscribe
 441 @sec2
 442 @SimpleFunctionWrapper
 443 def getitem(stack):
 444   '''
 445   ::
 446
 447     getitem == drop first
 448
 449   Expects an integer and a quote on the stack and returns the item at the
 450   nth position in the quote counting from 0.
 451   ::
 452
 453        [a b c d] 0 getitem
 454     -------------------------
 455                 a
 456
 457   '''
 458   n, (Q, stack) = stack
 459   return pick(Q, n), stack
 460
 461
 462 @inscribe
 463 @sec1
 464 @SimpleFunctionWrapper
 465 def drop(stack):
 466   '''
 467   ::
 468
 469     drop == [rest] times
 470
 471   Expects an integer and a quote on the stack and returns the quote with
 472   n items removed off the top.
 473   ::
 474
 475        [a b c d] 2 drop
 476     ----------------------
 477            [c d]
 478
 479   '''
 480   n, (Q, stack) = stack
 481   while n > 0:
 482     try:
 483       _, Q = Q
 484     except ValueError:
 485       raise IndexError
 486     n -= 1
 487   return Q, stack
 488
 489
 490 @inscribe
 491 @sec1
 492 @SimpleFunctionWrapper
 493 def take(stack):
 494   '''
 495   Expects an integer and a quote on the stack and returns the quote with
 496   just the top n items in reverse order (because that's easier and you can
 497   use reverse if needed.)
 498   ::
 499
 500        [a b c d] 2 take
 501     ----------------------
 502            [b a]
 503
 504   '''
 505   n, (Q, stack) = stack
 506   x = ()
 507   while n > 0:
 508     try:
 509       item, Q = Q
 510     except ValueError:
 511       raise IndexError
 512     x = item, x
 513     n -= 1
 514   return x, stack
 515
 516
 517 @inscribe
 518 @SimpleFunctionWrapper
 519 def choice(stack):
 520   '''
 521   Use a Boolean value to select one of two items.
 522   ::
 523
 524         A B False choice
 525      ----------------------
 526                A
 527
 528
 529         A B True choice
 530      ---------------------
 531                B
 532
 533   Currently Python semantics are used to evaluate the "truthiness" of the
 534   Boolean value (so empty string, zero, etc. are counted as false, etc.)
 535   '''
 536   (if_, (then, (else_, stack))) = stack
 537   return then if if_ else else_, stack
 538
 539
 540 @inscribe
 541 @SimpleFunctionWrapper
 542 def select(stack):
 543   '''
 544   Use a Boolean value to select one of two items from a sequence.
 545   ::
 546
 547         [A B] False select
 548      ------------------------
 549                 A
 550
 551
 552         [A B] True select
 553      -----------------------
 554                B
 555
 556   The sequence can contain more than two items but not fewer.
 557   Currently Python semantics are used to evaluate the "truthiness" of the
 558   Boolean value (so empty string, zero, etc. are counted as false, etc.)
 559   '''
 560   (flag, (choices, stack)) = stack
 561   (else_, (then, _)) = choices
 562   return then if flag else else_, stack
 563
 564
 565 @inscribe
 566 @sec_Ns_math
 567 @SimpleFunctionWrapper
 568 def max_(S):
 569   '''Given a list find the maximum.'''
 570   tos, stack = S
 571   return max(iter_stack(tos)), stack
 572
 573
 574 @inscribe
 575 @sec_Ns_math
 576 @SimpleFunctionWrapper
 577 def min_(S):
 578   '''Given a list find the minimum.'''
 579   tos, stack = S
 580   return min(iter_stack(tos)), stack
 581
 582
 583 @inscribe
 584 @sec_Ns_math
 585 @SimpleFunctionWrapper
 586 def sum_(S):
 587   '''Given a quoted sequence of numbers return the sum.
 588
 589   sum == 0 swap [+] step
 590   '''
 591   tos, stack = S
 592   return sum(iter_stack(tos)), stack
 593
 594
 595 @inscribe
 596 @SimpleFunctionWrapper
 597 def remove(S):
 598   '''
 599   Expects an item on the stack and a quote under it and removes that item
 600   from the the quote.  The item is only removed once.
 601   ::
 602
 603        [1 2 3 1] 1 remove
 604     ------------------------
 605             [2 3 1]
 606
 607   '''
 608   (tos, (second, stack)) = S
 609   l = list(iter_stack(second))
 610   l.remove(tos)
 611   return list_to_stack(l), stack
 612
 613
 614 @inscribe
 615 @SimpleFunctionWrapper
 616 def unique(S):
 617   '''Given a list remove duplicate items.'''
 618   tos, stack = S
 619   I = list(iter_stack(tos))
 620   return list_to_stack(sorted(set(I), key=I.index)), stack
 621
 622
 623 @inscribe
 624 @SimpleFunctionWrapper
 625 def sort_(S):
 626   '''Given a list return it sorted.'''
 627   tos, stack = S
 628   return list_to_stack(sorted(iter_stack(tos))), stack
 629
 630
 631 _functions['clear'] = s0, s1
 632 @inscribe
 633 @SimpleFunctionWrapper
 634 def clear(stack):
 635   '''Clear everything from the stack.
 636   ::
 637
 638     clear == stack [pop stack] loop
 639
 640        ... clear
 641     ---------------
 642
 643   '''
 644   return ()
 645
 646
 647 @inscribe
 648 @SimpleFunctionWrapper
 649 def unstack(stack):
 650   '''
 651   The unstack operator expects a list on top of the stack and makes that
 652   the stack discarding the rest of the stack.
 653   '''
 654   return stack[0]
 655
 656
 657 @inscribe
 658 @SimpleFunctionWrapper
 659 def reverse(S):
 660   '''Reverse the list on the top of the stack.
 661   ::
 662
 663     reverse == [] swap shunt
 664   '''
 665   (tos, stack) = S
 666   res = ()
 667   for term in iter_stack(tos):
 668     res = term, res
 669   return res, stack
 670
 671
 672 @inscribe
 673 @combinator_effect(_COMB_NUMS(), s7, s6)
 674 @SimpleFunctionWrapper
 675 def concat_(S):
 676   '''Concatinate the two lists on the top of the stack.
 677   ::
 678
 679        [a b c] [d e f] concat
 680     ----------------------------
 681            [a b c d e f]
 682
 683 '''
 684   (tos, (second, stack)) = S
 685   return concat(second, tos), stack
 686
 687
 688 @inscribe
 689 @SimpleFunctionWrapper
 690 def shunt(stack):
 691   '''Like concat but reverses the top list into the second.
 692   ::
 693
 694     shunt == [swons] step == reverse swap concat
 695
 696        [a b c] [d e f] shunt
 697     ---------------------------
 698          [f e d a b c]
 699
 700   '''
 701   (tos, (second, stack)) = stack
 702   while tos:
 703     term, tos = tos
 704     second = term, second
 705   return second, stack
 706
 707
 708 @inscribe
 709 @SimpleFunctionWrapper
 710 def zip_(S):
 711   '''
 712   Replace the two lists on the top of the stack with a list of the pairs
 713   from each list.  The smallest list sets the length of the result list.
 714   '''
 715   (tos, (second, stack)) = S
 716   accumulator = [
 717     (a, (b, ()))
 718     for a, b in zip(iter_stack(tos), iter_stack(second))
 719     ]
 720   return list_to_stack(accumulator), stack
 721
 722
 723 @inscribe
 724 @sec_unary_math
 725 @SimpleFunctionWrapper
 726 def succ(S):
 727   '''Increment TOS.'''
 728   (tos, stack) = S
 729   return tos + 1, stack
 730
 731
 732 @inscribe
 733 @sec_unary_math
 734 @SimpleFunctionWrapper
 735 def pred(S):
 736   '''Decrement TOS.'''
 737   (tos, stack) = S
 738   return tos - 1, stack
 739
 740
 741 @inscribe
 742 @SimpleFunctionWrapper
 743 def pm(stack):
 744   '''
 745   Plus or minus
 746   ::
 747
 748        a b pm
 749     -------------
 750        a+b a-b
 751
 752   '''
 753   a, (b, stack) = stack
 754   p, m, = b + a, b - a
 755   return m, (p, stack)
 756
 757
 758 def floor(n):
 759   return int(math.floor(n))
 760
 761 floor.__doc__ = math.floor.__doc__
 762
 763
 764 @inscribe
 765 @SimpleFunctionWrapper
 766 def divmod_(S):
 767   '''
 768   divmod(x, y) -> (quotient, remainder)
 769
 770   Return the tuple (x//y, x%y).  Invariant: div*y + mod == x.
 771   '''
 772   a, (b, stack) = S
 773   d, m = divmod(a, b)
 774   return d, (m, stack)
 775
 776
 777 def sqrt(a):
 778   '''
 779   Return the square root of the number a.
 780   Negative numbers return complex roots.
 781   '''
 782   try:
 783     r = math.sqrt(a)
 784   except ValueError:
 785     assert a < 0, repr(a)
 786     r = math.sqrt(-a) * 1j
 787   return r
 788
 789
 790 #def execute(S):
 791 #  (text, stack) = S
 792 #  if isinstance(text, str):
 793 #    return run(text, stack)
 794 #  return stack
 795
 796
 797 @inscribe
 798 @SimpleFunctionWrapper
 799 def id_(stack):
 800   '''The identity function.'''
 801   return stack
 802
 803
 804 @inscribe
 805 @SimpleFunctionWrapper
 806 def void(stack):
 807   '''True if the form on TOS is void otherwise False.'''
 808   form, stack = stack
 809   return _void(form), stack
 810
 811
 812 def _void(form):
 813   return any(not _void(i) for i in iter_stack(form))
 814
 815
 816
 817 ##  transpose
 818 ##  sign
 819 ##  take
 820
 821
 822 @inscribe
 823 @FunctionWrapper
 824 def words(stack, expression, dictionary):
 825   '''Print all the words in alphabetical order.'''
 826   print(' '.join(sorted(dictionary)))
 827   return stack, expression, dictionary
 828
 829
 830 @inscribe
 831 @FunctionWrapper
 832 def sharing(stack, expression, dictionary):
 833   '''Print redistribution information.'''
 834   print("You may convey verbatim copies of the Program's source code as"
 835         ' you receive it, in any medium, provided that you conspicuously'
 836         ' and appropriately publish on each copy an appropriate copyright'
 837         ' notice; keep intact all notices stating that this License and'
 838         ' any non-permissive terms added in accord with section 7 apply'
 839         ' to the code; keep intact all notices of the absence of any'
 840         ' warranty; and give all recipients a copy of this License along'
 841         ' with the Program.'
 842         ' You should have received a copy of the GNU General Public License'
 843         ' along with Thun.  If not see <http://www.gnu.org/licenses/>.')
 844   return stack, expression, dictionary
 845
 846
 847 @inscribe
 848 @FunctionWrapper
 849 def warranty(stack, expression, dictionary):
 850   '''Print warranty information.'''
 851   print('THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY'
 852         ' APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE'
 853         ' COPYRIGHT HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM'
 854         ' "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR'
 855         ' IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES'
 856         ' OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE'
 857         ' ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS'
 858         ' WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE'
 859         ' COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION.')
 860   return stack, expression, dictionary
 861
 862
 863 # def simple_manual(stack):
 864 #   '''
 865 #   Print words and help for each word.
 866 #   '''
 867 #   for name, f in sorted(FUNCTIONS.items()):
 868 #     d = getdoc(f)
 869 #     boxline = '+%s+' % ('-' * (len(name) + 2))
 870 #     print('\n'.join((
 871 #       boxline,
 872 #       '| %s |' % (name,),
 873 #       boxline,
 874 #       d if d else '   ...',
 875 #       '',
 876 #       '--' * 40,
 877 #       '',
 878 #       )))
 879 #   return stack
 880
 881
 882 @inscribe
 883 @FunctionWrapper
 884 def help_(S, expression, dictionary):
 885   '''Accepts a quoted symbol on the top of the stack and prints its docs.'''
 886   ((symbol, _), stack) = S
 887   word = dictionary[symbol]
 888   print(getdoc(word))
 889   return stack, expression, dictionary
 890
 891
 892 #
 893 # § Combinators
 894 #
 895
 896
 897 # Several combinators depend on other words in their definitions,
 898 # we use symbols to prevent hard-coding these, so in theory, you
 899 # could change the word in the dictionary to use different semantics.
 900 S_choice = Symbol('choice')
 901 S_first = Symbol('first')
 902 S_getitem = Symbol('getitem')
 903 S_genrec = Symbol('genrec')
 904 S_loop = Symbol('loop')
 905 S_i = Symbol('i')
 906 S_ifte = Symbol('ifte')
 907 S_infra = Symbol('infra')
 908 S_pop = Symbol('pop')
 909 S_step = Symbol('step')
 910 S_times = Symbol('times')
 911 S_swaack = Symbol('swaack')
 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.  Does not affect the rest of the 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 add_aliases(YIN_STACK_EFFECTS, ALIASES)
1528
1529 # Load the auto-generated primitives into the dictionary.
1530 _functions.update(YIN_STACK_EFFECTS)
1531 # exec '''
1532
1533 # eh = compose(dup, bool)
1534 # sqr = compose(dup, mul)
1535 # of = compose(swap, at)
1536
1537 # ''' in dict(compose=compose), _functions
1538 for name in sorted(_functions):
1539   sec = _functions[name]
1540   F = FUNCTIONS[name] = SymbolJoyType(name, [sec], _SYM_NUMS())
1541   if name in YIN_STACK_EFFECTS:
1542     _log.info('Setting stack effect for Yin function %s := %s', F.name, doc_from_stack_effect(*sec))
1543
1544 for name, primitive in getmembers(genlib, isfunction):
1545   inscribe(SimpleFunctionWrapper(primitive))
1546
1547
1548 add_aliases(_dictionary, ALIASES)
1549 add_aliases(_functions, ALIASES)
1550 add_aliases(FUNCTIONS, ALIASES)
1551
1552
1553 DefinitionWrapper.add_definitions(definitions, _dictionary)
1554
1555
1556 EXPECTATIONS = dict(
1557   ifte=(s7, (s6, (s5, s4))),
1558   nullary=(s7, s6),
1559   run=(s7, s6),
1560 )
1561 EXPECTATIONS['while'] = (s7, (s6, s5))
1562
1563
1564 for name in '''
1565   dinfrirst
1566   nullary
1567   ifte
1568   run
1569   dupdipd codireco
1570   while
1571   '''.split():
1572   C = _dictionary[name]
1573   expect = EXPECTATIONS.get(name)
1574   if expect:
1575     sec = doc_from_stack_effect(expect)
1576     _log.info('Setting stack EXPECT for combinator %s := %s', C.name, sec)
1577   else:
1578     _log.info('combinator %s', C.name)
1579   FUNCTIONS[name] = CombinatorJoyType(name, [C], _COMB_NUMS(), expect)
1580
1581
1582 for name in ('''
1583   of quoted enstacken ?
1584   unary binary ternary
1585   sqr unquoted
1586   '''.split()):
1587   of_ = _dictionary[name]
1588   secs = infer_expression(of_.body)
1589   assert len(secs) == 1, repr(secs)
1590   _log.info(
1591     'Setting stack effect for definition %s := %s',
1592     name,
1593     doc_from_stack_effect(*secs[0]),
1594     )
1595   FUNCTIONS[name] = SymbolJoyType(name, infer_expression(of_.body), _SYM_NUMS())
1596
1597
1598 #sec_Ns_math(_dictionary['product'])
1599
1600 ##  product == 1 swap [*] step
1601 ##  flatten == [] swap [concat] step
1602 ##  disenstacken == ? [uncons ?] loop pop
1603 ##  pam == [i] map
1604 ##  size == 0 swap [pop ++] step
1605 ##  fork == [i] app2
1606 ##  cleave == fork [popd] dip
1607 ##  average == [sum 1.0 *] [size] cleave /
1608 ##  gcd == 1 [tuck modulus dup 0 >] loop pop
1609 ##  least_fraction == dup [gcd] infra [div] concat map
1610 ##  *fraction == [uncons] dip uncons [swap] dip concat [*] infra [*] dip cons
1611 ##  *fraction0 == concat [[swap] dip * [*] dip] infra
1612 ##  down_to_zero == [0 >] [dup --] while
1613 ##  range_to_zero == unit [down_to_zero] infra
1614 ##  anamorphism == [pop []] swap [dip swons] genrec
1615 ##  range == [0 <=] [1 - dup] anamorphism
1616 ##  while == swap [nullary] cons dup dipd concat loop
1617 ##  dupdipd == dup dipd
1618 ##  primrec == [i] genrec
1619 ##  step_zero == 0 roll> step
1620 ##  codireco == cons dip rest cons
1621 ##  make_generator == [codireco] ccons
1622 ##  ifte == [nullary not] dipd branch