joy/library.py

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