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 swoncat == swap concat
 252 '''
 253 #
 254 #
 255 # ifte == [nullary] dipd swap branch
 256 # genrec == [[genrec] cons cons cons cons] nullary swons concat ifte
 257
 258 # Another definition for while. FWIW
 259 # while == over [[i] dip nullary] ccons [nullary] dip loop
 260
 261 ##ccons == cons cons
 262 ##unit == [] cons
 263 ##second == rest first
 264 ##third == rest rest first
 265 ##swons == swap cons
 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