Compile-Time Metaprogramming and Python

2007-05-31 at 18:09 | Posted in devel, lang:en, media, review | Leave a comment

Recently I’ve listened to an episode of SE Radio named Compile-Time Metaprogramming. It was quite nice. There is a discussion on the comments page between me and Laurence Tratt who was the guest of Markus Völter in this episode. I asked him about implementing the idea he’d talked about in run-time, and he replied that it could be a significant performance penalty. But I think run-time pre-compilation may reduce time of eval()uating very much.

I’ve written an example to show the idea. Actually, it is a prototype of JSON to Python bytecode compiler. I’ve used an Earley parser from SPARK library by John Aycock to build a parse tree from a JSON string and a BNF grammar of JSON. If you’re interested in getting the source, please leave a comment. The example of run-time pre-compilation (although the compiled code object is still interpreted) is shown below:

def main():
    # Pre-compilation, code is a Python code object
    code = generate_json_code("""
    {
        "GeoLoc":
        {
            "Latitude":  60.5667,
            "Longitude": 5.3959,
	}
        "Date": [2007, 05, 31]
    }
    """)
    call_json = lambda: eval(code)
    # Execution
    json = call_json()
    print "Today is %s" % str(json.Date)
    print "My geoloc is %.4f, %.4f" % (json.GeoLoc.Latitude,
        json.GeoLoc.Longitude)

def generate_json_code(str):
    tokens = tokenize(str)
    ast = JSONParser().parse(tokens)
    code = JSONTranslator(ast).translate()
    return code

And here is my outline of this interview:

  • Laurence Tratt, a researcher at King’s College, London, UK
  • His is the creator of Converge programming language
  • Markus and Laurence are talking about a DSL implementation at compile-time via syntax expressions
    • It’s a kind of macros, but more sophisticated than in C, for instance
  • Ruby approach: inline DSLs
  • Another approach: new languages that introduce a syntax to do something one couldn’t do before or it was too hard
  • Paul Hudak on DSLs: a DSL should:
    • Describe a domain in very domain-specific terms
    • Significantly improve productivity
    • Be maintainable
    • Allow non-programmers to program in it (the Holy Grail)
  • Integrating DSLs into a host language vs. stand-alone DSLs (e. g. Makefiles: make is written with lex/yacc)
  • A host language could do some stuff for us:
    • Error handling and reporting
    • Expressions
    • IO
  • Converge compile-time metaprogramming features: splices, quasi-quotes and insertions
  • Usually languages have macros because of lack of some features
  • Converge has macros because of keeping DSLs in mind
  • A DSL in Converge is like a JavaScript inside of HTML (i. e. something like <script type="javascript">)
  • A parse tree vs. AST:
    • Tokens → parse tree (of a DSL) → AST (of a host language)
  • In 1960s, parsing had to be effective: LL(k)/LALR/etc., O(n2) (?), SAX-like streaming
  • Nowadays, we can use Earley and GLR algorithms, O(n3), no look-aheads, any context-free grammar
  • In Converge, it is possible to create a function that takes a DSL code block, a grammar in EBNF, keywords info as its arguments and produces a parse tree
  • Error reporting in DSLs. Error messages should contain the position of an error both in the DSL code and in the host code where it has been invoked
  • Motivated by well-known problems with error reporting in C macros in C++ templates
  • DSLs tend to evolve, so you may take an advantage by using your host language features
  • Regex language is a great DSL
  • Converge is a research project, but some companies are interested in it
  • To summarize: there is an implicit and rather easy process of creating a DSL using Converge

Leave a Comment »

RSS feed for comments on this post. TrackBack URI

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

Create a free website or blog at WordPress.com.
Entries and comments feeds.

%d bloggers like this: