Lambda the Ultimate

This anti-MS sniping is getting pretty old--I personally have considerable respect for Don Box's work, and I doubt you are going to earn cool points by making snide remarks at his expense. If you'd been reading LtU for a while, you would remember a not-too-old article linking to Don's blog, in which he talks about his decision to teach his children Scheme (I think he's been using DrScheme).

As an FYI: this was part of Don's column in MSDN magazine. People who subscribe to this magazine are already working with .NET and other Microsoft technologies professionally. I think it's cute that Scheme makes a cameo appearance in Don's column and I find no need to assign sinister ulterior motives to anything here.

Whose evil plan is more likely to succeed? I predict that Scheme will slowly but surely subvert all those buttoned-down .NET developers, and more importantly, their managers. Muahaha!

Perhaps the last paragraph was just a little disclaimer automatically generated by a script for all pages there?

I'm sure he has good reasons to teach his children Scheme. But i doubt Scheme would've been mentioned wasn't it for .NET support of late for functional programming constructs.

It's the timing that's a little suspect...

M$ have indeed bought many bright minds and it's good they're finally making some good use for such an asset.

Do a little bit of research first. Look at what you find, disagree with some of it, then ask good questions about the syntax, or macros, or typing.

Asking questions like "Lisp is teh sukc; COBOL rules! WTF?" is annoying. I'm sure people will be much happier to answer your questions if you meet tham half (or even a tenth) of the way.

Also, there are links to the left just for this purpose.

If you do a search, you can also see that there are also numerous similar threads on this site (Why FP? What's good/bad about Scheme/Lisp) etc.

As far as Lisp advocates go, the most famous one is Paul Graham.

As far as Lisp advocates go, the most famous one is Paul Graham.

And for people who are mildly skeptical to begin with, perhaps not the first source of information one should turn to. Even for Lisp fans like myself, Graham's rhetorical style can be extremely grating.

I personally think "Structure and Interpretation of Computer Programs" is the most beautiful introduction to a Lisp dialect ever written. I'd recommend starting there.

...and let me start off by pointing out that Lisp isn't for everyone. However, I have loved Lisp deeply ever since being introduced to it in high school and having had the benefit of spending time in Lindley Hall at Indiana University, chatting up Douglas Hofstadter and Dan Friedman.

"Why Lisp" depends an awful lot upon to whom you talk. One possible answer is "because some dialects of Lisp get you really close to the most fundamental notions of what computation is," in which case Scheme is an excellent dialect, The Little Schemer is an excellent introduction, and Structure and Interpretation of Computer Programs is an even larger mind-expander.

At the other end of the spectrum, some folks appreciate having a built-in programmable parser, extraordinarily flexible object system, just about every data type you can shake a stick at, and even, if you care to use it, built-in support for formatting numbers as Roman numerals. That would be Common Lisp, and the best introduction to it that I know of is Practical Common Lisp.

For some folks, Lisp's support for macros is the biggest selling point. In this case, either Scheme or Common Lisp will do. I don't have a lot more to say about this, basically because I disagree with the premise.

Both Scheme and Common Lisp have good free-as-in-beer and free-as-in-speech implementations. My favorites are DrScheme and Steel Bank Common Lisp.

I am a Scheme man myself, but if you want to learn about Lisp itself, I second the recommendation of Practical Common Lisp. I plan on writing a review, but for the time being, let me just say that the book is well written, practical and fun to read.

It's hard to know where you're coming from, so it's hard to suggest appropriate starting points. However, I can tell you that one of the most exciting and eye-opening experiences for me was watching the SICP video lectures from Abelson and Sussman.

The contemporary viewer may be tempted to view these as backwards, seeing as how they wear 1980's clothes and use 1980's syntax. But there are deep ideas in there that, while they may go in or out of fashion, are no less fundamental today than they were then. Some of these ideas, I believe, are better laid out in HtDP and PLAI, but nonetheless I was first introduced to them via SICP.

I was raised with a view of CS as having a kind of natural progress that inevitably culminated in the current popular technology. In fact, to a large degree, many of the existing technologies are more a product of fashion and historical accident than technical superiority. Keep an open mind, don't believe everything you've been taught, and to quote my research group's motto, always question your assumptions.

I'm mainly replying to let you know that Structure and Interpretation of Computer Programs, mentioned by Mr. Snively above, is also available for free online, in case you don't want to pay for something you are already hostile towards. (I actually bought it, discovered my copy was missing 40 pages out of the middle, then sent it back and used the online one.)

You should really check it out. If you know computer science, it won't all be new ground of course, but some of it blew my mind. (Also you should know that SICP deliberately limits itself to a small subset of an already small language. For learning the rest of the Scheme language, R5RS, the current Scheme "standard", is available and is very readable. And there's the SRFIs also.)

If you get more specific about what doesn't click with you and Lisp people could help you more. Right now you come off slightly trollish (Lisp is "useless"? That's an odd claim; I'm certainly very productive with it...).

Lisp ignores levels of abstraction you typically find in compiler design, and some people find that pleasantly endearing.

Also, Lisp is dead-simple to implement. (Due to the above point.)

Gamedev.net used to have some interesting threads on Lisp. One of the longer ones is Lisp is King which begins with some advocates cheerleading Lisp, and then some people in your position asking questions. Two years after the first post to that thread, several people who were asking the "why Lisp?" questions are some of the biggest fans of Lisp over at Gamedev.net's forums.

I really was quite serious... I respect that intelligent people really like this family (correctly pointed out) of languages, but my experience with it was so negative that I don't understand why, and I'm interested in broadening my perspective on it.

As a small bit of background, I've been programming since the age of 11, starting on the Apple ][+, even writing 6502 Assembly back then. I've done a lot in the intervening 24 years: Pascal, COBOL, 370 Assembly, REXX, T-SQL, C, C++, VB, VB.NET, C#, 80x86 Assembly (to name a few), lots of sysadmin work on all platforms, and tons of DBA work. I'm currently most familiar with the .NET platform, and part of the reason I'm back poking around with this stuff is because I'm very impressed with the work that Don Box and Anders Hejlsberg have done with LINQ and C# 3.0, and the use of expression trees and lambda expressions within all of that led me here.

By the time I was introduced to Lisp, I was familiar with one form of Assembly, and with a few third-generation languages, and so the fact that Lisp required recursion, and gave nothing in the way of higher-level constructs, just left me feeling that it was forcing me into a highly unnatural state-of-mind to understand how to construct my programs. Why must I always be thinking backwards just to do a loop? Why must I define a function to do things that (to my mind) "ought to be" in any higher-level language than the Assembly that mapped to a particular CPU?

With all of that said, I'll also point out that Lisp was CIS 101 at my university in 1987, and poorly taught at that. Perhaps that had something to do with my dislike for it, or perhaps I'm just not wired correctly for it, and never will be. Anyway, it's probably time to take another look at it, to see what I can learn from it now.

Again, I really appreciate everyone's comments and information, and I will dig into all of it in the next few weeks to see what it can teach me.

Thanks,
Scott

If you're looking for the access panels to the bare metal in Lisp, you aren't going to find them. If you write code and compile it to assembler in your head, then you will indeed find Lisp very annoying. The machine model that you are working with in Lisp is not one of pointers and aligned memory regions. Rather, it is a model of recursively structured lists as the fundamental form of aggregation. If that seems a little "fat" to you, it is. But it's also very powerful, once you learn how to use higher order functions to full effect. As with everything in CS, Lisp is a point in the Tradeoff Space. It trades hardware correlation for powerful abstraction. To use Lisp productively, you need to give up your bit twiddling ways and embrace a more formal way of thinking.

David -

You've hit the nail on the head... I do think in terms of MSIL optimization/machine code and memory optimization as my natural perspective on writing code. Your comment is very helpful; I definitely need to reset to be able to learn this properly....

Thanks!

What higher-level constructs and functions are you thinking of that you believe Lisp is lacking?

As for the recursion thing, Lisp certainly does not require recursion - Scheme provides the "do" syntax for writing loops, and Common Lisp has "loop" and whatever else it has, and in Common Lisp iteration is probably more idiomatic than recursion. And, of course, creating your own syntax for loops is trivial in either Scheme or Common Lisp. But writing recursive functions shouldn't seem unnatural - when the language I'm using has the tail call optimisation I write loops pretty much exclusively in terms of recursive functions and don't miss other looping constructs for a second. I think this is more just a matter of what you're used to - the languages you list that you're familiar with do not in general encourage a functional approach.

Let's show one of the trivial ways to make a simplified 'while' loop in Scheme.

    (define-syntax while
      (syntax-rules ()
        ((_ test-exp e1 e2 ...)
         (let loop () 
           (when test-exp e1 e2 ... (loop))))))

So it's fairly easy to add new syntax to the language to make it palatable for people coming from other languages; Kent Dybvig's The Scheme Programming Language covers this in more detail.

And even if we don't use while we can use good equivalents like the "named-let" construct used in the macro above.

Lisp and Scheme are often taught to illustrate certain programming language topics (e.g. recursion, programming without mutation, interpreter implementation), not as practical languages.

Lisp and Scheme are the most expressive and least primitive languages I know of. To quickly illustrate this to people I've started to implement some familiar constructs from other languages in Scheme.

"Why must I always be thinking backwards just to do a loop?"

You don't need to if you don't want: most Lisp implementations already include several such common constructs, like for-each, implemented in terms of macros or functions.

"Why must I define a function to do things that (to my mind) 'ought to be' in any higher-level language than the Assembly that mapped to a particular CPU?"

I don't think i understood what you said correctly, but, like i said, most usual imperative constructs are available, though implemented mostly as macros giving a little syntatic sugar to tail-recursive functions...

Besides, you're looking at it from the wrong angle: it is the fact that Lisp is so flexible and lets you define such common operators using nothing more than common user-level functions that make it so amazing. Basically, Lisp is a very small core of simple primitives directly mapping to their underlying low-level implementation language counterparts, upon which all other high-level functions are implemented. Contrast that with most other languages, in which introducing new functionality, operators and semantics to the language means mostly extending the compiler, interpreters and base libraries.

If you couldn't do everything by means of functions, functional languages wouldn't be of much practical use.

Lisp is very, much higher level than assembler and its direct imperative descendants. You are using .NET, right? All of its current and past innovations come from Lisp, including garbage-collection, virtual machines, for-each kind of loops, map-like operations ( like the LINQs query expressions )...

Besides, no, recursion won't be that costly either in CPU time or memory: a technique known as tail-call optimization turns recursive-looking algorithms implemented in functional languages such as Scheme, Haskell or ML into proper iterative ones, so you gain all the expressive power of recursively defined algorithms with little performance penalty.

Enabling tail-call optimisation has also the unfortunate side effect that when you have to modify your program so that the tail call optimisation can occurs, a nice, logical program is transformed into an ugly, unreadable program.

Which is why I'm not so fond of functionnal programming in the first place..

It sounds to me as though you're confusing use of tail calls with CPS transformation, or something. Perhaps an example of what you're thinking of would help.

One common transformation to allow tail calls is to use accumulator-passing style, which is usually still very readable. Also, such patterns can be abstracted using operators like fold.

Also, such [recursive] patterns can be abstracted using operators like fold.

As can iteration, of course. For instance, I use fold and friends in Tcl code these days, but I implement it usually using iteration and mutable variables as Tcl doesn't (currently) support TCO. The end result behaves identically. These higher-order (and higher-level) operations are much more interesting and eye-opening than either recursion or iteration.

Functional programming languages don't have special constructs for iteration: it's all functions. Without tail-call optimization, you wouldn't be able to implement there "higher-order (and higher-level) operations", which are recursively defined via mere user-level functions.

Imperative languages, on the other hand, rely on a few special constructs to handle general purpose iteration. If you need more, you try to implement in terms of these, and if you can't, you're out of luck and have to expand the language syntax, parsers and compilers.

Continuations, tail-call optimizations and macros are very handy features of Scheme... :)

But, yeah, it can be done iteratively in TCL as in
http://wiki.hping.org/133

Like our thread on expressivity of idiomatic C++ tries to show, "can be done" doesn't always look nice... :)

Functional programming languages don't have special constructs for iteration: it's all functions. Without tail-call optimization, you wouldn't be able to implement there "higher-order (and higher-level) operations", which are recursively defined via mere user-level functions.

So, if I only had functions, and didn't have tail-call optimisation, then I couldn't implement fold et al? Yes, that's true. But it doesn't really tell us anything interesting.

Continuations, tail-call optimizations and macros are very handy features of Scheme... :)

Undoubtedly. The actual high-level constructs you implement with them are more useful, and there is often more than one way to implement these constructs that doesn't involve continuations, TCO, or macros. I'd welcome these features in Tcl, say, but they are not essential.

Like our thread on expressivity of idiomatic C++ tries to show, "can be done" doesn't always look nice... :)

Well, there's a challenge, if ever I saw one. OK, here is an iterative version of fold in Tcl, along with a few definitions:

proc foldl {func id list} {
    foreach item $list {
        set id [apply $func $id $item]
    }
    return $id
}
proc foldr {func id list} {
    for {set i [llength $list]} {$i > 0} {} {
        set id [apply $func [lindex $list [incr i -1]] $id]
    }
    return $id
}
# A few helpers:
proc apply {func args} { uplevel #0 $func $args }
foreach op {+ - * / && ||} { proc $op {a b} "expr \$a $op \$b" }
proc count {x n} { incr n }
proc swap {head tail} { linsert $tail end $head }
proc def {name = args} { interp alias {} $name {} {expand}$args }

And now we can write:

def sum     = foldl +     0
def product = foldl *     1
def diff    = foldr -     0
def div     = foldr /     1.0
def and     = foldr &&    1  ;# 1 == true
def or      = foldr ||    0  ;# 0 == false
def length  = foldr count 0
def reverse = foldr swap  [list]

I don't think that looks too bad, do you?

"But it doesn't really tell us anything interesting."

"there is often more than one way to implement these constructs that doesn't involve continuations, TCO, or macros."

"they are not essential."

Here's the catch: you either have real power and flexibility _in the language_ to do things, or you have to rely on extended syntax, speciall hooks in the interpreter, libs and others.

Macros, TCOs and continuations are _generic_ techniques that allow you to extend the language contructs in meaningful and novel ways, without requiring you to worry about writing new parsers or compilers.

for loops, upvar and other related commands are specialized and limited builtin constructs that allow you to do many useful and general-purpose computations, but they're not as powerful as those.

In a language with a limited builtin for loop, you really don't need TCO, since you'll be writing explicit iteration loops in terms of this builtin command rather than tail-call recursion. In a language where mostly everything can be treated as a mere string, and argument evaluation is parsed by the command they're called against, there really is not much need for macros. And continuations are very rarely useful.

TCL looks ok, but since it really just handle strings all around -- rather than structured data -- it performs horribly. If you want to extend, then it's easy to write a c lib implementing a new command, but then, you're not writing in TCL anymore, huh?

That's what generic constructs give you: power to do anything without ever leaving the same language.

I like TCL a bit, because it's a rather nice mix of Lisp and shell, but it always seems to lack something...

[EDIT: I posted a long-ish reply here, but this thread is getting quite off-topic now. If you want to continue discussing the merits of Tcl, then email me (address should be available from my user page).]

I don't think email addresses are publically available (they aren't supposed to be, at least).

For the record, I found the post above about functional style in Tcl quite interesting. Perhaps one of the site guidelines should be that posts can be off-topic if they include a cool and original code example. ;)

Cool examples are welcome.

all languages have merits, one of them being making people passionate about their fav tool. taste counts too... :)