Mercurial > repos > tabletprog

comparison types.js @ 99:b58b19c455ec

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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