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