a CONS is an object which cares

WebRTC and the File API

2012-01-24T19:24:00.000-07:00

Two interesting developments in HTML5 I've recently been made aware of are WebRTC (thanks to Manuel Simoni) and File API (thanks to Rich Jones). The RTC part of WebRTC stands for Real-Time Communications, but it's basically a way to provide TCP/IP sockets for a web browser while pretending you're not providing TCP/IP. The top-layer part consists of various video and audio codecs, but the basic gist is a way of providing a bidirectional channel for web browsers to communicate with each other. This is accomplished with NAT traversal in mind (the functionality for traversing NATs and proxies in the reference implementation is provided by the very handy looking libjingle library that seems to do most of the common NAT traversal tricks).

One obvious use of WebRTC is providing audio and video chat in webpages without Flash (WebRTC specifies audio/video input, real-time codecs, and jitter buffers). Another obvious use is to develop a BitTorrent-like distribution protocol for videos; something like this should really cut down on YouTube's bandwidth bills.

The File API provides the potential to use WebRTC for any kind of P2P file sharing. This is I think the most exciting potential of WebRTC.

To step back in terms of commentary, the web browser has now come full circle to being a very weird virtualized operating system, whose APIs rival Windows in size, idiosyncrasies and complexity. The need for application hosting declines - both the application and "putting your data in the cloud" can now be handled by a Freenode or Tahoe-LAFS-like WebRTC library. What's interesting is that friction surrounding development and deployment should push new web applications away from a centralized server and towards the P2P approach. Unlike fully hosted apps, there is no extra effort involved in making an offline version. Server rent/lease and administration costs are reduced considerably by offloading as much data storage and computation as possible onto the browser. This latter possibility in particular should enable many startups to avoid the capital requirements needed for scaling up services that depend on the network effect, such as most "social" things. I don't like to use buzzwords, but this looks to be disruptive.

Hollywood Mob

2012-01-22T18:05:00.000-07:00

The shutdown of MegaUpload and arrest of Kim Dotcom and several MegaUpload employees has been a big news item this week. The event demonstrates one thing: all you have to do is admit that your service can maybe, possibly be used to infringe on copyrights owned by members of the RIAA or MPAA for your company to be shut down, yourself arrested and all your assets seized.

The tactics of the RIAA/MPAA mafia ("essentially the cultural arm of the United States") are akin to suing the postal service and manufacturers of cardboard boxes for making it possible for people to receive counterfeit goods. The intimidation is aimed at all strata of online individuals and organizations: viewers of audio/video, hosting services, and software developers.

I have observed before that the actual business of the RIAA/MPAA members has nothing to do with audio or visual production, but is all about controlling distribution. The goal of the ongoing intimidation is to prevent innovation in distribution channels, and force viewers/hosts/developers to conform to the single distribution model authorized by RIAA/MPAA, regardless of whether any copyrights owned by members of the RIAA/MPAA are actually involved or not.

An interesting observation is that the RIAA/MPAA doesn't actually know what that distribution model is supposed to be. They are content to do business as usual selling plastic discs (all the while attempting to lock out smaller content producers and distributors with initiatives such as Macrovision, CGMS-A, CSS, ARccOS, SDMI, CPRM/CPPM, Sony rootkit CDs, AACS, Trusted Computing, UEFI (in an unholy alliance with Microsoft), PlaysForSure, HDCP, COPP, PMP, DVB-CPCM, FairPlay, OpenMG, etc.), and pretending that the ol' innertubes is a regional on-demand cable network (Netflix, Hulu, Spotify). Selling singles on iTunes (regionally restricted, of course) is about as innovative as the RIAA/MPAA members have dared to get in online distribution.

The arrest of Kim Dotcom has parallels to the 2004 arrest of Isamu Kaneko, author of the Winny file sharing program.

I am a card-carrying member of the Pirate Party of Canada. Given all the above observations and my previously expressed opinions on the futility and negative consequences of online copyright enforcement, I believe it's not safe for me to head up a project one of whose possible uses is to distribute files at the current time.

On the other hand, I have gotten really interested in research around F2F overlay networks and cryptographically-enabled online privacy, so expect me to write more about that.

Upcoming presentation about Parenscript

2012-01-18T17:06:00.001-07:00

I'm going to be giving a talk about Parenscript to the Montreal Scheme/Lisp Users Group on Thursday, January 19 (meeting details here).

The slides I'm going to be using are here, and a list of links referenced in the talk is below. The last time I gave a presentation on Parenscript was to LispNYC in 2007. Parenscript has received a huge number of changes and improvements since then, and continues to be the best language/compiler to JavaScript and one of the best tools available for web application development. What's also new since 2007 are libraries and tools that extend Parenscript: Red Daly has added CLOS and the Common Lisp condition system to JavaScript as a Parenscript library, and there are now several options for interactive development with SLIME in your browser.

Links:

Compiling by simplifying

2012-01-17T19:39:00.001-07:00

When you read the original Lambda Papers carefully, one thing you notice is that Steele didn't view Scheme as just a programming language, but also (and I would argue, primarily) as a philosophy of constructing compilers.

This philosophy made clear and transparent the issues of translating a high-level language into Von Neumann-style register machine code, and provided mechanisms to radically simplify the transformation. Continuation-passing style reified issues of control transfer, temporary stack values, and register use. Function arguments become registers, function calls - jumps. Difficult issues like nested scopes, first-class functions, closures, and exceptions become easy.

The other great, simplifying thing about Steele's philosophy is the self-similarity of the code as it undergoes transformation. The input of each stage of the compiler is a Scheme program, and (until machine code generation), the output is a simpler Scheme program.

Many compilers miss out on the self-similarity aspect of Scheme in two major ways. Those compilers that do follow continuation-passing style usually implement the CPS portion of compilation using completely different data structures than the other portions. This adds needless boilerplate code and makes the CPS portion look more complicated than it is. This needless complexity shows up in some ML compilers - in particular, Andrew Appel's otherwise excellent and highly recommended Compiling with Continuations, and causes people to remark that implementing SSA is not all that much harder than doing CPS (Olin Shivers disagrees).

The subtler, but even more serious omission is ignoring Steele's advice to implement the parts of the language above the intermediate layers as macros. This spreads the complexity for implementing features like classes and objects throughout the different portions of the compiler, starting with the parser.

Following Steele's techniques, building a Scheme compiler that is several times faster (and many times smaller) than the compilers/virtual machines of popular dynamic languages like Python and Ruby is easy. Scheme 48 was originally written in 48 hours. If you don't have that much time, Marc Feeley can show you how to build a Scheme compiler in 90 minutes. And if you're really strapped for time and don't want to sit through CPS theory, Abdulaziz Ghuloum shows you how to dive right into generating x86 machine code in 10 pages.

The personal computer you've never heard of

2012-01-11T12:53:00.002-07:00

I was watching Dan Ingalls' Seven (give or take) Smalltalk Implementations talk given at Stanford in 2005 on YouTube, and around the 43 minute mark Ingalls talked about something I consider shocking:

In 1978*, a year after the introduction of the Apple II, Xerox PARC built a portable computer with a 7 inch, 640 by 480 resolution bit-mapped, touch-screen display based around a commonly available 1 MHz, 16-bit microprocessor with 128 KiB** of memory running Smalltalk-76. The computer was called the NoteTaker.

The NoteTaker ran Smalltalk as fast as the Alto (the Smalltalk-76 VM (6 KiB) actually executed bytecode twice as fast on the 8086 as on the Alto, but the memory bus was much slower, making interactive performance feel similar).

I always thought the 8086 was extremely underpowered and good only for DOS and terminals. In hindsight, it's mind-boggling how long it took x86 PCs to catch up with the Macintoshes and Amigas of the 1980s.

* Note that Wikipedia and other sources give the NoteTaker's date as 1976, but this is likely the date when design started, as the 8086 design also just started in 1976 and the processor did not ship until 1978. The NoteTaker manual is also dated December, 1978.

** The NoteTaker manual specs the machine at 256 KiB of memory.

*** The current Wikipedia article about NoteTaker claims this computer would have cost more than $50,000 if sold commercially (presumably in 1978 dollars). Assume that the CRT, floppy disk, power supply, keyboard and mouse cost $2,000 (a whole Apple II system with 4 KiB memory retailed for $1,298.00 in 1977). The 8086 originally wholesaled for $360. According to the NoteTaker manual, the NoteTaker had a second 8086 which acted as an I/O processor but was "also available for general purpose computing tasks." It would have been entirely possible to replace the I/O processor with a much cheaper CPU. Looking again at Apple's price list, a 48 KiB Apple II board retailed for $1,938, while a bare-bones 4 KiB one sold for $598, which gives $31 per KiB. So 128 KiB would retail for $3,900 and 256 KiB would retail for $7,800. It certainly would have been possible to produce and maybe even sell the NoteTaker with 256 KiB of memory for less than $15,000. Note that a few years later, Kim McCall and Larry Tessler made a subset of Smalltalk-76 that ran in 64 KiB of memory, but with the full system image only about 8 KiB of memory was available for user programs.

**** The NoteTaker also came with an Ethernet interface.

PS - While researching this article, I also stumbled on another PC you've probably never heard of. The Kenbak-1, similar in operation and capabilities to the MITS Altair 8800 (both came with lights, toggle switches, and 256 bytes of memory), was sold via advertisements in Scientific American for $750 in 1971, four years before the Altair.

What is ClearSky going to look like as an application?

2012-01-11T11:04:00.000-07:00

ClearSky is going to have to be as simple as possible to use. Facebook-level simplicity. The only unavoidable extra requirement is that the node software is going to have to run as a binary on your own computer. The installation process needs to consist of just downloading a single binary. Once you have it, no more extra installation steps.

The first time the binary is run, it opens a web browser pointing to a page that asks you to choose a nickname and password (the binary will have a web server to present the local interface). In the background, it's going to generate a private/public key pair and set up the filesystem directory where you store data for that account. After that, it will let you look up friends online. I'm undecided about how this step will work. There are a lot of alternatives for federated, centrally located directories: just build a web one, XMPP (integration with chat seems like a good idea), IRC, etc. I don't know a lot about how the distributed options work, but they are out there and seem to work ok (Freenet, GNUnet, etc.). It seems like a good idea to make this part modular, but present it behind a consistent and easy to use interface.

The binary will provide an HTTPS port to the outside world to let your friends log in remotely (see previous discussion). If you're behind a NAT gateway, it's going to take some extra work - both the NAT-PMP and IGD protocols will need to be supported.

In general, UDP hole punching needs to be present to let two ClearSky nodes talk to each other, although it alone is not enough to provide remote logins from the outside. UDP hole punching needs an accessible third party to be present - using either a friend's computer that has an unrestricted connection, or a central server if no such friends are available. Using unknown third parties is problematic because it relies on either volunteers (every ClearSky client can be a volunteer, but this opens up possibilities for surveillance) or your mirror provider.

All traffic between you and your friends goes over SSH. Messages and files are cryptographically signed to ensure authenticity, but encryption during transport is provided by SSH. The ClearSky client should encrypt data before writing it to disk to ensure privacy even if the hosting computer gets lost or stolen.

Apps are going to be started in a separate process (via fork(), or by running the same executable with different options) for extra security, stability, and to let the OS handle resource control. Games, content libraries, chat, voice, calendars etc. are all possible apps. One example app that could be built but that's not possible with Facebook is a Tahoe-LAFS that would let you trade harddrive space with your friends to securely and redundantly back up your private data.

Apps will communicate with the ClearSky process via sockets and the file system. Security is going to be provided by language-level virtualization. The app runtime will prompt the user when the app wants to access filesystem folders or other resources. Things like video and audio will ideally be handled by HTML5, if not then by Flash. It's undesireable to have the app display native UI or use the OS multimedia or other capabilities directly - this shouldn't be included in the platform unless there's a good concrete demonstration that it's needed. OTOH, having an app be able to manage its own sockets may be a good idea.

Common Lisp is a good language/runtime to base the ClearSky platform on. A Common Lisp binary can run all the basic ClearSky functions (web server, crypto, discovery, networking, SSH) in the same process, provides excellent support for language-level virtualization (and of course already comes with a compiler), and has very good support for hosting and virtualizing other programming languages - of the popular scripting ones, CLPython and CL-JavaScript are currently available, and new ones are easy to implement: CL-JavaScript was written by 3 people (Alan Pavičić, Marijn Haverbeke, and Iva Jurišić), CL-Python by just one person (Willem Broekema).

Payment for hosting and mirroring

2012-01-09T13:04:00.002-07:00

Having a purely p2p private messaging and file sharing network works up to a tradeoff between the number of nodes, the aggregate average availability and bandwidth of all nodes, and the file sizes being shared. The larger a p2p network becomes, the less trusted and private it's going to be. But for example a torrent with a small number of seeders with low upload speeds doesn't work very well for huge files.

It would be nice to share a large number of large files securely with your friends over a high-bandwidth link. As well, having a reliable server on a high-bandwidth link would make replication and backup of your data more convenient.

A large number of companies offer storage services that can do that. Dropbox is the most popular, but it doesn't provide convenient sharing features because it focuses on replicating and syncing your private files. Ubuntu One is similar. These services are also insecure - Dropbox and Ubuntu One can read your files.

The service that's most convenient for private and easy to share storage on remote hosted servers was Allmydata. Allmydata may be gone, but the people behind and software behind it (Tahoe-LAFS) are still there. Tahoe-LAFS is Free Software and the techniques and algorithms well documented.

But storage and bandwidth aren't free. How would the economic model behind a secure, private mirroring service work?

Very few people want to pay cash for mirroring. Can't have the mirror show you ads - that would defeat the privacy aspect (besides, how would these ads be served and where would they be viewed?).

But your computer is going to be on a lot of the time to participate in the p2p network. Why not have it mine bitcoins? Then you can pay for mirroring storage/bandwidth with the bitcoins gained from contributing work to a mining pool.

Metcalfe's law hypothesizes that each node brings value to the network when it joins. A logical conclusion is that not only the network, but the node itself should be able to realize that value in monetary terms. Cryptographic currency mining enables this.

Another long sought-after idea that may be enabled by the mining approach is micropayments, but that's a problematic and unrelated area.

Who else is working on this stuff?

2012-01-07T13:54:00.003-07:00

None of the ideas in the ClearSky concept are original to me. This is sort of the zeitgeist of the times. Here's a list of people and projects that have thought about or are working on the same problem:

The basic idea stems back to the home media convergence attempts of the late 90s (and indeed Tonido is still following this marketing strategy).

Why no one has been successful so far is that the solutions offered are too hard to use (if it's any harder than Facebook, very few people will use it), don't address the issue of replication (Tonido and Opera Unite, for example), and don't have sustainable revenue models. I think that with the right design, engineering and business approach, these problems are not insurmountable.

You might notice I left out one project: Diaspora. A look at Diaspora's source code should convince you that while the project claims the same goals, the approach they're taking does not address any of the three aspects mentioned above.

The future of the App Store is source-only distribution

2012-01-07T13:47:00.001-07:00

Following up on the ClearSky idea, let's look at what the applications that run on your and your friends' computers will be like.

Obviously, the Apple app store model of cryptographic signing is useless as a measure of trust of what an application does in a decentralized scenario (note that this is different than using signing to establish authenticity during application distribution). The Apple app store model of cryptographic signing is actually useless for Apple app store apps as well - I know of at least two apps that have made it into the Apple app store that will keep an open, non-password protected telnet port on your iPhone. So centralized quality control does not work.

Will virtualization be able to solve the safety problem? What virtualization is really about is names and meta-machines. In the case of running a VMware virtual machine on your real PC, your real PC is the meta-machine from the point of view of the VMware one, and memory addresses are the names. As long as the software in the VMware box has no access to the memory addresses belonging to your real PC, it cannot escape to do things that the VMware virtual machine cannot already do (you can think of virtualization like being the plot of The Matrix).

Even if the virtualization is unbreakable and the virtual machine does everything you need without posing a danger to your data (and how would it do that if it needs to modify your data to be useful?), you cannot tell whether the app that the virtual machine will run doesn't have secret back-doors or information leaking channels (both can be accomplished using steganography to hide things in the data the app consumes and produces as part of its regular operation). Checking compiled binaries for these is simply not feasible.

The only alternative that is left is the one advocated by Richard Stallman - you can't trust a program unless you can read its source code. While it is still possible to hide back-doors in source code, it requires a very large and extremely messy code base to hide them effectively. And very large and extremely messy code bases tend to lead to shit applications that no one really wants to use (unless corporate IT makes you). Applications with clean code bases that are easy to audit are nice; use them.

Note that this model of software distribution (source-only) is not new - in fact, it has been the most popular method of software distribution for the last 10 years. This is how JavaScript works. And JavaScript has also shown that language-level virtualization (ie "sandboxing") is extremely effective as a security mechanism - there have been very few exploits where an attacker was able to escalate privileges outside of the JavaScript virtual machine.

There are two ways to get around the "easily auditable source" ideal with JavaScript. The most popular way is to use code obfuscation tools. The other way (which in the past year has gained more and more recognition) is to use JavaScript itself to implement another virtual machine (kind of like Russian nesting dolls).

While there is no way to prevent these two techniques (and in fact it is undesirable to do so; but it doesn't stop Apple from trying), you certainly should be able to have the freedom to use applications written and audited by people you trust. The centralized, signed app store approach used by Apple destroys this continuum of trust by putting all applications on an equal level - "approved by Apple" doesn't mean much when the approval process is secretive, arbitrary, and does not guarantee quality or security.

Are there any other benefits to source-only distribution besides security? Plenty: complete portability, high performance (compile to native code), tiny download sizes, easy dependency management, etc.

One way to encourage the ideal of "easily auditable source" is via licensing. This is where the innovation of Henry Poole comes in handy - the Affero GPL is the most business-friendly of all Free Software licenses (more on that in a later post) and when used effectively will enable disruptive new business models. The "platform" part of the hypothetical ClearSky virtual machine will benefit tremendously from being licensed under the AGPL.

Friends with [login] benefits

2012-01-05T10:25:00.002-07:00

To follow up on the last post, think about what it would mean to have a web application running on your friends' computers. How would you log in from a random computer on the Internet?

The account name and password combination is convenient to remember and seems to work well in practice for logging in to computer systems.

It's easy enough keeping your password secret when you log into your own machine, and you can use public-key cryptography to have trusted communications with your friends. You can remember your account name and password, but you're not going to be carrying around your private key (if such a system is to work for most people, you're probably not even going to be aware you have a private key).

You can trust your friends, but you don't want to tempt them by transmitting the cleartext passwords to their machine (ever have an obsessive ex as a friend on Facebook?). Having a unique password for each of your friends' machines won't work because you can't remember them all.

On the other hand, you can assume that your friends probably won't want to crack your password hash to get your password, and if their machine ever gets stolen, they'll tell you so you can change your password (ok, maybe that last point is not true).

If you take your password, assign each of your friends a unique salt, and give them the salt and the PBKDF2 (or whatever) digest of the salt and password, you can do the password checking in any browser with JavaScript by having their machine send the salt to the browser, the browser computing the PBKDF2 digest and sending it back to their machine, and their machine verifying the digest.

Your friends don't have your private key, but they can sign your messages with the private keys on their machines on your behalf. If you see strange messages signed on your behalf, you can assume that either your password has been compromised, or your friend's machine is acting maliciously (because it has been stolen, compromised, or your friend is doing the equivalent of the "let's post "I'm pregnant" status update" joke when you forgot to log out of Facebook).

You still have your private key on your machine, from where you can change your password, repudiate the fake messages, and publish a revised list of friends that you trust to sign messages on your behalf.

I'm sure this scheme has been thought of before, and I'm sure it has problems I didn't see. Any thoughts or comments? Where should I post this to get the opinions of people knowledgeable on cryptography?

I don't want Clouds, I want clear skies

2012-01-04T13:57:00.003-07:00

The Cloud is one of the most idiotic things to happen to computing.

The only thing fuzzy about The Cloud is the definition of the word. It's basically a way for large companies to bamboozle you into giving up your privacy.

There's also a lot of wishful thinking reality distortion involved here. Large companies would love it if the only way people could do anything was in The Cloud, because today that word really means "hundreds of thousands of servers," and only large companies have enough capital to afford that, keeping competition out. Hosting companies like Amazon (there, I've said it) love it even more, because they get better utilization of their hundreds of thousands of servers, and therefore of their capital.

This situation should remind you of something: the 70s. This isn't really any different than the mainframe era. Can't afford ~~a mainframe~~ tons of servers? Call ~~Tymshare~~ Amazon!

So why are all these hundreds of thousands of servers needed? In the case of Google or YouTube, it seems pretty straightforward - it takes a lot of space to index most of the Internet and host millions of cat videos. But what about Facebook? What's really on there besides a few hundred (or maybe thousand) photos, links to YouTube cat videos shared by your friends, and your whiny status updates? It's hard to purchase a USB memory stick that would be small enough not to fit all that three times over.

It turns out there are a lot of other things on Facebook. Things like your click stream (ie - things you don't care about), which is needed for analytics (ie - using statistics to invade your privacy) to better serve you advertisements (ie - make you buy things you don't want).

The only reason Facebook needs to be "web scale!!!" is so they can sell ads. The only reason they're selling ads is because millions of people signed up for Facebook. The only reason millions of people signed up for Facebook is because it's the easiest way to share photos, links to cat videos, and important news about where they had lunch with their friends (oh yeah, and play Farmville or whatever).

Putting it this way, it's obvious why Facebook needs to sell ads - their service isn't valuable enough to you to get you to pay for it. So it's certainly not worth your time to set up your own web server with a bunch of pub/sub protocols and get all your friends to do the same so you can log into your MyFace social network to post inane status updates and grow virtual beets from other random computers connected to the Internet. That's hard, and who wants to pay for hosting?

Except you and your friends already have one or more computers connected to the Internet. What if it was easy?

Don't steal my REPL, or Lisp lessons from ledger

2011-12-24T10:27:00.002-07:00

John Wiegley's ledger is a popular double-entry accounting system with a Unix command line interface.

What many people don't know is that version 3 of ledger was written in Common Lisp. This version was never made into an official release. In a FLOSS weekly podcast, Wiegley explains (31:00) that Common Lisp wasn't the best choice for ledger's users.

I emailed John to learn more about this. He replied that there were only two major problems: building cl-ledger was more difficult than building ledger, and that cl-ledger could no longer be scripted from the command line. In effect, the Common Lisp REPL had stolen the place of the Unix command line as ledger's interface.

cl-ledger was written in 2007, and there are now good solutions to these problems. ASDF works well as a build system, but before Quicklisp, dependency management for Common Lisp applications was difficult. Quicklisp solved the biggest outstanding problem in building Common Lisp applications. (PS - you can give Zach a Christmas gift for his work on Quicklisp)

Didier Verna's Command-Line Options Nuker is a widely portable Unix CLI library with many features that you can use to build command-line driven Common Lisp applications.

Wealth vs Creativity

2011-12-22T21:31:00.003-07:00

The basis of wealth is exclusively material. Everything non-material in an economy is a social convention.

Money, trade, and even labor is worthless unless it satisfies a particular desire in a particular point in time (see Deleuze and Guattari's Anti-Oedipus about the role of desire in capitalism).

It's easy to accept that money is a social convention, but how can labor be worthless? The famous illustration is Bastiat's "broken window" fallacy. While Bastiat's conclusions are correct, his reasoning starts with the wrong assumptions. Wealth has nothing do with the classical notions of trade and utility and "money better spent elsewhere" - the broken window fallacy is directly explained by the material reality of objects.

The key thing to understand is that material objects are cumulative and impermanent. These two qualities are what drive everything else about wealth.

A window is cumulative in that it satisfies a desire and has a physical manifestation, and it is impermanent in that the physical manifestation is now broken and the desire is no longer satisfied. Even if currency were completely devalued tomorrow, the fact that a window is there would still satisfy the desire.

This is why the labor theory of value (indeed any other theory of value that doesn't take into account Deleuze and Guattari's desire machines as the ultimate driver of the economic process) is wrong. Labor or technology itself has no value whatsoever, unless it ultimately (if through a long series of immaterial social transactions) results in the production of a material object that satisfies a desire.

So far this essay has talked about labor, but what about trade? To understand trade, first we need to define the word: there is no such single thing as "trade," rather the word refers to two things, which may or may not be present in a particular "trade" (transaction): the social (buyer/seller, consignee/consignor relationship) and the material (embodied in labor as transportation of material objects). A purely social transaction would be finance, a purely material one would be theft.

Trade is obviously important in satisfying desire - if a material object is not in the right place at the right time, it can't satisfy that desire. A chain of social trades resulting in the transportation of a material object then obviously has value.

One of the most pressing questions today (see: SOPA act), is where does this leave purely social transactions? If you want $10 for a pile of bits, money that will buy you lunch, but someone else is satisfied with a "thanks for sharing!" for the same pile of bits, where does materialism come in?

The material reality of the world is that those bits are worthless. The movie, music, and publishing industries were built on material objects: selling time slots in seats in a movie theater, selling vinyl and plastic discs, selling bound stacks of paper. The particular content on those material objects was in a very fundamental way completely irrelevant to their business, even if paradoxically it was the key to their business model.

Knowledge may be cumulative, but it is worthless unless it can be applied to satisfy a desire. It is also permanent - it cannot be stolen. What knowledge is great at is helping produce better material objects with less cost and greater ability to satisfy desire.

The real competition to the movie, music and publishing industries are the computer manufacturers and ISPs.

What the MPAA and RIAA and the SAG are doing when they attempt to put in digital restrictions management into computer hardware and force ISPs to filter content is the equivalent of the Luddites burning water mills and power looms. This is a strategy that will ultimately fail, but in the short term causes a slow-down in the rate of improvement of material objects, both directly (PCs and Internet connections suck more because of attempts to implement digital restrictions management), and indirectly (this improvement in the production of objects is driven by knowledge produced with the aid of PCs and the Internet, in a cumulative process).

So what about the MPAA excuse that no one will be able to finance the production of big-budget action movies anymore? At a time when the very same progress in material production is drastically reducing the cost of producing a movie (via an all-digital process and computer-generated imagery), this is exactly like arguing that no one will be able to afford to author books during the time of Gutenberg's invention of the printing press.

The creative urge is a desire in and of itself. If there's anything you should take away from this essay, it's that people pay to have their desires satisfied.

Programming considered harmful

2011-12-20T22:06:00.003-07:00

gotos make it possible to write bad programs
threads make it possible to write bad programs
global variables make it possible to write bad programs
anonymous functions make it possible to write bad programs
macros make it possible to write bad programs
mutable variables make it possible to write bad programs
continuations make it possible to write bad programs
dynamic scoping makes it possible to write bad programs
objects make it possible to write bad programs
recursion makes it possible to write bad programs
...

Take this argument far enough, and you are left with the S-K combinators, and now it is impossible to write good programs.

Having few features in a programming language is a fault, not a virtue. The bigger fault lies in failing to provide the language with the facilities to be extended with new features.

No amount of language design can force a programmer to write clear programs.

--Guy Steele & Gerald Sussman

Announcing: CLiki2 public beta 2

2011-12-12T17:41:00.002-07:00

CLiki, the Common Lisp wiki, is a good resource for finding out about Common Lisp libraries and other information. However, the code behind CLiki itself is hard to maintain and add features to.

Andrey Moskvitin and I have been working on a replacement wiki web application on and off for the past eight months. The first public beta came out in the summer. Since then, I've worked the software to the point where I think it's ready as a replacement to power CLiki.

The second beta of CLiki2 is now up at http://74.207.228.11/. Please try it out and let me know what you think. Bugs can be reported at https://github.com/archimag/cliki2/issues or by sending me email: vsedach@gmail.com

Most of the new features center around spam prevention:

Wikipedia-style history lists and diffs for all pages
Lists of edits by account/IP address
Blacklist of accounts and IP addresses
Atom change feeds for individual pages (as well as all of CLiki)
HTML tag filtering

Other new features include:

Real article deletion and undeletion
Code coloring using cl-colorize
Working list of uncategorized/orphan articles
Pages that work well in text browsers (and hopefully screen readers)
No JavaScript

Pages are marked up using a mixture of HTML (with some tags and attributes filtered out) as well as a slightly simplified form of CLiki syntax.

Behind the scenes, CLiki2 is powered by Hunchentoot, BKNR-datastore, and Nathan Froyd's diff library.

Source code is at https://github.com/vsedach/cliki2, and is licensed under the Affero GPL.

Montreal Scheme/Lisp Users Group back in action

2011-11-28T13:44:00.003-07:00

After a long hiatus, the Montreal Scheme/Lisp Users Group (MSLUG) is back to regular meetings, with the latest one taking place November 24.

Marc Feeley gave two talks, the first presenting his experiences adapting the Gambit Scheme implementation into the Gambit REPL Scheme interpreter app for iOS (most of the difficulties seemed to revolve around the Apple app store screening process). (slides)

Then Marc showed and discussed a demo doing distributed computing using mobile, serialized continuations bouncing around Gambit instances on x86 Macs and ARM-based iPhones/iPods. The slides are well worth checking out, particularly for insight into how serialization of problematic objects like I/O streams/ports is done.

There's at least one Common Lisp project (cl-walker) that claims to be able to serialize continuations, and another library (Storable Functions) which claims to be able to serialize closures (from which you can get continuations with a CPS transformer); I haven't tried either and to my knowledge there hasn't been any works done on mobile continuations for Common Lisp, or that much work for mobile code in CL in general.

The next MSLUG meeting is tentatively January 19th; I'm scheduled to present a talk on Parenscript.

Optional dependencies

2011-11-05T15:11:00.001-06:00

Both uri-template and css-lite provide optional support for generating JavaScript templates via Parenscript. However, I did not want to make Parenscript a required dependency for either library.

Previously, this was implemented using the #+parenscript read-time conditional in the source files.

That worked ok if you loaded Parenscript before loading css-lite, but there were two problems:

If you initially compiled css-lite without loading Parenscript first, you'd need to go back and re-compile css-lite by hand after loading Parenscript if you wanted the JavaScript output.
If you loaded the css-lite fasls compiled with Parenscript into a fresh Lisp image without loading Parenscript first, you'd get an error.

Both of these error stem from the fact that ASDF didn't know anything about the optional Parenscript dependency.

Didier Verna has written about optional ASDF dependencies previously (make sure to read the asdf-devel thread on optional dependencies Didier links to if you're interested in this). In short, relying on ASDF's :weakly-depends-on seems quite hairy.

I think I found a simple alternate solution for uri-template that seems to work: put all the Parenscript-dependent code into one file, and then use read-time conditionals in the uri-template.asd list of files like so:

:components ((:file "package")
             ...
             (:file "destructure-uri")
             #+parenscript (:file "parenscript-implementation")
             )

You can see the full implementation in the latest patch to uri-template.

Let me know if you have any ideas about this technique, or optional dependencies in general.

Common Lisp is the best language to learn programming

2011-10-30T15:00:00.000-06:00

Now that Conrad Barski's Land of Lisp (see my review on Slashdot) has come out, I definitely think Common Lisp is the best language for kids (or anyone else) to start learning computer programming.

Between Land of Lisp, David Touretzky's Common Lisp: A Gentle Introduction to Symbolic Computation (really great book for people new to programming, available for free) and The Little LISPer (3rd edition, editions four and up use Scheme) you have three really great resources to get started.

Lisp's syntax is a great advantage because it is so simple to learn and has so few special cases. The interactive, iterative development style and real late-binding means you can build programs in parts and add to them as you go. The presence of real metaprogramming means you always have the ability to look at any part of your program and its state to find out what it's doing/what's wrong. The HyperSpec and Common Lisp The Language are two of the best programming language reference manuals ever written.

The best parts about Common Lisp are that it's a language that's hard to outgrow and that it makes difficult things easy. One of the chapters in Land of Lisp explains HTTP and HTML and has you build a basic web server. That chapter is only 15 pages! There's tons of ideas in the language, and because you're not restricted to a particular programming paradigm, you're always discovering better ways of doing things and developing a personal style.

The new digital divide

2011-10-14T13:53:00.005-06:00

Steve Jobs passed away last week.

Kieran Healy wrote a wonderful examination of his role at Apple. But there is one thing in there that bears a closer look:

Jobs wanted people to love his products, take care to notice their craftsmanship, and be creative with them. They were supposed to help you make and do awesome things. But this love and attention to creativity was not extended to those involved in the manufacturing process.

I've been meaning to write about this subject, and now seems a good time.

The iPad, the iPhone, and the Apple App Store are not leading to a new age of digital freedom and creativity. They are creating the real digital divide.

Original PCs used to ship with a Basic interpreter. When that stopped, you could still get a programming language implementation without too much trouble. But Apple goes out of its way to make the iPad and iPhone not programmable by anyone except a self-selected caste of "developers."

The awesome things you can do with the iPad have very real limits. Limits that are unnecessary, artificially imposed, and at core opposed to iPad's essence as a programmable computer.

Ellen Rose wrote about the infantilization of computer "users" in User Error: Resisting Computer Culture, but few products until the iPad have shown how literal this effect is. Consider Apple's marketing:

Does the above image remind you of anything?

Further evidence of how literal the infantilization has become is the infamous "fart app" - it is nothing but a direct throwback to the anal stage of Freud's model.

Richard Stallman made a poorly received comment on Jobs' legacy upon news of the latter's death. I think the negative consequences of the iPad extend well beyond Apple's hostile and exploitative stance towards Free Software

This is not the Google campus

2011-09-23T11:30:00.002-06:00

A substantial fraction of workers were absent on any given day, and those at work were often able to come and go... at their pleasure to eat or smoke... [the workplace] would have eating places, barbers, drink shops, and other facilities to serve the workers taking a break. Some mothers allegedly brought their children with them... Workers' relatives would bring food to them.

A Farewell To Alms, Gregory Clark. p. 363

This is not about the Google complex, but a description of a 19th century Indian textile factory.

Common Lisp is case sensitive

2011-09-20T16:00:00.000-06:00

One Common Lisp feature that needs more publicity is case sensitivity. A common misconception is that Common Lisp is case insensitive, when in fact symbols in Common Lisp are case sensitive.

By default, the Common Lisp reader is case-converting: all unescaped characters in a symbol name get upper-cased. This gives the practical effect of making it seem as though symbol case doesn't matter. This is desirable behavior for interfacing with other case-insensitive languages (such as Fortran; from what I understand the main motivation for the default Common Lisp behavior), but a pain to interface with case-sensitive ones (such as C).

The behavior of the reader can be customized via readtable-case.

The one that might seem to be most useful for having case-sensitive symbols at first glance is :preserve, however remember that all code read in with the default setting (:upcase) is in upper-case, as are all the standard Common Lisp symbols (this is defined by the standard), so this means you will need to spell out all CL and external symbols IN ALL UPPERCASE. To make this less annoying, the :invert readtable-case is the most practical - all-lowercase symbol names become uppercase, all-uppercase become lowercase, and mixed-case stays mixed-case (the important part for case sensitivity). The Lisp printer outputs symbol names correctly this way by default. The only problem now becomes inconsistent spelling of a symbol in all lowercase or all uppercase in old code that expects case conversion. But otherwise you can get case sensitivity for your software by setting readtable-case to :invert today.

An easy way to manage the readtable-case is by using the named-readtables library. I've recommended named-readtables before; besides case sensitivity, it helps manage reader macros.

[This blog post is adapted from the case sensitivity CLiki FAQ entry I wrote. Feel free to make corrections and other suggestions on the CLiki page.]

Pioneers are the ones with the arrows in their backs

2011-09-13T10:40:00.002-06:00

Table of the fates of the inventors of the textile machinery that drove the Industrial Revolution in England. From A Farewell to Alms, Gregory Clark, p. 235

Programmer myopia

2011-08-28T13:15:00.003-06:00

We like to assume that people are basically competent and rational. Computer programmers enjoy pretending they are more competent and rational than people in other professions.

In many cases neither of those assumptions is true.

Two popular memes surrounding programming languages in the 80s and 90s were the assertions that "garbage collection is too slow" and that "dynamic typing doesn't work for large programs."

Many programmers were convinced both those things were true. In hindsight they were completely wrong, as languages such as Tcl (more on the importance of Tcl in the history of programming languages in an upcoming post), Perl, Java and Python "dragged people halfway to Lisp" and changed public perception.

How could so many people who consider themselves above-average in competence and rationality be so wrong? (Assume that every programmer is indeed a special snowflake and the Dunning-Kruger effect doesn't apply).

A hermit spent 10 years writing a program. 'My program can compute the motion of the stars on a 286-computer running MS DOS,' he proudly announced. 'Nobody owns a 286-computer or uses MS DOS anymore,' Fu-Tzu responded.

Eloquent JavaScript, Marijn Haverbeke

The problem is that programmers seem unable to think even a couple of years into the future. People complaining about garbage collection in the 80s were looking back at their existing 8-bit Trash-80s instead of at contemporary computers being produced and the future computers being planned. The idea that computers can be good at automating rote tasks like managing memory and checking and inferring types never occured to them.

People have trouble imagining the future even if the trends, such as Moore's law, are in front of them. It takes a very long time for people to understand the right ideas. Just ask Alan Kay. Being able to find the appropriate point of view really is better than a high IQ.

Here are some other Lisp concepts that programmers believe out of ignorance that will take a long time to dispel:

tail recursion is unnecessary and makes debugging difficult
macro-based metaprogramming results in unmaintainable programs

Implications of self-driving cars

2011-08-12T11:53:00.003-06:00

I predict one of the first things Google will do with self-driving cars is automate the trucking industry. This will be a huge change in terms of improving shipping efficiencies, but I don't believe that it will fundamentally disrupt the logistics industry: at most trucking companies, the turnover rate for drivers is over 100%. Truck drivers are already treated like robots.

The current passenger automobile system, on the other hand, will undergo a complete and total change.

Self-driving cars will lead to an almost complete elimination of both privately owned cars and public transportation in cities. Robot taxis will become so cheap and ubiquitous, and parking space so expensive, that it no longer makes sense to own your own car (many residents of NYC and San Francisco already find parking unaffordable today).

The first step to this is already being implemented - the automation of taxi dispatching.

Robot cars are safe. The auto insurance industry will be virtually eliminated.

Robots cars need less maintenance and will refuel themselves. Most gas stations and service shops will be consolidated into a few large service depots.

A city will have less automobiles but its citizens will use cars more often - even with peak demand, a smaller fleet of robot taxis than private vehicles can service commuter needs.

Self-driving cars have better road capacity utilization, so even with increased automobile usage the amount of paved roads in cities will be reduced, as unused lanes are reclaimed for real estate development. The same thing will happen to parking lanes and lots - even as demand for parking goes down, the price will rise as the parking spaces get reallocated to more profitable real estate development and the supply shrinks at a faster rate. This will have the effect of greatly reducing road maintenance expenses and increasing property tax income for city governments.

The layout of cities will return to the pre-automobile era, the most visible changes being narrower streets.

On the other hand, the highway system will face pressure to expand, as robot taxis will undoubtedly be used as a substitute for air, train, and bus travel. Robot taxi operators will be national or even international in scale, and who cares if a particular robot taxi was working in New York yesterday and is in Chicago today, as long as on average the operators' fleet utilization is maximized? The key ability of self-driving cars to link into aerodynamic paceline "trains" (much like bicycle racing teams) will make long-distance fuel consumption competitive with trains and buses.

The robot taxis by themselves will also be much more aerodynamic than today's cars. With the elimination of private ownership, automobile body design will no longer be driven by the status symbol desire, but by taxi operators' need to minimize fuel consumption.

What does this mean for public transit? Buses and street-level tramways will be out, but subway networks will likely remain viable because subways are not vulnerable to traffic jams and snow.

In terms of traffic, it's likely that the top speed of a journey will decrease, while the average speed increases. Robot cars can potentially negotiate intersections much more effectively than human drivers. Congestion at peak times will likely still be a problem in city centers due to decreased road capacity, but the traffic jams are likely to be shorter and involve higher average speeds.

Smart enough to predict stupidity

2011-08-12T10:00:00.000-06:00

I think the root of your mistake is saying that macros don't scale to larger groups. The real truth is that macros don't scale to stupider groups.

--Paul Graham on ll1

People who design programming languages sometimes like to imagine an idealized "average programmer" who will employ their design. The underlying assumption being that the language designer is smarter than the "average programmer," and will set out to protect the latter from their own incompetence.

The arrogance behind this view is twofold - not only is the language designer deeming himself objectively smarter than other people, but that he will be able to predict how other people's stupidity will play out. In view of this egotism, the (lack of) quality of the end result should not be surprising.

This objection -- "but bad programmers will make a mess of it" -- is the stock objection everybody makes to every unorthodox programming construct. Since it is an objection to everything, it is an objection to nothing.

--Daniel Gackle on programming language features

Continuation-based web applications: just say no

2011-06-06T14:32:00.001-06:00

Many people still seem to regard continuations as a possible or even preferable method for writing web applications. This blog post aims to dispel that notion and demonstrate that continuation-based web apps belong in the 90s.

Why are continuations good?

Anton van Straaten's excellent Continuations Continued argues that continuations are a good way to model server-side code, ergo they are a good way to implement server-side code. The modeling assertion is for some instances correct, the implementation assertion is not.

Continuations made sense for pre-JavaScript web applications, where each new functionality predicated on a possible user choice (ViaWeb's color picker palette being a good example) would lead to combinatorial growth in the complexity of the state machine behind the pages that that functionality would interface with. This is because the server was burdened with what is essentially transient client-side state. With AJAX, this is no longer the case.

Why are continuations bad for clients?

There are well-known problems with continuation-based web apps: bookmarks, history, and back/forward buttons don't work.

A web application session is a call-graph from the point of view of the browser, where the URLs are akin to procedures. HTTP interaction flows like a program, with the user making decisions of which procedure to invoke/URL to visit. By this analogy, using continuations is exactly like giving random names to all of the procedures in a program each time a procedure is called.

This is the core of the problem with continuation-based web applications. Everything that revolves around user control of accessing URLs (bookmarking, history, back/forward, etc.) breaks. This also makes it much harder to test continuation-based web applications programmatically and makes debugging harder.

One incidental advantage of this breakage is that some URLs do need to be unique and single-access to prevent cross-site attacks and duplicate form submissions. I argue that these mechanisms should be thought of as token-issuing state machines, and implemented explicitly. This leads to simpler code and manifest state.

Another strategy that has been used is storing continuations on the client side using cookies or URL query parameters. This approach is problematic for the amount of data it transmits on each request, and the possible security implications (the continuations need to be encrypted, and the keys frequently rotated and expired - however the expiry of continuations is exactly the problem that query-parameter serialized continuations were supposed to avoid - links that rely on continuations stored on the server cannot be bookmarked!).

Why are continuations bad for servers?

The essence of using continuations server-side is handing off control of inter-request state serialization to an implicit mechanism that is tied to the structure of application code.

Both data and logic are now intermingled and stored in opaque continuation structures. This makes the code hard to debug, state difficult to replicate for fail-over redundancy, problems difficult to reproduce, and control flow difficult to understand.

What should you do?

The ability of JavaScript to make HTTP requests without reloading the current page (AJAX) allows you to keep what is essentially client-side state on the client. The server is now responsible for a set of URIs, where each URI can be thought of as a separate service that can be modeled as a state machine. This keeps web application state and control flow manifest. Different parts of your web application (represented by different URIs) can now be completely isolated; any state interactions and dependencies between them become explicit.

Programming is a creative pursuit

2011-04-16T17:56:00.002-06:00

There is still some debate around whether programming qualifies as a creative endeavor akin to writing, arts, or crafts. Paul Graham attempts to draw analogies between hacking and painting (unconvincingly, some argue).

The answer is a strong positive if you examine the motivational factors (examining motivation to get better insights is something that I have emphasized before).

How else can you explain the motivational factors of people working on Free Software? Of people programming at work, and then going home and programming as a hobby? Of working on multiple, related and unrelated, projects simultaneously, sometimes over periods of years or decades at a time?

Another obvious but almost never discussed aspect of programming as a creative pursuit is that it is almost impossible to succeed in programming as a career if you do not enjoy your work. This is true for all creative professions, but can you argue the same for plumbers or assembly-line workers or, closer to the idiotic "knowledge worker" label, accountants?

Succeeding as a programmer of course has nothing at all to do with succeeding at being employed as a programmer, amusingly enough because of the widespread belief that programming is a non-creative profession and that 9 women can make 1 baby in 1 month. With perverse incentives such as "lines of code written" (when the only good thing about lines of code is how many you can remove) and no understanding by management of the impact of such things as technical debt, unit testing, or even basic things like quality, hapless code monkeys can stay on the payroll. But how many of them are recognized (in a positive way, mind you) by their peers? How many of them choose to continue to do programming into their 40s? The hapless code monkeys usually switch careers or "advance" themselves into the ultimate bastion of incompetence: management.

Wanted: plug computer with HomePlug and 802.11

2011-04-07T13:13:00.004-06:00

I've been thinking about mesh networks recently. Two of the better-known projects in this space are Open-Mesh and the Mesh Potato. Both use 802.11 to build a wireless network, but experience shows that wireless interference is a major problem in scaling these networks.

The solution seems obvious: add a HomePlug power line communications interface to the mesh routers. That way routers adjacent on the power grid (and so presumably adjacent to each other and other wireless devices, that is, in places with a lot of interference) can do forwarding over the wire.

If you add HomePlug interfaces to devices themselves (are there any PC or notebook power supplies with HomePlug built-in?), pervasive mesh networking starts to look like an inevitability.

Lisp linkdump, March 2011 edition.

2011-03-29T13:00:00.000-06:00

Here's a bunch of links to interesting Common Lisp stuff I've come across lately:

EOS is a drop-in replacement for the FiveAM test framework which has no dependencies on external libraries (one of the dependencies of FiveAM is heavily implementation-specific and doesn't work on LispWorks 6, among other platforms). I've converted all my FiveAM projects to EOS, and recommend you do the same.

I've ported the Multilisp benchmarks from Marc Feeley's PhD dissertation to Eager Future2. Some of them tax your Lisp implementation a lot, and might reveal bugs. On my 32-bit x86 system, the only implementation to run all benchmarks to completion without segfaulting was SBCL. Try them on yours: load :test.eager-future2 and call benchmark.eager-future2:run-benchmarks.

Speaking of Marc Feeley, here is some other cool work he has been involved in:

Vincent St-Amour and Feeley came up with the PICOBIT R4RS Scheme, which can run Scheme programs in 256 bytes RAM and 8KiB of ROM total (including VM footprint) on PIC microcontrollers.

Feeley gave a talk about Gambit Scheme at ILC2010, and had a really great set of slides which you can get at http://www.iro.umontreal.ca/~gambit/Gambit-inside-out.pdf (warning: 24MB PDF file!)

Common Lisp FORMAT continues to amaze. Peter Seibel pointed out Erik Naggum's cool hack for formatting dates on the Lisp-pro mailing list. I recently learned that instead of passing nil or t or a stream to FORMAT, you can pass a string with a fill-pointer, and "the output characters are added to the end of the string (as if by use of vector-push-extend)."

Jonathan Fischer wrote a good article about feeding binary data from Common Lisp to C.

Other things you can do with C is add s-expressions and macros - c-amplify does just that. c-amplify is motivated by the needs of game development, as was GOAL, Andy Gavin's Lisp system which powered the Jak & Daxter videogame franchise. Now there's a GPL-licensed attempt to create a GOAL-like environment called Score.

Other places besides C you can now run Lisp:

cl-gpu translates a subset of CL to CUDA GPU kernels. Arduino Lisp translates a subset of CL to a subset of C++ that can be compiled to run on the Arduino microcontrollers.

I keep promoting named-readtables (seriously, try it!), but Tobias C. Rittweiler has more cool libraries you should check out:

Hyperdoc provides a way for your Lisp library documentation have fancy Hyperspec-like lookup in SLIME.

Parse-Declarations is useful if you're building Lisp translators or code-walking tools.

There was a very interesting discussion of syntax and s-expressions on Hacker News; one of the things I learned is that according to X-bar linguistic theory, all natural languages basically consist of s-expressions. Of course the great thing about Common Lisp is, like natural languages, it is both homoiconic and its words have different meanings in different contexts. Alan Bawden came up with the "Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo" let quine of the Lisp world (another one of the cool things I learned from Doug Hoyte's Let Over Lambda).

If you've been looking for example code of large CL web applications, you should check out cl-eshop. cl-eshop currently runs the «ЦиFры» St. Petersburg store chain website and is licensed under the AGPL (Affero GPL).

Abstraction, indirection, and programming languages

2011-03-22T19:08:00.002-06:00

A common mistake programmers seem to make is assuming that abstraction is about putting a layer of indirection (whether through function calls or data structures) into a program. Indirection is one of the more commonly used tools to implement abstractions, but just because there is now an extra layer of function calls in your program doesn't make it more understandable, maintainable, or a better fit to the domain. Those are better (although somewhat subjective) criteria for what makes effective abstractions than layers of indirection.

Another thing programmers like to do is argue about programming languages and the abstractions (over machine language) they provide. Oftentimes you'll hear "language A has feature X" and the refrain "language B doesn't have feature X and is good enough, so feature X isn't important/is harmful." When iterated enough times, it's easy to see that this becomes a sort of reductio ad assembler argument.

Is a sufficiently powerful assembler good enough? So what makes C better than assembler? Why is C special? And what's better than C?

It is productive to be able to both ask and answer the last question, which is why real metaprogramming is an invaluable thing to have.

Stallman's Four Freedoms

2011-03-15T14:42:00.001-06:00

Freedom Zero is the freedom to run the program as you wish.

Freedom 1 is the freedom to study the source code, and change it so the program does your computing as you wish.

Freedom 2 is the freedom to help others; that's the freedom to make and distribute exact copies when you wish.

And Freedom 3 is the freedom to contribute to your community, which is the freedom to distribute copies of your modified versions when you wish.

An interview with Richard Stallman

SMP system wanted

2011-02-15T21:26:00.003-07:00

Does anyone have an 8- or 16-way machine gathering dust? I need a many-processor box to do tests and tuning for Common Lisp future library implementations (I recently ported the Multilisp benchmarks from Marc Feeley's PhD dissertation to Common Lisp). Age or architecture (as long as it runs SBCL or ECL) not a concern. Will pay shipping. The box will live at Foulab, where it will be given a good home for software projects.

If you have such a system, or know someone who does, get in touch at vsedach at gmail.com

Academic publishing is a scam

2011-01-24T06:40:00.003-07:00

Let's walk through the American Society's of Agricultural and Biological Engineers submission guide to see why:

Manuscript Submission

It is helpful, but not required, to prepare your manuscript using ASABE Manuscript Templates and to follow the Journal Manuscript Format. Please include line numbers and page numbers on each page (the templates will do this for you).

Do your own proofreading, editing, and even layout. Doesn't sound unreasonable.

Copyright Transfer Form

A complete Copyright Transfer Form must accompany your submitted journal manuscript. (Note: The Copyright Transfer Form replaces the earlier Manuscript Submission Form.) The manuscript will not be reviewed until the Copyright Transfer Form is received.

Now they expect to take my copyright away from me? Can they at least bother to do layout for themselves?

Page Charges

Please note that authors are required to pay, at publication, a page charge based on the number of published journal pages. The current charge is $100 ($110 for non-members) per 8.5 by 11 inch published page in Transactions of the ASABE and Applied Engineering in Agriculture, and $50 ($55 for non-members) per 6 by 9 inch published page in the Journal of Agricultural Safety and Health and Biological Engineering Transactions (formerly Biological Engineering). You will be advised of the total page charges when you receive the page proofs and billed when your article is published.

And now they expect me to pay for all this???

How much are libraries paying for subscriptions again? (The answer is here)

This journal is one particular example, but page charge fees levied on authors are not uncommon for scientific journals. Subscription costs to these journals for university libraries are astronomical.

I am not the first to have similar concerns.

Academic publishers have clearly become a scam industry. This is a market that is not only ripe for disruption, but by most reasonable standards should not exist (where do you think the money for subscription fees comes from? hint: probably your taxes).

What about the Public Library of Science? It's a good, non-profit scam. According to Wikipedia, "PLoS [author page charges] vary from $1,300 to $2,850." $2,000 to put your paper on the Internet. (note for those not aware: peer reviewers are volunteers that don't get paid, so there's no value-add costs that this $2,000 covers)

"But Vladimir," you say, "who is going to pay for publishing my ~~crap~~ research?" Your local university library already has printers, a connection to the Internet, and computers. Think "Digg for scientists" - verified accounts for peer reviewers (throw in digital signatures if you really care), with local library mirror proxies of papers (with BitTorrent-based distribution to cut down on bandwidth costs). Something like arXiv with multiple virtual journals, peer review, and mirroring/distribution.

The Cloud, SaaS, source code escrow, and the Affero GPL

2011-01-16T19:01:00.003-07:00

When making large deployments of commercial software, it is not uncommon for companies to force the suppliers to place the source code of that software into escrow. That might be an option if you're a large corporation, but for most users of SaaS/cloud computing services it is not, and not looking like one anytime soon.

There's nothing stopping your service provider from going bankrupt, being acquired, or deciding to shut down the service. This has already happened when SalesForce acquired SiteMasher (the latter was discontinued), and Twitter acquired DabbleDB - development and new signups ceased, but at least the current users have the comfort of knowing that "In the event we terminate the service, we will provide out customers with at least 60 days advance notice." And then what?

With shrink-wrapped software, you could continue running your existing version. Even if the discontinued software was tied to discontinued hardware, you could keep critical business functions running via judicious maintenance and spare parts suppliers (and later take advantage of emulation technology). This scenario is not uncommon, and of course entirely impossible for a cloud service.

This makes SaaS/cloud computing a big risk for basing your business on. Richard Stallman has previously criticized the lock-in risks of cloud computing, and there are also security concerns.

I think there's an overlooked strategy for mitigating this risk based around the Affero GPL. Releasing your service software as AGPL would eliminate this risk for customers, but unlike the GPL or other licenses it would keep your product protected - all competitors using your code would have to release their changes to the public (and to you). There's also the possibility of dual-licensing your code - an "Enterprise" version with the possibility of escrow for large customers, and an AGPL version with less features for smaller customers.

Why not simply provide an escrow clause into the contract with all customers? It won't help the smaller ones - they will certainly lack the knowledge and resources to go through your proprietary system and set it up on their Intranet. This is unlikely to be the case for Free Software that has a lot of users.

As more web services are created and shut down and their customers burned, the trend is likely to sway away from cloud computing. I think a Free Software strategy based around the AGPL is a way to avoid a "cloud computing winter."

Mouse-copy for Emacs

2011-01-16T18:57:00.003-07:00

Zmacs, MCL's Fred, and the Lispworks editor all contain a very nice time-saving feature absent from Emacs called mouse-copy. Rainer Joswig wrote a good description of mouse-copy; in brief it can be summarized as "hold down Ctrl and click on an s-exp to copy it to the current point."

I first found out about mouse copy from working with Jedi, JazzScheme's IDE, and ever since I've wanted it for my Emacs setup.

Michael Weber's redshank extensions to Paredit/SLIME include mouse-copy, but it depends on buffers being in Paredit mode.

Fortunately there's a simple way to get generic mouse-copy in Emacs. Unfortunately it doesn't do the right thing when it comes to spaces. This is easy to fix by borrowing a couple of lines from redshank. This is the mouse-copy I use right now, and it seems to work pretty well.

As you might suspect there's more time-saving things you can do with the mouse. For example, in redshank M-S-mouse-1 generates a skeleton for a make-instance when you click on a defclass definition. Looking at TI Explorer ZWEI sources, Lisp Machines had an entire modifier-key-and-mouse-button-chord convention that really made s-exp manipulation easy and direct. It would be nice to have something like that for Emacs.

If you have tips on better ways of using Emacs for editing Lisp, consider sharing them on CLiki's Emacs tips page.

January Lisp happenings

2011-01-10T12:54:00.010-07:00

The ALU wiki is running again. Despite requiring registration and having a captcha on every edit, it seems to have a worse spam problem than CLiki. Both seem to be being spammed by hand instead of by bots. Makes me wish the current SEO/content mill bubble would burst sooner.

One thing the ALU wiki does need is more up-to-date content. In particular, if you're a Lisp consultant or freelancer, please add yourself to the ALU wiki Lisp consultants directory.

LinkedIn gave me some ad credit to try out their ad platform, and I'm planning to run ads targeted at technologists and product managers to this landing page that strongly encourages them to try Common Lisp. Any ideas for how I can make it better?

One thing you might notice when perusing Ediware (what Luís Oliveira branded Edi Weitz's excellent Free Lisp Software) is the uniformly useful documentation right on the project webpage. What you may not realize is that Edi has written some software to help you write documentation like he does. DOCUMENTATION-TEMPLATE takes a package and generates HTML to describe the package's exported symbols (you are writing docstrings, right?).

Speaking of Ediware, one of the least appreciated of Edi's libraries is CL-INTERPOL. Besides regular expressions, it's also handy for things like HTML templating.

One of the highest-impact papers I've managed to overlook has come to my attention recently: Henry Baker's Metacircular Semantics for Common Lisp Special Forms. If you're working on Common Lisp compilers/translators/simulators it's a must-read (I wish I had noticed it sooner because a lot of the techniques are applicable to Parenscript). Techniques like that are also useful if you want to fake CL-style control flow mechanisms in other languages.

Perhaps the coolest such hack I've seen is Red Daly's implementation of the Common Lisp condition system for Parenscript. It's worth reading just for the fact that the implementation code explains how the condition system works better than the Hyperspec manages to.

Bonjure, the Montréal Clojure user's group, is having its next meeting January, Friday 21 at 17:30 at CRIM.

FunctionalJobs.com recently launched. They seem to have bootstrapped their first listings from Lispjobs; hopefully they'll have more Lisp-related jobs in the future.

Лисп как клей

2010-12-16T19:51:00.005-07:00

Перебежчик с Common Lispа на Clojure zahardzhan (Роман Захаров) публиковал отчёт о своей первой коммерческой программе в Clojure. Его тезис: "реальные программы — это комья грязи; липкая гадость которая склеивает энное количество технологий, семантик и языков."

Понятие "glue language" - "язык-клей" началось с Tcl и Perl тк они обычно использовались для обработки и послания данных между разными, уже существующими системами ("cклеивая" их вместе). В принципе Лисп полностью годен как клей, но мешало плохая интеграция с операционной системой, неполноценные FFI, и отсутствие библиотек для парсинга разных форматов и интерфейсинга с базами данных и сетевых сервисов. Сейчас первые две проблемы во многих своих образах устранены, и количество библиотек для интерфейсинга все растет. Главные задачи что бы сделать Common Lisp годным как клей, это разработка новых библиотек для интерфэйсинга, и обновление и пиар существующих.

Understanding Web in the context of the medium/message dichotomy

2010-12-15T22:01:00.005-07:00

Web is not a medium. Web is a space of possible combinations of medium, message, and method. The medium and the message are familiar, but what exactly is a method? Methods are algorithms and effects. Previous media had no algorithmic component, no way to conditionalize or effect outcome (choose-your-own-adventure books came closest).

Web IS NOT interactive. It is a two-way audience: every viewer is a publisher. But the websites themselves aren't publishers, they're the medium. Every website is a new medium.

Programming language evolution

2010-12-11T21:28:00.002-07:00

Programming language evolution is sometimes claimed to be a search for greater abstraction.

This is wrong, and mirrors the misunderstanding of biological evolution. There is no end-goal, no such thing as progress or improvement. It's about adaptation.

There are different kinds of models and different kinds of environmental factors, such as machine constraints, and how ignorant of mathematics and past programming languages the designers of a programming language are.

A good example of this is MapReduce. The programming paradigm goes back to APL. Limited support for parallelism was added in the form of vector co-processors on IBM mainframes. The first "massively" parallel implementation of the idea was StarLisp.

Another example is Objective C. Brad Cox claims that the only reason he developed Objective C was because at the time Xerox wouldn't sell Smalltalk (Masterminds of Programming, p. 258).

In terms of parameters like dynamism and introspection, Lisp already had all the necessary features in 1958. From there the same basic idea of lambda abstraction has been applied to Actors and prototype-based languages like Self and JavaScript, but in terms of other "dynamic" programming languages, almost all of them are a step backward from 1958 Lisp.

The same thing can be said about C and Algol 68.

Gaming academia, or why style is more important than substance

2010-12-01T15:29:00.003-07:00

I started with failure. I submitted a couple of papers to conferences and then waited on pins and needles for months, only to be rejected. It was disappointing and motivating at the same time. I realized there was something fundamentally wrong in my writing strategy. At the same time, some of my counterparts at Microsoft were publishing prolifically, and I asked myself, "What is it about their papers that gets them accepted so regularly?" I printed several of their papers looking for a pattern, and I found it. Every one of their papers used the same template and certain stylistic elements. I started using a similar formula and found my papers getting accepted almost immediately. My team submitted papers to some important venues - SIGMOD, VLDB, ICDE, and others - and had 90% of everything we submitted accepted, even in venues in which the acceptance rates were 1 in 6 or 1 in 9. Between 2001 and 2007, my team published more than 35 papers. We became incredibly efficient at it, authoring professional papers in just a few days, almost always using ideas and experimental results we had on hand from our regular line item development work.

--Sam Lightstone, Making it Big in Software

Free Software license onion

2010-11-18T14:50:00.007-07:00

There are tons of Free Software licenses out there, and it can be confusing choosing one for your Lisp project. I'm writing this guide to clear up some confusion, but be aware that I'm not a lawyer and you probably should consult one if you are going to take advantage of this advice for something that you hope to commercialize.

A good strategy for choosing a license is to consider how the project would fit in a software stack - is it a general-purpose utility library? A library to interface to specific services or hardware? A web server that can be used to build applications? A content management system that you one day hope to commercialize? These projects all have different potential uses, but it would be nice if their licensing terms reflected those uses and allowed the content management system to use the web server, allowed the web server to use the service interface library, and allowed the service interface library to use utilities from the general-purpose library.

I think general-purpose utility libraries should be public domain (consider using the unlicense, which is a copyright waiver with a warranty discalimer). One thing people often want to do is copy-paste one or two functions out of them into random projects. Other good things to put into the public domain include benchmark code and test suites (you can release just those parts of your project as public domain).

Next up on the hierarchy are permissive licenses. There are dozens of these around, however I think only those that are LLGPLv2.1 compatible should be used for Free Software written in Lisp (Wikipedia has a chart summarizing Free Software license compatibilities).

There are a few of these (see the GNU license list whether a particular license is GPL-compatible or not), but generally most of them are like the BSD license. I recommend using the ISC license, which is really concise and is used by OpenBSD. Good examples of projects that can be licensed under a permissive license are parsers for data formats and interfaces to C libraries or web services. Permissive-licensed software can include public domain code and code from most other permissive-licensed software.

Projects you do not want to see forked into a closed-source product without giving back to community should be licensed under the LLGPLv2.1 (version 2.1 specifically, as LGPLv3 code cannot be used in a GPLv2 project). Why the LLGPL and not the LGPL or the GPL? The GPL makes it impossible to use a Lisp library as part of a closed-source product (even if you only use it as a library and make no modifications), and the wording of the LGPL does likewise because the "linking clause" basically presumes you're using C.

LLGPL software can incorporate other LLGPL code, public domain code, and LLGPL-compatible permissive license code, but for example LLGPL code can't be put into an ISC-licensed project (the whole project would have to be re-licensed under the LLGPL).

I think it's pretty obvious that you shouldn't license your Lisp library under the GPL if you want other people to actually use it, but how to decide between a permissive license and the LLGPL? I think that aside from practical considerations, many times it comes down to a moral choice. LLGPL forces sharing reciprocity on others. I believe copyright should be abolished or severely reformed, and until those changes start taking place, the LLGPL can be used to similar effects through the impact of works on which you own the copyright (the real pirates aren't the people downloading mp3s, they're the people violating the GPL).

I think the most interesting licensing situation is when you want to develop commercial software, but allow proprietary use and extension only by certain parties (hopefully ones which will pay you lots of money). The general strategy for this is to dual-license your code under the GPL and a commercial license. The most prominent example of a project using this strategy is MySQL.

One implication of this is that in order to make it into your official repository to be dual-licensed, any patches must have their copyright assigned to you/your company by their contributors.

Which version of the GPL to choose for dual-licensing? I think either v2 or v3 is fine (one important thing v3 includes is the anti-tivoization clause, which prevents closed hardware platforms).

One thing the GPL doesn't cover is running proprietary modifications of GPLed software as a service without any distribution going on (for example, Google is rumored to have Linux kernel patches running that haven't been released). The AGPL addresses this issue. I don't know of any software dual-licensed under the AGPL, but I think it can be a promising strategy for a variety of projects.

Character encoding is about algorithms, not datastructures

2010-11-16T08:34:00.008-07:00

One thing you might be aware of is that both SBCL and Clozure represent characters using 4 bytes. There's been significant discussion about this already, but I hope I can offer more insight into how you can apply this to your Lisp applications.

First, the one thing most people seem to agree on is that UTF-16 is evil (it should be noted that both CLISP and CMUCL use UTF-16 as their internal character representation).

The important thing about UTF-32 vs. UTF-8 and UTF-16 is that it is not primarily a question of string size, but of algorithms.

Variable-length encodings work perfectly fine for stream algorithms. But string algorithms are written on the assumption of constant-time random access and being able to set parts of a string to certain values without consing. These assumptions can't be satisfied when variable-length encodings are used, and most string algorithms would not run with any level of acceptable performance.

What about immutable strings? Random access is still not constant-time for variable-length encodings, and all the mutator operations are gone. In effect most immutable string algorithms actually end up being stream algorithms that cons a lot.

Chances are, you're already using stream algorithms on your strings even if you're not aware of it. Any kind of search over a string really treats that string as a stream. If you're doing string concatenation, you're really treating your strings as though they were immutable - consider using with-output-to-string to cut down on consing and to simplify your code.

One thing that is special about UTF-8 is that it is the de-facto character encoding standard of the web. When you're reading UTF-8 into a Lisp string, what you're really doing is decoding and copying each character.

Most web application patterns are based around searching for and extracting some string from the HTTP request, and either using that string as a retrieval key in a database or splicing it together with some other strings to form the reply. All these actions can be modeled in terms of streams.

One of the things that makes John Fremlin's tpd2 fast is that it dispenses with the step of decoding and copying the incoming UTF-8 data into a Lisp string (this is also what antiweb does). Using some compiler macros and the cl-irregsexp library, all the searching and templating is done on byte arrays that hold the UTF-8 encoded data (Lisp string literals are converted to UTF-8 byte arrays by compiler macros). The result is a UTF-8 byte array that can be sent directly back to the web browser, bypassing another character encoding and copying step.

I read somewhere that the Exokernel operating system permitted extending this concept further down the software stack by allowing applications to send back pre-formatted TCP/IP packets, although I don't know if that's actually possible or how much of a speedup it would give.

In addition to skipping the overhead of copying and re-encoding characters, working on UTF-8 byte sequences directly means you can use algorithms that depend on working with a small alphabet set to achieve greater performance (an example of this is the Boyer–Moore–Horspool string searching algorithm).

uri-template, Eager Future и Руби, и ещё немного бреда о Лисповой операционной системе

2010-11-07T18:12:00.006-07:00

Выставил uri-template и Eager Future на github:

https://github.com/vsedach/uri-template
https://github.com/vsedach/Eager-Future

uri-template теперь использует named-readtables, которое дает возможность использовать readtables и reader macros аналогично packages. Рекоммендую named-readtables всем кто использует read-macros, и даже всем кто их не использует из за readtable-case :invert (самый перспективный метод иметь регистры типа верблюжих в символах).

План перевести uri-template на LLGPL (была лицензированной под BSD), а Eager Future переписать как совершенно новый проект с довольно уникальными свойствами среди конкурентных библиотек (тоже под LLGPL, но сначала надо додуматся как перебороть SBCL, там что-то вроде бага со слабыми ссылками - подробности (англ)).

Джастин Грант показал как можно реализовать компилятор с Ruby на Лисп (англ). Я наконец сошел с ума и тоже хочу сделать компилятор на Лисп, только из C. Зачем? Что бы взять NetBSD, скомпилировать его драйвера на Лисп, и получить Лисповую операционную систему (я же сказал я сошел с ума). Подробности на Hacker News (англ). Проект вот здесь, для начало взял Zeta-C, C компилятор для Лисп-машин, но уже видно что почти всё придётся переписывать. Для начала, может кто нибудь знает, существует ли рабочий Лисповый парсер C (в Zeta-C противная дрянь генерирована yacc-ом времен СССР и переведенная в Zetalisp)?

Protect the flock (or how to mitigate the effects of HTTP session hijacking without using SSL)

2010-10-26T14:41:00.004-06:00

So this thing called Firesheep is making a splash the past couple of days. It's a Firefox plugin that lets you hijack HTTP sessions on open WiFi networks (which presumably are NATed, hence trying to use the client IP address as extra authentication doesn't work).

It's possible to mitigate the scope of this kind of session hijacking significantly without resorting to tricks that break the back button. A note about what "mitigate" means here: we're on an open network, so any traffic from the server to the client can be spied on, and since we don't want to break the back button by using one-time information, any GET request that is made by the client can be spied on and repeated by the hijacker. However, the hijacker won't be able to make GET requests to URLs that she hasn't yet spied on, and will be unable to make POST requests.

So how does this work? I'm assuming the initial login is done over HTTPS, during which time the server sends the client a shared secret that the client then stores locally (window.name, Flash LSO, or localStorage). When a client wants to GET a URL, she rewrites it (this can be done using JavaScript on onload, for example) with a query parameter that is a hash (SHA1 in JavaScript, for example) of the secret concatenated with the URL. The server then verifies the hash before responding to the request. POST requests are handled by performing the same hashing on unique server-generated form identifiers (you're already using these to prevent duplicate form submissions, right?).

That wasn't so hard. Let me know if you see any problems with this scheme, or know of a better way.

Various Lisp news

2010-10-19T12:41:00.004-06:00

I've put uri-template and Eager Future on github and did some work on both.

uri-template got a new release, and now uses named-readtables to provide a modular way to use reader macros. I think named-readtables is a really big deal; if your library defines reader macros, start using named-readtables today. Once it is widely adopted, named-readtables can be used to facilitate things like a global move to readtable-case :invert.

I'm working on some really interesting features for Eager Future, but I'm getting stumped by how finalizers and thread-interrupt interact in SBCL. Any help appreciated (I've posted the problem description to sbcl-help).

I've mentioned CL-JavaScript before, and it's cool to see similar projects. Justin Grant did a toy Ruby to Common Lisp compiler that (no surprise) is a lot faster than Ruby at calculating factorials. The source code is a good illustration of why Common Lisp is the ultimate language implementation language.

In local news, Montreal Clojure user's group will be hosting their first meeting October 26 (details).

In less Lisp-related news, Foulab is hosting a demo party November 27.

Input needed

2010-08-15T17:52:00.003-06:00

Recently I've been doing a major cleanup/arson of CLiki. The cleanup effort was inspired by recurring comments on Hacker News of the form: "I didn't find Lisp libraries" or "I couldn't decide which libraries to use."

I would love for everyone to add a description of their Free Software Lisp libraries to CLiki with ASDF-installable tarballs and appropriate topic markers so libraries are easy to find and compare (maybe do it for cl-user.net first; I'm entertaining the idea of writing a scraper that would auto-generate new CLiki pages from cl-user.net entries). Currently this does not seem to be very realistic.

Instead I'm going to ask people who read Planet Lisp (where this blog is syndicated) to contribute to two specific tasks:

Go through the list of utilities packages on CLiki (add a CLiki entry with the *(utilities) tag for any utilities packages you know that aren't in the list) and add a description of what they contain to the package CLiki page.
Contribute to the Great Macro Debate CLiki page.

Right now there are almost two dozen "utility" CL packages offering everything from my-defun*$%# to map-nthcadadar (that's a joke, but only a slight exaggeration). It's quite hard to decide what to choose why. To me cl-utilities seems to be the most sane package, but it hasn't had development since 2006 (maybe it doesn't need it?). Disclaimer: I use kmrcl and Anaphora in my software.

The Great Macro Debate was a round-table at ILC 2009 that asked the unaskable: are macros evil?

To most post-Y2K Lisp programmers (like me) this seemed ridiculous. We grew up on Paul Graham's kool-aid. Macros are powerful, macros are awesome, they are special, don't use them when you can use a function, everything will be great.

But then all these experienced Lisp programmers came out at ILC and said that macros are bad for software maintenance. How can this be? In the absence of concrete examples, the cognitive dissonance was too great. The only defense mechanism was to tell yourself "bad programmers don't understand macros" and move on.

Two events changed my point of view. The first was encountering defclass* in a commercial project. The second was working with the TPD2 networking code and encountering my-defun (and you thought I was joking?). I came face-to-face with macros that made software maintenance hard.

The point of the Great Macro Debate CLiki page is to collect all relevant information as to why to write macros. That information will then get distilled into a sort of macro style writing document, which will contain examples and recommendations of how to write relevant macros, and what kinds of macros not to write, to make software maintenance easier.

JavaScript и Лисп

2010-08-15T11:47:00.002-06:00

Недавно появился целый ряд новых проектов обеспечивающих совместимость JavaScript c Common Lispом:

Ред Дэйли сделал Лисп байндинги для мозилловской SpiderMoney, CL-SpiderMonkey. Ещё у него есть форк SLIMEа который делает возможным вещи как автодополнение для Parenscript кода и тп. На данный момент возможности расширения сервисов SLIME под DSLы не очень хорошо поддержаны, но archimag обещал сделать все как надо.

Некий rb разработал SWANK прокси и форк Parenscriptа которые вместе позволяют подключить SLIME к браузеру (!) через web sockets. Так же он работает над компилятором с Лиспа на Флэш.

Marijn Haverbeke, Alan Pavičić, и Iva Jurišić решили реализовать JavaScript компилятор в Лиспе. Местами он уже более производителен чем SpiderMonkey.

Put JavaScript in your Lisp and Emacs in your JavaScript

2010-07-18T14:06:00.004-06:00

This month, Red Daly announced cl-spidermonkey, a set of Common Lisp bindings to Mozilla's SpiderMonkey JavaScript implementation.

Not long after that, I learned about Marijn Haverbeke, Alan Pavičić, and Iva Jurišić's CL-JavaScript JS to CL compiler. Apparently it's already faster than SpiderMonkey.

Not content with just having JS in CL, Red Daly also has a version of SLIME that integrates Parenscript to provide things like symbol completion (get it on github: http://github.com/gonzojive/slime).

A little while later another surprising discovery occurred: a certain 3b hacked up a SLIME proxy and a fork of Parenscript that lets you run a SLIME/Parenscript REPL in a browser using WebSockets. Apparently this all happened in a couple of days as part of the The 2010 Lisp Game Design Challenge.

Unrelated but still cool, 3b also wrote a CL to Flash bytecode compiler.

Book review: Nicholas C. Zakas, High Performance JavaScript

2010-07-14T10:44:00.001-06:00

Nicholas Zakas' High Performance JavaScript is a collection of tips and techniques for improving JavaScript web application performance. Although everything contained in the book has been published before, this is the first time the information has been compiled into one concise reference.

One of the highlights of the book is the discussion of reflows and interactions between JavaScript code and the browser UI. This area of JS-browser interaction is frequently overlooked by web developers, but is frequently responsible for perceived performance problems. Bringing this area of JS performance to popular attention may be book's most valuable contribution.

High Performance JavaScript is not a book to learn JavaScript from, and its weakest points are when it tries to review JS principles. The book attempts to provide explanations of JS semantics and implementation techniques, but the descriptions are inaccurate at best, wrong at worst. The explanation of JS scoping rules in particular is misleading and at times erroneous.

The book also includes dubious language-agnostic techniques like Duff's device and backward counting loops. Without guides to profiling, performance tuning principles, and an understanding of JS implementations, all of which the book lacks, this kind of advice will cause more harm than good in the hands of novice JS programmers, and its inclusion into an introductory book on JS performance tuning is questionable. The same can be said for the IE6-specific performance hacks mentioned throughout the book.

While the book has good coverage of contemporary JS profiling tools, it does not attempt to teach approaches to profiling and identifying bottlenecks. Also missing are tips on isolating sources of DOM access and reflow penalties.

Another thing High Performance JavaScript is not, is a guide to those working on JS implementations - there is no data on the JavaScript feature use and performance bottlenecks of contemporary JS web applications and libraries.

High Performance JavaScript is a concise collection of wide-ranging information on improving the performance of JavaScript web applications. However, it should be read with a solid understanding of JS and knowledge of general techniques for identifying and addressing performance problems. Recommended as a reference for anyone writing web applications.

Лисп семинары в Северной Америке

2010-07-13T23:10:00.003-06:00

2010 семинар Scheme и функционального программирования состоится в Монреале 21-22 августа. Коллеги будут вести презентацию доклада о JazzScheme. Планирую присутствовать, и выставить впечатления здесь.

2010 международная Лисп конференция будет в Рино, США 19-21 октября. В этом году не собираюсь.

Lisp and JS events

2010-07-05T14:06:00.003-06:00

Heads-up on some upcoming Lisp and JavaScript events:

Tuesday July 13, the Montréal JavaScript User Group is having a meet-up. James Duncan of Joyent will talk about why software sucks and JavaScript is the end of programming language history. Laurent Villeneuve will demonstrate idiomatic use of closures.

The 2010 Workshop on Scheme and Functional Programming is taking place at the University of Montreal August 21-22.

ILC 2010 will be taking place October 19-21 in Reno, Nevada. Abstracts are due by August 1. I'm not planning on attending.

Новый Лисп стартап

2010-07-01T14:29:00.002-06:00

Недавно Канадский Лисп-программист Уоррен Уилкинсон объявил о своем новом проекте - FormLis. FormLis состоит из комбинации вики и системы генерации веб-форм из простейшей разметки (пример), а так же безсхемной базы данных поддерживающей генерированные формы.

Уоррен решил описать конструкцию и использование встроенного Форт (Forth) компилятора в Лиспе (англ.). Интересно что Дуг Хойт посвятил главу своей книги Let Over Lambda конструкции встроенного Форт компилятора, но увидеть такое в веб-приложении неожиданно и оригинально.

Lisp in startups

2010-06-30T21:32:00.003-06:00

Calgary-area Lisper Warren Wilkinson recently launched FormLis, a Lisp-powered web application that combines a wiki with an ingeniously easy way to create custom forms (backed by a schemaless database that automatically manages form definition changes). One of the interesting technical details is Warren's use of an embedded Forth to Lisp compiler. Doug Hoyte's Let Over Lambda (read my review of the latter) features a Forth to Lisp compiler as a case-study chapter, but it's interesting to see one used in a real application.

In other news, ITA Software is trying to get acquired by Google for a billion dollars.

Postmodern programming

2010-05-02T22:24:00.001-06:00

Before the idea of postmodern programming can begin to be investigated, the question of whether anything like modernist and classical programming even exists needs to be asked.

It's not surprising that the question of how to define postmodern programming is reframed by the OO contingent (reflecting their ignorance as much as their immature self-obsession) as literally "what comes after object-orientation?" That is a silly question to ask when you don't know what object-oriented means or what came before.

James Noble and Robert Biddle attempted to address the issue in their Notes on Postmodern Programming, but focused on the act of writing programs and left the question of programming paradigms unexamined.

One possible interpretation gives surprisingly straightforward definitions: the development of the idea of algorithms constitutes the age of classical programming, while procedural and data abstraction, being the rationalization of the construction and application of algorithms, constitute modern programming.

What then is the narrative of a modern program? The evaluation strategy. Algorithms are executed in steps. Modernist programming promotes rationalization in laying out these steps. Postmodern programming rejects the linear evaluation strategy.

Curiously, we can arrive at the same conclusion by framing the relationship between procedural and functional programming in terms of a dialectic:

The thesis of procedural programming is the description of programs in terms of time (sequential execution of instructions, or branching) and behavior (the semantics of instructions), as entities operating on data - object identity, and state of addressable (nameable) places (registers, variables, arrays, etc.).

Functional programming presents a (quite literal) antithesis: programs are described in terms of data - identity (named functions) and state (first-class functions) - and operate on time (persistent/immutable data structures) and behavior (monads).

The synthesis is a nondeterministic, reified (homoiconic), first-class program. The program exists for the sake of itself, becomes the object of study and center of efforts. The computational narrative of the evaluation strategy escapes control, and so from the point of view of the programmer becomes irrelevant.

How, when, and why certain parts of the program are evaluated becomes subjective.

Perl wasn't the first postmodern programming language; Prolog was.

Non-determinism as the rejection of computational narrative and the reification of time arise naturally from physical constraints when attempting to reason about concurrency. Most of the modernist concurrency techniques concern themselves with maintaining what I call the global state illusion, or quite literally forcing a single narrative on a distributed system. Not only does the current state of the system remain unknown and unknowable, but its past history permits an exponential number of equally valid, relative interpretations.

Rich Hickey's 2009 JVM summit presentation explores these concepts of concurrency and time in a thought-provoking manner.

Манга о Лиспе

2010-04-20T21:27:00.003-06:00

Для тех кто знает японский язык, недавно наткнулся на забавные учебники Лиспа в виде манга и интерактивный. Ну а для англоязычных есть прославленный комикс Casting SPELs in Lisp (автор которого написал целую иллюстрированною книгу по теме - будет опубликована этим летом издательским домом No Starch Press).

Lisp Manga

2010-04-20T21:14:00.003-06:00

Many people will remember Conrad Barski's Casting SPELs in Lisp illustrated Lisp tutorial (Conrad's illustrated book, Land of LISP, is due out this summer). I just came upon a Lisp manga and interactive tutorial (both in Japanese) put together by a group of Japanese Lispers. Kawaii!

New native AMQP client for Common Lisp

2010-03-07T16:10:00.002-07:00

I posted about Common Lisp messaging libraries before, so I'm happy to see that James Anderson has recently released de.setf.amqp, a native Common Lisp AMQP client. (thanks to Vitaly Mayatskikh for the heads-up).

Обновление библиотек

2010-03-01T07:11:00.004-07:00

На прошлой неделе сделал релиз Parenscript 2.1 и Eager Future 0.4. В Parenscriptе добавилось неявное возвращение (как в Лиспе - те не надо всегда использовать return), возвращение множеств значений, и новое справочное руководство.

Paddy Mullen решил привести в приличный вид css-lite. На данный момент можно скачать здесь: http://github.com/paddymul/css-lite

Thomas de Grivel сделал форк uri-template: его cl-uri-templates дает возможность использовать операторы замены, которые были добавлены в третьем черновике документа URI Template. Сами операторы довольно плохо продуманы, и в добавок uri-template позволяет использовать обычные Лисповые формы в шаблонах, что намного проще.

Software updates

2010-02-28T19:07:00.006-07:00

I released Parenscript 2.1 (Parenscript now has real version numbers!) this week. Check out the updated reference manual.

Eager Future also got a new release making it optionally eager (by popular demand).

Paddy Mullen decided to take over css-lite development. His fork includes new features and actual code examples. You can find it on github (ASDF-installable package coming soon): http://github.com/paddymul/css-lite

Thomas de Grivel forked uri-template: cl-uri-templates adds the substitution operators introduced in the third draft of the URI Template proposal. I think they are quite horrible and so have abstained from implementing them.

First Montreal JavaScript user's group meeting

2010-01-08T14:21:00.002-07:00

The inaugural meeting of the Montreal JavaScript user's group will take place in two weeks, on January 21 (to coincide with CUSEC) at 7pm at the offices of Bloom Digital (481 Avenue Viger Ouest, Suite 202, right near Square-Victoria metro).

Laurent Villeneuve will present a talk about JavaScript domain-specific languages. You can follow announcements on Twitter (jsmontreal) and the mailing list.

Джон Фремлин о том как писать скоростной код на Lispе

2010-01-06T11:40:00.002-07:00

Джон Фремлин начал серию статей о оптимизации Common Lisp кода на своём блоге (англ.):

Много полезного.

John Fremlin's guide to writing fast code

2010-01-06T11:33:00.003-07:00

These haven't shown up on Planet Lisp, but they're definitely worth reading if you want to know how to write fast Common Lisp code:

I'm looking forward to more installments.

Common Lisp bindings now part of ZeroMQ 2.0

2009-12-03T16:56:00.003-07:00

Today Vitaly Mayatskikh announced the inclusion of his Common Lisp ZeroMQ bindings into the ZeroMQ 2.0 source tree. ZeroMQ 2.0 is a high-performance messaging system, which is great news if you are trying to build distributed systems in Common Lisp.

Previously, available Free Software alternatives for Common Lisp messaging included CL-XMPP (XMPP client only) and CL-RABBIT (Lispworks only).

Note that ZeroMQ 2.0, unlike version 1, no longer implements AMQP, due to performance reasons.

Как программировать скоростные сервера в Лиспе

2009-11-19T14:53:00.004-07:00

17 Ноября я презентовал мои идеи о конструкции скоростных серверов в Лиспе Монреальской группе программистов Scheme и Лисп.

Идеи презентации исходят из моей экзаменации веб-серверов Antiweb и TPD2 (смотрим презентацию Джона Фремлина о TPD2 Шибуйским Лисперам здесь). Один недостаток обоих серверов - довольно наивный подход к конкуренции и синхронизации. Я решил конструировать новый веб-сервер на базе этих примеров и размышлений, HTTP DOHC (DOHC - Dual Overhead Camshaft, когда в двигателе автомобиля двое распределительных валов в головке цилиндров - имя выбрано из за связанной двойной системы демультиплексирования в сервере).

Планирую дальнейшее развитие HTTP DOHC в полноценный веб-сервер, с интерфейсом схожим с Hunchentoot 1.0.

Ещё хочу обратить внимание - освободилось личное время для коммерческих проектов. Пишите на vsedach@gmail.com если есть что интересное.

November Montreal Scheme/Lisp User Group presentation

2009-11-19T14:36:00.005-07:00

On November 17, I gave a presentation to the Montreal Scheme/Lisp User Group about developing high-performance network servers in Lisp. I looked at the lessons to be learned from existing Common Lisp web servers, notably Antiweb and TPD2, tried out some of the ideas in my own new under-development web server HTTP DOHC along with some new ideas about threading and concurrency, and put the results of my findings into the presentation.

If you're interested in the topic, you should also watch John Fremlin's TPD2 presentation to the Shibuya Lisp user's group.

I plan on making HTTP DOHC a full-featured Common Lisp web server with an interface that's somewhat compatible with Hunchentoot 1.0.

In other news, I now have time available for contract work. Get in touch at vsedach@gmail.com.

Шаблоны и генерация кода

2009-11-19T13:19:00.003-07:00

Читатели Russian Lisp Planet уже знакомы с системой archimagа cl-closure-template. Повторять все подробности не буду, но сделаю несколько комментарий о этом подходе к шаблонам.

Главное что надо заметить - cl-closure-template является не системой шаблонов, а системой генерации систем шаблонов. Это примерно та же разница между любым парсером, и парсер-генератором yacc. Если посмотреть на диаграмму систем шаблонов на Википедии, то по сравнению cl-closure-template берет шаблон как параметр и выдает программу, которая берет дату и производит документ.

Такой подход дата генерации истинно Лисповский, и имеет множество превосходств над обычными системами шаблонов. Например можно совместить его с Common Lispовской системой reader macros и получить полноправные новые правила синтаксиса (так сделано в CL-INTERPOL и uri-template). Или пропустить генерированный код через систему трансляции типа Parenscript и получить возможность использовать те же самые шаблоны в разных языках программирования, как и делается в cl-closure-template и uri-template. Так же открывается возможность использования методов частичной эвалюации (partial evaluation) для генерации оптимизированного кода.

Templates and code generation

2009-11-18T15:12:00.003-07:00

Earlier this month Google released Closure Templates, a new templating library intended for generating HTML. Who cares? I personally dislike HTML templating, and avoid it whenever possible in lieu of s-expression based generation tools like CL-WHO. At first look, Closure Templates didn't seem to be anything new or useful.

The one thing that makes Closure Templates somewhat interesting is that the library works in both Java and JavaScript, so you get client and server-side templates in one place. I did a similar thing with uri-template by having the URI template expand into code that executed in both Common Lisp and JavaScript via Parenscript (here I have to state that despite being an author of a templating library, I still dislike templating libraries and even find my own creation annoying at times).

About a week after Closure Templates was released, Andrey Moskvitin (archimag) wrote an implementation in Common Lisp (interesting note: it took him only five days and 1/15 the number of lines of code as the original). The resulting system, cl-closure-template, similarly generates JavaScript via Parenscript.

I still didn't understand the motivation. Yesterday, Andrey was kind enough to explain it. Those pampered by web development in Common Lisp using s-expression HTML generation tools simply don't encounter the problem of trying to fit HTML templating onto the paradigm of incremental page updating via AJAX. So if you want to build an AJAX web application and use HTML templating, give cl-closure-template a try.

[Blog metanote: if you're reading this blog through its feed, you will shortly see this post show up in Russian. a CONS is an object which cares is now syndicated on Russian Lisp Planet, and I'm going to be writing Lisp-related posts in Russian as well as English. All such posts will be tagged 'lisp-ru'. Filter out that tag if you don't want the Russian version of the posts to show up in your feed reader.]

Recruiting Puzzles

2009-11-05T15:02:00.002-07:00

One of the most interesting parts of Peter Seibel's Coders at Work (see my review on Slashdot) was Peter Norvig's discussion of the Google programmer hiring process.

The impact of a bad hire on a programming team can be extremely negative - vastly increased code maintenance costs and reduced morale and productivity. "Hire slowly" is now becoming an ingrained mantra in software companies. Despite this, effective processes for evaluating candidate programmers still seem to be little known.

Interview puzzle questions (made (in)famous by Microsoft) as a tool in the hiring process came up in Norvig's interview. Not surprisingly he is against the idea. For a while puzzle questions were a fad in programmer interviews, based on the (unfounded and unverified) assumption that they were a predictor of coding prowess.

To examine why puzzle questions are a dumb idea, you need to look at the objectives you are trying to fulfill when hiring programmers:

Hire someone who is good at programming.

Hire someone who is good at programming as part of your team.

There is no need to resort to unrelated tasks with a low degree of correlation to see whether someone will help fulfill these objectives. A candidate can be assessed directly and efficiently by inviting them for three hours of pair programming.

Why are you still wasting time asking how many golf balls can fit in an airplane?

Web shortcomings and opportunities

2009-10-20T14:41:00.003-06:00

There is a very interesting post itemizing some of the perceived shortcomings of the web over at the SpaceCollective.

Some of those problems have been addressed by researchers in the past - notable examples are Freeman and Gelernter's Lifestreams, and Nelson's transclusion (I assume this is what the author of the SpaceCollective article means by the term collage; in any case you can start using a limited form of transclusion today).

Some of those problems are being addressed on an ad-hoc basis by commercial companies today. If you take some time to think about the problems, there is still a wide open field of opportunity to provide commercial offerings around the ideas there.

The history of programming language syntax

2009-10-18T09:57:00.002-06:00

http://news.bbc.co.uk/2/hi/technology/8306631.stm

Only if all the other "programming language designers" had the conscience to apologize for the pain their thoughtlessness has caused.

Computers are not getting faster

2009-10-15T16:50:00.003-06:00

When we discuss the inclusion of a feature in Lua, we ask ourselves, "OK, but will it run in a microwave oven?"

--Luiz Henrique de Figueiredo

I recently started working with John Fremlin's TPD2 HTTP server, one of the fastest web servers currently available. TPD2 uses a lot of interesting (at least from a Lisp point of view) techniques to achieve high performance. This reminded me of something I noticed in Masterminds of Programming: both Chuck Moore and the creators of Lua emphasized the tendency of computers to scale down.

When laptops and servers are getting faster processors with larger caches and more cores (which doesn't really help because we don't know even know how to think about writing software for them), it's easy to overlook the fact that we're trying to imbue ever smaller objects with computational intelligence. Moore provided the extreme example of a chip having cores with 64 words of RAM and 64 words of ROM memory each. A less extreme example comes in the form of smartphones.

At the same time use of existing systems is increasing to the point where some people are measuring how much servers they buy by the number of tons of waste their packaging generates. If each of your servers could handle three times as many requests per second, you could fit it on a computer three times as small, or have a datacenter a third of the size. The latter is a pragmatic consideration applicable at any time, but the former enables entirely new patterns of use and interaction.

The impossibility of global state

2009-10-13T16:40:00.006-06:00

(This post is a write-up of some ideas about concurrency that I've briefly discussed before).

By far the bulk of concurrency practice is aimed at dealing with systems based around shared, mutable state. Participants are asked to imagine a world with a global state whose changes are instantaneously observable by everyone. This world is a physical impossibility.

The global state illusion is based on elaborate consensus mechanisms. The concept only works because our perception of the flow of time is fixed vis-a-vis the rest of the world, which happens to be just quick enough to execute consensus algorithms over large networks that we don't get annoyed.

The common refrain to criticisms of the global state illusion is "but think of the bankers!" The consistent bank account with atomic deposits and withdrawals is an example found in almost all textbooks on concurrency. It is a neat and self-contained pedagogical tool for discussing the mechanisms needed to construct a global state illusion, but unfortunately its pervasive use seems to have done immense damage to any attempts to actually reason about concurrent systems.

Networked credit banking existed in 4th century BC Egypt. Banks still accept checks. Your bank account still has overdraft fees. Bank accounts work by reifying transactions as first-class objects. That this idea is considered novel is a testament to the pervasive confusion surrounding concurrency today.

What is the global state illusion really needed for? Distributed shared simulations. Most commonly seen in the guise of videogames. There, all the participants really do need to see a consistent view of the world with changes occurring in quantized time steps.

The key insight behind the global state illusion is that it is not time-scale independent. Whether the illusion can be maintained depends on how the participants perceive the flow of time relative to how quickly the mechanisms behind the illusion work. Banks could have implemented a pen-and-paper two-phase commit protocol for deposits and withdrawals before the advent of telecommunications. It would not have been very useful. This is the same exact issue affecting cache-coherency protocols in multi-core processors, at the micrometer scale.

The way forward in concurrency practice is the abandonment of the global state illusion in favor of constructing systems based on how concurrency works in the real world, taking cues and patterns from organizational and biological systems. This will entail the use of techniques from functional programming and linear logic.

Append-only databases

2009-10-10T16:44:00.005-06:00

Two years ago, Pat Helland wrote Accountants Don't Use Erasers, which resonated widely in the blogosphere. The central premise, append-only databases, offered a glimpse of the promises of purely functional programming. The idea itself is probably as old as transactional databases, however it has been significantly delayed in practical realization due to the nature of storage hardware.

Append-only filesystems have been around for some time for hard-drives, used mainly for archival storage (the Plan9 Venti filesystem being the most widely known example). Append-only database implementations have been held back by the high seek latency of mechanical drives. This is changing as high-capacity flash drives are becoming available.

Over the summer, Slava Akhmechet (of Weblocks fame), along with Michael Glukhovsky and Leif Walsh, started RethinkDB, a project to build a new append-only MySQL backend. Aside from the performance improvement, RethinkDB manages to solve some glaring MySQL DB management problems: hot backups (without special tools) and fast failure recovery.

The possibilities for flash storage to enable significantly greater database performance were previously noted in several papers (see Lee et alia and Graefe; even the late Jim Gray weighed in on flash drives).

A better way to do screencasts

2009-09-30T23:42:00.004-06:00

My friend Paddy Mullen recently released TerminalCast, a sort of online ttyrec player with synced audio (it is in fact based on a full in-browser JavaScript reimplementation of rxvt). This lets you do non-blurry screencast tutorials with full copy-and-paste support. I'm planning to make a Lisp web tutorial sometime in the near future.

Paddy will be giving a talk about TerminalCast at the next LispNYC meeting on October 13.

New Parenscript release.

2009-09-21T07:21:00.002-06:00

A new version of Parenscript has just been released (see the official release announcement for some more details). This release fixes a number of issues (among them poor compilation speed due to terrible choice of implementation on the part of yours truly, for which I have recently been called a lot of bad names in the Russian Lisp blog world).

Eager Future

2009-09-02T17:37:00.002-06:00

I just put up the common-lisp.net project page for Eager Future, a library for concurrent programming with composable, eager futures (see this LtU discussion of what that means).

Eager Future is a rewrite of Marijn Haverbeke's PCall library (I've blogged about PCall and extending it with support for composition before). Unlike PCall, Eager Future executes futures eagerly, which lets you use the futures composition mechanism for soft real-time programming.

Coders at Work

2009-09-02T14:49:00.002-06:00

Slashdot just ran my review of Peter Seibel's Coders at Work. The book comes out next week. Bottom line: pre-order you copy now!

The right way to use ORM: don't

2009-08-24T17:15:00.009-06:00

A couple of days ago I came across Ted Neward's essay on the problems with object-relational mapping schemes, The Vietnam of Computer Science. A really good examination of the problems with ORM, the essay wraps up in a list of six possible approaches to the problem of working with relational databases.

The database and the object-oriented application querying the database are clearly two different systems with two different domain models (the model of the programming language the application is written in, and SQL, respectively). From the perspective of domain-driven design, they represent two bounded contexts that are typically bridged using the repository pattern.

Barring the trivial ways out of the problem - using an OO database, hacking around the ORM, or "abandonment" (which seems to be a nonsensical proposition, given that the application language will need to have some kind of model different from SQL), there are three interesting alternatives left from the list: manual ORM, embedded relational DSLs, or building on your language's object model with relational-friendly classes.

I don't think embedded relational DSLs such as LINQ help solve the object-relational model mismatch in any but the most trivial ways. All they really are are macros providing syntactic sugar for database access; all the domain mismatch problems are still left unsolved.

The manual ORM and object model extension methods have proven fruitful in my experience.

Matchcraft's web directory product was already using sql2java to generate abstract Java classes (which were then subclassed and given domain logic) from a SQL schema hand-constructed from the domain model when I came on board the project. This approach worked well - the database schema and the object model were clean and sql2java's code generation provided efficient cruft-free boilerplate. There was no ORM layer to drain attention and fatten the software stack.

The only problem was that some behaviors were implemented with hand-written SQL queries right inside the derived class. This mix of domains was reflected in the culprit behaviors being problematic to modify and unit-test. By refactoring the system to use the repository pattern, I was able to make those problems go away, while still preserving all the benefits of the "sql2java and some handwritten queries" approach that yielded both a clean database and a clean object model.

On another project (this one to build a flight reservation system for small tour and air charter operators, written in Common Lisp), I went the other way with code generation. I wrote a set of macros that took domain object definitions and generated a SQL schema and CLOS objects describing those domain objects. The object instances were just lists of fields as returned by CLSQL (with type conversions done automatically based on information in the "meta objects"). The behaviors were based on a mix of multimethods specialized on the "meta objects" as well as ones executing hand-written SQL queries directly.

The above approach combined both aspects of the manual ORM and object model extension methods. While CLOS does come with an extensible meta-object protocol (and CLSQL already comes with a CLOS ORM based on the MOP), I wanted to prioritize a clean database schema above ease of integration with Lisp (as should any project where a SQL database is planned to be queried by more than one system). While Common Lisp's macros and multimethods made this approach extremely fast and easy, there is no reason it can't be used with other languages.

New homepage for uri-template

2009-08-17T17:32:00.002-06:00

uri-template now has its own common-lisp.net project page and mailing list:

http://common-lisp.net/project/uri-template/

The current version of the library is 0.6, released on 2009-08-17.

History of the American computer revolution

2009-08-12T15:27:00.003-06:00

I recently came across Steve Bank's Secret History of Silicon Valley series of blog posts. The essays do a wonderful job of dispelling the myth of Silicon Valley as "a bunch of orchards and then Hewlett & Packard came along." As with the major east-coast universities and research institutes that were instrumental in creating the computer revolution, it was the US military that turned out to have provided the resources for the start of Silicon Valley as we know it today (although in the form of the Air Force and not DARPA).

The east-coast/DARPA contribution to the computing revolution is described in similar investigative detail in M. Mitchell Waldrop's The Dream Machine: J.C.R. Licklider and the Revolution That Made Computing Personal. Blank's essays and The Dream Machine do a very thorough job of detailing the rise of today's computing industry; I consider the latter essential reading and am now happy to add the former to the same category.

Howard Rheingold's Tools for Thought is an interesting, light overview of the broader history of modern computing machines from Charles Babbage to Ted Nelson (the first edition was published in 1985, back when hypertext was still hypertext and there was no web).

The reusability fallacy and domain-driven design

2009-07-29T13:39:00.003-06:00

How can you make software reusable? The prevailing design fashion is to anticipate changes in the way that software will be used, then try to provide mechanisms for accommodating these imaginary uses. This approach would work, if you could predict the future.

The root cause of the drive to build reusable software is that the circumstances under which software is used change, ergo software needs to be changed to accommodate those circumstances. Seen this way, the concept of "building for reusability" is nonsensical. The solution is to go to the source of the problem and make software easier to change. Stop wasting time trying to design for reusability, start investing time in continuous refactoring.

One way reusability is achieved is through abstraction. All successful software libraries (graphics, algorithms, etc.) set out to solve problems in a particular domain. This is not "designing for reusability," this is designing software to address a particular domain broad enough to be useful for a wide variety of applications.

Platonic software design would consist of composing these domain libraries together using engineering techniques of abstraction, the outside ones building on the inside ones, like the layers of an onion. Two problems preventing this from being reality are leaky abstractions, and domain mismatch, making techniques such as Open Implementation necessary.

The only code reusability technique that is somewhat successful is the strategy pattern, but that is because the strategy pattern is just first-class functions and polymorphic types, which have a simple formal model behind them.

Live SQL database schema updates

2009-06-28T13:44:00.004-06:00

I previously wrote about managing live DB schema changes using protocols and context-oriented programming. About a month ago, I came across Jonathan Oxer's presentation about dealing with live schema changes to MySQL databases. The technique Oxer presents is a kind of obvious-in-hindsight thing that is beautiful in its simplicity: run update scripts and retry if an error (unknown table/column) in the query occurs.

Readers familiar with Geoff Wozniak's work will notice the similarity to his ideas about working with undefined functions (which, incidentally, was previously discussed on this blog in the context of using metaprogramming techniques to implement DB abstraction layers).

This is something I'm definitely going to try in my next SQL database based project.

Why your language needs macros

2009-06-08T20:51:00.004-06:00

A couple of days ago someone posted yet another "why do I need macros?" thread on Hacker News. The usual arguments and unconvincing examples arguing for macros were posted. Noted absence were the arguments against macros (all of which seem to be of the variety "programmers are too dumb to understand someone else's macros" - if you were at the Great Macro Debate at ILC 09 you would have heard it stated more eloquently).

I've been thinking about macros in terms of domain-driven design lately, kicking around my idea of "domain onions" (I'll write more about this later), so I decided to post my current thoughts about why every programming language that aspires to be general-purpose needs macros.

Gelernter

2009-06-08T20:27:00.004-06:00

Two years ago I posted a review of Nicholas Carriero and David Gelernter's How to write parallel programs. Today I came across an Edge roundtable discussion with David Gelernter (via Patrick Logan).

The entire discussion is fascinating, and I recommend reading up more on Gelernter's work if you are not familiar with it before watching the interview.

For me, there were three new insights from the roundtable:

Message passing is the assembly language of distributed systems.

Databases are a way to communicate through time. Networks are a way to communicate through space. Both are symmetrical. The point of Linda was to unify them.

The most powerful computers today are botnets. Botnets are also on the leading edge of distributed systems techniques.

In the second video, Gelernter discusses Lifestreams. It's amazing how closely FriendFeed, Twitter, and the new Facebook are all following the roadmap established by Lifestreams over a decade ago.

Debugging with H-toot

2009-06-04T14:02:00.002-06:00

Andreas Fuchs shows how to get Hunchentoot 1.0 to go into the debugger on handler errors, like previous versions of Hunchentoot used to do when *catch-errors-p* was nil.

This should have come as part of the 1.0 release IMO.

That may be, but my library is your programming language

2009-05-21T16:46:00.003-06:00

In another instance of look-what-I-can-do-with-closures-and-late-binding, Benjamin Pollack offers a criticism of C# and Linq.

On the value of metaprogramming

2009-05-04T17:37:00.002-06:00

Several weeks ago I wrote about a way to implement Smalltalk-style predicate function-to-SQL translation in Common Lisp, so I was amused to come across Dejavu for Python (via Jonathan Ellis), which implements the same technique by inspecting CPython bytecode.

It's amazing what kind of dumb hoops people will jump through when they don't have a system that permits real metaprogramming.

Review: Let Over Lambda

2009-04-22T12:35:00.002-06:00

So after a lot of not reading Doug Hoyte's Let Over Lambda, I finally did manage to read it all the way through.

My overall impression first: Hoyte styles the book as a successor to PG's On Lisp; I think Let Over Lambda falls short of that goal, although it does contain enough interesting material to make the book worthwhile.

The best parts of the book are the chapter on read macros and the subsection on sorting networks. Great, practical examples and illustrations of good programming style.

The worst parts of the book are the chapter on implementing a Forth interpreter in Lisp and the "caddar accessor generator" (it's ok for me to say this because the name of this blog is ironic).

The chapter on anaphoric macros has finally made me change my mind about those things. It's ok, use them when you need them. All the stuff about "sub-lexical scoping" (ie - various interesting ways of using macros to capture free variables) didn't really make a deep impression on me - maybe I'm just too dull to see any good uses for that.

As pointed out in other reviews, the book could have used a lot more proofreading (esp of the code) and editing. Hoyte chose to self-publish the book, which I think was a mistake (and just today Tim Ferriss blogged about some other reasons why it's not a good idea).

To cap the review, don't read Let Over Lambda until you've read On Lisp. It's a fun book about some interesting Common Lisp programming techniques, but it could have been shorter.

Problem-solving is hard, let's go write XML configuration files

2009-04-15T21:23:00.003-06:00

Previously I blogged about why the premise behind software frameworks turns out to be a logical fallacy. This blog post will continue my attack on the framework cult by examining the reasons why people continue to believe in the myth of increased productivity through frameworks.

There is one word that can summarize my argument: comfort.

Consider carpentry tools. How do you use them? What do you use them to accomplish? Now consider a toy construction set such as the Erector. The toy construction set offers you a path you can follow to arrive at some cool artifact, even if you don't know exactly what you want to do. The construction set can offer this security because it limits what you can accomplish, and how you can accomplish it.

According to Buddha, ignorance is the root of all evil. According to Christian tradition, people are inherently evil. It is then no surprise that most of the time most people do not know what they want to do. Finding out "what" is hard, requiring a lot of time and learning. In the realm of software development, this is practiced by methodologies such as domain-driven design. It is a lot easier to write XML configuration files instead.

There is a misguided comfort that comes from knowing that you did a day's worth of honest work. It doesn't matter if what you are doing is leading you down the wrong path, because with a framework you are at least accomplishing something, even if that something will not bring business value. As a project manager who decides to use a particular framework, you are in effect acting as a proxy sales agent for the party promoting that framework - selling your customer a solution that may not be in line with your customer's goals.

Many logical fallacies go into the typical software development decision-making process. Frameworks in particular are notoriously prone to the bandwagon effect (how many "enterprise" web-development frameworks for Java have come and gone and with what ridiculous frequency?). Any person held responsible for the consequences of a decision will be prone to post-purchase rationalization (remember that before a person tries to sell a methodology to his organization, he has to have been sold on it her/himself), so the bandwagon effect is frequently used as an argument for adopting a particular framework. In addition, nebulous terms such as "enterprise" (which, because of its strong association with frameworks, has almost universally acquired the definition as "verbose junk" in the software development world) somehow end up in place of well thought-out arguments and empirical evidence.

Obviously, there is some circumstantial evidence that frameworks do enhance productivity - people become experts at particular frameworks and can efficiently develop applications. This is not because they are using a particular framework, or because they are using a framework at all. This is because they have become experts at it.

Closure-oriented metaprogramming via dynamically-scoped functions

2009-04-09T18:52:00.007-06:00

Today I came across this post from the ll1 mailing list (almost 7 years old now, via Patrick Collison's blog) from Avi Bryant explaining how Smalltalk's message-based dispatch permits a type of metaprogramming with closures, as an alternative to macros.

Of course if you've read Pascal Costanza's Dynamically Scoped Functions as the Essence of AOP (and if you haven't, click the link and do it now; it's one of my favorite CS papers), you will realize that there is no need for message-based dispatch or any kind of object-oriented programming to do that. All we need are dynamically-scoped functions.

Here is how I approached the problem:

(defpackage "BAR"
  (:use "COMMON-LISP")
  (:shadow #:=))

(in-package "BAR")

(defmacro dflet1 ((fname &rest def) &body body)
  (let ((old-f-def (gensym)))
    `(let ((,old-f-def (symbol-function ',fname)))
       (unwind-protect (progn (setf (symbol-function ',fname) (lambda ,@def))
                              ,@body)
         (setf (symbol-function ',fname) ,old-f-def)))))

(defmacro dflet* ((&rest decls) &body body)
  (if decls
      `(dflet1 ,(car decls)
         (dflet* ,(cdr decls)
           ,@body))
      `(progn ,@body)))

(defun first-name (x) (gnarly-accessor1 x))
(defun address-city (x) (gnarly-accessor2 x))
(defun = (&rest args) (apply 'common-lisp:= args))
(defmacro & (a b) `(block-and (lambda () ,a) (lambda () ,b)))
(defun block-and (a b) (when (funcall a) (funcall b)))

(defun some-predicate (x)
  (& (= (first-name x) "John") (= (address-city x) "Austin")))

(defun make-parse-tree-from-predicate (predicate-thunk)
  (dflet* ((first-name (x) '#:|firstName|)
           (address-city (x) '#:|addressCity|)
           (= (a b) `(= ,a ,b))
           (block-and (a b) `(& ,(funcall a) ,(funcall b))))
    (funcall predicate-thunk nil)))

Then (make-parse-tree-from-predicate #'some-predicate) yields (& (= #:|firstName| "John") (= #:|addressCity| "Austin")), which we can manipulate and then pass to a SQL query printer.

Here I implemented dynamically-scoped functions using unwind-protect, which is not as powerful (or, possibly, efficient) as the implementation presented in Costanza's paper, but is simpler (I also used the same trick to implement dynamically-scoped variables in Parenscript).

The property of the same Lisp code to mean different things in different contexts is called duality of syntax by Doug Hoyte in his excellent book Let Over Lambda (almost finished reading, promise to write a review soon). Lisp offers this property both at run-time (via late-binding and closures) and at macro-expansion time (via homoiconicity and the macro-expansion process itself).

Another technique from Let Over Lambda illustrated in the above code is the recursive macro. This one is a personal favorite of mine; I find that the iterative simplification that recursive macros express provides very clean and maintainable code.

This code also provides examples of the two problems that the closure-oriented metaprogramming approach encounters in Common Lisp:

The first is the fact that we had to shadow = in our package. Common Lisp forbids the redefinition of the functions, macros and special forms defined in the standard, so we have to go out of our way if we want to achieve that effect. Barry Margolin provided a rationale for this in comp.lang.lisp post.

The second is the fact that Common Lisp has so many special forms and macros - and just happens to be one of them. Smalltalk avoids this problem by doing virtually everything via message passing and closures. In Common Lisp we don't have this straightjacket, but we also don't have this luxury of assuming that everything is an object or a closure.

Another Common Lisp feature that might break this example is function inlining (then again, I did just write about the benefits of late-binding...).

Masterminds of Programming

2009-04-08T17:42:00.004-06:00

Today my copy of Masterminds of Programming arrived in the mail from O'Reilly; a small reward for giving a lightning talk at ILC.

The book is a series of interviews with programming language designers. Along with some expected atrocities like Stroustrup on C++ and Gosling on Java, and bizarre ones such as a 50-page interview with Jacobson, Rumbaugh and Booch on UML, there are interviews with Adin Falkoff on APL, Moore on Forth, Wall on Perl, and a few others. The functional camp is well-represented with SPJ, Hudak, Wadler, and Hughes interviewed about Haskell, and Milner giving an interview about ML.

It is telling that right at the preface the book starts off with an urban legend: "children can learn foreign languages much more easily than adults."

Some of the interviews are very revealing. The discussions present an entertaining window on the cavalier attitudes and biases of many programming language designers, which helps explain some of the dysfunction of the software world today. I don't think this is what the editors intended, but it makes for hilarious reading material.

Some of the interviews can be frustrating to read (every third question in Falkoff's APL interview seems to boil down to "lolz funny syntax"); thankfully this is balanced out by absolutely delightful ones such as Moore on Forth (IMO, the highlight of the book), and the Objective-C interview with Brad Cox and Tom Love. Overall the quality of the interviews varies widely, but not surprisingly mostly seems to correspond to the quality of the language being discussed.

Ultimately Masterminds of Programming is worthwhile not for its insights into programming language design (most of which unsurprisingly boil down to "oops I made a bunch of mistakes because I didn't start with a good model/think/know any better/know enough math"), but into programming and computing history in general.

To finish this review where it started off, here is another unintentionally amusing bit of insight from the preface:

Imagine that you are studying a foreign language and you don't know the name of an object. You can describe it with the words that you know, hoping someone will understand what you mean. Isn't this what we do every day with software?

It comes as no surprise that there is not a single entry for either "macro" or "metaprogramming" in the book's index (although Wadler does make a passing mention of Lisp macros in the Haskell interview).

P-Cos Blew My Mind

2009-03-26T20:12:00.002-06:00

This post contains my impressions about the rest of ILC 2009. I'll start off with something that really impressed me.

One of the things I have been thinking about lately is database schema evolution. The flip side of database schema changes are the corresponding changes in the client code they entail. Combining the two with live system upgrades can potentially give rise to inconsistencies. Even ignoring databases, loading code into a multithreaded Lisp image can result in undesired behaviour since the loading is non-atomic.

This problem was discussed on comp.lang.lisp several years ago, with the general consensus being that some sort of atomic loading mechanism was needed to address the problem.

However atomic loading alone does not eliminate inconsistencies for systems providing services via asynchronous protocols, such as web applications. Any users in the middle of a workflow consisting of a chain of requests to HTTP resources will be affected if any of those HTTP resources are changed.

Pascal Costanza came to the rescue by presenting (during a lightning talk) a solution utilizing context-oriented programming. Each set of updates was integrated into the system as a new layer. Atomicity is provided by the fact that layers can be (are?) activated atomically, and can be made completely independent of each other. By associating layers with web application sessions, Pascal was able to preserve consistency for those users in the middle of a session during the time of update.

In a fascinating discussion on protocol versioning on Jane Street's OCaml blog a while back someone advocated essentially the same approach to the problem by utilizing two servers running different versions of the application. Pascal's context-oriented approach not only eliminates the need for the extra hardware (one server for each version of the protocol), but also provides an elegant way to structure the code for multi-version protocols, and to apply other, orthogonal updates that would affect users of all protocols provided by the system, which would otherwise require backporting patches.

If database access is implemented as an abstraction layer that acts as a protocol, the same technique can be applied to schema changes as well.

From the above discussion it is easy to overlook a really neat fact, but Nick Levine's lightning talk came to the rescue: load and fasls make a really great patch distribution mechanism. You can view the code from his talk here.

Shriram Krishnamurthi gave a very nice talk about hooking kids on Scheme by letting disadvantaged inner-city middle-schoolers put lambdas in their lambdas so they can make videogames in their cellphones. Purely functional programming a-la How to Design Programs turns out to be a really great way to teach algebra. Shriram also dislikes the OLPC project and thinks Etoys is weak.

Gerald Sussman gave a talk that essentially argued against formal methods for systems design, and for extensible systems with flexible failure modes.

One of the key reasons why MIT shifted its introductory CS curriculum away from the SICP-style bottom-up abstractions building approach is that the behaviour of modern systems components is too complicated for it to be practical for them to either be well-specified, or modelled in a reductionist way. A lot of the time engineers have to resort to an empirical approach to discovering the actual semantics of a sub-component.

To manage this complexity, Sussman argued for open systems that permit a great degree of extensibility and continue to function under various failure modes. An example he used was an autopilot system: it should continue to work under unexpected conditions such as control surface failures. This echoes some of the ideas of Richard Gabriel about mob software. Although Gabriel was at the conference, the term itself never came up, but Richard did object to macros at the macros debate by mentioning that they would be a hindrance to constructing systems worked on by thousands of programmers.

Fail-fast behaviour of a whole system under unexpected circumstances is something that formal specifications cannot avoid. A great quote from Sussman was: "proofs considered harmful." What Sussman was arguing for, in his words, was high-quality abstract specifications, not low-quality well-specified ones.

Sussman presented several ideas about taking inspiration from biological systems, among them biological degeneracy, which can best be summed up as "doing different things to get the same result," and the fact that a relatively small number of genes are responsible for common physiological structures in organisms.

The bio-mimetic argument was echoed again in a lightning talk by someone whose name I unfortunately cannot recall or look up (as the full list of lightning talks has not yet been posted anywhere). One of the things mentioned was parallelism in multi-cellular systems - of course I had to jump in and point out that the best lesson we can take away from parallelism in the real world is a rejection of the concept of global state (more on that in an upcoming post).

Olin Shivers gave essentially the same talk about his system for expressing scoping and iteration in terms of graphs as he did at Danfest, and this time wasn't any more exciting. Someone actually fell asleep and started snoring loudly a few rows down from me. The discussion at the end was quite good though, one of the things Shivers emphasized that echoed Sussman's keynote was the fact that unspecified behaviour actually gave you more opportunity for expressive power.

I gave a lightning talk based on a blog post I made previously, arguing that the criteria for whether language X is a Lisp should be how well you can write a metacircular evaluator for that language. No one booed or threw things at me, and some very smart people made insightful comments, so I think it went ok. The question of static typing came up, and after the talk I had a big argument with a couple of people trying to explain what type systems are and what they do. Typed calculi need to be taught as part of an undergrad CS cirriculum - most people have a very skewed understanding of what type systems are and this lets language "designers" get away with doing a lot of stupid shit.

ILC 09 Pt. 0

2009-03-24T08:50:00.004-06:00

Flew into Boston on Monday, arrived at the Stata Center just after the conference lunch. Highlights so far:

Michael Greenberg's lightning talk about TRAC, both for being probably the most well-prepared 5 minute talk ever, and for explaining the key essence (self-modifying code) of pure macro languages. Later during the macros debate Greenberg made the very insightful point that conceptually the Lisp language and Lisp macros are two distinct systems and need to be reasoned about as such.

Joe Marshall's daughter's insight about the subject of his talk: "[continuations are] just autosave for your program!"

Pascal Costanza's superhuman knowledge of Lisp history, wit, and strong opinions.

Some things that have been done to death and should be irrelevant but still managed to be somewhat entertaining: the "future of Lisp" panel and the "are macros bad" debate.

Parenscript birthday present

2009-03-15T04:08:00.005-06:00

A while ago I mentioned I was going to announce some exciting news about web development tools. Shortly thereafter my priorities changed, and I shelved the project with the intention of picking it up again in the future. Then I remembered about LispNYC's participation in the Google Summer of Code program - if I can't do the project now, why not try to get funding from Google to have a student work on it?

Here is what all this is about:

The PSDE project aims to develop an Emacs-based JavaScript programming and debugging tool for AJAX-based RIAs. The implementation will provide an unobtrusive client-side script that can be loaded alongside any JavaScript web application, and an Emacs interface (REPL) that will enable debugging of remote and mobile clients, including the possibility of no-reload drop-in for live user sessions.

Along with an interactive prompt/REPL, PSDE will provide a profiler, tracing and logging facilities, a DOM inspector, a completion and documentation system for DOM symbols, and other useful web programming tools, both by using the reflective capabilities of JavaScript, and by providing hooks (a la Open Implementation) into the Parenscript compiler to provide metaprogram information that cannot be gleamed using runtime techniques or analysis of JavaScript code.

In addition to providing a valuable tool to the web development community, the OI extensions to the Parenscript compiler included as part of the PSDE project will be useful in their own right to those wishing to create other web development tools based on Parenscript, or web developers using Parenscript and needing advanced JavaScript generation capabilities.

The project has its roots in the "browser Comet REPL" demo I gave during my talk about Parenscript at LispNYC in September 2007, but the idea of making a "browser SLIME" didn't occur to me until this past November, when Daniel Gackle told me: "Why don't you make a browser SLIME?"

If you are a student that might be interested in this project and qualify to participate in Google SoC, or know of such an individual, get in touch: vsedach@gmail.com. I'll be happy to answer any questions and help you with preparing an application. Google will start accepting student applications March 23rd, with the cut-off date being April 3rd.

UPDATE: LispNYC has not been selected as a mentoring organization for SOC 2009. I would like to fund this project myself, but currently cannot afford it.

Parenscript's 4th birthday

2009-03-14T16:30:00.000-06:00

Today is a day of many celebrations. As most of you are aware March 14 is π Day. It also happens to be Einstein's birthday.

Four years ago, Manuel Odendahl announced the release of Parenscript to the public. Reflecting on the original post in the context of what Parenscript is today, the power and appropriateness of Manuel's design have more than proven themselves, but also I see the amount of exciting work that is still ahead.

I think I finally understand what Alan Kay is saying about Lisp

2009-03-13T18:15:00.006-06:00

Joe Marshall recently wrote a series of very entertaining blog posts telling the story of his first experiences with Lisp:

I had a similar experience with Lisp - I didn't go to MIT or take 6.001, but reading the first couple of chapters of SICP changed my entire outlook on computer programming. By the time that happened (the summer of 2002, right before I started university), I was already somewhat proficient with C, although I wasn't particularly interested in computer programming as an activity in and of itself.

The funny thing is I was exposed to Scheme my first year of high school through Mike Zamansky's MCS1 at Stuy. That experience wasn't particularly memorable, even less so was one of the other programming languages used in the course (Python, I think?). On the other hand the course also taught a whole bunch of really neat stuff in StarLogo, which as they say in Canada was the cat's ass.

An even more amusing fact is that after going to see the professor before the start of the first term and taking the challenge exam that would give me credit for the first computer science course, I decided that since the university computer science courses didn't look anything like SICP, I would probably be better off investing my time in a math degree. The algebra and calculus examples in SICP were my first exposure to elegant computational mathematics, and a key reason for choosing math and not something else.

What does this have to do with Alan Kay?

Yesterday before falling asleep I was plagued by the question: why don't I enjoy using Haskell as much as Lisp? Haskell is purely functional, it features a really neat and unobtrusive type system, which when taken together with the great pattern-directed invocation programming style provides a better alternative to object-oriented programming. It's a really great programming language.

Could the reason be the ugly syntax? No, that's easy to fix. The type system doesn't bother me. There's a template system for both Haskell and Liskell syntax that provides preprocessor-style macros, but monads actually provide a much more powerful way of building control abstractions than macros do.

The only thing I could think of that Lisp has that Haskell can't provide is a dynamic runtime system. It's as if Lisp comes with a really neat invisible virtual machine.

Among the many nice things Alan Kay says about Lisp, the term late binding comes up often. Practitioners of programming languages that Alan Kay did not have in mind when he invented the term "object-oriented" have taken it upon themselves to equate this to the concept they term dynamic binding, which they define to be type-directed dispatch done at runtime.

This is a textbook example of cargo cult programming. Dynamic types and runtime dispatch are not axioms of Lisp and Smalltalk, they are the emergent properties of self-describing computational systems. The key is that the definition of Lisp is written in Lisp. The "invisible virtual machine" in Lisp is Lisp. That is what Alan Kay means by late binding.

Well, this insight did take almost seven years, but at least now I have a snappy label for the dynamic languages du jour whose existence helps put a lot of computer book publishers' editors' kids through college and kills hundreds of thousands of trees every year: cargo cult programming languages.

The question that remains unanswered is why isn't Haskell self-describing? The reason is that there are actually two computational systems behind Haskell: one for the language itself, and one underlying the type system for the language. If type systems could be expressed in a metacircular way by the systems they were trying to type, they wouldn't be able to express anything about types (restrictions on computational power) of that system.

You can read more about the metacircular definition of Lisp in several books. The first of these is the original Lisp 1.5 Programmer's Manual; Alan Kay has called the metacircular definition of Lisp provided there "Maxwell's Equations of Software." SICP includes a section on constructing a metacircular evaluator, and a whole chapter based around extending that evaluator with non-determinism and logic programming. The most thorough examination of the metacircular evaluation formulation of Lisp is present in John Allen's highly recommended 1978 book, Anatomy of Lisp.

Frameworks and the conjunction fallacy

2009-03-12T19:42:00.003-06:00

Frameworks are great. After all, some helpful way to do X combined in some helpful way with some helpful way to do Y must be a whole lot more helpful than just a way to do X and just a way to do Y, right?

Wait a minute, anyone who has used a framework might say, what if someone wants to do Z instead of Y? Why, of course, say the framework "architects," we'll just provide a helpful way to help you choose helpful ways.

How helpful! Now not only do you have to know how to do X and how to do Y and how the framework helps you do X in a helpful way with doing Y, but you also need to know the helpful mechanisms behind letting you choose the helpful ways.

Clearly the original argument for helpfulness broke down somewhere. But where, and why?

The underlying fallacy behind the majority of software design today is the belief that computer systems can be "useful" and "helpful." Useful and helpful for doing what? For doing what they were designed to do. Stated in these terms it is immediately apparent that this mindset is a tautology. Completely useless as a basis for reasoning.

Is there a better way of thinking about software? Let's start by asking why. The entire motivation underlying our enterprise is the desire to accomplish X and Y. Each step we take can either bring us closer to that goal, or not. Given that time and other resources are finite, each step that does not bring us closer to the goal is "unhelpful" - it gets in the way of what we want to do.

I believe the right way to think about computer systems is as things that get in the way of what you want to accomplish. This way the goal of software design becomes not getting in the way of what you want to do.

Given this approach it immediately becomes obvious that the argument presented at the start of this post is simply a conjunction fallacy. Likewise many other "reasonable assumptions" about software that are not borne out by experience can be shown to be flawed a priori. Most importantly, this mindset helps prevent such "reasonable assumptions" from being taken up in the first place.

While this post debunked one of the arguments used to both justify the development of frameworks and their use, the decisions surrounding the latter are also driven by other logical fallacies, and, like the vast majority of human decision-making, by emotions. In a forthcoming post I will examine some of these factors.

[Major thanks to Ryan Holiday for providing the inspiration for this blog post.]

Assorted Lisp news

2009-03-12T03:01:00.003-06:00

Last week I came across Bartosz Milewski's blog post criticizing the proposed implementation of futures in the forthcoming C++ standard. Milewski's chief dissatisfaction was the absence of a mechanism for composition. PCall (which I've blogged about before) was in a similar position, so I decided to implement a mechanism for non-deterministic composition and send in a patch. Milewski's blog post also spawned an excellent discussion about futures on Lambda the Ultimate.

Today I rewrote the Parenscript tutorial to use the recently released 1.0 version of Hunchentoot instead of AllegroServe. Edi Weitz and Hans Hübner did a major redesign for the 1.0 release, breaking interface compatibility with previous versions of Hunchentoot. The new interface provides greater Open Implementation capabilities, and makes a sharp demarcation between methods intended for OI and those for regular server programming. I like it.

Beware that if you're not using LispWorks, the 1.0 release of Hunchentoot depends on certain library capabilities (I suspect it's usocket but haven't verified) that as of the time of writing haven't been made into official releases yet. This means that if you get Hunchentoot dependencies via ASDF-Install it will likely not work (for me, it just instantly dropped all incoming connections) - use clbuild to get the latest repository versions of the dependencies.

Earlier last year I found out about Doug Hoyte's Let Over Lambda and after reading the sample chapters promptly got excited. I visited the site recently and found out that the book was published a few months ago. This morning my copy arrived in the mail - I'll be posting a review here later. In the meantime you can obtain your own copy.

LispNYC is once again looking to participate in Google's Summer of Code program. The list of accepted organizations hasn't been announced yet, but you can start proposing summer projects on the LispNYC website.

Just found out about lisp.ru. For a non-English generalist Lisp website the forum gets a fair amount of traffic.

Cassandra of Facebook, or A Tale of a Distributed Database, part 2

2009-03-10T04:31:00.000-06:00

This is the third in my series of blog posts about Facebook's Cassandra distributed database. Part 0 discussed the background of the problem Cassandra is meant to address, while part 1 gave an overview of the distributed systems techniques employed by Cassandra. This post is a scattering of my observations from reading the code.

The most obvious feature of Cassandra's code is the pervasive presence of checksums in communication and data handling modules. Checksums are used both to detect data and message corruption, and as a means of finding out if replicated nodes are out of sync.

Cassandra is a production system with a large deployment and the management features present reflect this. There is code for measuring node statistics and sending them off to a collection server. Nodes register themselves with both Zookeeper and JMX cluster-management services, although exactly what both of those are used for at Facebook is unclear as their cluster-management tools have not been released as free software.

The mechanism for selecting nodes for replication can be customized to use metadata about machines to choose nodes on redundant networks/power grids/backplanes/etc to increase availability. The strategy provided in the code indicates that Facebook structures their Cassandra deployment using IPv4 addresses so that all the machines with the same third octet of an address are in the same rack, and all machines with the same second octet are in the same datacenter.

The gossip protocol, besides being used for failure detection, is also used for load-balancing the cluster. Workload is measured as the number of requests per number of keys in a given time window that are handled by a node responsible for a particular interval of the key ring, and is disseminated by each node to the others. To alleviate high load, a node may move itself around on the key ring to more evenly distribute the keys between itself and a lightly loaded neighbor. The approach is an implementation of Abdallah and Le's Scalable Range Query Processing for Large-Scale Distributed Database Applications.

The gossip protocol itself is rather interesting, featuring three stages (gossip message, ack, ack-ack).

An interesting artifact is the com.facebook.infrastructure.continuations package, which has some stubs based on the Javaflow bytecode continuation transformer. You would guess this would be used for the server code since it's based on non-blocking IO, but the server code is actually hand-coded staged event-driven. The stubs in the package aren't used anywhere else, which means that some other Facebook project must be using those. I wonder what for?

The code itself can be found at http://code.google.com/p/the-cassandra-project/, but seems to be in the process of being moved to a different repository. In the meantime, there is an active git repository at http://wiki.github.com/jbellis/cassandra-dev that features community-submitted bugfixes and improvements.

To end on a light note, it is refreshing to find that the authors of Cassandra give a nod to the LOLspeak code commenting guidelines:

 * 3. Set one of teh messages to get teh data and teh rest to get teh digest
  // 4. SendRR ( to all the nodes above )
  // 5. Wait for a response from atleast X nodes where X <= N and teh data node
   * 6. If the digest matches return teh data.

Cassandra of Facebook, or A Tale of a Distributed Database, part 1

2009-03-10T04:20:00.001-06:00

This is the second part of my examination of the Cassandra distributed database. Part 0 described the problem that Cassandra is trying to address; this post will describe the distributed systems techniques that it utilizes to that end.

The basis for this post is a presentation describing Cassandra by Prashant Malik, Karthnik Ranganathan, and Avinash Lakshman given to the Facebook staff and available online: http://www.new.facebook.com/video/video.php?v=540974400803#/video/video.php?v=540974400803 (hosted on Facebook, an account is required for viewing). James Hamilton provides a summary of the presentation on his blog.

Underlying Cassandra is the technique of consistent hashing. Using consistent hashing, the key space can be modeled as a circle of the keys' hash values, and nodes assigned to points on that circle, so that a node is responsible for an interval of the circle of key hashes between itself and its next neighbor. Nodes leaving or joining only affect their previous neighbor, and lookup has a very low communication cost. Due to its great simplicity and robustness compared to other mechanisms, consistent hashing is probably the most significant development in distributed systems in the 1990s - virtually all current peer to peer systems are based on it.

Cassandra uses a gossip protocol for determining cluster membership and for failure detection (and for load-balancing, discussed in the next blog post). Failure detection in this context means the various failure detector mechanisms that can be used to achieve consensus in asynchronous distributed systems with unreliable nodes. Given unlimited time to finish a task, it is impossible to distinguish a dead node from one that is slow - failure detectors use timing assumptions and heartbeat messages between nodes to provide an answer (with some degree of uncertainty), something that would otherwise require a synchronous network between nodes. Cassandra implements a failure detector based on Hayashibara et alia's The φ Accrual Failure Detector; the presenter points out that some "ghetto" failure detectors with simpler mechanisms do not work very well in practice.

Each interval of the hash circle is replicated on a set number N of nodes. Cassandra provides a choice of replication scheme: optimistic replication, which gives eventual consistency, or stricter approaches for writes and reads: quorum write and sync on read. Optimistic replication allows writes even if all nodes that are responsible for storing the particular key are down: the node receiving the request logs it and later hands it to the appropriate nodes when they come back up. Under the quorum write scheme, a write is not successful until at least a specified x number of the N total replicas have performed the write. It would seem that if x=N, then we get both monotonic read and write consistency. Sync on read synchronizes all replicas on each read request, which gives monotonic write consistency.