Sunday, May 24, 2009

Compile This !

I've been looking into compiling high level RenderMan Shading Language (SL).

The shader virtual machine is already more or less there.. with some notable features missing (conditionals for one) ..but I think I need to hurry up and start supporting the high level language. If anything, to have an estimate of the complexity of the work.

RenderMan's SL looks like this:

 float Ka = 1;
 float Ks = 1;
 float roughness =.1;)
 normal Nf = faceforward(N, I);

 Oi = Os;
 Ci = Os * Cs * (Ka*ambient()+Ks*specular(Nf, -I, roughness));
..and my assembly, currently, looks like this:


 Cs  parameter varying color
 Os  parameter varying color
 Ci  parameter varying color
 Oi  parameter varying color
 N  parameter varying normal
 I  parameter varying vector

 Ka  parameter uniform float 1
 Kd  parameter uniform float 1

 Nf  temporary varying normal

 normalize $v0  N
 faceforward Nf $v0 I

 diffuse  $v0 Nf  // -- Kd * diffuse( Nf )
 mulvs  $v0 $v0 Kd

 ambient  $v1   // -- Ka * ambient()
 mulvs  $v1 $v1 Ka

 addvv  $v0 $v0 $v1 // +

 mulvv  $v0 $v0 Cs // * Cs
 mulvv  Ci $v0 Os // * Os -> Ci

 movvv  Oi Os  // Oi = Os

When it comes to implementing, there is a world of differences between the C-like high level shaders and the asm one.

Following the suggestions of the Production Rendering book, I started looking into Lex & Yacc and Flex & Bison, also ANTRL and finally Flex++ and Bison++.
I looked into tutorials, tried to make those tools work, but eventually gave up.

There are two things that really frustrated me. First the availability and the usability of the tools.
ANTRL and Flex++ and Bison++ are supposedly C++ friendly, but I couldn't quite understand how. I found some examples, one seemed good, with some comments in French (?).
ANTRL has this ANTRLWorks Java application that lets you experiement with some nice graph rendering. You can specify options to handle C++ code, only some odd error message comes out.

I found a tutorial on ANTRL which seemed nice, also explaining how to integrate it with Visual Studio, but then it was for version 2.7.8 (or something like that) while the dir structure of the latest version was completely different.

Lex/Flex and Yacc/Bison are tried and true Unix tools, but the Windows versions aren't distributed too officially.. meaning that one has to find a site of some guy that built the binaries for you 8)

The other thing that frustrated me is that those tools are not easy to use at all. I spent some time trying to get my head around one of the many tutorials out there. They all say things along the lines of "Thank God you don't have to parse things yourself !" ..and then they start going about rules, lexemes, with some sort of arcane notations. And I feel like I'll never quite understand what is going on if I don't actually try to code the thing myself.

So, I put the parsing tools on the side and I started writing my own shading language parser.
I'm still only barely extracting tokens, but at least I feel like I'm making a progress. I mean, if I have to spend days or months of my time learning some ancient Unix tools, I'd rather invest that time to understand the basics and code it myself.
How hard can it be to write a very basic C-like compiler ? Not easy for me, but it's been done a thousand times over and lexical parsing, while tedious, is really the easy part.

I think that those compiler writing tools are essential if one needs to periodically write new parsers and syntax analyzers. In the long run, the tool generalizes much of the low level work.. but I'm not in the business of parsing different types of languages or creating new ones, and I can use some experience of compiler writing.

I think I can do away without those tools for now, but I can certainly use all knowledge there is on the subject. The must-have book on compiler writing is "Compilers: Principles, Techniques, and Tools"
  aka the "Dragon Book".
I remember the book (English edition !) in store in Shinjuku. At the time I was interested, but still not quite sure. Also the book was sealed, I could have asked to look into it.. but I really didn't need it at the time. I did need it today however and so I downloaded it (^^;)
Well, if I find it useful I'll probably buy it. If anything to have it in a portable and easy to browse format (portable as into the restroom, at 1038 pages, I don't see myself bringing it on the subway 8) .. but for the time being it was good to find it online.. perhaps illegally, but not unfairly, as having the PDF now made me want to own the book.
..ahhh.. some day we'll look at the stupid anti-torrent policies just like we look now at religious inquisitions of the Dark Ages.

Back to the book !


  1. I've been trying to play with antlr this last week also and I can say I know how you feel...
    Powerfull tools not and not enough documentation :(

    But, if you ever plan to use antlr again, try using this one at least it gives out errors that make sense.

    Any tips on how to build a programming language?
    I'm planning on building over the .Net DLR
    Thanks :D

  2. ummmummm I think I saw an article from someone implementing a language using the DLR, but I really cannot find it now 8)
    But I guess (?) that there is more than one of those tutorials out there.

    Personally I really have 0 experience on the subject, but it's certainly easier to try implement a compiler of a language that I know well at first.


  3. The closest I've ever come was writing a node based shader editor.

    The fact that it was node based meant I didnt have to interpret human readable syntax.

    By the way, been having major issues with your blog lately. At home (Vista 64bit) it wont even load. Here at work (XP 32bit) it loads but sometimes gives an error when I try to post. And I have to retype everything. Sucks =(

  4. May 27, 2009 10:20:00 PM

    It's interesting to see how assembly is so much easier to deal with.
    When thinking about it.. C-like languages aren't much more complex. The main complexity being handling of variables, expressions and structs and arrays I guess 8)

    About the blog "not working".. works fine here on Vista 64 (both at work and at home) with Firefox 2 & 3, IE 8 and Chrome 1.0 and 2.0, you tell me 8)

    wooooo !!

  5. I guess I will just have to 'suffer' if I want to keep posting on your blog!

    I think context and flow control are also pretty complex to interpret in high level languages compared to asm.

  6. Suffer suffer !
    Actually I also sometimes have to hit preview twice.. but the text doesn't disappear.

    In any case, it try using Chrome or Firefox.. no need to keep trying use Internet Explorer 8)

    About the flow control.. once suggestion is to turn 'for' and 'while' right away into if & goto sequences ..ahhh goto !!