Archive for the ‘Functional’ Category

Reading On Lisp: Then and Now…

December 27, 2007

“In The Mythical Man-Month, Frederick Brooks proposed that the productivity of a group of programmers does not grow linearly with its size. As the size of the group increases, the productivity of individual programmers goes down. The experience of Lisp programming suggests a more cheerful way to phrase this law: as the size of the group decreases, the productivity of individual programmers goes up. A small group wins, relatively speaking, simply because it’s smaller.” (On Lisp, p 5.)

“Sophisticated users now demand so much from software that we can’t possibly anticipate all their needs. They themselves can’t anticipate all their needs. But if we can’t give them software which does everything they want right out of the box, we can give them software which is extensible. We transform our software from a mere program into a programming language, and advanced users can build upon it the extra features that they need.” (On Lisp, p 5.)

“So yes, reading a bottom-up program requires one to understand all the new operators defined by the author. But this will nearly always be less work than having to understand all the code that would have been required without them.” (On Lisp, p 59.)

I imagine that most people picking up On Lisp these days are mainly interested in two things: how do you use macros and what can lisp do that other languages can’t do? But after an inspiring introduction that deftly weaves in themes that are regularly discussed and debated even fifteen years after the book’s publication, the reader is faced with several dry chapters that focus on functions and utilities. To someone with little experience with functional programming, basic computer science, or extensive lisp coding, much of it will seem pointlessly tedious and pedantic.

I was just such a person last May just before starting this blog. I really wanted to skip ahead to the good stuff and savor Graham’s prose, but I was like Luke Skywalker cutting out on his training to go fight Darth Vader. (I was just about to get my face smashed by gigantic futuristic heavy things as I tried to wrap my mind around a lot of mind-blowing material.  Or something like that.) I strained myself through several chapters of On Lisp even though I understood little of it and finally exhausted myself. And yet, I have code that I wrote about that time that violates the spirit of everything Graham was trying to say! I was completely lost.

There’s really only a few core ideas that you need to know about, though. You need to know what functions can do inside and out before you can understand when to use macros. You need to know about recursion, iteration, accumulators, and mapping. You need to be able to reflexively see the skeleton of a function, know how to abstract it out, and know how create customizable functions that take functions for arguments. And you need to have coded enough of this stuff in Lisp such that you’ve done certain things over and over and over again. If you get to chapter 4 and don’t immediately think, “man, these utility functions are all stuff I wish was already built into the language!” then you probably haven’t done enough Lisp coding to appreciate the book. SICP covers all of these things and more. If you can work through the first two chapters of SICP, then you’ll be more than prepared for On Lisp.

Reading On Lisp now after working through parts of SICP and doing a few small practice projects, I can finally understand what it’s saying. It’s really satisfying to finally “get” what Paul says about closures. Here’s a brief summary of the points about closures he covers:

* Closures emerge from lexical scoping. (Lexical scoping forces the system to save copies of variables when functions are defined and then associate those copies with the functions.)

* Example 1: Create a function that uses a lambda function that references one of the original arguments. (Make an implicit “function factory”.)

* Example 2: Define two functions that share the same counter variable. (Eliminate the need for messy global variables.)

* Example 3: Create a function that returns a customized function based on the arguments. (Make an explicit “function factory”.)

* Example 4: Alter example three so that the customized functions can change their state after they’ve been created. (Use optional arguments on a closure to allow the users to change it’s behavior later– sort of like properties on an object.)

* Example 5: Create a function that returns a group of closures that all use the same data objects.

* Example 6 (Chapter 5): Create a function that takes a function as its argument and returns a function for its value. (In the examples, we get one for Complement and another for Composition. These functions are mainly used to simplify and refactor the core Common Lisp library. SICP‘s coverage of Newton’s Method is much more exciting and as a bonus, it will help you understand the famous fast inverse sqrt routine.)

* Example 7 (Chapter 6): Elegance and speed with closures: Instead of defining a data structure and then defining a set of functions to access it, you can define a “smart” data structure by using closures that keep their own state and reference other closures. The line between code and data can be further blurred here by writing routines to compile your closure-based data structures. “In Lisp we can sometimes use closures as a representation. Within a closure, variable bindings can store information, and can also play the role that pointers play in constructing complex data structures. By making a group of closures which share bindings, or can refer to one another, we can create hybrid objects which combine the advantages of data structures and programs.” (On Lisp, p 76.)

Looking at these examples together, it becomes clear that a typical OOP style emphasizes a top-down approach, while closures encourage a more finely grained bottom-up style. Keep in mind that the examples of closures here are not the final iterations that Graham wants you to take away from the book. In later sections he will improve the code using macros to increase the efficiency and generality of the samples.

Still Average After All These Years

December 14, 2007

I got the chance to browse one of those mega-sized book stores the other day. I walk in with a chip on my shoulder, daring the place to have a game or a book or a magazine that catches my interest. I just find myself drifting further and further out of the mainstream as “normal” and “regular” things pale in the face of my own private obsessions. The computer book section had shrunk since my last visit. It’s like its slowly dawning on the owners that they don’t make enough money selling them to cover the costs of having to put obsoleted editions into the dumpster every couple of years. I used to could spend hours browsing the shelves, but things look strangely mundane now. Then my eyes rest on a fat shiny Apress book on Ruby.

I want that book. I want everyone to go away and I want a weekend where I can just sit and read it cover to cover. But I don’t have a single project that I need Ruby for. I don’t even really want to make a project in Ruby. I want to know what Matz did and why. I want to get the gist of it so I can understand blog posts by people that write in Ruby for no other reason than that I like those guys and feel like they care about the same things that I care about.

It’s crazy, of course. Lisp deserves at least another six months of attention and experimentation. Just the other day I was thinking that it deserved three years: one for Common Lisp, one for Scheme, and one for elisp. I was even dreading the thought of picking another language for the whole “learn one language a year” thing. Never mind the fact that I’m already procrastinating my SICP problems. Why do I want that Ruby book all of a sudden?

Ah but my head is swimming with ideas. What I really want is to apply them in a creative way to make something cool. It’s time for a pet project… but what to do?

A scan of the job boards confirms my suspicions. Lots of C# jobs sprinkled here and there. Tons of them to choose from down in the big city. But only a couple of Ruby jobs for the entire state– and no Lisp jobs. Am I wasting time? Should I hedge my bets? On the one hand I should accept the fact that the inertia of my previous work experience means I should settle for a C# job. The postings for the offbeat stuff all want super-geniuses or something. I’m just an “average” developer. And besides, if I go with C#, I can have more options in terms of where I live and what kind of environment I have to work in… right? Or have I turned a corner now that I can’t go back on? Which is it?

It’s too big a question. I need a pet project so I can explore these issues and test them in code. Talk is cheap. Code is the only real test of the ideas. Or rather, working applications, to be even more specific….

But I know how these projects work for me. I start with a sense of elation: new tools open up a door to solve a problem I’ve always wanted to solve. It looks so easy. I charge in and make inspiring amounts of progress in the beginning. Then I start to come up against the limitations of my abstractions. The pressure to get some semblance of working code is so great that I push things as hard as I can anyway… but then the muck starts to creep in. Code that looked brilliant one week becomes an embarrassment the next. And then there’s the unanticipated hard problem that saps my will to continue.

It’s like that every time. My mental vocabulary increases from one project to the next– but even powerful “new” abstractions have their limitations and blind spots so I’m always having to learn more. And while a “hard” problem that stopped me in my tracks years ago is no longer that big of a deal, there’s always more ready to come along because the scope of my ambitions is always rising faster than the rate at which I master new ideas.

In other words, there’s only trivial problems… and ones I can’t do. There are trivial abstractions… and ones that I can’t even imagine a need for. So no matter how good I get, I still feel like an “average developer”. The things I’ve mastered seem trivial– only an idiot would fail to understand them. And it’s those unanticipated problems– the ones that I least suspect– that are going to force me to expand my scope of what I consider to be trivial. But I’ll assume the tools to solve those problems are irrelevant ivory tower academic garbage until I find myself in a situation where they are the only way to get out of an ugly coding nightmare.

But when I’m in the nightmare, I won’t necessarily know what tool I need to master to get out of it. I might not even know what I need to google for! If that’s the case, then the only way forward is to work on projects that are more on my level so that I can expand my imagination to the point where I’m able to even ask the right questions. (This is why the line between doing and talking in programming is so difficult to pin down.)

Anyways… I’ve got two ideas for pet projects.

One is a Common Lisp non-application application to solve problem that’s not really a problem… but really is just a piece of problem for a lot of only marginally related problems. I’ve solved enough “hard problems” for it at this point that it should be trivial to make a single-case solution (especially if I munge just a little bit from Peter Seibel’s code examples.) The challenge would be to take that single case… and then write a few macros that are capable of generating all of that code. I’d end up with a language for solving a certain class of problems… and an application that cheats by using the REPL prompt as the primary user interface for using it. (In the process of writing it, I’ll surely end up accidentally writing my own version of some existing Common Lisp feature.  I do it every time I write in Lisp.) The resulting solution will look silly to any expert Lisp user and advocates of other programming languages will tell me how they can do the same thing using some other tool.

The other is a C# application that I was working on last year. I’d solved enough “hard problems” to convince myself that I could take it on, but got stalled by an unanticipated “hard problem” that wasn’t compelling enough for me to want to tackle on my own. The project was written as a single-case solution. What I want to do is vivisect it until it becomes a tool for solving the general-case solution. I want to use every single functional technique I learned this year to get the abstractions right this time and eliminate the muck that had crept into my bloated object model. I want to write my own scripting language for it so that it’s possible for people to do unanticipated things with my solution. Success would be a working application that ends up being used by anyone other than me. (Unbelievable success would be that my solution is used by someone else to solve the “hard problem” that killed the project the year before—not at the code level, but at the meta level!)

Which one should I choose? Or should I do something else? What do you think?

If You Want to Understand C#, Then Don’t Waste Time Studying C#: Delegates vs Interfaces in a Nonfunctional World

December 7, 2007

“The new features being introduced like closure, continuation (yes, yes very limited continuation) in C#2.0 and now type inference, lambda expressions are de-generating the language. Even though there are people go gaga about continuation and lexical closures these are fundamentally functional language features and should be left to that. Introduction of bits and pieces of functional language features are not going to add value to C# and at the same time the surface area of C# is growing beyond what most developer can grasp.” — Abhinaba

“There are plenty of people who realize that learning LISP will make them incrementally better programmers, but that they may have done the calculus, and the the intellectual capacity might be better spent focused on the problem domain.” — Anonymous

So I installed Visual C# 2008 Express Edition to check out the new C# 3.0 features. The installation failed a couple of times and I went to check the Windows Updates to see if I was missing anything. A few random security updates and a whimsical installation of IE7 and several reboots later, I discover a service pack for .Net Framework 2.0 that has a note on it saying that its required if you want to install the .Net Framework 3.5. (Let’s see… .Net Framework 3.0 was not a replacement framework like you’d think it should have been… so thinking that 3.5 would just magically work on its on is silly because 3.0 wasn’t really a 3.0, it was really a 2.5… so maybe 3.5 isn’t really a 3.5; it’s really more of a 2.75… and that’s why I need service packs for 2.0. Maybe. How could I have been so stupid as to think that the installation would just work?!)

Alright… let’s see…. A good while back, I was looking for a C# job and came across a lead that sounded too good to be true. Several phone interviews later, I discover that it wasn’t really a job, but an extremely expensive training program that could “almost certainly” guarantee me a job when I completed it. The flirty sales rep almost had me convinced to sign the papers to take out a loan. I had the print-outs from Sallie Mae and everything. They sounded really smart to me. People that got their training just went out and changed the world. As I was just about to close the deal, I asked my last question. “Will I understand delegates if I take your course?”

I didn’t really get a clear answer on that one, so I hesitated….

Crazy, huh? I’d read an article about them and, yeah, maybe I could imitate the code and create a silly example… but I just couldn’t see the implications of that language feature. Why should it be so useful? I thought I understood Object Oriented Programming and the whole concept of a Delegate just seemed so foreign. I couldn’t see the point, but I was sure my confusion was an indication that I was in the presence of some deep magic from the dawn of time. I was willing to pay a great deal to be initiated into those mysteries. I had to know.

Fortunately, I found a paying gig before I parted with the loads of cash that it would have required to take that course from those opportunistic ruffians that seemed to want to prey upon naive people that have dreams of becoming professional developers. The thing is, it just doesn’t take a lot of know-how to keep up with the demands of life as a small-time maintenance programmer. The so-called .Net Framework 3.0 came out, and the subsequent marketing blitz failed to get me enamored. It just seemed like a bunch of solutions to problems I didn’t have. I grew enraged at the clunky performance of Visual Studio 2005 and SQL Server 2005 on my piddly little laptop. Service packs and glitzy refactoring tools did little to rekindle my faith in the great high priests at Redmond. I began tinkering with a strange language called Lisp and bizarre text editor called Emacs with every spare moment I could find.

I didn’t get very far at first, but it was really fun to play with it. A lot of people in those circles were talking about some crusty old book called Structure and Interpretation of Computer Programs. Somehow I got convinced to start working through it. I didn’t have to take out a loan or anything. There were even some cool lectures from the eighties to go with them. Many, many hours later, I finally began to get answers to those unanswered questions from the years before: the Delegate was a foreign concept borrowed from other traditions of programming where procedures were first class objects– they could be passed as arguments, stored as variables, anything…. In it’s original habitat, the first-class procedures were very cleanly expressed. When they were imported into C# land, the local instantiaton and declaration rituals required a little more work to set up the same idea. (I personally think that extra verbosity makes it harder to see the point, but that’s just me.)

So assuming you’re comfortable with objects, what exactly are delegates for? They make composition of functionality much easier. Imagine an object with several complex methods that inter-relate. You could set up several properties that could take delegates as their arguments. Suddenly you have everything you need to set up an event architecture. The same class is running everywhere, but each instantiation can be adapted to specific situations with the delegates. Whenever the methods are called and events need to be triggered, the object’s delegates essentially supply pointers to the code it needs to run. And unlike that crappy event code in your goofy Access application, you can reconfigure your events at runtime. This opens up a new level of configurability that can be a big help in setting up your core application architecture or when you need things to be set up slightly different for your test harness or if you want to have different types of output behavior in different situations.

But didn’t we have everything we need with classes and interfaces? Why do delegates have to come onto the scene and crash our object oriented party? Well it does come down to how much configurability you’re going to need. If you’ve got classes that are all going to need their own custom implementation of a method, then interfaces are probably going to be the way to go. But if you can look beyond the noise and see a common theme to all of those classes, you may be able to abstract out the core logic and use delegate functions to initialize the classes. Or you can do both and wire everything under the hood with delegates, and still have a nice complicated object model that makes it look like you’ve contributed a lot to the project. But the way C# is developing, it’s coming down more to a question of how much you like to type. The original syntax for defining delegates was almost as verbose as defining an interface and a class. Anonymous functions cut back on the required number of lines of code, but were a little bit clunky looking. The current iteration with Lambda Expressions is so clean and simple, that it’s hard not to like it. Why use several lines of code and as many curly braces to say what can be done with a single curly-brace free line of beauty?

Here’s some C# 3.0 code to compare several ways to do the same basic thing. (I’ve adapted some of it from Eric White’s post on this topic.) Judge for yourself which is better:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GoFunctional {
  class TestApp {
    //Why can't this be declared in the Main method?
    private delegate int ChangeInt(int arg);

    static void Main(string[] args) {
      DoubleIt dbit = new DoubleIt();
      Console.WriteLine("{0}", dbit.OperateOnInt(5));

      //Standard Delegate
      ChangeInt myDelegate = new ChangeInt(TripleIt);
      Console.WriteLine("{0}", myDelegate(5));

      //Standard Delegate w/out "new"
      ChangeInt myOtherDelegate = TripleIt;
      Console.WriteLine("{0}", myOtherDelegate(5));

      //Anonymous Method
      myDelegate = new ChangeInt(delegate(int arg){ return arg * 4; } );
      Console.WriteLine("{0}", myDelegate(5));

      //Lambda Expression
      myDelegate = arg => arg * 5;
      Console.WriteLine("{0}", myDelegate(5));

    static public int TripleIt(int arg) {
      return arg * 3;

  interface iIntMethod {
    int OperateOnInt(int arg);

  class DoubleIt : iIntMethod {
    public int OperateOnInt(int arg) {
      return arg * 2;

Crouching Euler, Hidden Closure

November 16, 2007

The Hacking Hat has been delving into Project Euler and I had to see what I could do with it– just to gauge whether or not SICP and Dominus are doing me any good.

My first attempt, I just read the problem and tried not to look at where the Hat was going with it:

(defun square (n) 
  (* n n))       

(defun sum-first-n-squares (n) 
  (cond ((< n 1) 0) 
        (t (+ (square n) 
              (sum-first-n-squares (1- n))))))       

(defun problem-6a () 
  (let ((x (sum-first-n-squares 100))) 
    (- (square x) x)))

I used a simple recursive function to do the job… but because I was just doing one quick problem, I didn’t even think of applying any functional techniques.

I love lists, though. They are just so handy and easy to deal with. They also force the computer to “show its work” at each step of the process. Besides, we might want to make a list of the first n cubes or something and then do several things with it.

(defun first-n-fns (n fn) 
  (cond ((< n 1) '()) 
        (t (cons (funcall fn n) 
              (first-n-fns (1- n) fn)))))       

(defun problem-6b () 
  (let ((x (apply #'+ (first-n-fns 100 #'square)))) 
    (- (square x) x)))

The problem with this approach is that there’s a limit to how many arguments the plus function can stand. I couldn’t get mine to take too much more than a couple of thousand. For the next attempt, I tried making an iterative function that took two functions for arguments– the transformation function to be applied to each number in the series and the operation to be applied to the entire list:

(defun operate-on-series (operation from to transformation initial-value) 
  (if (> from to) 
      (operate-on-series operation 
                         (1+ from) 
                         (funcall operation 
                                  (funcall transformation 

(defun problem-6c () 
  (let ((x (operate-on-series #'+ 1 100 #'square 0))) 
    (- (square x) x)))

Just for grins, I decided to implement the exact same thing, but using a closure this time to make an iterator:

(defun make-iterator (from to transformation) 
  (let ((n (1- from))) 
    (lambda () (if (>= n to) 
                    (progn (setf n (1+ n)) 
                           (funcall transformation 

(defun operate-on-iterator (op iterator &optional (initial 0)) 
  (let ((x (funcall iterator))) 
    (if (null x) 
        (operate-on-iterator op 
                             (funcall op initial x)))))       

(defun problem-6d () 
  (let ((x (operate-on-iterator #'+ (make-iterator 1 100 #'square)))) 
    (- (square x) x)))

Surprisingly, the final version using the closure seemed to be the most powerful. I couldn’t get any of the other versions to take near as large numbers. Then I realized that this was because the closure was a compiled function and the rest weren’t, so I used the compile-file function to make a .fas file. I loaded that one up and found that the straight iterative solution was actually superior to the closure/iterator version:

CL-USER> (time (operate-on-series #’+ 1 10000000 #’square 0))
Real time: 8.063119 sec.
Run time: 7.8125 sec.
Space: 347655180 Bytes
GC: 663, GC time: 2.796875 sec.


CL-USER> (time (operate-on-iterator #’+ (make-iterator 1 10000000 #’square)))
Real time: 10.516433 sec.
Run time: 9.78125 sec.
Space: 347655236 Bytes
GC: 663, GC time: 2.75 sec.


Interesting results… but I’m sure that denizens of the world-wide SICP study network could offer up ideas for further improvements….

UPDATE: I of course made an incorrect assumption in reading the problem. After seeing the example on the Euler site, I understand what they were really looking for. Of course… it’s easy to modify my code to give the correct answer in the functional designs:

(defun problem-6b () 
  (- (square (apply #'+ (first-n-fns 100 #'identity))) 
     (apply #'+ (first-n-fns 100 #'square)))) 

(defun problem-6c () 
  (- (square (operate-on-series #'+ 1 100 #'identity 0)) 
     (operate-on-series #'+ 1 100 #'square 0))) 

(defun problem-6d () 
  (- (square (operate-on-iterator #'+ (make-iterator 1 100 #'identity))) 
     (operate-on-iterator #'+ (make-iterator 1 100 #'square))))

Lisp at Work: Evidence Based Scheduling

November 13, 2007

When I heard about this I was immediately excited: Evidence Based Scheduling is a technique that sheds light on what’s going on with missed target dates and helps identify the true cost of scope creep. I’d thought about Monte Carlo methods before, but most of the time I used it as a sort of mental substitute for doing real mathematics– at best, I thought, they could be used to help check your work. But this tool from Joel Spolsky was a good example where the Monte Carlo was actually the right answer! Very neat. Not something you can explain to regular people in five minutes, but if you can get the to-do list broken down into small enough chunks (and get people to track their time) then you have the potential to do some interesting forecasting.

Implementing a quick and dirty version of this system would be something I could do in just a few hours back in my old programming language. How long would it take to thrash it out with Common Lisp? If you’d asked me before I started this one, I would have said it should take twice as long. I’d have been thinking it would take me three times as long, but I would have said, two. (Typical developer….) Let’s take a look at how I solved the problem with my current Lisp skill set and see if we discover anything that will help us in our future Lisp hacking efforts.

The first thing I had to set up was some basic functions for working with dates. In a modern IDE driven Blub language, this is the sort of thing a developer would just pick up from the intellisense dropdown. With Common Lisp, this is going to take a moment reading through The Common Lisp Cookbook.

CL-USER> (mmddyy 12 1 7)
CL-USER> (getmmddyy 3405474000)
(12 1 7)
CL-USER> (datenum-day-of-week 3405474000)

With that out of the way, I needed some way to set up my basic task and developer objects. On a whim, I decided to use macros for this just to practice. Because the macro is defining new global variables for me to store each new hash in, I can just type the name of a developer or task in at the REPL prompt and see what’s going on with it– that can be a big help in debugging or just browsing the data structure. But writing even simple macros like this can take a little more time than it would to write a similar function.

With some test data set up with my macros, I can now use my new-found functional programming powers to operate on it. Here’s a function that accepts a predicate function as an argument:

(defun from-to-datenums-if (start-datenum end-datenum p &optional (n 0)) 
  "Return a list of date numbers from a specific range 
excluding ones that fail to pass the predicate function." 
  (let ((datenum (+ start-datenum (* n *day-length*)))) 
    (cond ((> datenum end-datenum) '()) 
          ((funcall p datenum) (cons datenum 
                                     (from-to-datenums-if start-datenum 
                                                          (+ n 1)))) 
          (t (from-to-datenums-if start-datenum 
                                  (+ n 1))))))

With it, I could now write functions to determine the total number of working hours that a developer can expect to work during a given time period– taking into account half-days, days off, and weekends:

CL-USER> (working-datenums bob (mmddyy 12 1 7) (mmddyy 12 31 7))
(3405646800 3405906000 3405992400 3406251600 3406338000 3406424400 3406510800
3406597200 3406856400 3406942800 3407029200 3407115600 3407202000 3407461200
3407547600 3407634000 3407720400 3407806800 3408066000)
CL-USER> (mapcar #’getmmddyy *)
((12 3 7) (12 6 7) (12 7 7) (12 10 7) (12 11 7) (12 12 7) (12 13 7) (12 14 7)
(12 17 7) (12 18 7) (12 19 7) (12 20 7) (12 21 7) (12 24 7) (12 25 7)
(12 26 7) (12 27 7) (12 28 7) (12 31 7))
CL-USER> (total-working-hours bob (mmddyy 12 1 7) (mmddyy 12 31 7))

The core idea of Evidence Based Scheduling is to get a list of values that represent how accurate a developer’s estimates are. The cool thing about it is that if random distractions come up, a developer can just charge the time of such interruptions against whatever task he’s been working on. We’ll know how often such events occur, on average, and can use that information to determine our chances of hitting a specific release date. Here we set the ratings for all of the developers and then check out the results for our simplistic test data:

CL-USER> (set-ratings)
CL-USER> (gethash ‘rating bob)
(5/4 0.39130434 3/5)

Now, using that “evidence,” we’ll run 100 simulations. Each time, we’ll cycle through the tasks on our to-do list and pull a random value from the associated developer’s rating list. Using that as a factor, we can get a guess as to how long each task will take in the simulation. Simply track the number of simulations that are finished before the time was up to get a percentage chance of finishing the project on time:

(monte-carlo (mmddyy 12 1 7) (mmddyy 12 31 7))
Chance of success: 34

(Note that the Common Lisp: the Language index has typically been the quickest way to find the names of functions I need to know. Ansi Common Lisp sometimes works as the next best thing to an O’reilly book, but in both cases I don’t always get enough information to just take a built-in function and apply it correctly.)

So, how did the project go? Time spent working in Emacs seems to have been pretty rewarding. Even with the learning curve, I could get things done in about the same time as I would with other techniques. That was a real win: I was getting my work done and learning valuable skills at the same time. Tasks that would otherwise have been tedious were injected with some interesting intellectual challenges. But this project…? I’d said it probably take me twice as long as my old language… but the factor for working it through in Lisp was more like 5 or 6 times as long.

Where did the time go? I did write a few functions that would have probably been built-in to other languages’ libraries. To get used to playing with Lisp date numbers, I wasted time writing functions that I wouldn’t end up using. I wasted time writing some cutesy macros when more straight-forward functions would have done the job. I built a new data-structure when one that I’d already written would probably have been sufficient to the task and allowed me to think at a higher level abstraction. The syntax for talking to hash tables got unnecessarily cumbersome– I should probably have used a read macro to make that more expressive and just stick to that from now on even though my code won’t be “vanilla” Lisp anymore as a result.

Two other issues were probably significant as well. Programming in a clean functional style requires thought. And the closer I got to finishing the problem, the harder I had to think and the more I had to keep in my head at once. Somehow, I don’t remember having to think so hard while writing mediocre database code. It may be that I’m still getting used to new ideas and tools, but at each step of working on the problem I worry about whether or not I’m doing things the “right way.” And because of the inherent power of Lisp, I can to steps to address any perceived deficiency. You’re not going to let that power sit there and just ignore it! Even after solving the problem, I still want to spent an additional chunk of time equivalent to what it took just to get to this point to really sit down and find the “right answer.” That kind of effort is next to worthless in most corporate shops where it’s hard to justify unit tests or even basic refactoring. No wonder Lisp doesn’t win in the “real world.”

I was much worse at guessing how long it would take to do something in Lisp than I’d imagined I’d be. Working SICP problems is far from being the kind problem solving you typically use in the “real world” when you just need to get something done. On the other hand, I’ve got a small wish-list of things I want that would make me faster Lisp hacker. (I want, for instance, something for working magic with relational data.) If I could get the multiplier from x6 down to x2, I could justify using it more often even when I’m under pressure.

Anyways, this code file shows what I wrote for this. If you’re trying to thrash something out, you might find something useful there to help you jump start a quick-and-dirty skunkworks project. There’s a lot of room for improvement there, so as you read your Lisp texts you might keep your eye out for tricks that could have been used to cut the program length in half or make it more expressive…. I’ll do the same and post a revised version if I get around to it…. (If you’re stuck coming up with ideas for Common Lisp projects to practice on, you can always just take this one and try to add a few more features to it– that might be easier than opening up a blank file to stare at. As a bonus, you get something you can actually use at your day job to manage projects.)

How Studying SICP Made Me a Better Programmer, part II

October 27, 2007

Okay, I told “Jon” that I would follow this up, so here goes.

The problem I had with the code last time was that I was leaning too much on bad habits I developed staring at too much relational database code. I used a hash table to store everything about the data structures. In all my functions for manipulating the data, I had to tag the arguments with an additional reference to to the hash. This was pointlessly cumbersome. What I really needed to do was eliminate my dependency on a data store and just use cons, car, and cdr to construct everything. This allows me to treat my data structures (and pieces of my data structures) as primitives in a linguistic abstraction layer. As a bonus, all of the standard common lisp operators work with them without any “crutches” or extraneous code getting in the way.

One thing I learned going down this road is that the Visitor Pattern is hardly anything more than an application of mapcar. I remember trying to learn about Design Patterns a few years ago and I just couldn’t pick many of them up. The code examples for them and the UML diagrams seem to me to do a good job of obfuscating the whole point. Your brain has to “compile” so much information just to get to the point– its no wonder so many developers mangle them up in the application of them. After reading SICP, it’s much easier to parse them. In a lot of cases they just do things that are very similar to what I want to do in my more functional language anyway.

Another thing I picked up in this exercise was that dynamic variables and hash tables store references to the “conses”. This means you have a lot of control over the lists that are stored in them. It also means that I don’t have to work too hard to write code to manipulate or transform them. Life certainly gets easier coding in Lisp once you think in terms of “pairs” so fluently that they are more natural than anything else. The example code for this post demonstrates some implications of this in detail, so folks that are just beginning their studies with Lisp will want to take note of what’s going on there when we start doing the “forbidden” destructive operations….  (The output of the Common Lisp code should look like this.)

Finally, after having slogged through most of the first two chapters of SICP, I can finally understand much better how bad a developer I’ve been. On the one hand, I can comprehend a much wider range of architectural approaches… but as a consequence it’s sinking in more and more just how limited my mental programming vocabulary was up until now. I really had no clue how ignorant I was. I knew I was struggling with things that should have had tidier answers, but I really thought I could only ever get just a little bit better than what I was. Now I can sense all those several orders of magnitudes that I have to go and I wish I could consume a dozen more books before going on to the next project– but life and learning don’t work quite like that….

The main thing is that I now see that I never really understood OOP near as well as I thought that I did. A lot of people objected to the recent Golf ball example that a Perl hacker recently used to criticize typical object oriented “design,” but that guy sure had me pegged. Of course, good OOP design is going to be almost indistinguishable from functional programming approaches in some cases– even if it’s a little more verbose– but I don’t think I would ever have understood that so well without my many hours spent with Lisp and SICP.

What You Don’t Know About Closures Can Hurt You

October 25, 2007

Some of you out there may still be wondering why it is that closures and macros are so great. “What exactly can you do with them that I can’t do in my more widely used Turing-complete language,” you ask. That’s reasonable. Well, I don’t think you’ll fully appreciate closures until you grasp some of the basics of functional programming, so let’s start there.

Functional programming languages accord a first-class status to procedures:

* They may be named by variables.
* They may be passed as arguments to procedures.
* They may be returned as the results of procedures.
* They may be included in data structures.

In other words, you can treat procedures as primitives. In the same way that you operate on integers, juggle them, shuffle them, combine them, transform lists of them, do anything you want with them… a functional programmer does the exact same thing with procedures.

Now if you’ve never thought much about this or experimented with these ideas, this will sound bizarre. You might have a hard time imagining how this can possibly be so useful. The only way I can think of to describe it is to imagine that you lived in a world where there was no such thing as subroutines, yet– and then suddenly some experimental language came out that had that feature. People would not admit that it was particularly useful and they would point to their terrible hacks and workarounds as evidence that such “ivory tower” concepts were useless in the Real World. Of course, you’ve seen almost the exact same thing in your workplace already, more than likely. When you see code repeated across the code base and you abstract it out into a class that is referenced by multiple projects, suddenly your coworkers are peeved at you because they can’t understand a section of code that they’re looking at without hitting “right-click — Definition” to jump to your new class file. This is why the default code architecture for a crummy business app is to open up a hundred separate form files and freely mix, match, and repeat business logic, data access code, and gui instructions all together. It’s a wonder that these guys even use subroutines…. (Oh wait, you see that, too: gigantic subs that go on for screen after screen that you can’t understand….)

Anyways, when you get procedures being treated as first-class citizens of the language, new abstractions are possible. You can create procedures that take procedures as an argument and that return procedures as a value. This means you can take several similar functions and abstract out the basic process that they all share. The procedures that you use as arguments can be used customize as many other procedures as you like. So on the one hand, you get code reuse via the basic “skeleton” procedures… and on the other, you get opportunities to reuse the code that is being used to customize the “skeletons.” Anonymous functions can be used to in-line the customizations when they’re not going to be reused, so you end up with cleaner, more expressive code.

Before I looked much into it, functional programming sounded like a step backward. I thought that the whole idea of separating code and data out and encapsulating it into classes was the answer to everything. Of course, you don’t have to give up on classes altogether. You can use functional style techniques to expand the configurability of your objects. In some cases this might be a more appropriate choice than inheritance, for example.

Now, one thing I’ve noticed with my OOP designs is that I end up spending a lot of time tinkering with my interfaces. It seems like I spend more time fiddling with the properties and methods lists and avoiding breaking the Law of Demeter than I do actually working on real code. And then I go back and break apart classes and rework the object model some more. With first class procedures, you can often skip the tedious object instantiation ritual and the maintenance of a separate class file and just jump right to what you’re trying to do. And if you can apply your procedure to a wide variety of data structures, so much the better.

Along into this scene arrives the closure. Again, if you aren’t jumping up and down with excitement for what first class procedures can do for you, you won’t really appreciate what closures add in to the mix. A closure is just a procedure that carries an environment with it. It’s like a class that has just one method and as many private variables as you’d want to cram into it. If you’re entrenched in an OOP mindset, you might think that’s ridiculous– you can make such things in your current language, you think to yourself. But this is one of those cases where less is more… and when mixed with other functional techniques you get some powerful options at your disposal.

So a closure turns out to be just a procedure with state. It’s sort of like an extremely stripped down object. The first thing people tend to show off when they’re going over closures is how you can add a counter to a procedure. Not very exciting, eh? But yeah, you can actually use that simple counter to package all kinds of logging and diagnostic functionality with your procedures. You can make a procedure that takes a procedure as an argument and returns that exact same function with your diagnostic code bolted onto the inside of it. The rest of your code doesn’t care if you’re using the plain vanilla procedure or the one with the extra logging utilities running with it.

Another thing that attaching a counter to a procedure makes possible is the creation of iterators. You might have seen an article recently that talked about how one of these days you just might write your last for loop. This, my friends, is how you get rid of for loops: you write a procedure that takes a procedure and an integer as arguments and returns a closure as its value. Each time you call the procedure, the counter gets incremented and it returns the next value from the procedure. When the counter reaches the same value as the integer argument, the closure returns a null value. Then what you need is a means of applying your other procedures to the values that are kicked out of your iterators– and with that you are now set free from the tedium of cryptic for-next loop code.

Now you may be thinking that there’s nothing wrong with your trusty for-next loop. And if you’re an OOPy type of person, you might think that your for-each loop does the job just fine. But how would you say “for each prime number from 200 to 300, execute the following function with that number as an argument.” Functional programming gives you a very expressive way to code exactly that. Another situation where iterators are useful is where you’re working with infinite lists or loops that repeat back on themselves. You might not be able to store an entire list of objects in a collection all at once– but with iterators you can simulate that very thing. You probably already use something very similar to an iterator when you open up a text file and operate on it on a line by line basis.

It occurs to me as I write this, that there was a time when I’d write “do while not rs.eof” at least a dozen times a day. I’d crash my IDE at least once every week or so because I forgot to put in “rs.movenext” at the back end of loop. That redundant code peppered throughout the application was a major liability– especially when we ended up having to move to a different data access paradigm. Oh the pain! What we needed was an iterator that could be instantiated with a SQL string. Then we could have written procedures to operate on those iterators. No more annoying do-loops! As a special bonus, if we had been writing unit tests back then, we could have made dummy iterators that don’t even call a live database– they just ould have pulled in a stream of test data instead!

There’s a lot more we could delve into on this topic, but the point is that with even just a smidgen of functional programming techniques, we could have made our code much more concise. We would have had additional means of separating out redundant code, and it would have been much easier to “rewire” the code to change its behavior.

Now, I mentioned briefly already that in functional programming we’ll strive for making our procedures able to operate on a wide range of data structures. It turns out that the key to making your functions really powerful in a wide range of situations is to use recursion. In your Imperative/OOP world, you may have only used recursion in a few rare cases– like searching through directories or setting up a tree view. Well, in functional programming, the default approach to just about everything is to use recursion. Your data structures are often defined recursively, so your functions that operate on them are consequently recursive as well. Recursion becomes your meat and drink and even the air that you breath… and you become intimate with every variety of it.

And just as closures are always introduced with a lame “counter” example, so recursion is introduced with fibonacci numbers. This is a really good bad example, because it shows not only how recursion can be the easiest way to express something, but also that recursion can spin dangerously out of control if it is mishandled.

Anyways, as you study recursion, it often takes a lot of trial and error to get it right. You test your function with several arguments to make sure it’s coming out right. You add in code to print stuff out so that you can get a feel for what’s going on. You take out the text code when you think you’re done and you put it back in when you find a new problem you need to fix. There has to be a better way. Wouldn’t it be great if we could write code to help us write code? Sounds like a job for a macro!

What we’ve got for show and tell in today’s code example is a tool called memoization. When you memoize a procedure, you create a closure that contains the procedure and a hashtable to go with it. Each time you call it, the closure checks to see if the argument is already in the hash table. If it is, it returns what’s in the hash table instead of running the potentially time consuming code to determine the value in the usual way. If the argument is in the hashtable, the closure finds the value using your procedure and then stores it in the hash table. In the case of the typical fibonacci function, this results in a dramatic performance increase.

Looking at the code, we have two defuns, a defmacro, and a macro call. The testing-memoize function takes a function as an argument and returns a closure. The print statements we use to show us what our recursive function is doing are here. We also added a “back door” to allow us access to the hash table that is attached to the function. The other function, tree-substitutes, is a recursive function that searches a hierarchical list for a specific symbol and splices in a list of things in its place. The macro takes the same arguments as a defun, but sets up a parameter to hold the closure, defines the a slightly modified version of the function using the tree-substitutes function, stores the closure in the parameter, and then redefines the function to call the closure instead. Finally, we have an example of how to apply our memoization macro with our ubiquitous fibonacci procedure.

If we like the behavior of our recursive function, we can turn off the memoization by changing “memoize” to “defun” in our procedure definition. If we like the performance gains and want to keep them, we can create our closures with a different momoization technique that doesn’t print out diagnostic text or expose a back door.

So, we can see that closures give us a means of abstracting away any extraneous or temporary behavior in our procedures. These techniques don’t replace subroutines and libraries, but they do provide an additional means of eliminating redundant code. We also see that macros can be used to set up all kinds of behind-the-scenes code by giving us a means of establishing additional ways of defining functions. We could potentially set up “testing” and “production” variants of our definition macros to radically change the behavior of our application by switching between which package we reference.

Hopefully you now have a better idea of what you can gain from studying functional programming, closures and macros. We’ve only scratched the surface, of course. If you’d like to know more, I highly recommend the classic Structure and Interpretation of Computer Programs. If you’d rather learn from a cool Perl hacker (instead of a “smug Lisp weenie”) then you might try Mark Jason Dominus’s Higher Order Perl instead.

(By the way, if you take a peek at the hash table after running the fibonacci code, it makes a pretty picture for you at the REPL prompt.)

Just Put All Monopoly Rules in the .monopoly File and Be Done With It!

October 23, 2007

(Raganwald posted a while back that implementing Monopoly was a great interview question.  I wrote this before reading his blog post– and before reading too closely about this guy’s approach in Ruby.  This problem is very similar to one that has stumped me for years… and it appears to me that Lisp and Scheme provide a very “obvious” means of separating “rules” from code while allowing for a tremendous amount of configurability.  Should this answer get me invited back for a second round, or…?  What do you think?)

Let’s start looking at this by looking at the core iterators that run the game and define state. There is an (effectively) infinite list each of die rolls, Chance cards, Community Chest Cards, players and board positions– and iterators are a great way to model the wrap-around affect of the board structure.  A typical sequence of play will be to increment the player iterator, then move increment the player’s board position a number of times equal to the result of incrementing the die roll iterator. Technically, the very concept of the sequence of play as we described it is a rule, but for now we’re going to take it as a given: we’re going to focus on implementing just the set of all “Monopoly-like” games.

To define the shape of the board, we need a means of defining variables or objects. Each one will have a Name and an arbitrary number of properties stored in a hash table. Each one will have to reference the name of the next square on the board so that the board Iterator will be able to function.

We’ll need a constructor for the player iterator that takes a list of player names as an argument.

We’re going to need a domain specific language to handle instructions on the cards and some of the board positions. The language has to be able to handle moving money to a player’s account, moving them around the board, and triggering the draw of a card. We’re going to need a means of defining new functions for the language such as “Go To Jail.” It has to be possible to implement any possible change of state in the game through the language.

So far we can configure our game with a text file that defines the squares of the board, the cards in the game, and the instructions that go with them. What we need next is a list of options for the player to choose from based on a given state of the board. Each option will have an associated script written in the same DSL that we used for the cards.

In order to allow for additional customization, we can create a set of scripts for various events that occur during our sequence of play. So our final configuration text file will include board, card, and die roll definitions… some general function definitions, some definitions for each player option that determines when each one is available and what its action is, and also some event override code. All of the rules of the game– with the exception of some fundamental sequence of play rules– are separated out into the configuration file. If, for example, someone wanted to add the atrocious game-destroying house rule of placing money in the pot for when people land on free parking, then the user would modify the award-money-from-card function and alter the trigger script for the Free Parking square.

If we allow the users to redefine the iterator definitions and the core sequence of play, then they could create even more radical customizations. At the very least, developers will want to be able to override the die roll iterator so that they could set up their unit tests to work against a set series of rolls.

Call it EMOPS or something like that….

Two Minutes Hate: “Why Functional Programming is a Pointless Dead End”

October 16, 2007

Okay, folks. Don’t forget what the Judges said: “So programmers should worry less about languages and more about good old complexity.” You can take from that the lesson that, for hard problems, raw analytical power and mathematical ability is more important than “coding skills.” But what the judges were talking about was the fact that while C programmers could get away with a slightly more “brute force” approach, a good data structure implemented in Haskell would have been fast enough to do the job as well. The issue was not so much one of language choice, but raw problem solving.

But I really don’t understand the hate that keeps emerging in this discussion. “After three years of functional programming I’m nearly out of that dark cave I’ve been living in, and back into this real world…. At least for me, functional programming seems to have been an infatuation – well worth the time spent on it but ultimately not useful.” Why the religious tone? He might say the same thing for all of those years he spent dabbling in Zen or Christianity.

I keep seeing similar “anti-testimonies” cropping up. Stuff like, “Oh I studied that in university.” Oh yeah… like going to university can make anyone an expert on programming. Others claim to have “tried” Haskell or have “looked into” functional programming. This supposedly gives them the authority to dismiss functional programming languages altogether, and maybe accuse the egg-heads of being lazy… in the “wrong” way.

Admit it guys, this is pretty shallow. I think it’s perfectly okay to pick a random church in your area, show up randomly, and decide that maybe Christianity is not for you. Just like its okay to look at a few random news items from the last years and conclude that Islam is a violent religion. Just like you can shave your head and eat vegetarian food as a Hare Krishna for a few months before getting bored with it. But while there’s not much chance of us ever (collectively) coming up with an agreed upon standard for judging the merits of the major world religions, I think we do have a means at our disposal for judging the merits of your opinion of functional programming: it’s called blogging.

Pick an off-beat language. Start studying. Attempt hard things. Write up your solution in a “show and tell” fashion. Try to become a better programmer. Then give us your opinion on whether or not you’d like to use Haskell or Lisp or whatever instead of your usual language. At least then we can have an objective way of judging your skill and depth of experience.

I don’t care about your “testimony”. It doesn’t add one whit to your credibility whatsoever. Programming is not a religion; show me your code! Tell me what’s hard for you and how you’re overcoming your limitations. If you’ve learned something cool, put it in a format where even I can understand it. Chances are that the way things are going, you’ll be able to apply the bulk of what you learn in your non-functional language anyway. But please… support your opinion with real code examples.