CS Musings

Installing CouchDB 0.11 on Ubuntu 10.4 Lucid

Jason — Tue, 25 May 2010 05:34:23 +0000

After much soul-searching, I’ve finally figured out the full script for setting up couchdb from source on a newly minted Ubuntu 10.4 Lucid image on linode (should work elsewhere).

Some notes:

this shell script is my first attempt at one, so it doesn’t have anything other than a list of commands. I tried to put 1.9.2.3 (version number of xulrunner) in a variable, but that failed as well. So if anyone can help me improve it, it would be much appreciated!
to use it, download the latest source (0.11 at the time of writing), extract it (tar -xzf name-here), and drop the shell script into the root folder.

The sources/inspiration for this scheme is as follows:
http://wiki.apache.org/couchdb/Installing_on_Ubuntu – official wiki, but the instructions are misleading and incomplete, you need to do a lot of other directory stuff just to get it running.
http://depth-first.com/articles/2010/01/28/pubcouch-install-couchdb-on-ubuntu-karmic-from-source – this is generally very complete, but dated for lucid. In particular, libmozjs-dev is no longer available, replaced with xulrunner, as per instruction in the official wiki.

Bash History Command

Jason — Fri, 30 Oct 2009 18:55:19 +0000

Recently I came across an idea to more effectively search through the history of commands I typed. I already know about the up arrow will revisit the history in reverse chronological order. However, I would like to have a better way of searching for the command I typed.

Typing CTRL-r would give you a prompt and you can start typing in commands you already entered and it will search through the history and find the most recent command fit the description already provided. Very useful for long command you typed recently and do not want to type them out again.

Another thing I have found is putting HISTCONTRL=erasedups in your ~/.bashrc, it will prevent any duplicates from appearing in the history file and therefore allow for more space to put more commands.

Exercise 4-2

Jason — Fri, 03 Jul 2009 20:52:08 +0000

This particular problem comes from the book Erlang Programming published in 2009 by O’reilly, it is the ring message problem (ring.erl).

It took me a while to do this problem because this is my first foray into concurrency, and I’m not used to the way they pass information around (always tries to pass information in function parameters). However, after a few failed iterations, this is my solution. It is not as elegant as some of the solution online, and the best one I’ve seen uses foldr to shorten the program.

If there is any questions/problems regarding my code, please don’t hesitate and ask in the comments!

-module(ring).
 
-export([start/3, construct/4, loop/2]).
 
start(M, N, Msg) ->
	io:format("~p Testing ~p~n", [self(), Msg]),
	spawn(ring, construct, [true, N, M, Msg]).
 
construct(true, Count, M, Msg) ->
	Pid = spawn(ring, construct, [self(), Count-1, M, Msg]),
	loop(Pid, M);
 
construct(First, 0, _, Msg) -> First ! Msg;
 
construct(First, 1, M, Msg) ->
	spawn(ring, construct, [First, 0, M, Msg]),
	loop(First, M);
 
construct(First, Count, M, Msg) ->
	Pid = spawn(ring, construct, [First, Count-1, M, Msg]),
	loop(Pid, M).
 
loop(Next, 0) ->
	io:format("~p Stopping~n", [self()]),
	Next ! stop;
 
loop(Next, M) ->
	receive
		stop ->
			io:format("~p Stopping Abornomally~n", [self()]),
			true;
		Msg ->
			io:format("~p Received ~p~n", [self(), Msg]),
			Next ! Msg,
			loop(Next, M-1)
	end.

Section 3.1

Jason — Mon, 25 Aug 2008 23:00:30 +0000

I have skipped two sections on data-directed programming and generic operations. I have read through most of the texts, but I did not do any exercises for them, it seems boring enough that when I have more time in the future (or when I need the knowledge), I will come back and do the exercises.

I hope I will not skip anymore sections in the future.

Here are my solutions to section 3.1:

Exercise 3.1

This exercise should be quite simple as long as you understands the examples outlined before.

;; 3.1
(define (make-accumulator init)
  (lambda (x)
    (set! init (+ init x))
    init))
"3.1"
(define A (make-accumulator 5))
(A 10)
(A 10)

Exercise 3.2

This exercise is basically a modification to 3.1 with care and attention to the return value of the function.

;; 3.2
(define (make-monitored fun)
  (define calls 0)
  (lambda (x)
    (if (equal? x 'how-many-calls?)
        calls
        (begin
          (set! calls (+ calls 1))
          (fun x)))))
"3.2"
(define s (make-monitored sqrt))
(s 100)
(s 'how-many-calls?)

Exercise 3.3

Some thought (or not) should tell you that only dispatch needs modification, and that is the bottleneck in which all of the request are directed, so as to remove the need to modify every transaction function. One note, I made the wrong-pass function take in one parameter because of a need to return a function that takes in one parameter. Since error cannot be used because there could be more actions with the correct password following it, this is the minimal change action.

(define (make-account balance password)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
               balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (define (wrong-pass any)
    "Incorrect Password")
  (define (dispatch pass m)
    (if (eq? pass password)
        (cond ((eq? m 'withdraw) withdraw)
              ((eq? m 'deposit) deposit)
              (else (error "Unknown request -- MAKE-ACCOUNT" m)))
        wrong-pass))
  dispatch)
 
"3.3"
(define acc (make-account 100 'secret-password))
((acc 'secret-password 'withdraw) 40)
((acc 'some-other-password 'deposit) 50)

Exercise 3.4

This exercise is a simple change to 3.3, same rationale for call-the-cops function taking in one parameter.

;; 3.4
(define (make-account balance password)
  (define cop-counter 0)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
               balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (define (wrong-pass any)
    "Incorrect Password")
  (define (call-the-cops any)
  "calling cops")
  (define (dispatch pass m)
    (cond
      [(eq? pass password)
       (set! cop-counter 0)
       (cond ((eq? m 'withdraw) withdraw)
             ((eq? m 'deposit) deposit)
             (else (error "Unknown request -- MAKE-ACCOUNT" m)))]
      [else
       (set! cop-counter (+ cop-counter 1))
       (if (>= cop-counter 7)
           call-the-cops
           wrong-pass)]))
  dispatch)
"3.4"
(define acc (make-account 100 'secret-password))
((acc 'secret-password 'withdraw) 40)
((acc 'some-other-password 'deposit) 50)
((acc 'some-other-password 'deposit) 50)
((acc 'some-other-password 'deposit) 50)
((acc 'some-other-password 'deposit) 50)
((acc 'some-other-password 'deposit) 50)
((acc 'some-other-password 'deposit) 50)
((acc 'some-other-password 'deposit) 50)

Exercise 3.5

I took Eli’s advice and changed the random-in-range function so it accepts in-exact numbers. Mainly due to plt-scheme’s insistence on being precise whenever possible, such as using fractions when I want decimals.

;; 3.5
(define (random-in-range low high)
  (let ([range (- high low)])
    (+ low (* (random) range))))
 
(define (monte-carlo trials experiment)
  (define (iter trials-remaining trials-passed)
    (cond ((= trials-remaining 0)
           (/ trials-passed trials))
          ((experiment)
           (iter (- trials-remaining 1) (+ trials-passed 1)))
          (else
           (iter (- trials-remaining 1) trials-passed))))
  (iter trials 0))
 
(define (estimate-integral p x1 x2 y1 y2)
  (define (ei)
    (p (random-in-range x1 x2) (random-in-range y1 y2)))
  (let* ([trials 1000000]
         [success (monte-carlo trials ei)])
    (* (- x2 x1) (- y2 y1) success)))
 
(define (unit-circle x y)
  (<= (+ (* x x) (* y y)) 1))
 
"3.5"
(estimate-integral unit-circle -1.0 1.0 -1.0 1.0)

Exercise 3.6

This question is simple if you look through the scheme documentation and find random-seed. random-seed basically seeds the random generator with the value specified.

;; 3.6
(define (rand symb)
  (cond
    [(eq? symb 'generate) (random)]
    [(eq? symb 'reset) random-seed]))
"3.6"
(rand 'generate)
((rand 'reset) 0)
(rand 'generate)
(rand 'generate)
((rand 'reset) 0)
(rand 'generate)
(rand 'generate)

Exercise 3.7

For this exercise, it could be simple if it does not have the requirement that make-joint should fail when the second argument is not the correct password. If it does not have that requirement, then there is no need to modify the make-account function at all. Since it has that, I added a way to check the account password into the make-account from 3.3.

;; 3.7
(define (make-account balance password)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
               balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (define (wrong-pass any)
    "Incorrect Password")
  (define (check-pass pass)
    (eq? pass password))
  (define (dispatch pass m)
    (if (eq? m 'check-pass)
        check-pass
        (if (eq? pass password)
            (cond ((eq? m 'withdraw) withdraw)
                  ((eq? m 'deposit) deposit)
                  (else (error "Unknown request -- MAKE-ACCOUNT" m)))
            wrong-pass)))
    dispatch)
 
(define (make-joint acc orig-pass new-pass)
  (define (wrong-pass any)
    "Incorrect Password")
  (if ((acc orig-pass 'check-pass) orig-pass)
      (lambda (pass m)
        (if (eq? pass new-pass)
            (acc orig-pass m)
            wrong-pass))
      wrong-pass))
 
"3.7"
(define peter-acc (make-account 100 'open-sesame))
((peter-acc 'open-sesame 'withdraw) 40)
(define paul-acc
  (make-joint peter-acc 'open-seasame 'rosebud))
((paul-acc 'rosebud 'withdraw) 40)

Exercise 3.8

This question took me a while to get simple enough. Basically, the question asks you to flip a switch on the first pass and return 0 on the second pass, thus yield the result. For example, if evaulated from right to left, question asks (+ (f 0) (f 1)) to return 1. From my understanding, it is asking for a function f that when it pass over (f 1), it sets a state variable to 1, and then when it pass over (f 0), it returns 0. Same logic goes for the other way. Another note is how to test the program, we can force the excution one way or another by seperating out the function calls. If we want to evalulate (f 1) first, we just put it before (f 0).

;; 3.8
(define f
  (let ([state -1])
    (lambda (x)
      (cond
        [(= state -1) (set! state x) x]
        [else 0]))))
"3.8"
(f 1)
(f 0)

SICP 2.3

Jason — Thu, 21 Aug 2008 05:41:07 +0000

This will be the first section that I will post as I work through it. My hope from this point on is to complete one section per two day, see how that works out.

Skipped: 2.65, 2.71, 2.72

Without further ado, here is the first question:

Exercise 2.53:

For this exercise, just need to plug the expressions into a scheme interpreter and see what is the result.

Exercise 2.54:

This exercise is simple in that the book gave the algorithm to the reader already and all that is left to do is to implement the algorithm.

;; 2.54
(define (my-equal? obj1 obj2)
  (cond
    [(and (not (pair? obj1)) (not (pair? obj2)))
     (eq? obj1 obj2)]
    [(and (pair? obj1) (pair? obj2))
     (and (my-equal? (car obj1) (car obj2))
          (my-equal? (cdr obj1) (cdr obj2)))]
    [else #f]))
"2.54 - my-equal?"
(my-equal? '(this is a list) '(this is a list))
(my-equal? '(this is a list) '(this (is a) list))

Exercise 2.54:

This one is slightly more tricky, due to the fact that I do not think that the book explained how quoting worked exactly in the implementation. It only shows the ‘(elements…) syntax, but in fact it is just syntactical sugar for a more basic syntax (quote elements…). After realizing that, it is a simple matter of expanding the given expression: (car ”abracadabra) -> (car (quote ‘abracadabra)) -> (car (quote (quote abracadabra))) -> (car ‘(quote abracadabra)) -> ‘quote

Symbolic Differentiation

Now we get into a meaty project in the book. By the end of the next 3 exercises, you will have implemented a reasonable symbolic differentiator.

The following is the code given in the book right before the first exercise, for each exercise, I will use these pre-existing code as a base and redefining functions as needed.

;; Symbolic Differentiation
(define (variable? x) (symbol? x))
 
(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))
 
(define (sum? x)
  (and (pair? x) (eq? (car x) '+)))
 
(define (addend s) (cadr s))
 
(define (augend s) (caddr s))
 
(define (product? x)
  (and (pair? x) (eq? (car x) '*)))
 
(define (multiplier p) (cadr p))
 
(define (multiplicand p) (caddr p))
 
(define (=number? exp num)
  (and (number? exp) (= exp num)))
 
(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (list '+ a1 a2))))
 
(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (list '* m1 m2))))
 
(define (deriv exp var)
  (cond [(number? exp) 0]
        [(variable? exp)
         (if (same-variable? exp var) 1 0)]
        [(sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var))]
        [(product? exp)
         (make-sum
          (make-product (multiplier exp)
                        (deriv (multiplicand exp) var))
          (make-product (deriv (multiplier exp) var)
                        (multiplicand exp)))]
        [else
         (error "unknown expression type -- DERIV" exp)]))
"SD - Example"
(deriv '(+ x 3) 'x)
(deriv '(* x y) 'x)
(deriv '(* (* x y) (+ x 3)) 'x)

Exercise 2.56:

This exercise tests the reader’s understanding of the code given and his ability to extend the code. It is quite simple as long as you understand how each component fits together. Also you have to understand the purpose of the helper functions and learn to compose your own as needs arise. One extra function I have defined other than those specified in the problem description is make-subtraction. Since you need to do subtraction in the result as a general function.

;; 2.56
(define (exponentiation? x)
  (and (pair? x) (eq? (car x) '**)))
 
(define (make-exponentiation b e)
  (cond
    [(=number? e 0) 1]
    [(=number? e 1) b]
    [(and (number? b) (number? e)) (expt b e)]
    [else (list '** b e)]))
 
(define (base x)
  (cadr x))
 
(define (exponent x)
  (caddr x))
 
(define (make-subtraction x y)
  (cond
    [(=number? y 0) x]
    [(and (number? x) (number? y)) (- x y)]
    [else (list '- x y)]))
 
(define (deriv exp var)
  (cond [(number? exp) 0]
        [(variable? exp)
         (if (same-variable? exp var) 1 0)]
        [(sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var))]
        [(product? exp)
         (make-sum
          (make-product (multiplier exp)
                        (deriv (multiplicand exp) var))
          (make-product (deriv (multiplier exp) var)
                        (multiplicand exp)))]
        [(exponentiation? exp)
         (make-product
          (make-product
           (exponent exp)
           (make-exponentiation (base exp)
                                (make-subtraction (exponent exp) 1)))
          (deriv (base exp) var))]
        [else
         (error "unknown expression type -- DERIV" exp)]))
"2.56"
(deriv '(** x 6) 'x)

2.57

At this point, the author is trying to show the power of abstraction, by making modification to helper functions, we can keep the core of the program (deriv function) unchanged. This point is driven further in the subsequent exercise.

;; 2.57
(define (augend x)
  (if (null? (cdddr x))
      (caddr x)
      (cons '+ (cddr x))))
 
(define (multiplicand x)
  (if (null? (cdddr x))
      (caddr x)
      (cons '* (cddr x))))
"2.57"
(deriv '(* x y (+ x 3)) 'x)

Exercise 2.58 a

This exercise is quite easy when you think about it. The simplicity arise from the restriction that the input is always fully parenthesized. We pretty much just have to change the first selector as illustrated in the following example: in the prefix syntax, we have (+ x y), to handle infix form, we switch the places of the + and the x, to (x + y), so we just need to switch the corresponding functions which are sum?, product? ….. addend, multiplier…. To be consistent (and making sure that the output from this modification will feed into the input of the same deriv function), we also change all the make-* functions to reflect the infix form.

;; 2.58
(define (addend s) (car s))
 
(define (multiplier p) (car p))
 
(define (sum? x)
  (and (pair? x) (eq? (cadr x) '+)))
 
(define (product? x)
  (and (pair? x) (eq? (cadr x) '*)))
 
(define (exponentiation? x)
  (and (pair? x) (eq? (cadr x) '**)))
 
(define (base x)
  (car x))
 
(define (make-exponentiation b e)
  (cond
    [(=number? e 0) 1]
    [(=number? e 1) b]
    [(and (number? b) (number? e)) (expt b e)]
    [else (list b '** e)]))
 
(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (list a1 '+ a2))))
 
(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (list m1 '* m2))))
 
(define (make-subtraction x y)
  (cond
    [(=number? y 0) x]
    [(and (number? x) (number? y)) (- x y)]
    [else (list x '- y)]))
"2.58 a"
(deriv '(x * (y * (x + 3))) 'x)

Exercise 2.58 b

???

Representing Sets

Exercise 2.59

This exercise is a simple exercise making sure you are familiar with the inner workings of the list set representation. Note, I have taken the liberty to change false -> #f and true -> #t, to better suit my scheme environment.

;; 2.59
(define (element-of-set? x set)
  (cond ((null? set) #f)
        ((equal? x (car set)) #t)
        (else (element-of-set? x (cdr set)))))
 
(define (union-set set1 set2)
  (cond
    [(null? set1) set2]
    [(null? set2) set1]
    [(element-of-set? (car set1) set2) (union-set (cdr set1) set2)]
    [else (cons (car set1) (union-set (cdr set1) set2))]))
 
"2.59"
(union-set '(1 2 3 4 5) '(4 5 6 7 8))

Exercise 2.60

The implementation for element-of-set? and intersection-set did not change, they are just there for the purpose of completeness. However, both adjoin-set and union-set have been changed to one line and correspondingly much faster than previous. The down side is that due to duplicates, the worst case performance could be much worse than the non-duplicates version for the functions element-of-set? and intersection-set. Since the required element to find for element-of-set? could be located after a lot of duplicated entries.

;; 2.60
(define (element-of-set? x set)
  (cond ((null? set) #f)
        ((equal? x (car set)) #t)
        (else (element-of-set? x (cdr set)))))
 
(define (adjoin-set x set)
  (cons x set))
 
(define (union-set set1 set2)
  (append set1 set2))
 
(define (intersection-set set1 set2)
  (cond ((or (null? set1) (null? set2)) '())
        ((element-of-set? (car set1) set2)
         (cons (car set1)
               (intersection-set (cdr set1) set2)))
        (else (intersection-set (cdr set1) set2))))
 
"2.60"
(element-of-set? 1 '(2 3 2 1 3 2 2))
(adjoin-set 3 '(2 3 2 1 3 2 2))
(union-set '(2 3 2 1 3 2 2) '(4 3 2 1 3 2 2))
(intersection-set '(2 3 2 1 3 2 2) '(4 3 4 1 3 4 4))

Exercise 2.61

This exercise should be very simple if you understand the implementation for element-of-set?

;; 2.61
(define (adjoin-set x set)
  (cond
    [(null? set) (list x)]
    [(= x (car set)) set]
    [(&lt; x (car set)) (cons x set)]
    [else (cons (car set) (adjoin-set x (cdr set)))]))
"2.61"
(adjoin-set 5 '(1 3 6 7))

Exercise 2.62

This exercise basically implements the merge part of mergesort, with one notable difference that there is no duplicates in this version.

;; 2.62
(define (union-set set1 set2)
  (cond
    [(null? set1) set2]
    [(null? set2) set1]
    [(&lt; (car set1) (car set2)) (cons (car set1) (union-set (cdr set1) set2))]
    [(= (car set1) (car set2)) (cons (car set1) (union-set (cdr set1) (cdr set2)))]
    [else (cons (car set2) (union-set set1 (cdr set2)))]))
"2.62"
(union-set '(1 3 5 7 9) '(2 3 4 5 6 7 8 9 10))

Exercise 2.63

Tracing through a recursive function is a pain to do if you are not used to it. Especially when tracing through a function you have not wrote yourself. Fortunately, there are libraries available hopefully for your scheme implementation to make this task easier. However, for the purpose of this exercise, its best if you can come up with an explanation of how it works just by looking at it. Here is my version for the two functions, I will show the trace for one example after each explanation, and later explain how the trace came about.
tree->list-1: This one is simpler than the version 2 to trace through, simply because this is a straight recursive function, and by now, you should be very comfortable working with this kinds of function. What this function does is it converts the right branch first into a list, cons the current node onto the front and then append (O(n) time) the left branch onto the front. You may think this is just a straight translation of the code into English, but it is, there is no easy way to explain a recursive function by just thinking about it and remembering the recursive case and the base case. I can also mention the order in which it will convert the tree, it will convert from right to left, from bottom to top. So the rightmost and bottommost element will be the last element of the list, then comes the parent node, then the left child of the parent node. So on and so fourth.
Here is a trace for the second tree in Figure 2.16:

|(tree->list-1 (3 (1 () ()) (7 (5 () ()) (9 () (11 () ())))))
| (tree->list-1 (1 () ()))
| |(tree->list-1 ())
| |()
| |(tree->list-1 ())
| |()
| (1)
| (tree->list-1 (7 (5 () ()) (9 () (11 () ()))))
| |(tree->list-1 (5 () ()))
| | (tree->list-1 ())
| | ()
| | (tree->list-1 ())
| | ()
| |(5)
| |(tree->list-1 (9 () (11 () ())))
| | (tree->list-1 ())
| | ()
| | (tree->list-1 (11 () ()))
| | |(tree->list-1 ())
| | |()
| | |(tree->list-1 ())
| | |()
| | (11)
| |(9 11)
| (5 7 9 11)
|(1 3 5 7 9 11)

tree->list-2: This function is (at least for me) much harder to comprehend. It turns out, this function converts the tree in exactly the same order as the first function, but does it much faster. The reason behind most of the difficulties for me is that this function is tail recursive, and I do not have as much experience working with them than purely recursive functions, but in general replacing append with their tail-recursive equivalents will yield better performance. What it does is very similar to the first version, but it does not spawn a separate recursive call to tree->list-2, and append the result. It carries the result of all the computation it did with it as a second argument to copy-to-list. As the function moves through the tree, consing the individual elements it meets into the result and carry that forward. Therefore it will move through the whole tree only once and will not need to repeat calculation as it did for tree-list-1.
Here is a trace for copy-to-list for the same figure as above trace:

|(copy-to-list (3 (1 () ()) (7 (5 () ()) (9 () (11 () ())))) ())
| (copy-to-list (7 (5 () ()) (9 () (11 () ()))) ())
| |(copy-to-list (9 () (11 () ())) ())
| | (copy-to-list (11 () ()) ())
| | |(copy-to-list () ())
| | |()
| | (copy-to-list () (11))
| | (11)
| |(copy-to-list () (9 11))
| |(9 11)
| (copy-to-list (5 () ()) (7 9 11))
| |(copy-to-list () (7 9 11))
| |(7 9 11)
| (copy-to-list () (5 7 9 11))
| (5 7 9 11)
|(copy-to-list (1 () ()) (3 5 7 9 11))
| (copy-to-list () (3 5 7 9 11))
| (3 5 7 9 11)
|(copy-to-list () (1 3 5 7 9 11))
|(1 3 5 7 9 11)

Here is how I did the tracing in Dr Scheme 372:
One thing you need to be careful when doing trace, it appears to not recognize functions defined in another function, so to trace copy-to-list, you need to take it out and make it a separate function.

;; load the trace library
(require (lib "trace.ss"))
;; tag the functions you would like to trace
(trace tree->list-1 copy-to-list)
;; now run the functions
(define tree (make-tree 3
           (make-tree 1 '() '())
           (make-tree 7 (make-tree 5 '() '())
                      (make-tree 9 '() (make-tree 11 '() '())))))
(tree->list-1 tree)
(copy-to-list tree '())

Exercise 2.64

The first thing you should notice about this partial-tree function is that it has a lot of “let”. The reason upon closer inspection and perhaps some experimenting will revel that you cannot use the variable previously defined in the same let. For example, the following code is not allowed:

 (let* ((left-size (quotient (- n 1) 2))
         (left-result (partial-tree elts left-size)))
...)

Since left-size has been defined in the same let, to use left-size, we have to introduce another nested let as shown in the book. By looking in the right place, we can eliminate most of the redundancy, the magical word is let*, an improved let which is defined basically with nested “let”s.
We can therefore simplify the code to as follows:

(define (partial-tree elts n)
  (if (= n 0)
      (cons '() elts)
      (let* ((left-size (quotient (- n 1) 2))
             (left-result (partial-tree elts left-size))
             (left-tree (car left-result))
             (non-left-elts (cdr left-result))
             (right-size (- n (+ left-size 1)))
             (this-entry (car non-left-elts))
             (right-result (partial-tree (cdr non-left-elts) right-size))
             (right-tree (car right-result))
             (remaining-elts (cdr right-result)))
        (cons (make-tree this-entry left-tree right-tree)
              remaining-elts))))

That’s much easier to read
The keyword to remember when reading through this function is the input must be an ordered list. With the benefit of an ordered list, its an easy algorithm to implement. Basically we would just take the middle element (or roughly the middle element when the number of elements in the list is even), and make that the root of the tree. Make all of the element before the root element in the list to be left tree, and all the element after the root element in the list to be right tree, then recurse on these two sublists. Finally combining the left and right subtree into a whole tree with “make-tree”. With some thought, it should become clear that this is in fact what this function does.
The running time should be O(n) due to it running through the list of elements only once.

Exercise 2.65

Exercise 2.66

For 2.66, a slight modification on element-of-set? would suffice, and adding a new structure to hold two element is in order.

;; 2.66
(define (make-record key val)
  (cons key val))
(define (key record)
  (car record))
(define (val record)
  (cdr record))
 
(define (lookup given-key set)
  (cond ((null? set) #f)
        ((= given-key (key (entry set))) (entry set))
        ((< given-key (key (entry set)))
         (lookup given-key (left-branch set)))
        ((> given-key (key (entry set)))
         (lookup given-key (right-branch set)))))

Huffman Encoding Trees

Exercise 2.67

Just follow the algorithm outlined before, we then have: ‘(A D A B B C A)

Exercise 2.68

encode-symbol is quite simple to write, just follow the rough outline at the introduction to Huffman Encoding Trees. The first part of my code is to copy and paste all of the tree manipulation code from the book into the header.

;; 2.68
(define (make-code-tree left right)
  (list left
        right
        (append (symbols left) (symbols right))
        (+ (weight left) (weight right))))
(define (left-branch tree) (car tree))
(define (right-branch tree) (cadr tree))
(define (make-leaf symbol weight)
  (list 'leaf symbol weight))
(define (leaf? object)
  (eq? (car object) 'leaf))
(define (symbol-leaf x) (cadr x))
(define (weight-leaf x) (caddr x))
(define (symbols tree)
  (if (leaf? tree)
      (list (symbol-leaf tree))
      (caddr tree)))
(define (weight tree)
  (if (leaf? tree)
      (weight-leaf tree)
      (cadddr tree)))
 
(define (element-of-set? x set)
  (cond ((null? set) #f)
        ((equal? x (car set)) #t)
        (else (element-of-set? x (cdr set)))))
 
(define (encode message tree)
  (if (null? message)
      '()
      (append (encode-symbol (car message) tree)
              (encode (cdr message) tree))))
 
(define (encode-symbol symbol tree)
  (cond
    [(element-of-set? symbol (symbols tree))
     (cond
       [(leaf? tree) '()]
       [(element-of-set? symbol (symbols (left-branch tree)))
        (cons 0 (encode-symbol symbol (left-branch tree)))]
       [else (cons 1 (encode-symbol symbol (right-branch tree)))])]
    [else (error "Symbol does not exist in tree" symbol)]))
(define sample-tree
  (make-code-tree (make-leaf 'A 4)
                  (make-code-tree
                   (make-leaf 'B 2)
                   (make-code-tree (make-leaf 'D 1)
                                   (make-leaf 'C 1)))))
"2.68"
(encode '(A D A B B C A) sample-tree)

Exercise 2.69

This question is not very hard if you think about it in the right way, and a careful reading of the introduction paragraph about merging. Basically, follow the path that at every node, merge the smallest two trees (a leaf is a tree as well) currently available until one tree is left. If my explanation is not clear, hopefully my code will be clear.

;; 2.69
(define (adjoin-set x set)
  (cond ((null? set) (list x))
        ((< (weight x) (weight (car set))) (cons x set))
        (else (cons (car set)
                    (adjoin-set x (cdr set))))))
(define (make-leaf-set pairs)
  (if (null? pairs)
      '()
      (let ((pair (car pairs)))
        (adjoin-set (make-leaf (car pair)    ; symbol
                               (cadr pair))  ; frequency
                    (make-leaf-set (cdr pairs))))))
 
(define (successive-merge leaves)
  (if
   (null? (cdr leaves))
   (car leaves)
   (successive-merge
    (adjoin-set (make-code-tree (car leaves) (cadr leaves))
                (cddr leaves)))))
 
(define (generate-huffman-tree pairs)
  (successive-merge (make-leaf-set pairs)))
 
"2.69"
(generate-huffman-tree '((A 4) (B 3) (C 2) (D 1)))

Exercise 2.70

Shouldn’t be too hard when you have done the previous questions:

;; 2.70
"2.70"
(define htree (generate-huffman-tree '((a 2) (boom 1) (Get 2) (job 2) (na 16) (Sha 3) (yip 9) (Wah 1))))
(length (encode '(Get a job Sha na na na na na na na na Get a job Sha na na na na na na na na Wah yip yip yip yip yip yip yip yip yip Sha boom) htree))

SICP 2.2

Jason — Sat, 02 Aug 2008 02:00:48 +0000

Due to my need to move on, I will not comment on my solutions for this section either, but if anyone needs further explanation of anything i did, please feel free to ask either in comment or email.

The following exercises from this section are not done yet: 2.29 C), 2.32, 2.38, 2.39. They are not done probably due to the fact i have not came up with a solution to them. If you have a good solution and would like to share, please post it in the comments.

;; 2.17
(define (last-pair lst)
  (if (null? (rest lst))
      lst
      (last-pair (rest lst))))
(last-pair (list 23 72 149 34))
 
;; 2.18
(define (reverse lst)
  (define (iter orig new)
    (if (null? orig)
        new
        (iter (rest orig) (cons (first orig) new))))
  (iter lst empty))
(reverse (list 1 4 9 16 25))
 
;; 2.19
(define us-coins (list 50 25 10 5 1))
(define uk-coins (list 100 50 20 10 5 2 1 0.5))
 
(define (cc amount coin-values)
  (cond [(= amount 0) 1]
        [(or (< amount 0)(no-more? coin-values)) 0]
        [else
         (+ (cc amount
                (except-first-denomination coin-values))
            (cc (- amount
                   (first-denomination coin-values))
                coin-values))]))
 
(define (no-more? lst) (null? lst))
(define (except-first-denomination lst) (cdr lst))
(define (first-denomination lst) (first lst))
(cc 100 us-coins)
 
;; 2.20
(define (same-parity f . r)
  (let ((parity (if (even? f) even? odd?)))
    (define (list-parity lst)
      (cond [(null? lst) empty]
            [(parity (first lst)) (cons (first lst) (list-parity (rest lst)))]
            [else (list-parity (rest lst))]))
    (list-parity (cons f r))))
(same-parity 1 2 3 4 5 6 7)
 
;; 2.21
(define (square-list-rec items)
  (if (null? items)
      empty
      (cons (sqr (first items)) (square-list-rec (rest items)))))
(square-list-rec (list 1 2 3 4))
(define (square-list-map items)
  (map sqr items))
(square-list-map (list 1 2 3 4))
 
;; 2.23
(define (for-each fun items)
  (define (run)
    (fun (car items))
    (for-each fun (cdr items)))
  (if (null? items)
      #t
      (run)))
(for-each (lambda (x) (newline) (display x))
          (list 57 321 88))
 
;; 2.24: (1 (2 (3 4)))
 
;; 2.25
(car (cdr (car (cdr (cdr (list 1 3 (list 5 7) 9))))))
(car (car (list (list 7))))
(define complex (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7)))))))
(car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr complex))))))))))))
 
;; 2.26
(define x (list 1 2 3))
(define y (list 4 5 6))
(append x y) ;-> (1 2 3 4 5 6)
(cons x y) ;-> ((1 2 3) 4 5 6)
(list x y) ;-> ((1 2 3) (4 5 6))
 
;; 2.27
(define (deep-reverse lst)
  (define (iter orig new)
    (cond [(null? orig) new]
          [(pair? (first orig)) (iter (rest orig) (cons (deep-reverse (first orig)) new))]
          [else (iter (rest orig) (cons (first orig) new))]))
  (iter lst empty))
(define x (list (list 1 2) (list 3 4)))
x
(reverse x)
(deep-reverse x)
 
;; 2.28
(define (fringe tree)
  (cond [(null? tree) empty]
        [(not (pair? tree)) (list tree)]
        [else (append (fringe (car tree)) (fringe (cdr tree)))]))
(fringe x)
(fringe (list x x))
 
;; 2.29
(define (make-mobile left right)
  (list left right))
 
(define (make-branch length structure)
  (list length structure))
 
;a)
(define (left-branch mobile)
  (car mobile))
(define (right-branch mobile)
  (car (cdr mobile)))
(define (branch-length branch)
  (car branch))
(define (branch-structure branch)
  (car (cdr branch)))
 
;b)
(define (total-weight mobile)
  (cond [(not (pair? mobile)) mobile]
        [else (+ (total-weight (branch-structure (left-branch mobile)))
                 (total-weight (branch-structure (right-branch mobile))))]))
 
;c)
 
;; 2.30
(define test-tree (list 1
                        (list 2 (list 3 4) 5)
                        (list 6 7)))
(define (square-tree tree)
  (cond [(null? tree) null]
        [(pair? (car tree)) (cons (square-tree (car tree)) (square-tree (cdr tree)))]
        [else (cons (sqr (car tree)) (square-tree (cdr tree)))]))
(square-tree test-tree)
 
(define (square-tree-map tree)
  (map (lambda (x)
         (if (pair? x)
             (square-tree-map x)
             (sqr x))) tree))
(square-tree-map test-tree)
 
;; 2.31
(define (tree-map fun tree)
  (map (lambda (x)
         (if (pair? x)
             (tree-map fun x)
             (fun x))) tree))
(tree-map sqr test-tree)
 
;; 2.33
(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))
 
(define (my-map p sequence)
  (accumulate (lambda (x y) (cons (p x) y)) empty sequence))
 
(define (append seq1 seq2)
  (accumulate cons seq2 seq1))
 
(define (length sequence)
  (accumulate (lambda (x y) (+ 1 y)) 0 sequence))
(length (list 1 2 3 4 5))
 
;; 2.34
(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms) (+ this-coeff (* x higher-terms)))
              0
              coefficient-sequence))
(horner-eval 2 (list 1 3 0 5 0 1))
 
;; 2.35
;; enumerate-tree in book:
(define (enumerate-tree tree)
  (cond [(null? tree) empty]
        [(not (pair? tree)) (list tree)]
        [else (append (enumerate-tree (car tree))
                      (enumerate-tree (cdr tree)))]))
 
(define (count-leaves t)
  (accumulate + 0 (map (lambda (x) 1) (enumerate-tree t))))
(count-leaves (list x x))
 
;; 2.36
(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      empty
      (cons (accumulate op init (map first seqs))
            (accumulate-n op init (map rest seqs)))))
"2.36"
(accumulate-n + 0 '((1 2 3) (4 5 6) (7 8 9) (10 11 12)))
 
;; 2.37
(define (dot-product v w)
  (accumulate + 0 (map * v w)))

SICP 2.1

Jason — Sat, 02 Aug 2008 01:55:39 +0000

Section 2.1, I have kept most of the exercises I did for this section, but for some i got lazy and did not do. If you wish to compare answer for those exercises, please leave a comment and i would be happy to add them in. I will not add any comments since I did them a while ago, but i will just paste the code:

;; 2.1
(define (gcd x y) ;; we've implemented gcd in section 1.2.5.
  (if (= y 0)
      x
      (gcd y (remainder x y))))
 
(define (sign n)
  (if (= n 0)
      0
      (/ n (abs n))))
 
(define (make-rat n d)
  (let ((g (gcd n d))
        (sign (sign n)))
    (cons (/ n (* g sign))
          (/ d (* g sign)))))
 
;; 2.2
(define (make-point x y)
  (cons x y))
 
(define (x-point p)
  (car p))
 
(define (y-point p)
  (cdr p))
 
(define (make-segment p1 p2)
  (cons p1 p2))
 
(define (start-segment s)
  (car s))
 
(define (end-segment s)
  (cdr s))
 
(define (midpoint-segment s)
  (cons (/ (+
 
;; 2.4
(define (cons x y)
  (lambda (m) (m x y)))
 
(define (car z)
  (z (lambda (p q) p)))
 
(car (cons 1 2))
 
(define (cdr z)
  (z (lambda (p q) q)))
 
(cdr (cons 1 2))
 
;; 2.7
(define (make-interval x y)
  (cons a b))
 
(define (upper-bound interval)
  (cdr interval))
 
(define (lower-bound interval)
  (car interval))

Chapter 1

Jason — Sat, 12 Jul 2008 18:25:37 +0000

Stuff in this chapter i haven’t kept on my computer, this is largely a placeholder post until i get some time to come back to this.

Since I have more or less already done this chapter, I am going to lump the whole thing in one post.

Chapter was quite simple for me, since I have already finished HtDP for school. It is mostly a repeat of that book with some new problems, which I am going to present here.

I have skipped the exercises in Section 1.1 to go in to more interesting stuff, if I have time at the end, I will come back and do the exercises, but most people shouldn’t have problems with that section.

Section 1.2

Exercise 1.9:

Well this exercise should not cause too much problem, if you write it out, you will find that the version is recursive, and the second version is iterative.

Exercise 1.10:

This exercise practices the useful skill of tracing through the execution of a procedure more thoroughly, with multiple functions composed together, you can check the answer by running it through a scheme environment such as Dr Scheme.

Exercise 1.11:

Well the recursive process is straightforward, its just a translation of the definition, as follows:

(define (f-rec n)
  (if (< n 3)
      n
      (+ (f-rec (- n 1)) (* 2 (f-rec (- n 2))) (* 3 (f-rec (- n 3))))))

The iterative version is a bit more tricky, but still relatively easy if you study the iterative version for the Fibonacci numbers example. The basic idea behind the whole thing is that you are doing a lot of repeated work by translating straight from definition. For example, to calculate f(n), you will have to calculate f(n-1), f(n-2), f(n-3). Then when you go on to calculate 2f(n-1), without storing the value of f(n-1) somewhere, you will have to recalculate the whole thing again. So we will be creating some more parameters to store enough information to calculate f(n) without doing repeated work. A more general method to resolve this problem is called Dynamic Programming.
Anyways, without further ado, here is the code:

(define (f n)
  (f-iter 2 1 0 n))
 
(define (f-iter a b c count)
  (if (= count 0)
      c
      (f-iter (+ a (* 2 b) (* 3 c)) a b  (- count 1))))

Exercise 1.12

This exercise is to write a procedure to compute binomial coefficients, it is quite easy. We’ll have two parameters, one to denote the number of rows (first being 0), and the other denote the number of columns (first being 0):

(define (pascal-number row col)
  (cond
    [(= col 0) 1]
    [(= row 0) 0]
    [else (+ (pascal-number (- row 1) (- col 1))
             (pascal-number (- row 1) col))]))

Exercise 1.13

Skipped, due to it being a practice in induction proofs, and the actual process involved is quite nasty.

Exercise 1.14

scheme test

Jason — Mon, 07 Jul 2008 20:29:23 +0000

(define (make-queue)
  (let ([front-ptr '()]
        [rear-ptr '()])
    (define (empty-queue?) (empty? front-ptr))
    (define (insert-queue! new)
      (if (empty-queue?)
          (begin
            (set-front-ptr! new)
            (set-rear-ptr! new))
          (begin
            (set-cdr rear-ptr new)
            (set-rear-ptr! new))))
    (define (dispatch m)
      (cond
        [(equal? m 'insert-queue!) insert-queue!]))
    dispatch))

public class Hello {
  public static void main(String[] args) {
    System.out.println("Hello World!");
  }
}

Hello world!

Jason — Mon, 07 Jul 2008 20:17:18 +0000

Hi all, this is my first time blogging, I hope to have something fun/interesting up soon. I hope adding new content to this blog will be something I do regularly, let’s see how that turns out. This blog is going to be about my hobbies and interests, which currently include computer science (seeing that I am a computer science student), and other things which I have not figured out yet. I also hope through writing this blog it will improve/maintain my English skills, since now it is slipping a lot.