Commits

Brian McKenna committed 904f611

Add current state of constraint based inference

This commit should perform inference on row-polymorphic objects. May
need instantiation of row-variables for types with object input.

Need to remove return/bind nodes as they are now part of `do`. Need to
remove case node as that should now be part of `match`.

Need to remove bogosort from the constraint solver. Should be possible
to derive a proper sorting from "solvable" checker.

Type schems should now work properly. Giving let-bindings a proper
quantified, polymorphic type.

Still need to complete:

* Typeclasses (tricky)
* Nested data types (probably not so tricky)

Comments (0)

Files changed (25)

 docs/guide/_build/
 src/parser.js
 src/typeparser.js
+test/fixtures/**/*.js
+test/fixtures/**/*.js.map
 examples/*.js
 examples/*.js.map
 lib/*.js
 module.exports = function(grunt) {
     grunt.initConfig({
         lint: {
-            src: [
-                './src/*.js'
-            ]
+            src: ['./src/*.js']
         },
         jison: {
             './lib/typeparser.js': './src/typegrammar.js',
             'roy.js': 'rigger-roy.js'
         },
         jasmine: {
-            src: './test'
+            specs: {
+                src: './test',
+                cache: ['./test', './src']
+            }
         },
         min: {
             'roy-min.js': 'roy.js'
         });
     });
 
-    // Watching the task doesn't work. Sadly jasmine-node
-    // executeSpecsInFolder is not idempotent
     grunt.registerMultiTask('jasmine', 'Testing by jasmine.', function() {
         var path = require('path'),
             specDir = this.file.src,
-            badCache = grunt.file.expand(specDir).concat([
-                path.dirname(require.resolve("jasmine-node")),
-            ]),
+            badCache = grunt.utils._.map(this.data.cache || [], function(p) { return path.resolve(p); }),
             jasmine,
             done = this.async(),
             key;
         // Not nice (necessary for jasmine-node's asyncSpecWait, etc)
         for(key in jasmine) if(jasmine[key] instanceof Function) global[key] = jasmine[key];
 
-        function onComplete(runner) {
-            if (runner.results().failedCount > 0) {
-                grunt.log.error();
-                return;
-            }
-            done(true);
-        };
-
         jasmine.executeSpecsInFolder({
-            'specFolders': [specDir],
-            'onComplete': onComplete,
-            'isVerbose': false,
-            'showColors': true
+            specFolders: [specDir],
+            regExpSpec: /Comp.*Spec\.js/,
+            onComplete: function(runner) {
+                if (runner.results().failedCount > 0) {
+                    grunt.log.error();
+                }
+                done(true);
+            },
+            isVerbose: true,
+            showColors: true
         });
     });
 
     "roy": "./roy"
   },
   "scripts": {
-    "install": "node src/grammar.js && node src/typegrammar.js"
+    "install": "node src/grammar.js && node src/typegrammar.js",
+    "test": "$(npm bin)/grunt jasmine"
   },
   "homepage": "http://roy.brianmckenna.org/",
   "dependencies": {
     "jison": "0.2.7",
     "source-map": "0.1.8",
-    "underscore": "1.3.3",
+    "underscore": "1.4.3",
     "unicode-categories": "0.9.1"
   },
   "devDependencies": {
     "grunt": "0.3.15",
-    "rigger": "0.3.19",
+    "rigger": "0.5.2",
     "jasmine-node": "1.5.0"
   }
 }
                 }).join(", ");
             };
             pushIndent();
-            var split = splitComments(n.body);
+            var split = splitComments(n.value);
             var compiledWhereDecls = _.map(n.whereDecls, compileNode);
             var compiledNodeBody = _.map(split.body, compileNode);
             var init = [];
                 init.push(compiledNodeBody.slice(0, compiledNodeBody.length - 1).join(';\n' + getIndent()) + ';');
             }
             var lastString = compiledNodeBody[compiledNodeBody.length - 1];
-            var varEquals = "";
-            if(n.name) {
-                varEquals = "var " + n.name + " = ";
-            }
 
             var compiledEndComments = "";
             if(split.comments.length) {
             var functionString = "function(" + getArgs(n.args) + ") {\n" +
                 getIndent() + joinIndent(init) + "return " + lastString +
                 ";\n" + compiledEndComments + popIndent() + "}";
-            if(varEquals) {
-                return varEquals + functionString;
-            } else {
-                return '(' + functionString + ')';
-            }
+            return '(' + functionString + ')';
         },
         visitIfThenElse: function() {
             var compiledCondition = compileNode(n.condition);
         },
         // Let binding to JavaScript variable.
         visitLet: function() {
-            return "var " + n.name + " = " + compileNode(n.value);
+            pushIndent();
+            var last = compileNode(_.last(n.value));
+            popIndent();
+
+            if(n.value.length == 1) {
+                return "var " + n.name + " = " + last;
+            }
+
+            pushIndent();
+            var init = _.map(_.initial(n.value), compileNode);
+            popIndent();
+
+            return "var " + n.name + " = (function() {\n" + getIndent(1) + init.join(";\n" + getIndent(1)) + ";\n" + getIndent(1) + "return " + last + ";\n" + getIndent() + "})()";
         },
         visitInstance: function() {
             return "var " + n.name + " = " + compileNode(n.object);
             };
             return serialize(n.value);
         },
-        visitReturn: function() {
-            return "__monad__.return(" + compileNode(n.value) + ");";
-        },
-        visitBind: function() {
-            var init = n.rest.slice(0, n.rest.length - 1);
-            var last = n.rest[n.rest.length - 1];
-            return "__monad__.bind(" + compileNode(n.value) +
-                ", function(" + n.name + ") {\n" + pushIndent() +
-                _.map(init, compileNode).join(";\n" + getIndent()) + "\n" +
-                getIndent() + "return " + compileNode(last) + "\n" +
-                popIndent() + "});";
-        },
         visitDo: function() {
-            var compiledInit = [];
+            function compileReturnOrValue(node) {
+                if(node.isReturn)
+                    return "__monad__['return'](" + compileNode(node.value) + ')';
+
+                return compileNode(node);
+            }
+
+            return '(function(__monad__) { ' + _.reduceRight(_.initial(n.body), function(accum, node) {
+                if(!isStatement(node)) {
+                    return 'return __monad__.bind(' +
+                        compileReturnOrValue(node.value) +
+                        ', function(' + (node.isBind ? node.name : '') + ') { ' + accum + '; })';
+                }
+                return compileReturnOrValue(node) + '; ' + accum;
+            }, 'return ' + compileReturnOrValue(_.last(n.body))) + '})(' + compileNode(n.value) + ')';
+
+            /*var compiledInit = [];
             var firstBind;
             var lastBind;
             var lastBindIndex = 0;
             if(lastBind) {
                 lastBind.rest = n.body.slice(lastBindIndex + 1);
             }
-            return "(function(){\n" + pushIndent() + "var __monad__ = " +
-                compileNode(n.value) + ";\n" + getIndent() +
+            return "(function(__monad__){\n" + pushIndent() +
                 (!firstBind ? 'return ' : '') + compiledInit.join(';\n' + getIndent()) + '\n' + getIndent() +
                 (firstBind ? 'return ' + compileNode(firstBind) : '') + "\n" +
-                popIndent() + "})()";
+                popIndent() + "})(" + compileNode(n.value) + ")";*/
         },
         visitTag: function() {
             var args = _.map(n.vars, function(v, i) {
                 var maxTagPath = _.max(tagPaths, function(t) {
                     return t.path.length;
                 });
-                var maxPath = maxTagPath ? maxTagPath.path : [];
+                var maxPath = maxTagPath != -Infinity ? maxTagPath.path : [];
 
                 return {
                     path: maxPath,
 };
 exports.compileNodeWithEnv = compileNodeWithEnv;
 
-var withoutTopLevelStatements = function(ast) {
-    return _.reject(ast, function(n) {
-        return n.accept({
-            visitComment: function() {
-                return true;
-            },
-            visitFunction: function() {
-                return n.name;
-            },
-            visitLet: function() {
-                return true;
-            }
-        });
+function isStatement(node) {
+    return !!node.accept({
+        visitComment: function() {
+            return true;
+        },
+        visitData: function() {
+            return true;
+        },
+        visitLet: function() {
+            return true;
+        }
     });
-};
+}
 
 var compile = function(source, env, aliases, opts) {
     if(!env) env = {};
 
     // Typecheck the AST. Any type errors will throw an exception.
     var resultType;
-    if(withoutTopLevelStatements(ast).length) {
+    if(_.reject(ast, isStatement).length) {
         resultType = typecheck(ast);
     }
 
 
     // Include the standard library
     var fs = require('fs');
-    var prelude = fs.readFileSync(path.dirname(__dirname) + '/lib/prelude.roy', 'utf8');
-    vm.runInNewContext(compile(prelude, env, {}, {nodejs: true}).output, sandbox, 'eval');
+    //var prelude = fs.readFileSync(path.dirname(__dirname) + '/lib/prelude.roy', 'utf8');
+    //vm.runInNewContext(compile(prelude, env, {}, {nodejs: true}).output, sandbox, 'eval');
     repl.setPrompt('roy> ');
     repl.on('close', function() {
         stdin.destroy();

src/freeVariables.js

             return node.value.accept(visitor);
         },
         visitFunction: function(node) {
-            var bodyFreeVariables = getFreeVariablesOfBlock(node.body);
+            var bodyFreeVariables = getFreeVariablesOfBlock(node.value);
 
             _.each(node.whereDecls, function(whereDecl) {
                        _.extend(bodyFreeVariables, whereDecl.accept(visitor));
                    });
 
-            delete bodyFreeVariables[node.name];
-
             _.each(node.args, function(arg) {
                        delete bodyFreeVariables[arg.name];
                    });
 
             return variables;
         },
-        visitFunction: returnName,
         visitInstance: returnName,
         visitBind: returnName,
         visitTag: returnName,
 
         // all others don't bind variables in current environment;
         // they bind no variables or bind in their own environment.
+        visitFunction: returnEmpty,
         visitExpression: returnEmpty,
         visitType: returnEmpty,
         visitTypeClass: returnEmpty,
     return node.accept(visitor);
 }
 
-exports.getFreeVariables = getFreeVariables;
+exports.getFreeVariables = getFreeVariables;
         ],
         "doLine": [
             ["line", "$$ = $1;"],
-            ["IDENTIFIER LEFTARROW expression", n("$$ = new yy.Bind($1, $3);")],
+            ["IDENTIFIER LEFTARROW doLine", n("$$ = new yy.Bind($1, $3);")],
             ["RETURN expression", n("$$ = new yy.Return($2);")]
         ],
         "doBlock": [
         ],
         "expression": [
             ["innerExpression", "$$ = $1;"],
-            ["LAMBDA paramList optType RIGHTARROW expression", n("$$ = new yy.Function(undefined, $2, [$5], $3);")],
-            ["LAMBDA paramList optType RIGHTARROW block", n("$$ = new yy.Function(undefined, $2, $5, $3);")],
+            ["LAMBDA paramList RIGHTARROW expression", n("$$ = new yy.Function($2, [$4]);")],
+            ["LAMBDA paramList RIGHTARROW block", n("$$ = new yy.Function($2, $4);")],
             ["MATCH innerExpression INDENT caseList outdentOrEof", n("$$ = new yy.Match($2, $4);")],
             ["DO innerExpression doBlock", n("$$ = new yy.Do($2, $3);")],
             ["ifThenElse", "$$ = $1;"]
             ["MACRO IDENTIFIER = block", n("$$ = new yy.Macro($2, $4);")]
         ],
         "function": [
-            ["IDENTIFIER paramList optType = block optWhere", n("$$ = new yy.Function($1, $2, $5, $3, $6);")],
-            ["IDENTIFIER paramList optType = expression", n("$$ = new yy.Function($1, $2, [$5], $3, []);")]
+            ["IDENTIFIER paramList optType = block optWhere", n("$$ = new yy.Let($1, [new yy.Function($2, $5, $6)], $3);")],
+            ["IDENTIFIER paramList optType = expression", n("$$ = new yy.Let($1, [new yy.Function($2, [$5])], $3);")]
         ],
         "binding": [
-            ["IDENTIFIER optType = expression", n("$$ = new yy.Let($1, $4, $2);")],
-            ["IDENTIFIER optType = INDENT expression outdentOrEof", n("$$ = new yy.Let($1, $5, $2);")]
+            ["IDENTIFIER optType = expression", n("$$ = new yy.Let($1, [$4], $2);")],
+            ["IDENTIFIER optType = block", n("$$ = new yy.Let($1, $4, $2);")]
         ],
         "paramList": [
             ["( )", "$$ = [];"],
         ],
         "whereDecl": [
             ["dataDecl", "$$ = $1;"],
-            ["IDENTIFIER paramList optType = block optWhere", n("$$ = new yy.Function($1, $2, $5, $3, $6);")],
-            ["IDENTIFIER paramList optType = expression", n("$$ = new yy.Function($1, $2, [$5], $3, []);")]
+            ["IDENTIFIER paramList optType = block optWhere", n("$$ = new yy.Let($1, [new yy.Function($2, $5, $6)], $3);")],
+            ["IDENTIFIER paramList optType = expression", n("$$ = new yy.Let($1, [new yy.Function($2, [$5])], $3);")]
         ],
 
         "call": [
             }
         };
     },
-    Function: function(name, args, body, type, whereDecls) {
-        this.name = name;
+    Function: function(args, value, whereDecls) {
         this.args = args;
-        this.body = body;
+        this.value = value;
 
         // Optional
-        this.type = type;
         this.whereDecls = whereDecls || [];
 
         this.accept = function(a) {
             }
         };
     },
+    // TODO REMOVE
     Return: function(value) {
         this.value = value;
 
+        this.isReturn = true;
+
         this.accept = function(a) {
             if(a.visitReturn) {
                 return a.visitReturn(this);
             }
         };
     },
+    // TODO REMOVE
     Bind: function(name, value) {
         this.name = name;
         this.value = value;
 
+        this.isBind = true;
+
         // Set in compile stage
         this.rest = [];
 
             }
         };
     },
+    // TODO REMOVE
     Case: function(pattern, value) {
         this.pattern = pattern;
         this.value = value;

src/typeinference.js

     this.b = b;
     this.node = node;
 
-    this.solveOrder = 1;
-
     this.fold = function(f, _a, _b) {
         return f(this);
     };
     this.a = a;
     this.b = b;
     this.monomorphic = monomorphic;
-
-    this.solveOrder = 2;
+    this.node = node;
 
     this.fold = function(_a, f, _b) {
         return f(this);
     this.scheme = scheme;
     this.node = node;
 
-    this.solveOrder = 3;
-
     this.fold = function(_a, _b, f) {
         return f(this);
     };
 // ### Inference state
 // Immutable state monoid containing both the current constraints and
 // assumptions
-function InferenceState(constraints, assumptions) {
+function InferenceState(constraints, assumptions, instances) {
     this.constraints = constraints || [];
     this.assumptions = assumptions || {};
+    this.instances = instances || {};
 }
 InferenceState.empty = new InferenceState();
 InferenceState.concat = function(states) {
 };
 InferenceState.prototype.append = function(state) {
     var constraints = this.constraints.concat(state.constraints),
-        assumptions = _.extend(_.clone(this.assumptions), state.assumptions);
-    return new InferenceState(constraints, assumptions);
+        assumptions = mergeAssumptions(this.assumptions, state.assumptions),
+        instances = mergeInstances(this.instances, state.instances);
+
+    return new InferenceState(
+        constraints,
+        assumptions,
+        instances
+    );
 };
 InferenceState.prototype.withConstraints = function(constraints) {
-    return new InferenceState(this.constraints.concat(constraints), this.assumptions);
+    return new InferenceState(
+        this.constraints.concat(constraints),
+        this.assumptions,
+        this.instances
+    );
 };
 InferenceState.prototype.withAssumptions = function(assumptions) {
-    return new InferenceState(this.constraints, _.extend(_.clone(this.assumptions), assumptions));
+    return new InferenceState(
+        this.constraints,
+        mergeAssumptions(this.assumptions, assumptions),
+        this.instances
+    );
+};
+InferenceState.prototype.withInstances = function(instances) {
+    return new InferenceState(
+        this.constraints,
+        this.assumptions,
+        mergeInstances(this.instances, instances)
+    );
 };
 
+function mergeAssumptions(a1, a2) {
+    var merged = _.extend(_.clone(a1), a2);
+    _.each(_.intersection(_.keys(a1), _.keys(a2)), function(key) {
+        merged[key] = a1[key].concat(a2[key]);
+    });
+    return merged;
+}
+
+function mergeInstances(i1, i2) {
+    var merged = _.extend(_.clone(i1), i2);
+    _.each(_.intersection(_.keys(i1), _.keys(i2)), function(key) {
+        merged[key] = _.extend(merged[key], i2[key]);
+    });
+    return merged;
+}
+
 // ## Inference type
 function StateType(state, type) {
     this.state = state;
     });
 }
 
-function generateAccessConstraints(recurseIfMoreNodes, monomorphic) {
-    return function(node) {
-        var value = generate([node.value], monomorphic),
-            type = new t.Variable(),
-            objectTypes = {};
-
-        objectTypes[node.property] = type;
-
-        return recurseIfMoreNodes(new StateType(
-            value.state
-                .withConstraints([
-                    new EqualityConstraint(
-                        value.type,
-                        new t.ObjectType(objectTypes),
-                        node
-                    )
-                ]),
-            type
-        ));
-    };
-}
-
 // ## InferenceState generation
 // Takes a non-empty array of AST nodes and generates a new
 // InferenceType.
             var type = new t.Variable(),
                 assumptions = {};
 
-            assumptions[node.value] = type;
+            assumptions[node.value] = [type];
 
             return recurseIfMoreNodes(new StateType(
                 InferenceState
             var types = _.map(_.range(node.args.length), function() {
                     return new t.Variable();
                 }),
-                bodyStateType = generate(node.body, monomorphic.concat(types)),
+                valueStateType = generate(node.value, monomorphic.concat(types)),
                 argNames = _.map(node.args, function(a) {
                     return a.name;
                 }),
                 assumptionsNotInArgs = {},
                 constraintsFromAssumptions = [];
 
-            _.each(bodyStateType.state.assumptions, function(v, k) {
+            _.each(valueStateType.state.assumptions, function(v, k) {
                 var index = argNames.indexOf(k);
                 if(index != -1) {
-                    constraintsFromAssumptions.push(
-                        new EqualityConstraint(
-                            v,
-                            types[index],
-                            node
-                        )
-                    );
-                } else {
+                    _.each(v, function(assumption) {
+                        constraintsFromAssumptions.push(
+                            new EqualityConstraint(
+                                assumption,
+                                types[index],
+                                node
+                            )
+                        );
+                    });
+                } else if(k != node.name) {
                     assumptionsNotInArgs[k] = v;
                 }
             });
                 InferenceState
                     .empty
                     .withAssumptions(assumptionsNotInArgs)
-                    .withConstraints(bodyStateType.state.constraints)
+                    .withConstraints(valueStateType.state.constraints)
                     .withConstraints(constraintsFromAssumptions),
-                new t.FunctionType(types.concat(bodyStateType.type))
+                new t.FunctionType(types.concat(valueStateType.type))
             ));
         },
         visitLet: function() {
-            var value = generate([node.value], monomorphic),
+            var value = generate(node.value, monomorphic),
                 body,
                 assumptionsWithoutLet,
-                constraintsFromLet;
+                constraintsFromLet,
+                result;
 
-            // let bindings can't be treated as an expression
             if(nodesWithoutComments.length == 1) {
-                throw new Error("let binding without any child expressions");
+                return new StateType(
+                    value.state,
+                    new t.Variable()
+                );
             }
 
             body = generate(nodesWithoutComments.slice(1), monomorphic);
-            assumptionsWithoutLet = _.pick(
+            assumptionsWithoutLet = _.omit(
                 body.state.assumptions,
-                _.without(
-                    _.keys(body.state.assumptions),
-                    node.name
-                )
+                node.name
             );
             constraintsFromLet =
-                _.has(body.state.assumptions, node.name) ? [
-                    new ImplicitConstraint(
+                _.map(body.state.assumptions[node.name] || [], function(assumption) {
+                    return new ImplicitConstraint(
+                        assumption,
                         value.type,
-                        body.state.assumptions[node.name],
                         monomorphic,
                         node
-                    )
-                ] : [];
+                    );
+                });
 
             return new StateType(
                 value.state
                 assumptionsWithoutTags,
                 constraintsFromTags;
 
-            // data definitions can't be treated as an expression
             if(nodesWithoutComments.length == 1) {
-                throw new Error("data definition without any child expressions");
+                return new StateType(
+                    InferenceState
+                        .empty,
+                    new t.Variable()
+                );
             }
 
             body = generate(nodesWithoutComments.slice(1), monomorphic);
                     _.pluck(node.tags, 'name')
                 )
             );
+
             constraintsFromTags = _.reduce(node.tags, function(accum, tag) {
-                return [].concat(accum, _.has(body.state.assumptions, node.name) ? [
-                    new ImplicitConstraint(
-                        (function() { throw new Error("TAG TYPE HERE"); })(),
-                        body.type,
-                        monomorphic,
-                        tag
-                    )
-                ] : []);
+                var vars = {},
+                    args = {},
+                    tagType;
+
+                _.each(node.args, function(v) {
+                    vars[v.name] = new t.Variable();
+                });
+
+                _.each(tag.vars, function(v) {
+                    args[v.value] = _.has(vars, v.value) ? vars[v.value] : (function() {
+                        throw new Error("TODO: Data declaration using another declaration");
+                    })();
+                });
+
+                tagType = new t.TagType(node.name, _.map(node.args, function(a) {
+                    return _.has(args, a.name) ? args[a.name] : new t.Variable();
+                }));
+
+                return accum.concat(_.map(
+                    body.state.assumptions[tag.name] || [],
+                    function(assumption) {
+                        return new ImplicitConstraint(
+                            assumption,
+                            new t.FunctionType(_.values(args).concat(tagType)),
+                            monomorphic,
+                            node
+                        );
+                    }
+                ));
             }, []);
 
             return new StateType(
-                InferenceState.empty
+                InferenceState
+                    .empty
                     .withAssumptions(assumptionsWithoutTags)
                     .withConstraints(body.state.constraints)
                     .withConstraints(constraintsFromTags),
         },
         visitMatch: function() {
             var valueStateType = generate([node.value], monomorphic),
-                casesStateType = generate(node.cases, monomorphic);
+                casesType = new t.Variable();
 
-            return recurseIfMoreNodes(new StateType(
-                valueStateType.state
-                    .append(casesStateType.state),
-                casesStateType.type
-            ));
-        },
-        visitCase: function() {
-            var valueStateType = generate([node.value], monomorphic),
-                assumptionsWithoutVars,
-                constraintsFromVars;
+            casesState = _.reduce(node.cases, function(accum, c) {
+                var patternAssumptions = {},
+                    patternType = {},
+                    varTypes,
+                    caseValueStateType,
+                    assumptionsWithoutVars,
+                    caseConstraints;
 
-            assumptionsWithoutVars = _.pick(
-                valueStateType.state.assumptions,
-                _.difference(
-                    _.keys(valueStateType.state.assumptions),
-                    node.pattern.vars
-                )
-            );
-            constraintsFromVars = _.reduce(node.pattern.vars, function(accum, varName) {
-                return [].concat(accum, _.has(valueStateType.state.assumptions, varName) ? [
-                    new ImplicitConstraint(
-                        (function() { throw new Error("VAR TYPE HERE"); })(),
-                        valueStateType.type,
-                        monomorphic,
-                        tag
+                varTypes = _.map(c.pattern.vars, function() {
+                    return new t.Variable();
+                });
+
+                patternType = new t.FunctionType(varTypes.concat([valueStateType.type]));
+
+                patternAssumptions[c.pattern.tag.value] = [patternType];
+
+                caseValueStateType = generate([c.value], monomorphic.concat(varTypes));
+
+                assumptionsWithoutVars = _.pick(
+                    caseValueStateType.state.assumptions,
+                    _.difference(
+                        _.keys(caseValueStateType.state.assumptions),
+                        _.pluck(c.pattern.vars, 'value')
                     )
-                ] : []);
-            }, []);
+                );
+
+                caseConstraints = _.reduce(c.pattern.vars, function(accum, varName) {
+                    return {
+                        index: accum.index + 1,
+                        constraints: accum.constraints.concat(_.map(
+                            caseValueStateType.state.assumptions[varName.value] || [],
+                            function(assumption) {
+                                return new EqualityConstraint(
+                                    assumption,
+                                    patternType.types[accum.index],
+                                    node
+                                );
+                            }
+                        ))
+                    };
+                }, {
+                    index: 0,
+                    constraints: []
+                }).constraints;
+
+                return accum
+                    .withAssumptions(assumptionsWithoutVars)
+                    .withAssumptions(patternAssumptions)
+                    .withConstraints(caseValueStateType.state.constraints)
+                    .withConstraints(caseConstraints)
+                    .withConstraints([
+                        new EqualityConstraint(
+                            caseValueStateType.type,
+                            casesType,
+                            node
+                        )
+                    ]);
+            }, InferenceState.empty);
 
             return recurseIfMoreNodes(new StateType(
                 valueStateType.state
-                    .withAssumptions(assumptionsWithoutVars)
-                    .withConstraints(constraintsFromVars),
-                valueStateType.type
+                    .append(casesState),
+                casesType
             ));
         },
         visitDo: function() {
-            var instanceStateType = generate([node.value], monomorphic),
-                body = generate(node.body, monomorphic);
+            // Can be simplified; desugar the AST before typechecking
+            var instanceState = generate([node.value], monomorphic).state,
+                last = _.last(node.body),
+                init = _.initial(node.body),
+                lastStateType;
 
-            console.log(body);
-        },
-        visitBind: function() {
-            var restStateType = generate(nodesWithoutComments.slice(1));
-            console.log(restStateType);
-            console.log(node.name);
-        },
-        visitReturn: function() {
-            var valueStateType = generate([node.value], monomorphic);
+            function returnGenerate(n) {
+                // Return
+                var returnInput = new t.Variable(),
+                    returnOutput = new t.Variable(),
+                    instanceExpectedType = new t.RowObjectType(new t.Variable(), {
+                        'return': new t.FunctionType([returnInput, returnOutput])
+                    }),
+                    instanceStateType = generate([node.value], monomorphic),
+                    stateType = generate([n.value], monomorphic);
+
+                return new StateType(
+                    stateType.state
+                        .append(instanceStateType.state)
+                        .withConstraints([
+                            new EqualityConstraint(
+                                returnInput,
+                                stateType.type,
+                                node
+                            ),
+                            new EqualityConstraint(
+                                instanceExpectedType,
+                                instanceStateType.type,
+                                node
+                            )
+                        ]),
+                    returnOutput
+                );
+            }
+
+            function returnNodeGenerate(n) {
+                if(n.isReturn)
+                    return returnGenerate(n);
+
+                // Normal statements
+                return generate([n], monomorphic);
+            }
+
+            function bindGenerate(accum, name, value) {
+                // Bind
+                var valueStateType = returnNodeGenerate(value),
+                    bindInput = new t.Variable(),
+                    bindFunctionInput = new t.Variable(),
+                    bindOutput = new t.Variable(),
+                    instanceExpectedType = new t.RowObjectType(new t.Variable(), {
+                        'bind': new t.FunctionType([
+                            bindInput,
+                            new t.FunctionType([
+                                bindFunctionInput,
+                                bindOutput
+                            ]),
+                            bindOutput
+                        ])
+                    }),
+                    instanceStateType = generate([node.value], monomorphic),
+                    constraintsFromAssumptions = _.flatten(_.map(
+                        accum.state.assumptions[name] || [],
+                        function(assumption) {
+                            return [
+                                new EqualityConstraint(
+                                    assumption,
+                                    bindFunctionInput,
+                                    node
+                                ),
+                                new EqualityConstraint(
+                                    valueStateType.type,
+                                    bindInput,
+                                    node
+                                )
+                            ];
+                        }
+                    )),
+                    assumptionsWithoutBind = _.omit(
+                        accum.state.assumptions,
+                        name
+                    );
+
+                return new StateType(
+                    valueStateType.state
+                        .append(instanceStateType.state)
+                        .withConstraints(accum.state.constraints)
+                        .withAssumptions(assumptionsWithoutBind)
+                        .withConstraints(constraintsFromAssumptions)
+                        .withConstraints([
+                            new EqualityConstraint(
+                                valueStateType.type,
+                                bindInput,
+                                node
+                            ),
+                            new EqualityConstraint(
+                                accum.type,
+                                bindOutput,
+                                node
+                            ),
+                            new EqualityConstraint(
+                                instanceExpectedType,
+                                instanceStateType.type,
+                                node
+                            )
+                        ]),
+                    accum.type
+                );
+            }
+
+            lastStateType = returnNodeGenerate(last);
+
+            return recurseIfMoreNodes(_.reduceRight(init, function(accum, line) {
+                var stateType;
+                if(line.isBind)
+                    return bindGenerate(accum, line.name, line.value);
+
+                stateType = returnNodeGenerate(line);
+                return new StateType(
+                    accum.state
+                        .append(stateType.state),
+                    accum.type
+                );
+            }, new StateType(
+                instanceState
+                    .append(lastStateType.state),
+                lastStateType.type
+            )));
         },
 
         visitIfThenElse: function() {
                 ifTrue.type
             ));
         },
-        visitPropertyAccess: generateAccessConstraints(recurseIfMoreNodes, monomorphic),
-        visitAccess: generateAccessConstraints(recurseIfMoreNodes, monomorphic),
+        visitPropertyAccess: function() {
+            var value = generate([node.value], monomorphic),
+                type = new t.Variable(),
+                objectTypes = {};
+
+            objectTypes[node.property] = type;
+
+            return recurseIfMoreNodes(new StateType(
+                value.state
+                    .withConstraints([
+                        new EqualityConstraint(
+                            value.type,
+                            new t.RowObjectType(
+                                new t.Variable(),
+                                objectTypes
+                            ),
+                            node
+                        )
+                    ]),
+                type
+            ));
+        },
+        visitAccess: function() {
+            var value = generate([node.value], monomorphic),
+                property = generate([node.property], monomorphic),
+                type = new t.Variable();
+
+            return recurseIfMoreNodes(new StateType(
+                value.state
+                    .withConstraints([
+                        new EqualityConstraint(
+                            value.type,
+                            new t.ArrayType(type),
+                            node
+                        ),
+                        new EqualityConstraint(
+                            property.type,
+                            new t.NumberType(),
+                            node
+                        )
+                    ]),
+                type
+            ));
+        },
+
+        visitTypeClass: function() {
+            var body = generate(nodesWithoutComments.slice(1), monomorphic),
+                typeClassVariable = nodeToType(node.generic, vars),
+                memberConstraints = [],
+                vars = {};
+
+            _.each(node.types, function(v, k) {
+                var describedType = nodeToType(v, _.clone(vars));
+                _.each(body.state.assumptions[k], function(t) {
+                    memberConstraints.push(new EqualityConstraint(
+                        describedType,
+                        t,
+                        node
+                    ));
+                });
+            });
+
+            return recurseIfMoreNodes(new StateType(
+                body.state
+                    .withConstraints(memberConstraints),
+                body.type
+            ));
+        },
+        visitInstance: function() {
+            var body = generate(nodesWithoutComments.slice(1), monomorphic),
+                instance = {},
+                instances = {};
+
+            instance[node.name] = _.pick(node, ['typeName', 'object']);
+            instances[node.typeClassName] = instance;
+
+            return recurseIfMoreNodes(new StateType(
+                body.state
+                    .withInstances(instances),
+                body.type
+            ));
+        },
 
         visitExpression: function() {
             var value = generate([node.value], monomorphic);
                 new t.NumberType()
             ));
         },
+        visitBinaryStringOperator: function() {
+            var a = generate([node.left], monomorphic),
+                b = generate([node.right], monomorphic);
+
+            return recurseIfMoreNodes(new StateType(
+                InferenceState
+                    .empty
+                    .append(a.state)
+                    .append(b.state)
+                    .withConstraints([
+                        new EqualityConstraint(
+                            a.type,
+                            new t.StringType(),
+                            node
+                        ),
+                        new EqualityConstraint(
+                            b.type,
+                            new t.StringType(),
+                            node
+                        )
+                    ]),
+                new t.StringType()
+            ));
+        },
         visitBinaryGenericOperator: function() {
             var a = generate([node.left], monomorphic),
                 b = generate([node.right], monomorphic);
 }
 exports.generate = generate;
 
+function nodeToType(node, vars) {
+    if(!vars) vars = {};
+
+    function recurse(n) {
+        return nodeToType(n, vars);
+    }
+
+    return node.accept({
+        visitGeneric: function() {
+            if(!vars[node.value]) vars[node.value] = new t.Variable();
+            return vars[node.value];
+        },
+        visitTypeFunction: function() {
+            return new t.FunctionType(_.map(node.args, recurse));
+        },
+        visitTypeName: function() {
+            throw new Error("TODO #1: visitTypeName");
+        },
+        visitTypeArray: function() {
+            throw new Error("TODO #1: visitTypeArray");
+        },
+        visitTypeObject: function() {
+            throw new Error("TODO #1: visitTypeObject");
+        }
+    });
+}
+
+function tails(xs) {
+    return _.map(_.range(xs.length), function(i) {
+        return xs.slice(i);
+    });
+}
+
+function isSolvable(constraints) {
+    // Find first unsolvable.
+    return !_.find(tails(constraints), function(tail) {
+        var constraint = tail[0],
+            rest = tail.slice(1),
+            solvable = constraint.fold(function() {
+                // Equality
+                return true;
+            }, function() {
+                // Implicit
+                return !_.intersection(
+                    _.difference(
+                        free(constraint.b),
+                        constraint.monomorphic
+                    ),
+                    _.union.apply(_, _.map(rest, active))
+                ).length;
+            }, function() {
+                // Explicit
+                return true;
+            }, function() {
+                // TODO: I guess
+                return true;
+            });
+
+        return !solvable;
+    });
+}
+
 function solve(constraints) {
-    var sortedConstraints = _.sortBy(constraints, function(c) {
-            return c.solveOrder;
-        }),
-        rest = sortedConstraints.slice(1),
+    // Constraints need to be in a particular order to be solvable.
+    // Randomly shuffle the constraints until in an order that is solvable.
+    // TODO: Don't use bogosort.
+    var solvableConstraints = (function() {
+            var groupedConstraints = _.groupBy(constraints, function(constraint) {
+                    return constraint.fold(function() {
+                        return 'other';
+                    }, function() {
+                        return 'implicit';
+                    }, function() {
+                        return 'other';
+                    }, function() {
+                        return 'other';
+                    });
+                }),
+                implicitConstraints = groupedConstraints.implicit || [];
+
+            while(!isSolvable(implicitConstraints)) {
+                implicitConstraints = _.shuffle(implicitConstraints);
+            }
+
+            return (groupedConstraints.other || []).concat(implicitConstraints);
+        })(),
+        rest = solvableConstraints.slice(1),
         constraint;
 
-    if(!constraints.length) return {};
+    if(!constraints.length)
+        return {};
+
+    if(!solvableConstraints)
+        throw new Error('Unsolvable constraints');
 
-    constraint = sortedConstraints[0];
+    constraint = solvableConstraints[0];
     return constraint.fold(function() {
         // Equality constraints
         // Use the Most General Unifier (mgu)
         var m = mostGeneralUnifier(constraint.a, constraint.b, constraint.node),
-            s = _.map(rest, function(r) {
+            s = solve(_.map(rest, function(r) {
                 return constraintSubstitute(m, r, constraint.node);
-            });
-        return _.extend(m, solve(rest));
+            })),
+            r = {};
+        _.each(_.extend(m, s), function(v, k) {
+            r[k] = typeSubstitute(s, v);
+        });
+        return r;
     }, function() {
         // Implicit constraints
         return solve([new ExplicitConstraint(
         return [].concat.apply([], _.map(type.types, free));
     } else if(type instanceof t.ObjectType) {
         return [].concat.apply([], _.map(type.props, free));
+    } else if(type instanceof t.RowObjectType) {
+        return free(type.row).concat.apply([], _.map(type.props, free));
     } else if(type instanceof t.ArrayType) {
         return free(type.type);
+    } else if(type instanceof t.TagType) {
+        return [].concat.apply([], _.map(type.vars, free));
     }
     return [];
 }
 
 function instantiate(scheme) {
-    var substitutions = scheme.s.map(function() {
-        return new t.Variable();
+    var substitutions = {};
+    _.each(scheme.s, function(id) {
+        substitutions[id] = new t.Variable();
     });
     return typeSubstitute(substitutions, scheme.t);
 }
 
 function generalize(type, monomorphic) {
-    return new Scheme(_.without(free(type), monomorphic), type);
+    return new Scheme(_.difference(free(type), monomorphic), type);
 }
 
 function variableBind(a, b) {
 }
 
 function mostGeneralUnifier(a, b, node) {
+    function typeError() {
+        throw new Error('Type error on line ' + node.lineno + ': ' + b.toString() + ' is not ' + a.toString());
+    }
+
     if(a instanceof t.Variable) {
         return variableBind(a, b);
     } else if(b instanceof t.Variable) {
         return variableBind(b, a);
-    } else if(a instanceof t.FunctionType && b instanceof t.FunctionType) {
+    } else if(a instanceof t.FunctionType && b instanceof t.FunctionType && a.types.length == b.types.length) {
+        return _.reduce(_.zip(a.types, b.types), function(accum, pair) {
+            var a = typeSubstitute(accum, pair[0]),
+                b = typeSubstitute(accum, pair[1]);
+            return _.extend(accum, mostGeneralUnifier(a, b, node));
+        }, {});
+    } else if(a instanceof t.RowObjectType && b instanceof t.RowObjectType) {
+        return mostGeneralUnifier(a, b.row, node);
+    } else if(a instanceof t.RowObjectType && b instanceof t.ObjectType) {
         return (function() {
-            // TODO: Make into a fold
-            var subs1 = mostGeneralUnifier(a.types[0], b.types[0], node);
-            var subs2 = mostGeneralUnifier(typeSubstitute(subs1, a.types[1]), typeSubstitute(subs1, b.types[1]));
-            return _.extend(subs1, subs2);
-        });
+            var row = a,
+                props = [],
+                keys = [];
+
+            while(row instanceof t.RowObjectType) {
+                props.push(row.props);
+                keys = keys.concat(_.keys(row.props));
+                row = row.row;
+            }
+
+            if(_.difference(keys, _.keys(b.props)).length)
+                typeError();
+
+            return _.reduce(props, function(accum, prop) {
+                return _.reduce(_.keys(prop), function(accum, key) {
+                    var c = typeSubstitute(accum, prop[key]),
+                        d = typeSubstitute(accum, b.props[key]);
+
+                    return _.extend(accum, mostGeneralUnifier(c, d, node));
+                }, accum);
+            }, {});
+        })();
+    } else if(a instanceof t.ArrayType && b instanceof t.ArrayType) {
+        return mostGeneralUnifier(a.type, b.type);
+    } else if(a instanceof t.TagType && b instanceof t.TagType && a.name == b.name && a.vars.length == b.vars.length) {
+        if(!a.vars.length)
+            return {};
+
+        return _.reduce(_.range(a.vars.length), function(accum, i) {
+            return _.extend(
+                accum,
+                mostGeneralUnifier(a.vars[i], b.vars[i], node)
+            );
+        }, {});
     } else if(a instanceof t.NumberType && b instanceof t.NumberType) {
         return {};
     } else if(a instanceof t.StringType && b instanceof t.StringType) {
     } else if(a instanceof t.BooleanType && b instanceof t.BooleanType) {
         return {};
     }
-    throw new Error('Type error on line ' + node.lineno + ': ' + b.toString() + ' is not ' + a.toString());
+    typeError();
+}
+
+function active(constraint) {
+    return constraint.fold(function() {
+        // Equality
+        return _.union(
+            free(constraint.a),
+            free(constraint.b)
+        );
+    }, function() {
+        // Implicit
+        return _.union(
+            free(constraint.a),
+            _.intersection(
+                constraint.monomorphic,
+                free(constraint.b)
+            )
+        );
+    }, function() {
+        // Explicit
+        return _.union(
+            free(constraint.a),
+            _.difference(
+                free(constraint.scheme.t),
+                constraint.scheme.s
+            )
+        );
+    }, function() {
+        throw new Error("TODO");
+    });
 }
 
 function constraintSubstitute(substitutions, constraint) {
     }, function() {
         return new ExplicitConstraint(
             typeSubstitute(substitutions, constraint.a),
-            constraint.scheme,
+            schemeSubstitute(substitutions, constraint.scheme),
             constraint.node
         );
+    }, function() {
+        throw new Error("TODO: Should be easy");
     });
 }
 
+function schemeSubstitute(substitutions, scheme) {
+    var substitutionsWithoutScheme = {};
+
+    _.each(substitutions, function(v, k) {
+        if(_.contains(scheme.s, k)) return;
+        substitutionsWithoutScheme[k] = v;
+    });
+
+    return new Scheme(
+        scheme.s,
+        typeSubstitute(substitutionsWithoutScheme, scheme.t)
+    );
+}
+
 function typeSubstitute(substitutions, type) {
     var substituted;
     if(type instanceof t.Variable) {
             substituted[k] = typeSubstitute(substitutions, v);
         });
         return new t.ObjectType(substituted);
+    } else if(type instanceof t.RowObjectType) {
+        substituted = {};
+        _.each(type.props, function(v, k) {
+            substituted[k] = typeSubstitute(substitutions, v);
+        });
+        return new t.RowObjectType(typeSubstitute(substitutions, type.row), substituted);
+    } else if(type instanceof t.TagType) {
+        return new t.TagType(type.name, _.map(type.vars, function(v) {
+            return typeSubstitute(substitutions, v);
+        }));
     } else if(type instanceof t.ArrayType) {
         throw new Error("Not handled: " + type.toString());
     } else if(type instanceof t.NumberType) {
         constraints = stateType.state.constraints,
         substitutions = solve(constraints);
 
+    _.each(substitutions, function(v, k) {
+        console.log(k, v.toString());
+    });
+
     return typeSubstitute(substitutions, stateType.type);
 }
 exports.typecheck = typecheck;
 //     fun id x = x
 //
 // Here, `id` has the polymorphic type `#a -> #a`.
-var Variable = function(idString) {
+function Variable() {
     this.id = Variable.nextId;
     Variable.nextId++;
-};
+}
 Variable.nextId = 0;
 exports.Variable = Variable;
 
-var toChar = function(n) {
+function toChar(n) {
     return String.fromCharCode("a".charCodeAt(0) + n);
-};
+}
 // Type variables should look like `'a`.
 //
 // This is just bijective base 26.
-var variableToString  = function(n) {
+function variableToString(n) {
     var a = '';
     if(n >= 26) {
         a = variableToString(n / 26 - 1);
     }
     a += toChar(n);
     return a;
-};
+}
 Variable.prototype.toString = function() {
     return "#" + variableToString(this.id);
 };
 
-var variableFromString = function(vs) {
+function variableFromString(vs) {
     return _.reduce(_.map(vs.split(''), function(v, k) {
         return v.charCodeAt(0) - 'a'.charCodeAt(0) + 26 * k;
     }), function(accum, n) {
         return accum + n;
     }, 0);
-};
+}
 
 // ## Base type
 //
 // Base type for all specific types. Using this type as the prototype allows the
 // use of `instanceof` to detect a type variable or an actual type.
-var BaseType = function() {};
+function BaseType() {}
 BaseType.prototype.toString = function() {
     return this.name;
 };
 //
 // A `FunctionType` contains a `types` array. The last element represents the
 // return type. Each element before represents an argument type.
-var FunctionType = function(types) {
+function FunctionType(types) {
     this.types = types;
-};
+}
 FunctionType.prototype = new BaseType();
 FunctionType.prototype.name = "Function";
 FunctionType.prototype.toString = function() {
 };
 exports.FunctionType = FunctionType;
 
-var NumberType = function() {};
+function NumberType() {}
 NumberType.prototype = new BaseType();
 NumberType.prototype.name = "Number";
 exports.NumberType = NumberType;
 
-var StringType = function() {};
+function StringType() {}
 StringType.prototype = new BaseType();
 StringType.prototype.name = "String";
 exports.StringType = StringType;
 
-var BooleanType = function() {};
+function BooleanType() {}
 BooleanType.prototype = new BaseType();
 BooleanType.prototype.name = "Boolean";
 exports.BooleanType = BooleanType;
 
-var ArrayType = function(type) {
+function ArrayType(type) {
     this.type = type;
-};
+}
 ArrayType.prototype = new BaseType();
 ArrayType.prototype.name = "Array";
 ArrayType.prototype.toString = function() {
 };
 exports.ArrayType = ArrayType;
 
-var ObjectType = function(props) {
+function ObjectType(props) {
     this.props = props;
-};
+}
 ObjectType.prototype = new BaseType();
 ObjectType.prototype.name = "Object";
 ObjectType.prototype.getPropertyType = function(prop) {
 };
 exports.ObjectType = ObjectType;
 
-var TagNameType = function(name) {
-    this.name = name;
+function RowObjectType(row, props) {
+    this.row = row;
+    this.props = props;
+}
+RowObjectType.prototype = new BaseType();
+RowObjectType.prototype.toString = function() {
+    var strs = [];
+    var p;
+    for(p in this.props) {
+        strs.push(p + ': ' + this.props[p].toString());
+    }
+    return '{' + this.row.toString() + ', ' + strs.join(', ') + '}';
 };
-TagNameType.prototype = new BaseType();
-exports.TagNameType = TagNameType;
+exports.RowObjectType = RowObjectType;
 
-var TagType = function(types) {
-    this.types = types;
-    this.name = types[0].toString();
-};
+function TagType(name, vars) {
+    this.name = name;
+    this.vars = vars;
+}
 TagType.prototype = new BaseType();
 TagType.prototype.toString = function() {
-    return _.map(this.types, function(t) {
-        return t.toString();
+    if(!this.vars.length) return this.name;
+    return this.name + ' ' + _.map(this.vars, function(v) {
+        return v.toString();
     }).join(' ');
 };
 exports.TagType = TagType;
 
-var UnitType = function() {};
+function UnitType() {}
 UnitType.prototype = new BaseType();
 UnitType.prototype.name = "Unit";
 exports.UnitType = UnitType;
 
-var TypeClassType = function(name, type) {
+function TypeClassType(name, type) {
     this.name = name;
     this.type = type;
-};
+}
 TypeClassType.prototype = new BaseType();
 TypeClassType.prototype.toString = function() {
     return this.name + ' ' + this.type.toString();

test/CompileSpec.js

     }
 
     function expectExecutionToHaveExpectedOutput(s) {
-        var expected = fixtureExpectedOutput(s);
-        var compiled = fixtureCompilerOutput(s);
+        var expected = fixtureExpectedOutput(s),
+            compiled = fixtureCompilerOutput(s),
+            child = child_process.spawn(processBin),
+            actual = '';
 
-        //console.info(compiled);
-
-        var child = child_process.spawn(processBin);
         child.stdin.write(compiled, 'utf8');
         child.stdin.end();
         child.stdout.setEncoding('utf8');
 
-        var actual = '';
         asyncSpecWait();
         child.stdout.on('data', function(d) {
             actual += d;
         it('conditionals.roy with expected output', function() {
             expectExecutionToHaveExpectedOutput('good/conditionals');
         });
-        /*it('deep_matching.roy with expected output', function() {
+        it('deep_matching.roy with expected output', function() {
             expectExecutionToHaveExpectedOutput('good/deep_matching');
-        });*/
-        it('structural_constraints.roy with expected output', function() {
-            expectExecutionToHaveExpectedOutput('good/structural_constraints');
+        });
+        it('nested_structural_constraints.roy with expected output', function() {
+            expectExecutionToHaveExpectedOutput('good/nested_structural_constraints');
         });
         it('functions.roy with expected output', function() {
             expectExecutionToHaveExpectedOutput('good/functions');
         });
-        /*it('map.roy with expected output', function() {
+        it('map.roy with expected output', function() {
             expectExecutionToHaveExpectedOutput('good/map');
         });
         it('monoid.roy with expected output', function() {
             expectExecutionToHaveExpectedOutput('good/monoid');
         });
+        it('identity_monad.roy with expected output', function() {
+            expectExecutionToHaveExpectedOutput('good/identity_monad');
+        });
         it('option_monad.roy with expected output', function() {
             expectExecutionToHaveExpectedOutput('good/option_monad');
-        });*/
+        });
         it('primitive_types.roy with expected output', function() {
             expectExecutionToHaveExpectedOutput('good/primitive_types');
         });
         it('tagged_unions.roy with expected output', function() {
             expectExecutionToHaveExpectedOutput('good/tagged_unions');
         });
-        /*it('trace_monad.roy with expected output', function() {
+        it('trace_monad.roy with expected output', function() {
             expectExecutionToHaveExpectedOutput('good/trace_monad');
         });
         it('unicode.roy with expected output', function() {
             expectExecutionToHaveExpectedOutput('good/unicode');
-        });*/
+        });
         it('where.roy with expected output', function() {
             expectExecutionToHaveExpectedOutput('good/where');
         });
     });
 
     describe('should not execute', function() {
+        it('case_body.roy with expected output', function() {
+            expect(function() {
+                fixtureCompilerOutput('bad/case_body');
+            }).toThrow();
+        });
+        it('structure_literal_access.roy with expected output', function() {
+            expect(function() {
+                fixtureCompilerOutput('bad/structure_literal_access');
+            }).toThrow();
+        });
+        it('structure_function_access.roy with expected output', function() {
+            expect(function() {
+                fixtureCompilerOutput('bad/structure_function_access');
+            }).toThrow();
+        });
         it('tag_with_extra_arg.roy with expected output', function() {
-            expectExecutionToHaveExpectedOutput('bad/tag_with_extra_arg');
+            expect(function() {
+                expectExecutionToHaveExpectedOutput('bad/tag_with_extra_arg');
+            }).toThrow();
         });
     });
 });

test/ConstraintSpec.js

             var state = lib.generate('let x = 100\nx');
             expect(state.assumptions).toEqual({});
             expect(state.constraints.length).toEqual(1);
-            expect(state.constraints[0].a instanceof types.NumberType).toBe(true);
-            expect(state.constraints[0].b instanceof types.Variable).toBe(true);
-            expect(state.constraints[0].m).toEqual([]);
+            expect(state.constraints[0].a instanceof types.Variable).toBe(true);
+            expect(state.constraints[0].b instanceof types.NumberType).toBe(true);
+            expect(state.constraints[0].monomorphic).toEqual([]);
         });
         it('example from "Generalizing Hindley-Milner" paper', function() {
             var state = lib.generate('\\m ->\n  let y = m\n  let x = y true\n  x');

test/TypeInferenceSpec.js

-describe('type inference', function(){
+describe('type inference', function() {
     var typeinference = require('../src/typeinference'),
         types = require('../src/types');
         lexer = require('../src/lexer');
         return typeinference.typecheck(parseCode(s), {}, {});
     }
 
+    describe('should type function', function() {
+        it('identity', function() {
+            expect(typeOfCode('let id a = a\nid 1\nid true')).toStringEqual('Boolean');
+        });
+    });
+
     describe('should type literal', function() {
-        it('numbers', function(){
+        it('numbers', function() {
             expect(typeOfCode('-1')).toStringEqual('Number');
             expect(typeOfCode('-99999')).toStringEqual('Number');
             expect(typeOfCode('0')).toStringEqual('Number');
             expect(typeOfCode('100')).toStringEqual('Number');
         });
 
-        it('strings', function(){
+        it('strings', function() {
             expect(typeOfCode('"100"')).toStringEqual('String');
             expect(typeOfCode('""')).toStringEqual('String');
             expect(typeOfCode("'100'")).toStringEqual('String');
             expect(typeOfCode("''")).toStringEqual('String');
         });
 
-        it('booleans', function(){
+        it('booleans', function() {
             expect(typeOfCode('false')).toStringEqual('Boolean');
             expect(typeOfCode('true')).toStringEqual('Boolean');
         });
             expect(typeOfCode('{a: 1, b: true}')).toStringEqual('{a: Number, b: Boolean}');
         });
 
-        describe('arrays of primitive', function(){
+        describe('arrays of primitive', function() {
             it('strings', function() {
                 expect(typeOfCode('[""]')).toStringEqual('[String]');
             });

test/fixtures/bad/case_body.out

Empty file added.

test/fixtures/bad/case_body.roy

+data XYZ a b c = Z a b c
+
+// case identifier `c` should be a String, case body uses as Number.
+
+match (Z 1 true "three")
+  case (Z a b c) = c + 3

test/fixtures/bad/structure_function_access.roy

+let o a b = {a: a, b: b}
+
+(o 1 2).c

test/fixtures/bad/structure_literal_access.roy

+let o = {a: 1, b: true}
+
+o.c

test/fixtures/bad/tag_with_extra_arg.roy

 data A = B | C
-let x = A 1 2
+let x = B 1 2
 console.log x

test/fixtures/good/identity_monad.out

Empty file added.

test/fixtures/good/identity_monad.roy

+data Identity a = Id a
+
+let identityReturn x =
+  Id x
+
+let identityBind x f = match x
+  case (Id y) = f y
+
+let identityMonad = {
+  return: \x ->
+    Id x
+  bind: \x f -> match x
+    case (Id y) = f y
+}
+
+do identityMonad
+  a <- Id "Hello"
+  b <- Id "World"
+  return a ++ " " ++ b

test/fixtures/good/monoid.roy

   empty: ""
 }
 
-instance productMonoid = Monoid {product: Number} {
-  append: \x y -> {product: x.product * y.product}
-  empty: {product: 1}
-}
+// instance productMonoid = Monoid {product: Number} {
+//   append: \x y -> {product: x.product * y.product}
+//   empty: {product: 1}
+// }
 
-instance sumMonoid = Monoid {sum: Number} {
-  append: \x y -> {sum: x.sum + y.sum}
-  empty: {sum: 0}
-}
+// instance sumMonoid = Monoid {sum: Number} {
+//   append: \x y -> {sum: x.sum + y.sum}
+//   empty: {sum: 0}
+// }
 
-let f x = append (append x empty) x
-let g x = f x
+// let f x = append (append x empty) x
+// let g x = f x
 
 console.log (append (append "Hello!" empty) empty)
 
-console.log (g "TEST")
-console.log (g (append {product: 2} empty)).product
-console.log (g {sum: 1}).sum
+// console.log (g "TEST")
+// console.log (g (append {product: 2} empty)).product
+// console.log (g {sum: 1}).sum

test/fixtures/good/nested_structural_constraints.out

+Hello World

test/fixtures/good/nested_structural_constraints.roy

+(\builder ->
+  (builder "Hello").run (\x ->
+    console.log x (builder x).world
+  )
+) (\value -> {
+  run: \x -> x value
+  world: "World"
+})

test/fixtures/good/option_monad.roy

 data Option a = Some a | None
 
+let fromOption d o = match o
+  case (Some a) = a
+  case None = d
+
 let optionMonad = {
   return: λx →
     Some x
   bind: λx f → match x
     case (Some a) = f a
-    case None = None
+    case None = None ()
 }
 
-let m = (do optionMonad
+let someSix = do optionMonad
   x ← Some 1
   let y = 2
   z ← Some 3
   return x + y + z
-)
 
-match m
-  case (Some x) = console.log x
+let six = fromOption 0 someSix
+
+console.log six

test/fixtures/good/structural_constraints.out

-Hello World

test/fixtures/good/structural_constraints.roy

-(\builder ->
-  (builder "Hello").run (\x ->
-    console.log x (builder x).world
-  )
-) (\value -> {
-  run: \x -> x value
-  world: "World"
-})