This is a collection of blog entries written while learning Lisp. It is posted in the order written so you probably want to jump to the first post.

Wednesday, October 31, 2007

99 Lisp Problems

Ran across this website which has 99 Lisp problems, can't do them all, but I can do a few. They even include solutions to the problems so after you do it you can compare yours with theirs.


So here are my solutions to the first six.

1) Find the last box of a list.

(defun my-last (lst)
(if (not (listp lst))
(if (consp (cdr lst))
(my-last (cdr lst))
(car lst))))

2) Find the last but one box of a list.

(defun my-but-last (lst)
(if (not (listp lst))
(if (equal 2 (list-length (cdr lst)))
(cdr lst)
(my-but-last (cdr lst)))))

3) Find the K'th element of a list.

(defun element-at (lst num)
(if (null lst)
(if (eql 1 num)
(car lst)
(element-at (cdr lst) (- num 1)))))

4) Find the number of elements of a list.

(defun my-length (lst)
(if (null lst)
(+ 1 (my-length (cdr lst)))))

5) Reverse a list.

(defun my-reverse (lst)
(if (not (consp (cdr lst)))
(append (cdr lst) (cons (car lst) ()))
(append (my-reverse (cdr lst)) (cons (car lst) ()))))

6) Find out whether a list is a palindrome.

;; At first I had a big complicated way and then I realized...
(defun palindromep (lst)
(equal (reverse lst) lst))

Thursday, October 25, 2007

ANSI Common Lisp Chapter 2 : Welcome to Lisp

A nice good intro to Lisp diving straight into the prompt touching on prefix notation, lists, and expressions. Unlike Practical Common Lisp car cdr are introduced in the first chapter vs using first and rest. The first chapter also introduces a number of simpler built in macros, such as if, not, and listp. Then some functions, a quick recursion lesson, tips on reading and writing lisp code (indenting), basic io, and variables, functional programming, iteration. None of the sections go into any depth and macros are no where to be seen. This has to be one of my favorite technical book techniques in the first chapter to present how to do what people already know in the new language/tool.

And now for the fun part!

1. Describe what happens when the following expressions are

a. (+ (- 5 1) (+ 3 7))


b. (list 1 (+ 2 3))

(1 5)

c. (if (listp 1) (+ 1 2) (+ 3 4))


d. (list (and (listp 3) t) (+ 1 2))

(nil 3)

2. Give three distinct cons expressions that return (a b c).

(cons 'a '(b c))
(cons 'a (cons 'b '(c)))
(cons 'a (cons 'b (cons 'c nil))

3. Using car and cdr, define a function to return the fourth
element of a list.

(defun foo(lst)
(car (cdr (cdr (cdr lst)))))

4. Define a function that takes two arguments and returns the
greater of the two.

(defun foo(a b)
(if (> a b)

5. What do these functions do?

a. (defun enigma (x)
(and (not (null x))
(or (null (car x))
(enigma (cdr x)))))

Returns true if any item in the list is a null list.

b. (defun mystery (x y)
(if (null y)
(if (eql (car y) x)
(let ((z (mystery x (cdr y))))
(and z (+ z 1))))))

Returns the location of x in y or nil if it does not.

6. What could occur in place of the x in each of the following

a. > (car (x (cdr '(a (b c) d))))


b. > (x 13 (/ 1 0))

or (good one!)

c. > (x #'list 1 nil)


7. Using only operators introduced in this chapter, define a
function that takes a list as an argument and returns true if
one of its elements is a list.

(defun foo (lst)
(if (null lst)
(if (listp (car lst))
(foo (cdr lst)))))

8. Give iterative and recursive definitions of a function that

a. takes a positive integer and prints that many dots.

(defun foo(x)
(do ((i x (- i 1)))
((< i 1))
(format t ".")))

(defun foo(x)
(format t ".")
(if (not (> 2 x))
(foo (- x 1))))

b. takes a list and returns the number of times the symbol a
occurs in it.

(defun foo(lst symbol)
(if (null lst)
(if (eql symbol (car lst))
(+ 1 (foo (cdr lst) symbol))
(+ 0 (foo (cdr lst) symbol)))))

(defun foo (lst symbol)
(do ((z 0) (l lst (cdr l)))
((null l) z)
(if (eql symbol (car l))
(setf z (+ 1 z)))

9. A friend is trying to write a function that returns the sum of
all the non-nil elements in a list. He has written two versions
of this function, and neither of them work. Explain what's
wrong with each, and give a correct version:

a. (defun summit (lst)
(remove nil lst)
(apply #'+ lst))

Remove returns the list with nil's, you need to setf it.

(defun summit (lst)
(setf lst (remove nil lst))
(apply #'+ lst))

b. (defun summit (lst)
(let ((x (car lst)))
(if (null x)
(summit (cdr lst))
(+ x (summit (cdr lst))))))

It never ends because it never checks if lst is null.

(defun summit (lst)
(if (null lst)
(let ((x (car lst)))
(if (null x)
(summit (cdr lst))
(+ x (summit (cdr lst)))))))

ANSI Common Lisp

Because Paul Graham's ANSI Common Lisp contains exercises at the end of each chapter I have decided to put reading Practical Common Lisp on hold and start reading through it and doing the problems at the end of each chapter. Worst case scenario it will just be a refresher of what I have just learned. Best case scenario I could pick up some new things that are explained differently and through the problems will have a much firmer grasp on the language and become more confident in my ability to transform ideas into code.

Wednesday, October 24, 2007

Exercise problems

After yesterdays chapter I have gone a number of chapters without really coding anything, let alone trying to code up something from scratch. Looking around for some problems to try I found to my horror that I wasn't sure how to code the first test on Project Euler in Lisp. I kept fumbling with syntax and trying to remember what functions to use or their side effects. In the end I ended up just searching for someone's solution and learning from them. A bit of a wake up call. Even though I am learning concepts by going through and reading the book and typing in the examples and messing with them a little there is nothing to match simple exercises to learn new concepts. I might be able to read a bunch of Lisp code now, but I sure couldn't write it. So tonight I did a quick google to find some sample problems from courses and did the following one. Feel free to present your own better way to solve this problem.

Define (has-number-p s-exp) to return true if the s-expression is or contains a number.

(has-number-p '(a (b (c d) ((3)))))

And my solution:

(defun has-number-p (s-exp)
(if (and
(listp s-exp)
(< 0 (list-length s-exp)))
(has-number-p (first s-exp))
(has-number-p (rest s-exp)))
(numberp s-exp)))

Monday, October 22, 2007

Practical Common Lisp Chapter 12 : List Processing

Twelve chapters in we are finally introduced to car and crd. I didn't realize the first/rest car/crd correlation before today which is of course blindly obvious now. Props to the author for delaying this longer then most authors. There was also a nice little bit of history and explanation. The neat new (to me) stuff in this chapter was the section on "Destructive Operations". From the book:

for-side-effect operations - For example setf will modify a list

recycling operations - For example "nreverse x" is a recycling operation because it will return x after moving around the pointers rather then creating a whole new list like reverse does.

When doing functional programming you don't normally use destructive operations, but recycling operations are useful as an optimizing technique. But you should of course be careful with them.

It took about six reads through the section and a dozen re-writes of this blog entry to figure the above out. Don't worry if you don't get it the first time. It is a very confusing section. I have to say writing this blog has been very helpful just be forcing me to write out what I think I just learned. :)

Sunday, October 21, 2007

Practical Common Lisp Chapter 11 : Collections

Unlike other books which often concentrate on Lists first, Vectors, variations of vectors and hash lists are presented first. I am actually surprised that we haven't yet been taught about car and cdr yet. Perhaps that is good as that might bring up bad memories of that Lisp class they had in school where they were just confused. Unlike javascript you can make resizeable strings and unlike javascript there are support for bit vectors that it looks like it isn't supper slow. This chapter is mostly a list of functions that can be applied to a sequence. Some of the neater ones are map, reduce, merge and notany, but no mention of regular expressions. I really would have liked some problems to solve that take advantage of some of the more neat built in functions. But honestly I felt like there was a properly displayed API table and it was re-written in paragraphs. I would have preferred a list of functions with matching API docs like: Even if I tried out every function in Emacs (I tried some, but not them all) I am bound to need to re-look them up later (or more like sooner) and in the current format that is difficult.

Saturday, October 20, 2007

Practical Common Lisp Chapter 10 : Numbers, Characters, and Strings

Numbers, match, chars, strings. Nothing to exciting here. Just a quick overview for example of how in C you do % and in Lisp you do REM. Nice to know what numbers can be very big. To compare strings you can't use =, but have to use STRING=, I wonder why it can't automatically determine the type. The chapter doesn't cover common string operations such as its length or splitting them as that is covered in the next chapter (on arrays).

Thursday, October 18, 2007

Practical Common Lisp Chapter 9 : Building a Unit Test Framework

Todays lesson is that C-c C-c only evaluates the one function you are on, not the whole file. That was a half hour of frustration. :)

This was similar to chapter 2 in that it took you through an example problem, first creating a simple version and then adding features to it. The most interesting thing I saw was the idea of making a top level macro: deftest. Up until now I hadn't thought about doing that. I would have put the check call inside of deftest so that you wouldn't have to write 'check' over and over. At this point I am pretty sure that there will be no exercises for the lessons.

Practical Common Lisp Chapter 8 : Macros

Say this three times fast:

Common Lisp doesn't support macros so every Lisp programmer can create their own variants of standard control constructs any more than C supports functions so every C programmer can write trivial variants of the functions in the C standard library.

This chapter introduces us again to macros (and from the looks of it there will be more introductions in future chapters). It had a nice story that tried to show how one might want macros and then walked you through making the macro 'do-primes'. The more interesting part of the chapter was the sections on the leaks. It mentions that there are three types of leaks, but never explicitly lists them. Here is what I think they are:
  • multiple-evaluation leak
  • out of order leak
  • not using unique names leak

It was interesting to learn about the solutions presented and I am curious if there is any way to apply that knowledge to my c/c++ programming.

I went back in the book to chapter 2 and looked up how to reindent an entire function (C-c M-q) which came in handy as we kept adding and removing things from the macro.

Practical Common Lisp Chapter 7 : Macros (built in)

I read through the first half of this chapter very confused. I thought it was going to be a lesson on writing macros when it was really about the built-in macros that Lisp comes with. The first few paragraphs gave an introductory explanation and so I kept reading the chapter as though it was trying to teach my how to write macros, not how to use the IF, WHEN, and COND macro. Once I figured that what was really going on I quickly re-skimmed the chapter and it made a lot more sense :)

Not sure where the error is but the symbol "�" showed up a handful of times in the online book.

LOOP looks very interesting. As long as there is a cheat sheet I can get at while learning the different ways it can be used it looks to be a nice tool for making code easier to read.

Wednesday, October 17, 2007

Practical Common Lisp Chapter 6 : Variables

Most of this chapter was on scope with one of the best explanation of closures I have read. Plenty of good examples. It also covered global variables, and constant variables, setting and a handful of useful functions such as ROTATEF and SHIFTF. Not much more to say. Next up is Macros which should be more exciting.

Tuesday, October 16, 2007

Practical Common Lisp Chapter 5 : Functions

When reading the online version of the book it would be really nice to be able to click on a footnote number to read it and then have a link to go back to the place of the footnote. The following example just begs to be clicked:

Any symbol can be used as a function name.2

Coming from C++ and Qt where everythingIsCamelCase I will have to get used to functions-with-dashes, but I will try. The fact that functions can have built in documentation is really very cool. One of those, "why don't more languages have this?" features.

As the title went this chapter was all about functions, the first half was on parameters; optional, rest, and keyword. Lisp has some really nice parameter features that are not present in other languages. A little confusing. Then it talked about passing functions and using FUNCALL, APPLY, and lastly anonymous functions. Snuck in the middle it explained RETURN-FROM and introduced blocks (more to come about that in a future chapter). The chapter was low on stuff I could type and try (and screw up) in emacs and I felt myself forcing myself though it, but I honestly don't know how it could have been shorter. There was a bunch to cover, much of which will never be used (from the sounds of it) like keyboard, but still a very good thing to be aware of when you come across it later when reading code. It might have been cool to first try to do something in c or c++ and then when you can't show how you can do it in Lisp, but that would just make this chapter longer.

Sunday, October 14, 2007

Practical Common Lisp Chapter 4 : Syntax and Semantics

- What's with All the Parentheses?
- S-expressions
- S-expressions As Lisp Forms
- Function Calls
- Special Operators
- Macros
- Truth, Falsehood, and Equality
- Formatting Lisp Code

This chapter was a bit of everything. Explaining the basics of the language, more history, breaking apart S-expressions and explaining the parts. Flashed out the details on topics already touched. Well written. No examples for me to code though.

Saturday, October 13, 2007

Practical Common Lisp Chapter 3 : A Simple Database

Chapter 3 was quite good. It was an actually little program that did something while introducing you to a lot of concepts in Lisp. From io, loops and even a little bit about macros. There was just enough in the text that I could follow along in Emacs. It went at a good pace and I learned a lot of new things. I will probably have to go back and review things, but coding up everything as it went along really helped.

The parameter ability of Lisp is really cool, so many brain cells have been spent making functions with few arguments and pondering their order so that don't end up with functions where you have to put in default values just to change the last one.
Meanwhile in in Lisp you can put in the last one using its keyword. And not to forget the supplied-p parameter! I guess I have been coding in other languages for so long that the ideas of having that feature would have never occurred to me.

(defun foo (&key a (b 20) (c 30 c-p)) (list a b c c-p))

(foo :a 1 :b 2 :c 3) ==> (1 2 3 T)
(foo :c 3 :b 2 :a 1) ==> (1 2 3 T)
(foo :a 1 :c 3) ==> (1 20 3 T)
(foo) ==> (NIL 20 30 NIL)

Below are my notes for this chapter.

When implementing dump-db, it should mention that to run it do: (dump-db).

When I run add-cds there is a newline before Ripped and Another while in the book there was not.

Title: Give Us a break
Artist: Bimpopo
Rating: 10

Ripped [y/n] (y/n) y

Another? [y/n]: (y/n) n

When writing save-db I get the following warning which also prevents it from being run until I remove that line:

keyword :IFEXISTS is not allowed for function OPEN.

It says that I can do the following statement, but when run returns nil:

CL-USER> (select (where :rating 9 :ripped nil))

After a few minutes I figured out that this was correct because every cd was marked as ripped in the database. It would have been better to do:

(select (where :rating 9 :ripped t))

Updating the Dixie Chicks to 11 didn't output nil, but outputed the entire list.

CL-USER> (update (where :artist "Dixie Chicks") :rating 11)
((:TITLE "Give Us a break" :ARTIST "Bimpopo" :RATING 10 :RIPPED T)
(:TITLE "Ben Folds" :ARTIST "Rockin' the suburbs" :RATING 6 :RIPPED T)
(:TITLE "Home" :ARTIST "Dixie Chicks" :RATING 11 :RIPPED T)
(:TITLE "Fly" :ARTIST "Dixie Chicks" :RATING 11 :RIPPED T)
(:TITLE "Roses" :ARTIST "Kathy Mattea" :RATING 7 :RIPPED T))

Friday, October 12, 2007

Practical Common Lisp Chapter 1 & 2

I have begun reading through Practical Common Lisp

The author has put together a package with Emacs and SLIME called LispBox which is pretty cool. Maybe it is out of date (packaged in 2005 I think), but non less where LISP has so many different implementations and IDE's etc having this package pre built is a nice touch.

Back in 1999 during the first few weeks at RIT I attended a spontaneous seminar at CSH all about vim. And for the last eight years I have been using vi. :) Earlier this year I tried switching over to Emacs, but it was slow going and I ended up going back to vim one day when I needed to get stuff done asap. So I am enjoying walking through the Emacs tutorial (some new, some refreshing) while learning the basics of Lisp.

Chapter 2
Saving Your Work. It says "after you type the opening parenthesis and the word DEFUN, at the bottom of the Emacs window, SLIME will tell you the arguments expected" but I didn't see that. It did show up for format, but not defun

The first two chapters were a little bit of history, getting LispBox up and running, writing a hello world and walking around in Emacs.

OS X and clisp

I have a MacBook so I installed clisp via port. Took me ten minutes to figure out how to quit it after I started it. Even thought the FAQ said EXT:EXIT, it didn't work and the man page said quit, bye or exit should exit the application only ctrl-d did (after printing Bye.) How odd.

Practical Common Lisp (the tech talk video)

Sat down last night and watch the Practical Common Lisp Google tech talk video given by Peter Seibel who wrote the book by the same name. Honestly I found the video not worth watching. It took almost five minutes to get to any content, the first example had way to much code, the second example was horrible to the point that all I could think was that it was just the wrong way to do things and the last ten minutes were a rushed overview of macros explained in such as way that made it underwhelming when I already know that it is a very cool feature. I was expecting an intro to Lisp when it was clearly targeted to a different audience, but I am not sure who that is. So if you are going to read the book don't bother watching this video. I think the book will be better.

Taking the red pill

I have known about Lisp for many years and even tried learning it a little bit here and there. I have a basic understanding of its advantages, but never really got into it and created a real project with it. So I decided to finally sit down and make something with it. Go through a book, do the tutorials and see what problems I run across. I will try to write down my journey here. A few days ago I read on reddit about how developers are no longer reading through books, but just reading what they need online when they need it, but not picking up books that give full overviews. It inspired me to sit down and actually go through Practical Common Lisp and do the examples, tutorials and test problems and learn what it has to teach me.