Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version
Go to top

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
/// http://www.cat-language.com

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

namespace Cat
{
    /// <summary>
    /// A declaration of a type variable. Looks like "A:any" or "B:any*"
    /// Type variable declarations have an index which corresponds to their
    /// position in a function. This allows us to properly compare types with different
    /// variable names. For example: (A (A:any)->(B:any))->(B) is the same as 
    /// (C (C:any)->(D:any))->(D) but is different than (C (C:any)->(D:any))->(C)
    /// This means we have to number and rename them before comparison. 
    /// </summary>
    public class TypeVarDecl : CatType
    {
        #region fields
        string msBaseConstraints;
        string msName;
        int mnIndex = -1;
        static int gnUniqueId = 0;
        int mnId = gnUniqueId++;
        #endregion

        #region static functions
        /// <summary>
        /// UniqueTypeVarDecls is used to assure that each unique variable declaration within
        /// a function has a different name. 
        /// </summary>
        public static TypeVarDecl MakeNewUniqueTypeVarDecl()
        {
            TypeVarDecl ret = new TypeVarDecl("", "any*");
            ret.SetName("_" + ret.GetUniqueID().ToString());
            return ret;
        }
        #endregion

        #region constructors
        public TypeVarDecl(TypeVarDecl decl)
        {
            msName = decl.msName;
            msBaseConstraints = decl.msBaseConstraints;
        }
        public TypeVarDecl(string sName, string sConstraints)
        {
            msName = sName;
            msBaseConstraints = sConstraints;
        }
        public TypeVarDecl(AstNode pNode)
        {
            if ((pNode == null) || (pNode.node_type != NodeType.VarDecl) || (pNode.children.Count < 2) || (pNode.children.Count > 3))
            {
                Parser.Error(pNode, "invalid type declaration, expected a type variable declaration");
            }

            msName = pNode.children[0].ToString();
            msBaseConstraints = pNode.children[1].ToString();
            if (pNode.children.Count == 3)
            {
                string sTmp = pNode.children[2].ToString();
                if (sTmp != "*")
                {
                    throw new Exception("Only '*' type constraint modifiers currently supported");
                }
                msBaseConstraints += sTmp;
            }
        }
        #endregion

        #region public functions
        /// <summary>
        /// Returns true if a type variable matches only a single type. Multi-type variables
        /// have the "*" modifier after the constraint and can match 0 or more types on the 
        /// stack at the same time. 
        /// </summary>
        /// <returns></returns>
        public bool IsSingle()
        {
            return msBaseConstraints.IndexOf('*') < 0;
        }
        public string GetName()
        {
            return msName;
        }
        public string GetUniqueName()
        {
            return msName + "#" + mnId.ToString();
        }
        /// <summary>
        /// Returns the index of the type variable declaration within the 
        /// parent ResolvedFunctionType
        /// </summary>
        public int GetIndex()
        {
            return mnIndex;
        }
        public void SetIndex(int n)
        {
            mnIndex = n;
        }
        public void SetName(string s)
        {
            msName = s;
        }
        public int GetUniqueID()
        {
            return mnId;
        }
        #endregion

        #region overrides 
        public override CatType Clone()
        {
            return new TypeVarDecl(this);
        }
        public override string ToString()
        {
            if (Config.gbSimpleTypeNames)
            {
                return GetName() + ":" + msBaseConstraints;
            }
            else
            {
                return GetUniqueName() + ":" + msBaseConstraints;
            }
        }
        public override bool IsTypeEq(CatType t)
        {
            if (mnIndex < 0)
                throw new Exception("you can't compare type variable declarations within unitialized types");
            if (!(t is TypeVarDecl))
            {
                return false;
            }
            TypeVarDecl that = t as TypeVarDecl;
            if (that.msBaseConstraints != msBaseConstraints)
                return false;
            
            // We are comparing type variables according to their relative position within a function
            return that.mnIndex == mnIndex;
        }
        #endregion
    }

    /// <summary>
    /// TypeVars are created in response to ResolveVars, when no variables exist.  
    /// </summary>
    public class TypeVar : CatType
    {
        #region fields
        TypeVarDecl mpDecl;
        #endregion

        #region constructors
        public TypeVar(TypeVarDecl decl)
        {
            mpDecl = decl;
        }
        #endregion

        #region overrides
        public override CatType Clone()
        {
            return new SimpleType(GetName());
        }
        public override string ToString()
        {
            if (Config.gbSimpleTypeNames)
            {
                return mpDecl.GetName();
            }
            else
            {
                return mpDecl.GetUniqueName();
            }
        }
        public override bool IsTypeEq(CatType t)
        {
            if (t is TypeVar)
            {
                return AsDecl().GetIndex() == t.AsDecl().GetIndex();
            }
            else
            {
                return false;
            }
        }
        #endregion

        #region public functions
        public TypeVarDecl GetDecl()
        {
            return mpDecl;
        }
        public string GetName()
        {
            return GetDecl().GetName();
        }
        #endregion
    }

    /// <summary>
    /// Used for the mapping of SimpleTypes to type variables during the creation of FxnType
    /// objects. In a FxnType when a simple identifier is found, it is treated as a SimpleType,
    /// that is to say the name of a type. The TypeLookup class acts as a dictionary for 
    /// mapping simple type names to type variable declarations.
    /// </summary>
    public class TypeLookup
    {
        #region fields
        Dictionary<string, TypeVarDecl> mDict = new Dictionary<string, TypeVarDecl>();
        #endregion

        #region public functions
        public int GetCount()
        {
            return mDict.Count;
        }
        public TypeVarDecl GetValue(string s)
        {
            if (!mDict.ContainsKey(s))
                return null;

            TypeVarDecl result = mDict[s];

            return result;
        }
        public TypeVarDecl GetValue(TypeVarDecl decl)
        {
            return GetValue(decl.GetName());        
        }
        public TypeVarDecl GetValue(TypeVar var)
        {
            return GetValue(var.GetDecl());
        }

        public void SetValue(string s, TypeVarDecl t)
        {
            if (mDict.ContainsKey(s))
                throw new Exception("attempting to redefine type variable " + s + " as " + t.ToString() + " while it has value " + mDict[s].ToString());

            mDict[s] = t;
        }

        public bool ContainsKey(string s)
        {
            return mDict.ContainsKey(s);
        }
        public bool ContainsKey(TypeVarDecl decl)
        {
            return ContainsKey(decl.GetName());
        }
        public bool ContainsKey(TypeVar v)
        {
            return ContainsKey(v.GetDecl());
        }
        public void AddValue(TypeVarDecl decl)
        {
            mDict[decl.GetName()] = decl;
        }
        #endregion

    }
}

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.

License

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

Share

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.
Follow on   Twitter   Google+   LinkedIn

| Advertise | Privacy | Mobile
Web04 | 2.8.140916.1 | Last Updated 4 Nov 2006
Article Copyright 2006 by Christopher Diggins
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid