> Most Scheme stuff can optimize tail-recursion.
In order to actually qualify as Scheme, implementations are required to
be properly tail recursive. It's a short step... if you're using a
Scheme that can't optimize tail-recursion, find another Scheme. (Or
better yet, write your own!)
I wouldn't say that Scheme is impoverished by comparison to Perl or
Python... in fact, once people really know how to milk the key
abstractions in Scheme for all they're worth, I think it's easier to
write equivalent programs in less code than other languages. It's kind
of like UNIX, in that there're just a few incredibly powerful
abstractions, uniformly applied. The following are possible in Scheme:
whole OS kernel schedulers in less than a page... interpreters in a
page or two... compilers in about the same... (note: not necessarily
for Scheme-based syntaxes / semantics, either!) equation solvers in a
page and a half... whole OO runtimes in a couple of pages...
unification engines for theorem proving and type inferencing systems in
about a page... FFT in half a page. These are just some of the
canonical examples from (for instance) the essential Scheme texts like
Dybvig (see below.)
The one area that Perl and, to a lesser extent, Python have an edge on
Scheme in is text processing / string processing. Having the equivalent
of sed built into the language syntax for Perl gives it a real edge;
any sort of good integration with regexps is a bonus for that. OTOH, if
you step one step away from that and can abstract your problem into some
kind of symbolic processing, that's ameliorated to some extent and IMO
Scheme becomes a much better choice.
I wrote up this little piece this morning in a private response to John
Klassa... it's germaine to the discussion and has a few good pointers
so I thought I'd repost it to the list at large.
--
You know, my major epiphany about programming and programming languages didn't really happen until about 1990, when I was at Sun. My group was building a large distributed system which had a need to support dynamic updates to the client across a geographically dispersed user base. (This is the system Sun uses to handle service calls.) We came up with the notion of using downloadable code --- this is pre-Java --- the client was actually just an engine which would download the actual "functional" client code from a database at runtime. We designed a little (C++)-- language called "Evil" (don't ask ;-) and designed a little interpreter system for it. (In some ways, I've always wondered if we influenced Oak a.k.a. Java at all. Surely not. ;-) I learned more than I could've imagined by picking apart a bunch of different implementations of Scheme in C. It's amazing how little C it often takes to implement a Scheme --- sometimes in as little as, say, 2-4k LoC. Check some of these out, especially SIOD.
Diving into interpreters --- actually implementing one --- was a real eye-opener. I'd used Lisps a lot in school, and had a lot of formal stuff, but never really saw the connection between the mathematical underpinnings of programming languages and reality until then. Since then, I've come to realize that there's, like, this "infinitely deep Zen" in the lambda calculus and particularly in Scheme. My sort of "holy grail quest" ever since then has been in trying to synthesize an object calculus analog to Church's calculus. (The reason for this is that such a formalism would make it possible to produce efficient compilers for dynamic object-oriented languages, and would avoid lots of runtime messiness in generated code that often exists today.)
At any rate, here're some books and stuff I'd heartily recommend if you're interested in this kind of thing.
The Scheme Programming Language by Kent Dybvig Structure and Interpretation of Computer Programs by Abelson and Sussman
These two are general Scheme and "deep programming" texts. Dybvig is the K&R of Scheme, and a really pretty little book... it even covers areas like meta-circular interpreters, designing multitasking engines / schedulers for operating systems, etc. It's a real eye-opener to see how really complicated concepts like these can be implemented in a page or two of code in a powerful language like Scheme. (Aside - I worked with a woman who was a grad student of Dybvig's --- she said he was the smartest person she'd ever met.) Abelson and Sussman is a bit broader book, and may well be the best general programming book in existance.
Programming Languages: An Interpreter-Based Approach by Samuel Kamin
This book talks in great detail about how all programming languages share a common set of abstractions, and how the differences in certain language features drive implementation choices. It builds up implementations of interpreters for several "languages" - a "basic" (not BASIC) interpreter, Lisp, APL, Scheme, SASL, CLU, Smalltalk, and Prolog (note that he's really illustrating the key unique abstractions in each, he's actually re-worked the syntax for them all into a sort of s-expression / Scheme-like syntax so as not to obscure the issues.) The implementations in the book are done in Pascal, ick. However, there's a guy out on the net, Timothy Budd, who some years ago did an adjunct to this book called "The Kamin Interpreters in C++" which shows how each of these can be approached from an OOP / structural perspective and implemented in C++ --- in effect he builds up a really nice class library for building interpreters in C++. You can find that here.
Essentials of Programming Languages by Daniel Friedman et. al. Compiling with Continuations by Andrew Appel
This first one is the major mindblower. I can't even say enough about EOPL. It is the most mathematically-rigorous and interesting book of the set. The implementation language is Scheme; Friedman is a big name in Scheme, and one of the deepest thinkers about programming languages I've ever encountered. Also check out Friedman's numerous papers detailing his investigations into making various language elements first-class: continuations, interpreters themselves, extents. Essentially, anything by Friedman here. Once you get past the "lambda calculus gestalt" you run into a second gestalt regarding continuations and the usefulness of something called "continuation-passing style." This book closes in that direction, illustrating how programs can be formally transformed into CPS from which it is trivial to generate psuedo-assembly for Von Neumann processors. Wow. Math to assembly without all the Aho et. al. ;-) Maybe those Bell Labs guys weren't so smart after all. ;-) A much deeper look at that topic alone - compiling with continuations - can be had in CC above.
Enjoy! I'm convinced that there are at most a few dozen people on the planet that really have a fundamental grasp of programming. I don't, yet [despite years of cranking code in all sorts of languages] --- but I'm determined to get there. These books have helped me immensely along my way.
$0.02,
jb
--------------7C52BDCE72CED3F06B0A5D44 Content-Type: text/html; charset=us-ascii Content-Transfer-Encoding: 7bit
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
> Most Scheme stuff can optimize tail-recursion.In order to actually qualify as Scheme, implementations are required to be properly tail recursive. It's a short step... if you're using a Scheme that can't optimize tail-recursion, find another Scheme. (Or better yet, write your own!)
I wouldn't say that Scheme is impoverished by comparison to Perl or Python... in fact, once people really know how to milk the key abstractions in Scheme for all they're worth, I think it's easier to write equivalent programs in less code than other languages. It's kind of like UNIX, in that there're just a few incredibly powerful abstractions, uniformly applied. The following are possible in Scheme: whole OS kernel schedulers in less than a page... interpreters in a page or two... compilers in about the same... (note: not necessarily for Scheme-based syntaxes / semantics, either!) equation solvers in a page and a half... whole OO runtimes in a couple of pages... unification engines for theorem proving and type inferencing systems in about a page... FFT in half a page. These are just some of the canonical examples from (for instance) the essential Scheme texts like Dybvig (see below.)
The one area that Perl and, to a lesser extent, Python have an edge on Scheme in is text processing / string processing. Having the equivalent of sed built into the language syntax for Perl gives it a real edge; any sort of good integration with regexps is a bonus for that. OTOH, if you step one step away from that and can abstract your problem into some kind of symbolic processing, that's ameliorated to some extent and IMO Scheme becomes a much better choice.
I wrote up this little piece this morning in a private response to John Klassa... it's germaine to the discussion and has a few good pointers so I thought I'd repost it to the list at large.
--
You know, my major epiphany about programming and programming languages didn't really happen until about 1990, when I was at Sun. My group was building a large distributed system which had a need to support dynamic updates to the client across a geographically dispersed user base. (This is the system Sun uses to handle service calls.) We came up with the notion of using downloadable code --- this is pre-Java --- the client was actually just an engine which would download the actual "functional" client code from a database at runtime. We designed a little (C++)-- language called "Evil" (don't ask ;-) and designed a little interpreter system for it. (In some ways, I've always wondered if we influenced Oak a.k.a. Java at all. Surely not. ;-) I learned more than I could've imagined by picking apart a bunch of different implementations of Scheme in C. It's amazing how little C it often takes to implement a Scheme --- sometimes in as little as, say, 2-4k LoC. Check some of these out, especially SIOD.
Diving into interpreters --- actually implementing one --- was a real eye-opener. I'd used Lisps a lot in school, and had a lot of formal stuff, but never really saw the connection between the mathematical underpinnings of programming languages and reality until then. Since then, I've come to realize that there's, like, this "infinitely deep Zen" in the lambda calculus and particularly in Scheme. My sort of "holy grail quest" ever since then has been in trying to synthesize an object calculus analog to Church's calculus. (The reason for this is that such a formalism would make it possible to produce efficient compilers for dynamic object-oriented languages, and would avoid lots of runtime messiness in generated code that often exists today.)
At any rate, here're some books and stuff I'd heartily recommend if you're interested in this kind of thing.
The Scheme Programming Language by Kent Dybvig
Structure and Interpretation of Computer Programs by Abelson and SussmanThese two are general Scheme and "deep programming" texts. Dybvig is the K&R of Scheme, and a really pretty little book... it even covers areas like meta-circular interpreters, designing multitasking engines / schedulers for operating systems, etc. It's a real eye-opener to see how really complicated concepts like these can be implemented in a page or two of code in a powerful language like Scheme. (Aside - I worked with a woman who was a grad student of Dybvig's --- she said he was the smartest person she'd ever met.) Abelson and Sussman is a bit broader book, and may well be the best general programming book in existance.
Programming Languages: An Interpreter-Based Approach by Samuel Kamin
This book talks in great detail about how all programming languages share a common set of abstractions, and how the differences in certain language features drive implementation choices. It builds up implementations of interpreters for several "languages" - a "basic" (not BASIC) interpreter, Lisp, APL, Scheme, SASL, CLU, Smalltalk, and Prolog (note that he's really illustrating the key unique abstractions in each, he's actually re-worked the syntax for them all into a sort of s-expression / Scheme-like syntax so as not to obscure the issues.) The implementations in the book are done in Pascal, ick. However, there's a guy out on the net, Timothy Budd, who some years ago did an adjunct to this book called "The Kamin Interpreters in C++" which shows how each of these can be approached from an OOP / structural perspective and implemented in C++ --- in effect he builds up a really nice class library for building interpreters in C++. You can find that here.
Essentials of Programming Languages by Daniel Friedman et. al.
Compiling with Continuations by Andrew AppelThis first one is the major mindblower. I can't even say enough about EOPL. It is the most mathematically-rigorous and interesting book of the set. The implementation language is Scheme; Friedman is a big name in Scheme, and one of the deepest thinkers about programming languages I've ever encountered. Also check out Friedman's numerous papers detailing his investigations into making various language elements first-class: continuations, interpreters themselves, extents. Essentially, anything by Friedman here. Once you get past the "lambda calculus gestalt" you run into a second gestalt regarding continuations and the usefulness of something called "continuation-passing style." This book closes in that direction, illustrating how programs can be formally transformed into CPS from which it is trivial to generate psuedo-assembly for Von Neumann processors. Wow. Math to assembly without all the Aho et. al. ;-) Maybe those Bell Labs guys weren't so smart after all. ;-) A much deeper look at that topic alone - compiling with continuations - can be had in CC above.
Enjoy! I'm convinced that there are at most a few dozen people on the planet that really have a fundamental grasp of programming. I don't, yet [despite years of cranking code in all sorts of languages] --- but I'm determined to get there. These books have helped me immensely along my way.
$0.02,
jb
--------------7C52BDCE72CED3F06B0A5D44--