Something I'm missing?

This makes me a bit mad. And this ups the boggle factor. How do you define a -map function, a -fold function, but forget to do the -filter?

Probably I'm complaining about something I should be fixing. Or there's some good reason for this that every Schemer more experienced than me knows.

Scheme makes you smarter by making you feel dumb

This sums it up.

atom? - Get it right.

Since Google seems to be having a hard time finding it the right definition, I'd like to point out for the record that in Scheme, atom? should be defined so:

(define atom?
  (lambda (x)
    (and (not (pair? x)) (not (null? x)))))

Other definitions should be stoned to death or at least given a very dirty look.

Thank you for your attention to this matter.

Fever's break

Upon emerging from the worst of my head-cold chest-cold fever, I realized: association lists work fine for any arbitrary key/value pairs. A very obvious thing I suppose, but something had been throwing me off when I was thinking of alists this morning. When you cons the key onto the value, but the value is a list, then the resulting alist entry isn't a dotted pair, it's just a plain old list. But who cares? Functionally it's identical. It may as well be a dotted pair. Look:

(a . (1 2 3))
(a 1 2 3))

Are the car and cdr of this any different? No.

Obvious, yes, but I had a fever! I was lucky to be thinking at all. Get off my case!

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.

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)

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.

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.