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.

Sunday, December 2, 2007

Lisp on the web server (my intro to it)

So three weeks ago I was looking to relax one evening and popped in Final Fantasy X into my PS2... Two weeks later the addiction has worn down enough for me to get back to my other spare time projects. Excellent game. :)

One of the things that I want to do with Lisp is use it for making web applications. Six years ago I picked up a PHP book sitting on a friends desk and sense that have written too much PHP for me to feel comfortable. I knew it was vial and evil*, but it was just too easy to whip something up in five minutes that got the job done and the web wasn't where I spent most of my time. About a year ago I personally decided to attempt to not do any more PHP code on my personal projects if possible. So the past two weeks I have messed around with how to use Lisp to generate web pages. I started by just making a script that is run in cgi-bin and clisp which was pretty cool all by itself I must say. Then I found cl-who which is a very nice package. From that I have learned a little bit about asdf (still need to learn much more). Lastly I discovered kpax. KPax looks like a fantastic package that combines a lot of nice features. The writing Reddit in Lisp Movie really sold me on the ease that kpax lets you create pages and sites. I went through half of it myself, typing it in and messing around with the code. I also figured out how to get environment variable which from what I can tell is different in common lisp and sbcl (a bit of a bummer that it isn't portable).

My currently web provider like most doesn't have any sort of support for Lisp. While learning about the best way to get it all up and working I feel the most confident not running a separate process, but just relaunching clisp for each webpage request (i.e. a executable in the cgi-bin directory). Of course if kpax can't be run in that configuration I might sit down and figure out all the details about mod_lisp and how it works. Finally I was told about through a friend a feature in sbcl where it can save all the current scripts into an executable which makes for deploying sbcl cgi-bin apps nice and easy because the webserver wouldn't have to have anything installed.

Lastly Thursday night I skipped ahead in the web chapter in ANSI Common Lisp (chapter 16). I know that Paul Graham has done a lot of Web work and was expecting a real high quality chapter with all sorts of good hints, tips and tricks for making web pages in Lisp. That was about as far away as I could get from what I found. The chapter starts off explaining what a webpage is and how it contains "tags" and doesn't get much better.

So no exercises for this entry, but by messing around I have written some lisp and read much more, but more importantly begun to learn more in general about the tools and packages that are out there. There looks to be a lot of interesting packages out there and I will mess around with them more.

For the next entry we will be back to our regular scheduled entry of chapter four of ANSI Common Lisp.

* PHP is vial and evil for many reason which I don't need to go into here, I am sure that you can find many comprehensive lists of reasons just by Googling.

Monday, November 12, 2007

Chapter 3 problems revisited

I got some excellent feedback on my answers for the problems in chapter #3.

  • Try to not use length or reverse when possible as they have to traverse the list making it much slower then it could be.

  • Using cond over nested if statements makes for much easier to read code.

  • Rather then using loops, try to use recursion as the code is often smaller and easier to read.

Lastly I was trying to force the solutions into one function which was making it very hard. Splitting some of them into two makes it cleaner.

Some of the problems revisited:

2) Write a version of union that preserves the order of elements in the original lists (where the first list takes precedence over the second):
> (new-union '(a b c ) '(b a d))
(a b c d)

I modified the question to create a problem I could solve.

(defun new-union (lsta lstb)
(cond
((null lstb) lsta)
((not (eql nil (member (car lstb) lsta)))
(new-union lsta (cdr lstb)))
(t (new-union (append lsta (cons (car lstb) ())) (cdr lstb)))))

3) Define a function that take a list an returns a list indicating the number of times each (eql) element appears, sorted from most common element to least common:

Last time I tried to do this problem in just one function, which was turning out to be too hard so I used loops. But by splitting it into two it becomes very easy.

(defun occurrences (lst)
(occ-count (cdr (sort lst 'string<)) 1 (car lst)))

(defun occ-count (lst cnt x)
(cond
((null lst) (list (cons x cnt)))
((eql (car lst) x)
(occ-count (cdr lst) (+ 1 cnt) (car lst)))
(t (cons (cons x cnt) (occ-count (cdr lst) 1 (car lst))))))

5) Suppose the function pos+ takes a list and returns a list of each element plus its position:

> (pos+ '(7 5 1 4))
(7 6 3 7)

Last time I used maplist, but calling reverse and length would make it much slower then need be. Here is an alternative solution:

(defun pos+ (lst)
(bump 0 lst))

(defun bump (cnt lst)
(cond
((null lst) ())
(t (cons (+ cnt (car lst)) (bump (+ 1 cnt) (cdr lst))))))


On this last one I think that maplist might have been the solution the author was looking for (even if it wasn't that efficient) as it was covered in the chapter and it was the only problem where maplist fit.

Thursday, November 8, 2007

ANSI Common Lisp Chapter 3 : Lists

Chapter three starts off by going into more detail about how lists are made up and then dives into built in functions for manipulating lists. I must say that I find the map functions the most interesting as they are not often what you would find in c/c++ code. There is a brief introduction to keywords, but not enough to distract from the current lesson and a annotation with were the topic will be covered in the future.

Three of the introduced functions are union, intersection, and set-difference. This once again proves to me that I going through the books slowly learning what they have to offer will be very beneficial. The past weekend I was playing around and made the below function when I could have just used set-difference (my function assumes a and b are sorted).

(defun diff (a b)
(loop for x across a
for y across b
for i from 0
until (not (eq x y))
finally (return
(sort
(concatenate 'string (subseq a i) (subseq b i))
#'string<))))

We get an intro to functions for sequences, stacks, dotted lists, and accoc-lists. I enjoyed discovering the functions every and some, both functions that can only shine in a functional language. Putting it all together there was an example that found a shortest path with a breath-first algorithm. It took me a minute to follow everything that was going on, but it was a good example of how you could do quite a bit with lists (in very little code too).

Lastly at the end of each chapter in the book there is a "Summary" section. Where when I found myself not already knowing one of the points I went back and read the section. A nice touch to the book I think. Except this one which seems kinda silly as a summary point:

"Run length encoding is a simple compression algorithm for use in resaurants"

ANSI Common Lisp so far has been about how to solve tasks in lisp in comparison to the first few chapters of Practical Common Lisp which concentrated on the actual language features. I am not sure which method I like more. I like Practical Common Lisp's approach because it would introduce neat features and would get me all fired up to want to use them (and tell people about them). But at the same time I see value in ANSI Common Lisps approach of building a base of familiar functions before introducing features found only in Lisp. Reading both books is the best of both worlds :)

Exercises

1) Skipping this one because it wants drawings.

2) Write a version of union that preserves the order of elements in the original lists:
> (new-union '(a b c ) '(b a d))
(a b c d)

Not sure how to solve this sense even in the given example 'b is coming after 'a which does not preserve the order of the elements in the second list. Anyone?

3) Define a function that take a list an returns a list indicating the number of times each (eql) element appears, sorted from most common element to least common:

> (occurrences '(a b a d a c d c a))
((A . 4) (C . 3) (D . 3) (B . 1))

This one took me way to long to figure out. I kept trying to do it recursively, but was unable to because you can't use setf on every function I know like member and assoc. If you can solve this recursively please feel free to submit your solution in the comments.

(defun occurrences (lst)
(do ((i 0 (+ i 1))
(rst ()))
((> (+ 1 i) (length lst))
(reverse (sort rst '< :key #'cdr)))
(let ((cur (nth i lst)))
(if (not (member cur rst :key #'car))
(push (cons cur (count cur lst)) rst)))))

4) Why does (member '(a) '((a) (b)))) return nil

Because eql only returns true if the args are the same object or numbers or charector with the same value. None of which are true.

5) Suppose the function pos+ takes a list and returns a list of each element plus its position:

> (pos+ '(7 5 1 4))
(7 6 3 7)

(defun pos+ (lst)
(let ((rev (reverse lst)))
(reverse (maplist #'(lambda (x) (+ (car x) (length (cdr x)))) rev))))

6) After years of deliberation, a government commission has decided that lists should be represented by using the cdr to point to the first element and the car to point to the rest of the list. Define the government version of the following functions:

(a) cons
(b) list
(c) length(for lists)
(d) member (for lists; no keywords)

a) (defun gov-cons(x y) (cons y x))
b) (defun gov-list (list &rest other)
(if (null list)
()
(gov-cons list (gov-list (car other) (cdr other)))))
Although I had to look up how rest worked in Practical Common Lisp, ANSI Common Lisp hasn't covered it yet.
c) (defun gov-length (lst)
(if (null lst)
0
(+ 1 (gov-length (car lst)))))
d)(defun gov-member (item lst)
(if (null lst)
nil
(if (eql (cdr lst) item)
lst
(gov-member item (car lst)))))

7) Modify the program in FIgure 3.6 to use fewer cons cells. (Hint Use dotted lists)

(defun compress (x)
(if (consp x)
(compr (car x) 1 (cdr x))
x))
(defun compr (elt n lst)
(if (null lst)
(if (> n 1)
(cons n elt)
(cons n ()))
(let ((next (car lst)))
(if (eql next elt)
(compr elt (+ n 1) (cdr lst))
(cons (n-elts elt n)
(compr next 1 (cdr lst)))))))
(defun n-elts (elt n)
(if (> n 1)
(cons n elt)
elt))

8) Define a function that take a list and prints it in dot notation:
> (showdots '(a b c))
(A . (B . (C . NIL)))
NIL

(defun showdots (lst)
(do ((i 0 (+ i 1)))
((> (+ 1 i) (length lst))
(format t " NIL"))
(format t "\(~A ." (nth i lst)))
(do ((i 0 (+ i 1)))
((> (+ 1 i) (length lst)))
(format t "\)")))

9) Write a program to find the longest finite path with no duplicates through a network represented as in Section 3.15. The network may contain cycles.

(setf min '((a b c) (b c) (c d)))

(defun longest-path (start end net)
(bfs end (list (list start)) net ()))

(defun bfs (end queue net best)
(if (null queue)
best
(let ((path (car queue)))
(let ((node (car path)))
(bfs end
(if (eql 1 (count node path))
(append (cdr queue)
(new-paths path node net))
(cdr queue))
net
(if (eql node end)
(if (> (length path) (length best))
(reverse path)
best)))))))

(defun new-paths (path node net)
(mapcar #'(lambda (n)
(cons n path))
(cdr (assoc node net))))

Saturday, November 3, 2007

50 States

Over on reddit I saw the problem "Take the names of two U.S. States, mix them all together, then rearrange the letters to form the names of two other U.S. States. What states are these?"

At first I was going to code the (already presented) solution for the general case "Given a set of strings find two pair whom contain the same letter", but instead played around with the problem to see if I could find a faster solution which ended me with the following solution:

If you first sort each state and then sort the states you will find that four states sit next to one another (the exploitable property of the states set).
...
aachilnnoorrt (northcarolina)
aachilnoorstu (southcarolina)
...
aadhknoortt (northdakota)
aadhkoosttu (southdakota)
...

Then walk the list calculating the difference between the current word and the next word and store it in a list (haven't done hash yet in lisp) until you find a second duplicate difference in this case is "norsu"

This code could be cleaner and I think that I could write clean-states with map, but feel that I have spent a little too much time on this one problem so here is the code. A big problem I had with this was that I have no idea how to actually profile Lisp code. In C++ I would use valgrind. I will have to continue reading Practical Common Lisp to get to the chapter on packages so I can use the profiling packages. It was fun writing a larger problem in Lisp even when the fact that this is my first larger lisp program really shows.

(defun clean-states (lst)
(if (not lst)
nil
(cons (sort (copy-seq (car lst)) #'char<)
(clean-states (cdr lst)))))

(defun simplify (w &optional (s 0))
(if (> (+ 2 s) (length w))
w
(if (char= (char w s) (char w (+ 1 s)))
(simplify (concatenate 'string (subseq w 0 s) (subseq w (+ 2 s))) s)
(simplify w (+ 1 s)))))

(defun diff (a b)
(loop for x across a
for y across b
for i from 0
until (not (eq x y))
finally (return
(sort
(concatenate 'string (subseq a i) (subseq b i))
#'string<))))

(defun check (x lst)
(if (null lst)
nil
(let* ((y (first lst))
(dif (diff x y))
(sub (simplify dif)))
(let ((match (member sub *known* :test #'(lambda (x y) (string= x (car y))))))
(if (not match)
(progn
(push (cons sub (list x (first lst))) *known*)
;; (check x (cdr lst)) ;; enable this for the general solution
nil
)
(cdr (append (car match) (list x (first lst)))))))))

(defun find-match (lst)
(if (null lst)
nil
(let ((answer (check (car lst) (cdr lst))))
(if (not answer)
(find-match (cdr lst))
answer))))

(defun printout (words clean states)
(dolist (word words)
(loop for s in clean
for w in states
until (string= word s)
finally (return
(format t "~A " w)))))


(defvar *known* ())
(defun run ()
(setf *known* ())
(let* ((states '(
"alabama" "alaska" "arizona" "arkansas" "california" "colorado" "connecticut" "delaware" "florida" "georgia" "hawaii" "idaho" "illinois" "indiana" "iowa" "kansas" "kentucky" "louisiana" "maine" "maryland" "massachusetts" "michigan" "minnesota" "mississippi" "missouri" "montana" "nebraska" "nevada" "newhampshire" "newjersey" "newmexico" "newyork" "northcarolina" "northdakota" "ohio" "oklahoma" "oregon" "pennsylvania" "rhodeisland" "southcarolina" "southdakota" "tennessee" "texas" "utah" "vermont" "virginia" "washington" "westvirginia" "wisconsin" "wyoming"
))
(clean (clean-states states))
(results (find-match (sort (copy-list clean) #'string<))))
(printout results clean states)))

(run)

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.

Ninety-Nine_Lisp_Problems


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))
nil
(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))
nil
(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)
nil
(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)
0
(+ 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
evaluated:

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

14

b. (list 1 (+ 2 3))

(1 5)

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

7

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)
a
b))

5. What do these functions do?

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

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

b. (defun mystery (x y)
(if (null y)
nil
(if (eql (car y) x)
0
(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
exchanges?

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

car

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

or (good one!)

c. > (x #'list 1 nil)
(1)

apply

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)
nil
(if (listp (car lst))
t
(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)
0
(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)))
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)
0
(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.