🚀 go-pugleaf

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.