Click here to Skip to main content
12,500,937 members (49,123 online)
Click here to Skip to main content

Stats

43.7K views
414 downloads
44 bookmarked
Posted

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>
    /// Cat functions are transitions from two stacks to two stacks.
    /// A Cat type consumes a constant number of stack elements (consumption)
    /// and produces a constant number of stack elements (production)
    /// </summary>
    public class FxnType : CatType
    {
        #region fields
        private bool mbPure = true;
        private TypeStack mpMainCons = new TypeStack();
        private TypeStack mpAuxCons = new TypeStack();
        private TypeStack mpMainProd = new TypeStack();
        private TypeStack mpAuxProd = new TypeStack();
        #endregion

        #region constructors
        /// <summary>
        /// The default constructor is private. 
        /// </summary>
        public FxnType(bool bPure)
        {
            mbPure = bPure;
        }
        private FxnType()
        {
        }
        public FxnType(AstNode pNode)
        {
            if ((pNode.children.Count != 3) && (pNode.children.Count != 5))
                Parser.Error(pNode, "invalid function type declaration");

            if (pNode.children.Count == 3)
            {
                mpMainCons = new TypeStack(pNode.children[0]);
                mbPure = NodeToPurity(pNode.children[1]);
                mpMainProd = new TypeStack(pNode.children[2]);
            }
            else
            {
                mpMainCons = new TypeStack(pNode.children[0]);
                mpAuxCons = new TypeStack(pNode.children[1]);
                mbPure = NodeToPurity(pNode.children[2]);
                mpMainProd = new TypeStack(pNode.children[3]);
                mpAuxProd = new TypeStack(pNode.children[4]);
            }
        }
        #endregion

        #region public functions
        public void Initialize()
        {
            Assert(!AreFxnsShared(this, new List<FxnType>()));
            MakeTypeVars();
            Normalize();
        }
        public void AssertNormalized()
        {
            Assert(!AreFxnsShared(this, new List<FxnType>()));
            AssertNormalized(this, new List<TypeVarDecl>());
        }
        /// <summary>
        /// The default variables represent the stack before the execution of a given 
        /// function. They are implied in a functions definition. For example, (int)->(int int)
        /// actually means: (A:any* int)(B:any*)->(A int int)(B)
        /// </summary>
        public void AddDefaultVariables()
        {
            TypeVarDecl main = TypeVarDecl.MakeNewUniqueTypeVarDecl();
            TypeVarDecl aux = TypeVarDecl.MakeNewUniqueTypeVarDecl();
            mpMainCons.PushFront(main);
            mpMainProd.PushFront(new TypeVar(main));
            mpAuxCons.PushFront(aux);
            mpAuxProd.PushFront(new TypeVar(aux));
        }
        /// <summary>
        /// Default variables are only used during type inference, what is reported to the 
        /// user does not have default variables. 
        /// </summary>
        public void RemoveDefaultVariables()
        {
            mpMainCons.PopFront();
            mpAuxCons.PopFront();
            mpMainProd.PopFront();
            mpAuxProd.PopFront();
        }
        /// <summary>
        /// When creating function types, sub-functions will possibly use the same variable names.
        /// We have to assure that all the declarations (and as a result the variables) have appropriate
        /// names before we can create they names.
        /// </summary>
        public void UniquelyIdentifyDecls()
        {
            UniquelyIdentifyDecls(this);
        }
        /// <summary>
        /// This verifies that all declarations appear before variable declarations and are 
        /// numbered correctly. You should only call this when you know functions aren'key 
        /// being shared. This can be forced by cloning the function.
        /// </summary>
        public void Normalize()
        {
            Assert(!AreFxnsShared(this, new List<FxnType>()));
            TypeLookup lookup = new TypeLookup();
            Normalize(this, lookup);
            NameByIndex(this);
        }
        /// <summary>
        /// IsPure indicates that a function and none of its sub-functions have any side effects.
        /// </summary>
        public bool IsPure()
        {
            return mbPure;
        }
        public void SetPurity(bool bPure)
        {
            mbPure = bPure;
        }
        /// <summary>
        /// This is supposed to report true if any types are consumed or produced on 
        /// the auxiliary stack. However, if there are default variables declared, then this
        /// will still return true.
        /// </summary>
        public bool HasAuxEffect()
        {
            return (!GetAuxConsStack().IsEmpty()) || (!GetAuxProdStack().IsEmpty());
        }
        #endregion

        #region private functions
        /// <summary>
        /// Returns true if any subfunction occur multiple times. 
        /// The effect of which would be to cause any changes to one branch
        /// to propagate.
        /// </summary>
        private static bool AreFxnsShared(CatType t, List<FxnType> list)
        {
            if (t is FxnType)
            {
                FxnType f = t as FxnType;
                if (list.Contains(f)) return true;
                list.Add(f);
                if (AreFxnsShared(f.GetMainConsStack(), list)) return true;
                if (AreFxnsShared(f.GetAuxConsStack(), list)) return true;
                if (AreFxnsShared(f.GetMainProdStack(), list)) return true;
                if (AreFxnsShared(f.GetAuxProdStack(), list)) return true;
            }
            else if (t is TypeStack)
            {
                foreach (CatType u in (t as TypeStack))
                    if (AreFxnsShared(u, list))
                        return true;
            }
            return false;
        }
        /// <summary>
        /// Converts references to variables (SimpleTypes) in stkRet to TypeVar types, and generates
        /// TypeVars in lookup table in response to TypeVarDecl occurences. Note that during this 
        /// call some sub-functions may be referenced multiple times. This means that this algorithm
        /// can not be merged with Normalize() as I had previously thought. 
        /// </summary>
        private void MakeTypeVars()
        {
            TypeLookup lookup = new TypeLookup();
            MakeTypeVars(this, lookup);
            ExpandTypeVars(this, lookup);
        }
        static private void MakeTypeVars(FxnType ft, TypeLookup lookup)
        {
            MakeTypeVars(ft.GetMainConsStack(), lookup);
            MakeTypeVars(ft.GetAuxConsStack(), lookup);
            MakeTypeVars(ft.GetMainProdStack(), lookup);
            MakeTypeVars(ft.GetAuxProdStack(), lookup);
        }
        static private void MakeTypeVars(TypeStack stk, TypeLookup lookup)
        {
            for (int i = 0; i < stk.Count; ++i)
            {
                CatType t = stk[i];
                if (t is TypeVarDecl)
                {
                    TypeVarDecl decl = t as TypeVarDecl;
                    lookup.AddValue(decl);
                }
                else if (t is FxnType)
                {
                    FxnType f = t as FxnType;
                    MakeTypeVars(f, lookup);
                }
                else if (t is TypeVar)
                {
                    TypeVar tv = t as TypeVar;
                    if (!lookup.ContainsKey(tv))
                        lookup.AddValue(tv.GetDecl());
                }
            }
        }
        static private void ExpandTypeVars(TypeStack stk, TypeLookup lookup)
        {
            for (int i = 0; i < stk.Count; ++i)
            {
                CatType t = stk[i];

                if (t is SimpleType)
                {
                    string s = (t as SimpleType).ToString();
                    TypeVarDecl decl = lookup.GetValue(s);
                    if (decl != null)
                        stk[i] = new TypeVar(decl);
                }
                else if (t is FxnType)
                {
                    ExpandTypeVars(t as FxnType, lookup);
                }
            }
        }
        static private void ExpandTypeVars(FxnType ft, TypeLookup lookup)
        {
            ExpandTypeVars(ft.GetMainConsStack(), lookup);
            ExpandTypeVars(ft.GetAuxConsStack(), lookup);
            ExpandTypeVars(ft.GetMainProdStack(), lookup);
            ExpandTypeVars(ft.GetAuxProdStack(), lookup);
        }
        private void UniquelyIdentifyDecls(CatType t)
        {
            if (t is FxnType)
            {
                FxnType f = t as FxnType;
                UniquelyIdentifyDecls(f.GetMainConsStack());
                UniquelyIdentifyDecls(f.GetAuxConsStack());
                UniquelyIdentifyDecls(f.GetMainProdStack());
                UniquelyIdentifyDecls(f.GetAuxProdStack());
            }
            else if (t is TypeStack)
            {
                TypeStack stack = t as TypeStack;
                foreach (CatType u in stack)
                    UniquelyIdentifyDecls(u);
            }
            else if (t is TypeVarDecl)
            {
                TypeVarDecl decl = t as TypeVarDecl;
                decl.SetName(decl.GetUniqueName());
            }
        }
        /// <summary>
        /// Normalization assures that the type variable declarations occur
        /// before type variable references, and that these type variable
        /// declarations are numbered starting at zero, and increase
        /// sequentially appropriately. 
        /// </summary>
        private static void Normalize(CatType t, TypeLookup lookup)
        {
            if (t is FxnType)
            {
                FxnType f = t as FxnType;
                Normalize(f.GetMainConsStack(), lookup);
                Normalize(f.GetAuxConsStack(), lookup);
                Normalize(f.GetMainProdStack(), lookup);
                Normalize(f.GetAuxProdStack(), lookup);
            }
            else if (t is TypeStack)
            {
                Normalize(t as TypeStack, lookup);
            }
            else
            {
                Assert(false, "Only FxnTypes and TypeStacks can be normalized");
            }
        }
        private static void Normalize(TypeStack stk, TypeLookup lookup)
        {
            for (int i = 0; i < stk.Count; ++i)
            {
                CatType t = stk[i];
                if (t is FxnType)
                {
                    Normalize(t, lookup);
                }
                else if (t is TypeVar)
                {
                    TypeVar tv = t as TypeVar;
                    if (!lookup.ContainsKey(tv))
                    {
                        TypeVarDecl decl = new TypeVarDecl(tv.GetDecl());
                        decl.SetIndex(lookup.GetCount());
                        lookup.AddValue(decl);
                        Assert(decl.GetIndex() >= 0);
                        stk[i] = decl;
                    }
                    else
                    {
                        TypeVarDecl decl = lookup.GetValue(tv);
                        Assert(decl.GetIndex() >= 0);
                        stk[i] = new TypeVar(decl);
                    }
                }
                else if (t is TypeVarDecl)
                {
                    TypeVarDecl decl = t as TypeVarDecl;
                    string s = decl.GetName();
                    if (lookup.ContainsKey(s))
                    {
                        decl = lookup.GetValue(s);
                        Assert(decl.GetIndex() >= 0);
                        stk[i] = new TypeVar(decl);
                    }
                    else
                    {
                        decl.SetIndex(lookup.GetCount());
                        lookup.AddValue(decl);
                        Assert(decl.GetIndex() >= 0);
                        stk[i] = decl;
                    }
                }
            }
        }
        /// <summary>
        /// This will assure that the name of each type variable 
        /// will correspond to the variable index. 
        /// </summary>
        private static void NameByIndex(CatType t)
        {
            if (t is FxnType)
            {
                FxnType f = t as FxnType;
                NameByIndex(f.GetMainConsStack());
                NameByIndex(f.GetAuxConsStack());
                NameByIndex(f.GetMainProdStack());
                NameByIndex(f.GetAuxProdStack());
            }
            else if (t is TypeStack)
            {
                foreach (CatType u in (t as TypeStack))
                    NameByIndex(u);
            }
            else if (t is TypeVarDecl)
            {
                TypeVarDecl decl = t as TypeVarDecl;
                decl.SetName("_" + decl.GetIndex());
            }
        }
        private void AssertNormalized(CatType t, List<TypeVarDecl> list)
        {
            if (t is FxnType)
            {
                FxnType f = t as FxnType;
                AssertNormalized(f.GetMainConsStack(), list);
                AssertNormalized(f.GetAuxConsStack(), list);
                AssertNormalized(f.GetMainProdStack(), list);
                AssertNormalized(f.GetAuxProdStack(), list);
            }
            else if (t is TypeStack)
            {
                foreach (CatType u in (t as TypeStack))
                    AssertNormalized(u, list);
            }
            else if (t is TypeVarDecl)
            {
                TypeVarDecl decl = t as TypeVarDecl;
                Assert(decl.GetIndex() == list.Count);
                list.Add(decl);
            }
            else if (t is TypeVar)
            {
                TypeVar tv = t as TypeVar;
                Assert(list.Contains(tv.GetDecl()));
            }
        }
        #endregion

        #region stack accessors
        public TypeIterator GetMainConsIter()
        {
            return mpMainCons.GetTypeIterator();
        }
        public TypeIterator GetAuxConsIter()
        {
            return mpAuxCons.GetTypeIterator();
        }
        public TypeIterator GetMainProdIter()
        {
            return mpMainProd.GetTypeIterator();
        }
        public TypeIterator GetAuxProdIter()
        {
            return mpAuxProd.GetTypeIterator();
        }
        /// <summary>
        /// Contains the primary consumption of a function
        /// </summary>
        public TypeStack GetMainConsStack()
        {
            return mpMainCons;
        }
        /// <summary>
        /// Contains the auxiliary consumption of a function
        /// </summary>
        public TypeStack GetAuxConsStack()
        {
            return mpAuxCons;
        }
        /// <summary>
        /// Contains the primary production of a function
        /// </summary>
        public TypeStack GetMainProdStack()
        {
            return mpMainProd;
        }
        /// <summary>
        /// Contains the auxiliary production of a function
        /// </summary>
        public TypeStack GetAuxProdStack()
        {
            return mpAuxProd;
        }
        public void SetMainConsStack(TypeStack stk)
        {
            mpMainCons = stk;
        }
        public void SetAuxConsStack(TypeStack stk)
        {
            mpAuxCons = stk;
        }
        public void SetMainProdStack(TypeStack stk)
        {
            mpMainProd = stk;
        }
        public void SetAuxProdStack(TypeStack stk)
        {
            mpAuxProd = stk;
        }
        #endregion
        
        #region overrides
        public override string ToString()
        {
            string result = "";
            if (HasAuxEffect())
            {
                result += mpMainCons.ToString();
                result += mpAuxCons.ToString();
                result += mbPure ? " -> " : " ~> ";
                result += mpMainProd.ToString();
                result += mpAuxProd.ToString();
            }
            else
            {
                result += mpMainCons.ToString();
                result += mbPure ? " -> " : " ~> ";
                result += mpMainProd.ToString();
            }
            return result;
        }
        public override bool IsTypeEq(CatType t)
        {
            if (t == this) return true;
            if (t.IsAnyType()) return true;

            if (!(t is FxnType))
                return false;
            FxnType that = t as FxnType;

            // BUG: I call this where sometimes Pure functions are acceptable.
            // As a result the following line has to be left commented.
            // if (that.IsPure() != IsPure()) return false;

            return (that.GetMainConsStack().IsTypeEq(GetMainConsStack())
                && that.GetAuxConsStack().IsTypeEq(GetAuxConsStack())
                && that.GetMainProdStack().IsTypeEq(GetMainProdStack())
                && that.GetAuxProdStack().IsTypeEq(GetAuxProdStack()));
        }
        public override CatType Clone()
        {
            FxnType ret = new FxnType(mbPure);
            ret.SetMainConsStack(GetMainConsStack().Clone() as TypeStack);
            ret.SetAuxConsStack(GetAuxConsStack().Clone() as TypeStack);
            ret.SetMainProdStack(GetMainProdStack().Clone() as TypeStack);
            ret.SetAuxProdStack(GetAuxProdStack().Clone() as TypeStack);
            ret.MakeTypeVars();
            return ret;
        }
        #endregion

        #region internal utility functions
        static private bool NodeToPurity(AstNode pNode)
        {
            if (pNode.ToString() == "->")
            {
                return true;
            }
            else if (pNode.ToString() == "~>")
            {
                return false;
            }
            else
            {
                Parser.Error(pNode, "expected '->' or '~>'");
                return false;
            }
        }
        #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.

You may also be interested in...

Pro
Pro
| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.160919.1 | Last Updated 4 Nov 2006
Article Copyright 2006 by Christopher Diggins
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid