Tuesday, January 22, 2008

Thoughts on Lisp: Things that other languages should take from Lisp

Things I like about lisp that haven't crossed over into enough mainstream languages yet:

  1. "Bignum" support: language-integers are logical-integers, not fixed-width bitfields. In Scheme and Common Lisp, by default you can't overflow an integer --- the language will dynamically expand the size of the representation as necessary. This guarantees numerical correctness, at the cost of some performance.

    In Common Lisp, you can force your code to use fixed-size numbers (fixnums) for efficiency. I like this overall system: the default is automatically "correct", but you can turn the knob toward performance in critical regions. This helps avoid embarrassing explosions.

    Ruby and Python, by default, treat language-integers as logical-integers. Java, C, C++, and Perl don't; you have to go out of your way to use a bignum class. The rest of the numeric tower is also nice to have, but far less essential to basic correctness.

  2. Optional type declarations (Common Lisp.) CL allows, but does not require, type declarations. The compiler can use these declarations to improve the speed of compiled code, and you only have to put them in the critical regions to get the performance benefit. The compiler can also use type declarations to perform compile-time typechecking. (Sadly, it isn't required to do this.) I like being able to have a blend of static and dynamic typing in the same programming language. Both have their places.

  3. Proper (unbounded) tail-recursion (Scheme.) If the last statement of a function, F, calls another function, G, there is no need to save space for F on the stack. In Scheme, such tail-recursion really doesn't reserve space. This lets you write tail-recursive algorithms that go arbitrarily deep, without worrying about running out of memory. The Scheme standard requires this to work. In most other languages, the stack space gets saved anyhow, as the language specifications don't forbid it.

  4. Methods with multiple-dispatch (Common Lisp.) In most languages, when a method is invoked, the first argument to that method determines which of several implementations is actually run. In the Common Lisp Object System, any or all of the calling arguments may be used to select the method implementation. There's a lot I don't like about CLOS (perhaps I'll go on at length in some future post), but multiple dispatch is a very handy hammer to have in the toolbox.

  5. Some Lisp implementations are fast. Unlike Ruby, Python, Perl, PHP, and JavaScript, both Common Lisp and Scheme have good native compilers.

  6. Syntactic simplicity (Scheme.) This is a positive view of "syntactic poverty," which I said I don't like in I'm giving Scheme this exception here because it is widely used in teaching. Syntactic simplicity gets students writing code faster than if they're trying to handle a bunch of ideosyncractic syntactic rules. And student code is reliably write-once, read-never-again. Of course, even MIT seems to be replacing Scheme with Python in the undergraduate EECS curriculum. I'm inclined to bow to the wisdom of the practicing teachers on this one. Or perhaps Python is another incarnation of syntactic simplicity.

Coming up next: I'm going to give the Lisp series a break for awhile. I've got some robotics stories I've been meaning to write up forever. Maybe I'll get around to them finally.

15 comments:

Anonymous said...

arbitrarily large integers as standard? who cares?

optional typing? maybe, but its just not that compelling with concepts like .NET's anonymous types and sprinklings of type inference

Lisp is a fine sandbox for experimenting with new language ideas, but imho it is best to restrict the number of concepts easily available to the programmer by crystalizing the best in class ideas into language constructs

Anonymous said...

Anybody who gives a damn about correctness can see the value of making overflow go away.

Also, it's strange to see no mention of lisp's hairiest, most powerful, most compelling feature - macros.

Reggie Drake said...

Adding macros to a language is a hairy, dramatic decision. The points mentioned in the article are all nice, well-defined mechanisms with no serious drawbacks.

horia314 said...

"Lisp is a fine sandbox for experimenting with new language ideas, but imho it is best to restrict the number of concepts easily available to the programmer by crystalizing the best in class ideas into language constructs"

Imho this is a very dumb point-of-view. C++/Java/C#/Perl have so many things you need to remember that it's a wonder students can learn them at all. And I'm not speaking out of my a** here. I've been trying to teach my girlfriend C++ (for a university course). She knew some things (could do simple algorithms and knew some C syntax). Well - C++ almost totally put her off programming. All the little things you've got to remember and all the ways in which they don't make sense - and frankly I don't blame her. Every big language is ugly in this way. On the other hand I showed her some Python, and she took to it right from the start.

And I ask you - what's harder to learn for a novice programmer :

Lisp :

this is a list : (1 3 4 (4 5))
this is a function application : (+ 1 3 4 (* 5 6))

Now go program

C/C++ :

first we must include ... and make sure we've set that and that correctly ...

Sorry for the long post, but everyone who thinks that C++ and it's ilk are crystallized or in anyway resembling perfection are "not even wrong".

Anonymous said...

I am using ruby most of the time, but even I must say I see more advantages to python being taught in classes than Scheme/lisp, simply because with python you get to do the job at hand done faster.

I wonder if the lisp guys deny this? (But to make it known, they should teach ruby ;> )

The argument for speed is a little bit overrated, computers will only get faster and faster, and people who need every speed they can get will use assembler/C/C++ anyway.

Jeremy said...

anonymous #1: after pointer errors, integer overflow is the next-biggest generic kicker-of-puppies in C/C++.

.NET's anonymous types are orthogonal to optional type declarations in, say, function parameter lists. And while type inference can be helpful, it still needs hints to get started.

anonymous #2: in an earlier post, I said "I'm still conflicted about Lisp's structured macros --- that's for a later post". I haven't gotten to that post yet. If and when I do, it will be called "Growing a language... badly," and will riff shamelessly on Steele's talk/paper, Growing a language. (Even though his paper wasn't about macros --- that's how shameless the riffing will be!)

reggie: Amen on macros, and thanks for your kind evaluation of the other points.

horia314: I totally agree that C++/Java/C#/Perl have become enormous languages. That said, Common Lisp is at least as large, albeit along different axes. eval-when, the mutability of the reader, the single namespace for all the core symbols, CLOS (my God, CLOS)... Lisp is not an intrinsic panacea of simplicity.

anonymous #3: I went through the MIT undergrad curriculum many years ago. At that time, in 6.001 we would start with this very small language, Scheme, and learn not only to use the language to achieve tasks, but also how the language itself worked. And for that, a smaller language was probably better.

In the textbook for this sophomore-level class, there are sections on interpreters, compilers, garbage collectors, etc. The focus in the new class seems to be more on systems --- build robots, etc. --- but I hope they've moved the language-introspective stuff to another required module somewhere.


Thank you all for reading and commenting!

kk said...

I agree.

In all PHP's utter suckyness I came to like class hints. I can have loose typing when I don't care, and require precise type in code that is not allowed to fail.

Anonymous said...

The condition system! It’s sadly overlooked. When I first learned about it I was like “OMFG you can DO that?” It’s exceptions done right.

ddickison said...

I'm gonna have to agree with anonymous that Common LIsp's condition system deserves to be on the list, if not right at the very top. restart-case and handler-bind are terribly useful, make for clear code and seems extremely difficult to do in other languages.

Anonymous said...

@horia314:

I agree that C/C++ are not great languages for novice programmers. To me, the best get-their-feet-wet programming languages are the ones that read most like human language, with the minimum of punctuation and funky-looking syntax, which scare people off. IMHO, the top two would be Smalltalk and, dare I say it, BASIC. Smalltalk has cleaner syntax than BASIC, but it's not exactly a front-burner programming language anymore, while VB.NET and VBA are still relatively mainstream.

Conversely, anyone suggesting novice programmers should learn LISP desperately needs to have his or her head examined. Not that LISP is a bad language, just not one for novices. It's non-intuitive for people used to reading instruction manuals for MP3 players, recipes for chicken cacciatore, or other non-programming sorts of directions.

Of course, I may be biased. I've been programming for nearly three decades (and get off my lawn!), in assembler, FORTRAN, BASIC, Pascal, Forth, C, C++, Smalltalk, VB/VBA, Java, Javascript, bash, Ruby...and LISP (albeit 22+ years ago). Plus some languages I'm probably forgetting about. And I have no frakkin' clue what those two lines of LISP code you had in your comment do. I'm guessing the latter one is a Polish Notation mathematical expression of some form...

Zak said...

@Anon #3 - I'm a Lisp guy, but I also use Ruby quite a bit. Ruby is better for one-liners and as a substitute for shell scripts. The standard library has a lot to do with that, but I think the richer syntax is better suited to it as well.

For anything bigger than a script, I'll take Common Lisp and not look back. Macros and multiple-dispatch are the main features I miss with Ruby. For Python, I think you can add first-class symbols and proper lambdas to that list.

Jeremy said...

I left the condition system off for much the same reason that I left dynamically-scoped ("special") variables off. Basically, I don't like code behavior to vary based on implicit state from somewhere up the call stack.

The better approach is to use the Strategy design pattern. For Siebel's example, for instance, you might pass a recovery Strategy function to PARSE-LOG-FILE. Or you might make LOG-FILE an actual object, and pass the strategy to the constructor.

Either Strategy-based approach allows you work on multiple logfiles at once, each treating bogus log entries according to a distinct strategy, without having to establish a new dynamic restart scope each time you read from one or the other.

Anonymous said...

Yeah! Greenspun those other languages up!

:-)

Jeremy said...

Better the language than every program written in it, eh?

Robert said...

I think that people should learn Scheme precisely for the reason that @horia314 s aid they shouldn't:


Conversely, anyone suggesting novice programmers should learn LISP desperately needs to have his or her head examined. Not that LISP is a bad language, just not one for novices. It's non-intuitive for people used to reading instruction manuals for MP3 players, recipes for chicken cacciatore, or other non-programming sorts of directions.


By now beginners already will know how to do ordinary procedural programming. Beginners should be taught something new --- functional and recursive programming. Why? Because recursion is absolutely critical to understanding computer science --- you can't do formal languages, theory, algorithms, etc. without it --- and it's hard.

I can tell you, if you have a room full of CS seniors that you are trying to get through theory of computation, it's really bad when you realize that even as seniors, they don't get recursion, because they've been doing Java and C all the way through.

I don't know enough to know whether Python will do this as well as Scheme.