The sections introduces us to trees using pairs as the underlying structure.

Section example

1
2
3
4
5
6
7
8
9
10

(define (count-leaves x)
  (cond ((null? x) 0)
        ((not (pair? x)) 1)
        (else (+ (count-leaves (car x))
                 (count-leaves (cdr x))))))

(define x (cons (list 1 2) (list 3 4)))

(count-leaves x)
(count-leaves (list x x))

Each exercise of SICP makes me think more about recursion. The following exercise made me think more about how to model recursion and what the returns are to be when recursing multiple layers inside a tree.

Exercise 2.27

1
2
3
4
5
6
7
8

(define (deep-reverse items)
  (define (deep-reverse-iter items ans)
    (cond ((null? items) ans)
          ((not (pair? items)) items)
          (else (deep-reverse-iter (cdr items)
                                   (cons (deep-reverse-iter (car items) nil)
                                         ans)))))
  (deep-reverse-iter items nil))

Exercise 2.28

1
2
3
4
5
6
7
8

;;Exercise 2.28
(define (fringe items)
  (define (fringe-iter list1 ans)
    (cond ((null? list1) ans)
          ((pair? list1) (append (fringe-iter (car list1) nil) (fringe-iter (cdr list1) nil)))
          (else (list list1))))
  (fringe-iter items nil)
  )

Exercise 2.30

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

;;Exercise 2.30
(define (square-tree tree)
  (cond ((null? tree) nil)
        ((not (pair? tree)) (square tree))
        (else (cons (square-tree (car tree))
                    (square-tree (cdr tree))))))

(define (square-tree tree)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
           (square-tree sub-tree)
           (square sub-tree)))
       tree))

(square-tree
  (list 1
        (list 2 (list 3 4) 5)
        (list 6 7)))

Exercise 2.31

1
2
3
4
5
6
7
8

(define (tree-map proc tree)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
           (tree-map proc sub-tree)
           (proc sub-tree)))
       tree))

(define (square-tree tree) (tree-map square tree))

Exercise 2.32 could have been written better if currying was available. I am not sure whether scheme supports currying functions, and hence the regular lambda expression.

Exercise 2.32

1
2
3
4
5
6
7

;;Exercise 2.32
(define (subsets s)
  (if (null? s)
    (list nil)
    (let ((rest (subsets (cdr s))))
      (append rest (map (lambda (x) (cons (car s) x)) rest)))))
(subsets (list 1 2 3))

Exercise 2.20 deals with functions that take arbitrary number of arguments. This is extremely useful in the context of scheme because it allows you to use less brackets :).

Exercise 2.20

1
2
3
4
5
6
7
8

(define (same-parity elem . xlist)
  (define (same-parity-iter res-list num-list)
    (if (null? num-list)
      res-list
      (if (= (remainder (+ elem (car num-list)) 2) 0)
        (same-parity-iter (cons (car num-list) res-list) (cdr num-list))
        (same-parity-iter res-list (cdr num-list)))))
  (reverse (same-parity-iter (list elem) xlist)))

I used reverse followed by the same-parity-iter because I did not want to use the inefficient append function.

1
2

(same-parity 1 2 3 4 5 6 7)
mcons 4 (mcons 3 (mcons 5 (mcons 7 '()'))))

The sections also introduces us to the map higher order function.

1
2
3
4
5

(define (map proc items)
  (if (null? items)
    nil
    (cons (proc (car items))
          (map proc (cdr items)))))

But why map? Quoting SICP

The different between the two definitions is not that the computer is performing a different process (it isn’t) but that we think about the process differently. In effect, `map` helps establish an abstraction barrier that isolates the implementation of procedures that transforms lists from the details of how the elements of the list are extracted and combined.

This is the most succint way to put across the need for abstractions. Abstractions are invented to help us think differently and care about different things.

Exercise 2.21

1
2
3
4
5
6
7
8
9
10
11
12
13

;;Exercise 2.21
;; without using map
(define (square x) (* x x))
(define (square-list items)
  (if (null? items)
    nil
    (cons (square (car items))
          (square-list (cdr items)))))

;;with using map
(define (square-list items)
  (map (lambda (x) (* x x))
       items))

Exercise 2.22

1
2
3
4
5
6
7
8
9
10
11

;;Exercise 2.22
;; Iterative square list

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
      answer
      (iter (cdr things)
            (cons (square (car things))
                  answer))))
  (iter items nil))

Interchanging the arguments of cons does not work as it will generate a list of lists instead of generating a single list.

Exercise 2.23

1
2
3
4
5
6
7
8
9

;; Exercise 2.23

(define (for-each proc items)
  (cond ((null? items) #t)
        (else (proc (car items))
              (for-each proc (cdr items)))))

(for-each (lambda (x) (newline) (display x))
          (list 57 321 68))

I recently got gifted the book Structure and Interpretation of Programs(SICP) on my birthday. I have had a long desire to go through the complete book and complete all the exercises. Inspired by Eli Bendersky’s, I am going to spend the next 6 months or maybe a year going through the book. I have already finished the first chapter of the book. Hence I will be blogging only from chapter 2. I am going to follow the plan laid out by Eli Bendersky, the plan being

• Read the book
• See all the video lectures by Sussman and Abelson
• Do all the exercises in the book.
• Write about the exercises and the things that I have learnt from it.

This happens to be the last week of GSoC. The major things that I accomplished this week are

• Got pylab to work interactively.
• Made more changes to the documentation of plotting module.

I have a pull request for the restructured plotting module at here. There has been lots of discussions on how the new plot API should look like in the pull request. The API as of now has 5 functions:

• plot_line which plots 2D line plots, which I think I will change to plot.
• plot_parametric which plots 2D parametric plots.
• plot3D which plots 3D plots.
• plot3D_parametric which plots 3D parametric line plots. I think I will have to change it into plot_parametric3D.
• plot3D_surface which plots 3D parametric surfaces.

The names are slightly confusing, but the alternative to these names are big. If you have any good names for 3D plots, please leave it in the comments.

I will have another post describing the things I learnt over this GSoC period.

I got my adaptive sampling branch merged last week. Now the plots are sampled adaptively and is more accurate. I also added a lot of tests to the implicit plotting branch and the coverage now is greater than 90%.

One of the major things decided in the previous week was to restructure the plot function. Presently plot is a single function, which depending on its input, renders an 2d or an 3d plot. Though it plots the right kind of plot, the plot function is quite complex and it was decided to split the plot function into smaller functions that plots a particular type of plot. I tried an approach where all 2D plots are plotted by a plot2d function, the 3D plots by plot3D and the existing plot_implicit plots to plot regions and implicit equations. Aaron mentioned that the API is still very complex as I was using tuples and lists to differentiate between a parametric plot and a 2d line plot and he was right. It is a bit complex and it was decided to have a functions for each kind of plot.

I think i can have the new plot functions as an PR by next week and I would like to try getting a Mayavi backend ready by the end of my GSoC period.

I forgot to mention why I deviated from my what I said I would do in my GSoC application. I tried getting a svgfig backend ready for almost one and a half week, and it was quite difficult. svgfig is not being updated and I had a hard time getting the axis ticks labelling to work most of the time. I wrote to the project maintainer many times and he helped me with a lot of things, but the library was not polished enough to use it with Sympy Live. So plotting for SymPy Live should be attempted with a javascript plotting library rather than a python backend. If we get matplotlib support on GAE, then it would be awesome.