/// Public domain code by Christopher Diggins
/// The TypeInferer performs inference of types, and is also used to check that the inferred type
/// is the same as the declared type.
/// The reporting of type errors is not very elegant. The exception message spit out generally is
/// not very helpful to endusers, and is a clear point for improvement.
public class TypeInferer : CatBase
/// This is the work-horse function of the whole compiler / interpreter. Everything depends on this.
public FxnType InferType(Function p)
// The ret fxn type is built progressively by simulating the execution of each sub program.
FxnType ret = new FxnType(true);
// These two variables represent the consumption of the program
// Simulate the execution of the program in terms of tyeps
// and compute the purity at the same time
bool bPure = true;
foreach (Function child in p.mpChildren)
bPure = bPure && child.IsPure();
// Make sure that each type variable has the correct index.
/// This will push the production stack onto the return stack. This
/// is to be called after the production of a type is resolved.
public void SimulateProduction(TypeStack stkRet, TypeStack stkProd)
for (int i=stkProd.Count-1; i >= 0; --i)
/// Consumption simulation of a function checks that each item being consumed,
/// is on the stack, and no more items. This is to be called after the consumption
/// is resolved.
public void SimulateConsumption(TypeStack stkRet, TypeIterator iterCons)
TypeIterator iterRet = stkRet.GetTypeIterator();
while (!iterCons.AtEnd() && !iterRet.AtEnd())
// TEMP: This doesn't quite work the way I hoped.
// I want more of a Subtype checking.
// CatType key = iterCons.GetValue();
// CatType u = iterRet.GetValue();
// Assert(key.IsTypeEq(u), "type checking failed, " + key.ToString() + " and " + u.ToString());
Assert(iterCons.AtEnd(), "unexpected end of consumption stack");
Assert(iterRet.AtEnd(), "unexpected end of return stack");
/// The ret FxnType represents the current state of the type being inferred.
public void SimulateTypeExecution(FxnType ret, Function p)
if (p.mpType == null)
throw new Exception("encountered a program without a type; can't proceed to infer type");
// Cloning is a crucial step, we don't want Fxn to be shared within
// a function declaration, because side effects can cause changes in
// the wrong part of the function type declaration.
FxnType f = p.mpType.Clone() as FxnType;
// Default variables are "any*" variables added to the bottom of each stack
// in a function type.
// This will assure that the function is valid.
// Compute constraints by applying them to the production
ConstraintSolver solver = new ConstraintSolver();
f = solver.ResolveFxn(f);
ret = solver.ResolveFxn(ret);
By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.
If a file you wish to view isn't highlighted, and is a text file (not binary), please
let us know and we'll add colourisation support for it.