Advanced Codemunging: A Report from the Trenches

A year ago, I began studying Lisp and Emacs. I would ultimately get through about half of SICP and code up a few small Lisp projects that mainly showed how far I was from grasping the point. Having Emacs skills did come in handy a few times, though. Engaging in such focused deliberate practice was difficult: I rarely came up with anything truly innovative or useful, but instead had to constantly face my weak areas and incompetencies– and doing all of this pretty much in public would ensure those weaknesses would become notorious among the illuminated. I wasted some time blogging about programming practices and things gradually culminated into a manifesto of sorts. While I now had enough technical know-how to address some of the biggest problems I’d faced as a career programmer writing simple database apps and web pages, I also had a minor crisis in choosing which language to implement my new vision. Circumstances at work (and a large decrease in free time to experiment in) would soon narrow my options for me, though. This blog post is about what happened next.

I got really lucky in the way things panned out in my career. You’ve probably read where Joel Spolsky was talking about how awful it is to get stuck being an in-house developer. More recently, Paul Graham has gone off on how we’re all supposed to be like the start-up coders that he funds. Really, most of us aren’t *that* talented to begin with… or at least, we’re not willing to live the start-up lifestyle or take on the associated risks. But there is another option that can be almost as satisfying as working in a Graham/Spolsky type setting: be the *only* developer in a company that’s large enough to have interesting problems and that’s looking to cut the cord with as much of their legacy software as they can as they move to a new system.

If you can land that sort of job, you’re probably savvy enough to avoid most of the stupidity that comes with dealing with corporate type development. Because you’ll be they only developer on staff, you won’t have to waste time building consensus with fearful managers and mediocre “day coders”– and face it, they would never have gone along with your insane ideas to begin with. Also, you have a huge business value bearing down on the side of good design: you’re essentially getting paid to eliminate and refactor away all of the crappy development projects that have accrued over the years. The scope of such a change is so big (and everyone else is so busy), you’ll have to come up with big architectural ideas on your own and you probably won’t even have to pitch them to anybody except the other techy type people that are in your (small) IT department. You’ll just have to make the right decisions on your own.

Looking back on the most painful moments of my career, I think I have pinpointed the cause of most of the disasters. Because I needed the experience, I allowed myself to get into positions where I had to maintain code that I had no authority over. Whether out of my own fear or by decree of my immediate manager, I was isolated from the problems I was supposed to solve. I would continually get requirements that were just enough wrong to be useless and would often spend as much time removing them as I did implementing them. The common denominator in most successful projects/modifications were in situations where I rewrote entire sections of code (with or without permission) and where I also took the time (with or without permission) to hash things out with some smart folks lower down on the totem pole– people that actually did the work and people that would end up using the application. Talking to people like that would often uncover the real problem– but then I’d have to “sell” a new solution to managers at one or more companies. I’d often spend more time talking about the issues with management than I did writing code. And its those sorts of interactions that become the fodder for an unlimited number of Dilbert strips. And because of all of the bad requirements, IT departments start to withdraw from their users and create buffers of bureaucracy to protect themselves from getting “burned.” You can let this insanity grind you down… but you can also take advantage of it if you play your cards right.

You’ve got to realize that while management types generally can tell you what to do (and sign your paycheck and stuff), they can’t really help you with the bulk of your development work. Too many of them are going to just tell what kind of buttons to put in the application. “I just need one that has ANSWERS written on it.” Right. If you can just get your foot in the door, you won’t be so dependent on them. Any sort of application that you can roll out is your ticket to finding our how things really should work. Talk to your users at all levels. “Joe Six Pack” knows a heck of a lot about the company and will not waste your time with stupid requirements. Generally speaking, no one asks his opinion: he’ll be grateful for giving him a voice and making his work easier.

Growing up as a geek, you probably played off-beat rpg’s and war games in your basement. In order to run them, you had to have the bulk of the system “in your head”. This type of thing is very similar to a company’s overall business process– and your contacts with people on the ground and your familiarity with the back end data structures will allow you get large portions of a company’s business processes “in your head” as well. (As long as there’s some room left up there what with all the AD&D stuff junking it up.) The trick is to address the process issues in a coherent way: what’s convenient for one person may not be efficient for the whole. It’s this kind of knowledge and savvy that separates you from the code-monkies. People that have a slightly smaller interest in programming will often use the position they gain from this to become de facto controllers of the company. But you’re a geek, so you’ll probably just be glad to have the chance to deal with management as an equal instead of as a flunky. That way, you can get a chance to implement the code designs of your dreams! Party!

So, once you’ve got a decent job where you have the authority to develop code effectively, how do EMACS, Lisp, and SICP impact your day to day work? The main area is in your attitude. Even if you’ve never truly mastered those tools, you end up cultivating a conviction that your program should be dynamic and malleable at all levels. Your abhorrence of repetition and bloat will be cranked up to “11″ and you’ll just have this default expectation that your code should magically respond to you no matter what you’re trying to achieve. You’ll also be exposed to enough unusual ideas that you’ll see things you can do back in “blub” that you never would have imagined. You’ll have a wider range of programming styles at your disposal, and your ability to discern various “code smells” will be much sharper.

Back on the job, I did choose a ubiquitous “blub” as the primary language. The lesson of Lisp is that it takes very little to engineer a custom programming language: just a few axioms will get you something reasonably complete in short order as long as you’re able to combine the pieces into more complex concepts. I realized that if I stole somebody else’s evaluator, I had 90% of what it took to make a dynamic language. I embedded the evaluator into an “environment” that could manage the overall state. I then wrote a small deck of crappy string functions that I used to “compile” lines of text into “code objects”. From there it was a piece of cake to write code to “execute” the objects by running a series of operations on the environment variables based on what’s specified in a list of those “code objects”. This was all done with the crappiest of quick-and-dirty programming techniques. Just awful. It didn’t take long, though. And it doesn’t have to be great. It just needs to be “good enough” for now.

Once the core of this (albeit awful) custom language is done, you’re (generally) only about two hours away from being able to implement any given language feature that you want to do. And thanks to a small familiarity with Lisp, I realized that there was a lot of slick ideas that are opened up once a programmer has gains control over what gets evaluated and *when*. Macro-like functionality became possible, among other things…. In practice though, coding a new language feature take me maybe ten times as long as it would to write a comparable function to do the same thing. There are things that can be done to cut the time off of that, and it’ll be fun to someday compare and contrast my ideas with what can already be done with List “out of the box.”

What I ended up using my roll-your-own language for was to build a scripting language for customizing my main application. When the application is run, it reads a script to set up the environment. All of the GUI is bound to the environment. Advanced users can customize 90% of the application’s functionality without recompiling– and as a bonus, I have a way to test and experiment with malfunctioning desktops without having to use the old “it works on my machine” excuse. Not quite as good as a REPL prompt, but good enough. (For now.)

Because I’m a database app developer, 80% of my code is about connecting to database X, prompting the user for some stuff, getting a deck of rows, and maybe doing something for each row in the deck. (I get so sick of seeing the same crappy DAO, ADO.Net, and stored procedure call code over and over. Blech!) It sure would be nice to have a language designed completely around doing exactly that. And the thing is… I do! My custom language has all kinds of features for manipulating blobs of text. My “environment” stores the blobs in a prominent place, and the GUI automatically picks them up, displays them, and knows how to operate them. This may sound crazy at first, but I’ve been able to come up some powerful front end features because of this approach. Features that I never would have thought up emerge naturally and give my users an unprecedented amount of functionality. Dozens of minor problems routinely get addressed all at once with relatively simple abstractions.

For the first time, I am coding against the problem at both ends. The blobs of text that represent the fundamental unit of work in my system are abstractions that I once referred to as being “hairy at both ends” after trying describe something Peter Norvig was doing in an code sample. These abstractions allow the functionality of the program to be extended gracefully– and I’m generally only a “very short time” away from being able to extend those functions for either myself on the code side or my users on the GUI side. No… for the first time, I have an architecture that acknowledges myself as being the primary “user”. Refactoring is now easier than any other alternative– and the business case for it can be made convincingly at every stage of the project. I can code features that make it easier to manage growing collections of business object blobs in my heavily syntactic sugared scripting language. New blobs are automatically picked up by the GUI… and serendipitous GUI features emerge naturally because of the consistency inherent in the abstractions. Each layer of the architecture builds on and magnifies the efforts of the underlying layers. And every line of code I write is impacted by my (admittedly mediocre) understanding of recursion and the closure property.

You see a lot out there about those supposedly super-duper type programmers that are worth ten times as much as their lesser colleagues. While I will not claim to be one of those guys, I do feel at least ten times as effective of a programmer as I was a year ago. At any rate, I love my code base, I enjoy improving it continuously, and I enjoy seeing my users immediately benefit from the wacky ideas I come up with back at my desk. For the first time in a long while, I wake up excited every morning and I actually look forward to going to work. Life is good.

Thanks John, Harold, Jay, Peter and Paul. You guys have given me answers to the core problems I face every day– even as a lowly database app developer. I may not have the privilege of being able to code in a lisp dialect professionally, but at least I can now begin to “Greenspun” with the best of them….

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.

Why Comp Sci Grads Can’t Hack (and why you need them anyway…)

When I first got started programming I was shocked by the cluelessness of some of the Comp Sci grads that trickled through as interns and entry level coders. A couple were really brilliant, but some never really got up to speed. How could it be that I, with no real training, was coding circles around these guys on the job– even with only my very small amount of experience? Well, one answer to that is that the smart Comp Sci grads were probably all somewhere else doing much more interesting work (and making more money) than what I got stuck with in doing crappy business apps. Another answer is that I was learning a single tool 24/7 and using it to accomplish the sort of things my corporate masters wanted me to do. But Computer Science classes are not vocational training for that kind of work, so don’t make the mistake of assuming that it should prepare people for it.

David Chisnell spells this out for us in a recent article:

“A lot of dissatisfaction with computer science comes from the misplaced expectation that a computer science graduate will be a good programmer. Such a graduate should have been exposed to at least half a dozen languages, but won’t necessarily have done anything particularly complicated with those languages. She almost certainly won’t have any kind of deep understanding of the standard library available for a given platform. This kind of comprehension comes only with experience. She may have picked it up from other jobs or open source work, but not from her degree.”

“Computer science and software engineering are very different disciplines, and a lot of people seem to confuse the two. Software engineering teaches the process of developing software, in terms of both tools and processes. A computer science course briefly touches on these topics, in the same way that a materials physicist may learn something of mechanical engineering. This doesn’t make a computer scientist a software engineer, any more than it makes a physicist the best candidate for building a bridge.”

For all the time and money you spend getting your degree, I sure hope you bypass the kind of creeps us “street programmers” run into when we’re first getting our start. You know… the sort of people that think the answer to everything is to waltz through the internet picking up pirated copies of somebody else’s gigantic business application…. Once you get established, you are still stuck with the terror of out-of-control development way too often. At best you’ll be stuck working with people that refuse to make tools to help them do their jobs– they’re just always under the gun. “The shoemaker’s children have no shoes,” they blithely say. Bob Warfield reiterates what’s going on in these kinds of companies:

“Many times what has happened is a company started out with a great idea and some knowledge of the domain. They built a piece of software that is a very literal embodiment of their view of the domain. So long as the whole domain and all the customers fit their view, life is good. However, for most non-trivial (i.e. interesting market size) domains, nobody knows the whole domain. You learn as you go. Customers throw curve balls. If the only way to adapt to that is to either keep adding tons of features to the software, or do expensive custom work on each deal, that’s way too much friction to scale. A domain specific language makes it possible to maneuver a bit at low cost and give customers what they want.”

There are many ways to kill projects. Easily, the number one killer is going to be scope creep. (The most depressing sort is going to be scope creep caused by management that want a completely new system and then incrementally force you to make it just like their old system.) Well… scope creep wouldn’t be that bad. It’s unanticipated shifts of scope that occur in a direction that’s orthogonal to anything you ever anticipated. Teams will implement awful hacks to keep a client happy enough to keep the money coming in. Then, boom! Their money dries up and you’re suddenly dealing with people in a different region that have subtly different industries that they focus on. And your team can’t adapt to the new needs fast enough to either swing the sale or keep them happy enough to stay with you.

There are few things more depressing than the pain of failure. One of those things is– surprisingly– the pain of success…. What do you do when you’ve got lots of clients running your software– but they’ve all got different versions and different modifications done to it? Untrained “street programmers” can get this far with luck and hard work, but they (and their companies) cannot grow beyond this point without developing tools to help them write their tools. To do that, they need some serious Computer Science know-how. And that’s the bitter irony: the hell of real world development has, on the surface, little to do with what goes on in the Computer Science classroom. But, to solve the problems we face here, we need the help of people that understand the implications of what gets taught there.

Crouching Euler, Hidden Closure

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

How Studying SICP Made Me a Better Programmer, part II

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

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.)

How Studying SICP Made Me a Better Programmer

While working through the problems of SICP section 2-2 this week, I had a flash of insight. Things that had frustrated and stymied me for years were suddenly becoming trivial. One data structures problem that had particularly bugged me had become pretty easy, too– though I had to apply everything I’d learned in SICP about recursion, first class functions, and the closure property to do it. Here’s a quick tour of my proof of concept from the REPL prompt:

CL-USER> (setf c (make-hash-table))
#S(HASH-TABLE EQL)
CL-USER> (create-widget c ‘division-a ‘mega-corp ‘(factory-1 factory-2 factory-3))
(DIVISION-A MEGA-CORP (FACTORY-3 FACTORY-2 FACTORY-1) #S(HASH-TABLE EQL))
T
CL-USER> (create-widget c ‘division-b ‘mega-corp ‘(dist-1 dist-2 dist-3 main-office))
(DIVISION-B MEGA-CORP (MAIN-OFFICE DIST-3 DIST-2 DIST-1) #S(HASH-TABLE EQL))
T

We’re starting out by defining a hash-table to store all of our work in. I guess I could have stored everything in a global variable so that I wouldn’t have to keep referencing the store all of the time, but I figured it was worth it not to have all of my functions hard coded to a particular variable. With the above code we assigned division-a and division-b to a company we like to call Mega-Corp. We created some factories, distribution centers, and a main office while we were at it.

CL-USER> (gethash ‘mega-corp c)
(MEGA-CORP NIL (DIVISION-B DIVISION-A) #S(HASH-TABLE EQL))
T
CL-USER> (gethash ‘division-a c)
(DIVISION-A MEGA-CORP (FACTORY-3 FACTORY-2 FACTORY-1) #S(HASH-TABLE EQL))
T
CL-USER> (gethash ‘factory-1 c)
(FACTORY-1 DIVISION-A NIL #S(HASH-TABLE EQL))
T

Here we take a look at what we’re actually storing in our hash table. Each item in the hash is a list in the format of (WidgetName Parent-Widget Children-Widgets-List Properties-Hash-Table). You can see above that Mega-Corp has children, but no parent. Division-a has both a parent and children. And Factory-1 has a parent but no children.

CL-USER> (create-widget c ‘office-staff-f1 ‘factory-1 ‘(bob fred joe))
(OFFICE-STAFF-F1 FACTORY-1 (JOE FRED BOB) #S(HASH-TABLE EQL))
T
CL-USER> (create-widget c ‘office-staff-d1 ‘dist-1 ‘(james mike sally bert))
(OFFICE-STAFF-D1 DIST-1 (BERT SALLY MIKE JAMES) #S(HASH-TABLE EQL))
T
CL-USER> (gethash ‘office-staff-f1 c)
(OFFICE-STAFF-F1 FACTORY-1 (JOE FRED BOB) #S(HASH-TABLE EQL))
T
CL-USER> (gethash ‘bert c)
(BERT OFFICE-STAFF-D1 NIL #S(HASH-TABLE EQL))
T

Here we extend our data structure even further by adding some office staff groups. We can extend the structure as much we want– and in principle, there’s nothing preventing us from writing procedures to copy and combine such data structures however we choose. That wide-open combinatorial possibility is what the closure property is all about.

CL-USER> (setprops c ‘(bob fred joe james mike sally bert) ‘salary ‘(40100 55050 50010 35025 33099 75042 20010))
(40100 55050 50010 35025 33099 75042 20010)
CL-USER> (setprops c ‘(factory-1 factory-2 factory-3 dist-1 dist-2 dist-3 main-office) ‘assets ‘(800000 950000 725000 225000 235000 230000 125000))
(800000 950000 725000 225000 235000 230000 125000)
CL-USER> (getprop c ‘factory-2 ‘assets)
950000
T
CL-USER> (getprop c ‘sally ‘salary)
75042
T

These functions use mapcar to set a slew of property values all at once– without having lots of repetitive code. The getprop procedure allows us to read those settings back out again.

CL-USER> (getval #’+ 0 c ‘sally ‘salary)
75042
CL-USER> (getval #’+ 0 c ‘office-staff-d1 ‘salary)
163176
CL-USER> (getval #’+ 0 c ‘office-staff-f1 ‘salary)
145160
CL-USER> (getval #’+ 0 c ‘mega-corp ‘salary)
308336
CL-USER> (getval #’+ 0 c ‘mega-corp ‘assets)
3290000
CL-USER> (getval #’+ 0 c ‘division-a ‘assets)
2475000
CL-USER> (getval #’+ 0 c ‘division-b ‘assets)
815000

Here we’re using a recursive procedure to apply the plus function to all of the property values from a certain point in the hierarchy down. The zero in the s-expressions there is an identity value– just like the ones we coded in SICP section 1-3. I had to implement that just in case there were all NIL’s in my hash table for a certain property. With a careful use of property names, you can get some benefits of stratified design (covered in SICP section 2-2) in this kind of data structure. We can code in all kinds of information about the separate divisions at one level… and way down the hierarchy we can have all kinds of other information stored about the employees. While working at either end, we can effectively ignore all of the other levels. At the same time we can “roll up” related values however we like at any level we care to focus on.

(There’s probably a few other things I could have done to make this better, faster, or slicker. If you’re working through SICP, too, please check out this complete code file and let me know if you have any tips or suggestions.  I used Common Lisp instead of Scheme, though. I really needed to stop a while and apply what I was learning in SICP to problems that I’d developed a personal stake in. Most people tend to abandon the book by section 2-2, so I better get back to work if I want to finish it!)

Back in the day, I would have avoided a recursive data structure like this if I was working on a similar task. I would have (horrors!) hard-coded the hierarchy at maybe 3 or 4 levels deep, coded all my tables as separate entities, and more than likely built in some work-arounds for the places where such choices were inadequate. (Thinking that OOP was the “right way,” I would have coded a class file for companies, divisions, offices, and employees– and then been stuck storing and retrieving data in as many separate RDBMS tables and figuring out how to map them back and forth somehow.  Writing nested hash tables to a file, on the other hand, is trivial in Common Lisp.) The end result would have been a maintenance nightmare…. It’s a good thing I was too lazy to finish any of those pet projects back then! Funny, I could see clearly the problems of coding 50 slightly different forms when one generic form could be rigged up to do the same thing, but I couldn’t break through my mental limitations to think three-dimensionally about data structures. Thanks to many painful hours spent working through SICP, I can now synthesize recursion, first class functions, and the closure property to make more elegant solutions to things that used to be next-to-impossible for me.

Update 10/26/07: I did manage to follow this post up here.

Boilerplate code says a lot about a language…

 I ran across this recently:

“In fact the problem of ‘boilerplate design pattern code’ says nothing about the quality of the language; it says only that the programmer are working at the wrong level of abstraction and are the victims of that all too common sickness: bad design. Picking another language is not the cure for this disease. (More than likely it’s only going to make things worse!)”

This is just plain wrong– except for the part about the programmer working at the wrong level of abstraction and being a victim of “bad design.” The question is, how much of that has been foisted onto the programmer by the design of the language he’s writing in? And if much of it is due to the language, then it’s certainly not off base to go shopping for a new one!

If you’re not clear on this issue, then you need to watch SICP Lecture 3a: Henderson Escher Example. Early in the lecture (00:05:45) he points out the importance of closure in any means of combination in a programming language. (Now this isn’t about “closures”, now… this is a more general mathematical principle.) Anyways, Abelson says, “Closure was the thing that allowed us to start building up complexity…. The things that we make… those things themselves can be combined…. to make more complicated things…. When you look at a means of combination, you should be asking yourself whether things are closed under that means of combination.”

Obviously, it’s much better to be able to make an array of arrays than it is to be restricted to only storing numbers or strings in them. Whenever the principle of closure is violated, you’re going to be limited in your ability to formulate useful abstractions. Just like you lose the ability to express certain ideas cleanly (or even at all) when functions are anything other than first class citizens in your programming language. Programming languages really do have significant differences; they’re not all the same.

After going through his example step by step (and incorporating everything covered so far in the course), he (01:02:37) sums up why the ability to create embedded languages is so important: “That’s the important point: the  difference between merely implementing something in a language and embedding something in a language so that you don’t lose the original power of the language. Lisp is a lousy language for doing any particular problem; what it’s good for is figuring out the right language that you want and embedding that in Lisp. That’s the real power to this approach to design.”

I think a lot of people get the heeby jeebies when they hear Lisp programmers talking about creating new languages to solve problems. They’re thinking, “if people start writing their own macros, how will I understand the code when I have to maintain it?!” Well, yeah. That’s only going to be a problem if you don’t know how to use macroexpand to show what’s going on “under the hood.”

But when you look at what’s going on in the example from the video, you can see that the process of implementing languages to describe what’s going on actually makes the code much easier to understand. The languages are implemented at each level of abstraction. Each language doesn’t “care” how the lower level languages are actually implemented– you can think at each level in terms of that level without being confused by unnecessary detail. And each level can be manipulated with and integrated with all of the usual idioms of the Lisp language itself. It’s not like you’re randomly inventing a new Python or Perl depending on the problem you’re solving. You’re making languages that are fully embedded in Lisp… and there’s nothing keeping you from utilizing other Lisp tools, techniques, and elements with these language layers.

So don’t let all the talk about DSL’s and embedded languages scare you. Expressive code can actually be easier to understand, extend and maintain.

Update 10/2/07:   ”discipline and punish” responds with Programming Languages, DSLs, Static Typing, and the Answer to Life, the Universe and Everything.

Mastering Higher Order Programming Techniques with SICP Chapter 1

Section 1.1 was deceptively simple, but things rapidly got heavy in section 1.2. The process of tree recursion was exceedingly difficult to visualize. Exercise 1.13 asked us to “use induction” to prove something. Plugging through exercise 1.20 was exceedingly painful back when I was working on my own. The march of technology added some complications to the later problems that caused me to dread going on… and the Miller-Rabin problem was completely mystifying. (I hacked out a Common Lisp version of the algorithm described on Wikipedia, but even that exercise failed to give me the insight necessary to understand the question. I haven’t been that befuddled since that problem from PAIP chapter 2….) Collectively, these experiences might lead one to believe that working through SICP was a lost cause….

A couple of things can really improve your chances of getting through it, though. One thing is to definitely watch the videos– they really make things interesting and more accessible. Another thing is just to have a friend or two that you can bounce things off of. “I tried x on problem y… is that what you think they wanted there? Also, are you getting something like z on problem w?” A few encouragements from a peer can really help you focus.

Continuing on into section 1.3 things got much easier. The lecture was outstanding. It is probably the definitive sales pitch for higher order thinking. If you ever wondered what people mean when they talk about “higher order procedures,” this is the place to go. The problems for the most part were straight-forward or about medium level. A lot of them push you to alter or imitate clear examples, so they are pretty “fair” as exercises go. Others require a modicum of persistence and experimentation, but are still pretty straight forward. I got through most of them with only a couple of minor questions. (Simpson’s rule in 1.29 didn’t work for me as it was advertised. The instruction to “show that the Golden Mean is a fixed-point transformation” is perhaps beyond my math skills. I wasn’t sure how to test my answer in 1.44, and I’m not quite sure where to go with 1.46.) But if the goal here was to get me to understand when and how to implement functions that take functions as arguments and that return a function for their value… then I’m there. They push the level of abstraction… and then push it some more… and then push it until I want the merry-go-round to stop. I used to think that mapcar was pretty darn cool. Now I have an entire new mental apparatus that I can apply regardless of the language or platform.

So I’ve got the bulk of the problems from the first chapter completed and it’s all culminated into a deeper understanding of how to apply and implement functional style abstractions. I’m really pleased with how far they’ve brought me in the text, but I begin to get anxious: I want to go code something… and I’m afraid of how far into the stratosphere they’re going to push my mind. I wanted at first to learn more powerful methods of creating general solutions… but really, I only wanted to get maybe half an order of magnitude better as a programmer. I had no idea that they would push my mind so far beyond its comfort zone. I had no idea that I even had a mental comfort zone! The experience gives me a new respect for MIT… and I’m glad I have a chance to experience a bit of what they put their computer science students through. (I want to also give my thanks to the SICP study group for providing me the inspiration and the encouragement to continue working through this book!)

Two minor things stand out for me, as far as mental processes go. One is the “faith oriented programming” that Sussman advocates in the lecture: if you’re not sure how to code a complex routine, just assume the hard parts are already done. If you can put a name on what’s missing, you’ll be able to easily address it later. Thankfully, DrScheme doesn’t auto-highlight “syntax errors” in this case! This worked surprisingly well for me when I went back and reworked the Pascal’s Triangle problem from section 1.2. Also, in section 1.3 they formalize the “guess-fudge” method that helped me do well in so many math classes in the past. The iterative approaches in the section mirror my own problem solving techniques: if you’re not sure of the answer, guess… then make small improvements or adjustments until it’s good enough. Combining these techniques gives you the key to solving recursion problems: start with a rough outline the covers the trivial cases… then “guess-fudge” the missing piece into existence with a function or two. This works for many of the problems in the text.

Anyways, if you got overwhelmed in section 1.2, just hang tight… it gets easier. Or maybe you get smarter. Something. They keep the pressure on, but they are very steady in section 1.3. It’s a lot of work– almost like learning to program all over again– but everything they make you do is part of their perfect plan to transform the way you think about algorithms. I can’t for the life of me imagine why so many people have complained about Scheme: it’s an exceeding beautiful language that gets out of the way so that you can express raw thought in its most elegant form. It’s hard to believe how much can be accomplished with only a handful primitives and parentheses….

For those that want to compare notes, here’s my code for exercises 1.29 to 1.33, 1.35 to 1.39, and 1.40 to 1.46. Also, here’s my algorithm for the Miller-Rabin test based on the instrictions from this Wikipedia entry.

Recursive Discontents: Grahamian Macho Programmers are Restricted and Narrow-minded

Michael Harrison recently wondered why recursion was emphasized so much in Scheme and noted that it was perfectly natural for a language designed to model algorithms to do so. Notice the repetitive application inherent in Euclid’s algorithm: “Given two natural numbers a and b, not both equal to zero: check if b is zero; if yes, a is the gcd. If not, repeat the process using, respectively, b, and the remainder after dividing a by b.” Notice that step 6 of the Sieve of Eratosthenes is to “Repeat steps 4 and 5 until no more numbers are left in List A.” Step three of the Babylonian method for calculating square roots is “Repeat step 2 until r and x / r are as close as desired.” From the dawn of mathematical thought, recursion has naturally emerged in the study of algorithms. A computer language built to express algorithms concisely would necessarily include recursion.

But can’t we do without recursion in a programming language? Aren’t FOR…NEXT loops and DO…UNTIL loops sufficient? Those are nice friendly abstractions, of course, but they are just two special case forms of iteration. As we see in SICP lecture 1b (and section 1-2 in the book), recursive functions can be used to define any recursive or iterative process. Simpler language concepts will allow you to get by on most business programming assignments, but sooner or later you’ll come to a problem where you will actually need recursion to solve it. It is better to be fluent in the more general tool than to limit your mind to expressing itself with a small subset of what is possible.

But there’s something deeper here than the convulsions of Blub programmers sparing with smug functional dweebs. Recursion lies in the very heart of the “accurate reckoning for inquiring into things, and the knowledge of all things, mysteries… all secrets.” Recursive functions are the only functions that can be computed mechanically: Alonzo Church developed his lambda calculus in order to explore function definition, application, and recursion. Thanks to his work on the lambda calculus and to the work of Kurt Godel, he was able to demonstrate that Hilbert’s famous Entscheidungsproblem was impossible to solve. All known computational processes are equivalent to lambda calculus and Turing machines… and both of those have been shown to be equivalent to recursion.

Later on, John McCarthy (who was a student of Church) used the lambda calculus as a basis for the Lisp programming language. Recursion is inescapable in any dialect of Lisp. Not only is the list data type itself defined recursively (as Chuck Hoffman recently pointed out), but as we are reminded in SICP lecture 1-b, the evaluation process of Lisp is defined recursively as well. I expect recursion to be a continuing theme in the course as our work culminates into an understanding of the Metacircular Evaluator. At any rate, given the title of Macarthy’s original paper on Lisp, it is evident that the language itself is designed primarily as a means of expressing recursive functions.

As Leo Comerford Matthias Benkard said, “Lisp, in its most general sense, is a uniform notation for programs.” SICP will gradually develop our ability to think and implement code in Metalinguistic terms. Theoretically, this will allow us to conceptualize and solve problems without having our minds hindered by the limitations of procedural, OOP, or even functional methodologies– even while we cherry pick from those approaches whenever we feel inclined. Lisp’s homoiconic and multi-paradigmatic nature would seem to facilitate such thinking. It seems to me that someone who had mastered such techniques would be quite far from being “restricted and narrow-minded.”