Archive for the ‘LISP’ 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.

Building a Better Mapcro

December 27, 2007

Larry Clapp recently responded to my post on making a “mapcar” type routine that works with macros. I managed to make an ugly hack that got the job done, but Larry shows us a much better approach. Instead of using mapcar to force eval to get something done, he uses a macro to expand out a list of expressions in a progn operation. Notice the trick of mapcar’ing a lambda expression that kicks out back-quoted list. That technique will surely be useful in other macros, but is not something I’ve seen highlighted in any tutorials, yet:

CL-USER>  (defmacro mapcro (macro &rest args) 
           `(progn ,@(apply #'mapcar 
                            (lambda (&rest args2) 
                              `(,macro ,@args2)) 
                            args))) 
MAPCRO 
CL-USER>  (mapcro defparameter (a b c) (1 2 3)) 
C 
CL-USER>  a 
1 
CL-USER>  b 
2 
CL-USER>  c 
3 
CL-USER>  (macroexpand-1 '(mapcro defparameter (x y z) (1 2 3))) 
(PROGN (DEFPARAMETER X 1) (DEFPARAMETER Y 2) (DEFPARAMETER Z 3)) 
T

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) {
      //Interface
      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));
      Console.Read();
    }

    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;
    }
  }
}

Your macro is in my mapcar! (No! Your mapcar is in my macro!)

November 30, 2007

Macros are great. You can write code to write code. You can delay the evaluation of your arguments. You an remove all boiler plate code from your application. Yee-haw.

Mapcar is great. “Do this action to every item in this list and return a list of the actions’ return values.” For a lot of people this can be their first introduction to a function that takes a function as its argument. Woo-hoo.

Powerful stuff. You love it.

But what about the times when you want to mapcar with a macro?

CL-USER> (defun stupid (vars vals) 
           (mapcar #'defparameter vars vals)) 
STUPID 
CL-USER> (stupid '(x y z) '(43 54 65)) 
; Evaluation aborted: undefined function DEFPARAMETER

Hmmm…. This doesn’t work because defparameter’s a macro. Functions are first class citizens in the language, but macros aren’t.

Let’s start with a really silly example. We have a macro that takes a single argument… and we’ll use mapcar with a lambda function that constructs a list made up of the macro name and whatever value gets passed to it. It does that for each argument passed to it and uses eval to evaluate the resulting expression.

CL-USER> (defmacro z (var) 
           `(defparameter ,var 42)) 
Z 
CL-USER> (defun mapcro (macro &rest arguments) 
           (mapcar #'(lambda (x) 
                       (eval (list macro x))) 
                   arguments)) 
MAPCRO
CL-USER> (mapcro 'z 'a 'b 'c) 
(A B C) 
CL-USER> a 
42 
CL-USER> b 
42 
CL-USER> c 
42

Yeah, yeah. I know. “If you’re using eval then you’re doing something wrong.” There’s probably a cleaner way to do this, but I’m sure I’ve heard repeated complaints about macros not working near as good as functions. The fact that we have eval means that we can make things happen however we want regardless of how things are “supposed” to work. And if we ever get hung up on some wacky syntax issues, we can always brute force the issue in a pinch. Never mind the fact that we probably won’t get around to coming back later to clean it up!

Let’s keep tinkering with this, though. We want this to work with two variables instead of just one:

CL-USER> (defun mapcro (macro args1 args2) 
           (mapcar #'(lambda (x y) 
                       (eval (list macro x y))) 
                   args1 
                   args2)) 
MAPCRO
CL-USER> (mapcro 'defparameter '(k l m n) '(22 45 78 98)) 
(K L M N) 
CL-USER> k 
22 
CL-USER> l 
45 
CL-USER> m 
78 
CL-USER> n 
98

Okay, that’s getting somewhere…. We can use mapcar with something like defparameter now.

But what we really want is to have any number of argument lists. How do we handle that? The lambda has to know how many arguments it’s getting, right? Well… we can just use an &rest parameter and append them with the macro symbol insead of “listing” them. But if we’re passing in the argument lists via a &rest parameter to begin with, mapcar won’t know how to deal with them– it needs a set of list arguments, not a giant glob of lists!

This is complicated…. We’ll work it out at the repl prompt before rigging up the function:

CL-USER> (funcall #'mapcar
                  #'(lambda (&rest x) 
                       (eval (append (list 'defparameter) x))) 
                  '(x y z) 
                  '(55 66 77)) 
(X Y Z) 
CL-USER> x 
55 
CL-USER> y 
66 
CL-USER> z 
77

Oh wait… if I change the last arguments there to a list of lists, then it chokes! I should have used apply, not funcall:

CL-USER> (apply #'mapcar
                #'(lambda (&rest x) 
                    (eval (append (list 'defparameter) x))) 
                '((u v w) (34 53 63))) 
(U V W) 
CL-USER> u 
34 
CL-USER> v 
53 
CL-USER> w 
63

Okay… now we can fix our function to make it work for any number of arguments….

CL-USER> (defun mapcro (macro &rest args) 
           (apply #'mapcar
                  #'(lambda (&rest x) 
                      (eval (append (list macro) x))) 
                  args)) 
MAPCRO
CL-USER> (mapcro 'defparameter '(jj kk ll) '(77 87 97)) 
(JJ KK LL) 
CL-USER> jj
77 
CL-USER> kk
87 
CL-USER> ll 
97

We did it! We feel really guilty, but we did it! Party!

Oh wait… typing all of those quotes is a hassle. Just for fun, let’s rig up a macro to rearrange everything for us so we don’t have to bother with them:

CL-USER> (defmacro mapcro (macro &rest args) 
           `(apply #'mapcar
             #'(lambda (&rest x) 
                 (eval (append (list ',macro) x))) 
             ',args)) 
MAPCRO
CL-USER> (mapcro defparameter (mm nn oo pp) (63 74 85 96)) 
(MM NN OO PP) 
CL-USER> mm 
63 
CL-USER> nn
74 
CL-USER> oo
85 
CL-USER> pp 
96

Notice that macros and functions have their own namespaces. Anywhere in the code that we have a “mapcro” symbol on the far left side of an expression will trigger the macro expansion before anything else happens. We don’t have a naming conflict because we’re using apply with an explicit function reference.

(Yeah, this is probably completely evil or pointless somehow, but I wanted to do something like this a couple months ago and struggled to get something to work. It just hit me the other that that eval means I can do this even whether I’m supposed to or not….)

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) 
      initial-value 
      (operate-on-series operation 
                         (1+ from) 
                         to 
                         transformation 
                         (funcall operation 
                                  initial-value 
                                  (funcall transformation 
                                           from)))))       

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

(defun operate-on-iterator (op iterator &optional (initial 0)) 
  (let ((x (funcall iterator))) 
    (if (null x) 
        initial 
        (operate-on-iterator op 
                             iterator 
                             (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.

333333383333335000000

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.

333333383333335000000

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)
3405474000
CL-USER> (getmmddyy 3405474000)
(12 1 7)
CL-USER> (datenum-day-of-week 3405474000)
5

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 
                                                          end-datenum 
                                                          p 
                                                          (+ n 1)))) 
          (t (from-to-datenums-if start-datenum 
                                  end-datenum 
                                  p 
                                  (+ 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))
96.25

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)
NIL
CL-USER> (gethash ‘rating bob)
(5/4 0.39130434 3/5)
T

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:

CL-USER>
(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.)

By the way… Zach wins ;)

November 5, 2007

Following up on the next-power-of-two question:

It looks like Zach wins….

Lisp at Work: a macro for managing replace-regexp routines

November 5, 2007

The following commands have all become essential in my day to day Emacs usage:

C-M-% (query-replace-regexp)
C-x ESC ESC (repeat-complex-command)
M-x re-builder
C-x C-e (eval-last-sexp)

I use them to define regular expressions for use in editing text documents. Over time, I begin to collect quite a few of these, so it makes sense to think more carefully about my key bindings: normally I just use a Function key, but there’s other stuff I want to hot key from there now…. The Emacs manual says that the combination of C-c followed by a plain letter is reserved for the user, so I can put my custom routines there with a single letter mnemonic to help me remember what’s what.

Here’s a macro (with an example of its use) for setting up these sorts of text processing routines:

(defmacro defreplacer (name description search-for replace-with chord) 
  `(progn
     (defun ,name (n) 
       ,description 
       (interactive "p") 
       (query-replace-regexp ,search-for 
                             ,replace-with 
                             nil 
                             (if (and transient-mark-mode mark-active) 
                                 (region-beginning)) 
                             (if (and transient-mark-mode mark-active) 
                                 (region-end)))) 
     (global-set-key (kbd ,chord) ',name)))   

(defreplacer pull-text-from-semi-colons 
  "Remove text from between two semi-colon signs."
  "[ ]*;\\([a-z]*\\);[ ]*" ; use double back slash to 'escape' in quotes 
  "\\1"
  "C-c ;")

In the example above, we’re replacing lower case text inside a pair of semi-colons (and surrounded with any number of spaces on each side) with just the lower case text. The command chord to trigger that replace routine is “C-c ;”. This is a pointlessly simple example, but it should give you the basic idea of how to use the macro.

Does the “defmacro” really do much more for us than “defun” would otherwise do? The main savings you get with the macro is that it defines the key binding at the same time that the replacement function is defined– having a naming type there caused me a minor headache when I was wondering why my hot-keys weren’t working once. With “defmacro” you eliminate the chance of this kind of confusion occurring. On the other hand, if you change the definition of the macro after a file has been loaded, you will not change the operation of the existing functions– the macro only affects the environment at compile time. So there are trade offs either way. In this case I went with a macro because once I get my regular expression from re-builder, I wanted to be able to write the code for everything as quickly as possible. With “defreplacer”, all I needed was four arguments and I was good to go.

My Solution to the Rounding-Up-to-the-Nearst-Power-of-Two Problem

November 2, 2007

This is my solution to the dreaded Java-coder stumping round-up problem.  (Yeah, I subscribe to raganwald‘s feed and I like those del.icio.us links just fine, thank you.)

This algorithm runs in log(n) time, does it not?

***

Update (an hour or so later): Hmm… in this case, it appears to take 2 lisp programmers to solve this one…. Oh well. That’s what I get for not trying to “break” my code by testing the ambiguous cases….  The only change here is to make the ‘=’ into ‘<=’ and also to rename the local function per Zach’s suggestion:

(defun round-up (number) 
  (labels ((round-iter (n p) 
             (if (<= n (expt 2 p)) 
                 (expt 2 p) 
                 (round-iter n (+ p 1))))) 
    (round-iter number 0)))

***

Update (another hour or so later): Here’s Zach’s solution:

(defun round-up (value) 
  (cond ((zerop value) 
         1) 
        ((zerop (logand value (1- value))) 
         value) 
        (t 
         (expt 2 (integer-length value))))) ***

Update (another hour or so later): Here’s Chuck’s solution:

(defun next-power-of-2 (n) 
    (expt 2 (ceiling (/ (log n) (log 2)))))

Follow

Get every new post delivered to your Inbox.