Slashdot Mirror
Draft Scheme Standard R6RS Released
Watson Ladd writes, "The new version of the official Scheme standard has been released as a draft (PDF)." From the draft: "[This] report gives a defining description of the programming language Scheme. Scheme is a statically scoped and properly tail-recursive dialect of the Lisp programming language invented by Guy Lewis Steele Jr. and Gerald Jay Sussman. It was designed to have an exceptionally clear and simple semantics and few different ways to form expressions. A wide variety of programming paradigms, including imperative, functional, and message passing styles, find convenient expression in Scheme."
(I (for one (welcome (our new (Scheme (overlords.))))))
Scheme is a language that every programming language enthusiast should know. Being both simple and flexible, it's suitable for communicating and explaining all kinds of concepts. A lot of books and papers are about Scheme or use Scheme for examples or teaching (see Readscheme.org). Scheme also pioneered some of the concepts in modern programming languages (such as lexical scoping), as well as several uncommon features (such as hygienic macros and first-class continuations). There are many Scheme implementations, some tiny, some slow, some fast, some with extensive libraries, some which interface to other programming languages, etc. etc.
Please correct me if I got my facts wrong.
The GNU project adopted Scheme (with the Guile interpreter) as its official scripting language. Applications are not meant to be written in Scheme, but applications can expose functionality to the user through a Scheme interface. That is to say, plugins for extensible applications could be written in Scheme. The Gimp is one of the most noteworthy applications with a Scheme interface, and much of the lower-level functionality of GNU Lilypond is reached with Scheme.
Hmmm... you will need libraries and such for that, though some people do use Scheme for all of those things (see http://www.plt-scheme.org/ and http://www-sop.inria.fr/mimosa/fp/Bigloo/). I have personally used it for web applications, though I usually use common lisp and ocaml for that. In fact, if you are looking for an alternative to C++, Java, or Python, I must recommend OCaml. Look at this book. In fact, I wrote an interpreter for R5RS in OCaml...
``What about a web application?''
Scheme's first-class continuations are actually a very good match for web programming, where a user can re-submit an old form at any time. Basically, with languages that lack call/cc, you will have to break up your application in little pieces to account for this, whereas call/cc allows you to structure your application like a regular one, and the language implementation will deal with the issues.
When it comes to practicality, it all depends on the implementation. The Scheme report is (deliberately) very minimal, and you can't write many Real World programs using only standard Scheme. However, implementations often provide features and libraries that make Scheme practical for real projects, to some extent.
``Is it more or less powerful than, say, C++, Java, or Python?''
It depends what you mean by "powerful". In the programming language community, the answer would likely either be "Scheme is more powerful", because its constructs are very flexible (e.g. it has first-class functions and continuations, which the languages you mention lack or only have to a limited extent), or "No", because all these languages are Turing-complete and thus can do everything the others can.
However, outside the programming language community, the question probably refers not just to the language, but also to the libraries, and there Scheme could reasonably be said to lose out to at least Java. On the other hand, there are Scheme implementations that can call Java code, and thus access everything that is available for Java...
Please correct me if I got my facts wrong.
I've never heard about this language, but hopefully the new version will help it keep up with the latest innovations in programming languages, such as codeblocks and Web 2.0.
Yours truly,
Fictional stereotypical teenage Ruby fanatic.
"Oppression and harassment is a small price to pay to live in the land of the free." -- Montgomery Burns.
are both tools of beauty that have taught me more about programming and problem-solving than all other languages combined. SICP and PAIP are both classics in this regard that everyone should rush out and get now.
It's just such a pity that, since they're both standards which anyone can implement, lots of people do, and as a result, finding one you like and then getting it to talk to other languages and libraries can be a very frustrating experience. And languages like Python with one canonical implementation driven by a BDFL and with exceptional library support are just getting more Lisp-like, which can't be good news for for a renaissance in Lisp or Scheme. Pity really, since I really like 'em both...
--- Hot Shot City is particularly good.
For those of you who don't know what "properly tail recursive" means, a quick explanation. Consider the following code:
:-)
(define (f x) (x x))
(f f)
This defines a function, f, which takes one argument, x, which should be a function (yay, first-class functions!), and calls x upon itself. Then, it calls f on f.
Of course, this will cause f to call f upon itself. Again. And again. Infinite recursion!
Now, proper tail recursion means that if a function call returns in tail position (meaning it is the last thing the surrounding function does before it returns), the activation frame for the surrounding function is replaced by that of the function it calls. Contrast this with normal recursion, where a _new_ activation frame would be created for the called function.
Tail recursion makes the example code above run in bounded memory...looping forever.
Please correct me if I got my facts wrong.
Since Scheme wasn't the one of the versions of LISP that I learned back in the dark ages, I couldn't really follow the subtleties of which changes are really significant, but it looks like it would make sense if you were following Scheme.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
But Scheme looks like one of the many programming languages developed for parsers and compilers, instead of for the people. Programming languages should be easy to read for humans too.
Lisp syntax certainly does not attempt to look like the combination of English text and mathematical formulas that most languages shoot for, but this in fact has many advantages. The idea of making a language look like that doesn't change the fact that the language will work in a way very different from English or mathematical notation; your previous knowledge of those things will not necessarily help you reason about your code, and at worst, may confuse newcomers by tempting them to apply analogies that don't hold. And to achieve that "look" for your language, you always end up giving it a really complex and inflexible syntax, whose users are not going to have any systematic knowledge of. (Do you know many people who can give you a BNF grammar for Java, or tell you the exact precedence rules for it?)
Lisp makes no pretence at looking like English or mathematics. You're certainly expected to understand the syntax rules of the language more than in "friendlier" ones, but these rules are far, far simpler, and you can actually reason them through. Remember, Scheme oooks regularly include a section that shows you how to write a Scheme interpreter in one page of Scheme code; basic knowledge of how Scheme itself works is considered to be elementary Scheme knowledge.
That is, what I'm saying is that compared to other languages, Lisp dialects demand that you understand the language itself far more, but this is a good thing, which will make you program way better. Why? Because you're going to be able to reason about the execution of your program far better than your average Java programmer.
Plus, you can do macros.
Are you adequate?
;;;
;;; Macro to increment a variable by one.
;;;
;;; Usage:
;;;
;;; (define a 5)
;;; (inc! a) ; a is now 6
;;;
(define-syntax inc!
(syntax-rules ()
((inc! x)
(set! x (+ x 1)))))
Not that idiomatic Scheme code will do this very often. Langauges like Java or C use "++a" most often for loop indexes. Looping in Scheme is typically driven off data structures.
Are you adequate?
This is only distributing until you remember that almost every implementation has to implement something similar, often in a way that's slightly different and incompatible with everything else. I'll agree that there is a danger, yes.
However, I personally feel that R6RS is nearly at the perfect point. It is still very heavily leaning towards simplicity and clarity, but includes the bits that everyone ends up implementing anyway in non-standard ways. The truth is that modern unix systems are ugly, i/o is complicated, and a lack of a standard macro system (see the syntax-case variants) is horribly annoying. R6RS does reflect all of this, but I think trying to cleanly negate issues is far better than simply ignoring them. There are a few things that I think overreach, but I'm very happy with 95% of the additions. This is a standard we can make use of for the next 10-20 years.
From Wikipedia: "Scheme started as an attempt to understand Carl Hewitt's Actor model.[1] Scheme was originally called "Schemer", in the tradition of other Lisp-derived languages like Planner or Conniver. The current name resulted from the authors' use of the ITS operating system, which limited filenames to two components of at most six characters each. Currently, "Schemer" is commonly used to refer to a Scheme programmer."
but its really not the lanuage that you would want to use for your daily work, for that it simply lacks a lot of convenience features (++a becomes (set! a (+ a 1))
This just shows a lack of fundamental understanding of how one typically writes Scheme programs. If you're incrementing variables to the point where that becomes a concern, you're completely misusing the language.
even trivial tasks like a for-loop you have to either code yourself or rely on non-portable extensions.
Again, this shows you have no experience with the language, or you've been using it horribly wrong. There's no reason you should ever need a for loop in Scheme. If you're going to use Scheme as mostly imperative language, you're better off with Python or similar.
Actually, Scheme/LISP was designed for "correctness" rather than for ease of compiler implementation. Take for instance something like
x = y + 1;
in C. That doesn't actually mean "x = y + 1" it means "x = y + 1 (mod 2^32)". Why is it done this way? Because it is a lot easier for a compiler designer to implement integers if they are always a fixed number of bits.
On the other hand, Scheme does it the correct way, so that (set! x (+ y 1)) actually does what it looks like it does. This is one of the reasons C compilers took off in the 70s while lisp compilers stagnated. I suggest you read the paper "Worse is Better"
---
Your resident MIT student
PS. Don't take this as support for Scheme. I hate Scheme.
This always comes up, but if you're at all interested in programming languages, here's why you should learn Scheme.
A few years ago I was doing a project that involved parsing the intermediate code that GCC generated while compiling a C program. Doing a bit of research I found out that one of GCC's intermediate stages was a language called RTL (register transfer language). To my surprise, RTL looked something like this:
(set (reg:0) (mem:blah blah))
But wait, I thought -- that looks like Lisp. Come to find out RTL was based on lisp s-expressions.
It was then I realized what the Big Deal with Lisp was - it has no syntax at all, and programs written in this parenthetical form are trivially converted into a parse tree. In fact, if you've ever written a simple interpreter or compiler, odds are good you'd use a list-like structure to store the parsed code.
The reason Lisp and Scheme are so "powerful" is that you, as a programmer, have direct access to the program's parse tree at all times. (You can even alter the parse tree at compile time with macros, which is really modifying the compiler to suit your program.)
But really, the best way to learn why Scheme or Lisp are so great is to implement them. Writing a Scheme to assembly compiler will give you an incredibly deep understanding as to how compilers and programming languages in general work.
If you were to try to write a compiler for any other language, you'd probably spend most of your time on the lexer and parser. With Lisp or Scheme, the program, as written, is already almost fully parsed for you. Once you understand that, you'll realize why it's so cool.
If moderation could change anything, it would be illegal.
I am sure there are a numer of ways to learn Scheme if you are interested. Here's one: follow the CS-61A course podcast of Brian Harvey's class at Berkeley.
meh.
``"properly tail recursive" is an oxymoron. Tail recursion is not proper. Decent programmers use loop constructs for looping.''
That's highly debatable. I would agree that when you want to express the concept of a loop, it's best to use a looping construct, but other people would disagree. Also, tail calls are more general than loops; for example, they also work for mutually recursive functions.
Which is more elegant?
int gcd(int a, int b) {
return (b == 0) ? a : gcd(b, a % b);
}
or
int gcd(int a, int b) {
int t;
while (b != 0) {
t = b;
b = a % b;
a = t;
}
return a;
}
``Your problem is that Scheme can't do that.''
That depends on what you mean by "Scheme can't do that". It's entirely possible to implement looping constructs in Scheme, and several people have done so. Scheme can't do looping in the same sense that C can't compute factorials.
``When all you have is a hammer, everything looks like a nail.''
Except that, in Scheme, you can make your own tools on a much more fundamental level than in many other languages. Thanks to tail call optimization, you can _implement_ looping constructs, even though the language doesn't provide them.
``Needless recursion makes your code more convoluted and less readable.''
I think the example I gave earlier illustrates that, sometimes, recursion leads to less convoluted, more readable programs. The right tool for the job, ey? In a language that isn't properly tail recursive, the recursive gcd would be a bad idea because the recursion would eat memory, but in Scheme it's no problem.
``It's amazing how people can claim a deficiency as some kind of advantage. You just keep smoking...''
I'm not claiming a deficiency as an advantage. I'm claiming tail call optimization is a nice features to have. There is no deficiency here.
You could argue that the lack of looping constructs is a deficiency. However, the lack of looping constructs (1) is not at all implied by the language being properly tail recursive, (2) is easily remedied, and (3) actually has been remedied in many implementations.
And no, I don't smoke, though I do live in the Netherlands.
Please correct me if I got my facts wrong.
``Languages without extensive first/third parties libraries are useless.''
I won't argue this point further. I've already stated that languages without _extensive_ libraries can still be useful in specific domains. I still stand by that view.
``And languages like Scheme and Lisp are particularly crippled because they don't even have a standard extension mechanism.''
Huh? The package system is a standard feature of Common Lisp. R6RS may standardize a module system for Scheme (although this is not certain yet); in the absence of that there is SLIB, which provides a de-facto standard mechanism.
Please correct me if I got my facts wrong.
Given the fact that Guile is more than just Scheme and that Scheme has very little traction as a scripting language, Guile is essentially "yet another scripting language" in competition with Python, Ruby and the rest. At one point there was a pipe dream that other languages would be compiled to Guile but that never materialized. In retrospect, Guile was a huge mistake for the FSF. Despite their long-term investment in Guile, Python is more popular for programming Gnome than Guile is. If the translation concept had worked then Guile might have been a reasonable project. But as your post demonstrates, since development actually began, Guile has essentially been just another Scheme implementation.
As for what "Scheme is defined by", it doesn't matter: You program with implementations, not standards
We're not discussing whether Scheme is a good language to program in (that's a separate debate), we're discussing whether it's a good language to communicate ideas in, as the GP claimed.
Furthermore, Scheme, as it is now, can be a very good "grown-up" language (whatever that means).
It means that programmers and computer scientists find other languages more useful for communicating their ideas and getting their work done.
See Chicken Scheme and its large number of bindings for networking, graphics, sound, et cetera.
Implementations of Scheme with excellent bindings have existed for two decades, yet one new language after another has overtaken Scheme: Perl, Python, Tcl, Java, Ruby, C#, PHP, the list goes on. Evidently, people really don't want to use Scheme.
It's time you looked at the output from a modern C compiler. I compiled the example for PowerPC using gcc 4.1 and got the assembly shown below. There is no recursion. There isn't even any memory access; everything is done in registers. (FYI, "blr" is the PowerPC instruction for "return")
.p2align 4,,15 .L9: .L7:
gcd:
cmpwi 0,4,0
bne 0,.L7
blr
mr 4,0
divw 0,3,4
mullw 0,0,4
subf 0,0,3
mr 3,4
cmpwi 7,0,0
bne 7,.L9
mr 3,4
blr
Short and simple explanation of continuations:
A continuation is "the part of the program that hasn't been executed yet". If your code is
(foo)
(bar)
(baz)
and you've just executed (foo), the continuation is (bar) (baz).
In Scheme, continuations are first-class values, which means they can be stored in variables, returned from functions, passed as arguments, etc.
There is a single way to create continuations, namely through the call-with-current-continuation form (often abbreviated call/cc). You pass call/cc a function that takes one argument, and call/cc will call that function, passing it the current continuation as an argument. E.g., in
(foo)
(call/cc fun)
(bar)
(baz)
fun will be called with a continuation representing (foo) (bar) as an argument.
The continuation itself is a function that takes one argument, and calling that function will have the effect of returning from the call/cc that created it, with the value you pass to the continuation as a return value. E.g.
(display (call/cc (lambda (cont) (cont 42))))
will display 42, because that's the value you passed to the continuation.
Now, things get _really_ interesting once you don't immediately invoke the continuation, but you store it in a variable for later use. E.g.
(define cont #f)
(call/cc (lambda (c) (set! cont c)))
(foo)
Now, cont is set to the continuation that, when invoked, will have the effect or returning from the call/cc form (i.e. (foo) will be the next form executed). The great power of Scheme's continuations is that this cont can be invoked any number of times, just like a normal function.
What is it actually useful for? Well, it's definitely not something you use all the time. But you could use it to implement threads, for example:
(define *threads* '())
(define (schedule-thread thread)
(set! *threads* (append *threads* (list thread))))
(define (run-next-thread)
(if (not (null? *threads*))
(let ((thread (car *threads*))
(set! *threads* (cdr *threads*))
(thread))))
(define (make-thread thunk)
(schedule-thread thunk)
(yield))
(define (yield)
(call-with-current-continuation
(lambda (cont)
(schedule-thread (lambda () (cont #t)))
(run-next-thread))))
Now, you can create a new thread by saying
(make-thread (lambda ()
; your thread's code goes here
))
and a thread can give up its timeslice by calling (yield).
No time to check the code now, I have to go to a meeting.
Please correct me if I got my facts wrong.
For one, I'm not sure unicode should be mandatory. I believe it should be described as a recommended component, but not necessary to call your language R6RS-compliant. Would I use a Scheme without unicode support? No, but for some applications and on some systems it isn't necessary. It is great to standardize on an interface, so all that do implement it (and most will) will do it compatibly, but it shouldn't be mandatory. Other things that should probably be recommended by not required are exceptions and the hygienic macro system (although R5RS was no better on this point). I'm less sure about the macro system being recommended instead of required actually. Section 7 should be strictly optional. It already is in a way, but this should be more explicit. The I/O portion of the library is huge -- It does a lot, and is quite flexible. That's great, but it is a rather onerous implementation requirement, and should be recommended, not required... and maybe even broken up into two pieces. Finally, I'm not sure I agree with keeping mutable pairs (set-car!, set-cdr!), but again this is no different from R5RS. The rest of my things are trivial... 'when' and 'unless' aren't needed. Ultimately, anything that makes R6RS significantly harder to implement should be moved from "required" to "recommended". R6RS-compatible scheme can then clearly say which of the five or so "recommended" groups of functionality they suppose; In reality, probably most will support all five, but for some Schemes it just doesn't make sense to do so.
Isn't a central point of Scheme that it is properly tail-recursive, functional programming language? While I'm not all that familiar with Scheme, wouldn't you usually use a recursive function rather than a for-loop in such a language?
A for-loop isn't a task, its a construct that is natural in the idiom of certain languages for accomplishing certain tasks. Its not the idiomatic way to approach those tasks in all languages, though.
Most modern C compilers will do tail-call optimization. However, it is not a requirement of the language (an implementation that fails to do so will still be "C"), and so implementation-agnostic portable code shouldn't count on it, and the language itself provides strong support for programming constructs that make sense when you can't count on tail-call optimization.
Functional programming languages that require tail-call optimization as part of their definition, tend not to support such constructs as well (or, when they do, to do so as syntactic sugar for a recursive implementation), but rather use recursive functional idioms to address the same situation. These may be less natural appearing if you've spent lots of time working with imperative languages where those approaches aren't the natural solution (and where likely you've had "don't use recursion unnecessarily" beaten into your head), but recursive expressions of algorithms tend to be both compact and clear.