Mercurial > repos > tabletprog
comparison types.js @ 99:b58b19c455ec
Initial work on type system
author | Mike Pavone <pavone@retrodev.com> |
---|---|
date | Tue, 07 Aug 2012 23:29:21 -0700 |
parents | |
children | 9db0e3533b23 |
comparison
equal
deleted
inserted
replaced
98:094227f2f64e | 99:b58b19c455ec |
---|---|
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) { | |
67 ret = false; | |
68 } | |
69 if (ret) { | |
70 for (var msgname in this.messages) { | |
71 if (!(msgname in type.messages) || !this.messages[msgname].satisfiedBy(type.messages[msgname])) { | |
72 ret = false; | |
73 break; | |
74 } | |
75 } | |
76 } | |
77 this.satisfies_cache[type.id] = ret; | |
78 return ret; | |
79 }; | |
80 | |
81 objecttype.prototype.str = function(indent) { | |
82 if (indent === undefined) { | |
83 indent = ''; | |
84 } | |
85 if (indent.length > 6) { | |
86 return 'max depth reached\n'; | |
87 } | |
88 var newindent = indent + '\t'; | |
89 var childindent = newindent + '\t' | |
90 var ret = indent + 'objectype {\n'; | |
91 for (var msgname in this.messages) { | |
92 ret += newindent + msgname + ':\n' + this.messages[msgname].str(childindent) | |
93 } | |
94 return ret + indent + '}\n'; | |
95 }; | |
96 | |
97 objecttype.prototype.replaceParams = function(paramtypes, visited) { | |
98 if (visisted === undefined) { | |
99 visited = {}; | |
100 } | |
101 if (this.id in visited) { | |
102 return visited[this.id]; | |
103 } | |
104 var me = visited[this.id] = this.clone(); | |
105 for (var msgname in this.messages) { | |
106 me.messages[msgname] = me.messages[msgname].replaceParams(paramtypes, visited); | |
107 } | |
108 return me; | |
109 }; | |
110 | |
111 objecttype.prototype.clone = function() { | |
112 var clone = new objecttype(); | |
113 for (var msgname in this.messages) { | |
114 clone.messages[msgname] = this.messages[msgname]; | |
115 } | |
116 clone.typeparams = this.typeparams; | |
117 return clone; | |
118 }; | |
119 | |
120 function lambdatype() | |
121 { | |
122 this.id = nexttypeid++; | |
123 this.messages = {}; | |
124 this.params = []; | |
125 this.paramlu = {}; | |
126 this.typeparams = []; | |
127 this.returntype = any; | |
128 this.satisfies_cache = {}; | |
129 this.satisfies_cache[this.id] = true; | |
130 } | |
131 | |
132 lambdatype.prototype.callable = true; | |
133 | |
134 lambdatype.prototype.addParam = function(name) { | |
135 this.paramlu[name] = this.params.length; | |
136 this.params.push(any); | |
137 }; | |
138 | |
139 lambdatype.prototype.paramType = function(name, type) { | |
140 this.params[this.paramlu[name]] = type; | |
141 }; | |
142 | |
143 lambdatype.prototype.addMessage = function(name, type) | |
144 { | |
145 this.messages[name] = type; | |
146 }; | |
147 | |
148 lambdatype.prototype.satisfiedBy = function(type) { | |
149 if (type.id in this.satisfies_cache) { | |
150 return this.satisfies_cache[type.id]; | |
151 } | |
152 if (type.lazyinit) { | |
153 type.lazyinit(); | |
154 } | |
155 //temporarily set cache entry to true to prevent infinite recursion | |
156 this.satisfies_cache[type.id] = true; | |
157 var ret = true; | |
158 if (!(type.callable) || this.params.length != type.params.length) { | |
159 ret = false; | |
160 } | |
161 if (ret) { | |
162 for (var i in this.params) { | |
163 if (i >= type.params.length || !this.params[i].satisfiedBy(type.params[i])) { | |
164 ret = false; | |
165 break; | |
166 } | |
167 } | |
168 } | |
169 if (ret) { | |
170 for (var msgname in this.messages) { | |
171 if (!(msgname in type.messages) || !this.messages[msgname].satisfiedBy(type.messages[msgname])) { | |
172 ret = false; | |
173 break; | |
174 } | |
175 } | |
176 } | |
177 ret = ret && this.returntype.satisfiedBy(type.returntype); | |
178 this.satisfies_cache[type.id] = ret; | |
179 return ret; | |
180 } | |
181 | |
182 lambdatype.prototype.str = function(indent) { | |
183 if (indent === undefined) { | |
184 indent = ''; | |
185 } | |
186 if (indent.length > 6) { | |
187 return 'max depth reached\n'; | |
188 } | |
189 var newindent = indent + '\t'; | |
190 var childindent = newindent + '\t' | |
191 var ret = indent + 'lambdatype {\n' + newindent + 'params: {\n'; | |
192 for (var i = 0; i < this.params.length; i++) { | |
193 ret += childindent + i + ':\n' + this.params[i].str(childindent + '\t'); | |
194 } | |
195 ret += newindent + '}\n' + newindent + 'returntype:\n' + this.returntype.str(childindent); | |
196 | |
197 for (var msgname in this.messages) { | |
198 ret += newindent + msgname + ':\n' + this.messages[msgname].str(childindent) | |
199 } | |
200 return ret + indent + '}\n'; | |
201 }; | |
202 | |
203 lambdatype.prototype.replaceParams = function(paramtypes, visited) { | |
204 if (visisted === undefined) { | |
205 visited = {}; | |
206 } | |
207 if (this.id in visited) { | |
208 return visited[this.id]; | |
209 } | |
210 var me = visited[this.id] = this.clone(); | |
211 for (var msgname in this.messages) { | |
212 me.messages[msgname] = me.messages[msgname].replaceParams(paramtypes, visited); | |
213 } | |
214 return me; | |
215 }; | |
216 | |
217 lambdatype.prototype.clone = function() { | |
218 var clone = new lambdatype(); | |
219 for (var msgname in this.messages) { | |
220 clone.messages[msgname] = this.messages[msgname]; | |
221 } | |
222 clone.paramlu = this.paramlu; | |
223 clone.params = this.params.slice(0, this.params.length); | |
224 clone.returntype = this.returntype; | |
225 clone.typeparams = this.typeparams; | |
226 return clone; | |
227 }; | |
228 | |
229 function uniontype(a, b) | |
230 { | |
231 this.a = a; | |
232 this.b = b; | |
233 this.id = nexttypeid++; | |
234 this.satisfies_cache = null; | |
235 } | |
236 | |
237 uniontype.prototype.lazyinit = function() { | |
238 if (this.satisfies_cache = null) { | |
239 this.satisfies_cache = {}; | |
240 this.satisfies_cache[this.id] = true; | |
241 this.messages = {}; | |
242 if (a.messages !== undefined && b.messages !== undefined) { | |
243 for (var msgname in a.messages) { | |
244 if (msgname in b.messages) { | |
245 this.messages[msgname] = mkunion(a.messages[msgname], b.messages[msgname]); | |
246 } | |
247 } | |
248 } | |
249 this.callable = false; | |
250 if (a.callable && b.callable && a.params.length == b.params.length) { | |
251 this.callable = true; | |
252 this.params = []; | |
253 for (var i = 0; i < a.params.length; i++) { | |
254 this.params.push(mkunion(a.params[i], b.params[i])); | |
255 } | |
256 this.returntype = mkunion(a.returntype, b.returntype); | |
257 } | |
258 } | |
259 }; | |
260 | |
261 uniontype.prototype.satisfiedBy = function(type) | |
262 { | |
263 this.lazyinit(); | |
264 if (type.id in this.satisfies_cache) { | |
265 return this.satisfies_cache[type.id]; | |
266 } | |
267 this.satisfies_cache[type.id] = true; | |
268 var ret = this.a.satisfiedBy(type) || this.b.satisfiedBy(type); | |
269 this.satisfies_cache[type.id] = ret; | |
270 return ret; | |
271 }; | |
272 | |
273 uniontype.prototype.str = function(indent) | |
274 { | |
275 if (indent === undefined) { | |
276 indent = ''; | |
277 } | |
278 if (indent.length > 6) { | |
279 return 'max depth reached\n'; | |
280 } | |
281 return indent + 'Union {\n\t' + indent + this.a.str() + '\t' + indent + this.b.str() + indent + '}\n'; | |
282 }; | |
283 | |
284 uniontype.prototype.replaceParams = function(paramtypes, visited) { | |
285 if (visisted === undefined) { | |
286 visited = {}; | |
287 } | |
288 if (this.id in visited) { | |
289 return visited[this.id]; | |
290 } | |
291 var me = visited[this.id] = this.clone(); | |
292 me.a = me.a.replaceParams(paramtypes, visited); | |
293 me.b = me.b.replaceParams(paramtypes, visited); | |
294 return me; | |
295 }; | |
296 | |
297 uniontype.prototype.clone = function() { | |
298 return new uniontype(this.a, this.b); | |
299 }; | |
300 | |
301 | |
302 function mkunion(a, b) | |
303 { | |
304 //if b is a subtype of a, then a | b is equivalent to a | |
305 if (a.satisfiedBy(b)) { | |
306 return a; | |
307 } | |
308 //if a is a subtype of b, then a | b is equivalent to b | |
309 if (b.satisfiedBy(a)) { | |
310 return b; | |
311 } | |
312 return new uniontype(a, b); | |
313 } | |
314 | |
315 function withtparams(type, params) | |
316 { | |
317 this.type = type; | |
318 this.params = params; | |
319 } | |
320 | |
321 withtparams.prototype.satisfiedBy = function(type) { | |
322 return this.type.satisfiedBy(type); | |
323 }; | |
324 | |
325 withtparams.prototype.str = function(indent) { | |
326 return this.type.str(indent) + indent + '<' + this.params.map(function(p) { return p.str(indent); }).join(', ') + '>'; | |
327 }; | |
328 | |
329 withtparams.prototype.replaceParams = function(paramtypes) { | |
330 var replaced = false; | |
331 for (var i in this.params) { | |
332 var newp = this.params[i].replaceParams(paramtypes); | |
333 if (newp != this.params[i]) { | |
334 replaced = true; | |
335 this.params[i] = newp; | |
336 } | |
337 } | |
338 if (replaced) { | |
339 var childptypes = {}; | |
340 for (var i in this.type.typeparams) { | |
341 childptypes[this.type.typeparams[i]] = this.params[i] | |
342 } | |
343 this.type = this.type.replaceParams(childptypes, {}); | |
344 } | |
345 return this; | |
346 }; | |
347 | |
348 function typetest() | |
349 { | |
350 var foo = new objecttype(); | |
351 var msgtype = new lambdatype(); | |
352 msgtype.addParam('fo'); | |
353 msgtype.returntype = foo; | |
354 foo.addMessage('bar', msgtype); | |
355 var baz = new objecttype(); | |
356 var msgtype2 = new lambdatype(); | |
357 msgtype2.addParam('fo'); | |
358 msgtype2.paramType('fo', foo); | |
359 msgtype2.returntype = baz; | |
360 baz.addMessage('bar', msgtype2); | |
361 baz.addMessage('qux', msgtype); | |
362 var shizzle = new objecttype(); | |
363 shizzle.addMessage('bar', msgtype); | |
364 shizzle.addMessage('boo', msgtype); | |
365 return {foo: foo, baz: baz, shizzle: shizzle}; | |
366 } | |
367 | |
368 function paramtypetest() | |
369 { | |
370 var empty = new objecttype(); | |
371 var tlnode = new objecttype(); | |
372 tlnode.typeparams = ['T']; | |
373 var t = new typeparam('T', any); | |
374 var q = new typeparam('Q', any); | |
375 var head = new lambdatype(); | |
376 head.returnType = t; | |
377 tlnode.addMessage('head', head); | |
378 var tail = new lambdatype(); | |
379 var econs = new lambdatype(); | |
380 econs.addParam('val'); | |
381 econs.typeparams = ['Q']; | |
382 econs.paramType('val', q); | |
383 econs.returntype = new withtparams(tlnode, [q]); | |
384 empty.addMessage('cons', econs); | |
385 tail.returntype = new uniontype(new withtparams(tlnode, [t]), empty); | |
386 tlnode.addMessage('tail', tail); | |
387 var cons = new lambdatype(); | |
388 cons.addParam('val'); | |
389 cons.paramType('val', t); | |
390 cons.returntype = new withtparams(tlnode, [t]); | |
391 tlnode.addMessage('cons', cons); | |
392 return {empty: empty, tlnode: tlnode}; | |
393 } | |
394 |