Lincoln Knows What’s Up

Posted on August 18, 2008
Filed Under Quote | 1 Comment

Give me six hours to chop down a tree and I will spend the first four sharpening the axe.

~ Abraham Lincoln

Coming across this quote forced me to reflect on my software work habits, especially for “throwaway” projects.

Popularity: 10% [?]

Learning Lisp Through Examples: XHTML Generation

Posted on August 11, 2008
Filed Under Programming, Programming Languages, Software Development | 3 Comments

I’ve learned a subset of Common Lisp that is large enough to start writing programs. This uncovered a small problem: how do I know I’m doing it right? Lisp is an old language, and there are ancient conventions and standards written deep in the caverns of MIT.

Fortunately for me, the internet is best used to tell people they are wrong. I’ll show you my code, and you tell me when I’m doing it wrong. Deal?

For the complete source code listing, click here. I don’t have any public version control set up to date, so it’s just a static file.

If you are a Lisp power user, this will be horribly boring. I’m just looking to see where I make mistakes.

Disclosure: I did not write unit tests for this project, and I’m aware that this constitutes “doing it wrong.” I recently discovered “lisp-unit“, and will be rectifying the situation.

I also make no effort to validate or encode user input strings.

XHTML Syntax

The “XHTML” referred to will be considered Transitional XHTML, since tags like <center> are not explicitly disallowed.

Basically, I wanted the program to convert something like this:

'(html
 (head
  (title "Greetings, Terran orb!"))
 (body
  (img "src" "./img/some_image.jp2")
  (p (** "margin" "1em") "Some paragraph")))

into this:

<html>
 <head>
  <title>
   "Greetings, Terran orb!"
  </title>
 </head>
 <body>
  <img src="./img/some_image.jp2"/>
  <p margin="1em">
   Some paragraph
  </p>
 </body>
</html>

There will be a separate function to generate the DOCTYPE declaration.

The biggest eyesore here is the (**) tags used for attributes. However, I don’t use very many attributes in my coding, so it’s easier for me to specify when I have an attribute than to use the following syntax:

(tag attributes inner-stuff)

and have my code scattered with more nil than you can shake a stick at.

A Summary of my Development

Based on memory and SVN commit messages.

1. I’m going to print some tags!

2. OK, I screwed up the first time, but I’m really going to print some tags this time!

3. Attributes are now supported.

4. Singleton elements are now supported.

5. Holy hell, “FORMAT” is complicated! All I want to do is indent! I am also adding code to specify the output stream.

6. I have realized that it is simpler to redirect *standard-output* than it is to specify the stream.

7. DOCTYPEs are supported.

8. It turns out that XHTML tags are mandated to be lowercase. Who knew?!

Walking Through My Code

Package definitions

(defpackage "XHTML"
  (:use "COMMON-LISP")
  (:export "GENERATE")
  (:export "DOCTYPE")
  (:export *singletons*))
 
(in-package XHTML)
 
(defparameter *singletons* '("IMG" "META" "LINK" "HR" "BR" "INPUT"))

The only interesting thing here are the exports. “GENERATE” is the function that will be generating the XHTML. “DOCTYPE” allows you to generate the DOCTYPE with an optional argument to specify the location of the DTD.

*singletons* is a list of singleton elements (Elements like <img /> or <meta />), and is available to the user as a helper. It will be more useful if/when I alter this to be an XML generator.

Function: GENERATE

(defun generate (lst &amp;optional (depth 0))
  "Recursively outputs a list of pseudo-xhtml as real xhtml to *standard-output*. Does not print doctype."
  (cond ((null lst) nil)
        ((stringp lst) (format t "~VT~A" depth lst))
        ((atom lst) (format t "~A " lst))
        ((singleton? lst) (print-singleton lst (+ depth 1)))
        ((listp lst) (print-tag (car lst) (cdr lst) (+ depth 1)))))

Calling (xhtml-generate my-list) will print the desired output to *standard-output*. The program recursively partitions the work, but all tag calls inevitably go through this function. Atoms are included so that the user is not punished if they slip and forget to quote their sentences (unless they consider caps-lock a punishment).

(p This is a paragraph!)

Will be output as

<p>THIS IS A PARAGRAPH!</p>.

They will still get an admonishment (from SBCL, anyways) if there are commas in the text, but this is a happy medium for compromise.

Function: DOCTYPE

(defun doctype (&amp;optional (dtd-loc "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"))
  (format t "" dtd-loc))

This is included separately so the user can use a different DOCTYPE declaration.

Function: PRINT-TAG

(defun print-tag (name lst &amp;optional (depth 0))
  "Prints a normal html tag. Parameters are the name of the element and a list of elements that are children of this tag. If the first element of the parameter `lst` is a list whose first element is the atom **, then this list is treated as an attribute list."
  (format t "~&amp;~VT&lt;~(~A~)" depth name)
  (let ((cur-lst lst)
        (head (car lst)))
    (cond ((null lst) nil)
          ((and (listp head)
                (equal (car head) '**))
           (progn
             (print-atts (cdr head))
             (setf cur-lst (cdr lst)))))
    (format t "&gt;~&amp;")
    (mapcar #'(lambda(x) (generate x (+ depth 1))) cur-lst)
    (format t "~&amp;~VT<!--~(~A~)-->~&amp;" depth name)))

Most of my time writing and rewriting this function was spent in the “FORMAT” docs, as it is far more complicated than ANSI Common Lisp ever suggested. Not only can it do any type of formatting under the sun, but it can also butter your toast and summon dead relatives.

The logic of this function is almost identical to the simpler “PRINT-SINGLETON” below. The added ugly checks to see if we have attributes to print. The first line and the last 3 lines are all that is really important with respect to the logic of the function.

Function: SINGLETON?

(defun singleton? (inpt)
  "Checks to see if 'inpt' is a singleton (e.g. <img alt="" />)"
  (cond ((null inpt) nil)
        ((not (listp inpt)) nil)
        (t (member (symbol-name (car inpt))
                   *singletons*
                   :test #'equal))))

Function: PRINT-SINGLETON

(defun print-singleton (lst &amp;optional (depth 0))
  "Handles singleton (<img alt="" />, etc.) statements. Parameter: A list whose car
is the singleton in question, and any remaining elements are considered
attributes. Optional: The indentation depth."
  (format t "~&amp;~VT&lt;~(~A~)" depth (car lst))
  (print-atts (cdr lst))
  (format t "/&gt;~&amp;"))

This is the simpler version of “PRINT-TAG” written above. This function is a lot simpler because any extra elements in the list are assumed to be attributes. We don’t have the possibility of attributes that are mixed with tags.

Function: PRINT-ATTS

(defun print-atts (lst)
  "Prints attribute lists. There must be an even number of parameters,
the odd parameters being the names and the even parameters being attributes."
  (if (null lst)
      nil
      (progn
        (format t " ~A=\"~A\"" (car lst) (nth 1 lst))
        (print-atts (cdr (cdr lst))))))

Pretty boring, as things go.

Future Directions

Generating Related Pages

I would like to generate pages that are related. They use the same CSS, refer to the same image directories, and perhaps have the same navigation elements.

Database connections

Does anybody have any suggestions for good database interfaces [such as CLSQL]?

Running as CGI under Apache

The last thing that I will need in order to make simple client-server web applications.

Popularity: 15% [?]

Norvig, Atwood, and Comments

Posted on August 4, 2008
Filed Under Politics, Programming | 1 Comment

Steve McConnell on Comments

Jeff Atwood recently wrote an article on comments in source code. He discusses a few different approaches to commenting a Newton’s method square root function, and describes the pros and cons. His reasoning was (unsurprisingly) influenced by Steve McConnell.

Good code is its own best documentation. As you’re about to add a comment, ask yourself, ‘How can I improve the code so that this comment isn’t needed?’ Improve the code and then document it to make it even clearer.

~ Steve McConnell, Code Complete

Atwood goes through a few design iterations of a snippet of code and arrives at the following:

private double SquareRootApproximation(n) {
  r = n / 2;
  while ( abs( r - (n/r) ) &gt; t ) {
    r = 0.5 * ( r + (n/r) );
  }
  return r;
}

This has been written about extensively by various bloggers, but nobody cares about what bloggers think. It logically follows that I don’t care about what I think.

I couldn’t indifferently agree more.

Rather than take a stab at improving the documentation of this particular piece of code myself, I wanted to improve it using someone else’s method. To do this, I engaged in an old hobby of mine: I researched the practices of people who are hell of a lot more successful than I am.

Knuth’s Literate Programming has always fascinated me, and I might someday use it to write a large program. However, it won’t be soon, and I sure won’t be using it when working with others. I also feel that its effect would be lost on an example this small, so I decided to pass on this.

In lieu of this, I found that Peter Norvig has written the best practical advice on comments.

Enter Norvig

Dr. Peter Norvig [bio] wrote a Tutorial on Good Lisp Programming Style [.ps alert]. This particular work is worth the read from beginning to end, but of particular use are his few commenting conventions. Some are Lisp-specific, but there are a few good lessons for the taking.

Be Helpful

“Documentation should be organized around tasks the user needs to do, not around what your program happens to provide. Adding documentation strings to each function doesn’t tell the reader how to use your program, but hints in the right place can be very effective.”

This has been very helpful for me in the week since I first read it. He also cites good examples from the Emacs documentation:

“next-line: Move cursor vertically down ARG lines.

… If you are thinking of using this in a Lisp program, consider using ‘forward-line’ instead. It is usually easier to use and more reliable (no dependence on goal-column, etc.)”

Declare the unobvious

“If you’re thinking of something useful that others might want to know when they read your code and that might not be instantly apparent to them, make it a comment.”

This is related to the above. Anything that a person might need when using your code should be mentioned. If you had to derive your code, the method should be described (even if briefly) so that a maintainer may double-check your work.

Say what you mean

Speak in declarations and assertions. Use appropriate detail. Be explicit. Not much to say here.

Applying it to the Code Sample

There are two different ways that I would comment this code. If the interface and the implementation were separated such as in C++, I would add different comments for the header file and the source file:

Header

/* Approximates sqrt(n) to within the specified error.
 * Convergence is quadratic.*/
private double SquareRootApproximation(double n);

Source

// Approximates sqrt(n) using Newton's method.
private double SomeClass::SquareRootApproximation(double n) {
  r = n / 2;
  while ( abs( r - (n/r) ) &gt; t ) {
    r = 0.5 * ( r + (n/r) );
  }
  return r;
}

We could also be using a language where the interface and the code are the same. I would comment like this:

/* Approximates sqrt(n) using Newton's Method
 *      to within the specified error.
 *
 * Convergence is quadratic.*/
private double SquareRootApproximation(double n) {
  r = n / 2;
  while ( abs( r - (n/r) ) &gt; t ) {
    r = 0.5 * ( r + (n/r) );
  }
  return r;
}

So is this helpful, declarative, and straightforward?

I think so.

Giving the user the convergence is simply being considerate. We just as easily could have developed a linear method using fixed-point methods, or any method for getting super-quadratic convergence.

Without the comment, it would simply be an implicit assumption that this was “fast”, for some value of fast.

We also stated (for the maintainer’s sake) that we are using Newton’s Method. The maintainer could verify that the code does what you claim it does, replace it with his favorite super-quadratic convergence sqrt() function, or ignore it because it’s too mathy.

The example is also concise, in that Mr. Atwood’s rearrangement of the code allowed a few little comments to convey a world of information.

Popularity: 20% [?]

« go back — keep looking »