14 April 2006

In the last entry we successfully derived a double-linked list implementation from a single-linked list implementation, but we had to use casts to get it to compile. What we want to do now is see if we can remove the casts.

We will first remove the cast in the Backwards method.

        DoubleNode current = (DoubleNode)Last;

The reason we need the cast is because the base class defines Last to be

        protected Node Last { get { return _last; } }

What we need is the type to be DoubleNode, but this property is defined in a descendent class. To allow us to change the type we need to leave the type open, or, in other words,  add the node type as a type parameter. To accomplish this, I replaced all references to the node type with a type parameter. The new LinkedList class looks like,

    class LinkedList<T, NodeType>: IEnumerable<T>, ILinkedList<T>
        where NodeType: LinkedList<T, NodeType>.Node, new() {

        public class Node {
            private T _data;
            private NodeType _next;

            public T Data {
                get { return _data; }
                set { _data = value; }
            }
            public virtual NodeType Next {
                get { return _next; }
                set { _next = value; }
            }
        }

        NodeType _last;

        public void Add(T value) {
            NodeType newNode = new NodeType();
            newNode.Data = value;
            if (_last == null) {
                _last = newNode;
                newNode.Next = newNode;
            }
            else {
                newNode.Next = _last.Next;
                _last.Next = newNode;
                _last = newNode;
            }
        }

        public void Clear() {
            _last = null;
        }

        public IEnumerator<T> GetEnumerator() {
            if (_last != null) {
                NodeType current = _last;
                do {
                    current = current.Next;
                    yield return current.Data;
                } while (current != _last);
            }
        }

        IEnumerator IEnumerable.GetEnumerator() {
            return GetEnumerator();
        }

        protected NodeType Last {
            get { return _last; }
        }
    }

The where clause looks complicated but what it says is that NodeType's actual parameter must derive from the Node type defined in the class. This allows me to use the properties defined for the node class on variables of type NodeType. The new() part says that the actual parameter must also have a default constructor. This allows us to remove the CreateNode() method.

Unfortunately, this definition is a bit difficult to use because you need to define a node class to pass as a parameter. To make this easier, I defined a single parameter version,

    class LinkedList<T>: LinkedList<T, LinkedList<T>.MyNode> {
        public class MyNode: Node { }
    }

I implemented the double-linked list as,

    class DoubleLinkedList<T, NodeType>: LinkedList<T, NodeType>, IDoubleLinkedList<T>
        where NodeType: DoubleLinkedList<T, NodeType>.DoubleNode, new() {

        public class DoubleNode: Node {
            NodeType _previous;

            public override NodeType Next {
                get {
                    return base.Next;
                }
                set {
                    base.Next = value;
                    value._previous = (NodeType)this;
                }
            }

            public NodeType Previous { get { return _previous; } }
        }

        public IEnumerable<T> Backwards {
            get {
                if (Last != null) {
                    NodeType current = Last;
                    do {
                        yield return current.Data;
                        current = current.Previous;
                    } while (current != Last);
                }
            }
        }
    }

This looks almost identical to the previous DoubleLinkedList that I posted last time but it no longer needs a cast in Backwards. This is achieved by constraining types passed as NodeType to descend from DoubleNode instead of just Node. We can pass NodeType to LinkedList<T, NodeType> because the constrains on NodeType are compatible with the constraints for NodeType in LinkedList<T, NodeType>. I require that NodeType derive from DoubleNode which, itself, derives from Node. LinkedList<T, NodeType> requires NodeType to derive from Node; requiring it derive from DoubleNode ensures that is the case. I will also make this easier to use, like LinkedList<T, NodeType> above, by creating DoubleLink<T> from DoubleLink<T, NodeType>, as in,

    class DoubleLinkedList<T>: DoubleLinkedList<T, DoubleLinkedList<T>.MyNode> {
        public class MyNode: DoubleNode { }
    }

But, we still need a cast in the Next property. The reason we need it is, even though we know that NodeType derives from DoubleNode, the compiler only is sure that the type of the object itself is DoubleNode. It cannot prove that it must be a NodeType and there is no way in C# to declare that it must be. Currently, in C#, we are stuck with the cast. A couple languages have tried to deal with this problem. One such language is LOOM by Kim Bruce and others. LOOM allows declaring that a variable must be the same type as this. What that might look like in our example is the following,

        public class DoubleNode: Node {
            this _previous;

            public override NodeType Next {
                get {
                    return base.Next;
                }
                set {
                    base.Next = value;
                    value._previous = this;
                }
            }

            public this Previous { get { return _previous; } }
        }

where I assume that the keyword this is used where the type is assumed to be the type of this. This concept also shows up in Eiffel as like Current. Unfortunately, proving that NodeType and DoubleNode's this type are identitical is a non-trivial problem and has the side affect of adding exact typing to the language or leaves the type system unsound as Eiffel's like Current does.

Another approach is to constrain the decedents of DoubleNode to also to be decedents of NodeType. The only requirement we have on this is that it be assignable to a variable of type NodeType. If we could express that all concrete implementations of DoubleNode are required to be decedents of NodeType this requirement would be met. This is the approach that Scala, by Martin Odersky and others, took to the problem. What this might look like in C# is,

        public abstract class DoubleNode: Node requires NodeType {
            NodeType _previous;

            public override NodeType Next {
                get {
                    return base.Next;
                }
                set {
                    base.Next = value;
                    value._previous = this;
                }
            }

            public NodeType Previous { get { return _previous; } }
        }

This states that descendants of DoubleNode are required to also be decedents of type NodeType (or be NodeType, as is more likely the case). Knowing this we can then remove the cast of this because we are guaranteed it is assignment compatible with NodeType.

Whether either of these extensions make it into C# is anyone's guess. It is still open whether the solutions presented are really better than the problem. Is requiring the cast really that bad? I will leave that up to you to answer. Also I glossed over some tricky problems that would need to be addressed to implement either option, not the least of which are the changes to the CLR.

This all started off innocently enough. We wanted to implement

    interface ILinkedList<T>: IEnumerable<T> {
        void Add(T value);
        void Clear();
    }

and,

    interface IDoubleLinkedList<T>: ILinkedList<T> {
        IEnumerable<T> Backwards { get; }
    }

but things got complicated when we wanted to share code and remove casts. This innocent looking problem is devilishly hard to express in a type-checked object-oriented language.



blog comments powered by Disqus