I’ve intermittently read SICP over the past few years, but never made it past the second chapter. One of my goals for the year is to get through the whole book. I’ve created a github repo (https://github.com/edtan/sicp) containing my solutions and will try to work on problems every day for 15-30 minutes.
So far, I’ve just finished sections 1.1 and 1.2, and here are some notes of some topics I found interesting:
- Tail recursion: Iterative processes, even if they are implemented using recursive procedures, can be optimized to use constant space instead of taking linear space (e.g. taking up stack space with each additional procedure call). It looks like Python doesn’t have this enabled, as it can lead to misleading stack traces, and is an available option in Ruby but not enabled by default.
- Applicative vs. normative order execution: It seems applicative vs. normative order execution can actually change the run time of an algorithm depending on which one is used. See exercise 1.26 where it seems this makes a difference between O(log n) and O(n). The main idea here is that if we have a tree-recursive call, the operands may be executed once or twice depending of the type of execution.