Click here to Skip to main content
13,293,178 members (42,853 online)
Click here to Skip to main content


44 bookmarked
Posted 4 Nov 2006

Cat - A Statically Typed Programming Language Interpreter in C#

, 4 Nov 2006
This article contains the public domain implementation of an interpreter for a statically typed stack-based programming language in C# called Cat. The accompanying article is a high-level description of how the various modules work, a brief description of the language, and links to related work.
/// Public domain code by Christopher Diggins

using System;
using System.Collections.Generic;
using System.Text;

namespace Cat
    /// <summary>
    /// 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. 
    /// </summary>
    public class TypeInferer : CatBase
        /// <summary>
        /// This is the work-horse function of the whole compiler / interpreter. Everything depends on this. 
        /// </summary>
        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)
                SimulateTypeExecution(ret, child);
                bPure = bPure && child.IsPure();


            // Make sure that each type variable has the correct index.

            return ret;
        /// <summary>
        /// This will push the production stack onto the return stack. This 
        /// is to be called after the production of a type is resolved. 
        /// </summary>
        public void SimulateProduction(TypeStack stkRet, TypeStack stkProd)
            for (int i=stkProd.Count-1; i >= 0; --i)
        /// <summary>
        /// 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. 
        /// </summary>
        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");
        /// <summary>
        /// The ret FxnType represents the current state of the type being inferred.         
        /// </summary>
        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();
            solver.IntegrateConstraints(ret.GetMainProdIter(), f.GetMainConsIter());
            solver.IntegrateConstraints(ret.GetAuxProdIter(), f.GetAuxConsIter());

            f = solver.ResolveFxn(f);
            ret = solver.ResolveFxn(ret);

            SimulateConsumption(ret.GetMainProdStack(), f.GetMainConsIter());
            SimulateConsumption(ret.GetAuxProdStack(), f.GetAuxConsIter());

            SimulateProduction(ret.GetMainProdStack(), f.GetMainProdStack());
            SimulateProduction(ret.GetAuxProdStack(), f.GetAuxProdStack());


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.


This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


About the Author

Christopher Diggins
Software Developer Autodesk
Canada Canada
This article was written by Christopher Diggins, a computer science nerd who currently works at Autodesk as an SDK specialist.

You may also be interested in...

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.171207.1 | Last Updated 4 Nov 2006
Article Copyright 2006 by Christopher Diggins
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid