joy/library.py

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