A Trifle Absurd

Local or Remote Servers?

I wrote the last entry with the assumption that people would want to install Trifle on other people’s servers, rather than just on their home machines. The question, though, is whether that’s an important case or not. With the prevalence of broadband, more and more people have home machines connected to the internet, and could serve out Trifle information from there. Scalability isn’t a concern since the server would normally be accessible to only a handful of people.

Not only that, but when it comes to sensitive information like financial records (which, like anything else, Trifle can organize), people would be far more likely to trust their home machine than some third-party server. And if they don’t want to even host a private server, they don’t have to.

So perhaps the 80% solution is to expect a home-machine install, but then provide tools to reflect certain items (such as blog entries) to a public server. That, of course, reopens the door to using any language I want (darn, that means I have to choose one).

Any Language I Want?

Trifle will be distributed for people to install on their own servers, instead of a Web service centralized on one (set of) servers.  (In other words, it’s like Movable Type, not Google.)  I should probably keep hosting-provider server setups in mind as I design Trifle and pick components, unless I can assume the user will (a) install it on their own machine, or (b) have a virtual host they can do anything with.

This could be a big factor in the choice of language.  I’ve been assuming that I can use any language I want on the server, for the reasons Paul Graham mentions.  But those reasons only hold if I control the server.  I suspect that not many hosting providers offer Haskell…

So does that mean I’m limited to Perl, Python, PHP, and maybe Ruby?  I’m not sure.  I expect that a common use of Trifle will be on a home server (where you could install anything), but if you don’t have broadband with static IP, you won’t be able to access your data remotely.  (Hmm, need to think some more about replication.)

This sure does seem like a case where using a (relatively) Popular Language has its advantages.  Oh, well.  At least Python doesn’t suck.

Building Trifle for the Web

I’ve decided to build Trifle as a Web application — runs on the server, you use it through a browser, you know the drill. I resisted this thought for a while because it seemed like a knee-jerk response (aren’t we all writing web applications these days?), and because Trifle itself doesn’t have an intrinsic relationship to the Web (it could be built on another platform if needed). In the end, though, I’ve realized that the Web is the right platform for Trifle.

Leaving aside all of the obvious Good Things about the Web like worldwide reach and easy sharing, the Web is becoming a great application development platform. I can build a dynamic and flexible UI and change its look with style sheets. I have a built-in scripting language to control the front end. And if I play my cards right, my application will run on just about every OS under the sun. Sounds like a good platform to me — especially for an information-centric application like Trifle that doesn’t need much real-time interaction.

So how am I going to implement this? Naturally, the back-end components look awfully familiar: a web server, a page generator, a document archive, and a database. On the one hand, this is a bit discouraging since it makes me feel like I’m trodding a well-worn path. On the other hand, it makes it seem plausible for me to build Trifle by myself, since I can use existing components.

I’m assuming the web server will be Apache unless the page generator happens to have its own server. The page generator will be yet another template system — I don’t particularly feel like writing my own, but I still haven’t come across anything I like very much. The document archive will probably be just the filesystem at first, later augmented to include versioning and full-text search.

The database will be harder to find. I want to use an items-and-categories metadata scheme like Agenda’s, but that doesn’t fit into the relational model very well, so I may be forced to roll my own. This is where most of my experimentation has been so far, but I still don’t have a solution I like.

The Functional Programming Process

When I program in a functional style, I go about it differently than when I program imperatively. There’s more up-front thinking (sometimes a lot more) before I start coding, and when I do write code, more thought goes into each line. The resulting program is often much shorter than its imperative equivalent, and is far more likely to work the first time (with or without static typing).

So, if it (usually) works the first time, isn’t it faster to write functional programs? An imperative program may take a few tries to debug, but I’m able to get started on something sooner that way, so I’m debugging sooner. In the end, the time to develop a program in each style may be about the same. (Remember, this is all my subjective experience.)

But isn’t there an advantage to having shorter programs? Shouldn’t they have fewer bugs and be easier to understand? You’d think so, but perhaps the functional program is simply a denser representation of the same ideas. If the functional program is 50% shorter but each line takes twice as long to understand, have you gained anything? I’m playing devil’s advocate a bit with this one; I think that in general the shorter FP programs are higher-level as well, and so there are benefits of fewer bugs and greater understandability. It’s not a cut-and-dried win, though.

Is FP ‘better’? I’m still not sure. It’s certainly a paradigm that all good programmers should be familiar with, especially since there are problem areas where it’s a huge win. But, of course, there are always tradeoffs. We still haven’t found that silver bullet.

Haskell’s Native Design Model

In reading Haskell papers and programs, I keep seeing the same design model: combinators. I’d almost say that combinator-oriented programming is Haskell’s native design model. Consider this quote from John Hughes’ paper The Design Of A Pretty-Printing Library: “The functional programmer, then, should approach a new application by seeking to identify the programming idioms common in that application area, and to define them as (probably higher order) functions. Each particular application program should then be built by so far as possible combining these functions, rather than writing ‘new code’. (Perhaps for this reason, such functions are often called combinators.)” [emphasis in original]

Just what does Haskell provide to enable this style? First, as Hughes implies, higher order functions. Next is the ability to define new infix operators; combinators are often conveniently expressed as infix operators (e.g. >>=, the monadic bind operator). Also, IMO, pervasive currying simplifies common combinator expressions quite a bit. Finally, type classes provide a useful way to generalize combinators (the same mapM works in any monad). Not all of those features are strictly necessary for combinator-oriented programming, but they combine to provide a convenient and expressive environment for combinators to thrive.

Trifling with Names

Confession time: I originally picked Trifle as a name by looking through the “tri-” section of the dictionary. At the time, I was planning to make Trifle RDF-centric (a plan since dropped, thank heavens), and so I was thinking in terms of triples. I toyed with “trigram” and even “triskele” (the latter thanks to Gene Wolfe) before settling on “trifle”. It appealed to me as a nice-sounding word with a meaning that would keep me from taking the project too seriously. I also thought of Alan Kay’s rationale for naming Smalltalk: “I figured that ‘Smalltalk’ was so innocuous a label that if it ever did anything nice people would be pleasantly surprised.”

However, I’m starting to have doubts about the utility of “Trifle” as a project name. The reason: it’s too common a word to be Googleable. There’s a big advantage in having a unique name in the Google era — someone can hear the name somewhere and just Google to find it. (Of course, past a certain level of popularity it doesn’t matter anymore: Google for ‘python’ and you won’t find any pages about snakes in the first hundred results.)

So, given that plus the fact that I’m not using RDF anymore, I’m thinking a new name is in order. It could be acronym, like IMDB, or a compound word, like fluxbox or icecast; or a collision of two words, like Linux, Mozilla, or Wikipedia. In general, I’d prefer a neologism over an acronym, just because it’s easier to say and easier for people to remember. But what?

Mandelbrot ASCII Art in Haskell

Bill Clementson has posted a short Lisp program (by Frank Buss, see his newsgroup post) that draws an ASCII Mandelbrot set. I thought I’d try writing a Haskell version as a fun exercise. Here it is (reformatted to 65 columns):

import Complex
import Char

main = putStrLn $ unlines [ mrow y | y←[-1,-0.9..1]]
where mrow y = [ mchr (x :+ y) | x ← [-2,-1.96..1]]
      mchr a = chr . (126-) . length
             . takeWhile ((<2).magnitude) . take 94
             $ iterate (λz → z*z + a) a

I know what you’re thinking, ’cause it was my first thought too: “Gosh, isn’t that pipeline terribly inefficient?” Remember, though, we’re in Lazy Land. The functions in the pipeline act incrementally and in step with each other. For instance, if the fifth element in the list reaches magnitude 2, causing takeWhile to stop, then take doesn’t traverse the remaining 89 elements, and they’re never constructed. In other words, only a list of five elements is actually built — that’s just how cool lazy evaluation is.

Actually, it can be even cooler than that. Since the elements generated by takeWhile are immediately consumed by length, mchr can run in constant space. It’s the data-structure equivalent of tail recursion. In effect, we’ve transformed a control structure (a recursive function) into a data structure (a list). This seems like a Big Idea to me, but I’m still not deep enough into Haskell to see how big it can get.

~~~~~~~}}}}}}||||||||||||||||||||{{{{{{{{zzzyxuqvtVz{{{{{||||||}}}}}}}}}}}}}
~~~~~~}}}}||||||||||||||||||||{{{{{{{{{zzzyxwvn`pvwyzzz{{{{{||||||}}}}}}}}}}
~~~~~}}}|||||||||||||||||||{{{{{{{{{zzyyyxwum    Jmvxyzzzz{{{{||||||}}}}}}}}
~~~~}}||||||||||||||||||{{{{{{{{zzyxwtwwwvutp     ruvvxyyyxqz{{|||||||}}}}}}
~~~}|||||||||||||||||{{{{{zzzzzyyyws=  pe             ossepdpyz{||||||||}}}}
~~}||||||||||||||{{{zzzzzzzzzyyyxvnsm                     `sxyz{{||||||||}}}
~~|||||||||{{{{zzyvuxxxxxxxxxxxwurO                        rvuyz{{||||||||}}
~||||{{{{{{{zzzzyxwuoMZtqrouvvuh                           pwyz{{{||||||||}
~|{{{{{{{{zzzzzyxxstm         pp                            `uyz{{{||||||||}
~{{{{{{zyyyyxxwsqnpa           `                            wyzz{{{||||||||}
~?G:9" 6% (                                              ouwxyzz{{{{|||||||}
~{{{{{{zyyyyxxwsqnpa           `                            wyzz{{{||||||||}
~|{{{{{{{{zzzzzyxxstm         pp                            `uyz{{{||||||||}
~||||{{{{{{{zzzzyxwuoMZtqrouvvuh                           pwyz{{{||||||||}
~~|||||||||{{{{zzyvuxxxxxxxxxxxwurO                        rvuyz{{||||||||}}
~~}||||||||||||||{{{zzzzzzzzzyyyxvnsm                     `sxyz{{||||||||}}}
~~~}|||||||||||||||||{{{{{zzzzzyyyws=  pe             ossepdpyz{||||||||}}}}
~~~~}}||||||||||||||||||{{{{{{{{zzyxwtwwwvutp     ruvvxyyyxqz{{|||||||}}}}}}
~~~~~}}}|||||||||||||||||||{{{{{{{{{zzyyyxwum    Jmvxyzzzz{{{{||||||}}}}}}}}
~~~~~~}}}}||||||||||||||||||||{{{{{{{{{zzzyxwvn`pvwyzzz{{{{{||||||}}}}}}}}}}
~~~~~~~}}}}}}||||||||||||||||||||{{{{{{{{zzzyxuqvtWz{{{{{||||||}}}}}}}}}}}}}

Is Purity Worth It?

I’m still pondering whether purity is worth it. What does it gain you? In a strict language, I don’t think it really gains you anything — there’s nothing to lose by adding in assignment, as long as it’s added in a controlled way (i.e. like ML’s refs as opposed to Scheme’s set!). Then you can be pure when you want to, and impure when you want to, no problem.

But when you come to lazy evaluation, the game changes. Instead of assignment being a nice additional feature, it becomes a completely nonsensical feature. Lazy evaluation abstracts away from the sequencing of operations, yet assignment only makes sense in terms of a sequence of operations. So, one potential win purity buys you is the possibility of lazy evaluation. (I wonder: did the creators of lazy functional languages make them pure so they could be lazy, or did they make them lazy so they’d have to stay pure?)

Laziness, of course, has its own pros and cons. On the one hand, it makes many kinds of programs simpler and clearer, for example by enabling pipeline patterns. But on the other hand, it all but eliminates the possibility of having a debugger in the conventional sense. (Whether the latter is a pro or a con depends on who you ask…) Yes, it abstracts from sequencing, but does it abstract too much? Smalltalk-style OOP has a concrete simplicity that pure-and-lazy FP doesn’t match.

One could counter by saying that a lot more people write code in Excel than in Smalltalk. Clearly, spreadsheets are the all-time-greatest FP win. Does that experience generalize to all-around programming, or is it specific to the domain of arithmetic? We still don’t know — another reason why lazy purity is still a research topic.

A Grand Experiment

Haskell is unabashedly a research language, because it centers on the exploration of way-out-of-the-mainstream ideas that might not ever enter the mainstream. Despite all the pro and con pronouncements of the past few decades, the jury is still out on purely functional programming and lazy evaluation.

Purity makes it easier to reason about programs and algebraically manipulate them, and opens the door to a host of program transformations and optimizations that would be unthinkable in an imperative context. For instance, purity makes lazy evaluation possible (just imagine trying to program in a lazy language with assignment!).

Many ideas can be expressed simply and elegantly in a purely-functional fashion; still, there are many ideas that are awkward to express in a purely-functional form. The idea of mutable state just won’t go away, not because it’s based on imperative programming languages, but because it’s based on our mental models of and interactions with the physical world (see Gelernter and Jagannathan’s Programming Linguistics). So how do we think about state when programming? Should state be a fundamental construct that you just happen to ignore when programming functionally? That’s the approach Scheme and ML take. Or should state be modeled atop a pure system? That’s Haskell’s way, via monads.

Are the gains of purity worth its sacrifices? Right now most programmers don’t think so, but pure languages just keep getting better and better, and the sacrifices get fewer and fewer. Still, it might all peter out in the end, or maybe just get watered down and inserted into mainstream languages (e.g. as generators, a limited form of lazy evaluation). As things stand, purity and laziness are fascinating avenues to explore, not just for theses and papers, but for practical programming, too.

The Power of Being Lazy

A couple of posts ago, I mentioned that lazy evaluation can substitute for macros in certain cases. Philip Wadler goes further in How to Replace Failure by a List of Successes. His last sentence: “Whereas the power of Lisp is that it is relatively easy to define new language features, the power of lazy functional languages is that one does not need to.” The content of the paper bears that out: Wadler demonstrates how to implement backtracking search and a DSL for parsing using a few simple functions.

The more I get into Haskell, the more I appreciate the power of lazy evaluation; it’s good for a lot more than replacing macros. Lazy evaluation lets you decouple problems into separate stages without the inefficiency of building large intermediate data structures — the different stages pass control back and forth behind the scenes, not unlike a Unix shell pipeline.

There’s no doubt, though, that lazy evaluation takes some getting used to, because it doesn’t just change when things happen, but also what order they happen in. This can lead to subtle gotchas, such as space leaks, and things that run counter to a strict-programmer’s intuition. For example, under lazy evaluation, foldr is sometimes more space-efficient than foldl. The Schemer in me splutters “But, but… foldr isn’t tail-recursive!” Yes, but this is Lazy Land, where things are not what they seem.