August 27, 2010

at Friday, August 27, 2010 Labels: Posted by Billy 0 comments

In the world of software development, managers have deployed many
strategies over the years to guide complex software projects. As the
result of the numerous headaches and failures, different methodologies
have arisen that try to handle the malleable process of developing
software. The so-called waterfall approach, a mirror image of
traditional management of most non-software projects, first
entails producing an unequivocal specification that theoretically
leads to a simple implementation process.

Nevertheless, this waterfall approach failed time and time again for
many software projects. In comes the Agile software development
approach. It encourages rapid and incremental development, continuous
communication with the customers, adaptation and self organizing
teams.

Scrum is a method of agile software development, and Agile Project Management with Scrum by Ken Schwaber gives
real life stories of teams that used scrum successfully and
unsuccessfully. The stories are short and illustrative of common
pitfalls and misunderstandings that teams encounter when first using
Scrum. For example, one such story told of a Scrum Master running the
daily scrum meeting, asking each developer what he/she has
accomplished and assigning them their next task. This is a major
violation of Scrum; Scrum teams are self managed. The Scrum Master
facilitates the use of Scrum for the project, but scrum teams decide
who works on what and the best way to get the job done correctly.

This book was a quick read and great introduction to Scrum. No
software development process is perfect, however, and neither will any
new methodologies that may appear in the future be either. In my ideal
world of software projects, developers should never need to attend
meetings, interruptions will never spring up, and they will work
unbothered in "the flow" all day long. However, people need to
exchange information and software development is a team game. The
Scrum process seems to be a great way to boost productivity, satisfy
managers and stakeholders, and increase workplace moral.

August 15, 2010

at Sunday, August 15, 2010 Posted by Billy 0 comments

Unhappy with the lack of a sophisticated way to auto-generate public properties from private variables in Visual Studio, I turned to EMacs to implement my own version. The code at the end of this post is for VB.NET. It takes a buffer like this:

strLastName
strFirstName
intAmount
dblPrice

and changes it to this:

Private strLastName As String
Private strFirstName As String
Private intAmount As Integer
Private dblPrice As Double

Public Property LastName() As String
  Get
    Return strLastName
  End Get
  Set(ByVal value As String)
    strLastName = value
  End Set
End Property

Public Property FirstName() As String
  Get
    Return strFirstName
  End Get
  Set(ByVal value As String)
    strFirstName = value
  End Set
End Property

Public Property Amount() As Integer
  Get
    Return intAmount
  End Get
  Set(ByVal value As Integer)
    intAmount = value
  End Set
End Property

Public Property Price() As Double
  Get
    Return dblPrice
  End Get
  Set(ByVal value As Double)
    dblPrice = value
  End Set
End Property

You can easily configure the variable types it detects by modifying the alist *vb-types*. At work I have adjusted the template to expand into code complying with my company's coding guidelines. To use, visit a new buffer, type in the names of your private variables prefixed with a type designator, then type M-x props.

(defconst *vb-types*
  '(("str" . "String")
    ("dbl" . "Double")
    ("int" . "Integer")))

(defun var-name (var)
  (unless (< (length var) 4)
    (substring var 3)))

(defun var-type (var)
  (unless (< (length var) 4)
    (let ((type (substring var 0 3)))
      (cdr (assoc type *vb-types*)))))

(defun insert-private-vars (var)
  (let ((type (var-type var)))
    (when type
      (insert "Private " var " As " type)
      (newline))))

(defun insert-properties (var)
  (let ((type (var-type var))
 (name (var-name var)))
    (when (and name type)
      (insert "
Public Property " name "() As " type "
  Get
    Return " var "
  End Get
  Set(ByVal value As " type ")
    " var " = value
  End Set
End Property
"))))

(defun props ()
  (interactive)
  (let ((vars (split-string (buffer-string))))
    (erase-buffer)
    (mapc #'insert-private-vars vars)
    (newline) (newline)
    (mapc #'insert-properties vars)))

July 5, 2010

The Pragmatic Programmer: From Journeyman to Master was a quick and relatively fun read. The book covers many broad topics of everyday programming, such as project management, documentation, testing and automation. While reading I noticed that I already follow many of the principles outlined in the book, but reading it on paper helped encourage me to continue to do so.

Most of material new to me concerned project management and customer relationships. Two such items include having a project glossary and choosing appropriate ways to pleasantly surprise customers.

All programmers should know the book's material and practice it everyday. In my opinion, college's should require more reading of this type to help prepare students for the real world. Overall, it is a great book for professional programmers.

June 4, 2010

at Friday, June 04, 2010 Labels: , Posted by Billy 0 comments

Many people unfamiliar with Common Lisp believe it's a purely
functional language, but this is untrue. While you can shape your
Common Lisp programs in a functional way, Common Lisp also support
Object Oriented Programming via CLOS, the Common Lisp Object
System. It is truly a multi-paradigm language.

This books teaches all the aspects of CLOS, and although written
several years ago, the knowledge still applies today. After learning
about Object Oriented programming using languages like C++ and Java,
learning about CLOS really opened my eyes to what this style of
programming should feel like. All the other languages now seem to
constrained compared to the power and flexibility of CLOS.

In CLOS, classes only have member variables, called slots, and support
multiple inheritance. They do not define methods. Instead, methods are
defined for Generic Functions which specialize on the classes. While
most OO languages use single dispatch, meaning methods specialize on
only one class, CLOS uses multiple dispatch. It also supports
specializing on distinct object instances. In addition to primary
methods, CLOS has before, after and around methods. You can even
dictate the order in which CLOS calls all of the applicable methods.

I truly enjoyed this book as it expanding my understanding of object
oriented techniques. I hope the mainstream language designers can take
the time to read this and incorporate more of CLOS into today's
popular, but limited, object oriented systems.

May 31, 2010

;;; SICP Section 3.1

;;; 3.1
(defun make-accumulator (n)
  (lambda (x)
    (incf n x)))

;;; 3.2
(defun make-monitored (f)
  (let ((count 0))
    (lambda (x)
      (cond ((eq x 'how-many-calls?) count)
     ((eq x 'reset-count) (setf count 0))
     (t (incf count)
        (funcall f x))))))

;;; 3.3 and 3.4 - updated for 3.7
(defun make-account (balance password)
  (let ((consecutive-attempts 0))
    (labels ((withdraw (amount)
        (if (>= balance amount)
     (setf balance (- balance amount))
     "Insufficient funds"))
      (deposit (amount)
        (setf balance (+ balance amount)))
      (dispatch (pass m)
        (cond
   ;; Incorrect password?
   ((not (eq pass password))
    (lambda (x)
      (if (<= 7 (incf consecutive-attempts))
   "Calling cops"
   "Incorrect password")))
   ;; Withdrawing?
   ((eq m 'withdraw)
    (setf consecutive-attempts 0)
    #'withdraw)
   ;; Depositing?
   ((eq m 'deposit)
    (setf consecutive-attempts 0)
    #'deposit)
   ;; Creating joint account?
   ((eq m 'joint)
    (lambda (new-pass)
      (lambda (pass m)
        (if (eq pass new-pass)
     (funcall #'dispatch password m)
     (funcall #'dispatch nil m)))))
   (t (error "Unknown request -- MAKE-ACCOUNT")))))
      #'dispatch)))

(defun withdraw (acc pwd amt)
  (funcall (funcall acc pwd 'withdraw) amt))

(defun deposit (acc pwd amt)
  (funcall (funcall acc pwd 'deposit) amt))

;;; 3.5
(defun random-in-range (low high)
  (let ((range (- high low)))
    (+ low (random range))))

(defun monte-carlo (trials experiment)
  (labels ((iter (trials-remaining trials-passed)
      (cond ((= trials-remaining 0)
      (float (/ trials-passed trials)))
     ((funcall experiment)
      (iter (- trials-remaining 1) (+ trials-passed 1)))
     (t
      (iter (- trials-remaining 1) trials-passed)))))
    (iter trials 0)))

(defun in-circle-p ()
  (let ((x (random-in-range 0 1.0))
 (y (random-in-range 0 1.0)))
    (<= (+ (expt (- x 0.5) 2)
    (expt (- y 0.5) 2))
 (expt 0.5 2))))

(defun estimate-integral (p x1 x2 y1 y2 trials)
  (let ((area-of-rect (* (- x2 x1)
    (- y2 y1)))
 (frac-inside (monte-carlo trials p)))
    (* frac-inside area-of-rect)))

;;; 3.6
(let ((st (make-random-state)))
  (defun rnd (sym)
    (cond ((eq sym 'generate)
    (lambda (x)
      (random x st)))
   ((eq sym 'reset)
    (lambda (x)
      (setf st x)))
   (t "Unknown symbol"))))

;;; 3.7
(defun make-joint (acc pass new-pass)
  (funcall (funcall acc pass 'joint) new-pass))

;;; 3.8
(let ((num 1))
  (defun f (n)
    (setf num (* num n))))

May 25, 2010

at Tuesday, May 25, 2010 Labels: Posted by Billy 0 comments

I recently updated to Ubuntu Lucid and immediately noticed UI performance degradation after using it for a short while. The sluggish performance affected window switching and scrolling in Firefox/Chrome/Evince etc. Nothing on my system indicated a memory leak or chewed-up processor.

I searched Ubuntu's bug tracking system and came across this post, which indicated the using the latest kernel version fix the problem. After following the steps here to update my kernel, my system runs as fast as ever. Hopefully other users experience my situation will stumble across this post and find it helpful.

May 22, 2010

at Saturday, May 22, 2010 Labels: Posted by Billy 0 comments

The Selfish Gene does a marvelous job explaining the core concepts of
evolution for the lay person. It begins with the predominate theory of
how life began in the primordial soup. It then explains how the first
replicators became the genes that make up our DNA and how the natural
environment shapes evolution by pruning the most adaptive and
advantageous of those genes.

Genes are responsible for manufacturing organisms to help them
replicate. They affect not only its own organism, but the surrounding
environment and other organisms. The book explains how the genes
affect the organisms behavior, and how the behavior of a population of
species follows an Evolutionary Stable Strategy (ESS). The book's
title refers to the concept that genes are really looking after
themselves first, but it also explains how altruistic behavior can
arise from the gene's selfishness. The author adamantly proposes that
we are the first species that can defy our genes and oppose the
ruthless nature of natural selection to make the world a better,
friendlier place.

It worries me that many people are ignorant of evolution. Never once
did my high school offer a class on the topic. In my opinion, everyone
should be familiar with the concepts because I believe it's important
to know how we came to be. I recommend this book to everybody.

May 8, 2010

at Saturday, May 08, 2010 Labels: , Posted by Billy 0 comments

Practical Common Lisp has turned into the de facto standard for beginners who want to learn Common Lisp, and deservingly so. The opening chapters delve right into the development style of Common Lisp and show how it differs from more mainstream languages. It covers all the basics and more, eventually leading into chapters explaining how to parse MP3 files and create and create an MP3 Shoutcast server from scratch.

Common Lisp is my favorite language to develop in, but most people I talk to dismiss it as being too old and irrelevant for today's computer applications. I highly disagree. The fact that the language is old is actually one of it's strengths: every design decision seems so well thought out. I've had numerous moments where I commented to myself "you know, it would be nice if this function could do this," and then discovered that it could after reading the documentation. And the development environment is the best out there. The Slime/Emacs/Lisp combination is way ahead of Visual Studio in terms of interactivity, customization, jumping through source files and debugging.

I recommend this book to all developers out there, as learning Common Lisp helped me in my day job as well. At least read through the chapter on creating a unit test framework to get a feel of what software development should be like.

April 24, 2010

at Saturday, April 24, 2010 Labels: Posted by Billy 0 comments

I never have done much reading about psychology before so I thought this book would be a good change of pace for me. The book was easy to read and covered the general ideas about how evolution cause major deficiencies in our brains. Most people don't realize how imperfect we actually are, but just by learning about it we can avoid certain downfalls that all people are prone too.

It was a quick and enjoyable read, but I didn't learn a whole lot from it, probably because I read much about evolution before. Still, I recommend this book for all non-psychology students so they can better understand who they are.

April 11, 2010

at Sunday, April 11, 2010 Labels: Posted by Billy 0 comments

Set in the 1800s, the Piano Tuner is a well written novel about an ordinary man who journey's to the remote jungles of Burma on an odd mission from the British military. There he experiences sights and sounds that he had never seen before, met many interesting people and discovered a source of excitement that was missing from his bland life.

Without revealing any spoils, I found the ending of this book highly engaging, but it still served as a poor penance for the uneventful, unexciting story leading up to it. I found the main character lacking any charm or personality whatsoever. In a sense, I found him distasteful and selfish for leaving his wife behind while seeking adventure. And all through his journey, he did nothing to change his attitude, nothing to prove his worth as a character who deserved respect and admiration.

Though I dislike giving negative reviews, I cannot recommend this book to anyone, but I'm sure others will have different opinions.

March 21, 2010

at Sunday, March 21, 2010 Labels: Posted by Billy 0 comments

SQL Prompt is a great add-on tool for SQL Server Management Studio that I use at work extensively. One of the features it has is "Snippets", which allow you to type a piece of code that expands into other code. For example, typing "ssf" and hitting Tab expands into "SELECT * FROM".

Users can customize snippets, which are saved in a file and can be shared with others (more info here). The database schema I use at work contains hundreds of tables, each named accoring to their abbreviated primary keys. Since some names are very long and cumbersome to type even with SQL Prompt, I created a Lisp script to auto generate snippets for each of the tables.

For example, lets say our database models baseball statistics. We have tables for players and teams. Since we want to tract statistics for multiple years, we have a year table and tables relating the three. So, our very simple database may look like this:

- Teams
- Players
- Years
- PlayersYears
- TeamsYears
- PlayersTeamsYears

My simple Lisp program created snippets for each of the tables, expanding "pty" to "PlayersTeamsYears" and such for each of the tables.

After saving my new SQL Prompt snippets file and starting Management Studio, SQL Prompt generated a run-time error because I had duplicate shortcut keys. Unfortuately, the error message didn't say which keys were duplicates, so I used the s-xml package and parsed the SQL Prompt file looking for duplicate shortcuts.

s-xml works by parsing the xml file sequentially. For each new element, it calls a new-element hook function, and for each new piece of text it calls a new-text hook. The new-element hook takes as pararmenters the name of the element and the attributes. The new-text hook takes the string of text. Each hook also accepts a seed element, which can be any object and is passed along while parsing the file.

I wanted to find duplicate shortcuts, so I decided to keep a hash-table with shortcuts as the key and the number of occurances as values. The shortcuts live inside of the "Shortcut" element, so my seed also needed to know the name of current element it was working on. I created the following class for my seed:

(defclass dup-shortcut-seed ()
  ((name :accessor name)
   (hash :initform (make-hash-table :test 'equalp) :accessor hash)))

I created a method to easily increment the class's hash table:
(defgeneric inc-hash (dup-shortcut-seed key))

(defmethod inc-hash ((dup-shortcut-seed dup-shortcut-seed) key)
  (incf (gethash key (hash dup-shortcut-seed) 0)))

Now that I have my seed, I created the element and text hooks that use the seed to keep track of duplicate shortcuts:
(defun dup-shortcut-xml-new-element-hook (name attributes seed)
  (declare (ignore attributes))
  (let ((name (print-xml-string name)))
    (setf (name seed) name)
    (format t "New element: ~s~%" name))
  seed)

(defun dup-shortcut-xml-text-hook (string seed)
  (when (equalp (name seed) "Shortcut")
    (format t "Modifying hash~%")
    (inc-hash seed string))
  seed)

Next I created a function to call the parser on a stream:
(defun dup-shortcut-xml (in)
  (start-parse-xml
   in
   (make-instance 'xml-parser-state
    :seed (make-instance 'dup-shortcut-seed) 
    :new-element-hook #'dup-shortcut-xml-new-element-hook
    :text-hook #'dup-shortcut-xml-text-hook)))

Finally, I created the main function, which parses the xml file and diplays any duplicate shortcuts:
(defun find-dup-shortcuts-in-xml (&optional (file *output-file*))
  (with-open-file (in file)
    (let ((hash (hash (dup-shortcut-xml in))))
      (maphash (lambda (key value)
   (when (> value 1)
     (format t "~s:~s" key value)))
        hash))))

After finding the shortcuts, I modified my snippet file and it worked beautifully!

March 14, 2010

at Sunday, March 14, 2010 Labels: Posted by Billy 0 comments

Anybody who loves science and technology will love this book. The book is about how technology will involve during the next one hundred years, not at a constant, linear rate, but as a double exponential rate. Ray provides many data and examples of this theory, and explains how the current research done by todays scientists and engineers will change the world more quickly than most people realize.

The book focuses on three areas of science and technology: genetics, nanotechnology, and artificial intelligence. Advancements in each this century will bring major changes, including augmented our intelligence and replacing all of our organs so we could essentially live forever. Machines will become more intelligent than us, for when we create the first machine that can produce a machine smarter than itself, the cycle will iterate at an astonishing rate and machine intelligence will skyrocket past human intelligence. All of these future technologies he describes may seem bizarre, but keep in mind the progress of each one has already begun today.

This book also contains a wealth of online references which I find very interesting and useful. As with any book, it should be regarded with great skepticism. For one thing, we may discover fundamental limits that stop our progressions in a particular area of research, or Ray Kurzweil may underestimate the complexities and challenges of the technologies he wrote about. This book was entertaining. The advancements mentioned are possible but not definite. I recommend this book for every technology lover and for those who are interested in the current research areas of science and technology companies and universities.

February 6, 2010

;;;; SICP Section 2.3

;;; 2.54
(defun my-equals (list1 list2)
  (cond ((and (null list1) (null list2)) t)
 ((and (consp (car list1)) (consp (car list2)))
  (and (my-equals (car list1) (car list2))
       (my-equals (cdr list1) (cdr list2))))
 (t (and (equalp (car list1) (car list2))
  (my-equals (cdr list1) (cdr list2))))))

;;; 2.55
;; ''abc => (quote (quote abc))
;; (car (quote (quote abc))) = > quote

;;; 2.56
;;; Differentiation definitions
(defun variablep (x)
  (symbolp x))

(defun same-variable-p (v1 v2)
  (and (variablep v1) (variablep v2) (equal v1 v2)))

(defun sump (x)
  (and (consp x) (equal (car x) '+)))

(defun addend (s)
  (cadr s))

(defun augend (s)
  (caddr s))

(defun productp (x)
  (and (consp x) (equal (car x) '*)))

(defun multiplier (p)
  (cadr p))

(defun multiplicand (p)
  (caddr p))

(defun =number (exp num)
  (and (numberp exp) (= exp num)))

(defun make-sum (a1 a2)
  (cond ((=number a1 0) a2)
 ((=number a2 0) a1)
 ((and (numberp a1) (numberp a2)) (+ a1 a2))
 (t (list '+ a1 a2))))

(defun make-product (m1 m2)
  (cond ((or (=number m1 0) (=number m2 0)) 0)
 ((=number m1 1) m2)
 ((=number m2 1) m1)
 ((and (numberp m1) (numberp m2)) (* m1 m2))
 (t (list '* m1 m2))))

;;; Exponent definitions
(defun exponentiationp (x)
  (and (consp x) (equal (car x) '^)))

(defun base (exp)
  (cadr exp))

(defun exponent (exp)
  (caddr exp))

(defun make-exponentiation (base exp)
  (cond ((=number exp 0) 1)
 ((=number exp 1) base)
 ((and (numberp base) (numberp exp)) (expt base exp))
 (t (list '^ base exp))))

(defun deriv (exp var)
  (cond ((numberp exp) 0)
 ((variablep exp)
  (if (same-variable-p exp var) 1 0))
 ((sump exp)
  (make-sum (deriv (addend exp) var)
     (deriv (augend exp) var)))
 ((productp exp)
  (make-sum
   (make-product (multiplier exp)
   (deriv (multiplicand exp) var))
   (make-product (deriv (multiplier exp) var)
   (multiplicand exp))))
 ((exponentiationp exp)
  (make-product
   (exponent exp)
   (make-product
    (make-exponentiation (base exp) (- (exponent exp) 1))
    (deriv (base exp) var))))
 (t "unknown expression type")))

;;; 2.57
(defun addend (s)
  (cadr s))

(defun augend (s)
  (let ((augend (cddr s)))
    (if (= 1 (length augend))
 (car augend)
 (make-sum (car augend) (cdr augend)))))

(defun multiplier (p)
  (cadr p))

(defun multiplicand (p)
  (let ((multiplicand (cddr p)))
    (if (= 1 (length multiplicand))
 (car multiplicand)
 (make-product (car multiplicand)
        (cdr multiplicand)))))

(defun make-sum (a1 a2)
  (cond ((=number a1 0) a2)
 ((=number a2 0) a1)
 ((and (numberp a1) (numberp a2)) (+ a1 a2))
 ((sump a2) (list '+ a1 (addend a2) (augend a2)))
 ((productp a2) (list '+ a1 (make-product
        (multiplier a2)
        (multiplicand a2))))
 ((and (consp a2) (> (length a2) 1))
  (list '+ a1 (make-sum (car a2) (cdr a2))))
 ((consp a2) (list '+ a1 (car a2)))
 (t (list '+ a1 a2))))

(defun make-product (m1 m2)
  (cond ((or (=number m1 0) (=number m2 0)) 0)
 ((=number m1 1) m2)
 ((=number m2 1) m1)
 ((and (numberp m1) (numberp m2)) (* m1 m2))
 ((productp m2) (list '* m1 (multiplier m2) (multiplicand m2)))
 ((sump m2) (list '* m1 (make-sum (addend m2) (augend m2))))
 ((and (consp m2) (> (length m2) 1))
  (list '* m1 (make-product (car m2) (cdr m2))))
 ((consp m2) (list '* m1 (car m2)))
 (t (list '* m1 m2))))

;;; 2.58
(defun sump (x)
  (and (consp x) (equal (cadr x) '+)))

(defun addend (s)
  (car s))

(defun augend (s)
  (caddr s))

(defun productp (x)
  (and (consp x) (equal (cadr x) '*)))

(defun multiplier (p)
  (car p))

(defun multiplicand (p)
  (caddr p))

(defun make-sum (a1 a2)
  (cond ((=number a1 0) a2)
 ((=number a2 0) a1)
 ((and (numberp a1) (numberp a2)) (+ a1 a2))
 (t (list a1 '+  a2))))

(defun make-product (m1 m2)
  (cond ((or (=number m1 0) (=number m2 0)) 0)
 ((=number m1 1) m2)
 ((=number m2 1) m1)
 ((and (numberp m1) (numberp m2)) (* m1 m2))
 (t (list m1 '* m2))))

;;; lookup b

;;; 2.59
(defun element-of-set-p (x set)
  (cond ((null set) nil)
 ((equal x (car set)) t)
 (t (element-of-set-p x (cdr set)))))

(defun adjoin-set (x set)
  (if (element-of-set-p x set)
      set
      (cons x set)))

(defun intersection-set (set1 set2)
  (cond ((or (null set1) (null set2)) nil)
 ((element-of-set-p (car set1) set2)
  (cons (car set1)
        (intersection-set (cdr set1) set2)))
 (t (intersection-set (cdr set1) set2))))

(defun union-set (set1 set2)
  (cond ((null set1) set2)
 ((null set2) set1)
 ((element-of-set-p (car set1) set2)
  (union-set (cdr set1) set2))
 (t (cons (car set1)
   (union-set (cdr set1) set2)))))

;;; 2.60
(defun adjoin-set-2 (x set)
  (cons x set))

(defun union-set-2 (set1 set2)
  (cond ((null set1) set2)
 ((null set2) set1)
 (t (cons (car set1)
   (union-set-2 (cdr set1) set2)))))

;;; 2.61
(defun adjoin-set-2 (x set)
  (let ((first (car set)))
    (cond ((null set) (list x))
   ((= x first) set)
   ((> x first) (cons first (adjoin-set-2 x (cdr set))))
   (t (cons x set)))))

;;; 2.62
(defun union-set-2 (set1 set2)
  (cond ((null set1) set2)
 ((null set2) set1)
 ((= (car set1) (car set2))
  (cons (car set1) (union-set-2 (cdr set1) (cdr set2))))
 ((> (car set1) (car set2))
  (cons (car set2) (union-set-2 set1 (cdr set2))))
 (t (cons (car set1) (union-set-2 (cdr set1) set2)))))

;;; 2.66
(defun lookup (given-key set-of-records)
  (let ((current-record (car set-of-records))
 (key (key current-record)))
    (cond ((null set-of-records) nil)
   ((= given-key key) current-record)
   ((> given-key key)
    (lookup given-key (right-tree set-of-records)))
   (t (lookup given-key (left-tree set-of-records))))))

;;; Huffman tree representation
(defun make-leaf (symbol weight)
  (list 'leaf symbol weight))

(defun leaf? (object)
  (equalp (car object) 'leaf))

(defun symbol-leaf (x) (cadr x))

(defun weight-leaf (x) (caddr x))

(defun make-code-tree (left right)
  (list left
 right
 (append (symbols left) (symbols right))
 (+ (weight left) (weight right))))

(defun left-branch (tree) (car tree))

(defun right-branch (tree) (cadr tree))

(defun symbols (tree)
  (if (leaf? tree)
      (list (symbol-leaf tree))
      (caddr tree)))

(defun weight (tree)
  (if (leaf? tree)
      (weight-leaf tree)
      (cadddr tree)))

(defun decode (bits tree)
  (defun decode-1 (bits current-branch)
    (if (null bits)
 nil
 (let ((next-branch
        (choose-branch (car bits) current-branch)))
   (if (leaf? next-branch)
       (cons (symbol-leaf next-branch)
      (decode-1 (cdr bits) tree))
       (decode-1 (cdr bits) next-branch)))))
  (decode-1 bits tree))

(defun choose-branch (bit branch)
  (cond ((= bit 0) (left-branch branch))
 ((= bit 1) (right-branch branch))
 (t (error "bad bit"))))

(defun adjoin-set (x set)
  (cond ((null set) (list x))
 ((< (weight x) (weight (car set))) (cons x set))
 (t (cons (car set) (adjoin-set x (cdr set))))))

(defun make-leaf-set (pairs)
  (if (null pairs)
      nil
      (let ((pair (car pairs)))
 (adjoin-set (make-leaf (car pair) (cadr pair))
      (make-leaf-set (cdr pairs))))))

;;; 2.67
(defparameter *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)))))

(defparameter *sample-message* '(0 1 1 0 0 1 0 1 0 1 1 1 0))

(decode *sample-message* *sample-tree*) ; => (A D A B B C A)

;;; 2.68
(defun encode (message tree)
  (if (null message)
      nil
      (append (encode-symbol (car message) tree)
       (encode (cdr message) tree))))

(defun encode-symbol (symbol tree)
  (cond ((or (null tree) (leaf? tree)) nil)
 ((member symbol (symbols (left-branch tree)))
  (cons 0 (encode-symbol symbol (left-branch tree))))
 ((member symbol (symbols (right-branch tree)))
  (cons 1 (encode-symbol symbol (right-branch tree))))
 (t (error "Symbol not in tree."))))

;;; 2.69
(defun generate-huffman-tree (pairs)
  (successive-merge (make-leaf-set pairs)))

(defun successive-merge (leaf-set &optional sub-tree)
  (cond ((null (cdr leaf-set))
  (make-code-tree (car leaf-set) sub-tree))
 ((null sub-tree)
  (successive-merge (cdr leaf-set) (car leaf-set)))
 (t (successive-merge (cdr leaf-set)
        (make-code-tree (car leaf-set)
          sub-tree)))))

;;; 2.70
(defparameter *lyric-huff-tree*
  (generate-huffman-tree '((a 2) (boom 1) (get 2) (job 2)
      (na 16) (sha 3) (yip 9) (wah 1))))

(defparameter *song* '(get a job sha na na na na na na na na
         get a job sha na na na na na na na
         wah yip yip yip yip yip yip yip yip
         yip Sha boom))

(length (encode *song* *lyric-huff-tree*)) ; => 86

;; 2.71
;; Most frequent = 1, least = N - 1


The novel 1984 left me feeling dreadful. Not because of the quality of the writing or story, but because of the hopeless world the author created and because, as I read through the book and put myself in Winston's shoes, I could not imagine how to rebel and defeat the party. At times I thought some parts extreme, but then when reflecting about all the slavery and hardships in past society I thought perhaps this novel's world may not be so far fetched after all.

The story started slow for my tastes but the vivid writing and lucid details kept me interested. I felt some parts a bit too drawn out, such as when Winston read a couple chapters of Goldstein's book. But once I hit the book's turning point I found it hard to put down.

Overall, this book was a great change of pace for me. I'm glad I finally took the time to read it, as so many others have before me, and I recommend it to people who love drama, history, politics, or simply great writing.