LINQ to YAML

LINQ to XML is one of the many technologies introduced with the .NET Framework 3.5, and one that is certainly a step forward in terms of usability. It allows querying in both the functional style (using LINQ and lambda expressions) and the more traditional imperative one, meaning that it’s a great tool for concisely working with XML data in any sort of application, and undoubtedly a significant improvement over the old XML DOM that resides in the System.Xml namespace.

In the spirit of LINQ, and with the advent of YAML, I recntly decided it was about time that this new “markup language” were integrated with LINQ. Surprisingly, there does not already exist anything akin to LINQ to YAML out there (though there are a couple of fairly usable implementations of a YAML reader/writer for .NET). This seemed to me like a good chance to potentially create something that might be used by more than the odd .NET developer or two. My plans are to implement a LINQ to YAML provider either from scratch or on top of one of the existing YAML libraries. (Which option I choose will depend on the state of the existing projects, which I haven’t yet investigated properly. I am however suspecting that it might be worthwhile writing my own, since it would a) teach me all the intricacies of YAML, and b) allow me to support the latest version [1.2], which the existing libraries do not.)

Before I launch into an overview of my intended implementation, here is a little bit about YAML itself, for those who aren’t already familiar with it. Although technically YAML isn’t a markup language (after all, the recursive acronym stands for YAML Ain’t Markup Language) – it is rather a serialisation format – it does essentially fulfill the the role that XML  traditionally has, in a variety of common situations. I’m not going to try to sell the format to you right now, but it should suffice to say that you wouldn’t have reached this far in the post if you weren’t already at least intrigued! Without doubt, the format is actively gaining popularity because of it’s ultra-lightweight syntax and suitability for hand editing, perhaps the two points that summarise its advantages over XML.

Anyway, here’s a short example of a YAML document (taken straight from the Wikipedia page), so you can see precisely how pleasant it is to work with (at least for humans).

—

receipt:     Oz-Ware Purchase Invoice
date:        2007-08-06
customer:
    given:   Dorothy
    family:  Gale

items:
    - part_no:   A4786
      descrip:   Water Bucket (Filled)
      price:     1.47
      quantity:  4

    - part_no:   E1628
      descrip:   High Heeled "Ruby" Slippers
      price:     100.27
      quantity:  1

bill-to:  &id001
    street: |
            123 Tornado Alley
            Suite 16
    city:   East Westville
    state:  KS

ship-to:  *id001

specialDelivery:  >
    Follow the Yellow Brick
    Road to the Emerald City.
    Pay no attention to the
    man behind the curtain.
...

Of course, the great thing about YAML, which is demonstrated clearly by this example, is that you don’t have to have any real knowledge about YAML to understand exactly and immediately what the data represents, and as a bonus it doesn’t hurt your eyes to stare at for too long! Even the referencing syntax should be fairly self evident. (&id00 and *id001 would surely be nothing new to C programmers.)

The semantics as well as the syntax of YAML obviously differ to those of XML greatly, although there is almost always some sort of correspondence between the features and possibilities that the two formats offer. The only notable missing feature when contrasted to XML is attributes, yet their usefulness is questionable anyway.

Right, so now I ought to explain a bit about how I actually plan to design this library. The basic framework will be virtually equivalent to that of LINQ to XML. In other words, the hierarchy will be largely based around an abstract YamlObject (YObject?) class, and will look very much like the one contained within System.Xml.Linq.

LINQ to XML class hierarchy

Though LINQ to YAML must of course accomodate for the unique nature of the format, I would initially aim for minimal difference and only significantly adjust the hierarchy when it is found to be necessary. Classes such as XCData and XDocumentType would not apply at all to YAML, yet there would need to be a place for a YReference or such somewhere in the hierarchy. The referencing aspect of YAML will likely prove to be one of the more interesting challenges; while YAML’s lists, maps (dictionaries), and combinations thereof would seem relatively straightforward with regards to emulation of the LINQ to XML design, references would introduce a substantially novel concept. Some sort of implementation of lazy evaluation followed by concrete referencing should be able to solve the problem, but there’s no way to predict how well this might work in practice at this moment.

What I realised only after deciding to create a LINQ to YAML library is that among LINQ providers, LINQ to XML is somewhat special in that the LINQ aspect of it is built on top of LINQ to Objects (i.e. LINQ using IEnumerable<T> objects), with only a relatively small number of extension methods specific to LINQ to XML. Indeed, most LINQ providers (LINQ to Objects and LINQ to SQL among others) require you to implement the IQueryable and IQueryProvider interfaces to provide complex logic for interpreting and returning the results of expressions, as well as evaluating complex expression trees.  All this means that I can pretty much just design a DOM  to a certain style (i.e. one suited to functional code, like LINQ to XML), and let LINQ to Objects to everything else for me.

As I can’t think of anything more worth mentioning about my project at this time, I shall leave any more specific and complex details to a future post. Still, do by all means feel free to query me about my plans – I would be glad to answer any questions, and even gladder to receive some suggestions as how you think I might design LINQ to YAML, or simply a nod that you might find this useful at some point. I don’t anticipate this project to be a very long one, though I must say that both my work and free-time schedule are likely to be fairly messed up for the next month or two, therefore I’m not going to promise when I’ll get around to my initial release. Whenever it so happens, I will duly post the link to the project page on Launchpad (or wherever I decide to host it).

Strongly-Typed CSV Reader in C#

As part of a project on which I’ve recently started working, I found it necessary to write a class that reads entries from CSV files. Such a simple format, you might think, so why would I bother sharing such trivial code? Indeed, it is a relatively short class, but I thought I’d post it here nonetheless, primarily because I believe its usage promotes a design practice of which I am particularly fond, and I suspect (hope) other people may appreciate as well. There are also a few bits of code that might be considered interesting (and unusual) from a language/design perspective.

When I decided to formalise the logic for reading from CSV files, I firstly thought it would be nice to write something in the spirit of .NET 3.5 – in this case, easily compatible with LINQ, fully generic (strongly-typed), and attribute-oriented (as seems to be the trend in APIs nowadays). Before I launch into any further discussion, here’s the code for the class in full.

using System;
using System.ComponentModel;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Text;

namespace NetworkAnalyser
{
    public class CsvReader<TEntry> : IDisposable where TEntry : struct
    {
        private StreamReader streamReader;
        private FieldTypeInfo[] fieldTypeInfos;

        private bool isDisposed = false;

        public CsvReader(string path)
        {
            streamReader = new StreamReader(path);
            Initialize();
        }

        public CsvReader(Stream stream)
        {
            streamReader = new StreamReader(stream);
            Initialize();
        }

        ~CsvReader()
        {
            Dispose(false);
        }

        public void Dispose()
        {
            Dispose(true);
            GC.SuppressFinalize(this);
        }

        protected virtual void Dispose(bool disposing)
        {
            if (!isDisposed)
            {
                if (disposing)
                {
                    if (streamReader != null)
                        streamReader.Dispose();
                }
            }

            isDisposed = true;
        }

        public IEnumerable<TEntry> ReadAllEntries()
        {
            TEntry? entry;
            while ((entry = ReadEntry()).HasValue)
                yield return entry.Value;
        }

        public TEntry? ReadEntry()
        {
            var line = streamReader.ReadLine();
            if (line == null)
                return null;

            var entry = new TEntry();
            var fields = line.Split(new char[] { ',' }, StringSplitOptions.None);
            FieldTypeInfo fieldTypeInfo;
            object fieldValue;

            for (int i = 0; i < fields.Length; i++)
            {
                fieldTypeInfo = fieldTypeInfos[i];
                fieldValue = fieldTypeInfo.TypeConverter.ConvertFromString(fields[i].Trim());
                fieldTypeInfo.FieldInfo.SetValueDirect(__makeref(entry), fieldValue);
            }

            return entry;
        }

        private void Initialize()
        {
            var entryType = typeof(TEntry);
            fieldTypeInfos = (from fieldInfo in entryType.GetFields(BindingFlags.Instance |
                                  BindingFlags.Public)
                              let fieldTypeConverterAttrib = fieldInfo.GetCustomAttributes(
                                  typeof(TypeConverterAttribute), true).SingleOrDefault()
                                  as TypeConverterAttribute
                              let fieldTypeConverter = (fieldTypeConverterAttrib == null) ? null :
                                  Activator.CreateInstance(Type.GetType(
                                      fieldTypeConverterAttrib.ConverterTypeName))
                                  as TypeConverter
                              select new FieldTypeInfo()
                              {
                                  FieldInfo = fieldInfo,
                                  TypeConverter = fieldTypeConverter ??
                                      TypeDescriptor.GetConverter(fieldInfo.FieldType)
                              }).ToArray();
        }

        private struct FieldTypeInfo
        {
            public FieldInfo FieldInfo;
            public TypeConverter TypeConverter;
        }
    }
}

(Please excuse the utter lack of comments in the code. Most of it is self-explanatory, but admittedly some parts are probably not. I put it together pretty quickly, but I may get around to commenting it some time soon. Some basic error handling might also be nice.)

At this point it may seem rather excessive just to read data from a CSV file, but I hope you’ll agree that it’s worthwhile once you see an example of typical usage.

The first step is to define a structure (struct) that holds each entry in memory. Here we’re going to define one that holds some basic information about a programming language.

public struct LanguageEntry
{
    public string Name;
    public string[] Paradigms;
    public string LatestVersion;
    [TypeConverter(typeof(CustomDateTimeConverter))]
    public DateTime InitialRelease;
    [TypeConverter(typeof(CustomDateTimeConverter))]
    public DateTime LatestRelease;
    public float Popularity;
}

The TypeConverter attributes are completely optional, and are only required when you’re reading some fields that have unusual formats and whose values you would like to convert to something simpler/more accessible (e.g. a string “Jun2002″ to a DateTime object in this case). For any field of a type recognisable by the default type converter, you don’t need to bother, as is shown for the double type. (This actually applies to a very large range of types within the BCL, including System.Drawing.Color, which can be specified in any format that you might use in the propeprty editor of Visual Studio, such as “DarkRed”.)

Finally, here’s a snippet to show how you might actually use the CsvReader<TEntry> class to read from a CSV file. This example reads all entries from the languages.csv file and prints out to the console the names of all functional languages.

using (var languagesReader = new CsvReader<LanguageEntry>("language.csv"))
{
    var languages = from lang in languagesReader.ReadAllEntries()
                    where lang.Paradigms.Contains("Functional")
                    select lang;
    foreach (var lang in languages)
        Console.WriteLine(lang.Name);
}

Hopefully that’s now convinced you that this is the right way to go about reading data entries from files. What this class provides is completely strongly-typed I/O (reading in this case, though it wouldn’t be very hard to create a similar CsvWriter class), and a declarative manner to defining entry types (or records, to use database termninology).

I’m not going to delve too deeply into the implementation of the class, but I think it’s worth highlighting a few specifics. Going back to the code for the class, the first thing to notice is the Initialize method – this is where much of the interesting stuff is happening. To summarise: it loops over all the public fields of the type specified by TEntry, gets the default type converter for the type of each field (or the one given by TypeConverterAttribute, if it exists), and then stores the FieldInfo along with the TypeConverter in a simple struct. The only other noteworthy point is the call to SetValueDirect in the ReadEntry method. This uses a keyword that’s almost wholly unknown (and undocumented!) to C# developers by the name of __makeref (there are other related ones by the names of __reftype and __refvalue) – I was certainly unaware of it before today. The problem that I initially encountered was one of using the SetValue method, which works perfectly well on classes, but presents a unique problem with structs: namely, because they are value-types, and the obj parameter is of type object, the argument must be boxed (wrapped into a reference type) and placed on the heap rather than the stack, meaning that the heap-based copy gets altered, and not the one you passed to the method (which is on the stack)! What the __makeref keyword does is create a TypeReference that directly references the stack-based object and thus allows SetValueDirect to set the field accordingly.

That’s enough explanation, I think. If you still aren’t sure about how it works precisely, then feel free to comment on this post. I’d also be quite happy to hear what anyone thinks of the general design and implementation, too.

Combining Ordered Lists in .NET

I recently came across an issue with LINQ involving the combination of ordered (sorted) lists. The problem does not seem to have a simple solution within the core libraries of .NET 3.5, so I decided to write my own (short) function to accomplish the task. Extensions methods and the static Enumerable class usually contain all the possible methods you might need for dealing with lists (or more generally enumerable collections). Combining ordered lists, however, isn’t quite so straightforward a process (to do efficiently) as it might first seem. Of course, you could simply do Enumerable.Concat(listA, listB).OrderBy(keySelector) but it should be apparent that this is very inefficient for large lists if you know your lists are already ordered. Moreover, the call will never return if either or both of the enumerable collections you pass are of infinite length. What you really want to do is select items from the lists by switching back and forth between them, picking whichever of the next items ought to come first (which is determined by the key selector and associated IComparable implementation).

public static IEnumerable<TSource> CombineOrdered<TSource, TKey>(this IEnumerable<TSource> first,
    IEnumerable<TSource> second, Func<TSource, TKey> keySelector) where TKey : IComparable<TKey>
{
    var firstEnumerator = first.GetEnumerator();
    var secondEnumerator = second.GetEnumerator();
    var firstCanAdvance = firstEnumerator.MoveNext();
    var secondCanAdvance = secondEnumerator.MoveNext();
    var firstCurKey = keySelector(firstEnumerator.Current);
    var secondCurKey = keySelector(secondEnumerator.Current);

    while (true)
    {
        if (firstCanAdvance && (!secondCanAdvance || firstCurKey.CompareTo(secondCurKey) <= 0))
        {
            yield return firstEnumerator.Current;
            firstCanAdvance = firstEnumerator.MoveNext();
            if (firstCanAdvance) firstCurKey = keySelector(firstEnumerator.Current);
        }
        else if (secondCanAdvance)
        {
            yield return secondEnumerator.Current;
            secondCanAdvance = secondEnumerator.MoveNext();
            if (secondCanAdvance) secondCurKey = keySelector(secondEnumerator.Current);
        }
        else
        {
            yield break;
        }
    }
}

To use the function, for example within a static class named Enumerable2, you can call it as such:

var combinedList = Enumerable2.CombineOrdered(listA, listB, keySelector);

Note: The given implementation needs to take lists sorted in an ascending order and returns a combined list in the same order. To sort descending, change the <= sign to a >= sign in the code and insure that you pass lists sorted in a descending order.

Querying the Semantic Web

Although the Semantic Web is yet in its infancy and has a long way to go before widespread adoption, the evolution of some of its projects is finally starting to enable some interesting applications. DBpedia now provides a semantic framework for accessing much (though far from all) of the data in the 2.5 million articles currently on Wikipedia. Other projects are attemping to create semantic databases of music, books, geography, and photos, to name some of the larger ones. If you’re not very familiar with the concept of the Semantic Web, I recommend the Wikipedia article as a good introduction, though for the purposes of this post you won’t need to know the details. In summary, the eventual goal of the Semantic Web is to create a huge interlinked web of knowledge that can be accessed and utilised by computers for all sorts of tasks. This would ultimately enable a computer to perform most of the actions humans can currently perform on the WWW, such as researching knowledge, making bookings, or ordering products from online companies.

Having done some research into the current state of the Semantic Web, I have recently been considering the (admittedly rather ambitious) idea of querying the semantic web with human-language questions. The plan is to make use of two great sources of semantic data, DBPedia and WordNet (a lexical database of the English language) to give precise answers to advanced questions, similar to the Ask.com service but much more “intelligent”. The former allows a program to access an enormous amount of encyclopaedic information while the latter provides detailed specific information about the meanings of words and expressions in the English language. The data is accessible in RDF format and can be queried via SPARQL (an SQL-like language). RDF is the standard model for representing semantic data, consisting of simple statements called triples (see the RDF link for a detailed explanation). Combined with the appropiate AI, a computer could (at least in theory) answer any question contained, either explicitly or implicitly, by the contents of Wikipedia. The aim is to allow a person to enter a complex question in English and receive an accurate response (or set of ranked responses) from the system, displayed in whichever way is most appropiate. Examples of such questions are:

• “When was Microsoft founded and where are its current headquarters?”
• “Who succeeded Octavian as Emporer of Rome and when was he born?”
• “List all of the papers published by Albert Einstein in 1905.”
• “Through which countries do the Alps pass?”
• “Give me a list of all the computers costing more than £1000 manufactured by Dell between 1998 and 2000.”

It is clear that translating queries like these into computer-understandable ones is far from a simple process and will require a significant level of AI. Some can be directly queried against RDF with hardly any further processing but others will need some form of machine logic (to perform simple numerical or set operations, for example).

It is important to note that there are a few major obstacles to creating such a system and allowing it to achieve high accuracy, though some of them can be at least partially resolved by human training. Such training or evolution of the system could be accomplished effectively by making question askers utilise a user-interface that provides feedback.

1. Human languages are inherently ambiguous methods of communication. Any algorithm used to interpret queries will necessarily involve a probabilistic model to resolve ambiguities. Also, more intricately phrased questions can be very difficult for AI to comprehend. A user would ideally use as simple and direct language as possible.
2. DBpedia in its current form does not express in a semantic form a very large proportion of the information contained by Wikipedia since much of it is given in continuous prose. However, improvements in the quantity and density of information in DBpedia articles are likely to come in the near future as Wikipedia and the Semantic Web continue their growth. The system could additionally be expanded to search within other databases of knowledge apart from Wikipedia, such as Geonames and MusicBrainz.
3. Similarly, WordNet is an incomplete lexical database of the English language; some words/expressions and links between them will inevitably be missing or poorly defined.
4. There is no easy way to link the objects and concepts defined by WordNet to those in Wikipedia/DBpedia. In fact, it could prove all but impossible to do so without the aid of humans (or a very advanced and currently infeasable level of AI.) Still, there are various solutions to this issue and the topic will be a main focus point in upcoming posts.
5. The processing or even actual intelligence required to accurately answer certain questions may be too great in certain cases. This does not present as big a problem as some of the other points, though it is desirable that either the human questioner or the AI recognises when a question is obviously unanswerable. An example of such a question would be:
   “What was the mean average speed of computer processors between 1990 and 1995?”
   Although there is a possibility that Wikipedia or other databases of knowledge implicitly contain the answer to such a query, it would require a very high degree of intelligence to answer it, which goes far beyond the purpose of the system. It should also be noted that this condition may not be differentiable to that where the information is not contained by the knowledge base. Questions which require opinionated replies however ought to be recognisable upon querying WordNet but before searching the knowledge base.

This post is only meant to be an introduction to my currently half-formed project idea of querying the semantic web for encyclopaedic information. I plan to discuss the details of high-level implementation in a series of following posts as I begin and continue work on this project. These posts ought to mainly include conceptual diagrams and images with explanations, plus some rare short snippets of code. I firmly believe that getting bogged down in low-level implementation details will not offer a good understanding of the system and should only serve to clarify key ideas. Explaining the architecture will be the focus of the series and certainly ought to fill enough posts! The project will become open-source once it (with  with any luck) reaches the first development milestone, which I will define at a later date. Current plans are to carry out development in C#/.NET 3.5 using LinqToRDF to query RDF data.

Well, that’s all for now, but hopefully you now have a general understanding of the the core ideas. Comments on any aspect of the project are welcome.