Getting Lisp

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.

Scheme code capsule: currying

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 »

Scheme or Common Lisp?

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.)

A Scheme bookshelf

It all began while i was using MDK‘s development as an excuse to learn everything i could about programming and programming tools: makefiles, autoconf, automake, localization, texinfo docs, lexers, parsers… and, eventually, extensibility. I kept hearing about an exotic thing by the name of GNU’s Ubiquitous Intelligent Language for Extensions, and, finally, rose to the bait. But my first attempts at writing Scheme felt awkward. Not because of the parens (i liked Scheme syntax from day zero), but basically because i was writing C code using Scheme. Clearly, i needed to read a bit about this new thing and, to that end, i got a copy of The Little Schemer… to no avail: i didn’t get what elephants, food and Socrates had to do with programming; i still felt awkward. (It was not the book’s fault, mind you, but mine. More about this in a bit.)

Then i found the book. Abelson and Sussman’s Structure and Interpretation of Computer Programs changed my life as a programmer. I’m sure you’ve read lots of praise for this book. Totally deserved! SICP is not really about Scheme, but about thinking about programming. Reading it will make you a better programmer in any language. It will expand your mind. It will cure your diseases. It’s really that good. Besides, SICP is freely available in HTML, PDF and texinfo formats, so you really have no excuse. For extra fun, get the accompanying video lectures, by Abelson and Sussman themselves. These lectures are charming: these guys have a passion for what they do, and they transmit it from the very beginning, when Abelson jokingly explains why computer science is neither a science nor about computers.

Concrete AbstractionsThe most cited alternative to SICP is How to Design Programs by Felleisen, Findler, Flatt and Krishnamurthi. Its authors have even published a rationale, The Structure and Interpretation of the Computer Science Curriculum, on why they think SICP is not well suited to teaching programming and how their book tries to fix the problems they’ve observed. I won’t try to argue against such eminent schemers, but, frankly, my feeling is that HtDP is a far, far cry from SICP. HtDP almost made me yawn, and there’s no magic to be seen. If for whatever reason SICP is not your cup of tea, i would recommend Max Hailperin‘s Concrete Abstractions as a far better (as in more fun than HtDP) alternative.

With SICP under my belt, i was ready for The Little Schemer and The Seasoned Schemer(by Daniel P. Friedman and Matthias Felleisen), which i read in a row. You’d be hard pressed to find any programming book similar to the Schemers books. As in my case, the initial reaction may well be of rejection: on a superficial reading they look too queer, even childish, and by any means the kind of book a serious programmer should read, except maybe for fun. But that’s precisely the point: you won’t learn unless it is for fun! If you enter the game proposed by Daniel and Matthias, accepting to participate in their Socratic scheme, you’ll learn a lot with their books. I found easier to put me in the right mood after SICP because it also is imbued of a kind of magic, and also because i was much better equipped to capture the subtleties lurking in every page of the Schemers books. Besides having a great time, one ends up with a sound grasp of higher order functions, recursion (including the Y combinator) and continuations. In fact, it was reading The Seasoned Schemer that something clicked and i really understood continuations.

After all these readings i felt i was starting to have a good grasp of the conceptual underpinnings of Scheme and Lisp, and that it was due time to strengthen the technical details. Or in other words, i wanted to come to grips with the nitty gritty details of Scheme syntax and semantics, including macros (which i knew from some tutorials and readings on Common Lisp). To that end, Dybvig‘s The Scheme Programming Language was the perfect book. Comprehensible, exacting and with an elegant prose, and to the point. But, despite its succinctness, Dybvig does an excellent job in conveying the details of the language and its usage. The book also includes extended usage examples for a good measure. Thus, TSPL works nicely as both a tutorial and a handy reference.

If you already have a good basis on functional programming you can use TSPL as your first Scheme book and skip the previous ones (but you will be skipping lots of fun and, maybe, insight too). And if you happen to read French, an interesting alternative for a speedier learning path is Jacques Chazarain’a Programmer avec Scheme. In the first part of the book, Practical programming with Scheme, Scheme is thoroughly presented, using it in many examples taken from the standard data structures and algorithms curriculum. Taking this practical basis as a starting point, Chazarain proceeds to a comprehensive (almost 400 pages long) discussion of the formal basis of the theory of programming languages: automata, lexers and parsers, propositional calculus, rewriting systems, logic programming, lambda calculus and more. As you can see, the scope of this book is amazing, and it’s well worth learning a little French!

The nice thing about learning a programming language in such a good company is that one learns much more than a single programming language. These books helped me obtain a conceptual basis for thinking about programming and programming languages in abstract terms, applicable to any programming problem. As Sussman colorfully demonstrates in one of the SICP lectures, one feels like beholding the heart of the spirit that lives in the machine. An that spirit, of course, is an interpreter. So i delved into the theory and practice of implementing interpreters guided by another classic: Essentials of Programming Languages by Daniel P. Friedman, Mitchell Wand, and Christopher T. Haynes. This marvelous book delves deep into the art of writing interpreters using Scheme as the implementation language. By way of running example, an interpreter for an ML-like language is developed all along, showing the magic of, among other things, register machines or continuation-passing style. To get a flavor of what this book has to offer, i wholeheartedly recommend reading Friedman’s The Role of the Study of Programming Languages in the Education of a Programmer, an insightful talk on how a theoretical background is useful (and even needed) to any programmer in any language, which Friedman illustrates with practical cases taken from his book.

Sussman the magicianOne of the rites of passage of any self-deserving schemer is writing a metacircular scheme interpreter, that is, a scheme implemented in itself. Having a look at the innards of your language implementation sheds a whole new light on your daily usage of the language. Sussman goes as far as wearing his magician’s hat when he explains the metacircular interpreter in the SICP lectures, and rightly so. But i’ve always felt a bit frustrated by the fact that the implementations one finds in books like SICP, EOPL or, to cite another classical example, PAIP are actually for toy interpreters not covering all the details of real Schemes. And often the left out precisely the most interesting bits! Fortunately, there’s a book that will tell you everything you ever wanted to know about implementing Lisp interpreters and compilers: Lisp in Small Pieces by Christian Queinnec. This is easily the best book about Lisp i have ever read. LiSP shows, without omitting any details, how the family of Lisp languages is implemented (in interpreted and compiled forms). You’ll learn from the inside the difference between Lisp-1 and Lisp-2, how dynamical and lexical scope work, how blocks and continuations are related, how on earth one implements… everything you ever wanted to know about Lisp implementations, and then more. On top of that, Queinnec writing style is engaging and the book is pervaded by a fine sense of humour that made me laugh out loud several times. If you’re serious about Lisp, you must read this book.

Let me close my list of recommendations with the last addition to my Scheme bookshelf, namely, the third schemer installment: The Reasoned Schemer (by Daniel P. Friedman, William E. Byrd, Oleg Kiselyov). Paraphrasing Alan Perlis, the key reason for learning new languages and paradigms is the fact that they, hopefully, change the way you think about programming. Functional languages do a pretty good job at that, but they’re not the only game in town. Declarative programming is definitely another mind blowing experience, which you can enjoy reading The Reasoned Schemer. The book presents, in that peculiar style of its predecessors that i like so much, the basis of logic programming using a Scheme implementation that, in many ways, surpasses standard declarative languages like Prolog. The best of two awesome worlds, and an excellent way to ensure that you keep learning and expanding your programming horizons.

Happy reading!

The Lord of the Lambdas

Data and procedures and the values they amass,
Higher-order functions to combine and mix and match,
Objects with their local state, the messages they pass,
A property, a package, the control point for a catch–
In the Lambda Order they are all first-class.
One Thing to name them all, One Thing to define them,
One Thing to place them in environments and bind them,
In the Lambda Order they are all first-class.

Abelson et al., The Revised Revised Report on Scheme
(Hat tip jcowan on #scheme)

The Road to Enlightenment

Arto Bendiken has just explained, in delicious detail, his Lisp experience in The Road to Enlightenment is Littered with Irritating, Superfluous Parentheses. He recalls his going from C and Basic, to Java, Python, Ruby and, finally, the light. A very interesting reading, with excellent links and references for a good measure. You’ll also find in there Arto’s solution to one of the conundrums we lispers face sooner or later: CL or Scheme?

Know your tools

Just to illustrate what i meant the other day when i exhorted you to pick a powerful enough editor, and, most importantly, learn how to use it, i think this Emacs Screencast is quite adequate. It’s made by a Ruby coder, but note that Emacs plays these kind of tricks (and many more) for virtually any language out there.

The point is, if your environment is not powerful enough to make this kind of things, you should be looking for something better. The keyword here is extensibility. If your environment is not able to automate a task, you should be able to extend it; and the best way i can imagine is having a full featured lisp at my disposal when i need to write an extension (here is the list of Emacs extensions used in the screencast, by the way). Phil Windley has also made a similar point recently, in his When you pick your tools, pick those that can build tools mini-article.

And of course, when your editor and your dynamic language conspire to provide an integrated environment, you’ve reached nirvana: that’s the case of Common Lisp and Slime, as shown in other widely known videos.

As said, the message is not that you should use Emacs, but that you should use the right tool. For instance, PLT Scheme users have other alternatives, like DrScheme, which can also be easily extended, as beautifully demonstrated by DivaScheme, an alternative set of key-bindings for DrScheme that you can see in action below:

You see, as programmers, we’re lucky: we can build our tools and make they work exactly the way we want. If your environment precludes your doing so in any way, something’s wrong with it, no matter how much eye-candy it uses to hide its deficiencies. (Yes, i have some examples in mind ;-) .)

Update: Phil has just posted an interesting follow-up to his tools article. His closing words nicely summarise what this post of mine is all about:

Note that I’m not writing all this to convert the dedicated vi users or anyone else. If you’ve got something that works for you, then good enough. But if you’re searching for a editor that’s programmable with plenty of headroom, then give emacs a try. There’s a steep learning curve, but the view is great from the top (or even half way up)!

Exactly!

Not your parents’ shell

The developers of scsh, the Scheme shell, have just released version 0.6.7 of their awesome Scheme implementation. Scsh is, in my opinion, simply the best scripting language around, by a long stretch. It was initially implemented by Olin Shivers on top of scheme48, as a result of his problems with traditional shell languages: he wrote a detailed rationale on the design principles behind scsh that is full of insight and a must read. In addition, this page is full of writings by Olin and other minds behind s48/scsh (like Michael Sperber or Martin Gasbichler) with interesting details on many aspects of scsh’s implementation.

CommanderDuring the last years, scsh has become, slowly but surely, my default scripting tool (emacs’ eshell is also fine, but, you know, elisp is not scheme), my only nit being its lack of a shell prompt powerful enough to fully replace zsh or bash. But, lo and behold, it seems the writing may be on the wall for my bash/zsh’s days: a beauty called Commander S is well underway. Commander S is an interactive frontend for scsh, based on the ncurses library, described in the workshop paper Commander S – The shell as a browser, by Gasbichler and Knauel. In the author’s words:

Commander S is a new approach to interactive Unix shells based on interpretation of command output and cursor-oriented terminal programs. The user can easily refer to the output of previous commands when composing new command lines or use interactive viewers to further explore the command results. Commander S is extensible by plug-ins for parsing command output and for viewing command results interactively. The included job control avoids garbling of the terminal by informing the user in a separate widget and running background processes in separate terminals. Commander S is also an interactive front-end to scsh, the Scheme Shell, and it closely integrates Scheme evaluation with command execution.

Although it’s not yet released, the brave and bold among you can already give it a try from its CVS repository.

(I wish i had time for Conjure: one of the features i had in mind was some sort of interactive build tasks inspector, and Commander S’s plug-ins look like an excellent implementation vehicle for such a thing. You’re not looking for a nifty scheme project, are you?)

Tags: , ,

A minsky machine to play with

Over at Good Math, Bad Math (a wonderful blog i wholeheartedly recommend), Mark Chu-Carroll has published a minsky machine to play with, implemented in Scheme. In case you’re wondering, Mark also explains what a minski machine is (and why they’re equivalent to Turing machines). Minski machines are sometimes called register machines: a bit more on them here and here.

For additional fun (if you feel like philosophizing a bit) see also this other kind of Minski machine.

Tags: ,

A Haskell bookshelf

My favourite scheme implementation is scheme48, which takes its name from its being initially implemented in 48 hours by Richard Kelsey and Jonathan Rees in August 1986. They used Common Lisp on a Symbolics 3600 and Maclisp on a PDP-10.

Now, thanks to Jonathan Tang’s tutorial, you can write yourself a scheme in 48 hours, but using Haskell instead of Lisp. The tutorial is intended as an introduction to Haskell for Schemers (and (brave) programmers in general) wanting to get started in the purest member of the functional family. And it is extremely fun, for instead of following the boring language features overview way, it plunges right on in interesting, hands-on stuff like parser combinators (one of the most beautiful applications of Haskell, if you ask me) or monads. The lessons include exercises, so that you have really no excuse for not learning Haskell once and for all. Believe me, it’s good for your (mental) health.

If you’re totally new to Haskell and find the pace of Jonathan’s tutorial a bit hard to follow, you may start with a tour of the Haskell syntax and the Hitchikers’ guide to Haskell, after making sure, of course, that you have your towel at hand. As for me, well i’ve been planning to learn Haskell for some years now and, since i happen to love books, i have accumulated a little (but selected) Haskell library, together with a sort of learning roadmap that, unfortunately, i have yet to complete. Just in case the above links whetted your appetite and you happen to have more time than i do, here you have my bookworm guide to Haskell enlightenment.

The little Haskeller

There are many introductory Haskell books, but i was (at the time i started learning) keen of those providing also a good basis on functional programming (which was a totally new world for me at the time). Therefore, my first Haskell book, and still a wholehearted recommendation, was Richard Bird and Philip Wadler‘s Introduction to Functional Programming Using Haskell, one of the most elegant books on programming i’ve ever read.

One of the nicest things about writing Haskell code is that it’s the closest one can probably get to writing pure maths while programming. Thus, learning Haskell is an excellent way to learn more about maths and logic. If that sounds to you like doubling the fun (and you’re not yet a math wizard), The Haskell Road to Logic, Maths and Programming (see also this extensive review (PDF)) by Jan van Eijck and Kees Doets is definitely the book for you. Its purpose is to teach logic and mathematical reasoning in practice, and to connect logical reasoning with Haskell programming. And, in my opinion, it does a pretty good job at that. Although it begins with the very basics, it includes chapters on far from trivial (i.e., fun!) stuff like, for instace, corecursion or Cantor sets. And i found amazing how natural it was to express logical and mathematical ideas in Haskell.

But maybe you prefer to learn a bit of applied Computer Science, instead of abstract maths, with Haskell. No problem: just grab a copy of Fethi Rabhi and Guy Lapalme‘s Algorithms, a functional programming approach, which challenges the academic establishment by teaching algorithms using Haskell, that is, in a purely functional context. Revisiting classical (and apparently imperative) algorithms like sorting, tree and graph traversal or dynamic programming methods under a functional light is a refresing experience, and an eye-opener: the fact that all the typical algorithms are covered in just 256 pages is a testament to the authors’ claim that functional programming leads to smaller, clearer and more elegant program. Besides, as you probably know, Haskell features lazy evaluation, which poses entirely new (and pretty instructive) challenges when it comes to evaluating the efficiency of an algorithm.

The seasoned haskeller

fopOnce you’re comfortable with the language and have learnt all about monads, the best thing to do is to study non-trivial Haskell applications. To that end, you can hardly find a better book than The fun of programming, a Festschrift celebrating Richard Bird’s sixtieth birthday. Including thirteen chapters by luminaries in the field, this book describes fun applications on such fun things as musical composition or graphical design, as well as covering advanced programming techniques such as data structures design, interpreters or optimization. Amazing.

I also own a copy of Paul Hudak‘s The Haskell School of Expression, which is often recommended as as Haskell primer. In my opinion, it goes too quickly into the nitty-gritty details of (music and multimedia) implementations to be a good first book, but it is probably a good second book on Haskell programming. But that’s just me: as you can read in the review above, some people have diverging opinions.

The fun never ends…

After all these readings, and a bit more about monads, you’ll begin to feel an expert, and may be interested in more advanced stuff. I’ve got a couple of books reserved for that moment. The first one is The Algebra of Programming, by Richard Bird and Oege de Moor, and its purpose, simply stated, is to show how to calculate programs algebraically using and old friend of ours: category theory, including the bananas that will be the main theme of my second post on these matters. There you’ll find and in-depth, abstract treatment of algorithmic strategies with an eye of correctness proofs. Although heavy on theory, there are interesting applications of this algebra of programming, like the conversion between binary and decimal numbers in TeX, the best way of drawing a cylinder in LaTeX or good data compression algorithms. A slight nuisance is that this book uses an old Haskell dialect (a precursor, actually) called Gopher, but the conversion to modern notation is pretty straightforward.
Finally, anyone serious about algorithms and data structures should read Chris Okasaki’s Purely Functional Data Structures, and amazing tour on advanced algorithimcs using functional programming languages, with source code in SML and Haskell. The exposition is extremely elegant and synthetic, and i’ve spent many, many hours immersed in its 220 pages (i can’t think of any other programming book with a better signal to noise ratio, really).

That’s it. I just hope that 48-hours days are invented any time soon. Happy reading!

Follow

Get every new post delivered to your Inbox.

Join 42 other followers