Scott's Blog

Dingbat

2006-10-15T12:10:00.000-07:00

Chris is studying for the GRE today and we're testing each other's vocabulary. This definition for dingbat is by far my favorite today:

1. An eccentric or silly person; 2. An ornimental piece of type for borders, seperators, etc; 3. An object (as a brick) serving as a missile.

Finding a job sucks. Or: on exposing your trackers to the world

2006-10-13T09:53:00.000-07:00

Finding a job sucks. One thing that drives me crazy is when you go to a career fair for your university and you physically hand a recruiter your resume. They look it over and say "Wow! You look really qualified, we'd love to interview you!" You nod in satisfaction, having spent days polishing your resume. "But," says the recruiter, "we'd like you to go online to your campus's Career Services website and submit your resume through them to us; and then, would you go ahead and visit our corporate website and use our lame-ass resume tracker too?" Honestly, what's the point of giving the recruiters your resume if they're just going to shred it and ask for two electronic copies?

I wouldn't mind visiting corporate website X Y and Z to submit my resume if that's all their resume trackers wanted me to do. But that isn't what a resume tracker is for. Resume trackers provide a company three things: a way to keep track of applicants, a bar to entry, and a way to avoid paying something with a brain to weed through the pile of resumes, discarding the obviously incompetent. What I truly resent is having to rewrite my resume for every single company I apply for. Every company has its own unique take on what a resume should be; every company just knows the One True Resume Format. And it's your responsibility as an applicant to take the work of art that is your resume and compromise its integrity and eye-catching uniqueness in order to shoehorn it into the bland, uniform, generic Corporate Resume Form.

Okay, I get it: you're a big company and you've got thousands of hungry developers scratching at your door and you'd like a little bar to entry. Well, here's a hint. Think about exactly who you're barring. You're not barring the desperate underqualified morons with Gud Tiping Skills. They have nothing else to do but rewrite their resumes over and over, targeting with mindnumbing persistence every company they can think of. You're definitely discouraging creative programmers who find repetitive tasks disgusting. Your Generic Corporate Resume form doesn't provide the creative programmer a way to express all the neat projects he's worked on. And if you think letting your own applicants tell you how experienced they are in the limited number of skill fields you allow them to enter will produce accurate profiles of characteristically hard to qualify skills, you're just fooling yourself. Yes, resume trackers are a bar to entry, but it's the wrong bar to entry.

Okay, I get it: you're a big company and your HR department of 40 needs a way to track the state of 40,000 applications. I'm no stranger to that problem. My honors fraternity usually has two people in charge of handling all the requests for new membership. They aren't paid, they're in school, and they handle collectively about 150 new contacts each semester. These new contacts are the brightest crayons in the box, the top kids in their class, and by far the most discerning applicants. We don't want to drop the ball with them. I built our fraternity a recruiting tracker to keep track of who applied, when they applied, their statistics, which events they've attended, and any number of other things we would otherwise have to keep track of with paper. HR departments have these trackers as well.

When my honors fraternity wants new members, we ask our campus's registrar to send a note to students with a certain GPA who have a certain number of credit hours. Companies do this too: they send messages through my university's career services website, through my department chair, and through advertisements on campus. The result of this kind of direct advertising is a landslide response. Our honors fraternity recruitment begins with an info session, followed by two weeks of events open to the public before Pinning, the official start of the initiation period---a six-week long introduction to the fraternity before Induction, when the initiates become members. Companies do this too: you attend an info session, you interview, and you get hired.

The big difference is how we handle our recruitment trackers. When I wrote the recruitment tracker for my fraternity, I explicitly did NOT allow anyone besides the two officers who handle new applicants to use the tracker. Everyone else needs to ask them for information if they want it. Applicants never ever see the recruitment tracker. We don't want them to! The president and recruitment advisor, the two officers responsible for handling applicants, respond to every single application by email and make the changes to the recruitment tracker themselves.

"Inefficient!" you say, "Why not have a link in your advertising and have your applicants do it themselves?" Two very good reasons: integrity and respect. We don't want our applicants interacting with the recruitment tracker because we want to make sure the tracker has high data integrity. This internal tool is a great time saver for us, but it's worthless if it contains crap for data. The tool is inherently limited in what it accepts for input and what functions it can perform. If an outstanding applicant doesn't fit the mould, I fix the tracker or we flag the applicant and make annotations to the tracker entry. If an applicant hasn't provided enough information, the president or the rush advisor personally gets in touch with the applicant to get the required information. "Inefficient!" you say, "Why not use form validation and get all the information in one fell swoop?" Because it's not just about data integrity, it's also about respect for our applicants. We want them to know we care about them. Our fraternity isn't going to be just another name on their resume, it's going to be a big part of their life. Every interaction we have with them tells us more about them and tells them more about us.

Companies that don't interact with their applicants are missing worlds of information about their prospective employees! Not only do they avoid personal contact with these applicants, who may eventually become their co-workers, supervisors, or underlings; not only do they risk polluting their precious tracking databases with crappy data; but they also turn off the creative people they want to reach in the first place. Your HR people are extremely intelligent and quite adept at discerning the bullshit from the real. Much more so than any computerized filter could ever be.

The best of the best, the worst of the worst

All ranting aside, I wanted to share my application experience for the hopeful benefit of humankind.

Google. You don't even need to wonder. I've never seen Google's recruitment tracker, but I have no doubt it's brilliant. Every interaction I've had with them has been through email with their extremely competent and respectful recruiters. These guys are the best of the best.
Sun. Sure, I had to deal with their tracker, but it let me upload my own resume in PDF format. It didn't ask me to enter my experience as a form field. They didn't ask a bunch of questions that a non-moron would answer with their resume. If you're going to have a tracker, do it like Sun.
Micron. Aside from having a nice looking website anyway, their tracker uses AJAX for a much smoother experience. Kudos to Taleo. If you're going to use an off-the-shelf product, use these guys. The first page on the tracker asks you to upload your resume, transcript, any other helpful documentation. That's the way to do it. They ask you some form questions about your name, your institute of higher education (a pretty safe field to add to a form---there's pretty much only one way to report this, unlike your employment history and your skillset). They ask broad questions about where you'd like to work. That's it---end of story. Very much one of the best trackers I've seen.
Agilent. This may be one of the poorest trackers I've seen. You can't upload your resume, but you CAN paste a text copy of it. For those of us who don't use word processors but prefer to generate our resumes from XML or LaTeX, this is a big pain in the ass. Oh, but you can use the resume generator, which asks you a bunch of questions and produces a generic resume in text format for you. At least they don't force you to enter your work history in a series of forms. It's not really Agilent's fault, they just chose crappy tracking software. Agilent, go get Taleo.

These are just a few of the many places I'm applying to. Many are worse, some are better. None are better than Google, though.

Common Resume Interchange

In a world constantly spouting mumbo-jumbo about service connectivity and integration, you'd think the hiring process would be seeing some of this. But it hasn't. Most employers ask the same basic questions: who are you, where can we reach you, and why should we care. I call on the leaders of HR companies to produce an XML specification for resumes. If you don't want to excite your applying developers' gag reflex even further, your product had better allow for the following:

Be open and not restrictive about the format and content of employment history and skills. There's no objective way to quantify your skills, and your employment history (especially for the self-employed or you built your own company) is going to be very difficult to fit into someone else's idea of what your employment history should be.
Understand that the CRI is about metadata, not a replacement for a resume. It's fine if you want me to extract important metadata from my resume so you can get to it faster. I really don't mind. But the CRI will never replace a resume.
Build a plugin for Word. I don't use Word and I'd prefer never to have to. But if you want CRI to be useful, you should give away a Word plugin that can annotate your word documents with CRI data.
For God's sake, don't overengineer it! Don't build another XSL spec, don't build another GEDCOM spec. It doesn't need to be that complicated. And make sure you document the spec well enough.
If your client company can't be bothered to look at resumes individually, then your product should use natural language processing techniques to attempt to extract useful information from freeform resumes translated into text format. Yeah, it's a hard problem; your clients would be better off just paying a brain to look through the resumes. But don't succumb to the urge to put this problem in your applicant's lap, or you'll find that your tracker product reduces the quality of your clients' new hires. Talk about solving the wrong problem.

Carbonleaf and Matt Nathanson at the Aggie

2006-10-01T23:05:00.000-07:00

I discovered I love Carbonleaf! Perhaps despite the Aggie Theatre, which seems to be completely incapable of decent sound balance. Matt Nathanson's band sounded muddy; the accoustic guitar and the vocals were barely audible over the bass! The Fox Theater did a much job when I saw Steven Kellog and the 6ers last Thursday, and when I last saw Matt Nathanson two years ago. Carbonleaf must be really awesome when the sound technician is decent.

Busy Beaver hunter up and running!

2006-09-12T23:06:00.000-07:00

A hastily-written python program hums quietly away on four different machines, patiently guessing solutions to the 5-node busy beaver problem. Hooray!! If I'd been thinking properly, I'd have written it in scheme and used gambit to compile it... the algorithm I'm using uses constant memory, but is quite greedy in terms of computation time, so every little bit of speed counts.

After about half an hour of running, one of the processes has found a machine that produces 12 marks after 61 cycles!

It would help prune down the search space enormously if I could prove there were equivalent turing machines out there that had non-isomorphic state graphs; especially if the result allowed us to prune down the possible labels for the edges of the state graph! That's where the really terrible performance comes from...

The potency of configurations

2006-09-12T00:55:00.000-07:00

As a fun question to try to answer related to Turing machines... let C_n represent the set of all Turing templates of n states, as defined in the last post. Let P(c) represent the potency of configuration c∈C_n, defined to be the mean productivity of all the Turing machines t∈c.
The question: What's the distribution of P(c)?

Why it matters...

If P(c) has a Gaussian distribution with a fairly tight standard deviation, then the potency function is a useful heuristic that could be used to drive an A* search through C_n. A few samples of t∈c could establish whether c is worth examining.

It's not likely to be the case though, given that two machines in c could behave completely differently. This suggests looking for a different similarity metric between machines.

Hunting beavers: exhaustive generation without isomorphism

2006-09-11T21:28:00.000-07:00

In the previous post, I decided to narrow my brute-force search for the 5-node Busy Beaver down to a smaller number of 5-node machines that at least stood a fair chance of halting and used all 5 states. I haven't proved this simplification doesn't exclude the Busy Beaver machine, but I have a strong intuition it doesn't.

The graph-theoretic reformulation

To make the search tractable, we're going to represent the busy beaver Turing machine with a graph. There are two symbols in the alphabet of the Turing machine, so each node in the graph representing a Turing machine "state" should have two outgoing edges. To guarantee that the machine at least contains a HALT instruction, add another node "E" representing the HALT instruction, and stipulate that there must be a path between the start node "S" and the HALT state "E". The situation: Suppose we have a directed graph of n nodes that allows loops and self-loops. Two nodes are distinguished: S and E. There must be a path from every node but E to E. All the nodes but E have two outgoing edges; E must have none. The question: How many non-isomorphic graphs of this form are there? The answer: 6⁵ = 7,776 graphs. Few enough to be tractable!

Ugly details

Where did the magic 6⁵ come from? A chain from S to E must exist, so start there. We can additionally ensure that every node has a path to E by having the chain from S to E run through every node:

The "backbone" of the isomorphism guarantees at least one HALT instruction and gives the machine a chance at reaching it
S	→	2	→	3	→	…	→	n	→	E
↓		↓		↓				↓		↓
?		?		?				?		?

That takes care of half the edges. The other n edges each choose one of the n+1 nodes independently, for a total of (n+1)ⁿ possibilities.

Applying the results

For each distinct graph found above, a number of machines can be generated by annotating the edges. For example, an annotation "1:1L" means "if I read a one, write a one, move the head left, and transition the Turing machine to the state at the end of this line." There are 2×4×4 = 32 possible annotation sets for each node, putting the solution space at 32ⁿ(n+1)ⁿ; a whopping 6⁵32⁵ (that's a 26-digit number in decimal!). Still too big to brute force, but still much smaller than the unrestricted solution space of (2n)⁸ⁿ (10⁴⁰). The restrictions tighten the solution space by roughly 14 orders of magnitude for the n=5 case. Given that the constraints enforce the presence of at least one HALT, and the use of the entire 5 states of the machine, it's easy to see why the stochastic method over the unrestricted state space fails to find answers. The chances of hitting on one of the machines that fits the constraints is roughly 1 to 10¹⁴ against; given that the constraint machines aren't guaranteed to halt makes this statistic even more abysmal. Note that this approach still overgenerates. It's easy to see if both outgoing edges of a node lead to the same node that there are only 16 possible labels for the node's edges. The graph approach looks promising. Possibly there are further sensible constraints that would reduce the number of potential non-isomorphic graphs

Busy Beaver

2006-09-06T20:02:00.000-07:00

Note: This article is in progress. The assignment is due Wednesday the 13th, so you can count on it being done sometime around then!

This problem comes to us by way of Tibor Radó's 1962 paper on the Busy Beaver function. A brief formulation goes like this: Suppose you define the productivity of a Turing machine with n states as the number of 1's written to the Turing machine's tape after it successfully halts. Represent the productivity as a function p(n). Call the machine with n states that maximizes p(n) the Busy Beaver Machine. Radó proved that no Turing machine can compute the value of p(n)¹.

Our primary interest in the problem is to find the Busy Beaver Machine for n=5 in order to win a contest for class: who can write the 5-state Turing machine that halts and writes the most ones to an initially blank tape?

For an intuition about the magnitudes involved in this problem, previous research turns up the current leader in the n=5 case at Pascal Michel's page. This particular machine (found in 1989 by Heiner Marxen and Jürgen Buntrock) produces 4,098 marks before halting after 47,176,870 steps.

Formalizing the problem a bit

The Busy Beaver problem, being a subset of Turing literature, requires a bit further definition. Our Turing machine has the following form:

	0	1
1	S_new D I_new	…
…
n

The instructions arranged into rows corresponding to the states of the Turing machine, and into columns based on the contents of the cell at the tape's current location. The instruction cell consists of three components: what to write at the current location, which way to move the tape, and what state to transition to next.

First approach: the stochastic method

The stochastic method builds random Turing machines and tests them. Because the Halting Problem is also not solvable, we run the Turing machine for an arbitrary amount of time and stop the machine if it hasn't stopped itself by then. The stochastic method is a rather naive method. Since it's not an exhaustive search of the state space, it's not possible to determine whether p(5) has been maximized or not. The best we can do is run the stochastic machine builder, keeping track of the most performant candidates, until we run out of time for the contest. It's important to understand the size of the search space. Suppose we examine each cell in the 2×n table individually and assign it an instruction. We choose S_new, D, and G independently for each instruction, giving 2×2×5 = 20 different operating instructions. Add to that the halt instruction and the total is 21 instructions, for a total of 10²¹ combinations! If the stochastic method finds any solution at all, it's by sheer luck. My python process has been running several hours, and the best it's come up with is 5-state Turing machine that produces 1 mark on the tape and halts. Obviously, even a human can do better than this!

Intuitions about behavior may improve our chances

Intuition 1: Avoiding Isomorphisms

The intuition here is that much of the state space is populated by clones—that is, equivalent Turing machines. Any machine M' which is equivalent to the halting machine M also halts and additionally produces the same number of marks on the tape. If a brute-force method could avoid generating all the isomorphisms of a halting machine, the state space to be searched might be significantly reduced. This approach, done without care, may produce a crippling effect on memory usage as each halting machine is stored so the algorithm can avoid producing its isomorphisms. Additionally, if the generator randomly generates new machines and then attempts to prove to itself whether it's an isomorphism of a known machine is likely to be more costly than simply running the machines themselves. What's needed is an algorithm for enumerating the non-isomorphic machines with n states that doesn't involve storing history.

Intuition 2: Graph Theory

Enter graph theory. By reformulating the question in terms of graph theory, we can take advantage of the powerful methods and proofs already developed in this domain. To simplify the machine representation, let's only examine the potential instruction sequences instead of the entire machine. Let's build a directed graph of the states. We'll represent the special HALT instruction as an extra node, giving n + 1 nodes to the state graph. We'll represent state transitions with colored edges to indicate that the state transitions are not fungible. First, some obvious observations on the necessary nature of this graph. The state graph should be connected, with no islands. By this I mean from any node it should be possible to reach the halt node. Otherwise the machine has effectively fewer than n states, and it's been proven that p(n) > p(n') where n > n'. This constraint guarantees that it is at least plausible that the machine will eventually reach the special halt node. Additionally, this helps the machine avoid some obvious infinite loops—for example, a state where both outgoing edges lead back to itself. The graph may be cyclic without necessarily causing the machine to run forever—the state graph doesn't encompass enough information to determine this (and in fact this is a good thing---we're hoping by simplifying the problem we can make it tractable. We already know the problem is not directly soluble, we're just trying to find a practical approximation). Fixing the state graph is a big win. For a given n-state graph, there are now only O(n²) machines (in reality, this number is slightly smaller—at least one of the instructions is the halt instruction, which has no second component). The next question in combinatorial analysis is: how many non-isomorphic, connected graphs of n+1 nodes, where n of the nodes have two distinct outgoing edges, and the special halt node has no outgoing edges? Finally, the last question is: how do we generate these graphs?

Intuition n: The optimal number of HALTs

The question of how many HALT instructions to include in the machine is intuitively related to the bridge-crossing question. Look at it this way: we must start at state 0, and to get the best of the machine we should try to use every state possible. In some cases, this is an even number of crossings, in some cases, an odd number. This affects the number of HALT instructions that need to be available (or does it? After all, we're not restricted to crossing a bridge only once—we're restricted to only crossing bridges that exist. That is, we can't modify the machine after it starts running). This most likely will turn out to be a false intuition.

1. http://plato.stanford.edu/entries/turing-machine/

My Christine

2006-08-31T21:24:00.000-07:00

ὠ ἡ χρίστη, χριστίν, ἡ καρδίᾱς ἐμῆς φύλαξ· ἐμή φιλίᾱ σοί.

Moved In-ness!

2006-08-25T23:51:00.000-07:00

I'm finally moved in! Well most of the way. Got a TV and DVD player from Elizabeth for <intonation type="salesman">cheap cheap cheap</intonation> but nowhere really to hook it up. Not that I particularly watch TV anyway, but it might be nice to catch the odd episode of SNL, or tune into those important emergency system tests! With the last of the peaches going bad, it's time for a food-drying experiment. We'll see how dried peaches turn out. Hopefully they'll make a delightful addition to the bread pudding I'm making tomorrow from all the crusty French bread around here. Which it turns out is something I actually like… between the two of us, Chris and I can almost consume an entire loaf in one sitting, leaving just about a quarter left. Perfect for bread pudding. Now if I could only manage to find time to clean up this mess...

Jumping cow amber ale (++)

2006-08-20T23:19:00.000-07:00

Yum yum! Light, wih just enough body...

One thing I'd change about python

2006-08-20T22:53:00.000-07:00

I think python is a nice enough language, but the lack of proper lexical scoping drives me nuts! Also, the generator concept almost works, but when you want to do a non-local yield, it's just not possible. For example, if your generator has a helper function that wants to yield, control flows back to your generator instead of to the code calling your generator!

Almost moved into my new apartment!

2006-08-20T22:46:00.000-07:00

It's taking for freaking ever, but I'm almost moved in to my apartment! Serious amounts of material were omitted from this blog because I didn't have an internet connection or I was out of the state (maybe more on that later :o). Actually the biggest reason is I'm exceedingly lazy. I picked up a cheap modem at CompUSA which amazingly enough worked in Linux. I tweaked my old server box a bit by installing dnsmasq for DHCP and DNS service and used it as a router, since the modem on my laptop isn't as linux-friendly. Works very well! Go gentoo again for having useful HOWTO material readily available (google gentoo home router). My newest addition to my growing library is "The Scheme Language." It looks quite informative and hopefully will be helpful when I'm implementing my .net scheme compiler! Yeah that's right, even though they already exist, I really want the experience of implementing scheme and since I want to learn about .net, this is a natural combination. Let's hope I can get someone on the CU faculty to advise this project so I can substitute it for some boring core class.

Autohighlight moves to a permanent home

2006-08-20T22:43:00.000-07:00

After a lengthy stay in no-man's land, Autohighlight finally has a home! As described on the home page, autohighlight is a project I worked on with another student in Spring 2006 whose purpose it was to automatically generate syntax description files for VIM and EMACS when given an input grammar in BNF form. The project was a mixed success, when taken in light of the fact it was implemented in 2 months, and the problem of reducing a context-free language to regular expressions is inherently intractable! Anyway, I hope someone gets use out of the code; it looks promising. Update: The url is really http://trac.artesiancode.com/trac/autohighlight.

Blogger stuff, and pictures and poems

2006-05-20T23:58:00.000-07:00

I apparently just now figured out how to get post titles to appear in the RSS feeds... apparently you have to add class="post-title" to your title header…. Sucks to that! Apparently some people's post editors have a little place for TITLE, but not mine. Maybe its broken.

Today someone showed me how to upload pictures, so some of the more interesting ones should be forthcoming, perhaps with some meditative text about them.

In other news, another project is born: a photo essay of abandoned and decaying spaces in Boulder; I'm thinking I'll call it Something there is that doesn't love a wall, in homage to Robert Frost's poem The Mending Wall:

Something there is that doesn't love a wall,
That sends the frozen-ground-swell under it,
And spills the upper boulders in the sun,
And makes gaps even two can pass abreast.
…
Something there is that doesn't love a wall,
That wants it down.' I could say 'Elves' to him,
But it's not elves exactly, and I'd rather
He said it for himself. I see him there
Bringing a stone grasped firmly by the top
In each hand, like an old-stone savage armed.
He moves in darkness as it seems to me—
Not of woods only and the shade of trees.
He will not go behind his father's saying,
And he likes having thought of it so well
He says again, "Good fences make good neighbors."

2006-05-19T09:49:00.000-07:00

Surviving Identity Theft

God forbid it should ever happen to one of us, but if it did, here's a post on the consumerist that gives you a Step -by-step HOWTO for dealing with a stolen identity. Very useful stuff brought to you by the security guru Bruce Schneier.

2006-05-17T17:03:00.000-07:00

Reason and the facts beat Intelligent Design again

Check out this ruling handed down in the Middle District court of Pennsylvania! Of course, with all the money behind the ID machine, it'll probably be appealed for a long time. In the mean time, rejoice in the truth! ID is a doggle, to quote the old man in Life of Brian.

2006-05-17T16:56:00.000-07:00

Chris gets a blog!

Well not quite a blog, but a livejournal... and hey, it offers RSS syndication, awesome!

2006-05-16T16:30:00.000-07:00

A Sonnet

Terror of the birdbath, she
In stalking quiet solitude
Approacheth near the feather-swarm
As birds erupt in hectic flurry
from branch and feeder where they stood.
Kitten smiles amid the storm.

2006-04-16T09:04:00.000-07:00

Mervyns to become shopper heaven

KINGDOM OF HEAVEN - In a press conference Tuesday, God declared, "Only the elect shall get into Mervyns." Mervyns, until recently a retail fixture of malls the country over, will be repurposed as a heaven for good consumers. An angel discussing the decision on condition of anonymity noted, "Since Mervyns, God rest its soul, has departed the earth forever and ever, really the only way to get into Mervins is to be among one of the elect," which are 13,000 in number and pre-chosen before birth by the Lord God Himself. "No amount of righteousness can cause Him to send to Mervins someone who was not elected at birth; but a single failure by one of the elect to heed His holy command could result in an instant loss of the promise of everlasting peace in Mervyns."

Experts in holy affairs speculate that the move may be intended as a test to the children of God. "Will they be good consumers?" Asks the Reverend Al Jameston, "Or will God's command to buy, buy, buy go unheeded?" He added, "the fate of the shopper's soul hangs in the balance by a perilous thread, suspended between unending damnation in the fiery pits of Hell and the paradise of Mervyns."

Rev. Jameston was unwilling to reveal his sources, but claimed to have it on good authority that there would be a second coming of Mervyns. "It is written by the hand of God Himself that when the final hour be reached, the celestial Mervyns will descend again to earth to bring shopping bargains and high-quality clothing to all," he said. The time of the second coming would be marked with plagues of frothy mochas and consumer savings cards, a strange disappearance of funds in bank accounts, and hip designer fashions returning mysteriously to Earth.

God, King of Kings and Lord of hosts, ruler of heaven and earth, in infinite wisdom abiding, could not be reached for further comment.

2006-03-26T08:33:00.000-08:00

More unfinished musings

So if a dispatch function/closure represents an object, then around-advice on the dispatch function is extending an object. Can a closure be cloned using primitives in Scheme? If so, then closures + aspect-oriented programming == prototype-based object system. The downside to the closure object system is that code is not shared. For cases where the clone dag is deep (large with a small branching factor), not sharing code is a good thing. For cases where the clone dag is wide (large with a large branching factor), sharing code is a good thing. How does one decide which slots will behave like class slots and which slots will behave like instance slots in the clone? Does the closure object necessarily need the concept of a slot at all? It could all be defined in terms of reactions to messages, some of which appear to cause state changes in the object. How does Prometheus handle this? Speaking of, a type could be defined either in terms of the clone dag, where children of a node are types; or type could be defined purely in terms of the interface supported by an object (if it looks like a duck, walks like a duck, quacks like a duck...). What kind of type safety optimizations can be made in a prototype-based language? Is it reasonable to be able to freeze changes to the clone dag in order to optimize method dispatch and slot mutation? Can freezing easily be undone, allowing the developer to resume modifying the objects in the dag interactively? Hmm...

2006-03-25T12:35:00.000-08:00

Unfinished thoughts on object systems

Prototype-based object systems, plus aspect-oriented programming, plus multiple dispatch generic functions... hmm... The naive way to implement method dispatch and slot access in prototype-based object systems is to chain-up to the original object when a clone doesn't understand a message. This means potentially several indirections if the clone-chain is deep. Some language I saw recently claimed to be able to do single-dispatch method invocations using a maximum of three indirections. Hygenic mix-ins require lexical closures. If you have a mix-in that modifies the behaviour of an object and requires keeping additional state, you need to be positive that your state-keeping slot doesn't clash with an existing slot. It seems like method invocation could be called "resume environment", where the object represents an environment, that is, a set of bindings. In the multiple-dispatch generic function case, method specializers are real, actual objects, specifying a node in the clone tree. All the progeny (objects created by cloning) of the specializer object are considered subclasses of the progeny. Some support should be built programmatically for moving methods and slots around in the tree. This implies that methods are first-class objects. This is also necessary because adding advice to a function requires having access to the function object. This implies that behaviour is somehow external to objects, which seems to contradict the prototype-based system; unless some provision for "cloning" methods exists, and this sounds a lot like aspect-orientation: orthogonal extensions to behavior. What if they're not orthogonal, but more like behavioral mixins? You'd like to be able to replace, not just augment behavior. It would be really nice to do this in scheme in 10 lines using closures. What does a MOP look like for prototype-based object system? Unfinishedness...

2006-02-07T10:17:00.000-08:00

Capturing a debugger backtrace

In my web application, I want to capture backtraces automatically and continue with the top-level request-handler-response loop. Here's how I did it:

(with-output-to-string (s)
 (block nil
    (handler-bind ((t #'(lambda (condition)
                                (sys::print-backtrace :out s)
                                (fresh-line s)
                                (sys::pretty-print-condition condition s)
                                (return))))
       (error "foo"))))
=> ".....[giant backtrace omitted]....."

Pretty ugly. I need to do some work to get clisp to print only the relevant frames (ie none of the driver, and none of the frames before the handler-bind, which I don't really care about). Pascal Bourguignon suggests a more elegant abstraction, which I have adopted for my own purposes (having the condition object responsible for the mess seemed useful).

(defmacro collecting-backtrace (&body body)
  (let ((s (gensym)) (b (gensym)))
    `(block ,b
       (handler-bind
           ((t (lambda (condition)
                 (return-from ,b 
                   (values nil condition
                           #+clisp (with-output-to-string (,s)
                                     (sys::print-backtrace :out ,s)
                                     (fresh-line ,s)
                                     (sys::pretty-print-condition condition ,s))
                           #-clisp
                           (format nil
                             "I don't know how to generate a backtrace on ~A"
                             (lisp-implementation-type)))))))
         (values (multiple-value-list (progn ,@body)) nil)))))

Much cleaner. I wonder whether the t in the handler-bind should be customizable... Anyways, still haven't looked into limiting the verbosity and depth of the stack trace.

2006-02-05T12:46:00.000-08:00

Finding nested ASDF components easily

The problem that prompted this excursion is that I wanted to get at a specific file in another ASDF package, and I didn't particularly care to know where the package is installed. Here's how the code started

(asdf:find-component 
  (asdf:find-component 
    (asdf:find-component nil :cl-catalyst)
    "templates") 
  "error")

There's a much easier way to do this kind of canonical component finding:

(reduce #'asdf:find-component 
        '(nil :cl-catalyst "templates" "error"))

Neat!!! It almost reminds me of logical pathnames...

2006-02-01T13:32:00.000-08:00

Using mod_rewrite to avoid seeing script names

It seemed like a pretty innocuous job... getting rid of the script name in the request http://localhost/~scottw/puma3/puma3.lisp/extra/path. But you wouldn't believe the pain it caused me! I record here the eventual solution (the inspiration is from this post related to removing the index.php from wiki urls).

Suppose you have a script ~/web/script.cgi, which is ordinarily accessible from the web as ~user/script.cgi. You want to rewrite requests like ~user/path into requests like /~user/script.cgi/path. The important piece being that the script sits in the same directory as your "virtual" path filename. Because of this important fact, the following ~/web/.htaccess will not work:

RewriteEngine On
RewriteBase /~user/
RewriteRule ^(.*)$ script.cgi/$1 [L]

Even though you added [L] to your rule, requesting ~user/anything will result in a 500 error. Looking at the apache logs, you'll see mod_rewrite complaining of too many internal rewrites. This is because your request is being rewritten over and over again like this:

anything -> script.cgi/anything -> script.cgi/script.cgi/anything

This is where the magic happens. You only want the rewrite rule to run when the virtual path doesn't exist. Here's the correct and working solution:

RewriteEngine On
RewriteBase /~user/
RewriteCond %{REQUEST_FILENAME} !-f
RewriteRule ^(.*)$ script.cgi/$1

Now after the first rewrite, the request filename begins with script.cgi, so the condition isn't true and the rewrite isn't triggered.

2006-01-26T22:46:00.000-08:00

McCLIM and CLISP

After several hours of trying, I successfully managed to load mcclim into a recent clisp. However, none of the demos are "working." By working, i mean, no errors are generated, but no output is really displayed. I'm trying to figure out how to debug the damned thing without really knowing much CLIM, but the more I learn, the more impressed I am with CLIM. I was especially impressed with the command object idea, having recently emerged from a software engineering class where we discussed the command pattern. It seems so natural in this context! I'm eager to try my hand at CLIM development, I'd like especially to build a gdk/gtk+-2.0 backend. Even cooler, potentially, when gobject introspection turns from vapourware into software, would be to have the backend mapping happen dynamically! Lots left to learn about CLIM and gdk first... I have a feeling the first thing to do is to make a gdk backend that mirrors the CLX backend, and hook the GTK widgets in place higher in CLIM abstraction model once I know the gdk drawing stuff is going to produce correct if not beautiful output for CLIM applications that use the low-level drawing toolkit stuff. It's quite exciting! If one could get CLIM running atop gdk and gtk, it wouldn't be hard to deliver clisp applications for windows (especially with clisp's recently-acquired ability to build executable files for windows!). I guess I'll start by tracing the crap out of the CLIM protocols to find out what's wrong with the CLX backend. I suspect it's a method combination or class precedence problem somewhere... I saw quite a few suspicious looking compilation errors on those topics. More later.

2006-01-26T22:44:00.000-08:00

An update on clisp-sqlite

I packaged clisp-sqlite as an ASDF-installable package!! Go check it out here. More documentation and some examples should follow soon.

2005-12-07T17:12:00.000-08:00

I've been programming some mind-bending algorithms in Python lately, and was truly irritated to be unable to find a Python analogue for Common Lisp's TRACE macro. Specifically, TRACE like clisp's TRACE. So, I built my own. This TRACE notifies you function invocations and returns, which makes it a lot more useful than the line-based TRACE offered by Python itself. My trace implementation only works on methods, not functions, so it's a little limited. When you call funtrace on a method name, it replaces the method with a wrapper that prints the name of the method, its arguments, and then calls the method itself. When the method returns, it prints which method finished and the return values. Sometimes you don't want to print all the arguments (because one is a gigantic dict and fills the entire screen when printed), which is what the second argument of funtrace is for. If you set this argument to False, all arguments are suppressed. If you set it to a numerical value n, only the first n arguments to the function will be printed (useful if you pass the dict in last). Each time a traced function is called, a global indent variable is incremented, and each time a traced function exits, the indent variable is decremented. If you print debugging statements using trprint, your output will be indented appropriately as well. If you want things that look like function invocations, for example at the beginning and end of a block, you can use trenter and trleave, just remember to balance them or you'll get very strange results. Both of these simply print their argument and do the indent bookkeeping. trace.py

indent = 0

from sys import stdout
import sys

def trprint(*args):
    global indent
    sys.stdout.write(indent * "   ")
    sys.stdout.write(*args)
    sys.stdout.write("\n")

def trenter(name):
    global indent
    trprint("ENTERING %s:" % name)
    indent += 1

def trleave(name):
    global indent
    indent -= 1
    trprint("LEAVING %s." % name)

def trace(func, printArgs):
    def inner(*args):
        global indent
        if printArgs:
            trenter("%s%s" % (func.__name__, args[:printArgs]))
        else:
            trenter("%s(...)" % (func.__name__))
        rt = func(*args)
        if printArgs:
            trleave("%s%s = %s" % (func.__name__, args[:printArgs], rt))
        else:
            trleave("%s(...) = %s" % (func.__name__, rt))
        return rt
    return inner

def funtrace(func, printArgs):
    func.im_class.__dict__[func.__name__] = trace(func, printArgs)
    return func

example.py

from trace import funtrace
from trace import trprint
class foo:
   def __str__(self): return ""
   def __repr__(self): return str(self)
   def bar(self, x):
     trprint("X = %s" % x)
     if x != 0:
        self.bar(x - 1)
     return x

funtrace(foo.bar, 3)
foo().bar(1)

This produces

ENTERING bar(, 3)
   X = 3
   ENTERING bar(, 2)
     X = 2
     ENTERING bar(, 1)
       X = 1
       ENTERING bar(, 0)
         X = 0
       LEAVING bar(, 0) = 0
     LEAVING bar(, 1) = 1
   LEAVING bar(, 2) = 2
LEAVING bar(, 3) = 3

Quite useful!

2005-11-03T23:00:00.000-08:00

I've just started The Mystery of Capital, by Hernando de Soto, and so far I don't think it's a bad read. I confess that I don't know much about economics, so it's sometimes disorienting. The premise is that formal property systems in developing nations exclude the poor, who hold the vast majority of assets in those nations. The poor have no access to the formal property systems, because the assets they own are owned illegally or because the legal system is too cumbersome to use. Lacking an entry into the formal property system, there is no way to use these assets for collateral. The statistics de Soto and his team use to illustrate the massive impediment to property ownership in developing nations is enlightening. My biggest question so far is whether the "formal property" argument can explain conditions in inner-city slums, and I suspect the answer is that inner-city slums in developed nations are caused by fundamentally different forces than shanty towns on the outskirts of a sprawling third-world metropolis. The author notes that land value in shanty towns is sometimes as high or higher than land in the legally-owned areas of town and going up, whereas land value in inner-city slums is wretched and deteriorating quickly. Hopefully more reading will clear up some of my economic confusion.

2005-11-03T22:22:00.000-08:00

I'm releasing version 1.0 of my clisp SQLite bindings for SQLite 2.8. If you've never used SQLite before, it's an embeddable SQL (duh) database. Check out SQLite. You can download my clisp binding at http://ucsub.colorado.edu/~williasr/sqlite-2.8-1.0.lisp. An ASDF/ASDF-Install-able version is Real Soon Now (tm). The bindings offer two levels of support: a low-level binding which is directly tied to the FFI (package SQLITE.RAW) and a more friendly, lisp-like interface built atop it (package SQLITE). Here's a glimpse of how it works:

[1]> (use-package :sqlite)
=> T
[2]> (setf my-db (sqlite-open #"~/tmp/test.db"))
=> #<SQLITE::DATABASE #P"/home/scottw/tmp/test.db" :OPEN>
[3]> (sql my-database "malformed sql")
*** - sql error 1: "near \"malformed\": syntax error. Offending query:
        "malformed sql"
Break 1 [4]> :r1
[5]> (sql my-database "create table bar (a, b)")
=> NIL
[6]> (sql my-database "insert into bar values (1, 2)")
=> NIL
[7]> (sql my-database "insert into bar values ('a', 'x')")
=> NIL
[8]> (sql my-database "select * from bar")
=> (("1" "2") ("a" "x"))
[9]> (sqlite-close my-database)
=> #<SQLITE::DATABASE #P"/home/scottw/tmp/test.db" :CLOSED>
[10]> (with-open-db (db #"~/tmp/test.db")
        (with-query (db (a b) "select a, b from bar")
          (format nil "Processing a row with a=~s, b=~s.~%" a b)))
Processing a row with a="1", b="2".
Processing a row with a="a", b="x".
=> T

So far as I've used it, I find with-query to be one of the most efficient and useful of the sql forms supplied with the binding. I optimized it for relatively high throughput (though for some reason, clisp creates 3 strings for every column in the row, odd), so it's fast in tight loops where your lisp must process a lot of data (it can handle a million 3-column rows in less than a second on my machine). Since the body of with-query is executed once for each row as the row is returned, it avoids building up potentially large lists, the way the plain SQL call is likely to. I find this form so particularly useful because it binds the columns from each result row to the specified variables, making them much more accessible. There are a few outstanding issues. The first is the lack of a with-transaction. Inserts into the database are much more efficient when wrapped in a transaction, but I haven't yet worked out how to wrap the body of with-transaction so that "rollback" is called if the body is left abnormally, and "commit" is called otherwise. I suspect some trickery with unwind-protect and catch is going to be necessary, though it's not obvious to me how to do it, so I'm delaying a while. Next, I plan to explore the MOP by building a Class::DBI-style object mapper. CLSQL already does this, but a) it doesn't compile out of the box with clisp, and b) I want to make my own.

2005-11-01T21:06:00.000-08:00

I got my copy of the Art of the Meta-Object Protocol in the mail today! Already it's more well-written and accessible than I could possibly have imagined, and is so far answering several questions in fields I hadn't related to the MOP (like how classical object models can be integrated with the generic object models used in CLOS, and how the MOP relates to the "essential difficulty" of software production). Thinking over the essential difficulty of programming today and the most promising (though non-silver) bullets, I was trying to decide how Generators, Patterns, and metaprogramming are related to one another in the attack on the essence of difficulty in programming. I've been thinking a lot, especially about Paul Graham's assertion that "When I see patterns in my programs, I consider it a sign of trouble. The shape of a program should reflect only the problem it needs to solve. Any other regularity in the code is a sign, to me at least, that I'm using abstractions that aren't powerful enough-- often that I'm generating by hand the expansions of some macro that I need to write." Perhaps more stewing on this idea is necessary before coming to a conclusion, but I'm tempted to agree, and also to point out Graham's use of Generators (in the form of macros) to help him accomplish some metaprogramming (someone who deserves an attribution but whose name I can't remember once said that metaprogramming is the art of engineering the language upward to meet it's intended use).

2005-11-01T20:54:00.000-08:00

Perl and Python, Lisp and TeX: Fundamental differences in user communities. I have a bias against Lisp and Tex documentation because I have always found it difficult to come by; hence I have always regarded these languages as poorly documented, even though I'm a fairly active and excited user of both. On the difference of availability of documentation, I think the origins of the languages are extremely important. Both Lisp and TeX have a rather more academic user group (not that they are any more capable than the Perl and Python crowd, but when you think practical programming, you think Perl, not TeX), whereas Perl and Python are grassroots efforts, so to speak. The very definition and elaboration of the languages themselves reflect this. If you want good documentation of TeX, buy the TeXbook, which I've heard is quite a rigorous bible of TeX. Consequently, anybody who owns the TeXbook is unlikely to be constantly publishing the little tidbits of information and procedure that float around. When I first began using LaTeX, I had a hell of a time finding any documentation for it, and now that I know exactly what to search for, I have a slightly less hard time, but by no means is it as easy as CPAN. The same is true with Lisp. The official common lisp spec has to be purchased from ANSI, and if you want to delve under the hood with the MOP, you're pretty much out of luck unless you buy the AMOP. Contrast this with the Python and Perl world: if you've been to CPAN, if you've read the perldocs, or browsed doc.python.org, you already know what I'm talking about. The TeX group has CTAN, which is similar to CPAN, and common lisp has cliki, which is also similar, but these two repositories are fundamentally different than CPAN—it's the documentation! The CTAN and cliki are only (or at least mostly) code repositories. They allow for quick and easy downloading of code, but provide no support for the user. I posit that it is exactly because the languages Perl and Python grew up in the bright sun of public scruitiny that they are so well documented on the Internet. As single individuals attempt to document a language, they must surely fail to document all of it. The Internet responds by producing stacks of How-To articles that guide the novice user. In the more academic world, the novice is guided to a book. The book may be perfectly instructive, but the community dialog, that searchable collective experience, is not available. I think this accounts for a significant difference between the Perl and Python, Lisp and TeX crowds.

2005-10-31T21:34:00.000-08:00

An automatic syntax highlighter for EMACS and VI. I'm taking a compiler construction course at CU this semester and a friend and I have chosen to write a compiler that produces syntax highlighters for two popular editors based on the abstract syntax specification of the language. We're using Eli (see Eli homepage). We spent last night wrangling with the AST, communally editing the AST spec using vim on screen. Nothing earth-shattering here, but it's what I'm working on.

2005-10-30T13:42:00.000-08:00

For those of us who have never heard of a MetaObject Protocol, the MOP for CLOS is a bit puzzling. What exactly is it? It's a standard that allows you to customize and extend the common lisp object system. For example, if you want to map objects onto databases like Class::DBI in Perl, or you want object persistance like Java's Prevayler, the MOP is the lisp machinery that will allow you to do it. Before one can delve into the dank cave of MOP, it helps to orient oneself a bit, and see how the CLOS is really put together. I'm using clisp, so if you run these examples in a different lisp, you may see different results. First, let's see what classes are made of. [1]> (defclass myclass () ((a :accessor mc-a))) #<standard-class> [2]> (class-of (make-instance 'myclass)) #<standard-class> There's nothing surprising about this. The class of a myclass object is #, just like we suspected. But here's something novel, classes in common lisp are first-class objects. What's the class of MyClass? [3]> (class-of (find-class 'myclass)) #<standard-class> Interesting. What this should tell you is that the class MyClass is an instance of the class Standard Class. Do not make the mistake of thinking that MyClass is a SUBCLASS of Standard-Class! This is emphatically NOT the case! [4]> (subtypep (find-class 'myclass) (find-class 'standard-class)) NIL ; T Compare this to [5]> (subtypep '(integer 0 2) 'integer) T; T Which tells us that yes, the integer range from 0 to 2 is indeed a subtype of integers. So what's going on here? Why isn't MyClass a subclass of Standard-Class? In MOP parliance, Standard-Class is the metaclass of MyClass. You can do all sorts of wonderful and strange things using metaclasses, but let's hold off on that for a bit. The next interesting thing to find out is that the slots of a class are themselves objects. Not just ordinary places that can be SETFed, but real, full-fledged objects of their own right, with inheritance, subtyping, and metaclasses of their own. Let's explore. [6]> (class-direct-slots (find-class 'myclass)) (#<standard-direct-slot-definition>) One may wonder at the awkward verbosity of MOP, it certainly can cause hand cramps. Why class-direct-slots and not class-slots? It so happens that class-slots already exists. [7]> (class-slots (find-class 'myclass)) (#<standard-effective-slot-definition>) What gives? There's an important distinction in MOP between direct slots and effective slots. Direct slots are the objects that are created when the slot is first created. For example, A is a direct-slot in myclass. The difference comes into play when inheritance happens: instead of inheriting the slot objects themselves, copying them straight into the subclass, the MOP allows one to combine the slot definitions for the superclass and the subclass. This makes a lot of sense when you consider what happens when you have (defclass MyOtherClass (MyClass) ((a :accessor moc-a))). Remember that slot A was once accessible using mc-a. What accessor should fetch the slot value of A in MyOtherClass objects? Should it be mc-a or moc-a? Using an effective-slot-definition, you can allow both. To make this more real, let's have an example. Everyone who's used CLOS is aware that CLOS doesn't support encapsulation directly. Even if you supply no accessors for a slot, someone can always read and write the slot using slot-value. Since slot-value is a function, there's no way to override the behavior of slot-value using defmethod. But there is another way, using the MOP. Conceptually, slot-value is defined to call slot-value-using-class, which is a generic method. In many lisps, slot-value is optimized when slot-value is called on an object whose class has a metaclass of standard-class. So we'll need to make a metaclass in order to define a method that can intercept calls to slot-value-using-class. [8]> (defclass my-metaclass (standard-class) ((class-var :accessor mc-class-var :initarg :class-var))) #<standard-class> We next need a class of metaclass My-Metaclass so we can make objects to call slot-value on. [9]> (defclass my-other-class () ((instance-var :accessor moc-instance-var :initarg :instance-var)) (:metaclass my-metaclass)) #<my-metaclass> Then we can specialize slot-value-using-class. [10]> (defmethod slot-value-using-class :before ((class my-metaclass) instance slot) (print 'fetching-slot-value)) Now, make an instance and get the slot's value. [11]> (setf inst (make-instance 'my-other-class :instance-var 'hello)) [12]> (slot-value inst 'instance-var) FETCHING-SLOT-VALUE HELLO This should instantly suggest several interesting things. For example, one could replace slot-value-using-class instead of wrapping it, and thereby get computed slots! This would be useful if your class represented a database table and the slots represented columns. Suppose you had a BLOB column that you didn't want to transfer unless it was requested. By wrapping slot-value-using-class, you could fetch the BLOB if it wasn't already present. There are lots more interesting things you can do with the MOP. I'll get around to giving some more concrete and followable examples. Mostly, I wanted something to be online for googlers who had as much trouble learning about MOP as I did.