exec() yourself silly

Now we all know exec() is cruise-control for awesome. Despising readability, sanity, and performance, I sprinkle my code liberally with this MSG and joyfully await the ensuing migraine. But sometimes I ask myself, is it enough?

Correct Answers Considered Harmful

A wonderfully dynamic language like python lets us take exec() where no string literal has gone before by allowing us to pass in global and local environments that are used for variable lookup. The high-priests of python would have us use this functionality to constrain the side-effects of gratuitious exec()ing, but we can do so much better. A simple subclass of dict() that overrides __getitem__ and only returns the item we’re looking for 50% of the time gives us some ammo:

class AreYouFeelingLuckyDict(dict):
    #this is idealized. see complete source at end of post.
    def __getitem__(self, item):
        if random.choice([True, False]):
            return dict.__getitem__(self, item)
        else:
            raise KeyError(item)

With this dictionary implementation, we can move on to more interesting exec()s:

exec("""a = 1; print a""",
     AreYouFeelingLuckyDict(), #globals
     AreYouFeelingLuckyDict()) #locals

Because python is using instances of AreYouFeelingLuckyDict for global and local variable lookups inside our string of code, half the time the code will work properly. The other half of the time a NameError will be raised. Introducing another variable brings the odds of success to 1 in 4:

exec("""a = 1; b=2; print(a); print(b)""",
     AreYouFeelingLuckyDict(),
     AreYouFeelingLuckyDict())

Of course we can program a bit more defensively and ensure that we’ll get the output we’re looking for. If we encounter a NameError along the way, we simply try, try, and try again:

    exec("""
a=1
b=2
while True:
  try:
    print(a)
    print(b)
    break
  except NameError:
    pass
""", AreYouFeelingLuckyDict(), AreYouFeelingLuckyDict())

Keep in mind that “1” will most likely be printed out several times as its lookup occurs first (and most persistently) and the exception handling is coarse-grained. The obvious solution is to pipe the output through tail -n 2.

But Wait, There’s More

Becaue of a debilitating gambling problem, bogosort is my favorite sorting algorithm. Bogosort is the equivalent of throwing an array of items onto the floor and seeing if they’ve come up in the proper order. Given a list of N unique items, the odds of getting the answer on the first go round of bogosort are 1 in N!. Running bogosort in production on your company’s machines is like playing roullette (with an enormous wheel and your career). Feel that rush.

But bogosort gets even more awesomer with our exec() trick:

    myglobals = AreYouFeelingLuckyDict(random=random)
    mylocals = AreYouFeelingLuckyDict()
    exec("""
def sorted(is_sorted):
    prev = is_sorted[0]
    for x in is_sorted:
        if prev > x:
            return False
        prev = x
    return True

mylist = [4, 1, 9, 5]
runs = 1
while True:
    try:
        is_sorted = []
        while True:
            mutable_mylist = list(mylist)

            for i in range(len(mutable_mylist)):
                index = random.randint(0, len(mutable_mylist)-1)
                is_sorted.append(mutable_mylist.pop(index))

            if sorted(is_sorted):
                break
            else:
                runs+=1
                is_sorted=[]
        break
    except NameError:
        runs += 1
        pass
""", myglobals, mylocals)

Because I’m a generous man, I’ve modified the AreYouFeelingLuckyDict to always return a result when the item being looked up is “runs”, “NameError”, “True”, “random”, “len”, “list”, “range”, or “sorted.” It’s also worth noting that as soon as we drop into is_sorted() we’re back to a plain-jane, well-behaved locals() with boringly reliable dict-like properties.

With this bogosort modification (err, improvement) and considering a list of length 4, I figure the odds of getting an answer the first time out is 1 in 3,145,824. Now we’re talking! Of course, the code above keeps going until it sorts our list. Running it a few times, I’ve seen the answer produced in as little as 700,000 tries. A paragon of efficiency.

Wink

I hope you’ve enjoyed this. I’ve been playing around with this post for a while and have had a great time. The source to this party can be found in this gist: https://gist.github.com/945666

Also, please check out Be careful with exec and eval in Python which inspired this post.

thatmattbone.com