Schemers in Haskell country

Before coming to this conference I hadn't realized how much the Functional Programming community is dominated by Haskell people. Most of the presenations are very Haskell-y even though in theory much of the work should be universal.

Although the Scheme people occasionally point out to a presenter that his work sure looks like something the Scheme people figured out fifteen years ago, the two camps seem to get along fine most of the time. Wait'll the coffee runs low, though.

Why you should attend academic conferences

I really should apologize to my readers for the content of my posts on the presentations at the ICFP. Most of what I am saying about these have to do with my own level of knowledge about the subject (ranging from very minimal to completely innocent) and extent to which it piqued my interest, instead of the content of the talk. This is the way it has to be, as I am, with some exceptions, not sufficiently knowledgeable about the field to speak with authority about the talks - in fact I generally can't even provide a synopsis.

If you want to know about one of the presentations you'll need to find other bloggers, or better yet, read the paper. At least the abstract. But than since such papers are almost always available on the web, I have to ask: why are you reading this? Probably you are one of my regular readers (hi Mom!). Or you wrote the paper and are interested in what the community thinks of it (hi Jacob!). It's to the second group that my apology is directed: I'm sorry. I really don't know. You may as well ask the congressional page what he thinks of the Constitutional implications of a bill being debated. (I originally had that "ask the dog about the craftsmanship of a Persian rug he just soiled" but this is a family blog and a cheap dog poop joke just won't do now, will it?)

But if, like me, your understanding of most of the papers is limited, then maybe you are reading this blog to help you to decide if you should go to next year's ICFP. The answer is yes. Go, even if you must pay your own pay like I did. You meet really interesting people. I've met the authors of my favorite computer book of all time for example (one of them, Dan Friedman, and his co-author of another book, Robert Byrd, are right now sitting directly to my right, huddled over a cons cell diagram and some Scheme code scibbled on some hotel stationary trying to puzzle something out. Cool, eh?) You get to talk to interesting people and get a real feel about what the work of an academic is like (at least the research part). You get an idea of where the field is going, who is considered to be doing the most interesting work, and most of all, what parts of the field have attracted the most interesting and enthusiastic people and how to participate in those parts. I can tell you that I'm much more seriously thinking of grad school now than I was when I arrived. I want to understand more of these papers.

ICFP presentation: Practical Proofs of Concurrent Programs by Marc Shapiro

I'm not especially interested in concurrency issues (read that: I'm not sufficiently knowledgeable in the field to be interested). They tend to be difficult, non-hackable problems. That is, you can't just start hacking away on the problem to see what works. You have to prove that your solution works; no amount of testing (much less a quick try through a few edge cases) can prove that it will work. That said, I'm all for people coming up with abstractions or frameworks that ease this problem for those of us who would rather not think about these problems so much. Hats off to them!

Everything before lunch today (Tuesday, the second day of the official conference, my third day day here since I attended this pre-conference Scheme workshop) is on the topic of concurrency so I'm not exactly on the edge of my seat. I wonder if I can catch a nap somehow...

Nevertheless I was interested by the first talk, by Marc Shapiro on using Rely-Guarantee analysis to prove correctness of concurrent programs. If I understand what he is doing, his work shows a new way to divide the concurrency issues of a given program into smaller pieces, each of which may be divided into smaller pieces using the same technique, until the pieces are small enough that the set of all the things that the pieces rely upon are guaranteed by the pieces. If you can do this, your program is proven to be safe with concurrency. I need to read the paper, except it looks like only the abstract is present in the Proceedings of the conference.

Planet - PLTScheme's central package storehouse and installation system.

Surely everyone envies Perl's CPAN. Other languages either already have such a system (like Ruby Gems or Common Lisp's asdf-install) or are building one.

So one of the happy warriors who hack PLTScheme, Jacob Matthews, has come up with a system of his own, Planet. It sounds good. I really don't know much about it but at least one can be heartened by his choice of models, CPAN and Debian's apt-get.

It has some nice features:
They enforce standards on the numbering of versions. If you release a version that breaks users of your previous version, you must call it by a new major number (5.0, 6.0, etc.)
They have integrated Dr. Scheme with this so that you can visually see what functions came from what packages, using the arrow pointing thing that Dr. Scheme uses to show you your stack trace when your code crashes. (Wait, is this just part of the packaging system? I'm not sure that Planet added this. In any case, it's a good thing for Scheme.)

Of course the real difference between this and CPAN is that CPAN has 2 gigabyes of perl source made up of who knows how many gazillions of modules. Planet has 115 packages (or modules, I don't know about Scheme packaging).

Given the trouble I've had getting Common Lisp's asdf-install configured properly on my Windows machine, I am hopeful about the prospect of something better in the Scheme world.

Technorati: scheme, icfp, lisp, pltscheme, drscheme, planet, packagerepositories

Ray Rischpater: Scheme on the mobile phone. From the Scheme workshop at ICFP

Ray Rischpater gave an gratifying talk on what his company, RocketMobile Phone has done with Scheme on the mobile phone. They've done it with a port of TinyScheme.

It sounds like they wrote their own browser so that they can get access to things like the address book, the list of recent phone calls, etc. Probably GPS data too. They do this by serving WML-like pages to the browser that include Scheme between script tags. I'm interested in knowing why they chose the browser route. They were building their own client to interact with thier own server... is the browser model superior even for a single application, single server situation? I suppose a major factor was that they already had server-side infrastructure ready to go, including programmers that are accustomed to that model. And who knows, maybe they are reserving the option to dominate the wireless browser market for the glory of Scheme!

Question: are they sending WML to their browser when not sending blocks? It would seem so.



(Technorati Tags: icfp, scheme, lisp, wireless, rocketmobile, tinyscheme)

2006 Scheme workshop at ICFP - Jay McCarthy and Shriram Krishnamurthi on continuation passing for web state.

So far this was the best session for me here at the ICFP. We've been hearing a lot about using continuations for keeping state in web applications. This was a good, non overreaching presentation on the subject. It was something of a revelation for me. I was previously under the impression that if you choose the continuation-passing method of preserving state, then you forsake all others. Putting data in cookies, keeping session data in the database (with session id in URLs or in a session variable), putting data directly in session variables... I had thought that this new statefulness required you to kick these to the curb. But it turns out that continuation passing is not jealous. There's no reason not to use them for some of the state in your application and whatever other method for other parts of your state. This is great. Basically you keep using the older methods of state as long as they are working fine for you. It's only when the state becomes problematic (Jay implies that this especially comes up when the user has multiple views of the same data open at once) that you turn to the continuations. Kudos to Jay for being pragmatic about this. Jay's paper (with Shiriram Krishnamurthi) and presentation was based on the the production code they shipped for the PLT Web Server to do these continuations.

Great talk.

(Technorati Tags: icfp, scheme, lisp, continuations, pltwebserver, web)

More from the Scheme workshop at ICFP - Guillaume Germain and Termite Scheme

SeaFunc's own Guillaume Germain presented on Termite Scheme. This is his implementation of the interesting and useful principles of Erlang in Scheme. As I know nearly nothing of Erlang, I appreciated his overview of what exactly it's principles are. Those include : "Every process has a mailbox, the only way to talk to it is send it a message." "Sending a message won't block." "Receiving a message might."

Interesting talk. It was good to talk to Guillaume again, too.


(Technorati Tags: icfp, scheme, lisp, erlang, termitescheme)

Blogging the Scheme workshop at ICFP - William Byrd, Dan Friedman and miniKanren

Some very interesting stuff so far. William Byrd - coauthor of The Reasoned Schemer (along with Dan Friedman, who is sitting behind and to the right of me which is pretty damn cool. Dan and Mattias Fellesen co-wrote The Little Schemer, which is probably my favorite book ever. Mattias sat right next to me earlier. There's the advantage of a working with a language that hasn't achieved mass popularity - beginners like me are have access to the leading people. That the leading people of your language are a big chunk of the leading people in the field of Computer Science is a good indication that you are working with the right language.) - gave a talk on his and Dan Friedman's creation, miniKanren, which apparently is a more or less an implementation, in Scheme, of an imaginary language described in that book. It's for logic programming - interesting. He lost me several times - I need to read the paper. And learn more about logic programming generally. Byrd is a very clear speaker. It would seem he's given the talk before, based on his polished delivery. If not he's someone a conference-goer really appreciates: a speaker who rehearses a lot.


(Technorati Tags: icfp, scheme, lisp, minikanren, logicprogramming)

Switching to Blogger, leaving behind my old blog.

Hello, readers. I've been mulling the advantages of moving my blog to an automated and hosted option for a little while now. I think now's the time. Now if I can figure out how to add my old blog's posts here with the proper dates...

My old blog is www.herdrick.com

First professional guitar lesson.

Time to stop noodling around on the new guitar and start playing. I just got back from my first lesson ($40 per hour! It better be good.) I'm looking forward to plenty of hard but rewarding work. A lot like the other learning going on in my life right now.

Party archeology.

You know it was a good party when you find mysterious things like this the next morning:

Launch Party 2.0

Did you hear a booming sound or was that just in my head? The TechCrunch party last night was good and there were some signs that technology optimism is back.

ConWorks, the hip South Lake Union venue where the TechCrunch people (are there people or it is just Michael Arrington by himself) held the party was perfect - a big, artsy (apparently it is usually an art gallery) warehouse. Talking with the bartender (on her smoke break) and some guy who works there in the alley behind the place I was told it was supposed to be held somewhere else; ConWorks was a last minute replacement. I don't know how it could have turned out better, though. They also said that some students of a digital art program at the U were busy assembling their exhibits for some kind of show this weekend. Sounds interesting.

Demos and evangelizing by the sponsors, Redfin (who paid for the hefeweizen and pizza I'm told), TripHub and Farecast, were available on the corners and edges of the rooms. I like TripHub; it's sort of an Evite for trips with lots of extra features. I wonder if it would work for planning mountaineering expeditions? Farecast looked more like an economics research project than something I would use. The idea is that is uses historical data to figure out when airfares go up and down for particular routes on particular days, and then recommends when to buy tickets. I'd think that the cyclical trends this thing tracks would be overwhelmed by changes in fuel prices and structural changes in the industry. The airline business is known for major changes which would make previous data pretty useless. In any case I'm not waiting a week to buy airline tickets because some software is confident that the price will drop $20. Sounds like a hassle.

Quite a few conversations about interesting startup ideas were happening and - funny thing - the founders were admirably keen to talk in detail about what they are working on and why it's good. That was unusual - getting people to tell you what they are building can be impossible. Winter Founders Program investee Chris Smoak was there, plotting his move to Boston and mulling over the virtues of other towns, like Portland and Pittsburgh. I met up with John Wulff whom I had previously met at the Seattle Ruby users group, and Ruby on Rails podcaster Geoffrey Grosenbach and Tom Lianza also from Seattle Ruby. Tom will soon launch his startup, Wishlisting which sounds like a useful service. The founders of this hotornot inspired site drove down from Vancouver and seemed to think it was worthwhile. UPDATE: Thanks to TechCrunch and Jay and Silent Rob for links...

A good party - and the abundant free beer and pizza didn't hurt.

Paging Erik Lickerman

I'm looking for my friend Erik Lickerman who has recently moved to Cambridge, (Boston) dropping his email address and telephone number. So if you see this Erik, email me. Hester and I are looking for you.

Scheming

In reading the excellent book, The Little Schemer (see blog posting below) and writing the code for the exercises, I've come across something in Chapter 6 that is puzzling me. It appears that the book's code for numbered? is wrong. (Yes, I know it's not. Just stick with me while I try to figure out what I'm missing.) Here it is:

(define numbered?
(lambda (aexp)
(cond
((atom? aexp) (number? aexp))
((eq? (car (cdr aexp)) '+)  (and (numbered? (car aexp)) (numbered? (car (cdr (cdr aexp))))))
((eq? (car (cdr aexp)) 'X)  (and (numbered? (car aexp)) (numbered? (car (cdr (cdr aexp))))))
((eq? (car (cdr aexp)) '^)  (and (numbered? (car aexp)) (numbered? (car (cdr (cdr aexp)))))))))

As I have done with all of the exercises in the book, I coded up the solution (using Dr. Scheme, which is great, by the way) before looking at the answer. I was pretty disappointed to see that the book's solution was much smaller than mine. As I reasoned my way through their solution I was confused at how it could work. I was right to be confused; it doesn't work.

Let's try it from Dr. Scheme's interactive toplevel.

> (numbered? '(1 + 2))
true

Great!

> (numbered? '(1 + a))
false

OK, fine. Let's try something a bit more complicated.

> (numbered? '((1 X 2) + 3))
true

Still good. How about a bit more complicated?

> (numbered? '(1 + 2 X (3 + 4) ^ 5))
true

OK, but let's try one that should fail.

> (numbered? '(1 + 2 X (3 + 4) ^ a))
true

Uh, oh.

> (numbered? '(1 + 2 X (3 + 4) ^ a + + ))
true

That's not good.

> (numbered? '(+ 1 + 2))

Well? We're waiting! (No result was returned.)

It turns out that there is a problem in communication. I didn't read the definitions carefully enough, and I'd argue that they weren't clear. First of all, they make the assumption that the argument to the function is an arithmetic expression, so things like (numbered? '(+ 1 + 2) aren't allowed. OK, but what about (numbered? '(1 + 2 X (3 + 4) ^ a))? Well, here's the definition of an arithmetic expression from the book: "For the purpose of this chapter, an arithmetic expression is either an atom (including numbers) or two arithmetic expressions combined by +, X or ^". Now, I thought that would include something like (1 + 2 + 3), since 2 + 3 is an arithmetic expression, and 1 is an arithmetic expression. Since this book is all about recursion and defining things recursively, my mind sort of skipped over the fact that although 1 is an arithmetic expression, 1 + is not. So (for the purpose of this chapter) (1 + 2 + 3) isn't an arithmetic expression.

This is something I hadn't figured out when I started writing this blog post. It turns out that for me, completely understanding what happened required writing about it. So thanks for listening, internet people.

I'd also like to note that such a terse explanation really isn't so good in this case because "arithmetic expression" is a term loaded with meaning already. Their explanation wasn't enough to make me realize that I needed to recalibrate my thinking. Possibly what is happening here is that "arithmetic expression" expression is a common term in academic Computer Science, something of which I am not knowledgeable. But then, this book makes no assumptions about the readers previous experience.

While I'm complaining, I'll mention that I didn't really understand what this question and answer meant, either: "Question: Why do we ask (number? aexp) when we know that aexp is an atom? Answer: Because we want to know if all arithmetic expressions are numbers." Huh? I guess they mean, "Because we want to know if each arithmetic expression is a number", which makes sense but seems to be circular reasoning. This might seem like a pretty minor thing to trip oneself up on, but the rest of the book has been so precise that I was assumed there had to be more meaning. That's a testament to how good this book is.

It goes very strongly against my experience in software development to write brittle programs. numbered? is just the most egregious of those so far, really most of the code in the book doesn't handle bad input. Yes, I completely realize that this is meant to be a learning experience about recursion, lambda calculus and so forth, and not about practical stuff like error handling, and I'm glad of it. The problem is that it's hard for me to get myself completely unwrapped from my practical experience. My brain has a hard time not coming up with code that tries to deal with this.

Anyway, for what it's worth, here's my version of numbered?, which works for a more broad definition of arithmetic expressions:

(define numbered?
(lambda (aexp)
(cond
( (number? (car aexp))   (or (null? (cdr aexp)) (and (operator? (car (cdr aexp))) (numbered? (cdr aexp) ))))
( (operator? (car aexp)) (and (or (number? (car (cdr aexp))) (not (atom? (car (cdr aexp))))) (numbered? (cdr aexp))))
( (not (atom? (car aexp))) (and (or (null? (cdr aexp)) (operator? (car (cdr aexp)))) (numbered? (car aexp)) (numbered? (cdr aexp))))
( else (write "else") #f))))

Which requires this helper function:

(define operator?
(lambda (op)
(cond
((eq? op '+) #t)
((eq? op 'X) #t)
((eq? op '^) #t)
(else #f))))

And I should mention that since the book's version assumes that the input is an arithmetic expression, they simplify it to:

(define numbered-simplified?
(lambda (aexp)
(cond
((atom? aexp) (number? aexp))
(else (and (numbered-simplified? (car aexp)) (numbered-simplified? (car (cdr (cdr aexp)))))))))

which is impressive.

A good April Fools Day weekend.

What all books ought to be.

The Little Schemer was first published (then called "The Little LISPer") over two decades ago, it uses an dialect of a somewhat obscure programming language that's been around since 1958, and it's the best computer book I've ever read. It's the best textbook I've ever read. In fact, it's the best book I've ever read to learn something. Maybe it's just the best book. Why? Look at the first page of text (courtesy Amazon):





Where's the text? Where's the explanation of what I'm supposed to learn? Where's the material? Well, it there, but it's just questions and answers. You read a question and you try to answer it. You probably know this as the Socratic method of teaching, or it would be called that if there were a teacher in the flesh asking the questions. You would think that such a style of learning would rely upon the teacher carefully monitoring the student's understanding and tailoring the questions accordingly. But I guess not. Or that is, I guess you don't need to customize the questions, you just need to get the questions exactly right. They did.


(Even if this book weren't socratic, I'd be in my top ten of computer books just for jumping into the subject right off the bat instead of starting with fifty pages of the usual filler followed by a "gentle" introduction to the topic at hand. If I had a dollar for every book I own that has: "Chapter One: The History of Java" and "Chapter Two: Why Should I learn Java?" and "Chapter Three: Java and the World Wide Web" I could save myself the time of selling them on Amazon. Though I could make, in many cases, as much as double that.)


The really great thing about this book is that actually the material mostly isn't there, not in print. The most important part of the "read a question, try to answer" cycle is "figure out what the writers wanted you to learn from it". For the best questions, you don't figure out all the intent until several questions later. Or maybe even several chapters later, I don't know yet. I'll keep you posted.

So are there any other "socratic" books? Yes. The authors of The Little Schemer (Daniel P. Friedman and Matthias Felleisen) later wrote a similarly styled book about Java (and though I haven't read it, I know Java very well, and I'm pretty sure that what the reader learns is far inferior in that book). This book in turn collected an imitator (I mean no disrespect) directed at teaching Ruby. Only a few chapters of the Ruby book have been written, but on the plus side, they are freely available. Shouldn't there be books written in this style in other subjects? There must be, right?

In raving about socratic books, I have left something out. I implied above that the subject matter of the book is a drag on it's greatness, that the book is good in despite that it's a Lisp book. And I would be pretty impressed with such a book no matter what the topic. But in fact I am working my way through the book entirely *because* it's teaching me Lisp (in this case the Scheme dialect of Lisp), or using Lisp to teach me how to program in the Lisp style. And Lisp is good.

Logos!

Want a Google-esque logo? The fun people at GoogleFor.com have it covered for you. You can make a logo with any arbitrary text and they throw in a branded skin on Google while they are at it.
You can get sort of 2003-vintage web startup logo from the same folks: Downside: it looks like a bag of ugly. Also, it's in .bmp format. I guess this must have been the first version, which gives the little "beta" stamped on each logo extra meaning. Really you can do better than this in a few minutes with MS Paint.