Object Oriented Nested Dictionary Data Structure

Question

I'm attempting to create an abstract syntax for a lisp style plist. For example:

(:A 1 :B (:X 3 :Y 2) :C 4)

Here's the grammar so far (in EBNF):

Plist -> { Key Value }*
Key -> string
Value -> string | Plist

I need to represent this data structure in C#. Unfortunately, I'm struggling to create classes for the nonterminals. This seems trivial in a dynamically typed language like python (dict with values that are either strings or dicts). But in C#, how can the user of the data structure know if a value is a plist or a string in a polymorphic way?

Here's the C# code I have so far:

interface Value { }

class PList : Value
{
    private Dictionary<string, Value> Dict;

    public Value this[string key]
    {
        get
        {
            return Dict[key];
        }
    }
}

class String : Value
{
    public string Datum { get; set; }
}

Answer 1

You're definitely on the right track. The pattern you are trying to use is the Composite Pattern. In this pattern the common behavior or a common abstraction is used for the leaves and internal nodes(both in trees and here in your example). Then the abstraction is used in the composite like so:

public interface IValue
{
    public void OperationOnValue();
    public List<IValue> GetChildren();
}

public class CompositePList : IValue
{
    private Dictionary<string, IValue> dict;

    public void OperationOnValue()
    {
        foreach(var things in dict)
        {}//things to do
    }

    public List<IValue> GetChildren()
    {
        return dict.Select(keyValue => keyValue.Value).ToList();
    }
}

public class StringValue : IValue
{
    private string leafValue;
    public void OperationOnValue()
    {}//thing to do

    public List<Children> GetChildren()
    {
        return null; //or return new List<Children>()
    }
}

With this design you can have a root IValue and then polymorphically call OperationOnValue() on it. Is there any more functionality you have in mind?