Listening To Reason

random musings about technologies by Andy Norris

06 February 2008

The .Net DLR makes building a new language implementation ridiculously easy

Making language implementations easier

I've noticed that the greater population of working programmers seems to consider designing and implementing a new programming language a black art that only large-corporations or super-gurus know how to do. And really, it has traditionally been the case that an enormous amount of work is involved.

In the past, you had to know how to use parsing and scanning tools like lex and yacc (or you built your own recursive descent parser from scratch), you had to use tree transforms to build an intermediate representation, then you either had to build a virtual machine that could run on the intermediate representation, or you had to compile the intermediate representation down to machine code. And, of course, this isn't even counting things like various forms of optimization and type validation.

Even if you understand the theory involved very well, building out a language implementation like this takes a ton of work. Fortunately for potential language designers, new tools and technologies have started making things easier.

Step 1: Reusable Virtual Machines

The existence of widespread, reusuable VMs like the JVM and the .Net CLR have made life a lot easier for language implementers. Instead of having to design your own VM and implement things like garbage collection, JIT compilation, and virtual method dispatch yourself, you can just use a pre-existing implementation that has the virtues of being well-tested and highly optimized.

The advent of these VMs has led to a great variety of language implementations for them, such as Scala, Groovy, IronPython, JRuby, and F#. But even with a virtual machine, there's still a fair bit of work left for a language implementer to do. You still have to do scanning and parsing, and you still have to generate all that bytecode from your abstract syntax tree.

Step 2: New Parsing Technologies

Of course, if you've been following parsers, there are a lot of cool technologies for making parsers a lot easier. Parser combinators such as Parsec make parsing a lot easier.

In fact, there are quite a few ways to put together a parser fairly easily these days. I saw several last week at Lang.Net 2008. Roman Ivantsov presented a very cool new toolkit called Irony that makes writing a combined parser/scanner about as easy as writing a BNF grammar. Harry Pierson presented some cool work he'd been doing with Parsing Expression Grammars in F#, and also was nice enough to suggest I go check out FParsec, an F# port of the Haskell Parsec library.

I'm planning on spending some time trying out all of these over the coming months, to try and see which is the best fit for how I work. I'll try to post blogs as I work through some of these.

So that simplifies two out of the three hard parts, but what about building bytecode?

Step 3: The DLR is awesome for generating bytecode

The DLR contains a general-purpose system of expression trees (a superset of the LINQ expression trees, if you're curious) that allow you to define not only simple expressions like x + 2, but statements such as variable assignment, function definition, control flow (loops and branches), and so on.

Once you construct a DLR expression tree out of these common constructs, it handles all the work of rendering your code to IL and just-in-time compiling it. In other words, once you build an abstract syntax tree, you're done.

Martin Maly from the DLR team has started publishing a lot of useful information on his blog on how to work with the DLR, but the easiest entry point may be to download the latest IronPython 2.0 alpha (which includes the DLR) and play with the ToyScript sample. IronPython, the DLR, and ToyScript are all released under the open source Microsoft Permissive License, so feel free to reuse anything you see for your own purposes.

To give you some idea of what I'm talking about, here's the toyscript source for taking a binary operation expression off the parse tree and constructing an equivalent DLR expression tree.

protected internal override MSAst.Expression Generate(ToyGenerator tg) {
    MSAst.Expression left = _left.Generate(tg);
    MSAst.Expression right = _right.Generate(tg);

    Operators op;
    switch (_op) {
        // Binary
        case Operator.Add: op = Operators.Add; break;
        case Operator.Subtract: op = Operators.Subtract; break;
        case Operator.Multiply: op = Operators.Multiply; break;
        case Operator.Divide: op = Operators.Divide; break;

        // Comparisons
        case Operator.LessThan: op = Operators.LessThan; break;
        case Operator.LessThanOrEqual: op = Operators.LessThanOrEqual; break;
        case Operator.GreaterThan: op = Operators.GreaterThan; break;
        case Operator.GreaterThanOrEqual: op = Operators.GreaterThanOrEqual; break;
        case Operator.Equals: op = Operators.Equals; break;
        case Operator.NotEquals: op = Operators.NotEquals; break;

        default:
            throw new System.InvalidOperationException();
    }
    return Ast.Action.Operator(op, typeof(object), left, right);
}

Operator is a ToyScript enumeration of all of the supported operators, while Operators is the DLR enumeration of all supported operators. And, of course, if your language supports some exotic operators that don't exist in the DLR, you can just generate a function call.

Doesn't get much simpler than that, does it?

So if you have a cool idea for a new language and you're not allergic to the .Net platform, consider trying out the DLR. You'll spend a lot less time implementing the back end for your language, which will leave you more time to concentrate on whatever interesting new characteristics you want your language to have.

kick it on DotNetKicks.com

Labels: , , , , , , , , , ,

29 Comments:

At 8:02 AM, Anonymous Anonymous said...

I agree with this article that designing a new language traditionally has required an enormous amount of work. I would like to name another tool that is specifically designed to greatly facilitate the task of creating a programming language. It is uCalc Language Builder. The interactive tutorial that comes with uCalc LB covers aspects from languages as varied as Python, BASIC, Lisp, Forth, and more. Working interpreted versions of some of those languages are included in the download along with the code for creating those languages.

 
At 7:55 AM, Anonymous Anonymous said...

DLR is a great library. If you are looking for example of DLR lanaguage try this out:
Simple DRL language

 
At 2:39 AM, Blogger mj41cz said...

Parrot VM has Parrot Compiler Toolkit.

Great introduction are talks All Your Dynamic Languages Are Belong To Us, Programming Parrot and others.

 
At 4:32 AM, Anonymous Anonymous said...

Good Job! :)

 
At 5:47 AM, Blogger Knox Karter said...

"Thanks for sharing, nice post.
i follow you hope you could visit me here and follow me too,, thanks."

Pay Per Click

 
At 4:33 AM, Anonymous Food Logo Design said...

It's really beautiful work.Thanks for this kind of stuff.I mean I am totally impressed.Hope to see more updated work here.I have to say, it is very informative.

 
At 4:23 AM, Blogger Knox Karter said...

Very interesting looking post and I must appraise your efforts to write this post.

Buy A Ready-Made Logo

 
At 6:31 AM, Blogger Knox Karter said...

Good article! Thank you so much for sharing this post. Your views truly open my mind.
Free Photo App

 
At 2:27 PM, Anonymous price per head said...

This is an interesting..... great information found here... Thanks very much!

 
At 3:16 AM, Blogger Unknown said...

It feels great reading such post this way. Fairly excellent submit, keep the good writing coming...

Dissertation Writing

 
At 6:52 AM, Anonymous Dissertation Writing Services said...

Good stuff. It is interesting to read comments.Dissertation Writing Services

 
At 7:41 AM, Anonymous Seo Mexico said...

Nice information. I have added this post to my blog. Hope you will post these kind of informative post more so we all can take benefit from these information

 
At 8:46 AM, Anonymous Photocopier Repairs Basildon said...

Nice information, many thanks to the author. It is incomprehensible to me now, but in general, the usefulness and significance is overwhelming. Thanks again and good luck!

 
At 5:58 AM, Anonymous Online Shopping in Karachi said...

I have found this blog very exciting. Do you have any others on this topic? I am also sending it to my friend to enjoy your writing style. Thanks for sharing.
Online Shopping in Karachi

 
At 11:29 PM, Anonymous Custom Essay Writing Service said...

Thank you for sharing this! Just what I’ve been searching for. Great info!

 
At 11:05 AM, Anonymous sunglasses for women said...

Your Blog is very good, I like it! Thank you for you sharing!Your blog is really helps for my search and i really like it.

 
At 12:05 AM, Anonymous Accredited GED Diploma Online said...

Really decent post I simply unearthed your weblog and wished to say that I have genuinely delighted in searching your weblog posts. Much obliged man.

Visit : Accredited GED Diploma Online

 
At 4:49 AM, Anonymous High School Diploma Program said...

Great effort you have shared here keep it up.

 
At 3:21 AM, Anonymous Online GED Diploma said...

Nice one, there's truly some sensible points on this website a number of my readers might realize this useful; i have to send a link, several thanks.

 
At 9:22 PM, Anonymous baixar mobogenie said...

Great post,Thanks for providing us this great knowledge,Keep it up.
A good blog
---
i like play game clickjogos online free and apply baixar facebook online free and apply baixar mobogenie online free

 
At 3:16 AM, Blogger Unknown said...

I would like to thank you for your nicely written post
Signature:
download free descargar whatsapp and download baixar whatsapp online and descargar whatsapp gratis , baixar whatsapp gratis

 
At 4:18 AM, Anonymous cool math 4 kids said...

now that is released increases bikini and soaking in pool
girlgogames.com , baixaki whatsapp , coolmath4kids , girlsgogames , baixar whatsapp , coolmath4kids

 
At 7:49 PM, Anonymous descargar whatsapp gratis para android said...

Thanks for sharing this quality information with us. I really enjoyed reading.
----
apply baixar facebook and descargar whatsapp para android and apply baixar facebook movel

 
At 3:31 AM, Blogger Unknown said...

Very interesting! Thanks you
Signature:
Versión en facebook español a los países hablan Español: facebook login entrar , facebook en español para and facebook entrar direto

 
At 8:18 PM, Blogger Unknown said...

Its really good information, i like your blog post. Thanks for sharing
Signature:
i like play games happy wheels online and play happy wheels 2 games and Download retrica online includes more than eighty different filters with many different styles and include retrica indir , and zombie tsunami is the ideal game for anyone who loves the running game genre

 
At 4:00 AM, Blogger Rozersmith said...

Thanku for sharing the information it really helped me while learning the concepts of .net...awriter.org we have an unique essay writing services, do check our interesting link.

 
At 2:35 AM, Blogger Deddy Corbuzier said...

keajaiban dunia piramida
keajaiban dunia koloseum
keajaiban dunia lubang hitam
keajaiban dunia patung zeus
keajaiban dunia alexandria
keajaiban dunia
keajaiban dunia piramida
keajaiban dunia candi borobudur
keajaiban dunia modern
keajaiban dunia tembok cina
keajaiban dunia pulau komodo
keajaiban dunia menara pisa
keajaiban dunia machu picchu
keajaiban dunia
keajaiban dunia

keajaiban dunia
keajaiban dunia
keajaiban dunia
keajaiban dunia
keajaiban dunia

 
At 3:57 PM, Anonymous Anonymous said...

staedtler pensil terbaik untuk anak

 
At 1:52 PM, Blogger Freddi King said...

I really enjoyed reading this post. Thanks for sharing!
Salud Pulso

 

Post a Comment

<< Home