OSDN Git Service

Do not let defs shadow built-ins.
[joypy/Thun.git] / joy / library.py
1 # -*- coding: utf-8 -*-
2 #
3 #    Copyright © 2014-2020 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 pkg_resources import resource_stream
27 from io import TextIOWrapper
28 from inspect import getdoc, getmembers, isfunction
29 from functools import wraps
30 from itertools import count
31 import operator, math
32
33 from . import __name__ as _joy_package_name
34 from .parser import text_to_expression, Symbol
35 from .utils import generated_library as genlib
36 from .utils.errors import (
37     NotAListError,
38     NotAnIntError,
39     StackUnderflowError,
40     )
41 from .utils.stack import (
42     concat,
43     expression_to_string,
44     iter_stack,
45     list_to_stack,
46     pick,
47     )
48
49
50 def default_defs(dictionary):
51     def_stream = TextIOWrapper(
52         resource_stream(_joy_package_name, 'defs.txt'),
53         encoding='UTF_8',
54         )
55     Def.load_definitions(def_stream, dictionary)
56
57
58 HELP_TEMPLATE = '''\
59
60 ==== Help on %s ====
61
62 %s
63
64 ---- end (%s)
65 '''
66
67
68 # This is the main dict we're building.
69 _dictionary = {}
70
71
72 def inscribe(function, d=_dictionary):
73     '''A decorator to inscribe functions into the default dictionary.'''
74     d[function.name] = function
75     return function
76
77
78 def initialize():
79     '''Return a dictionary of Joy functions for use with joy().'''
80     return _dictionary.copy()
81
82
83 ALIASES = (
84     ('add', ['+']),
85     ('and', ['&']),
86     ('bool', ['truthy']),
87     ('mul', ['*']),
88     ('floordiv', ['/floor', '//', '/', 'div']),
89     ('mod', ['%', 'rem', 'remainder', 'modulus']),
90     ('eq', ['=']),
91     ('ge', ['>=']),
92     ('getitem', ['pick', 'at']),
93     ('gt', ['>']),
94     ('le', ['<=']),
95     ('lshift', ['<<']),
96     ('lt', ['<']),
97     ('ne', ['<>', '!=']),
98     ('rshift', ['>>']),
99     ('sub', ['-']),
100     ('xor', ['^']),
101     ('succ', ['++']),
102     ('pred', ['--']),
103     ('rolldown', ['roll<']),
104     ('rollup', ['roll>']),
105     ('eh', ['?']),
106     ('id', [u'•']),
107     )
108
109
110 def add_aliases(D, A):
111     '''
112     Given a dict and a iterable of (name, [alias, ...]) pairs, create
113     additional entries in the dict mapping each alias to the named function
114     if it's in the dict.  Aliases for functions not in the dict are ignored.
115     '''
116     for name, aliases in A:
117         try:
118             F = D[name]
119         except KeyError:
120             continue
121         for alias in aliases:
122             D[alias] = F
123
124
125 def FunctionWrapper(f):
126     '''Set name attribute.'''
127     if not f.__doc__:
128         raise ValueError('Function %s must have doc string.' % f.__name__)
129     f.name = f.__name__.rstrip('_')  # Don't shadow builtins.
130     return f
131
132
133 def SimpleFunctionWrapper(f):
134     '''
135     Wrap functions that take and return just a stack.
136     '''
137     @FunctionWrapper
138     @wraps(f)
139     def inner(stack, expression, dictionary):
140         return f(stack), expression, dictionary
141     return inner
142
143
144 def BinaryBuiltinWrapper(f):
145     '''
146     Wrap functions that take two arguments and return a single result.
147     '''
148     @FunctionWrapper
149     @wraps(f)
150     def inner(stack, expression, dictionary):
151         try:
152             (a, (b, stack)) = stack
153         except ValueError:
154             raise StackUnderflowError('Not enough values on stack.')
155         # Boolean predicates like "or" fail here.  :(
156 ##        if (   not isinstance(a, int)
157 ##            or not isinstance(b, int)
158 ##            or isinstance(a, bool)  # Because bools are ints in Python.
159 ##            or isinstance(b, bool)
160 ##            ):
161 ##            raise NotAnIntError
162         result = f(b, a)
163         return (result, stack), expression, dictionary
164     return inner
165
166
167 def UnaryBuiltinWrapper(f):
168     '''
169     Wrap functions that take one argument and return a single result.
170     '''
171     @FunctionWrapper
172     @wraps(f)
173     def inner(stack, expression, dictionary):
174         (a, stack) = stack
175         result = f(a)
176         return (result, stack), expression, dictionary
177     return inner
178
179
180 class Def(object):
181     '''
182     Definitions created by inscribe.
183     '''
184
185     def __init__(self, name, body):
186         self.name = name
187         self.body = body
188         self._body = tuple(iter_stack(body))
189         self.__doc__ = expression_to_string(body)
190         self._compiled = None
191
192     def __call__(self, stack, expression, dictionary):
193         if self._compiled:
194             return self._compiled(stack, expression, dictionary)  # pylint: disable=E1102
195         expression = list_to_stack(self._body, expression)
196         return stack, expression, dictionary
197
198     @classmethod
199     def load_definitions(class_, stream, dictionary):
200         for line in stream:
201             if line.lstrip().startswith('#'):
202                 continue
203             name, body = text_to_expression(line)
204             if name not in dictionary:
205                 inscribe(class_(name, body), dictionary)
206 ##            inscribe(class_(name, body), dictionary)
207
208
209 #
210 # Functions
211 #
212
213
214 @inscribe
215 @FunctionWrapper
216 def inscribe_(stack, expression, dictionary):
217     '''
218     Create a new Joy function definition in the Joy dictionary.  A
219     definition is given as a quote with a name followed by a Joy
220     expression. for example:
221
222         [sqr dup mul] inscribe
223
224     '''
225     (name, body), stack = stack
226     inscribe(Def(name, body), dictionary)
227     return stack, expression, dictionary
228
229
230 @inscribe
231 @SimpleFunctionWrapper
232 def parse(stack):
233     '''Parse the string on the stack to a Joy expression.'''
234     text, stack = stack
235     expression = text_to_expression(text)
236     return expression, stack
237
238
239 # @inscribe
240 # @SimpleFunctionWrapper
241 # def infer_(stack):
242 #     '''Attempt to infer the stack effect of a Joy expression.'''
243 #     E, stack = stack
244 #     effects = infer_expression(E)
245 #     e = list_to_stack([(fi, (fo, ())) for fi, fo in effects])
246 #     return e, stack
247
248
249 @inscribe
250 @SimpleFunctionWrapper
251 def getitem(stack):
252     '''
253     ::
254
255         getitem == drop first
256
257     Expects an integer and a quote on the stack and returns the item at the
258     nth position in the quote counting from 0.
259     ::
260
261            [a b c d] 0 getitem
262         -------------------------
263             a
264
265     '''
266     n, (Q, stack) = stack
267     return pick(Q, n), stack
268
269
270 @inscribe
271 @SimpleFunctionWrapper
272 def drop(stack):
273     '''
274     ::
275
276         drop == [rest] times
277
278     Expects an integer and a quote on the stack and returns the quote with
279     n items removed off the top.
280     ::
281
282            [a b c d] 2 drop
283         ----------------------
284                [c d]
285
286     '''
287     n, (Q, stack) = stack
288     while n > 0:
289         try:
290             _, Q = Q
291         except ValueError:
292             raise IndexError
293         n -= 1
294     return Q, stack
295
296
297 @inscribe
298 @SimpleFunctionWrapper
299 def take(stack):
300     '''
301     Expects an integer and a quote on the stack and returns the quote with
302     just the top n items in reverse order (because that's easier and you can
303     use reverse if needed.)
304     ::
305
306            [a b c d] 2 take
307         ----------------------
308                [b a]
309
310     '''
311     n, (Q, stack) = stack
312     x = ()
313     while n > 0:
314         try:
315             item, Q = Q
316         except ValueError:
317             raise IndexError
318         x = item, x
319         n -= 1
320     return x, stack
321
322
323 @inscribe
324 @FunctionWrapper
325 def gcd2(stack, expression, dictionary):
326     '''Compiled GCD function.'''
327     (v1, (v2, stack)) = stack
328     tos = True
329     while tos:
330         v3 = v2 % v1
331         tos = v3 > 0
332         (v1, (v2, stack)) = (v3, (v1, stack))
333     return (v2, stack), expression, dictionary
334
335
336 @inscribe
337 @SimpleFunctionWrapper
338 def choice(stack):
339     '''
340     Use a Boolean value to select one of two items.
341     ::
342
343            A B False choice
344         ----------------------
345            A
346
347
348            A B True choice
349         ---------------------
350              B
351
352     Currently Python semantics are used to evaluate the "truthiness" of the
353     Boolean value (so empty string, zero, etc. are counted as false, etc.)
354     '''
355     (if_, (then, (else_, stack))) = stack
356     return then if if_ else else_, stack
357
358
359 @inscribe
360 @SimpleFunctionWrapper
361 def select(stack):
362     '''
363     Use a Boolean value to select one of two items from a sequence.
364     ::
365
366            [A B] False select
367         ------------------------
368             A
369
370
371            [A B] True select
372         -----------------------
373               B
374
375     The sequence can contain more than two items but not fewer.
376     Currently Python semantics are used to evaluate the "truthiness" of the
377     Boolean value (so empty string, zero, etc. are counted as false, etc.)
378     '''
379     (flag, (choices, stack)) = stack
380     (else_, (then, _)) = choices
381     return then if flag else else_, stack
382
383
384 @inscribe
385 @SimpleFunctionWrapper
386 def max_(S):
387     '''Given a list find the maximum.'''
388     tos, stack = S
389     return max(iter_stack(tos)), stack
390
391
392 @inscribe
393 @SimpleFunctionWrapper
394 def min_(S):
395     '''Given a list find the minimum.'''
396     tos, stack = S
397     return min(iter_stack(tos)), stack
398
399
400 @inscribe
401 @SimpleFunctionWrapper
402 def sum_(S):
403     '''
404     Given a quoted sequence of numbers return the sum.
405     ::
406
407         sum == 0 swap [+] step
408
409     '''
410     tos, stack = S
411     return sum(iter_stack(tos)), stack
412
413
414 @inscribe
415 @SimpleFunctionWrapper
416 def remove(S):
417     '''
418     Expects an item on the stack and a quote under it and removes that item
419     from the the quote.  The item is only removed once.
420     ::
421
422            [1 2 3 1] 1 remove
423         ------------------------
424              [2 3 1]
425
426     '''
427     (tos, (second, stack)) = S
428     l = list(iter_stack(second))
429     l.remove(tos)
430     return list_to_stack(l), stack
431
432
433 @inscribe
434 @SimpleFunctionWrapper
435 def unique(S):
436     '''Given a list remove duplicate items.'''
437     tos, stack = S
438     I = list(iter_stack(tos))
439     return list_to_stack(sorted(set(I), key=I.index)), stack
440
441
442 @inscribe
443 @SimpleFunctionWrapper
444 def sort_(S):
445     '''Given a list return it sorted.'''
446     tos, stack = S
447     return list_to_stack(sorted(iter_stack(tos))), stack
448
449
450 @inscribe
451 @SimpleFunctionWrapper
452 def clear(stack):
453     '''Clear everything from the stack.
454     ::
455
456         clear == stack [pop stack] loop
457
458            ... clear
459         ---------------
460
461     '''
462     return ()
463
464
465 @inscribe
466 @SimpleFunctionWrapper
467 def disenstacken(stack):
468     '''
469     The disenstacken operator expects a list on top of the stack and makes that
470     the stack discarding the rest of the stack.
471     '''
472     return stack[0]
473
474
475 @inscribe
476 @SimpleFunctionWrapper
477 def reverse(S):
478     '''
479     Reverse the list on the top of the stack.
480     ::
481
482         reverse == [] swap shunt
483     '''
484     (tos, stack) = S
485     res = ()
486     for term in iter_stack(tos):
487         res = term, res
488     return res, stack
489
490
491 @inscribe
492 @SimpleFunctionWrapper
493 def concat_(S):
494     '''
495     Concatinate the two lists on the top of the stack.
496     ::
497
498            [a b c] [d e f] concat
499         ----------------------------
500                [a b c d e f]
501
502     '''
503     (tos, (second, stack)) = S
504     return concat(second, tos), stack
505
506
507 @inscribe
508 @SimpleFunctionWrapper
509 def shunt(stack):
510     '''
511     Like concat but reverses the top list into the second.
512     ::
513
514         shunt == [swons] step == reverse swap concat
515
516            [a b c] [d e f] shunt
517         ---------------------------
518                [f e d a b c] 
519
520     '''
521     (tos, (second, stack)) = stack
522     while tos:
523         term, tos = tos
524         second = term, second
525     return second, stack
526
527
528 @inscribe
529 @SimpleFunctionWrapper
530 def zip_(S):
531     '''
532     Replace the two lists on the top of the stack with a list of the pairs
533     from each list.  The smallest list sets the length of the result list.
534     '''
535     (tos, (second, stack)) = S
536     accumulator = [
537         (a, (b, ()))
538         for a, b in zip(iter_stack(tos), iter_stack(second))
539         ]
540     return list_to_stack(accumulator), stack
541
542
543 @inscribe
544 @SimpleFunctionWrapper
545 def succ(S):
546     '''Increment TOS.'''
547     (tos, stack) = S
548     return tos + 1, stack
549
550
551 @inscribe
552 @SimpleFunctionWrapper
553 def pred(S):
554     '''Decrement TOS.'''
555     (tos, stack) = S
556     return tos - 1, stack
557
558
559 @inscribe
560 @SimpleFunctionWrapper
561 def pm(stack):
562     '''
563     Plus or minus
564     ::
565
566            a b pm
567         -------------
568            a+b a-b
569
570     '''
571     a, (b, stack) = stack
572     p, m, = b + a, b - a
573     return m, (p, stack)
574
575
576 def floor(n):
577     return int(math.floor(n))
578
579 floor.__doc__ = math.floor.__doc__
580
581
582 @inscribe
583 @SimpleFunctionWrapper
584 def divmod_(S):
585     '''
586     divmod(x, y) -> (quotient, remainder)
587
588     Return the tuple (x//y, x%y).  Invariant: q * y + r == x.
589     '''
590     a, (b, stack) = S
591     d, m = divmod(a, b)
592     return d, (m, stack)
593
594
595 def sqrt(a):
596     '''
597     Return the square root of the number a.
598     Negative numbers return complex roots.
599     '''
600     try:
601         r = math.sqrt(a)
602     except ValueError:
603         assert a < 0, repr(a)
604         r = math.sqrt(-a) * 1j
605     return r
606
607
608 #def execute(S):
609 #  (text, stack) = S
610 #  if isinstance(text, str):
611 #    return run(text, stack)
612 #  return stack
613
614
615 @inscribe
616 @SimpleFunctionWrapper
617 def id_(stack):
618     '''The identity function.'''
619     return stack
620
621
622 @inscribe
623 @SimpleFunctionWrapper
624 def void(stack):
625     '''True if the form on TOS is void otherwise False.'''
626     form, stack = stack
627     return _void(form), stack
628
629
630 def _void(form):
631     return any(not _void(i) for i in iter_stack(form))
632
633
634
635 ##  transpose
636 ##  sign
637 ##  take
638
639
640 @inscribe
641 @FunctionWrapper
642 def words(stack, expression, dictionary):
643     '''Print all the words in alphabetical order.'''
644     print(' '.join(sorted(dictionary)))
645     return stack, expression, dictionary
646
647
648 @inscribe
649 @FunctionWrapper
650 def sharing(stack, expression, dictionary):
651     '''Print redistribution information.'''
652     print("You may convey verbatim copies of the Program's source code as"
653     ' you receive it, in any medium, provided that you conspicuously'
654     ' and appropriately publish on each copy an appropriate copyright'
655     ' notice; keep intact all notices stating that this License and'
656     ' any non-permissive terms added in accord with section 7 apply'
657     ' to the code; keep intact all notices of the absence of any'
658     ' warranty; and give all recipients a copy of this License along'
659     ' with the Program.'
660     ' You should have received a copy of the GNU General Public License'
661     ' along with Thun.  If not see <http://www.gnu.org/licenses/>.')
662     return stack, expression, dictionary
663
664
665 @inscribe
666 @FunctionWrapper
667 def warranty(stack, expression, dictionary):
668     '''Print warranty information.'''
669     print('THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY'
670     ' APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE'
671     ' COPYRIGHT HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM'
672     ' "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR'
673     ' IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES'
674     ' OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE'
675     ' ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS'
676     ' WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE'
677     ' COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION.')
678     return stack, expression, dictionary
679
680
681 # def simple_manual(stack):
682 #   '''
683 #   Print words and help for each word.
684 #   '''
685 #   for name, f in sorted(FUNCTIONS.items()):
686 #     d = getdoc(f)
687 #     boxline = '+%s+' % ('-' * (len(name) + 2))
688 #     print('\n'.join((
689 #       boxline,
690 #       '| %s |' % (name,),
691 #       boxline,
692 #       d if d else '   ...',
693 #       '',
694 #       '--' * 40,
695 #       '',
696 #       )))
697 #   return stack
698
699
700 @inscribe
701 @FunctionWrapper
702 def help_(S, expression, dictionary):
703     '''Accepts a quoted symbol on the top of the stack and prints its docs.'''
704     ((symbol, _), stack) = S
705     word = dictionary[symbol]
706     print(HELP_TEMPLATE % (symbol, getdoc(word), symbol))
707     return stack, expression, dictionary
708
709
710 #
711 # § Combinators
712 #
713
714
715 # Several combinators depend on other words in their definitions,
716 # we use symbols to prevent hard-coding these, so in theory, you
717 # could change the word in the dictionary to use different semantics.
718 S_choice = Symbol('choice')
719 S_first = Symbol('first')
720 S_genrec = Symbol('genrec')
721 S_getitem = Symbol('getitem')
722 S_i = Symbol('i')
723 S_ifte = Symbol('ifte')
724 S_infra = Symbol('infra')
725 S_loop = Symbol('loop')
726 S_pop = Symbol('pop')
727 S_primrec = Symbol('primrec')
728 S_step = Symbol('step')
729 S_swaack = Symbol('swaack')
730 S_times = Symbol('times')
731
732
733 @inscribe
734 @FunctionWrapper
735 def i(stack, expression, dictionary):
736     '''
737     The i combinator expects a quoted program on the stack and unpacks it
738     onto the pending expression for evaluation.
739     ::
740
741            [Q] i
742         -----------
743             Q
744
745     '''
746     try:
747         quote, stack = stack
748     except ValueError:
749         raise StackUnderflowError('Not enough values on stack.')
750     return stack, concat(quote, expression), dictionary
751
752
753 @inscribe
754 @FunctionWrapper
755 def x(stack, expression, dictionary):
756     '''
757     ::
758
759         x == dup i
760
761         ... [Q] x = ... [Q] dup i
762         ... [Q] x = ... [Q] [Q] i
763         ... [Q] x = ... [Q]  Q
764
765     '''
766     quote, _ = stack
767     return stack, concat(quote, expression), dictionary
768
769
770 @inscribe
771 @FunctionWrapper
772 def b(stack, expression, dictionary):
773     '''
774     ::
775
776         b == [i] dip i
777
778         ... [P] [Q] b == ... [P] i [Q] i
779         ... [P] [Q] b == ... P Q
780
781     '''
782     q, (p, (stack)) = stack
783     return stack, concat(p, concat(q, expression)), dictionary
784
785
786 @inscribe
787 @FunctionWrapper
788 def dupdip(stack, expression, dictionary):
789     '''
790     ::
791
792         [F] dupdip == dup [F] dip
793
794         ... a [F] dupdip
795         ... a dup [F] dip
796         ... a a   [F] dip
797         ... a F a
798
799     '''
800     F, stack = stack
801     a = stack[0]
802     return stack, concat(F, (a,  expression)), dictionary
803
804
805 @inscribe
806 @FunctionWrapper
807 def infra(stack, expression, dictionary):
808     '''
809     Accept a quoted program and a list on the stack and run the program
810     with the list as its stack.  Does not affect the rest of the stack.
811     ::
812
813            ... [a b c] [Q] . infra
814         -----------------------------
815             c b a . Q [...] swaack
816
817     '''
818     (quote, (aggregate, stack)) = stack
819     return aggregate, concat(quote, (stack, (S_swaack, expression))), dictionary
820
821
822 @inscribe
823 @FunctionWrapper
824 def genrec(stack, expression, dictionary):
825     '''
826     General Recursion Combinator.
827     ::
828
829                   [if] [then] [rec1] [rec2] genrec
830         ---------------------------------------------------------------------
831            [if] [then] [rec1 [[if] [then] [rec1] [rec2] genrec] rec2] ifte
832
833     From "Recursion Theory and Joy" (j05cmp.html) by Manfred von Thun:
834     "The genrec combinator takes four program parameters in addition to
835     whatever data parameters it needs. Fourth from the top is an if-part,
836     followed by a then-part. If the if-part yields true, then the then-part
837     is executed and the combinator terminates. The other two parameters are
838     the rec1-part and the rec2-part. If the if-part yields false, the
839     rec1-part is executed. Following that the four program parameters and
840     the combinator are again pushed onto the stack bundled up in a quoted
841     form. Then the rec2-part is executed, where it will find the bundled
842     form. Typically it will then execute the bundled form, either with i or
843     with app2, or some other combinator."
844
845     The way to design one of these is to fix your base case [then] and the
846     test [if], and then treat rec1 and rec2 as an else-part "sandwiching"
847     a quotation of the whole function.
848
849     For example, given a (general recursive) function 'F':
850     ::
851
852         F == [I] [T] [R1] [R2] genrec
853
854     If the [I] if-part fails you must derive R1 and R2 from:
855     ::
856
857         ... R1 [F] R2
858
859     Just set the stack arguments in front, and figure out what R1 and R2
860     have to do to apply the quoted [F] in the proper way.  In effect, the
861     genrec combinator turns into an ifte combinator with a quoted copy of
862     the original definition in the else-part:
863     ::
864
865         F == [I] [T] [R1]   [R2] genrec
866           == [I] [T] [R1 [F] R2] ifte
867
868     Primitive recursive functions are those where R2 == i.
869     ::
870
871         P == [I] [T] [R] tailrec
872           == [I] [T] [R [P] i] ifte
873           == [I] [T] [R P] ifte
874
875     '''
876     (rec2, (rec1, stack)) = stack
877     (then, (if_, _)) = stack
878     F = (if_, (then, (rec1, (rec2, (S_genrec, ())))))
879     else_ = concat(rec1, (F, rec2))
880     return (else_, stack), (S_ifte, expression), dictionary
881
882
883 @inscribe
884 @FunctionWrapper
885 def map_(S, expression, dictionary):
886     '''
887     Run the quoted program on TOS on the items in the list under it, push a
888     new list with the results in place of the program and original list.
889     '''
890     # (quote, (aggregate, stack)) = S
891     # results = list_to_stack([
892     # joy((term, stack), quote, dictionary)[0][0]
893     # for term in iter_stack(aggregate)
894     # ])
895     # return (results, stack), expression, dictionary
896     (quote, (aggregate, stack)) = S
897     if not aggregate:
898         return (aggregate, stack), expression, dictionary
899     batch = ()
900     for term in iter_stack(aggregate):
901         s = term, stack
902         batch = (s, (quote, (S_infra, (S_first, batch))))
903     stack = (batch, ((), stack))
904     return stack, (S_infra, expression), dictionary
905
906
907 @inscribe
908 @FunctionWrapper
909 def primrec(stack, expression, dictionary):
910     '''
911     From the "Overview of the language JOY":
912
913     > The primrec combinator expects two quoted programs in addition to a
914     data parameter. For an integer data parameter it works like this: If
915     the data parameter is zero, then the first quotation has to produce
916     the value to be returned. If the data parameter is positive then the
917     second has to combine the data parameter with the result of applying
918     the function to its predecessor.::
919
920         5  [1]  [*]  primrec
921
922     > Then primrec tests whether the top element on the stack (initially
923     the 5) is equal to zero. If it is, it pops it off and executes one of
924     the quotations, the [1] which leaves 1 on the stack as the result.
925     Otherwise it pushes a decremented copy of the top element and
926     recurses. On the way back from the recursion it uses the other
927     quotation, [*], to multiply what is now a factorial on top of the
928     stack by the second element on the stack.::
929
930         n [Base] [Recur] primrec
931
932            0 [Base] [Recur] primrec
933         ------------------------------
934               Base
935
936              n [Base] [Recur] primrec
937         ------------------------------------------ n > 0
938            n (n-1) [Base] [Recur] primrec Recur
939
940     '''
941     recur, (base, (n, stack)) = stack
942     if n <= 0:
943         expression = concat(base, expression)
944     else:
945         expression = S_primrec, concat(recur, expression)
946         stack = recur, (base, (n - 1, (n, stack)))
947     return stack, expression, dictionary
948
949
950 #def cleave(S, expression, dictionary):
951 #  '''
952 #  The cleave combinator expects two quotations, and below that an item X.
953 #  It first executes [P], with X on top, and saves the top result element.
954 #  Then it executes [Q], again with X, and saves the top result.
955 #  Finally it restores the stack to what it was below X and pushes the two
956 #  results P(X) and Q(X).
957 #  '''
958 #  (Q, (P, (x, stack))) = S
959 #  p = joy((x, stack), P, dictionary)[0][0]
960 #  q = joy((x, stack), Q, dictionary)[0][0]
961 #  return (q, (p, stack)), expression, dictionary
962
963
964 @inscribe
965 @FunctionWrapper
966 def branch(stack, expression, dictionary):
967     '''
968     Use a Boolean value to select one of two quoted programs to run.
969
970     ::
971
972         branch == roll< choice i
973
974     ::
975
976            False [F] [T] branch
977         --------------------------
978               F
979
980            True [F] [T] branch
981         -------------------------
982                  T
983
984     '''
985     (then, (else_, (flag, stack))) = stack
986     return stack, concat(then if flag else else_, expression), dictionary
987
988
989 ##@inscribe
990 ##@FunctionWrapper
991 ##def ifte(stack, expression, dictionary):
992 ##  '''
993 ##  If-Then-Else Combinator
994 ##  ::
995 ##
996 ##                  ... [if] [then] [else] ifte
997 ##       ---------------------------------------------------
998 ##          ... [[else] [then]] [...] [if] infra select i
999 ##
1000 ##
1001 ##
1002 ##
1003 ##                ... [if] [then] [else] ifte
1004 ##       -------------------------------------------------------
1005 ##          ... [else] [then] [...] [if] infra first choice i
1006 ##
1007 ##
1008 ##  Has the effect of grabbing a copy of the stack on which to run the
1009 ##  if-part using infra.
1010 ##  '''
1011 ##  (else_, (then, (if_, stack))) = stack
1012 ##  expression = (S_infra, (S_first, (S_choice, (S_i, expression))))
1013 ##  stack = (if_, (stack, (then, (else_, stack))))
1014 ##  return stack, expression, dictionary
1015
1016
1017 @inscribe
1018 @FunctionWrapper
1019 def cond(stack, expression, dictionary):
1020     '''
1021     This combinator works like a case statement.  It expects a single quote
1022     on the stack that must contain zero or more condition quotes and a 
1023     default quote.  Each condition clause should contain a quoted predicate
1024     followed by the function expression to run if that predicate returns
1025     true.  If no predicates return true the default function runs.
1026
1027     It works by rewriting into a chain of nested `ifte` expressions, e.g.::
1028
1029               [[[B0] T0] [[B1] T1] [D]] cond
1030         -----------------------------------------
1031            [B0] [T0] [[B1] [T1] [D] ifte] ifte
1032
1033     '''
1034     conditions, stack = stack
1035     if conditions:
1036         expression = _cond(conditions, expression)
1037         try:
1038             # Attempt to preload the args to first ifte.
1039             (P, (T, (E, expression))) = expression
1040         except ValueError:
1041             # If, for any reason, the argument to cond should happen to contain
1042             # only the default clause then this optimization will fail.
1043             pass
1044         else:
1045             stack = (E, (T, (P, stack)))
1046     return stack, expression, dictionary
1047
1048
1049 def _cond(conditions, expression):
1050     (clause, rest) = conditions
1051     if not rest:  # clause is [D]
1052         return clause
1053     P, T = clause
1054     return (P, (T, (_cond(rest, ()), (S_ifte, expression))))
1055
1056
1057 @inscribe
1058 @FunctionWrapper
1059 def dip(stack, expression, dictionary):
1060     '''
1061     The dip combinator expects a quoted program on the stack and below it
1062     some item, it hoists the item into the expression and runs the program
1063     on the rest of the stack.
1064     ::
1065
1066            ... x [Q] dip
1067         -------------------
1068              ... Q x
1069
1070     '''
1071     try:
1072         (quote, (x, stack)) = stack
1073     except ValueError:
1074         raise StackUnderflowError('Not enough values on stack.')
1075     expression = (x, expression)
1076     return stack, concat(quote, expression), dictionary
1077
1078
1079 @inscribe
1080 @FunctionWrapper
1081 def dipd(S, expression, dictionary):
1082     '''
1083     Like dip but expects two items.
1084     ::
1085
1086            ... y x [Q] dip
1087         ---------------------
1088              ... Q y x
1089
1090     '''
1091     (quote, (x, (y, stack))) = S
1092     expression = (y, (x, expression))
1093     return stack, concat(quote, expression), dictionary
1094
1095
1096 @inscribe
1097 @FunctionWrapper
1098 def dipdd(S, expression, dictionary):
1099     '''
1100     Like dip but expects three items.
1101     ::
1102
1103            ... z y x [Q] dip
1104         -----------------------
1105              ... Q z y x
1106
1107     '''
1108     (quote, (x, (y, (z, stack)))) = S
1109     expression = (z, (y, (x, expression)))
1110     return stack, concat(quote, expression), dictionary
1111
1112
1113 @inscribe
1114 @FunctionWrapper
1115 def app1(S, expression, dictionary):
1116     '''
1117     Given a quoted program on TOS and anything as the second stack item run
1118     the program and replace the two args with the first result of the
1119     program.
1120     ::
1121
1122              ... x [Q] . app1
1123         -----------------------------------
1124            ... [x ...] [Q] . infra first
1125
1126     '''
1127     (quote, (x, stack)) = S
1128     stack = (quote, ((x, stack), stack))
1129     expression = (S_infra, (S_first, expression))
1130     return stack, expression, dictionary
1131
1132
1133 @inscribe
1134 @FunctionWrapper
1135 def app2(S, expression, dictionary):
1136     '''Like app1 with two items.
1137     ::
1138
1139                ... y x [Q] . app2
1140         -----------------------------------
1141            ... [y ...] [Q] . infra first
1142                [x ...] [Q]   infra first
1143
1144     '''
1145     (quote, (x, (y, stack))) = S
1146     expression = (S_infra, (S_first,
1147         ((x, stack), (quote, (S_infra, (S_first,
1148             expression))))))
1149     stack = (quote, ((y, stack), stack))
1150     return stack, expression, dictionary
1151
1152
1153 @inscribe
1154 @FunctionWrapper
1155 def app3(S, expression, dictionary):
1156     '''Like app1 with three items.
1157     ::
1158
1159              ... z y x [Q] . app3
1160         -----------------------------------
1161            ... [z ...] [Q] . infra first
1162                [y ...] [Q]   infra first
1163                [x ...] [Q]   infra first
1164
1165     '''
1166     (quote, (x, (y, (z, stack)))) = S
1167     expression = (S_infra, (S_first,
1168         ((y, stack), (quote, (S_infra, (S_first,
1169         ((x, stack), (quote, (S_infra, (S_first,
1170             expression))))))))))
1171     stack = (quote, ((z, stack), stack))
1172     return stack, expression, dictionary
1173
1174
1175 @inscribe
1176 @FunctionWrapper
1177 def step(S, expression, dictionary):
1178     '''
1179     Run a quoted program on each item in a sequence.
1180     ::
1181
1182            ... [] [Q] . step
1183         -----------------------
1184               ... .
1185
1186
1187            ... [a] [Q] . step
1188         ------------------------
1189              ... a . Q
1190
1191
1192            ... [a b c] [Q] . step
1193         ----------------------------------------
1194                  ... a . Q [b c] [Q] step
1195
1196     The step combinator executes the quotation on each member of the list
1197     on top of the stack.
1198     '''
1199     (quote, (aggregate, stack)) = S
1200     if not aggregate:
1201         return stack, expression, dictionary
1202     head, tail = aggregate
1203     stack = quote, (head, stack)
1204     if tail:
1205         expression = tail, (quote, (S_step, expression))
1206     expression = S_i, expression
1207     return stack, expression, dictionary
1208
1209
1210 @inscribe
1211 @FunctionWrapper
1212 def times(stack, expression, dictionary):
1213     '''
1214     times == [-- dip] cons [swap] infra [0 >] swap while pop
1215     ::
1216
1217            ... n [Q] . times
1218         ---------------------  w/ n <= 0
1219              ... .
1220
1221
1222            ... 1 [Q] . times
1223         -----------------------
1224              ... . Q
1225
1226
1227            ... n [Q] . times
1228         -------------------------------------  w/ n > 1
1229              ... . Q (n - 1) [Q] times
1230
1231     '''
1232     # times == [-- dip] cons [swap] infra [0 >] swap while pop
1233     (quote, (n, stack)) = stack
1234     if n <= 0:
1235         return stack, expression, dictionary
1236     n -= 1
1237     if n:
1238         expression = n, (quote, (S_times, expression))
1239     expression = concat(quote, expression)
1240     return stack, expression, dictionary
1241
1242
1243 # The current definition above works like this:
1244
1245 #             [P] [Q] while
1246 # --------------------------------------
1247 #    [P] nullary [Q [P] nullary] loop
1248
1249 #   while == [pop i not] [popop] [dudipd] tailrec
1250
1251 #def while_(S, expression, dictionary):
1252 #  '''[if] [body] while'''
1253 #  (body, (if_, stack)) = S
1254 #  while joy(stack, if_, dictionary)[0][0]:
1255 #    stack = joy(stack, body, dictionary)[0]
1256 #  return stack, expression, dictionary
1257
1258
1259 @inscribe
1260 @FunctionWrapper
1261 def loop(stack, expression, dictionary):
1262     '''
1263     Basic loop combinator.
1264     ::
1265
1266            ... True [Q] loop
1267         -----------------------
1268               ... Q [Q] loop
1269
1270            ... False [Q] loop
1271         ------------------------
1272               ...
1273
1274     '''
1275     try:
1276         quote, stack = stack
1277     except ValueError:
1278         raise StackUnderflowError('Not enough values on stack.')
1279     if not isinstance(quote, tuple):
1280         raise NotAListError('Loop body not a list.')
1281     try:
1282         (flag, stack) = stack
1283     except ValueError:
1284         raise StackUnderflowError('Not enough values on stack.')
1285     if flag:
1286         expression = concat(quote, (quote, (S_loop, expression)))
1287     return stack, expression, dictionary
1288
1289
1290 @inscribe
1291 @FunctionWrapper
1292 def cmp_(stack, expression, dictionary):
1293     '''
1294     cmp takes two values and three quoted programs on the stack and runs
1295     one of the three depending on the results of comparing the two values:
1296     ::
1297
1298            a b [G] [E] [L] cmp
1299         ------------------------- a > b
1300             G
1301
1302            a b [G] [E] [L] cmp
1303         ------------------------- a = b
1304                 E
1305
1306            a b [G] [E] [L] cmp
1307         ------------------------- a < b
1308                 L
1309     '''
1310     L, (E, (G, (b, (a, stack)))) = stack
1311     expression = concat(G if a > b else L if a < b else E, expression)
1312     return stack, expression, dictionary
1313
1314
1315 #  FunctionWrapper(cleave),
1316 #  FunctionWrapper(while_),
1317
1318
1319 for F in (
1320
1321     #divmod_ = pm = __(n2, n1), __(n4, n3)
1322
1323     BinaryBuiltinWrapper(operator.eq),
1324     BinaryBuiltinWrapper(operator.ge),
1325     BinaryBuiltinWrapper(operator.gt),
1326     BinaryBuiltinWrapper(operator.le),
1327     BinaryBuiltinWrapper(operator.lt),
1328     BinaryBuiltinWrapper(operator.ne),
1329
1330     BinaryBuiltinWrapper(operator.xor),
1331     BinaryBuiltinWrapper(operator.lshift),
1332     BinaryBuiltinWrapper(operator.rshift),
1333
1334     BinaryBuiltinWrapper(operator.and_),
1335     BinaryBuiltinWrapper(operator.or_),
1336
1337     BinaryBuiltinWrapper(operator.add),
1338     BinaryBuiltinWrapper(operator.floordiv),
1339     BinaryBuiltinWrapper(operator.mod),
1340     BinaryBuiltinWrapper(operator.mul),
1341     BinaryBuiltinWrapper(operator.pow),
1342     BinaryBuiltinWrapper(operator.sub),
1343 ##    BinaryBuiltinWrapper(operator.truediv),
1344
1345     UnaryBuiltinWrapper(bool),
1346     UnaryBuiltinWrapper(operator.not_),
1347
1348     UnaryBuiltinWrapper(abs),
1349     UnaryBuiltinWrapper(operator.neg),
1350     UnaryBuiltinWrapper(sqrt),
1351
1352     UnaryBuiltinWrapper(floor),
1353     UnaryBuiltinWrapper(round),
1354     ):
1355     inscribe(F)
1356 del F  # Otherwise Sphinx autodoc will pick it up.
1357
1358
1359 for name, primitive in getmembers(genlib, isfunction):
1360     inscribe(SimpleFunctionWrapper(primitive))
1361
1362
1363 add_aliases(_dictionary, ALIASES)