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.Reflection;
using System.Reflection.Emit;
using System.Collections;
using System.Collections.Generic;

namespace Cat
{
    /// <summary>
    /// The base class for all Cat functions 
    /// </summary>
    public abstract class Function : CatBase
    {
        /// <summary>
        /// Quotations are anonymous functions, they are all given the same name.
        /// </summary>
        public static string gStringUnnamed = "_unnamed_";

        /// <summary>
        /// Creates a function from an AST node.
        /// </summary>
        public static Function CreateFunctionFromNode(AstNode node, Scope scope)
        {
            switch (node.node_type)
            {
                case NodeType.Quotation:
                    return new Quotation(node, scope);
                case NodeType.String:
                    return new StringLiteral(node.ToString());
                case NodeType.Number:
                    return new IntLiteral(Parser.StringToInt(node.ToString()));
                case NodeType.Word:
                    return scope.ThrowingLookupProgram(node.ToString());
                default:
                    throw new Exception("unhandled node_type " + node.node_type.ToString());
            }
        }

        /// <summary>
        /// Creates a program from the string passed and attaches it to a particular scope.
        /// </summary>
        /// <param name="s"></param>
        /// <param name="pScope">This parameter should be Scope.GetGlobal() for now </param>
        /// <returns></returns>
        public static Function MakeFunction(string s, Scope pScope)
        {
            return MakeNamedFunction(gStringUnnamed, s, pScope, "");
        }
        public static Function MakeNamedFunction(string sName, string sCode, Scope pScope, string sDesc)
        {
            Parser parser = new Parser();
            parser.Parse(sCode);
            AstNode node;
            List<Function> progs = new List<Function>();
            while ((node = parser.ExtractNode()) != null)
            {
                Function p = CreateFunctionFromNode(node, pScope);
                progs.Add(p);
            }
            Function prog = new Definition(progs, sName, pScope, sDesc);
            pScope.AddProgram(prog);
            return prog;
        }

        public static Function MakeFunction(string s)
        {
            return MakeFunction(s, Scope.Global());
        }

        #region static fields
        public static TypeInferer gpTypeInferer = new TypeInferer();
        #endregion

        #region Fields
        public List<Function> mpChildren;
        public string msName = "_unnamed_"; 
        public FxnType mpType; 
        public AstNode mpNode;
        public Scope mpScope = Scope.Global();
        public string msDesc = "";
        #endregion

        public Function()
        {
            mpType = null;
            mpNode = null;
            mpChildren = new List<Function>();
        }
        public string GetDesc()
        {
            return msDesc;
        }
        public bool IsNamed()
        {
            return msName != gStringUnnamed && msName.Length > 0;
        }
        public string GetFullName()
        {
            string result = "";
            if (mpScope.GetParent() != null)
            {
                result += mpScope.GetParent().GetFullName();
            }
            return result + msName;
        }
        public override string ToString()
        {
            if (msName == "_unnamed_")
            {
                return ToShortString();
            }
            else
            {
                return msName;
            }
        }
        public string ToShortString()
        {
            const int nMaxChildren = 3;
            string result = "{ ";
            for (int i = 0; (i < mpChildren.Count) && (i < nMaxChildren); ++i)
            {
                Function p = mpChildren[i];
                result += "@";
                result += p.ToString();
                result += " ";
            }
            if (mpChildren.Count > nMaxChildren)
            {
                result += "...";
            }
            result += "}";
            return result;
        }

        public abstract void AbstractExec();

        public void Exec()
        {
            AbstractExec();
        }
        public void SetType(string sType)
        {
            mpType = CatType.MakeCatType(sType) as FxnType;
            mpType.Initialize();
        }
        public FxnType GetFxnType()
        {
            return mpType;
        }

        public bool IsPure()
        {
            return mpType.IsPure();
        }
    }

    /// <summary>
    /// This represents a function defined by the user, as opposed 
    /// to a built in function or literal pushing function.
    /// </summary>
    public class Definition : Function
    {
        public Definition(AstNode pNode, Scope pScope)
        {
            Parser.AssertNodeType(pNode, NodeType.Definition);
            mpChildren = new List<Function>();

            if (pNode.children.Count == 2)
            {
                AstNode p = pNode.children[0];
                Parser.AssertNonEmptyName(p);
                msName = p.ToString();
                mpType = null;
                mpScope = new Scope(pNode.children[1], pScope);
            }
            else if (pNode.children.Count == 3)
            {
                // throw new Exception("Scoped definitions are not supported in this version");
                AstNode p = pNode.children[0];
                Parser.AssertNonEmptyName(p);
                msName = p.ToString();
                mpType = CatType.MakeCatType(pNode.children[1]) as FxnType;
                mpType.Initialize();
                mpScope = new Scope(pNode.children[2], pScope);            
            }
            else
            {
                Parser.Error(pNode, "badly formed parse node for a definition");
            }

            foreach (Object o in mpScope.GetInstructions())
            {
                if (o is Function)
                    mpChildren.Add(o as Function);
            }

            // type checking and inference code
            if (mpType != null && Config.gbStaticTyping)
            {
                try
                {
                    FxnType f = gpTypeInferer.InferType(this);
                    if (!f.IsTypeEq(mpType))
                    {
                        throw new Exception("expected type " + mpType.ToString() + " but inferred type " + f.ToString()); 
                    }
                }
                catch (Exception e)
                {
                    throw new Exception("Type checking error in " + msName + " : " + e.Message);
                }
            }
            else
            {
                try
                {
                    if (Config.gbStaticTyping)
                    {
                        mpType = gpTypeInferer.InferType(this);
                        if (Config.gbLogTypeInference)
                            Console.WriteLine("inferred type for program '" + msName + "' as " + mpType.ToString());
                    }
                }
                catch (Exception e)
                {
                    throw new Exception("Type inference error in " + msName + " : " + e.Message);
                }
            }
        }

        public Definition(List<Function> pChildren, string sName, Scope pScope, string sDesc)
        {
            mpScope = new Scope(pScope);
            msName = sName;
            msDesc = sDesc;
            mpChildren = pChildren;
            try
            {
                if (Config.gbStaticTyping)
                {
                    mpType = gpTypeInferer.InferType(this);
                }
                else
                {
                    mpType = null;
                }
            }
            catch (Exception e)
            {
                Console.WriteLine("Uncaught type inference error occured in program " + msName);
                Console.WriteLine(e.Message);
            }
        }

        public Definition(List<Function> pChildren, string sName, Scope pScope) 
            : this(pChildren, sName, pScope, "")
        {
        }

        public override void AbstractExec()
        {
            foreach (Function p in mpChildren)
            {
                p.Exec();
            }
        }

        public override string ToString()
        {
            return base.ToString();
        }
    }

    /// <summary>
    /// Represents an integer literal. That is a function which pushes 
    /// an integer onto the stack.
    /// </summary>
    public class IntLiteral : Function
    {
        int mnValue;        
        public IntLiteral(int x) 
        {
            msName = x.ToString();
            // TODO: compute this and other functions once statically
            SetType("() -> (int)");
            mnValue = x;
        }
        public override void AbstractExec() 
        { 
            Executor.PushInt(mnValue);
        }
        public override string ToString()
        {
            return msName;
        }
        public int GetValue()
        {
            return mnValue;
        }
        public MethodInfo GetMethodInfo()
        {
            return typeof(Executor).GetMethod("PushInt");
        }
    }

    /// <summary>
    /// This is the class representing string literals. That is a function
    /// which pushes a string onto the stack.
    /// </summary>
    public class StringLiteral : Function
    {
        string msValue;
        public StringLiteral(string x) 
        {
            msName = x;
            msValue = x.Substring(1, x.Length - 2);
            SetType("() -> (string)");
        }
        public override void AbstractExec()
        {
            Executor.PushString(msValue);
        }
        public string GetValue()
        {
            return msValue;
        }
        public MethodInfo GetMethodInfo()
        {
            return typeof(Executor).GetMethod("PushString");
        }
    }

    /// <summary>
    /// This class represents a token which is a reference to a function (e.g. @MyFunction)
    /// which results in the function being pushed onto the stack, as opposed to being 
    /// executed immediately.
    /// </summary>
    public class ReferenceOp : Function
    {
        Function value;
        public ReferenceOp(Function p) 
        {
            msName = "@" + p.msName;
            SetType("()->(" + p.GetFxnType().ToString() + ")");
            value = p;
        }
        public override void AbstractExec()
        {
            Executor.main_stack.Push(value);
        }
        public override string ToString()
        {
            return msName;
        }
        public Function GetValue()
        {
            return value;
        }
        public MethodInfo GetMethodInfo()
        {
            return typeof(Executor).GetMethod("PushReference");
        }
    }

    /// <summary>
    /// A quotation is an anonymous function, which is pushed onto the stack
    /// rather than executed. 
    /// </summary>
    public class Quotation : Function
    {
        private Definition prog;

        public Quotation(AstNode pNode, Scope pScope)
        {
            Parser.AssertNodeType(pNode, NodeType.Quotation);
            msName = "[...]";
            mpScope = new Scope(pScope);
            List<Function> progs = new List<Function>();
            foreach (AstNode child in pNode.children)
            {
                progs.Add(CreateFunctionFromNode(child, mpScope));
            }
            
            prog = new Definition(progs, "_unnamed_", pScope);

            if (Config.gbStaticTyping)
            {
                mpType = new FxnType(true);
                mpType.GetMainProdStack().Push(prog.GetFxnType());
                mpType.Initialize();
            }
        }

        public override string ToString()
        {
            string result = "[ ";
            foreach (Function p in prog.mpChildren) 
            {
                result += "@";
                result += p.ToString();
                result += " ";
            }
            result += "]";
            return result;
        }

        public override void AbstractExec()
        {
            Executor.Push(prog);
        }

        public List<Function> GetChildren()
        {
            return prog.mpChildren;
        }

        public Definition GetDefinition()
        {
            return prog;
        }
    }

    /// <summary>
    /// This class is not yet used. 
    /// </summary>
    public class ComposedFunction : Function
    {
        public ComposedFunction(ArrayList a, Scope scope) 
        {
            msName = "_composed_fxn_";
            mpScope = scope;
            foreach (Object o in a)
            {
                if (o is Function)
                    mpChildren.Add(o as Function);
                else
                    throw new Exception("Composed function requires a lookup of programs");
            }
        }
        public override void AbstractExec()
        {
            foreach (Function p in mpChildren)
                p.Exec();
        }
    }
}

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
Web01 | 2.8.140921.1 | Last Updated 4 Nov 2006
Article Copyright 2006 by Christopher Diggins
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid