CLazy interpreter and compiler (12 January 2009)

CLazy interpreter and compiler

12 January 2009 (programming language lisp) (1 comment)

CLazy is my toy functional programming language featuring a Lisp-like syntax, lazy evaluation, and not much else at the moment. To get a taste of it, here's the definition of map in CLazy, using pattern matching:

(deftype list (t)
  nil
  (cons t (list t)))
   
(defun map (f nil)         nil)
(defun map (f (cons x xs)) (cons (f x) (map f xs)))

I've written the interpreter (in Lisp) back in November, and now I had this idea of writing a compiler. This compiler, instead of generating e.g. x86 assembly code, generates C# which is then compiled into .NET IL.

To do the actual code generation, instead of outright outputting text, the compiler (also written in Lisp) generates an s-expr representation of C# code. For example, the code generated for the type list, as defined above, is represented as the following:

(class ("List" :extends (instantiate-generic (dot "CLazy" "Runtime" "ConstructorTag")
                                             (dot "List" "Kcons")))
  (enum ("KCons" :visibility :public)
    "NIL"
    "CONS")
  (empty-line)
  (constructor (:visibility :public
                :formals ((var ("kcons" :type "Kcons")))
                :delegated-constructor (base "kcons")))
  (empty-line)
  (procedure ("Nil" :visibility :public :staticp t :type "List")
    (return (new "List" (dot "Kcons" "NIL"))))
  (empty-line)
  (procedure ("Cons" :visibility :public :staticp t :type "List")
    (return (new "List" (dot "Kcons" "CONS")))))

Which is then coverted to the usual, plain-text representation of C# code by a separate un-parser, yielding the following piece of code readable by C# compilers:

class List: CLazy.Runtime.ConstructorTag<List.Kcons>
{
    public enum Kcons
    {
        NIL,
        CONS
    }

    public List (Kcons kcons): base (kcons)
    {
    }

    public static List Nil ()
    {
        return new List (Kcons.NIL);
    }

    public static List Cons ()
    {
        return new List (Kcons.CONS);
    }
}

The actual function application code is simply a compiled instance for the given function of the generic graph reduction algorithm that the interpreter uses internally, e.g. the following is the C# code generated from the second definition of map:

private static bool Reduce_2 (CLazy.Runtime.Node node)
{
    CLazy.Runtime.Node actual_f;
    CLazy.Runtime.Node actual_x;
    CLazy.Runtime.Node actual_xs;

    actual_f = node.children[0];
    var P_0 = node.children[1];
    ReduceExprToCons (P_0);
    if (!(object.Equals (P_0.objPayload, ID.List.Cons ())))
    {
        return false;
    }
    actual_x = P_0.children[0];
    actual_xs = P_0.children[1];
    var R_0 = new CLazy.Runtime.Node (ID.List.Cons ());
    var R_1 = new CLazy.Runtime.Node (new CLazy.LangID.Apply ());
    
    R_1.Add (actual_f);
    R_1.Add (actual_x);
    R_0.Add (R_1);
    var R_2 = new CLazy.Runtime.Node (new CLazy.LangID.Apply ());
    var R_3 = new CLazy.Runtime.Node (new CLazy.ID.Map ());
    R_2.Add (R_3);
    R_2.Add (actual_f);
    R_2.Add (actual_xs);
    R_0.Add (R_2);
            
    node.Overwrite (R_0);
    return true;
}

« Type inference for CLazy

All posts

Pierre Basieux: Top 7 »

Encsé 2009-01-13 09:21:48

Good job! Congrats! Don't you want to come up with a tasks for gekko in CLisp? That would be great I think... ;)