Five-Dollar Words For Programmers, Part Three: Homoiconic

Jeff Atwood was kind enough to once more give me the shout-out in his blog the other day. Thanks Jeff!

This inspires me to continue my series on five-dollar words for programmers. Here’s one that I only learned relatively recently, when I helped write the code that translates a lambda expression into an expression tree which represents the content of the lambda: homoiconic .

A language is said to be homoiconic if the representation of the program can be seen as a data structure expressible in that language. With expression lambdas being convertible to expression trees (which can then be compiled into code at runtime), C# 3.0 is somewhat homoiconic. But it pales in comparison to, say, LISP, where pretty much everything you can do in the language you can also represent as structurally isomophic data.

Something I personally would like to see more of in C# in the future is greater homoiconicity. We could extend expression trees to statement trees, declaration trees, program trees, and so on. This series of steps would enable increasingly powerful and interesting metaprogramming scenarios.

C# suffers from the lack of a metalanguage. We absolutely do not want to go towards the horrible and primitive metaprogramming language exemplified by the C preprocessor language. We already have a great language, C#, so why not use C# as a metalanguage? Wouldn’t it be nice to make C# its own metalanguage? And once we do that, then we get into some truly strange loops, where we could use those data structures in the compiler implementation itself!

This is a long way off and might never happen, but a guy can dream.

Comments

• Anonymous
  March 23, 2009
  The comment has been removed

• Anonymous
  March 23, 2009
  The comment has been removed

• Anonymous
  March 23, 2009
  .NET already has it CodeDOM, which does almost the same: I say 'almost' because it does not create a direct representation of a program, but a representation of the program's source code, in the language of your choosing. Later, this source code can be compiled in memory and loaded on the fly; I believe WF does a lot of the same (although I do not pretend to know for sure: it's just that back in 2006 I have written tons of very similar code for a company whose engineers had created XML representations of their workflows used to automate their hardware testing and brought me aboard to create a sort of 'visual studio' to make those workflows run, the WF being in a very early beta back then). My intuition tells me that the expression trees are more 'immediate', although, once again, I do not pretend to understand in what way, exactly: you still need to call the Compile method of your LambdaExpression object, right? But, if C# does eventually become its own 'meta-language', the Business Process Mangement dream may come true: just define the English (or any other 'human' language) keywords, like, 'Incident', 'Change Request', 'Asset', etc., as data types, then make the verbs like 'deploy' or 'break-fix' invoke the related workflows (for example) and -- voila! -- you have RUNNABLE DOCUMENTS, in English, or in your business' native language, which the Big Bosses write to define the 'standard operating procedures' for their business and you then run for them! That should dwarf both WF and Azure, both by 'being cool' and by selling around the world... :-)

• Anonymous
  March 23, 2009
  +1 Douglas Hofstadter reference.

• Anonymous
  March 24, 2009
  > The lack of a metalanguage in C# is a major failing It's not, it's merely an indicator that it will take some more time for MP to become mainstream. Be patient. We've already got lambdas and type inference, and look at the poor Java guys who have neither :) > T4, which implements meta-programming T4 effectively is a macro system, which is a very weak form of metaprogramming. In truth, for anything serious, you want a proper language to work with (and it's best if it's the same as the target language, and not like template metaprogramming in C++). > .NET already has it CodeDOM, which does almost the same: I say 'almost' because it does not create a direct representation of a program, but a representation of the program's source code, in the language of your choosing. Later, this source code can be compiled in memory and loaded on the fly Ah, but that is not the point of the exercise. Generating C# code on the fly is quite doable even without CodeDOM. The trick is rather to parse the code, and manipulate it. > But, if C# does eventually become its own 'meta-language', the Business Process Mangement dream may come true: just define the English (or any other 'human' language) keywords, like, 'Incident', 'Change Request', 'Asset', etc., as data types, then make the verbs like 'deploy' or 'break-fix' invoke the related workflows (for example) and -- voila! -- you have RUNNABLE DOCUMENTS, in English, or in your business' native language, which the Big Bosses write to define the 'standard operating procedures' for their business and you then run for them! That should dwarf both WF and Azure, both by 'being cool' and by selling around the world I believe that's how the Oslo guys are trying to sell their product now. Me, I'm not convinced. So far such experiments haven't been successful. By the way, do you know that SQL was supposed to be a language that non-programmers could use "naturally" to get immediate results without deep exposure and learning?

• Anonymous
  March 24, 2009
  Have you seen Nemerle?  The ability to extend the language's syntax with "macros" written in the Nemerle language itself is seriuosly powerful.  I'm tired of external code-generation tools, including T4 and CodeSmith.  Ideally, C# should follow in Nemerle's footsteps and allow one to define coding patterns within the language itself.  Simply adding an attribute to a method (among other ways) to compile-time modify the behavior of that method or to generate code is indeed powerful.

• Anonymous
  March 24, 2009
  I seem to remember Anders saying something about statement trees and meta-programming in the E2E he did on the future of C# on Channel 9 recently. Meta-programming is definitely something I'd like to see, given the amount of time I spend writing code generators of one form or another, and writing generic and/or reflection code that borders on insanity.

• Anonymous
  March 24, 2009
  The comment has been removed

• Anonymous
  March 24, 2009
  The comment has been removed

• Anonymous
  March 24, 2009
  You can't have a homoiconicity post without somebody referring to Greenspun's 10th Law. "Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified bug-ridden slow implementation of half of Common Lisp." ;)

• Anonymous
  March 24, 2009
  Eric, I wonder whether you or any of the C# designers have ever taken a look at Boo. It's a statically typed programming language for .NET that enables exactly what you describe in this blog post, and it also enables what Anders Hejlsberg has shown about his vision of C# 5 in a few talks in the past. Boo can do this because it is already implemented in C# (and is currently rewritten in Boo), so it can simply provide the AST representation of the program in its internal expression tree syntax. This enables things like Meta methods (method calls executed at compilation time instead of runtime), AST attributes (attributes with a Process method that gets invoked when the attributed code element is compiled), macros, etc. It also has an extensible compiler queue, where you can insert custom compilation steps, transforming the program tree to your heart's desire. It is well-suited for any kind of metaprogramming, and is heavily used for DSLs. Whenever somebody on the C# team talks about these features, it's like "this is so far into the future" mixed with "in ye olden times, mysterious languages like LISP could do that".  Yet, Boo can do all of this, now. On the .NET platform. Look at it: <http://boo.codehaus.org/>. And maybe learn from it? Or at least acknowledge that approaches like this already exist on the .NET platform. Regards, Fabian

• Anonymous
  March 24, 2009
  The comment has been removed

• Anonymous
  March 24, 2009
  If you want to see an example of a object-oriented (albeit prototype based) homoiconic language, then you might find Ioke interesting. It's not fit for production use (it's still a baby) but it currently serves as an excellent didactic vehicle for exploring and understanding these concepts in a fairly recognisable syntax for people with Java, C#, Ruby backgrounds. Oh, and quite a bit of the core of the language is written in itself and has a whole load of tests which really makes things a lot more accessible and easy to understand. http://ioke.org

• Anonymous
  March 24, 2009
  If you want to see an example of an object-oriented (albeit prototype based) homoiconic language, then you might find Ioke interesting. It's not fit for production use (it's still a baby) but it currently serves as an excellent didactic vehicle for exploring and understanding these concepts in a fairly recognisable syntax for people with Java, C#, Ruby backgrounds. Oh, and quite a bit of the core of the language is written in itself and has a whole load of tests which really makes things a lot more accessible and easy to understand. http://ioke.org

• Anonymous
  March 25, 2009
  Why not implement a Common Lisp.Net like clojure? Not a toy like ironscheme, but a real supported implementation. You will never get away from ASTs, so why not just use lisp.

• Anonymous
  March 25, 2009
  The comment has been removed

• Anonymous
  March 25, 2009
  The macros in Scheme (and Lisp) only work because of the beautifully regular syntax, code is data and data is code. It just wouldn't work in C# or any other Algol derived language. It's amazing to think that over 50 years ago when Lisp was created, it was a near perfect language and hasn't been bettered since. Here's a radical suggestion but if you want these capabilities to set your creative skills free then why not simply learn Scheme. There is an explosion of interest in Scheme at the moment and it is rapidly edging towards the mainstream. Even Microsoft has woken up to functional languages and has released F#. The more of us that create libraries for Scheme, the more everyone else can use it for real projects instead of the flawed languages we are forced to earn a living with.

• Anonymous
  March 25, 2009
  > It just wouldn't work in C# or any other Algol derived language. As stated above by others, there are counterexamples of that, such as Nemerle (which is pretty close to C# syntactically all in all). BTW, Microsoft hasn't yet released F# :)

• Anonymous
  March 26, 2009
  So XSLT is homoiconic and Judy Garland isn't? Go figure.

• Anonymous
  March 27, 2009
  Hold on there.  What's so great about homoiconic?  It gives you lots of power -- to tie yourself into knots of un-manageable, un-maintainable, un-readable code.  And talk about security risks...  HUGE!  Ask yourself -- why isn't Lisp used in any major commercial setting?  Because making code -> data and data -> code creates huge pitfalls. I would argue that there are many more reasons than that. A language is successful in a particular domain when it successfully models the processes and concepts in that domain. Business settings tend to have a lot of concerns about processes, so it should not be surprising that procedural coding styles are important. Business settings tend to be concerned about rapidly changing external state, so it should not be surprising that coding styles involving mutable global state are common. Businesses tend to manage human scenarios by throwing the "hierarchy pattern" at problems; it should not be surprising that hierarchical object-oriented programs are common. Lisp can do all that of course, but the fundamental metaphor that Lisp throws at every problem -- the analysis of lists by functions -- is a far remove from the model world. In C# we deliberately make procedures, mutable properties, and the ability to explicitly model hierarchy all first-class concepts in the language right there for you to use. Though there certainly are pitfalls with homoiconicity, you can get yourself into even deeper morasses with C macros -- and many people do! The success of C speaks to the desirability of giving programmers "enough rope". You can't go denying people a tool just because some will misuse it horribly. But of course we want to make sure that the tools are designed to be easily used well, and designed specifically for real-world scenarios. -- Eric And any coneptual advantages of of doing so pail in comparison to the problems caused.  Algol and Algol-derived languages have maintained that separation for very good reasons.  Just because something can be done, and because there may some academic symmetries in such a concept, doesn't mean it should be adopted. And just because programmers love to produce "cute" (if obtuse) code doesn't mean we should design commercial languages to cater to that anti-pattern.  Careful language design needs to take into consideration much broader concepts of usefulness and useability.  I think the C# team has done a pretty good job of maintaining that perspective. Indeed. We're not interested in homoiconicity and metaprogramming because its cool (though it is.) We're interested in it because we have many customers whose fundamental use of C# involves in large part the automatic generation of more C#. Our existing code models are not strong enough to do all the tasks our customers would like them to do. -- Eric

• Anonymous
  March 30, 2009
  Ahora que ya hemos visto que es una expresión lambda podemos ver otra nueva característica mucho más

• Anonymous
  March 30, 2009
  Ahora que ya hemos visto que es una expresión lambda podemos ver otra nueva característica mucho más

• Anonymous
  March 31, 2009
  But, Eric, Common Lisp has a well fleshed-out OO system, and it not really FP-centric - at least most CL code that I've seen uses mutable state and imperative constructs (such as loops) heavily.

• Anonymous
  March 31, 2009
  Ahora que ya hemos visto que es una expresión lambda podemos ver otra nueva característica mucho más