# SICP Section 1.3

## Procedures as Arguments

Why ‘high order procedures’ is useful?

Often the same programming pattern will be used with a number of different procedures. To express such patterns as concepts, we will need to construct procedures that can accept procedures as arguments or return procedures as values. Procedures that manipulate procedures are called high-order procedures, they can serve as powerful abstraction mechanisms, vastly increaseing the expressive power of our language.

## Lambda

• Using lambda to create anonymous functions:
• (define (plus4 x) (+ x 4)) is equivalent to (define plus4 (lambda (x) (+ x 4)))
• Using lambda(let) to create local variables
Sometimes we can use internal definitions to get the same effect as with let.

And in which cases we couldn’t get the same effect?

## Abstractions and first-class procedures

As programmers, we should be alert to oppotunities to identify the underlying abstractions in our programs and to build upon then and generalize them to create more powerful abstractions. This is not to say one should always write programs in the most abstract way possible; expert programmers know how to choose the level of abstraction appropriate to their task. But it’s important to be able to think in terms of these abstractions, so that we can be ready to apply them in new contexts.

## Exercises

This is not very hard, just simply translate the simpson rule definition to code:

Put both the recursive and iterative versions here to compare:

They produce the same results as expected.

There might be better ways to translate the formula. The solution above the is not veru accurate and if the upper bound is too large (say 100), it will yield to ‘nan+’.

Apply (f f) with get (f 2), while tring to apply (f 2), error will be issued since a procedure is expected but an integer parameter 2 is given.

# SICP Section 1.2

## Recursive Process V.S. Iterative Process

• Recursive process

The substitution model of a recursive process reveals a shape of expansion followed by constraction. The expansion occurs as the process builds up a chain of defered operations. The contraction occurs as the operations are actually performed.

• Iterative process

An iterative process is one whose state can be summarized by a fixed number of state variables, together with a fixed rule that describes how the state variables should be updated as the process moves from state to state and an (optional) end test that specifies the conditions under which the process should terminate.

In the iterative case, the program variables provide a complete description of the state of the process at any point, while in the recursive case, there is some additional "hidden" information, maintained by the interpreter and not contained in the program variables.

In contrasting iteration and recursion, we must be careful not to confuse the notion of a recursive process with the notion of a recursive procedure. When we describe a procedure as recursive, we are referring to the syntactic fact that the procedure definition refers (either directly or indirectly) to the procedure itself. But when we describe a process as following a pattern that is, say, linearly recursive, we are speaking about how the process evolves, not about the syntax of how a procedure is written. It may seem disturbing that we refer to a recursive procedure as generating an iterative process.

## Lame’s Theorem

If Euclid’s Algorithm requires k steps to compute the GCD of some pair, then the smaller number in the pair must be greater than or equal to the kth Fibonacci number.

## Fermat’s Little Theorem

If n is a prime number and a is any positive integer less than n, then a raised to the nth power is congruent to a modulo n.

## Exercises

1.9 Answer: The first process is recursive and the second one is iterative.

1.10 Answer: from the definition of (A x y), we have:

(A 1 10) = A(0 (A 1 9)) = 2 * (A 1 9) = … = 2^9 * (A 1 1) = 2^10

(A 2 4) = 65536

(A 3 3) = 65536

(f n) computes 2n

(g n) computes 2^n

(h n) computes 2^2^2… (n times)

1.11 Answer: This is similar with the example of computing Fibonacci number.

1.12

a. from the the procedure definition, suppose p will be called t times, we have:

a / (3^t) <= 0.1, which leads to:

log(10a) <= t, so t = ceiling (log(10a)) = 5, (the base of the log is 3)

b. both the space and number of steps depend on how many times p is called, so it’s O(t) = O(log(a)).

1.16

1.17

1.18

1.19

1.21

Since Scheme has built-in support for arbitrary precision arithmetic, the procedure will produce the same result as the original expmod, however, it will be very inefficient since the huge number arithmetic will take much longer time than the numbers can be represented by a single computer word.

The original expmod used the successive squaring, the numbers to be processed will never be larger than m^2.

With the calling of square, the original problem can be reduced to a sub problem with half of the size at each of the step when even? test is true. So T(n) = T(n/2) = O(logn)

However, if the explicit multiplication used instead, the recursive call of expmod will be evaluated twice, it not only just compute the sub problems two time, it is actually a tree recursion like the first solution for computing fibnacci sequence, so the number of expmod calls grow exponentially, which conclues that T(n) = O(2^n * logn) = O(n)

1.27

1.28

# SICP Section 1.1

Computational processes are abstract beings that inhabit computers. As they evolve, processes manipulate other abstract things called data. The evolution of a process is directed by pattern of rules called a program.

Why use Lisp for the book?

The most significant unique feature of Lisp is the fact that Lisp descriptions of processes, called procedures, can themselves be represented and manipulated as Lisp data. The importance of this is that there are powerful program-design techniques that rely on the ability to blur the traditional distinction between "passive" data and "active" processes.

The three mechanisms of combining simple ideas to form more complex ideas in any powerful programming languages:

1. primitive expressions
2. means of combination
3. means of abstraction

## Substitution model

• Applicative order

Evaluate the operator and operands first and then applies the resulting procedure to the resulting arguments. "Fully expand and then reduce"

• Normal order

Don’t evaluate the operands until their values are needed, instead, substitute operand expressions for parameters until it obtained an expression involving only primitive operators, and would then perform the evaluation. "Evaluate the arguments and then apply"

## Example: Square Roots by Newton’s Method

The contrast between function and procedure is a reflection of the general distinction between describing properties of things and describing how to do things, or, as it is sometimes refered to, the distinction between declarative knowledge and imperative knowledge. In mathematics we are usually concerned with declarative (what is) descriptions, whereas in computer science we are usually concerned with imperative (how to) descriptions.

## Exercises

1.3 Define a procedure that takes three numbers as arguments and return the sum of squares of the two larger numbers.

1.4 Observe that our model of evaluation allows for combinations whose operators are compound expressions. Use this observation to describe the behavior of the following procedure:

if b is greater than 0, the operator that will apply to a and b is +, or else it will be -, so the a-plus-abs-b will always result in a plus abs of b.

1.5 Answer: the interpreter that uses applicative order evaluation will hang due to the infinite recursive call of ‘p’, while an interpreter that uses normal order evaluation will get 0.

Note: p is a function, (p) is a call to function p.

1.6 Answer: the interpreter will hang due to the infinite recursive call to sqrt-iter. Since List uses applicative order evaluation, in the definition of new-if, the else-clause will always be evaluated no matter the result of the predicate, thus lead to infinite recursive call to sqrt-iter. That’s why if needs to be a special form, the predicate expression is evaluated first, and the result determines whether to evaluate the consequent or the alternative expression.

1.7 Answer: For small values, the absolute tolerance 0.001 is too large, so the results become inaccurate. For example, (sqrt 0.001) gives 0.04124542607499115 on my machine. (ubuntu 12.10 x86_64); And for large values, due to the precision limitation of float-point representation, the guess couldn’t be refined to a value that can be represented within the tolerance. In such cases, the program can endlessly alternate between two guesses that are more than 0.001 away from the true square root.

so, instead of using absolute tolerance, we changed to use the relative tolerance of two continuous guess values. This can be demonstrated with the below updated good-enough? procedure:

1.8

The only difference between cbrt and sqrt is the improve procedure.

# Coursera Online Functional Programming Course - a Retrospective

Here comes the summary of the Coursera course Fucntional Programming Principles in Scala It’s a little bit late, it has been two months since I finished the course. This is the first Coursera course I followed from the very beginning to the end and accomplished all the programming assignments with full scores, which helped me to get the certificate with distinction.

First the excellent parts of the course:

• Martin Odersky is a pretty good teacher, and all the lectures are well designed. I enjoyed watching the lectures a lot and most of which I have read more than once.
• The programming assignments are well structured, with detailed instructions and step by step guide. In each of the assignments, the whole task is split into several steps with approprivate level of abstractions.
• There are also many useful supporting materials like scala style guide, sbt tutorial, instructions on tools setup for the course, which made it easier to concentrate on the course content. For me, I don’t have scala develop environment setup before the course, and by following the tools setup section in only took me less than half an hour to get everything ready for trying the example code and the assignments.

As for the less-good things, I would say:

• Both the lectures and the assignments are quite easy for an experienced programmers (No functional programming background needed), I was expecting more challenging stuff.
• There are no official solutions distributed. (The course will be offered again some time later) However, I still think for those students who passed the course should be qualified to get the solutions so that they can compare those with their own to see where they can still improve.
• It’s a pity that this is only the first half of an advanced undergraduate course that Martin taught on campus. I am interested in the other half.

After taking this cousre, I got a deeper understanding of the functional programming basics and it made me feel more comfortable while picking up SICP again (after 3 years). Now, I am convinced that I am able to go through SICP and finish most of the exercises. Also, I had a firmer grasp of Scala even though I didn’t write more than 100 lines of Scala before; I understand more about the scala syntax, idioms and even the motivations behind some of the language structures. E.g., call by name/value, lazy evaluation, currying, pattern matching and so on. I will publish my detailed notes on the lectures and assignments to this blog later.

To conclude, I really enjoyed taking the course and many thanks to Martin , the TAs, and also the coursera staff for offering such a wonderful course.

# Python Abc

## Introduction

This module provides the infrastructure for defining abstract base classes (ABCs) in Python. The ABCs define a minimal set of methods that establish the characteristic behavior of the type. For more details about this, see PEP 3119.

## Highlights

The module provides a metaclass used to create ABCs. An ABC can be subclassed directly. The class also has a ‘register’ method to register unrelated concrete classes (including built-in classes) and unrelated ABCs as ‘virtual subclasses’

Also there are two decorators abstractmethod and abstractproperty, which will set the function object’s attribute ‘__isabstractmethod__’ to True. Only when all of the abstract methods and abstract properties are overriden, can a class that has a metaclass derived from ABCMeta be instantiated.

### ABCMeta.__new__

• It first creates a ‘type’ object cls. (super(ABCMeta, mcls) is ‘type’)
• Iterate through all the attributes (including all the attributes inherited from all the bases), if any of them have ‘__isabstractmethod__’ set to true, add it to cls’s __abstractmethods__.
• Initialize the attributes ‘_abc_registry’, ‘_abc_cache’, ‘_abc_negative_cache’ and ‘_abc_negative_cache_version’, which are used to speed up the check in __instancecheck__ and __subclasscheck__.

### ABCMeta.__subclasscheck__

The code and comment in this function is very clear and straightforward.

Just make sure the different cases needed to check:

1. check the subclass hook
2. check if it’s a direct subclass through __mro__
3. check if it’s a subclass of a registered class (issubclass is called to do recursive check)
4. check if it’s a subclass of a subclass (issubclass is called to do recursive check)

In this post, we only talk about the defitions of ABCMeta. We will see the typical usages in the collections module.

# Python Bisect

## Introduction

This module provides support for maintaining a list in sorted order without having to sort the list after each insertion. It uses a basic bisection algorithm similar with the classic binary search.

The above binsearch function will return the first of the elements that equals to the target if there are more than one. Sometimes it’s required to find the left most one or the right most one. We can achieve this by using the bisect() functions. Let’s examine the pre and post conditions, and also loop invariants.

After exiting the loop, we have lo == hi. Now we have to distinguish some cases:

• If lo == l, from the third conjunct, we know that a[hi] > x, and since lo == hi, we have a[lo] > x. In this case, all e in a[l:h] > x
• If hi == h, from the second conjunct, we know that a[lo - 1] < x, in this case, all e in a[l:h] <= x
• if lo != l and hi != h, from the second and third conjuncts, we know that a[lo - 1] <= x, a[hi] > x. The post condition still holds.

We can do the same analysis on the function bisect_left().

Note: In the pre condition I explicitly written down that lo < hi is required, the code will directly return lo when hi is less than or equal to lo, but that’s simply meaningless, if this is the case, the sorted order of ‘a’ after we insert element before the index returned by the function.

In the doc of the module, it’s bisect.bisect_right(a, x, lo=0, hi=len(a)) while in the source code, it’s def bisect_left(a, x, lo=0, hi=None)

bisect.bisect_right(a, x, lo=0, hi=len(a)) is not valid python code, you will get error like this: NameError: name ‘a’ is not defined. This is because default values are computed and bound at the function definition time rather than when you call the function. This means that you can’t have a default which is dependent on something that is not known until the function is called.

## Pythonic stuff

### Gotcha – Mutable default arguments

See here for more details.

# Support LaTex in Octopress

It took me some time to finally get latex math formulas working in Octopress. If you googled ‘Octopress latex’, you can get quite a few online resources about how to support latex in octopress, with various levels of complexity. In this post, I will write down how I achieve this.

## The initial attempt

As I installed the jekyll-rst plugin to use rst to write my posts, I thought it should be easy to write latex math because docutils has native support for it since version 0.8 (A :math: role and also a .. math: directive introduced for that). However, after I tried to use these in a octopress post, I found that the post will be rendered to empty. For example, if I insert the following rst code into my post, the whole post becomes empty; but after removing this line, everything is fine.

I also verified that the exact same code can be successfully converted to valid html using the ‘rst2html.py’ script on my system, so I guess maybe something is wrong in ‘RbST’. I found that in RbST, it has its own copies of rst2html and rst2latex tools under ** /gems/RbST-0.1.3/lib/rst2parts **,

which will be used in rbst.rb. I have even tried to change rbst.rb to use the rst2html.py installed on my system, but this also didn’t get any luck.

Finally, I gave up on this and opened an issue on this for the jekyll-rst plugin. Hope the author can fix this.

## Switch back to markdown and using kramdown

First, install kramdown: gem install karmdown

Then, add mathjax configs into <head></head> tag, in octopress, just add the below code into /source/_includes/custom/head.html:

See here for more details. After this, we are ready to test latex math in our post. For example:

will render as

And for inline latex code, just use $\exp(-\frac{x^2}{2})$, which will give $\exp(-\frac{x^2}{2})$.

# Python Heapq

## Introduction

The module provides an implementation of heap queue algorithm, also known as priority queue algorithm.

## Highlights

• Zero-based indexing is used, so the children’s index of node with index k are (2*k + 1) and (2*k + 2) respectively.
• Internally a ‘min heap’ is maintained rather than ‘max heap’, which is more generally used in algorithm textbooks.
• Three general functions based on heaps are also provided:

## Pythonic stuff

### Rich comparison methods

In python, there are 6 so called "Rich Comparison" methods, x < y calls x.__lt__(y) and others are similar (__le__ and <=; __gt__ and >=; __eq__ and ==; __ne__ and <>). Arguments to rich comparison methods are never coerced. see coercion

### Why heapify(x) is O(n)?

This is not obvious at first by seeing the code, given that there is a ‘while’ loop in _siftup and also a while loop in _siftdown(called in _siftup). Let’s look into it further:

1. in the while loop of _siftup, it takes O(L) time for nodes that L levels above leaves.
2. and in the while loop of _siftdown called in _siftup, it takes at most L steps, so _siftdown is O(L).
3. since we have n/4 nodes in level 1, n/8 nodes in level 2, and finally one root node, which is lg(n) levels above leaf, so the total amount in the while loop of heapify is:
n/4 * c + n/8 * c + n/16 * 3c + … + 1 * lg(n) * c, and let n/4 = 2^k, after simplification, we get:
c * 2^k(1/2^0 + 2/2^1 + 3/2^2 + … + (k+1)/2^k), as the limit of (k+1)/2^k is 0 when k is infinite, so the term in the brackets bound to a constant, from this we can conclude that heapify is O(2^k), which is O(n).

### Why it continues to find the smaller child until a leaf is hit in _siftup?

As explained in the comment by the module author, this is a ad hoc to reduce the comparisons on the following operations on the heap.

# Introduction on Reading Source of Python Standard Libraries Series

I am going to start the series of posts on reading the source of python standard modules. I will go with the pure python modules first, and maybe later I can continue with C implementations of the modules. Let’s see how far I could go.

## What will be included

• A brief introduction of the module. (It should be very short, people can go to the standard library doc for more information.)
• Special highlights about the important APIs, implementation details.
• Python features/idioms/tricks/gotchas that worth the whistle, especially those I was not familiar with
• Detail explanations about the tricky part of the code if any

## What will not be included

Also, alone the way, I may start another series on some specific ‘advanced topics’ in python, like descriptor, decorator, method resolution order(mro) and so on. Mainly about why they are introduced into python, how they are used and the typical use cases. This is inspired by the blogs about python history

This post will also be used to track my progress.

# Octopress and Github

This post documents how I set up this blog and the problems encounted. Octopress is quite popular recently and you can just find a huge number of bloggers who have written about how to set this up online. My main references are Setting up a blog on Octopress and github and Blog = Github + Octopress (In Chinese).