6 ["Typing Tools for Typeless Stack Languages" by Jaanus Pöial
7 ](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.212.6026)
9 @INPROCEEDINGS{Pöial06typingtools,
10 author = {Jaanus Pöial},
11 title = {Typing tools for typeless stack languages},
12 booktitle = {In 23rd Euro-Forth Conference},
18 This rule deals with functions (and literals) that put items on the stack `(-- d)`:
26 This rule deals with functions that consume items from the stack `(a --)`:
33 The third rule is actually two rules. These two rules deal with composing functions when the second one will consume one of items the first one produces. The two types must be *unified* or a type conflict declared.
35 (a -- b t[i])∘(c u[j] -- d) t <= u (t is subtype of u)
36 -------------------------------
37 (a -- b )∘(c -- d) t[i] == t[k] == u[j]
40 (a -- b t[i])∘(c u[j] -- d) u <= t (u is subtype of t)
41 -------------------------------
42 (a -- b )∘(c -- d) t[i] == u[k] == u[j]
45 Let's work through some examples by hand to develop an intuition for the algorithm.
47 There's a function in one of the other notebooks.
49 F == pop swap roll< rest rest cons cons
51 It's all "stack chatter" and list manipulation so we should be able to deduce its type.
53 ### Stack Effect Comments
54 Joy function types will be represented by Forth-style stack effect comments. I'm going to use numbers instead of names to keep track of the stack arguments. (A little bit like [De Bruijn index](https://en.wikipedia.org/wiki/De_Bruijn_index), at least it reminds me of them):
60 roll< (1 2 3 -- 2 3 1)
62 These commands alter the stack but don't "look at" the values so these numbers represent an "Any type".
68 Here we encounter a complication. The argument numbers need to be made unique among both sides. For this let's change `pop` to use 0:
72 Following the second rule:
78 (1 2 0 -- 2 1) (1 2 3 -- 2 3 1)
82 (1a 2a 0a -- 2a 1a) (1b 2b 3b -- 2b 3b 1b)
84 Now we follow the rules.
86 We must unify `1a` and `3b`, and `2a` and `2b`, replacing the terms in the forms:
88 (1a 2a 0a -- 2a 1a) (1b 2b 3b -- 2b 3b 1b)
90 (3b 2a 0a -- 2a ) (1b 2b -- 2b 3b 1b)
92 (3b 2b 0a -- ) (1b -- 2b 3b 1b)
94 Here we must apply the second rule:
96 (3b 2b 0a --) (1b -- 2b 3b 1b)
97 -----------------------------------
98 (1b 3b 2b 0a -- 2b 3b 1b)
100 Now we de-label the type, uh, labels:
102 (1b 3b 2b 0a -- 2b 3b 1b)
113 And now we have the stack effect comment for `pop∘swap∘roll<`.
115 ### Compiling `pop∘swap∘roll<`
116 The simplest way to "compile" this function would be something like:
121 return roll_down(*swap(*pop(s, e, d)))
124 However, internally this function would still be allocating tuples (stack cells) and doing other unnecesssary work.
126 Looking ahead for a moment, from the stack effect comment:
130 We should be able to directly write out a Python function like:
135 (_, (a, (b, (c, stack)))) = stack
136 return (c, (b, (a, stack)))
139 This eliminates the internal work of the first version. Because this function only rearranges the stack and doesn't do any actual processing on the stack items themselves all the information needed to implement it is in the stack effect comment.
141 ### Functions on Lists
142 These are slightly tricky.
144 rest ( [1 ...] -- [...] )
146 cons ( 1 [...] -- [1 ...] )
148 ### `pop∘swap∘roll< rest`
150 (1 2 3 0 -- 3 2 1) ([1 ...] -- [...])
152 Re-label (instead of adding left and right tags I'm just taking the next available index number for the right-side stack effect comment):
154 (1 2 3 0 -- 3 2 1) ([4 ...] -- [...])
158 (1 2 3 0 -- 3 2 1) ([4 ...] -- [...])
160 ([4 ...] 2 3 0 -- 3 2 ) ( -- [...])
162 Apply the first rule:
164 ([4 ...] 2 3 0 -- 3 2) (-- [...])
165 ---------------------------------------
166 ([4 ...] 2 3 0 -- 3 2 [...])
170 ### `pop∘swap∘roll<∘rest rest`
174 ([4 ...] 2 3 0 -- 3 2 [...]) ([1 ...] -- [...])
176 Re-label (the tails of the lists on each side each get their own label):
178 ([4 .0.] 2 3 0 -- 3 2 [.0.]) ([5 .1.] -- [.1.])
180 Unify and update (note the opening square brackets have been omited in the substitution dict, this is deliberate and I'll explain below):
182 ([4 .0.] 2 3 0 -- 3 2 [.0.] ) ([5 .1.] -- [.1.])
184 ([4 5 .1.] 2 3 0 -- 3 2 [5 .1.]) ([5 .1.] -- [.1.])
186 How do we find `.0.]` in `[4 .0.]` and replace it with `5 .1.]` getting the result `[4 5 .1.]`? This might seem hard, but because the underlying structure of the Joy list is a cons-list in Python it's actually pretty easy. I'll explain below.
188 Next we unify and find our two terms are the same already: `[5 .1.]`:
190 ([4 5 .1.] 2 3 0 -- 3 2 [5 .1.]) ([5 .1.] -- [.1.])
194 ([4 5 .1.] 2 3 0 -- 3 2) (-- [.1.])
196 From here we apply the first rule and get:
198 ([4 5 .1.] 2 3 0 -- 3 2 [.1.])
200 Cleaning up the labels:
202 ([4 5 ...] 2 3 1 -- 3 2 [...])
204 This is the stack effect of `pop∘swap∘roll<∘rest∘rest`.
206 ### `pop∘swap∘roll<∘rest∘rest cons`
208 ([4 5 ...] 2 3 1 -- 3 2 [...]) (1 [...] -- [1 ...])
212 ([4 5 .1.] 2 3 1 -- 3 2 [.1.]) (6 [.2.] -- [6 .2.])
216 ([4 5 .1.] 2 3 1 -- 3 2 [.1.]) (6 [.2.] -- [6 .2.])
218 ([4 5 .2.] 2 3 1 -- 3 2 ) (6 -- [6 .2.])
220 ([4 5 .2.] 6 3 1 -- 3 ) ( -- [6 .2.])
224 ([4 5 .2.] 6 3 1 -- 3 [6 .2.])
228 ([4 5 ...] 2 3 1 -- 3 [2 ...])
232 ### `pop∘swap∘roll<∘rest∘rest∘cons cons`
235 ([4 5 ...] 2 3 1 -- 3 [2 ...]) (1 [...] -- [1 ...])
239 ([4 5 .1.] 2 3 1 -- 3 [2 .1.]) (6 [.2.] -- [6 .2.])
243 ([4 5 .1.] 2 3 1 -- 3 [2 .1.]) (6 [.2.] -- [6 .2.] )
245 ([4 5 .1.] 2 3 1 -- 3 ) (6 -- [6 2 .1.])
247 ([4 5 .1.] 2 6 1 -- ) ( -- [6 2 .1.])
249 First or second rule:
251 ([4 5 .1.] 2 6 1 -- [6 2 .1.])
255 ([4 5 ...] 2 3 1 -- [3 2 ...])
257 And there you have it, the stack effect for `pop∘swap∘roll<∘rest∘rest∘cons∘cons`.
259 ([4 5 ...] 2 3 1 -- [3 2 ...])
261 From this stack effect comment it should be possible to construct the following Python code:
266 (_, (d, (c, ((a, (b, S0)), stack)))) = stack
267 return (d, (c, S0)), stack
272 ### Representing Stack Effect Comments in Python
274 I'm going to use pairs of tuples of type descriptors, which will be integers or tuples of type descriptors:
278 roll_dn = (1, 2, 3), (2, 3, 1)
282 swap = (1, 2), (2, 1)
291 (f_in, f_out), (g_in, g_out) = f, g
296 # ---------------------
301 fg_in, fg_out = f_in, f_out + g_out
306 # ---------------------
311 fg_in, fg_out = g_in + f_in, g_out
313 else: # Unify, update, recur.
315 fo, gi = f_out[-1], g_in[-1]
319 if s == False: # s can also be the empty dict, which is ok.
320 raise TypeError('Cannot unify %r and %r.' % (fo, gi))
322 f_g = (f_in, f_out[:-1]), (g_in[:-1], g_out)
324 if s: f_g = update(s, f_g)
326 fg_in, fg_out = compose(*f_g)
335 def unify(u, v, s=None):
342 if isinstance(u, int):
346 if isinstance(v, int):
358 if not isinstance(term, tuple):
359 return s.get(term, term)
360 return tuple(update(s, inner) for inner in term)
367 def relabel(left, right):
368 return left, _1000(right)
371 if not isinstance(right, tuple):
373 return tuple(_1000(n) for n in right)
381 (((1,), ()), ((1001, 1002), (1002, 1001)))
390 s = {u: i for i, u in enumerate(sorted(_unique(f)))}
393 def _unique(f, seen=None):
396 if not isinstance(f, tuple):
403 delabel(relabel(pop, swap))
409 (((0,), ()), ((1, 2), (2, 1)))
415 At last we put it all together in a function `C()` that accepts two stack effect comments and returns their composition (or raises and exception if they can't be composed due to type conflicts.)
441 C(C(pop, swap), roll_dn)
447 ((3, 1, 2, 0), (2, 1, 3))
459 ((2, 0, 1), (1, 0, 2))
465 C(pop, C(swap, roll_dn))
471 ((3, 1, 2, 0), (2, 1, 3))
477 poswrd = reduce(C, (pop, swap, roll_dn))
484 ((3, 1, 2, 0), (2, 1, 3))
489 Here's that trick to represent functions like `rest` and `cons` that manipulate lists. We use a cons-list of tuples and give the tails their own numbers. Then everything above already works.
493 rest = ((1, 2),), (2,)
495 cons = (1, 2), ((1, 2),)
506 (((3, 4), 1, 2, 0), (2, 1, 4))
510 Compare this to the stack effect comment we wrote above:
512 (( (3, 4), 1, 2, 0 ), ( 2, 1, 4 ))
513 ( [4 ...] 2 3 0 -- 3 2 [...])
515 The translation table, if you will, would be:
527 F = reduce(C, (pop, swap, roll_dn, rest, rest, cons, cons))
535 (((3, (4, 5)), 1, 2, 0), ((2, (1, 5)),))
539 Compare with the stack effect comment and you can see it works fine:
541 ([4 5 ...] 2 3 1 -- [3 2 ...])
543 ### Dealing with `cons` and `uncons`
544 However, if we try to compose e.g. `cons` and `uncons` it won't work:
548 uncons = ((1, 2),), (1, 2)
559 Cannot unify (1, 2) and (1001, 1002).
562 #### `unify()` version 2
563 The problem is that the `unify()` function as written doesn't handle the case when both terms are tuples. We just have to add a clause to deal with this recursively:
567 def unify(u, v, s=None):
577 if isinstance(u, int):
581 if isinstance(v, int):
585 if isinstance(u, tuple) and isinstance(v, tuple):
586 if len(u) != len(v) != 2:
587 raise ValueError(repr((u, v)))
588 for uu, vv in zip(u, v):
590 if s == False: # (instead of a substitution dict.)
610 Now consider the Python function we would like to derive:
615 (_, (d, (c, ((a, (b, S0)), stack)))) = stack
616 return (d, (c, S0)), stack
619 And compare it to the input stack effect comment tuple we just computed:
629 ((3, (4, 5)), 1, 2, 0)
633 The stack-de-structuring tuple has nearly the same form as our input stack effect comment tuple, just in the reverse order:
635 (_, (d, (c, ((a, (b, S0)), stack))))
637 Remove the punctuation:
641 Reverse the order and compare:
644 ((3, (4, 5 )), 1, 2, 0)
662 is similar to the output stack effect comment tuple:
664 ((d, (c, S0)), stack)
667 This should make it pretty easy to write a Python function that accepts the stack effect comment tuples and returns a new Python function (either as a string of code or a function object ready to use) that performs the semantics of that Joy function (described by the stack effect.)
669 ### Python Identifiers
670 We want to substitute Python identifiers for the integers. I'm going to repurpose `joy.parser.Symbol` class for this:
674 from collections import defaultdict
675 from joy.parser import Symbol
679 I = iter(xrange(1000))
680 return lambda: Symbol('a%i' % next(I))
683 def identifiers(term, s=None):
685 s = defaultdict(_names_for())
686 if isinstance(term, int):
688 return tuple(identifiers(inner, s) for inner in term)
691 ### `doc_from_stack_effect()`
692 As a convenience I've implemented a function to convert the Python stack effect comment tuples to reasonable text format. There are some details in how this code works that related to stuff later in the notebook, so you should skip it for now and read it later if you're interested.
696 def doc_from_stack_effect(inputs, outputs):
697 return '(%s--%s)' % (
698 ' '.join(map(_to_str, inputs + ('',))),
699 ' '.join(map(_to_str, ('',) + outputs))
704 if not isinstance(term, tuple):
706 t = term.prefix == 's'
707 except AttributeError:
709 return '[.%i.]' % term.number if t else str(term)
712 while term and isinstance(term, tuple):
714 a.append(_to_str(item))
718 except AttributeError:
721 if term.prefix != 's':
722 raise ValueError('Stack label: %s' % (term,))
724 a.append('.%s.' % (n,))
725 return '[%s]' % ' '.join(a)
729 Now we can write a compiler function to emit Python source code. (The underscore suffix distiguishes it from the built-in `compile()` function.)
733 def compile_(name, f, doc=None):
735 doc = doc_from_stack_effect(*f)
736 inputs, outputs = identifiers(f)
737 i = o = Symbol('stack')
742 return '''def %s(stack):
745 return %s''' % (name, doc, i, o)
748 Here it is in action:
752 source = compile_('F', F)
758 """([3 4 .5.] 1 2 0 -- [2 1 .5.])"""
759 (a5, (a4, (a3, ((a0, (a1, a2)), stack)))) = stack
760 return ((a4, (a3, a2)), stack)
768 (_, (d, (c, ((a, (b, S0)), stack)))) = stack
769 return ((d, (c, S0)), stack)
778 eval(compile(source, '__main__', 'single'), {}, L)
794 from notebook_preamble import D, J, V
795 from joy.library import SimpleFunctionWrapper
800 D['F'] = SimpleFunctionWrapper(L['F'])
805 J('[4 5 ...] 2 3 1 F')
811 With this, we have a partial Joy compiler that works on the subset of Joy functions that manipulate stacks (both what I call "stack chatter" and the ones that manipulate stacks on the stack.)
813 I'm probably going to modify the definition wrapper code to detect definitions that can be compiled by this partial compiler and do it automatically. It might be a reasonable idea to detect sequences of compilable functions in definitions that have uncompilable functions in them and just compile those. However, if your library is well-factored this might be less helpful.
815 ### Compiling Library Functions
816 We can use `compile_()` to generate many primitives in the library from their stack effect comments:
822 roll_down = (1, 2, 3), (2, 3, 1)
824 roll_up = (1, 2, 3), (3, 1, 2)
828 swap = (1, 2), (2, 1)
830 rest = ((1, 2),), (2,)
832 rrest = C(rest, rest)
834 cons = (1, 2), ((1, 2),)
836 uncons = ((1, 2),), (1, 2)
838 swons = C(swap, cons)
845 for name, stack_effect_comment in sorted(defs().items()):
847 print compile_(name, stack_effect_comment)
853 """(1 2 -- [1 .2.])"""
854 (a1, (a0, stack)) = stack
855 return ((a0, a1), stack)
866 ((a0, a1), stack) = stack
870 def roll_down(stack):
871 """(1 2 3 -- 2 3 1)"""
872 (a2, (a1, (a0, stack))) = stack
873 return (a0, (a2, (a1, stack)))
877 """(1 2 3 -- 3 1 2)"""
878 (a2, (a1, (a0, stack))) = stack
879 return (a1, (a0, (a2, stack)))
883 """([0 1 .2.] -- 2)"""
884 ((a0, (a1, a2)), stack) = stack
890 (a1, (a0, stack)) = stack
891 return (a0, (a1, stack))
895 """(0 1 -- [1 .0.])"""
896 (a1, (a0, stack)) = stack
897 return ((a1, a0), stack)
901 """([1 .2.] -- 1 2)"""
902 ((a0, a1), stack) = stack
903 return (a1, (a0, stack))
907 ## Types and Subtypes of Arguments
908 So far we have dealt with types of functions, those dealing with simple stack manipulation. Let's extend our machinery to deal with types of arguments.
912 Consider the definition of `sqr`:
917 The `dup` function accepts one *anything* and returns two of that:
921 And `mul` accepts two "numbers" (we're ignoring ints vs. floats vs. complex, etc., for now) and returns just one:
927 (1 -- 1 1)∘(n n -- n)
929 The rules say we unify 1 with `n`:
931 (1 -- 1 1)∘(n n -- n)
932 --------------------------- w/ {1: n}
935 This involves detecting that "Any type" arguments can accept "numbers". If we were composing these functions the other way round this is still the case:
937 (n n -- n)∘(1 -- 1 1)
938 --------------------------- w/ {1: n}
941 The important thing here is that the mapping is going the same way in both cases, from the "any" integer to the number
943 ### Distinguishing Numbers
944 We should also mind that the number that `mul` produces is not (necessarily) the same as either of its inputs, which are not (necessarily) the same as each other:
949 (1 -- 1 1)∘(n2 n1 -- n3)
950 -------------------------------- w/ {1: n2}
951 (n2 -- n2 )∘(n2 -- n3)
954 (n2 n1 -- n3)∘(1 -- 1 1 )
955 -------------------------------- w/ {1: n3}
956 (n2 n1 -- )∘( -- n3 n3)
960 ### Distinguishing Types
961 So we need separate domains of "any" numbers and "number" numbers, and we need to be able to ask the order of these domains. Now the notes on the right side of rule three make more sense, eh?
963 (a -- b t[i])∘(c u[j] -- d) t <= u (t is subtype of u)
964 -------------------------------
965 (a -- b )∘(c -- d) t[i] == t[k] == u[j]
968 (a -- b t[i])∘(c u[j] -- d) u <= t (u is subtype of t)
969 -------------------------------
970 (a -- b )∘(c -- d) t[i] == u[k] == u[j]
972 The indices `i`, `k`, and `j` are the number part of our labels and `t` and `u` are the domains.
974 By creative use of Python's "double underscore" methods we can define a Python class hierarchy of Joy types and use the `issubclass()` method to establish domain ordering, as well as other handy behaviour that will make it fairly easy to reuse most of the code above.
978 class AnyJoyType(object):
982 def __init__(self, number):
986 return self.prefix + str(self.number)
988 def __eq__(self, other):
990 isinstance(other, self.__class__)
991 and other.prefix == self.prefix
992 and other.number == self.number
995 def __ge__(self, other):
996 return issubclass(other.__class__, self.__class__)
998 def __add__(self, other):
999 return self.__class__(self.number + other)
1003 return hash(repr(self))
1006 class NumberJoyType(AnyJoyType): prefix = 'n'
1007 class FloatJoyType(NumberJoyType): prefix = 'f'
1008 class IntJoyType(FloatJoyType): prefix = 'i'
1011 class StackJoyType(AnyJoyType):
1016 A = map(AnyJoyType, _R)
1017 N = map(NumberJoyType, _R)
1018 S = map(StackJoyType, _R)
1021 Mess with it a little:
1025 from itertools import permutations
1028 "Any" types can be specialized to numbers and stacks, but not vice versa:
1032 for a, b in permutations((A[0], N[0], S[0]), 2):
1033 print a, '>=', b, '->', a >= b
1044 Our crude [Numerical Tower](https://en.wikipedia.org/wiki/Numerical_tower) of *numbers* > *floats* > *integers* works as well (but we're not going to use it yet):
1048 for a, b in permutations((A[0], N[0], FloatJoyType(0), IntJoyType(0)), 2):
1049 print a, '>=', b, '->', a >= b
1070 dup = (A[1],), (A[1], A[1])
1072 mul = (N[1], N[2]), (N[3],)
1099 ### Modifying the Inferencer
1100 Re-labeling still works fine:
1104 foo = relabel(dup, mul)
1112 (((a1,), (a1, a1)), ((n1001, n1002), (n1003,)))
1116 #### `delabel()` version 2
1117 The `delabel()` function needs an overhaul. It now has to keep track of how many labels of each domain it has "seen".
1121 from collections import Counter
1124 def delabel(f, seen=None, c=None):
1127 seen, c = {}, Counter()
1134 if not isinstance(f, tuple):
1135 seen[f] = f.__class__(c[f.prefix])
1139 return tuple(delabel(inner, seen, c) for inner in f)
1150 (((a0,), (a0, a0)), ((n0, n1), (n2,)))
1154 #### `unify()` version 3
1158 def unify(u, v, s=None):
1168 if isinstance(u, AnyJoyType) and isinstance(v, AnyJoyType):
1175 raise TypeError('Cannot unify %r and %r.' % (u, v))
1177 if isinstance(u, tuple) and isinstance(v, tuple):
1178 if len(u) != len(v) != 2:
1179 raise TypeError(repr((u, v)))
1180 for uu, vv in zip(u, v):
1181 s = unify(uu, vv, s)
1182 if s == False: # (instead of a substitution dict.)
1186 if isinstance(v, tuple):
1188 raise TypeError('Cannot unify %r and %r.' % (u, v))
1192 if isinstance(u, tuple):
1194 raise TypeError('Cannot unify %r and %r.' % (v, u))
1202 return thing.__class__ in {AnyJoyType, StackJoyType}
1205 Rewrite the stack effect comments:
1211 roll_down = (A[1], A[2], A[3]), (A[2], A[3], A[1])
1213 roll_up = (A[1], A[2], A[3]), (A[3], A[1], A[2])
1217 popop = (A[2], A[1],), ()
1219 popd = (A[2], A[1],), (A[1],)
1221 popdd = (A[3], A[2], A[1],), (A[2], A[1],)
1223 swap = (A[1], A[2]), (A[2], A[1])
1225 rest = ((A[1], S[1]),), (S[1],)
1227 rrest = C(rest, rest)
1229 cons = (A[1], S[1]), ((A[1], S[1]),)
1231 ccons = C(cons, cons)
1233 uncons = ((A[1], S[1]),), (A[1], S[1])
1235 swons = C(swap, cons)
1237 dup = (A[1],), (A[1], A[1])
1239 dupd = (A[2], A[1]), (A[2], A[2], A[1])
1241 mul = (N[1], N[2]), (N[3],)
1245 first = ((A[1], S[1]),), (A[1],)
1247 second = C(rest, first)
1249 third = C(rest, second)
1251 tuck = (A[2], A[1]), (A[1], A[2], A[1])
1253 over = (A[2], A[1]), (A[2], A[1], A[2])
1255 succ = pred = (N[1],), (N[2],)
1257 divmod_ = pm = (N[2], N[1]), (N[4], N[3])
1269 for name, stack_effect_comment in sorted(DEFS.items()):
1270 print name, '=', doc_from_stack_effect(*stack_effect_comment)
1273 ccons = (a0 a1 [.0.] -- [a0 a1 .0.])
1274 cons = (a1 [.1.] -- [a1 .1.])
1275 divmod_ = (n2 n1 -- n4 n3)
1277 dupd = (a2 a1 -- a2 a2 a1)
1278 first = ([a1 .1.] -- a1)
1280 over = (a2 a1 -- a2 a1 a2)
1281 pm = (n2 n1 -- n4 n3)
1283 popd = (a2 a1 -- a1)
1284 popdd = (a3 a2 a1 -- a2 a1)
1287 rest = ([a1 .1.] -- [.1.])
1288 roll_down = (a1 a2 a3 -- a2 a3 a1)
1289 roll_up = (a1 a2 a3 -- a3 a1 a2)
1290 rrest = ([a0 a1 .0.] -- [.0.])
1291 second = ([a0 a1 .0.] -- a1)
1294 swap = (a1 a2 -- a2 a1)
1295 swons = ([.0.] a0 -- [a0 .0.])
1296 third = ([a0 a1 a2 .0.] -- a2)
1297 tuck = (a2 a1 -- a1 a2 a1)
1298 uncons = ([a1 .1.] -- a1 [.1.])
1303 globals().update(DEFS)
1306 #### Compose `dup` and `mul`
1320 Revisit the `F` function, works fine.
1324 F = reduce(C, (pop, swap, roll_down, rest, rest, cons, cons))
1331 (((a0, (a1, s0)), a2, a3, a4), ((a3, (a2, s0)),))
1337 print doc_from_stack_effect(*F)
1340 ([a0 a1 .0.] a2 a3 a4 -- [a3 a2 .0.])
1343 Some otherwise inefficient functions are no longer to be feared. We can also get the effect of combinators in some limited cases.
1348 print doc_from_stack_effect(*reduce(C, funcs))
1354 neato(roll_up, swap, roll_down)
1357 (a0 a1 a2 -- a1 a0 a2)
1363 neato(popdd, roll_down, pop)
1366 (a0 a1 a2 a3 -- a2 a3)
1371 # Reverse the order of the top three items.
1372 neato(roll_up, swap)
1375 (a0 a1 a2 -- a2 a1 a0)
1378 #### `compile_()` version 2
1379 Because the type labels represent themselves as valid Python identifiers the `compile_()` function doesn't need to generate them anymore:
1383 def compile_(name, f, doc=None):
1386 doc = doc_from_stack_effect(inputs, outputs)
1387 i = o = Symbol('stack')
1390 for term in outputs:
1392 return '''def %s(stack):
1395 return %s''' % (name, doc, i, o)
1400 print compile_('F', F)
1404 """([a0 a1 .0.] a2 a3 a4 -- [a3 a2 .0.])"""
1405 (a4, (a3, (a2, ((a0, (a1, s0)), stack)))) = stack
1406 return ((a3, (a2, s0)), stack)
1409 But it cannot magically create new functions that involve e.g. math and such. Note that this is *not* a `sqr` function implementation:
1413 print compile_('sqr', C(dup, mul))
1423 The functions that *can* be compiled are the ones that have only `AnyJoyType` and `StackJoyType` labels in their stack effect comments. We can write a function to check that:
1427 from itertools import imap
1431 return isinstance(f, tuple) and all(imap(compilable, f)) or stacky(f)
1436 for name, stack_effect_comment in sorted(defs().items()):
1437 if compilable(stack_effect_comment):
1438 print name, '=', doc_from_stack_effect(*stack_effect_comment)
1441 ccons = (a0 a1 [.0.] -- [a0 a1 .0.])
1442 cons = (a1 [.1.] -- [a1 .1.])
1444 dupd = (a2 a1 -- a2 a2 a1)
1445 first = ([a1 .1.] -- a1)
1446 over = (a2 a1 -- a2 a1 a2)
1448 popd = (a2 a1 -- a1)
1449 popdd = (a3 a2 a1 -- a2 a1)
1451 rest = ([a1 .1.] -- [.1.])
1452 roll_down = (a1 a2 a3 -- a2 a3 a1)
1453 roll_up = (a1 a2 a3 -- a3 a1 a2)
1454 rrest = ([a0 a1 .0.] -- [.0.])
1455 second = ([a0 a1 .0.] -- a1)
1456 swap = (a1 a2 -- a2 a1)
1457 swons = ([.0.] a0 -- [a0 .0.])
1458 third = ([a0 a1 a2 .0.] -- a2)
1459 tuck = (a2 a1 -- a1 a2 a1)
1460 uncons = ([a1 .1.] -- a1 [.1.])
1463 ## Functions that use the Stack
1465 Consider the `stack` function which grabs the whole stack, quotes it, and puts it on itself:
1467 stack (... -- ... [...] )
1468 stack (... a -- ... a [a ...] )
1469 stack (... b a -- ... b a [a b ...])
1471 We would like to represent this in Python somehow.
1472 To do this we use a simple, elegant trick.
1475 stack (a, S) -- ( (a, S), (a, S))
1476 stack (a, (b, S)) -- ( (a, (b, S)), (a, (b, S)))
1478 Instead of representing the stack effect comments as a single tuple (with N items in it) we use the same cons-list structure to hold the sequence and `unify()` the whole comments.
1481 Let's try composing `stack` and `uncons`. We want this result:
1483 stack∘uncons (... a -- ... a a [...])
1485 The stack effects are:
1489 uncons = ((a, Z), S) -- (Z, (a, S))
1493 S -- (S, S) ∘ ((a, Z), S) -- (Z, (a, S ))
1495 (a, Z) -- ∘ -- (Z, (a, (a, Z)))
1499 stack∘uncons == (a, Z) -- (Z, (a, (a, Z)))
1503 ### `stack∘uncons∘uncons`
1504 Let's try `stack∘uncons∘uncons`:
1506 (a, S ) -- (S, (a, (a, S ))) ∘ ((b, Z), S` ) -- (Z, (b, S` ))
1510 (a, (b, Z)) -- ((b, Z), (a, (a, (b, Z)))) ∘ ((b, Z), S` ) -- (Z, (b, S` ))
1512 w/ { S`: (a, (a, (b, Z))) }
1514 (a, (b, Z)) -- ((b, Z), (a, (a, (b, Z)))) ∘ ((b, Z), (a, (a, (b, Z)))) -- (Z, (b, (a, (a, (b, Z)))))
1516 (a, (b, Z)) -- (Z, (b, (a, (a, (b, Z)))))
1520 #### `compose()` version 2
1521 This function has to be modified to use the new datastructures and it is no longer recursive, instead recursion happens as part of unification.
1527 (f_in, f_out), (g_in, g_out) = f, g
1530 fg_in, fg_out = f_in, stack_concat(g_out, f_out)
1533 fg_in, fg_out = stack_concat(f_in, g_in), g_out
1535 else: # Unify and update.
1537 s = unify(g_in, f_out)
1539 if s == False: # s can also be the empty dict, which is ok.
1540 raise TypeError('Cannot unify %r and %r.' % (fo, gi))
1542 fg_in, fg_out = update(s, (f_in, g_out))
1544 return fg_in, fg_out
1547 stack_concat = lambda q, e: (q[0], stack_concat(q[1], e)) if q else e
1550 I don't want to rewrite all the defs myself, so I'll write a little conversion function instead. This is programmer's laziness.
1554 def sequence_to_stack(seq, stack=StackJoyType(23)):
1555 for item in seq: stack = item, stack
1559 name: (sequence_to_stack(i), sequence_to_stack(o))
1560 for name, (i, o) in DEFS.iteritems()
1563 globals().update(NEW_DEFS)
1568 stack = S[0], (S[0], S[0])
1579 ((a0, s0), (s0, (a0, (a0, s0))))
1585 C(C(stack, uncons), uncons)
1591 ((a0, (a1, s0)), (s0, (a1, (a0, (a0, (a1, s0))))))
1595 The display function should be changed too.
1597 ### `doc_from_stack_effect()` version 2
1598 Clunky junk, but it will suffice for now.
1602 def doc_from_stack_effect(inputs, outputs):
1603 switch = [False] # Do we need to display the '...' for the rest of the main stack?
1604 i, o = _f(inputs, switch), _f(outputs, switch)
1608 return '(%s--%s)' % (
1609 ' '.join(reversed([''] + i)),
1610 ' '.join(reversed(o + [''])),
1614 def _f(term, switch):
1616 while term and isinstance(term, tuple):
1619 assert isinstance(term, StackJoyType), repr(term)
1620 a = [_to_str(i, term, switch) for i in a]
1624 def _to_str(term, stack, switch):
1625 if not isinstance(term, tuple):
1630 '[.%i.]' % term.number
1631 if isinstance(term, StackJoyType)
1636 while term and isinstance(term, tuple):
1638 a.append(_to_str(item, stack, switch))
1639 assert isinstance(term, StackJoyType), repr(term)
1644 end = '.%i.' % term.number
1646 return '[%s]' % ' '.join(a)
1651 for name, stack_effect_comment in sorted(NEW_DEFS.items()):
1652 print name, '=', doc_from_stack_effect(*stack_effect_comment)
1655 ccons = (a0 a1 [.0.] -- [a0 a1 .0.])
1656 cons = (a1 [.1.] -- [a1 .1.])
1657 divmod_ = (n2 n1 -- n4 n3)
1659 dupd = (a2 a1 -- a2 a2 a1)
1660 first = ([a1 .1.] -- a1)
1662 over = (a2 a1 -- a2 a1 a2)
1663 pm = (n2 n1 -- n4 n3)
1665 popd = (a2 a1 -- a1)
1666 popdd = (a3 a2 a1 -- a2 a1)
1669 rest = ([a1 .1.] -- [.1.])
1670 roll_down = (a1 a2 a3 -- a2 a3 a1)
1671 roll_up = (a1 a2 a3 -- a3 a1 a2)
1672 rrest = ([a0 a1 .0.] -- [.0.])
1673 second = ([a0 a1 .0.] -- a1)
1676 swap = (a1 a2 -- a2 a1)
1677 swons = ([.0.] a0 -- [a0 .0.])
1678 third = ([a0 a1 a2 .0.] -- a2)
1679 tuck = (a2 a1 -- a1 a2 a1)
1680 uncons = ([a1 .1.] -- a1 [.1.])
1685 print ; print doc_from_stack_effect(*stack)
1686 print ; print doc_from_stack_effect(*C(stack, uncons))
1687 print ; print doc_from_stack_effect(*C(C(stack, uncons), uncons))
1688 print ; print doc_from_stack_effect(*C(C(stack, uncons), cons))
1694 (... a0 -- ... a0 a0 [...])
1696 (... a1 a0 -- ... a1 a0 a0 a1 [...])
1698 (... a0 -- ... a0 [a0 ...])
1703 print doc_from_stack_effect(*C(ccons, stack))
1706 (... a1 a0 [.0.] -- ... [a1 a0 .0.] [[a1 a0 .0.] ...])
1719 ((s0, (a0, (a1, s1))), (((a1, (a0, s0)), s1), ((a1, (a0, s0)), s1)))
1723 #### `compile_()` version 3
1724 This makes the `compile_()` function pretty simple as the stack effect comments are now already in the form needed for the Python code:
1728 def compile_(name, f, doc=None):
1731 doc = doc_from_stack_effect(i, o)
1732 return '''def %s(stack):
1735 return %s''' % (name, doc, i, o)
1740 print compile_('Q', Q)
1744 """(... a1 a0 [.0.] -- ... [a1 a0 .0.] [[a1 a0 .0.] ...])"""
1745 (s0, (a0, (a1, s1))) = stack
1746 return (((a1, (a0, s0)), s1), ((a1, (a0, s0)), s1))
1751 unstack = (S[1], S[0]), S[1]
1752 enstacken = S[0], (S[0], S[1])
1757 print doc_from_stack_effect(*unstack)
1765 print doc_from_stack_effect(*enstacken)
1773 print doc_from_stack_effect(*C(cons, unstack))
1781 print doc_from_stack_effect(*C(cons, enstacken))
1784 (a0 [.0.] -- [[a0 .0.] .1.])
1795 ((s0, (a0, s1)), (a0, s0))
1799 ## Multiple Stack Effects
1804 class IntJoyType(NumberJoyType): prefix = 'i'
1807 F = map(FloatJoyType, _R)
1808 I = map(IntJoyType, _R)
1814 ((I[2], (I[1], S[0])), (I[3], S[0])),
1815 ((F[2], (I[1], S[0])), (F[3], S[0])),
1816 ((I[2], (F[1], S[0])), (F[3], S[0])),
1817 ((F[2], (F[1], S[0])), (F[3], S[0])),
1824 print doc_from_stack_effect(*f)
1840 print doc_from_stack_effect(*dup), doc_from_stack_effect(*f), doc_from_stack_effect(*e)
1843 (a1 -- a1 a1) (i1 i2 -- i3) (i0 -- i1)
1844 (a1 -- a1 a1) (f1 f2 -- f3) (f0 -- f1)
1849 from itertools import product
1852 def meta_compose(F, G):
1853 for f, g in product(F, G):
1861 return sorted(set(meta_compose(F, G)))
1866 for f in MC([dup], muls):
1867 print doc_from_stack_effect(*f)
1876 for f in MC([dup], [mul]):
1877 print doc_from_stack_effect(*f)
1885 How to deal with `concat`?
1887 concat ([.0.] [.1.] -- [.0. .1.])
1889 We would like to represent this in Python somehow...
1893 concat = (S[0], S[1]), ((S[0], S[1]),)
1896 But this is actually `cons` with the first argument restricted to be a stack:
1898 ([.0.] [.1.] -- [[.0.] .1.])
1900 What we have implemented so far would actually only permit:
1902 ([.0.] [.1.] -- [.2.])
1906 concat = (S[0], S[1]), (S[2],)
1910 Which works but can lose information. Consider `cons concat`, this is how much information we *could* retain:
1912 (1 [.0.] [.1.] -- [1 .0. .1.])
1916 (1 [.0.] [.1.] -- [.2.])
1918 ### Brzo...'s Derivitives of Regular Expressions
1920 We can invent a new type of type variable, a "sequence type" (I think this is what they mean in the literature by that term...) or "Kleene Star" type. I'm going to represent it as a type letter and the asterix, so a sequence of zero or more `AnyJoyType` variables would be:
1924 The `A*` works by splitting the universe into two alternate histories:
1928 The Kleene star variable disappears in one universe, and in the other it turns into an `AnyJoyType` variable followed by itself again. We have to return all universes (represented by their substitution dicts, the "unifiers") that don't lead to type conflicts.
1930 Consider unifying two stacks (the lowercase letters are any type variables of the kinds we have defined so far):
1932 [a A* b .0.] U [c d .1.]
1934 [ A* b .0.] U [ d .1.]
1936 Now we have to split universes to unify `A*`. In the first universe it disappears:
1942 While in the second it spawns an `A`, which we will label `e`:
1944 [e A* b .0.] U [d .1.]
1946 [ A* b .0.] U [ .1.]
1948 [ A* b .0.] U [ .1.]
1950 Giving us two unifiers:
1952 {c: a, d: b, .1.: .0.}
1953 {c: a, d: e, .1.: A* b .0.}
1957 class KleeneStar(object):
1961 def __init__(self, number):
1962 self.number = number
1964 self.prefix = repr(self)
1967 return '%s%i*' % (self.kind.prefix, self.number)
1971 return self.kind(10000 * self.number + self.count)
1973 def __eq__(self, other):
1975 isinstance(other, self.__class__)
1976 and other.number == self.number
1979 def __ge__(self, other):
1980 return self.kind >= other.kind
1982 def __add__(self, other):
1983 return self.__class__(self.number + other)
1987 return hash(repr(self))
1989 class AnyStarJoyType(KleeneStar): kind = AnyJoyType
1990 class NumberStarJoyType(KleeneStar): kind = NumberJoyType
1991 #class FloatStarJoyType(KleeneStar): kind = FloatJoyType
1992 #class IntStarJoyType(KleeneStar): kind = IntJoyType
1993 class StackStarJoyType(KleeneStar): kind = StackJoyType
1996 As = map(AnyStarJoyType, _R)
1997 Ns = map(NumberStarJoyType, _R)
1998 Ss = map(StackStarJoyType, _R)
2001 #### `unify()` version 4
2002 Can now return multiple results...
2006 def unify(u, v, s=None):
2016 if isinstance(u, AnyJoyType) and isinstance(v, AnyJoyType):
2023 raise TypeError('Cannot unify %r and %r.' % (u, v))
2025 if isinstance(u, tuple) and isinstance(v, tuple):
2026 if len(u) != len(v) != 2:
2027 raise TypeError(repr((u, v)))
2030 if isinstance(a, KleeneStar):
2031 # Two universes, in one the Kleene star disappears and unification
2032 # continues without it...
2035 # In the other it spawns a new variable.
2036 s1 = unify(u, (a.another(), v))
2044 if isinstance(a, KleeneStar):
2046 s1 = unify(v, (a.another(), u))
2052 ses = unify(u[0], v[0])
2055 results += unify(u[1], v[1], sn)
2058 if isinstance(v, tuple):
2060 raise TypeError('Cannot unify %r and %r.' % (u, v))
2064 if isinstance(u, tuple):
2066 raise TypeError('Cannot unify %r and %r.' % (v, u))
2074 return thing.__class__ in {AnyJoyType, StackJoyType}
2105 for result in unify(b, a):
2106 print result, '->', update(result, a), update(result, b)
2109 {s1: (a1, s2)} -> (a1*, (a1, s2)) (a1, s2)
2110 {a1: a10001, s2: (a1*, s1)} -> (a1*, s1) (a10001, (a1*, s1))
2115 for result in unify(a, b):
2116 print result, '->', update(result, a), update(result, b)
2119 {s1: (a1, s2)} -> (a1*, (a1, s2)) (a1, s2)
2120 {a1: a10002, s2: (a1*, s1)} -> (a1*, s1) (a10002, (a1*, s1))
2124 (a1*, s1) [a1*] (a1, s2) [a1]
2126 (a1*, (a1, s2)) [a1* a1] (a1, s2) [a1]
2128 (a1*, s1) [a1*] (a2, (a1*, s1)) [a2 a1*]
2132 sum_ = ((Ns[1], S[1]), S[0]), (N[0], S[0])
2134 print doc_from_stack_effect(*sum_)
2142 f = (N[1], (N[2], (N[3], S[1]))), S[0]
2144 print doc_from_stack_effect(S[0], f)
2152 for result in unify(sum_[0], f):
2153 print result, '->', update(result, sum_[1])
2156 {s1: (n1, (n2, (n3, s1)))} -> (n0, s0)
2157 {n1: n10001, s1: (n2, (n3, s1))} -> (n0, s0)
2158 {n1: n10001, s1: (n3, s1), n2: n10002} -> (n0, s0)
2159 {n1: n10001, s1: (n1*, s1), n3: n10003, n2: n10002} -> (n0, s0)
2162 #### `compose()` version 3
2163 This function has to be modified to use the new datastructures and it is no longer recursive, instead recursion happens as part of unification.
2169 (f_in, f_out), (g_in, g_out) = f, g
2172 yield f_in, stack_concat(g_out, f_out)
2175 yield stack_concat(f_in, g_in), g_out
2177 else: # Unify and update.
2179 s = unify(g_in, f_out)
2182 raise TypeError('Cannot unify %r and %r.' % (fo, gi))
2185 yield update(result, (f_in, g_out))
2191 def meta_compose(F, G):
2192 for f, g in product(F, G):
2194 for result in C(f, g):
2201 f, g = relabel(f, g)
2202 for fg in compose(f, g):
2208 for f in MC([dup], muls):
2209 print doc_from_stack_effect(*f)
2220 for f in MC([dup], [sum_]):
2221 print doc_from_stack_effect(*f)
2224 ([n0* .0.] -- [n0* .0.] n0)
2231 for f in MC([cons], [sum_]):
2232 print doc_from_stack_effect(*f)
2236 (n0 [n0* .0.] -- n1)
2241 sum_ = (((N[1], (Ns[1], S[1])), S[0]), (N[0], S[0]))
2242 print doc_from_stack_effect(*cons),
2243 print doc_from_stack_effect(*sum_),
2245 for f in MC([cons], [sum_]):
2246 print doc_from_stack_effect(*f)
2249 (a1 [.1.] -- [a1 .1.]) ([n1 n1* .1.] -- n0) (n0 [n0* .0.] -- n1)
2254 a = (A[4], (As[1], (A[3], S[1])))
2261 (a4, (a1*, (a3, s1)))
2267 b = (A[1], (A[2], S[2]))
2280 for result in unify(b, a):
2284 {a1: a4, s2: s1, a2: a3}
2285 {a1: a4, s2: (a1*, (a3, s1)), a2: a10003}
2290 for result in unify(a, b):
2294 {s2: s1, a2: a3, a4: a1}
2295 {s2: (a1*, (a3, s1)), a2: a10004, a4: a1}
2298 ### represent `concat`
2300 ([.0.] [.1.] -- [A*(.0.) .1.])
2302 Meaning that `A*` on the right-hand side should all the crap from `.0.`.
2304 ([ .0.] [.1.] -- [ A* .1.])
2305 ([a .0.] [.1.] -- [a A* .1.])
2306 ([a b .0.] [.1.] -- [a b A* .1.])
2307 ([a b c .0.] [.1.] -- [a b c A* .1.])
2313 ([ .0.] [.1.] -- [ .1.])
2314 ([a .0.] [.1.] -- [a .1.])
2315 ([a b .0.] [.1.] -- [a b .1.])
2316 ([a b c .0.] [.1.] -- [a b c .1.])
2317 ([a A* c .0.] [.1.] -- [a A* c .1.])
2321 (a, (b, S0)) . S1 = (a, (b, (A*, S1)))
2325 class Astar(object):
2332 while isinstance(s0, tuple):
2335 assert isinstance(s0, StackJoyType), repr(s0)
2337 for term in reversed(a):
2344 a, b = (A[1], S[0]), (A[2], S[1])
2355 (a1, (A*, (a2, s1)))
2359 ## Joy in the Logical Paradigm
2360 For this to work the type label classes have to be modified to let `T >= t` succeed, where e.g. `T` is `IntJoyType` and `t` is `int`
2364 F = reduce(C, (pop, swap, roll_down, rest, rest, cons, cons))
2366 print doc_from_stack_effect(*F)
2370 ---------------------------------------------------------------------------
2372 ValueError Traceback (most recent call last)
2374 <ipython-input-113-4b4cb6ff86e5> in <module>()
2375 1 F = reduce(C, (pop, swap, roll_down, rest, rest, cons, cons))
2377 ----> 3 print doc_from_stack_effect(*F)
2380 <ipython-input-101-ddee30dbb1a6> in C(f, g)
2382 11 f, g = relabel(f, g)
2383 ---> 12 for fg in compose(f, g):
2384 13 yield delabel(fg)
2387 <ipython-input-100-4237a6bb159d> in compose(f, g)
2388 1 def compose(f, g):
2390 ----> 3 (f_in, f_out), (g_in, g_out) = f, g
2395 <ipython-input-101-ddee30dbb1a6> in C(f, g)
2397 11 f, g = relabel(f, g)
2398 ---> 12 for fg in compose(f, g):
2399 13 yield delabel(fg)
2402 <ipython-input-100-4237a6bb159d> in compose(f, g)
2403 1 def compose(f, g):
2405 ----> 3 (f_in, f_out), (g_in, g_out) = f, g
2410 <ipython-input-101-ddee30dbb1a6> in C(f, g)
2412 11 f, g = relabel(f, g)
2413 ---> 12 for fg in compose(f, g):
2414 13 yield delabel(fg)
2417 <ipython-input-100-4237a6bb159d> in compose(f, g)
2418 1 def compose(f, g):
2420 ----> 3 (f_in, f_out), (g_in, g_out) = f, g
2425 <ipython-input-101-ddee30dbb1a6> in C(f, g)
2427 11 f, g = relabel(f, g)
2428 ---> 12 for fg in compose(f, g):
2429 13 yield delabel(fg)
2432 <ipython-input-100-4237a6bb159d> in compose(f, g)
2433 1 def compose(f, g):
2435 ----> 3 (f_in, f_out), (g_in, g_out) = f, g
2440 <ipython-input-101-ddee30dbb1a6> in C(f, g)
2442 11 f, g = relabel(f, g)
2443 ---> 12 for fg in compose(f, g):
2444 13 yield delabel(fg)
2447 <ipython-input-100-4237a6bb159d> in compose(f, g)
2448 1 def compose(f, g):
2450 ----> 3 (f_in, f_out), (g_in, g_out) = f, g
2455 ValueError: need more than 1 value to unpack
2460 from joy.parser import text_to_expression
2465 s = text_to_expression('[3 4 ...] 2 1')
2490 ## Typing Combinators
2494 This is an open subject.
2496 The obvious thing is that you now need two pairs of tuples to describe the combinators' effects, a stack effect comment and an expression effect comment:
2498 dip (a [F] --)--(-- F a)
2500 One thing that might help is...
2502 ## Abstract Interpretation
2504 ## Something else...
2505 [4 5 ...] 2 1 0 pop∘swap∘roll<∘rest∘rest∘cons∘cons
2506 [4 5 ...] 2 1 swap∘roll<∘rest∘rest∘cons∘cons
2507 [4 5 ...] 1 2 roll<∘rest∘rest∘cons∘cons
2508 1 2 [4 5 ...] rest∘rest∘cons∘cons
2509 1 2 [5 ...] rest∘cons∘cons