1 The Blissful Elegance of Typing Joy
2 ===================================
4 This notebook presents a simple type inferencer for Joy code. It can
5 infer the stack effect of most Joy expressions. It’s built largely by
6 means of existing ideas and research. (A great overview of the existing
7 knowledge is a talk `“Type Inference in Stack-Based Programming
8 Languages” <http://prl.ccs.neu.edu/blog/2017/03/10/type-inference-in-stack-based-programming-languages/>`__
9 given by Rob Kleffner on or about 2017-03-10 as part of a course on the
10 history of programming languages.)
12 The notebook starts with a simple inferencer based on the work of Jaanus
13 Pöial which we then progressively elaborate to cover more Joy semantics.
14 Along the way we write a simple “compiler” that emits Python code for
15 what I like to call Yin functions. (Yin functions are those that only
16 rearrange values in stacks, as opposed to Yang functions that actually
17 work on the values themselves.)
22 `“Typing Tools for Typeless Stack Languages” by Jaanus
23 Pöial <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.212.6026>`__
27 @INPROCEEDINGS{Pöial06typingtools,
28 author = {Jaanus Pöial},
29 title = {Typing tools for typeless stack languages},
30 booktitle = {In 23rd Euro-Forth Conference},
38 This rule deals with functions (and literals) that put items on the
50 This rule deals with functions that consume items from the stack
62 The third rule is actually two rules. These two rules deal with
63 composing functions when the second one will consume one of items the
64 first one produces. The two types must be
65 `unified <https://en.wikipedia.org/wiki/Robinson's_unification_algorithm>`__
66 or a type conflict declared.
70 (a -- b t[i])∘(c u[j] -- d) t <= u (t is subtype of u)
71 -------------------------------
72 (a -- b )∘(c -- d) t[i] == t[k] == u[j]
75 (a -- b t[i])∘(c u[j] -- d) u <= t (u is subtype of t)
76 -------------------------------
77 (a -- b )∘(c -- d) t[i] == u[k] == u[j]
79 Let’s work through some examples by hand to develop an intuition for the
82 There’s a function in one of the other notebooks.
86 F == pop swap roll< rest rest cons cons
88 It’s all “stack chatter” and list manipulation so we should be able to
94 Joy function types will be represented by Forth-style stack effect
95 comments. I’m going to use numbers instead of names to keep track of the
96 stack arguments. (A little bit like `De Bruijn
97 index <https://en.wikipedia.org/wiki/De_Bruijn_index>`__, at least it
106 roll< (1 2 3 -- 2 3 1)
108 These commands alter the stack but don’t “look at” the values so these
109 numbers represent an “Any type”.
118 Here we encounter a complication. The argument numbers need to be made
119 unique among both sides. For this let’s change ``pop`` to use 0:
125 Following the second rule:
136 (1 2 0 -- 2 1) (1 2 3 -- 2 3 1)
142 (1a 2a 0a -- 2a 1a) (1b 2b 3b -- 2b 3b 1b)
144 Now we follow the rules.
146 We must unify ``1a`` and ``3b``, and ``2a`` and ``2b``, replacing the
151 (1a 2a 0a -- 2a 1a) (1b 2b 3b -- 2b 3b 1b)
153 (3b 2a 0a -- 2a ) (1b 2b -- 2b 3b 1b)
155 (3b 2b 0a -- ) (1b -- 2b 3b 1b)
157 Here we must apply the second rule:
161 (3b 2b 0a --) (1b -- 2b 3b 1b)
162 -----------------------------------
163 (1b 3b 2b 0a -- 2b 3b 1b)
165 Now we de-label the type, uh, labels:
169 (1b 3b 2b 0a -- 2b 3b 1b)
180 And now we have the stack effect comment for ``pop∘swap∘roll<``.
182 Compiling ``pop∘swap∘roll<``
183 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
185 The simplest way to “compile” this function would be something like:
190 return rolldown(*swap(*pop(s, e, d)))
192 However, internally this function would still be allocating tuples
193 (stack cells) and doing other unnecesssary work.
195 Looking ahead for a moment, from the stack effect comment:
201 We should be able to directly write out a Python function like:
206 (_, (a, (b, (c, stack)))) = stack
207 return (c, (b, (a, stack)))
209 This eliminates the internal work of the first version. Because this
210 function only rearranges the stack and doesn’t do any actual processing
211 on the stack items themselves all the information needed to implement it
212 is in the stack effect comment.
217 These are slightly tricky.
221 rest ( [1 ...] -- [...] )
223 cons ( 1 [...] -- [1 ...] )
225 ``pop∘swap∘roll< rest``
226 ~~~~~~~~~~~~~~~~~~~~~~~
230 (1 2 3 0 -- 3 2 1) ([1 ...] -- [...])
232 Re-label (instead of adding left and right tags I’m just taking the next
233 available index number for the right-side stack effect comment):
237 (1 2 3 0 -- 3 2 1) ([4 ...] -- [...])
243 (1 2 3 0 -- 3 2 1) ([4 ...] -- [...])
245 ([4 ...] 2 3 0 -- 3 2 ) ( -- [...])
247 Apply the first rule:
251 ([4 ...] 2 3 0 -- 3 2) (-- [...])
252 ---------------------------------------
253 ([4 ...] 2 3 0 -- 3 2 [...])
257 ``pop∘swap∘roll<∘rest rest``
258 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
264 ([4 ...] 2 3 0 -- 3 2 [...]) ([1 ...] -- [...])
266 Re-label (the tails of the lists on each side each get their own label):
270 ([4 .0.] 2 3 0 -- 3 2 [.0.]) ([5 .1.] -- [.1.])
272 Unify and update (note the opening square brackets have been omited in
273 the substitution dict, this is deliberate and I’ll explain below):
277 ([4 .0.] 2 3 0 -- 3 2 [.0.] ) ([5 .1.] -- [.1.])
279 ([4 5 .1.] 2 3 0 -- 3 2 [5 .1.]) ([5 .1.] -- [.1.])
281 How do we find ``.0.]`` in ``[4 .0.]`` and replace it with ``5 .1.]``
282 getting the result ``[4 5 .1.]``? This might seem hard, but because the
283 underlying structure of the Joy list is a cons-list in Python it’s
284 actually pretty easy. I’ll explain below.
286 Next we unify and find our two terms are the same already: ``[5 .1.]``:
290 ([4 5 .1.] 2 3 0 -- 3 2 [5 .1.]) ([5 .1.] -- [.1.])
296 ([4 5 .1.] 2 3 0 -- 3 2) (-- [.1.])
298 From here we apply the first rule and get:
302 ([4 5 .1.] 2 3 0 -- 3 2 [.1.])
304 Cleaning up the labels:
308 ([4 5 ...] 2 3 1 -- 3 2 [...])
310 This is the stack effect of ``pop∘swap∘roll<∘rest∘rest``.
312 ``pop∘swap∘roll<∘rest∘rest cons``
313 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
317 ([4 5 ...] 2 3 1 -- 3 2 [...]) (1 [...] -- [1 ...])
323 ([4 5 .1.] 2 3 1 -- 3 2 [.1.]) (6 [.2.] -- [6 .2.])
329 ([4 5 .1.] 2 3 1 -- 3 2 [.1.]) (6 [.2.] -- [6 .2.])
331 ([4 5 .2.] 2 3 1 -- 3 2 ) (6 -- [6 .2.])
333 ([4 5 .2.] 6 3 1 -- 3 ) ( -- [6 .2.])
339 ([4 5 .2.] 6 3 1 -- 3 [6 .2.])
345 ([4 5 ...] 2 3 1 -- 3 [2 ...])
349 ``pop∘swap∘roll<∘rest∘rest∘cons cons``
350 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
356 ([4 5 ...] 2 3 1 -- 3 [2 ...]) (1 [...] -- [1 ...])
362 ([4 5 .1.] 2 3 1 -- 3 [2 .1.]) (6 [.2.] -- [6 .2.])
368 ([4 5 .1.] 2 3 1 -- 3 [2 .1.]) (6 [.2.] -- [6 .2.] )
370 ([4 5 .1.] 2 3 1 -- 3 ) (6 -- [6 2 .1.])
372 ([4 5 .1.] 2 6 1 -- ) ( -- [6 2 .1.])
374 First or second rule:
378 ([4 5 .1.] 2 6 1 -- [6 2 .1.])
384 ([4 5 ...] 2 3 1 -- [3 2 ...])
386 And there you have it, the stack effect for
387 ``pop∘swap∘roll<∘rest∘rest∘cons∘cons``.
391 ([4 5 ...] 2 3 1 -- [3 2 ...])
393 From this stack effect comment it should be possible to construct the
394 following Python code:
399 (_, (d, (c, ((a, (b, S0)), stack)))) = stack
400 return (d, (c, S0)), stack
402 Part II: Implementation
403 -----------------------
405 Representing Stack Effect Comments in Python
406 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
408 I’m going to use pairs of tuples of type descriptors, which will be
409 integers or tuples of type descriptors:
413 roll_dn = (1, 2, 3), (2, 3, 1)
417 swap = (1, 2), (2, 1)
426 (f_in, f_out), (g_in, g_out) = f, g
431 # ---------------------
436 fg_in, fg_out = f_in, f_out + g_out
441 # ---------------------
446 fg_in, fg_out = g_in + f_in, g_out
448 else: # Unify, update, recur.
450 fo, gi = f_out[-1], g_in[-1]
454 if s == False: # s can also be the empty dict, which is ok.
455 raise TypeError('Cannot unify %r and %r.' % (fo, gi))
457 f_g = (f_in, f_out[:-1]), (g_in[:-1], g_out)
459 if s: f_g = update(s, f_g)
461 fg_in, fg_out = compose(*f_g)
470 def unify(u, v, s=None):
474 if isinstance(u, int):
476 elif isinstance(v, int):
489 if not isinstance(term, tuple):
490 return s.get(term, term)
491 return tuple(update(s, inner) for inner in term)
498 def relabel(left, right):
499 return left, _1000(right)
502 if not isinstance(right, tuple):
504 return tuple(_1000(n) for n in right)
513 (((1,), ()), ((1001, 1002), (1002, 1001)))
523 s = {u: i for i, u in enumerate(sorted(_unique(f)))}
526 def _unique(f, seen=None):
529 if not isinstance(f, tuple):
536 delabel(relabel(pop, swap))
543 (((0,), ()), ((1, 2), (2, 1)))
550 At last we put it all together in a function ``C()`` that accepts two
551 stack effect comments and returns their composition (or raises and
552 exception if they can’t be composed due to type conflicts.)
578 C(C(pop, swap), roll_dn)
585 ((3, 1, 2, 0), (2, 1, 3))
598 ((2, 0, 1), (1, 0, 2))
604 C(pop, C(swap, roll_dn))
611 ((3, 1, 2, 0), (2, 1, 3))
617 poswrd = reduce(C, (pop, swap, roll_dn))
625 ((3, 1, 2, 0), (2, 1, 3))
632 Here’s that trick to represent functions like ``rest`` and ``cons`` that
633 manipulate stacks. We use a cons-list of tuples and give the tails their
634 own numbers. Then everything above already works.
638 rest = ((1, 2),), (2,)
640 cons = (1, 2), ((1, 2),)
651 (((3, 4), 1, 2, 0), (2, 1, 4))
655 Compare this to the stack effect comment we wrote above:
659 (( (3, 4), 1, 2, 0 ), ( 2, 1, 4 ))
660 ( [4 ...] 2 3 0 -- 3 2 [...])
662 The translation table, if you will, would be:
676 F = reduce(C, (pop, swap, roll_dn, rest, rest, cons, cons))
685 (((3, (4, 5)), 1, 2, 0), ((2, (1, 5)),))
689 Compare with the stack effect comment and you can see it works fine:
693 ([4 5 ...] 2 3 1 -- [3 2 ...])
696 Dealing with ``cons`` and ``uncons``
697 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
699 However, if we try to compose e.g. ``cons`` and ``uncons`` it won’t
704 uncons = ((1, 2),), (1, 2)
716 Cannot unify (1, 2) and (1001, 1002).
719 ``unify()`` version 2
720 ^^^^^^^^^^^^^^^^^^^^^
722 The problem is that the ``unify()`` function as written doesn’t handle
723 the case when both terms are tuples. We just have to add a clause to
724 deal with this recursively:
728 def unify(u, v, s=None):
735 if isinstance(u, int):
738 elif isinstance(v, int):
741 elif isinstance(u, tuple) and isinstance(v, tuple):
743 if len(u) != 2 or len(v) != 2:
744 # Not a type error, caller passed in a bad value.
745 raise ValueError(repr((u, v))) # FIXME this message sucks.
747 (a, b), (c, d) = u, v
769 Part III: Compiling Yin Functions
770 ---------------------------------
772 Now consider the Python function we would like to derive:
777 (_, (d, (c, ((a, (b, S0)), stack)))) = stack
778 return (d, (c, S0)), stack
780 And compare it to the input stack effect comment tuple we just computed:
791 ((3, (4, 5)), 1, 2, 0)
795 The stack-de-structuring tuple has nearly the same form as our input
796 stack effect comment tuple, just in the reverse order:
800 (_, (d, (c, ((a, (b, S0)), stack))))
802 Remove the punctuation:
808 Reverse the order and compare:
813 ((3, (4, 5 )), 1, 2, 0)
832 is similar to the output stack effect comment tuple:
836 ((d, (c, S0)), stack)
839 This should make it pretty easy to write a Python function that accepts
840 the stack effect comment tuples and returns a new Python function
841 (either as a string of code or a function object ready to use) that
842 performs the semantics of that Joy function (described by the stack
848 We want to substitute Python identifiers for the integers. I’m going to
849 repurpose ``joy.parser.Symbol`` class for this:
853 from collections import defaultdict
854 from joy.parser import Symbol
858 I = iter(xrange(1000))
859 return lambda: Symbol('a%i' % next(I))
862 def identifiers(term, s=None):
864 s = defaultdict(_names_for())
865 if isinstance(term, int):
867 return tuple(identifiers(inner, s) for inner in term)
869 ``doc_from_stack_effect()``
870 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
872 As a convenience I’ve implemented a function to convert the Python stack
873 effect comment tuples to reasonable text format. There are some details
874 in how this code works that related to stuff later in the notebook, so
875 you should skip it for now and read it later if you’re interested.
879 def doc_from_stack_effect(inputs, outputs):
880 return '(%s--%s)' % (
881 ' '.join(map(_to_str, inputs + ('',))),
882 ' '.join(map(_to_str, ('',) + outputs))
887 if not isinstance(term, tuple):
889 t = term.prefix == 's'
890 except AttributeError:
892 return '[.%i.]' % term.number if t else str(term)
895 while term and isinstance(term, tuple):
897 a.append(_to_str(item))
901 except AttributeError:
904 if term.prefix != 's':
905 raise ValueError('Stack label: %s' % (term,))
907 a.append('.%s.' % (n,))
908 return '[%s]' % ' '.join(a)
913 Now we can write a compiler function to emit Python source code. (The
914 underscore suffix distiguishes it from the built-in ``compile()``
919 def compile_(name, f, doc=None):
921 doc = doc_from_stack_effect(*f)
922 inputs, outputs = identifiers(f)
923 i = o = Symbol('stack')
928 return '''def %s(stack):
931 return %s''' % (name, doc, i, o)
933 Here it is in action:
937 source = compile_('F', F)
945 """([3 4 .5.] 1 2 0 -- [2 1 .5.])"""
946 (a5, (a4, (a3, ((a0, (a1, a2)), stack)))) = stack
947 return ((a4, (a3, a2)), stack)
955 (_, (d, (c, ((a, (b, S0)), stack)))) = stack
956 return ((d, (c, S0)), stack)
964 eval(compile(source, '__main__', 'single'), {}, L)
981 from notebook_preamble import D, J, V
982 from joy.library import SimpleFunctionWrapper
986 D['F'] = SimpleFunctionWrapper(L['F'])
990 J('[4 5 ...] 2 3 1 F')
998 With this, we have a partial Joy compiler that works on the subset of
999 Joy functions that manipulate stacks (both what I call “stack chatter”
1000 and the ones that manipulate stacks on the stack.)
1002 I’m probably going to modify the definition wrapper code to detect
1003 definitions that can be compiled by this partial compiler and do it
1004 automatically. It might be a reasonable idea to detect sequences of
1005 compilable functions in definitions that have uncompilable functions in
1006 them and just compile those. However, if your library is well-factored
1007 this might be less helpful.
1009 Compiling Library Functions
1010 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
1012 We can use ``compile_()`` to generate many primitives in the library
1013 from their stack effect comments:
1019 rolldown = (1, 2, 3), (2, 3, 1)
1021 rollup = (1, 2, 3), (3, 1, 2)
1025 swap = (1, 2), (2, 1)
1027 rest = ((1, 2),), (2,)
1029 rrest = C(rest, rest)
1031 cons = (1, 2), ((1, 2),)
1033 uncons = ((1, 2),), (1, 2)
1035 swons = C(swap, cons)
1041 for name, stack_effect_comment in sorted(defs().items()):
1043 print compile_(name, stack_effect_comment)
1051 """(1 2 -- [1 .2.])"""
1052 (a1, (a0, stack)) = stack
1053 return ((a0, a1), stack)
1063 """([1 .2.] -- 2)"""
1064 ((a0, a1), stack) = stack
1068 def rolldown(stack):
1069 """(1 2 3 -- 2 3 1)"""
1070 (a2, (a1, (a0, stack))) = stack
1071 return (a0, (a2, (a1, stack)))
1075 """(1 2 3 -- 3 1 2)"""
1076 (a2, (a1, (a0, stack))) = stack
1077 return (a1, (a0, (a2, stack)))
1081 """([0 1 .2.] -- 2)"""
1082 ((a0, (a1, a2)), stack) = stack
1088 (a1, (a0, stack)) = stack
1089 return (a0, (a1, stack))
1093 """(0 1 -- [1 .0.])"""
1094 (a1, (a0, stack)) = stack
1095 return ((a1, a0), stack)
1099 """([1 .2.] -- 1 2)"""
1100 ((a0, a1), stack) = stack
1101 return (a1, (a0, stack))
1105 Part IV: Types and Subtypes of Arguments
1106 ----------------------------------------
1108 So far we have dealt with types of functions, those dealing with simple
1109 stack manipulation. Let’s extend our machinery to deal with types of
1115 Consider the definition of ``sqr``:
1121 The ``dup`` function accepts one *anything* and returns two of that:
1127 And ``mul`` accepts two “numbers” (we’re ignoring ints vs. floats
1128 vs. complex, etc., for now) and returns just one:
1138 (1 -- 1 1)∘(n n -- n)
1140 The rules say we unify 1 with ``n``:
1144 (1 -- 1 1)∘(n n -- n)
1145 --------------------------- w/ {1: n}
1148 This involves detecting that “Any type” arguments can accept “numbers”.
1149 If we were composing these functions the other way round this is still
1154 (n n -- n)∘(1 -- 1 1)
1155 --------------------------- w/ {1: n}
1158 The important thing here is that the mapping is going the same way in
1159 both cases, from the “any” integer to the number
1161 Distinguishing Numbers
1162 ~~~~~~~~~~~~~~~~~~~~~~
1164 We should also mind that the number that ``mul`` produces is not
1165 (necessarily) the same as either of its inputs, which are not
1166 (necessarily) the same as each other:
1173 (1 -- 1 1)∘(n2 n1 -- n3)
1174 -------------------------------- w/ {1: n2}
1175 (n2 -- n2 )∘(n2 -- n3)
1178 (n2 n1 -- n3)∘(1 -- 1 1 )
1179 -------------------------------- w/ {1: n3}
1180 (n2 n1 -- )∘( -- n3 n3)
1182 Distinguishing Types
1183 ~~~~~~~~~~~~~~~~~~~~
1185 So we need separate domains of “any” numbers and “number” numbers, and
1186 we need to be able to ask the order of these domains. Now the notes on
1187 the right side of rule three make more sense, eh?
1191 (a -- b t[i])∘(c u[j] -- d) t <= u (t is subtype of u)
1192 -------------------------------
1193 (a -- b )∘(c -- d) t[i] == t[k] == u[j]
1196 (a -- b t[i])∘(c u[j] -- d) u <= t (u is subtype of t)
1197 -------------------------------
1198 (a -- b )∘(c -- d) t[i] == u[k] == u[j]
1200 The indices ``i``, ``k``, and ``j`` are the number part of our labels
1201 and ``t`` and ``u`` are the domains.
1203 By creative use of Python’s “double underscore” methods we can define a
1204 Python class hierarchy of Joy types and use the ``issubclass()`` method
1205 to establish domain ordering, as well as other handy behaviour that will
1206 make it fairly easy to reuse most of the code above.
1210 class AnyJoyType(object):
1214 def __init__(self, number):
1215 self.number = number
1218 return self.prefix + str(self.number)
1220 def __eq__(self, other):
1222 isinstance(other, self.__class__)
1223 and other.prefix == self.prefix
1224 and other.number == self.number
1227 def __ge__(self, other):
1228 return issubclass(other.__class__, self.__class__)
1230 def __add__(self, other):
1231 return self.__class__(self.number + other)
1235 return hash(repr(self))
1238 class NumberJoyType(AnyJoyType): prefix = 'n'
1239 class FloatJoyType(NumberJoyType): prefix = 'f'
1240 class IntJoyType(FloatJoyType): prefix = 'i'
1243 class StackJoyType(AnyJoyType):
1248 A = map(AnyJoyType, _R)
1249 N = map(NumberJoyType, _R)
1250 S = map(StackJoyType, _R)
1252 Mess with it a little:
1256 from itertools import permutations
1258 “Any” types can be specialized to numbers and stacks, but not vice
1263 for a, b in permutations((A[0], N[0], S[0]), 2):
1264 print a, '>=', b, '->', a >= b
1277 Our crude `Numerical
1278 Tower <https://en.wikipedia.org/wiki/Numerical_tower>`__ of *numbers* >
1279 *floats* > *integers* works as well (but we’re not going to use it yet):
1283 for a, b in permutations((A[0], N[0], FloatJoyType(0), IntJoyType(0)), 2):
1284 print a, '>=', b, '->', a >= b
1308 dup = (A[1],), (A[1], A[1])
1310 mul = (N[1], N[2]), (N[3],)
1338 Modifying the Inferencer
1339 ~~~~~~~~~~~~~~~~~~~~~~~~
1341 Re-labeling still works fine:
1345 foo = relabel(dup, mul)
1354 (((a1,), (a1, a1)), ((n1001, n1002), (n1003,)))
1358 ``delabel()`` version 2
1359 ^^^^^^^^^^^^^^^^^^^^^^^
1361 The ``delabel()`` function needs an overhaul. It now has to keep track
1362 of how many labels of each domain it has “seen”.
1366 from collections import Counter
1369 def delabel(f, seen=None, c=None):
1372 seen, c = {}, Counter()
1379 if not isinstance(f, tuple):
1380 seen[f] = f.__class__(c[f.prefix] + 1)
1384 return tuple(delabel(inner, seen, c) for inner in f)
1395 (((a1,), (a1, a1)), ((n1, n2), (n3,)))
1399 ``unify()`` version 3
1400 ^^^^^^^^^^^^^^^^^^^^^
1404 def unify(u, v, s=None):
1414 if isinstance(u, AnyJoyType) and isinstance(v, AnyJoyType):
1421 raise TypeError('Cannot unify %r and %r.' % (u, v))
1423 if isinstance(u, tuple) and isinstance(v, tuple):
1424 if len(u) != len(v) != 2:
1425 raise TypeError(repr((u, v)))
1426 for uu, vv in zip(u, v):
1427 s = unify(uu, vv, s)
1428 if s == False: # (instead of a substitution dict.)
1432 if isinstance(v, tuple):
1434 raise TypeError('Cannot unify %r and %r.' % (u, v))
1438 if isinstance(u, tuple):
1440 raise TypeError('Cannot unify %r and %r.' % (v, u))
1448 return thing.__class__ in {AnyJoyType, StackJoyType}
1450 Rewrite the stack effect comments:
1456 rolldown = (A[1], A[2], A[3]), (A[2], A[3], A[1])
1458 rollup = (A[1], A[2], A[3]), (A[3], A[1], A[2])
1462 popop = (A[2], A[1],), ()
1464 popd = (A[2], A[1],), (A[1],)
1466 popdd = (A[3], A[2], A[1],), (A[2], A[1],)
1468 swap = (A[1], A[2]), (A[2], A[1])
1470 rest = ((A[1], S[1]),), (S[1],)
1472 rrest = C(rest, rest)
1474 cons = (A[1], S[1]), ((A[1], S[1]),)
1476 ccons = C(cons, cons)
1478 uncons = ((A[1], S[1]),), (A[1], S[1])
1480 swons = C(swap, cons)
1482 dup = (A[1],), (A[1], A[1])
1484 dupd = (A[2], A[1]), (A[2], A[2], A[1])
1486 mul = (N[1], N[2]), (N[3],)
1490 first = ((A[1], S[1]),), (A[1],)
1492 second = C(rest, first)
1494 third = C(rest, second)
1496 tuck = (A[2], A[1]), (A[1], A[2], A[1])
1498 over = (A[2], A[1]), (A[2], A[1], A[2])
1500 succ = pred = (N[1],), (N[2],)
1502 divmod_ = pm = (N[2], N[1]), (N[4], N[3])
1512 for name, stack_effect_comment in sorted(DEFS.items()):
1513 print name, '=', doc_from_stack_effect(*stack_effect_comment)
1518 ccons = (a1 a2 [.1.] -- [a1 a2 .1.])
1519 cons = (a1 [.1.] -- [a1 .1.])
1520 divmod_ = (n2 n1 -- n4 n3)
1522 dupd = (a2 a1 -- a2 a2 a1)
1523 first = ([a1 .1.] -- a1)
1525 over = (a2 a1 -- a2 a1 a2)
1526 pm = (n2 n1 -- n4 n3)
1528 popd = (a2 a1 -- a1)
1529 popdd = (a3 a2 a1 -- a2 a1)
1532 rest = ([a1 .1.] -- [.1.])
1533 rolldown = (a1 a2 a3 -- a2 a3 a1)
1534 rollup = (a1 a2 a3 -- a3 a1 a2)
1535 rrest = ([a1 a2 .1.] -- [.1.])
1536 second = ([a1 a2 .1.] -- a2)
1539 swap = (a1 a2 -- a2 a1)
1540 swons = ([.1.] a1 -- [a1 .1.])
1541 third = ([a1 a2 a3 .1.] -- a3)
1542 tuck = (a2 a1 -- a1 a2 a1)
1543 uncons = ([a1 .1.] -- a1 [.1.])
1548 globals().update(DEFS)
1550 Compose ``dup`` and ``mul``
1551 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
1566 Revisit the ``F`` function, works fine.
1570 F = reduce(C, (pop, swap, rolldown, rest, rest, cons, cons))
1578 (((a1, (a2, s1)), a3, a4, a5), ((a4, (a3, s1)),))
1584 print doc_from_stack_effect(*F)
1589 ([a1 a2 .1.] a3 a4 a5 -- [a4 a3 .1.])
1592 Some otherwise inefficient functions are no longer to be feared. We can
1593 also get the effect of combinators in some limited cases.
1598 print doc_from_stack_effect(*reduce(C, funcs))
1603 neato(rollup, swap, rolldown)
1608 (a1 a2 a3 -- a2 a1 a3)
1614 neato(popdd, rolldown, pop)
1619 (a1 a2 a3 a4 -- a3 a4)
1624 # Reverse the order of the top three items.
1630 (a1 a2 a3 -- a3 a2 a1)
1633 ``compile_()`` version 2
1634 ^^^^^^^^^^^^^^^^^^^^^^^^
1636 Because the type labels represent themselves as valid Python identifiers
1637 the ``compile_()`` function doesn’t need to generate them anymore:
1641 def compile_(name, f, doc=None):
1644 doc = doc_from_stack_effect(inputs, outputs)
1645 i = o = Symbol('stack')
1648 for term in outputs:
1650 return '''def %s(stack):
1653 return %s''' % (name, doc, i, o)
1657 print compile_('F', F)
1663 """([a1 a2 .1.] a3 a4 a5 -- [a4 a3 .1.])"""
1664 (a5, (a4, (a3, ((a1, (a2, s1)), stack)))) = stack
1665 return ((a4, (a3, s1)), stack)
1668 But it cannot magically create new functions that involve e.g. math and
1669 such. Note that this is *not* a ``sqr`` function implementation:
1673 print compile_('sqr', C(dup, mul))
1684 (Eventually I should come back around to this becuase it’s not tooo
1685 difficult to exend this code to be able to compile e.g.
1686 ``n2 = mul(n1, n1)`` for ``mul`` with the right variable names and
1687 insert it in the right place. It requires a little more support from the
1688 library functions, in that we need to know to call ``mul()`` the Python
1689 function for ``mul`` the Joy function, but since *most* of the math
1690 functions (at least) are already wrappers it should be straightforward.)
1695 The functions that *can* be compiled are the ones that have only
1696 ``AnyJoyType`` and ``StackJoyType`` labels in their stack effect
1697 comments. We can write a function to check that:
1701 from itertools import imap
1705 return isinstance(f, tuple) and all(imap(compilable, f)) or stacky(f)
1709 for name, stack_effect_comment in sorted(defs().items()):
1710 if compilable(stack_effect_comment):
1711 print name, '=', doc_from_stack_effect(*stack_effect_comment)
1716 ccons = (a1 a2 [.1.] -- [a1 a2 .1.])
1717 cons = (a1 [.1.] -- [a1 .1.])
1719 dupd = (a2 a1 -- a2 a2 a1)
1720 first = ([a1 .1.] -- a1)
1721 over = (a2 a1 -- a2 a1 a2)
1723 popd = (a2 a1 -- a1)
1724 popdd = (a3 a2 a1 -- a2 a1)
1726 rest = ([a1 .1.] -- [.1.])
1727 rolldown = (a1 a2 a3 -- a2 a3 a1)
1728 rollup = (a1 a2 a3 -- a3 a1 a2)
1729 rrest = ([a1 a2 .1.] -- [.1.])
1730 second = ([a1 a2 .1.] -- a2)
1731 swap = (a1 a2 -- a2 a1)
1732 swons = ([.1.] a1 -- [a1 .1.])
1733 third = ([a1 a2 a3 .1.] -- a3)
1734 tuck = (a2 a1 -- a1 a2 a1)
1735 uncons = ([a1 .1.] -- a1 [.1.])
1738 Part V: Functions that use the Stack
1739 ------------------------------------
1741 Consider the ``stack`` function which grabs the whole stack, quotes it,
1742 and puts it on itself:
1746 stack (... -- ... [...] )
1747 stack (... a -- ... a [a ...] )
1748 stack (... b a -- ... b a [a b ...])
1750 We would like to represent this in Python somehow. To do this we use a
1751 simple, elegant trick.
1756 stack (a, S) -- ( (a, S), (a, S))
1757 stack (a, (b, S)) -- ( (a, (b, S)), (a, (b, S)))
1759 Instead of representing the stack effect comments as a single tuple
1760 (with N items in it) we use the same cons-list structure to hold the
1761 sequence and ``unify()`` the whole comments.
1766 Let’s try composing ``stack`` and ``uncons``. We want this result:
1770 stack∘uncons (... a -- ... a a [...])
1772 The stack effects are:
1778 uncons = ((a, Z), S) -- (Z, (a, S))
1784 S -- (S, S) ∘ ((a, Z), S) -- (Z, (a, S ))
1786 (a, Z) -- ∘ -- (Z, (a, (a, Z)))
1792 stack∘uncons == (a, Z) -- (Z, (a, (a, Z)))
1796 ``stack∘uncons∘uncons``
1797 ~~~~~~~~~~~~~~~~~~~~~~~
1799 Let’s try ``stack∘uncons∘uncons``:
1803 (a, S ) -- (S, (a, (a, S ))) ∘ ((b, Z), S` ) -- (Z, (b, S` ))
1807 (a, (b, Z)) -- ((b, Z), (a, (a, (b, Z)))) ∘ ((b, Z), S` ) -- (Z, (b, S` ))
1809 w/ { S`: (a, (a, (b, Z))) }
1811 (a, (b, Z)) -- ((b, Z), (a, (a, (b, Z)))) ∘ ((b, Z), (a, (a, (b, Z)))) -- (Z, (b, (a, (a, (b, Z)))))
1813 (a, (b, Z)) -- (Z, (b, (a, (a, (b, Z)))))
1817 ``compose()`` version 2
1818 ^^^^^^^^^^^^^^^^^^^^^^^
1820 This function has to be modified to use the new datastructures and it is
1821 no longer recursive, instead recursion happens as part of unification.
1822 Further, the first and second of Pöial’s rules are now handled
1823 automatically by the unification algorithm. (One easy way to see this is
1824 that now an empty stack effect comment is represented by a
1825 ``StackJoyType`` instance which is not “falsey” and so neither of the
1826 first two rules’ ``if`` clauses will ever be ``True``. Later on I change
1827 the “truthiness” of ``StackJoyType`` to false to let e.g.
1828 ``joy.utils.stack.concat`` work with our stack effect comment cons-list
1834 (f_in, f_out), (g_in, g_out) = f, g
1835 s = unify(g_in, f_out)
1836 if s == False: # s can also be the empty dict, which is ok.
1837 raise TypeError('Cannot unify %r and %r.' % (f_out, g_in))
1838 return update(s, (f_in, g_out))
1840 I don’t want to rewrite all the defs myself, so I’ll write a little
1841 conversion function instead. This is programmer’s laziness.
1845 def sequence_to_stack(seq, stack=StackJoyType(23)):
1846 for item in seq: stack = item, stack
1850 name: (sequence_to_stack(i), sequence_to_stack(o))
1851 for name, (i, o) in DEFS.iteritems()
1853 NEW_DEFS['stack'] = S[0], (S[0], S[0])
1854 NEW_DEFS['swaack'] = (S[1], S[0]), (S[0], S[1])
1855 globals().update(NEW_DEFS)
1866 ((a1, s1), (s1, (a1, (a1, s1))))
1872 reduce(C, (stack, uncons, uncons))
1879 ((a1, (a2, s1)), (s1, (a2, (a1, (a1, (a2, s1))))))
1883 The display function should be changed too.
1885 ``doc_from_stack_effect()`` version 2
1886 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1888 Clunky junk, but it will suffice for now.
1892 def doc_from_stack_effect(inputs, outputs):
1893 switch = [False] # Do we need to display the '...' for the rest of the main stack?
1894 i, o = _f(inputs, switch), _f(outputs, switch)
1898 return '(%s--%s)' % (
1899 ' '.join(reversed([''] + i)),
1900 ' '.join(reversed(o + [''])),
1904 def _f(term, switch):
1906 while term and isinstance(term, tuple):
1909 assert isinstance(term, StackJoyType), repr(term)
1910 a = [_to_str(i, term, switch) for i in a]
1914 def _to_str(term, stack, switch):
1915 if not isinstance(term, tuple):
1920 '[.%i.]' % term.number
1921 if isinstance(term, StackJoyType)
1926 while term and isinstance(term, tuple):
1928 a.append(_to_str(item, stack, switch))
1929 assert isinstance(term, StackJoyType), repr(term)
1934 end = '.%i.' % term.number
1936 return '[%s]' % ' '.join(a)
1940 for name, stack_effect_comment in sorted(NEW_DEFS.items()):
1941 print name, '=', doc_from_stack_effect(*stack_effect_comment)
1946 ccons = (a1 a2 [.1.] -- [a1 a2 .1.])
1947 cons = (a1 [.1.] -- [a1 .1.])
1948 divmod_ = (n2 n1 -- n4 n3)
1950 dupd = (a2 a1 -- a2 a2 a1)
1951 first = ([a1 .1.] -- a1)
1953 over = (a2 a1 -- a2 a1 a2)
1954 pm = (n2 n1 -- n4 n3)
1956 popd = (a2 a1 -- a1)
1957 popdd = (a3 a2 a1 -- a2 a1)
1960 rest = ([a1 .1.] -- [.1.])
1961 rolldown = (a1 a2 a3 -- a2 a3 a1)
1962 rollup = (a1 a2 a3 -- a3 a1 a2)
1963 rrest = ([a1 a2 .1.] -- [.1.])
1964 second = ([a1 a2 .1.] -- a2)
1966 stack = (... -- ... [...])
1968 swaack = ([.1.] -- [.0.])
1969 swap = (a1 a2 -- a2 a1)
1970 swons = ([.1.] a1 -- [a1 .1.])
1971 third = ([a1 a2 a3 .1.] -- a3)
1972 tuck = (a2 a1 -- a1 a2 a1)
1973 uncons = ([a1 .1.] -- a1 [.1.])
1978 print ; print doc_from_stack_effect(*stack)
1979 print ; print doc_from_stack_effect(*C(stack, uncons))
1980 print ; print doc_from_stack_effect(*reduce(C, (stack, uncons, uncons)))
1981 print ; print doc_from_stack_effect(*reduce(C, (stack, uncons, cons)))
1989 (... a1 -- ... a1 a1 [...])
1991 (... a2 a1 -- ... a2 a1 a1 a2 [...])
1993 (... a1 -- ... a1 [a1 ...])
1998 print doc_from_stack_effect(*C(ccons, stack))
2003 (... a2 a1 [.1.] -- ... [a2 a1 .1.] [[a2 a1 .1.] ...])
2017 ((s1, (a1, (a2, s2))), (((a2, (a1, s1)), s2), ((a2, (a1, s1)), s2)))
2021 ``compile_()`` version 3
2022 ^^^^^^^^^^^^^^^^^^^^^^^^
2024 This makes the ``compile_()`` function pretty simple as the stack effect
2025 comments are now already in the form needed for the Python code:
2029 def compile_(name, f, doc=None):
2032 doc = doc_from_stack_effect(i, o)
2033 return '''def %s(stack):
2036 return %s''' % (name, doc, i, o)
2040 print compile_('Q', Q)
2046 """(... a2 a1 [.1.] -- ... [a2 a1 .1.] [[a2 a1 .1.] ...])"""
2047 (s1, (a1, (a2, s2))) = stack
2048 return (((a2, (a1, s1)), s2), ((a2, (a1, s1)), s2))
2058 unstack = (S[1], S[0]), S[1]
2059 enstacken = S[0], (S[0], S[1])
2063 print doc_from_stack_effect(*unstack)
2073 print doc_from_stack_effect(*enstacken)
2083 print doc_from_stack_effect(*C(cons, unstack))
2093 print doc_from_stack_effect(*C(cons, enstacken))
2098 (a1 [.1.] -- [[a1 .1.] .2.])
2110 ((s1, (a1, s2)), (a1, s1))
2115 Part VI: Multiple Stack Effects
2116 -------------------------------
2122 class IntJoyType(NumberJoyType): prefix = 'i'
2125 F = map(FloatJoyType, _R)
2126 I = map(IntJoyType, _R)
2131 ((I[2], (I[1], S[0])), (I[3], S[0])),
2132 ((F[2], (I[1], S[0])), (F[3], S[0])),
2133 ((I[2], (F[1], S[0])), (F[3], S[0])),
2134 ((F[2], (F[1], S[0])), (F[3], S[0])),
2140 print doc_from_stack_effect(*f)
2158 print doc_from_stack_effect(*dup), doc_from_stack_effect(*f), doc_from_stack_effect(*e)
2163 (a1 -- a1 a1) (i1 i2 -- i3) (i1 -- i2)
2164 (a1 -- a1 a1) (f1 f2 -- f3) (f1 -- f2)
2169 from itertools import product
2172 def meta_compose(F, G):
2173 for f, g in product(F, G):
2181 return sorted(set(meta_compose(F, G)))
2185 for f in MC([dup], [mul]):
2186 print doc_from_stack_effect(*f)
2196 for f in MC([dup], muls):
2197 print doc_from_stack_effect(*f)
2206 Representing an Unbounded Sequence of Types
2207 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2209 We can borrow a trick from `Brzozowski’s Derivatives of Regular
2210 Expressions <https://en.wikipedia.org/wiki/Brzozowski_derivative>`__ to
2211 invent a new type of type variable, a “sequence type” (I think this is
2212 what they mean in the literature by that term…) or “`Kleene
2213 Star <https://en.wikipedia.org/wiki/Kleene_star>`__” type. I’m going to
2214 represent it as a type letter and the asterix, so a sequence of zero or
2215 more ``AnyJoyType`` variables would be:
2221 The ``A*`` works by splitting the universe into two alternate histories:
2227 The Kleene star variable disappears in one universe, and in the other it
2228 turns into an ``AnyJoyType`` variable followed by itself again. We have
2229 to return all universes (represented by their substitution dicts, the
2230 “unifiers”) that don’t lead to type conflicts.
2232 Consider unifying two stacks (the lowercase letters are any type
2233 variables of the kinds we have defined so far):
2237 [a A* b .0.] U [c d .1.]
2239 [ A* b .0.] U [ d .1.]
2241 Now we have to split universes to unify ``A*``. In the first universe it
2250 While in the second it spawns an ``A``, which we will label ``e``:
2254 [e A* b .0.] U [d .1.]
2256 [ A* b .0.] U [ .1.]
2258 [ A* b .0.] U [ A* b .0.]
2260 Giving us two unifiers:
2264 {c: a, d: b, .1.: .0.}
2265 {c: a, d: e, .1.: A* b .0.}
2269 class KleeneStar(object):
2273 def __init__(self, number):
2274 self.number = number
2276 self.prefix = repr(self)
2279 return '%s%i*' % (self.kind.prefix, self.number)
2283 return self.kind(10000 * self.number + self.count)
2285 def __eq__(self, other):
2287 isinstance(other, self.__class__)
2288 and other.number == self.number
2291 def __ge__(self, other):
2292 return self.kind >= other.kind
2294 def __add__(self, other):
2295 return self.__class__(self.number + other)
2299 return hash(repr(self))
2301 class AnyStarJoyType(KleeneStar): kind = AnyJoyType
2302 class NumberStarJoyType(KleeneStar): kind = NumberJoyType
2303 #class FloatStarJoyType(KleeneStar): kind = FloatJoyType
2304 #class IntStarJoyType(KleeneStar): kind = IntJoyType
2305 class StackStarJoyType(KleeneStar): kind = StackJoyType
2308 As = map(AnyStarJoyType, _R)
2309 Ns = map(NumberStarJoyType, _R)
2310 Ss = map(StackStarJoyType, _R)
2312 ``unify()`` version 4
2313 ^^^^^^^^^^^^^^^^^^^^^
2315 Can now return multiple results…
2319 def unify(u, v, s=None):
2329 if isinstance(u, AnyJoyType) and isinstance(v, AnyJoyType):
2336 raise TypeError('Cannot unify %r and %r.' % (u, v))
2338 if isinstance(u, tuple) and isinstance(v, tuple):
2339 if len(u) != len(v) != 2:
2340 raise TypeError(repr((u, v)))
2343 if isinstance(a, KleeneStar):
2344 # Two universes, in one the Kleene star disappears and unification
2345 # continues without it...
2348 # In the other it spawns a new variable.
2349 s1 = unify(u, (a.another(), v))
2357 if isinstance(a, KleeneStar):
2359 s1 = unify(v, (a.another(), u))
2365 ses = unify(u[0], v[0], s)
2368 results += unify(u[1], v[1], sn)
2371 if isinstance(v, tuple):
2373 raise TypeError('Cannot unify %r and %r.' % (u, v))
2377 if isinstance(u, tuple):
2379 raise TypeError('Cannot unify %r and %r.' % (v, u))
2387 return thing.__class__ in {AnyJoyType, StackJoyType}
2419 for result in unify(b, a):
2420 print result, '->', update(result, a), update(result, b)
2425 {s1: (a1, s2)} -> (a1*, (a1, s2)) (a1, s2)
2426 {a1: a10001, s2: (a1*, s1)} -> (a1*, s1) (a10001, (a1*, s1))
2431 for result in unify(a, b):
2432 print result, '->', update(result, a), update(result, b)
2437 {s1: (a1, s2)} -> (a1*, (a1, s2)) (a1, s2)
2438 {a1: a10002, s2: (a1*, s1)} -> (a1*, s1) (a10002, (a1*, s1))
2443 (a1*, s1) [a1*] (a1, s2) [a1]
2445 (a1*, (a1, s2)) [a1* a1] (a1, s2) [a1]
2447 (a1*, s1) [a1*] (a2, (a1*, s1)) [a2 a1*]
2451 sum_ = ((Ns[1], S[1]), S[0]), (N[0], S[0])
2453 print doc_from_stack_effect(*sum_)
2463 f = (N[1], (N[2], (N[3], S[1]))), S[0]
2465 print doc_from_stack_effect(S[0], f)
2475 for result in unify(sum_[0], f):
2476 print result, '->', update(result, sum_[1])
2481 {s1: (n1, (n2, (n3, s1)))} -> (n0, s0)
2482 {n1: n10001, s1: (n2, (n3, s1))} -> (n0, s0)
2483 {n1: n10001, s1: (n3, s1), n2: n10002} -> (n0, s0)
2484 {n1: n10001, s1: (n1*, s1), n3: n10003, n2: n10002} -> (n0, s0)
2487 ``compose()`` version 3
2488 ^^^^^^^^^^^^^^^^^^^^^^^
2490 This function has to be modified to yield multiple results.
2495 (f_in, f_out), (g_in, g_out) = f, g
2496 s = unify(g_in, f_out)
2498 raise TypeError('Cannot unify %r and %r.' % (f_out, g_in))
2500 yield update(result, (f_in, g_out))
2506 def meta_compose(F, G):
2507 for f, g in product(F, G):
2509 for result in C(f, g):
2516 f, g = relabel(f, g)
2517 for fg in compose(f, g):
2522 for f in MC([dup], muls):
2523 print doc_from_stack_effect(*f)
2536 for f in MC([dup], [sum_]):
2537 print doc_from_stack_effect(*f)
2542 ([n1* .1.] -- [n1* .1.] n1)
2549 for f in MC([cons], [sum_]):
2550 print doc_from_stack_effect(*f)
2556 (n1 [n1* .1.] -- n2)
2561 sum_ = (((N[1], (Ns[1], S[1])), S[0]), (N[0], S[0]))
2562 print doc_from_stack_effect(*cons),
2563 print doc_from_stack_effect(*sum_),
2565 for f in MC([cons], [sum_]):
2566 print doc_from_stack_effect(*f)
2571 (a1 [.1.] -- [a1 .1.]) ([n1 n1* .1.] -- n0) (n1 [n1* .1.] -- n2)
2576 a = (A[4], (As[1], (A[3], S[1])))
2584 (a4, (a1*, (a3, s1)))
2590 b = (A[1], (A[2], S[2]))
2604 for result in unify(b, a):
2610 {a1: a4, s2: s1, a2: a3}
2611 {a1: a4, s2: (a1*, (a3, s1)), a2: a10003}
2616 for result in unify(a, b):
2622 {s2: s1, a2: a3, a4: a1}
2623 {s2: (a1*, (a3, s1)), a2: a10004, a4: a1}
2626 Part VII: Typing Combinators
2627 ----------------------------
2629 In order to compute the stack effect of combinators you kinda have to
2630 have the quoted programs they expect available. In the most general
2631 case, the ``i`` combinator, you can’t say anything about its stack
2632 effect other than it expects one quote:
2636 i (... [.1.] -- ... .1.)
2642 i (... [A* .1.] -- ... A*)
2644 Consider the type of:
2650 Obviously it would be:
2654 (a1 [..1] a2 -- [a1 ..1] a2)
2656 ``dip`` itself could have:
2660 (a1 [..1] -- ... then what?
2662 Without any information about the contents of the quote we can’t say
2663 much about the result.
2665 Hybrid Inferencer/Interpreter
2666 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2668 I think there’s a way forward. If we convert our list (of terms we are
2669 composing) into a stack structure we can use it as a *Joy expression*,
2670 then we can treat the *output half* of a function’s stack effect comment
2671 as a Joy interpreter stack, and just execute combinators directly. We
2672 can hybridize the compostition function with an interpreter to evaluate
2673 combinators, compose non-combinator functions, and put type variables on
2674 the stack. For combinators like ``branch`` that can have more than one
2675 stack effect we have to “split universes” again and return both.
2677 Joy Types for Functions
2678 ^^^^^^^^^^^^^^^^^^^^^^^
2680 We need a type variable for Joy functions that can go in our expressions
2681 and be used by the hybrid inferencer/interpreter. They have to store a
2682 name and a list of stack effects.
2686 class FunctionJoyType(AnyJoyType):
2688 def __init__(self, name, sec, number):
2690 self.stack_effects = sec
2691 self.number = number
2693 def __add__(self, other):
2700 Specialized for Simple Functions and Combinators
2701 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
2703 For non-combinator functions the stack effects list contains stack
2704 effect comments (represented by pairs of cons-lists as described above.)
2708 class SymbolJoyType(FunctionJoyType):
2711 For combinators the list contains Python functions.
2715 class CombinatorJoyType(FunctionJoyType):
2719 def __init__(self, name, sec, number, expect=None):
2720 super(CombinatorJoyType, self).__init__(name, sec, number)
2721 self.expect = expect
2723 def enter_guard(self, f):
2724 if self.expect is None:
2726 g = self.expect, self.expect
2727 new_f = list(compose(f, g, ()))
2728 assert len(new_f) == 1, repr(new_f)
2731 For simple combinators that have only one effect (like ``dip``) you only
2732 need one function and it can be the combinator itself.
2738 dip = CombinatorJoyType('dip', [joy.library.dip], 23)
2740 For combinators that can have more than one effect (like ``branch``) you
2741 have to write functions that each implement the action of one of the
2746 def branch_true(stack, expression, dictionary):
2747 (then, (else_, (flag, stack))) = stack
2748 return stack, concat(then, expression), dictionary
2750 def branch_false(stack, expression, dictionary):
2751 (then, (else_, (flag, stack))) = stack
2752 return stack, concat(else_, expression), dictionary
2754 branch = CombinatorJoyType('branch', [branch_true, branch_false], 100)
2756 You can also provide an optional stack effect, input-side only, that
2757 will then be used as an identity function (that accepts and returns
2758 stacks that match the “guard” stack effect) which will be used to guard
2759 against type mismatches going into the evaluation of the combinator.
2764 With those in place, we can define a function that accepts a sequence of
2765 Joy type variables, including ones representing functions (not just
2766 values), and attempts to grind out all the possible stack effects of
2769 One tricky thing is that type variables *in the expression* have to be
2770 updated along with the stack effects after doing unification or we risk
2771 losing useful information. This was a straightforward, if awkward,
2772 modification to the call structure of ``meta_compose()`` et. al.
2776 ID = S[0], S[0] # Identity function.
2779 def infer(*expression):
2780 return sorted(set(_infer(list_to_stack(expression))))
2783 def _infer(e, F=ID):
2790 if isinstance(n, SymbolJoyType):
2791 eFG = meta_compose([F], n.stack_effects, e)
2792 res = flatten(_infer(e, Fn) for e, Fn in eFG)
2794 elif isinstance(n, CombinatorJoyType):
2795 fi, fo = n.enter_guard(F)
2796 res = flatten(_interpret(f, fi, fo, e) for f in n.stack_effects)
2798 elif isinstance(n, Symbol):
2799 assert n not in FUNCTIONS, repr(n)
2800 func = joy.library._dictionary[n]
2801 res = _interpret(func, F[0], F[1], e)
2805 res = _infer(e, (fi, (n, fo)))
2810 def _interpret(f, fi, fo, e):
2811 new_fo, ee, _ = f(fo, e, {})
2812 ee = update(FUNCTIONS, ee) # Fix Symbols.
2814 return _infer(ee, new_F)
2820 len(inspect_stack()),
2821 doc_from_stack_effect(*F),
2822 expression_to_string(e),
2828 And that brings us to current Work-In-Progress. The mixed-mode
2829 inferencer/interpreter ``infer()`` function seems to work well. There
2830 are details I should document, and the rest of the code in the ``types``
2831 module (FIXME link to its docs here!) should be explained… There is
2832 cruft to convert the definitions in ``DEFS`` to the new
2833 ``SymbolJoyType`` objects, and some combinators. Here is an example of
2834 output from the current code :
2838 1/0 # (Don't try to run this cell! It's not going to work. This is "read only" code heh..)
2840 logging.basicConfig(format='%(message)s', stream=sys.stdout, level=logging.INFO)
2842 globals().update(FUNCTIONS)
2844 h = infer((pred, s2), (mul, s3), (div, s4), (nullary, (bool, s5)), dipd, branch)
2849 print doc_from_stack_effect(fi, fo)
2855 ---------------------------------------------------------------------------
2857 ZeroDivisionError Traceback (most recent call last)
2859 <ipython-input-1-9a9d60354c35> in <module>()
2860 ----> 1 1/0 # (Don't try to run this cell! It's not going to work. This is "read only" code heh..)
2862 3 logging.basicConfig(format='%(message)s', stream=sys.stdout, level=logging.INFO)
2864 5 globals().update(FUNCTIONS)
2867 ZeroDivisionError: integer division or modulo by zero
2870 The numbers at the start of the lines are the current depth of the
2871 Python call stack. They’re followed by the current computed stack effect
2872 (initialized to ``ID``) then the pending expression (the inference of
2873 the stack effect of which is the whole object of the current example.)
2875 In this example we are implementing (and inferring) ``ifte`` as
2876 ``[nullary bool] dipd branch`` which shows off a lot of the current
2877 implementation in action.
2881 7 (--) ∘ [pred] [mul] [div] [nullary bool] dipd branch
2882 8 (-- [pred ...2]) ∘ [mul] [div] [nullary bool] dipd branch
2883 9 (-- [pred ...2] [mul ...3]) ∘ [div] [nullary bool] dipd branch
2884 10 (-- [pred ...2] [mul ...3] [div ...4]) ∘ [nullary bool] dipd branch
2885 11 (-- [pred ...2] [mul ...3] [div ...4] [nullary bool ...5]) ∘ dipd branch
2886 15 (-- [pred ...5]) ∘ nullary bool [mul] [div] branch
2887 19 (-- [pred ...2]) ∘ [stack] dinfrirst bool [mul] [div] branch
2888 20 (-- [pred ...2] [stack ]) ∘ dinfrirst bool [mul] [div] branch
2889 22 (-- [pred ...2] [stack ]) ∘ dip infra first bool [mul] [div] branch
2890 26 (--) ∘ stack [pred] infra first bool [mul] [div] branch
2891 29 (... -- ... [...]) ∘ [pred] infra first bool [mul] [div] branch
2892 30 (... -- ... [...] [pred ...1]) ∘ infra first bool [mul] [div] branch
2893 34 (--) ∘ pred s1 swaack first bool [mul] [div] branch
2894 37 (n1 -- n2) ∘ [n1] swaack first bool [mul] [div] branch
2895 38 (... n1 -- ... n2 [n1 ...]) ∘ swaack first bool [mul] [div] branch
2896 41 (... n1 -- ... n1 [n2 ...]) ∘ first bool [mul] [div] branch
2897 44 (n1 -- n1 n2) ∘ bool [mul] [div] branch
2898 47 (n1 -- n1 b1) ∘ [mul] [div] branch
2899 48 (n1 -- n1 b1 [mul ...1]) ∘ [div] branch
2900 49 (n1 -- n1 b1 [mul ...1] [div ...2]) ∘ branch
2911 ----------------------------------------
2921 We built a simple type inferencer, and a kind of crude “compiler” for a
2922 subset of Joy functions. Then we built a more powerful inferencer that
2923 actually does some evaluation and explores branching code paths
2925 Work remains to be done:
2927 - the rest of the library has to be covered
2928 - figure out how to deal with ``loop`` and ``genrec``, etc..
2929 - extend the types to check values (see the appendix)
2930 - other kinds of “higher order” type variables, OR, AND, etc..
2931 - maybe rewrite in Prolog for great good?
2934 - don’t permit composition of functions that don’t compose
2935 - auto-compile compilable functions
2937 - Compiling more than just the Yin functions.
2938 - getting better visibility (than Python debugger.)
2939 - DOOOOCS!!!! Lots of docs!
2941 - docstrings all around
2942 - improve this notebook (it kinda falls apart at the end
2943 narratively. I went off and just started writing code to see if it
2944 would work. It does, but now I have to come back and describe here
2947 Appendix: Joy in the Logical Paradigm
2948 -------------------------------------
2950 For *type checking* to work the type label classes have to be modified
2951 to let ``T >= t`` succeed, where e.g. ``T`` is ``IntJoyType`` and ``t``
2952 is ``int``. If you do that you can take advantage of the *logical
2953 relational* nature of the stack effect comments to “compute in reverse”
2954 as it were. There’s a working demo of this at the end of the ``types``
2955 module. But if you’re interested in all that you should just use Prolog!
2957 Anyhow, type *checking* is a few easy steps away.
2961 def _ge(self, other):
2962 return (issubclass(other.__class__, self.__class__)
2963 or hasattr(self, 'accept')
2964 and isinstance(other, self.accept))
2966 AnyJoyType.__ge__ = _ge
2967 AnyJoyType.accept = tuple, int, float, long, str, unicode, bool, Symbol
2968 StackJoyType.accept = tuple