Waylaid by Euler

Sorry, Euler ambushed me and now I've been focusing on solving his mathematical challenges. I will return to ACL soon. Chapter 4 is almost done.

ACL Chapter 3

Chris Riesbeck of Northwestern has some criticisms on Graham's coding style. Some of the examples he cites were unclear to me as well at first read.

On to ACL chapter 3 exercises:

1. Show the following lists in box notation:

I did them, but I just am not good enough with LaTeX to show the box notations.

2. Write a version of union that preserves the order of the elements in the original lists:

> (new-union '(a b c) '(b a d))
(A B C D)

(defun new-union (list1 list2)
  (let ((lst list2))
    (dolist (obj list1)
      (setf lst (remove obj lst)))
    (append list1 lst)))

3. Define a function that takes a list and 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 . 2) (D . 2) (B . 1))

(defun occurrences (lst)
  (let ((freq-list nil)
        (uniq-list (remove-duplicates (copy-list lst) :test #'eql)))
    (dolist (elem uniq-list)
      (push (cons elem (count elem lst)) freq-list))
    (sort (copy-list freq-list) #'> :key #'cdr)))

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

member, by default, compares objects using eql, which returns true only if its arguments are the same object. While there appear to be (a) in both lists, each is a distinct object and eql would return nil (equal, however, would return T).

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)

Define this function using (a) recursion, (b) iteration, (c) mapcar.

(defun pos+ (lst) ;recursion
  (pos+recourse lst 0))

(defun pos+recourse (lst pos)
  (if lst       
      (cons (+ (car lst) pos) (pos+recourse (cdr lst) (+ pos 1)))))

(defun pos+ (lst) ;iteration
  (let ((pos -1)
 (output-lst nil))
    (dolist (elem lst)
      (push (+ elem (incf pos)) output-lst))
    (reverse output-lst)))
    
(defun pos+ (lst) ;mapcar
  (let ((pos -1))
    (mapcar #'(lambda (x) (+ x (incf pos))) lst)))

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 versions of the following functions:
(a) cons
(b) list
(c) length (for lists)
(d) member (for lists; no keywords)

(defun govt-cons (obj1 obj2)
  (let ((lst '(nil . nil)))
    (setf (cdr lst) obj1)
    (setf (car lst) obj2)
    lst))

(defun govt-list (&rest lst)
  lst)

(defun govt-length (lst)
  (if (null lst)
      0
      (+ (govt-length (car lst)) 1)))

(defun govt-member (obj lst)
  (if lst
      (if (eql (cdr lst) obj)
   lst
   (govt-member obj (car lst)))))

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

Only one word needs to be changed in n-elts:

(defun compress (x)
  (if (consp x)
      (compr (car x) 1 (cdr x))
      x))

(defun compr (elt n lst)
  (if (null lst)
      (list (n-elts elt 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) ; this is the only change
      elt))

8. Define a function that takes a list and prints it in dot notation:

> (showdots '(a b c))
(A . (B . (C . NIL)))
NIL

(defun showdots (lst)
  (FORMAT T "~A" (showdots-recourse lst)))

(defun showdots-recourse (lst)
  (if (not (null lst))
      (if (atom lst)
   lst
   (format nil "(~A . ~A)"
    (showdots-recourse (car lst))
    (showdots-recourse (cdr lst))))))

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

Answer9

Chapter 3 is done.

A Cygwin/X Tip

Learned something new about running X:

Any time you enter commands in Unix, you can place an ampersand ( "&" ) at the end of the command to run that command in the background. This "disconnects" the command from your keyboard (in that window). You get a prompt immediately and can enter your next command even if the one you just launched has not yet completed.

Now this capability is not all that useful if you're not running X. After all, if the program you are running needs input from you, it has been disconnected and can't see your subsequent keystrokes. Also, if that program produces output, it will still appear, but will be intermingled with the outputs of any new commands you have entered in the meantime. So, if you're not in X, the & is useful only for commands and programs that need no additional inputs and produce no additional outputs.

Under X, however, many useful programs open their own windows and direct their inputs and outputs through those new windows. For example, you would enter "emacs &" rather than "emacs" , and "netscape &" rather than "netscape" . Without the &, the window where you entered the command to launch a program would be useless to you until that program has finished. With the &, that program runs in its own window and the old window gets a new prompt and can still be used to issue more commands.

A SLIME/Emacs Conversion

Thank you Marco Baringer! You've convinced me to learn Emacs/SLIME. Since I only have a WinXP machine, I am using Cygwin/X and CLISP, which is included. I decided to go with emacs-X11 because Cygwin's Emacs (terminal) has this unfortunate problem.

My fear of Emacs's steep learning curve has not been realized so far. 'C-h t' (the tutorial) is easier for me to follow than vim's modal-editing walk-thru. Dare I say it? Learning Emacs is more fun than I expected, even without keywiz.el!

My current .emacs dotfile:

;; disable loading of default.el at startup
(setq inhibit-default-init t)

;; name of host and current path/file in title bar
(require 'dired)
(setq frame-title-format
      (list (format "%s %%S: %%j " (system-name))
     '(buffer-file-name "%f" ("%b"))))

;; disable the toolbar
(tool-bar-mode -1)

;; replace y-e-s by y
(fset 'yes-or-no-p 'y-or-n-p)

;; colorize all buffers / syntax coloring
(global-font-lock-mode t)

;; put scroll bars on the right
(set-scroll-bar-mode 'right)

;; turn on mouse wheel scrolling--works on many systems
(if (load "mwheel" t)
    (mwheel-install))

;; column-number-mode
(column-number-mode t)

;; SLIME
(add-to-list 'load-path (expand-file-name "~/slime/"))
(require 'slime)

(add-hook 'lisp-mode-hook (lambda () (slime-mode t)))
(add-hook 'inferior-lisp-mode-hook (lambda () (inferior-slime-mode t)))
(setq inferior-lisp-program "/bin/clisp"
      lisp-indent-function 'common-lisp-indent-function
      slime-complete-symbol-function 'slime-fuzzy-complete-symbol
      common-lisp-hyperspec-root (expand-file-name "~/HyperSpec/")
      slime-startup-animation nil)

(setf paren-priority 'close)

(setf slime-save-buffers nil)

(slime-setup :autodoc t)
(global-set-key "\C-cs" 'slime-selector)

;; enable visual feedback on selections
(setq transient-mark-mode t)

;; highlight parens & colorize
(show-paren-mode 1)

;; start directory
(find-file "~/")

A minor annoyance is not being able to figure out why 'M-x slime' results in a path error if I include (setf default-directory "~/") in my .emacs file. Somehow SLIME looks for cygcrypt-0.dll (which is in /cygwin/bin/) in /cygwin/cygdrive/c/Documen~/Peatey/Local~/temp/.

Reconsidering LispWorks

While reading Chapter 3 of ANSI Common Lisp (ACL) I noticed something strange. LispWorks implements union differently than Paul Graham's choice of implementation (most likely CLISP):

ACL> (union '(a b c) '(b a d))
(C B A D)

LISPWORKS> (union '(a b c) '(b a d))
(D A B C)

Common Lisp HyperSpec (CLHS) seems to allow this discrepancy:

The order of elements in the result do not have to reflect the ordering of list-1 or list-2 in any way.
Examples:

 (union '(a b c) '(f a d))
=>  (A B C F D)
OR=>  (B C F A D)
OR=>  (D F A B C)

However, this discrepancy between Lisp implementations is confusing to a Lisp newbie like me. If simple functions (or macros?) like union behave differently, what other more significant differences exist? Graham recommends CLISP and CMUCL for free implementation but what about other implmentations like the non-free Allegro CL? If I go away from LispWorks implementation I might take a look at Jabberwocky, as commenter James McCarthy recommended.

I will attempt to ponder choice of Lisp implementation while sleeping.

[update 20060108]: Okay, I'm a doofus. Paul Graham, in the very next paragraph:

Since there is no notion of ordering in a set, these functions do not necessarily bother to preserve the order of elements found in the original lists.

So LispWorks is not deficient. In fact, Sven Van Caekenberghe's famous movie,Episode 2: (Re)writing Reddit in Lisp is 20 minutes and 100 lines, showed me how a good Lisp programmer could use LispWorks.

But I just saw Marco Baringer's "definitive" SLIME tutorial movie. It sure did inspire me to learn Emacs/SLIME.

The real question to ponder while sleeping: Go through ACL on LispWorks then learn Emacs/SLIME, or try to learn Emacs/SLIME/CommonLisp all-at-once?

ACL Chapter 2

Chapter 2 of ANSI Common Lisp (ACL) is available online. Chapter 1 is free too.

Let's work through the exercises in chapter 2:

1. Describe what happens when the following expressions are evaluated:

a. (+ (- 5 1) (+ 3 7))
b. (list 1 (+ 2 3))
c. (if (listp 1) (+ 1 2) (+ 3 4))
d. (list (and (listp 3) t) (+ 1 2))

a. 14
b. (1 5)
c. 7
d. (NIL 3)

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

1. (cons 'a '(b c))
2. (cons 'a (cons 'b (cons 'c nil)))
3. (car (cons '(a b c) nil)) ; *

* I cheat by using car, but I can't think of a third way using only cons. [update]: A very kind commenter, agillesp, shows the third way:

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

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

(defun my-fourth (x)
  (car (cdr (cdr (cdr x)))))

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

(defun my-greater (x y)
  (if (> x y)
      x
    y))

5. What do these functions do?

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

If x is empty, then enigma returns nil; if first(x) is nil, then it returns T; otherwise it recursively calls itself on the rest(x). Enigma returns T only if the list x contains a nil element.

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

If y is empty, then mystery returns nil; if first(y) equals x, then mystery returns 0; otherwise it recursively calls itself with x and rest(y). If y becomes empty first, then nil propagates back up. If x is found in list y then (+ z 1) adds up how many elements were in the list before it. Thus, mystery returns nil if x is not in y; otherwise it returns the location of the first x in y with the first position being 0.

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

a. > (car (x (cdr '(a (b c) d))))
   B
b. > (x 13 (/ 1 0))
   13
c. > (x #'list 1 nil)
   (1)

a. car
b. or
c. 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 element-listp (x)
  (and (not (null x))
       (or (listp (car x))
           (element-listp (cdr x)))))

8. Give iterative and recursive definitions of a function that
a. takes a positive integer and prints that many dots.

(defun print-dots-iterative (x)
  (do ((i 1 (+ i 1)))
      ((> i x) 'done)
    (format t ".")))

(defun print-dots-recursive (x)
  (if (eql x 0)
      'done
    (progn
      (format t ".")
      (print-dots-recursive (- x 1)))))

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

(defun number-of-a-iterative (lst)
  (let ((n 0))
    (dolist (obj lst)
      (if (eql obj 'a)
          (setf n (+ n 1))))
    n))

(defun number-of-a-recursive (lst)
  (if (null lst)
      0
    (if (eql (car lst) 'a)
        (+ (number-of-a-recursive (cdr lst)) 1)
      (number-of-a-recursive (cdr lst)))))

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 only returns a new list containing everything but nil; it does not remove nil from lst. A solution is to pass the new list into apply:

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

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

This version does not first check to see if lst is empty; (cdr lst) will cause an error. A solution is to check for an empty lst first:

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

Chapter 2 is done.

I'm learning Common Lisp

I will learn Lisp. I will learn Common Lisp:

Which should I learn, Common Lisp or Scheme? What's the difference?
Common Lisp is powerful but ugly. Scheme is small and clean, but the standard only defines the inner core of the language. If I had to deliver an application I'd probably use Common Lisp; if I were teaching a course I might use Scheme (but with Common Lisp macros).

I will use Paul Graham's ANSI Common Lisp, a better resource for a Lisp beginner than either On Lisp or Practical Common Lisp. I will attempt the exercises and post my solutions in an open-source effort at learning because Paul Graham never got around to writing a set of solutions to the problems:

Is there a set of solutions to the problems in ANSI Common Lisp?
Unfortunately not. I was supposed to write one, but we started Viaweb right after the book went to press, and I never got around to it.

After some research, Emacs + SLIME (e.g., Lispbox) seems to be the truth path, but I suck at Emacs. I'm more partial to vim but vim/SLIME has not arrived yet. I will be using LispWorks Personal Edition 4.4.6 for Windows [update 20060109]: SLIME/Emacs-X11 on Cygwin/X.

Mine will be a difficult journey: One has already gone off-line, and another appears abandoned. Will I successfully learn to lisp?