I think you might have to add environments and worlds to CL inorder to
add call/cc but am not sure about how to extend Lisp in this way? I am
not talking about writing a Scheme in ANSI CL--just adding the call/cc
function to ANSI CL using only ANSI CL code; to make it portable
between many different vendors versions of ANSI CL.

Jim Bender

"Franz Kafka" <Symbolics_XL1201_Sebek_Budo_Ka...@hotmail.com> wrote in
message news:b3b6b110.0304121624.1bec15d9@posting.google.com...

According to Graham, once the necessary groundwork is done, call/cc
itself can be written as one simple CL macro.

Don't confuse all of what I wrote above with Graham's six macros on
page 267 of his book.  Those six macros implement a crippled version of
continuations, which have many drawbacks compared to "real"
continuations.

Anyway, since common lisp doesn't give you access to continuation,
you'll have to transform ALL the scheme code to continuation passing
style to get the full effect. Possibly there are ready made packages for
doing that floating around, although i don't know of any particular one.

tom

Pascal

That is nonsense, except when speaking in the context of certain
implementations.  As it's a pretty common misconception (as is the
general idea that proper tail recursion is merely an "optimization"),
you might want to check out

http://zurich.ai.mit.edu/pipermail/rrrs-authors/1998-January/002231.html

And as it is easier to not perform this optimization than to do it, it
is also harder to retain a certain kind of debugging support when you
introduce that optimization.

Pascal

As for the link; you must take that whole message in context.  Guy
Steele is a language expert, experienced in many languages, and when
he talks of concepts and truths about concepts, you must understand
those truths in the context of which he is speaking.  I don't remember
the timing of when he worked on Scheme, and it doesn't really even
matter - the message you link to was clearly talking about Scheme,
and thus the context was clearly Scheme, otherwise his statement that
a goto is merely an impoverished function call would be ludicrous.  And
as I understand it, Scheme's "proper tail recursion" is truly not an
optimization, it is mandatory in Scheme.  But only in Scheme.

We've discussed before on comp.lang.lisp what tail call merging is and
isn't - Scheme doesn't define the most comprehensive tail call merging
requirement; as I understand it there are circumstances in Scheme where
tail calls are not merged, but since it is called out by definition in
Scheme, it poses no problem to Scheme users because they know when
their calls will not be merged.

Screamer sounds like a good compromise between the trivial and the
impossible.

Does Scheme have standard OO extensions? Is there a CLOS for Scheme?

Can I used Scheme to create Windows/ GNU\Linux executables?

Is there a standard Interface Managers, GUI builder for Scheme?

ANSI CL has CLIM -- or should have it.

<http://www-2.cs.cmu.edu/Groups/AI/html/faqs/lang/scheme/part1/faq-doc...>
seems pertinent.

(Another *possible* interpretation of the original question would be
`Would an implementation be able to provide Scheme-like continuations
without violating ANSI CL?'  To which the answer is also `Yes')

<http://download.plt-scheme.org/doc/203/html/mzscheme/mzscheme-Z-H-12....>

Furthermore the traditional (non-hygienic) define-macro way is also
supported by all the serious implementations (but it's not in R5RS).

Most serious Scheme implementation offer their own object systems.

There are a couple of object systems implemented in raw R5RS, which means
that the can be used every where. This includes Christian Queinnec's Meroon,
which is described in LiSP (LISP in Small Pieces). Jaffer also have a portable
implmentation in SLIB. For DrScheme's approach see
<http://download.plt-scheme.org/doc/203/html/mzlib/mzlib-Z-H-3.html#%_...>

There are to my knowledge no implementation og a GUI portable across implementations.
DrScheme's GUI works with no code changes on Windows, Linux and Machintosh, so there
are implementations that provide GUIs portable between operating systems.

For more info on Scheme see

  http://www.schemers.org
  http://srfi.schemers.org  ("extensions" of R5RS)

And my favorite:

  http://readscheme.org     (research papers about Scheme/Lisp)

But continuations of the type provided by scheme's call/cc (ie,
which you can call more than once and can call after returning
from the context once or more) make recovering from protocol
errors, a serious pain in most languages, totally trivial.  

If I could have had schemish call/cc-like continuations with
CL's standard binary operations, that would have been really neat.  

Hmmm.  I don't know exactly what "dynamic" means in the context
of continuations.  My mind grabbed onto the "like call/cc" part
of the question.  But if we're talking about extent, "like
call/cc" isn't dynamic extent, it's unlimited extent.  Is a
"dynamic continuation" one with dynamic extent?

    1.  implementing feature X in some language L
and
    2.  extending language L to support feature X

Suppose, for example, that feature X is "the syntax of C++".  You
can implement the syntax of C++ in just about any language L by
writing a C++ parser in L, but there aren't too many languages that
can be extended to support the syntax of C++ without introducing
many syntactic ambiguities and outright conflicts.

One reason my explanation was unsuccessful is that it is indeed
possible to extend the Common Lisp language with call/cc; the
thing that is impossible is to write an implementation of call/cc
in portable CL that will work in all conforming implementations
of CL with all legacy CL code.  Had I noticed that this thread was
cross-posted to comp.lang.lisp, I wouldn't have tried to say
anything so subtle.

The concept of proper tail recursion is not unique to Scheme.  That
and related concepts such as Appel's safe-for-space-complexity have
proved useful in quite a few languages.  Scheme is no longer the only
language that mandates proper tail recursion.

The compiler community has developed a separate tradition of tail call
optimization.  This has created some confusion, as many people assumed
that proper tail recursion is the same thing as tail call optimization.
They are not, however, the same.  There are cases in which it is not
possible to achieve the asymptotic space efficiency of proper tail
recursion while allocating variables on a stack.  In the compiler
community's definition of tail call optimization, these conflicts
between stack allocation and space efficiency are resolved by using
stack allocation at the expense of space efficiency.  Proper tail
recursion requires these conflicts to be resolved in favor of space
efficiency, at the expense of stack allocation.

So it is a technical fact that tail call optimization and proper tail
recursion are different things.  Nonetheless it remains easy for people
to confuse the two.  That is why people who understand the distinction
are inclined to object when someone proposes to replace the established
names of these concepts by names that are likely to create even more
confusion.

For example, it is not at all clear to me whether Duane intends for
his preferred terms, "tail merging" or "tail-call merging", to mean
tail call optimization or proper tail recursion.  It is not at all
clear that Duane even understands the difference.

ces...@qnci.net (William D Clinger) writes:

    William D Clinger. Proper tail recursion and space efficiency.
    In the Proceedings of the 1998 ACM Conference on Programming
    Language Design and Implementation, June 1998, pages 174-185.
    ftp://ftp.ccs.neu.edu/pub/people/will/tail.ps.gz

    Abstract: The IEEE/ANSI standard for Scheme requires implementations
    to be properly tail recursive. This ensures that portable code can
    rely upon the space efficiency of continuation-passing style and
    other idioms. On its face, proper tail recursion concerns the
    efficiency of procedure calls that occur within a tail context. When
    examined closely, proper tail recursion also depends upon the fact
    that garbage collection can be asymptotically more space-efficient
    than Algol-like stack allocation.

    Proper tail recursion is not the same as ad hoc tail call optimization
    in stack-based languages. Proper tail recursion often precludes stack
    allocation of variables, but yields a well-defined asymptotic space
    complexity that can be relied upon by portable programs.

    This paper offers a formal and implementation-independent definition
    of proper tail recursion for Scheme. It also shows how an entire
    family of reference implementations can be used to characterize
    related safe-for-space properties, and proves the asymptotic
    inequalities that hold between them.

I regard this paper as a commentary on the classic papers by Steele
and Sussman from the early 1970s.  If you read those papers carefully,
you will see that the property they called "proper tail recursion" has
to do with space efficiency.  Somewhere (and I regret that I don't
remember the exact citation) Steele actually wrote that it should be
possible to formalize proper tail recursion as a matter of asymptotic
space complexity.  Several later authors (Appel, Harper, Morrisette,
Felleisen) have said the same thing, often adding that it should be
trivial to do this.  The chief technical contribution of my paper is
that I actually did this trivial thing.

The motivations for my paper were twofold.  First of all, in addition
to the very smart people who had said the formalization of proper tail
recursion should be trivial, there were other very smart people who
said it couldn't be done.  I got tired of arguing with them, so I did
it.

Having done this trivial thing, I decided to use it to explain the
distinction between proper tail recursion as defined by Steele and
Sussman and the various tail call optimizations that had sprung up
in the compiler community.

The problem here is that Steele and Sussman were not all that careful
to distinguish the space efficiency property that they called proper
tail recursion from the implementation techniques that they used to
achieve that property.  The compiler community zeroed in on the
techniques without understanding the property.  In the process, the
compiler community added restrictions as necessary to prevent these
techniques from interfering with stack allocation, which they took
for granted, completely missing the point that these added restrictions
destroyed the property that Steele and Sussman were at such pains to
describe.  This happened even in the Lisp community, where the terms
"tail merging" and "tail call merging" were used to refer to various
optimizations, not to the space efficiency property.

On the other hand, there are a few notable papers in which the authors
understood full well that proper tail recursion is a space efficiency
property, and their concern is whether a proposed optimization is legal
with respect to that property (that is, does the optimization preserve
proper tail recursion?).  See for example the papers I cited by Appel,
Chase, Hanson, and Serrano and Feeley.  These papers give real-world
examples of the conflict between stack allocation (or some related
optimization) and proper tail recursion.

The examples in my paper aren't at all realistic; they were the simplest
I could contrive.  Here is the example I gave:

    (define (f n)
      (let ((v (make-vector n)))
        (if (zero? n)
            0
            (f (- n 1)))))

If v is stack-allocated, then this will not be properly tail-recursive.
This is not a convincing example, because most compilers (though not most
interpreters) would recognize that v isn't used, and wouldn't allocate
any storage for it at all.  But you can modify this example in various
ways to make it more convincing.  For example:

    (define (f v)
      (let* ((n (vector-length v 0))
             (v (make-vector (- n 1))))
        (if (zero? n)
            0
            (f v))))

This still isn't very convincing in Lisp-like languages, because the
location allocated for v in f is quite clearly dead once it has been
dereferenced to evaluate the actual parameter for the tail call to f.
To keep that location alive beyond a tail call in Lisp or Scheme, we'd
have to introduce a lambda expression that closes over v.  In some
other languages we might pass v by reference or pass its address.
Either way, it becomes clear that allocating v on a stack would
interfere with proper tail recursion.