untyping: August 2007 Archives

« July 2007 | Main | September 2007 »

August 23, 2007

As recently seen on the Untyped Subversion commit list...

I personally watch commits go by for several projects, and it is instructive in many ways to read the commit messages and code. It is a way to learn new things about the software process as well as the implementation of solutions in code. That said, very occasionally, you actually get a giggle from the process...

Today was one of those times.

Date: 2007-08-22 12:22:06 +0100 (Wed, 22 Aug 2007)
New Revision: 1398
Log:
[DJG] IDCheck trunk:

Tests tests tests.

Date: 2007-08-22 12:41:46 +0100 (Wed, 22 Aug 2007)
New Revision: 1399
Log:
[DJG+NHW] IDCheck trunk:

Testing all the way.

Date: 2007-08-22 12:49:21 +0100 (Wed, 22 Aug 2007)
New Revision: 1400
Log:
[NHW+DJG] IDCheck trunk:

Oh what fun it is to ride on a one horse testing sleigh.

The song ends there, I'm afraid... but it does seem like Dave and Noel are a bit cracked out today. Perhaps they should be out playing frisbee instead of coding this fine Thursday. As I'm not in the same timezone, it's difficult to say what's going on over there...

Posted by jadudm at 12:44 PM | Comments (1)

August 21, 2007

S3 Doesn't Count the Pennies (Yet)

This is post is from Dave, though it is posted under my name -- Noel

I use Amazon S3 as an off-site backup for data on my desktop computer. S3 has two principle advantages: there's no upper limit on the amount of data you can transmit or store, and it's very cheap... sometimes a little too cheap.

Two days ago I received an auto-generated warning from S3 about my account status:

Greetings from Amazon Web Services,

AWS was unable to charge your account based on the payment information you provided. Please update your payment method information using the Your Web Services Account section of the AWS web site.

Sincerely,

Amazon Web Services

There were a few extra details in there that convinced me that this wasn't spam, but that was the gist of it. I logged on to my account to find that my balance was a whopping $0.01. A single cent!

I checked my credit card details and they seemed to be okay. I re-entered them to be on the safe side, and then emailed AWS asking them to re-try the payment and let me know if it failed again. I received this response:

Thank you for contacting AWS regarding the payment issue related to your August 1st bill. We have found that some credit card issuers decline charges of $0.01 (USD), especially when the amount is converted to another currency. AWS is working on a solution for this issue. In the meantime, please contact AWS directly at webservices@amazon.com if this issue should occur again.

The $0.01 (USD) charge on your August 1st bill has been forgiven, and your account is in good standing.

A month's backups, totally free of charge - that's value for money. I shall be recommending S3 to all my friends.

Posted by Noel at 12:05 PM | Comments (4) | TrackBack

August 06, 2007

Refactoring Functional Programs

A little while ago we released an interface to Selenium, a web testing framework. Since then we've learned that Selenium is simply too slow to use in our work-flow. Hence we started on a faster reimplementation of the Selenium Remote Control.

A key part of this system is a proxy server, which is necessary to get around the same origin security restriction in Javascript. I've just finished a large refactoring of the proxy code, and I think the experience is interesting enough to warrant a blog post. While there is a large literature on refactoring object-oriented programs, there is rather less on refactoring functional programs, and what there is tends to concentrate on program transformation tools (long a FP strength) at the expense of collecting useful FP refactorings. This post is a small contribution to redressing the balance.

The code I spent most time on was the HTTP parser. It is structured as a state machine, so the initial version used the classic FP pattern of mutually tail recursive functions. The code for parsing an HTTP request looked something like this:

(define (parse-request)
  (define request-line #f)
  (define headers #f)

  (define (parse-request-line)
    (set! request-line (read-request-line))
    (parse-headers))

  (define (parse-headers)
    (let ([line (read-line)])
      (if (end-of-input line)
          (begin (set! headers (reverse headers))
                 (do-something))  
          (begin (set! headers (cons line headers))
                 (parse-headers)))))

  (parse-request-line))

The code for parsing an HTTP response was very similar:

(define (parse-response)
  (define response-line #f)
  (define headers #f)

  (define (parse-response-line)
    (set! response-line (read-response-line))
    (parse-headers))

  (define (parse-headers)
    (let ([line (read-line)])
      (if (end-of-input line)
          (begin (set! headers (reverse headers))
                 (do-something-different))  
          (begin (set! headers (cons line headers))
                 (parse-headers)))))

  (parse-response-line))

The real code was several screens long. I wanted to make it simpler by changing to a functional style, and reusing common code between the request and response parsing functions. Converting to functional style is simple:

(define (parse-request)
  (define (parse-request-line)
    (define request-line (read-request-line))
    (parse-headers request-line))

  (define (parse-headers request-line)
    (define headers
      (let loop ([line (read-line)])
        (if (end-of-input line)
            null
	    (cons line (loop (read-line))))))
     (do-something request-line headers))

  (parse-request-line))

Reusing common code is not simple. The finite state machine pattern doesn't abstract the next state. For example parse-headers in parse-request always calls do-something whereas the otherwise identical version in parse-response calls do-something-different.

I solved this by refactoring the code into continuation-passing style, leading to code that looks like the following:

;; shared between parse-request and parse-response
(define (parse-headers request-line k)
  (define headers
    (let loop ([line (read-line)])
      (if (end-of-input line)
          null
	  (cons line (loop (read-line))))))
  (k request-line headers))

(define (parse-request)
  (define (parse-request-line k)
    (define request-line (read-request-line))
    (k request-line))

  (parse-request-line
    (cut parse-headers <> do-something)))

Note that I've used cut as a short-cut for lambda.

I've got code reuse but the code itself isn't nice. The arguments lists were quite a bit longer in the real code and most of the time arguments are just passed from function to function without being used (I've seen these sort of arguments called “tramp data”). I also find that CPSed code can be quite difficult to read — you have to construct the control flow graph in your head and then look at the application site to fill in all the continuations. Ugh.

One way to get rid of tramp data is to use parameters, and this something we talk about in our experience report. However that solution isn't appropriate here. It forces me to stick with CPS so I can set the parameters in the dynamic extent of the succeeding code, and it extends the lifetime of the values beyond what is strictly necessary. This could be an issue if storing, say, a large request body in a parameter.

Notice that the different versions of parse-request only differed in which function they called with the value they computed. If I separate out the computation of that value, and the decision of which function to call I can get code reuse without CPS, and I don't have long argument lists! This is what my final solution looks like:

;; shared between parse-request and parse-response
(define (parse-headers request-line)
  (let loop ([line (read-line)])
    (if (end-of-input line)
        null
	(cons line (loop (read-line))))))

(define (parse-request)
  (define (parse-request-line)
    (read-request-line))

  (do-something (parse-request-line)
                (parse-headers)))

(define (parse-response)
  (define (parse-response-line)
    (read-response-line))

  (do-something-different (parse-response-line)
                          (parse-headers)))

It's short and sweet, and easy to understand.

So let's recap what I did:

I started with the mutually tail-recursive FSM pattern (that's a mouthful!)
I refactored into continuation-passing style.
I separated computation and control, and refactored back to direct style.

So three refactoring (direct style to CPS, separating computation and control, and CPS to direct style), two of which are particular to functional languages, and one pattern. I could do with a better name than “separating computation and control”. If you're aware of some prior work or can think of a better name do let me know.

Although they use different terminology, the programming language theory and software engineering communities have explored a lot of the same ground from different perspectives. Program transformations are pretty much the same thing as refactorings, though the former are often presented in the context of compiler optimisations. Functional Pearls are very similar to design patterns.

If you're a student of software engineering in functional languages it is necessary to familiarise yourself with this literature. This can be difficult. There are no books summarising this literature, as you'll find for OO languages, and the papers are often terse and are not focused on software engineering. This means they can be difficult to read if you don't have a background in programming languages, and you have to read between the lines a bit.

Posted by Noel at 01:23 PM | Comments (2) | TrackBack

August 02, 2007

A Scheme Case Study

If you've looked at the ICFP 2007 preliminary program you'll have noticed we're presenting “Experience Report: Scheme in Commercial Web Application Development”. We submitted the final version of the paper a couple of weeks ago, and I've finally got around to putting it online for your reading pleasure. The contents shouldn't come as a surprise: a summary of our experiences developing commercial web applications in PLT Scheme over the last year. We've tried to be honest, including the good and bad. Hopefully the points you'll take away are that we've been able to overcome initial problems with stability, and in a fairly short time we've developed a framework that compares well to popular alternatives such as Ruby on Rails.

The four page limit on experience reports is very tight, and unfortunately our experiences with Flapjax were cut from the final version. So let me say here that if you write Javascript code you need to check out Flapjax! Our Flapjax code is about half the size of the equivalent Javascript, and this is without using the Flapjax compiler. The only problem with Flapjax is performance in large networks. This is more a property of the poor quality of Javascript interpreters: Wolfenstein 3D on my 286 back in 1990-something was smoother than Javascript raycaster running today on my Powerbook. Luckily the new developments taking place at Mozilla will alleviate this problem in the next few years.

Posted by Noel at 09:47 PM | Comments (6) | TrackBack