Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

The case where a source-level operator actually describes an operation to take place at some future point, thunking the real operator together with its operands.

I don't know if this has any kind of general name, or perhaps it's too low-level a design element to be thought of as a "pattern" at all, but anyway it's an element that is frequently seen in a number of situations:

  • If I understand correctly (not a frequent C++ user), Boost::Phoenix does this to represent its lambdas and lazy operations, e.g. overloading + to actually capture the arguments along with the real + function for their type
  • Parser combinators in functional languages (or something like Spirit) look like operators on data, but actually build a parser that runs later
  • Other EDSLs (in languages with operator overloading) seem to do this a lot, e.g. functional reactive programming libraries tend to invisibly build procedures that will do what the operation looks like it's doing right now
  • (Again, if I understand correctly) IO in Haskell builds an imperative computation out of pure components that is then "executed" by dark magic hidden in the language runtime, while looking like it's just executing the functions in-place
  • At a simpler level, Greenspunning an embedded mini-Lisp into a C program could be considered the same thing: S-expressions can be built out of calls to C functions, to be run later (this last one would probably usually be considered the antipattern case), letting you look like you're passing "a lambda" to a C function, when you're really passing interpreter data

It's obviously not an antipattern in all cases, as in some of those it's the only way to use the tool in question (doing it in C might earn one a beating though). I don't think it's "Greenspunning" or "using an EDSL" by itself, as it can be more generic and widely applicable than that. I don't think it's the Interpreter pattern, although I may not have correctly understood that one: the computation is being built directly by executing host language code (so it effectively exists at compile-time, but usually not as a first-class language construct), rather than parsed out of a string or other runtime loaded data.

In all cases, what seems to happen is that an operation looks like it's doing one thing (not necessarily very convincingly, if it's C and you need to write out Add instead of overloading +, but same idea), while actually packaging that action up for later consumption. Something like a "computation builder" pattern? But I haven't found that term in use.

I don't have a practical problem to solve here; it's just bugging me that there seems to be a common design element that I can't put a name to.

(Question originally posted at StackOverflow, moved by hand)

share|improve this question
1  
Please flag for migration instead of reposting. It helps keeps comments (which may contain clarifications) together. Sometimes, a question isn't appropriate for the target site and the moderators can help explain why rather than having closed/deleted questions on multiple sites. –  MichaelT Aug 8 '13 at 4:03
    
In this C++ world this would be called "normal". –  James Anderson Aug 8 '13 at 4:22
    
Besides lazy evaluation maybe this could also be described as late binding? –  AndreasScheinert Aug 8 '13 at 10:32
1  
And don't forget ORM method chaining, which is either an instance of this or something very similar. You start with an object and then run methods like "where", "order_by", etc..., but it doesn't evaluate the query until you actually request data. In the background, it progressively builds a query to be evaluated later. Lazy evaluation is definitely a good pattern here, because it limits the number of database calls. –  Ben Lee Aug 8 '13 at 11:42
add comment

2 Answers

up vote 9 down vote accepted

What you seem to be describing is Lazy Evaluation. Computations to be performed when the result is needed, rather than when it appears in the source code.

In Haskell, this is done by hiding these computations behind monadic abstractions. In C++, the abstractions are similar, but more explicit, and partially hidden behind overloaded operators and expression templates.

Similarly, your cited example of "Greenspunning" of a Lisp-like construct in C is not an antipattern, but rather a data-driven lazily-evaluated DSL, and seems, actually, to be one of the most common patterns of an FFI for Lisp and Scheme interpreters (especially in ECL, Chicken, tinyscheme and others), since C lacks the means to construct and pass unexecuted functions as data.

You will notice that these patterns do not appear in languages which have first-class function objects.

share|improve this answer
    
Thanks. Actually, being reminded of the existence of things like delay makes this suddenly fall into place. I was aware of lazy evaluation before but never regarded it as anything other than an implementation strategy. –  Leushenko Aug 8 '13 at 17:39
add comment

This is called Lazy Evaluation. It is a quite common pattern. In fact, every time you use the && or || operator in a C-like language, the second operand will only be evaluated if it needs to. Likewise, in an if/then/else, only one of the branches is evaluated.

Lazy Evaluation has some interesting properties:

In the absence of side-effects, making something lazy cannot change the result of the program. It can, however, make a non-terminating program terminate. For example, if you have something like:

False && infiniteLoop

Under eager evaluation, this will result in an infinite loop, but under lazy evaluation, this will return False.

IOW: lazy evaluation makes it possible to write programs that cannot be written with eager evaluation. Consider the famous fibonacci sequence example in Haskell:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

[Which is a bad example, BTW, because it doesn't have optimal algorithmic complexity.]

With side-effects however, lazy evaluation may change the order in which side-effects occur, or they won't even occur at all.

For pure and total programs, lazy vs. eager evaluation changes nothing at all, it simply becomes an optimization choice for the compiler. (Total programs always terminate, and the only difference between eager and lazy evaluation is termination, therefore for total programs, there is no difference.)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.