Lazy programming is a general concept of delaying the processing of a function or request until the results are needed. This concept has numerous applications, from the obvious to the obscure. Thinking in terms of lazy programming can help you rid your code of unneeded computation and restructure programs to be more problem-oriented.
Lazy Programming and Evaluation
About The Author
Eugenia Loli
Ex-programmer, ex-editor in chief at OSAlert.com, now a visual artist/filmmaker.
Follow me on Twitter @EugeniaLoli
My subject says it. IBM articles are in depth and this one is still easy to understand. This is a must read for budding programmers and a refresher for those who already know it. And the prose is clearly written to brighten days.
The only problem is to clear the stored value for another calculation, but thats another problem.
The word lazy caught my attention, but that just explains how I work.. :o)
I am too lazy to read this article. yawn….
Hehe, I actually opened the article…
Either the programming or the programmer gets to be lazy, and this article is not about the latter.
Interesting article. While you remove the “unneeded computation”, you add the risk that some values may not be current. A simple check for null may not be adequate in some scenarios.
True. The delay/force constructs, as well as the object oriented imitation illustrated in Java code, really just boils down to the good old technique of caching. It’s trivial to see that while caching has the nice effect of saving computing power, it has the flip side that values may not be valid when taken from cache.
In the original realm of lazy evaluation, pure functional programming, this is not a problem because no function will ever depend on anything but its arguments. The beauty of lazy evaluated languages is that this happens whether or not you think about it. The result of every evaluated expression is cached until it gets garbage collected.
Of course, back in real world, you need certain things to happen in order and you need side effects for a program to be at all useful. Once you start adding monads and other tricks to achieve this, you’re no longer in functional programming heaven.
Unneeded computation isn’t eliminated, but put off until the value is neeeded. Once the value is written to disk, used in a comparison, or used in a different computation, then its value is computed.
Assuming the language being used is lazy, the compiler or interpretter takes care of everything for you, so there’s no need to check for up to date values. In fact, any such checks would defeat the purpose, because they would force values to be computed before they were otherwise needed.
With a new jargon “concept” flavor-of-the month?
Lemme see, there’s: agile programming, extreme programming, RAD, now lazy programming.
When you look closely at any of these are they really “break-throughs” ? Or just re-packaged common knowledge with some new jargon attached? Much as pop-psychology and pop-management has been doing for ages?
Is 6-sigma really a break-through? Or just a load of hooey? Are the concepts behind “exteme programming” really unknown before somebody coined the phrase and wrote a book?
Makes me laugh when I go to read about some new methodology and, “extreme”, turns out to be somehthing we were doing 20 years ago with our backs to the wall at crunch time.
What’s the jargon? This is just simple old stuff that’s often underused (though I do wonder about the value of the 0/null checking example). AFAICT, nothing new or marketing-worthy was in it.
Or at least, something very similar. The description is here: http://boo.codehaus.org/Asynchronous+Design+Pattern
Basically every function in Boo is an object. To call a function you say myObj.funcName.Invoke (param1, param2) etc. but as a nice shortcut they allow you to just say myObj.funcName (param1, param2).
However function objects also have BeginInvoke() methods (to begin invocation) and EndInvoke() methods (to wait for the invocation to end and return the result). Thus you can write
val1 = funcOne.BeginInvoke (param1, param2)
val2 = funcTwo.BeginInvoke (param1, param3)
result = funcThree (val1.EndInvoke(), val2.EndInvoke())
What’s impressive about this, is that it’s an easy way to multi-thread your code. Now the difference between this and lazy evaluation is that here evaluation straights straight-away (albeit in a background thread) whereas in lazy evaluation work doesn’t start till it’s needed. Lazy evaluation is hand in functional languages as it allows you to define a list of infinite length (e.g. fibonacci numbers).
For those who don’t know about it, Boo is a bit like Python, but simplified to allow you to work faster, and totally integrated into .Net you can take advantage of its libraries.
Edited 2006-12-20 14:53
But then, that could just be the machine language coder in me… Not calculating until you need it, specifically as done in the ‘statistical calculations’ example is less efficient, because it means you need to trap whether the value has been calculated or not INSIDE THE LOOP! Conditionals are slow, and putting them inside a loop is just asking for your code to take LONGER to execute, not less time. If it takes four clocks to calculate the mean and six clocks for the conditional (rough estimate) and one clock to just look up a memory offset (variable) we’re talking the difference at execution of 4 clocks outside and 1 clocks inside for the traditional method, or ten clocks on the first look and seven clocks for each additional using the ‘lazy’ technique… It’s going to be slower. Sure, you could probably use an ‘open branch’ – one set of code for the first execute, second set for the for the later loops, but that just bloats up the code… suddenly instead of just needing one set of source that solution ends up doubling your code size every time you ‘delay’ a calculation – oh yeah, THAT’s efficient.
WORSE, yes, it opens it up to threading, but unfortunately introduces the possibility of leaving one thread hanging waiting on another – ENTIRELY DEFEATING THE POINT of threading. (mind you, branch prediction can eliminate this particular problem…)
Entire thing smacks of theories put forth by someone who doesn’t understand how code actually EXECUTES.
Edited 2006-12-20 15:06
Sometimes it seems like nobody cares what the compiler spits out any more as long as it runs. Embedded space is the last sanctuary of the true coder.
“Sometimes it seems like nobody cares what the compiler spits out any more as long as it runs.”
As I had my years learning at the university, I often had to say something like this:
1. Trial & error is no programming concept.
2. Is the result of your program the result of the given problem? Fine, it gives an answer, but the answer is wrong.
3. The compiler does not know what you want. int x, y, sum; sum = x – y; The “semantic compiler” semcc throws an error.
Efficiency is no longer needed because we have more computing power (CPU time, memory ressources, disk space etc.) than we need. So why don’t use Bubblesort and linear search? They’re just fine for everything.
To come back on topic: I’m not familiar with the concept of lazy programming and evaluation so the article was quite interesting.
“Unneeded values are never computed.” is a goal achievable by intelligent programming outside the lazy world – in every language, even cc -Wall can give a hint to unused values. The author states that traditional ways of programming still have their right to exist: “However, the behavior of lazy programs is often hard to predict. In call-by-value programs, the evaluation order is very predictable, so any time- or sequence-based computations are relatively easy to implement.” As a conclusion: “Consider adding them [lazy programming techniques] to your repertoire of techniques.” I surely will, just because it promises to be fun using them.
Your rant is worthless, of course, because nobody would cache a calculation that was cheaper to recompute. The example given was pedagogical, not something you’d necessarily do in that situation.
Moreover, these days your simplistic description of “how code actually executes” is insufficient. For example, if the cache behavior is easily predictable (many consequent loop iterations use the same loop value), the branch is going to be more or less free on a modern, OOO CPU. Moreover, if the computation involves any memory access at all, the potential of a cache miss totally burying any conditional overhead is extremely high.
Counting cycles in your head is just a pointless idea on modern CPUs. If you really care about what your inner loop is doing, stick it under VTune. You’ll probably be quite surprised by the results.
Edited 2006-12-20 16:03
“Your rant is worthless, of course, because nobody would cache a calculation that was cheaper to recompute. The example given was pedagogical, not something you’d necessarily do in that situation.”
I don’t think it is worthless.
Don’t be too sure that nobody would cache a calculation that was cheaper to recompute.
I bet there are quite a lot of programming noobs who just follow the latest trend, regardless of its real benefit. You are obviously not the type of person who this rant was directed at, anyway.
And, of course, you’re right:
Just counting cycles is pretty useless.
In the end there is only one way to (reliably) improve the performance of your program:
Benchmark it and then tweak the slowest part.
Otherwise chances are you’ll be wasting your effort on some unimportant function and ignoring the real bottleneck.
And finally, although I know it’s stupid, I simply _have_ to visualize how the highlevel stuff works on C or assembly language level.
That’s not to say that these high level languages are bad.
I just think it depends on my taste if I want to deal with the lowlevel stuff.
Can’t even say that writing some C code spoilt me since I started with Delphi (hated it) and going to C was all like “Wow, now THAT’s what I’ve been looking for!”
Yes, I know I’m sick but I can’t help it
But still, all this lazy programming stuff is really cool, especially building infinite lists and the like.
It would be nice to unify functions and lists in a way like
f(x)=sin(x)/x;
f(0)=1; //it really is 1 but the computer doesn’t know
I mean, the example was nice and all but it still looked _way_ too complicated.
Is there a language in which funtions and lists are _really_ the same, without cumbersome syntax that is?
Of course, there would be the danger that if lists were functions, we would write them like “list(j)” instead of “list[j]”. While we’re at it, we could make blocks of code functions, too.
That would allow for even higher levels of abstraction and look like…
Damn it, it choked on the parentheses.
Fallen to Greenspun’s rule again, damn it, damn it damn it!
“That’s not to say that these high level languages are bad.
I just think it depends on my taste if I want to deal with the lowlevel stuff.”
Yes, from my experience that’s right. The selection of language level and particular programming language depends on what you want to do with it. Sometimes it’s necessary to implement low level stuff because special functionalities don’t exist in available libraries. And was always, it’s not useless until you learn something. Achieving education is possible even by dealing with primitive stuff like lists and functions.
“Yes, I know I’m sick but I can’t help it
“
INPUT aspirin && GOTO bed;
“Is there a language in which funtions and lists are _really_ the same, without cumbersome syntax that is? “
I don’t think there’s such a language because of a simple thing: Lists, if we assume them to be indexed, so they exist as a vector or array form, need integer arguments as index. Multidimensional indices are possible. Functions can have (multidimensional) integer arguments, but they can also have double, struct something or void * arguments. While lists of a particular data type (or mixed up types) are indexed by countable types only, functions can have overcountable (überabz"ahlbare) arguments as well.
I hope I understood right.
“INPUT aspirin && GOTO bed; :-)”
goto? GOTO?!? *puke*
Now, a good old fashioned jz would have been something different.
Anyway, I was not suggesting to make functions lists, we should instead make lists
(and hashtables) functions.
This mix of array and function was meant to be a function, with a countable number of exceptions.
So internally this new type of function would consist of a pointer to the generic function and a hashtable of exceptions. The hashfunction would then, for example, take the number of arguments and their types and look up if there was any matching exception.
It would then go on and do a second computation to find out if there is an exception stored for this _specific_ value. If not, it would of course execute the general function.
This function could be everything from
double f(double x){return x*x;} to
int f(int x){
static int a[100];
if((x>=0)&&(x<100)) return a[x];
else{
printf(“Number out of range
“);//or any other error message/exception
return -1;}}
Of course, the function could also grow the array if it was a pointer rather than a fixed size array.
So dynamic arrays should be a breeze.
To take the whole concept a little further, variables could be made functions that take no arguments – that empty parens annoyed me anyway
Of course _internally_ it would still use functions and old fashioned variables but it would make it a lot easier to make changes to the code and write some pretty cool stuff.
It would be slow as hell, though
Anyway, I’m not even sure I understood you right (it’s always funny when two German guys are talking to each other in English). So if there’s anything left to discuss feel free to email me at ben_ (nodamnspam) schuenemann AT yahoo dot de.
Sorry if this discussion annoyed anybody.
Btw, is there a way to make the code _readable_?
I guess pre tags are not allowed…
>> Your rant is worthless, of course, because nobody would cache a
>> calculation that was cheaper to recompute. The example given was
>> pedagogical, not something you’d necessarily do in that situation.
If it’s not something you’d do with it, why the **** would someone use it as an example?
>> Moreover, these days your simplistic description of “how code
>> actually executes” is insufficient. For example, if the cache
>> behavior is easily predictable (many consequent loop iterations
>> use the same loop value), the branch is going to be more or less
>> free on a modern, OOO CPU. Moreover, if the computation involves
>> any memory access at all, the potential of a cache miss totally
>> burying any conditional overhead is extremely high.
So in other words you are praying that the cache fixes bad code, instead of writing good code in the first place? Sorry, I’m not buying it… you are going to have a hard time convincing me that a memory reference (status) followed by a conditional (is it set?) followed by either running the calculation or… well, running a MEMORY REFERENCE is going to be FASTER than just using a reference in the first place? Sorry, /FAIL/ hard. [bp+8] FTW… makes about as much sense as the whackjob claims about java being faster than machine language – which ANYONE who understands what machine language is, well, is going to call bullshit on. That type of thinking is just going to load up all the execution pipes on something that should only need one…
>> Counting cycles in your head is just a pointless idea on modern CPUs.
While yes, it is questionable with multiple execution pipes, caching and branch prediction, it is STILL a good place to start, because as I said above expecting some 6 to 10 opcodes to execute faster than one is total manure… especially when BEST CASE this ‘lazy programming’ would boil down to a conditional AND that same one opcode… and being conditionals result in a JUMP, the SLOWEST of all opcodes, that just does not paint a pretty picture.
Edited 2006-12-20 23:35
“Sorry, /FAIL/ hard. [bp+8] FTW… makes about as much sense as the whackjob claims about java being faster than machine language – which ANYONE who understands what machine language is, well, is going to call bullshit on.”
Ok, only complete retards would claim that Java could ever be faster than machine language.
Even the argument about how the Java JIT-compiler knows more about the executing environment and can do better optimizations based on this knowledge is BS, because the compiler itself is just a machine language program. Granted.
On the other hand noone would actually write a whole JIT-compiler suited to his specific few hundred lines that need optimizing.
Using reasonable amounts of time you are probably better off using, say, C or C++ or maybe even Java (though I _really_ doubt it).
This way you can put more effort into the algorithm and datastructure and less into the specific details of implementation.
But things will probably change when hardware for Java becomes mainstream.
>> Ok, only complete retards would claim that Java
>> could ever be faster than machine language.
Back read on this very site on Java benchmarks – six months to a year ago the web was rife with topics and posts on that very subject… and I called bullshit on that – and was modded down for it.
If it’s not something you’d do with it, why the **** would someone use it as an example?
You use caching to avoid repeating complex computations. Putting a complex computation in the example makes the example… complex. The point of the example is to demonstrate the form of the solution — it is expected that the reader is intelligent enough to apply that solution to cases where there is a problem.
So in other words you are praying that the cache fixes bad code, instead of writing good code in the first place?
You’re missing the point. Accessing a cache is generally cache-friendly (you’re repeatedly accessing the same memory location). Repeating a complex computation may not be. If an easily-predicted branch lets you replace a poorly-cached memory access, that’s a win. Its not about “bad code” versus “good code”, but about the relative trade-off between potential bottlenecks in a piece of code.
makes about as much sense as the whackjob claims about java being faster than machine language – which ANYONE who understands what machine language is, well, is going to call bullshit on.
A JIT can be faster than machine code (unless of course you write a JIT in machine code). If a computation has a substantial amount of run-time redundancy, a JIT can optimize the code in ways a static assembler cannot. This isn’t just a theoretical point — SGI’s software OpenGL implementation uses a dynamic code generator (effectively, a JIT) to optimize rendering routines based on the current state of the GL state machine. C++ BLAS packages use the template mechanism to optimize their routines for the specific compile-time constants used in the program.
While yes, it is questionable with multiple execution pipes, caching and branch prediction, it is STILL a good place to start, because as I said above expecting some 6 to 10 opcodes to execute faster than one is total manure…
If that one opcode is a poorly-cached LOAD, you can probably get dozens of opcodes in its place and still win in terms of performance.
and being conditionals result in a JUMP, the SLOWEST of all opcodes, that just does not paint a pretty picture.
Unconditional JUMP is free for all intents and purposes on a modern OOO processor (it doesn’t even eat up an execute slot on Core 2). Conditional jumps range from almost free (well-predicted), to moderately expensive (~12-14 clocks). Memory loads on the other hand range from pretty cheap (~3 clocks) to comically expensive (~300+ clock cycles).
Memory accesses are the dominant performance bottleneck for modern processors. Bad cache behavior dominates every other factor in modern code. Cache behavior is very unpredictable, since its hard to know beforehand about details like cache line sizes, prefetch algorithms, etc. Unless you’re in a situation where code size really counts, the best idea in nearly all cases is to code the algorithm in a sane way, then stick it under VTune or Valgrind to see what it is actually doing. A lot of stuff that gives assembly programmers fits (eg: array bounds checks, oh noes!) shows up as noise in a VTune profile.
The examples don’t really show the value of lazy evaluation because they were chosen to be simple to understand rather than indicative of the potential win.
The classic example of lazy evaluation being successful is copy-on-write (COW) semantics in virtual memory. It’s also a good example of how lazy evaluation isn’t quiet like caching.
The pedantic example that’s most effective is the old trick of caching the return value of getpid() so that subsequent lookups don’t actually cause a system call:
static int mypid = 0;
int mygetpid() {
if (!mypid) mypid = getpid();
return mypid;
}
even in the above form, without inlining, the syscall overhead that’s saved on 2nd and subsequent calls more than makes up for the penalty of the call/return and branch.
I hate this term. It isn’t “lazy” programming. The programming has to do just as much work, even more, with this style of programming. Instead, this should be called by a better name: delayed evaluation.