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