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 ii == [dip] dupdip i
 210 of == swap at
 211 product == 1 swap [*] step
 212 flatten == [] swap [concat] step
 213 quoted == [unit] dip
 214 unquoted == [i] dip
 215 enstacken == stack [clear] dip
 216 ? == dup truthy
 217 disenstacken == ? [uncons ?] loop pop
 218 dinfrirst == dip infra first
 219 nullary == [stack] dinfrirst
 220 unary == nullary popd
 221 binary == nullary [popop] dip
 222 ternary == unary [popop] dip
 223 pam == [i] map
 224 run == [] swap infra
 225 sqr == dup mul
 226 size == 0 swap [pop ++] step
 227 fork == [i] app2
 228 cleave == fork [popd] dip
 229 average == [sum 1.0 *] [size] cleave /
 230 gcd == 1 [tuck modulus dup 0 >] loop pop
 231 least_fraction == dup [gcd] infra [div] concat map
 232 *fraction == [uncons] dip uncons [swap] dip concat [*] infra [*] dip cons
 233 *fraction0 == concat [[swap] dip * [*] dip] infra
 234 down_to_zero == [0 >] [dup --] while
 235 range_to_zero == unit [down_to_zero] infra
 236 anamorphism == [pop []] swap [dip swons] genrec
 237 range == [0 <=] [1 - dup] anamorphism
 238 while == swap [nullary] cons dup dipd concat loop
 239 dupdipd == dup dipd
 240 primrec == [i] genrec
 241 step_zero == 0 roll> step
 242 codireco == cons dip rest cons
 243 make_generator == [codireco] ccons
 244 ifte == [nullary not] dipd branch
 245 '''
 246 #
 247 #
 248 # ifte == [nullary] dipd swap branch
 249 # genrec == [[genrec] cons cons cons cons] nullary swons concat ifte
 250
 251 # Another definition for while. FWIW
 252 # while == over [[i] dip nullary] ccons [nullary] dip loop
 253
 254 ##ccons == cons cons
 255 ##unit == [] cons
 256 ##second == rest first
 257 ##third == rest rest first
 258 ##swons == swap cons
 259 ##swoncat == swap concat
 260
 261 ##Zipper
 262 ##z-down == [] swap uncons swap
 263 ##z-up == swons swap shunt
 264 ##z-right == [swons] cons dip uncons swap
 265 ##z-left == swons [uncons swap] dip swap
 266
 267 ##Quadratic Formula
 268 ##divisor == popop 2 *
 269 ##minusb == pop neg
 270 ##radical == swap dup * rollup * 4 * - sqrt
 271 ##root1 == + swap /
 272 ##root2 == - swap /
 273 ##q0 == [[divisor] [minusb] [radical]] pam
 274 ##q1 == [[root1] [root2]] pam
 275 ##quadratic == [q0] ternary i [q1] ternary
 276
 277 # Project Euler
 278 ##'''\
 279 ##PE1.1 == + dup [+] dip
 280 ##PE1.2 == dup [3 & PE1.1] dip 2 >>
 281 ##PE1.3 == 14811 swap [PE1.2] times pop
 282 ##PE1 == 0 0 66 [7 PE1.3] times 4 PE1.3 pop
 283 ##'''
 284 #PE1.2 == [PE1.1] step
 285 #PE1 == 0 0 66 [[3 2 1 3 1 2 3] PE1.2] times [3 2 1 3] PE1.2 pop
 286 )
 287
 288
 289 def FunctionWrapper(f):
 290   '''Set name attribute.'''
 291   if not f.__doc__:
 292     raise ValueError('Function %s must have doc string.' % f.__name__)
 293   f.name = f.__name__.rstrip('_')  # Don't shadow builtins.
 294   return f
 295
 296
 297 def SimpleFunctionWrapper(f):
 298   '''
 299   Wrap functions that take and return just a stack.
 300   '''
 301   @FunctionWrapper
 302   @wraps(f)
 303   @rename_code_object(f.__name__)
 304   def inner(stack, expression, dictionary):
 305     return f(stack), expression, dictionary
 306   return inner
 307
 308
 309 def BinaryBuiltinWrapper(f):
 310   '''
 311   Wrap functions that take two arguments and return a single result.
 312   '''
 313   @FunctionWrapper
 314   @wraps(f)
 315   @rename_code_object(f.__name__)
 316   def inner(stack, expression, dictionary):
 317     (a, (b, stack)) = stack
 318     result = f(b, a)
 319     return (result, stack), expression, dictionary
 320   return inner
 321
 322
 323 def UnaryBuiltinWrapper(f):
 324   '''
 325   Wrap functions that take one argument and return a single result.
 326   '''
 327   @FunctionWrapper
 328   @wraps(f)
 329   @rename_code_object(f.__name__)
 330   def inner(stack, expression, dictionary):
 331     (a, stack) = stack
 332     result = f(a)
 333     return (result, stack), expression, dictionary
 334   return inner
 335
 336
 337 class DefinitionWrapper(object):
 338   '''
 339   Provide implementation of defined functions, and some helper methods.
 340   '''
 341
 342   def __init__(self, name, body_text, doc=None):
 343     self.name = self.__name__ = name
 344     self.body = text_to_expression(body_text)
 345     self._body = tuple(iter_stack(self.body))
 346     self.__doc__ = doc or body_text
 347     self._compiled = None
 348
 349   def __call__(self, stack, expression, dictionary):
 350     if self._compiled:
 351       return self._compiled(stack, expression, dictionary)  # pylint: disable=E1102
 352     expression = list_to_stack(self._body, expression)
 353     return stack, expression, dictionary
 354
 355   @classmethod
 356   def parse_definition(class_, defi):
 357     '''
 358     Given some text describing a Joy function definition parse it and
 359     return a DefinitionWrapper.
 360     '''
 361     name, proper, body_text = (n.strip() for n in defi.partition('=='))
 362     if not proper:
 363       raise ValueError('Definition %r failed' % (defi,))
 364     return class_(name, body_text)
 365
 366   @classmethod
 367   def add_definitions(class_, defs, dictionary):
 368     '''
 369     Scan multi-line string defs for definitions and add them to the
 370     dictionary.
 371     '''
 372     for definition in _text_to_defs(defs):
 373       class_.add_def(definition, dictionary)
 374
 375   @classmethod
 376   def add_def(class_, definition, dictionary, fail_fails=False):
 377     '''
 378     Add the definition to the dictionary.
 379     '''
 380     F = class_.parse_definition(definition)
 381     _log.info('Adding definition %s := %s', F.name, expression_to_string(F.body))
 382     dictionary[F.name] = F
 383
 384   @classmethod
 385   def load_definitions(class_, filename, dictionary):
 386     with open(filename) as f:
 387       lines = [line for line in f if '==' in line]
 388     for line in lines:
 389       class_.add_def(line, dictionary)
 390
 391
 392 def _text_to_defs(text):
 393   return (line.strip() for line in text.splitlines() if '==' in line)
 394
 395
 396 #
 397 # Functions
 398 #
 399
 400
 401 @inscribe
 402 @sec0
 403 @FunctionWrapper
 404 def inscribe_(stack, expression, dictionary):
 405   '''
 406   Create a new Joy function definition in the Joy dictionary.  A
 407   definition is given as a string with a name followed by a double
 408   equal sign then one or more Joy functions, the body. for example:
 409
 410       sqr == dup mul
 411
 412   If you want the definition to persist over restarts, enter it into
 413   the definitions.txt resource.
 414   '''
 415   definition, stack = stack
 416   DefinitionWrapper.add_def(definition, dictionary, fail_fails=True)
 417   return stack, expression, dictionary
 418
 419
 420 @inscribe
 421 @SimpleFunctionWrapper
 422 def parse(stack):
 423   '''Parse the string on the stack to a Joy expression.'''
 424   text, stack = stack
 425   expression = text_to_expression(text)
 426   return expression, stack
 427
 428
 429 @inscribe
 430 @SimpleFunctionWrapper
 431 def infer_(stack):
 432   '''Attempt to infer the stack effect of a Joy expression.'''
 433   E, stack = stack
 434   effects = infer_expression(E)
 435   e = list_to_stack([(fi, (fo, ())) for fi, fo in effects])
 436   return e, stack
 437
 438
 439 @inscribe
 440 @sec2
 441 @SimpleFunctionWrapper
 442 def getitem(stack):
 443   '''
 444   ::
 445
 446     getitem == drop first
 447
 448   Expects an integer and a quote on the stack and returns the item at the
 449   nth position in the quote counting from 0.
 450   ::
 451
 452        [a b c d] 0 getitem
 453     -------------------------
 454                 a
 455
 456   '''
 457   n, (Q, stack) = stack
 458   return pick(Q, n), stack
 459
 460
 461 @inscribe
 462 @sec1
 463 @SimpleFunctionWrapper
 464 def drop(stack):
 465   '''
 466   ::
 467
 468     drop == [rest] times
 469
 470   Expects an integer and a quote on the stack and returns the quote with
 471   n items removed off the top.
 472   ::
 473
 474        [a b c d] 2 drop
 475     ----------------------
 476            [c d]
 477
 478   '''
 479   n, (Q, stack) = stack
 480   while n > 0:
 481     try:
 482       _, Q = Q
 483     except ValueError:
 484       raise IndexError
 485     n -= 1
 486   return Q, stack
 487
 488
 489 @inscribe
 490 @sec1
 491 @SimpleFunctionWrapper
 492 def take(stack):
 493   '''
 494   Expects an integer and a quote on the stack and returns the quote with
 495   just the top n items in reverse order (because that's easier and you can
 496   use reverse if needed.)
 497   ::
 498
 499        [a b c d] 2 take
 500     ----------------------
 501            [b a]
 502
 503   '''
 504   n, (Q, stack) = stack
 505   x = ()
 506   while n > 0:
 507     try:
 508       item, Q = Q
 509     except ValueError:
 510       raise IndexError
 511     x = item, x
 512     n -= 1
 513   return x, stack
 514
 515
 516 @inscribe
 517 @SimpleFunctionWrapper
 518 def choice(stack):
 519   '''
 520   Use a Boolean value to select one of two items.
 521   ::
 522
 523         A B False choice
 524      ----------------------
 525                A
 526
 527
 528         A B True choice
 529      ---------------------
 530                B
 531
 532   Currently Python semantics are used to evaluate the "truthiness" of the
 533   Boolean value (so empty string, zero, etc. are counted as false, etc.)
 534   '''
 535   (if_, (then, (else_, stack))) = stack
 536   return then if if_ else else_, stack
 537
 538
 539 @inscribe
 540 @SimpleFunctionWrapper
 541 def select(stack):
 542   '''
 543   Use a Boolean value to select one of two items from a sequence.
 544   ::
 545
 546         [A B] False select
 547      ------------------------
 548                 A
 549
 550
 551         [A B] True select
 552      -----------------------
 553                B
 554
 555   The sequence can contain more than two items but not fewer.
 556   Currently Python semantics are used to evaluate the "truthiness" of the
 557   Boolean value (so empty string, zero, etc. are counted as false, etc.)
 558   '''
 559   (flag, (choices, stack)) = stack
 560   (else_, (then, _)) = choices
 561   return then if flag else else_, stack
 562
 563
 564 @inscribe
 565 @sec_Ns_math
 566 @SimpleFunctionWrapper
 567 def max_(S):
 568   '''Given a list find the maximum.'''
 569   tos, stack = S
 570   return max(iter_stack(tos)), stack
 571
 572
 573 @inscribe
 574 @sec_Ns_math
 575 @SimpleFunctionWrapper
 576 def min_(S):
 577   '''Given a list find the minimum.'''
 578   tos, stack = S
 579   return min(iter_stack(tos)), stack
 580
 581
 582 @inscribe
 583 @sec_Ns_math
 584 @SimpleFunctionWrapper
 585 def sum_(S):
 586   '''Given a quoted sequence of numbers return the sum.
 587
 588   sum == 0 swap [+] step
 589   '''
 590   tos, stack = S
 591   return sum(iter_stack(tos)), stack
 592
 593
 594 @inscribe
 595 @SimpleFunctionWrapper
 596 def remove(S):
 597   '''
 598   Expects an item on the stack and a quote under it and removes that item
 599   from the the quote.  The item is only removed once.
 600   ::
 601
 602        [1 2 3 1] 1 remove
 603     ------------------------
 604             [2 3 1]
 605
 606   '''
 607   (tos, (second, stack)) = S
 608   l = list(iter_stack(second))
 609   l.remove(tos)
 610   return list_to_stack(l), stack
 611
 612
 613 @inscribe
 614 @SimpleFunctionWrapper
 615 def unique(S):
 616   '''Given a list remove duplicate items.'''
 617   tos, stack = S
 618   I = list(iter_stack(tos))
 619   list_to_stack(sorted(set(I), key=I.index))
 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