Friday, 30 November 2007

Emacs and indenting styles

Emacs, as we all know, is quite flexible. One of it's most useful features is that it allows you to define indentation styles in a portable, text format. I think it is useful to set up per-project coding styles, if you work on various teams, or even just to document the style. For example, I have the following in my .emacs file:

(defconst project-c-style
'((c-basic-offset . 4)
(c-comment-only-line-offset . 4) ; this is an odd one!
(c-offsets-alist . ((statement-block-intro . +)
(substatement-open . 0)
(substatement-label . 0)
(label . 0)
(statement-cont . +))))
"Project coding style" )

(c-add-style "project" project-c-style)

(defun project-c-mode-common-hook()
(c-set-style "project")
(setq tab-width 4)
(setq indent-tabs-mode nil)
(c-toggle-auto-newline -1))

(add-hook 'c-mode-common-hook 'project-c-mode-common-hook)

This is pretty much the stroustrup coding style, taken from cc-styles.el except for the comment about the "odd one". Here, I am (for some reason), deciding that I want to indent my comments above the line they reference. So for example, instead of:

// Hello, how are you;

I want:

// Hello, how are you;

If Emacs can support that weird style, it can definitely support your style! Do yourself a favour and document it using Emacs so your code looks as consistent as possible.

Wednesday, 28 November 2007

Testing C++ applications

Software testing is one of those things that you can't really nail down. Thanks to a lot of advertising and ease-of-use due to the *Unit libraries, unit testing is quite popular nowadays. But really, unit testing is just the tip of the iceberg.

A unit test tests the tiniest part of a program that can be tested. This can be a free function, a class function or sometimes even a whole class. But thats it. However, most people are really writing component tests. A component is the combination of multiple units to give some larger functionality. A component test therefore tests this combination. Then there are integration tests, then regression tests, etc, etc. There is a whole spectrum of testing. You can find more information in Code Craft.

In a lot of projects, there is a huge gap between developer testing and QA testing. Usually the only type of testing that takes place including both groups is unit testing and usability testing, if you are lucky! And in a lot of these, neither the unit tests nor the tests QA run are automated; they usually require some manual intervention.

With a little bit of work, you can really boost the way you test your C++ code. There are a couple of things you need to do first:

  • Automated build

  • Automated deployment

That is, you need to be able to push a button to build the distributable from scratch and push another button to deploy the application. And yes, as you guessed, you need to wire one button to the other. If you used batch files to accomplish the above, do it again using either SCons, Ant, Final Builder or the bazillion tools created especially for automating builds. I shouldn't have to tell you this, but you would be surprised!

Anyway, the next step is to choose a tool for writing tests in C++. I have used Boost.Test with great success. For whatever this is worth, I highly recommend this library. You want to write your unit and component tests in this library, for obvious reasons.

Automate the running of these tests and add them to the automated build.

If you have been keeping up, and since you are a C++ guru, you are also proficient in a language like Python. Now pay attention: you will be writing at least half of your tests in Python! Really. Just because all your tests are either unit tests or component tests, does not mean that you don't need to be doing this! In my opinion, this is where most teams miss out. They write their tests in CPPUnit or Boost.Test and then it is off to QA. And the main reason is that C++ is not a glue language. It is an application/library development language. Python (or other languages with a REPL) shine at gluing components together. You can effortlessly write a whole bunch of portable tests by choosing to go this way. The Boost.Python library with some code generation will get you started with a minimum of fuss.

Whether you are shipping a library or an application, the addition of a Python API can be very useful: for a library, it is another checkbox in the "we support these languages" box. For an application it is a bullet point: "Fully portable scripting." Not to mention the benefits you'll reap.

The addition of this simple functionality means that now there is now no excuse not to automate all your non-UI tests. And if you are on Windows, with a choice few Windows API functions, you can do your UI testing in the same language. Quite handy.

Chances are, now you are going to have a bunch of Python scripts lying around which still need to be invoked manually. To close the loop, I would recommend QMTest to manage your tests and their dependencies.

Now don't lie, you aren't testing as much as you can in C++. You need Python for that :-)

Update: I forgot one very important aspect of this whole thing: continuous integration. I've used BuildBot with great success and would recommend it's use. One little thing you might want to add onto the bot is the ability to create builds for each platform, for each branch, automatically. I've done this using Subversion triggers and it is beautiful to watch in action.

More about delimited continuations

Chris Double has pointed me to a couple of articles that he wrote on the subject of partial continuations in Factor:

You go boy.

Tuesday, 27 November 2007

Wrapping my head around continuations

I am pretty clueless in general. But to my credit, I relentlessly pursue knowledge, some of it being useful! As you may know, I have been looking at Weblocks as I feel I would eventually reinvent it badly.

Anyway, one of the things that the author recently added was support for continuations. A very simple example was demonstrated, and lo and behold it worked! So I went off, confident that I understood what a continuation was. I created an app skeleton and started using with-flow. And it didn't work. I fixed some parentheses. It still didn't work. "Hmm," I thought, "perhaps continuations aren't just things to gloss over." So I went back and read Continuations-Based Web Applications in CL with Weblocks again. Still didn't get it. I finally ended up at Wikipedia's continuation entry. And it all made sense. I even understood what a delimited continuation was.

I went back to my code, moved a couple of more parentheses, added a couple of functions, and lo and behold, it worked!

Thank you Slava Akhmechet for making this useful feature available. Note, neither he or I are claiming that Weblocks is the first system to use continuations.

The use of continuations for Web applications should be more popular. I would assume the main reason it is unheard of is because most languages don't support it. To Java's credit however, this article discusses using continuations. However, true to Java form, the third listing uses XML. Sigh...

The Four Stooges of Standard C++

The C++ standard library is more than just std::vector<T,Allocator>. It is a rich set of data structures (containers) and algorithms that are functional in nature. At the very least, the library allows you to use higher-order functions to perform common tasks on the various containers. This is accomplished through functions such as std::for_each, std::transform and many others (scroll to the section on algorithms).

Why would you use the standard algorithms? Glad you asked. In my opinion, the main reason is readability. The above mentioned algorithms were the ones that came to mind immediately because they are the ones I've seen used the most. The aha moment for me (and indeed, I believe anyone that I've mentored) is that you realize that the algorithms communicate intent and not instructions. As we all know, declarative languages are so much better than imperative languages (except no one uses them.) But especially when it comes to data structure manipulation, being able to read what is going on rather than how it is being accomplished is great for readability. My intent is not to convince you of this fact, but just know that this is the main benefit for me.

Unfortunately, there isn't as much use of these algorithms as there should be. On the bright side, through the Boost libraries, people are being exposed (albeit indirectly) to their use more and more. This gives birth to four types of programmers or the Four Stooges (purely affectionate term):

  1. Eager beaver

  2. Wise old fart

  3. Scaredy-cat

Yes, I know there are three here :-)

The eager beaver is the (likely junior) programmer who must use a stdlib algorithm no matter how convoluted it appears. He has read The C++ Standard Library three or four times and can more or less flip to the exact page he needs. This is a very good programmer to have. Eventually he will gain experience when to use them, when not to use them, and how to really use std::remove_if, becoming quite pragmatic.

The wise old fart is the (likely senior) programmer who has been programming in C++ back when it was called CFront. He still thinks that the C++ standard library is unportable because of the time that HP changed that one thing with the IOStreams and his program crashed because of it (I made that up.) But, he is usually open to other people using it and doesn't chide them for doing so. He makes sure that whoever is using it, knows what he is doing though. This is a very good programmer to have. Eventually, he will start using the algorithms and because of his experience, will be very pragmatic.

The scaredy-cat is very difficult to root out. Usually, he appears to be disguised as the wise old fart: experienced, appears to be deliberate, questions what the other programmers are doing, among other generally paranoid activities. The dead giveaway though is that there is not one use of the C++ standard algorithms or data structures in his code. He will stick to arrays and for loops. This programmer is good to have because of his experience, but he writes potentially buggy code. An example of potentially buggy code is code that were you to resize a container to contain one less element, that would cause a buffer overrun later. No, you shouldn't "have known that would happen." That is why containers that know their size exist. I don't know how you deal with this guy. If he is very stubborn, it is a tough situation.

The first two stooges can eventually become the fourth stooge: the pragmatic programmer. This programmer does not magically appear but always an evolution of the first two stooges. He is the super stooge. He understands that sometimes you just need a for loop.

Sunday, 25 November 2007

Installing Weblocks on Ubuntu

One of the most annoying parts of ASDF is all the GPG verification that needs to happen. This is not my favourite thing to do, let me tell you.

Fortunately, Ubuntu 7.10 takes some of the pain away. To install Weblocks dependencies, you can do:

$ sudo apt-get install cl-closer-mop \
cl-hunchentoot \
cl-who \
cl-ppcre \
cl-puri \
cl-rt \
cl-md5 \

Then in the REPL:

(asdf-install:install :cl-json :tinaa :cl-cont :fare-matcher)

Then follow the instructions on installing Weblocks for getting Weblocks itself. Does someone know some easy way to verify the GPG keys besides hunting for the keys?

Update: mathrick on #lisp says "press 0". LOL!

Saturday, 24 November 2007

The all-elusive HTTP parameter bind-to-function-arguments

So last time, I mentioned that my defpage macro does not handle POST arguments. To recap, when writing the backend for a website, I'd like to treat my page definition as just a function call (sound familiar?) That is, if I was writing a page that returned the value of the submitted argument and added one to it, I'd really love to just write:

(defpage add-1 (a) #p"tmpl/add-one.tmpl"
(list :a-plus-1 (1+ a)))

Well now that dream is a reality. If you have been following along at home (I'm pretty sure I'm talking to myself just now), what we need to do is modify the defpage macro to iterate through each argument, look up the parameters using hunchentoot:get-parameter, setq them to something sensible, and call the body of our page.

Lets look at a macro expand of our macro now (yeah, thats right, I took a screenshot):

You can see in the above code that the macro generates some very bad code! But, it gets the job done for now. Here is the finished macro:

(defmacro defpage ((name args-list &key html-template)
&body body)
(unless html-template (error "Need html-template"))
`(defun ,name ()
(let (,@args-list)
(log-for (application info)
"Calling ~A with html-template ~A"
',name ,html-template)
,@(loop for arg in args-list collect
`(let ((arg-value (hunchentoot:get-parameter
(string-downcase (symbol-name ',arg)))))
(unless arg-value
(error (format nil
"Missing required value: ~A"
(string-downcase (symbol-name ',arg)))))
(setq ,arg arg-value)))
(let ((template-vars (progn ,@body))
(stream (make-string-output-stream)))
:stream stream)
(get-output-stream-string stream)))))

You must be saying: "You can't be finished Sohail, you don't handle non-string types in the arguments yet! Not to mention optional arguments! You are lazy!" You hurt my feelings by thinking that. But maybe, JUST MAYBE, I SHOULD JUST USE define-easy-handler. Believe me, I swore pretty loudly when I realized that existed. Oh well, atleast I learned something useful.

I'll just spend some time looking at lolcats. Ah, lolcats.

Friday, 23 November 2007

The sorry state of signalling conditions in "modern" languages

You know the mantra: "Only throw an exception in exceptional circumstances." A close brother of this mantra is: "Exceptions as flow-control are bad."

I submit to you, the single reader of this article: Exceptions as implemented by most languages are the solution to the problem: "Something bad happened! OMG! <commence-running-around-like-headless-chicken>." The problem should really be stated as: "Something bad happened! Is there anyone who can tell me what to do? If not, I'll just launch the debugger and wait for someone." It is a subtle but important difference.

Consider enabling some code to exit early because you want to have a quick test of the current parameters for validation. In C++, you might write:

int calc_value(int a)
parameters = setup_parameters();
int b = do_expensive_calc(parameters);
return b+a;
int do_expensive_calc(parameters p)
for(size_t i = 0; i < some_large_number; ++i)
if(i==1 && want_to_exit_early)
throw ReachedFirstIteration(calculated_value);
return calculated_value;

Oops! Except you can't do that can you? In a code review, inevitably someone is going to say: "HEY MAN NO EXCEPTIONS AS FLOW CONTROL. IT SAYS RIGHT HERE IN THE CODING STANDARD 1.9! (I'm so telling the boss)" And they are absolutely right. Well, except the snitching. We don't like those people. They aren't TEAM PLAYERS.

As you are new to the team, you go back and rewrite your code so you are no longer throwing the exception:

bool do_expensive_calc(parameters p, int & outval)
for(size_t i = 0; i < some_large_number; ++i)
if(i==1 && want_to_exit_early)
outval = calculated_value
return true;
return false;

Ugh. Mr. (or even Dr.) Senior Developer says: "Hey, thats the way this is done in C++. Whaddayagonnado?" and gives your code approval.

Mr. Senior Developer is right. But for the wrong reason. C++ compilers have been heavily, heavily optimized to have no overhead in non-exceptional circumstances. See this Going Deep episode on C++ exceptions for an understanding of how that is accomplished. Interesting stuff. But damnit, what about non-exceptional circumstances? And damnit, what about when I may not decide to take any action and want the code to keep going when this condition occurs?! So as you can see, he is right only because there is a big gaping deficiency in the C++ language and trying to patch the hole either gives you a performance issue or it makes the code ugly.

So hopefully you see now why the problem was restated. But that form still doesn't apply here. What we really want to say is: "Hey, I'm in some state, does anyone care? I'm just going to keep going otherwise." This is exactly what Lisp provides with the condition system.

The above example is a bit contrived. But what do you expect for a half hour of writing? See Chapter 19 - Beyond Exception Handling: Conditions and Restarts to get a very good example of when it is useful (and from a better writer.)

You can also see the video version of Practical Common Lisp if that appeals to you. Peter starts talking about conditions around 42 minutes into it.

Go forth and Lithp!

Thursday, 22 November 2007

Get your Juice here

For some odd reason, this link is very hard to find: Download JeOS

From what I can tell, JeOS (Just enough OS) is a stripped down version of Ubuntu which can be of use to ISVs looking to create virtual appliances. It has been optimized for VMware. I have no idea what that means.

I think virtual appliances are a great idea. There is no configuration anyone needs to do to get started and more importantly only one install configuration to support. I do wonder how the underlying OS stays up-to-date. With Ubuntu, its usually apt-get update && apt-get upgrade. I suppose one can schedule that one if all else fails.

Separating content generation from presentation generation

So where I left off last time, Bopinder and I had just created a sample page where (as a web designer) he was able to work on the application's front end without futzing around in Lisp. However, to get him there, I had to write a bunch of messy of code. See the end of the above linked article for the gory details.

In this article, there was the ever-present "business logic" intertwined with the code to generate the dynamic page (calls to html-template). Yuck. I would have to do this for every page! No good. So after writing the second page in this manner, I decided it was time to write a macro. Ideally, I would like to write:

(defpage add-one (a) "The value of a+1 is: <!-- tmpl_var a-and-one -->"
(list :a-and-one (1+ a))

That is, my page definition would amount to returning some named values. A formidable task! But a good separation in my opinion as then I could easily turn the results into a JSON (or XMSmell) service without blinking too much.

Since I have not yet written the macro to grab the values of the HTTP POST parameters that are posted to the page, lets pretend that functionality works as I expect, that is:

Would eventually call the function add-one where a is 1. Then the code inside the add-one function just has to concern itself with doing the actual calculations, not yucky HTML. I do have a nagging feeling that I will eventually reinvent WebBlocks badly, but that is how I learn!

The most important thing is that I want to be able to give hunchentoot a function called add-one which pulls out the required POST parameters, executes the body which returns our list with named values and passes this list to whichever template I specify. So here is the macro which now allows me to separate content generation from presentation generation (yay):

(defmacro defpage (name args-list template &body body)
; define a function
`(defun ,name ,args-list
; execute the function body
(let ((template-vars (progn ,@body))
(stream (make-string-output-stream)))
; make the call to html-template
:stream stream)
(get-output-stream-string stream))))

So given the above macro definition:

CL-USER> (defpage add-one (a) "a+1=<!-- tmpl_var a -->"
(list :a (1+ a)))
CL-USER> (add-one 1)

I figure that next, I will modify the defpage macro to pull out the POST parameters.

Wednesday, 21 November 2007

Interesting Google Trends

Someone turned me onto Google Trends as a way to gauge the popularity of certain search terms. The coolest thing about it is that you can compare the relative popularity of certain terms. Here are some I found interesting:

The most interesting one was Microsoft vs Linux. The interesting part is that searching for Linux is on a downward trend. The clever among you should be able to figure out why.

I think Google Trends is a good way to gauge market interest in something or the other, especially with respect to related/competitive terms (but not the only way!) I wonder if there are any other ways to do it online.

Tuesday, 20 November 2007

The let macro

I recently had the opportunity to read (and unfortunately let go of) Lisp in Small Pieces (LiSP). Fortunately, not before I had the opportunity to have my eyes opened.

One of the most basic useful units in any programming language are variables. Lisp has the concept of bindings which are an association between a name and the bound thing. In Lisp, you can bind functions as well as variables which is why the preceding definition (lifted from CLHS) is so generic. The LET operator is the mechanism to accomplish lexical binding as one is used to in other languages. So if one were to write the following n C++:

int a = 5;

The equivalent Lisp would be:

(let ((a 5)) ... )

Where the ellipses denote the scope in which the binding is valid.

For most people, thats where it ends: "Ok, so now I can declare variables. Yay." And for me, that was the case until I picked up LiSP. LiSP develops a Scheme-like language whose definition is in Scheme to start with. But did you know that the LET operator can be defined if all you have are lambda functions? I sure didn't! For example:

(let ((x 5) (y 2)) ...)
; becomes
((lambda (x y) ...) 5 2)

Wow! For those of you who missed it, the implementation of LET can be a call of a lambda function. Now of course there are little details missing here like the fact that you need some way of looking up the bindings, but that is fairly easy if implementing the interpreter.

LiSP is full of these little insights and I really need to buy a copy for myself. Cherish the book if you have it!

Monday, 19 November 2007

What does it mean to be a (good) C++ programmer?

I was recently asked this question by someone who is looking to move from a system admin type role into a programming role, specifically in C++.

The first thing that came to my mind was: "You want to be a C++ programmer?" But that was just pure shock as I thought I would be the only person alive besides Bjarne who actually wanted to learn C++. The rest of us obviously committed suicide after having come across one too many non-compliant compilers.

In the world of hired C++ programmers, there are two types: the ones you want to hire and the ones you don't want to hire but do anyway. What follows is a list of characteristics (?), that in my humble opinion, differentiate these two types of programmers. A C++ programmer you would want to hire:

  • Can explain the modern C++ tool chain in excruciating detail, including how templates are compiled and linked. From memory.

  • Is proficient in at least one dynamically typed language that doesn't start with Visual Basic. Java is not dynamically typed.

  • Has read The C++ Programming Language. Twice.

  • Understands functional programming concepts.

  • Is not a patterns freak.

  • Is a minimalist when it comes to coding: the code you don't write, works.

On top of these, there are a few other software engineering related characteristics such as understanding the need for continuous integration, QA, iterative development and developer testing.

None of these have anything to do with being a C++ programmer in particular. So lets rephrase the question a bit: What does it mean to be a good programmer?

A good programmer you would want to hire:

  • Can explain the implementation of the chosen programming language in excruciating detail. Including garbage collection. From memory.

  • Is proficient in at least one other language that requires a paradigm shift.

  • Has read the <Programming language X Bible >. Twice.

  • Understands functional programming concepts.

  • Is not a patterns freak.

  • Is a minimalist when it comes to coding: the code you don't write, works.

The bottom line is: no matter what programming language you choose, you must be the best at it but make sure that you are also proficient in something that can be considered the total opposite of your language of choice. However, that is not all there is to it. You must also be aware of the software life cycle and understand where your language helps you and where it doesn't. There are very few people who get this. And of all 5 of you who will read this post, one of you will get it.

Sunday, 18 November 2007

Ok, so the government ain't that bad

The least fun (and second most important) part of running a business is keeping within the laws of the land when it comes to operating and taxation.

Last year, you had to file PST in British Columbia every month and remit by the 15th of the next month. In addition to the GST and depending on revenue, it could add up to 25 units of paperwork per year just to keep the Government happy. In addition to your own return! That adds up to a lot of accountant fees and administrative overhead. For a small business with modest revenue, you would have to file 15 units of paperwork per year.

I was very happy to learn that the PST leashes have been loosened so for business with modest revenue, you have to file 4 units of paperwork:

  • 2 PST returns

  • 1 GST return

  • 1 annual return

Not bad! Just have to verify with my accountant that I am right first. I still wish it was just one unit of paperwork per year but I knew there would be some paperwork involved when I signed up!

Lisp web framework - Designer friendliness

As promised in an earlier post, I was going to take a look at another way to generate HTML for a web app written in Common Lisp. I decided that cl-who would be good for quick scripting but would be a major bottleneck when developing the front end. The main basis for this decision was that it required some knowledge of Lisp should things go horribly wrong and the person developing the HTML would not necessarily know Lisp. So I took a look at a templating library called html-template. Calling it html-template is a bit of a misnomer because the parser actually knows nothing about HTML. Thank *GOD* (get it?) This means that it is useful for generating more than just HTML. Not that we will make use of this capability just yet.

The way templating libraries work is that you write some text in a string or file with special characters that will be replaced with some values at runtime. Some templating libraries (including html-template) include control flow such as looping and if statements. A simple example follows:

# file: template.tmpl
# This template requires the variable: subject
Hello, <!-- tmpl_var subject -->!

The intended result here is that when a program or function is called with a given subject, it generates "Hello, Sohail!" for when the subject is Sohail. The variable is referenced with <!-- tmpl_var subject -->.

To generate the result, one usually gives the templating library the file or string containing the template (in this case, template.tmpl) and a data structure mapping names to values. So, in some hypothetical language called Lisp, with a hypothetical library called html-template, you might write:

CL-USER> (html-template:fill-and-print-template #p"template.tmpl"
(list :subject "Sohail"))
Hello, Sohail!

Quite simple really. Now imagine the content of the file containing some HTML directives around the variable reference. Presto! A web page is dynamically generated. Sweet.

Anyway, to determine whether this templating technique accomplishes my goal of being designer friendly, I donned the hat of a CSS/HTML artist. Pay no attention to the fact that I am actually quite clueless when it comes to CSS/HTML. I figured the technique would be golden if the designer could focus on the layout and aesthetic appeal of the site while I could focus on the backend. The CSS/HTML guru's name is Bopinder. Here is our conversation:

Sohail: Hey Bopinder, I've heard some great things about your web design skills. I'm writing a blog app and I want to make it look pretty.
Bopinder: Yes, my strengths lie in web page aesthetics. I hope there isn't much programming involved.
Sohail: No, there isn't! Or atleast I hope not. I am writing the backend in Lisp, which is quite possibly the second most obscure web programming language in existence. But I get stuff done quite fast and it is free! I figure we will use a templating library called html-template. If you have done templating before, it shouldn't be a problem.
Bopinder: Sounds good to me. In fact, I have done templating using something written in Java.
Sohail: Java sucks.
Bopinder: Yeah, I don't even program and I could tell you that.
Sohail: Looks like we'll get along just fine, you and I! So anyway, I figure we will start on a blog entry page. My current page looks like this:

Bopinder: Dear God.
Sohail: Hey, I'd like to see your Lisp code!
Bopinder: Good point.
Sohail: Ok so here is the file you need to edit: template.tmpl. I have set up a server for you here: You can ftp the changes to that file here:
Bopinder: Ok... So is there some layout you like?
Sohail: Yeah, I'd like it to look classy. Like I'm environmentally friendly as well.
Bopinder: So lots of green.
Sohail: Sounds good to me!
Bopinder: I meant the colour.
Sohail: Oh. Yes, well that too. Why don't you just come back with something in 3 days and we can discuss where to go from here.
Bopinder: Sounds good.

So Bopinder went away, cursing my HTML skills under his breath and came back with something quite nice. It was CSS-based and there were no tables. More importantly, whenever he needed some more variables, he was able to put in stubs and sent me a list of the information he would have liked to put on the page. Even more importantly, he never touched Lisp. He only read the html-template documentation and asked me a few questions every now and then. That was awesome. Anyway, without further ado, the exact same page, after Bopinder got through with it:

Blog entry with some comments:

Adding comments:

So all in all, not bad for someone with multiple personalities. I later discovered that Bopinder ripped off the site design from Freelance Switch. Good thing I found out before I gave him the second half of the deposit! To anyone reading, do not hire Bopinder!

Here is the template (converted using Quick Escape). Something to notice is that Bopinder could reference variables within tag attributes without breaking a sweat. Of course this is possible because html-template knows nothing about HTML.

<!-- Hey emacs, this is a -*- html -*- file! -->
This template requires:
id: The blog entry id
title: The blog entry title
timestamp: A formatted representation of the timestamp
body: The blog entry itself
comments: A list of comments. The list of comments would contain author, timestamp and content variables
<link rel="stylesheet" href="/static/style.css" type="text/css"/>
<body id="blog">
<div id="content">
<div id="post" class="post">
<a href="/entries?id=<!-- tmpl_var id -->">
<h2 id="title">
<!-- tmpl_var title -->
<a href="">
<h3><!-- tmpl_var author --></h3>
<!-- tmpl_var timestamp -->
<div class="post-content">
<!-- tmpl_var body -->
<ol class="comments">
<!-- tmpl_loop comments -->
<li class="comment">
<div class="commentor">
<p class="comment-author">
<a href=""><!-- tmpl_var author --></a>
<p class="comment-metadata">
<!-- tmpl_var timestamp -->
<div class="the-comment">
<!-- tmpl_var content -->
<!-- /tmpl_loop -->
<div style="clear: both;"/>
<h2>Add Comment</h2>
<div id="formcontainer">
<form id="commentform" method="post" action="/add-comment">
<input type="text" value="" name="name"/>
<label for="author">
Name (required)
<textarea id="comment" name="comment"></textarea>
<input id="submit" class="button" type="submit" value="Submit Comment" name="submit"/>
<input type="hidden" name="id" value="<!-- tmpl_var id -->"/>

Just a reminder: Bopinder and I are the same person. Bopinder is to Sohail as Clark Kent is to Superman. The situation depicted above is purely fictional and I would wholly recommend Bopinder for your next project.

And for the extra curious, here is the Lisp code used to generate the above page (don't mind the weird parentheses placement, I'm trying something new):

(defun render-blog-post (post)
(let* ((comments
(loop for comment in (comments post)
collecting (list :timestamp (fmt-date (timestamp comment))
:author (author comment)
:content (content comment)))
(vars (list :id (id post)
:title (title post)
:body (body post)
:author (author post)
:timestamp (fmt-date (timestamp post))
:comments comments
(stream (make-string-output-stream))
(html-template:fill-and-print-template #p"render-blog-post.tmpl"
:stream stream)
(get-output-stream-string stream)


Saturday, 17 November 2007

A Polynominal Time Algorithm for Graph Isomorphism

A Polynominal Time Algorithm for Graph Isomorphism

Algorithms testing two graphs for isomorphism known as yet have exponential worst case complexity. In this paper we propose a new algorithm that has polynomial complexity and constructively supplies the evidence that the graph isomorphism lies in P.

Will be very interesting to see if the algorithm is indeed correct. I wonder how this process works. Do they have millions of comp sci geeks on hand to verify it? I know that these computational complexity problems were the most interesting problems I did in school. Reducing one problem to the other was awesome.

I'm going to try and give it a read if I have some time and brainpower.

Friday, 16 November 2007

Negative people: Good or bad for business?

I've been thinking about this recently. Thankfully, I haven't seen too much of it, but I have noticed that there are people who will be negative at any cost. Especially when it comes to starting a business. "Oh, you're never going to succeed" or "Oh, there is too much competition".

In general though, I never let any of these people get away with it. I usually ask: "So why do you think that this is true?" Most of the time, the answer is weak, something like: "Oh, well I tried running my own business and it didn't work." Obviously, you can see why that is not a strong argument. But sometimes, just sometimes, you get a nugget of wisdom from these Negative Nellies that can give you new insight into your business or market: "Oh, I tried running my own business and it didn't work because I was too focused on product development and not marketing." The start of an enlightening conversation. I think all those Negative Nellies are worth their weight in gold if you can use them the right way.

On a similar topic, I came across a very interesting quote by the US President Theodore Roosevelt* here:

It is not the critic who counts; not the man who points out how the strong man stumbles, or where the doer of deeds could have done them better. The credit belongs to the man who is actually in the arena, whose face is marred by dust and sweat and blood; who strives valiantly; who errs, who comes short again and again, because there is no effort without error and shortcoming; but who does actually strive to do the deeds; who knows great enthusiasms, the great devotions; who spends himself in a worthy cause; who at the best knows in the end the triumph of high achievement, and who at the worst, if he fails, at least fails while daring greatly, so that his place shall never be with those cold and timid souls who neither know victory nor defeat.

Very inspirational.

* Yes, I know he had some very interesting views but this view was not at all uncommon at the time. It is only less blatant now!

Monday, 12 November 2007

Update: Web programming frameworks

So I've been using Hunchentoot to develop a blogging application. Nothing spectacular. If anyone actually reads this and is interested, I can send you the source.

The best things about it so far:

  • SLIME. Oh man, this has got to be the most productive development environment ever
  • Very flexible/DIY
It doesn't get in my way at all which I like very much. I've been more or less following the LispCast Lisp Reddit episodes (only the source, I don't have enough time to watch the videos!)

One of the most painful points of Hunchentoot is that you cannot accept posted arguments like function arguments as you can with CherryPy. What I would really like to do is something like the following:

(defdynamicpage add-post ( (title string) (content string) &optional (tags list) )

Right now, you have to write some mess like:

(defun add-post ()
(let ((title (hunchentoot:parameter "title")))
(when (empty-parameter-p title)
(hunchentoot:redirect "/"))

Where empty-parameter-p checks for null or zero length strings. I'm sure I can write some macro to handle it if I end up caring enough about it.

Also, using cl-who is probably not the smartest thing to do if you want a designer's help. I think the next step will be figuring out the best setup to allow a designer to do her work without requiring knowledge of Lisp.

Saturday, 10 November 2007

You are inferior!

What is an ``inferior-lisp''?

For the longest time, I'd wondered why Emacs always called an ``inferior-lisp'' process. Apparently, the term refers to a child Lisp process. Through IRC and Google, I became aware that this term was normally used in the TOPS-10 operating system. Since Emacs was first written on the PDP-6 and PDP-10 machines, that is a good an explanation as any.

All this time, I thought the Emacs authors considered Emacs Lisp to be better than all other Lisps!

I for one, would like a return to this terminology. Kill the inferior processes!

Friday, 9 November 2007

Yay for IRC

So last night I sent yesterday's post to #lisp for some feedback. Lucky for me, Peter Seibel of Practical Common Lisp fame was online and read over my post.

He pointed out that the special characters which are useful in macro expansion actually have nothing to do with macro expansion *at all*. For example, the backquote character is useful for creating lists while interpolating values. This surprised me but if you read Peter's book, specifically Chapter 8 - Macros: Defining Your Own, you would surely come to that understanding.

In the end, the best resource on macros for a noob is definitely the above linked chapter. I will have to read it again tonight.

Peter also looked over my multiple-value-bind post and pointed to his own macro. It is actually quite clever but I still prefer my solution :-)

Thanks Peter, I appreciate your time!

Thursday, 8 November 2007

Common Lisp macros cheatsheet

One great feature of Lisp is that it's syntax is very minimal. When it comes to macros, the syntax really is (syntactically) minimal. A macro is basically Lisp code that gets run at "compile time" and is usually used to generate code. However, since it is Lisp code, it could just as well access a database if you are into those sort of things! Take a look at yesterday's post for a useful example of code generation with macros.

Since macros are just Lisp code, there are special characters that come into play when evaluating macros, essentially to determine when the code will be evaluated. By default, the code is evaluated at macroexpand-time.

; this progn is executed at macroexpand time
CL-USER> (defmacro test-1 () (progn 'foo))
CL-USER> (macroexpand '(test-1))
; this progn is executed at runtime
CL-USER> (defmacro test-2 () `(progn 'foo))
CL-USER> (macroexpand '(test-2))

So the `(backquote) character delays evaluation until runtime. Nice. Here we've used the quite helpful macroexpand function to expand the macro.

What if you wanted to write a macro that would print the sum of it's two constant arguments? You might try writing:

CL-USER> (defmacro test-3 (a b) (print (+ a b)))

But watch what happens when we expand it:

CL-USER> (macroexpand-1 '(test-3 1 2))

Oops! What we really wanted to happen was have (test-3 1 2) expand into (print 3) but what our attempt above really did was print out the result at macroexpand time. To get around this, we want to be explicit about what to evaluate during macroexpand time and what to leave until runtime:

CL-USER> (defmacro test-4 (a b) `(print ,(+ a b)))
CL-USER> (macroexpand-1 '(test-4 1 2))

So what we did above was use the backquote character to delay evaluation of the print form but evaluated the sum form by prefixing it with a comma. Double nice.

That leaves only one(?) remaining macro-specific character: ,@. This one is not so complicated given our understanding of the comma character above. What it means is to evaluate the list following ,@ at macroexpand time but removes the outermost level of parentheses and inserts the result at this point. For example:

CL-USER> (defmacro test-5 (operands) `(+ ,operands))
CL-USER> (macroexpand '(test-5 (1 2 3 4 5 6)))
(+ (1 2 3 4 5 6))
CL-USER> (defmacro test-6 (operands) `(+ ,@operands))
CL-USER> (macroexpand '(test-6 (1 2 3 4 5 6)))
(+ 1 2 3 4 5 6)

So to summarize (i.e., cheatsheet!):

  • ` - backquote operator: delay evaluation of prefixed form until runtime

  • , - comma operator: within a delayed form (i.e., backquoted), evaluate prefixed form at macroexpand time

  • ,@ - comma-at operator: within a delayed form (i.e., backquoted), evaluate prefixed form at macroexpand time and remove outermost level of parentheses

  • macroexpand is a useful function for debugging the code your macros generate

How does one go back to C++/Java and friends after this?

Update: See this followup post to see what a Lisp noob I really am.

Wednesday, 7 November 2007

The power of Common Lisp macros

I have started looking at Hunchentoot as I threatened to do in an earlier post. The app I'm going to use to benchmark the framework is a blogging app. Going pretty well so far, I must say.

One of the functions I am using is decode-universal-time. It returns multiple values which you can liken to tuples. For example:

CL-USER> (decode-universal-time (get-universal-time))

The usual way of dealing with these types of functions is to use multiple-value-bind which essentially creates bindings for each value. However, this usually means that you have to bind all the values, even if you don't want to:

CL-USER> (multiple-value-bind
(second minute hour date)
(decode-universal-time (get-universal-time))
(print date))

So you can see that just to get at the date value we had to bind three other value. Not only is this annoying but SBCL complains about it:

; The variable SECOND is defined but never used.
; The variable MINUTE is defined but never used.
; The variable HOUR is defined but never used.
; compilation unit finished
; caught 3 STYLE-WARNING conditions


In Python, one can write:

_,_,_,date = decode_universal_time(get_universal_time)

Which is also known as destructuring assignment (by me!)

So ideally, I would have loved to write:

(multiple-value-bind (_ _ _ date) (decode-universal-time (get-universal-time)) (print date))

Whats that? Smells like a language extension? Ah, you mean a macro, what Lisp has had natively since forever. Thanks to some help from the fine people on #lisp, I have written my first useful macro:

(defmacro multiple-value-bind-2 (bindlist value-form &body body)
(ignores-list args-list)
(make-gensym-and-fixed-bindlist bindlist)
(declare (ignore ,@ignores-list))

; Take a list of symbols that may contain _, and return two lists
; first being a list of the symbols generated, the second being a list
; of the _ replaced with said generated symbols.
; (make-gensyn-and-fixed-bindlist '(a b _ d)) =>
; (:#G1023)
; (a b :#G1023 d)
(defun make-gensym-and-fixed-bindlist (bindlist)
(let* (gensym-list
(fixed-bindlist (loop for item in bindlist
when (eq '_ item)
collect (car (push (gensym) gensym-list))
else collect item)))
(values gensym-list fixed-bindlist)))

I called it multiple-value-bind-2 because I have no idea how Lisp packages work yet and don't know how to create my own that exports this macro. Here is example usage:

CL-USER> (multiple-value-bind-2
(_ _ _ date)
(decode-universal-time (get-universal-time))

Pretty damn sweet.

I apologize for the bad formatting, I have not yet figured out how to get blogger to let me put code snippets :-(

Update: Figured out that using the <pre> tag does the job wrt code snippets.

Tuesday, 6 November 2007

Web programming frameworks

I've been putting this off for long enough. I want to decide on a web programming approach. In the past, I've used ASP.NET and Python CGI. They are both OK but last I remember, ASP.NET relies on a crap load of wizard generated code and this is bad. CGI is just annoying.

I guess it would help to list my criteria:

  • Designer-friendly
  • Small is beautiful
  • No generated code required
In the Python world, I've toyed around with CherryPy. I thought it was quite good and it allowed me to (more or less) focus on the app I was writing rather than jamming the framework into my app. I have no problem at all with CherryPy and might just stick with it.

In the Common Lisp world, I want to try UCW and Hunchentoot. My favourite thing about UCW is that it tries to hide you from the bad world of stateless HTTP in quite a clever way. I don't think that there is anything particularly novel about Hunchentoot except that it doesn't get in your way. This is another way of saying "do-it-yourself" which I am more than happy to do. In general, both of these guys fulfill my (admittedly small) set of criteria.

I know that Java is the 800-pound gorilla in this space and to be honest I haven't actually tried any of the Java frameworks. I don't think any framework can make up for Java though so I would likely use some other JVM language were I to try a Java web framework.

I think I'm going to try one of the Common Lisp frameworks (obviously using SBCL) and see about reporting my findings!

Edit: Looks like Django is a contender as well

Monday, 5 November 2007

Pursuing your dreams

When I was younger, I wanted to create music for the rest of my life. Never mind that I didn't know a half-note from a quarter-note (and still don't!) That never entered my mind. But then one day, I met the Turing programming language. And it was love. Fortunately, I've always found that tracking and coding are complementary. So my dream evolved a bit: I wanted to create music and software for the rest of my life.

I will spare you from the clich├ęd details of the current state of my life goals but to me, pursuing a dream/goal means always inching yourself closer. It is rare that someone is fortunate (stupid?) enough to drop everything and pursue that one single overarching desire. Usually, life gets in the way. People have families, mortgages and obligations which feel more important than your goal. Not to say that they aren't equally important (well, not mortgages anyway!) but people shelve their dreams for the wrong reasons.

Sometimes, keeping the pursuit of the dream alive is as important as achieving it.

Friday, 2 November 2007

How many Java programmers does it take to round up to a power of 2?

Came across this thread through the news.yc RSS feed. Found it quite interesting for many reasons. Now I know I haven't handled negative values, but here is what I did in Python:

def roundup_pow2f(a):
if a <= 0: raise RuntimeError, "Oops. doesn't handle negative values"
import math
power = math.ceil(math.log(a,2))
return math.pow(2,power)

def roundup_pow2i(a):
if type(a)!=type(0): raise RuntimeError, "Only works for ints!"
if a <=0: raise RuntimeError, "Oops, doesn't handle negative values"

while(next_one_up < a):
next_one_up = next_one_up << 1
return next_one_up

assert(roundup_pow2f(1)==1) # nearest power 1 = 2^0


There is some ambiguity about the exact needs of this somewhat anonymous Java programmer but in my world, when you say "round to the next" you usually mean "round to the nearest one up." So rounding up by 2's, if you input 2, the output is 2.

But I am not a Java programmer. Actually, this might be a trivial enough problem to try in Factor for learning purposes!

Thursday, 1 November 2007

Build Systems

The F5 key is not a build process

In my opinion, building software is the most important part of the development process besides developing the actual code. I think this is even more important than bug tracking. To me, a build process must:

  • Be fully automated aka "Push-button builds"
  • Only depend on source (no pre-built tools or libraries thank you very much)
  • Run sanity tests
  • Be able to run torture tests
  • Build a package you can ship to QA or clients
One way to accomplish most of the above goals is to use a build system. My favourite tool in this space is currently SCons. While it isn't nearly as sexy as Boost Jam, and scripts can be quite verbose, it is flexible enough to implement my favourite part of Boost Jam: usage requirements.

Usage requirements are essentially a neat way of saying: If you are going to use this module, then you should use these flags to compile. For example, if I was using static library A to create executable B, A might require me to add -DUSING_LIBA_STATIC=1 to the command line (and will most definitely require some linker flags.) In traditional build systems, this logic would be forced on the client usage in some annoying way:

# pseudo-makefile syntax
app: libA.a main.cpp
$(CC) $(LIBA_CCFLAGS) $(LIBA_LINKFLAGS) main.cpp -o app

Not bad but it can quickly get redundant and complex when the number of libraries grows. With Boost Jam:

exe app : main.cpp /path/to//libA ;

Thats it. Pretty neat eh? This is one feature that I sorely wish existed in SCons. However, it is possible to approximate the above:

def build(env):
return env.Program('app','main.cpp')

I just prototyped something like this last night that handled propagated usage requirements. I doubt I will need the full power of Boost Jam usage requirements, but even just being able to have the logic in one place would make life a lot easier for me.

I have yet to decide whether it is a kludge or an elegant hack :-)