# input: # - env = mapping of variable names to types # - expr = an expression (AST) # # output: # - type = a type "judgment" # - constraints = a list of type constraints that must be satisfied def infer_type( env, expr ): case expr: ## wow, a literal integer has type IntType! LiteralIntExpr( thenumber ): return ( IntType, {} ); # no constraints ## similar rules for other kinds of literals ... ## here's an interesting one: ## empty lists are polymorphic EmptyListExpr(): return( ListExpr( fresh PolymorphicType ), {} ); # no constriants ## fresh PolymorphicType means make a new PolymorphicType with ## a never-before-used identifying number/letter ## list expression: [item1, ... itemn] ## - infer the type of each item ## - pass along constraints from the subexpressions ## - add constraints that all items have the same type ListExpr( item1, ... itemn ): (type1, constr1) = infer_type( env, item1 ); ... (typen, constrn) = infer_type( env, itemn ); ## union of these lists of constraints return ( ListType(type1), constr1 + ... + constrn + "type1==type2" + ... + "type1==typen" ); ## someone names a variable? if it doesn't have a type ## in our environment, we are hosed! otherwise, the ## environment contains a type mapping for the variable VariableExpression( varname ): croak if not exists env{varname}; return ( env{varname}, {} ) # no constraints ## for addition expression: ## - return IntType ## - constrain both args to be IntType ## - pass along constraints from subexpressions AdditionExpression( subexpr1, subexpr2 ): (type1, constr1) = infer_type( env, subexpr1 ); (type2, constr2) = infer_type( env, subexpr2 ); ## union of these lists of constraints return (IntType, constr1 + constr2 + "type1==IntType" + "type2==IntType"); ## for concatenation: ## - same as above, but with StrType ConcatExpression( subexpr1, subexpr2 ): (type1, constr1) = infer_type( env, subexpr1 ); (type2, constr2) = infer_type( env, subexpr2 ); ## union of these lists of constraints return ( StrType, constr1 + constr2 + "type1==StrType" + "type2==StrType" ); ## list cons expression: i.e,: head::tail ## - return the same type as the tail ## - ensure that the head has the same type as ## tail's elements ListConsExpression( head, tail ): (type1, constr1) = infer_type( env, head ); (type2, constr2) = infer_type( env, tail ); return ( type2, constr1 + constr2 + "type2==ListType(type1)" ); ## fun var -> body ## - assign var a fresh type ## - infer the type of the body in a modified environment ## - return an appropriate function type FuncDefExpression( var, body ): vartype = fresh PolymorphicType; (bodytype, bodyconstr) = infer_type( env + "var:vartype", body ); return (FuncType(vartype,bodytype), bodyconstr); ## func(arg): ## - constrain that the argument's type is appropriate ## - this expression's type is the return value type of func ## - easiest to do this by introducing a new polymorphic type FuncAppExpression( func, arg ): (type1, constr1) = infer_type( env, head ); (type2, constr2) = infer_type( env, tail ); resulttype = fresh PolymorphicType; return ( resulttype, constr1 + constr2 + "type1==FuncType(type2,resulttype)" );