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;

            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

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


At 8:02 AM, Anonymous Corbier 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 mj41 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 fahrschule würzburg said...

Good Job! :)

At 11:18 PM, Blogger vfdvgf said...

We always Wow Power Leveling and world of warcraft gold

At 12:50 AM, Blogger Adi said...

Oes Tsetnoc one of the ways in which we can learn seo besides Mengembalikan Jati Diri Bangsa. By participating in the Oes Tsetnoc or Mengembalikan Jati Diri Bangsa we can improve our seo skills. To find more information about Oest Tsetnoc please visit my Oes Tsetnoc pages. And to find more information about Mengembalikan Jati Diri Bangsa please visit my Mengembalikan Jati Diri Bangsa pages. Thank you So much.

At 3:41 AM, Anonymous Anonymous said...

i dont know if there suitalbe to write something good website i meet here, for i hope every body could have a good shopping experience online.

here i want to introduce this website, mainly selling nfl jerseys,
ghd, christian louboutin, and air max 95.

they offer 24 hours online service, and very very good customer service.
i buy the air max 90 shoes online on the website, nice design and good quality. that is why i strongly introduce you here.

it is not a advertisment, just share my shopping experience with everybody. hope you have a nice day, and could enjoy the good shopping.

At 9:56 PM, Blogger Jorce said...

wholesale moncler clothing
cheap moncler jackets
moncler ski apparel
Moncler ski jacketsg
Moncler down jackets
Moncler Men Jackets
Moncler Women's Jackets
Moncler kids clothing
Moncler vest on sale
Manolo Blahnik Pumps
Manolo Blahnik Sandals
Manolo Blahnik Slingbacks
Manolo Blahnik d'Orsays
Yves Saint Laurent Shoes
Christian Louboutin Ankle Boots

At 1:30 AM, Anonymous Microsoft Office 2007 said...

Office 2010
Microsoft Office 2010
Microsoft word
Office 2007
Microsoft Office
Microsoft Office 2007
Office 2007 key
Office 2007 download
Office 2007 Professional
Outlook 2010
Microsoft outlook
Microsoft outlook 2010
Windows 7

At 10:31 PM, Blogger Windows 7 Key said...

Recently i find a website that sell,Windows 7 Activation Key it makes me think i'm so Office 2010 Activation Key lucky a person. Compared with the Office 2007 Activation Key other sites i had bought Keys before, Windows 7 Keygen this one may be more welcomed Office 2010 Keygen by people in my opinion. For the website Office 2007 Keygen looks brief and the products are good Windows 7 Generator and genuine. Furthermore, it is professional and you can feel the warm-heart Office 2010 Generator of the service there. They will Windows 7 Upgrade help you solve the Office 2007 Generator problems you have patiently both Office 2010 Upgrade before and after. The delivery of Office 2007 Upgrade the products is very fast and you needn't worry Windows 7 Product Key about it. The most important is that the price on the web is Office 2010 Product Key reasonable, and you will be always have discounts, it is most Windows 7 Key attractive for me. If you're interested in this website, Office 2010 Key you can go and have a look.

At 5:30 AM, Anonymous Computer said...

Wow! This can be one particular of the most beneficial blogs we have ever arrived across on this subject. Actually Magnificent. I am also a specialist in this topic so I can understand your hard work.

Computer Accessories | buy webcam

At 5:47 AM, Blogger Bob_Alfredo 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 Admin said...

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

Buy A Ready-Made Logo

At 4:26 AM, Blogger justin albert said...

That's really massive exposure post and I must admire you in this regard.

Blackberry App

At 6:31 AM, Blogger Ad min 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 david Rice 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 3:01 AM, Blogger Fabian Smith said...

This is a really good read for me. Must agree that you are one of the coolest blogger I ever saw. Thanks for posting this useful information. Hamilton Resourcing
Human Resource Solutions UAE
Psychometrics Tests
Psychometrics Test Dubai
Talent Management
Integrity International
Executive Recruitment UAE
The McQuaig Psychometric System
The McQuaig Job Survey
The McQuaig Word Survey
The McQuaig Self-Development Survey
Executive Search Firms in Dubai
Head Hunters Dubai
Executive Recruitment in Dubai
Emirati Talent Management
Executive Headhunters Dubai
Executive Recruitment Dubai
Executive Search Dubai

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 6:12 AM, Anonymous Live Links Of High PR Commenting Site said...

Such a wonderful work has been done by you really your work is likeable to praise it is an awesome post.

Just Click : Live Links Of High PR Commenting Site


Post a Comment

Links to this post:

Create a Link

<< Home