Wednesday, March 09, 2005


Fun With Lisp

I have occasionally played with Lisp and Scheme in the past, but never long enough to get a good feel for the language. Lately, however, I have spent a significant amount of time working with Lisp and I am really beginning to appreciate the beauty of the language.

I have started a web page for Lisp stuff where I will put some of the interesting things I come up with. So far, it has an implementation of the Fibonacci Heap, which I can tell you is a bear to implement. I also have an implementation of Dijkstra's Shortest Path algorithm and some code to parse Tiger/Line files.

Why do I think Lisp is cool?

First of all, the syntax is extremely simple. Yes, there are a lot of parentheses, but I think the reason that they stand out so much is that, apart from quotes, there's not a lot of punctuation required. You don't have to end statements with a semi-colon, or put commas between list items, or put curly braces around statements. It is simple and direct.

First class functions are really cool, as well. Although they are not unique to Lisp, first class functions are not found in Java, which is my current day-job-language. By saying a function is "first class", it means that a function has the same status as other data items. You can pass a function as a parameter to another function. You can store functions in other data structures. You could, for example, iterate over a list and apply each function in the list to a particular piece of data. This would make it easier to apply business rules, for example. You can do this in Java with Interfaces, it's just a bit easier in Lisp.

There are lots of functions for dealing with data structures. For all the different containers that Java has, it really falls down on the job when it comes to actually using them. One of the things that always impressed me about Smalltalk was the things you could do with containers (Ruby has this as well, and Python's list comprehensions are close enough). In Lisp, for example, there is the (map) function, which in its simple form is just like iterating through a list with a for loop.
For example:

(mapc #'print '(1 2 3 4 5 6 7))
loops through a list and calls the (print) function for each item in the list. There are numerous (map) functions, some return no result, some return a list of the result of applying the function. Where the (map) functions excel beyond a simple loop, however, is that it can use multiple lists and invoke functions that take more than one argument. A simple example would be adding together corresponding elements in two lists:

(mapcar #'+ '(1 2 3 4 5) '(6 7 8 9 10))
which returns the list
(7 9 11 13 15).

There are other cool things, one last one I'd like to mention is that a Lisp environment tends to be highly interactive. You can write some functions and immediately interact with them from a Lisp prompt.

i like the examples you gave. that gives me a much better idea of some of the powerful features that lisp provides. what tools are you using to edit/compile?
The Lisp implementation I am using is SBCL. It can compile to native code. My IDE is Emacs, with a package called SLIME (Superior Lisp Interaction Mode for Emacs).

Slime provides some handy features, one of which is that it can show expected function parameters on the status bar. It's like the drop-down menus you get in Java/.Net IDEs, but less intrusive. It also has completion with c-c TAB. Being a vi user for 21 years, it has been difficult retraining myself to use EMACS, but it is starting to grow on me.
Hi Mark,

Michael mentioned your blog and pro-Lisp ranting to me. I'm practically a static-typing bigot, not tempered much by years of experience with dynamically-typed languages (including both Lisp and Smalltalk), so I just had to come visit. Maybe I can convince you to convert to the light side where you can embrace our world of F-bounded parametric polymorphism? ;)

In general, I'd like to point out that the same advantages you speak of are available in more sophisticated statically-typed functional languages, like Nice. Here's an example of an anonymous function in Nice:

set.foreach(int i => println(i));

God bless,
Oh, I also forgot to mention that it looks like Nice is getting an interpreter, so it would also have the same kind of interactivity as most Lisp environments.

God bless,
Thanks for mentioning Nice, Toby. Mike mentioned it at lunch the other day as well. I didn't realize that it appears to have first-class functions.

Looking at some of the code on the web site, I have to say that my first reaction was "Gaaah! It's C++ returned from the grave!" Then I calmed down. Nice seems to improve on some of the shortcomings of Java. I've been reading a bit on Haskell and OCaml as well, and they also show that you can still get a lot done in a statically-typed language.

The interactivity is really more than whether there is an interpreter, though. I'm speaking more about Java here. There are several really nice shells for Java that let you interact with objects. I have used BeanShell to interactively test my Java objects.

When you start using these big frameworks and you have classes that really can't operate on their own, an interactive shell won't help too much. A less-intrusive framework that lets you work with POJOs (Plain Old Java Objects, for any non-Java people out there) helps tremendously. I wonder sometimes if the presence of all these annotation languages and code generators might indicate that Java isn't flexible enough on its own.

Jumping back to static typing for a minute, I know there has been a lot more debate about it recently. One of the points that several people have brought up (Bruce Eckel & Robert Martin, for example) is that static typing helps you eliminate errors where you use the wrong type somewhere. If you are thoroughly testing your code, those errors should shake out anyway. If they don't, it might indicate that you aren't testing well enough. That sounds good in theory, at least.
Mike mentioned it at lunch the other day as well.

/me cackles - My sphere of influence is spreading... ;)

"Gaaah! It's C++ returned from the grave!"

How is that? The parametric polymorphism or free functions? These are good things.

I've been reading a bit on Haskell and OCaml as well,

Haskell is a favorite of researchers in terms of applying new static-typing capabilities to languages. I hear Haskell is also a favorite as a base for DSLs.

A less-intrusive framework that lets you work with POJOs

I'm having a hard time getting a handle on what you're talking about here... J2EE maybe? I'm really not sure how that affects what code snippets you're going to write in a transcript window. As a side note, I prefer working with "POJOs" myself, which is why I prefer JDO for persistence.

I wonder sometimes if the presence of all these annotation

Annotations together with APT and bytecode rewriting are a compromise in the face of macros. The Java language designers will probably never add macros (I'm speaking in the sense of hygienic macros like Scheme), because they're not convinced that the benefits of being able to syntactically warp the language are worth the disadvantages. It's similar to why operator overloading doesn't exist in Java. Anyway, annotations/APT/bytecode-rewriting get you most of the functionality you'd get out of macros without the language bending side-effects. What I'm looking forward to is an implementation of APT that allows you to write first-class compiler plugins. It would be much simpler than bytecode-rewriting, and also more powerful in some ways too.

If you are thoroughly testing your code, those errors should shake out anyway.

(I'm aware of Eckel. He quoted me on Java Generics)

Here we go. ;)

I assume you've heard about all of the effort that has been poured into language research to implement proof-solving compilers? Static compilers are proof solvers. When I compile my program, I am proving the type-correctness of my system. I can't imagine having to replace a proof of correctness with an infinite set of manually written tests to come to the same conclusion. Even the normal, limited, application of test-cases involves writing a significant body of code which is potentially erroneous in and of itself.

My personal experience is that types are less useful when programs and teams are reasonably small. As either of those factors increase, typing becomes more and more useful. It becomes impossible for everyone to keep everything in their heads. A typical counter-response is that comments and documentation can be written to expound on the appropriate values to supply to a function - yet, in the real world, comments and documentation are always out of synch with code. Types are always in synch. Another counter-argument is that test-cases themselves can serve as this documentation, but I've already explained why test-cases are an inadequate substitute.

You might want to do a search through LTU for static vs. dynamic typing. Frank Atanassow, makes some very reasoned arguments in favor of static typing. Some other folks also make some interesting arguments for dynamic typing. My personal opinion is that, "in the end", static typing is going to win out, and features which are typically found in dynamically-typed languages are going to work their way into statically-typed languages. For example, for statically-typed languages, we already see type-inference, interpreters, dynamic code loading / redefinition, and introspection/reflection.

God bless,
Toby, thanks for your insight. I have read some of your comments on as well and you are very good at getting your point across without being a jerk. That seems rare these days.

I'm having a hard time getting a handle on what you're talking about here... J2EE maybe? I'm really not sure how that affects what code snippets you're going to write in a transcript window. As a side note, I prefer working with "POJOs" myself, which is why I prefer JDO for persistence.
Yes, I was speaking about J2EE. A lot of the projects I have worked on use EJB and rely heavily on XDoclet to generate additional classes and such. My comment was born out of the frustration of not being able to interact with those classes directly. It seems like some of the newer frameworks are more Pojo-oriented.

I think that I tend to agree with you with respect to static typing and larger projects. The appeal of dynamic typing is that you don't waste time with all these extra declarations about types. For a small program, expecially a throw-away, that trade-off is reasonable. For code that may be used for a long time, by many teams, the time you spend writing type declarations is no longer a waste.

If I need to process a file quickly, it's hard to beat Python's:
for line in file("foobar.txt"):

The more I look at Nice, the cooler it looks. The nullable option thing looks a little odd to me. I've never been that fond of character annotations on variable names, especially at the beginning. That's more of a nit, though. I was also surprised at the lack of explicit casting, but it looks like an interesting solution.

As far as contracts go, I see pre & post conditions, are invariants not useful? Eiffel has them and I always thought they were an interesting idea, but wondered how practical they are to implement.

As I was writing this, it occurred to me that it would be easy in Nice to write a function to do the equivalent of Python's "for line in file('xx'):". I'm definitely going to have to play with this language some more.
Post a Comment

<< Home

This page is powered by Blogger. Isn't yours?