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