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

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 scope class holds definitions and definition lookup tables. 
    /// Every program and type is associated with a single scope. 
    /// The current implementation of Cat does not support nested scopes, so 
    /// for the time being everything shares the global scope. 
    /// 
    /// The inclusion of non-static Scope objects lays the groundwork for extending 
    /// Cat with the idea of nested functions and namespaces. These are very important 
    /// concepts for non-trivial software development. 
    /// </summary>
    public class Scope
    {
        #region fields
        private string msName = "";
        private List<Scope> mpChildren = new List<Scope>();
        private List<Function> mpDefinitions = new List<Function>();
        private List<Function> mpInstructions = new List<Function>();
        private Scope mpParent;
        private Dictionary<string, Function> mpHash = new Dictionary<string, Function>();
        static Scope gpGlobal = new Scope();
        #endregion

        #region constructors
        public Scope(AstNode node, Scope parentScope)
        {
            if (node.node_type == NodeType.Namespace)
            {
                Parser.AssertNodeChildCount(node, 2);
                Parser.AssertNonEmptyName(node.children[0]);
                msName = node.children[0].ToString();
                node = node.children[1];
            }
            else 
            {
                msName = "";
            }

            mpChildren = new List<Scope>();
            mpParent = parentScope;
            
            Parser.AssertNodeType(node, NodeType.BraceGroup);
            foreach (AstNode child in node.children)
            {
                ProcessNode(child);
            }
        }

        public Scope(Scope parentScope)
        {
            mpChildren = new List<Scope>();
            mpParent = parentScope;
        }

        public Scope()
        {
            mpChildren = new List<Scope>();
        }
        #endregion

        #region static functions
        /// <summary>
        /// The global scope represents all top-level definitions.
        /// </summary>
        public static Scope Global()
        {
            return gpGlobal;
        }
        #endregion

        #region public functions
        public Scope GetParent()
        {
            return mpParent;
        }
        public string GetName()
        {
            return msName;
        }

        public bool IsNamed()
        {
            return msName.Length > 0;
        }

        public string GetFullName()
        {
            string result = "";
            if (mpParent != null)
            {
                result += mpParent.GetFullName();
            }
            if (IsNamed())
            {
                result += msName + ".";
            }
            return result;
        }

        public Function ThrowingLookupProgram(string s)
        {
            Function result = LookupProgram(s);
            if (result == null) throw new Exception("unable to find program " + s);
            return result;
        }

        /// <summary>
        /// I am not sure about this function. It has certain problems. 
        /// There is not enough looking up, things like literals are always created 
        /// Just an efficiency issue I guess. The other potential problem is the placement.
        /// It seems to do too many things, and in the wrong place. I would have to think about
        /// this more though.
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public Function LookupProgram(string s)
        {
            if (s.Length < 1) return null;
            if (s[0] >= '0' && s[0] <= '9')
            {
                int n = int.Parse(s);
                return new IntLiteral(n);
            }
            if ((s[0] == '"') && (s.Length > 1))
            {
                return new StringLiteral(s);
            }
            Function result = null;
            if (s.IndexOf('.') > 0)
            {
                string[] sScopes = s.Split(new char[] { '.' }, 2);
                string sScope = sScopes[0];
                string sProgram = sScopes[1];
                Scope pScope = LookupScope(sScope);
                if (pScope != null) result = pScope.LookupProgram(sProgram); 
            }
            else
            {
                if (mpHash.ContainsKey(s))
                {
                    result = mpHash[s];
                }
            }
            if (result == null)
            {
                if (mpParent != null)
                {
                    result = mpParent.LookupProgram(s);
                }
            }
            return result;
        }

        public Scope LookupScope(string s)
        {
            if (mpParent != null)
            {
                return mpParent.LookupScope(s);
            }
            else
            {
                foreach (Scope child in mpChildren)
                {
                    if (child.msName == s)
                    {
                        return child;
                    }
                }
                return null;
            }
        }
        
        // Finds a program from a name returning null if not found
        public Function LookupProgramLocally(string s)
        {
            if (s.Length == 0) { throw new Exception("Looking up function with no name"); }
            // In the case of numbers literals the program is generated on the fly.
            if ((s[0] >= '0') && (s[0] <= '9'))
            {
                return new IntLiteral(Parser.StringToInt(s));
            }
            if (s[0] == '"')
            {
                return new StringLiteral(s);
            }
            return mpHash[s] as Function;
        }
               
        public Scope NewNamespace(AstNode node)
        {
            Scope result = new Scope(node, this);
            mpChildren.Add(result);
            return result;
        }

        public void Clear()
        {
            mpDefinitions.Clear();
            mpChildren.Clear();
            mpHash.Clear();
        }

        public Function AddProgram(Function p)
        {
            mpDefinitions.Add(p);
            mpHash[p.msName] = p;
            return p;
        }

        public Function NewReference(AstNode node)
        {
            // TODO: this algorithm doesn't allow for references to anonymous functions.
            if ((node == null) || (node.node_type != NodeType.Reference) || (node.children.Count != 1))
            {
                throw new Exception("Internal Error: expected reference node with one child");
            }
            AstNode child = node.children[0];
            string name = child.ToString();
            Function p = LookupProgramLocally(name);
            Function result = new ReferenceOp(p);
            mpInstructions.Add(result);
            return result;
        }

        public Function NewDefinition(AstNode node)
        {
            Definition result = new Definition(node, this);
            AddProgram(result);
            return result;
        }

        public Scope NewScope(AstNode node)
        {
            Scope result = new Scope(node, this);
            mpChildren.Add(result);
            return result;
        }

        public Quotation NewQuotation(AstNode node)
        {
            Quotation result = new Quotation(node, this);
            AddProgram(result);
            mpInstructions.Add(result);
            return result;
        }

        public List<Function> GetInstructions()
        {
            return mpInstructions;
        }

        public List<Function> GetDefinitions()
        {
            return mpDefinitions;
        }

        public List<Scope> GetChildren()
        {
            return mpChildren;
        }

        public void ProcessNode(AstNode node)
        {
            switch (node.node_type)
            {
                case NodeType.Definition:
                    NewDefinition(node);
                    break;
                case NodeType.Quotation:
                    NewQuotation(node);
                    break;
                case NodeType.Namespace:
                    NewNamespace(node);
                    break;
                case NodeType.BraceGroup:
                    NewScope(node);
                    break;
                case NodeType.ParanGroup:
                    throw new Exception("paranthesized expressions not implemented");
                case NodeType.Reference:
                    NewReference(node);
                    break;
                default:
                    mpInstructions.Add(ThrowingLookupProgram(node.ToString()));
                    break;
            }
        }        
        #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.141022.2 | Last Updated 4 Nov 2006
Article Copyright 2006 by Christopher Diggins
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid