1 # -*- coding: utf-8 -*-
3 # Copyright © 2014, 2015, 2017, 2018 Simon Forman
5 # This file is part of Thun
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.
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.
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/>.
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()
26 from __future__ import print_function
27 from builtins import map
28 from builtins import zip
29 from builtins import range
30 from builtins import object
31 from logging import getLogger
33 _log = getLogger(__name__)
34 _log.info('Loading library.')
36 from inspect import getdoc
37 from functools import wraps
38 from itertools import count
39 from inspect import getmembers, isfunction
42 from .parser import text_to_expression, Symbol
43 from .utils.stack import expression_to_string, list_to_stack, iter_stack, pick, concat
45 if sys.version_info.major < 3:
46 from .utils.brutal_hackery import rename_code_object
48 rename_code_object = lambda _: lambda f: f
50 from .utils import generated_library as genlib
51 from .utils.types import (
73 poly_combinator_effect,
74 doc_from_stack_effect,
78 _SYM_NUMS = lambda c=count(): next(c)
79 _COMB_NUMS = lambda c=count(): next(c)
83 A = a0, a1, a2, a3, a4, a5, a6, a7, a8, a9 = list(map(AnyJoyType, _R))
84 B = b0, b1, b2, b3, b4, b5, b6, b7, b8, b9 = list(map(BooleanJoyType, _R))
85 N = n0, n1, n2, n3, n4, n5, n6, n7, n8, n9 = list(map(NumberJoyType, _R))
86 S = s0, s1, s2, s3, s4, s5, s6, s7, s8, s9 = list(map(StackJoyType, _R))
87 F = f0, f1, f2, f3, f4, f5, f6, f7, f8, f9 = list(map(FloatJoyType, _R))
88 I = i0, i1, i2, i3, i4, i5, i6, i7, i8, i9 = list(map(IntJoyType, _R))
89 T = t0, t1, t2, t3, t4, t5, t6, t7, t8, t9 = list(map(TextJoyType, _R))
92 _R = list(range(1, 11))
93 As = list(map(AnyStarJoyType, _R))
94 Ns = list(map(NumberStarJoyType, _R))
95 Ss = list(map(StackStarJoyType, _R))
98 sec0 = stack_effect(t1)()
99 sec1 = stack_effect(s0, i1)(s1)
100 sec2 = stack_effect(s0, i1)(a1)
101 sec_binary_cmp = stack_effect(n1, n2)(b1)
102 sec_binary_ints = stack_effect(i1, i2)(i3)
103 sec_binary_logic = stack_effect(b1, b2)(b3)
104 sec_binary_math = stack_effect(n1, n2)(n3)
105 sec_unary_logic = stack_effect(a1)(b1)
106 sec_unary_math = stack_effect(n1)(n2)
107 sec_Ns_math = stack_effect((Ns[1], s1),)(n0)
112 def inscribe(function):
113 '''A decorator to inscribe functions into the default dictionary.'''
114 _dictionary[function.name] = function
119 '''Return a dictionary of Joy functions for use with joy().'''
120 return _dictionary.copy()
126 ('bool', ['truthy']),
128 ('floordiv', ['/floor', '//']),
129 ('floor', ['round']),
131 ('mod', ['%', 'rem', 'remainder', 'modulus']),
134 ('getitem', ['pick', 'at']),
139 ('ne', ['<>', '!=']),
145 ('rolldown', ['roll<']),
146 ('rollup', ['roll>']),
152 def add_aliases(D, A):
154 Given a dict and a iterable of (name, [alias, ...]) pairs, create
155 additional entries in the dict mapping each alias to the named function
156 if it's in the dict. Aliases for functions not in the dict are ignored.
158 for name, aliases in A:
163 for alias in aliases:
169 Return a dict of named stack effects.
171 "Yin" functions are those that only rearrange items in stacks and
172 can be defined completely by their stack effects. This means they
173 can be auto-compiled.
175 # pylint: disable=unused-variable
176 cons = ef(a1, s0)((a1, s0))
177 ccons = compose(cons, cons)
179 dupd = ef(a2, a1)(a2, a2, a1)
180 dupdd = ef(a3, a2, a1)(a3, a3, a2, a1)
181 first = ef((a1, s1),)(a1,)
182 over = ef(a2, a1)(a2, a1, a2)
184 popd = ef(a2, a1,)(a1)
185 popdd = ef(a3, a2, a1,)(a2, a1,)
186 popop = ef(a2, a1,)()
187 popopd = ef(a3, a2, a1,)(a1)
188 popopdd = ef(a4, a3, a2, a1,)(a2, a1)
189 rest = ef((a1, s0),)(s0,)
190 rolldown = ef(a1, a2, a3)(a2, a3, a1)
191 rollup = ef(a1, a2, a3)(a3, a1, a2)
192 rrest = compose(rest, rest)
193 second = compose(rest, first)
195 swaack = (s1, s0), (s0, s1)
196 swap = ef(a1, a2)(a2, a1)
197 swons = compose(swap, cons)
198 third = compose(rest, second)
199 tuck = ef(a2, a1)(a1, a2, a1)
200 uncons = ef((a1, s0),)(a1, s0)
201 unswons = compose(uncons, swap)
202 stuncons = compose(stack, uncons)
203 stununcons = compose(stack, uncons, uncons)
204 unit = ef(a1)((a1, ()))
206 first_two = compose(uncons, uncons, pop)
207 fourth = compose(rest, third)
209 _Tree_add_Ee = compose(pop, swap, rolldown, rrest, ccons)
210 _Tree_get_E = compose(popop, second)
211 _Tree_delete_clear_stuff = compose(rollup, popop, rest)
212 _Tree_delete_R0 = compose(over, first, swap, dup)
220 product == 1 swap [*] step
221 flatten == [] swap [concat] step
224 enstacken == stack [clear] dip
226 disenstacken == ? [uncons ?] loop pop
227 dinfrirst == dip infra first
228 nullary == [stack] dinfrirst
229 unary == nullary popd
230 binary == nullary [popop] dip
231 ternary == unary [popop] dip
235 size == 0 swap [pop ++] step
237 cleave == fork [popd] dip
238 average == [sum 1.0 *] [size] cleave /
239 gcd == 1 [tuck modulus dup 0 >] loop pop
240 least_fraction == dup [gcd] infra [div] concat map
241 *fraction == [uncons] dip uncons [swap] dip concat [*] infra [*] dip cons
242 *fraction0 == concat [[swap] dip * [*] dip] infra
243 down_to_zero == [0 >] [dup --] while
244 range_to_zero == unit [down_to_zero] infra
245 anamorphism == [pop []] swap [dip swons] genrec
246 range == [0 <=] [1 - dup] anamorphism
247 while == swap [nullary] cons dup dipd concat loop
249 primrec == [i] genrec
250 step_zero == 0 roll> step
251 codireco == cons dip rest cons
252 make_generator == [codireco] ccons
253 ifte == [nullary not] dipd branch
257 # ifte == [nullary] dipd swap branch
258 # genrec == [[genrec] cons cons cons cons] nullary swons concat ifte
260 # Another definition for while. FWIW
261 # while == over [[i] dip nullary] ccons [nullary] dip loop
265 ##second == rest first
266 ##third == rest rest first
268 ##swoncat == swap concat
271 ##z-down == [] swap uncons swap
272 ##z-up == swons swap shunt
273 ##z-right == [swons] cons dip uncons swap
274 ##z-left == swons [uncons swap] dip swap
277 ##divisor == popop 2 *
279 ##radical == swap dup * rollup * 4 * - sqrt
282 ##q0 == [[divisor] [minusb] [radical]] pam
283 ##q1 == [[root1] [root2]] pam
284 ##quadratic == [q0] ternary i [q1] ternary
288 ##PE1.1 == + dup [+] dip
289 ##PE1.2 == dup [3 & PE1.1] dip 2 >>
290 ##PE1.3 == 14811 swap [PE1.2] times pop
291 ##PE1 == 0 0 66 [7 PE1.3] times 4 PE1.3 pop
293 #PE1.2 == [PE1.1] step
294 #PE1 == 0 0 66 [[3 2 1 3 1 2 3] PE1.2] times [3 2 1 3] PE1.2 pop
298 def FunctionWrapper(f):
299 '''Set name attribute.'''
301 raise ValueError('Function %s must have doc string.' % f.__name__)
302 f.name = f.__name__.rstrip('_') # Don't shadow builtins.
306 def SimpleFunctionWrapper(f):
308 Wrap functions that take and return just a stack.
312 @rename_code_object(f.__name__)
313 def inner(stack, expression, dictionary):
314 return f(stack), expression, dictionary
318 def BinaryBuiltinWrapper(f):
320 Wrap functions that take two arguments and return a single result.
324 @rename_code_object(f.__name__)
325 def inner(stack, expression, dictionary):
326 (a, (b, stack)) = stack
328 return (result, stack), expression, dictionary
332 def UnaryBuiltinWrapper(f):
334 Wrap functions that take one argument and return a single result.
338 @rename_code_object(f.__name__)
339 def inner(stack, expression, dictionary):
342 return (result, stack), expression, dictionary
346 class DefinitionWrapper(object):
348 Provide implementation of defined functions, and some helper methods.
351 def __init__(self, name, body_text, doc=None):
352 self.name = self.__name__ = name
353 self.body = text_to_expression(body_text)
354 self._body = tuple(iter_stack(self.body))
355 self.__doc__ = doc or body_text
356 self._compiled = None
358 def __call__(self, stack, expression, dictionary):
360 return self._compiled(stack, expression, dictionary) # pylint: disable=E1102
361 expression = list_to_stack(self._body, expression)
362 return stack, expression, dictionary
365 def parse_definition(class_, defi):
367 Given some text describing a Joy function definition parse it and
368 return a DefinitionWrapper.
370 name, proper, body_text = (n.strip() for n in defi.partition('=='))
372 raise ValueError('Definition %r failed' % (defi,))
373 return class_(name, body_text)
376 def add_definitions(class_, defs, dictionary):
378 Scan multi-line string defs for definitions and add them to the
381 for definition in _text_to_defs(defs):
382 class_.add_def(definition, dictionary)
385 def add_def(class_, definition, dictionary, fail_fails=False):
387 Add the definition to the dictionary.
389 F = class_.parse_definition(definition)
390 _log.info('Adding definition %s := %s', F.name, expression_to_string(F.body))
391 dictionary[F.name] = F
394 def load_definitions(class_, filename, dictionary):
395 with open(filename) as f:
396 lines = [line for line in f if '==' in line]
398 class_.add_def(line, dictionary)
401 def _text_to_defs(text):
402 return (line.strip() for line in text.splitlines() if '==' in line)
413 def inscribe_(stack, expression, dictionary):
415 Create a new Joy function definition in the Joy dictionary. A
416 definition is given as a string with a name followed by a double
417 equal sign then one or more Joy functions, the body. for example:
421 If you want the definition to persist over restarts, enter it into
422 the definitions.txt resource.
424 definition, stack = stack
425 DefinitionWrapper.add_def(definition, dictionary, fail_fails=True)
426 return stack, expression, dictionary
430 @SimpleFunctionWrapper
432 '''Parse the string on the stack to a Joy expression.'''
434 expression = text_to_expression(text)
435 return expression, stack
439 @SimpleFunctionWrapper
441 '''Attempt to infer the stack effect of a Joy expression.'''
443 effects = infer_expression(E)
444 e = list_to_stack([(fi, (fo, ())) for fi, fo in effects])
450 @SimpleFunctionWrapper
455 getitem == drop first
457 Expects an integer and a quote on the stack and returns the item at the
458 nth position in the quote counting from 0.
462 -------------------------
466 n, (Q, stack) = stack
467 return pick(Q, n), stack
472 @SimpleFunctionWrapper
479 Expects an integer and a quote on the stack and returns the quote with
480 n items removed off the top.
484 ----------------------
488 n, (Q, stack) = stack
500 @SimpleFunctionWrapper
503 Expects an integer and a quote on the stack and returns the quote with
504 just the top n items in reverse order (because that's easier and you can
505 use reverse if needed.)
509 ----------------------
513 n, (Q, stack) = stack
526 @SimpleFunctionWrapper
529 Use a Boolean value to select one of two items.
533 ----------------------
538 ---------------------
541 Currently Python semantics are used to evaluate the "truthiness" of the
542 Boolean value (so empty string, zero, etc. are counted as false, etc.)
544 (if_, (then, (else_, stack))) = stack
545 return then if if_ else else_, stack
549 @SimpleFunctionWrapper
552 Use a Boolean value to select one of two items from a sequence.
556 ------------------------
561 -----------------------
564 The sequence can contain more than two items but not fewer.
565 Currently Python semantics are used to evaluate the "truthiness" of the
566 Boolean value (so empty string, zero, etc. are counted as false, etc.)
568 (flag, (choices, stack)) = stack
569 (else_, (then, _)) = choices
570 return then if flag else else_, stack
575 @SimpleFunctionWrapper
577 '''Given a list find the maximum.'''
579 return max(iter_stack(tos)), stack
584 @SimpleFunctionWrapper
586 '''Given a list find the minimum.'''
588 return min(iter_stack(tos)), stack
593 @SimpleFunctionWrapper
595 '''Given a quoted sequence of numbers return the sum.
597 sum == 0 swap [+] step
600 return sum(iter_stack(tos)), stack
604 @SimpleFunctionWrapper
607 Expects an item on the stack and a quote under it and removes that item
608 from the the quote. The item is only removed once.
612 ------------------------
616 (tos, (second, stack)) = S
617 l = list(iter_stack(second))
619 return list_to_stack(l), stack
623 @SimpleFunctionWrapper
625 '''Given a list remove duplicate items.'''
627 I = list(iter_stack(tos))
628 return list_to_stack(sorted(set(I), key=I.index)), stack
632 @SimpleFunctionWrapper
634 '''Given a list return it sorted.'''
636 return list_to_stack(sorted(iter_stack(tos))), stack
639 _functions['clear'] = s0, s1
641 @SimpleFunctionWrapper
643 '''Clear everything from the stack.
646 clear == stack [pop stack] loop
656 @SimpleFunctionWrapper
659 The unstack operator expects a list on top of the stack and makes that
660 the stack discarding the rest of the stack.
666 @SimpleFunctionWrapper
668 '''Reverse the list on the top of the stack.
671 reverse == [] swap shunt
675 for term in iter_stack(tos):
681 @combinator_effect(_COMB_NUMS(), s7, s6)
682 @SimpleFunctionWrapper
684 '''Concatinate the two lists on the top of the stack.
687 [a b c] [d e f] concat
688 ----------------------------
692 (tos, (second, stack)) = S
693 return concat(second, tos), stack
697 @SimpleFunctionWrapper
699 '''Like concat but reverses the top list into the second.
702 shunt == [swons] step == reverse swap concat
704 [a b c] [d e f] shunt
705 ---------------------------
709 (tos, (second, stack)) = stack
712 second = term, second
717 @SimpleFunctionWrapper
720 Replace the two lists on the top of the stack with a list of the pairs
721 from each list. The smallest list sets the length of the result list.
723 (tos, (second, stack)) = S
726 for a, b in zip(iter_stack(tos), iter_stack(second))
728 return list_to_stack(accumulator), stack
733 @SimpleFunctionWrapper
737 return tos + 1, stack
742 @SimpleFunctionWrapper
746 return tos - 1, stack
750 @SimpleFunctionWrapper
761 a, (b, stack) = stack
767 return int(math.floor(n))
769 floor.__doc__ = math.floor.__doc__
773 @SimpleFunctionWrapper
776 divmod(x, y) -> (quotient, remainder)
778 Return the tuple (x//y, x%y). Invariant: div*y + mod == x.
787 Return the square root of the number a.
788 Negative numbers return complex roots.
793 assert a < 0, repr(a)
794 r = math.sqrt(-a) * 1j
800 # if isinstance(text, str):
801 # return run(text, stack)
806 @SimpleFunctionWrapper
808 '''The identity function.'''
813 @SimpleFunctionWrapper
815 '''True if the form on TOS is void otherwise False.'''
817 return _void(form), stack
821 return any(not _void(i) for i in iter_stack(form))
832 def words(stack, expression, dictionary):
833 '''Print all the words in alphabetical order.'''
834 print(' '.join(sorted(dictionary)))
835 return stack, expression, dictionary
840 def sharing(stack, expression, dictionary):
841 '''Print redistribution information.'''
842 print("You may convey verbatim copies of the Program's source code as"
843 ' you receive it, in any medium, provided that you conspicuously'
844 ' and appropriately publish on each copy an appropriate copyright'
845 ' notice; keep intact all notices stating that this License and'
846 ' any non-permissive terms added in accord with section 7 apply'
847 ' to the code; keep intact all notices of the absence of any'
848 ' warranty; and give all recipients a copy of this License along'
850 ' You should have received a copy of the GNU General Public License'
851 ' along with Thun. If not see <http://www.gnu.org/licenses/>.')
852 return stack, expression, dictionary
857 def warranty(stack, expression, dictionary):
858 '''Print warranty information.'''
859 print('THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY'
860 ' APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE'
861 ' COPYRIGHT HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM'
862 ' "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR'
863 ' IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES'
864 ' OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE'
865 ' ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS'
866 ' WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE'
867 ' COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION.')
868 return stack, expression, dictionary
871 # def simple_manual(stack):
873 # Print words and help for each word.
875 # for name, f in sorted(FUNCTIONS.items()):
877 # boxline = '+%s+' % ('-' * (len(name) + 2))
880 # '| %s |' % (name,),
882 # d if d else ' ...',
892 def help_(S, expression, dictionary):
893 '''Accepts a quoted symbol on the top of the stack and prints its docs.'''
894 ((symbol, _), stack) = S
895 word = dictionary[symbol]
897 return stack, expression, dictionary
905 # Several combinators depend on other words in their definitions,
906 # we use symbols to prevent hard-coding these, so in theory, you
907 # could change the word in the dictionary to use different semantics.
908 S_choice = Symbol('choice')
909 S_first = Symbol('first')
910 S_getitem = Symbol('getitem')
911 S_genrec = Symbol('genrec')
912 S_loop = Symbol('loop')
914 S_ifte = Symbol('ifte')
915 S_infra = Symbol('infra')
916 S_pop = Symbol('pop')
917 S_step = Symbol('step')
918 S_times = Symbol('times')
919 S_swaack = Symbol('swaack')
923 @combinator_effect(_COMB_NUMS(), s1)
925 def i(stack, expression, dictionary):
927 The i combinator expects a quoted program on the stack and unpacks it
928 onto the pending expression for evaluation.
937 return stack, concat(quote, expression), dictionary
941 @combinator_effect(_COMB_NUMS(), s1)
943 def x(stack, expression, dictionary):
949 ... [Q] x = ... [Q] dup i
950 ... [Q] x = ... [Q] [Q] i
951 ... [Q] x = ... [Q] Q
955 return stack, concat(quote, expression), dictionary
959 @combinator_effect(_COMB_NUMS(), s7, s6)
961 def b(stack, expression, dictionary):
967 ... [P] [Q] b == ... [P] i [Q] i
968 ... [P] [Q] b == ... P Q
971 q, (p, (stack)) = stack
972 return stack, concat(p, concat(q, expression)), dictionary
976 @combinator_effect(_COMB_NUMS(), a1, s1)
978 def dupdip(stack, expression, dictionary):
982 [F] dupdip == dup [F] dip
992 return stack, concat(F, (a, expression)), dictionary
996 @combinator_effect(_COMB_NUMS(), s7, s6)
998 def infra(stack, expression, dictionary):
1000 Accept a quoted program and a list on the stack and run the program
1001 with the list as its stack. Does not affect the rest of the stack.
1004 ... [a b c] [Q] . infra
1005 -----------------------------
1006 c b a . Q [...] swaack
1009 (quote, (aggregate, stack)) = stack
1010 return aggregate, concat(quote, (stack, (S_swaack, expression))), dictionary
1014 #@combinator_effect(_COMB_NUMS(), s7, s6, s5, s4)
1016 def genrec(stack, expression, dictionary):
1018 General Recursion Combinator.
1021 [if] [then] [rec1] [rec2] genrec
1022 ---------------------------------------------------------------------
1023 [if] [then] [rec1 [[if] [then] [rec1] [rec2] genrec] rec2] ifte
1025 From "Recursion Theory and Joy" (j05cmp.html) by Manfred von Thun:
1026 "The genrec combinator takes four program parameters in addition to
1027 whatever data parameters it needs. Fourth from the top is an if-part,
1028 followed by a then-part. If the if-part yields true, then the then-part
1029 is executed and the combinator terminates. The other two parameters are
1030 the rec1-part and the rec2-part. If the if-part yields false, the
1031 rec1-part is executed. Following that the four program parameters and
1032 the combinator are again pushed onto the stack bundled up in a quoted
1033 form. Then the rec2-part is executed, where it will find the bundled
1034 form. Typically it will then execute the bundled form, either with i or
1035 with app2, or some other combinator."
1037 The way to design one of these is to fix your base case [then] and the
1038 test [if], and then treat rec1 and rec2 as an else-part "sandwiching"
1039 a quotation of the whole function.
1041 For example, given a (general recursive) function 'F':
1044 F == [I] [T] [R1] [R2] genrec
1046 If the [I] if-part fails you must derive R1 and R2 from:
1051 Just set the stack arguments in front, and figure out what R1 and R2
1052 have to do to apply the quoted [F] in the proper way. In effect, the
1053 genrec combinator turns into an ifte combinator with a quoted copy of
1054 the original definition in the else-part:
1057 F == [I] [T] [R1] [R2] genrec
1058 == [I] [T] [R1 [F] R2] ifte
1060 Primitive recursive functions are those where R2 == i.
1063 P == [I] [T] [R] primrec
1064 == [I] [T] [R [P] i] ifte
1065 == [I] [T] [R P] ifte
1068 (rec2, (rec1, stack)) = stack
1069 (then, (if_, _)) = stack
1070 F = (if_, (then, (rec1, (rec2, (S_genrec, ())))))
1071 else_ = concat(rec1, (F, rec2))
1072 return (else_, stack), (S_ifte, expression), dictionary
1076 @combinator_effect(_COMB_NUMS(), s7, s6)
1078 def map_(S, expression, dictionary):
1080 Run the quoted program on TOS on the items in the list under it, push a
1081 new list with the results in place of the program and original list.
1083 # (quote, (aggregate, stack)) = S
1084 # results = list_to_stack([
1085 # joy((term, stack), quote, dictionary)[0][0]
1086 # for term in iter_stack(aggregate)
1088 # return (results, stack), expression, dictionary
1089 (quote, (aggregate, stack)) = S
1091 return (aggregate, stack), expression, dictionary
1093 for term in iter_stack(aggregate):
1095 batch = (s, (quote, (S_infra, (S_first, batch))))
1096 stack = (batch, ((), stack))
1097 return stack, (S_infra, expression), dictionary
1100 #def cleave(S, expression, dictionary):
1102 # The cleave combinator expects two quotations, and below that an item X.
1103 # It first executes [P], with X on top, and saves the top result element.
1104 # Then it executes [Q], again with X, and saves the top result.
1105 # Finally it restores the stack to what it was below X and pushes the two
1106 # results P(X) and Q(X).
1108 # (Q, (P, (x, stack))) = S
1109 # p = joy((x, stack), P, dictionary)[0][0]
1110 # q = joy((x, stack), Q, dictionary)[0][0]
1111 # return (q, (p, stack)), expression, dictionary
1114 def branch_true(stack, expression, dictionary):
1115 # pylint: disable=unused-variable
1116 (then, (else_, (flag, stack))) = stack
1117 return stack, concat(then, expression), dictionary
1120 def branch_false(stack, expression, dictionary):
1121 # pylint: disable=unused-variable
1122 (then, (else_, (flag, stack))) = stack
1123 return stack, concat(else_, expression), dictionary
1127 @poly_combinator_effect(_COMB_NUMS(), [branch_true, branch_false], b1, s7, s6)
1129 def branch(stack, expression, dictionary):
1131 Use a Boolean value to select one of two quoted programs to run.
1135 branch == roll< choice i
1139 False [F] [T] branch
1140 --------------------------
1144 -------------------------
1148 (then, (else_, (flag, stack))) = stack
1149 return stack, concat(then if flag else else_, expression), dictionary
1152 #FUNCTIONS['branch'] = CombinatorJoyType('branch', [branch_true, branch_false], 100)
1157 ##def ifte(stack, expression, dictionary):
1159 ## If-Then-Else Combinator
1162 ## ... [if] [then] [else] ifte
1163 ## ---------------------------------------------------
1164 ## ... [[else] [then]] [...] [if] infra select i
1169 ## ... [if] [then] [else] ifte
1170 ## -------------------------------------------------------
1171 ## ... [else] [then] [...] [if] infra first choice i
1174 ## Has the effect of grabbing a copy of the stack on which to run the
1175 ## if-part using infra.
1177 ## (else_, (then, (if_, stack))) = stack
1178 ## expression = (S_infra, (S_first, (S_choice, (S_i, expression))))
1179 ## stack = (if_, (stack, (then, (else_, stack))))
1180 ## return stack, expression, dictionary
1185 def cond(stack, expression, dictionary):
1187 This combinator works like a case statement. It expects a single quote
1188 on the stack that must contain zero or more condition quotes and a
1189 default quote. Each condition clause should contain a quoted predicate
1190 followed by the function expression to run if that predicate returns
1191 true. If no predicates return true the default function runs.
1193 It works by rewriting into a chain of nested `ifte` expressions, e.g.::
1195 [[[B0] T0] [[B1] T1] [D]] cond
1196 -----------------------------------------
1197 [B0] [T0] [[B1] [T1] [D] ifte] ifte
1200 conditions, stack = stack
1202 expression = _cond(conditions, expression)
1204 # Attempt to preload the args to first ifte.
1205 (P, (T, (E, expression))) = expression
1207 # If, for any reason, the argument to cond should happen to contain
1208 # only the default clause then this optimization will fail.
1211 stack = (E, (T, (P, stack)))
1212 return stack, expression, dictionary
1215 def _cond(conditions, expression):
1216 (clause, rest) = conditions
1217 if not rest: # clause is [D]
1220 return (P, (T, (_cond(rest, ()), (S_ifte, expression))))
1224 @combinator_effect(_COMB_NUMS(), a1, s1)
1226 def dip(stack, expression, dictionary):
1228 The dip combinator expects a quoted program on the stack and below it
1229 some item, it hoists the item into the expression and runs the program
1230 on the rest of the stack.
1238 (quote, (x, stack)) = stack
1239 expression = (x, expression)
1240 return stack, concat(quote, expression), dictionary
1244 @combinator_effect(_COMB_NUMS(), a2, a1, s1)
1246 def dipd(S, expression, dictionary):
1248 Like dip but expects two items.
1252 ---------------------
1256 (quote, (x, (y, stack))) = S
1257 expression = (y, (x, expression))
1258 return stack, concat(quote, expression), dictionary
1262 @combinator_effect(_COMB_NUMS(), a3, a2, a1, s1)
1264 def dipdd(S, expression, dictionary):
1266 Like dip but expects three items.
1270 -----------------------
1274 (quote, (x, (y, (z, stack)))) = S
1275 expression = (z, (y, (x, expression)))
1276 return stack, concat(quote, expression), dictionary
1280 @combinator_effect(_COMB_NUMS(), a1, s1)
1282 def app1(S, expression, dictionary):
1284 Given a quoted program on TOS and anything as the second stack item run
1285 the program and replace the two args with the first result of the
1290 -----------------------------------
1291 ... [x ...] [Q] . infra first
1293 (quote, (x, stack)) = S
1294 stack = (quote, ((x, stack), stack))
1295 expression = (S_infra, (S_first, expression))
1296 return stack, expression, dictionary
1300 @combinator_effect(_COMB_NUMS(), a2, a1, s1)
1302 def app2(S, expression, dictionary):
1303 '''Like app1 with two items.
1307 -----------------------------------
1308 ... [y ...] [Q] . infra first
1309 [x ...] [Q] infra first
1312 (quote, (x, (y, stack))) = S
1313 expression = (S_infra, (S_first,
1314 ((x, stack), (quote, (S_infra, (S_first,
1316 stack = (quote, ((y, stack), stack))
1317 return stack, expression, dictionary
1321 @combinator_effect(_COMB_NUMS(), a3, a2, a1, s1)
1323 def app3(S, expression, dictionary):
1324 '''Like app1 with three items.
1327 ... z y x [Q] . app3
1328 -----------------------------------
1329 ... [z ...] [Q] . infra first
1330 [y ...] [Q] infra first
1331 [x ...] [Q] infra first
1334 (quote, (x, (y, (z, stack)))) = S
1335 expression = (S_infra, (S_first,
1336 ((y, stack), (quote, (S_infra, (S_first,
1337 ((x, stack), (quote, (S_infra, (S_first,
1338 expression))))))))))
1339 stack = (quote, ((z, stack), stack))
1340 return stack, expression, dictionary
1344 @combinator_effect(_COMB_NUMS(), s7, s6)
1346 def step(S, expression, dictionary):
1348 Run a quoted program on each item in a sequence.
1352 -----------------------
1357 ------------------------
1361 ... [a b c] [Q] . step
1362 ----------------------------------------
1363 ... a . Q [b c] [Q] step
1365 The step combinator executes the quotation on each member of the list
1366 on top of the stack.
1368 (quote, (aggregate, stack)) = S
1370 return stack, expression, dictionary
1371 head, tail = aggregate
1372 stack = quote, (head, stack)
1374 expression = tail, (quote, (S_step, expression))
1375 expression = S_i, expression
1376 return stack, expression, dictionary
1380 @combinator_effect(_COMB_NUMS(), i1, s6)
1382 def times(stack, expression, dictionary):
1384 times == [-- dip] cons [swap] infra [0 >] swap while pop
1388 --------------------- w/ n <= 0
1393 ---------------------------------
1398 --------------------------------- w/ n > 1
1399 ... . Q (n - 1) [Q] times
1402 # times == [-- dip] cons [swap] infra [0 >] swap while pop
1403 (quote, (n, stack)) = stack
1405 return stack, expression, dictionary
1408 expression = n, (quote, (S_times, expression))
1409 expression = concat(quote, expression)
1410 return stack, expression, dictionary
1413 # The current definition above works like this:
1416 # --------------------------------------
1417 # [P] nullary [Q [P] nullary] loop
1419 # while == [pop i not] [popop] [dudipd] primrec
1421 #def while_(S, expression, dictionary):
1422 # '''[if] [body] while'''
1423 # (body, (if_, stack)) = S
1424 # while joy(stack, if_, dictionary)[0][0]:
1425 # stack = joy(stack, body, dictionary)[0]
1426 # return stack, expression, dictionary
1429 def loop_true(stack, expression, dictionary):
1430 quote, (flag, stack) = stack # pylint: disable=unused-variable
1431 return stack, concat(quote, (S_pop, expression)), dictionary
1433 def loop_two_true(stack, expression, dictionary):
1434 quote, (flag, stack) = stack # pylint: disable=unused-variable
1435 return stack, concat(quote, (S_pop, concat(quote, (S_pop, expression)))), dictionary
1437 def loop_false(stack, expression, dictionary):
1438 quote, (flag, stack) = stack # pylint: disable=unused-variable
1439 return stack, expression, dictionary
1443 @poly_combinator_effect(_COMB_NUMS(), [loop_two_true, loop_true, loop_false], b1, s6)
1445 def loop(stack, expression, dictionary):
1447 Basic loop combinator.
1451 -----------------------
1455 ------------------------
1459 quote, (flag, stack) = stack
1461 expression = concat(quote, (quote, (S_loop, expression)))
1462 return stack, expression, dictionary
1466 @combinator_effect(_COMB_NUMS(), a1, a2, s6, s7, s8)
1468 def cmp_(stack, expression, dictionary):
1470 cmp takes two values and three quoted programs on the stack and runs
1471 one of the three depending on the results of comparing the two values:
1475 ------------------------- a > b
1479 ------------------------- a = b
1483 ------------------------- a < b
1486 L, (E, (G, (b, (a, stack)))) = stack
1487 expression = concat(G if a > b else L if a < b else E, expression)
1488 return stack, expression, dictionary
1491 # FunctionWrapper(cleave),
1492 # FunctionWrapper(while_),
1497 #divmod_ = pm = __(n2, n1), __(n4, n3)
1499 sec_binary_cmp(BinaryBuiltinWrapper(operator.eq)),
1500 sec_binary_cmp(BinaryBuiltinWrapper(operator.ge)),
1501 sec_binary_cmp(BinaryBuiltinWrapper(operator.gt)),
1502 sec_binary_cmp(BinaryBuiltinWrapper(operator.le)),
1503 sec_binary_cmp(BinaryBuiltinWrapper(operator.lt)),
1504 sec_binary_cmp(BinaryBuiltinWrapper(operator.ne)),
1506 sec_binary_ints(BinaryBuiltinWrapper(operator.xor)),
1507 sec_binary_ints(BinaryBuiltinWrapper(operator.lshift)),
1508 sec_binary_ints(BinaryBuiltinWrapper(operator.rshift)),
1510 sec_binary_logic(BinaryBuiltinWrapper(operator.and_)),
1511 sec_binary_logic(BinaryBuiltinWrapper(operator.or_)),
1513 sec_binary_math(BinaryBuiltinWrapper(operator.add)),
1514 sec_binary_math(BinaryBuiltinWrapper(operator.floordiv)),
1515 sec_binary_math(BinaryBuiltinWrapper(operator.mod)),
1516 sec_binary_math(BinaryBuiltinWrapper(operator.mul)),
1517 sec_binary_math(BinaryBuiltinWrapper(operator.pow)),
1518 sec_binary_math(BinaryBuiltinWrapper(operator.sub)),
1519 sec_binary_math(BinaryBuiltinWrapper(operator.truediv)),
1521 sec_unary_logic(UnaryBuiltinWrapper(bool)),
1522 sec_unary_logic(UnaryBuiltinWrapper(operator.not_)),
1524 sec_unary_math(UnaryBuiltinWrapper(abs)),
1525 sec_unary_math(UnaryBuiltinWrapper(operator.neg)),
1526 sec_unary_math(UnaryBuiltinWrapper(sqrt)),
1528 stack_effect(n1)(i1)(UnaryBuiltinWrapper(floor)),
1531 del F # Otherwise Sphinx autodoc will pick it up.
1534 YIN_STACK_EFFECTS = yin_functions()
1535 add_aliases(YIN_STACK_EFFECTS, ALIASES)
1537 # Load the auto-generated primitives into the dictionary.
1538 _functions.update(YIN_STACK_EFFECTS)
1541 # eh = compose(dup, bool)
1542 # sqr = compose(dup, mul)
1543 # of = compose(swap, at)
1545 # ''' in dict(compose=compose), _functions
1546 for name in sorted(_functions):
1547 sec = _functions[name]
1548 F = FUNCTIONS[name] = SymbolJoyType(name, [sec], _SYM_NUMS())
1549 if name in YIN_STACK_EFFECTS:
1550 _log.info('Setting stack effect for Yin function %s := %s', F.name, doc_from_stack_effect(*sec))
1552 for name, primitive in getmembers(genlib, isfunction):
1553 inscribe(SimpleFunctionWrapper(primitive))
1556 add_aliases(_dictionary, ALIASES)
1557 add_aliases(_functions, ALIASES)
1558 add_aliases(FUNCTIONS, ALIASES)
1561 DefinitionWrapper.add_definitions(definitions, _dictionary)
1564 EXPECTATIONS = dict(
1565 ifte=(s7, (s6, (s5, s4))),
1569 EXPECTATIONS['while'] = (s7, (s6, s5))
1580 C = _dictionary[name]
1581 expect = EXPECTATIONS.get(name)
1583 sec = doc_from_stack_effect(expect)
1584 _log.info('Setting stack EXPECT for combinator %s := %s', C.name, sec)
1586 _log.info('combinator %s', C.name)
1587 FUNCTIONS[name] = CombinatorJoyType(name, [C], _COMB_NUMS(), expect)
1591 of quoted enstacken ?
1592 unary binary ternary
1595 of_ = _dictionary[name]
1596 secs = infer_expression(of_.body)
1597 assert len(secs) == 1, repr(secs)
1599 'Setting stack effect for definition %s := %s',
1601 doc_from_stack_effect(*secs[0]),
1603 FUNCTIONS[name] = SymbolJoyType(name, infer_expression(of_.body), _SYM_NUMS())
1606 #sec_Ns_math(_dictionary['product'])
1608 ## product == 1 swap [*] step
1609 ## flatten == [] swap [concat] step
1610 ## disenstacken == ? [uncons ?] loop pop
1612 ## size == 0 swap [pop ++] step
1614 ## cleave == fork [popd] dip
1615 ## average == [sum 1.0 *] [size] cleave /
1616 ## gcd == 1 [tuck modulus dup 0 >] loop pop
1617 ## least_fraction == dup [gcd] infra [div] concat map
1618 ## *fraction == [uncons] dip uncons [swap] dip concat [*] infra [*] dip cons
1619 ## *fraction0 == concat [[swap] dip * [*] dip] infra
1620 ## down_to_zero == [0 >] [dup --] while
1621 ## range_to_zero == unit [down_to_zero] infra
1622 ## anamorphism == [pop []] swap [dip swons] genrec
1623 ## range == [0 <=] [1 - dup] anamorphism
1624 ## while == swap [nullary] cons dup dipd concat loop
1625 ## dupdipd == dup dipd
1626 ## primrec == [i] genrec
1627 ## step_zero == 0 roll> step
1628 ## codireco == cons dip rest cons
1629 ## make_generator == [codireco] ccons
1630 ## ifte == [nullary not] dipd branch