2007 February « programming musings

Scheme loops

February 25, 2007 — jao

If you’re a schemer, expressing iteration by means of tail-recursion and named lets has probably become second-nature to you. I find this idiom both natural and elegant, but as Olin Shivers points out in his DanFest presentation below, it has some drawbacks. For instance, the code in a typical named let will work only for a given sequence type (e.g., a vector or a list); and, as Olin explains, its ‘goto-nature’ does not mix well with lexical scope. In other words, tail-recursive schemy iteration is too low-level and, according to Olin, a higher-level abstraction hiding details and providing a modular interface and proper lexical scope is called for. In his presentation, he outlines his solution to this problem, which, as you will see, amounts to defining a looping domain-specific language (actually, a couple of them). A more detailed explanation is given in his paper The Anatomy of a Loop. As an extra, the first few minutes of the video below will get you acquainted with the mysterious Dan effect.

But Olin’s is not the only solution to looping in scheme. Alex Shinn wrote and excellent survey on Scheme iteration methods in his Yow! LOOP macros are LOOPY!, which discusses at length current approaches to solve the problems mentioned above (like srfi-42 eager comprehensions or Jonathan Amsterdam’s iterate macro). For extra fun, Alex includes implementations for most of the loop constructs he reviews, a good way of improving your macro programming.

(Also worth reading in this context are Oleg Kiselyov’s thoughts on collection traversal APIs, where he draws a clear distinction between enumerators (such as scheme’s for-each or fold) and cursors (such as C++ iterators, i.e., objects maintaining internally the “current element” of the collection being traversed). As you will see, he makes a pretty good case for enumerators.)

So, you see, there’s many a way to loop a cat!

Posted in Scheme. 2 Comments »

Classic Texts in Computer Science

February 22, 2007 — jao

Babar Kazar has compiled an awesome (and i mean awesome) list of Classic Texts in Computer Science. There one finds almost every paper to read if one is serious about computers. The list is too long to put it all here, and virtually all of them are interesting in one way or the other, so i won’t make a selection right now: just take a look at them, and try to pick one: i bet you’ll have a hard time deciding!

Although it’s a bit late for new year’s resolutions, here is mine: i plan to at least skim through all these texts, read many of them, and, of course, keep you informed.

Posted in Lisp, Programming, Scheme. 5 Comments »

A (video) celebration

February 21, 2007 — jao

On December 3 and 4 of 2004, the Computer Science Department at Indiana University hosted a conference on the occasion of Dan Friedman’s sixtieth birthday. It brought together many of his former and present students, colleagues, research collaborators, co-authors and friends. That is, it brought together many of the big names in the Lisp/Scheme community (not in vain Shriram Krishnamurthi once imagined the Scheme community “a brotherhood of Dan”). Guy Steele delivered a one hour keynote, which was followed by more than twenty half-an-hour talks by people like Sussman, Dybvig, Shivers or Kiselyov, just to name a few.

The extremely good news is that, in the conference’s webpage, one can find the videos for almost all these talks! So, don’t be surprised if i’m missing during a few days! Besides the obvious interest in their contents, i’ll also find amusing to connect names with faces (it’s funny how one makes up fictitious faces for the authors of papers one reads and re-reads)… how many of them do you recognise?:

(I admire the work of many of these people, and i was convinced i wouldn’t be able to single out one among them… but to my surprise, and with all due respect to all schemers, i can: to my amusement, one of the participants is one of my few personal heroes. I’m not sure about the connection between him and Dan, but i’m very pleased to know there’s one. Surely you can spot this (to me, at least) rara avis?)

Posted in History, Lisp, Programming, Scheme. 2 Comments »

Quantum hype

February 18, 2007 — jao

One of the things i would really, really like to see some day is a working quantum computer. Quantum mechanics is deep magic that nobody really understands, but we have learnt a lot about how to use it during the last century–including its application to some kinds of computation. As you surely know, the most outstanding quantum algorithm is Shor’s prime factorization, which allows factoring a number N with a time complexity $O({(\log N)}^3)$ . That means that we go from exponential to polynomial time when going from classical to quantum for this particular problem (and related ones: the Wikipedia article on QC gives a pretty good survey; see also David Deutsch’s introductory lectures). I’m stressing the last point because there’s a widespread misconception that quantum computers will be able to solve NP-complete problems in polynomial time. Not so. On the contrary, experts are almost sure by now that this won’t be the case (note, by the way, that factoring is not NP-complete).

The most recent examples of such bogus claims are the reports on D-wave’ demos of their ‘quantum computer’, which are surrounded by piles of hype. So please, before taking them at face value, see Scott Aaronson’s The Orion Quantum Computer Anti-Hype FAQ (more here here here). Scott Aaronson is an expert in the field and the author of a PhD thesis under the title Limits on Efficient Computation in the Physical World (for a less technical introduction to quantum computing, see his nice Quantum Computing Since Democritus lectures). For an executive summary, here’s the first entry in the FAQ:

Q: Thanks to D-Wave Systems — a startup company that’s been in the news lately for its soon-to-be-unveiled “Orion” quantum computer — is humanity now on the verge of being able to solve NP-complete problems in polynomial time?

A: No. We’re also not on the verge of being able to build perpetual-motion machines or travel faster than light.

The old rule applies: no silver bullet. But, of course, their limitations notwithstanding, quantum computers would (will?) be an interesting challenge for us programmers, and we do not have to wait for the hardware to play with them: see this Brief survey of quantum programming languages, or a more in-depth description of how an imperative quantum programming language looks like, although, if you ask me, functional quantum languages like QML are nicer. Simon Gay has also put together a comprehensive Bibliography of Quantum Programming Languages.

Finally, if you’d rather write some code, there’s André van Tonder’s Scheme simulator (which will work with any R5RS scheme), and a QML simulator written in Haskell. Haskellers will also enjoy Jerzy Karczmarczuk’s Structure and Interpretation of Quantum Mechanics: a functional framework.

Happy quantum hacking!

Posted in Haskell, Programming, Scheme. 4 Comments »

Assumptions

February 16, 2007 — jao

Please don’t assume Lisp is only useful for Animation and Graphics, AI, Bioinformatics, B2B and E-Commerce, Data Mining, EDA/Semiconductor applications, Expert Systems, Finance, Intelligent Agents, Knowledge Management, Mechanical CAD, Modeling and Simulation, Natural Language, Optimization, Research, Risk Analysis, Scheduling, Telecom, and Web Authoring just because these are the only things they happened to list.

Ken Pitman

Posted in Lisp. Leave a Comment »

Getting Lisp

February 12, 2007 — jao

I was re-reading fare‘s excellent What Makes Lisp Great, an awesome and insightful discussion of Lisp’s unique qualities (which, regretfully, didn’t take off on reddit, hence this post). I took the time to read the comments and enjoy the author’s answers. And there i found this little gem on how Greg Trasuk finally gets Lisp. If you’re a lisper, you probably knew about it already; but if you really need a little push to start learning Lisp, that may be it. Of course, Faré’s article should make for a great one. While you’re at it, be sure to read some of his other great articles on Lisp:

(as selected by himself). Great stuff.

Posted in Common Lisp, Lisp, Scheme. 1 Comment »

Reinventing programming

February 12, 2007 — jao

Alan Kay hardly needs a presentation, so i won’t waste your time before pointing out to his latest interview, where he talks with Allan E. Alter about the current computing landscape. As you may expect from a visionary such as Kay, he is not exactly happy with what he sees, and is currently working in his Viewpoints Research Institute to try and invent the future of programming. Besides his involvement in the “One Laptop per Child” project, Kay and coworkers have recently been awarded a NFS grant to develop their ideas on how a better programming platform should be. If you’re curious (and who would not!), you can read some of the details of their amazing plans in the proposal they submitted to the NFS: Steps Towards the Reinvention of Programming. This proposal for the future starts by trying to recover the best from the past, particularly the seemingly forgotten ideas of another visionary, Doug Engelbart. As Kay rightly points out during the interview,

[Most of those ideas] were written down 40 years ago by Engelbart. But in the last few years I’ve been asking computer scientists and programmers whether they’ve ever typed E-N-G-E-L-B-A-R-T into Google-and none of them have. I don’t think you could find a physicist who has not gone back and tried to find out what Newton actually did. It’s unimaginable. Yet the computing profession acts as if there isn’t anything to learn from the past, so most people haven’t gone back and referenced what Engelbart thought.

The reinventing programming project tries to change this situation with some interesting proposals. Their envisioned system would put forward the lessons drawn from Squeak and Etoys towards the creation of a fully introspective environment which can be understood completely by its users; actually, a system which guides programmers to full disclosure of its innards. In Kay and coworkers’ words:

This anticipates one of the 21st century destinies for personal computing: a real computer literacy that is analogous to the reading and writing fluencies of print literacy, where all users will be able to understand and make ideas from dynamic computer representations. This will require a new approach to programming. [...] This will eventually require this system to go beyond being reflective to being introspective via a self-ontology. This can be done gradually without interfering with the rest of the implementation.

So, simplicity is key, and they purport to write such a system in a mere 20K LOC. To that end, they propose a sort of great unification theory of particles (homogeneous, extensible objects) and fields (the messages exchanged by myriad objects)—well, yes, it’s just a metaphor, but you can see it in action in the paper, applied to images and animations. The report also explains how the physical metaphor is completed with a proper simulation of the concept of time. As for introspection, inspiration comes, quite naturally, from Lisp:

What was wonderful about this [John McCarthy's] approach is that it was incredibly powerful and wide-ranging, yet was tiny, and only had one or two points of failure which would cause all of it to “fail fast” if the reasoning was faulty. Or, if the reasoning was OK, then the result would be a very quick whole system of great expressive power. (John’s reasoning was OK.) In the early 70s two of us used this approach to get the first version of Smalltalk going in just a few weeks: one of us did what John did, but with objects, and the other did what Steve Russell did. The result was a new powerful wide-ranging programming language and system seemingly by magic.

Lest anyone thinks that all of this is just a loosely knitted bag of metaphors and wishful thinking, the report gives some technical detail on an actual implementation of some of these ideas. Albert is a bootstrapper that is able in a few hundreds of lines of code to make a kernel for Squeak that runs nine times faster than existing interpreters. The bootstrap process looks fascinating:

A disposable compiler (written in C++) implements a simple message-passing object-oriented language in which a specification-based Object compiler (implementing the same language) is implemented. The system is now self-implementing but still static. A dynamic expression compiler/evaluator is then implemented using the static compiler and used to replace the static messaging mechanisms with dynamic equivalents. The system is now self-describing and dynamic hence pervasively late-bound: its entire implementation is visible to, and dynamically modifiable by, the end user.

Again, the proposal gives a bit more detail, but i’m not sure i’m understanding it fully: if anyone knows if/where Albert’s code is available, please chime in!

Not that i agree 100% with all the ideas in the report (and, as i said, there’re quite a few i don’t fully grasp), and i’m sure most of you won’t agree with everything either. But it’s definitely worth the effort reading, trying to understand and mulling over Alan Kay’s vision of the future of programming. He knows a bit about these things.

Update: Thanks to Glenn Ehrlich, who in a comment below provides links to learn more about Ian Piumarta’s Albert, also known as Cola/Coke/Pepsi.

Posted in Programming, Smalltalk. 6 Comments »

Scheme code capsule: currying

February 3, 2007 — jao

One of the few things i miss when programming in Scheme is ML-style function currying. ML, Haskell and OCaml come with this handy feature that allows you to obtain new functions from a given one by calling it with an ‘incomplete’ number of arguments.

Fortunately, we have macros in our programmable programming language, and actually there’re lots of them floating around providing implementations of currying in Lisp. But today, Piet Delport posted (during a discussion in #scheme) the nicest currying macro i’ve seen so far:

(define-syntax curried
  (syntax-rules ()
    ((curried () body ...) (lambda () body ...))
    ((curried (arg) body ...) (lambda (arg) body ...))
    ((curried (arg args ...) body ...)
     (lambda (arg . rest)
       (let ((next (curried (args ...) body ...)))
         (if (null? rest)
             next
             (apply next rest)))))))

(define-syntax define-curried
  (syntax-rules ()
    ((define-curried (name args ...) body ...)
     (define name (curried (args ...) body ...)))))

;;;; Sample usage:

(define-curried (foo x y z) (+ x (/ y z))) ;; foo has arity 3
((foo 3) 1 2) ;; (foo 3) is a procedure with arity 2
((foo 3 1) 2) ;; (foo 3 2) is a procedure with arity 1

This code shows the elegance and power of hygienic syntax-rules macros, which allow you to extend the language seamlessly, incorporating new features as if they were native. It also makes for a pretty instructive demonstration of how to take advantage of higher-order functions and recursion, nicely combined. All that in just a few lines!

If you’re new to Scheme and want to learn more about similar magic, be sure to read JRM’s syntax-rules Primer for the Merely Eccentric. You’ll have a great time.

Posted in Scheme. 9 Comments »

Five Tidbits You Didn’t Know About Me

February 2, 2007 — jao

Arto Bendiken has kindly transfered me the right to bore you with five things you might not know about me:

I smoke pipes since i was fifteen, when i bought my first one out of admiration for my literary heroes Sherlock Holmes and Gandalf the Grey.
Despite being a Spaniard, i strongly disapprove bullfighting (as many other Spanish people, by the way); and i dislike flamenco: give me a good jam session any day.
I write non-publishable poetry and short fiction, and still dream of publishing a novel when i’m sixty-four.
I wanted to be a basketball player, but had to quit due to height problems. Afterwards, i tried my hand at a high-school choir: after five minutes hearing me singing, the conductor raised her eyes to the ceiling, shook her head and muttered: “this boy won’t be able to sing.” Time has proved her correct.
I own a copy of Effective C++, 3rd Edition–and have read it.

According to the rules of this infectious meme, i hereby nominate Bill Clementson, Francesc Xavier Noria, Oliver Ansaldi, Ted Dziuba and Steve Jobs as the next rungs of the ladder, and i must warn all of them that, should they decide to break this chain, nothing whatsoever will befall on their heads.

Posted in Programming. 1 Comment »

Scheme or Common Lisp?

February 1, 2007 — jao

A sure way to start a flamebait in any Lisp forum is to ask what’s better, Scheme or Common Lisp, or, as a poster did today at comp.lang.scheme, whether Scheme is geared towards academics and CL to real world applications. Fortunately, one can always count on the good sense of lispers like Ray “Bear” Dillinger, who answered with this long, informed and very interesting post: recommended reading.

(To me, the answer is crystal-clear: both.)

Posted in Common Lisp, Lisp, Scheme. Leave a Comment »

programming musings

Reading