Bob Balaban's Blog

     
    alt

    Bob Balaban

     

    "Lazy Evaluation": When Being Lazy Causes You More Work

    Bob Balaban  August 16 2009 06:39:18 AM
    Greetings, Geeks!

    I have always held that being "lazy" is not a bad thing. In fact, I often tell people that I'm lazy, and that this is why I became a software developer: I want the computer to do the work, so that I don't have to.

    Being "lazy" (if you define the word as meaning "don't do more work than you have to") is not a bad programming principle. It's really just another way of saying "KISS" (Keep It Simple, [Silly]).

    Recently, though, I got bit by a LotusScript program I was working on because I forgot that LotusScript isn't as "lazy" as other programming languages I regularly use (Java, C++...).

    But, to tell you that story, I have to tell you about a thing called "lazy evaluation". It's a principle that applies to the runtime evaluation of "if" statements in a program. In virtually all programming languages, an "if" statement is a critical control-flow influencer, and an important part of the logic a developer is implementing. Usually the word "if" is followed by a boolean expression. The expression can be of arbitrary complexity, nested parenthetical sub-expressions, whatever, but the expression, in the end, needs to evaluate to a value that can be interpreted as either "true" or "false" (thus, boolean). In some languages, the defintion of "true" is more, um, flexible than in others. The most relaxed definition says that "true" is anything that is non-zero, while (in most languages) "false" is zero.

    So, you can have an "if" that contains lots of logical "AND"s and "OR"s, and as long as the whole thing can be computed down to a numeric value that represents either T or F. Most compilers take advantage of some standard optimizing intelligence that says, "we don't have to completely evaluate the expression, we can stop once we know that  the expression will never be TRUE. Thus, "lazy evaluation", it won't do more work than it has to. Here's a pseudo-code example:

        if doc.IsValid() AND DocIsWhatIWant(doc) then
             ' something
        ELSE
             ' something else
        end if

    Because there are 2 sub-expressions here connected by an AND, the "then" part of the block should only be executed if BOTH  conditions are TRUE. With most compilers, the generated code will test the first sub-expression, and if it's FALSE, it won't bother to test the second, because it "knows" that the entire expression will certainly fail. Lazy evaluation, it works for me!

    So. What's the problem?? The problem is that LotusScript does NOT USE lazy evaluation. Here's an example similar to the one that bit me:

                                                   dim preserved as variant
                                                   dim respIdx as Integer
                                                 respIdx = 0
                                                  preserved = FillArrayWithStuff    ' might be an array, might be NULL
                                                  If Not Isnull(preserved)  AND  Isarray(preserved) AND If respIdx <= Ubound(preserved) Then
                                                         values = preserved(respIdx)
                                                        ' do more work
                                                End If

    Here's what's happening with this code: I have a "preserved" variable that gets computed by the FillArrayWithStuff() function. If there's nothing for it to do, it returns a NULL. So my next bit of work has to be controlled by a test for IsNull(), then I want to make sure that when "preserved" has something in it, the thing is an array. THEN I want to be sure that the index I'm about to apply to the array is within bounds.

    In Java, or C or many other languages, the sub-expressions here would be evaluated left-to-right. If preserved is null, they stop right there. If it's not NULL, but is not an array, don't even bother to check the array bounds.

    HOWEVER, LotusSCRIPT DOES NOT WORK THAT WAY!! LotusScript ALWAYS evaluates ALL the sub-expressions. Why? Because Visual Basic (from which LotusScript was cloned) does it that way (or at least, used to).

    So, the first time I ran this code where "preserved" was NULL (not an error condition, it was set up that way on purpose), LotusScript threw an exception on the Ubound() call. I had forgotten that LotusScript is not "lazy". I should have coded it this way:

                                                   dim preserved as variant
                                                   dim respIdx as Integer
                                                 respIdx = 0
                                                  preserved = FillArrayWithStuff    ' might be an array, might be NULL
                                                 If Not Isnull(preserved)  Then
                                                        If Isarray(preserved) Then
                                                                If respIdx <= Ubound(preserved) Then
                                                                        values = preserved(respIdx)
                                                                         ' do more work
                                                                End If        ' ubound
                                                       End If                 ' isarray
                                               End If                   ' isnull

    So, here's one case where the fact that LS is not "lazy" made more work for me. Sigh. I need a nap.

    Geek Ya Later!


    (Need expert application development architecture/coding help? Contact me at: bbalaban, gmail.com)
    Follow me on Twitter @LooseleafLLC
    This article ┬ęCopyright 2009 by Looseleaf Software LLC, all rights reserved. You may link to this page, but may not copy without prior approval.

    Comments

    1jake  8/16/2009 8:32:48 AM   Lazy Evaluation : When Being Lazy Causes You More Work

    Well articulated. Because I'm switching languages so much (there are so many loosely typed languages out there to make a buck on) I'm a bit hardwired to double check if a language is lazy or not. But it's worth repeating.

    2  8/16/2009 8:10:26 PM   Lazy Evaluation : When Being Lazy Causes You More Work

    I remember discovering this years ago and being very annoyed with LS. ;-)

    I'm sure I have many inefficient programs where I don't use nested IFs because (unlike your example) it won't cause a problem (like multiple tests of var that's not null). Thanks for reminding me that I should use multiple, nested IFs more often than I do, so LS doesn't evaluate things it doesn't need to. Grumble. ;-)

    3Richard Schwartz  8/16/2009 10:19:10 PM   Lazy Evaluation : When Being Lazy Causes You More Work

    The reason LotusScript and VB don't do it is because ANSI standard BASIC, upon which both were cloned, didn't do it. And the reason ANSI standard BASIC didn't is that the early versions of BASIC that the ANSI standard sought to maintain compatibility with didn't. And the reason that the earlier versions of BASIC didn't is... well... I dunno for sure, but there were no pointers to contend with and functions with side effects were considered a bad practice, so there just probably wasn't any reason to do it.

    Another thing: it's debatable whether lazy evaluation is an optimization. It inserts an extra test where the programmer didn't put one, so if we're in a loop and the first condition evaluates to true except in unexpected error cases (which is the case in an awful lot of common programming idioms) then it actually costs an extra instruction on each iteration. Not saying this is a bad thing.

    4Scott Leis  8/17/2009 10:00:07 PM  Lazy Evaluation : When Being Lazy Causes You More Work

    I vaguely recall a high school CS teacher saying there are (rare) cases where lazy evaluation can produce an incorrect result. I'm sure she actually demonstrated an example, but I can't remember the details.

    5Kendall  8/19/2009 9:58:05 PM   Lazy Evaluation : When Being Lazy Causes You More Work

    Hmm, my previous comment (#2) didn't have my name--sorry about that.

    Richard: I vaguely knew the history but still find it annoying, since I grew up with languages that IMHO are 'smarter' in this regard. ;-) LS has all those 'option' flags to control how things work; if only it had an 'option shortcircuit'.... ;-) (I think 'short circuiting' was what I learned to call it in school, way back when.) Anyway, I'm unclear on how skipping one or more tests is inserting an extra test; can you elaborate? For example, let's say we loop through docs in a view till we hit one with a certain set of criteria, or we hit the end of the view; we expect the former, but include the latter test in the 'while' condition since we know it's theoretically possible; knowing how short circuit ("lazy") eval works, we put that last in the list of conditions; with short circuiting, we skip that useless test; without it (in LS), we have to check whether doc Is Nothing every time through the loop. (This is probably a poor example--just something simple off the top of my head, sorry.) Where's the extra test imposed by the "lazy" eval?

    (Sorry if I'm missing the obvious; big dinner+long drive home = brain at half power.)

    Scott: Well, it produces an incorrect result if you do something in the second test that's more than just a test (e.g., modify a var). But surely it comes down to knowing how a language works and coding appropriately, as with any feature. (That's why I kick myself for not splitting up multiple conditions into nested IFs more often...I know how LS works but usually forget to code for it unless it'll actually cause a problem...d'oh!)

    6Bob Balaban  8/19/2009 10:52:55 PM   Lazy Evaluation : When Being Lazy Causes You More Work

    @5 - I think the "extra instruction" in the assembler-level version of the condition test would be a goto, to break out of the test sequence. At least, that's what I've seen when stepping through assembly code in the debuggerer. Doesn't seem like a huge performance hit to me.

    7Kendall  8/22/2009 9:18:28 PM   Lazy Evaluation : When Being Lazy Causes You More Work

    Thanks, Bob!

    8Richard Schwartz  8/24/2009 9:17:36 PM   Lazy Evaluation : When Being Lazy Causes You More Work

    Given that the condition is:

    while ( a OR b OR c)

    The non-short-circuit version is:

    top-of-loop:

    condition = EVAL a

    condition = condition OR EVAL b

    condition = condition OR EVAL c

    IF condition = false goto exit-loop

    stuff

    goto top-of-loop

    exit-loop:

    etc.

    The short-circuit version is:

    top-of-loop:

    condition = EVAL a

    IF condition==true goto enter-loopbody

    condition = EVAL b

    IF condition==true goto enter-loopbody

    condition = EVAL c

    IF condition = false goto exit-loop

    enter-loopbody:

    stuff

    goto top-of-loop

    exit-loop:

    etc.

    The first two IFs are the extra tests I referred to.

    Run each version through N iterations. Assume on the last iteration that the first condition will be the one that turns out false. The short-circuit version does 3(N-1)+1 EVALs + 3(N-1)+1 IFs. The non-short-circuit version does 3N evals + 2N ORs + N IFs. Assuming that results of EVALs are already in registers, an OR is probably faster than an IF because it doesn't involve loading the branch address, but really the difference is going to be trivial, so unless saving the final EVAL b or EVAL c is really a significant savings I just wouldn't consider it an optimization.

    9Phil  3/9/2012 3:30:24 AM   Lazy Evaluation : When Being Lazy Causes You More Work

    Thanks for pre-answering the question I googled without me having to look stupid when my code failed :-)