Friday, February 08, 2008

Call by Name: "Yo Elvis"

So Groovy has this Elvis operator:


def gender = user.male ? "male" : "female" //traditional ternary operator usage

def displayName = user.name ?: "Anonymous" //more compact Elvis operator
OK, I can dig it. I've got lots of Java code that could use this operator, following a form like x==null? "defaultSomething": x.getSomething().

Let's think for a second what this operator means, inventing some syntax for defining an operator:

?:(expr, defaultExpr) => ((expr)==null? defaultExpr : expr)
At one point in time at least, the Groovy implementation followed this implementation pattern, and if the twice-mentioned expr contained any side-effects they would be repeated. Usually something you don't want, always something you want to document, unless you want blunt objects headed toward your cranium. The odd thing about this implementation: it sounds just like call-by-name (CBN) evaluation. Unfortunately CBN is not accessible to the Groovy programmer, and in what is an obviously side-effecting language it's the worst possible form of CBN.

After digging into Lisp macros last week, this looks like a great candidate for a macro. Alternatively, imagine if Groovy let you define call-by-name functions yourself, then you could write this operator the way you'd expect:

?:(expr, defaultExpr) {
var exprEvaluated = expr // force evaluation
return exprEvaluated==null? defaultExpr : exprEvaluated
}
In call-by-name, a function's arguments are not evaluated before calling the function. Instead they are passed in as expression trees at runtime, and only if "needed" are they fully evaluated.

The advantage of a call-by-name function over a macro is code size: expanded macro invocations would add up, increasing the code size, and possibly leading to poor instruction cache locality.

The funny thing is that call-by-name, in a sense, in not an unfamiliar concept to any programmer. Any language reference's section on "control structures" is telling us all the built-in call-by-name functions: repeat(body,test), while(test,body), unless(expr,test), if(test,truecase,falsecase) are all potentially definable as call-by-name functions. Macros serve pretty much the same purpose, which is Arc includes so many cool control structures as macros. The tricky part for adding call-by-name definitions to statically-typed languages is that they work on expression trees, not values, and writing the type annotations most likely requires parametric polymorphism.

4 comments:

Reginald Braithwaite said...

Fantastic post, I wish I had known about Groovy’s Elvis operator when I wrote about Object#andand for Ruby: they serve similar purposes and I’m sure Rubyists would be interested in reading about alternative approaches.

murphee said...

Well, I guess this is where Mathematica's "Hold*" functions come in as a kind of dynamic macros.

Things like .NET's LINQ
http://msdn2.microsoft.com/en-us/netframework/aa904594.aspx
do the same thing, also by passing expression trees.

As for Ruby: there are few projects that use the AST of Ruby Blocks to do something like this, eg:
http://ambition.rubyforge.org/
The problem is the fact that accessing the AST of a Block (at runtime) is non-standard in Ruby. You need a native extension called ParseTree, which needs native code (or my very own jParseTree for JRuby, which - as these things go - work only for 95% of the cases, and of course the linked Ambition project managed to find the 5% that don't work yet).
Oh well... maybe Ruby 2.0 will finally make accessing ASTs a non-risky feature (Matz was somewhat reluctant at the last RubyConf about this).

Mike Kucera said...

I think you may have meant:

?:(expr, defaultExpr) => ((expr)==null? defaultExpr : expr)

JFKBits said...

mike kucera: Thank you, thank you very much. I did intend Elvis to return defaultExpr if expr was null.