Dynamic Domain Specific Languages in C# and the Quine

Wikipedia defines a quine as “a computer program that takes no input and produces a copy of its own source code as its only output”.  Some standard terms for this category of program are “self-replicating”, “self-reproducing”, and “self-copying” programs.  Quines are possible in any programming language.  The term quine, itself, was first coined in Douglas Hofstadter’s brilliant tome, “Gödel, Escher, Bach: An Eternal Golden Braid, in the honor of philosopher Willard Van Orman Quine (1908–2000), who made an extensive study of indirect self-reference, and in particular for the paradox-producing expression, known as Quine’s paradox.

A while back, I was on an experimental jag centered on seeing just how badly I could abuse .NET  dynamic dispatch capabilities.  Specifically, what kind of DSLs could we make with C# dynamic and what would be the nature of a Quine built to accommodate fully adhoc call chaining over dynamics.  Well, this led to a series of DSLs and built on the metaprogramming concepts that fell out this work.  In this article, I will introduce you to the first and simplest DSL in this series, EchoDSL.  Echo is not a pure quine, yet it is a simple framework for creating self-replicating code.

Here is a test demonstrating the usage of the Echo:


[TestMethod]
public void Testing_EchoDSL()
{
    var self_is = Echo._
                      .Hello("Joel").Your.Last.Name.Is["Holder"].You.Should.Record.This(foo: "bar")
                      .ToString();

    var should_be = ".Hello(\"Joel\").Your.Last.Name.Is[\"Holder\"].You.Should.Record.This(foo: \"bar\")";

    Assert.AreEqual(self_is, should_be);
}

As you can see we just kind of told Echo what it should repeat back to us, but the important thing is that we expressed that in source code.  The source is both legal C# and code that is obviously legal in the domain specific language itself.  To the point, in Echo, chained code that is syntactically legal in C#, it will happily convert to stringified source code and give back to you with a simple ToString() call.  The sheer meta”ness” of this may not be apparent on its face.  Let’s a try a more aggressive usage of Echo.


[TestMethod]
public void Testing_EchoDSL2()
{
    var self = Echo._
                   .In.Order.To.Create.An.Apple.Pie.From.Scratch(", ")
                   ["You "].Must.First.Invent.The.Universe
                   .You().Should().Record.This.too(foo: "bar")[""][""]
                   [" ... wait what just happened!. "]["magic must have occurred."].LOL.lfmao
                   .terms_can_comeIn_any_ORDER(question1: "is there anything it won't tolerate?",
                                               answer1: "apparently not",
                                               question2: "what is the meaning of life?",
                                               answer2: 42)
                   .And["please don't feed the monkies"]
                   .And("don't stare at the gorrilla")
                   .He.will(think: "you").are["challenging"].him
                   .Or.At_worst_he_will_think_you_are_a(suitable: "mate").Or.
                   I.Could.Go.On.To["other things"].like().monkey.chicken(".")["cow"]
                   .IMean("it")["!!!"].NoReally["..."].Ok.Fine("!")["  Go_Ahead"].
                   And["Do_Whatever you"].Want().to;

    var self_is = self.ToString();
    var should_be = ".In.Order.To.Create.An.Apple.Pie.From.Scratch(\", \")[\"You \"].Must.First.Invent.The.Universe.You().Should().Record.This.too(foo: \"bar\")[\"\"][\"\"][\" ... wait what just happened!. \"][\"magic must have occurred.\"].LOL.lfmao.terms_can_comeIn_any_ORDER(question1: \"is there anything it won't tolerate?\", answer1: \"apparently not\", question2: \"what is the meaning of life?\", answer2:  42).And[\"please don't feed the monkies\"].And(\"don't stare at the gorrilla\").He.will(think: \"you\").are[\"challenging\"].him.Or.At_worst_he_will_think_you_are_a(suitable: \"mate\").Or.I.Could.Go.On.To[\"other things\"].like().monkey.chicken(\".\")[\"cow\"].IMean(\"it\")[\"!!!\"].NoReally[\"...\"].Ok.Fine(\"!\")[\"  Go_Ahead\"].And[\"Do_Whatever you\"].Want().to";

    Assert.AreEqual(self_is, should_be);
}

Again, we get a faithful representation from the code of itself as it executes.  There are a number of interesting points of note locked within this basic paradigm.  First, I am writing the code I want to write while writing it, and yet the program is executing and writing my code for me as well.  Second, given that it will accept any legal c# syntax, I can simply babble into the DSL and it will babble back.  And, beyond these superficial aspects, there are some potentially powerful genetic programming capabilities.  Consider, adding some semantic meanings and key words into the DSL that do more than just spool.   The output of a dynamic DSL such as Echo could be presented to CodeDom to produce and execute whole new programs that are runtime generated copies of itself, with perhaps mild nondeterministic mutations randomly interspersed.   What would millions of successive iterations produce?

Here is the implementation of EchoDSL: (this code uses the int.Times() extension method shown here)


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Dynamic;
using System.Xml.Linq;
using System.Text.RegularExpressions;

public class Echo : DynamicObject
{
    string history = "";

    Dictionary<string, Func<Echo>> customOperators = new Dictionary<string, Func<Echo>>();

    /// <summary>
    /// Fluent Echo
    /// </summary>
    /// <param name="key"></param>
    /// <returns></returns>
    public Echo this[string key]
    {
        get
        {
            RecordIndexerCall(key);
            if (customOperators.ContainsKey(key))
                return customOperators[key]();
            else
                return Self();
        }
    }

    /// <summary>
    /// Fluent method getter for resolving self
    /// </summary>
    private Func<Echo> Self
    {
        get { return () => this; }
    }

    /// <summary>
    /// Fluent Property used for spawning instances from static.
    /// </summary>
    public static dynamic New
    {
        get
        {
            Func<dynamic> exp = () =>
            {
                var b = new Echo();
                return (dynamic)b;
            };
            return exp.Invoke();
        }
    }

    public static dynamic _
    {
        get { return New; }
    }

    #region constructors and initialization

    protected void init()
    {
        customOperators.Add("self", () => Self());
        customOperators.Add("new", () => New);
        customOperators.Add("_", () => New);
    }

    public Echo()
    {
        //todo
        init();
    }

    public Echo(Echo Echo)
    {
        //todo
        init();
    }

    public Echo(Echo Echo1, Echo Echo2)
    {
        //todo
        init();
    }

    #endregion

    #region operator overloading

    public static Echo operator +(Echo c1, Echo c2)
    {
        c1.history += c2.history;
        return c1;
    }

    public static Echo operator -(Echo c1, Echo c2)
    {
        c2.history += c1.history;
        return c2;
    }

    #endregion

    #region overrides

    public override string ToString()
    {
        //echo output
        return history.ToString();
    }

    #endregion

    #region dynamic api

    public override bool TryGetMember(GetMemberBinder binder, out object result)
    {
        RecordPropertyCall(binder.Name);

        if (customOperators.ContainsKey(binder.Name))
            result = customOperators[binder.Name]();
        else
            result = Self();
        return true;
    }

    public override bool TryInvokeMember(InvokeMemberBinder binder, object[] args, out object result)
    {
        result = default(object);

        if (customOperators.ContainsKey(binder.Name))
            result = customOperators[binder.Name]();
        else //build with it
        {

            var namedArgs = new Dictionary<string, object>();
            var indexArgs = new LinkedList<object>();
            Action prepare = () =>
            {
                var diff = args.Count() - binder.CallInfo.ArgumentNames.Count;
                var argQueue = new Queue<object>(args);
                if (diff > 0)
                {
                    diff.Times(i => indexArgs.AddLast(argQueue.Dequeue()));
                }

                var shiftedArgs = argQueue.ToArray();

                binder.CallInfo.ArgumentNames.Count().Times(i =>
                {
                    namedArgs.Add(binder.CallInfo.ArgumentNames[i], shiftedArgs[i]);
                });
            };

            var work = new Func<object>(() =>
                {
                    return null; //something
                });

            prepare();

            RecordMethodCall(binder.Name, indexArgs.ToArray(), namedArgs);

            //feed engine/managed state
            var output = work();
            //...

            result = Self();
        }

        return true;
    }

    #endregion

    #region private helpers
    void RecordMethodCall(string name, object[] indexArgs, Dictionary<string, object> namedArgs)
    {
        //fix string args
        indexArgs.Count().Times(i => indexArgs[i] = indexArgs[i] is string ? "\"" + indexArgs[i] + "\"" : indexArgs[i]);
        var call = name + "(" + String.Join(", ", indexArgs.ToArray());
        if (indexArgs.Count() > 0)
            call += ", ";

        namedArgs.ToList().ForEach(namedArg =>
            {
                call += namedArg.Key + ": ";
                call += (namedArg.Value is string ? "\"" + namedArg.Value + "\"" : " " + namedArg.Value) + ", ";
            });
        call = Regex.Replace(call.Trim(), ",$", "");
        call += ")";
        history += "." + call;
    }
    void RecordIndexerCall(string name)
    {
        var call = "[\"" + name + "\"]";
        history += call;
    }
    void RecordPropertyCall(string name)
    {
        var call = name;
        history += "." + call;
    }
    #endregion
}

In following posts, I will extend off of what has been demonstrated to show how higher-order functions can be folded into these dynamic DSLs to provide dynamic execution, decisioning, and data mutation pipelines. Namaste…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s