Reading On Lisp: Then and Now…

“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

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

Test Driven Myopia and its Remedy

“Bottom-up design is becoming more important as software grows in complexity. Programs today may have to meet specifications which are extremely complex, or even open-ended. Under such circumstances, the traditional top-down method sometimes breaks down. In its place there has evolved a style of programming quite different from what is currently taught in most computer science courses: a bottom-up style in which a program is written as a series of layers, each one acting as a sort of programming language for the one above.” (On Lisp, p v.)

“This is the approach of stratified design, the notion that a complex system should be structured as a sequence of levels that are described using a sequence of languages. Each level is constructed by combining parts that are regarded as primitive at that level, and the parts constructed at each level are used as primitives at the next level. The language used at each level of a stratified design has primitives, means of combination, and means of abstraction appropriate to that level of detail.” (SICP Section 2.2)

I spent a few hours fiddling with some C# 3.5 code recently– it was pretty jarring considering how much time I’d spent with Lisp this past while. The compile/execute/manual-test loop seems incredibly slow to me. Painstakingly slow, even. As I worked, it crossed my mind that the whole Test-Driven-Development meme was probably spawned by the fact that impoverished developers across the world were attempting to code applications without the benefit of a REPL. Yeah, the main benefit of Unit Tests is that you get control of your codebase so that you’re not afraid to refactor and improve it. But with TDD you can end up coding a lot of unnecessary tests that are just there because it’s so time consuming to interact with your code. If size is the enemy, then any unnecessary tests are going to take away valuable momentum from your project.

But the TDD advocate will surely argue back that the “real” benefit of their technique is to help you design your interfaces and object models correctly as you go– which is well worth a little extra code that mainly helps document the system. I would argue that such an approach may not be deep enough for the long term. Yes, things will be pretty in your IDE when you hit the “.” key and the IntelliSense(tm) window pops up. But the granularity of your object model may not be fine enough to allow for a really expressive and adaptable design.

An alternative (or complement) to TDD would be Language Driven Development. Don’t start with tests or object models. Start with a language. Make up an imaginary language that will handle everything you want your program to do. The main benefit of this is that you can think about the entire application at one time and see commonalities between disparate parts of the architecture. Write up lots of examples of how you would implement common tasks in the language and make sure you have the main bases covered, and then try to imagine the machinery that would be required to execute the pseudo code. Now you will be much more likely to come up with powerful abstractions because the methodology is forcing you to think in terms of at least two complementary directions. You’re working top-down when you spec out your imaginary language… and you’re working bottom-up when your define the underlying machinery. Good programming requires a person that can move deftly between both levels– and TDD alone can be dangerously myopic.

If you can identify ways of stratifying your design, you’ll need fewer unit tests in the long term. With proper abstraction barriers between the layers of your design, you won’t be as dependent on exhaustive unit tests when you want to refactor your code. Instead of a sprawling pyramid with custom tests for each brick, you could instead code tests for a smaller number of generic components at each level.

A Solution to Out-of-Control Computer Book Purchases

I really lucked up with my whole Ruby book purchase dilemma. When I went back to the store, I discovered that they actually had two Ruby books to choose from. I couldn’t decide which one to choose! Over lunch I perused the user reviews over on Amazon. It turned out that one was extremely well written, but lacked depth while the other was poorly written but covered the important stuff. Yes! Now I had a good reason not to purchase either of them!

Seriously, though, Brad Bollenbach’s advice was sort of percolating in my head. I agreed with myself not to buy another book until I had gone through at least the first ten chapters of On Lisp again, picked out ten neat tricks from PAIP chapter three, experimented with the General Problem Solver from PAIP, worked through the Huffman Encoding Trees example in SICP, finished up SICP section 2.4, and read another chapter of HOP. The quality of those four books is so great that there’s probably little chance of any of the modern $50 phone-book sized disposable computer tomes coming close to them anyway.

Still Average After All These Years

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?

Meet the New Problem… Same as the old Problem

“Investing a large amount of resources into creating a tool or language to simplify a particular problem never makes much economic sense precisely because the problems that exist today are never the problems that exist tommorow [sic].” — ocean

No. This is just completely wrong.

In the first place, I’d just like to ask why we have all of this mind numbing unceasing tech churn? Evidently there is some economic sense to this whole language/tool creation thing. I mean… even the obvious examples like Java, VB, Erlang, XML, NAnt, SubVersion, etc. should settle this. To be a software developer is to be in a constant state of assessing and evaluating tools. This is about as “mucky” a problem as they come, and where there’s muck there’s brass… so there’s an entire industry striving to meet this need.

But maybe I’m taking ocean’s remarks out of context here. Let’s blur our vision for a second and pretend that all the holy wars and competing tool sets have gone away. All we’re left with is just a typical man on the street developer trying to keep up with a huge number of change requests and bug reports. Here’s a snippet from a random job posting:

“Creating web application ordering systems for many different clients (each client has a unique ordering process) -All new development work is in C#, dozens of existing applications are in Visual Basic .NET -Candidate must be able to switch between languages without issue.”

What are we going to tell the guy that ends up with that job? “Hey, we can’t wait to have you here. We’ve got so much to do. But look man, we know we’ve got 50 web pages running here that have a lot of the same code, but don’t even think of making a code library to share between all of the projects. We tried that once and it just didn’t work.”

Are we going to look over the guy’s shoulder and randomly pipe in and say, “Hey… stop that. We decided last year that refactoring was a waste of time. Take all of those carefully named subroutines and pack them all back into one giant procedure like we had it before.”

Are we going to cry “foul” if he starts coding up a macro for his text editor?

I suppose we should fire him if he starts working up framework or a templating system to use as a basis for all of his “store” projects. And if he even toys with the idea of a human readable custom scripting language for handling certain triggers or events we should go ahead and just burn him at the stake.

Shoot, to be consistent, let’s ban OOP. A sufficiently sophisticated object model starts to look like a language anyway… let’s outlaw the use of the .Net framework as far as we can.

Okay. Alright. We’re not going to do any of that stuff. We’re not going to just randomly start banning the nuts and bolts of basic software development. Of course there’s an entire strata of developers that will never develop their own object model to solve a problem– even though they spend all day poking around in other people’s object models. There’s an even larger strata of developers that will never make up their own language to solve a problem– even though they might need to learn a dozen just to work a lame web project. But just because we aren’t comfortable with metalinguistic abstraction, it doesn’t mean we need to shoot down anybody that wants to explore its possibilities. And at some point, there were folks that had some computing problems and then wrote C and awk in order to get around them– so by definition, a new language/tool has to be the right answer sooner or later.

But if you look back at that job posting and think about it… that’s almost exactly the same problem that Paul Graham solved back in the eighties working on what became Yahoo Store. It’s ten years or more and we’ve still got pretty much the same sorts of problems. And if you’re in the business of solving a certain class of problems, you’ll want more of them, too. Why not invest in developing tools/frameworks/languages that can help you manage more problems with less effort? Why not continue investing in those tools so that you can expand the scope of the problems that you consider trivial? If you insist on working crappy development projects, you’re sure to get away with it for a time. But somewhere, someone is working on the tools that will make most of your painstakingly crafted custom solutions irrelevant. They are doing everything they can to make it easy for the people that write your paycheck to ditch you and move to their system.

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

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