Week 8
What did you do this past week?
I finished up some assignments, had an exam, and started working on some of next week’s work. I did give myself most of a day to rest as well, so this week has been an improvement.
What’s in your way?
Still very busy, but I feel like I’m pulling along. Part of me wants to find time for hobbies and other fun things, but work gets in the way of that.
What will you do next week?
Besides an exam, next week looks a bit lighter. That isn’t to say it is, because I have two looming deadlines the week after, so I’ll probably make progress on those assignments, the IDB project being one of them.
If you read it, what did you think of Paper #8: Liskov Substitution Principle?
It’s a nice principle. It very clearly states the need to think in terms of behavior (which seems to the case when your programming model allows side effects), and enforces good usage of object oriented design. Most importantly, I think it simply boils down to this: make use of preconditions and postconditions. If no one breaks the contract created this way, many potential issues can be eliminated from the code.
What was your experience of comprehensions, generators, and yield?
Comprehensions and generators are a nice object-oriented way of expressing laziness. And laziness, speaking as a Haskell fan, is wonderful. You can avoid computing things you don’t need. You can express infinite sequences. This is probably more of a footnote, but dynamic programming can be very beautifully expressed with laziness, by defining an array in terms of itself and letting laziness determine which elements to fill in.
Ok, but this isn’t exactly how Python does things. It looks like we only get lazy iterables, for one. The rest of the programming model is still eager. This limits us, but it looks like we still have infinite sequences, and lazy mapping, which gives us the ability to process large amounts of data in a pipelined manner. And since Python doesn’t subscribe to immutability, generators can be consumed and can even be affected by changes to the underlying structure, which seems quite complex to work around, especially in a concurrent setting (although I don’t think it’ll be an issue, since we probably won’t dive into concurrency).
One thing Prof. Downing keeps saying that I am hesitant to agree with is that lazy operations are O(1). Clearly, this is true, since there is not much of an upfront cost. However, overall runtime of a program that consumes a generator will still be O(N), and there can be pitfalls to ignoring the complexity of lazy operations. One example is the Sieve of Eratosthenes. One might write:
def primes():
def filterdiv(p, xs):
return filter(lambda x: x % p, xs)
nums = itertools.count(2)
while True:
p = next(nums)
nums = filterdiv(p, nums)
yield pWhich seems to implement the Sieve lazily. One might think, filter is lazy, so it’s O(1), so finding the first N primes is O(N)! Not quite. Since we defer the evaluation of the filter, when we get the next prime, we have to force that evaluation — this means testing if the next element is divisible by all the primes before it and repeating until we find a prime. This is slow, and this is definitely not O(1). The operations that we saved by making things lazy come back to bite us when we force evaluation in next.
On the topic of yield: it’s a neat little keyword that makes expressing generators much easier. It also reminds me of coroutines and continuations (I may be forgetting the correct terminology), so I wonder if asynchronous Python code also uses it.
What made you happy this week?
Went grocery shopping and bought some more tea. It’s nice to feed my addictions, and there’s so much I want to try.
What’s your pick-of-the-week or tip-of-the-week?
There’s a very nice and enlightening paper on the limits of laziness. It uses the Haskell example of the naive sieve, which exhibits the same issues (although the Haskell syntax is much nicer, because everything is lazy and we don’t have to explicitly make iterators for it). The solution is quite interesting and gives the opportunity to use one of my favorite data structures, the pairing heap (a possible implementation of a functional priority queue).
