cromwellian

2011-05-15T01:09:00.000-07:00

Myths and Misunderstandings of Chromebooks

When the iPod was launched, pundits immediately compared it to the existing mp3 player market. It was too big, too expensive, not powerful enough, and lacked the features other players had.

Then, when the iPhone was announced, a similarly sounding chorus declared its deficiencies, some of which I detailed here in 2007 It had no MMS, no swappable battery, no 3g, etc. Oh sure, there were other smartphones on the market that had a much longer list of features and were even cheaper, but it didn't matter. Paul Buchheit covers this "more features = better" philosophy here.

Now, Paul is somewhat pessimistic about Chrome OS, which I disagree with, but what's interesting, is that some of his arguments against Chromebooks I actually used myself when the iPad came around -- If already have an iPhone, and a Macbook Air, why do I need this tablet thingy? It sucks for content creation, and if I already lug around my notebook, why would I lug this thing around in addition? I was wrong, because there are times of the day where you need to create content, and times when you simply need to consume it, and tablets are perfect for the latter. More on that divide later.

The parallels today are appearing again. At $349, Chromebooks are too expensive compared to Netbooks at the same price level! Netbooks had been tried before, and failed! With Windows 7 basic or whatever, on a Netbook, you have far more flexibility and features! If someone already has a tablet, and a notebook, why would they want a Chromebook! And so on. There may be some merit to those arguments, but at iPad launch, the idea that a third kind of device wasn't needed also had merit. After all, tablets had been tried before and failed. We now know there was a market need.

Content creation vs Content Consumption

Where I disagree with Paul and others, is that even a souped up tablet is not a good stand-in for a work device. Perhaps with a large external monitor, and external keyboard and mouse, but as tablets constructed today, I would not want to write code on them, or even long blog articles like this. Perhaps it's my generation and young people won't have such hangups, but my generation is still a large market.

Thus, I assert, the need for a traditional WIMP device: physical keyboard, mouse, connection for monitor. I don't think enterprise IT would really find this controversial. So the next question is, why would a Web-only device be better than one with "native apps".

Myths about Chrome

In Paul's message on Chrome OS, he rightly sees that Android is becoming more "webby", but does not comment on the fact that the Web is becoming more "natively". What is the difference between an offline, cached, Chrome Web Application, that uses file system APIs, and WebGL, and a Android app, other than the fact that one is written in Java and uses Java APIs, the other is written in JavaScript and uses Browser APIs? Is Angry Birds Chrome really that much different than Angry Birds Android?

The principle difference between Web, Flash, and Android, is merely the difference in virtual machine, programming language, and API flavor. With Chrome, you have V8 as the VM, JavaScript as the source language, and HTML5 as the API to the VM. With Flash, you've got Flash VM + Actionscript3 + Flex APIs. With Android, you have Dalvik, Java, and Android APIs. All three have APIs for UI, 2d/3d, sound, network, etc. All three platforms have "web-like" install/update models, and all three have webby sandbox security models.

Well, you say, Android has NDK. To that I answer, Chrome has Native Client.

Well, you say, Android is Linux. To that I answer, so is Chrome OS.

Well, you say, Android doesn't force every app be a "document". To that, I point to Bespin and Angry Birds.

The conceptual gulf just isn't that big folks.

Other Myths overheard

If I'm not online, I can't do anything!
Not true, Web apps can be offline. Chromebooks have local storage which can act as a sync repository/cache. It will depend on how apps are written. It's really no different than iOS/Android.
Everything is in the cloud, Google can read everything.
Conditionally true, depending on the app, data can be encrypted on the server with only the client app able to view it
I can't access some critical windows apps
True in some cases, false in others, see: Citrix, VNC, X

So if they're the same, why not just merge the platforms?

That may very well happen someday, who knows. But I do want to take issue with a point Paul made about the webby-ness of iOS/Android apps, because I think it is only true in theory, much like (not not as severe as) Web apps being offline capable.

Assertion: Web apps encourage linkability and searchability more than native apps

While it is true that you can deep link into iOS or Android apps, how many times have you followed a link from Flipboard directly into a story in the HuffingtonPost app? Web apps by their nature, and by years of convention, make their location and state known. By contrast, if native apps have URL schemes to trigger deep links, they are not omnipresent in an Address bar, but typically custom and hidden and not easy to find. Web apps are composeable by links because of their relative transparency, and it is more difficult to achieve in a native app ecosystem. Such conventions may evolve later, but it requires vigilence by developers for the gradient is not towards such transparency.

This concerns me, because if every website becomes a custom app, the web-of-links will be broken, and even Page Rank will become less relevant. Granted, this is not an argument against merging, but it is in argument to preserving the current model of publishing information via a standardized document format as opposed to proprietary per-website native applications.

So why then, do we need Chrome OS?

Because 90% of what people seem to do this days, outside of games, can be done on the Web. If a user is spending almost all of their time running Web apps and NOT running native apps, why not construct a device that is stripped down and simplified to streamline exactly what he needs?

I hear you say, "but why not include Android as well?" But this gets back to "more features == better". Remember, the postulated user is one who spends most of his time browsing Sure, it sounds good to have all of these extra features and access to the wealth of Android Apps, but non-iPod MP3 players also sounded like a better value proposition compared to the iPod originally.

In particular, for old fuddie-duddie Enterprise users, a locked down device, centrally managed, with cloud backup, and no expensive IT department needed, sounds very viable.

The idea of producing a netbook, which boots up with Android OS and contains a *full, not chopped down* version of the latest Chrome, also sounds like a viable SKU for content-creation activities. It may very well be the winning formula as Paul indicates!

But Google's trying Chrome OS first and experiments are good. I don't think power users who want to run Crysis on high-powered windows notebooks, can dismiss it, nor can it be dismissed just because it doesn't include every feature and the kitchen sink.

Sometimes I just need a fast, convenient browser.

p.s. I'm also not sure, a future in which every website is a native app (all newspapers, all blogs, etc) that I will be able to find information as easily, or to extract, mashup, and link information as easily. The Web has its problems, but let's not throw it out because of smooth animations and sexy devices.

p.p.s. The separate evolution of Chrome as an OS in which you can do everything and to which apps can be targeted will be good for a merged Chrome OS/Android OS too, because it ensures the Chrome team will have to make Chrome as great as possible before that merge happens. If the merge happened too early (say, Chrome 1.0), then Dalvik would have been a crutch, and they probably wouldn't have improved it as much as they have. Right now, the idea of Web as an app platform is a forcing function for improvement.

2011-05-13T11:20:00.000-07:00

The problems with HTML5 <Audio>

I've been having a Twitter back and forth discussion with Giorgio Sardo, Microsoft's HTML5/IE evangelist on Audio, but I find 140 characters too limiting to explain the issues, and Giorgio seems more interested in snark and attacking Chrome, than attacking the root of the problem.

Background

This all started because after the release of Angry Birds at Google I/O, people noticed that it was requesting Flash. Angry Birds is written in GWT and uses a GWT library written by Fred Sauer called GWT-voices. This library not only supports HTML5 audio, but has fallbacks to flash and even <bgsound> on IE6!

There was speculation the Flash requirement was done for nefarious purposes (to block iOS) or because Chrome includes Flash, but the reality is, it was done *both* because Chrome has some bugs, and HTML5 <audio> just isn't good for games or professional music applications.

I first noticed the shortcomings of the audio tag last year when we ported Quake2 to HTML5 (GwtQuake) shown at last years I/O, where I also demoed a Commodore 64 SID music emulator. There are two issues with using HTML5 Audio, which was originally designed to support applications like streaming music players.

It is missing functionality

The HTML5 audio element permits operations like seeking, looping, and volume control, which are great for jukebox applications, but you cannot synthesize sound on the fly, retrieve sound samples, process sound samples, apply environmental effects, or even do basic stereo panning. Quake2 required 3D sound based OpenAL's inverse distance damping method as well as stereo panning, I did my best, and implemented distance damping with the volume control, but had no ability to position sounds left or right.

For sound synthesis, there is no official way to play back dynamically created buffers. The workaround is to use Javascript to encode sample buffers into PCM or OGG in realtime, convert them to data URLs and use those as the source for an audio element, which is very computationally expensive and chews up browser memory. For developers wishing to create even basic music visualizers, it creates huge difficulties.

Problem #2: Latency

Audio applications require low latency. Studies have shown human beings can perceive audio latency down to the millisecond, but in general, lower than 7ms is considered good enough. This means in some circumstances, you need to schedule sounds within 7ms of one another, for example, if you need to simultaneously start two sounds, one on the left ear, and one on the right ear, or if you need to concatenate several sounds together in series.

Giorgio has a neat demo here of playing piano notes in sequence, and hats off to Microsoft for providing a great <audio> implementation. It's a cool demo, but I still hear latency variation in playback between notes and occasional glitches. No one's going to build something even 1/10th as good as Garage Band on iPad using this technique. That's because the one way you can schedule audio in HTML5 is via the browser's event-loop using setInterval or setTimeout, and that's problematic for several reasons.

First, it's unreliable. Over the years, setInterval/Timeout has been clamped to different minimal resolutions, depending on the browser and operating system. On some systems, it was tied to vertical refresh and would clamp to 16ms, then vendors started clamping to 10ms, and now they clamp as low as 4ms. But 4ms isn't a guarantee, it's a request. Many things can stand in the way of that request, for example, by just mousing over the page, user interface events can trigger Javascript handlers, CSS rules which force a relayout, and excessive Javascript work can trigger garbage collection.

Secondly, aggressive setInterval periods can delay response to user input, making the browser feel sluggish. If the user tabs to another window, the browser must decide whether or not to clamp timeouts to a much higher value (say 1 second), to avoid needlessly burning CPU which could harm background playback. Unlike requestAnimationFrame which solves this problem for graphics, there's no "requestSoundEvent".

Music Apps and Games sometime require playback of short-buffers

Some of the sounds in Quake2, for example, the hyper-blaster are sample buffers as small as 300 bytes. At 44khz, this is a hard deadline of 8ms to schedule the playback of the next sound in the sequence. With all of the other stuff going on within a frame, processing physics, AI, rendering, it is highly unlikely to be consistent, and do we really want JS performing this scheduling task.

Especially on mobile

Remember, mobile devices are HTML5 devices as well, and are continually getting better at HTML5, but they are much more resource constrained, and Javascript is even slower. Here, native scheduling is even more beneficial, and intensive Javascript scheduling of playback would be difficult, and waste battery.

That's why the Web Audio APIis important, because it permits complex audio schedule tasks, application of environmental effects, convolutions, etc to be natively accelerated without involving the Javascript engine in many cases. This takes pressure off the CPU, off of memory and the garbage collector, and makes timing overall more consistent. Here's a neat demo recently shown at Google I/O

Microsoft deserves credit

They made massive improvements in support of HTML5 from IE8 and IE9 especially in <canvas> and <audio>, and they deserve the right to feel proud and evangelize them. We celebrate that. It's why Angry Birds works, to some people's shock on other browsers, and it's not by accident. We built in fallbacks in our core library for 2d canvas, and tested on non-WebGL capable browsers like IE9 which have excellent GPU accelerated 2d support.

Angry Birds was not an attempt to make non-Chrome browsers look bad, but to make HTML5 look good, because when developers start realizing that professionally developed and polished games and applications can be done in HTML5, we all win.

But now is not the time to rest on our laurels. HTML5 is not done. There are many things incomplete and broken in the spec. I am sad to see Microsoft trying to talk down the experimentation that is going on in Firefox and Chrome, vis-a-vis WebGL and new Audio APIs, just because they are on a slower release cycle and do not have these bleeding edge features.

Giorgio seems to be suggesting in his tweets that the basic HTML5 <audio> tag is "good enough" and that the current IE9 implementation covers use cases sufficiently, and I disagree with that strongly.

We need 3d on the web. We need high quality, low latency, audio. We need to be able to do the things that OpenAL and DirectX can do with sound on the Web. And we're not going to get there by sticking our head in the sand and declaring premature victory.

2007-01-11T03:25:00.000-08:00

Top In-Denial Comments Overheard about the iPhone

1. What's the big deal?! It's just a touchscreen phone, like numerous PowerPC phones!
2. My Nokia already has WiFi and an Opera browser, where's the innovation.
3. Way too expensive
4. Non-replaceable batteries kill any chance of success
5. But my phone already has a camera, photo management, and email
6. Either you have a great music player or great phone, a combination device can't possibly be good at both.
7. Battery life is too short!
8. No UMTS/3G! No EVDO.
9. Multitouch is nothing more than a gimmick
10. You can't install any third party apps
11. It doesn't support Exchange!
12. Won't view MS Office attachments!
13. Cingular! Wahh!

Those are just a few. Yes, another year, another MacWorld, another flurry of contrarian naysayers trying to bash holes in the reality distortion field. Yes, some of the comments have some merit, but many of them are plainly based on unproven assumptions for which no real facts exist.

I used to be a big Apple basher. Macs are for non-technical clueless people. Apple sells inferior overpriced hardware. I mean, are iPod users brainwashed zombies? You go to COMDEX or CES, and you'll see a bazillion Chinese no-name MP3 players offer similar technical specs to the iPod for far cheaper and smaller. What's so special about the iPod that justifies its price? It's obviously going to be a failure and offers no innovation. That was before they sold 100 million of them. I couldn't understand it either, until I started using one. When the iPod arrived on the scene, it simply offered a better UI and desktop integration experience compared to the myriad of PC market players (go back to the year it was introduced and try to find something as easy to use as iPod + iTunes) Later, a huge add-on market emerged around it, that increased the value of having one. I wouldn't deny that there is an "incrowd" fashion/sexiness aspect to them, but it can't explain away the iPod's success.

Is the iPhone different? Yes, because the iPhone actually has alot more innovative hardware features that no one else has at the moment, which I'll get into later.

Let's talk about UI. People who often compare Macs to PCs exclaim that the Mac WIMP interface is easier to use and more consistent than Windows, which it may be, but it's hard to prove, and subject to aesthetics. On mobile devices however, UI and ergonomics are the number one most important issue, given the really poor screen size, pointing, and data entry capabilities.

A good way to visualize your interaction with a mobile device is to visualize the interaction of a disabled person with a real PC using accessibility tools, like huge fonts, a screen reader, magnifying glass window, or perhaps a menu based input system for the paralyzed. The speed at which you can navigate menus using a 1-9 keyboard and softkeys is not much better than the speed at which Stephen Hawking can navigate word lists, in fact, Stephen would probably kick your ass.

And that's exactly how I feel using the vast majority of smartphones today -- handicapped. The applications are typically poorly designed for numeric keyboards or joysticks, the information display makes you feel like you have tunnel vision, and to top it all off, many of the devices have serious UI latency issues. You know, you go to your address book, photos, or calendar and about 500ms to a full second pass before you see the result. One of my favorite things to do when I pick up a new phone is to rapidly jump around the menus just to see how bad the UI latency is.

I don't have any inside information, but from the keynote, let's try to see how the iPhone attempts to address many of these issues:

1. UI latency - From the keynote video, the iPhone appeared not only capable of keeping up with UI events, but it appeared to render UI transitions at atleast 30hertz. It looked super smooth and didn't appear to have many issues. Jobs is a stickler for perfection, and I doubt he would tolerate a laggy device.

2. Tunnel Vision (Small Screen) - Some data is best viewed in portrait format, some in landscape. The iPhone first and foremost appears to offer the user a choice. It also appears to have designed many of common apps like contacts, to be optimized for the most common display attributes and operations. The high resolution screen helps with smaller fonts to pack more information on the screen and remain readable. The fast rendering speed allows rapid switching between different screens and zoomable user interface techniques. Zooming only works if it can be done in real time. Fast screen switching provides a sort of "virtual desktop" which expands how much information can be displayed. If you can't keep up however, you'll start lagging behind user inputs. Using zoom/scroll when it takes you a second or more to get where you want is frustrating.

3. Input - different applications call for different inputs. I think we can all agree that a keyboard is best for text entry, or that a mouse rocks at First Person Shooters, or that a pen-tablet is better for architectural drawing/painting, but on small devices, a mapping application works best if you've got absolute pointing capability. (Try Mobile Google Maps on any non-touchscreen phone to see what I mean) I think the touchscreen is a nice compromise, since you get a recofigurable input, but of course, you lose tactile feedback. Maybe the next-gen iPhone will have some kind of Haptic feedback, or the ability to raise parts of the touchscreen at will :) (maybe using smart materials) Apple appears to have done something smart. The multitouch sensor opens the doors to much better accuracy (yes, if they are using FTIR it provides multitouch as well as better accuracy) as well as being able to discard accidental touchs of other fingers easier.

Moreover, Apple appears to be using contextual clues to enhance touch recognition. So for example, if you typing the word "PHONE" and when you're about to type the 'N' you press the the J and the N simultaneously, it uses statistical models to predict the more likely intended key. This differs considerably from the way stylus input keyboards on PPC and other smartphones work.

4. Context - many phones don't have all their little applets integrated very well, so when inside of these applets, you can't see whats happening elsewhere. What I liked about the iPhone was how when you were on a call, the caller-ID information was omnipresent and one click away. Some phones do better than others. Can we trust Apple to be consistent here?

5. WiFi and Browsing - Kick ass. I've used Opera Mobile and PocketIE on smart phones. Scrolling around and zooming is painful (as well as laggy and slow). The iPhone "double click to zoom" feature was extremely nice, and it's amazing no one thought it this before! The browser's live DOM/CSS information has an already calculated tree of bounding boxes for each screen element. All they have to do is start on the DOM node the user touched, and walk up the tree to find the biggest box that fits. Analog scrolling and zooming with the touchscreen IMHO is far better than pressing digital scroll-up-down buttons on most phones in the same way that a mouse is better than joystick. If I know I want to jump really far, I flick my finger faster or further, rather than trying to work those horizontal/vertical digital scroll buttons.

6. Seemless WiFi<->EDGE roaming. Um, yeah, if they can make this work seemlessly, it will be incredible. I've tried PocketPC Phones and Nokia phones with WiFi, for which they are supposed to offer automatic failover, but which never worked properly.

7. PIM (Address Book, Calendar, etc) - One of the problems with PocketPC and Palm phones that I've used is that they still assume people want their PDAs to be miniaturized versions of desktop apps. Microsoft is the biggest offender. Their contacts on PPC is atrocious, and impossible to dial from with one hand. There wasn't any integration between the Phone dialer and Contacts, so if you entered a number on the dialer, there was no 1-click "add as new contact" option. Maybe that's changed in recent revisions. Apple appears not to have followed this route. The iPhone address book is not simply a hacked port of OS X Address Book, but apparently totally new app optimized for touch navigation.

8. Photos. Nuff Said. Who's kidding who, you think any of the smartphones in the iPhone class will have better UI for doing this?

Future Directions

The multitouch screen's true potential seems barely tapped on the iPhone when you consider it's pedigree . I think Apple should also look at Zoomable User Interfaces. In any case, this feature is most definately not a gimmick, and one that sets the iPhone apart from any other device on the market.

The accelerometer potential can be further exploited as well. See Smackbook for example. Games could take advantage of the yaw axis detection, such as steering vehicles, for example.

The WiFi inclusion seems to offer the potential for iChat and VOIP, as well as seemless switching between SMS and Jabber/Bonjour. Since in some countries, both the receive and sender pay, this would cut costs for many.

Summing up my opinion:

1. It really is innovative hardware, period. The best smartphones on the market don't have everything this device has.
2. The user interface seems more reactive, faster, and easier to use
3. The browser especially seems nice
4. Jobs is right, interplay of hardware and software design is important. Many uber phones make the mistake of designing a good hardware platform and filling it up with crappy non-integrated applications and saddling it with bad ergonomics.
5. It's only too expensive if you don't want a video iPod. it's not really that much more expensive than other highend smartphones.
6. Talk time is comparable to other smartphones
7. fixed battery - legitimate issue for some, but probably impractical given the design of their case/screen
8. Don't support Exchange? Talk to your system administrator about supporting internet standards like everyone else: IMAP, SMTP
9. Cingular. Yeah, sucks for people who are not Cingular customers. Apple is clearly trying to grab the largest market, and that means GSM. In the US, the largest GSM carrier is Cingular.

What is it missing?
1. AGPS would have been AWESOME incombination with Google Maps
2. Non-adjustable camera/non-forward facing means no video conferencing
3. No 3G UMTS/EVDO (IMHO, not a big issue given WiFi. I imagine I'll be browsing mostof the time at the airport or at a cafe which has a WiFi hotspot. 3G data services are often congested and expensive anyway) Would be nice to have tho.

As for the reports of it not displaying PDF or Word attachments, and Apple not allowing any third party app development, none of this has been officially confirmed by Apple at the top level, and I suspect that Apple is still evaluating how they're going to do it, but I don't doubt that they will eventually allow it. If not Cocoa apps, then Java J2ME and JavaScript widgets.

2006-10-19T01:42:00.002-07:00

18 Mistakes That Kill Startups...

I always get a chuckle out of Paul Graham's essays, the latest one 18 Mistakes That Kill Startups being no exception. As with most business essays, it is full of obvious truisms, cliches, and of course, the mythical great hacker hero. One of the problems of autobiographical business writers who write from their own experience is selection bias, the inability of people to be objective about their own success and see it within the big picture.

One's own success, of course, is always due to one's great ideas, work, foresight, and lack of mistakes, and never due to serendipitous events, suddenly favorable market conditions, or just plain old personal connections. Why was Viaweb a "success"? Surely, it's because it was written in Lisp! and not because the internet boom was in a full swing sellers market, larger companies were practically buying anything with a half dozen users and a web site. As a programmer, I'd love to believe that the biggest influence on the success or failure of a business idea is programming ability, it strokes the narcissist ego of anyone who considers themselves a good programmer. I mean, for every socially isolated geek growing up in school, what could be better than finding out that the universe is optimized for nerds to succeed.

This is not to say that one's success can't be because of merit, just that one can't determine which factors lead to success by only measuring one's own successes in isolation. Would you take a new medicine because the last couple of times it worked for someone else to cure their disease? Business advice essays are the financial equivalent of diet pill and herbal remedy testimonials.

Many people who invest in the stock market love to believe that their successful stock picks are because of a special insight, or technique that they use for their picks. The reality is, most people are unable to beat a random dart board or index fund, but in isolation and over small time windows, their successful choices look to be correlated with their behavior -- until -- they lose spectacularly on some trade. And so it goes, in sports, in politics, in competitions, many winning competitors attribute their success to lucky charms, daily superstituous rituals, herbal supplements, religious prayers. Does athletic training and genetics play a part? Certainly the answer is yes, but at high levels of competition, an athlete can also win by another competitor falling on bad luck -- a gust of wind, a slippery track, a misplaced foot, an equipment malfunction, a bad starting position draw. That's why writing a book on "18 mistakes that stop you from winning a Gold Medal at the Olympics" is practically worthless.

There may be a list of "do's and don'ts" that are neccessary (but not sufficient) for successful startups, but I believe that most of them are probably conditional on situation, and probably not discoverable in practice, there are just too many variables. Instead, I would view the market as a memetic ecosystem, and startups as organisms competiting within the environment. Which organism is the fittest? The only way to know is to release it into the environment and see. The system is too complex for a simple set of rules of thumb to determine optimal fitness. Sometimes organisms which appear poorly designed or weak, end up surviving because off an odd confluence of external factors.

I'm often stumped by stories of accidental success, of people who created something on a whim, and overnight had it spread like wildfire, while at the same time, people who had created almost exactly the same ideas in the past failed miserably. We'd like to attribute their success to design or intent or "something they did right" and the failures to "something they did wrong" Did they use the wrong programming language? Did they raise too little money? Too much. Hire the wrong people? All the while, ignoring the fact that sometimes the result is due to the nebulous, continually shifting aspects of human desire.

In the end, probably the most important worthwhile advice that most business writers give regardless of what you believe determines success is this: you're more likely to succeed if you try to do something, than if you do nothing. You won't know if your organism will survive in the memetic environment if you don't release it.

Graham's 18 point list is full of truisms and hedged statements.

Rule #3. Don't choose niche ideas because other people are already doing the other great ideas
Rule #4. Don't choose ideas other people are already doing

Rule #8. Don't launch your site too late.
Rule #9. Don't launch your site too early.

Rule #11. Don't raise too little money.
Rule #12. Don't spend too much money.
Rule #13. Don't raise too much money.

Which I reduce to the following:
1. A successful startup does exactly what is required for success, and not too little or too much.

And of course, the implicit rules, like Don't Solve Other People's Problems (unless of course, you're ViaWeb) Spending time doing business development is bad (especially by hiring a business guy) unless of course it's done by a hacker who takes time out of hacking to make calls to other executives, who of course, love getting calls from hackers. Oh, and don't hire Bad Programmers, except that no one can tell what makes a Good Programmer, except for Good Programmers(*). Apparently, it's impossible for any Good Programmer to want to work with a Business Guy(tm) also. That's why so many startups failed during the dot-com boom, because of bad programmers, not writing in LISP on Unix machines, and the inability of Business Guy to inspire Good Programmer Guy to join him.

Oh, and if you want to know which programming language to use on your next startup project, go find out what Phd students are using on research projects at elite colleges. (of course, an elite college by definition won't be using Java for such projects.)

-Ray

(*) This reminds me of the way immortals in the HighLander series "sense" other immortals. Hmm, maybe a YouTube spoof is in order? Hacker gods walk among us undetectable to all but themselves! (cue weird "six sense" soundfx as Paul Graham enters a room where Eric S Raymond is sitting)

2006-09-30T14:10:00.000-07:00

Geeking out: Quad Core Tower of Power Yumminess

I've needed to upgrade my P4 3Ghz Dell Dimension desktop for awhile -- it's been 2+ years since I got a new computer. Once Apple went x86, I always knew my next computer would be a Mac. I've been using Unix for the last 16 years as a development environment, but I never really liked any of the Unix desktops (except NeXT), so I always kept a PC around as my main terminal and connected remotely to Unix boxes. Not so much for applications per se, but mostly for games, multimedia, and Java performance (remember the bad ole days of no Hotspot for Linux and old JDKs?)

Mac OS X gives me the environment I'm most comfortable in: Unix and the Unix command line, as well as a fabulous desktop. My only dilemma was: MacBook Pro or Mac Pro? Last year, I traveled alot for work, so it would be a no brainer, but given that I rarely travel now, and I'm replacing a PC Desktop that also acts as a gaming rig, the Mac Pro became alot more desirable.

The only worry was I haven't seen the Merom based notebooks and Clovertown based Mac Pros on the horizon, with supposedly a new case design for the Mac Pro by an internationally famous designer. Should I wait till January or longer? The next-gen NVidia and ATI DirectX10 video cards would be out by then as well. The problem with waiting is that there is *always* something new and great in the pipeline 6 months later. If you wait for the next big thing, you'll always be paralyzed.

I decided that the Mac Pro was so much better than my current setup, it doesn't matter what's coming 6 months from now. The Mac Pro case, before redesign, is already very very nice, especially the RAM and SATA connections. But once I saw how Anandtech was able to just plug Clovertown engineering samples into a Mac Pro and turn it into a Octo-Core monster, it clinched it -- this baby's CPU is upgradable too. In any case, I need to do lots of video editing, and 4 easily accessible SATA drive bays + 4 cores is good for the task.

So last Friday, I pulled the trigger. Mac Pro, 2.667 Ghz, minimum sized HD, ATI X1900XT, 2Gb FB-DIMM RAM, Bluetooth = $3003. I did not get the 3Ghz version because I think a 12% gain in serial performance is not worth $800. I expect that when Clovertown is released, Xeon 5160 prices will drop radically, and I'll upgrade later if I need to, and it will be far cheaper. Moreover, Apple charges $400 for 500Gb HDs when I can buy them online for $170. I'll use the 160Gb that comes with it as my Windows XP Bootcamp drive for gaming. I'll also have 4 empty FB-DIMM slots to upgrade RAM later if I need more, when the price is cheaper.

Now goddamn it, hurry up and deliver my machine Apple!

P.S. Parallels announced that they will support DirectX acceleration near the end of the year, which would effectively eliminate the need for Boot Camp for gaming in most cases. Yay!

As for my old Dell PC, I've got another 1TB RAID sitting in the house and I've been itching to run ZFS, so I'm gonna try running OpenSolaris on it. The Linux and Apple guys need to get their butts into gear and get ZFS ported ASAP!

2006-09-27T15:19:00.000-07:00

Balanced Incomplete Block Designs, Difference Sets, Klein's Quartic Curve, Projective Planes, and lots more!

I've been busy lately and unable to provide the answer for the Extreme Programming Code Review problem posted last time. I chose this problem, because when I was taking a graduate combinatorics class in college, the underlying problem had an almost mystic relation to a large number of other areas of combinatorics and geometry, as well as producing a simple, but beautiful and symmetric structure.

Mathematical history has many examples of similar, but harder arrangement problems. Catherine The Great supposedly kicked things off by posing to Euler, The 36 Officers Problem. Later, Kirkman proposed the 15 schoolgirl problem (my oh my, a Reverend and thoughts of schoolgirls eh?). These seemingly simple problems acted as a catalyst and resulted in great advances in the field of combinatorics, which has enormous applications in many fields. One application of course, is solving the problem I posed.

The problem says, given 7 people, arrange them into 7 teams of 3 each, such that no two people are ever on the same team twice. It is probably possible to construct this design using trial and error, but there are many other ways to do it.

Let us number the programmers 0 through 6, and start off with the team {0,1,3}. If we were to add 1 to each number, it is easy to see that the new team will consist of 3 new members, no two of which are in the first team. {1,2,4} And likewise, the same will be true for each new team, for all teams {x+0, x+1, x+3} up to x=0 to 6. The first two positions will always differ by 1, the second and third by 2, and the first and third by 3. If you read down the three columns, we're just rewritten the numbers 0 through 6 shifted by 1 or 2 places. Here's our list of teams, you can also verify them by visual inspection.

{0,1,3}
{1,2,4}
{2,3,5}
{3,4,6}
{4,5,0}
{5,6,1}
{6,7,2}

It turns out that this solution is also unique except for permuting order.

Combinatorics describes this as a t-(v,k,l) design. A t-(v,k,l) design is a set P of v points, a set of subsets of P called blocks (also called lines) B containing k points, and an incidence structure I in P * B which describes the relation of P and B (which elements of P are in which blocks). For any t points, exactly l blocks are incident.

Our problem says that there are p=7 points, and it says that for any t=2 points, they are contained in only l=1 block (team), and the blocks consist of k=3 points. Therefore, our problem is to construct a 2-(7,3,1) design. Such 2-designs are called Steiner Triple Systems and denoted STS(7). One result of combinatorics is that STS(v) exists if and only if v = 1 or 3 (mod 6).

So what's so special about this problem to get so worked up about? It turns out there are many connections with STS(7) and other areas of mathematics, in addition to which I mentioned in the header, there are also connections to coding theory, latin squares, octonions, simple groups, and geometry.

And now I will show you how this problem is connected to the Balsa Wood problem, as well as to very beautiful geometry.

Recall that there are 7 teams of 3-programmers, 7 programmers, no two programmers are on the same team twice. Remember back to the defination of a 2-(7,3,1) design, the programmers are called "points" and the teams are called "lines". If no two programmers are on the same team twice, that means 2 programmers (or points) uniquely determine a line, and also, that at most, two teams can only have 1 programmer in common, which says that any two lines intersect at one and only 1 point. Hmm...

7 points
7 lines
2 points determine a line
2 lines determine a point

What would happen if we wrote down those 7 programmers and connected the dots according to teams?

We form what's called a projective plane. This plane, the projective plane of order 2 called the Fano Plane has the interesting property that there are no parallel lines. It also has a 168-fold symmetry. (another interesting property, since each line has 3 points as well as each point is incident with 3 lines, you can interchange points and lines to no effect! The Fano Plane is its own dual.)

How can we use this to solve the Balsa Wood problem? I will give a partial solution, by showing the solution for 3 successive writes.

if you are writing X and the ram is already in state X, do nothing
if the ram is empty, and you're writing I, then place a 1 in bit position I
if the ram contains 1 bit in position I and you are writing the number J, find a line (I,J,K) and place a 1 in bit position K
if the ram contains 2 bits in positions I, K, and you are writing value X, write 2 more bits such that 3 of the bits will be colinear on a line, and X will be a point NOT on that line. That is, if X != I or != K, then find the line (I,J,K) and place a 1 bit in position J, as well as in position X. If X == I then write two bits on the other line containing K, and if X == K, then write two bits on the other line containing I.

Step 2 and 3 work because of the inherent property of projective planes. Step 2 works because 2 points uniquely determine a line. Step 3 works, because no matter what, there are three lines intersecting any point colinear with X, therefore, you can always place 2 1-bits on one of those lines.

The rules for reading are as follows:

if the memory is blank, nothing has been written yet
if exactly one bit is written in position I, then the value in the memory is I
if exactly two bits are written in position I and K, then the value in the memory is J, where J is on the line containing I and K
if exactly 4 bits are written in positions X, I, J, K, find the 3 positions which form a colinear line, the one which is "left out" by itself is the value in the memory.

I leave the construction of the final rule for writing and reading, as well as an argument as to its correctness to the reader. There is an alternate solution to this problem by using womcode techniques, which have applications to both error correcting codes and cryptography. Sadly, Rivest and Shamir seemed to have patented it, and the solution to the Balsa Wood problem actually violates the patent.

Another related problem to look up is the Transylvanian Lottery Problem, also solved with the Fano Plane.

-Ray

2006-09-20T16:20:00.000-07:00

The Extreme Programming Code Review Problem

You manage a team of 7 programmers and have become a recent convert to extreme programming. You have decided to use a style of pair-programing that you call the weekly triplet review.

Each day of the week, 3 programmers will be picked from the 7 available to conduct code reviews together such that no two programmers will ever be on the same team more than once in one week. (Note, these programmers work on weekends too, so you need 7 teams of 3.)

If the programmers are numbered 1 through 7, can you enumerate all the possible teams?

-Ray

P.S. It is no coincidence that this problem features 7 objects like the previous problem. Believe it or not, this is a hint: if you solve this problem, you may have some inspiration for how to solve the Balsa Wood RAM problem.

2006-09-19T17:21:00.000-07:00

Puzzles you can't solve with Google

One of the techniques that people commonly use in interviewing software engineers is to use puzzle questions to ascertain the problem solving process of candidates. However, the problems themselves are generally drawn from commonly asked puzzle questions, some of them even famous puzzle problems, which lets candidates solve them either by search engine, or by memorization.

So what's a good source of problems to ask which are not generally available on the internet? Well, many college mathematics or computer science textbooks contain obscure and hard example problems which are not generally covered in internet discussions.

One of them, that I encountered over 12 years ago, still burns in my memory today because of connections with quite beautiful mathematical structures. I will reproduce the problem below, obfuscated from the original way it was stated, in order to avoid book searches. I have only seen this problem discussed twice by others in 20 years of internet usage. It has analogous solutions in some ACM/IEEE/CiteSeer references, but in general is not discussed in IT or Puzzle literature.

I will post the solution later in another message.

The Balsa Wood RAM Machine

You are given a computer attached to a unique memory device consisting of a number of sticks of Balsa Wood, 7 to be exact. The computer can read from this memory by checking to see whether a given stick of wood in position X is either broken or unbroken, representing a 1 or a 0 respectively. The computer can also write to this memory, but it can only write *1* bits, it cannot write a 0, that is, it can break sticks, but it cannot repair a broken stick.

The computer operates on decimal number in the range 0-6, and the question arises, how many times can the computer write a number to the RAM and read it back? What would the read and write procedures look like?

As an example, you can imagine that if the RAM is empty, if you want to write a decimal value X, you place a 1 in the Xth RAM position (break stick X). You read this value back by observing which position contains a broken stick.

The RAM however has 6 more unbroken sticks, can't we use this to support multiple writes? Yes, a second write could be supported for value Y by breaking all sticks except Y, in which the read procedure would be to observe which stick is left unbroken.

Those are the trivial procedures. What about 3 writes or 4? It turns out that 4 writes are possible. So, the question is:

Specify an algorithm for writing 4 values into the RAM and being able to read them back at each step, without foreknowledge of what was written before.

That is, your task is to produce two procedures: WRITE(BitSet current, Integer valueFromZeroToSix) -> returning BitSet and READ(BitSet current) -> returning Integer, in which the following is true:

1) WRITE returns a new BitSet produced by taking the old BitSet and changing only 0 to 1s. It also replaces the current bitset with the return value.
2) READ(WRITE(current, X)) == X
3) Any sequence of WRITE and READ operations may occur as long as the number of WRITE operations is less than 5.

I will post the solution some time in the future.

-Ray

2006-09-15T17:32:00.000-07:00

Awe inspiring complexity and logical depth.

That's what I got watching "The inner life of a cell" a 3D visualization of some of the molecular mechanics of cell biology.

Watching this video was tantamount to a religious experience for me in the level of awe and wonder at the truly staggering and overwhelming complexity of what goes inside the cell at the level of molecular biology. I've read about the MAP/Microtubule transport before and seen diagrams of how the foot-over-foot moveement was supposed to work, but to watch it artistically portrayed recalled memories of "2001" A Space Odyssey -- beauty and science in a single package. It is surreal, almost like a Dali creation, watching those tiny feet attached to a thin strand carry a large amorphous bag of material hundreds or thousands of times larger in volume up a bean stalk.

None of the 3D visualizations of molecular biology I've seen before could convey this sense. There are videos floating around of macrophages in action, or HIV penetrating a cell, but they lack the artistry of this video. The closest I've seen have been the microphotography series of the development of the human fetus in the womb.

The video of course takes some artistic liberties, speeding up or slowing down time, making the cell look mostly empty inside instead of packed to the brim with molecules, but I can accept that these are done so that you may focus on a single mechanism at a time.

In the field of computer science, we are used to coding procedures to construct the proper output data according to guaranteed determinism and error-free execution, so to watch code execute which produces self assembling structures in the presense of error and stochastic processes is simply amazing. The amount of information and logical depth encoded in 4 billion years worth of evolution is a wonder to behold, even for an atheist.

I await the full 8 minute video. Hats off to XVIVO, HHMI and Harvard Biovision.

2006-07-06T11:38:00.000-07:00

Infinite Streams in Groovy

In my last post, I showed how you can use byte-code manipulation and Generics to achieve a modicum of functional programming in Java without overly cumbersome syntax. However, it still feels a little clunky.

But how about in Groovy? Groovy's support for real closure syntax turns out to make functional programming, er, Groovy! I won't bother writing up the basics, since they have already been done elsewhere, such as Functional Programming in Groovy

What I will do is show how to build a classic data structure used in functional programming, streams, using Groovy. And then I'll show a classic application of functional streams: a stream of the Sieve of Eratosthenes, in one line of code.

Streams

A stream is a collection, like a list, only that it doesn't necessarily produce its contents until needed, and it may in fact, be infinitely large. It bears some resemblance to streams used in I/O, such as InputStream in Java. For example, one could create a stream of integers, by implementing a class IntegerInputStream whose read() method returns the integers in montonically increasing order.

But our streams won't subclass InputStream, ours will be a sort of linked-list.

LazyLists

First, we'll create a new data structure, LazyList which represents a pair of values: a concrete value 'car', and a closure 'cdr' which returns another LazyList.


class LazyList
{
  private def car;
  private Closure cdr;
  LazyList(def car, Closure cdr) { this.car=car; this.cdr=cdr; }
  public def getCar() { return car; }
  public LazyList getCdr() { if(cdr != null){  return cdr(); } else { cdr;  } }
}

Notice that the getCdr() function doesn't return the cdr field, it returns the result of executing the closure.

Next we'll need a way of constructing a new LazyList, so we add the following method to class LazyList


public static cons(def val, Closure c) { return new LazyList(val, c); }

This factory method just uses the LazyList constructor (for now). And finally, we need a method for grabbing some values out of the list.


public List take(int n) 
{ 
   def r = []; def l = this;
   n.times { r.add(l.car); l = l.cdr(); }
   return r;
}

We're not done yet, but we're already capable of defining our first infinite stream.


def integers(n) { cons(n, { integers(n+1) }) }
def naturalnumbers = integers(1)

naturalnumbers.take(10).each { print "$it\n"; }

The first line says that the integers starting from N, is the result of constructing a list consisting of the element N and the integers starting from N+1. Note that the recursive call to integers(n+1) is inside a closure. Groovy is an eager language, and all function parameters are evaluated before calling the function. Without the closure, this would result in an infinite loop and overflow the stack.

The second line says that the natural numbers are the integers starting from 1.

The third line says to take the first 10 elements from the natural numbers, iterate over the result, printing them out.

Big deal! What about filters?

Yeah, you could do that easily with [1..10].each { print "$it\n" }. So let's move on. What if we want to filter an infinite LazyList? We can do that too, with the following method added to LazyList.


public LazyList filter(Closure pred)
  {
  if(getCar() != null)
      if(pred(getCar()))
          return cons(getCar(), { getCdr().filter(pred) })
      else
          return getCdr().filter(pred) 
   return l
}

Which says that to filter a LazyList with closure predicate 'pred', we call pred() on the first element of the list, and if true, we construct a new list using this element, and a closure which will invoke filter on the rest of the elements of the list. Otherwise, we recursively call filter until we find an element that satisfies the predicate.

Now we can define the even numbers...


def evennumbers = naturalnumbers.filter { it % 2 == 0 }

The Sieve of Eratosthenes

One of the classic examples used to demonstrate the power of streams is the Sieve of Eratosthenes, which is to define a stream whose successive list of values are the prime numbers.

This can in fact be done in a single line of code using LazyList:


def sieve(list) { cons(list.car, { sieve(list.cdr.filter { x-> x % list.car != 0 }) }) }

although that is kinda ugly, but formatted this way


def sieve(list) 
{ 
    cons(list.car, 
           { 
             sieve(list.cdr.filter { x-> x % list.car != 0 }) 
           })
}

is easier to read. If you read the Wikipedia link above, you'll see that the sieve takes a list, whose first element is prime, and returns a new list, with this first element, followed by a sieve of another list with all multiplies of the prime number filtered out.

Now we can print the first hundred prime numbers:


def primes = sieve(integers)
primes.take(100).each { print "$it\n" }

or the first 100 fibonacci numbers


def fibo(a,b) { cons(a, { fibo(b, a+b) }) }
fibo(0,1).take(100).each { print "$it\n" }

And with just two other magic functions


public LazyList compose(Closure c, LazyList l)
{
      return cons(c(getCar(), l.car), { getCdr().compose(c, l.cdr) })
}

public LazyList map(Closure c)
{
      return cons(c(getCar()), { getCdr().map(c); });
}

we can even print out the first 10 twin primes:


def twinprimes = primes.compose({x,y -> [y-x == 2, x]}, primes.cdr).filter({it[0] == true}).map({ it[1] });
twinprimes.take(10).each { print "($it, ${it+2})\n" }

Caveats

First, don't expect this code to run fast. It generates alot of garbage lazylists, uses recursion, and it also recalculates values. The first problem probably can't be fixed, the second problem can be fixed by rewriting the LazyList functions to be tail-recursive and then hacking Groovy to make sure it optimizes tail-recursion.

The final problem (recalcuation) can be fixed with memoization. Recall the cons() function which appears to do nothing but invoke the LazyList constructor? Let's introduce a new function:


public static delay(Closure c)
{
   boolean evaled=false;
   def val=null;
   return { 
           Object[] args -> 
               if(!evaled) { evaled=true; val=c(args); return val } 
               else return val;
          }
}

and modify cons


public static cons(def val, Closure c)
{
   return new LazyList(val, delay(c));
}

so that now the Closure passed to cons() is only executed once. Subsequent values are returned from the cached value. Of course, this only helps performance if the closure block is computationally expensive to evaluate. Otherwise, the overhead of creating the memoization closure probably incurs even worse penalties.

That's it for today's hack. Practical? Maybe not. Groovy? Yes. If you want to use these techniques and run them more efficiently on the JVM, you may want to look at some of the Scheme/Lisp dialects available for Java.

-Ray

2006-07-01T01:00:00.000-07:00

Fun with Generics and CGLib: Functional Programming in Java with less hassle

Come on, admit it. You've got functional envy. You've seen Quicksort in 3 lines or less of code. You've salivated over map/reduce and function curry looks as good as it tastes.

Up until now, you've had two choices. One, switch to a language which allows functional expressions with economical syntax, such as Scheme, Haskell, Ruby, or Groovy. Or, use laborious Anonymous Inner/Local classes to fake it like commons-collections.

We'll, I'm gonna show you how to do it without much syntactic overhead, and preserve enough type information to even allow your IDE to do some refactoring, and popup fields and methods on return values of "functions"

Preliminaries

Before we get started, you should review Alex Winston's Strongly Typed Java Delegates and my previous blog entry on Refactorable Type-Safe Configuration without XML or Annotations. If you don't know what functional programming is, or why it matters, read Why Functional Programming Matters.

Goal

Our goal is to try and make writing functions as easy as possible, and allow them to be curried, composed, and passed as arguments to other functions. Functions, as used in this article, are not just any old Java method. They are Java instance methods which are pure-functional, that is, without side-effects, and do not reference any object fields or non-static variables. Essentially, they are non-mutating static functions declared without a static qualifier.

This,


public MathFuncs
{
public int add(int x, int y) { return x+y; }
public int mul(int x, int y) { return x*y; }
}

is an example of functions. They are an instance methods and do not mutate state.

Example functional usage


Lambda mul = lambda(nop(MathFuncs.class).mul(0,0));
Lambda triple = mul.curry(3);
Lambda quadruple = mul.curry(4);
Lambda timesTwelve = compose(triple, quadruple);

System.out.println("10 timesTwelve = "+timesTwelve.call(10));

or how about


Lambda sum = reducel(add, 0);
// the numbers 1-10 times twelve, and then summed together
int x=sum.call(map(timesTwelve, list(1,2,3,4,5,6,7,8,9,10)));

Ok, my interest is peaked. What is that funky lambda and nop function?

All Java functions must first be converted to Lambda functions, which is a Java interface with the following signature:


public interface Lambda<T> {
public T call(Object... args);
public Lambda<T> curry(Object arg);
public Method method();
}

Extremely simple as you can see, you can either invoke a function, curry it, or get access to the underlying Java reflection Method, which is used internally. Ordinarily, to make Java functions into Lambda functions, you've have to write classes like this


public class Add implements Lambda<Integer>
{
public T call(Object... arg) { return MathFuncs.instance().add(arg[0], arg[1]); }
...
}

and indeed, you'd have to write a separate implementation for each and every interface you use.

Ahhh...Don't tell me. Delegates!
Yes, if you recall the Strongly Typed Delegates trick, this will be yet another variation. What we'll do is use the nop() function to create an CGLib interceptor for a given class, return an instance of this proxied class, and invoke a method on this instance. This will then tell the proxy which method we want to create a Lambda for.

Here's a snippet of how nop() works, the complete listing will follow later


public static <T> T nop(Class<T> clz)
{
   T x = (T) Enhancer.create(clz, new Class[]{Lambda.class},
             new LambdaInterceptor(clz));
   return x;
}

Now, you'll note that this function does not return a Lambda object! It returns an instance of the type of the class it was invoked on! nop(Foo.class) returns Foo! That's where lambda() comes in. It turns instances of Objects into Lambda interfaces! When you invoke a method like add() on Foo.class, the interceptor takes the return value of the add() function and associates itself with it. Then lambda converts these back into Lambda interfaces.


public static <T> Lambda<T> lambda(T pm) {
     Lambda<T> l = (Lambda<T>) interceptors.get(pm);
     interceptors.remove(pm);
     return l;
 }

How does it do it? Well, when you write nop(Foo.class), a CGLib proxy is created for an instance of class Foo, and placed into a global interceptors Map with object instance as key, and the Lambda interceptor as value. Next, when you call something like nop(Foo.class).add(1,2), the add() function gets intercepted, and a java.lang.Method reference is placed in this map as well. Finally, when you call lambda() on an instance that has be proxied by a LambdaInterceptor, it pulls the interceptor out of the map, and casts it into a Lambda.

Other Tricks
If you feel like typing extra generics parameters, you could have call() methods which are type-safe. For example, you could create a Lambda1 and Lambda2 interface which both extend Lambda, but which have non-varargs call() methods taking 1 and 2 parameters each.

Then you could write code like


  lambda2(nop(MathFuncs.class).add(1,2)).call("Foo", "Bar")

And your IDE would flag call("Foo", "Bar") as an error! I leave the generic type signatures of Lambda1 and Lambda2, and the definition of the lambda1 and lambda2 helper functions as an exercise for the reader.

As a final note, yet, there is a way to optimize away some of the unneccessary object creation, which will I do in a later release.

Have fun(ctional)!
-Ray

Here's the complete listing for Func.java, which includes the LambdaInterceptor
Func.java


package functional;

import net.sf.cglib.proxy.Enhancer;
import net.sf.cglib.proxy.MethodInterceptor;
import net.sf.cglib.proxy.MethodProxy;

import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.util.HashMap;

/**
 * Created by IntelliJ IDEA.
 * User: ray
 * Date: Jun 29, 2006
 * Time: 12:21:31 PM
 *
 */
public class Func {

    protected static HashMap<Object, LambdaInterceptor> interceptors = new HashMap<Object, LambdaInterceptor>();

    public static <T> Lambda<T> lambda(T pm) {
        Lambda<T> l = (Lambda<T>) interceptors.get(pm);
        interceptors.remove(pm);
        return l;
    }

    public static <T> T nop(Class<T> clz) {
        T x = (T) Enhancer.create(clz, new Class[]{Lambda.class}, new LambdaInterceptor(clz));
        return x;
    }


    public static <F,G> Lambda<F> compose(Lambda<F> f, Lambda<G> g) {
        return new CompositionLambda<F>(f, g);
    }

    protected static class LambdaInterceptor<T,S> implements MethodInterceptor, Lambda<S> {
        private T proxy;
        private Class<T> clazz;
        private Method binding = null;

        public LambdaInterceptor(Class<T> target) {
            try {
                this.proxy = target.newInstance();
            } catch (InstantiationException e) {
                e.printStackTrace();  //To change body of catch statement use File | Settings | File Templates.
            } catch (IllegalAccessException e) {
                e.printStackTrace();  //To change body of catch statement use File | Settings | File Templates.
            }
            this.clazz = target;
        }

        public Object intercept(final Object o, final Method m,
                                final Object[] args, MethodProxy mp) throws Throwable {


            if (m.getName().equals("toString")) {
                return "Invoked by Debugger variable display!";
            } else if (m.getName().equals("method")) {
                return method();
            } else if (m.getName().equals("call")) {
                return call(args);
            } else if (m.getName().equals("curry")) {
                return curry(args[0]);
            } else {
                Method[] meths = proxy.getClass().getMethods();
                for(Method mi : meths)
                  if(mi.equals(m)) { binding=mi; break; }
                
                if(binding==null) throw new NoSuchMethodException(m.toString());
                binding.setAccessible(true);
                Object ob = null;

                ob = binding.invoke(proxy, args);
                interceptors.put(ob, this);
                return ob;

            }
        }


        private static Class[] classes(Object[] objects) {
            Class[] classes = new Class[objects.length];
            for (int i = 0; i < objects.length; i++)
                classes[i] = objects[i].getClass();
            return classes;
        }

        public S call(Object... args) {
            try {
                return (S) binding.invoke(proxy, args);
            } catch (IllegalAccessException e) {
                e.printStackTrace();
                throw new RuntimeException(e);
            } catch (InvocationTargetException e) {
                e.printStackTrace();
                throw new RuntimeException(e);
            }
        }

        public Lambda<S> curry(Object arg) {
            return new CurriedLambda(this, arg);
        }

        public Method method() {
            return binding;
        }
    }

}

Util.java


package functional;

import static functional.Func.lambda;
import static functional.Func.nop;

import static java.util.Collections.EMPTY_LIST;
import java.util.*;

/**
 * Created by IntelliJ IDEA.
 * User: ray
 * Date: Jun 30, 2006
 * Time: 5:33:25 PM
 */
public class Util {
    public static <F, I> F reduce(Lambda<F> f, I init, List<I> list) {
        if (list == null || list.isEmpty()) return f.call(init, init);
        if (list.size() == 1) return f.call(init, list.get(0));
        return f.call(list.get(0), reduce(f, init, list.subList(1, list.size())));
    }

    public <F,I> F _reduce(Lambda<F> f, I init, List<I> list)
    {
        return reduce(f, init, list);
    }

    public static <F, I> Lambda<F> reducel(Lambda<F> f, I init) {
        return lambda(nop(Util.class)._reduce(f, init, (List<I>) EMPTY_LIST)).curry(f).curry(init);
    }


    public <T> List<T> _map(Lambda<T> lambda, List<?> list)
    {
        return map(lambda, list);
    }

    public static <T> Lambda<List<T>> mapl(Lambda<T> lambda)
    {
       return lambda(nop(Util.class)._map(lambda, (List<?>) EMPTY_LIST));
    }

    public static <T> List<T> map(Lambda<T> lambda, List<?> list)
    {

            List<T> nl = newList(list);
            for(Object o : list)
            {
               nl.add(lambda.call(o));
            }
        return nl;
    }

    private static <T> List<T> newList(List<?> list) {
        return list instanceof LinkedList ? new LinkedList<T>() : new ArrayList<T>();
    }

    public static List<Integer> list(int... ints)
    {
      ArrayList al=new ArrayList();
      for(int x : ints) al.add(x);
      return al;
    }


    public static <T> List<T> cons(T a, List<T> l)
    {
        List<T> nl = newList(l);
        nl.add(a);
        nl.addAll(l);
        return nl;
    }

    public <T> List<T> _cons(T a, List<T> l)
    {
        return cons(a, l);
    }

    public static <T> Lambda<List<T>> consl(T a)
    {
        return lambda( nop(Util.class)._cons(a, (List<T>)EMPTY_LIST));
    }
}

CurriedLambda.java


package functional;

import java.lang.reflect.Method;

/**
 * Created by IntelliJ IDEA.
 * User: ray
 * Date: Jun 30, 2006
 * Time: 5:31:43 PM
 */
public class CurriedLambda<T> implements Lambda<T> {
    private final Lambda<T> lambda;
    private final Object arg;

    public CurriedLambda(Lambda<T> lambda, Object arg) {

        this.lambda = lambda;
        this.arg = arg;
    }

    public T call(Object... args) {
        return lambda.call((Object[]) args(arg, args));
    }

    public Lambda<T> curry(Object arg) {
        return new CurriedLambda(this, arg);
    }

    public Method method() {
        return lambda.method();
    }

    private Object args(Object arg, Object[] args) {
        Object[] nargs = new Object[args.length + 1];
        nargs[0] = arg;
        System.arraycopy(args, 0, nargs, 1, args.length);
        return nargs;
    }
}

CompositionLambda.java


package functional;

import java.lang.reflect.Method;

/**
 * Created by IntelliJ IDEA.
 * User: ray
 * Date: Jun 30, 2006
 * Time: 5:31:35 PM
 */
public class CompositionLambda<T> implements Lambda<T> {
    private final Lambda<T> f;
    private final Lambda g;

    public CompositionLambda(Lambda<T> f, Lambda g) {

        this.f = f;
        this.g = g;
    }

    public T call(Object... args) {
        return f.call(g.call((Object[]) args));
    }

    public Lambda<T> curry(Object arg) {
        return new CurriedLambda<T>(this, arg);
    }

    public Method method() {
        return f.method();
    }
}

FuncTest.java test code


package functional;


import static functional.Func.compose;
import static functional.Func.nop;
import static functional.Func.lambda;
import static functional.Util.list;

import java.util.Collection;

/**
 * Created by IntelliJ IDEA.
 * User: ray
 * Date: Jun 30, 2006
 * Time: 1:16:23 PM
 */
class FuncTest {
    public int add(int x, int y) {
        return x + y;
    }

    public int mul(int x, int y) {
        return x * y;
    }

    public int square(int x) { return x*x; }
    public Boolean greater(Comparable x, Comparable y)
    {
        return x.compareTo(y) > 0;
    }

    public Boolean or(Boolean a, Boolean b) { return a.booleanValue() || b.booleanValue(); }
    public Boolean and(Boolean a, Boolean b) { return a.booleanValue() && b.booleanValue(); }

    public Boolean truth(Object o)
    {
        if(o == null) return Boolean.FALSE;
        if(o instanceof Number) return ((Number)o).longValue() != 0;
        if(o instanceof String) return ((String)o).length() != 0;
        if(o instanceof Collection) return ((Collection)o).size() != 0;

        return false;
    }

    public static void main(String[] args) {
        try {
            // Func.curry(Test.class, Func.nop(Test.class).add(1,2)).curry(1).call(2);
            Lambda<Integer> mul = lambda(nop(FuncTest.class).mul(1, 2));

            Lambda<Integer> plus = lambda(nop(FuncTest.class).add(1, 2));
            Lambda<Integer> triple = mul.curry(3);
            Lambda<Integer> quadruple = mul.curry(4);
            Lambda<Integer> timesTwelve = compose(triple, quadruple);
            Lambda<Integer> sum = Util.reducel(plus, 0);
            Lambda<Integer> square = lambda(nop(FuncTest.class).square(0));

            quadruple.call(12);

            System.out.println(
                    timesTwelve.call(
                            sum.call(list(1,2,3,4,5,6,7,8,9,10))));

            System.out.println(
                        sum.call(Util.map(square, list(1,2,3,4,5,6,7,8,9,10))));


            Lambda<Boolean> or = lambda(nop(FuncTest.class).or(true, true));
            Lambda<Boolean> and = lambda(nop(FuncTest.class).and(true, true));
            Lambda<Boolean> truth = lambda(nop(FuncTest.class).truth(true));

            Lambda<Boolean> anyTrue = Util.reducel(or, false);
            Lambda<Boolean> allTrue = Util.reducel(and, true);

            Lambda<Boolean> greater =  lambda(nop(FuncTest.class).greater(1,2));

            System.out.println("There is a number greater than less than 0 "+anyTrue.call(Util.map(greater.curry(2), list(1,2,3,4,5,6,7,8,9,10))));

        } catch (Exception e) {
            e.printStackTrace();  //To change body of catch statement use File | Settings | File Templates.
        }
    }
}

2006-06-28T15:44:00.000-07:00

R.J. Lorimer who frequently posts very well written and useful Java tips on JavaLobby (and has authored the cool new site DZone. Update: RJ reports he had no active development role in DZone, sorry for the mistake) recently posted a few tips on using Ibatis. I'm not that big of a fan of Ibatis since IMHO mainly transforms writing tedious Java code to propagate ResultSets into Beans, into writing tedious but XML configuration files.

Using external XML mapping files, as is common in many frameworks for XML or Database persistence, if you make a change to the underlying objects, you have to make sure you keep the XML map files up to date. Sometimes IDEs can do this for you if you are lucky.

However, the point was made in the discussion that although annotations save some of the tedium of creating mappings, and provide some type-safe refactoring for the mappings, they have the downside of requiring the mapping information to be placed inside the POJO bean itself. In some scenarios, this could get ugly, especially if you've got a POJO that must be bound to both an ORM and an XML binding like JAXB.

So, is it possible to use Java to create refactorable type-safe bindings in external classes? The answer turns out to be yes. To understand how this can be done, one must recall a trick that Alex Winston posted a few months ago on Strongly Typed Java Delegates.

Alex's technique uses Generics in Tiger and CGLib generated method interceptors to perform its magic. But this trick is far more powerful than Alex is given credit for. It opens a new vista on metaclass programming in Java, a subset of what one gets in a language like Groovy or Ruby, but with strong type information preserved for the IDE to and compiler.

I started out not sure if it was possible, but after an hour of so of hacking, and I had a rudimentary Hibernate configuration version done. I won't fully explain how the following works, you can read Alex's original article for the gist, but here is a sample of what one can do.

Given the following POJO

public class POJO
{
   private Long id;
   private String firstname;
  
    public String getFirstname() {
        return firstname;
    }

    public void setFirstname(String firstname) {
        this.firstname = firstname;
    }

    public String getLastName() {
        return lastName;
    }

    public void setLastName(String lastName) {
        this.lastName = lastName;
    }

    public Long getId() {
        return id;
    }

    public void setId(Long id) {
        this.id = id;
    }
}

one map create a Hibernate mapping using my new Config class as so

public ConfigTest
{
  public static void config(Configuration cfg)
  {
       MapOp mo=Config.map(POJO.class);
       mo.table("mytable").id().bind().getId();
       mo.column("first").bind().getFirstname();
       cfg.addDocument(Config.xml(POJO.class));
  }
}

If you refactor any of the getter methods in POJO, the ConfigTest class will automagically be updated in most IDEs. Moreover, errors in mapping due to property name changes will be caught at compile time, unlike the XML mapping approach.

Looking at the above code, one might want to write

Config.map(POJO.class).id().bind().getId();

but javac complains, and there is a BugParade bug claiming that one must assign the return value of the map() function above to a temporary variable first. (ugh!)

Anyway, here is the hacked up code demonstrating the technique. Thanks for Alex for his original, of which I borrowed the code skeleton to produce this.



import net.sf.cglib.proxy.Enhancer;
import net.sf.cglib.proxy.MethodInterceptor;
import net.sf.cglib.proxy.MethodProxy;
import net.sf.cglib.proxy.NoOp;
import org.w3c.dom.Document;
import org.w3c.dom.Element;

import javax.xml.parsers.DocumentBuilderFactory;
import javax.xml.parsers.ParserConfigurationException;
import java.lang.reflect.Method;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * Create type-safe refactorable hibernate configurations without using annotations in POJOs.
 */
public class Config {

    private static Map<Class, MapData> mapping = new HashMap<Class, MapData>();
    private static Set<String> mapOpMethods = new HashSet<String>();

    static {
        for (Method m : MapOps.class.getDeclaredMethods())
            if (!m.getName().equals("bind")) mapOpMethods.add(m.getName());
    }

    /**
     * @param t - a class that you want to map in hibernate
     * @return a MapOp class which builds up a map before binding it to a method
     * @throws Exception
     */
    public static <T, S extends MapOps<T>> S map(Class<T> t) throws Exception {
        return (S) Enhancer.create(t, new Class[]{MapOps.class}, new ProxyInterceptor<S, T>(t));
    }

    public static Document xml(Class t) {
        MapData md = mapping.get(t);
        return md.getXmlDocument();
    }

    public static class ProxyInterceptor<S,T> implements MethodInterceptor {
        private T proxy;
        private Class<T> clazz;
        final private HashMap<String, Object> bindingData = new HashMap<String, Object>();

        public ProxyInterceptor(Class<T> target) {
            this.proxy = (T) Enhancer.create(target, NoOp.INSTANCE);
            this.clazz = target;
        }

        public Object intercept(final Object o, final Method m,
                                final Object[] args, MethodProxy mp) throws Throwable {
            final MapData md[] = new MapData[1];
            md[0] = mapping.get(clazz.getClass());

            if (md[0] == null) {
                md[0] = new MapData();
                mapping.put(clazz, md[0]);
            }

            md[0].setClassName(clazz.getCanonicalName());

            if (m.getName().equals("bind")) {
                return Enhancer.create(clazz,
                        new MethodInterceptor() {
                            public Object intercept(Object o1, Method m1,
                                                    Object[] args1, MethodProxy mp1) throws Throwable {
                                if (m1.getName().startsWith("get")) {
                                    md[0].bindToProperty(bindingData, getPropertyName(m1.getName()));

                                    bindingData.clear();
                                }
                                return null;

                            }


                        });
            }
            if (mapOpMethods.contains(m.getName())) {
                bindingData.put(m.getName(), args.length == 0 ? "" : args.length < 2 ? args[0] : args);
                return o;

            } else
                return Enhancer.create(m.getReturnType(),
                        new MethodInterceptor() {
                            public Object intercept(Object o1, Method m1,
                                                    Object[] args1, MethodProxy mp1) throws Throwable {
                                return proxy.getClass().getMethod(
                                        m.getName(), classes(args1)).invoke(proxy, args1);
                            }
                        });
        }
    }

    private static String getPropertyName(String methodName) {
        return methodName.substring(3, 4).toLowerCase() + (methodName.length() > 4 ? methodName.substring(4) : "");

    }

    private static Class[] classes(Object[] objects) {
        Class[] classes = new Class[objects.length];
        for (int i = 0; i < objects.length; i++)
            classes[i] = objects[i].getClass();
        return classes;
    }

    public static class MapData<T> {
        private Document hbm;
        private Element hibernate_mapping;
        private Element clazz;
        private Element id;
        private Map<String, Element> properties = new HashMap<String, Element>();

        public MapData() {
            try {
                hbm = DocumentBuilderFactory.newInstance().newDocumentBuilder().newDocument();
                hibernate_mapping = hbm.createElement("hibernate-mapping");
                hbm.appendChild(hibernate_mapping);
                clazz = hbm.createElement("class");
                hibernate_mapping.appendChild(clazz);
                id = hbm.createElement("id");
                clazz.appendChild(id);
            } catch (ParserConfigurationException e) {
                e.printStackTrace();  //To change body of catch statement use File | Settings | File Templates.
            }
        }

        public void setId(String name) {
            id.setAttribute("name", name);

        }

        public void setColumn(String dbColName, String propName) {
            getProperty(propName).setAttribute("column", dbColName);
            getProperty(propName).setAttribute("name", propName);

            System.out.println("Mapping " + dbColName + " to " + propName);
        }

        private Element getProperty(String propName) {
            Element e = properties.get(propName);
            if (e == null) {
                e = hbm.createElement("property");
                clazz.appendChild(e);
                properties.put(propName, e);
            }
            return e;
        }

        public void setTable(String tableName) {
            clazz.setAttribute("table", tableName);
        }

        public void bindToProperty(HashMap<String, Object> bindingData, String propertyName) {
            for (Map.Entry<String, Object> e : bindingData.entrySet()) {
                if ("id".equals(e.getKey())) setId(propertyName);
                else if ("column".equals(e.getKey())) setColumn(e.getValue().toString(), propertyName);
                else if ("table".equals(e.getKey())) setTable(e.getValue().toString());

            }
        }

        public Document getXmlDocument() {
            return hbm;
        }

        public void setClassName(String canonicalName) {
            clazz.setAttribute("name", canonicalName);
        }
    }

    public interface MapOps<T> {
        /**
         * Sets the database table for this class. Equivalent to @Table annotation
         *
         * @param tableName
         * @return
         */
        public MapOps<T> table(String tableName);

        /**
         * identifies the db column of the property to be bound, for example
         * <code> Config.map(Foo.class).column("first").bind().getFirstName(); </code>
         *
         * @param dbColumn
         * @return
         */
        public MapOps<T> column(String dbColumn);

        /**
         * identifies that the property to be bound will be be an ID column, equivalent to @Id annotation
         * <code> Config.map(Foo.class).id().bind().getFirstName(); </code>
         *
         * @return
         */
        public MapOps<T> id();

        /**
         * ends the current context for property mapping. The very next method call on type T if it is a call to a getter, like getFoo(), will bind
         * all of the previously configured information in the expression to the property 'foo'
         * <code> Config.map(Foo.class).table("footable").column("foofoo").bind().getMyFoo() </code>
         *
         * @return
         */
        public T bind();
    }


}