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.

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

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

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

Powerful stuff. You love it.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

… and all remnants of literature disappeared…

Here are some random snippets and comments on a really large essay by Richard P. Gabriel & Ron Goldman.

It’s not so much that your favorite programming language is slow— rather, that lame hardware we have to run on is optimized for Fortran:

“Early computing practices evolved under the assumption that the only uses for computers were military, scientific, and engineering computation-along with a small need for building tools to support such activities. We can characterize these computational loads as numeric, and the resulting computational requirements as Fortran-like. Early attempts to expand the realm of computing-such as John McCarthy’s valiant attempt with Lisp and artificial intelligence, Kristen Nygaard’s similarly pioneering attempt with Simula, Doug Englebart’s intriguing attempt to expand our usage options, Alan Kay’s later attempt with Smalltalk, and Alain Colmerauer’s attempt with Prolog-were rebuked.”

The way we write code, we might as well be writing in assembly:

“Programming languages have hardly shown one scintilla of difference from the designs made in the first few years of computing. All significant programming languages are expressively, conceptually, and aesthetically equivalent to Fortran and assembly language.”

The only thing worse than a lack of modularity is any attempt to actually reuse the component parts:

“The real problem with modular parts is that we took a good idea-modularity-and mixed it up with reuse. Modularity is about separation: When we worry about a small set of related things, we locate them in the same place. This is how thousands of programmers can work on the same source code and make progress. We get in trouble when we try to use that small set of related things in lots of places without preparing or repairing them.”

The “Popular Culture” that Kay has complained about is not the thing that killed the next revolutionary computer language– Atari and Infocom aren’t responsible for the retardation of computer science. It’s was the commoditization of programmers and the subsequent elimination of a common and accessible source code that set us back a decade or more:

“When software became merchandise, the opportunity vanished of teaching software development as a craft and as artistry. The literature became frozen. It’s extremely rare today to stumble across someone who is familiar with the same source code as you are. If all remnants of literature disappeared, you’d expect that eventually all respect for it-as an art form, as a craft, as an activity worthy of human attention-would disappear. And so we’ve seen with software: The focus is on architecture, specifications, design documents, and graphical design languages. Code as code is looked down on: The lowest rank in the software development chain is “coder”-right alongside QA drone and doc writer.”

The fact that the masses had home computers and did goofy things is not what caused the setback. It was the demand that those users brought to the table that made change the dynamics of the hacker cultures of the day: teams of programmers all over the world were suddenly in competition with each other. Community ceased to exist, and software development culture shifted to something modeled more on dark age alchemists than modern mathematicians or scientists.

I didn’t know the history of the Oxford English Dictionary:

“Over a period of 70 years, many hundreds of people sent in over 6 million slips with words and their interesting occurrences in thousands of books. This resulted in the Oxford English Dictionary, the ultimate authority on English, with 300,000 words, about 2.5 million citations, 8.3 citations per entry, and in 20 volumes.”

Of course, in spite of OED’s influence, the decisions of its editors were still of the sort to routinely gall a philologist like Tolkien. Nevertheless, the point is taken: in a similar situation, Wikipedia has managed to take down Brittanica as the standard Encyclopedia. (Where else can you get insanely detailed articles on important stuff like the Star Wars Holiday Special….)

Many people have bitterly shot back at Lisp weenies that the Blub paradox applies equally to them as well. This is one of the rare articles that attempts to articulate a vision as to what the next step will be. It sounds sort of like a combination of reddit, Wikipedia, and SVN… heavily commented code modules and snippets that somehow are able to rely on each other in spite of constant change and development. The whole concept of interface evolution sounds crazy, though. How can little software “bots” know which methods to call when the interfaces are changing over time? Weird.

Why Linguistic Abstraction is a Winning Strategy

I want to highlight a couple of things that Bob Warfield has pointed out in a recent blog entry on the “small vs large” team size debate. My very small experiences observing and participating in development projects in the thick of the small and medium sized business environment have lead me to suspect these things, but it’s always good to hear someone that can articulate this stuff concisely:

“There are two ways to think about this. Chris takes the path that says the example is irrelevant because most software isn’t that way. I take the path of saying that the example is spot on because all software should become a language if done right. The benefit? Your small team is enormously more productive as are your customers if you can actually make the language something they can grasp and use. There is a reason these small teams built languages (though I’m not sure I view Linus as a tool/language). In fact, Quattro Pro had no less than 18 interpreters buried in the guts. Very few of them were surfaced for end users, most were there to make the code simpler and the product more powerful.”

So if you’re building something complex that has to meet a lot of different people’s needs (and whose needs are constantly changing) then you need to see through the cloud of conflicting requirements to the generic tools that would enable solutions to actually emerge. And the most powerful tools are actually going to be languages.

“Don’t kid yourself that a giant team running around gathering requirements and hacking out use cases in monolithic modules is building software, business or otherwise. It’s creating an unmaintainable mess that makes nobody but the IT guys that assembled that laundry list happy. Certainly the business users who it lands on are going to find it isn’t what they thought they were getting and it is almost impossible to change it into what they wanted.”

If we solve today’s problem, we’re hosed. Today’s problem isn’t the real problem… it’s just one iteration of it. So we shouldn’t give into the temptation to “hard code” stuff for the check-list people just to please them in the short term. The requirements and use cases of today have to be expressed in terms of our tools and linguistic abstractions: we need to invest efforts in expanding their scope and expressiveness.

Programming is too often a substitute for mathematics…

I didn’t immediately recognize the equation that Steve Knight used in his answer to problem 6 of the Euler Project, but it was in fact just the formula for an arithmetic series. This one’s actually pretty easy to come to from an intuitive standpoint.

The story goes that Gauss had one of the meanest school teachers in the world. He made all of the students add the whole numbers from one to one hundred. The children would work for hours scratching away on their little chalk boards trying to get the answer, but Gauss was too lazy for that. He scribbled the answer and threw the chalk board across the room and said, “there it lies.”

What he had done was simplified the problem. If you take the numbers from 1 to 50 and pair them up with the numbers 100 to 51, you get a series of sums: 1 + 100, 2 + 99, … , 49 + 52, 50 + 51. All of these add up to 101. To get the answer he simply multiplied 101 by 50.

Generalizing this technique, to add up the first n natural numbers, you multiply half of n with n plus one… which is (n/2) * (n + 1). Algebraically, this “simplifies” to [n(n+1)]/2. Putting that into prefix notation gives you Steve Knight’s equation: (/ (* n (1+ n)) 2).

Now the people who put together the Euler project did not intend for us to write clever recursive programs. The problems they chose were meant to be so onerous that one would rather do the math than work it out. Us being programers, we miss the point completely!

Now, I’ve seen the formula for doing whatever you want with arithmetic series. I’ve seen stuff for geometric series, too. Arithmetic series are defined recursively where each term equals the previous term plus a constant. The nth term of a geometric series is equal to the first term times the “common ratio” raised to the (n – 1)th power. So we’ve got math for series like 55, 55, 60, … , 2035 and 1, 2, 4, 8, 16, 32, …. But I don’t see math for series like 1, 4, 9, 16, … , 10000.

I don’t see the cutesy thing we were supposed to be doing with this one….  What is the “right way” to sum a list of squares??

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

Lisp at Work: Evidence Based Scheduling

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

By the way… Zach wins ;)

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

It looks like Zach wins….

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

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

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

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

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

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

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

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

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

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

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

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

***

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

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

***

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

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

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

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