Mercurial > repos > tabletprog
diff types.js @ 126:a2d2d8e09291
Merge
author | Mike Pavone <pavone@retrodev.com> |
---|---|
date | Mon, 05 Aug 2013 23:37:17 -0700 |
parents | 182c311a9fed |
children | 09b65b364927 |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/types.js Mon Aug 05 23:37:17 2013 -0700 @@ -0,0 +1,421 @@ +function anytype() {}; +anytype.prototype.satisfiedBy = function(type) { + return true; +}; +anytype.prototype.str = function(indent) { + if (indent === undefined) { + indent = ''; + } + return indent + 'any\n'; +}; +anytype.prototype.id = 0; +anytype.prototype.callable = true; +anytype.prototype.replaceParams = function() { return this; }; +var any = new anytype(); + +function typeparam(name, base) +{ + this.name = name; + this.base = base; + this.callable = base.callable; +} +typeparam.prototype.replaceParams = function(paramtypes) { + if (!(this.name in paramtypes)) { + return this; + } + if (!this.base.satisfiedBy(paramtypes[this.name])) { + throw new Error('param ' + this.name + ' has base type ' + this.base.str() + ' which is not satisfied by ' + paramtypes[this.name].str()); + } + return paramtypes[this.name]; +}; +typeparam.prototype.satisfiedBy = function(type) { + return this.base.satisfiedBy(type); +}; +typeparam.prototype.str = function(indent) { + return indent + 'param ' + this.name + '\n'; +}; + +var nexttypeid = 1; + +function objecttype() +{ + this.messages = {}; + this.id = nexttypeid++; + this.typeparams = []; + this.satisfies_cache = {}; + this.satisfies_cache[this.id] = true; +} + +objecttype.prototype.callable = false; + +objecttype.prototype.addMessage = function(name, type) +{ + this.messages[name] = type; +}; + +objecttype.prototype.satisfiedBy = function(type) { + if (type.id in this.satisfies_cache) { + return this.satisfies_cache[type.id]; + } + //temporarily set cache entry to true to prevent infinite recursion + this.satisfies_cache[type.id] = true; + var ret = true; + if (type.messages === undefined) { + ret = false; + } + if (ret) { + for (var msgname in this.messages) { + if (!(msgname in type.messages) || !this.messages[msgname].satisfiedBy(type.messages[msgname])) { + ret = false; + break; + } + } + } + this.satisfies_cache[type.id] = ret; + return ret; +}; + +objecttype.prototype.str = function(indent) { + if (indent === undefined) { + indent = ''; + } + if (indent.length > 6) { + return 'max depth reached\n'; + } + var newindent = indent + '\t'; + var childindent = newindent + '\t' + var ret = indent + 'objectype {\n'; + for (var msgname in this.messages) { + ret += newindent + msgname + ':\n' + this.messages[msgname].str(childindent) + } + return ret + indent + '}\n'; +}; + +objecttype.prototype.replaceParams = function(paramtypes, visited) { + if (visited === undefined) { + visited = {}; + } + if (this.id in visited) { + return visited[this.id]; + } + var me = visited[this.id] = this.clone(); + for (var msgname in this.messages) { + me.messages[msgname] = me.messages[msgname].replaceParams(paramtypes, visited); + } + return me; +}; + +objecttype.prototype.clone = function() { + var clone = new objecttype(); + for (var msgname in this.messages) { + clone.messages[msgname] = this.messages[msgname]; + } + clone.typeparams = this.typeparams; + return clone; +}; + +function lambdatype() +{ + this.id = nexttypeid++; + this.messages = {}; + this.params = []; + this.paramlu = {}; + this.typeparams = []; + this.returntype = any; + this.satisfies_cache = {}; + this.satisfies_cache[this.id] = true; +} + +lambdatype.prototype.callable = true; + +lambdatype.prototype.addParam = function(name) { + this.paramlu[name] = this.params.length; + this.params.push(any); +}; + +lambdatype.prototype.paramType = function(name, type) { + this.params[this.paramlu[name]] = type; +}; + +lambdatype.prototype.addMessage = function(name, type) +{ + this.messages[name] = type; +}; + +lambdatype.prototype.satisfiedBy = function(type) { + if (type.id in this.satisfies_cache) { + return this.satisfies_cache[type.id]; + } + //temporarily set cache entry to true to prevent infinite recursion + this.satisfies_cache[type.id] = true; + var ret = true; + if (!(type.callable) || this.params.length != type.params.length) { + ret = false; + } + if (ret) { + for (var i in this.params) { + if (i >= type.params.length || !type.params[i].satisfiedBy(this.params[i])) { + ret = false; + break; + } + } + } + if (ret) { + for (var msgname in this.messages) { + if (!(msgname in type.messages) || !this.messages[msgname].satisfiedBy(type.messages[msgname])) { + ret = false; + break; + } + } + } + ret = ret && this.returntype.satisfiedBy(type.returntype); + this.satisfies_cache[type.id] = ret; + return ret; +} + +lambdatype.prototype.str = function(indent) { + if (indent === undefined) { + indent = ''; + } + if (indent.length > 6) { + return 'max depth reached\n'; + } + var newindent = indent + '\t'; + var childindent = newindent + '\t' + var ret = indent + 'lambdatype {\n' + newindent + 'params: {\n'; + for (var i = 0; i < this.params.length; i++) { + ret += childindent + i + ':\n' + this.params[i].str(childindent + '\t'); + } + ret += newindent + '}\n' + newindent + 'returntype:\n' + this.returntype.str(childindent); + + for (var msgname in this.messages) { + ret += newindent + msgname + ':\n' + this.messages[msgname].str(childindent) + } + return ret + indent + '}\n'; +}; + +lambdatype.prototype.replaceParams = function(paramtypes, visited) { + if (visited === undefined) { + visited = {}; + } + if (this.id in visited) { + return visited[this.id]; + } + var me = visited[this.id] = this.clone(); + for (var msgname in me.messages) { + me.messages[msgname] = me.messages[msgname].replaceParams(paramtypes, visited); + } + for (var i in me.params) { + me.params[i] = me.params[i].replaceParams(paramtypes, visited); + } + me.returntype = me.returntype.replaceParams(paramtypes, visited); + return me; +}; + +lambdatype.prototype.clone = function() { + var clone = new lambdatype(); + for (var msgname in this.messages) { + clone.messages[msgname] = this.messages[msgname]; + } + clone.paramlu = this.paramlu; + clone.params = this.params.slice(0, this.params.length); + clone.returntype = this.returntype; + clone.typeparams = this.typeparams; + return clone; +}; + +function uniontype(a, b) +{ + this.a = a; + this.b = b; + this.id = nexttypeid++; + this.satisfies_cache = null; +} + +uniontype.prototype = { + lazyinit: function() { + if (this.satisfies_cache == null) { + this.satisfies_cache = {}; + this.satisfies_cache[this.id] = true; + this._messages = {}; + if (this.a.messages !== undefined && this.b.messages !== undefined) { + for (var msgname in this.a.messages) { + if (msgname in this.b.messages) { + this._messages[msgname] = mkunion(this.a.messages[msgname], this.b.messages[msgname]); + } + } + } + this._callable = false; + if (this.a.callable && this.b.callable && this.a.params.length == this.b.params.length) { + this._callable = true; + this._params = []; + for (var i = 0; i < this.a.params.length; i++) { + this._params.push(mkunion(this.a.params[i], this.b.params[i])); + } + this._returntype = mkunion(this.a.returntype, this.b.returntype); + } + } + }, + satisfiedBy: function(type) + { + this.lazyinit(); + if (type.id in this.satisfies_cache) { + return this.satisfies_cache[type.id]; + } + this.satisfies_cache[type.id] = true; + var ret = this.a.satisfiedBy(type) || this.b.satisfiedBy(type); + this.satisfies_cache[type.id] = ret; + return ret; + }, + str: function(indent) + { + if (indent === undefined) { + indent = ''; + } + if (indent.length > 6) { + return 'max depth reached\n'; + } + return indent + 'Union {\n\t' + indent + this.a.str(indent+'\t') + '\t' + indent + this.b.str(indent+'\t') + indent + '}\n'; + }, + replaceParams: function(paramtypes, visited) { + if (visited === undefined) { + visited = {}; + } + if (this.id in visited) { + return visited[this.id]; + } + var me = visited[this.id] = this.clone(); + me.a = me.a.replaceParams(paramtypes, visited); + me.b = me.b.replaceParams(paramtypes, visited); + return me; + }, + clone: function() { + return new uniontype(this.a, this.b); + }, + get messages() { + this.lazyinit(); + return this._messages; + }, + get params() { + this.lazyinit(); + return this._params; + }, + get returntype() { + this.lazyinit(); + return this._returntype; + }, + get callable() { + this.lazyinit(); + return this._callable; + } +}; + + +function mkunion(a, b) +{ + //if b is a subtype of a, then a | b is equivalent to a + if (a.satisfiedBy(b)) { + return a; + } + //if a is a subtype of b, then a | b is equivalent to b + if (b.satisfiedBy(a)) { + return b; + } + return new uniontype(a, b); +} + +function withtparams(type, params) +{ + this.type = type; + this.params = params; + this.replaced = false; +} + +withtparams.prototype = { + satisfiedBy: function(type) { + this.lazyinit(); + return this.type.satisfiedBy(type); + }, + str: function(indent) { + if (indent === undefined) { + indent = ''; + } + if (indent.length > 6) { + return 'max depth reached\n'; + } + return this.type.str(indent) + indent + '<' + this.params.map(function(p) { return p.str(indent); }).join(', ') + '>'; + }, + replaceParams: function(paramtypes) { + var replaced = false; + for (var i in this.params) { + var newp = this.params[i].replaceParams(paramtypes); + if (newp != this.params[i]) { + replaced = true; + this.params[i] = newp; + } + } + return this; + }, + lazyinit: function() { + if (!this.replaced) { + var childptypes = {}; + for (var i in this.type.typeparams) { + childptypes[this.type.typeparams[i]] = this.params[i] + } + this.type = this.type.replaceParams(childptypes, {}); + this.replaced = true; + } + }, + get messages() { + this.lazyinit(); + return this.type.messages; + } +}; + +function typetest() +{ + var foo = new objecttype(); + var msgtype = new lambdatype(); + msgtype.addParam('fo'); + msgtype.returntype = foo; + foo.addMessage('bar', msgtype); + var baz = new objecttype(); + var msgtype2 = new lambdatype(); + msgtype2.addParam('fo'); + msgtype2.paramType('fo', foo); + msgtype2.returntype = baz; + baz.addMessage('bar', msgtype2); + baz.addMessage('qux', msgtype); + var shizzle = new objecttype(); + shizzle.addMessage('bar', msgtype); + shizzle.addMessage('boo', msgtype); + return {foo: foo, baz: baz, shizzle: shizzle}; +} + +function paramtypetest() +{ + var empty = new objecttype(); + var tlnode = new objecttype(); + tlnode.typeparams = ['T']; + var t = new typeparam('T', any); + var q = new typeparam('Q', any); + var head = new lambdatype(); + head.returntype = t; + tlnode.addMessage('head', head); + var tail = new lambdatype(); + var econs = new lambdatype(); + econs.addParam('val'); + econs.typeparams = ['Q']; + econs.paramType('val', q); + econs.returntype = new withtparams(tlnode, [q]); + empty.addMessage('cons', econs); + tail.returntype = new uniontype(new withtparams(tlnode, [t]), empty); + tlnode.addMessage('tail', tail); + var cons = new lambdatype(); + cons.addParam('val'); + cons.paramType('val', t); + cons.returntype = new withtparams(tlnode, [t]); + tlnode.addMessage('cons', cons); + return {empty: empty, tlnode: tlnode}; +} +