Exploring Lisp

Initial thoughts on XCVB

2009-11-15T13:07:00.001-05:00

Having struggled with the build system at work lately, I have decided to force myself to learn another build system at home: I am using XCVB for my UNIVAC emulator project.

I was intrigued by XCVB when I read about it in ILC'09. ASDF has always felt unfinished, even though it's a vast improvement over loading files manually (or using customized system definitions). However, I've run into problems with ASDF and I'm not against other options.

Some thoughts I had during the building, installation and use of XCVB:

The name needs to change. Is it possible to pick a name that is not some strained acronym? Ant. Maven. Make. These are reasonable (if not goofy) names. XCVB (and for that matter, ASDF) is just alphabet soup. Pick a word and go with it.
cl-launch feels like a whole lot of magic, but I've seen a whole lot of other magic work before.
The process of building your own systems is a bit awkward right now. xcvb make-makefile --build foo when in the directory with the build file for foo is excessive specification. Building the system is even more awkward: make -f xcvb.mk obj/foo.image. Something akin to make foo would be much nicer.
The idea of introducing metadata into a source file to indicate its dependencies doesn't sit well with some people. Personally, I like information about dependencies being close at hand; whether it comes from textual information or system queries doesn't matter. I'm content with textual information at the level of a file for now, but I suspect maintaining that information will become a pain. On the other hand, I found maintaining ASDF system definition files to be a pain (especially with refactoring and reorganization). As much as I would prefer to not use files in a Lisp system, files are a reality. I think starting with file-level meta-information is a good place to start in order find out what works and what doesn't.

Hopefully I get some time to try and help out with the project since I think it's ambitious enough to work.

Postscript to the jump-tables stuff

2009-07-19T15:19:00.001-05:00

As some commenters pointed out in my last jump tables post, my recommendation to not really worry about jump tables misses uses cases related to compiler and macro writers. It may be there are cases where hundreds (or even thousands) of cases will appear in a single conditional.

I should have been more clear in what I was trying to say: If you're writing case expressions directly (not generated), then you probably never have to worry about jump tables. That is, if you think you should take your case expression and write a jump table macro for it, you're probably wasting your time. If you are generating case expressions, you may have to consider the possibility when the number of cases is very large since the data indicates hundreds or thousands of cases does make a difference.

Of course, these measurements assumed that the case expression used elements such that a jump table was even reasonably representable (see Duane Rettig's comment). It's a relatively narrow use case, but is likely applicable to most other situations where the number of conditions is hovering around ten.

Thanks to the those who commented. It helps keep these things honest. :) (Comments are the peer review of blogging, after all.) Hopefully I'll get around to looking at some other aspects of this work soon.

SMP in Allegro CL 9.0

2009-07-16T11:13:00.001-05:00

Franz's latest tech update states that SMP is coming to Allegro CL 9.0 and recommends people work on migrating their code, since it may break things.

With this news, I must say I'm looking forward to trying out ACL 9.0.

Jump tables follow-up

2009-07-16T11:05:00.001-05:00

Based on comments from my previous post on jump tables, I decided to follow-up with a slightly more comprehensive analysis.

Below is the running time, in milliseconds, to execute a given case-style macro one million times with n branches; each execution resulted in the code taking the default case. These running times include the changes suggested by Juho Snellman (seconded by Duane Rettig) to make the times somewhat more accurate, that is, use funcall on a function object instead of a symbol.

At the request of Michael Weber, I included his ecase macro, except that has been renamed to case/tree and changed slightly to accept a default case.

A '—' means that I could not get the given use case to compile.

Jump table running times (ms)
Clozure Common Lisp 1.3-RC1		case	ncase	switch	case/tree
n	10	45	52	361	42
	100	278	51	443	68
	1000	3447	51	725	88
SCBL 1.0.29.54.rc2
n	10	54	60	222	63
	100	218	59	203	88
	1000	2029	60	222	112
ACL (free edition) 8.1
n	10	40	50	280	50
	100	40	50	270	50
	1000	4160	40	340	70
Lispworks Personal 5.1.1
n	10	43	44	288	48
	100	258	43	237	54
	1000	3064	—	277	69
CLISP 2.47
n	10	363	550	615	804
	100	390	549	693	1332
	1000	368	549	612	1898

I should point out that you shouldn't put much stock into the n = 1000 case since any case macro that uses 1000 or more cases is almost certainly pathological. Duane made this point in the comments of my previous post and I think it's important to consider. It might be tempting to say that CLISP has a "better" case macro since it has the same performance on 10 elements as it does for 1000; however, this would miss the point that most other Lisp systems are about 6-9 times faster in the vast majority of cases. Even n = 100 is probably so rare that you'd never see it in daily work unless you went digging.

Below is a bar graph of the performance of ncase, switch and case/tree relative to case. Each bar represents the relative difference for the performance of a given macro on n branches compared to case; I omitted the case of n = 1000 since I can't see it being practical. A value of 0 indicates it is equivalent to case. For example, in Lispworks, the ncase macro is 5 times faster with 100 branches than case (represented by the dark blue colour █ bar). Conversely, in Clozure CL, the switch macro is about 7 times slower with 10 branches than the case macro (the red colour █ bar).

What is clear from the graphs is that switch doesn't provide any benefits over case (when the cases are all single integer values, anyway). Also, using ncase or case/tree is of some benefit when the number of cases is large, except when using Allegro CL or CLISP. Probably the most interesting aspect is that ncase and case/tree tend to be slightly worse for small numbers of branches.

There are still some interesting questions that could be explored here (Can a compelling use case for switch be made? How often do large branch case expressions appear in actual code?), but it seems to me that jump table macros are, for the most part, of academic interest only. You can probably feel pretty confident that using case is sufficient.

Tinkering with jump tables

2009-07-12T19:11:00.004-05:00

I've often wondered whether writing a case or cond-like macro that uses jump tables is worth the effort. To get an idea as to how much I should pursue this, I decided to take Tim Bradshaw's ncase macro and pit it against case.

Tim admits that ncase is meant to show what is possible with macros and that it may be the case it may not make any performance improvement at all. Still, I think it would be interesting to compare it and see the results, simply because I really don't know what will happen.

In addition to Tim's jump table, I wrote a simple jump table implementation called switch that uses a hash table to look up the value and associates the body with a thunk; the hash table is computed with an load-time-value to minimize table creation overhead. switch has the disadvantage of performing a hash table lookup and calling a function with the advantage that the values to match can be anything you would compare with equal.

To compare the running times, I generated functions that contain 10, 100 and 1000 branches respectively (plus the default branch). This was done for each of case, ncase and switch. Each branch would compare a single integer and return that integer. For example, the body of case-100 would look something like the following.


  (case v (1 1) (2 2) ... (100 100) (t nil))

It's easy to see why I generated these function bodies with macros...

I ran each function one million times, making it hit the default case each time. The time required to run the function one million times on different Lisp systems are given below in milliseconds. These were run on a 2.16 GHZ 17" Macbook Pro running Mac OS X 10.5.7.

SBCL 1.0.29.54.rc2	`case`	`ncase`	`switch`
10	469	469	633
100	631	471	612
1000	2455	469	630
CLISP 2.47	`case`	`ncase`	`switch`
10	348	558	579
100	391	561	645
1000	375	560	571
ACL Free edition 8.1	`case`	`ncase`	`switch`
10	40	40	280
100	40	50	270
1000	4290	50	350

I was quite surprised at the results. I ran these a few times to make sure I wasn't missing something. In particular, I'm drawn to the results from CLISP. It seems lookups with case is constant. The reason this is so compelling is that SBCL and ACL are quite slow in these cases. ACL seems to be very fast otherwise.

I'll have to take a closer look at the disassembled code to see what is going on (or perhaps you can mention something in the comments if you know). Regardless, it's something that deserves some more attention.

Some notes:

SBCL took approximately 4 minutes to compile the ncase with 1000 branches. It also used up an awful lot of memory in the process. It took more than 10 seconds to compile the switch with 1000 cases.
The code I used to get these numbers can be found on paste.lisp.org.

Franz's facelift

2009-07-12T17:35:00.001-05:00

I guess it's been a while since I visited Franz's website. It appears to have gotten a serious makeover. Last I checked, it looked very 1990s-ish. It looks much better now.

I'd rank it about as effective as SBCL's simplicity and considerably better than the cluttered CLISP bucket 'o links.

Thanks to the ILC 2009 Twitterers

2009-03-25T17:40:00.001-05:00

Just wanted to say thanks to all those who posted updates about ILC 2009 on Twitter. It made me feel bad for having to miss the conference, but at least I got to keep up on what was going on.

Now, anyone up for writing a blog entry providing a little more detail?

Following ILC 2009 on Twitter

2009-03-23T05:35:00.001-05:00

Like Zach said, you can follow the updates tagged with #ilc2009. With what danbernier is posting, I'm wondering if it's the International Clojure Conference... I'm curious to see what today brings now that the tutorials are over.

CADR Emulator on Leopard

2009-03-23T05:31:00.001-05:00

I managed to get the CADR Emulator up and running on OS X 10.5; the current distribution only supports 10.4. The changes were minimal, but I'm still testing it out to make sure nothing is seriously wrong.

One thing is problematic: it doesn't like the year 2009.

I tried entering 1990 once, but it resulted in my machine locking up. I'm pretty sure it was the emulator that locked up my machine, but I don't know if the date had anything to do with it. (Since I'm not at ILC 2009 — sigh — I figured I should at least do something Lisp-y.)

Unfortunate circumstances

2009-03-19T11:19:00.001-05:00

I've recently come down with a serious eye infection and as a result, I will have to cancel my trip to ILC 2009. I'm really disappointed with this development, but I've decided to value my health over that of the conference.

The infection is in conjunction with a condition called recurrent corneal erosion. The section of eroded cornea recently expanded and managed to become infected. The pain I experienced was severe and intense. That pain has since subsided, but my vision is blurry and I have to administer eye drops frequently. I decided that travelling in this condition wouldn't be wise, especially if it were to flare up again.

I really didn't want to have to make this choice and delayed it for as long as possible. I had lots of discussions planned and was working on a couple lightning talks, but that's not going to happen now.

I thought some people would want to know in the event someone wanted to talk to me (I know I was going to track a couple people down and chat with them!). Here's hoping the conference goes well. I'll try to stay active on the forums (even though using a computer is difficult right now) and will write some blog entries in lieu of lightning talks. I'll also try to finish my UNIVAC I emulator and get it up on the web soon.

Here's hoping there's lots of blogging about the conference -- and that I don't have to wait two years for another ILC! :)

Heading to ILC 2009

2009-03-01T01:12:00.001-05:00

To get myself back into a Lisp frame of mind, I'm going to ILC 2009. I may also sign up to give a couple lightning talks since there seems to be so much space available.

My current employment involves embedded programming in Java and takes up most of my days. Still, I've managed to keep doing stuff with Lisp in my (short) spare time.

One Lisp project I'm working on that is a candidate for a lightning talk is a UNIVAC I emulator. Part of it is just for the fun of implementing an emulator, but also to experiment with self-adjusting systems.

Another project I may talk about is some stats I'm trying to collect regarding coding conventions. I think refactoring for Lisp might be well served by taking advantage of conventions. My work has consisted of basic code analysis, looking for commonalities across various projects.

Neither of these are terribly deep projects at this point, making them good candidates for lightning talks.

As for the schedule at ILC'09, there seems to be some interesting stuff. I'm wondering how much conversation will revolve around Clojure and not (Common) Lisp. I hope there is some discussion around some big, "pie-in-the-sky" topics in addition to the usual pragmatism.

If anyone feels like chatting about such things, feel free to track me down. I plan on attending as much as possible, even though Monday's schedule goes until 10 p.m. (!)

Quick thought on dynamism

2008-10-24T05:58:00.001-05:00

A recent post by Luke Gorrie got me thinking about why dynamism is useful. Having been a (paid) Java programmer for a little over three months now, I've come to appreciate a little more the static properties it offers, but grow increasingly frustrated by them. The dichotomy breaks down as follows: I appreciate the static elements for what is already built, but find them frustrating while building. Dynamism is a wonderful "genre" to work in and static is a good one to rely on. I think the interesting questions lie in the transition between the two.

Slowly working through LiSP

2008-09-02T05:49:00.001-05:00

As of Friday at around 11:30 a.m., I officially have the degree of Doctor of Philosophy. To celebrate the end of an era for me, I spent the weekend relaxing with my wife at the lake. Oh yes, and I worked through the first chapter of Queinnec's book.

Just for fun, I'm translating as much of the code to Common Lisp as I can, although continuations could prove challenging. Since it's a spare time project and I don't have the guilt of having to finish a thesis hanging over me, I don't mind. If the Scheme to CL translation doesn't work out, I'll at least have to port some old Scheme code to new Scheme code.

I should get around to posting the thesis in HTML format later this week, for those interested^*. At the very least, a PDF version will make an appearance.

^*Amazingly, a couple people have said they want to read it! One of my colleagues said recently that a good thesis should collect dust (since it is the point from which new research starts), meaning no one should read it. Here's hoping that violating this maxim doesn't mean the thesis is worthless.

Queinnec's book, at last!

2008-08-22T21:22:00.001-05:00

As a gift for successful completion of my thesis, a friend of mine gave me a copy of Queinnec's book, Lisp In Small Pieces. If I had this book earlier, I probably would have finished my thesis a lot later.

Behavioural synthesis, the (Lisp) thesis

2008-08-21T23:47:00.001-05:00

On August 18, I successfully defended my PhD thesis entitled Structuring data via behavioural synthesis. I explored the idea of deriving data structure for objects in a system by examining the behavioural aspects of a system. I did all the programming for the work in Common Lisp and did three things in the thesis to demonstrate how behavioural synthesis can work.

The first was a framework for defining data types whose instances can change their internal structure to accommodate different conditions related to their usage. This is done at the individual object level. It allows for highly adaptive objects, but incurs significant overhead. This demonstrated using limited context to control structural changes.

The second approach used this framework to expand the contexts detected. In particular, I showed how you can define data types that are the union of other data types, possibly with intersecting interfaces. By considering where an object is created in the code and what is on the system stack, code is generated to capture this context. By putting the context directly into the code, the overhead of detecting the conditions in the objects is removed.

Finally, I demonstrated a more open-ended approach that offers up some interesting future work: building class hierarchies on-the-fly. The idea is to write programs without class definitions, but still use classes and objects. I augmented a Lisp system to handle three cases: no class defined, no slot defined and no method found. Using various clues, I come up with a class hierarchy and try it out. There are various limitations to the approach (no surprise!) but it's really interesting and worth some future study. That said, there are certain conditions where it produces reasonable class hierarchies.

The external examiner on the thesis was Richard P. Gabriel, who asked some good questions and gave me some ideas with what to do next with the work. In general, I got the impression the examination committee liked the work, even though it was imprecise in some areas. There are only some minor revisions to make before officially submitting it to the university.

I'm in the process of making the code available — it needs some serious clean-up in places — along with a tech report of the work. When I have the revisions complete and its been submitted to the university, I'll post a copy of the thesis online. Some may be interested in the introduction and literature survey. (One examiner said I should look at publishing the survey.) The more ambitious can dive into the technical elements.

A Lisper's initial experience with Java

2008-07-20T08:59:00.008-05:00

I started a new job a little over a week ago wherein I have to write Java code, mostly writing tests in JUnit. I will state up front that I do not have anything against Java. I think it's a decently designed language considering when it was designed and its target audience. I should also say that I'm impressed with Eclipse. I doubt my experience with Java would be as enjoyable without it. Kudos to the Eclipse team. That said, I sorely miss the qualities of Lisp when trying to do my work.

Now, I haven't done extensive work with Java yet since I am still getting up to speed on many things at my new place of employment. Thus, it may be the case I don't know how to do certain things effectively in Java/JUnit. Still, here are some things I really miss in Lisp when moving to Java.

Special variables: Debugging in the system I'm using involves changing various static constants in classes. This is fine if you have write access to things, but when you don't or when obtaining it may cause conflicts with the version control software, it's a pain. I do not like that it is a compile-time constant. (let ((*debug* t)) ...) would be so much nicer.

CLOS and its MOP: You don't realize the power of generic functions until you don't have them. Some of the code I'm working on is old and contains, shall we say, questionable design decisions. (To be fair, the old code would never pass current code reviews, but it's now production code, so we can't change it.) Testing it is problematic because I have to extend existing (mock!) classes to get at the objects I need to examine at the right time. Adding an around method to a particular method would be much cleaner. Even better, adjusting the methods programatically while debugging would be great.

Multiple inheritance: The desire to use multiple inheritance in Java may pass as I get more accustomed to Java, but certain common methods would be better served if implemented as a mixin or something similar. Right now, there's more code repetition than there should be, in my opinion. However, it can't be factored out into separate classes very easily.

Overall, what I dislike about using Java is the inability to poke and prod a running system to learn something about how it works. Sure, you can use a debugger with breakpoints, but when an error occurs, I can't drop down to Java code and start making calls. It's the interaction that's lovely about Lisp and Java just doesn't have it in the same way. Partial information is powerful. Interacting with a failure is powerful. Being able to navigate the stack after an exception has been thrown while the system is still loaded is powerful. They are powerful because they provide information that may otherwise be hard to obtain. Instead of tracing through code, I can interact with data. The latter is considerably more productive, in my experience.

5th European Lisp Workshop

2008-07-08T07:58:00.003-05:00

I just attended the 5th European Lisp Workshop at ECOOP 2008, organized by Didier Verna. As Didier pointed out in his introduction at the workshop, it’s the third Lisp meeting in Europe in a short period of time demonstrating that Lisp is alive and well.

The workshop started with a keynote by Mark Tarver, “Lisp for the 21st century”. His basic thesis is that Lisp’s problems are mostly social and outlined ten qualities work future work in Lisp needs in order to be relevant and noticable. He then described his Qi language (pronounced “Q-I”, something I didn’t know), which brings strong type checking to Lisp. The end of his talk focussed on what he calls “computational adequacy” (one of his ten qualities) and how Qi fails in this regard. Essentially, computational adequacy means a language having enough stuff to easily get things done that people want to do. The main argument was that Lisp lags in this respect. It wasn’t as inflammatory as you might think since Mark seems genuinely concerned with Lisp.

Michael Wessel then gave a talk about descriptional logics and a way to use them in Lisp that is simpler than current approaches. I found the talk a little confusing and dense, but managed to get some clarification from Michael afterwards. He works on semantic web tools and we seem to be in agreement that multiple, specialized ontologies will probably be the norm and there need to be tools to create the ontologies, since no one wants to do it manually.

Next, Pascal Costanza and Charlotte Herzeel talked about work done by their student Leonardo Uribe with QLisp, a Lisp for the simulation of quantum computation. They went into the history of parallelism in Lisp dialects, namely CmLisp, *Lisp and Paralation Lisp, and a little on how QLisp was implemented using them. Charlotte talked a bit about adding parallelizing constructs to Lisp and why it is important. I rather liked the talk, since I considered doing work on this a couple years ago, but got onto other things instead.

After Pascal and Charlotte, I gave my talk, “Adaptive Libraries and Interactive Code Generation for Common Lisp”. I showed one way to realize a library for objects representing many types and how to evaluate code using it. Since there are ambiguities, I use interaction to resolve them and remember the context of the operation. Then I generate code specializing the use of the library using the contexts so that the ambiguities are removed and just for fun, I generate the code interactively. Didier asked for a demo, which I couldn’t give for a variety of reasons, the main one being that I didn’t have access to my code(*). Once I submit my thesis, I’ll make a demo and put the code out there. I like to think my talk went well, but I’m not the best judge of such things.

In the afternoon session, Rich Hickey presented his work on Clojure. I like what he’s done with it, especially his use of interfaces. I think I’ll play around with it for some of my work instead of trying to use Java directly. My short synopsis: Check out Clojure.

Lastly, Pascal gave a great talk entitled “make-method-lambda Considered Harmful”. It boiled down to this: make-method-lambda is a macro-like facility the depends on runtime values, so you get unintuitive results when compiling versus interpreting — sometimes. The proposed solution was to deprecate make-method-lambda and use keyword arguments to call-method in method combination. The bonus is that you can now use closures for the lambda forms of methods programmatically.

Overall, I thoroughly enjoyed the workshop and commend Didier for his efforts. The intimacy of the workshop allowed for better conversation than I have found at larger meetings. Discussions at the breaks and in the evening were enjoyable as well. My only regret is that I couldn’t stick around to attend the Dynamic Languages Symposium today; I have to head back home so I can start a new job.

As for the venue, I didn't care for Cyprus all that much. The conference website claimed it was 3 km from my hotel to the conference venue, but it's more like 5 or 6. I walked there on Monday morning and learned of the error the hard way. There was lots of garbage on the side of the road and the cab ride back from the conference to my hotel seemed excessively expensive. Drivers there seem to totally ignore the concept of a lane. I also wasn't impressed by Larnaca airport. It wasn't awful, but it isn't making me want to come back.

I'm looking forward to ILC 2009.

(*) It’s a long story, but basically, I took my wife’s laptop instead of mine and didn’t have time to get my environment up and running on it before leaving.

European Lisp Workshop paper

2008-05-29T20:00:00.001-05:00

I submitted a paper to the European Lisp Workshop at ECOOP 2008 and got notice that it was accepted! I'm glad to say that the reviewers provided constructive feedback and didn't write terse, dismissive reviews.

The paper is entitled Adaptive libraries and interactive code generation for Common Lisp and builds on some work I presented at ILC 2007. It is joint work with my thesis supervisors. The paper describes a library for an abstract data type (called a dynamic abstract data type or DADT) whose instances represent multiple abstract data types. When the code is evaluated, instances of the DADT note what operations are done to them and where those operations take place in the source code. Most importantly, when these instances are created, they note where in the code they were created.

In some cases, operations may be ambiguous, in which case the programmer is prompted to indicate which data types the operation is to be applied to. This takes place in the context of a certain place in the code and is remembered for disambiguation purposes in the future.

After the profiling information is analyzed, instances of the DADT are grouped together based on where in the code they were created and a specific type is generated for that place; the type is just a class with a slot for each structure inside the DADT instances that were actually used. Code to operate on that type is also produced.

The code generated is not inserted automatically, however (although there is no reason it couldn't be). Instead, the code is given to the editor to present to the programmer in much the same way as a macroexpansion. The reason for this is that the indicators of where in the source code things happen is actually provided by the editor and not the compiler. The reason for this was to make the changing of places less sensitive to edits. This way, the code generation scheme fits better with the usual workflow of Lisp programming.

I'm in the process of adjusting the paper based on the reviewers' comments, but here is a draft version of the one I submitted, if you're interested. I'll also post some code for this once I've submitted the final version (due July 11). I'm also putting together my thesis and gearing up to start a new job, so I'm rather busy of late.

Getting structure from behaviour

2008-04-27T09:43:00.000-05:00

Suppose you wrote the following (contrived) code snippet and tried to evaluate it.

(let ((point (make-instance 'point :xval 1 :yval 2)))
  (print (xval point))
  (print (yval point)))

Without any definition for the class point or function values associated with xval or yval, it will fail. But can you learn something useful from trying to run it? (Maybe even get it to print 1 2?)

Looking at the code, it's reasonable (but not necessarily correct!) to think that is says something like, "I want to make an instance of a class called point. Assume it has two slots called xval and yval because I tend to name the slots in accordance with the initialization arguments. And since I tend to associate accessor functions with symbols bearing the same name as the slots, the calls to xval and yval can be considered accessors."

There are an awful lot of assumptions being made here based on conventions, but in my experience, it's not really that far from the intent. So, what if the system could take advantage of these kinds of conventions to help build structural definitions based on the use of the code? That is something I find really interesting and is what I've been working on for the last little while (in addition to that whole teaching thing).

The goal I set out for myself was to build class definitions dynamically based on the use of the code. Essentially, I want to watch the execution of the code to make some reasonable guesses as to what the classes look like without having to define them ahead of time. It's a bit like programming by example, except I'm not interested in generalizing behaviour; instead, I want to derive structure from behaviour.

This presents a bit of a chicken-and-egg problem: How can you run code that relies on structure without having that structure? One answer is to make the structure as you go along. This means harvesting information from errors while taking advantage of convention and adjusting the definition of correctness.

The last point may be cringe-inducing, but is pragmatically necessary. Getting such code to be correct means defining what "correct" even means in this context. Usually, correct is taken to mean "produces the desired output". Here, the desired output is not what the program would produce given a suitable structure, but a suitable structure itself that may lead to the desired output.

Thus, we trust that what is being said as what is intended. Nothing is to be verified because we have nothing to verify against. All that can be done is to present a structure that in turn is verified by some external agent, such as the developer.

This is really a search through a very large space given some information to go on. The output produced can be put into the program text to help refine the program, but the idea of deriving structure in this manner should not be seen as a kind of operational semantics in which production code can be run on. There are just too many unknowns.

A reasonable question at this point is, "Why bother?" First and foremost, I think it's an interesting challenge and I'm curious to see how far it can be taken. More practically, if you could get reasonable structural definitions from somewhat complicated behavioural descriptions, it might be interesting to incorporate it with testing in some fashion, such as writing tests to produce programs (or significant parts of programs) that pass those tests.

This stems from my annoyance with having to write and amend structural definitions all the time during program development. (This is basically why I stopped using OCaml and its ilk in my day-to-day work.) When writing programs I tend to specify the behaviour first, then fill in the structure because the act of figuring out what I want the program to do helps me figure out what the data should look like.

Over the next few days, I'll be posting more about this, including how I've gotten it to work in a somewhat limited (although mildly interesting) context. It's just too much to put in one post. :)

Done with teaching!

2008-04-26T17:55:00.000-05:00

I spent the last three and a half months teaching a programming languages course and working on my dissertation, which is why I haven't posted much here of late. The worst part about the teaching job was that it was in a different city than my home and had an awkward schedule, so I had to commute and stay at someone else's house for the majority of the week. It also meant I couldn't make any of the Toronto Lisp Meetings.

I used Shriram Krishnamurthi's text Programming Languages: Application and Interpretation for the course, which seemed to go over well, despite difficulties. The students coming into the course are mostly exposed only to Java and C/C++, so Scheme tends to break a few brains at the beginning. I'd like to say the whole class had a firm grasp on Scheme when it was over, but I can't.

For the most part, students could write Scheme code, but it was mostly by translating (not very good) Java to Scheme. I'm not sure why. For example, there was an awful lot of this in assignment submissions:

(if (predicate? foo)
    (begin
      (set! ret-val (compute-something ...))
      ret-val)
    ...)

To say that I stressed the idea of expressions evaluating to a value and avoiding mutation in my lectures, labs and through assignment feedback would be an understatement. I'm not sure why this mindset persisted, but I hypothesize it has something to do with wanting to make the simple complex. Or maybe it has something to do with not seeing the forest for the trees. I really don't know.

I had a difficult time getting across the idea of trusting an abstraction, even when comparing to something like the APIs used frequenty in the Java libraries. For example, many students just couldn't deal with continuations without knowing what happened inside them. One even remarked he wished it had a toString method. It took a lot of convincing that seeing #<continuation> in DrScheme was basically the same thing.

Student: "But I don't know what's happening inside it!"

Me: "That's the point: it doesn't really matter."

The same symptom could be seen in trying to understand functions as values, except that I flogged the notion of closures so much that some students' brains couldn't help but give up and understand it. :)

Another thing that struck me was how, after explaining macros in Scheme, most tried to write macros as you would in Common Lisp. I expect its because CL macros let you manipulate the code directly, which fits with the theme of getting at the guts of something. Maybe there's something deeper at work here, but I'm not going to go wild in my conjectures based on this small sample.

After this class, I'm more convinced that starting with something like Scheme followed by Java would be an easier transition than the other way around. Whether starting with Scheme is easier than Java is another question entirely.

Oddly enough, they seemed to grasp Prolog pretty well...

Continuing and restarts

2008-02-19T10:53:00.003-05:00

It's been a while since I have posted anything, mostly due to the fact that I'm teaching an undergraduate course on programming languages. Since today is a new holiday (ok, yesterday, technically) in my province ("Family Day"), I actually have a little free time. That hasn't happened in a while.

Lately, I've been working on an approach to dealing with certain kinds of errors such that evaluation continues, even though it may not be entirely correct. This has me working with one of my favourite features of Lisp or any other language: restarts. Restarts are not only a wonder to behold, but provide a lot of potential. The primary reason, in my opinion, is that you can continue computation in the face of some problem that doesn't have an immediately obvious solution.

That being said, the usefulness of restarts is limited by those who provide them. In your own code, you can add restarts as you see fit, but if you want to try and recover from problems indicated by the Lisp implementation, you're at the mercy of the Lisp implementor.

What restarts are made available and when are rarely (if ever) defined in the standard. So I thought it might be worthwhile to provide a partial survey of situations and whether an implementation provides the continue restart (or something similar, such as retry) so that you can correct the situation and continue, either interactively or within a program.

Situation	Lisp implementations⁰
Situation	Allegro CL	Lispworks	SBCL	CLISP
No function defined¹	✓	✓	-	✓
Failed `function` lookup²	-	✓	-	✓
No class found	✓	✓	-	-
Division by zero	-	✓	-	-
No method found³	✓	✓	-	✓
No slot found³	✓	-	-	-
Replace function with generic function	✓	✓	✓	-
Redefine a generic function⁴	✓	✓	-	-

⁰ The versions tested were ACL 8.1 Enterprise, Lispworks 5.0 Personal, SBCL 1.0.13.53, and CLISP 2.4.

¹ Use case: evaluate a form such as (foo 0) where foo is not fbound.

² Evaluate (function foo) where foo is not fbound.

³ In these situations, it is not necessary to offer a continuable restart, since there are ways to deal with this using the MOP.

⁴ Use case: define a generic function, then evaluate some defmethod forms and make an incompatible change to the generic function definition using either defgeneric or defmethod. Alternatively, define a method without a generic function definition, then make an incompatible change to generic function.

If an implementation doesn't offer a restart for SETF functions (which usually means it doesn't offer one for function lookup), you can add your own by customizing *macroexpand-hook* to wrap the expansion in something that provides a way to continue, perhaps like the following, assuming that the (setf (foo (list 1)) 2) is replaced with the actual expanded form.

(block #1=#:BLOCK-1000
  (tagbody
     #2=#:START-1001
     (handler-bind
         ((undefined-function #'(lambda (#3=#:CONDITION-1002)
                                  (cerror (format nil "Try calling ~A again."
                                                  (cell-error-name #3#))
                                           "~A is not fbound."
                                           (cell-error-name #3#))
                                  (go #2#))))
        (return-from #1# (setf (foo (list 1)) 2)))))

Doing this for everything that is macroexpanded would be a bit much, so you should probably only do it in certain circumstances.

Currently, these are the only situations I'm concerned with. Well, almost — I threw in the division by zero one since it's a canonical example of an error.

It's hard not to notice that the commercial implementations listed offer a lot more in the way of restarts than the free ones listed. I'm sure there is a reason for this, probably related to customer demands. I will say that the restarts offered by Allegro and LispWorks have caused me to start using them instead of SBCL. Doing what I want to do in SBCL requires a lot more hackery (either changing SBCL itself or using some techniques I'd rather not use). Right now, I'm using Allegro CL Enterprise since I got an equipment grant for it with AllegroGraph, but LispWorks is looking pretty good too.

Auto-defining functions

2008-01-11T23:07:00.001-05:00

Here's a puzzle I've been playing around with lately: How would you go about defining functions automatically in Common Lisp?

Try to put out of your mind why you would want to do this for the time being (I'll make my reasons for doing so known in another post).

First of all, some definitions and ground rules. "Auto-defining a function" means that if you have code executing and an attempt to evaluate a form signals an undefined function, a function is defined for the symbol and called without interrupting the evaluation. That is to say, the debugger is not entered and execution continues.

(Yes, this is fraught with potential problems, like making a function that does what was intended. Again, I'll worry about this later.)

The hurdle in this is to be able to continue the execution. I'll take advantage of restarts to accomplish this, but it requires that the Lisp implementation supply a continuable restart at the correct time. Allegro CL does, so that's what I'll use.

The general principle can be seen in this interaction at the REPL.

  CL-USER(1): (square 5)
  Error: attempt to call `SQUARE' which is an undefined function.
    [condition type: UNDEFINED-FUNCTION]

  Restart actions (select using :continue):
   0: Try calling SQUARE again.
   1: Return a value instead of calling SQUARE.
   2: Try calling a function other than SQUARE.
   3: Setf the symbol-function of SQUARE and call it again.
   4: Return to Top Level (an "abort" restart).
   5: Abort entirely from this (lisp) process.
  [1] CL-USER(2): (setf (fdefinition 'square) #'(lambda (x) (* x x)))
  #<Interpreted Function FOO>
  [1] CL-USER(3): (invoke-restart 'excl::try-again)
  25

The above is actually possible using one of the provided interactive restarts, but the goal is to avoid interaction. The name of the restart (excl::try-again) was obtained using compute-restarts and inspecting the results, which was not shown.

To do this programmatically, you need to set up a handler for undefined-function and do the above. Again, ignoring the notion of actually building a "correct" function, there is a small problem: undefined-function only tells you the name of the function and nothing about the arguments.

Getting around this can be done using a two stage process: define a dummy function that works for any number of arguments that does the real work of defining the function. This prevents the messiness that would result from trying to get this information by inspecting the stack, for example.

For demonstration purposes, I'll only be concerned with auto-defining the square function.

(defun auto-definable-function-p (name args)
  (and (eql name 'square) (= 1 (length args))))

(defun auto-define-function-stage-one (name)
  (setf (fdefinition name)
        #'(lambda (&rest args)
            (auto-define-function-stage-two name args))))

(defun auto-define-function-stage-two (name args)
  (cond
    ((auto-definable-function-p name args)
     (setf (fdefinition name) #'(lambda (arg) (* arg arg)))
     (apply name args))
    (t (fmakunbound name)
       (error 'undefined-function :name name))))

(defun handle-undefined-function (condition)
  (when (find-restart 'excl::try-again condition)
    (auto-define-function-stage-one (cell-error-name condition))
    (invoke-restart 'excl::try-again)))

(defmacro try-undefined (&body body)
  `(handler-bind
       ((undefined-function (function handle-undefined-function)))
     ,@body))

Here it is at work.

CL-USER> (fboundp 'square)
NIL
CL-USER> (trace auto-define-function-stage-one)
(AUTO-DEFINE-FUNCTION-STAGE-ONE)
CL-USER> (trace auto-define-function-stage-two)
(AUTO-DEFINE-FUNCTION-STAGE-TWO)
CL-USER> (try-undefined (square 25))
 0[7]: (AUTO-DEFINE-FUNCTION-STAGE-ONE SQUARE)
 0[7]: returned
         #<Closure (:INTERNAL AUTO-DEFINE-FUNCTION-STAGE-ONE
                    0) [SQUARE]
           @ #x105642c2>
 0[7]: (AUTO-DEFINE-FUNCTION-STAGE-TWO SQUARE (25))
 0[7]: returned 625
625
CL-USER> (fboundp 'square)
#<Function (:INTERNAL AUTO-DEFINE-FUNCTION-STAGE-TWO 0)>
CL-USER> (square 100)
10000

This is clearly a rough implementation and only a proof of concept, but it provides a foothold for further work. I've offered no compelling reason for actually doing this; I've only shown that it is technically possible to do so. I'll elaborate on the why soon enough. (It may be a bit delayed because I've started lecturing a programming languages course and I first have to convince my students that Scheme — as foreign as it is to them — isn't as awful as they may think!)

The Revised Maclisp Manual

2007-12-17T18:11:00.001-05:00

Some fun reading for programming language history buffs: the Revised Maclisp Manual is now available on the web, care of Kent M. Pitman. Thanks Kent! Now I'll be sufficiently distracted for the next little while.

My favourite RtL survey answer

2007-11-24T09:31:00.001-05:00

From Dan Weinreb's Road to Lisp entry:

How far have you gotten in your study of Lisp? Pretty far. I am one of the designers of Common Lisp.

More code walking

2007-11-22T22:26:00.001-05:00

One of the tricky aspects to understanding and writing a code-walker is knowing how and when to expand macros.

When you are walking code, it's necessary to keep track of what is in the current lexical environment so that you know when a symbol names a function or a macro. If it names a macro, you have to call the necessary macro function.

In order to call the macro function, you have to evaluate it when you come to it. Ignoring defmacro and define-symbol-macro for the time being, you still have a bit of a problem with macrolet and symbol-macrolet.

The trouble lies in the evaluation of the macro function. To illustrate, here's an example.

(macrolet ((foo () `(print 1)))
  (foo)
  (macrolet ((bar () (foo) `(print 2)))
    (bar)))

When you walk the macro definition for foo, you have to construct the macro function for it so that it is available to the enclosed body of code. A simple way to do this is to actually call eval on the body of the macro definition, say, by creating a defmacro form and passing it to eval.

Say you do this and keep processing forms. When you get to the (foo) form, you know that foo is a macro so you expand it and substitute (foo) with (print 1). No problem there.

Now you get to the definition for the local macro bar. You still have to walk the macro definition so that you can expand the foo macro. The HyperSpec says that with macrolet, it is undefined if the body of the macro references any local variable or function bindings, but macros (local or global) must be expanded.

When I tried this code out with the arnesi code-walker under ACL and SBCL, it failed. The error it gives me is that it is trying to call a function foo. Using some traces, I found that when the macro function for bar is being defined, the lexical environment is empty. Thus, the macro function produced considers foo to be a function.

Oddly enough, ACL's code-walker (see the symbol excl::walk) gave me the same error! I don't know why yet, but it evaluates and compiles it just fine. SBCL didn't have a problem with it.

Goes to show you that writing these code walkers is tricky. And I didn't even mention anything about environment objects...

Code walking caveats

2007-11-21T18:40:00.001-05:00

As Richard C. Waters has pointed out, it often handy to have a program that can walk Lisp code to be able to analyse it. In my case, I've tried to avoid the need for a code-walker, but the time has come in my work to make use of one. (Compiler macros can only take you so far.)

There are plenty of code walking programs out there, so I'm not overly concerned with implementing it. What I'm more concerned with is idiosyncrasies across implementations.

The first one I've found is in SBCL (1.0.11.22). When you walk a DEFUN form and expand the macros, you get something that fools some code-walkers. For example,

(defun example (x) (+ x x))

eventually expands into

(PROGN
 (EVAL-WHEN (:COMPILE-TOPLEVEL)
   (SB-C:%COMPILER-DEFUN 'EXAMPLE 'NIL T))
 (EVAL-WHEN (:LOAD-TOPLEVEL :EXECUTE)
   (SB-IMPL::%DEFUN
    'EXAMPLE
    (FUNCTION
     (SB-INT:NAMED-LAMBDA EXAMPLE (X) (BLOCK EXAMPLE (+ X X))))
    NIL 'NIL (SB-C:SOURCE-LOCATION))))

The key here is the NAMED-LAMBDA part. Note that it is found within a FUNCTION form. FUNCTION is a special operator which takes either a function name or a lambda expression. The SB-INT:NAMED-LAMBDA form doesn't qualify as either, so I've got myself a classic special case particular to an implementation. (Although it is clearly a special kind of lambda form.)

The reason this is important is that I want to get at the BLOCK part which holds the body of the function. The arnesi walker (the one I've been using) doesn't walk the NAMED-LAMBDA part unless the form is a LAMBDA. On the other hand, the PCL walker does (as far as I can tell), which is what SBCL's is based on. Allegro CL's walker behaves similar to arnesi's.

So it seems that with choosing a code-walker (or writing one), I'll have to make it handle things that don't quite mesh with the HyperSpec.

Specializing object representations

2007-10-25T14:12:00.000-05:00

Using profiling information to adjust program code has been an obsession of mine lately. Ever since I started programming, I’ve been interested in program changes over time based on the program’s previous performance. Over the last few months, I’ve been working on a way to feed profiling information back to a Lisp compiler to specialize code.

Specifically, I’ve been experimenting with specializing object representations. Suppose you know that an object is of some generic type, like a sequence, but when used in a program, it is always a string. Furthermore, this information is known to some kind of profiler, which could be an external program or even part of the program itself. Lastly, the information collected by the profiler is available to the compiler. Assuming the information is reliable, the compiler could specialize the sequence object to be a string. To speed up execution, the compiler could also change operations done on the object to be specific to strings (such as changing ELT to CHAR).

Note that I am describing source level changes to the code. Also, I am assuming that the program is profiled in a comprehensive manner.

I'll quickly describe the way I've done this without delving into too many details.

Profiling

It is important to be clear about the scope of objects being specialized in this context. I decided to break down objects according to some general type. I chose to work with sets since they are non-native data types (save for treating lists as sets) and admit many possible implementations. There was a single interface used for all implementations.

The next step was to figure out the scope of those objects within the program itself. I thought that considering the entire program at once to be too broad, so I settled on only considering the places in the code where set objects are created. For simplicity, I added a function to the interface that makes set objects. I was only concerned with static calls for the time being.

The only hurdle left was collecting information that could be used by the compiler. How do you identify places in the source code to the compiler? I came up with a hack that tends to work, but that I wouldn’t count on.

I define compiler macros for the interface functions I am interested in tracking. When profiling code is to be generated, a counter is incremented in the environment of the compiler macros. The value of this counter is the identifier for the place in the source code, known as the lexical place identifier. It is reset each time the compiler is run. This relies on the compiler walking the source code in the same way each time and that no changes are made to the source between compilations.

Finally, to track information about objects, I annotate the objects themselves. Each object is tagged with the lexical place identifier of where it was created. Using the object annotations, information about the use of the object is collected into the environment of the compiler macros.

As an example, suppose the function MAKE-SET creates set objects. I define a compiler macro for it that, when profiling is enabled, takes immediate calls written as

(make-set)

and turns them into something like the following.

(locally (declare (notinline make-set))
  (let ((obj (make-set)))
    (initialize-profiling obj 1)
    obj))

The 1 here is really the value of the lexical place identifier. It would be different for each call site. The declaration is used to prevent any further invocation of the compiler macro.

Specialization

Once profiling information has been collected, the compiler is run again with specialization turned on. In order to know how to specialize the call site, the lexical place identifier is used. During profiling, each object writes information to a database keyed on the lexical place identifier. Thus, when the compiler macro goes to specialize a call, it looks up the information associated with the lexical place identifier, analyzes it, and generates code accordingly.

Using the example above, suppose analysis showed that set objects created at lexical place 1 were usually very small and that lots of them were created. This suggests using sets that are implemented as lists. The compiler macro for MAKE-SET would then produce something to create sets represented as lists at lexical place 1, such as

(make-instance 'list-set)

possibly with extra initialization arguments, such as a specific test function.

This only deals with the lexical places that create set objects directly. It is also possible to use this approach to specialize direct uses of the objects. (I’ve done this with a very general map implementation, where direct access is used when the field is known).

Caveats and stuff to do

The whole thing relies on comprehensive inputs for profiling. Obviously, there is a risk here. It also needs source code to be processed in exactly the same way for each compilation and that the source code doesn’t change. Overall, the system is a bit brittle, but it mostly works.

The hack to identify lexical places to the compiler is just that: a hack. The version I have works with SBCL and ACL, but there is an issue with LispWorks. I wanted to avoid having to write my own source analyzer and use the compiler macro mechanism instead. This allowed me to be somewhat implementation agnostic. I don’t know if it scales or not and wouldn’t be surprised if it didn’t.

ACL has an identifier in their environment objects that could be used instead of the counter. I haven’t tried it out yet, but it seems promising. Some sort of file identifier would have to be issued as well.

Currently, I only look for static calls to the interface functions. The notion of lexical places could work in a dynamic environment too, but you would have to use something other than just compiler macros.

Why?

I started out trying to implement something to model very abstract concepts (sets, maps, graphs and grammars) in such a way that the user doesn’t have to be concerned with implementation details, even more than usual. Really, I was interested in very simple interfaces.

The problem is that a single implementation is rarely appropriate for these structures. However, when an object can take on multiple representations, the overhead can be a problem and the logic is difficult to capture. So I thought it might be interesting to try and come up with ways that objects could be profiled such that either the object can change its representation or the compiler could pick one that is suitable for how it is used.

In the end, I’m aiming to build something where representation choice can be made by the programming environment for simple to moderately complex situations without any necessary user intervention and still have decent performance. Kind of like automatic memory management, but for data structures.

Finally…

The code isn’t ready for public release yet, but if anyone is interested, feel free to get in touch with me. If I can’t write it as a library, I’m thinking about integrating it into SBCL as an extension.

Always pause for reflection

2007-09-24T06:45:00.000-05:00

I caught myself doing something rather foolish last night and I thought it would serve as a nice reminder for people who fall into the same trap I did.

In short, I found myself rewriting library functions. Stupid, I know, but sometimes you get caught up in a context that doesn't have you stopping to assess what it is you're doing. I was profiling some different implementations of things and at one point I wrote

(loop for elem in list
      thereis (funcall test check (funcall key elem)))

instead of

(find check list :test test :key key)

and I was wondering why the function it was in was a bit of a laggard. (To be precise, the latter was between 6 and 7 times faster than the former!) I had my head so buried in the problem that I couldn't see the forest for the trees.

This is just further reinforcement for the notion that you should stand up every now and then and take stock of what it is you are doing.

Fixing compiler macro annoyances in Allegro CL

2007-09-16T19:49:00.000-05:00

Allegro CL is a nice Lisp implementation to use, but I recently discovered one caveat that was nearly a show-stopper for my work: compiler macros are not expanded for setf functions. This is allowed by the standard, but is frustrating nevertheless. As Willem Broekema pointed out, the lack of expansion of setf compiler macros results in some weirdness when setf is expanded and the place is a compound form that corresponds to a function with a compiler macro.

I used the past tense above because I managed to come up with a way around this for my purposes. Namely, I use *macroexpand-hook* to inhibit or expand the compiler macro functions when in a compilation environment. This is possible because ACL has environments support, which means it is possible to determine if a symbol names a compiler macro and whether it is applicable.

To inhibit the compiler macros, any compiler macro function that could cause problems is temporarily disabled when the setf form is expanded. This amounts to saving the compiler macro function and expanding the setf form in an unwind-protect.

Expanding the compiler macro function for the setf function is more involved. To properly expand the compiler macro, you would have to get the expansion of the setf form and look for the form that makes the call to the setf function. Doing this properly requires a code walker. I didn’t want to bother with that since the situations I need to deal with are specific and I’m not defining any custom setf expanders.

I took the following approach. If the setf form matches (setf (foo ...) ...) (*) and there is a compiler macro function for (setf foo) that can be applied, then disable compiler macros as above and get the expansion using get-setf-expansion. If the storing form matches (funcall #'(setf foo) ...) then expand the compiler macro for (setf foo) and use the form it returns in place of the storing form.

This solution is not suitable for all situations since it doesn’t expand forms in the correct order. Specifically, it doesn’t expand any forms that evaluate to the arguments passed to (setf foo) before getting its compiler macro expansion (these are returned by get-setf-expansion). I also didn’t bother with psetf, but that’s only because I didn’t need it.

I thought of two other ways that you could go about expanding setf compiler macros, but I haven’t thought the approaches through in great detail.

If setf calls are always of the form (funcall #'(setf foo) ...) then you could put a compiler macro function on funcall and call the appropriate compiler macro. I played with this a little, but ACL defines a compiler macro for funcall already and I’m not sure what it does.
You could define a setf expander to return a different form when in a compilation environment. I’m not convinced this is markedly different than the above approach and it would probably involve more work or be less aesthetically pleasing.

Code for this is available here with a colourized html version as well. The interface needs work, but it is suitable for my purposes.

(*) Note that (setf p1 v1 p2 v2 ...) is transformed into the equivalent (progn (setf p1 v1) (setf p2 v2) ...) before looking for this pattern.

Lisp quiz of the day: macroexpansion gotchas

2007-08-19T09:42:00.000-05:00

Suppose you want to use *MACROEXPAND-HOOK* to track something while debugging. For example, you're interested in SETF forms with the pattern (SETF (FOO ...) ...). You might decide to try something like the following. (The values returned by TRACKING-HOOK are just for demonstration.)

(defun setf-list-form-p (form)
  (and (consp form) (eq 'setf (car form)) (consp (cadr form))))

(defun setf-form-place-name (form)
  (when (setf-list-form-p form) (caadr form)))

(defun tracking-hook (expander form env)
  (if (eql 'foo (setf-form-place-name form))
      (values '(cons "Yes" nil) t)
      (values '(cons "No" nil) t)))

If you're not careful (see below) and use this directly in Allegro CL, you will have a problem. (Try to figure out why before reading on.)

To make things a little easier, try it out and see what happens. Assume we have entered the definitions for the above functions are the REPL already.

CL-USER> (let ((*macroexpand-hook* 'tracking-hook))
           (macroexpand-1 '(setf (foo 10) 10)))
Error: Stack overflow (signal 1000)
  [condition type: SYNCHRONOUS-OPERATING-SYSTEM-SIGNAL]

So, why does this happen?

This had me stumped for a while this morning until I looked at some stack traces by using BREAK at the beginning of TRACKING-HOOK. The problem will go away if you compile SETF-LIST-FORM-P and SETF-FORM-PLACE-NAME.

CL-USER> (compile 'setf-list-form-p)
SETF-LIST-FORM-P
NIL
NIL
CL-USER> (compile 'setf-form-place-name)
SETF-FORM-PLACE-NAME
NIL
NIL
CL-USER> (let ((*macroexpand-hook* 'tracking-hook))
           (macroexpand-1 '(setf (foo 10) 10)))
(CONS "Yes" NIL)
T

The problem lies in how the function is evaluated. Each call to TRACKING-HOOK results in the body of SETF-FORM-PLACE-NAME being evaluated, which results in a macroexpansion of the WHEN form. This means that TRACKING-HOOK gets called again!

Welcome to infinite recursion land.

Compiling will steer us away from this because no macroexpansion happens for the evaluation of a compiled function.

The same behaviour can be seen in LispWorks Personal 5.0.1, but not CLisp 2.4 or SBCL 1.0.8.27. SBCL wouldn't let me bind *MACROEXPAND-HOOK* to a non-compiled function. CLisp worked, but when I tried to insert a BREAK form in TRACKING-HOOK or SETF-FORM-PLACE-NAME, it would print out information on the break some number of times and start using all the CPU. I'm not sure why yet.

The moral of the story: compile functions to be called from macroexpansion hooks.

Grandstanding on a tar pit

2007-08-16T08:34:00.001-05:00

Last night I read a transcription of a panel discussion from a symposium on the role of language in problem solving wherein I found the following, care of Ben Schneiderman.

I was very strongly influenced by an article by John Platt in Science magazine in 1964 (October 10, p. 347) [subscription required]. He relates the history of primary disciplines in the 20th century, molecular biology and particle physics. He recounts how the laboratories of researchers would have on their bulletin boards or blackboards tree structures of experiments. The outcome of each experiment would determine the next experiment--very clear delineation of research plans. Yet, much of the work I see today is just an exploration, without a formal basis, without a rigorous underpinning, without a theory of human behavior, and without a commitment to an empirical approach which is based on human factors studies about how people really use different systems. I think once we move in that direction and get beyond the arguments about "my language is more user friendly than your language" and "my system is more natural than your system" &mdash whenever you hear the speakers in the next two days saying "better", "natural", "more understandable", try to ask them what they mean, what are the metrics — and only when we get to measurement do we begin to really talk about science.

[...] I think we risk being perceived by not only the general population but our colleagues and other scientific disciplines as being so much the snake oil salesmen. We may discover some tool or idea which works well for one domain, maybe it cures some people of headaches sometimes, but then we promote it as if it's the cure-all for everything. I hope for a much more rigorous and diligent approach to address what... [was] referred to as the multiplicity of tasks that users have to accomplish and the diversity of users. For me that's been the greatest encounter in becoming 20% of an experimental psychologist, in discovering how very differently individuals behave from each other and how very different they are from myself. It's a great struggle to overcome the egocentric approach that many people take towards design and to open our minds, to find out how other people work.

I found that particularly poignant given the postings in a thread in comp.lang.lisp lately (which, mercifully, seem to be subsiding). Consider what Don Geddis has to say about it.

This whole thread might have been short circuited if the static typing fans had merely said: "static/dynamic typing is a tradeoff, with the following pros and cons, and we are part of the programming community that prefers the static side of the tradeoff."

Instead of: "static typing is the future; all modern languages use it; languages that use dynamic typing are relics of the past, soon to be extinct or only used for toy scripts. But no educated, serious, mature programmer could possibly make the tradeoff that the benefits of dynamic typing are worth the cost of losing the static type checker. Only ignorant, uneducated, naive programmers believe such primitive nonsense."

(Inevitably, when a thread balloons to over 1000 messages, it becomes a Möbius strip of conversation: You get the occasional twist, but you really aren't going anywhere.)

The aforementioned thread suffers from what Schneiderman is talking about and shows why the static/dynamic typing question is worthless discussion. People on both "sides" (or just the vocal people?) make grandiose claims with no evidence to back it up, mostly because there is little to none of it in the first place.

My personal experience shows me that a lack of statically checked, strong typing has benefits in terms of program evolution, development and problem solving. Conversely, I've found that rigorous checks can be very useful when I'm clear on what it is I want to say. I cannot (and will not, although I might have when I was more ignorant than I am now) make claims about one being inherently better than the other because the metrics behind such a statement are (still) unclear. And really, my best evidence is anecdotal. Meta-analysis of what goes on in industry is the best evidence I've seen so far, and even then it's awfully wishy-washy.

For those who want do their grandstanding on a tar pit, go right ahead. People with sense and humility know that you aren't really saying much.

Amazon taketh away, then giveth back a little

2007-08-15T18:50:00.000-05:00

Amazon's decision to summarily cancel the order of Lisp in Small Pieces and the other tech books priced at $3.95 CDN irked me a little. Yeah, it seemed too good to be true, so I guess I wasn't shocked that it was "displayed at the incorrect price", as stated in their rejection letter. Still, I have a hard time believing that red flags weren't raised sooner than they were. At the very least, someone with some influence at Amazon must have heard about the story from Reddit or Digg. Maybe they didn't care to say anything.

At least Amazon was nice enough to include $10 gift certificates with the notification that my books had been cancelled &mdash well after I noticed they were removed from my order, of course. I used those to get The LaTeX Companion, but I expect that will the be last book I buy from them for a little while.

Their policy is quite clear on this, but that doesn't make the taste in my mouth any less bitter. Methinks I'll be cruising AbeBooks for my next purchases...

Lisp In Small Pieces craze may be running out of gas

2007-08-09T23:12:00.000-05:00

It looks like the Lisp In Small Pieces for $3.95 craze has met its end. The book is no longer listed with a price, nor is it listed as available, except from other sellers.

I ordered my copy yesterday. Here's hoping there aren't any problems with it.

Reflecting on development and types

2007-08-05T22:11:00.000-05:00

After teaching a course on algorithm analysis and design for over a month and having it consume most of my time, I've come back to a flurry of words that gives the impression of a discussion in comp.lang.lisp and comp.lang.functional. It has given me pause to reflect on how I approach solving my coding problems. Specifically, this paragraph from Pascal Costanza caught my attention.

If I understand correctly, people who prefer static type systems tend to think in terms of structural invariants of their programs, while people who prefer dynamic type systems tend to think in terms of their programs' behavior. I am convinced this is a personal preference, nothing more, nothing less. I guess that static typers have equal problems developing in dynamically typed languages as dynamic typers have developing in statically typed languages. I don't see a problem here: If the requirements are such that a focus on static correctness is important, it's probably better to employ a static typer, whereas if the requirements are such that dynamic flexibility is more important, the job should better be done by a dynamic typer. There is nothing wrong with specialization, we don't need a grand unified theory of program development.

My recent work has me experimenting with ways to profile data processed by programs then analyzing that data to see how it can be used to optimize those programs. Additionally, I'm exploring ways to measure the specificity (an admittedly vague term) of programs. During this time, it's been tough to ascertain just what it is I want to collect data about and how it should be stored. In the process of figuring things out, I tend to throw information into lists and hash tables just so I can take a look at it later knowing full well that I don't really know what I'm going to be dealing with. Hence it is difficult, if not impossible, for me to specify much ahead of time.

As things become clearer, I come up with more specific types and data stores within an already working framework. In short, the program I'm writing helps me to figure out how to make the program “more specific” in some sense (say, for example, I know the kinds of things that will be put into a list). But at this point, things are behaving as required and the specific types are icing on the cake.

I switched to using Lisp for my work because it fit my problem solving methodology. I started out using OCaml and appreciated the language, but I didn't really enjoy writing in it; it didn't mesh with my approach to the problem. Is this the fault of the language? Hardly, and I would never make the claim that it was. It's also silly to claim that this approach is impossible in OCaml. I just didn't like it.

My personal experience suggests that Pascal's comment is accurate.

Investigating slot access

2007-06-25T18:22:00.000-05:00

My curiosity has a way of making me check some seemingly innocuous things. I've been thinking about implementations of maps and associative arrays. Besides hash tables and association lists, structures and classes can act as maps. This got me wondering about the speed of slot access, where a "slot" is defined as a mapping of one element to another. In a hash table or association list, this is the association of an element with a key. In structures and instances (where "instance" means a direct instance of a class defined with defclass), it's the usual definition of labelling a particular element that will be accessed frequently.

I wrote a test to see the difference between these different map implementations across multiple Lisp implementations. The code I used to test access times is given below. The access test consists of setting the slot to a random number, then reading the slot and detecting some trivial condition. I hypothesized that slot access in structure instances would be slightly faster than other instances due to the lack of generic function overhead. Indirect access to class instances using slot-value would probably be similar to hash tables, which would be considerably slower than direct access.

(defstruct struct-example f0)

(defclass class-example () ((f0 :accessor class-example-f0)))

(defmacro run-access-test (creator-form accessor-form times)
  (let* ((example (gensym "EXAMPLE-"))
         (aform (substitute example '* accessor-form)))
    `(let ((,example ,creator-form))
       (format t "~%Testing ~S with ~S~%"
               (quote ,creator-form) (quote ,accessor-form))
       (time
        (loop
           repeat ,times
           do (setf ,aform (random 100))
           counting (= 0 (mod ,aform 13)))))))

(defun run-tests (times)
  (run-access-test
   (make-struct-example) (struct-example-f0 *) times)
  (run-access-test
   (make-instance 'class-example) (class-example-f0 *) times)
  (let ((slot 'f0))
    (run-access-test
     (make-instance 'class-example) (slot-value * slot) times))
  (run-access-test
   (make-hash-table :test 'eq) (gethash 'f0 *) times))

I compiled the code with default compiler settings and executed (run-tests (expt 10 7)), recording the times, not including any system time or garbage collection. The results are given in the graph and table below. To my surprise, things didn't work in quite the fashion I was expecting. The difference between direct and indirect access was narrower than I thought and there was one case where my hypothesis did not hold up.

Running times reported by (run-tests (expt 10 7)) in seconds.
Access type	SBCL	Allegro	LispWorks	CLISP
Hash tables	3.131	2.560	2.884	7.880
Indirect (using slot-value)	3.079	2.019	2.984	7.541
Direct (using :accessor)	0.837	1.530	2.240	12.423
Structure	0.624	1.200	1.586	6.927

The first thing to notice is that CLISP has awful direct access times on my setup. I ran the test several times just to be sure the result wasn't an outlier — it wasn't. The difference between direct access in instances versus structures is similar across implementations, save for CLISP; each differ by a factor of around 1.3 or 1.4 (CLISP is about 1.8). However, the difference in indirect access versus direct access varies from a factor of 3.7 for SBCL to about 1.3 for both Allegro and LispWorks. Again, CLISP is the freak in that indirect access is 1.6 times faster than direct access.

Part of the reason I'm looking into this is that I'm looking at automatic generation of representations for maps. This simple test gives me an idea as to what I should be factoring into my decisions.

In defense of LOOP

2007-06-03T11:22:00.001-05:00

Joe Marshall gives some reasons to hate LOOP and I can't say I disagree with him, save for has last point.

LOOP encourages users to think linearly, sequentially, and iteratively. They start trying to flatten everything into a single pass, first-to-last, state-bashing mess. Suddenly they forget about recursion. I've seen this happen over and over again. It literally damages the thought process.

This alludes to the old iteration versus recursion quagmire which is analogous to static versus dynamic "debates." Joe's self-professed knee-jerk reaction isn't going to get me to stop me from using LOOP, nor will it convince me to use recursion more. With both, I will use the one that fits the problem best given the context in which it is written.

Mapping over hash tables is one such example. Suppose I have a hash table whose values are lists and I want to calculate the sum of the length of all the lists. LOOP provides a succinct and clear way to express it.

(loop for list being each hash-value in htable
      sum (length list))

The MAPHASH and WITH-HASH-TABLE-ITERATOR approaches aren't quite as simple (although, admittedly, not difficult for this problem).

LOOP is also really handy for short-circuiting.

(defun first-n-things (list pred n)
  (loop with count = 0
        for e in list
        when (funcall pred e) collect e and do (incf count)
        until (= count n)))

I can't say I'm fond of the LABELS approach to the latter.

(defun first-n-things-2 (list pred n)
  (labels ((helper (elems count acc)
             (cond ((or (null elems) (= n count))
                    acc)
                   ((funcall pred (first elems))
                    (helper (rest elems) (1+ count) (cons (first elems) acc)))
                   (t (helper (rest elems) count acc)))))
    (helper list 0 nil)))

Using an &OPTIONAL parameter as an accumulator is only slightly cleaner.

(defun first-n-things-3 (list pred n &optional acc)
  (cond
    ((or (null list) (zerop n))
     acc)
    ((funcall pred (first list))
     (first-n-things-3 (rest list) pred (1- n) (cons (first list) acc)))
    (t (first-n-things-3 (rest list) pred n acc))))

Debunking the "LOOP damages the thought process" claim isn't the point here, since I don't think it was meant to be an assertion in the first place. LOOP makes dealing with state a lot cleaner when it comes up, but I agree that there is no need to use it when a simple MAPCAR will do. Sometimes recursion is messy, sometimes it isn't. Frankly, I go back forth between the two all the time, trying to find the best way to express my problem, just like I do when I'm writing. I don't always succeed, but I want to keep my options open.

Objects as functions

2007-05-30T13:55:00.001-05:00

Normally you can't apply a non-function object to another object and get a useful result (unless the error it produces is meaningful). You have to define functions that work on objects to do something with them. Sometimes this is annoying — especially when the mapping that the function represents is not fixed.

The programming language SETL has something called maps, which are sets that contained ordered pairs. A map can be applied to an object and if the object is the first element of an ordered pair, the second element (or set of them) is returned. What's neat about SETL maps is that they can be extended easily.

$ Welcome to example program land!
f := {[1, 100], [2, 200]};   $ define f
print(f(1));
print(f(2));
f(3) := 300;                 $ add the pair [3, 300] to f
print(f(3));

[woz ~] $ setl -k example.setl       # no REPL... (*sigh*)
100
200
300

There are a couple ways to add this kind of behaviour to Common Lisp, but the cleanest I've found uses CLOS and the MOP.

The MOP defines funcallable instances which allow objects to be called as functions. From the example given in the documentation, it's straightforward to build an object that acts like a map.

(asdf:operate 'asdf:load-op :closer-mop)

(defclass setl-map ()
  ((pairs :initarg :pairs :initform nil :accessor setl-map-pairs))
  (:metaclass closer-mop:funcallable-standard-class))

(defmethod initialize-instance :after ((instance setl-map) &rest initargs)
  (declare (ignore initargs))
  (closer-mop:set-funcallable-instance-function
   instance
   #'(lambda (x) (rest (assoc x (setl-map-pairs instance))))))

We can now go about making a function f that will act like the one from SETL. In order to add pairs, we'll define a setf function.

(defun f () nil)

(setf (symbol-function 'f)
      (make-instance 'setl-map :pairs '((1 . 100) (2 . 200))))

(defun (setf f) (result arg)
  (let ((setl-map (symbol-function 'f)))
    (push (cons arg result) (setl-map-pairs setl-map))
    result))

Now f is a function that we can call and add things to.

CL-USER> (f 1)
100
CL-USER> (f 2)
200
CL-USER> (setf (f 3) 300)
300
CL-USER> (f 3)
300

Implementing the definition of f (and its setf version) as a macro and adding the ability to remove pairs is left as an exercise to the reader.

Funcallable objects come in handy when you want (or need) to use a function as the interface to an object or a collection of objects. I generally use them when I need to define a mapping that changes over time and holding the mapping outside of the function would be cumbersome. They're a handy tool to have around.

Using data profiling in a running system

2007-05-23T06:37:00.001-05:00

Profiling a program usually means profiling function calls. Why not profile data? Furthermore, what can be gained by making the profiling data available at run time? I attempt to show that using profiling data at run time allows you to create adaptable data objects with, dare I say, interesting results. I also introduce some the stuff I've been working on of late.

(Note: This is a long entry.)

According to Wirth, programs equal algorithms plus data structures. Profiling programs mostly consists of watching how functions behave — and functions roughly correspond to algorithms. Given the equation, why not profile data structures as well?

The concept is not foreign. Watching data is a common occurrence when debugging in order to verify its structural integrity and the correctness of any related algorithms. This is part of the impetus behind watchpoints.

Data profiling is also done when selecting a structure to hold data. Developers make trade-offs in choosing a representation; this is part and parcel of program creation. These decisions are usually made by using abstract data types tested with different implementations.

Choosing a representation is affected by the characteristics of the data and how it is used. When little definitive can be said about these factors in advance or there is a wide range of possibilities in each, accurate analysis is important. Furthermore, it may be the case that the structure of the data should change in accordance with its usage history and current environment.

Dynamic ADTs

The difference between profiling functions and profiling data is that functions are an active agent in a computation. When a function is executed, the mechanism behind the execution provides a hook with which we can monitor a function. Data doesn't have such a counterpart — it's inert. In order to profile data, you have to associate something active with it.

Dynamic ADTs (DADTs) are something I came up with to try doing something with the idea of "active" data. DADTs are wrappers for data objects that collect profiling information and allow you to attach functionality to the objects. You associate functions (or methods) with the DADTs to provide points in a program where the information is collected and the functionality may be triggered.

Put succinctly, DADTs allow you to collect information about how an object is used and act on it.

Using DADTs, you can track the life of a data object. For example, you can count the number of times certain operations are performed on the object or monitor the subcomponents of the data (say, noting the kinds of elements added to it if the object is a container). With actions attached to the DADT object, you can adjust the object to better suit its use, perhaps by changing its representation.

A (contrived) example

While I try to avoid contrived examples, I also don't want this post to get too long or involved — something that would assuredly happen with a comprehensive demonstration. Please note that the following is demonstrative, but little else.

(defclass base-number ()
  ((number-value :initarg :number-value
                 :initform 0
                 :accessor number-value)))

(defclass silly-number (base-number) ())
(defclass dumb-number (base-number) ())

(defgeneric set-number-value (num val))

(defmethod set-number-value ((num silly-number) (val integer))
  (if (< (number-value num) val)
      (loop until (= (number-value num) val) do (incf (number-value num)))
      (loop until (= (number-value num) val) do (decf (number-value num))))
  num)

(defmethod set-number-value ((num dumb-number) (val integer))
  (sleep 1)
  (setf (number-value num) val)
  num)

There are two immediately obvious conclusions to be drawn from this code: that the example is truly contrived, and that there are certain situations where a silly number is going to be better than a dumb number and vice versa.

When the difference between the current value of a number and what it is to be set to is large, a dumb number is going to be a better representation; otherwise, a silly number is better. The difference between the current value and val parameter in set-number-value is called the delta value.

This shows the two major factors we have to consider before choosing which one to use in our program: we need to have a good idea as to the nature of the data we'll be working with and we need to know which one is going to be faster (it will vary with the architecture). If the data is likely to exhibit large delta values between the setting of numbers, then we'll pick a dumb number (even with its absurd delay). In any other case, a silly number is almost surely faster.

A DADT for numbers

Using DADTs, we can take advantage of the behavioural differences between two classes that provide the same functionality. In our example, this means we are going to switch between using a silly or dumb number when one is better than another. To do that, we define a DADT class for numbers. A DADT class does not inherit structure. Instead, it is a wrapper object that holds an instance of the type it seeks to mimic. It is also associated with other objects that collect information and act on it.

What kind of number and when?

The first step is figuring out how we detect when we want to use a silly number over a dumb number and vice versa. As reasoned above, it can be found by computing the delta value. Once we know the point at which it is faster to wait one second then set the value instead of counting up (or down) to the number, the logic behind choosing is easy. This value will be known as the delta threshold.

Computing the delta value means comparing the current value of a number to what it will be set to, which can be done by observing the parameters passed to set-number-value. Operations specifically written to work on DADTs give us access to this information through the use of triggers. Triggers are functions attached to DADT objects that are run within the context of a DADT operation. Using a trigger, we can compute the delta value and choose the number behaviour that is best suited to accomplish the operation.

The trigger we're going to use for our number DADT is going to work in the following manner.

If the current operation is set-number-value, compute the delta value. Otherwise, do nothing.
If the delta value is less than the delta threshold and the number is currently behaving as a dumb number, change the number to act as a silly number.
If the delta value is greater than the delta threshold and the number is behaving as a silly number, then change the number to act as a dumb number.
In any other case, do nothing.

Computing the delta threshold

Now we need to figure out the delta threshold. It is certainly possible to do this manually, but doing it programmatically would be cleaner. We'll use the DADT framework.

The complement to triggers are resources. Resources are simply data stores. A resource is defined by providing a class and adding methods on predefined generic functions. The methods are used to take measurements that can be stored in instances of the given resource class.

To compute the delta threshold, we can define a resource that measures the approximate run time of the set-number-value operation. The timing information is used to get a reasonably accurate value for the delta threshold. Conveniently, this isolated timing experiment can be done within our trigger and only if the delta threshold is unknown. As long as we arrange for triggers to be run before the operation (which is the default) this will work.

Dealing with performance issues

The last element of the number DADT is that of performance. DADTs can incur quite a bit of overhead and we want to mitigate it somewhat. It's unlikely we'll be able to determine ahead of time exactly what number behaviour is best for all situations, so instead we'll look at defining a reasonable heuristic.

If we were to track the history of a number object, we may find that one kind of number is better for the object that another. For example, if the average delta value for a number is less than the delta threshold, we could just ignore any attempts to change the behaviour and stick with the behaviour of silly numbers.

DADTs can achieve this using directives. Directives are a rudimentary form of memory for DADT objects. There are standard directives that can be used to indicate whether the extra work of collecting and using information on a DADT object is done. Note that this is at the individual object level (although it can be applied globally).

In order to "optimize" a number DADT object, we'll assume that if the object has had its value changed N times and hasn't changed its behaviour, then it will be configured to keep that behaviour, that is, stabilize it. This will be done through another trigger.

Summary

In summary, to define the number DADT we will define a DADT class for numbers whose instances will behave as either silly or dumb numbers. The operations for these numbers will be number-value and set-number-value. A trigger will change the behaviour based on the delta value for the set-number-value operation; the delta value is also computed by the trigger when necessary. A resource will be attached to each number DADT object that keeps track of the number of times the value of the number has been changed. Another trigger will use this information to stabilize it when the conditions for doing so have been met.

The DADT in action

I will preclude going through the code to define the DADT because it is too lengthy for this post (which is long enough as is). The code is available, for those who want to see. (The following was done one a 2.16 GHz Intel Core Duo using SBCL 1.0.5.25.)

For starters, let's take a look at what a number DADT object looks like. (Information irrelevant to the present discussion has been omitted.)

DNUMBERS> (describe (make-dnumber))
#<DNUMBER rep: SILLY-NUMBER {11C9EDD9}>
is an instance of class #<DYNAMIC-ADT-CLASS DNUMBER>.
The following slots have :INSTANCE allocation:
 REP                 #<SILLY-NUMBER value: 0  {11C9EE01}>
 LOCAL-TRIGGERS      (CONVERSION-TRIGGER STABILITY-TRIGGER)
 RESOURCES           (#<CHANGE-COUNTER {11C9EE21}>)
...

Note that a dnumber has the behaviour of a silly number by default. We can see that it has two triggers (the functions conversion-trigger and stability-trigger) and an instance of change-counter as its only resource object.

At this point, the delta threshold has not been computed. When setting a dnumber to a value, it will be computed if it hasn't already.

DNUMBERS> *delta-threshold*
NIL
DNUMBERS> (set-number-value (make-dnumber) 1)
#<DNUMBER rep: SILLY-NUMBER {1277C3C1}>
DNUMBERS> *delta-threshold*
9872727
DNUMBERS> (time (set-number-value (make-instance 'silly-number)
                                  *delta-threshold*))
Evaluation took:
  1.011 seconds of real time
  1.007832 seconds of user run time
  6.63e-4 seconds of system run time
  0 calls to %EVAL
  0 page faults and
  0 bytes consed.
#<SILLY-NUMBER value: 9872727  {12848CC9}>

We can see that the delta threshold is reasonably accurate.

Now we want to compare dnumbers to silly and dumb numbers. We'll do this by creating an instance of a number and assigning it a series of values. These values should cause the delta value to cross the delta threshold occasionally. The second result below tells us what behaviour would be best when setting a number based on its previous value (starting at 0).

DNUMBERS> (defparameter *test-numbers*
            (loop repeat 50
                  collect (random (* 10 *delta-threshold*))))
*TEST-NUMBERS*
DNUMBERS> (let ((curr 0))
            (mapcar
             #'(lambda (n)
                 (prog1
                     (if (<= (abs (- curr n)) *delta-threshold*)
                         'silly
                         'dumb)
                   (setf curr n)))
             *test-numbers*))
(DUMB DUMB DUMB DUMB DUMB DUMB DUMB DUMB SILLY SILLY
 SILLY DUMB DUMB DUMB DUMB SILLY DUMB DUMB DUMB SILLY
 DUMB DUMB SILLY SILLY DUMB DUMB SILLY DUMB DUMB DUMB
 DUMB DUMB DUMB DUMB SILLY SILLY DUMB DUMB SILLY SILLY
 DUMB SILLY SILLY DUMB DUMB DUMB DUMB SILLY DUMB DUMB)

When we set a dnumber to the test numbers, we should see 19 conversions: one for each transition in the list (which accounts for 18) and one more because — can you guess? — a dnumber starts out as a silly number.

DNUMBERS> (defun run-test (num)
            (time
             (loop for n in *test-numbers*
                   do (set-number-value num n))))
RUN-TEST
DNUMBERS> (progn (run-test (make-instance 'dumb-number))
                 (run-test (make-instance 'silly-number))
                 (run-test (make-dnumber)))
Evaluation took:
  50.006 seconds of real time
  ...
Evaluation took:
  153.342 seconds of real time
  ...
Converting #<DNUMBER rep: SILLY-NUMBER {122CC261}> to DUMB-NUMBER
Converting #<DNUMBER rep: DUMB-NUMBER {122CC261}> to SILLY-NUMBER
Converting #<DNUMBER rep: SILLY-NUMBER {122CC261}> to DUMB-NUMBER
Converting #<DNUMBER rep: DUMB-NUMBER {122CC261}> to SILLY-NUMBER
Converting #<DNUMBER rep: SILLY-NUMBER {122CC261}> to DUMB-NUMBER
Converting #<DNUMBER rep: DUMB-NUMBER {122CC261}> to SILLY-NUMBER
Converting #<DNUMBER rep: SILLY-NUMBER {122CC261}> to DUMB-NUMBER
Converting #<DNUMBER rep: DUMB-NUMBER {122CC261}> to SILLY-NUMBER
Converting #<DNUMBER rep: SILLY-NUMBER {122CC261}> to DUMB-NUMBER
Converting #<DNUMBER rep: DUMB-NUMBER {122CC261}> to SILLY-NUMBER
Converting #<DNUMBER rep: SILLY-NUMBER {122CC261}> to DUMB-NUMBER
Converting #<DNUMBER rep: DUMB-NUMBER {122CC261}> to SILLY-NUMBER
Converting #<DNUMBER rep: SILLY-NUMBER {122CC261}> to DUMB-NUMBER
Converting #<DNUMBER rep: DUMB-NUMBER {122CC261}> to SILLY-NUMBER
Converting #<DNUMBER rep: SILLY-NUMBER {122CC261}> to DUMB-NUMBER
Converting #<DNUMBER rep: DUMB-NUMBER {122CC261}> to SILLY-NUMBER
Converting #<DNUMBER rep: SILLY-NUMBER {122CC261}> to DUMB-NUMBER
Converting #<DNUMBER rep: DUMB-NUMBER {122CC261}> to SILLY-NUMBER
Converting #<DNUMBER rep: SILLY-NUMBER {122CC261}> to DUMB-NUMBER
Evaluation took:
  41.465 seconds of real time
  ...
NIL

The timing for dumb numbers isn't surprising, but silly numbers demonstrate how horrible they are for large delta values. The dnumbers manage to shave about 8.5 seconds off a dumb numbers' time and the expected conversions took place.

And how about the stability notion? We'll set the N value mentioned earlier to 100 and see what the results are versus a "plain" silly number, a dnumber with the heuristic and a dnumber without the heuristic.

DNUMBERS> (let ((num (make-instance 'silly-number)))
            (time
             (loop repeat 10000
                   do (set-number-value num (random 100)))))
Evaluation took:
  0.039 seconds of real time
  ...
NIL
DNUMBERS> (let ((num (make-dnumber)))
            (time
             (loop repeat 10000
                   do (set-number-value num (random 100)))))
Stabilizing #<DNUMBER rep: SILLY-NUMBER {11CAF209}>
Evaluation took:
  0.041 seconds of real time
  ...
NIL
DNUMBERS> (let ((num (make-dnumber)))
            (delete-local-trigger num 'stability-trigger)
            (time
             (loop repeat 10000
                   do (set-number-value num (random 100)))))
Evaluation took:
  0.104 seconds of real time
  ...
NIL

The heuristic may not be perfect, but it does make a big difference.

Of course, this example is grossly oversimplified. For one thing, dumb numbers and silly numbers have the same structure, so conversion between the two is very cheap. Notice how the address of the internal representation of the dnumber didn't change? That's because change-class is used to actually convert between dumb and stupid numbers. In most cases, this isn't going to be the case. Normally, we would have to take into account the cost of converting between different representations in order to achieve the behavioural change for the DADT object. (The complexity of doing so is why I chose such a contrived example.)

That's cute, but what's the point?

This is all well and good, but the common objection to such things is that it has little to no practical value. To some extent, sure. In a production system built for speed, this kind of construct is of dubious use. But if you look at the entire process of building such a system, they could come in handy.

The act of programming is a process that involves the specialization of concepts. Developers start out with a description of concepts which get realized in some particular fashion. Along the way, they may find that one implementation may not capture a concept adequately; multiple implementations of the same concept may be needed. Furthermore, a concept may not map neatly onto one particular realization so it is spread across different interfaces. What DADTs try to do is capture the essence of a concept without including the code to manage interactions between different implementation elements directly.

In short, DADTs provide a way to express the concept before is becomes specialized. During development, this could be useful in employing concepts before deciding on specializations. DADTs can even be used to determine specializations themselves — the stability trigger given above is a simple example.

Observation and adaptation are integral to the process of feedback. I am fascinated by what feedback can do for software and software development; arguably, it's necessary. Dynamic ADTs are my humble effort to see where it can lead.

Human and computers probably shouldn't trust each other

2007-05-22T21:45:00.001-05:00

Digging through the archives of computer science history can reveal some really interesting stuff. Take the paper Social Processes and Proofs of Theorems and Programs (pdf), recently discussed on Lambda the Ultimate.

The gist of the paper is that program verification is a red herring and resources dedicated to verification are probably misspent. After arguing that proofs only get used when they are believed (and that a proof by itself is not enough to express truth), the meat of the argument is reached.

There is a fundamental logical objection to verification, an objection on its own ground of formalistic rigor. Since the requirement for a program is informal and the program is formal, there must be a transition, and the transition itself must necessarily be informal. We have been distressed to learn that this proposition, which seems self-evident to us, is controversial. So we should emphasize that as antiformalists, we would not object to verification on these grounds; we only wonder how this inherently informal step fits into the formalist view. Have the adherents of verification lost sight of the informal origins of the formal objects they deal with? Is it their assertion that their formalizations are somehow incontrovertible? We must confess our confusion and dismay.

I have a hard time disagreeing with this observation. I'd love for verification to be practical, but I just don't buy it due to the human factor.

There is also a good discussion of continuity. Formalists argue that programs are nothing more than algorithms and model programs. The authors don't buy it.

It is with (2) [programs being nothing more than algorithms and model programs] that we have our fundamental disagreement. We argue that there is no continuity between the world of FIND or GCD and the world of production software, billing systems that write real bills, scheduling systems that schedule real events, ticketing systems that issue real tickets. And we argue that the world of production software is itself discontinuous.

One of the reasons I'm not enamoured by verification is that even if my program were verified, I still wouldn't trust it. I'd feel compelled to test it and check in on it at regular intervals to make sure it was working. After all, I had a hand in making it (what does that say?) and a computer informed me that I was doing fine. Would this verification save me any time during my regularly scheduled scrutiny? I have my doubts.

The paper is rife with food for thought and refreshing perspectives, even though it was published 28 years ago. I highly recommend it.

The static/dynamic albatross

2007-05-13T19:23:00.001-05:00

Nothing strikes me as more pointless than the static/dynamic typing argument in the programming languages community. So much time has been wasted on this topic that it almost brings a tear to my eye.

That being said, there are sometimes diamonds in the perennial rough. These quotes are representative of my views on the matter.

Two from Kent M. Pitman in the c.l.lisp thread Does ANSI Common Lisp have pattern matching?.

Language choices are not about Good vs Bad, they are about design trade-offs: you trade away the things you don't plan to do in favor of the things you do plan to do. The hard part is getting that planning right so you aren't pinned into a corner down the line. Since Lisp supports changing one's mind later, I tend to like that, but it comes at some occasional costs, and I think there's a minor but manageable cost on the issue of clarity of intent on certain intentional type issues. It's not a cost that troubles me because it buys other things I care about. Static typing feels like a stranglehold to me. But it's worth acknowledging that there are people who will be troubled by these design trade-offs because they value things differently.

and

The static/dynamic thing was not done as a way of saying, as a community, "we're too lazy to do things up front where they belong". Rather, we as a community have said "we want to first choose what we want to say, and when the right time is to say it, and only after that is done will we see about making that maximally efficient".

Read the posts here and here.

Next, Anton van Straaten has a comment over at Lambda the Ultimate.

I'll state for the record that I don't like what I see as a false dichotomy in the static/dynamic debate — what I'm really looking forward to in the future is a more sophisticated attitude towards types from both camps. Dynamic advocates who see absolutely no benefit to static checks are missing the fact that the programs they write are full of static types which they actually reason about, even if they don't realize it; but static advocates who think that a universal type encapsulates everything there is to know about dynamic languages are, funnily enough, missing the exact same point. (emphasis his)

I'm sure there will be plenty more rough of this nature in the future. I at least hope that diamonds keep coming with it.

Wrapping code using compiler macros

2007-05-09T01:15:00.000-05:00

Macros are probably my favourite thing about Lisp. They were the reason I started using Common Lisp and I do a lot of work with them. I guess I like manipulating programs, but I don't want to write new compilers.

Recently, I've been looking for ways to take an existing function definition and replace each occurrence of it in some source code that wraps the call to set up a specific environment. Furthermore, I wanted to avoid the need to actually change the source code. I thought it would be nice to share the way I went about doing this. (Hey, that's what blogs are for, right?) Plus, it gives a nice demonstration of what compiler macros are and how they work.

The problem

For demonstration purposes, here's a simple function definition that we'll use throughout.

(defun example (x y) (* x x y y))

The goal is to wrap each occurrence of example in the source code with code that will keep a history of the second argument. That is, throughout the entire program, we want to remember all the values that were passed as the second argument.

There are certainly other ways to do this (using around methods, for example), but for the sake of illustration, we'll ignore them.

Ultimately, we want to turn this

(example x y)

into something like this

;; You only want to evaluate the second argument once.
(let ((tmp y))
  (add-value-to-history tmp)
  (example x tmp))

A solution using compiler macros

Recall that compiler macros are macros that are applied only during compilation. Although it is optional for an implementation to apply them, I'm going to assume that the implementation does.

One very important property of compiler macros is that if the same form to be expanded is returned, no expansion is done. This is in contrast to regular macros in that they must always provide an expansion that is not the same as the form to expand lest you end up in an infinite loop.

How can we take advantage of this? The idiom for this is to insert a macro into the enclosing lexical environment and decline to expand the form if the macro is present in the environment.

(defparameter *value-history* nil)

(defun add-value-to-history (val)
  (push val *value-history*))

(defun expands-in-environment-p (form env)
  (second (multiple-value-list (macroexpand-1 form env))))

(define-compiler-macro example (&whole form x y &environment env)
  (if (expands-in-environment-p '(%foo%) env)
      form
      (let ((tmp (gensym)))
        `(macrolet ((%foo% () t))
           (let ((,tmp ,y))
             (add-value-to-history ,tmp)
             (example ,x ,tmp))))))

We can try it out to see if it works as advertised.

CL-USER> (funcall (compiler-macro-function 'example)
                  '(example 1 2)
                  nil)
(MACROLET ((%FOO% NIL T))
  (LET ((#:G177 2)) (ADD-VALUE-TO-HISTORY #:G177) (EXAMPLE 1 #:G177)))
CL-USER> (macrolet ((%foo% () t))
           (macrolet ((check (&environment env)
                        `(quote ,(funcall
                                   (compiler-macro-function 'example)
                                   '(example 1 2)
                                   env))))
             (check)))
(EXAMPLE 1 2)

Note that the second example sets up the environment so that the compiler macro doesn't expand the form. We use the check macro so that we can get an environment object to pass to the compiler macro function.

We're not quite done yet. The next step is to recompile the code that uses example. Remember, compiler macros are only expanded by the compiler, which means simply running code that uses example isn't enough.

(defun foo ()
  (loop
     repeat 10
     for i = (random 100) and j = (random 100)
     collect (example i j)))

Now we'll test to see if everything is working.

CL-USER> (foo)
(10890000 5793649 14561856 7617600 327184 33918976 980100 3418801
 467856 2509056)
CL-USER> *value-history*
NIL
CL-USER> (compile 'foo)
FOO
NIL
NIL
CL-USER> (foo)
(944784 2446096 659344 49702500 0 792100 13924 19377604 15023376 290521)
CL-USER> *value-history*
(77 51 62 59 10 0 94 28 17 12)

Excellent!

It turns out there is an even easier way to prevent recursive expansion of compiler macros. According to the HyperSpec, if a function name is declared as notinline and the call appears within the scope of this declaration, then the compiler macro is not applied. Our compiler macro gets a little simpler.

(define-compiler-macro example (&whole form x y)
  (declare (ignore form))
  (let ((tmp (gensym)))
    `(let ((,tmp ,y))
       (declare (notinline example))
       (add-value-to-history ,tmp)
       (example ,x ,tmp))))

Subtleties

Above I used a call to compile to compile foo, but that only worked because foo wasn't a compiled function yet. If you redefine the compiler macro, you have to recompile everything. Unfortunately, there isn't a way to recompile an already compiled function without re-evaluating its definition. Thus, my presentation of compilation is simplistic. Since I do most of my Lisp coding in an IDE of some form (Slime, Allegro, LispWorks), recompilation isn't usually a big deal. In the future, I may look into a way to use asdf to make it a little easier.

Technorati Tags: lisp, macros

A different place to post my Lisp stuff

2007-04-18T00:25:00.000-05:00

I've decided to move all my Lisp related posts to here instead of my usual blog. This is mainly for the benefit of friends and family who don't care about Lisp stuff.