Where is Scheme going? 
Author Message
 Where is Scheme going?

When I started using Scheme in the days of R2RS, I was pleased with
its principled simplicity, but disappointed in the 'missing' features:
macros and OOP. Soon I switched to Common Lisp, but tried to monitor
Scheme's development from afar. Lately I've been dabbling in R4RS
Scheme, with the same old disappointments.

I've noticed some documents that mention R5RS "real soon now", but
I've also seen comments to the effect that R5RS may never be.
Questions: What's going on? Is Scheme's definition now IEEE's
responsibility? Is Scheme becoming moribund? Is Scheme still a
research language? Is it used for production programming anywhere?
If 'Scheme' refers to an ossified standard, is there a replacement to
fulfill the need for a rapidly evolving research language (to
paraphrase the TI Scheme Language Reference Manual)?

I would appreciate any news or views from those closer to the
Scheme scene ...

Mike Blackstone



Thu, 17 Oct 1996 02:31:03 GMT  
 Where is Scheme going?

   When I started using Scheme in the days of R2RS, I was pleased with
   its principled simplicity, but disappointed in the 'missing' features:
   macros and OOP. Soon I switched to Common Lisp, but tried to monitor
   Scheme's development from afar. Lately I've been dabbling in R4RS
   Scheme, with the same old disappointments.

You didn't read far enough -- Scheme now has the probably most
advanced macro facility of all programming languages.  (I know -- it's
only in the appendix and not really part of R4RS yet.)  As far as OOP
is concerned I don't share your point of view.  Hopefully `they' will
not do the same to Scheme that `they' did to C (meaning: C++).
I have yet to come accross a real use of OOP in the presence of
polymorphism and first-class-everything.

   I've noticed some documents that mention R5RS "real soon now", but
   I've also seen comments to the effect that R5RS may never be.
   Questions: What's going on? Is Scheme's definition now IEEE's
   responsibility? Is Scheme becoming moribund? Is Scheme still a
   research language? Is it used for production programming anywhere?
   If 'Scheme' refers to an ossified standard, is there a replacement to
   fulfill the need for a rapidly evolving research language (to
   paraphrase the TI Scheme Language Reference Manual)?

   I would appreciate any news or views from those closer to the
   Scheme scene ...

Even though I'm now on the `rrrs-authors' mailing list and even though
I spent quite some time and effort on implementing a Scheme system
myself, I'm not really sure whether I'm any closer to the ``Scheme
scene'' than you are.  But I agree with your complaints.  R5RS is long
overdue.

However, when I read through the proposals for R5RS I get the strong
feeling that the language is being developed into the wrong direction
anyway.  `values' is totally unnecessary (its use through
`call-with-values' is awkward, and it doesn't buy you anything),
`dynamic-wind' eliminates the last chance of having an efficient
call/cc mechanism and is (IMO) in inherent contradiction with the
concept of continuations.  In the case of `evaluate' we just barely
escaped from greater damage, because they did not require first-class
local environments.

What's really still missing is a sensible module system, which
facilitates efficiency and separate compilation.

--
-Matthias



Thu, 17 Oct 1996 03:09:29 GMT  
 Where is Scheme going?



      When I started using Scheme in the days of R2RS, I was pleased with
      its principled simplicity, but disappointed in the 'missing' features:
      macros and OOP. Soon I switched to Common Lisp, but tried to monitor
      Scheme's development from afar. Lately I've been dabbling in R4RS
      Scheme, with the same old disappointments.

   You didn't read far enough -- Scheme now has the probably most
   advanced macro facility of all programming languages.  (I know -- it's
   only in the appendix and not really part of R4RS yet.)  As far as OOP
   is concerned I don't share your point of view.  Hopefully `they' will
   not do the same to Scheme that `they' did to C (meaning: C++).
   I have yet to come accross a real use of OOP in the presence of
   polymorphism and first-class-everything.

What would you consider to be a real use?

-- Harley Davis
--

------------------------------------------------------------------------------
nom: Harley Davis                       ILOG S.A.

tel: (33 1) 46 63 66 66                 94253 Gentilly Cedex, France



Thu, 17 Oct 1996 20:58:29 GMT  
 Where is Scheme going?


   >You didn't read far enough -- Scheme now has the probably most
   >advanced macro facility of all programming languages.

   Surely you aren't suggesting that the word "simplicity" could possibly be
   applied to that elephantine macro appendix!

You might be true about the appearance of the appendix itself,
especially the ``explanation'' of the low-level macro system.  The
high-level pattern language, however, is (IMO) very simple and
intuitive.  And I really like the hygiene stuff.
BTW, the low-level stuff described in the appendix has essentially
been sacked, and hopefully we won't see it anymore in the next
revision of the report.  (This is trivially true if the new report
doesn't come out. :-)

These days (in my spare time) I'm playing with an implementation of a
low-level macro system, which supports hygienic macros.  It is
modelled after Jonathan Rees' paper (``The Scheme of Things...'').
I believe that the solution I came up with (for the low-level stuff)
is actually quite easy to use.  But I'm not done yet.

   >  In the case of `evaluate' we just barely
   >escaped from greater damage, because they did not require first-class
   >local environments.

   No doubt there's some efficiency issue that I'm missing, but it's always
   seemed to me that "everything first-class" is one of the central design
   principles of Scheme, and that it's served us well.  I'd really like to
   have first-class environments.

But environments have never been a part of Scheme.  At least not at
the surface. If you allow the program to muck around with it's
closures and the mapping from names to locations directly, then it
becomes very difficult for a compiler to produce efficient code --
mainly because this mapping (which thanks lexical binding can be
compiled very efficiently) can now change at any time without warning.
Simple interpreters, which already use the most expensive way to
access variables, don't suffer from that.  Compiled code does.

   >What's really still missing is a sensible module system, which
   >facilitates efficiency and separate compilation.

   No need for that, if you have first-class environments!  :-)

I keep hearing this argument -- without smiley.  But I would like to
put an emphasis on the word ``efficiency''.  First-class environments
really miss out here (unless you want to go through a lot of
unnecessary trouble).

--
-Matthias



Thu, 17 Oct 1996 14:08:42 GMT  
 Where is Scheme going?


      I have yet to come accross a real use of OOP in the presence of
      polymorphism and first-class-everything.

   What would you consider to be a real use?

Anything that could not be expressed with the same ease by something
else but OOP.

--
-Matthias



Fri, 18 Oct 1996 02:58:05 GMT  
 Where is Scheme going?
|   No doubt there's some efficiency issue that I'm missing, but it's always
|   seemed to me that "everything first-class" is one of the central design
|   principles of Scheme, and that it's served us well.  I'd really like to
|   have first-class environments.
|
|But environments have never been a part of Scheme.  At least not at
|the surface. If you allow the program to muck around with it's
|closures and the mapping from names to locations directly, then it
|becomes very difficult for a compiler to produce efficient code --
|mainly because this mapping (which thanks lexical binding can be
|compiled very efficiently) can now change at any time without warning.

Couldn't you make much the same sort of argument about continuations?
For that matter, lambda hurts efficiency because it means you can't
keep frames on a stack.  And so good Scheme compilers recognize special
cases in which there's an efficient way to do things, but also can
handle cases in which there isn't.  Surely first-class environments
could be implemented in a way that only hurts if you use them, just as
some Scheme compilers *do* keep frames on a stack when possible.



Fri, 18 Oct 1996 12:32:40 GMT  
 Where is Scheme going?

Quote:

> Couldn't you make much the same sort of argument about continuations?
> For that matter, lambda hurts efficiency because it means you can't
> keep frames on a stack.  And so good Scheme compilers recognize special
> cases in which there's an efficient way to do things, but also can
> handle cases in which there isn't.  Surely first-class environments
> could be implemented in a way that only hurts if you use them, just as
> some Scheme compilers *do* keep frames on a stack when possible.

Well, SML/NJ seems to prove that call/cc can be implemented very
efficiently without impacting (too much) on the performance of code
that doesn't use it. And I wouldn't consider it's implementation
technique as complex. It's actually simpler in many ways than using a
stack. (I'm not saying that SML/NJ is a simple compiler, but that's
not because of call/cc, because of its optimisations)

        Stefan



Fri, 18 Oct 1996 15:55:31 GMT  
 Where is Scheme going?

|>    No need for that, if you have first-class environments!  :-)
|>
|> I keep hearing this argument -- without smiley.  But I would like to
|> put an emphasis on the word ``efficiency''.  First-class environments
|> really miss out here (unless you want to go through a lot of
|> unnecessary trouble).

Depends on what you mean by supporting first-class environments.  If
all you want is to capture and inspect the current environment, then
add a syntactic form grab-current-lexical-environment.  This
(macro)expands to (list (list 'x x) ...), one pair for each variable
lexically bound.  Hygenic macro expanders could work some magic so no
introduced variables are grabbed.  No runtime hit.

Perhaps you want some sort of delimiter for this capture?  Still not a
problem: everything complicated happens at compile time.  If you also
include an evaluator (eval-in-top-level-environment), it's trivial to
create a wrapper for this which takes, as a second argument, an alist
like the one created by grab-current-lexical-environment.  It's just
(lambda (text env) (eval-in-top-level-environemt `(let ,env text))).
Still no additional runtime hit.

So, you must mean something like an ability to grab environments and
mutate variables through their symbols.  It gets more complicated, but
how about grab-mutable-lexical-environment, which expands (as above)
to (list (list 'x (lambda () x) (lambda (y) (set! x y))) ...).
Now, where's that runtime hit?

Or does first-class environment mean something more to you?

dr



Sat, 19 Oct 1996 01:43:42 GMT  
 Where is Scheme going?
(Sorry if you see this twice, I'm not sure if it made it out of Rice.)


|> `dynamic-wind' eliminates the last chance of having an efficient
|> call/cc mechanism and is (IMO) in inherent contradiction with the
|> concept of continuations.

dynamic-wind is needed because Scheme has no continuation delimiters.
Add such, and the need for dynamic-wind will disappear.  Also, you get
closer to full abstraction with traditional denotational semantic
models and you can give a rewrite semantics which is compatibly
closed.  (that is, you can write the rewrite rules such that: if M ->
M', then (M N) -> (M' N), (N M) -> (N M'), (lambda (x) M) -> (lambda
(x) M') etc.)

What are continuation delimiters?  Check the work of Dorai Sitaram;
various papers of his are in the directory
titan.cs.rice.edu:/public/languages/.

As for efficiency, I believe the most efficient callcc style
continuations can get is amortized O(1) (by allocating frames, or
groups of frames, on the heap).  Given this implementation, one of the
Freedman & ??? books, _Scheme & the Art of Programming_ has an
implementation of dynamic-wind which is O(n), where n is the number of
winds walked through (that is, the number of unwinds going towards the
root of the continuation tree plus the number of winds going towards
the destination of the jump).  If no dynamic-wind needs to be walked
through, you get negligible overhead.

dr



Sat, 19 Oct 1996 01:45:57 GMT  
 Where is Scheme going?



   > Couldn't you make much the same sort of argument about continuations?
   > For that matter, lambda hurts efficiency because it means you can't
   > keep frames on a stack.  And so good Scheme compilers recognize special
   > cases in which there's an efficient way to do things, but also can
   > handle cases in which there isn't.  Surely first-class environments
   > could be implemented in a way that only hurts if you use them, just as
   > some Scheme compilers *do* keep frames on a stack when possible.

   Well, SML/NJ seems to prove that call/cc can be implemented very
   efficiently without impacting (too much) on the performance of code
   that doesn't use it. And I wouldn't consider it's implementation
   technique as complex. It's actually simpler in many ways than using a
   stack. (I'm not saying that SML/NJ is a simple compiler, but that's
   not because of call/cc, because of its optimisations)

Exactly.  There is a paper by Andrew Appel and Zhong Shao coming up
(can't seem to remember where), which shows in great detail that
heap-allocated continuation closures (aka stack frames) can be about
as efficient as stack-allocated ones.

BTW, the ``was never part of the language'' argument can *not* be used
agains continuations.  In fact, continuations are the feature which
started Scheme in the first place (if I remember correctly) --
Sussman's and Steele's (re)discovery that function calls and actor
calls are essentially the same thing.

--
-Matthias



Fri, 18 Oct 1996 22:17:38 GMT  
 Where is Scheme going?

[ a valid set of suggestions for
        - grabbing a local environment through a special form
        - mutating existing variables through their names
]

All this doesn't require the existence of first-class environments.
Macros and a-lists do fine.  In fact, David's article shows exactly
how it can be done...

Something must be said about mutable variables:

Normally the compiler can see, whether there are any SET! expression
for a given variable within its scope. (In Scheme this is not true for
global variables, which makes their use potentially less efficient.)

An implementation can take advantage of this when it comes to closure
creation.  In the case of an immutable variable the compiler only need
to save the VALUE of the variable, not its LOCATION.  I.e., the
``location'' doesn't need to be unique.

For mutable variables the (unique) location must be saved.  In
implementations, which cannot provide unique locations one must
introduce ``reference cells'' for mutable local variables.  Orbit does
this, I do it in VSCM, and I suppose other systems use the same
technique.  (Global variables always must have a unique location.)

Fazit: In many implementations it is better (more efficient) to have
immutable local variables.  In the presence of first-class local
environments, which allow assignment all variables are potentially
mutable, hence less efficient.

   Or does first-class environment mean something more to you?

I know people who want to be able to *add* (or remove) variables to
(or from) local environments at run-time (e.g., evaluate DEFINE forms
in local environments).  Crazy -- isn't it? The last time I checked,
MIT Scheme possessed this ``feature''.

I don't see how changing the scope of variables (because of shadowing
effects and such) on the fly can be done without serious performance
hits or *lots* of trouble in the run-time system (backpatching of code
during DEFINEs, ...).  I'm also not sure whether it would be worth it.

--
-Matthias



Sat, 19 Oct 1996 03:02:20 GMT  
 Where is Scheme going?



   |> `dynamic-wind' eliminates the last chance of having an efficient
   |> call/cc mechanism and is (IMO) in inherent contradiction with the
   |> concept of continuations.

   dynamic-wind is needed because Scheme has no continuation delimiters.

Hmmm.  And I always thought that the ``continuation of an expression''
is the ``computation that would normally proceed after the expression
has been evaluated''.  With ``dynamic-wind'' a continuation captured
by call/cc will do things which wouldn't have been done without saving
and invoking this continuation.  So call/cc ``adds'' stuff to the
continuation, which wasn't there before.

   Add such, and the need for dynamic-wind will disappear.

I know of the problems which are supposed to be solved by
``dynamic-wind''.  Still, I think that the solution contradicts the
spirit of the term ``continuation''.  This might sound like
nitpicking, but I feel that way.

Why can't we add some differently named routines and the concept of
``contexts'', ``thread''s, or whatever word you like best, which would
be implemented on top of call/cc and which would provide
``dynamic-wind''.  The ``new call/cc plus dynamic-wind'' can be
implemented on top of the ``old'' call/cc.  Just do the same thing,
but don't overload the meaning of ``continuation''.  Use different
names and leave the original call/cc alone!  That's all I'm asking
for.

                                                           Also, you get
   closer to full abstraction with traditional denotational semantic
   models and you can give a rewrite semantics which is compatibly
   closed.  (that is, you can write the rewrite rules such that: if M ->
   M', then (M N) -> (M' N), (N M) -> (N M'), (lambda (x) M) -> (lambda
   (x) M') etc.)

I'm lacking sufficient background here, so I can't comment.

   As for efficiency, I believe the most efficient callcc style
   continuations can get is amortized O(1) (by allocating frames, or
   groups of frames, on the heap).

No, the most efficient call/cc's have *guaranteed* O(1) time
complexity.  Look at SML/NJ, for example!

--
-Matthias



Sat, 19 Oct 1996 03:20:15 GMT  
 Where is Scheme going?
This is a long message that started out as a simple reply to a message
from David Richter.  But this simple reply evolved into a more
complicated message because I've been thinking about first-class
environments for too long.  I'm also an ex-believer in first-class
environments, and everyone knows that ex-believers are the worst
flamers.

Thus, the latter part of this message is an argument in favor of
another way to view how procedures are connected together to form
programs.  In the context of this view, first-class environments are a
poor way to implement modules.

   Date: 2 May 1994 17:43:42 GMT

   Subject: Where is Scheme going?

   Depends on what you mean by supporting first-class environments.  If
   all you want is to capture and inspect the current environment, then
   add a syntactic form grab-current-lexical-environment.  This
   (macro)expands to (list (list 'x x) ...), one pair for each variable
   lexically bound.  Hygenic macro expanders could work some magic so no
   introduced variables are grabbed.  No runtime hit.

This is false: there is a runtime cost if the environment is passed
out from the code that the compiler is inspecting.  The cost is that
all named internal procedures visible in the captured environment must
be fully closed because they will have indefinite extent.  And
virtually all interesting uses of first-class environments involve
passing the environment out of the compiler's view; any other use can
always be written in a way that does not use first-class environments.
In short, the most common reason for wanting a first-class environment
is so that it can be passed to EVAL; but this is also the worst case
from the point of view of the compiler.

   So, you must mean something like an ability to grab environments and
   mutate variables through their symbols.  It gets more complicated, but
   how about grab-mutable-lexical-environment, which expands (as above)
   to (list (list 'x (lambda () x) (lambda (y) (set! x y))) ...).
   Now, where's that runtime hit?

This has an even more serious runtime hit.  Now, in addition to being
forced to close named internal procedures, the compiler also cannot
make any assumptions about the value of any internally bound variable
after the environment has been captured.  At this point you have
eliminated nearly all of the interesting optimizations that a compiler
can perform.  There *is* one simple optimization that can be
performed, which consists of inline-coding the interpreter based on
the program text.  But the result will be only slightly better than
direct interpretation.

   Or does first-class environment mean something more to you?

First-class environments as implemented by MIT Scheme allow
"top-level" definitions to be performed in any environment.  This
significantly complicates the implementation when the environment can
be snatched from any block by means of a (THE-ENVIRONMENT) special
form.  In addition to the problems I explained above, this introduces
one further problem: the compiler now can't even predict what variable
binding corresponds to a particular identifier (unless that binding
occurs in the innermost block of the captured environment).  This
prevents the use of such simple optimizations as lexical addressing
where the shape of the environment is known and the compiled code just
indexes to the proper location.

At the time that MIT Scheme's environments were being designed, this
support for "top-level" definitions was considered by most of us to be
an essential feature of these environments.  Today, at least some of
us feel that the cost is too high to justify the power gained.

[Long flame follows:]

My current belief is that first-class environments with semantics at
least as powerful as those of MIT Scheme's are useful in a limited
way: as "top-level environments".  When used in this way, they do no
harm, because the environments that matter to the compiler are the
internal ones, not the top-level ones.  In other words, if you don't
make the internal environments first-class, the compiler won't have
any trouble.

As Jim Miller and Bill Rozas have shown, having multiple, nested,
top-level first-class environments has equivalent performance to a
single distinguished top-level environment.  In fact, the mechanism
they have described trivially generalizes to support arbitrary maps
from names to bindings.  The key to their mechanism is that the
top-level environment is primarily a data structure used by the linker
to connect procedures directly to the bindings that thay use.

In the longer term I think that first-class environments, as currently
implemented, are too limited for a "top level".  The problem with them
is that they present only one view of the objects that they contain,
and they can't be combined to make new environments.  From the point
of view of a particular procedure closed at "top level", it doesn't
matter that the enclosing context is an environment frame with
particular structure -- all the procedure cares about is that it can
access the values of particular variable bindings.  The procedure
doesn't even care about the identifiers used to name the variables:
the identifiers are just names that tell the linker how to connect the
procedure to other objects.  If the compiler and linker are
implemented right, all the procedure knows is that it can access a
particular binding's value using a simple and efficient protocol; the
linker guarantees that the bindings are correctly attached to the
procedure so that the binding-access protocol finds the right object.

So, think of a "top-level environment" as a collection of viewpoints
into a space of objects; each closed procedure has its own viewpoint
into the space.  In this paradigm, what we currently think of as the
"top-level environment" becomes an internal data structure of the
linker: it is a map that tells the linker, for each procedure, what
name that procedure uses to refer to an object in the space (in the
case of a variable binding that is dynamically modified by the
program, the object is an implicit cell).  This map is a kind of
"schematic diagram" describing the "wires" that connect procedures and
other objects together to form a larger entity.

This idea provides a natural and very general substrate on which to
build module systems.  In particular, it is capable of supporting a
module system in which any definition in any module can be
interactively redefined; it is also capable of supporting multiple
different module systems on the same substrate.  When implemented on
such a substrate, a module system is largely a linguistic artifact: it
is a language that describes a portion of the linker's map.

Brian Harvey has argued that first-class environments are a simple and
powerful idea.  That's true, but I think they are more powerful than
necessary for most purposes, and they make it difficult to implement
efficient compilers and linkers.  I think the most useful purpose for
them is to build module systems, and for this purpose they are too
dynamic and not sufficiently expressive.  I think the real challenge
is to design a module language that provides a similar simplicity and
power, but in the context of a more general procedure-connection model
rather than a block-structured namespace model.



Sat, 19 Oct 1996 15:54:24 GMT  
 
 [ 200 post ]  Go to page: [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14]

 Relevant Pages 

1. I am going to start assembly programming

2. am i gonna go down in flames??

3. Am stupid and now going crazy...

4. Tk in C: I am going insane

5. Questions... I am new to scheme

6. Where is Scheme going?: A user point of view

7. A PC-Scheme Question: problem going back to edwin from main buffer

8. I am wondering what I am going to do with the following simulation error.

9. I am not deaf, but am I mute?

10. Windows Installer - a go/no-go (in)decision

11. Going (Gone) Nuts !!!

12. LOGO-L> go turtle go

 

 
Powered by phpBB® Forum Software