ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (06/11/91)
There has been some discussion in both comp.lang.prolog and
comp.lang.scheme recently concerning standards for the respective
languages. I think that the Scheme standard has a great deal to
teach people concerned with the Prolog standard (to the point
that I was flabbergasted to discover that some people concerned
with the Prolog standard with whom I corresponded not only hadn't
seen the Scheme standard, not only didn't know one was under way,
but had barely even heard of Scheme).
Let me start right off by saying that when I saw a draft of the
Scheme standard, my immediate reaction was "at LAST Algol 60 has
a successor!" I still feel that way. Scheme is a beautiful
language. It's almost exactly the right "size". The Scheme
standard is a superb piece of work. 50-odd pages _including_ a
formal semantics (which transliterates nicely into Scheme. The
people who wrote that standard really understood the language
they were standardising.
I think it would be an excellent thing if more of the people
concerned with the Prolog standard understood the language they
were standardising. In particular, one would expect the
formal specification of Prolog to be _about_ the same size as
the formal specification of Scheme.
But a standard is not an exercise in academic symbol-pushing.
The development of a standard should not be treated as an excuse
for CS self-stimulation. A standard is a practical instrument,
and the important thing about a standard is the practical effect
it actually has. This is of particular interest because for
many years an explicit goal (indeed, almost the only explicit
goal) of the BSI committee was to develop a "minimal" standard,
and the Scheme standard is just such a "minimal" standard. So a
very important lesson to be learned from the Scheme standard is
"what is the practical effect of a small standard like this".
I regret to inform you that the answer appears to be "not much".
Let me offer you two examples.
1. Adding and Subtracting 1.
Many Lisp systems have functions for adding and subtracting 1.
Over the years, the names have varied a lot, but Common Lisp
has finally settled on the names
(1+ expr) ; add 1 to expr
(1- expr) ; subtract 1 from expr.
Now, the last name is a little misleading. It suggests
1 - expr, rather than expr - 1. So the language described in
"Structure and Interpretation of Computer Programs", namely
"Scheme", included
(1+ expr) ; add 1 to expr
(-1+ expr) ; add -1 to expr == subtract 1
The Scheme standard, however, includes neither of these
operations. They can easily be replaced by the entirely
equivalent
(+ expr 1) ; add 1 to expr
(- expr 1) ; subtract 1 from expr
and a smart compiler will generate the same code for those
expressions that it would have generated for 1+ and -1+.
Indeed, there is nothing in the Scheme standard that requires
a Scheme system to accept 1+ and -1+ as valid identifiers!
What is the effect of this?
a) Some Scheme systems provide 1+, 1-, and -1+
b) Some Scheme systems provide 1+ and 1-
c) Some Scheme systems provide 1+ and -1+
d) Some Scheme systems provide none of them.
And people using a) or c) systems look at SICP and think they
are writing portable Scheme code, while people using b) systems
look at CLtL and think "Scheme is a Lisp, so 1- is portable".
Frankly, I am getting just a little bit tired of having to go
through Scheme code fixing references to 1+, 1-, and -1+.
The identifiers + and - are already exceptional; would adding
1+ and -1+ to the list of exceptional identifiers been _such_
a big deal? And would defining 1+ and -1+ really have made
the standard too big?
2. Sorting.
Sorting is indispensable in Prolog. It is difficult to write
a non-trivial efficient Prolog program without using it. As
Scheme lacks hash tables, sorting is also very useful in Scheme.
However, sorting is not part of the Scheme standard or R^(3.99)RS.
The result is that sorting is often provided, _but_ the only
thing you can rely on is that
if there is a non-destructive sort, it is called `sort'
if there is a destructive sort, it is called `sort!'.
Apart from that, the variations I have encountered are
a) both are provided
b) only `sort' is provided
c) only `sort!' is provided
d) neither is provided
--
e) The interface is (sort sequence less?)
f) The interface is (sort sequence &optional (less? <))
g) The interface is (sort less? sequence)
--
h) Sorting only works on lists
i) Sorting only works on vectors
j) `sort' works on lists only, `sort!' on vectors only
k) Sorting works on both lists and vectors
--
l) Sorting is stable
m) Sorting is not stable
n) It isn't specified whether sorting is stable or not.
All of this variation is really rather pointless, and does nothing
to help people who want to write non-trivial portable code.
i) It is just as easy to provide _both_ sort and sort! as it
is to provide either.
ii) The interface (sort sequence less?) is both consistent with
Common Lisp and the majority of Schemes known to me.
iii) Given vector->list and list->vector, there is no reason not
to make sort and sort! work on both lists and vectors.
iv) merge sort is not only stable, it is considerably faster than
the quicksort chosen by people who haven't read the fine print.
I have my own implementations of `sort' and `sort!' (based on David
H. D. Warren's keysort/2 in DEC-10 Prolog) and they are faster than
the sorts provided in any of the Schemes where I've yet been able to
make measurements. But why should _everyone_ have to carry around
their own sorting functions? (Their own _different_, incompatible,
and (if they succumb to the temptation to use quicksort, inefficient)
sorting functions.)
That's looking at the effect of a `minimal' standard.
Mind you, some of the things the standard _does_ say haven't received
much in the way of conformance, so perhaps it doesn't really matter
that these things _were_ left out of the standard.
The point I want to make is that there is a ``right'' size for a
standardised language, and that many of the things which could have
been defined using the kernel of the language should be included in
a standard library. `sort' and `sort!' can be implemented well using
only standard operations, and so could `1+' and `-1+' be if they were
legal identifiers. Perhaps the answer is to have a kernel standard
and a free source-code `specification-quality' library, like ML. But
Scheme seems to be a successor to Algol 60 in more ways than one, and
I'd hate to see Prolog go the same way.
--
Q: What should I know about quicksort? A: That it is *slow*.
Q: When should I use it? A: When you have only 256 words of main storage.oz@ursa.ccs.yorku.ca (Ozan Yigit) (06/12/91)
Richard A. O'Keefe (ok@goanna.cs.rmit.oz.au) writes:
I have my own implementations of `sort' and `sort!' (based on David
H. D. Warren's keysort/2 in DEC-10 Prolog) and they are faster than
the sorts provided in any of the Schemes where I've yet been able to
make measurements.
Richard was kind enough to provide a copy of his implementation
[sorted?, sort, sort!, merge, merge! in sort.scm] to the Scheme
Repository*. I hope that these functions get picked up and used
enough to become a practical alternative to any muddled versions
[if you have them at all] in your scheme.
That's looking at the effect of a `minimal' standard.
But, scheme does not have one standard. It has two: a static IEEE
document, and a dynamic Revised Report. I personally am inclined to
forget about the former for the next five years. ;-)
oz
---
* The Scheme Repository (sometimes referred as Scheme Yellow Pages+)
is currently accessible via ftp from nexus.yorku.ca [130.63.9.66]
under pub/scheme. See pub/scheme/scm for sort.scm and other scheme
sources.
+ Yellow Pages is a registered trademark of British Telecommunications.
---
Often it is means that justify ends: Goals | email: oz@nexus.yorku.ca
advance technique and technique survives even | phone: 416-736-5257 x 33976
when goal structures crumble. -- A. J. Perlis | other: oz@ursa.ccs.yorku.cacarlton@husc10.harvard.edu (david carlton) (06/14/91)
In article <6209@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:
1. Adding and Subtracting 1.
Many Lisp systems have functions for adding and subtracting 1.
Over the years, the names have varied a lot, but Common Lisp
has finally settled on the names
(1+ expr) ; add 1 to expr
(1- expr) ; subtract 1 from expr.
Now, the last name is a little misleading. It suggests
1 - expr, rather than expr - 1. So the language described in
"Structure and Interpretation of Computer Programs", namely
"Scheme", included
(1+ expr) ; add 1 to expr
(-1+ expr) ; add -1 to expr == subtract 1
The Scheme standard, however, includes neither of these
operations. They can easily be replaced by the entirely
equivalent
(+ expr 1) ; add 1 to expr
(- expr 1) ; subtract 1 from expr
and a smart compiler will generate the same code for those
expressions that it would have generated for 1+ and -1+.
A standard-conforming compiler can't - they have quite different
semantics. I'd rather have named constants...
Indeed, there is nothing in the Scheme standard that requires
a Scheme system to accept 1+ and -1+ as valid identifiers!
One reason why I use add1 and sub1. 1+ and -1+ always looked odd to
me, anyways.
2. Sorting.
Sorting is indispensable in Prolog. It is difficult to write
a non-trivial efficient Prolog program without using it. As
Scheme lacks hash tables, sorting is also very useful in Scheme.
True. Another reason why I like having first-class environments -
they're basically hash tables indexed by symbols. A hot
implementation can even provide dynamically expanding and contracting
environments and spend the time tuning it for speed, ending up with
something that is likely to be much faster than whatever hash tables
you implement by hand.
I think that I agree with your basic point, though. (Which is why I
didn't quote the parts of your posting that actually present your
point.) I do think that it is a bit unfair for you to claim that
thinking that '1-' is portable because CLtL says it is and Scheme is a
list is a particularly reasonable thought process - Scheme has so many
superficial differences from other Lisps that people who have learned
to use begin instead of progn, define instead of defun, etc. probably
will figure that one out, too. SICP is more of a problem - truly
unfortunate that that book was written before R3RS appeared. All
sorts of completely unnecessary nonconformities with current Schemes
that arose from that - my favorite one is the bit where the authors
admit that having '() and #f be the same thing isn't particularly
necessary, but then say that Scheme has it that way so they are going
to use it. Quite reasonable at the time, but a real pain in
retrospect. Hopefully enough other good books about Scheme (not that
SICP is really about Scheme) that conform to current standards are out
there that one has enough other options for becoming familiar with the
language, but it is a problem, all the more so because of the high
quality of SICP.
david carlton
carlton@husc9.harvard.edu
JOYCE: Huelsenbeck demanding, for example?
TZARA: International revolutionary union of all creative men
and women on the basis of radical Communism -
expropriation of property - socialization...
JOYCE: As opposed to Tzara's demanding?
TZARA: The right to urinate in different colours.
- Tom Stoppard, _Travesties_sra@ecs.soton.ac.uk (Stephen Adams) (06/17/91)
In article <CARLTON.91Jun13212846@husc10.harvard.edu> carlton@husc10.harvard.edu (david carlton) writes: > In article <6209@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: > > Indeed, there is nothing in the Scheme standard that requires > a Scheme system to accept 1+ and -1+ as valid identifiers! > > One reason why I use add1 and sub1. 1+ and -1+ always looked odd to > me, anyways. I was disappointed to see the definition of scheme identifiers changed to disallow names like `1+'. I also note the Eulisp has made the same bad decision. I think it is a bad decision because it makes data stored as s-expressions in text files less versatile and no longer a valid `lowest common denominator' data format between different kinds of lisp. I also prefered to use my set of selection functions called `1st', `2nd', `3rd', `4th' etc. I think that these look much nicer on the screen and printed page than `first' and `second'. They are shorter, have an `obvious' meaning and line up nicely beneath on another in larger expressions. -- Stephen Adams S.R.Adams@ecs.soton.ac.uk Computer Science University of Southampton Southampton SO9 5NH, UK
markf@zurich.ai.mit.edu (Mark Friedman) (06/18/91)
In article <SRA.91Jun17100310@pessoa.ecs.soton.ac.uk> sra@ecs.soton.ac.uk (Stephen Adams) writes:
I was disappointed to see the definition of scheme
identifiers changed to disallow names like `1+'. I also
note the Eulisp has made the same bad decision.
This is not true in the case of Scheme. The IEEE standard does not
disallow names like `1+', it considers them extensions to the syntax
of identifiers. The standard does, however, disallow identifiers
which would otherwise be parsed as numbers (i.e. `1e3').
-Mark
--
Mark Friedman
MIT Artificial Intelligence Lab
545 Technology Sq.
Cambridge, Ma. 02139
markf@zurich.ai.mit.edu