• R/O
  • SSH

Joypy: Commit

Main interpreter and library.


Commit MetaInfo

Revision150ba0008881e5d786a44b2ae48730976a9d2533 (tree)
Time2018-07-18 09:12:27
AuthorSimon Forman <sforman@hush...>
CommiterSimon Forman

Log Message

Moving right along.

A little clunky but it seems to work so far.

Change Summary

Incremental Difference

diff -r f60f46a50473 -r 150ba0008881 joy/library.py
--- a/joy/library.py Tue Jul 17 12:43:24 2018 -0700
+++ b/joy/library.py Tue Jul 17 17:12:27 2018 -0700
@@ -25,11 +25,12 @@
2525 '''
2626 from inspect import getdoc
2727 from functools import wraps
28+from itertools import count
2829 from inspect import getmembers, isfunction
2930 import operator, math
3031
3132 from .parser import text_to_expression, Symbol
32-from .utils.stack import list_to_stack, iter_stack, pick, concat
33+from .utils.stack import expression_to_string, list_to_stack, iter_stack, pick, concat
3334 from .utils.brutal_hackery import rename_code_object
3435
3536 from .utils import generated_library as genlib
@@ -38,16 +39,28 @@
3839 ef,
3940 stack_effect,
4041 AnyJoyType,
42+ AnyStarJoyType,
4143 BooleanJoyType,
4244 NumberJoyType,
45+ NumberStarJoyType,
4346 StackJoyType,
47+ StackStarJoyType,
4448 FloatJoyType,
4549 IntJoyType,
50+ SymbolJoyType,
4651 TextJoyType,
4752 _functions,
53+ FUNCTIONS,
54+ infer,
55+ JoyTypeError,
56+ combinator_effect,
4857 )
4958
5059
60+_SYM_NUMS = count().next
61+_COMB_NUMS = count().next
62+
63+
5164 _R = range(10)
5265 A = a0, a1, a2, a3, a4, a5, a6, a7, a8, a9 = map(AnyJoyType, _R)
5366 B = b0, b1, b2, b3, b4, b5, b6, b7, b8, b9 = map(BooleanJoyType, _R)
@@ -58,6 +71,12 @@
5871 T = t0, t1, t2, t3, t4, t5, t6, t7, t8, t9 = map(TextJoyType, _R)
5972
6073
74+_R = range(1, 11)
75+As = map(AnyStarJoyType, _R)
76+Ns = map(NumberStarJoyType, _R)
77+Ss = map(StackStarJoyType, _R)
78+
79+
6180 sec0 = stack_effect(t1)()
6281 sec1 = stack_effect(s0, i1)(s1)
6382 sec2 = stack_effect(s0, i1)(a1)
@@ -67,7 +86,7 @@
6786 sec_binary_math = stack_effect(n1, n2)(n3)
6887 sec_unary_logic = stack_effect(a1)(b1)
6988 sec_unary_math = stack_effect(n1)(n2)
70-
89+sec_Ns_math = stack_effect((Ns[1], s1),)(n0)
7190
7291 _dictionary = {}
7392
@@ -350,6 +369,14 @@
350369 Add the definition to the dictionary.
351370 '''
352371 F = class_.parse_definition(definition)
372+ try:
373+ #print F._body
374+ secs = infer(*F._body)
375+ except JoyTypeError:
376+ pass
377+ print F.name, '==', expression_to_string(F.body), ' --failed to infer stack effect.'
378+ else:
379+ FUNCTIONS[F.name] = SymbolJoyType(F.name, secs, _SYM_NUMS())
353380 dictionary[F.name] = F
354381
355382
@@ -357,23 +384,11 @@
357384 return (line.strip() for line in text.splitlines() if '==' in line)
358385
359386
360-
361-## eh = compose(dup, bool_)
362-## sqr = compose(dup, mul)
363-## of = compose(swap, at)
364-
365-
366387 #
367388 # Functions
368389 #
369390
370391
371-# Load the auto-generated primitives into the dictionary.
372-_functions.update(yin_functions())
373-for name, primitive in getmembers(genlib, isfunction):
374- inscribe(SimpleFunctionWrapper(primitive))
375-
376-
377392 @inscribe
378393 @sec0
379394 @FunctionWrapper
@@ -528,6 +543,7 @@
528543
529544
530545 @inscribe
546+@sec_Ns_math
531547 @SimpleFunctionWrapper
532548 def max_(S):
533549 '''Given a list find the maximum.'''
@@ -536,6 +552,7 @@
536552
537553
538554 @inscribe
555+@sec_Ns_math
539556 @SimpleFunctionWrapper
540557 def min_(S):
541558 '''Given a list find the minimum.'''
@@ -544,6 +561,7 @@
544561
545562
546563 @inscribe
564+@sec_Ns_math
547565 @SimpleFunctionWrapper
548566 def sum_(S):
549567 '''Given a quoted sequence of numbers return the sum.
@@ -872,6 +890,7 @@
872890
873891
874892 @inscribe
893+@combinator_effect(_COMB_NUMS(), s1)
875894 @FunctionWrapper
876895 def i(stack, expression, dictionary):
877896 '''
@@ -889,6 +908,7 @@
889908
890909
891910 @inscribe
911+@combinator_effect(_COMB_NUMS(), s1)
892912 @FunctionWrapper
893913 def x(stack, expression, dictionary):
894914 '''
@@ -906,6 +926,7 @@
906926
907927
908928 @inscribe
929+#@combinator_effect(_COMB_NUMS(), s7, s6)
909930 @FunctionWrapper
910931 def b(stack, expression, dictionary):
911932 '''
@@ -941,6 +962,7 @@
941962
942963
943964 @inscribe
965+#@combinator_effect(_COMB_NUMS(), s7, s6)
944966 @FunctionWrapper
945967 def infra(stack, expression, dictionary):
946968 '''
@@ -1150,6 +1172,7 @@
11501172
11511173
11521174 @inscribe
1175+@combinator_effect(_COMB_NUMS(), a1, s1)
11531176 @FunctionWrapper
11541177 def dip(stack, expression, dictionary):
11551178 '''
@@ -1437,7 +1460,31 @@
14371460 del F # Otherwise Sphinx autodoc will pick it up.
14381461
14391462
1463+YIN_STACK_EFFECTS = yin_functions()
1464+
1465+# Load the auto-generated primitives into the dictionary.
1466+_functions.update(YIN_STACK_EFFECTS)
1467+# exec '''
1468+
1469+# eh = compose(dup, bool)
1470+# sqr = compose(dup, mul)
1471+# of = compose(swap, at)
1472+
1473+# ''' in dict(compose=compose), _functions
1474+
1475+FUNCTIONS.update(
1476+ (name, SymbolJoyType(name, [_functions[name]], _SYM_NUMS()))
1477+ for name in sorted(_functions)
1478+ )
1479+for name, primitive in getmembers(genlib, isfunction):
1480+ inscribe(SimpleFunctionWrapper(primitive))
1481+
1482+
14401483 add_aliases(_dictionary, ALIASES)
1484+add_aliases(_functions, ALIASES)
1485+add_aliases(FUNCTIONS, ALIASES)
14411486
14421487
14431488 DefinitionWrapper.add_definitions(definitions, _dictionary)
1489+
1490+#sec_Ns_math(_dictionary['product'])
diff -r f60f46a50473 -r 150ba0008881 joy/utils/polytypes.py
--- a/joy/utils/polytypes.py Tue Jul 17 12:43:24 2018 -0700
+++ b/joy/utils/polytypes.py Tue Jul 17 17:12:27 2018 -0700
@@ -10,12 +10,6 @@
1010
1111 '''
1212 import sys
13-from inspect import stack as inspect_stack
14-from itertools import chain, product
15-from logging import getLogger
16-
17-_log = getLogger(__name__)
18-
1913 import joy.library
2014 from joy.parser import Symbol, text_to_expression
2115 from joy.utils.stack import (
@@ -23,391 +17,22 @@
2317 expression_to_string,
2418 list_to_stack,
2519 )
26-from joy.utils.types import (
27- AnyJoyType, A,
28- BooleanJoyType, B,
29- DEFS,
30- doc_from_stack_effect,
31- FloatJoyType, F,
32- JoyTypeError,
33- NumberJoyType, N,
34- StackJoyType, S,
35- _stacky,
36- _R,
37- relabel, delabel,
38- reify,
39- )
40-
41-
42-# We no longer want FloatJoyType to accept IntJoyType.
43-class IntJoyType(NumberJoyType): prefix = 'i'
44-
45-
46-class KleeneStar(object):
47- u'''
48- A sequence of zero or more `AnyJoyType` variables would be:
49-
50- A*
51-
52- The `A*` works by splitting the universe into two alternate histories:
53-
54- A* → ∅
55-
56- A* → A A*
57-
58- The Kleene star variable disappears in one universe, and in the other
59- it turns into an `AnyJoyType` variable followed by itself again.
60-
61- We have to return all universes (represented by their substitution
62- dicts, the "unifiers") that don't lead to type conflicts.
63- '''
64-
65- kind = AnyJoyType
66-
67- def __init__(self, number):
68- assert number
69- self.number = number
70- self.count = 0
71- self.prefix = repr(self)
72-
73- def __repr__(self):
74- return '%s%i*' % (self.kind.prefix, self.number)
75-
76- def another(self):
77- self.count += 1
78- return self.kind(10000 * self.number + self.count)
79-
80- def __eq__(self, other):
81- return (
82- isinstance(other, self.__class__)
83- and other.number == self.number
84- )
85-
86- def __ge__(self, other):
87- return self.kind >= other.kind
88-
89- def __add__(self, other):
90- return self.__class__(self.number + other)
91- __radd__ = __add__
92-
93- def __hash__(self):
94- return hash(repr(self))
95-
96-
97-class AnyStarJoyType(KleeneStar): kind = AnyJoyType
98-class NumberStarJoyType(KleeneStar): kind = NumberJoyType
99-#class FloatStarJoyType(KleeneStar): kind = FloatJoyType
100-#class IntStarJoyType(KleeneStar): kind = IntJoyType
101-class StackStarJoyType(KleeneStar): kind = StackJoyType
102-
103-
104-class FunctionJoyType(AnyJoyType):
105-
106- def __init__(self, name, sec, number):
107- self.name = name
108- self.stack_effects = sec
109- self.number = number
110-
111- def __add__(self, other):
112- return self
113- __radd__ = __add__
114-
115- def __repr__(self):
116- return self.name
117-
118-
119-class SymbolJoyType(FunctionJoyType):
120- '''
121- Represent non-combinator functions.
122-
123- These type variables carry the stack effect comments and can
124- appear in expressions (as in quoted programs.)
125- '''
126- prefix = 'F'
127-
128-
129-class CombinatorJoyType(FunctionJoyType):
130- '''
131- Represent combinators.
132-
133- These type variables carry Joy functions that implement the
134- behaviour of Joy combinators and they can appear in expressions.
135- For simple combinators the implementation functions can be the
136- combinators themselves.
137-
138- These types can also specify a stack effect (input side only) to
139- guard against being used on invalid types.
140- '''
141-
142- prefix = 'C'
143-
144- def __init__(self, name, sec, number, expect=None):
145- super(CombinatorJoyType, self).__init__(name, sec, number)
146- self.expect = expect
147-
148- def enter_guard(self, f):
149- if self.expect is None:
150- return f
151- g = self.expect, self.expect
152- new_f = list(compose(f, g, ()))
153- assert len(new_f) == 1, repr(new_f)
154- return new_f[0][1]
155-
156-
157-def _log_uni(U):
158- def inner(u, v, s=None):
159- _log.debug(
160- '%3i %s U %s w/ %s',
161- len(inspect_stack()), u, v, s,
162- )
163- res = U(u, v, s)
164- _log.debug(
165- '%3i %s U %s w/ %s => %s',
166- len(inspect_stack()), u, v, s, res,
167- )
168- return res
169- return inner
20+# from joy.utils.types import (
21+# AnyJoyType, A,
22+# BooleanJoyType, B,
23+# DEFS,
24+# doc_from_stack_effect,
25+# FloatJoyType, F,
26+# JoyTypeError,
27+# NumberJoyType, N,
28+# StackJoyType, S,
29+# _stacky,
30+# _R,
31+# relabel, delabel,
32+# reify,
33+# )
17034
17135
172-@_log_uni
173-def unify(u, v, s=None):
174- '''
175- Return a tuple of substitution dicts representing unifiers for u and v.
176- '''
177- if s is None:
178- s = {}
179- elif s:
180- u = reify(s, u)
181- v = reify(s, v)
182-
183- if u == v:
184- res = s,
185-
186- elif isinstance(u, tuple) and isinstance(v, tuple):
187- if len(u) != 2 or len(v) != 2:
188- if _that_one_special_case(u, v):
189- return s,
190- raise ValueError(repr((u, v))) # Bad input.
191-
192-
193- (a, b), (c, d) = v, u
194- if isinstance(a, KleeneStar):
195- if isinstance(c, KleeneStar):
196- s = _lil_uni(a, c, s) # Attempt to unify the two K-stars.
197- res = unify(d, b, s[0])
198-
199- else:
200- # Two universes, in one the Kleene star disappears and
201- # unification continues without it...
202- s0 = unify(u, b)
203-
204- # In the other it spawns a new variable.
205- s1 = unify(u, (a.another(), v))
206-
207- res = s0 + s1
208- for sn in res:
209- sn.update(s)
210-
211- elif isinstance(c, KleeneStar):
212- res = unify(v, d) + unify(v, (c.another(), u))
213- for sn in res:
214- sn.update(s)
215-
216- else:
217- res = tuple(flatten(unify(d, b, sn) for sn in unify(c, a, s)))
218-
219- elif isinstance(v, tuple):
220- if not _stacky(u):
221- raise JoyTypeError('Cannot unify %r and %r.' % (u, v))
222- s[u] = v
223- res = s,
224-
225- elif isinstance(u, tuple):
226- if not _stacky(v):
227- raise JoyTypeError('Cannot unify %r and %r.' % (v, u))
228- s[v] = u
229- res = s,
230-
231- else:
232- res = _lil_uni(u, v, s)
233-
234- return res
235-
236-
237-def _that_one_special_case(u, v):
238- '''
239- Handle e.g. ((), (n1*, s1)) when type-checking sum, product, etc...
240- '''
241- return (
242- u == ()
243- and len(v) == 2
244- and isinstance(v[0], KleeneStar)
245- and isinstance(v[1], StackJoyType)
246- )
247-
248-
249-def _lil_uni(u, v, s):
250- if u >= v:
251- s[u] = v
252- return s,
253- if v >= u:
254- s[v] = u
255- return s,
256- raise JoyTypeError('Cannot unify %r and %r.' % (u, v))
257-
258-
259-def _compose(f, g, e):
260- (f_in, f_out), (g_in, g_out) = f, g
261- for s in unify(g_in, f_out):
262- yield reify(s, (e, (f_in, g_out)))
263-
264-
265-def compose(f, g, e):
266- '''
267- Yield the stack effects of the composition of two stack effects. An
268- expression is carried along and updated and yielded.
269- '''
270- f, g = relabel(f, g)
271- for fg in _compose(f, g, e):
272- yield delabel(fg)
273-
274-
275-def _meta_compose(F, G, e):
276- for f, g in product(F, G):
277- try:
278- for result in compose(f, g, e): yield result
279- except JoyTypeError:
280- pass
281-
282-
283-def meta_compose(F, G, e):
284- '''
285- Yield the stack effects of the composition of two lists of stack
286- effects. An expression is carried along and updated and yielded.
287- '''
288- res = sorted(set(_meta_compose(F, G, e)))
289- if not res:
290- raise JoyTypeError('Cannot unify %r and %r.' % (F, G))
291- return res
292-
293-
294-def flatten(g):
295- return list(chain.from_iterable(g))
296-
297-
298-ID = S[0], S[0] # Identity function.
299-
300-
301-def _infer(e, F=ID):
302- _log_it(e, F)
303- if not e:
304- return [F]
305-
306- n, e = e
307-
308- if isinstance(n, SymbolJoyType):
309- eFG = meta_compose([F], n.stack_effects, e)
310- res = flatten(_infer(e, Fn) for e, Fn in eFG)
311-
312- elif isinstance(n, CombinatorJoyType):
313- fi, fo = n.enter_guard(F)
314- res = flatten(_interpret(f, fi, fo, e) for f in n.stack_effects)
315-
316- elif isinstance(n, Symbol):
317- assert n not in FUNCTIONS, repr(n)
318- func = joy.library._dictionary[n]
319- res = _interpret(func, F[0], F[1], e)
320-
321- else:
322- fi, fo = F
323- res = _infer(e, (fi, (n, fo)))
324-
325- return res
326-
327-
328-def _interpret(f, fi, fo, e):
329- new_fo, ee, _ = f(fo, e, {})
330- ee = reify(FUNCTIONS, ee) # Fix Symbols.
331- new_F = fi, new_fo
332- return _infer(ee, new_F)
333-
334-
335-def _log_it(e, F):
336- _log.info(
337- u'%3i %s ∘ %s',
338- len(inspect_stack()),
339- doc_from_stack_effect(*F),
340- expression_to_string(e),
341- )
342-
343-
344-def infer(*expression):
345- '''
346- Return a list of stack effects for a Joy expression.
347-
348- For example::
349-
350- h = infer(pop, swap, rolldown, rest, rest, cons, cons)
351- for fi, fo in h:
352- print doc_from_stack_effect(fi, fo)
353-
354- Prints::
355-
356- ([a4 a5 ...1] a3 a2 a1 -- [a2 a3 ...1])
357-
358- '''
359- return sorted(set(_infer(list_to_stack(expression))))
360-
361-
362-def infer_string(string):
363- e = reify(FUNCTIONS, text_to_expression(string)) # Fix Symbols.
364- return sorted(set(_infer(e)))
365-
366-
367-def infer_expression(expression):
368- e = reify(FUNCTIONS, expression) # Fix Symbols.
369- return sorted(set(_infer(e)))
370-
371-
372-def type_check(name, stack):
373- '''
374- Trinary predicate. True if named function type-checks, False if it
375- fails, None if it's indeterminate (because I haven't entered it into
376- the FUNCTIONS dict yet.)
377- '''
378- try:
379- func = FUNCTIONS[name]
380- except KeyError:
381- return # None, indicating unknown
382-
383- for fi, fo in infer(func):
384- try:
385- U = unify(fi, stack)
386- except (JoyTypeError, ValueError), e:
387- #print >> sys.stderr, name, e, stack
388- continue
389- #print U
390- return True
391- return False
392-
393-
394-a0, a1, a2, a3, a4, a5, a6, a7, a8, a9 = A
395-b0, b1, b2, b3, b4, b5, b6, b7, b8, b9 = B
396-n0, n1, n2, n3, n4, n5, n6, n7, n8, n9 = N
397-f0, f1, f2, f3, f4, f5, f6, f7, f8, f9 = F
398-i0, i1, i2, i3, i4, i5, i6, i7, i8, i9 = I = map(IntJoyType, _R)
399-s0, s1, s2, s3, s4, s5, s6, s7, s8, s9 = S
400-
401-_R = range(1, 11)
402-As = map(AnyStarJoyType, _R)
403-Ns = map(NumberStarJoyType, _R)
404-Ss = map(StackStarJoyType, _R)
405-
406-
407-FUNCTIONS = {
408- name: SymbolJoyType(name, [DEFS[name]], i)
409- for i, name in enumerate(sorted(DEFS))
410- }
41136 '''Docstring for functions in Sphinx?'''
41237
41338
@@ -452,6 +77,7 @@
45277 ))
45378 })
45479
80+
45581 def branch_true(stack, expression, dictionary):
45682 (then, (else_, (flag, stack))) = stack
45783 return stack, CONCAT(then, expression), dictionary
diff -r f60f46a50473 -r 150ba0008881 joy/utils/types.py
--- a/joy/utils/types.py Tue Jul 17 12:43:24 2018 -0700
+++ b/joy/utils/types.py Tue Jul 17 17:12:27 2018 -0700
@@ -1,7 +1,13 @@
1+# -*- coding: utf_8
2+from logging import getLogger
3+
4+_log = getLogger(__name__)
5+
16 from collections import Counter
2-from itertools import imap
3-from joy.utils.stack import concat
4-from joy.parser import Symbol
7+from itertools import imap, chain, product
8+from inspect import stack as inspect_stack
9+from joy.utils.stack import concat, expression_to_string, list_to_stack
10+from joy.parser import Symbol, text_to_expression
511
612
713 class AnyJoyType(object):
@@ -49,7 +55,7 @@
4955
5056
5157 class NumberJoyType(AnyJoyType):
52- accept = int, float, long, complex
58+ accept = bool, int, float, long, complex
5359 prefix = 'n'
5460
5561
@@ -78,6 +84,118 @@
7884 return False
7985
8086
87+class KleeneStar(object):
88+ u'''
89+ A sequence of zero or more `AnyJoyType` variables would be:
90+
91+ A*
92+
93+ The `A*` works by splitting the universe into two alternate histories:
94+
95+ A* → ∅
96+
97+ A* → A A*
98+
99+ The Kleene star variable disappears in one universe, and in the other
100+ it turns into an `AnyJoyType` variable followed by itself again.
101+
102+ We have to return all universes (represented by their substitution
103+ dicts, the "unifiers") that don't lead to type conflicts.
104+ '''
105+
106+ kind = AnyJoyType
107+
108+ def __init__(self, number):
109+ assert number
110+ self.number = number
111+ self.count = 0
112+ self.prefix = repr(self)
113+
114+ def __repr__(self):
115+ return '%s%i*' % (self.kind.prefix, self.number)
116+
117+ def another(self):
118+ self.count += 1
119+ return self.kind(10000 * self.number + self.count)
120+
121+ def __eq__(self, other):
122+ return (
123+ isinstance(other, self.__class__)
124+ and other.number == self.number
125+ )
126+
127+ def __ge__(self, other):
128+ return self.kind >= other.kind
129+
130+ def __add__(self, other):
131+ return self.__class__(self.number + other)
132+ __radd__ = __add__
133+
134+ def __hash__(self):
135+ return hash(repr(self))
136+
137+
138+class AnyStarJoyType(KleeneStar): kind = AnyJoyType
139+class NumberStarJoyType(KleeneStar): kind = NumberJoyType
140+class FloatStarJoyType(KleeneStar): kind = FloatJoyType
141+class IntStarJoyType(KleeneStar): kind = IntJoyType
142+class StackStarJoyType(KleeneStar): kind = StackJoyType
143+class TextStarJoyType(KleeneStar): kind = TextJoyType
144+
145+
146+class FunctionJoyType(AnyJoyType):
147+
148+ def __init__(self, name, sec, number):
149+ self.name = name
150+ self.stack_effects = sec
151+ self.number = number
152+
153+ def __add__(self, other):
154+ return self
155+ __radd__ = __add__
156+
157+ def __repr__(self):
158+ return self.name
159+
160+
161+class SymbolJoyType(FunctionJoyType):
162+ '''
163+ Represent non-combinator functions.
164+
165+ These type variables carry the stack effect comments and can
166+ appear in expressions (as in quoted programs.)
167+ '''
168+ prefix = 'F'
169+
170+
171+class CombinatorJoyType(FunctionJoyType):
172+ '''
173+ Represent combinators.
174+
175+ These type variables carry Joy functions that implement the
176+ behaviour of Joy combinators and they can appear in expressions.
177+ For simple combinators the implementation functions can be the
178+ combinators themselves.
179+
180+ These types can also specify a stack effect (input side only) to
181+ guard against being used on invalid types.
182+ '''
183+
184+ prefix = 'C'
185+
186+ def __init__(self, name, sec, number, expect=None):
187+ super(CombinatorJoyType, self).__init__(name, sec, number)
188+ self.expect = expect
189+
190+ def enter_guard(self, f):
191+ if self.expect is None:
192+ return f
193+ g = self.expect, self.expect
194+ new_f = list(poly_compose(f, g, ()))
195+ assert len(new_f) == 1, repr(new_f)
196+ return new_f[0][1]
197+
198+
81199 class JoyTypeError(Exception): pass
82200
83201
@@ -135,7 +253,7 @@
135253 return tuple(delabel(inner, seen, c) for inner in f)
136254
137255
138-def unify(u, v, s=None):
256+def uni_unify(u, v, s=None):
139257 '''
140258 Return a substitution dict representing a unifier for u and v.
141259 '''
@@ -157,7 +275,7 @@
157275 if len(u) != len(v) != 2:
158276 raise ValueError(repr((u, v))) # Bad input.
159277 (a, b), (c, d) = u, v
160- s = unify(b, d, unify(a, c, s))
278+ s = uni_unify(b, d, uni_unify(a, c, s))
161279
162280 elif isinstance(v, tuple):
163281 if not _stacky(u):
@@ -175,6 +293,112 @@
175293 return s
176294
177295
296+def _log_uni(U):
297+ def inner(u, v, s=None):
298+ _log.debug(
299+ '%3i %s U %s w/ %s',
300+ len(inspect_stack()), u, v, s,
301+ )
302+ res = U(u, v, s)
303+ _log.debug(
304+ '%3i %s U %s w/ %s => %s',
305+ len(inspect_stack()), u, v, s, res,
306+ )
307+ return res
308+ return inner
309+
310+
311+@_log_uni
312+def unify(u, v, s=None):
313+ '''
314+ Return a tuple of substitution dicts representing unifiers for u and v.
315+ '''
316+ if s is None:
317+ s = {}
318+ elif s:
319+ u = reify(s, u)
320+ v = reify(s, v)
321+
322+ if u == v:
323+ res = s,
324+
325+ elif isinstance(u, tuple) and isinstance(v, tuple):
326+ if len(u) != 2 or len(v) != 2:
327+ if _that_one_special_case(u, v):
328+ return s,
329+ raise ValueError(repr((u, v))) # Bad input.
330+
331+
332+ (a, b), (c, d) = v, u
333+ if isinstance(a, KleeneStar):
334+ if isinstance(c, KleeneStar):
335+ s = _lil_uni(a, c, s) # Attempt to unify the two K-stars.
336+ res = unify(d, b, s[0])
337+
338+ else:
339+ # Two universes, in one the Kleene star disappears and
340+ # unification continues without it...
341+ s0 = unify(u, b)
342+
343+ # In the other it spawns a new variable.
344+ s1 = unify(u, (a.another(), v))
345+
346+ res = s0 + s1
347+ for sn in res:
348+ sn.update(s)
349+
350+ elif isinstance(c, KleeneStar):
351+ res = unify(v, d) + unify(v, (c.another(), u))
352+ for sn in res:
353+ sn.update(s)
354+
355+ else:
356+ res = tuple(flatten(unify(d, b, sn) for sn in unify(c, a, s)))
357+
358+ elif isinstance(v, tuple):
359+ if not _stacky(u):
360+ raise JoyTypeError('Cannot unify %r and %r.' % (u, v))
361+ s[u] = v
362+ res = s,
363+
364+ elif isinstance(u, tuple):
365+ if not _stacky(v):
366+ raise JoyTypeError('Cannot unify %r and %r.' % (v, u))
367+ s[v] = u
368+ res = s,
369+
370+ else:
371+ res = _lil_uni(u, v, s)
372+
373+ return res
374+
375+
376+def _that_one_special_case(u, v):
377+ '''
378+ Handle e.g. ((), (n1*, s1)) when type-checking sum, product, etc...
379+ '''
380+ return (
381+ u == ()
382+ and len(v) == 2
383+ and isinstance(v[0], KleeneStar)
384+ and isinstance(v[1], StackJoyType)
385+ )
386+
387+
388+def flatten(g):
389+ return list(chain.from_iterable(g))
390+
391+
392+def _lil_uni(u, v, s):
393+ if u >= v:
394+ s[u] = v
395+ return s,
396+ if v >= u:
397+ s[v] = u
398+ return s,
399+ raise JoyTypeError('Cannot unify %r and %r.' % (u, v))
400+
401+
178402 def _stacky(thing):
179403 return thing.__class__ in {AnyJoyType, StackJoyType}
180404
@@ -185,7 +409,7 @@
185409 '''
186410 # Relabel, unify, update, delabel.
187411 (f_in, f_out), (g_in, g_out) = relabel(f, g)
188- fg = reify(unify(g_in, f_out), (f_in, g_out))
412+ fg = reify(uni_unify(g_in, f_out), (f_in, g_out))
189413 return delabel(fg)
190414
191415
@@ -275,7 +499,144 @@
275499 return %s''' % (name, doc, i, o)
276500
277501
278-_functions = {}
502+def _poly_compose(f, g, e):
503+ (f_in, f_out), (g_in, g_out) = f, g
504+ for s in unify(g_in, f_out):
505+ yield reify(s, (e, (f_in, g_out)))
506+
507+
508+def poly_compose(f, g, e):
509+ '''
510+ Yield the stack effects of the composition of two stack effects. An
511+ expression is carried along and updated and yielded.
512+ '''
513+ f, g = relabel(f, g)
514+ for fg in _poly_compose(f, g, e):
515+ yield delabel(fg)
516+
517+
518+def _meta_compose(F, G, e):
519+ for f, g in product(F, G):
520+ try:
521+ for result in poly_compose(f, g, e): yield result
522+ except JoyTypeError:
523+ pass
524+
525+
526+def meta_compose(F, G, e):
527+ '''
528+ Yield the stack effects of the composition of two lists of stack
529+ effects. An expression is carried along and updated and yielded.
530+ '''
531+ res = sorted(set(_meta_compose(F, G, e)))
532+ if not res:
533+ raise JoyTypeError('Cannot unify %r and %r.' % (F, G))
534+ return res
535+
536+
537+_S0 = StackJoyType(0)
538+ID = _S0, _S0 # Identity function.
539+
540+
541+def _infer(e, F=ID):
542+ _log_it(e, F)
543+ if not e:
544+ return [F]
545+
546+ n, e = e
547+
548+ if isinstance(n, SymbolJoyType):
549+ eFG = meta_compose([F], n.stack_effects, e)
550+ res = flatten(_infer(e, Fn) for e, Fn in eFG)
551+
552+ elif isinstance(n, CombinatorJoyType):
553+ fi, fo = n.enter_guard(F)
554+ res = flatten(_interpret(f, fi, fo, e) for f in n.stack_effects)
555+
556+ elif isinstance(n, Symbol):
557+ if n in FUNCTIONS:
558+ res =_infer((FUNCTIONS[n], e), F)
559+ else:
560+ raise JoyTypeError
561+ # print n
562+ # func = joy.library._dictionary[n]
563+ # res = _interpret(func, F[0], F[1], e)
564+
565+ else:
566+ fi, fo = F
567+ res = _infer(e, (fi, (n, fo)))
568+
569+ return res
570+
571+
572+def _interpret(f, fi, fo, e):
573+ new_fo, ee, _ = f(fo, e, {})
574+ ee = reify(FUNCTIONS, ee) # Fix Symbols.
575+ new_F = fi, new_fo
576+ return _infer(ee, new_F)
577+
578+
579+def _log_it(e, F):
580+ _log.info(
581+ u'%3i %s ∘ %s',
582+ len(inspect_stack()),
583+ doc_from_stack_effect(*F),
584+ expression_to_string(e),
585+ )
586+
587+
588+def infer(*expression):
589+ '''
590+ Return a list of stack effects for a Joy expression.
591+
592+ For example::
593+
594+ h = infer(pop, swap, rolldown, rest, rest, cons, cons)
595+ for fi, fo in h:
596+ print doc_from_stack_effect(fi, fo)
597+
598+ Prints::
599+
600+ ([a4 a5 ...1] a3 a2 a1 -- [a2 a3 ...1])
601+
602+ '''
603+ return sorted(set(_infer(list_to_stack(expression))))
604+
605+
606+def infer_string(string):
607+ e = reify(FUNCTIONS, text_to_expression(string)) # Fix Symbols.
608+ return sorted(set(_infer(e)))
609+
610+
611+def infer_expression(expression):
612+ e = reify(FUNCTIONS, expression) # Fix Symbols.
613+ return sorted(set(_infer(e)))
614+
615+
616+def type_check(name, stack):
617+ '''
618+ Trinary predicate. True if named function type-checks, False if it
619+ fails, None if it's indeterminate (because I haven't entered it into
620+ the FUNCTIONS dict yet.)
621+ '''
622+ try:
623+ func = FUNCTIONS[name]
624+ except KeyError:
625+ return # None, indicating unknown
626+
627+ for fi, fo in infer(func):
628+ try:
629+ U = unify(fi, stack)
630+ except (JoyTypeError, ValueError), e:
631+ #print >> sys.stderr, name, e, stack
632+ continue
633+ #print U
634+ return True
635+ return False
636+
637+
638+FUNCTIONS = {} # Polytypes (lists of stack effects.)
639+_functions = {} # plain ol' stack effects.
279640
280641
281642 def __(*seq):
@@ -303,6 +664,14 @@
303664 return _ef
304665
305666
667+def combinator_effect(number, *expect):
668+ def _combinator_effect(c):
669+ C = FUNCTIONS[c.name] = CombinatorJoyType(c.name, [c], number)
670+ if expect: C.expect = __(*expect)
671+ return c
672+ return _combinator_effect
673+
674+
306675 def show(DEFS):
307676 for name, stack_effect_comment in sorted(DEFS.iteritems()):
308677 t = ' *'[compilable(stack_effect_comment)]
Show on old repository browser