December 11, 2009

The topics of physics and the universe have always intrigued me, but since studying them in general has little relevance to my everyday job, I always had difficulty making time to learn about them. I took my last physics course in my freshman year of college and since the only knowledge I learned about the universe came from Discovery channel shows. I liked this book because I felt more in tune about modern physics and the universe after reading it.

This book explains the history of physics, from the Greeks to Isac Newton to modern topics like relativity to string theory. It explains them all in a general sense, enough to grasp the mechanisms but it does not overwhelm the reader with details, as the author geared the book to the wider audience.

Some parts of the book mentioned the intentions of God when he created the universe, which I disliked. The notion of a higher power creating the universe only means we remain even farther away from knowing the true roots of the universe, for then the next obvious question is how was this higher power created? If the unified theory of physics ends up being associated with a creator's intentions I would be gravely disappointed.

Overall, I got exactly what I wanted from this book: a concise overview of modern physics. I doubt I'll find the time to delve deeper into the topic, but I'll make sure to keep up-to-date with the current progress.

December 1, 2009

Undone is a dark, suspenseful quick-pace novel about a couple's insurance-scamming scheme gone wrong, leading to a world of chaos involving murder, seduction and scandalous blackmail. Set in a small Maine town, the quiet world of the locals becomes disrupted after a suspicious death and a blatant murder. The lives of those involved quickly spiral out of control.

I breezed through this novel as I found myself craving to discover what would happen next. The characters were dark and grim and the entire time I wondered if anyone would find their salvation. If you are looking for a fast and entertaining read, I recommend this book.

November 1, 2009

Set in the near future, THE ROAD is a story about a father and son
traveling through the bleak, post-apocalyptic world. In the ash
covered earth they struggle scavenging for food and avoiding
cannibalistic nomads, all while trying to keep their wits and humanity

Cormac's writing style simultaneously paints a hopeless world and
shows the loving bond between father and son. The ash covered
landscapes, toxic air, endless gray skies, constant threat of being
hunted, and sparse scraps of food tests the pair's will to survive.
While reading the novel, I often questioned whether it would be better
for them to die.

This is indeed a great novel; not one that will cheer you up on a
rainy day but move you with intricate emotions. It is a powerful story
with a deep writing style. I intend to keep this on my bookshelf for the
rest of my life.

October 25, 2009

SICP Exercise 2.17

(defun last-pair (list)
(if (null (cdr list))
(last-pair (cdr list))))

SICP Exercise 2.18

(defun rev (list)
(if (null (cdr list))
(cons (car (last list))
(rev (butlast list)))))

SICP Exercise 2.19

(defparameter *us-coins* (list 50 25 10 5 1))
(defparameter *uk-coins* (list 100 50 20 10 5 1 0.5))

(defun count-change (amount coin-values)
(cc amount coin-values))

(defun cc (amount coin-values)
(cond ((= amount 0) 1)
((or (< amount 0) (no-more-p coin-values)) 0)
(t (+ (cc amount
(except-first-denomination coin-values))
(cc (- amount
(first-denomination coin-values))

(defun no-more-p (coin-values)
(null coin-values))

(defun except-first-denomination (coin-values)
(cdr coin-values))

(defun first-denomination (coin-values)
(car coin-values))

SICP Exercise 2.20

(defun same-parity (integer &rest integers)
(cond ((null integers) integer)
((evenp integer) (append (list integer)
(remove-if-not #'evenp integers)))
(t (append (list integer) (remove-if-not #'oddp integers)))))

SICP Exercise 2.21

defun square-list-1 (items)
(if (null items)
(cons (expt (car items) 2)
(square-list-1 (cdr items)))))

(defun square-list-2 (items)
(mapcar (lambda (x) (* x x))

SICP Exercise 2.23

(defun for-each (proc items)
(when (consp items)
(funcall proc (car items))
(for-each proc (cdr items))))

SICP Exercise 2.27

(defparameter x (list (list 1 2) (list 3 4)))

(defun last-element (list)
"Returns the last element of LIST."
(car (last list)))

(defun deep-rev (list)
(cond ((and (= 1 (length list)) (not (listp (car list)))) list)
((= 1 (length list)) (list (deep-rev (car list))))
((listp (last-element list))
(cons (deep-rev (last-element list))
(deep-rev (butlast list))))
(t (cons (last-element list)
(deep-rev (butlast list))))))

SICP Exercise 2.28

(defun fringe (list)
(when list
(if (atom list)
(list list)
(append (fringe (car list))
(fringe (cdr list))))))

SICP Exercise 2.29

;; a.
(defun make-mobile (left right)
(list left right))

(defun make-branch (length structure)
(list length structure))

(defun left-branch (mobile)
(first mobile))

(defun right-branch (mobile)
(second mobile))

(defun branch-length (branch)
(first branch))

(defun branch-structure (branch)
(second branch))

;; b.
(defun mobilep (structure)
(listp structure))

(defun total-weight (mobile)
(+ (total-branch-weight (left-branch mobile))
(total-branch-weight (right-branch mobile))))

(defun total-branch-weight (branch)
(let ((branch-structure (branch-structure branch)))
(if (mobilep branch-structure)
(total-weight branch-structure)

;;; c.
(defun torque (branch)
(* (branch-length branch)
(total-branch-weight branch)))

(defun balanced-mobile-p (mobile)
(let ((left (left-branch mobile))
(right (right-branch mobile)))
;; Return false if the left and right torques are unequal.
((/= (torque left) (torque right)) nil)
;; The mobile is balanced at this level. Return true if there
;; are no more submobiles.
((and (not (mobilep left))
(not (mobilep right)))
;; Submobiles exist. Check their balance.
(t (and (if (mobilep (branch-structure left))
(balanced-mobile-p (branch-structure left))
(if (mobilep (branch-structure right))
(balanced-mobile-p (branch-structure right))

;;; d. For section a, we need to replace the first and second
;;; functions with car and cdr respectively. The remaining sections
;;; can be left intact.

SICP Exercise 2.30

(defun square-tree-1 (tree)
(cond ((null tree) nil)
((not (listp tree)) (* tree tree))
(t (cons (square-tree-1 (car tree))
(square-tree-1 (cdr tree))))))

(defun square-tree-2 (tree)
(mapcar (lambda (sub-tree)
(if (listp sub-tree)
(square-tree-2 sub-tree)
(* sub-tree sub-tree)))

SICP Exercise 2.31

(defun tree-map (proc tree)
(mapcar (lambda (sub-tree)
(if (listp sub-tree)
(tree-map proc sub-tree)
(funcall proc sub-tree)))

(defun square (x)
(* x x))

(defun square-tree-3 (tree)
(tree-map #'square tree))

SICP Exercise 2.32

(defun subsets (s)
(if (null s)
(list nil)
(let ((rest (subsets (cdr s))))
(append rest (mapcar (lambda (x)
(cons (car s) x))

SICP Exercise 2.33

(defun accumulate (op initial sequence)
(if (null sequence)
(funcall op (car sequence)
(accumulate op initial (cdr sequence)))))

(defun my-map (p sequence)
(accumulate (lambda (x y)
(cons (funcall p x) y))

(defun my-append (seq1 seq2)
(accumulate #'cons seq2 seq1))

(defun my-length (sequence)
(accumulate (lambda (x y)
;; Avoid style warnings by telling the compiler to
;; ignore X.
(declare (ignore x))
(+ 1 y))
0 sequence))

SICP Exercise 2.34

(defun horner-eval (x coefficient-sequence)
(accumulate (lambda (this-coeff higher-terms)
(+ this-coeff
(* x higher-terms)))

SICP Exercise 2.35

(defun count-leaves (tree)
(accumulate #'+
(mapcar (lambda (sub-tree)
(if (listp sub-tree)
(count-leaves sub-tree)

SICP Exercise 2.36

(defun accumulate-n (op init seqs)
(if (null (car seqs))
(cons (accumulate op init (mapcar #'car seqs))
(accumulate-n op init (mapcar #'cdr seqs)))))

SICP Exercise 2.37

(defun dot-product (v w)
(accumulate #'+ 0 (mapcar #'* v w)))

(defun matrix-*-vector (m v)
(mapcar (lambda (row)
(dot-product row v))

(defun transpose (mat)
(accumulate-n #'cons nil mat))

(defun matrix-*-matrix (m n)
(let ((cols (transpose n)))
(mapcar (lambda (row)
(matrix-*-vector cols row))

SICP Exercise 2.39

(defun fold-left (op initial sequence)
(labels ((iter (result rest)
(if (null rest)
(iter (funcall op result (car rest))
(cdr rest)))))
(iter initial sequence)))

(defun fold-right (op initial sequence)
(accumulate op initial sequence))

(defun reverse-1 (sequence)
(fold-right (lambda (x y)
(append y (list x)))

(defun reverse-2 (sequence)
(fold-left (lambda (x y)
(append (list y) x))

SICP Exercise 2.40

(defun flatmap (proc seq)
(accumulate #'append nil (mapcar proc seq)))

(defun enumerate-interval (x y)
"Returns the list from X to Y"
(loop for i from x to y collect i))

(defun unique-pairs (n)
(lambda (i)
(mapcar (lambda (j)
(list i j))
(enumerate-interval 1 (- i 1))))
(enumerate-interval 1 n)))

;;; Definitions for prime?

(defun dividesp (a b) (zerop (mod b a)))

(defun find-divisor (n test-divisor)
(cond ((> (square test-divisor) n) n)
((dividesp test-divisor n) test-divisor)
(t (find-divisor n (+ test-divisor 1)))))

(defun smallest-divisor (n)
(find-divisor n 2))

(defun prime? (n) (= n (smallest-divisor n)))

(defun prime-sum? (pair)
(prime? (+ (car pair) (cadr pair))))

(defun make-pair-sum (pair)
(list (car pair) (cadr pair) (+ (car pair) (cadr pair))))

(defun prime-sum-pairs (n)
(mapcar #'make-pair-sum
(remove-if-not #'prime-sum?
(unique-pairs n))))

SICP Exercise 2.41

(defun triples (n s)
(remove-if-not (lambda (list) (= s (reduce #'+ list)))
(lambda (i)
(lambda (j)
(mapcar (lambda (k) (list i j k))
(enumerate-interval 1 (- j 1))))
(enumerate-interval 1 (- i 1))))
(enumerate-interval 1 n))))

SICP Exercise 2.42

(defparameter empty-board nil)

(defun board-position (row col)
"Represents a chess piece's position on the board."
(list row col))

(defun adjoin-position (row col set-of-positions)
"Adjoins a new row-column position to a set of positions."
(append set-of-positions (list (board-position row col))))

(defun get-column (position)
"Returns the column of the board-position POSITION."
(cadr position))

(defun get-row (position)
"Returns the row of the board position POSITION."
(car position))

(defun get-board-position (col positions)
"Returns the board position in column COL."
(car (remove-if-not (lambda (position)
(= col (get-column position)))

(defun in-same-row? (col positions)
"Returns true if the queen in column COL shares the same row with
another queen in the position set POSITIONS."
(let ((row (get-row (get-board-position col positions))))
(some (lambda (position)
(and (/= col (get-column position))
(= row (get-row position))))

(defun in-diagonal? (col positions)
"Returns true if the queen in column COL resides in the diagonal
of another queen in the position set POSITIONS."
(let ((row (get-row (get-board-position col positions))))
(some (lambda (position)
(when (/= col (get-column position))
(= 1 (abs (/ (- row (get-row position))
(- col (get-column position)))))))

(defun safe? (new-queen old-queens)
"Returns true if the NEW-QUEEN does not reside in the same row
or diagonal of any of the OLD-QUEENS."
;; Return true when no OLD-QUEENS exist.
((null old-queens) t)
;; Test if NEW-QUEEN resides on the same row.
((in-same-row? new-queen old-queens) nil)
;; Test if NEW-QUEEN resides on the same diagonal.
((in-diagonal? new-queen old-queens) nil)
;; Return true if all the tests pass.
(t t)))

(defun queens (board-size)
(labels ((queen-cols (k)
(if (= k 0)
(list empty-board)
(lambda (positions) (safe? k positions))
(lambda (rest-of-queens)
(mapcar (lambda (new-row)
(adjoin-position new-row
(enumerate-interval 1 board-size)))
(queen-cols (- k 1)))))))
(queen-cols board-size)))

SICP Exercise 2.44

(defun up-split (painter n)
(if (= n 0)
(let ((smaller (up-split painter (- n 1))))
(below painter (beside smaller smaller)))))

SICP Exercise 2.45

(defun split (proc1 proc2)
(labels ((do-split (painter n)
(if (= n 0)
(let ((smaller (do-split painter (- n 1))))
(funcall proc1 painter
(funcall proc2 smaller smaller))))))
(lambda (painter n)
(do-split painter n))))

SICP Exercise 2.46

(defun make-vect (x y)
(cons x y))

(defun xcor-vect (v)
(car v))

(defun ycor-vect (v)
(cdr v))

(defun add-vect (v1 v2)
(make-vect (+ (xcor-vect v1) (xcor-vect v2))
(+ (ycor-vect v1) (ycor-vect v2))))

(defun sub-vect (v1 v2)
(make-vect (- (xcor-vect v1) (xcor-vect v2))
(- (ycor-vect v2) (ycor-vect v2))))

(defun scale-vect (s v)
(make-vect (* s (xcor-vect v))
(* s (ycor-vect v))))

October 14, 2009

In his second novel, Khaled Hosseini wrote a more gripping, compelling, page turner than his first, which says a lot considering how much I enjoyed the first novel. This novel follows two women, who grew up in vastly different lifestyles, and shows how the wars in Afghanistan ruined their families and eventually brought them together.

Throughout reading the novel, I got the feeling that these two lives, however dreadful and punished they seemed, are typical in Afghanistan. This made me realize how much I take for granted, the simple freedoms that I practice without the thought that some other force could snatch them from me. In this sense, the book made me more grateful for the country I live in.

Overall, I found the book easy to read and finished it quickly. The tale seemed powerful and held my attention till the end. Though not one of my all time favorites, I would recommend this book to others.

October 8, 2009

I recently finished the critically acclaimed novel “The Kite Runner” by Khaled Hosseini and understand why the book received so much praise. The story contains vibrant characters and a compelling plot, but for me the most interesting and beneficial aspect of the story was the exposure to a different culture, one where all my previous knowledge originated from news reports of war and violence. Reading about this tiny part of Afghan life helped me realize how little I knew about their customs and beliefs.

Although gripping and entertaining, I would not consider this novel my favorite of all time, but definitely liked it enough to read the follow up book, A Thousand Splendid Suns, which I plan to do in the coming months.

September 29, 2009

Sorry for the long hiatus, as I lacked personal internet access for the entire summer while in the midst of job relocation and house hunting. But now since I'm finally back, look for new posts very soon!

April 19, 2009

at Sunday, April 19, 2009 Labels: Posted by Billy 0 comments

Ian McEwan's tale about a guilt stricken woman troubled by an unfortunate lie she orchestrated as a young teenager really displays his proficient, magnificent prose. I thoroughly enjoyed the author's mastery of describing his characters. Most writers are content to describe the physical characteristics and superficial emotions of their characters. Ian McEwan, on the other hand, shows how his characters think, such as the worrisome sentiments of a migraine-sickened mother to the coping fantasies of a child struggling with growing up. Within these life-like descriptions he wrote a compelling story that, while takes a while to set in motion, gripped me until the end.

April 14, 2009

Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714.

What is the total of all the name scores in the file?

This solution's final function follows the problem's definition precisely: sort the file, compute the alphabetical values for each name, then sum the values.

;;; Use the split-sequence library for splitting the names.txt file.
(require 'split-sequence)

(defparameter *ansi-base-code* 64
"Subtract this value from a character's ansi integer value to get
the characters position in the alphabet.")

(defparameter *names-file* "programming/lisp/euler/names.txt"
"The locations of names.txt on my computer.")

(defun char-position (char)
"Returns CHAR's position in the alphabet.
Example: (char #\A) => 1
(char #\C) => 3"
(- (char-int char)

(defun alphabetical-value (string)
"Returns the alphabetical value of STRING. For example, COLIN is worth
3 + 15 + 12 + 9 + 14 = 53"
(reduce #'+ (map 'list (lambda (char)
(char-position char))

(defun name-score (string position)
"Returns the name score of STRING."
(* (alphabetical-value string) position))

(defun name-scores (list)
"Returns a list of the name scores of LIST. Removes any quotes from
the items in LIST before calculating the score."
(let ((alphabetical-position 0))
(mapcar (lambda (name)
(incf alphabetical-position)
(name-score (remove #\" name) alphabetical-position))

(defun parse-file (file delimiter)
"Returns a list of items from FILE parsed by DELIMITER."
(with-open-file (stream file)
(split-sequence:split-sequence delimiter (read-line stream))))

(defun sort-list (list)
"Sorts LIST by alphabetical string value."
(sort list #'string<))

(defun sum-list (list)
"Returns the sum of all the elements in LIST."
(reduce #'+ list))

(defun euler-22 ()
(sum-list (name-scores (sort-list (parse-file *names-file* #\,)))))

March 24, 2009

SICP Exercise 2.2
Consider the problem of representing line segments in a plane. Each segment is represented as a pair of points: a starting point and an ending point. Define a constructor make-segment and selectors start-segment and end-segment that define the representation of segments in terms of points. Furthermore, a point can be represented as a pair of numbers: the x coordinate and the y coordinate. Accordingly, specify a constructor make- point and selectors x-point and y-point that define this representation. Finally, using your selectors and constructors, define a procedure midpoint-segment that takes a line segment as argument and returns its midpoint (the point whose coordinates are the average of the coordinates of the endpoints). To try your procedures, you'll need a way to print points: (define
(print-point p)
(display "(")
(display (x-point p))
(display ",")
(display (y-point p))
(display ")"))

;;; Utility functions
(defun average (x y)
(/ (+ x y)

;;; Point and segment functions
(defun make-point (x y)
(cons x y))

(defun x-point (point)
(car point))

(defun y-point (point)
(cdr point))

(defun make-segment (start end)
(cons start end))

(defun start-segment (segment)
(car segment))

(defun end-segment (segment)
(cdr segment))

(defun midpoint-segment (segment)
(make-point (average (x-point (start-segment segment))
(x-point (end-segment segment)))
(average (y-point (start-segment segment))
(y-point (end-segment segment)))))

(defun print-point (p)
(format t "x=~D y=~D~%"
(x-point p)
(y-point p)))

SICP Exercise 2.3
Implement a representation for rectangles in a plane. (Hint: You may want to make use of exercise 2.2.) In terms of your constructors and selectors, create procedures that compute the perimeter and the area of a given rectangle. Now implement a different representation for rectangles. Can you design your system with suitable abstraction barriers, so that the same perimeter and area procedures will work using either representation?

(defun make-rec (lower-left-pt upper-right-pt)
(cons lower-left-pt upper-right-pt))

(defun rec-upper-right (rec)
(cdr rec))

(defun rec-lower-left (rec)
(car rec))

(defun rec-upper-left (rec)
(make-point (x-point (rec-lower-left rec))
(y-point (rec-upper-right rec))))

(defun rec-lower-right (rec)
(make-point (x-point (rec-upper-right rec))
(y-point (rec-lower-left rec))))

(defun rec-len (rec)
(- (y-point (rec-upper-left rec))
(y-point (rec-lower-left rec))))

(defun rec-width (rec)
(- (x-point (rec-lower-right rec))
(x-point (rec-lower-left rec))))

(defun area-rec (rec)
(* (rec-len rec)
(rec-width rec)))

(defun perimeter-rec (rec)
(* 2
(+ (rec-len rec)
(rec-width rec))))

;;; Alternative representation of rectangles

(defun alt-make-rec (bottom-seg left-seg)
(cons bottom-seg left-seg))

(defun alt-upper-left (rec)
(end-segment (cdr rec)))

(defun alt-lower-left (rec)
(start-segment (car rec)))

(defun alt-lower-right (rec)
(end-segment (cdr rec)))

(defun alt-upper-right (rec)
(make-point (x-point (alt-lower-right rec))
(y-point (alt-upper-left rec))))

SICP Exercise 2.4
Here is an alternative procedural representation of pairs. For this representation, verify that (car (cons x y)) yields x for any objects x and y.

(define (cons x y)
(lambda (m) (m x y)))
(define (car z)
(z (lambda (p q) p)))

What is the corresponding definition of cdr? (Hint: To verify that this works, make use of the substitution model of section 1.1.5.)

;;; Redefine Scheme functions in CL
(defun alt-cons (x y)
(lambda (m) (funcall m x y)))

(defun alt-car (z)
(funcall z (lambda (p q) p)))

(defun alt-cdr (z)
(funcall z (lambda (p q) q)))

SICPSICP Exercise 2.5
Show that we can represent pairs of nonnegative integers using only numbers and arithmetic operations if we represent the pair a and b as the integer that is the product 2^a*3^b. Give the corresponding definitions of the procedures cons, car, and cdr.

(defun alt2-cons (a b)
(* (expt 2 a) (expt 3 b)))

(defun alt2-car (z)
(do ((i 0 (1+ i))
(n z (/ n 2)))
((> (mod n 2) 0) i)))

(defun alt2-cdr (z)
(do ((i 0 (1+ i))
(n z (/ n 3)))
((> (mod n 3) 0) i)))

SICP Exercise 2.6
In case representing pairs as procedures wasn't mind-boggling enough, consider that, in a language that can manipulate procedures, we can get by without numbers (at least insofar as nonnegative integers are concerned) by implementing 0 and the operation of adding 1 as

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
(lambda (f) (lambda (x) (f ((n f) x)))))

This representation is known as Church numerals, after its inventor, Alonzo Church, the logician who invented the calculus. Define one and two directly (not in terms of zero and add-1). (Hint: Use substitution to evaluate (add-1 zero)). Give a direct definition of the addition procedure + (not in terms of repeated application of add-1).

;;; Redefine Scheme functions in CL
(defun zero ()
(lambda (f)
(lambda (x) x)))

(defun add-1 (n)
(lambda (f)
(lambda (x)
(funcall f (funcall (funcall n f) x)))))

;;; Definitions of one and two
(defun one ()
(lambda (f)
(lambda (x)
(funcall f x))))

(defun two ()
(lambda (f)
(lambda (x)
(funcall f (funcall f x)))))

;;; We can test our definitions of one and two with the following code:
;;; (funcall (funcall (one) #'1+) 0) => 1
;;; (funcall (funcall (two) #'1+) 0) => 2

;;; Notice the pattern for the definitions of one and two: the natural
;;; number N converts to its corresponding Church numeral by
;;; compositing the function f N times. We can abstract this by
;;; using a macro to define our Church numerals

(defun compose (times)
(if (= times 1)
'(funcall f x)
`(funcall f ,(compose (1- times)))))

(defmacro def-church-numeral (name N)
`(defun ,name ()
(lambda (f)
(lambda (x)
,(compose N)))))

;;; Now we can define new Church numerals as follows:
;;; (def-church-numeral three 3)
;;; (funcall (funcall (three) #'1+) 0) => 3

;;; To define an add function for Church numerals, implement the
;;; identity f(m + n)(x) = fm(fn(x)). The code can look rather
;;; ugly in Common Lisp because the need for funcall, but to
;;; understand it remember how we call the church numeral
;;; functions, and see that the code calls the first church
;;; numeral and passes it to the second.

(defun add (m n)
(lambda (f)
(lambda (x)
(funcall (funcall (funcall m) f)
(funcall (funcall (funcall n) f) x)))))

;;; We can test the add function as follows:
;;;(funcall (funcall (add #'one #'three) #'1+) 0) => 4

SICP Exercise 2.7
Alyssa's program is incomplete because she has not specified the implementation of the interval abstraction. Here is a definition of the interval constructor:

(define (make-interval a b) (cons a b))

Define selectors upper-bound and lower-bound to complete the implementation.

;;; Redefine the Scheme functions in CL

(defun add-interval (x y)
(make-interval (+ (lower-bound x) (lower-bound y))
(+ (upper-bound x) (upper-bound y))))

(defun mul-interval (x y)
(let ((p1 (* (lower-bound x) (lower-bound y)))
(p2 (* (lower-bound x) (upper-bound y)))
(p3 (* (upper-bound x) (lower-bound y)))
(p4 (* (upper-bound x) (upper-bound y))))
(make-interval (min p1 p2 p3 p4)
(max p1 p2 p3 p4))))

(defun dev-interval (x y)
(mul-interval x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y)))))

(defun make-interval (a b)
(cons a b))

;;; End of Scheme definitions

(defun upper-bound (interval)
(max (car interval) (cdr interval)))

(defun lower-bound (interval)
(min (car interval) (cdr interval)))

SICP Exercise 2.8
Using reasoning analogous to Alyssa's, describe how the difference of two intervals may be computed. Define a corresponding subtraction procedure, called sub-interval.

(defun sub-interval (x y)
(add-interval x
(make-interval (- (upper-bound y))
(- (lower-bound y)))))

SICP Exercise 2.9
The width of an interval is half of the difference between its upper and lower bounds. The width is a measure of the uncertainty of the number specified by the interval. For some arithmetic operations the width of the result of combining two intervals is a function only of the widths of the argument intervals, whereas for others the width of the combination is not a function of the widths of the argument intervals. Show that the width of the sum (or difference) of two intervals is a function only of the widths of the intervals being added (or subtracted). Give examples to show that this is not true for multiplication or division.

(defun interval-width (interval)
(abs (/ (- (upper-bound interval) (lower-bound interval))

SICP Exercise 2.11
In passing, Ben also cryptically comments: ‘‘By testing the signs of the endpoints of the intervals, it is possible to break mul-interval into nine cases, only one of which requires more than two multiplications.’’ Rewrite this procedure using Ben’s suggestion.

(defun sym-signum (n)
"Calls signum and returns + or - instead of 1, -1, 0. 0 is
considered postive for the sake of this exercise"
(let ((sign (signum n)))
(cond ((eq sign 1) '+)
((eq sign -1) '-)
((eq sign 0) '+))))

(defun list-signs (lst)
"Given a list of numbers, returns a list of the number's signs"
(mapcar #'sym-signum lst))

(defmacro make-interval-if (signs &body body)
"Cleans up the definition of new-mul-interval by removing lots
of repeated code"
`(cond ,@(mapcar #'(lambda (statement)
(let ((test-signs (first statement))
(lower-bound (second statement))
(upper-bound (third statement)))
`((equal ,signs ',test-signs)
(make-interval (* ,(first lower-bound)
,(second lower-bound))
(* ,(first upper-bound)
,(second upper-bound))))))

(defun new-mul-interval (x y)
(let* ((ux (upper-bound x))
(lx (lower-bound x))
(uy (upper-bound y))
(ly (lower-bound y))
(signs (list-signs (list lx ux ly uy)))
;; max and min are needed for the special case
(max (max (* lx ly) (* lx uy) (* ux uy) (* ux ly)))
(min (min (* lx ly) (* lx uy) (* ux uy) (* ux ly))))
(make-interval-if signs
((+ + + +) (lx ly) (ux uy))
((+ + - +) (ux ly) (ux uy))
((+ + - -) (ux ly) (lx uy))
((- + + +) (uy lx) (uy ux))
((- + - -) (ux ly) (lx ly))
((- - + +) (lx uy) (ly ux))
((- - - +) (lx uy) (ly lx))
((- - - -) (ux uy) (ly lx))
;; special case:
((- + - +) (min 1) (max 1)))))

SICP Exercise 2.12
Define a constructor make-center-percent that takes a center and a percentage tolerance and produces the desired interval. You must also define a selector percent that produces the percentage tolerance for a given interval. The center selector is the same as the one shown above.

(defun make-center-percent (center percent)
(let ((percent (/ percent 100.0)))
(cons (- center (* center percent))
(+ center (* center percent)))))

(defun center (interval)
(/ (+ (lower-bound interval) (upper-bound interval)) 2))

(defun percent (interval)
(let ((center (center interval))
(lb (lower-bound interval)))
(* (/ (- center lb)

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be
1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.
The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

(defun num-of-divisors (num)
"Returns the number of divisors of num for num > 1"
(let ((square-root (sqrt num))
(result 0))
(do ((x 1 (1+ x)))
((> x square-root) result)
(when (zerop (mod num x))
(setf result (+ 2 result))))))

(defun euler-12 (&optional (tri-num 1) (tri-val 1))
(if (> (num-of-divisors tri-val) 500)
(euler-12 (1+ tri-num) (+ 1 tri-num tri-val))))

February 19, 2009

If you have a pre 1.0.0 version of Hunchentoot installed on your system, you'll be happy to know that upgrading is fairly easy. But be warned! Hunchentoot 1.0 is incompatible with code written for older versions!

Using asdf-upgrade is the easiest way to upgrade. First launch SBCL with root priveliges:

sudo sbcl

If you do not have asdf-upgrade, you'll need to install it:
(require 'asdf-install)
(asdf-install:install 'asdf-upgrade)

Choose a system wide install. Again, I usally skip gpg checks, but if you're inclined to check them this is a great site:

Now we can use asdf-upgrade.
(require 'asdf-upgrade)

To see a list of out-dated packages run the report function:

To upgrade Hunchentoot, as well as your other packages, run the upgrade command:

Now we can run Hunchentoot 1.0:
(require 'hunchentoot)
(hunchentoot:start (make-instance 'hunchentoot:acceptor :port 4242))

Point your browser to and you should see the Hunchentoot default page.

See my previous post for further configuration details of Hunchentoot. Some major differences between the current version and older versions include discontinued support for mod_lisp and a different api to start and stop the server.

February 12, 2009

Edit: A couple days ago the developers released Hunchentoot 1.0.0 . I have updated this article for the current version. Details for pre 1.0 versions reside at the bottom of this article.

This article explains how to install Hunchentoot 1.0.0 behind Apache on Ubuntu 8.10 Intrepid. It assumes you have Apache installed and you have some basic familiarity of Lisp, Slime, Emacs, Apache and Linux. The article uses SBCL as the Common Lisp implementation.

The steps in this article follow closely to the blog Lost in Technopolis's article "Running Common Lisp behind Apache" but are updated for Ubuntu and Hunchentoot 1.0. I recommend reviewing that article also so you become aware of other options while using Hunchentoot and SBCL.

Configure Apache

Hunchentoot is more than capable of being a stand alone webserver, but if your server uses Apache to serve other sites then we need to create a site configuration file so Apache can let Hunchentoot handle requests. Some people also prefer to let Apache handle static pages and Hunchentoot handle the dynamic pages.

First we will configure a new site for our Hunchentoot server. This site will serve all URLs to Hunchentoot except for the /static directory. It looks for Hunchentoot on port 8000. Create a new file in /etc/apache2/sites-available called "htoot" and enter the text below. Be sure to modify it to suit your needs.

<VirtualHost *:80>
# Admin email, Server Name (domain name) and any aliases
ServerAdmin YOUR-EMAIL

# Index file and Document Root (where the public files are located)
DirectoryIndex index.html
DocumentRoot /home/USERNAME/public_html/

# Custom log file locations
LogLevel warn
ErrorLog /home/USERNAME/public_html/
CustomLog /home/USERNAME/public_html/ combined

ProxyRequests Off
<Proxy *>
allow from all
ProxyPass /static !
ProxyPass /
ProxyPassReverse /


Since we are configuring proxy rules on a site-level basis, comment out everything in the global proxy configuration file /etc/apache2/mods-available/proxy.conf. If you run other sites that use mod_proxy be sure they are secure as well!

Enable the site with this command:
sudo a2ensite test

Enable the proxy modules:
sudo a2enmod proxy
sudo a2enmod proxy_http

Restart Apache:
sudo /etc/init.d/apache2 restart

Now if you point your browser to your site, an Apache error message should display since we haven't install Hunchentoot yet. You can test your configuration by creating a "/static" directory in your DocumentRoot folder and pointing your browser there.

Install SBCL

Next up we need to install a lisp implementation on our machine. I created a ~/apps directory on my server and downloaded SBCL. Be sure to change the download file to the version of SBCL you're using. I usually go to the SBCL website to get the correct link for my system.

Unpack it:
bzip2 -cd sbcl-1.0.23-x86-linux-binary.tar.bz2 | tar xvf -

And run the installation script:
cd sbcl-1.0.23-x86-linux
sudo sh

All done!

Configure Slime

Slime will be used to access the server while it's running. All we have to do is load "swank-loader.lisp" in the lisp image to use it. Download and upack Slime's package:
cd ~/apps
tar xvf slime-current.tgz
mv slime-2009-02-15 slime

Be sure to modify the above commands for your particular version of Slime. You should now have slime installed in your ~/apps/slime directory. Now run swank-loader.lisp in SBCL so Slime creates its necessary folders:
(load "/PATH-TO-YOUR-SLIME-DIR/swank-loader.lisp")

Install Hunchentoot

We will use SBCL's ASDF-INSTALL tool to install Hunchentoot and all of its dependencies. Start SBCL with root privileges:
sudo sbcl

Start the install:
(require 'asdf-install)
(asdf-install:install :hunchentoot)

Choose to do a System-Wide installation. I chose to skip gpg checking because it's a long and tedious process, but if you're inclined to do so this website is a great source:

When complete, install cl-who:
(asdf-install:install :cl-who)

To test the installation, in SBCL execute the following:
(hunchentoot:start (make-instance 'hunchentoot:acceptor :port 4242))

Point your browser to your server's 4242 port, such as, and you should see the Hunchentoot default page. Quit SBCL before continuing.

Create start-up scripts

For security purposes, we will create a new system user to run Hunchentoot called htoot:
sudo adduser --system --group --no-create-home htoot

The Ubuntu way of launching services is to put a control script in the /etc/init.d directory. Luckily, for those of you who are not experienced at writing these scripts, Ubuntu comes with a handy skeleton file that makes a great starting point.

First go to /etc/init.d and create a new file with nano called htoot:
cd /etc/init.d
sudo nano htoot

Copy and paste the following code, being sure to replace the STARTUPSCRIPT file to where you want to put your Hunchentoot start-up lisp script that we will create next:
#! /bin/sh
# Provides: skeleton
# Required-Start: $remote_fs
# Required-Stop: $remote_fs
# Default-Start: 2 3 4 5
# Default-Stop: 0 1 6
# Short-Description: Example initscript
# Description: This file should be used to construct scripts to be
# placed in /etc/init.d.

# Author: William Bruschi (

# Do NOT "set -e"

# PATH should only include /usr/* if it runs after the script

# STARTUPSCRIPT should point to your hunchentoot lisp startup script


# Exit if the package is not installed
[ -x "$DAEMON" ] || exit 0

# Read configuration variable file if it is present
[ -r /etc/default/$NAME ] && . /etc/default/$NAME

# Load the VERBOSE setting and other rcS variables
. /lib/init/

# Define LSB log_* functions.
# Depend on lsb-base (>= 3.0-6) to ensure that this file is present.
. /lib/lsb/init-functions

# Function that starts the daemon/service
# Return
# 0 if daemon has been started
# 1 if daemon was already running
# 2 if daemon could not be started
start-stop-daemon --start --quiet -u htoot --exec $DAEMON --test > /dev/null \
|| return 1

sudo -b -u htoot $DAEMON $DAEMON_ARGS &
# Add code here, if necessary, that waits for the process to be ready
# to handle requests from services started subsequently which depend
# on this one. As a last resort, sleep for some time.

# Function that stops the daemon/service
# Stop the Hunchentoot and Swank servers before killing the daemon
(telnet localhost 6440 &) > /dev/null
# Wait for servers to shutdown
sleep 10

# Return
# 0 if daemon has been stopped
# 1 if daemon was already stopped
# 2 if daemon could not be stopped
# other if a failure occurred
start-stop-daemon --stop --quiet --retry=TERM/30/KILL/5 --name $NAME
[ "$RETVAL" = 2 ] && return 2
# Wait for children to finish too if this is a daemon that forks
# and if the daemon is only ever run from this initscript.
# If the above conditions are not satisfied then add some other code
# that waits for the process to drop all resources that could be
# needed by services started subsequently. A last resort is to
# sleep for some time.
start-stop-daemon --stop --quiet --oknodo --retry=0/30/KILL/5 --exec $DAEMON
[ "$?" = 2 ] && return 2
return "$RETVAL"

# Function that sends a SIGHUP to the daemon/service
do_reload() {
# If the daemon can reload its configuration without
# restarting (for example, when it is sent a SIGHUP),
# then implement that here.
start-stop-daemon --stop --signal 1 --quiet --name $NAME
return 0

case "$1" in
[ "$VERBOSE" != no ] && log_daemon_msg "Starting $DESC" "$NAME"
case "$?" in
0|1) [ "$VERBOSE" != no ] && log_end_msg 0 ;;
2) [ "$VERBOSE" != no ] && log_end_msg 1 ;;
[ "$VERBOSE" != no ] && log_daemon_msg "Stopping $DESC" "$NAME"
case "$?" in
0|1) [ "$VERBOSE" != no ] && log_end_msg 0 ;;
2) [ "$VERBOSE" != no ] && log_end_msg 1 ;;
# If do_reload() is not implemented then leave this commented out
# and leave 'force-reload' as an alias for 'restart'.
#log_daemon_msg "Reloading $DESC" "$NAME"
#log_end_msg $?
# If the "reload" option is implemented then remove the
# 'force-reload' alias
log_daemon_msg "Restarting $DESC" "$NAME"
case "$?" in
case "$?" in
0) log_end_msg 0 ;;
1) log_end_msg 1 ;; # Old process is still running
*) log_end_msg 1 ;; # Failed to start
# Failed to stop
log_end_msg 1
#echo "Usage: $SCRIPTNAME {start|stop|restart|reload|force-reload}" >&2
echo "Usage: $SCRIPTNAME {start|stop|restart|force-reload}" >&2
exit 3


Save the file and exit nano, then make the file executable:
sudo chmod 755 htoot 

The script above starts Hunchentoot by telling SBCL to load the Hunchentoot start-up script, which we will create next. To stop Hunchentoot, we simply telnet to a specific port that the SBCL instance listens to. With this configuration, the Hunchentoot instance runs under the user 'htoot'.

Next change to the directory where you want to place the Hunchentoot start-up lisp script and create a new file called "start-hunchentoot.lisp". Copy and paste the code below. Be sure to read over this code, changing the path to your swank-loader file and any other options as you see fit.
;;;; start-hunchentoot.lisp
;;;; Author: William Bruschi
;;;; Date: 02-14-2009
;;;; Starts Hunchentoot and Swank, then listens for a shutdown
;;;; command on the specified port.

(require 'asdf)
(require 'hunchentoot)
(require 'cl-who)
(require 'sb-bsd-sockets)

(defpackage :webserver
(:use :common-lisp :hunchentoot :cl-who))

(in-package :webserver)

(defparameter *hunchentoot-port* 8000)
(defparameter *shutdown-port* 6440)
(defparameter *swank-loader*
(defparameter *swank-port* 4006)

;;; Start the hunchentoot server
(defparameter *hunchentoot-server*
(start (make-instance 'acceptor :port *hunchentoot-port*)))
(princ "Hunchentoot server started on port ")
(princ *hunchentoot-port*) (terpri)

;;; Load any sites here

(in-package :webserver)

;;; Start swank
(load *swank-loader*)
(swank:create-server :port *swank-port* :dont-close t)
(princ "Loaded Swank on port ")
(princ *swank-port*)(terpri)

;;; Wait and listen for shutdown command
(let ((socket (make-instance 'sb-bsd-sockets:inet-socket
:type :stream :protocol :tcp)))

;; Listen on a local port for a TCP connection
(sb-bsd-sockets:socket-bind socket #(127 0 0 1) *shutdown-port*)
(sb-bsd-sockets:socket-listen socket 1)

;; When it comes, close the sockets and continue
(multiple-value-bind (client-socket addr port)
(sb-bsd-sockets:socket-accept socket)
(sb-bsd-sockets:socket-close client-socket)
(sb-bsd-sockets:socket-close socket)))

;; Shut down Hunchentoot
(princ "Stopping Hunchentoot...")(terpri)
(stop *hunchentoot-server*)

;; Shut down Swank and anyone else by terminating all threads
(dolist (thread (sb-thread:list-all-threads))
(unless (equal sb-thread:*current-thread* thread)
(sb-thread:terminate-thread thread)))
(sleep 1)

When you have lisp sites that you want loaded upon start up, you can place their load commands after the ';;; Load any sites here' comment above.

Now we're ready to launch Hunchentoot:
sudo /etc/init.d/htoot start

Point your browser to your site. Instead of the error seen before, you should see the Hunchentoot default page!

Starting Hunchentoot at bootup

To start Hunchentoot when Ubuntu boots, issue the following commands:
cd /etc/init.d
sudo update-rc.d htoot defaults

Connecting to your server via Slime

Our start-up scripts also starts up the swank server so we can connect to it via Slime and Emacs. View the Slime Manual for the steps on how to do so. Remember that swank is using port 4006, not the default 4005!


1. Sometimes if I use the htoot script to restart Hunchentoot, start-up will fail because port 6440 is in use. Issue the command "netstat -a | grep 6440" and verify it's free before trying to start Hunchentoot. Usually you'll have to wait a few seconds before the previous telnet command to stop Hunchentoot finishes.
2. If you have problems starting Hunchentoot during boot-up, you can modify the htoot script to direct output to a file, such as /var/log/boot to help debug. I once did this and found I had issues starting Slime when Ubuntu booted.


I hope this article will help people get up and running with Hunchentoot on Ubuntu, which in my opinion is web programming paradise. Feel free to leave any tips or suggestions below.

Other links of interest:

  • Weblocks - A continuations based web framework
    - AJAX framework for Hunchentoot
  • LispCast
    - A series of videos about creating a Reddit clone using Hunchentoot

Hunchentoot Pre 1.0

Older versions of Hunchentoot support the Apache module mod_lisp. Instructions for installing mod_lisp and configuring Apache are as follows:

Install Mod_Lisp
First ensure your software repository list contains the proper source.

Open your software repository list
sudo nano /etc/apt/sources.list

If the file lacks the following line, add it to the end.
deb intrepid main universe

Save the changes and exit nano. Next install mod_lisp:
sudo aptitude install libapache2-mod-lisp

The file lisp.load should now reside in /etc/apache2/mods-available/. Next enable it in Apache:
sudo a2enmod lisp

Then restart Apache:
sudo /etc/init.d/apache2 restart

The file lisp.load should now be seen in /etc/apache2/mods-enabled/

In the Apache site configuration file, add something like the following:
   LispServer 8000 "hunchentoot"

<location "/">
SetHandler lisp-handler
<location "/static">
SetHandler None

This lets Hunchentoot handle all of your sites pages except for the /static directory.

Note that if you are using an older version of Hunchentoot, be sure to modify start-hunchentoot.lisp to use the older start-server and stop-server functions instead of start and stop.

January 23, 2009

This article describes how to install Tomcat 6 behind the Apache web server. This allows Apache to serve the static content and Tomcat to handle the dynamic content of your site. It assumes you have already installed Apache and that the operating system is Ubuntu 8.10 Intrepid.

First we need to install Java on our system. We can use aptitude if we set our software sources correctly. To check, open the software sources list:

sudo nano /etc/apt/sources.list

Add the following two lines:
deb intrepid main restricted
deb intrepid multiverse

Update the repository:
sudo aptitude update

Now we can install Java:
sudo aptitude install sun-java6-jre

Confirm the Java installation by entering the following:
java -version

You should see output similar to "java version 1.6.0_10"

Installing Tomcat 6

The following command installs Tomcat 6 with the admin and example applications:
sudo aptitude install tomcat6 tomcat6-admin tomcat6-examples

The admin and example applications are optional. The admin applications provides quick and easy monitoring of the Tomcat server via a browser. The example applications help new users learn Tomcat and Java servlet programming.

To test the installation, point your web browser to http://server-name:8080, replacing server-name with the name or ip-address of your server. Be sure to add port 8080 to the end of the address. If you are installing Tomcat on your local machine, use localhost as the server name. Your browser should display the tomcat welcome page.

Previous versions of Tomcat required extra steps to set the java home variable and to automatically start tomcat when booting, but with Tomcat 6 this should be taken care of for you. You can view the Tomcat startup script in /etc/init.d/tomcat6.

Running Tomcat behind Apache

For this section, I assume you already have Apache installed. To connect Apache and Tomcat we need to install mod_jk:
sudo aptitude install libapache2-mod-jk

Installing mod_jk automatically adds it to Apache's list of enabled modules. If you already have it and need to enable it, issue the command:
sudo a2enmod jk

Next we need to modify Apache's configuration files to point specified paths of your site to Tomcat. First create a workers file that contains connection properties to Tomcat.
sudo nano

Add the following lines to the file:

# This file provides minimal jk configuration properties needed to
# connect to Tomcat.
# We define a worked named 'default'



This creates a worker named "default" which connects to the Tomcat ajp port 8009. Now we make Apache aware of this file and tell it how to log jk information. Open apache2.conf:
sudo nano /etc/apache2/apache2.conf 

Add the following lines to the bottom of the file:

# Where to find
JkWorkersFile /etc/apache2/

# Where to put jk logs
JkLogFile /var/log/apache2/mod_jk.log

# Set the jk log level [debug/error/info]
JkLogLevel info

# Select the log format
JkLogStampFormat "[%a %b %d %H:%M:%S %Y] "

Next we tell Apache which paths of your site to let Tomcat serve. Site configuration files reside in /etc/apache2/sites-available/. If Apache serves one site you can edit the default site. Open the site configuration file and add the following between the VirtualHosts tags:

# JkOptions indicate to send SSL KEY SIZE,
JkOptions +ForwardKeySize +ForwardURICompat -ForwardDirectories

# JkRequestLogFormat set the request format
JkRequestLogFormat "%w %V %T"

# Tomcat serves everything by default
JkMount / default
JkMount /* default

# Apache serves the following URLs
JkUnMount /static default
JkUnMount /static/* default
JkUnMount /photos default
JkUnMount /photos/* default

Notice the JKMount and JKUnMount lines. These settings enable Tomcat to serve all paths by default, and Apache to handle the /static and /photos paths. Adjust accordingly to your site. Next restart Apache so the changes take effect:
sudo /etc/init.d/apache2 restart

Point your web browser to you site, leaving off the trailing port number. You should see the Tomcat welcome page. Congratulations! You now have a Tomcat server running behind Apache!

January 18, 2009

at Sunday, January 18, 2009 Labels: Posted by Billy 0 comments

While setting up my new Ubuntu server, I discovered a great set of articles about server configuration thanks to Slicehost. The articles outline typical installations of apache, php, mysql and more.