Mercurial > repos > tabletprog
annotate types.js @ 100:9db0e3533b23
Some work on parameterized types
author | Mike Pavone <pavone@retrodev.com> |
---|---|
date | Wed, 08 Aug 2012 09:19:14 -0700 |
parents | b58b19c455ec |
children | 5d15b91e738a |
rev | line source |
---|---|
99 | 1 function anytype() {}; |
2 anytype.prototype.satisfiedBy = function(type) { | |
3 return true; | |
4 }; | |
5 anytype.prototype.str = function(indent) { | |
6 if (indent === undefined) { | |
7 indent = ''; | |
8 } | |
9 return indent + 'any\n'; | |
10 }; | |
11 anytype.prototype.id = 0; | |
12 anytype.prototype.callable = true; | |
13 anytype.prototype.replaceParams = function() { return this; }; | |
14 var any = new anytype(); | |
15 | |
16 function typeparam(name, base) | |
17 { | |
18 this.name = name; | |
19 this.base = base; | |
20 this.callable = base.callable; | |
21 } | |
22 typeparam.prototype.replaceParams = function(paramtypes) { | |
23 if (!(this.name in paramtypes)) { | |
24 return this; | |
25 } | |
26 if (!this.base.satisfiedBy(paramtypes[this.name])) { | |
27 throw new Error('param ' + this.name + ' has base type ' + this.base.str() + ' which is not satisfied by ' + paramtypes[this.name].str()); | |
28 } | |
29 return paramtypes[this.name]; | |
30 }; | |
31 typeparam.prototype.satisfiedBy = function(type) { | |
32 return this.base.satisfiedBy(type); | |
33 }; | |
34 typeparam.prototype.str = function(indent) { | |
35 return indent + 'param ' + this.name + '\n'; | |
36 }; | |
37 | |
38 var nexttypeid = 1; | |
39 | |
40 function objecttype() | |
41 { | |
42 this.messages = {}; | |
43 this.id = nexttypeid++; | |
44 this.typeparams = []; | |
45 this.satisfies_cache = {}; | |
46 this.satisfies_cache[this.id] = true; | |
47 } | |
48 | |
49 objecttype.prototype.callable = false; | |
50 | |
51 objecttype.prototype.addMessage = function(name, type) | |
52 { | |
53 this.messages[name] = type; | |
54 }; | |
55 | |
56 objecttype.prototype.satisfiedBy = function(type) { | |
57 if (type.id in this.satisfies_cache) { | |
58 return this.satisfies_cache[type.id]; | |
59 } | |
60 if (type.lazyinit) { | |
61 type.lazyinit(); | |
62 } | |
63 //temporarily set cache entry to true to prevent infinite recursion | |
64 this.satisfies_cache[type.id] = true; | |
65 var ret = true; | |
66 if (type.messages === undefined) { | |
100
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
67 print('type has no messages'); |
99 | 68 ret = false; |
69 } | |
70 if (ret) { | |
71 for (var msgname in this.messages) { | |
72 if (!(msgname in type.messages) || !this.messages[msgname].satisfiedBy(type.messages[msgname])) { | |
100
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
73 print(msgname, 'missing in type'); |
99 | 74 ret = false; |
75 break; | |
76 } | |
77 } | |
78 } | |
79 this.satisfies_cache[type.id] = ret; | |
80 return ret; | |
81 }; | |
82 | |
83 objecttype.prototype.str = function(indent) { | |
84 if (indent === undefined) { | |
85 indent = ''; | |
86 } | |
87 if (indent.length > 6) { | |
88 return 'max depth reached\n'; | |
89 } | |
90 var newindent = indent + '\t'; | |
91 var childindent = newindent + '\t' | |
92 var ret = indent + 'objectype {\n'; | |
93 for (var msgname in this.messages) { | |
94 ret += newindent + msgname + ':\n' + this.messages[msgname].str(childindent) | |
95 } | |
96 return ret + indent + '}\n'; | |
97 }; | |
98 | |
99 objecttype.prototype.replaceParams = function(paramtypes, visited) { | |
100
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
100 if (visited === undefined) { |
99 | 101 visited = {}; |
102 } | |
103 if (this.id in visited) { | |
104 return visited[this.id]; | |
105 } | |
106 var me = visited[this.id] = this.clone(); | |
107 for (var msgname in this.messages) { | |
108 me.messages[msgname] = me.messages[msgname].replaceParams(paramtypes, visited); | |
109 } | |
110 return me; | |
111 }; | |
112 | |
113 objecttype.prototype.clone = function() { | |
114 var clone = new objecttype(); | |
115 for (var msgname in this.messages) { | |
116 clone.messages[msgname] = this.messages[msgname]; | |
117 } | |
118 clone.typeparams = this.typeparams; | |
119 return clone; | |
120 }; | |
121 | |
122 function lambdatype() | |
123 { | |
124 this.id = nexttypeid++; | |
125 this.messages = {}; | |
126 this.params = []; | |
127 this.paramlu = {}; | |
128 this.typeparams = []; | |
129 this.returntype = any; | |
130 this.satisfies_cache = {}; | |
131 this.satisfies_cache[this.id] = true; | |
132 } | |
133 | |
134 lambdatype.prototype.callable = true; | |
135 | |
136 lambdatype.prototype.addParam = function(name) { | |
137 this.paramlu[name] = this.params.length; | |
138 this.params.push(any); | |
139 }; | |
140 | |
141 lambdatype.prototype.paramType = function(name, type) { | |
142 this.params[this.paramlu[name]] = type; | |
143 }; | |
144 | |
145 lambdatype.prototype.addMessage = function(name, type) | |
146 { | |
147 this.messages[name] = type; | |
148 }; | |
149 | |
150 lambdatype.prototype.satisfiedBy = function(type) { | |
151 if (type.id in this.satisfies_cache) { | |
152 return this.satisfies_cache[type.id]; | |
153 } | |
154 if (type.lazyinit) { | |
155 type.lazyinit(); | |
156 } | |
157 //temporarily set cache entry to true to prevent infinite recursion | |
158 this.satisfies_cache[type.id] = true; | |
159 var ret = true; | |
160 if (!(type.callable) || this.params.length != type.params.length) { | |
100
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
161 print('type is not callable or param length mismatch'); |
99 | 162 ret = false; |
163 } | |
164 if (ret) { | |
165 for (var i in this.params) { | |
166 if (i >= type.params.length || !this.params[i].satisfiedBy(type.params[i])) { | |
100
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
167 print('param ', i, ' is not satisfied'); |
99 | 168 ret = false; |
169 break; | |
170 } | |
171 } | |
172 } | |
173 if (ret) { | |
174 for (var msgname in this.messages) { | |
175 if (!(msgname in type.messages) || !this.messages[msgname].satisfiedBy(type.messages[msgname])) { | |
100
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
176 print('message', msgname, 'is not satisfied'); |
99 | 177 ret = false; |
178 break; | |
179 } | |
180 } | |
181 } | |
182 ret = ret && this.returntype.satisfiedBy(type.returntype); | |
183 this.satisfies_cache[type.id] = ret; | |
184 return ret; | |
185 } | |
186 | |
187 lambdatype.prototype.str = function(indent) { | |
188 if (indent === undefined) { | |
189 indent = ''; | |
190 } | |
191 if (indent.length > 6) { | |
192 return 'max depth reached\n'; | |
193 } | |
194 var newindent = indent + '\t'; | |
195 var childindent = newindent + '\t' | |
196 var ret = indent + 'lambdatype {\n' + newindent + 'params: {\n'; | |
197 for (var i = 0; i < this.params.length; i++) { | |
198 ret += childindent + i + ':\n' + this.params[i].str(childindent + '\t'); | |
199 } | |
200 ret += newindent + '}\n' + newindent + 'returntype:\n' + this.returntype.str(childindent); | |
201 | |
202 for (var msgname in this.messages) { | |
203 ret += newindent + msgname + ':\n' + this.messages[msgname].str(childindent) | |
204 } | |
205 return ret + indent + '}\n'; | |
206 }; | |
207 | |
208 lambdatype.prototype.replaceParams = function(paramtypes, visited) { | |
100
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
209 if (visited === undefined) { |
99 | 210 visited = {}; |
211 } | |
212 if (this.id in visited) { | |
213 return visited[this.id]; | |
214 } | |
215 var me = visited[this.id] = this.clone(); | |
216 for (var msgname in this.messages) { | |
217 me.messages[msgname] = me.messages[msgname].replaceParams(paramtypes, visited); | |
218 } | |
219 return me; | |
220 }; | |
221 | |
222 lambdatype.prototype.clone = function() { | |
223 var clone = new lambdatype(); | |
224 for (var msgname in this.messages) { | |
225 clone.messages[msgname] = this.messages[msgname]; | |
226 } | |
227 clone.paramlu = this.paramlu; | |
228 clone.params = this.params.slice(0, this.params.length); | |
229 clone.returntype = this.returntype; | |
230 clone.typeparams = this.typeparams; | |
231 return clone; | |
232 }; | |
233 | |
234 function uniontype(a, b) | |
235 { | |
236 this.a = a; | |
237 this.b = b; | |
238 this.id = nexttypeid++; | |
239 this.satisfies_cache = null; | |
240 } | |
241 | |
242 uniontype.prototype.lazyinit = function() { | |
100
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
243 if (this.satisfies_cache == null) { |
99 | 244 this.satisfies_cache = {}; |
245 this.satisfies_cache[this.id] = true; | |
246 this.messages = {}; | |
100
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
247 if (this.a.messages !== undefined && this.b.messages !== undefined) { |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
248 for (var msgname in this.a.messages) { |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
249 if (msgname in this.b.messages) { |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
250 this.messages[msgname] = mkunion(this.a.messages[msgname], this.b.messages[msgname]); |
99 | 251 } |
252 } | |
253 } | |
254 this.callable = false; | |
100
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
255 if (this.a.callable && this.b.callable && this.a.params.length == this.b.params.length) { |
99 | 256 this.callable = true; |
257 this.params = []; | |
100
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
258 for (var i = 0; i < this.a.params.length; i++) { |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
259 this.params.push(mkunion(this.a.params[i], this.b.params[i])); |
99 | 260 } |
100
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
261 this.returntype = mkunion(this.a.returntype, this.b.returntype); |
99 | 262 } |
263 } | |
264 }; | |
265 | |
266 uniontype.prototype.satisfiedBy = function(type) | |
267 { | |
268 this.lazyinit(); | |
269 if (type.id in this.satisfies_cache) { | |
270 return this.satisfies_cache[type.id]; | |
271 } | |
272 this.satisfies_cache[type.id] = true; | |
273 var ret = this.a.satisfiedBy(type) || this.b.satisfiedBy(type); | |
274 this.satisfies_cache[type.id] = ret; | |
275 return ret; | |
276 }; | |
277 | |
278 uniontype.prototype.str = function(indent) | |
279 { | |
280 if (indent === undefined) { | |
281 indent = ''; | |
282 } | |
283 if (indent.length > 6) { | |
284 return 'max depth reached\n'; | |
285 } | |
100
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
286 return indent + 'Union {\n\t' + indent + this.a.str(indent+'\t') + '\t' + indent + this.b.str(indent+'\t') + indent + '}\n'; |
99 | 287 }; |
288 | |
289 uniontype.prototype.replaceParams = function(paramtypes, visited) { | |
100
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
290 if (visited === undefined) { |
99 | 291 visited = {}; |
292 } | |
293 if (this.id in visited) { | |
294 return visited[this.id]; | |
295 } | |
296 var me = visited[this.id] = this.clone(); | |
297 me.a = me.a.replaceParams(paramtypes, visited); | |
298 me.b = me.b.replaceParams(paramtypes, visited); | |
299 return me; | |
300 }; | |
301 | |
302 uniontype.prototype.clone = function() { | |
303 return new uniontype(this.a, this.b); | |
304 }; | |
305 | |
306 | |
307 function mkunion(a, b) | |
308 { | |
309 //if b is a subtype of a, then a | b is equivalent to a | |
310 if (a.satisfiedBy(b)) { | |
311 return a; | |
312 } | |
313 //if a is a subtype of b, then a | b is equivalent to b | |
314 if (b.satisfiedBy(a)) { | |
315 return b; | |
316 } | |
317 return new uniontype(a, b); | |
318 } | |
319 | |
320 function withtparams(type, params) | |
321 { | |
322 this.type = type; | |
323 this.params = params; | |
100
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
324 this.replaced = false; |
99 | 325 } |
326 | |
100
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
327 withtparams.prototype = { |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
328 satisfiedBy: function(type) { |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
329 this.lazyinit(); |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
330 return this.type.satisfiedBy(type); |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
331 }, |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
332 str: function(indent) { |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
333 if (indent === undefined) { |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
334 indent = ''; |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
335 } |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
336 if (indent.length > 6) { |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
337 return 'max depth reached\n'; |
99 | 338 } |
100
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
339 return this.type.str(indent) + indent + '<' + this.params.map(function(p) { return p.str(indent); }).join(', ') + '>'; |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
340 }, |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
341 replaceParams: function(paramtypes) { |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
342 var replaced = false; |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
343 for (var i in this.params) { |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
344 var newp = this.params[i].replaceParams(paramtypes); |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
345 if (newp != this.params[i]) { |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
346 replaced = true; |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
347 this.params[i] = newp; |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
348 } |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
349 } |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
350 return this; |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
351 }, |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
352 lazyinit: function() { |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
353 if (!this.replaced) { |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
354 var childptypes = {}; |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
355 for (var i in this.type.typeparams) { |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
356 print(this.type.typeparams[i], 'is', this.params[i].str()); |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
357 childptypes[this.type.typeparams[i]] = this.params[i] |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
358 } |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
359 this.type = this.type.replaceParams(childptypes, {}); |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
360 this.replaced = true; |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
361 } |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
362 }, |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
363 get messages() { |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
364 this.lazyinit(); |
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
365 return this.type.messages; |
99 | 366 } |
367 }; | |
368 | |
369 function typetest() | |
370 { | |
371 var foo = new objecttype(); | |
372 var msgtype = new lambdatype(); | |
373 msgtype.addParam('fo'); | |
374 msgtype.returntype = foo; | |
375 foo.addMessage('bar', msgtype); | |
376 var baz = new objecttype(); | |
377 var msgtype2 = new lambdatype(); | |
378 msgtype2.addParam('fo'); | |
379 msgtype2.paramType('fo', foo); | |
380 msgtype2.returntype = baz; | |
381 baz.addMessage('bar', msgtype2); | |
382 baz.addMessage('qux', msgtype); | |
383 var shizzle = new objecttype(); | |
384 shizzle.addMessage('bar', msgtype); | |
385 shizzle.addMessage('boo', msgtype); | |
386 return {foo: foo, baz: baz, shizzle: shizzle}; | |
387 } | |
388 | |
389 function paramtypetest() | |
390 { | |
391 var empty = new objecttype(); | |
392 var tlnode = new objecttype(); | |
393 tlnode.typeparams = ['T']; | |
394 var t = new typeparam('T', any); | |
395 var q = new typeparam('Q', any); | |
396 var head = new lambdatype(); | |
100
9db0e3533b23
Some work on parameterized types
Mike Pavone <pavone@retrodev.com>
parents:
99
diff
changeset
|
397 head.returntype = t; |
99 | 398 tlnode.addMessage('head', head); |
399 var tail = new lambdatype(); | |
400 var econs = new lambdatype(); | |
401 econs.addParam('val'); | |
402 econs.typeparams = ['Q']; | |
403 econs.paramType('val', q); | |
404 econs.returntype = new withtparams(tlnode, [q]); | |
405 empty.addMessage('cons', econs); | |
406 tail.returntype = new uniontype(new withtparams(tlnode, [t]), empty); | |
407 tlnode.addMessage('tail', tail); | |
408 var cons = new lambdatype(); | |
409 cons.addParam('val'); | |
410 cons.paramType('val', t); | |
411 cons.returntype = new withtparams(tlnode, [t]); | |
412 tlnode.addMessage('cons', cons); | |
413 return {empty: empty, tlnode: tlnode}; | |
414 } | |
415 |